4糾錯(cuò)編碼的基本原理

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

2、00的 碼重W=3，而碼字00000000的碼重W=0。同理：1001111001， 1100110111,,碼距——所謂碼元距離就是兩個(gè)碼組中對(duì)應(yīng)碼位上碼元不同的個(gè)數(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三個(gè)碼組相比較，碼距有1和2兩個(gè)值 最小碼距是碼的一個(gè)重要參數(shù)， 它是衡量碼檢錯(cuò)、糾錯(cuò)能力的

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

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

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

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

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

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

10、 2 3 4 5 t t

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

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

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

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

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

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

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

18、的碼元均進(jìn)行奇校驗(yàn)或偶校驗(yàn)，并將校驗(yàn)結(jié)果附加在每一行及每一列碼元之后。例如：對(duì)6個(gè)ASCII信息碼進(jìn)行行列奇偶校驗(yàn)的結(jié)果如下：,,方陣碼不但能檢測(cè)出某一行某一列所有奇數(shù)個(gè)錯(cuò)誤, 有時(shí)還能檢測(cè)出某偶數(shù)個(gè)錯(cuò)誤 信息碼元 監(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適用于檢測(cè)突發(fā)錯(cuò)誤,能糾錯(cuò):碼組中存在僅一行中有奇數(shù)個(gè)錯(cuò)誤時(shí),能夠確定錯(cuò)碼的位置,行列奇偶監(jiān)督碼不但能檢測(cè)出某一行或某一列的所有奇數(shù)個(gè)錯(cuò)誤，有時(shí)還能檢測(cè)出某些偶數(shù)個(gè)錯(cuò)誤。,,但對(duì)于以矩陣形式出現(xiàn)的偶數(shù)位差錯(cuò)，行列奇偶校驗(yàn)碼是檢測(cè)不出來(lái)的。此外，通過(guò)水平和垂直兩個(gè)方向上的校驗(yàn)，它能夠確定某一行或列中出現(xiàn)的單個(gè)差錯(cuò)碼位置，因此行列奇偶校驗(yàn)碼具有對(duì)單個(gè)差錯(cuò)的糾錯(cuò)能力。,（3） 恒比碼(等重碼),恒

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

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

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

25、 10110 00100 11011001100100101111 10000其他組合，錯(cuò)碼多于一個(gè),,,,,,檢糾錯(cuò)能力：長(zhǎng)度為10的正反碼有糾正一位錯(cuò)碼的能力，并能檢測(cè)出全部?jī)晌灰韵碌腻e(cuò)誤，和大部分兩位以上的錯(cuò)誤。編碼效率：5/10=1/25、群計(jì)數(shù)碼群計(jì)數(shù)碼是將信息碼元分組后，計(jì)算每組碼元中1的個(gè)數(shù)，然后將這個(gè)數(shù)目的二進(jìn)制表示為