工程熱力學

[拼音]：jiucuoma

[英文]：error correcting code

在傳輸過程中發生錯誤後能在收端自行發現或糾正的碼。僅用來發現錯誤的碼一般常稱為檢錯碼。糾錯編碼又稱通道編碼，它與信源編碼是資訊傳輸的兩個方面。它們之間存在對偶的關係。應用通道譯碼直接對一些自然資訊進行處理，可以去掉剩餘度，以達到壓縮資料的目的。

為了使一種碼具有檢錯或糾錯能力，必須對原碼字增加多餘的碼元，以擴大碼字之間的差別，使一個碼字在一定數目內的碼元上發生錯誤時，不致錯成另一個碼字。準確地說，即把原碼字按某種規則變成有一定剩餘度的碼字，並使每個碼字的碼元間有一定的關係。關係的建立稱為編碼。碼字到達收端後，用編碼時所用的規則去檢驗。如果沒有錯誤，則原規則一定滿足，否則就不滿足。由此可以根據編碼規則是否滿足以判定有無錯誤。當不能滿足時，在可糾能力之內按一定的規則確定錯誤所在的位置，並予以糾正。糾錯並恢復原碼字的過程稱為譯碼；碼元間的關係為線性時，稱為線性碼；否則稱為非線性碼。檢錯碼與其他手段結合使用，可以糾錯。檢錯反饋重發系統（ARQ系統）就是一例。

在構造糾錯碼時，將輸入資訊分成 k位一組以進行編碼。若編出的校驗位僅與本組的資訊位有關，則稱這樣的碼為分組碼。若不僅與本組的 k個資訊位有關，而且與前若干組的資訊位有關，則稱為格碼。這種碼之所以稱為格碼，是因為用圖形分析時它象籬笆或格架。線性格碼在運算時為卷積運算，所以叫卷積碼。

發展過程

C.E.仙農在1948年發表在《通訊的數學理論》一文中的通道編碼定理指出：只要採用適當的糾錯碼，就可在多類通道上傳輸訊息，其誤位元速率pe可以任意小

(1)

式中n為碼長；Er(R)為資訊率R的函式，與通道有關。當R小於通道容量C時，Er(R)為正值。可惜的是這一定理僅僅指出理論上可以達到的目標，而未能給出構造性的實現方法。自仙農的論文發表以來，人們經過持續不懈的努力已找到多種好碼，可以滿足許多實用要求。但在理論上，仍存在一些問題未能解決。

R.W.漢明於1950年首先給出可以糾正一個獨立錯誤的線性分組碼──漢明碼。差不多與此同時E.戈雷給出一種可以糾正三個錯誤的完備碼。完備碼雖然十分罕見，但有較大實用意義。1954年D.E.莫勒提出一種能糾正多個錯誤的碼；I.S.裡德則立即給出它的譯碼方法，用的是擇多判決法，這種碼常稱為RM碼。1957年，E.普勒齊引入了迴圈碼的概念。1959～1960年出現了BCH碼，引進有限域的概念，解決了迴圈碼的構造和效能估計等基本問題。後來成為線性分組碼中最重要的一類碼。它能糾正多個錯誤，且在實用範圍內接近通道編碼定理所指出的誤位元速率值。但當 n增大時，其誤位元速率不能呈指數下降。BCH碼的譯碼問題是W.W.彼得森解決的;錢天聞則提供了一種系統地搜尋根的方法。1967年，E.R.伯利坎普提出一種迭代演算法，大大簡化了譯碼，使糾錯碼趨於實用。1970年В.Д.戈帕提出一種線性分組碼的構造方法，原則上它可以達到吉爾伯特限，實現了理論上預期的目標。但至今仍未解決如何具體構造這種碼的問題。

卷積碼最早由P.伊萊亞斯於1955年提出。它的糾錯能力較強，裝置複雜程度與分組碼大體相當。首先獲得成功的譯碼方法是序列譯碼。1967年A.J.維特比提出的譯碼演算法，能較好地按最大似然準則譯碼，且在許多領域中均可應用。卷積碼還可用代數方法譯碼。它的裝置雖較簡單，但效能較差。卷積碼在理論上不如分組碼成熟，所用的工具也比較多樣，尚缺乏系統的、統一的方法處理。

分組碼和卷積碼不但可以用來糾正獨立錯誤，而且可以用來恢復刪除錯誤和糾正突發錯誤。如分組碼中有裡德-索洛蒙碼，法爾碼等；卷積碼中有巖垂碼及擴散卷積碼等。

為了實現低的誤位元速率，根據式(1)，要求碼長n較大。但已知的大多數碼，當 n變大時不是效能欠佳或者難以構造，就是譯碼過分複雜，不容易實現。但是，可以利用好的碼進行級連，以得到效能更好的碼。級連碼的內碼和外碼，用分組碼和卷積碼都可以。這在深空通訊中應用較多。

基本原理和效能引數

糾錯碼能夠檢錯或糾錯，主要是靠碼字之間有較大的差別。這可用碼字之間的漢明距離 d(x，y)來衡量。它的定義為碼字x與y之間的對應位取不同值的碼元個數。一種糾錯碼的最小距離 d定義為該種碼中任兩個碼字之間的距離的最小值。一種碼要能發現e個錯誤，它的最小距離d應不小於e+1。若要能糾正t個錯誤，則d應不小於2t+1。一個碼字中非零碼元的個數，稱為此碼字的漢明重量。一種碼中非零碼字的重量的最小值，稱為該碼的最小重量。對線性碼來說，一種碼的最小重量與其最小距離在數值上是相等的。

在構造線性碼時，數字上是從n維空間中選一k維子空間，且使此子空間內各非零碼字的重量儘可能大。當構造迴圈碼時，可進一步將每一碼字看成一多項式，將整個碼看成是多項式環中的理想，這一理想是主理想，故可由生成多項式決定；而多項式完全可由它的根規定。這樣，就容易對碼進行構造和分析。這是BCH碼等迴圈碼構造的出發點。一般地說，構造一種碼時，均設法將它與某種代數結構相聯絡，以便對它進行描述，進而推導它的性質，估計它的效能和給出它的譯碼方法。若一種碼的碼長為n，碼字數為M，或資訊位為h，以及最小距離為d，則可把此碼記作[n，M，d]碼。若此碼為線性碼，常簡記作(n，k)或(n，k，d)碼。人們還常用R=log2M/n表示碼的資訊率或簡稱位元速率，單位為位元/碼元。R越大，則每個碼元所攜帶的資訊量越大，編碼效率越高。

實現

糾錯碼實現中最複雜的部分是譯碼。它是糾錯碼能否應用的關鍵。根據式(1)，採用的碼長n越大，則誤位元速率越小。但n越大，編譯碼裝置也越複雜，且延遲也越大。人們希望找到的譯碼方法是:誤位元速率隨碼長n的增加按指數規律下降;譯碼的複雜程度隨碼長n的增加接近線性地增加；譯碼的計算量則與碼長 n基本無關。可惜，已經找到的碼能滿足這樣要求的很少。不過由於大規模積體電路的發展，既使應用比較複雜的但效能良好的碼，成本也並不太高。因此，糾錯碼的應用越來越廣泛。

糾錯碼傳輸的都是數字訊號。這既可用硬體實現，也可用軟體實現。前者主要用各種數位電路，主要是採用大規模積體電路。軟體實現特別適合計算機通訊網等場合。因為這時可以直接利用網中的計算機進行編碼和譯碼，不需要另加專用裝置。硬體實現的速度較高，比軟體可快幾個數量級。

在傳信率一定的情況下，如果採用糾錯碼提高可靠性，要求通道的傳輸率增加，頻寬加大。因此，糾錯碼主要用於功率受限制而頻寬較大的通道，如衛星、散射等系統中。糾錯碼還用在一些可靠性要求較高，但裝置或器件的可靠性較差，而餘量較大的場合，如磁帶、磁碟和半導體儲存器等。

在分組碼的研究中，譜分析的方法受到人們的重視。糾同步錯誤碼、算術碼、不對稱碼、不等錯誤糾正碼等，也得到較多的研究。

參考書目

萬哲先：《代數與編碼》，科學出版社，北京，1976。

W.W.Peterson， Error-Correcting Codes，MIT Press，Cambridge，Mass.，1961.

E.R.Berlekamp， Algebraic Coding Theory，McGraw-Hill，New York，1968.