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

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

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

k階矩陣，Ir

為r

r階單位方陣。

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

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

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

G的各行本身就是一個(gè)碼組。

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

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

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

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

S3錯(cuò)碼位置S1

S2

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

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

ei=vi–ci。定義：設(shè)碼C的校驗(yàn)矩陣為H，接收向量v的伴隨式為s=vHT。16第十六頁(yè)，共三十五頁(yè)，編輯于2023年，星期六譯碼步驟1）由接收向量v計(jì)算伴隨式s；2）由伴隨式s求得錯(cuò)誤圖樣e；3）c=v–e。17第十七頁(yè)，共三十五頁(yè)，編輯于2023年，星期六循環(huán)碼18第十八頁(yè)，共三十五頁(yè)，編輯于2023年，星期六 循環(huán)碼的概念： 循環(huán)性是指任一碼組字循環(huán)一位后仍然是該編碼中的一個(gè)碼字。例：一種(7,3)循環(huán)碼的全部碼字如下 表中第2碼字向右移一位即得到第5碼字；第5碼字向右移一位即得到第7碼字。碼組編號(hào)信息位監(jiān)督位碼組編號(hào)信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001019第十九頁(yè)，共三十五頁(yè)，編輯于2023年，星期六一般情況 若(an-1

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

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)

仍然是該編碼中的碼字。多項(xiàng)式表示法 一個(gè)長(zhǎng)度為n的碼字(an-1

an-2…a0)可以表示成

上式中x的值沒(méi)有任何意義，僅用它的冪代表碼元的位置。 例：碼字1100101可以表示為20第二十頁(yè)，共三十五頁(yè)，編輯于2023年，星期六循環(huán)碼的運(yùn)算整數(shù)的按模運(yùn)算 在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有

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

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

m

p(模n)

所以，在模n運(yùn)算下，一個(gè)整數(shù)m等于它被n除得的余數(shù)。21第二十一頁(yè)，共三十五頁(yè)，編輯于2023年，星期六碼多項(xiàng)式的按模運(yùn)算 若任意一個(gè)多項(xiàng)式F(x)被一個(gè)n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，即 則在按模N(x)運(yùn)算下，有 這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算。 例1：x3被(x3+1)除，得到余項(xiàng)1，即 例2： 因?yàn)?/p>

x

x3+1x4+x2+1

x4+x

x2+x+1

在模2運(yùn)算中加法和減法一樣。22第二十二頁(yè)，共三十五頁(yè)，編輯于2023年，星期六循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)T(x)是一個(gè)長(zhǎng)度為n的碼字，若 則T(x)也是該編碼中的一個(gè)碼字。

[證]設(shè)一循環(huán)碼為 則有 上式中的T(x)正是碼組T(x)向左循環(huán)移位i次的結(jié)果。 例：一循環(huán)碼為1100101，即 若給定i=3，則有 上式對(duì)應(yīng)的碼組為0101110，它正是T(x)向左移3位的結(jié)果。結(jié)論：一個(gè)長(zhǎng)為n的循環(huán)碼必定為按模(xn+1)運(yùn)算的一個(gè)余式。23第二十三頁(yè)，共三十五頁(yè)，編輯于2023年，星期六循環(huán)碼的生成如果有了生成矩陣G，就可以由k個(gè)信息位得出整個(gè)碼字A： 例:(7,4)碼 式中， 生成矩陣G的每一行都是一個(gè)碼組。因此，若能找到k個(gè)已知的碼字，就能構(gòu)成矩陣G。如前所述，這k個(gè)已知碼組必須是線性不相關(guān)的。在循環(huán)碼中，一個(gè)(n,k)碼有2k個(gè)不同的碼字。若用g(x)表示其中前(k-1)位皆為“0”的碼字，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個(gè)碼組是線性無(wú)關(guān)的。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣G。24第二十四頁(yè)，共三十五頁(yè)，編輯于2023年，星期六在循環(huán)碼中除全“0”碼組外，再?zèng)]有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n-k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n–k)，即連續(xù)“0”的個(gè)數(shù)多于(k–1)。顯然，這是與前面的結(jié)論矛盾的。我們稱這唯一的(n–k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。25第二十五頁(yè)，共三十五頁(yè)，編輯于2023年，星期六因此，循環(huán)碼的生成矩陣G可以寫成例：

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

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

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

將此g(x)代入上矩陣，得到 或 上式不符合G=[IkQ]形式，所以它不是標(biāo)準(zhǔn)生成矩陣。但它經(jīng)過(guò)線性變換后，不難化成標(biāo)準(zhǔn)陣。 此循環(huán)碼的碼字多項(xiàng)式表示式T(x)： 上式表明，所有碼字多項(xiàng)式T(x)都能夠被g(x)整除，而且任意一個(gè)次數(shù)不大于(k–1)的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。27第二十七頁(yè)，共三十五頁(yè)，編輯于2023年，星期六尋求碼生成多項(xiàng)式因?yàn)槿我庖粋€(gè)循環(huán)碼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)式，故xkT

(x)是一個(gè)n次多項(xiàng)式。由 可知，xk

T

(x)在模(xn+1)運(yùn)算下也是一個(gè)碼組，所以有 上式左端分子和分母都是n次多項(xiàng)式，故相除的商式Q(x)=1。因此，上式可以寫成28第二十八頁(yè)，共三十五頁(yè)，編輯于2023年，星期六將T(x)=h(x)g(x)和T

(x)=g(x)代入 化簡(jiǎn)后，得到上式表明，生成多項(xiàng)式g(x)應(yīng)該是(xn+1)的一個(gè)因子。例：(x7+1)可以分解為 為了求出(7,3)循環(huán)碼的生成多項(xiàng)式g(x)，需要從上式中找到一個(gè)(n–k)=4次的因子。這樣的因子有兩個(gè)，即 以上兩式都可以作為生成多項(xiàng)式。 選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼字也不同。29第二十九頁(yè)，共三十五頁(yè)，編輯于2023年，星期六循環(huán)碼的編碼方法用xn-k乘m(x)。這一運(yùn)算實(shí)際上是在信息碼后附加上(n–k)個(gè)“0”。例如，信息碼為110，它寫成多項(xiàng)式為m(x)=x2+x。當(dāng)n–k=7–3=4時(shí)，xn-km(x)=x4(x2+x)=x6+x5，它表示碼組1100000。用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即有 例：若選定g(x)=x4+x2+x+1，則有 上式是用碼多項(xiàng)式表示的運(yùn)算。它和下式等效：編出的碼字T(x)為：T(x)=xn-km(x)+r(x)

在上例中，T(x)=1100000+101=1100101 30第三十頁(yè)，共三十五頁(yè)，編輯于2023年，星期六循環(huán)碼的解碼方法在檢錯(cuò)時(shí)：當(dāng)接收碼字沒(méi)有錯(cuò)碼時(shí)，接收碼組R(x)必定能被g(x)整除，即下式 中余項(xiàng)r(x)應(yīng)為零；否則，有誤碼。當(dāng)接收碼組中的錯(cuò)碼數(shù)量過(guò)多，超出了編碼的檢錯(cuò)能力時(shí)，有錯(cuò)碼的接收碼組也可能被g(x)整除。這時(shí)，錯(cuò)碼就不能檢出了。在糾錯(cuò)時(shí)：用生成多項(xiàng)式g(x)除接收碼組R(x)，得出余