糾錯編碼的基本原理.ppt

糾錯編碼的基本原理,1、 基本概念 為了方便對差錯編碼原理進行敘述，下面先介紹一些基本術語。 信息碼元指進行差錯編碼前送入的原始信息編碼。 監(jiān)督碼元指經(jīng)過差錯編碼后在信息碼元基礎上增加的冗余碼元。,碼字（組）由信息碼元和監(jiān)督碼元組成的，具有一定長度的編碼組合。 碼集不同信息碼元經(jīng)差錯編碼后形成的多個碼字組成的集合。 碼重碼字的重量，即一個碼字中“1”碼的個數(shù)。通常用W表示。 例如：碼字10011000的 碼重W=3，而碼字00000000的碼重W=0。同理：1001111001， 1100110111,碼距所謂碼元距離就是兩個碼組中對應碼位上碼元不同的個數(shù)（也稱漢明距）。碼距反映的是碼組之間的差異程度，比如，00和01兩組碼的碼距為1；011和100的碼距為3。11000 與 10011之間的距離d=3。碼字10011001和11110101之間的碼距為4。 最小碼距碼集中所有碼字之間碼距的最小值即稱為最小碼距，用 表示。 例如：若碼集包含的碼字有10010，00011，和11000，則各碼字兩兩之間的碼距分別如下：,10010和00011之間 10010和11000之間 00011和11000之間 因此該碼集的最小碼距為2，即 。 000、001、110三個碼組相比較，碼距有1和2兩個值 最小碼距是碼的一個重要參數(shù)， 它是衡量碼檢錯、糾錯能力的依據(jù)。,2. 分組碼 分組碼一般可用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元， 組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余 2n-2k個碼字未被選用，稱為禁用碼組。（7，4） （9，5）,k,r,n,3、編碼糾檢錯能力與最小碼距之間的關系,數(shù)字通信系統(tǒng)中送入信道的信息都是“0”“1”組合的數(shù)字信號，例如：待傳送的信息是“晴”和“雨”，則只需一位數(shù)字編碼就可以表示。若用“1”表示“晴”，“0”表示“雨”。當“0”“1”形式的信息在信道中傳輸時將0錯成1或?qū)?錯成0時，由于發(fā)生差錯后的信息編碼狀態(tài)是發(fā)送端可能出現(xiàn)的狀態(tài)，因此接收端無法發(fā)現(xiàn)差錯。,但是如果發(fā)送信息送進信道之前，在每個編碼之后附加一位冗余碼，變成用兩位編碼“11“表示”晴“，“00”表示“雨”，則在傳輸過程中由于干擾造成信息編碼中一位碼發(fā)生差錯，錯成“10”（或“01”）時，由于“10”或“01”都是發(fā)送端不可能出現(xiàn)的編碼，接收端就能發(fā)現(xiàn)差錯，但此時并不能判斷出差錯是第一比特還是第二比特，因此不能自動糾錯 許用碼組 00 11 禁用碼組 10 01,若繼續(xù)增加冗余碼位數(shù)，用“111”表示“晴”，“000”表示“雨”，當編碼在傳輸中出現(xiàn)1位或2位碼差錯（如錯成001或101等編碼）時，接收端都能檢測到，并能確定只有1位碼差錯時錯誤碼位的位置，此時這種編碼方式可以檢測1位或2位差錯，并能糾正單個的誤碼。 許用碼組：000， 111 禁用碼組：001 010 011 100 101 110,由上例的分析可見，冗余碼位數(shù)增加后，編碼的抗干擾能力增強。這主要是因為冗余碼位數(shù)增加后，發(fā)送端使用的碼集中，碼字之間最小碼距 增大。由于 反映了碼集中每兩個碼字之間的差別程度，如果 越大，從一個編碼錯成另一個編碼的可能性越小，則其檢錯、糾錯能力也就越強。因此最小碼距是衡量差錯控制編碼糾、檢錯能力大小的標志。一般情況下，差錯編碼的糾錯能力及檢錯能力與最小碼距之間的關系如下：,4. 檢錯和糾錯能力,碼的最小距離d0直接關系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi): (1) 檢測e個隨機錯誤，則要求碼的最小距離d0e+1; A 0 1 2 3 B A 0 1 2 3e B,B,A0,(2) 糾正t個隨機錯誤， 則要求碼的最小距離d02t+1; 2 3 4 5 t t 2t 1 2t,1,(3) 糾正t個同時檢測e個隨機錯誤，則要求碼的最小距離d0t+e+1。 (e t) 例如： d0=3， 或者4， 或者5,t,1,e,A,B,檢1位糾1位 檢出2位，糾正1位 檢2糾2,例：已知四個碼組為 （110001000） （100010111） （000101111） （001011110） 若將此碼用于檢錯最多可以檢出多少位錯嗎？若用于糾錯，最多糾正幾位？若同時用于檢錯和糾錯，能檢出幾位，糾正幾位？,3. 編碼效率 用差錯控制編碼提高通信系統(tǒng)的可靠性， 是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性: R=k/n 其中, k是信息元的個數(shù)，n為碼長。 對糾錯碼的基本要求是: 檢錯和糾錯能力盡量強； 編碼效率盡量高；編碼規(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)督碼位為0，對碼組10100000進行奇校驗的監(jiān)督碼為1。 設 是同一碼組內(nèi)各位碼元， 是監(jiān)督碼元，其余碼位都是信息碼元，則偶校驗時應滿足,接收端譯碼時，對各碼元進行模二加運算，其結(jié)果為0（偶監(jiān)督碼）如果傳輸過程中碼組任何一位發(fā)生了錯誤，則收到的碼組不滿足偶檢驗關系，因此就能發(fā)現(xiàn)錯誤。 偶監(jiān)督碼的編碼規(guī)則可以用公式表示 （設碼組長度為n，表示為 ） 監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定,對于奇校驗碼必須保證 因此式中的監(jiān)督碼可以用下式求出 奇偶監(jiān)督碼的編碼效率R為,在接收端按照相同的規(guī)律進行檢測，若檢測到與規(guī)律不符，則說明傳輸中有差錯產(chǎn)生，奇偶監(jiān)督碼的檢錯能力為只能檢出奇數(shù)位差錯，不能檢測出偶數(shù)位差錯，也不能判斷出差錯的具體碼元，故奇偶檢驗碼只有一定檢錯能力而不具備糾錯能力。但利用奇偶檢驗碼檢測單個差錯的效果還是令人滿意的，因此在計算機數(shù)據(jù)傳輸及SDH傳輸技術中得到廣泛的應用。,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)督碼 又行列奇偶校驗碼或者水平垂直奇偶校驗碼，還稱作方陣碼，它是將若干信息碼字按照每個碼字一行排列成若干行，使每個碼字中相同的碼位均對齊在同一列中，形成矩陣形式。然后對每一行和每一列的碼元均進行奇校驗或偶校驗，并將校驗結(jié)果附加在每一行及每一列碼元之后。例如：對6個ASCII信息碼進行行列奇偶校驗的結(jié)果如下：,方陣碼不但能檢測出某一行某一列所有奇數(shù)個錯誤, 有時還能檢測出某偶數(shù)個錯誤 信息碼元 監(jiān)督碼元 信息碼元 監(jiān)督碼元 1 0 1 1 0 0 0 1 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 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 1 0 1 1 0 0 0 1 適用于檢測突發(fā)錯誤,能糾錯:碼組中存在僅一行中有奇數(shù)個錯誤時,能夠確定錯碼的位置,行列奇偶監(jiān)督碼不但能檢測出某一行或某一列的所有奇數(shù)個錯誤，有時還能檢測出某些偶數(shù)個錯誤。,但對于以矩陣形式出現(xiàn)的偶數(shù)位差錯，行列奇偶校驗碼是檢測不出來的。此外，通過水平和垂直兩個方向上的校驗，它能夠確定某一行或列中出現(xiàn)的單個差錯碼位置，因此行列奇偶校驗碼具有對單個差錯的糾錯能力。,（3） 恒比碼(等重碼),恒比碼的編碼原則是從確定碼長的碼組中挑選那些“1”和“0”個數(shù)的比值一樣的碼組作為許用碼組。 這種碼通過計算接收碼組中“1”的數(shù)目是否正確，就可檢測出有無錯誤。 五單位數(shù)字保護電碼 碼字長度為5，只選用碼字中含有三個“1”和兩個“0”的碼字作為許用碼字來表示10個阿拉伯數(shù)字1，2，9，0，這種碼亦稱“5中取3碼”。,中文電報編碼首先將每一個單字編碼為四位十進制數(shù)字，再將每一位十進制數(shù)字用二進制的五單位數(shù)字保護碼表示。 通 信 6639 0207 10101 10101 10110 10011 01101 11001 01101 11100 國際電報通信中廣泛采用的是“7中取3碼”，許用碼字共有個，可分別表示26個字母和其它的一些符號。,4、正反碼 編碼的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼是信息碼的重復還是反碼，由信息碼中1的個數(shù)而定。 例：1011010110 （重復） 0011011001 （反碼） 譯碼：接收碼組中信息位和監(jiān)督位按位模2相加 若接收碼組的信息位中有奇數(shù)個1，則合成的碼組為檢驗碼組 若接收碼組的信息位中有偶數(shù)個1，則合成的碼組的反碼為檢驗碼組,檢驗碼組全為0，無錯碼 有4個1，1個0則信息碼組中有一位錯碼，其位置對應檢驗碼組中0的位置 有4個0，1個1則監(jiān)督碼中有一位錯碼，其位置對應檢驗碼組中1的位置 例：10010 （收到碼組為1001010110） 10110 00100 11011 00110 01001 01111 10000 其他組合，錯碼多于一個,檢糾錯能力：長度為10的正反碼有糾正一位錯碼的能力，并能檢測出全部兩位以下的錯誤，和大部分兩位以上的錯誤。 編碼效率：5/10=1/2 5、群計數(shù)碼