循環(huán)碼BCH碼卷積碼

10.6循環(huán)碼10.6.1循環(huán)碼的概念：循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個碼組。例：一種(7,3)循環(huán)碼的全部碼組如下表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。碼組編號信息位碼組編號信息位A6a5a4a3a2a1a0a6a5a4A3a2a1a010000000510010112001011161011100301011107110010140111001811100102021/5/91一般情況 若(an-1

an-2…a0)是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組： (an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)

仍然是該編碼中的碼組。多項式表示法 一個長度為n的碼組(an-1

an-2…a0)可以表示成

上式中x的值沒有任何意義，僅用它的冪代表碼元的位置。 例：碼組1100101可以表示為2021/5/9210.6.2循環(huán)碼的運算整數(shù)的按模運算

在整數(shù)運算中，有模n運算。例如，在模2運算中，有

1+1=20(模2)， 1+2=31(模2)，23=60(模2)

等等。 一般說來，若一個整數(shù)m可以表示為 式中，Q為整數(shù)，則在模n運算下，有

m

p(模n)

所以，在模n運算下，一個整數(shù)m等于它被n除得的余數(shù)。2021/5/93碼多項式的按模運算

若任意一個多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即 則在按模N(x)運算下，有 這時，碼多項式系數(shù)仍按模2運算。 例1：x3被(x3+1)除，得到余項1，即 例2： 因為

x

x3+1x4+x2+1

x4+x

x2+x+1

在模2運算中加法和減法一樣。2021/5/94循環(huán)碼的數(shù)學(xué)表示法

在循環(huán)碼中，設(shè)T(x)是一個長度為n的碼組，若 則T(x)也是該編碼中的一個碼組。 上式中的T(x)正是碼組T(x)向左循環(huán)移位i次的結(jié)果。 例：一循環(huán)碼為1100101，即 若給定i=3，則有 上式對應(yīng)的碼組為0101110，它正是T(x)向左移3位的結(jié)果。結(jié)論：一個長為n的循環(huán)碼必定為按模(xn+1)運算的一個余式。

2021/5/95循環(huán)碼的生成有了生成矩陣G，就可以由k個信息位得出整個碼組： 例： 式中， 生成矩陣G的每一行都是一個碼組。因此，若能找到k個已知的碼組，就能構(gòu)成矩陣G。如前所述，這k個已知碼組必須是線性不相關(guān)的。在循環(huán)碼中，一個(n,k)碼有2k個不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。2021/5/96在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個常數(shù)項不為“0”的(n-k)次多項式，而且這個g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一一個多項式。因為如果有兩個，則由碼的封閉性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多項式的次數(shù)將小于(n–k)，即連續(xù)“0”的個數(shù)多于(k–1)。顯然，這是與前面的結(jié)論矛盾的。我們稱這唯一的(n–k)次多項式g(x)為碼的生成多項式。一旦確定了g(x)，則整個(n,k)循環(huán)碼就被確定了。2021/5/97生多項式的性質(zhì)：（1）g(x)是一(n-k)次多項式；（2）g(x)的常數(shù)項不為0；（3）g(x)必須是（xn+1）的一個因子。2021/5/98因此，循環(huán)碼的生成矩陣G可以寫成例： 上表中的編碼為(7,3)循環(huán)碼，n=7,k=3,n–k=4，其中唯一的一個(n–k)=4次碼多項式代表的碼組是第二碼組0010111，與它對應(yīng)的碼多項式，即生成多項式，為

g(x)=x4+x2+x+1。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位A6a5a4a3a2a1a0a6a5a4A3a2a1a010000000510010112001011161011100301011107110010140111001811100102021/5/99

g(x)=x4+x2+x+1即“10111”

將此g(x)代入上矩陣，得到 或 上式不符合G=[IkQ]形式，所以它不是典型生成矩陣。但它經(jīng)過線性變換后，不難化成典型陣。 此循環(huán)碼組的多項式表示式T(x)： 上式表明，所有碼多項式T(x)都能夠被g(x)整除，而且任意一個次數(shù)不大于(k–1)的多項式乘g(x)都是碼多項式。

2021/5/910尋求碼生成多項式

因為任意一個循環(huán)碼T(x)都是g(x)的倍式，故它可以寫成

T(x)=h(x)g(x)

而生成多項式g(x)本身也是一個碼組，即有

T

(x)=g(x)

由于碼組T

(x)是一個(n–k)次多項式，故xkT

(x)是一個n次多項式。由 可知，xk

T

(x)在模(xn+1)運算下也是一個碼組，所以有 上式左端分子和分母都是n次多項式，故相除的商式Q(x)=1。因此，上式可以寫成2021/5/911將T(x)=h(x)g(x)和T

(x)=g(x)代入 化簡后，得到上式表明，生成多項式g(x)應(yīng)該是(xn+1)的一個因子。例：(x7+1)可以分解為 為了求出(7,3)循環(huán)碼的生成多項式g(x)，需要從上式中找到一個(n–k)=4次的因子。這樣的因子有兩個，即 以上兩式都可以作為生成多項式。 選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。

2021/5/91210.6.3循環(huán)碼的編碼方法用xn-k乘m(x)。這一運算實際上是在信息碼后附加上(n–k)個“0”。例如，信息碼為110，它寫成多項式為m(x)=x2+x。當(dāng)n–k=7–3=4時，xn-km(x)=x4(x2+x)=x6+x5，它表示碼組1100000。用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即有 例：若選定g(x)=x4+x2+x+1，則有 上式是用碼多項式表示的運算。它和下式等效：編出的碼組T(x)為：T(x)=xn-km(x)+r(x)

在上例中，T(x)=1100000+101=1100101

2021/5/913

10.6.4循環(huán)碼的解碼方法在檢錯時：當(dāng)接收碼組沒有錯碼時，接收碼組R(x)必定能被g(x)整除，即下式 中余項r(x)應(yīng)為零；否則，有誤碼。當(dāng)接收碼組中的錯碼數(shù)量過多，超出了編碼的檢錯能力時，有錯碼的接收碼組也可能被g(x)整除。這時，錯碼就不能檢出了。在糾錯時：用生成多項式g(x)除接收碼組R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或計算方法得出錯誤圖樣E(x)。從R(x)中減去E(x)，便得到已經(jīng)糾正錯碼的原發(fā)送碼組T(x)。2021/5/914

Ⅰ.BCH碼

BCH碼是具有糾正多個隨機差錯功能的循環(huán)碼，它是循環(huán)碼的一個重要子類。這種碼是建立在現(xiàn)代代數(shù)理論基礎(chǔ)之上的，數(shù)學(xué)結(jié)構(gòu)嚴謹，在譯碼同步等方面有許多獨特的優(yōu)點，故在數(shù)字微波以及數(shù)字衛(wèi)星傳輸設(shè)備中常使用這種能糾正多重錯誤的BCH碼來降低傳輸誤碼率。

BCH碼可分為兩類，一類是原本BCH碼，另一類是非原本BCH碼。原本BCH碼的特點是碼長為2m－1(m為正整數(shù))，其生成多項式是由若干最高次數(shù)為m的因式相乘構(gòu)成的，且具有如下形式：

2021/5/915

(2-5)

其中，t為糾錯個數(shù)，mi(t)為最小多項式，LCM代表最小公倍式。

具有上述特點的循環(huán)碼就是BCH碼，其最小碼距d≥2t＋1(在一種編碼中，任意兩個許用碼組之間的對應(yīng)位上所具有的最小不同二進制碼元數(shù)，稱為最小碼距)。由此可見，一個(2m－1，k)循環(huán)碼的2m－1－k階生成多項式必定是由x2m－1＋1的全部或部分因式組成的。而非原本BCH碼的生成多項式中卻不包含這種原本多項式，并且碼長n是2m－1的一個因子，即2m－1一定是碼長n的倍數(shù)。2021/5/916

下面以碼長為15的BCH碼為例來進行說明?？梢姶藭rm=4(24－1＝15)，即表示最高次數(shù)為4。由xn＋1的因式分解可知：

2021/5/917其中，m7(x)是m1(x)的反多項式(若有限域上的m次多項式為

則

稱為f(x)的反多項式)。對于(15，5)BCH碼的生成多項式為2021/5/918

可見它能糾正3(由2t－1=5得到)個隨機差錯。2021/5/919BCH碼是能夠糾正多個隨機錯碼的循環(huán)碼。

BCH碼分為兩類：本原BCH碼和非本原BCH碼。本原BCH碼：碼長n=2m–1(m

3，任意正整數(shù))，它的生成多項式g(x)中含有最高次數(shù)為m次的本原多項式；非本原BCH碼：碼長n是(2m–1)的一個因子，它的生成多項式g(x)中不含有最高次數(shù)為m的本原多項式。BCH碼的工程設(shè)計：可以用查表法找到所需的生成多項式。 例：二進制非本原BCH碼的生成多項式系數(shù) 表中g(shù)(x)是用8進制數(shù)字表示的；t為糾錯能力。nktg(x)nktg(x)172123334191212222122324727166353435145664713347656573245340465244430733571076135430006717177735372021/5/920常用BCH碼：戈萊(Golay)碼：

(23,12)非本原BCH碼，它能糾正3個隨機錯碼，并且容易解碼。擴展BCH碼(n+1,k)：BCH碼的長度為奇數(shù)。在應(yīng)用中，為了得到偶數(shù)長度的碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上一個因式(x+1)，從而得到擴展BCH碼(n+1,k)。擴展BCH碼已經(jīng)不再具有循環(huán)性。擴展戈萊碼(24,12)：其最小碼距為8，碼率為1/2，能夠糾正3個錯碼和檢測4個錯碼。2021/5/921

前面所介紹的BCH碼都是二進制的，即BCH碼的每一個碼元(元素)的取值為0或1。如果BCH中的每一個元素用多進制表示的話，例如2m進制，那么BCH中的每個元素就可以用一個m位的二進制碼組表示，我們稱這種多進制的BCH碼為RS碼。例如對于其信息位為10011的(15，5)BCH碼序列是100110111000010。如果進行RS編碼，取m=2，即每一位將用一個2位的二進制碼表示(若用01代表“0”碼，用10代表“1”碼)，那么輸出的RS碼就是100101101001101010010101011001?？梢?，當(dāng)以2比特為一組計算，一旦出現(xiàn)00或11或不符合循環(huán)碼的循環(huán)關(guān)系時，則可以斷定，該序列出現(xiàn)差錯。因此，RS碼是一個具有很強的糾錯能力的多進制碼。2021/5/922

一個糾t個符號錯誤的(n，k)RS碼的參數(shù)如下：

碼長

n=2m－1符號或m(2m－1)比特

信息段 k符號或km比特

監(jiān)督段 n－k=2t符號或m(n－k)比特

最小碼距 d=2t＋1符號或m(2t＋1)比特

RS碼特別適合于糾正突發(fā)性錯誤，它可以糾正的差錯長度(第1位誤碼與最后1位誤碼之間的比特序列)如下：

總長度為b1=(t－1)m＋1比特的1個突發(fā)差錯；

總長度為b2=(t－3)m＋3比特的2個突發(fā)差錯；

……

總長度為bi=(t－2i＋1)m＋2i－1比特的i個突發(fā)差錯。2021/5/92310.6.7RS碼RS碼：是q進制BCH碼的一個特殊子類，并且具有很強的糾錯能力。RS碼的主要優(yōu)點：它是多進制糾錯編碼，所以特別適合用于多進制調(diào)制的場合；它能夠糾正t個q位二進制錯碼，即能夠糾正不超過q個連續(xù)的二進制錯碼，所以適合在衰落信道中糾正突發(fā)性錯碼。2021/5/92410.7卷積碼卷積碼的特點：監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，而且還同前面m=(N–1)個信息段有關(guān)。將N稱為碼組的約束度。將卷積碼記作(n,k,m)，其碼率為k/n。2021/5/925卷積碼的編碼一般原理方框圖編碼輸出每次輸入k比特1k…1k…1k…1k…………

1…k…2k3kNk……………

…………

12nNk級移存器n個模2加法器每輸入k比特旋轉(zhuǎn)1周2021/5/926卷積碼編碼器的實例方框圖：(n,k,m)=（3,1,2）每當(dāng)輸入1比特時，此編碼器輸出3比特c1c2c3：編碼器的工作狀態(tài)123b3b1輸入b2編碼輸出c2c1c3b11101000b3b200011110011000c1c2c3111110010100001011000狀態(tài)abdcbca2021/5/92710.7.2卷積碼的解碼碼樹搜索法：(3,1,2)卷積碼的碼樹圖 此法不實用：因為隨信息位增多，分支數(shù)目按指數(shù)規(guī)律增長000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3信息位 1 1 0 1ba起點信息位000111c1c2c3abcdabcdabcdabcd上半部下半部10a狀態(tài)b3b2a00b01c10d11abcdabcdcdab↑0↓1↓1↑0↑0↓12021/5/928狀態(tài)圖和網(wǎng)格圖移存器狀態(tài)和輸入輸出碼元的關(guān)系狀態(tài)圖前一狀態(tài)b3b2當(dāng)前輸入

b1輸出c1c2c3下一狀態(tài)b3b2a(00)01000111a(00)b(01)b(01)01001110c(10)d(11)c(10)01011100a(00)b(01)d(11)01010101c(10)d(11)123b3b1輸入b2編碼輸出c2c1c3abcd0001111011100100111000012021/5/929(3,1,2)卷積碼網(wǎng)格圖網(wǎng)格圖中的編碼路徑舉例輸入信息位為11010時輸出編碼序列是：

111110010100011…110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100abcd000111101110010011100001abcdabcd1100100011111002021/5/930維特比算法基本原理：將接收到的序列和所有可能的發(fā)送序列作比較，選擇其中漢明距離最小的序列當(dāng)作是現(xiàn)在的發(fā)送序列例：設(shè)卷積碼為(n,k,m)=(3,1,2)碼現(xiàn)在的發(fā)送信息位為1101為了使移存器中的信息位全部移出，在信息位后面加入了3個“0”，即1101000編碼后的發(fā)送序列：111110010100001011000接收序列：111010010110001011000(紅色為錯碼)由于這是一個(3,1,2)卷積碼，發(fā)送序列的約束度為N=m+1＝3，所以首先需考察3個信息段，即考察3n＝9比特，即接收序列前9位“111010010”。2021/5/931解碼第1步由網(wǎng)格圖可見，沿路徑每一級有4種狀態(tài)a,b,c和d。每種狀態(tài)只有兩條路徑可以到達。故4種狀態(tài)共有8條到達路徑。比較網(wǎng)格圖中的這8條路徑和接收序列之間的漢明距離。例如，由出發(fā)點狀態(tài)a經(jīng)過3級路徑后到達狀態(tài)a的兩條路徑中上面一條為“000000000”。它和接收序列“111010010”的漢明距離等于5；下面一條為“111001011”,它和接收序列的漢明距離等于3。110110110110011011011010010010101101101001001001001abcdabcd0000000000000001111111111111111001001002021/5/932將這8個比較結(jié)果列表如下：比較到達每個狀態(tài)的兩條路徑的漢明距離，將距離小的一條路徑保留，稱為幸存路徑。這樣，就剩下4條路徑了，即表中第2,4,6和8條路徑。序號路徑對應(yīng)序列漢明距離幸存否？1aaaa0000000005否2abca1110010113是3aaab0000001116否4abcb1110011004是5aabc0001110017否6abdc1111100101是7aabd0001111106否8abdd1111101014是2021/5/933解碼第2步：繼續(xù)考察接收序列中的后繼3個比特“110”計算4條幸存路徑上增加1級后的8條可能路徑的漢明距離。計算結(jié)果列于下表中。表中總距離最小為2，其路徑是abdc+b，相應(yīng)序列為111110010100。它和發(fā)送序列相同，故對應(yīng)發(fā)送信息位1101。序號路徑原幸存路徑的距離新增路徑段新增距離總距離幸存否？1abca+a3aa25否2abdc+a1ca23是3abca+b3ab14否4abdc+b1cb12是5abcb+c4bc37否6abdd+c4dc15是7abcb+d4bd04是8abdd+d4dd26否2021/5/934按照上表中的幸存路徑畫出的網(wǎng)格圖示于下圖中。圖中粗線路徑是距漢明離最?。ǖ扔?）的路徑。abcd011010010101001abcd1111001001101102021/5/935在編碼時，信息位后面加了3個“0”。若把這3個“0”仍然看作是信息位，則可以按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。圖中的粗線仍然是漢明距離最小的路徑。110011010010101101001001abcdabcd0001111001000000110110011012021/5/936若已知這3個碼元是（為結(jié)尾而補充的）“0”，則在解碼時就預(yù)先知道在接收這3個“0”碼元后，路徑必然應(yīng)該回到狀態(tài)a。而由圖可見， 只有兩條路徑可以回到a狀態(tài)。所以，這時上圖可以簡化成：110011010010101101001001abcdabcd000111100100000011011001110011010010101101001001abcdabcd0001111001000000110110011012021/5/937在上例中卷積碼的約束度為N=3，需要存儲和計算8條路徑的參量。由此可見，維特比算法的復(fù)雜度隨約束度N按指數(shù)形式2N增長。故維特比算法適合約束度較?。∟10）的編碼。對于約束度大的卷積碼，可以采用其他解碼算法，2021/5/93810.8Turbo碼和LDPC碼Turbo碼基本原理：復(fù)合編碼：將兩種或多種簡單的編碼組合成復(fù)合編碼。鏈接碼：鏈接碼是復(fù)合編碼的一種，它包括一個內(nèi)（部）碼和一個外（部）碼，如下圖所示：內(nèi)碼是二進制分組碼或卷積碼，而典型的外碼則是多進制的RS碼。Turbo碼：是一種特殊的鏈接碼。它在兩個并聯(lián)或串聯(lián)的編碼器之間增加一個交織器，使之具有很大的碼組長度和在低信噪比條件下得到接近理想的性能。內(nèi)編碼器(n,k)調(diào)制器信道解制器內(nèi)解碼器(n,k)外解碼器(N,K)外編碼器(N,K)輸入輸出2021/5/939Turbo碼的基本結(jié)構(gòu)編碼器：由一對遞歸系統(tǒng)卷積碼（RSCC）編碼器和一個交織器組成。輸入信息位是bi，輸出是bic1ic2i，故碼率等于1/3。RSCC編碼器：和前面討論的卷積碼編碼器之間的主要區(qū)別是從移存器輸出到信息位輸入端之間有反饋路徑：上圖為碼率等于1/2的RSCC編碼器RSCC交織器RSCCbibic1ic2iDDbibici2021/5/940交織器：基本形式是矩陣交織器。交織目的：將集中出現(xiàn)的突發(fā)錯碼分散，變成隨機錯碼交織原理：交織器由容量為(n-1)m比特的存儲器構(gòu)成。碼元按行的方向輸入存儲器，再按列的方向輸出。a11a12a1ma21a22a2man1an2anm2021/5/9