信息論與編碼循環(huán)碼

信息論與編碼循環(huán)碼1第一頁，共三十五頁，編輯于2023年，星期六線性分組碼的一般原理線性分組碼的構(gòu)造H矩陣（監(jiān)督陣）HAT=0T或AHT=0監(jiān)督陣2第二頁，共三十五頁，編輯于2023年，星期六H矩陣的性質(zhì)：

H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，等于監(jiān)督位個數(shù)r。

典型監(jiān)督陣可分解為[PIr]形式，P為r

k階矩陣，Ir

為r

r階單位方陣。

由代數(shù)理論可知，H矩陣的各行應(yīng)該是線性無關(guān)的

3第三頁，共三十五頁，編輯于2023年，星期六生成陣如果找到了碼的生成矩陣G，則編碼的方法就完全確定了。具有[IkQ]形式的生成矩陣稱為典型生成矩陣。系統(tǒng)碼4第四頁，共三十五頁，編輯于2023年，星期六G矩陣的性質(zhì)：

G矩陣的各行是線性無關(guān)的。

G的各行本身就是一個碼組。

如果已有k個線性無關(guān)的碼組，則可以用其作為生成矩陣G。5第五頁，共三十五頁，編輯于2023年，星期六錯誤圖樣

B–A=E錯誤圖樣接收碼發(fā)送碼6第六頁，共三十五頁，編輯于2023年，星期六2.監(jiān)督矩陣H和生成矩陣G（1）監(jiān)督矩陣第七頁，共三十五頁，編輯于2023年，星期六我們把H稱為監(jiān)督矩陣，或稱一致校驗矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為r×n階矩陣，H矩陣每行之間是彼此線性無關(guān)的。H矩陣可分成兩部分，其中P為r×k階矩陣，Ir為r×r階單位陣。能寫成H=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。第八頁，共三十五頁，編輯于2023年，星期六（2）生成矩陣第九頁，共三十五頁，編輯于2023年，星期六 稱為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×n階矩陣，各行也是線性無關(guān)的。生成矩陣也可以分為兩部分：其中Q為k×r階矩陣，Ik為k階單位陣，可以寫成式（8-12）形式的G矩陣，稱為典型生成矩陣。非典型形式的矩陣經(jīng)過運算也一定可以化為典型矩陣形式。第十頁，共三十五頁，編輯于2023年，星期六（3）監(jiān)督矩陣H和生成矩陣G之間的關(guān)系 由上可知，監(jiān)督矩陣H和生成矩陣G之間有一一對應(yīng)的關(guān)系。由于G的每一行都為碼字，因此它必然滿足式HAT=0T即HGT=0T第十一頁，共三十五頁，編輯于2023年，星期六3.線性分組碼的譯碼——伴隨式（校正子）S

若某一碼字為許用碼組，則它必然滿足式。利用這一關(guān)系，在接收端將收到的碼組和事先與發(fā)端約定好的監(jiān)督矩陣相乘，看是否為零。若滿足條件，則認(rèn)為接收正確；反之，則認(rèn)為傳輸過程中發(fā)生了錯誤，進而設(shè)法確定錯誤的數(shù)目和位置。第十二頁，共三十五頁，編輯于2023年，星期六例：設(shè)分組碼(n,k)中k=4，為了糾正1位錯碼，由上式可知，要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7。S1S2

S3錯碼位置S1

S2

S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼錯碼位置與校正子關(guān)系監(jiān)督關(guān)系式13第十三頁，共三十五頁，編輯于2023年，星期六 令S=BHT，稱為伴隨式或校正子。S=BHT=（A+E）HT=EHT

由此可見，伴隨式S與錯誤圖樣E之間有確定的線性變換關(guān)系，與發(fā)送碼組A無關(guān)。接收端譯碼器的任務(wù)就是從伴隨式確定錯誤圖樣，然后從接收到的碼字中減去錯誤圖樣。第十四頁，共三十五頁，編輯于2023年，星期六從以上分析可以得出線性分組碼譯碼的基本步驟：①計算接收碼組B的伴隨式S；②根據(jù)S找出錯誤圖樣E，判定誤碼位置；③根據(jù)E糾正錯誤，得到正確的碼組A=E+B。第十五頁，共三十五頁，編輯于2023年，星期六錯誤圖樣和伴隨式定義：發(fā)送碼字c=(c1,c2,…,cn)經(jīng)過有擾信道得到接收向量v=(v1,v2,…,vn)，則稱e=(e1,e2,…,en)為錯誤圖樣，其中

ei=vi–ci。定義：設(shè)碼C的校驗矩陣為H，接收向量v的伴隨式為s=vHT。16第十六頁，共三十五頁，編輯于2023年，星期六譯碼步驟1）由接收向量v計算伴隨式s；2）由伴隨式s求得錯誤圖樣e；3）c=v–e。17第十七頁，共三十五頁，編輯于2023年，星期六循環(huán)碼18第十八頁，共三十五頁，編輯于2023年，星期六 循環(huán)碼的概念： 循環(huán)性是指任一碼組字循環(huán)一位后仍然是該編碼中的一個碼字。例：一種(7,3)循環(huán)碼的全部碼字如下 表中第2碼字向右移一位即得到第5碼字；第5碼字向右移一位即得到第7碼字。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001019第十九頁，共三十五頁，編輯于2023年，星期六一般情況 若(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可以表示為20第二十頁，共三十五頁，編輯于2023年，星期六循環(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ù)。21第二十一頁，共三十五頁，編輯于2023年，星期六碼多項式的按模運算 若任意一個多項式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運算中加法和減法一樣。22第二十二頁，共三十五頁，編輯于2023年，星期六循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)T(x)是一個長度為n的碼字，若 則T(x)也是該編碼中的一個碼字。

[證]設(shè)一循環(huán)碼為 則有 上式中的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)運算的一個余式。23第二十三頁，共三十五頁，編輯于2023年，星期六循環(huán)碼的生成如果有了生成矩陣G，就可以由k個信息位得出整個碼字A： 例:(7,4)碼 式中， 生成矩陣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。24第二十四頁，共三十五頁，編輯于2023年，星期六在循環(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)碼就被確定了。25第二十五頁，共三十五頁，編輯于2023年，星期六因此，循環(huán)碼的生成矩陣G可以寫成例：

上表中的編碼為(7,3)循環(huán)碼，n=7,k=3,n–k=4，其中唯一的一個(n–k)=4次碼多項式，且前(k-1)=2位皆為“0”的碼字是第二碼字0010111，與它對應(yīng)的碼多項式，即生成多項式，為

g(x)=x4+x2+x+1。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001026第二十六頁，共三十五頁，編輯于2023年，星期六

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

將此g(x)代入上矩陣，得到 或 上式不符合G=[IkQ]形式，所以它不是標(biāo)準(zhǔn)生成矩陣。但它經(jīng)過線性變換后，不難化成標(biāo)準(zhǔn)陣。 此循環(huán)碼的碼字多項式表示式T(x)： 上式表明，所有碼字多項式T(x)都能夠被g(x)整除，而且任意一個次數(shù)不大于(k–1)的多項式乘g(x)都是碼多項式。27第二十七頁，共三十五頁，編輯于2023年，星期六尋求碼生成多項式因為任意一個循環(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。因此，上式可以寫成28第二十八頁，共三十五頁，編輯于2023年，星期六將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)碼碼字也不同。29第二十九頁，共三十五頁，編輯于2023年，星期六循環(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 30第三十頁，共三十五頁，編輯于2023年，星期六循環(huán)碼的解碼方法在檢錯時：當(dāng)接收碼字沒有錯碼時，接收碼組R(x)必定能被g(x)整除，即下式 中余項r(x)應(yīng)為零；否則，有誤碼。當(dāng)接收碼組中的錯碼數(shù)量過多，超出了編碼的檢錯能力時，有錯碼的接收碼組也可能被g(x)整除。這時，錯碼就不能檢出了。在糾錯時：用生成多項式g(x)除接收碼組R(x)，得出余