糾錯編碼概念

基本介紹

• 中文名：糾錯編碼概念
• 外文名：Errorcorrection coding concept
• 所屬技術：電信技術

1．差錯控制碼的分類

按不同的方法，差錯控制碼有不同的分類。

（1）按碼元的取值分，有二進制碼和多進制碼。

（2）按處理差錯的特點分，有檢錯碼和糾錯碼，糾錯碼可分為糾隨機錯誤的碼和糾突發錯誤的碼。

（3）按信息元與校驗元之間的關係分，有線性碼和非線性碼；系統碼和非系統碼。

線性碼能用線性方程式表達信息元和校驗元之間的關係，而非線性碼則不能。

系統碼是指信息元部分和校驗元部分能顯然分開的碼，而非系統碼的信息元和校驗元是相互錯亂排列的。

（4）按校驗元所校驗的信息元的範圍分，有分組碼和卷積碼。分組碼中，每一碼組中包括一定數量的信息元和校驗元，每一碼組的校驗元只與本組信元發生關係。卷積碼則把本組的信息元和校驗元和前後若干組的碼元連環起來，所以又叫連環碼。

線性分組碼如果還具有循環移位的特性，則為循環碼，循環碼中又包含BCH碼等。

2．幾個術語

一般地來說，碼的檢錯和糾錯能力是用冗餘度來換取的。拿最簡單的重複碼來舉例，要傳送A和B兩個訊息，我們可以用“1”表示A，“0”表示B。但是，這樣的碼是沒有任何抗干擾能力的。如果在傳輸的過程中“1”錯成了“0”，或“0”錯成了“1”，接收端就會收到錯誤的訊息。如果我們用“11”表示A，“00”表示B，如果錯1位，即“11”錯成“10”或“01”；“00”錯成“01”或“10”，接收端解碼器就知道傳輸出錯，因為只規定了“00”為B，“11”為A。但如果兩位都錯，即“11”錯成“00”，或“00”錯成“11”則解碼器又無從識別出傳輸差錯了，也就是此時的碼有檢一位錯的能力。

（1）禁用碼字和許用碼字

在上面的例子中規定了用“11”表示A，“00”表示B，稱“11”和“00”為許用碼字，而“01”，“10”則為禁用碼字。

同樣為了進一步提高碼的抗干擾能力，可以用“111”和“000”分別來表示A和B，這時“000”，“111”為許用碼字，而餘下的“001”，“010”，“100”，“101”，“110”“011”等6個碼組則為禁用碼字。很顯然，此時的碼組具有檢兩位錯的功能。或者如果根據“最大似然”的解碼法則來解碼，即碼組中如有2個和3個“0”則判為“000”碼字，有2個和3個“1”則判為“111”碼字，此時就有糾1位錯的能力。可見要使碼的糾錯、檢錯的能力強，就要多加校驗碼元，但信道的傳輸效率也就下降得多。

以上的兩種碼可分別用(2，1)，(3，1)來表示，括弧內的前一位數表示碼長，後一位數表示信息位數，因此碼長為n，信息位為k位的碼可表示為(n,k)。

（2）“漢明距離”或“最小碼距”

從以上的例子可看出，一個(n,k)碼的抗干擾能力，完全取決於任二個碼字間對應碼元數值不同的位數。在信道編碼中，把碼字中非零碼元的數目定義為碼的重量，簡稱碼重，如“011”碼重為2。把二個碼字中對應碼元數值不同的位數定義為兩碼字的距離。在一種包括若干碼字c₁,c₂,……,c_n的碼中，所有這些碼字相互間碼距的最小值，稱為該碼的最小距離或漢明距離，簡稱碼距，用d_min表示。它是衡量碼的抗干擾能力大小的標準。d_min越大，抗干擾能力越強。圖1給出了由於3位碼元構成的8個碼字的碼，其最小碼距為1。

圖1 碼距的幾何表示

（3）錯誤圖樣和錯誤長度

目前傳輸大多為二進制，所以這裡只討論二進制數字通信中的差錯控制和抗干擾碼。

二進制數字序列中0和1按下述規則進行運算。

模二加：0+0=1+1=0，1+0=0+1=1

模二乘：0·0=1·0=0·1=0，1·1=1

如果傳送端傳送的碼字是T：11111111，而接收端收到的碼字R：10010011。傳送序列T之所以會出現差錯變成R，是因為在傳輸的途中受到了干擾，疊加了錯誤。二進制出錯無外乎1→0，0→1，即序列中任何一位，只要疊加了一個“1”，則該位就出錯，疊加了“0”，則不出錯。在這裡T疊加了序列：01101100。我們把它稱為錯誤圖樣E，即：

R=T+E

在E中從第一個“1”至最後一個“1”的長度，稱為錯誤長度，本例中錯誤長度為5。

由於信道干擾所造成的錯誤，可以出現在碼字中的任何一位，而且可以同時出現一位、兩位，直至n位錯誤。所以若傳送碼字長為n，則可能產生的錯誤圖樣數有2ⁿ－1種。

3．檢錯能力與糾錯能力

（1）檢測e個錯誤，要求最小碼距

d_min≥e+1

也就是說一個碼組的碼距為d_min，則它能檢出 小於或等於d_min－1個錯誤碼元。

上式可用圖2.16(a)來說明，設碼組中A、B兩碼字有最小距離d_min。若碼字A發生e位錯誤，則可以認為此時錯碼位於以A為圓心，e為半徑的圓上，只要錯誤位數不大於e，錯碼的位置就不會超出該圓，由於碼組的最小距離d_min為e+1，所以圓中不會有其他碼字，即錯碼不會和B及其他碼字混淆，可以識別。

（2）糾正t個錯誤，要求最小碼距

d_min≥2t +1

在圖2.16(b)中，以A和B為圓心，t為半徑各作一個圓。由於d_min=2t+1，所以這二個圓距離為1。若出現的錯誤位數小於或等於t，那么A碼出錯後的錯誤碼字，只能落在以A為圓心的這個圓內或圓周上，不可能落在此圓外；同理，對於B碼也一樣。所以，可以把落在A圓中的錯碼譯為A，B圓中的錯碼譯為B，而不會產生錯譯，但如果錯碼的位數大於t，例如為t+1，那么這個錯碼就會落在B圓上，或其他碼的圓上，從而產生錯譯。所以要能糾t位錯，碼距不能小於2t+1。

（3）糾正t個錯，同時又能檢測e個錯，要求最小碼距

d_min≥e+t+1

在圖2中，若出現的錯誤位數小於等於t，則A碼的錯碼不會超出以A為圓心t為半徑的圓周，B碼也一樣，從而可以各自糾正錯誤。但如果錯誤位數大於t，拿A碼來說，它的錯碼就要超出A圓，但由於碼距為e+t+1，只要差錯的位數不大於e，從圖中可看出A的錯碼仍不會落到B圓或其他碼的圓上去，因此可以發現差錯，但如果差錯位數為e+1，則可能落到B圓上或其他碼的圓上，從而被作為B碼或其他碼糾正，產生錯糾，所以要糾正t位錯同時又能檢出e位錯，d_min不能小於e+t+1。

圖2 碼距與糾檢錯能力的關係