信息論與糾錯編碼題庫

1、第九章 循環(huán)碼9.1 什么是循環(huán)碼？如何用多項式來描述一個循環(huán)碼？解答： 一個線性分組碼，若具有如下特性，則稱為循環(huán)碼。設(shè)碼字 c=(cn-1 cn-2 c1 c0)將碼元左移一位，得 c1=(cn-2 c1 c0 cn-1) 也是一個碼字，則稱此分組碼為循環(huán)碼。 把碼長為n的碼組中的各碼元當(dāng)作n-1次多項式的系數(shù)若碼組c=（cn-1，cn-2，c1，c0)，則其相應(yīng)的碼多項式為： c(x)= cn-1xn-1+ cn-1xn-1+ + c1x+ c0 對應(yīng)于每一碼字，可以寫出相應(yīng)的碼字多項式(最高次數(shù)小于n次)c (x) = c n-1 x n-1 +cn-2 x n-2+c1 x +c0c

2、1(x) = cn-2 x n-1+c n-3 x n-2+c0 x +c n-1c2(x) = cn-3xn-1+cn-4xn-2+cn-1x+cn-2 cn-1(x) =c0 xn-1+cn-1xn-2+c2 x+c1對于上述多項式，有x c (x) + c1 (x) = cn-1 x n + cn-1 = cn-1 (xn + 1 ) x c (x) + c1 (x) 0 mod (xn +1) c1 (x) xc (x)x2 c (x) + c2 (x) = cn-1 (xn +1) c2 (x) x2 c (x) mod (xn +1)ci (x) xi c(x) mod (xn +

3、 1)c n-1 (x)x n-1 c1(x) mod (xn+1)得出結(jié)論：在循環(huán)碼中，若c(x)是一個長為n的許用碼組，則xi c(x)在按模xn+1運算下，也是一許用碼組。即若 xi c(x)ci(x) （模xn+1）則ci(x) 也是一許用碼組，且為c(x)碼組向左循環(huán)移位i次的結(jié)果。9.2 循環(huán)碼的生成多項式是如何定義的？ 生成多項式g(x)有什么特點和性質(zhì)？答：若一個循環(huán)碼的所有碼子多項式都是一個次數(shù)最低的非零首一多項式g(x)的倍式，則g(x)生成該碼，并稱g(x)為該碼的生成元或者生成多項式。g(x)的特點和性質(zhì)：1.g(x)是一個次數(shù)最低的唯一的首一多項式，其次數(shù)r=n-k正

4、好是碼字中檢驗元的數(shù)目。2.生成多項式g(x)是xn-1的因式。3.由xn-1=g(x)h(x),h(x)稱為校驗多項式。對于任意一個(n,k)循環(huán)碼，必有g(shù)(x)h(x)=0mod xn-1及ght=0.9.3 循環(huán)碼的生成多項式g(x)和校驗多項式h(x)之間有什么關(guān)系？如何在已知碼的生成多項式和校驗多項式的情況下，得到對應(yīng)的生成矩陣和校驗矩陣？解：若g（x）是（n,，k）循環(huán)碼的生成多項式，則有校驗多項式h(x)使g(x) h(x)=xn-1,h(x)為k次多項式。且有生成矩陣g和校驗矩陣h，g ht=0.若有生成多項式g(x)=gn-k xn-k + gn-k-1 xn-k-1 + +

5、g1 x+g0 ，由于k個碼多項式必線性無關(guān)，故可以構(gòu)造出生成矩陣g同樣的，也能通過h(x)求出校驗矩陣h。9.4試述利用生成多項式實現(xiàn)循環(huán)編碼的步驟。如何用電路實現(xiàn)編碼。答：系統(tǒng)循環(huán)碼的編碼方法：首先將信息元多項式m(x)乘以成為，然后將以生成多項得到余式,該余式就是校驗元多項式，從而得到碼字多項式。 用電路實現(xiàn)編碼可采用以為除式的除法電路。在除法電路的基礎(chǔ)上，將輸入信息元組從個寄存器的高端輸入，相當(dāng)于乘以。移位脈沖在1到個節(jié)拍內(nèi)，打向“1”，各信息元直接經(jīng)輸出，成為系統(tǒng)碼的前個碼元；同時它們又依次進入除法電路，進行除以的運算。運算結(jié)束時留在移位寄存器中的存數(shù)就是余式的系數(shù)。然后，cp在到個

6、節(jié)拍內(nèi)，打向“2”，使移位寄存器中的各校驗元依次輸出，形成一個長為的碼字。9.5 利用接收序列y(x)的伴隨式s(x)進行檢錯的原理是什么？答：接收端譯碼器由伴隨式確定錯誤圖樣然后從接收到的碼字中減去錯誤圖樣。9.6 什么樣的運算叫做s(x)的自發(fā)運算？它對循環(huán)碼的譯碼有何意義？解答：若是接收碼字多項式的伴隨式，則的一次循環(huán)移位 (mod )的伴隨式是在伴隨式計算電路中無輸入時，右移一位的結(jié)果（稱稱為自發(fā)運算），即有 把某一可糾正的錯誤圖樣e(x)及其所有的小于等于n1次的循環(huán)移位歸成一類，用一個錯誤圖樣來代表。譯碼時只要計算這個錯誤圖樣的伴隨式，該類中其它錯誤圖樣的伴隨式都可由該伴隨式在g(

7、x)除法電路中循環(huán)移位來得到。 把某一可糾正的錯誤圖樣e(x)及其所有的小于等于n1次的循環(huán)移位歸成一類，用一個錯誤圖樣來代表。譯碼時只要計算這個錯誤圖樣的伴隨式，該類中其它錯誤圖樣的伴隨式都可由該伴隨式在g(x)除法電路中循環(huán)移位來得到。9.7 meggit通用譯碼器有什么特點？為什么這種譯碼器能夠?qū)崿F(xiàn)連續(xù)譯碼輸出？答：特點：將s(x)計算電路與s(x)自發(fā)運算電路并行完成，實現(xiàn)了連續(xù)譯碼輸出。因為接收碼字y(x)一方面被送入n級移位寄存器，一方面被送入s(x)計算電路，經(jīng)n節(jié)拍后，將在s(x)計算電路中得到的s(x)送入自發(fā)運算電路。 s(x)自發(fā)運算電路在結(jié)構(gòu)上與s(x)計算電路相同。從

8、n+1拍至2n拍完成該碼字對應(yīng)伴隨式的自發(fā)運算及糾錯、譯碼輸出。于此同時，第二個接收碼字一方面被送入n級移位寄存器，一方面被送入s(x)計算電路?？梢?，前一個碼字的糾錯譯碼過程與后一個碼字的s(x)計算過程在時間上是重疊的。雖然每一個碼字在譯碼器中仍需逗留2n拍，但從整體上，該譯碼器實現(xiàn)了連續(xù)譯碼輸出。9.8 已知（7,3）碼的生成多項式g(x)=x4+x2+x+1，求其校驗多項式h(x)解：方法一： 因為x7-1 =（x+1）（x3+x+1）(x3+x2+1)，而g(x)=x4+x2+x+1，且g(x) h(x) =0 mod x7-1 ，所以得h(x) = x3+x2+1.方法二： 由于有

9、生成矩陣g和校驗矩陣h，使g ht= 0所以可以通過上式得到 所以可以得到h(x)=x3+x2+1.9.9 在gf(2)上可分解為以下既約多項式的乘積：當(dāng)構(gòu)成（15，9）碼時，有多少種不同的選擇？分別寫出對應(yīng)的生成多項式。解：根據(jù)題意：。該多項式構(gòu)成（15，9）碼共有3種不同的選擇，生成多項式分別為：9.10設(shè)(15,7)循環(huán)碼是由g(x)=x8+x7+x6+x4+1生成的。試回答：y(x)=x7+x5+x3+x+1是碼多項式嗎？求y(x)的伴隨式。答：y(x) = x7+x5+x3+x+1不是碼多項式。s(x) = y(x) mod g(x)= x7+x5+x3+x+1。9.11 設(shè)計一個由

10、g(x)= x4+x+1 生成的（15,11）循環(huán)漢明碼的編碼器。解答：循環(huán)漢明碼編碼器如下所示：9.12 證明：x10+x8+x5+x4+x2+x+1為（15，5）循環(huán)碼的生成多項式，并求：（1）該碼的生成矩陣。（2）當(dāng)信息多項式為m(x)= x4+x2+x+1時的系統(tǒng)碼多項式。（3）畫出以g(x)除法電路為核心的n-k級編碼器。證明： (x10+x8+x5+x4+x2+x+1)| x15-1 且最高次10=15-5，故為該碼的生成矩陣。（1）生成矩陣（2）校驗多項式r(x)=x10*m(x) mod g(x)=x5+x3+1 系統(tǒng)碼多項式為：x10*m(x)+ r(x)= x14+x12+

11、x11+x10+x5+x3+1（3）編碼器： 9.13 證明：由g(x)=x10+x7+x6+x4+x2+1可生成一個（21,11）循環(huán)碼。畫出此碼的伴隨式計算電路。若接受碼字多項式為y=x17+x5+1,其伴隨式是什么？解： 因為x21+1 = (x10+x7+x6+x4+x2+1)*(x11+x8+x7+x2+1)，因為g(x)=x10+x7+x6+x4+x2+1，所以校驗多項式為h(x)= x11+x8+x7+x2+1.故可以生成一個（21,11）的循環(huán)碼。 由于s(x)=y(x) mod g(x)，所以得到s(x)=x8+x6+x4+x3+1.則伴隨式的通式為s（i）(x)=xis(x

12、)=xi(x8+x6+x4+x3+1)9.14 已知一個循環(huán)碼的生成多項式，是的一個因子。求證：（1） 設(shè)n為奇數(shù)，則全1的n重矢量不是一個碼字；（2） 設(shè)n為偶數(shù)，則全1的n重矢量是一個碼字。證明：（1）用多項式表示全1的n重矢量：若為一個碼字多項式則由于即是的一個解當(dāng)n為奇數(shù)時，時，當(dāng)n為奇數(shù)時，時，即證得n為奇數(shù)時，則全1的n重矢量不是一個碼字；n為偶數(shù)時，則全1的n重矢量是一個碼字。9.15設(shè)計一個由g(x)=x4+x+1生成的(15,11)循環(huán)漢明碼的譯碼器。答：碼得校驗矩陣為h=14 13 1=11110101100100001111010110010000111101011001

13、0111010110010001假設(shè)信道錯誤出現(xiàn)在最高位, 即 =（100000000000000）, 對應(yīng)的錯誤圖樣多項式為e(x)= x14 可以求得相應(yīng)的伴隨式多項式：sx=x3+1=exmodgx=x14mod( x4+x+1) 即相應(yīng)的伴隨式多項式為x3+1 對應(yīng)的伴隨式為=(1001)相應(yīng)的譯碼電路為：9.16設(shè)a是gf（24）上的本原元，求a, a3 ,a5 的最小多項式。解答：若碼以a為根，即以a, a2 ,a4 ，a8，共軛根系為根，最小多項式為 m1(x)= x4+x+1若碼以a, a3 為根，即以a, a2 ,a4 ，a8，共軛根系和 a3 ,a6 ，a12，a24=a9 共軛根系為根，最小多項式為 m3(x)= x4+ x3+ x2+x+1若碼以a, a3, a5為根，即以a, a2 ,a4 ，a8，共軛根系, 和 a3 ,a6 ，a12，a24=a9 共軛根系和 a