常用的差錯控制編碼方法

第二節(jié)常用差錯控制編碼方法一、奇偶校驗碼奇偶校驗碼是一種檢錯碼，又稱奇偶監(jiān)督碼，屬于分組碼。奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼字中“1”的個數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的（n，n-1）分組碼。奇偶監(jiān)督碼分為奇監(jiān)督碼和偶監(jiān)督碼。1.一般奇偶校驗碼（1）基本原理編碼規(guī)則：先將所要傳輸?shù)臄?shù)據(jù)碼元分組，在分組數(shù)據(jù)后面附加一位校驗位，使得該組碼連同校驗位在內(nèi)的碼組中的“1”的個數(shù)為偶數(shù)（稱為偶校驗）或奇數(shù)（稱為奇校驗）在接收端按同樣的規(guī)律檢查，如發(fā)現(xiàn)不符就說明產(chǎn)生了差錯，但是不能確定差錯的具體位置，即不能糾錯。偶檢驗條件：奇校驗條件：1.一般奇偶校驗碼（2）糾錯能力只能發(fā)現(xiàn)單個或奇數(shù)個錯誤，而不能檢測出偶數(shù)個錯誤，此方法難于對付突發(fā)錯。偶校驗監(jiān)督碼2.垂直奇偶校驗碼（1）基本原理以ASCII碼的數(shù)字0～9為例說明垂直奇偶校驗的編碼。接收端根據(jù)收到的b1～b7重新計算奇偶校驗碼元，將此與收到的b8相比較。如相同則無錯，否則存在錯誤。垂直偶校驗2.垂直奇偶校驗碼（2）糾錯能力垂直奇偶校驗編碼，無論是采用偶校驗還是奇校驗，將檢出全部奇數(shù)個差錯，而出現(xiàn)的全部偶數(shù)個差錯均不能發(fā)現(xiàn)。3.水平奇偶校驗碼（1）基本原理將要進行奇偶校驗的碼元序列按行排成方陣，每行為一組奇偶校驗碼，但發(fā)送時則按列的順序傳輸，接收端仍將碼元排成發(fā)送時的方陣形式，然后按行進行奇偶校驗。水平偶校驗練習(xí)：寫出水平奇校驗的校驗碼元3.水平奇偶校驗碼（2）糾錯能力可發(fā)現(xiàn)某一行上所有奇數(shù)個錯誤及所有長度小于或等于方陣中行數(shù)的突發(fā)錯。這種編碼的優(yōu)點是突發(fā)連續(xù)錯誤被分散到每行，當(dāng)收端按行監(jiān)督檢驗時，可檢測出有錯；但是由于該編碼在檢錯過程中需要對數(shù)據(jù)進行重組，所以需要的緩存空間較大，并且在數(shù)據(jù)的處理方面延時增大。4.二維奇偶校驗碼（1）基本原理二維奇偶校驗碼又稱行列校驗碼或方陣碼。其方法是水平監(jiān)督的基礎(chǔ)上對方陣中每一列再進行奇偶校驗，發(fā)送是按列序順次傳輸。二維齊偶校驗問題：這是二維齊校驗還是偶校驗？練習(xí)：寫出另一種校驗的校驗碼元

二維奇偶監(jiān)督碼，它是將若干個信息碼字按每個碼字一行排列成矩陣形式，然后在每一行和每一列的碼元后面附加一位奇（偶）監(jiān)督碼元。

信息碼元監(jiān)督碼元信息碼元監(jiān)督碼元

10110001101100011101001011010010001001110110011101101100011011001001100110011001監(jiān)督碼元1

0

11000

1

10110001二維奇偶監(jiān)督碼4.二維奇偶校驗碼（2）糾錯能力能發(fā)現(xiàn)某行或某列上的奇數(shù)個錯誤和長度不大于行數(shù)（或列數(shù)）的突發(fā)錯誤。有可能檢測出偶數(shù)個錯碼?？梢约m正一些錯誤。檢錯能力強，又有一定糾錯能力，且實現(xiàn)容易得到廣泛應(yīng)用。二、恒比碼碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的個數(shù)是否與規(guī)定的相同，就可判斷有無錯誤。漢明碼：能夠糾正1位錯碼且編碼效率較高的一種線性分組碼。構(gòu)造原理（以奇偶校驗為例）在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位a0，它和信息位an-1…a1一起構(gòu)成一個代數(shù)式： 在接收端解碼時，實際上就是在計算若S=0，就認(rèn)為無錯碼；若S=1，就認(rèn)為有錯碼。三、漢明碼現(xiàn)將上式稱為監(jiān)督關(guān)系式，S稱為校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。若監(jiān)督位增加一位，即變成兩位，則能增加一個類似的監(jiān)督關(guān)系式。由于兩個校正子的可能值有4中組合：00，01，10，11，故能表示4種不同的信息。若用其中1種組合表示無錯，則其余3種組合就有可能用來指示一個錯碼的3種不同位置。同理，r個監(jiān)督關(guān)系式能指示1位錯碼的(2r–1)個可能位置。一般來說，若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)r＝n－k。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示1位錯碼的n種可能位置，則要求

例：設(shè)分組碼(n,k)中k=4，為了糾正1位錯碼，由上式可知，要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7。我們用a6

a5

a0表示這7個碼元，用S1、S2和S3表示3個監(jiān)督關(guān)系式中的校正子，則S1、S2和S3的值與錯碼位置的對應(yīng)關(guān)系可以規(guī)定如下表所列：S1S2

S3錯碼位置S1S2

S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼由表中規(guī)定可見，僅當(dāng)一位錯碼的位置在a2

、a4、a5或a6時，校正子S1為1；否則S1為零。這就意味著a2

、a4、a5和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：

a1、a3、a5和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：a0、a3、a4

和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系在發(fā)送端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監(jiān)督位a2、a1和a0應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使上3式中S1、S2和S3的值為0（表示編成的碼組中應(yīng)無錯碼）：上式經(jīng)過移項運算，解出監(jiān)督位。給定信息位后，可以直接按上式算出監(jiān)督位，結(jié)果見下表：信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111接收端收到每個碼組后，先計算出S1、S2和S3，再查表判斷錯碼情況。例如，若接收碼組為0000011，按上述公式計算可得：S1=0，S2=1，S3=1。由于S1

S2

S3

等于011，故查表可知在a3位有1錯碼。按照上述方法構(gòu)造的碼稱為漢明碼。表中所列的(7,4)漢明碼的最小碼距d0=3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。由于碼率k/n=(n-r)/n=1–r/n，故當(dāng)n很大和r很小時，碼率接近1。可見，漢明碼是一種高效碼。三、漢明碼2.編碼示例設(shè)分組碼（n，k）中k=4，則r≥3.校正子與錯碼位置對應(yīng)關(guān)系規(guī)定如表4-5.閱讀練習(xí)若接收碼組為1100101，判斷錯誤位置。已知信息位k為1001，求監(jiān)督位r。四、循環(huán)碼1.循環(huán)碼的特性（1）循環(huán)性（2）封閉性閱讀p31(7，3)循環(huán)碼的一種碼組2.循環(huán)碼的碼多項式閱讀，練習(xí)：寫出表4-6中碼組的碼多項式在這種多項式中，x僅是碼元位置的標(biāo)記3.碼多項式的按模運算若一個多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個小于n的余式R(x)，即F(x)=N(x)Q(x)+R(x)寫為F(x)≡R(x)（模N(x)）3.碼多項式的按模運算就循環(huán)碼來說，若是一個長為n的許用碼組A(x)，則xi·A(x)在按模（xn+1）運算下，亦是一個許用碼組，即若xi·A(x)≡A′(x)（模xn+1）（4-12）則A′(x)也是一個許用碼組。可見：一個長為n的（n，k）循環(huán)碼，它必是按模（xn+1）運算的一個余式。4.循環(huán)碼的生成多項式一個（n，k）循環(huán)碼有2k個不同的碼組。若用g(x)表示其中前（k?1）位皆為“0”，而第k位及第n位為1的碼組為循環(huán)碼的一個許用碼組，根據(jù)循環(huán)性，則xg(x)，x2g(x)，…，xk－1g(x)都是它的許用碼組，連同g(x)共同構(gòu)成k個許用碼組，即