text: 在計算機，電信，資訊理論和編碼理論中，糾錯碼是資訊傳輸中錯誤檢測與糾正的工具。它通常用在不可靠或嘈雜的通道中。資料傳送方利用糾錯碼中的冗餘資訊，使得接收方能夠檢測訊息傳輸中發生的錯誤，而且通常可以糾正這些錯誤而無需重新傳輸。美國數學家理查德·漢明程式碼。相比錯誤檢測，糾錯碼不僅能夠檢測到錯誤，而且可以將其更正。它的優點是在出現錯誤時不需要反向通道來請求重發資料，缺點是訊息中增加了固定開銷，因此需要更高的前向通道頻寬。因此，糾錯碼用於重傳成本高昂或無法實現的情況，例如單向通訊鏈路，時延較長的連結，以及以多播方式傳送給多個接收者的連結。比如，繞天王星執行的衛星，由於傳輸錯誤而造成的重發會造成5個小時的延遲。糾錯碼資訊通常新增到大容量儲存裝置中，以恢復損壞的資料，並廣泛用於調變解調器、固態硬碟，以及主存為 ECC 記憶體的系統中。接收機中的糾錯碼處理可以應用於數字位元流，也可以應用於數字調製載波的解調。對於後者，糾錯碼是接收器中類比數位轉換器的組成部分。維特比訊號，該訊號可用作反饋以微調模擬接收電子裝置。糾錯碼能夠糾正的錯誤位/丟失位的最大數量取決於它的的設計，因此，不同的糾錯碼適用於不同的環境。一般來說，能夠糾正大量錯誤的程式碼中有著更多的冗餘資訊，所以會需要更多頻寬進行傳輸，從而降低了有效位元率，且同時提高了接收到的有效信噪比。克勞德·夏農的有噪通道編碼定理回答了以下問題：若使用最有效的程式碼將解碼錯誤機率變為零，資料通訊還剩下多少頻寬？對於具有基本噪聲水平的通道，該定理給出了理論上的最大資訊傳輸速率。但是，該證明不具建設性，也就是說它並不能用來構建實現最大速率的程式碼。經過多年的研究，如今一些先進的糾錯碼系統，其速率已非常接近理論最大值。工作原理.糾錯碼的編碼方法如下：發信方利用演算法，向要傳輸的資訊新增冗餘位。這些冗餘位通常是將原始輸入位由複雜的函式轉換而成。原始資訊不一定原樣出現在輸出的編碼中；包含原始資訊的程式碼稱為系統程式碼，反之稱為非系統程式碼。下面是一個簡單糾錯碼的例子：將每個資料位傳送3次。這種編碼稱為重複碼。 透過嘈雜的頻道，接收器可能會收到8個不同版本的輸出，表：若收到的資訊非3個重複的數位，則以重複次數較多的數位為準。該糾錯碼最多糾正一位錯誤位，或兩位丟失位。雖然這種糾錯碼實施方便且應用廣泛，但這種三重模組冗餘的形式是效率較低的。更好的糾錯碼通常會檢查先前接收到的幾十位，或幾百位，由此判斷如何解碼當前的幾位。利用噪聲的“平均化”來減少錯誤.糾錯碼的使用對資訊噪聲產生的破壞有“平均化”的作用。由於每一個原始資料位生成了多於一個的傳輸符，儘管某些傳輸符可能遭到噪聲的破壞，接收方通常能夠依賴其它未損壞的，由相同原始位生成的接收符來獲取原本資料。由於這種效應，使用糾錯碼的數字通訊系統往往能夠在信噪比遠高於最小信噪比的情況下運轉。在運轉過程中，系統的信噪比永遠不會低於最小信噪比。當使用更強的，接近夏農極限的程式碼時，這種懸崖效應將變得更加明顯。有時，通道錯誤通常是突發型的。在這種情況下，可以使用交錯的糾錯碼來將資料編碼，這樣能夠降低所傳輸糾錯碼的懸崖效應。但是，這種方法也有侷限性，它比較適用於窄帶資料。大多數電信系統使用固定的通道程式碼，這樣的通道程式碼通常可以容忍預期的最壞誤位元速率；如果誤位元速率高於該值，則系統根本無法運轉。但是，有些系統能夠適應特定的通道錯誤條件：在一些混合式自動重送請求的例項中，錯誤率較低時系統使用固定的糾錯碼，而在錯誤率過高時切換到自動重傳請求。 自適應調變和編碼能夠應對多種錯誤率：當通道中的錯誤率較高時，在每個資料包中新增更多的糾錯位，而在不需要它們時將其刪除。糾錯碼的種類.糾錯碼分為兩大類：分組碼和卷積碼。分組碼適用於一連串固定長度的資料包，而每一種分組碼只能用於特定長度的資料包。實際用途中的分組碼一般使用硬解碼方式，所需時間為每一個數據包長度的多項式時間。分組碼有許多不同的型別，值得關注的有裡德-所羅門碼，它被廣泛的應用於光碟，DVD和硬碟驅動器中。經典分組碼的其他例子有格雷碼，BCH碼，和漢明碼。卷積碼適用於任意長度的位元流/符號流。接收方通常使用維特比演算法將其軟解碼，但有時也會用其他演算法。隨著卷積碼約束條件的長度增加，維特比解碼的解碼效率漸近最優；但作為代價，計算時間將以對數式增長。長度有限的卷積碼也可以看作一種“分組碼”，因為輸入資料是成組的；但是卷積碼的每一“組”長度不一，而分組碼的長度是固定的，且由其特定的代數性質而定。 卷積碼有幾種不同的終止方式，如“咬尾巴”。漢明糾錯碼一般用來糾正NAND快閃記憶體錯誤。它可以矯正一位錯誤或檢測兩位錯誤。漢明碼僅適用於相對可靠的單層單元NAND，較稠密的多層單元NAND需要能夠校正更多位的糾錯碼，例如BCH或裡德-所羅門碼 。NOR快閃記憶體通常不需要任何錯誤校正。分組碼通常使用硬決策演算法解碼，在這種決策方式下，每個輸入和輸出訊號都非1即0。而卷積碼則相反，使用如維特比，MAP或演算法之類的軟決策演算法進行解碼，該演算法用於離散化的模擬訊號，並且比硬判決解碼具有更高的糾錯效能。幾乎所有的經典分組碼都利用了有限域的代數性質。因此，經典分組碼也稱為代數碼。經典分組碼的檢錯或糾錯能力通常是事先預定的，而許多現代的分組碼並沒有這方面的保證；它們的能力是由誤位元速率來評估的。大多數前向糾錯碼僅糾正翻轉位，而不能糾正插入位或丟失位。在這種情況下，計算誤位元速率時應使用漢明距離。一些前向糾錯碼可以糾正插入位和丟失位，例如標記碼和水印碼。若使用此類程式碼，測量位元誤位元速率時使用萊文斯坦距離更加合適。可靠性和編位元速率的權衡利弊.糾錯碼的基本原理是以新增冗餘位的方法，來幫助解碼器尋回編碼前的原本訊息。糾錯碼系統的編位元速率指的是通訊包中，資訊位數與總位數之間的比率。接近零的低位元速率表示程式碼的糾錯能力強，反之，若糾錯碼有著接近1的大位元速率，則意味著程式碼的糾錯能力較弱。傳輸這些冗餘位時，必須消耗有限的通訊資源，這導致了可靠性和資料速率之間的相互衝突。在極端情況下，具有低傳輸效率的強程式碼會導致接收器信噪比的大幅增加，這樣降低了誤位元速率，但同時也降低了有效資料的速率。另一方面，不使用任何糾錯碼將整個通道用於資訊傳輸目的，這樣效率極高但沒有任何糾錯能力。具有極低錯誤率的糾錯碼，能夠達到怎樣的資訊傳輸效率？克勞德·夏農的第二定理給出了答案，根據該定理，若錯誤率趨於零，糾錯碼的速率最大可以達到通道容量 。他的證明使用了高斯隨機編碼，並不適用於實際應用。夏農給出了一個速率的上限，而學界為了設計出達到速率上限的糾錯碼，踏上了漫長的旅途。如今，有些糾錯碼幾乎可以達到夏農極限，但是通常實施起來極其複雜。常見的幾種糾錯碼必須在糾錯效能和計算複雜度之間取得平衡。通常，它們的引數可以適用特定區間以內的編位元速率，可以根據不同的情況自動選擇較優的編位元速率。這樣可以降低冗餘位對資料速率的影響，同時減少錯誤。最佳化編位元速率的另一個準則是在低誤位元速率的情況下儘量減少重傳次數，以降低通訊的能源成本。如上文中的許多例子所示，“不定式”一詞並不表明它的極限不存在。在許多情況下，我們可以使用洛必達法則，代數方程求解，或其他方法計算極限。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 糾錯碼
metadata: https://zh.wikipedia.org/wiki?curid=6534688