4糾錯編碼的基本原理

1、4.1.4 糾錯編碼的基本原理,1、 基本概念為了方便對差錯編碼原理進行敘述，下面先介紹一些基本術(shù)語。信息碼元——指進行差錯編碼前送入的原始信息編碼。 監(jiān)督碼元——指經(jīng)過差錯編碼后在信息碼元基礎(chǔ)上增加的冗余碼元。,,碼字（組）——由信息碼元和監(jiān)督碼元組成的，具有一定長度的編碼組合。 碼集——不同信息碼元經(jīng)差錯編碼后形成的多個碼字組成的集合。 碼重——碼字的重量，即一個碼字中“1”碼的個數(shù)。通常用W表示。例如：碼字100110

2、00的 碼重W=3，而碼字00000000的碼重W=0。同理：1001111001， 1100110111,,碼距——所謂碼元距離就是兩個碼組中對應(yīng)碼位上碼元不同的個數(shù)（也稱漢明距）。碼距反映的是碼組之間的差異程度，比如，00和01兩組碼的碼距為1；011和100的碼距為3。11000 與 10011之間的距離d=3。碼字10011001和11110101之間的碼距為4。 最小碼距——碼集中所有碼字之間碼距的最小值即稱為最小碼距

3、，用 表示。例如：若碼集包含的碼字有10010，00011，和11000，則各碼字兩兩之間的碼距分別如下：,,10010和00011之間 10010和11000之間 00011和11000之間 因此該碼集的最小碼距為2，即 。 000、001、110三個碼組相比較，碼距有1和2兩個值 最小碼距是碼的一個重要參數(shù)， 它是衡量碼檢錯、糾錯能力的

4、依據(jù)。,2. 分組碼 分組碼一般可用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元， 組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應(yīng)地可得到2k個不同的碼字，稱為許用碼組。其余 2n-2k個碼字未被選用，稱為禁用碼組。（7，4） （9，5

5、）,k,r,,n,3、編碼糾檢錯能力與最小碼距之間的關(guān)系,數(shù)字通信系統(tǒng)中送入信道的信息都是“0”“1”組合的數(shù)字信號，例如：待傳送的信息是“晴”和“雨”，則只需一位數(shù)字編碼就可以表示。若用“1”表示“晴”，“0”表示“雨”。當(dāng)“0”“1”形式的信息在信道中傳輸時將0錯成1或?qū)?錯成0時，由于發(fā)生差錯后的信息編碼狀態(tài)是發(fā)送端可能出現(xiàn)的狀態(tài)，因此接收端無法發(fā)現(xiàn)差錯。,,但是如果發(fā)送信息送進信道之前，在每個編碼之后附加一位冗余碼，變成用兩位編

6、碼“11“表示”晴“，“00”表示“雨”，則在傳輸過程中由于干擾造成信息編碼中一位碼發(fā)生差錯，錯成“10”（或“01”）時，由于“10”或“01”都是發(fā)送端不可能出現(xiàn)的編碼，接收端就能發(fā)現(xiàn)差錯，但此時并不能判斷出差錯是第一比特還是第二比特，因此不能自動糾錯許用碼組 00 11禁用碼組 10 01,,若繼續(xù)增加冗余碼位數(shù)，用“111”表示“晴”，“000”表示“雨”，當(dāng)編碼在傳輸中出現(xiàn)1位或2位碼差

7、錯（如錯成001或101等編碼）時，接收端都能檢測到，并能確定只有1位碼差錯時錯誤碼位的位置，此時這種編碼方式可以檢測1位或2位差錯，并能糾正單個的誤碼。許用碼組：000， 111禁用碼組：001 010 011 100 101 110,,由上例的分析可見，冗余碼位數(shù)增加后，編碼的抗干擾能力增強。這主要是因為冗余碼位數(shù)增加后，發(fā)送端使用的碼集中，碼字之間最小碼距 增大。由于 反映了

8、碼集中每兩個碼字之間的差別程度，如果 越大，從一個編碼錯成另一個編碼的可能性越小，則其檢錯、糾錯能力也就越強。因此最小碼距是衡量差錯控制編碼糾、檢錯能力大小的標志。一般情況下，差錯編碼的糾錯能力及檢錯能力與最小碼距之間的關(guān)系如下：,4. 檢錯和糾錯能力,碼的最小距離d0直接關(guān)系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi): (1) 檢測e個隨機錯誤，則要求碼的最小距離d0≥e+1;

9、 A 0 1 2 3 B A 0 1 2 3………………e B,,,B,A0,,(2) 糾正t個隨機錯誤， 則要求碼的最小距離d0≥2t+1;

10、 2 3 4 5 t t

11、 2t 1 2t,,1,,,,,,,(3) 糾正t個同時檢測e個隨機錯誤，則要求碼的最小距離d0≥t+e+1。 (e ≥ t)例如： d0=3， 或者4， 或者5,,,,,,,,,t,,1,e,A,B,,,檢1位糾1位

12、 檢出2位，糾正1位 檢2糾2,,例：已知四個碼組為 （110001000） （100010111） （000101111）

13、 （001011110）若將此碼用于檢錯最多可以檢出多少位錯嗎？若用于糾錯，最多糾正幾位？若同時用于檢錯和糾錯，能檢出幾位，糾正幾位？,3. 編碼效率 用差錯控制編碼提高通信系統(tǒng)的可靠性， 是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:R=k/n其中, k是信息元的個數(shù)，n為碼長。 對糾錯碼的基本要求是: 檢錯和糾錯能力盡量強； 編碼效率盡量高；編

14、碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。,,,4.2 常用的幾種簡單分組碼,1、 奇偶監(jiān)督碼,是一種最簡單的差錯編碼又稱奇偶檢驗碼。編碼方法：奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得該碼字中連同監(jiān)督碼在內(nèi)的“1”的個數(shù)為奇數(shù)（稱為奇校驗）或偶數(shù)（稱為偶校驗）?；蛘哒f，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼。,,例如：對碼組01101001進行偶校驗的監(jiān)督碼位

15、為0，對碼組10100000進行奇校驗的監(jiān)督碼為1。設(shè) 是同一碼組內(nèi)各位碼元， 是監(jiān)督碼元，其余碼位都是信息碼元，則偶校驗時應(yīng)滿足,,,,接收端譯碼時，對各碼元進行模二加運算，其結(jié)果為0（偶監(jiān)督碼）如果傳輸過程中碼組任何一位發(fā)生了錯誤，則收到的碼組不滿足偶檢驗關(guān)系，因此就能發(fā)現(xiàn)錯誤。偶監(jiān)督碼的編碼規(guī)則可以用公式表示（設(shè)碼組長度為n，表示為

16、 ）監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定,,,,對于奇校驗碼必須保證 因此式中的監(jiān)督碼可以用下式求出奇偶監(jiān)督碼的編碼效率R為,在接收端按照相同的規(guī)律進行檢測，若檢測到與規(guī)律不符，則說明傳輸中有差錯產(chǎn)生，奇偶監(jiān)督碼的檢錯能力為只能檢出奇數(shù)位差錯，不能檢測出偶數(shù)位差錯，也不能判斷出差錯的具體碼元，故奇偶檢驗碼只有一定檢錯能力而不具備糾錯能力。但利用奇偶檢驗碼檢測單個差

17、錯的效果還是令人滿意的，因此在計算機數(shù)據(jù)傳輸及SDH傳輸技術(shù)中得到廣泛的應(yīng)用。,1 0 1 0 0 0 1 0 有錯1 1 1 0 0 1 1 0 有錯1 0 1 0 0 1 1 0 不能確定,1 0 1 1 0 0 1 0,,2、二維奇偶監(jiān)督碼又行列奇偶校驗碼或者水平垂直奇偶校驗碼，還稱作方陣碼，它是將若干信息碼字按照每個碼字一行排列成若干行，使每個碼字中相同的碼位均對齊在同一列中，形成矩陣形式。然后對每一行和每一列

18、的碼元均進行奇校驗或偶校驗，并將校驗結(jié)果附加在每一行及每一列碼元之后。例如：對6個ASCII信息碼進行行列奇偶校驗的結(jié)果如下：,,方陣碼不但能檢測出某一行某一列所有奇數(shù)個錯誤, 有時還能檢測出某偶數(shù)個錯誤 信息碼元 監(jiān)督碼元 信息碼元 監(jiān)督碼元 1 0 1 1 0 0 0 1

19、 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1

20、 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1監(jiān)督碼元 1 0 1 1 0 0 0 1

21、1 0 1 1 0 0 0 1適用于檢測突發(fā)錯誤,能糾錯:碼組中存在僅一行中有奇數(shù)個錯誤時,能夠確定錯碼的位置,行列奇偶監(jiān)督碼不但能檢測出某一行或某一列的所有奇數(shù)個錯誤，有時還能檢測出某些偶數(shù)個錯誤。,,但對于以矩陣形式出現(xiàn)的偶數(shù)位差錯，行列奇偶校驗碼是檢測不出來的。此外，通過水平和垂直兩個方向上的校驗，它能夠確定某一行或列中出現(xiàn)的單個差錯碼位置，因此行列奇偶校驗碼具有對單個差錯的糾錯能力。,（3） 恒比碼(等重碼),恒

22、比碼的編碼原則是從確定碼長的碼組中挑選那些“1”和“0”個數(shù)的比值一樣的碼組作為許用碼組。這種碼通過計算接收碼組中“1”的數(shù)目是否正確，就可檢測出有無錯誤。 五單位數(shù)字保護電碼 碼字長度為5，只選用碼字中含有三個“1”和兩個“0”的碼字作為許用碼字來表示10個阿拉伯?dāng)?shù)字1，2，…，9，0，這種碼亦稱“5中取3碼”。,中文電報編碼首先將每一個單字編碼為四位十進制數(shù)字，再將每一位十進制數(shù)字用二進制的五單位數(shù)

23、字保護碼表示。 通 信 6639 020710101 10101 10110 10011 01101 11001 01101 11100 國際電報通信中廣泛采用的是“7中取3碼”，許用碼字共有個，可分別表示26個字母和其它的一些符號。,,4、正反碼編碼的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼是信息碼的重復(fù)還是反碼，由信息碼中1的個數(shù)而定。例：1011010110 （重復(fù)）

24、 0011011001 （反碼）譯碼：接收碼組中信息位和監(jiān)督位按位模2相加若接收碼組的信息位中有奇數(shù)個1，則合成的碼組為檢驗碼組若接收碼組的信息位中有偶數(shù)個1，則合成的碼組的反碼為檢驗碼組,,,檢驗碼組全為0，無錯碼有4個1，1個0則信息碼組中有一位錯碼，其位置對應(yīng)檢驗碼組中0的位置有4個0，1個1則監(jiān)督碼中有一位錯碼，其位置對應(yīng)檢驗碼組中1的位置例：10010 （收到碼組為1001010110）

25、 10110 00100 11011001100100101111 10000其他組合，錯碼多于一個,,,,,,檢糾錯能力：長度為10的正反碼有糾正一位錯碼的能力，并能檢測出全部兩位以下的錯誤，和大部分兩位以上的錯誤。編碼效率：5/10=1/25、群計數(shù)碼群計數(shù)碼是將信息碼元分組后，計算每組碼元中1的個數(shù)，然后將這個數(shù)目的二進制表示為