糾錯編碼

在傳輸過程中發生錯誤後能在收端自行發現或糾正的碼。僅用來發現錯誤的碼一般常稱為檢錯碼。為使一種碼具有檢錯或糾錯能力，須對原碼字增加多餘的碼元，以擴大碼字之間的差別 ，即把原碼字按某種規則變成有一定剩餘度（見信源編碼）的碼字，並使每個碼字的碼之間有一定的關係。關係的建立稱為編碼。碼字到達收端後，可以根據編碼規則是否滿足以判定有無錯誤。當不能滿足時，按一定規則確定錯誤所在位置並予以糾正。糾錯並恢復原碼字的過程稱為譯碼。檢錯碼與其他手段結合使用，可以糾錯。發表論文指出，只要採用適當的糾錯碼，就可在多類信道上傳輸消息。自仙農的論文發表以來，人們經過持續不懈的努力已經找到多種好碼，可以滿足許多實用要求。但在理論上，仍存在一些問題未能解決。糾錯碼能夠檢錯或糾錯，主要是靠碼字之間有較大的差別。糾錯碼實現中最複雜的部分是譯碼，它是糾錯碼能否應用的關鍵。糾錯碼傳輸的都是數字信號。這既可用硬件實現，也可用軟件實現。

糾錯能力、編碼效率和解碼複雜性是衡量一個糾錯碼好壞的重要參數。

在構造糾錯碼時，將輸入信息分成k位一組進行編碼。若編出的n位長碼僅與本組的位信息k位有關，則稱這樣的碼為分組碼。由於這時用n位符號傳送了k位信息，所以編碼效率（碼率）為。若編出的位長碼不僅與本組的個信息位有關，而且與其前面若干組的信息位有關，則稱為網格碼，這種碼之所以稱為網格碼是因為用圖形分析時其圖形像網格或籬笆。線性網格碼在編碼運算時為卷積運算，所以又叫做卷積碼。

分組碼的碼長和碼字個數M是一個碼的主要構造參數。碼長為的碼中所有碼字的位數均為；若要用一個碼傳送比特信息，則碼字的個數M必須滿足。典型的分組碼是由位信息位和r位監督位組成的，這樣構成的碼一般稱為系統碼。

分組碼中應用最廣的線性分組碼。線性分組碼中的M個碼字之間具有一定線性約束關係，即這些碼字總體構成了n維線性空間的一個k維子空間。稱此k維子空間為（n，k）線性分組碼。線性系統碼的特點是每個碼字的前k位均由這個碼字所對應的信息位組成，並通過對這k位信息位的線性運算得到後面n—k是位監督位。

線性分組碼中應用最廣的是循環碼，循環碼的主要特徵是任何碼字在循環移位後個碼字。循環碼的優點在於其編碼和解碼手續比一般線性碼簡單，因而易於在設備上實現。在循環碼中，碼字可表示為多項式。循環碼的碼字多項式都可表示成為循環碼的生成多項式與這個碼字所代表的信息多項式的乘積，即，因此一個循環碼可以通過給出其生成多項式來規定。常用的循環碼有BCH碼和RS碼。

碼率為1/2、包含四種狀態的網格碼的網格圖

網格碼有多種描述方法，網格圖是常用方法之一，它能表示出編碼過程。一個碼率為1/2、包含四種狀態的網格碼的網格圖如圖所示。圖中00，01，10，11表示編碼器所具有的四種狀態，以“·”示出，從每一狀態出發都存在兩條支路，位於上面的一條支路對應於編碼器輸入為“0”的情況，位於下面的一條支路對應於編碼器輸入為“1”的情況，而每一支路上所列出的兩個二進位碼則表示相應的編碼輸出。因而可知，編碼輸出不僅決定於編碼器的當前輸入，還決定於編碼器的狀態，例如在圖中從“00”狀態出發；，若輸入的二進制數據序列為1011，則編碼器的狀態轉移過程為00→01→10→01→11，而相應的編碼輸出序列為11010010。在網格圖中任意兩條從同一狀態出發；，經不同的狀態轉移過程後又歸於另一相同狀態（該狀態也可與初始狀態相同）的路徑間的距離的最小值稱為碼的自由距離。如該圖中的為5。對於卷積碼來説，的計算可簡化為始於且終於零狀態的非全零路徑與全零路徑間距離的最小值。是表徵網格碼糾錯能力的重要參數。維特比算法是廣泛採用的網格碼的譯碼方法。由於網格碼的狀態越多，譯碼越複雜，所以狀態個數是度量網格碼譯碼複雜性的重要參數。一般説來可以通過增大譯碼複雜性來增加，從而提高碼的糾錯能力。

BCH碼、網格碼已被廣泛地應用於移動通信、衞星通信和頻帶數據傳輸中。RS碼也被廣泛應用於光盤的存儲中。

大多數糾錯碼是設計來糾隨機誤碼的，可以通過交織的方法使它適用於對突發誤碼的糾錯。交織是一種使得集中出現的突發誤碼在解碼時進行分散化的措施，從而使其不超出糾錯碼的糾錯能力範圍。

1．自動請求重發（ARQ） ^[1] 

採用這種方法時，當接收端檢測到所接收的信息有錯以後，通過反向信道向發送端要求重發原信息，直到接收端認可為止，從而達到糾正誤碼的目的。這種方法的優點是糾錯編解碼設備簡單，但需要具備反向信道，且實時性較差。

2．前向糾錯（FEC）

前向差錯控制編碼的基本做法是在發送端被傳輸的信息序列上附加一些監督碼元，這些多餘的監督碼元與信息碼元之間以某種確定的規則相互關聯(約束)。接收端按照既定的關聯規則檢驗信息碼元與監督碼元之間的關係，一旦傳輸過程中發生差錯，則信息碼元與監督碼元之間的關係將受到破壞，從而可以發現錯誤，乃至糾正錯誤。具體説就是接收端對接收到的碼字施加一定的算法，從而發現誤碼並予以糾正。這種方式的優點是不需要反向信道，糾錯編解碼的實時性較好。缺點是糾錯編解碼較複雜，且糾錯能力有限。

3．混合糾錯（HEC）

該方式是前兩種方式的結合。接收端對所接收的碼流中少量的誤碼可通過前向糾錯方式進行自動糾正；而對超過前向糾正能力的誤碼，但能檢測出來，則接收端通過反向信道請求發端重發，以此對錯碼加以糾正。

以上三種差錯控制方式可以用圖1來概括。無論採用那種糾錯方法，都要在原信息中插入冗餘碼才能實現糾錯或檢錯。由於前向糾錯方法簡單，不需要反向信道，且能實時實現。因此在實時圖像通信系統中，多采用前向糾錯的方法來進行對圖像信號和系統控制信號的差錯控制。

4．BCH糾錯編碼

實測表明，對圖像信息進行了BCH(511，493)的糾錯處理，通過增加4%的冗餘度信息可以將信道誤碼率由10－6改善到10－9，從而確保了圖像信息的可靠傳輸。

糾錯碼的實現框圖如圖2所示，圖像數據首先被分成一個個的493比特的數據組，組與組之間空18比特，有待於插入校驗位。圖像數據組進入BCH糾錯編碼單元，按照上述的BCH(511，493)的算法，算出18位校驗位。延時單元主要的目的就是補償BCH編碼所花費的時間，使得經編碼輸出的校驗位和相應的數據剛好對齊，然後將兩者複合起來形成一路經BCH糾錯編碼的圖像信號送至多路複用單元和音頻、數據信號進行多路複用。

圖1差錯控制方式

圖2糾錯編碼框圖

在接收端，解碼器對圖像進行BCH譯碼。在譯碼電路中，譯碼器根據18位校驗信號對相應的493位圖像信號進行驗算，如果圖像數據中有一位隨機誤碼，則通過這樣的校驗可以將它們自動糾正。如果有2位，則可以將它檢測出來。

5．比特交織

在實際應用中，還可以將比特交織和前向糾錯相結合，以期進一步提高糾錯能力，如圖3所示。FEC和編碼交織在分組前完成，在接收端通過反交織可以使突發錯誤分散開來，這樣，具有糾隨機錯誤能力的糾錯碼能糾突發錯誤，這在無線或分組視頻通信中特別有效。

圖3FEC和比特交織