差錯控制編碼-循環(huán)碼

1、3.1 循環(huán)碼循環(huán)碼一、循環(huán)碼的特點循環(huán)碼最大的特點就是碼字的循環(huán)特性，所謂循環(huán)特性是指：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。 若若 （ ） 為一循環(huán)碼組，則為一循環(huán)碼組，則 還是許用碼組。還是許用碼組。 0121aaaann)(10132nnnaaaaa)(2143nnnnaaaa如（7，3）循環(huán)碼的全部碼字 第三章差錯控制編碼第三章差錯控制編碼二、碼多項式 為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項式來表示，這個多項式被稱為碼多項式，對于許用循環(huán)碼 )(0121aaaaAnn可以將它的碼多項式表示為： 對于二進制碼組，多項式的每個系數(shù)不是對于二進制碼組，多

2、項式的每個系數(shù)不是0就是就是1，x僅是碼元位僅是碼元位置的標(biāo)志。因此，這里并不關(guān)心置的標(biāo)志。因此，這里并不關(guān)心x的取值。表中的第的取值。表中的第7碼字可以表碼字可以表示為：示為： 在整數(shù)運算中，有模在整數(shù)運算中，有模n運算。例如，在模運算。例如，在模2運算中，有運算中，有1+120（模（模2），），1+231（模（模2），），2360（模（模2）等。因）等。因此，若一個整數(shù)此，若一個整數(shù)m可以表示為可以表示為: 則在模則在模n運算下，有運算下，有mp（模（模n），也就是說，在模），也就是說，在模n運算下，運算下，一整數(shù)一整數(shù)m等于其被等于其被n除所得的余數(shù)。除所得的余數(shù)。 如：如：在碼多項式運

3、算中也有類似的按模運算法則。若一任意多項式在碼多項式運算中也有類似的按模運算法則。若一任意多項式F(x)被一個被一個n次多項式次多項式N(x)除，得到商式除，得到商式Q(x)和一個次數(shù)小于和一個次數(shù)小于n的的余式余式R(x)，也就是：，也就是： 則可以寫為：F(x)R(x)（模N(x)） 這時，碼多項式系數(shù)仍按模這時，碼多項式系數(shù)仍按模2運算，即只取值運算，即只取值0和和1，假設(shè)：，假設(shè)：計算計算x4+x2+1除以除以x3+1的值可得：的值可得： 這樣式也可以表示為： 注意，在上述運算中，由于是模注意，在上述運算中，由于是模2運算，因此，加法和減法是等運算，因此，加法和減法是等價的，在式子中通

4、常用加法運算符，具體模價的，在式子中通常用加法運算符，具體模2運算的規(guī)則定義如運算的規(guī)則定義如下：下： 在循環(huán)碼中，若A(x)是一個長為n的許用碼組，則 在按模 運算下，亦是一個許用碼組，也就是假如： （模 ），可以證明 亦是一個許用碼組，并且， 正是A(x)代表的碼組向左循環(huán)移位i次的結(jié)果。例如，由式表示的循環(huán)碼，其碼長n7，現(xiàn)給定i3，則： 其對應(yīng)的碼組為0101110，它正是表中第3碼字。)()(xAxAxli )(xAxi)(xAl)(xAl結(jié)論：一個長度為結(jié)論：一個長度為n的循環(huán)碼，它必為按模（的循環(huán)碼，它必為按模（ ）運算的）運算的一個余式。一個余式。 三、循環(huán)碼的生成多項式及其特

5、征 如果一種碼的所有碼多項式都是多項式g(x) 的倍式，的倍式， 則稱則稱g(x) （全0碼字除外）為生成多項式。循環(huán)碼中次數(shù)最低的多項式（全0碼字除外)就是生成多項式?？梢宰C明生成多項式g(x)具有以下特性： （1）g(x)是一個常數(shù)項為1的r=n-k次多項式(首一多項式)； （2）g(x)是是 的一個因式；的一個因式； （3）該循環(huán)碼中其它碼多項式都是g(x)的倍式。 為了保證構(gòu)成的生成矩陣為了保證構(gòu)成的生成矩陣G的各行線性不相關(guān)，通常用的各行線性不相關(guān)，通常用g(x)來來構(gòu)造生成矩陣，這時，生成矩陣構(gòu)造生成矩陣，這時，生成矩陣G(x)可以表示成為：可以表示成為： 其中：其中：因此，一旦生

6、成多項式因此，一旦生成多項式g(x)確定以后，該循環(huán)碼的生成矩陣就可確定以后，該循環(huán)碼的生成矩陣就可以確定，進而該循環(huán)碼的所有碼字就可以確定。以確定，進而該循環(huán)碼的所有碼字就可以確定。 顯然，顯然， （*式）不符合式）不符合 形式，所以此生成矩陣不是典形式，所以此生成矩陣不是典型形式，不過，可以通過簡單的代數(shù)變換將它變成典型矩陣。型形式，不過，可以通過簡單的代數(shù)變換將它變成典型矩陣。 （*式）式） 現(xiàn)在以（現(xiàn)在以（7，3）循環(huán)碼為例，來構(gòu)造它的生成矩陣和生成多項式，）循環(huán)碼為例，來構(gòu)造它的生成矩陣和生成多項式，這個循環(huán)碼主要參數(shù)為，這個循環(huán)碼主要參數(shù)為，n7，k3，r4?？梢钥吹剑渖啥??？?/p>

7、以看到，其生成多項式可以用第項式可以用第1碼字構(gòu)造：碼字構(gòu)造： 在上面的例子中，是（在上面的例子中，是（7，3）循環(huán)碼的所有碼字，構(gòu)造了它的）循環(huán)碼的所有碼字，構(gòu)造了它的生成多項式和生成矩陣。但在實際循環(huán)碼設(shè)計過程中，通常只生成多項式和生成矩陣。但在實際循環(huán)碼設(shè)計過程中，通常只給出碼長和信息位數(shù)，這就需要設(shè)計生成多項式和生成矩陣，給出碼長和信息位數(shù)，這就需要設(shè)計生成多項式和生成矩陣，這時可以利用這時可以利用g(x)所具有基本特性進行設(shè)計。所具有基本特性進行設(shè)計。 矩陣矩陣nk 四、監(jiān)督多項式和監(jiān)督矩陣四、監(jiān)督多項式和監(jiān)督矩陣首先，生成多項式首先，生成多項式g(x)是是 的一個因式，其次的一個因

8、式，其次g(x)是一是一個個r次因式。因此，就可以先對次因式。因此，就可以先對 進行因式分解，找到它的進行因式分解，找到它的r次因式。下面仍以（次因式。下面仍以（7，3）循環(huán)碼為例進行分析。）循環(huán)碼為例進行分析。 第一步：對第一步：對 進行因式分解得：進行因式分解得： 第二步：構(gòu)造生成多項式g（x）為了求（7，3）循環(huán)碼的生成多項式g(x)，要從上式中找到r=n-k次的因子。不難看出，這樣的因子有兩個，即： 1式式2式式以上兩式都可作為生成多項式用。不過，選用的生成多項式不以上兩式都可作為生成多項式用。不過，選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組就不同。用同，產(chǎn)生出的循環(huán)碼碼組就不同。用1式

9、作為生成多項式產(chǎn)生的式作為生成多項式產(chǎn)生的循環(huán)碼為上述表碼所列。循環(huán)碼為上述表碼所列。當(dāng)然，在得到生成矩陣當(dāng)然，在得到生成矩陣G以后，可以通過線性變化，使之成為以后，可以通過線性變化，使之成為典型矩陣，同時得到監(jiān)督矩陣典型矩陣，同時得到監(jiān)督矩陣H。除此之外，還可以利用循環(huán)。除此之外，還可以利用循環(huán)碼的特點來確定監(jiān)督矩陣碼的特點來確定監(jiān)督矩陣H。 由于（由于（n,k）循環(huán)碼中）循環(huán)碼中g(shù)(x)是是 的的因式，因此可令：因式，因此可令： 這里h（x）稱為監(jiān)督多項式。與G(x)相對應(yīng)，監(jiān)督矩陣表示為： 其中其中 是是 逆多項式逆多項式對于前述例子中的（7,3）循環(huán)碼， 則：則：1)(24xxxxg設(shè)

10、發(fā)送碼組設(shè)發(fā)送碼組A=an-1,an-2,a1,a0，在傳輸過程中可能發(fā)生，在傳輸過程中可能發(fā)生誤碼。接收碼組誤碼。接收碼組B=bn-1,bn-2,b1,b0，則收發(fā)碼組之差定，則收發(fā)碼組之差定義為錯誤圖樣義為錯誤圖樣E， 也稱為誤差矢量，也稱為誤差矢量， 即即 ABE ABE其中E=en-1,en-2,e1,e0，且當(dāng)bi=ai 當(dāng)biai 10ie00TTTHAHA或)(0123456aaaaaaaA 矩陣矩陣nr 0001101001101001101001101000)(123134245356HxxxxxxxxxxxxxH五、循環(huán)碼的編碼 在編碼時，首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生

11、成多項式在編碼時，首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項式g(x)，也就是從，也就是從 的因子中選一個（的因子中選一個（n-k）次多項式作為）次多項式作為g(x)；然后，利用循環(huán)碼的編碼特點，即所有循環(huán)碼多項式；然后，利用循環(huán)碼的編碼特點，即所有循環(huán)碼多項式A(x)都可以被都可以被g(x)整除，來定義生成多項式整除，來定義生成多項式g(x)。 EAB 令S S=BHBHT，稱為伴隨式或校正子。 TTTEHHEABHS )(由此可見，伴隨式S與錯誤圖樣E之間有確定的線性變換關(guān)系。接收端譯碼器的任務(wù)就是從伴隨式確定錯誤圖樣，然后從接收到的碼字中減去錯誤圖樣。若若S=0,則為有效碼字則為有效碼字為

12、求解為求解B(x)整除整除g(x)的余式的余式TBHS 根據(jù)上述原理可以得到一個較簡單的系統(tǒng)循環(huán)碼編碼方法：設(shè)根據(jù)上述原理可以得到一個較簡單的系統(tǒng)循環(huán)碼編碼方法：設(shè)要產(chǎn)生（要產(chǎn)生（n,k）循環(huán)碼，）循環(huán)碼，m(x)表示信息多項式，則其次數(shù)必小于表示信息多項式，則其次數(shù)必小于k，而，而 m(x)的次數(shù)必小于的次數(shù)必小于n，用，用 m(x)除以除以g(x)，可，可得余數(shù)得余數(shù)r(x)，r(x)的次數(shù)必小于（的次數(shù)必小于（n-k），將），將r(x)加到信息位后作加到信息位后作監(jiān)督位，就得到了系統(tǒng)循環(huán)碼。監(jiān)督位，就得到了系統(tǒng)循環(huán)碼。（1）用）用 乘乘m(x)。這一運算實際上是把信息碼后附加上。這一運算

13、實際上是把信息碼后附加上（n-k）個）個“0”。例如，信息碼為。例如，信息碼為110，它相當(dāng)于，它相當(dāng)于m(x) +x。當(dāng)當(dāng)n-k7-34時，時， m（x） ，它相當(dāng)于，它相當(dāng)于1100000。而希望的到得系統(tǒng)循環(huán)碼多項式應(yīng)當(dāng)是。而希望的到得系統(tǒng)循環(huán)碼多項式應(yīng)當(dāng)是A(x) = m(x) + r(x)。56xx （2）求）求r(x)。由于循環(huán)碼多項式。由于循環(huán)碼多項式A(x)都可以被都可以被g(x)整除，也整除，也就是：就是： 這樣就得到了r(x)。 （3）編碼輸出系統(tǒng)循環(huán)碼多項式A(x)為： 例如，對于（例如，對于（7，3）循環(huán)碼，若選用）循環(huán)碼，若選用 ，信息碼信息碼110時，則：時，則：

14、上式相當(dāng)于： 這時的編碼輸出為：1100101。 六、循環(huán)碼編碼硬件實現(xiàn) 上述三步編碼過程，在硬件實現(xiàn)時，可以利用除法電路來實上述三步編碼過程，在硬件實現(xiàn)時，可以利用除法電路來實現(xiàn)，這里的除法電路采用一些移位寄存器和?，F(xiàn)，這里的除法電路采用一些移位寄存器和模2加法器來構(gòu)成。加法器來構(gòu)成。下面將以（下面將以（7,3）循環(huán)碼為例，來說明其具體實現(xiàn)過程。）循環(huán)碼為例，來說明其具體實現(xiàn)過程。 設(shè)該（7,3）循環(huán)碼的生成多項式為： 則構(gòu)成的系統(tǒng)循環(huán)碼編碼器如圖所示，圖中有則構(gòu)成的系統(tǒng)循環(huán)碼編碼器如圖所示，圖中有4個移位寄存器，個移位寄存器，一個雙刀雙擲開關(guān)。當(dāng)信息位輸入時，開關(guān)位置接一個雙刀雙擲開關(guān)。當(dāng)

15、信息位輸入時，開關(guān)位置接“2”，輸入的，輸入的信息碼一方面送到除法器進行運算，一方面直接輸出；當(dāng)信息位信息碼一方面送到除法器進行運算，一方面直接輸出；當(dāng)信息位全部輸出后，開關(guān)位置接全部輸出后，開關(guān)位置接“1”，這時輸出端接到移位寄存器的輸，這時輸出端接到移位寄存器的輸出，這時除法的余項，也就是監(jiān)督位依次輸出。當(dāng)信息碼為出，這時除法的余項，也就是監(jiān)督位依次輸出。當(dāng)信息碼為110時，編碼器的工作過程如表：時，編碼器的工作過程如表： 編碼器工作過程輸入輸入 (m) 移位寄存器移位寄存器 (abcd)反饋反饋 (e) 輸出輸出 (f) 00 0 0 0001101 1 1 01 0 0 11 0 1

16、011111000000 1 0 10 0 1 00 0 0 10 0 0 001010101由于數(shù)字信號處理器（DSP）和大規(guī)?？删幊踢壿嬈骷–PLD和FPGA）的廣泛應(yīng)用，目前已多采用這些先進器件和相應(yīng)的軟件來實現(xiàn)上述編碼。 七、 循環(huán)碼的譯碼 對于接收端譯碼的要求通常有兩個：檢錯與糾錯。達到檢錯目對于接收端譯碼的要求通常有兩個：檢錯與糾錯。達到檢錯目的的譯碼十分簡單，通過判斷接收到的碼組多項式的的譯碼十分簡單，通過判斷接收到的碼組多項式B(x)是否能是否能被生成多項式被生成多項式g(x)整除作為依據(jù)。當(dāng)傳輸中未發(fā)生錯誤時，也整除作為依據(jù)。當(dāng)傳輸中未發(fā)生錯誤時，也就是接收的碼組與發(fā)送的碼

17、組相同，即就是接收的碼組與發(fā)送的碼組相同，即A(x)=B(x)，則接收的，則接收的碼組碼組B(x)必能被必能被g(x)整除；若傳輸中發(fā)生了錯誤，則整除；若傳輸中發(fā)生了錯誤，則A(x)B(x)，B(x)不能被不能被g(x)整除。因此，可以根據(jù)余項是否為零來判斷碼整除。因此，可以根據(jù)余項是否為零來判斷碼組中有無錯碼。組中有無錯碼。 需要指出的是，有錯碼的接收碼組也有可能被需要指出的是，有錯碼的接收碼組也有可能被g(x)整除，這整除，這時的錯碼就不能檢出了。這種錯誤被稱為不可檢錯誤，不可檢時的錯碼就不能檢出了。這種錯誤被稱為不可檢錯誤，不可檢錯誤中的錯碼數(shù)必將超過這種編碼的檢錯能力。錯誤中的錯碼數(shù)必

18、將超過這種編碼的檢錯能力。 在接收端為糾錯而采用的譯碼方法自然比檢錯要復(fù)雜許多，因此，對糾錯碼的研究大都集中在譯碼算法上。校正子與錯誤圖樣之間存在某種對應(yīng)關(guān)系。如同其它線性分組碼，循環(huán)碼的譯碼可以分三步進行： （1）由接收到的碼多項式B(x)計算校正子（伴隨式）多項式S(x)； （2）由校正子S(x)確定錯誤圖樣E(x)； （3）將錯誤圖樣E(x)與B(x)相加，糾正錯誤。上述第（上述第（1）步運算和檢錯譯碼類似，也就是求解）步運算和檢錯譯碼類似，也就是求解B(x)整除整除g(x)的余式，第（的余式，第（3）步也很簡單。因此，糾錯碼譯碼器的復(fù)雜性）步也很簡單。因此，糾錯碼譯碼器的復(fù)雜性主要取決

19、于譯碼過程的第（主要取決于譯碼過程的第（2）步。）步。TBHS 錯誤圖樣錯誤圖樣伴隨式（校正子）伴隨式（校正子）0000000000000000010000010000010000010000010000010000010000001100100001101011010100100001錯誤圖樣和伴隨式是一一對應(yīng)的。錯誤圖樣和伴隨式是一一對應(yīng)的。11000000100? 圖中圖中k級緩存器用于存儲系統(tǒng)循環(huán)碼的信息碼元，模級緩存器用于存儲系統(tǒng)循環(huán)碼的信息碼元，模2加電路用加電路用于糾正錯誤。當(dāng)校正子為于糾正錯誤。當(dāng)校正子為0時，模時，模2加來自錯誤圖樣識別電路的加來自錯誤圖樣識別電路的輸入端為輸

20、入端為0，輸出緩存器的內(nèi)容；當(dāng)校正子不為，輸出緩存器的內(nèi)容；當(dāng)校正子不為0時，模時，模2加來加來自錯誤圖樣識別電路的輸入端在第自錯誤圖樣識別電路的輸入端在第i位輸出為位輸出為1，它可以使緩存，它可以使緩存器輸出取補，即糾正錯誤。器輸出取補，即糾正錯誤。 基于錯誤圖樣識別的譯碼器稱為梅吉特譯碼器。錯誤圖樣識基于錯誤圖樣識別的譯碼器稱為梅吉特譯碼器。錯誤圖樣識別器是一個具有（別器是一個具有（n-k）個輸入端的邏輯電路，原則上可以采）個輸入端的邏輯電路，原則上可以采用查表的方法，根據(jù)校正子找到錯誤圖樣，利用循環(huán)碼的上用查表的方法，根據(jù)校正子找到錯誤圖樣，利用循環(huán)碼的上述特性可以簡化識別電路。梅吉特譯碼器特別適合于糾