【文章內(nèi)容簡(jiǎn)介】 0 和 1。例如， x3被 (x3 + 1)除，得到余項(xiàng) 1。所以有同理因?yàn)? xx3 + 1 x4 +x2 + 1 x4 + x x2 +x +1應(yīng)當(dāng)注意，由于在模 2運(yùn)算中，用加法代替了減法，故余項(xiàng)不是 x2 – x + 1，而是 x2 + x + 1。34第 11章差錯(cuò)控制編碼u 循環(huán)碼的碼多項(xiàng)式p 在循環(huán)碼中，若 T(x)是一個(gè)長為 n的許用碼組，則 xi?T(x)在按模 xn + 1運(yùn)算下，也是該編碼中的一個(gè)許用碼組，即若則 T ?(x)也是該編碼中的一個(gè)許用碼組?！?證 】 因?yàn)槿魟t（模 (xn + 1)）所以，這時(shí)有35第 11章差錯(cuò)控制編碼上式中 T ?(x)正是 T(x)代表的碼組向左循環(huán)移位 i次的結(jié)果。因?yàn)樵鸭俣?T(x)是循環(huán)碼的一個(gè)碼組，所以 T? (x)也必為該碼中一個(gè)碼組。例如，循環(huán)碼組其碼長 n = 7。現(xiàn)給定 i = 3，則其對(duì)應(yīng)的碼組為 0101110，它正是表中第 3碼組。由上述分析可見，一個(gè)長為 n的循環(huán)碼必定為按模 (xn + 1)運(yùn)算的一個(gè)余式。36第 11章差錯(cuò)控制編碼u 循環(huán)碼的生成矩陣 Gp 在循環(huán)碼中，一個(gè) (n, k)碼有 2k個(gè)不同的碼組。若用 g(x)表示其中前 (k1)位皆為 “0”的碼組，則 g(x)， x g(x)， x2 g(x)，? ， xk1 g(x)都是碼組，而且這 k個(gè)碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣 G。p 在一個(gè) （ n,k） 循環(huán)碼中，有 且只有一個(gè)次數(shù)為 (n – k)的多項(xiàng)式 g(x)，稱其為碼的生成多項(xiàng)式。一旦確定了 g(x)，則整個(gè) (n, k)循環(huán)碼就被確定了。 37第 11章差錯(cuò)控制編碼p 因此，循環(huán)碼的生成矩陣 G可以寫成 p 例： 在上表所給出的 (7, 3)循環(huán)碼中， n = 7, k = 3, n – k = 4。由此表可見，唯一的一個(gè) (n – k) = 4次碼多項(xiàng)式代表的碼組是第二碼組 0010111，與它相對(duì)應(yīng)的碼多項(xiàng)式（即生成多項(xiàng)式） g(x) = x4 + x2 + x + 1。 將此 g(x)代入上式，得到或38第 11章差錯(cuò)控制編碼由于上式不符合 G = [IkQ]的形式，所以它不是典型陣。不過，將它作線性變換，不難化成典型陣。我們可以寫出此循環(huán)碼組，即上式表明，所有碼多項(xiàng)式 T(x)都可被 g(x)整除，而且任意一個(gè)次數(shù)不大于 (k – 1)的多項(xiàng)式乘 g(x)都是碼多項(xiàng)式。39第 11章差錯(cuò)控制編碼u 如何尋找任一 (n, k)循環(huán)碼的生成多項(xiàng)式 由上式可知，任一循環(huán)碼多項(xiàng)式 T(x)都是 g(x)的倍式 ，故它可以寫成T(x) = h(x)?g(x) 而生成多項(xiàng)式 g(x)本身也是一個(gè)碼組，即有 T ?(x) = g(x) 由于碼組 T ?(x)是一個(gè) (n – k)次多項(xiàng)式，故 xk T ?(x)是一個(gè) n次多項(xiàng)式。由下式可知， xk T ?(x)在模 (xn + 1)運(yùn)算下也是一個(gè)碼組，故可以寫成40第 11章差錯(cuò)控制編碼 上式左端分子和分母都是 n次多項(xiàng)式，故商式 Q(x) = 1。因此，上式可以化成將 T(x)和 T?(x)表示式代入上式，經(jīng)過化簡(jiǎn)后得到上式表明， 生成多項(xiàng)式 g(x)應(yīng)該是 (xn + 1)的一個(gè)因子 。這一結(jié)論為我們尋找循環(huán)碼的生成多項(xiàng)式指出了一條道路，即 循環(huán)碼的生成多項(xiàng)式應(yīng)該是 (xn +1)的一個(gè) (n – k)次因式 。例如， (x7 + 1)可以分解為為了求 (7, 3)循環(huán)碼的生成多項(xiàng)式 g(x)，需要從上式中找到一個(gè) (n – k) = 4次的因子。不難看出，這樣的因子有兩個(gè)，即41第 11章差錯(cuò)控制編碼 以上兩式都可作為生成多項(xiàng)式。不過，選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組也不同。42第 11章差錯(cuò)控制編碼n 循環(huán)碼的編解碼方法u 循環(huán)碼的編碼方法p 編碼原則在編碼時(shí)，首先要根據(jù)給定的 (n, k)值選定生成多項(xiàng)式g(x)，即從 (xn + 1)的因子中選一個(gè) (n k)次多項(xiàng)式作為g(x)。 43第 11章差錯(cuò)控制編碼p 編碼步驟：216。 （ 1）用 xn k乘 m(x)。這一運(yùn)算實(shí)際上是在信息碼后附加上 (n – k)個(gè) “0”。例如，信息碼為 110，它相當(dāng)于 m(x) = x2 + x。當(dāng) n – k = 7 – 3 = 4時(shí)， xn k m(x) = x4 (x2 + x) = x6 + x5，它相當(dāng)于 1100000。216。 （ 2）用 g(x)除 xn k m(x)，得到商 Q(x)和余式 r(x)，即例如，若選定 g(x) = x4 + x2 + x + 1，則 上式相當(dāng)于44第 11章差錯(cuò)控制編碼216。 （ 3）編出的碼組 T(x)為T(x) = xn k m(x) + r(x) 在上例中， T(x) = 1100000 + 101 = 1100101，它就是上表中的第 7碼組。45第 11章差錯(cuò)控制編碼u 循環(huán)碼的解碼方法p 解碼要求：檢錯(cuò)和糾錯(cuò)。p 檢錯(cuò)解碼原理：由于任意一個(gè)碼組多項(xiàng)式 T(x)都應(yīng)該能被生成多項(xiàng)式 g(x)整除，所以在接收端可以將接收碼組 R(x)用原生成多項(xiàng)式 g(x)去除。當(dāng)傳輸中未發(fā)生錯(cuò)誤時(shí)，接收碼組與發(fā)送碼組相同，即 R(x) = T(x)，故接收碼組 R(x)必定能被 g(x)整除；若碼組在傳輸中發(fā)生錯(cuò)誤，則 R(x) ? T(x)， R(x)被 g(x)除時(shí)可能除不盡而有余項(xiàng)，即有因此，就以余項(xiàng)是否為零來判別接收碼組中有無錯(cuò)碼。需要指出，有錯(cuò)碼的接收碼組也有可能被 g(x)整除。這時(shí)的錯(cuò)碼就不能檢出了。這種錯(cuò)誤稱為 不可檢錯(cuò)誤 。不可檢錯(cuò)誤中的誤碼數(shù)必定超過了這種編碼的檢錯(cuò)能力。46第 11章差錯(cuò)控制編碼p 糾錯(cuò)解碼原理：為了能夠糾錯(cuò)，要求每個(gè)可糾正的錯(cuò)誤圖樣必須與一個(gè)特定余式有一一對(duì)應(yīng)關(guān)系。因?yàn)橹挥写嬖谏鲜鲆灰粚?duì)應(yīng)的關(guān)系時(shí)，才可能從上述余式唯一地決定錯(cuò)誤圖樣，從而糾正錯(cuò)碼。因此，原則上糾錯(cuò)可按下述步驟進(jìn)行：216。 用生成多項(xiàng)式 g(x)除接收碼組 R(x)，得出余式 r(x)。216。 按余式 r(x)，用查表的方法或通過某種計(jì)算得到錯(cuò)誤圖樣 E(x)；例如，通過計(jì)算校正子 S和查表，就可以確定錯(cuò)碼的位置。216。 從 R(x)中減去 E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組T(x)。p 通常，一種編碼可以有幾種糾錯(cuò)解碼方法，上述解碼方法稱為 捕錯(cuò)解碼法 。 u 目前多采用軟件運(yùn)算實(shí)現(xiàn)上述編解碼運(yùn)算。47第 11章差錯(cuò)控制編碼l 卷積碼n 非分組碼概念：u 卷積碼是一種非分組碼。通常它更適用于前向糾錯(cuò)，因?yàn)閷?duì)于許多實(shí)際情況它的性能優(yōu)于分組碼，而且運(yùn)算較簡(jiǎn)單。u 卷積碼在編碼時(shí)雖然也是把 k個(gè)比特的信息段編成 n個(gè)比特的碼組，但是監(jiān)督碼元不僅和當(dāng)前的 k比特信息段有關(guān)，而且還同前面 m = (N – 1)個(gè)信息段有關(guān)。所以一個(gè)碼組中的監(jiān)督碼元監(jiān)督著 N個(gè)信息段。通常將 N稱為編碼 約束度 ，并將 nN稱為編碼 約束長度 。一般說來，對(duì)于卷積碼， k 和 n 的值是比較小的整數(shù)。我們將卷積碼記作 (n, k, N)。碼率則仍定義為 k / n。 48