信息論理論基礎(chǔ)

信息論基礎(chǔ)

第4章抗干擾二元編碼韓宇輝6/23/20241第4章抗干擾二元編碼4.1抗干擾二元編碼的基本概念4.2檢錯(cuò)碼4.3用于單向信道的簡(jiǎn)單糾錯(cuò)碼4.4糾一位錯(cuò)誤的漢明碼4.5循環(huán)碼4.6糾正獨(dú)立錯(cuò)誤的卷積碼4.7糾正突發(fā)錯(cuò)誤的編碼4.8有限域的基本知識(shí)6/23/202424.1抗干擾二元編碼的基本概念6/23/202434.1.1抗干擾編碼的基本思想000110110011奇校驗(yàn)抗干擾編碼的基本思想：利用剩余的增加來換取可靠性的提高信息元監(jiān)督元許用碼字：系統(tǒng)實(shí)際使用的碼字。001,010,100,111禁用碼字：系統(tǒng)中不使用的碼字。000,011,101,1106/23/202444.1.2幾個(gè)定義①碼距（漢明距離）W=x1x2…xn

xi∈{0,1}W’=x1’x2’…xn’xi’

∈{0,1}②最小碼距（最小漢明距離）一個(gè)碼組（碼字）集合中，兩碼字間的最小距離dmin稱為該碼字集合的最小距離，簡(jiǎn)稱最小碼距。③碼重（漢明重量）碼組中所含碼元“1”的數(shù)量，稱為該碼組的重量，簡(jiǎn)稱碼重。6/23/202454.1.3最小碼距與糾檢錯(cuò)能力的關(guān)系1.譯碼準(zhǔn)則X:{x1,x2,…,xn}Y:{y1,y2,…,ym}P(Y/X):{p(yj/xi);i=1,2,…n;j=1,2,…m這時(shí)定義一個(gè)收到y(tǒng)j后判定為xi的單值函數(shù)，即：F(yj)=xi(i=1,2,…n;j=1,2,…m)；這個(gè)函數(shù)稱為譯碼函數(shù)。它構(gòu)成一個(gè)譯碼函數(shù)組，這些函數(shù)的值組成了譯碼準(zhǔn)則。對(duì)于有n個(gè)輸入，m個(gè)輸出的信道來說，可以有nm個(gè)不同的譯碼準(zhǔn)則。6/23/202462.最小碼距譯碼準(zhǔn)則若d(x*j,yj)≤d(xi,yj)

(對(duì)一切的i)，則F(yj)=x*j(j=1,2,…m，x*j

∈X)3.最小碼距與糾檢錯(cuò)能力的關(guān)系【例】X：{0000000,1111111}，

dmin=7檢錯(cuò)能力：發(fā)送碼字：接收碼字：判斷結(jié)果：糾錯(cuò)能力：發(fā)送碼字：接收碼字：譯碼結(jié)果：00000000000000√00000000000000√10000000000000√11000000000000√11100001111111

×11110001111111

×11111001111111

×11111101111111

×11111110000000最多可以發(fā)現(xiàn)6位錯(cuò)誤0000000傳輸正確√

最多可以糾正3位錯(cuò)誤1000000傳輸錯(cuò)誤

√

1100000傳輸錯(cuò)誤

√

1110000傳輸錯(cuò)誤

√

1111000傳輸錯(cuò)誤√

1111100傳輸錯(cuò)誤

√

1111110傳輸錯(cuò)誤√

1111111傳輸正確

×

6/23/20247糾錯(cuò)同時(shí)檢錯(cuò)的能力糾正1位錯(cuò)誤：發(fā)送碼字：接收碼字：判斷結(jié)果：譯碼結(jié)果：糾正2位錯(cuò)誤：發(fā)送碼字：接收碼字：判斷結(jié)果：譯碼結(jié)果：0000000000000010000001100000111000011110001111100111111011111110000000最多可以同時(shí)發(fā)現(xiàn)5位錯(cuò)誤0000000傳輸正確√

1000000傳輸錯(cuò)誤√

1100000傳輸錯(cuò)誤√

1110000傳輸錯(cuò)誤√

1111000傳輸錯(cuò)誤√

1111100傳輸錯(cuò)誤√

1111110傳輸錯(cuò)誤√1111111傳輸正確

×

最多可以同時(shí)發(fā)現(xiàn)4位錯(cuò)誤0000000

√0000000

√不進(jìn)行譯碼不進(jìn)行譯碼不進(jìn)行譯碼不進(jìn)行譯碼1111111

×1111111

×傳輸正確√

傳輸錯(cuò)誤√

傳輸錯(cuò)誤√

傳輸錯(cuò)誤√

傳輸錯(cuò)誤√

傳輸錯(cuò)誤√

傳輸錯(cuò)誤√傳輸正確

×

0000000

√0000000

√0000000√不進(jìn)行譯碼√不進(jìn)行譯碼1111111

×1111111

×1111111

×6/23/20248若發(fā)現(xiàn)e個(gè)錯(cuò)誤，則要求dmin≥e+1;若糾正t個(gè)錯(cuò)誤，則要求dmin≥2t+1;若糾正t個(gè)錯(cuò)誤，同時(shí)發(fā)現(xiàn)e個(gè)錯(cuò)誤，則要求dmin≥t+e+1（t<e

）6/23/202494.1.4抗干擾編碼的基本原理1.原理：

dmin與糾檢錯(cuò)能力的關(guān)系2.實(shí)現(xiàn)方法：信息元+監(jiān)督元3.代數(shù)編碼：信息元與監(jiān)督元是按一定的代數(shù)關(guān)系互相制約的。(1)分組碼（塊碼）

k—信息位長(zhǎng)度

n—碼長(zhǎng)

r=n-k—監(jiān)督位長(zhǎng)度特點(diǎn)：無記憶性(n,k)分組碼的碼率（編碼效率）：η=R/C=H(A)/Hmax(A)=k/n邏輯網(wǎng)絡(luò)12k12n......6/23/202410分組碼按其結(jié)構(gòu)可以分為系統(tǒng)碼和非系統(tǒng)碼。如果在一個(gè)分組碼碼字中，信息元安排在前k位，而監(jiān)督元安排在后n-k=r位，則稱其為系統(tǒng)碼，否則就稱為非系統(tǒng)碼。(2)卷積碼（連環(huán)碼）

m=m’+1—編碼器的約束長(zhǎng)度或編碼約束長(zhǎng)度

n=n0×m—卷積碼的約束長(zhǎng)度

特點(diǎn)：有記憶性，輸出不僅與當(dāng)時(shí)的輸入有關(guān)，還與前m’個(gè)單位時(shí)間的輸入有關(guān)。(n0,k0,m)卷積碼的碼率（編碼效率）：η=k0/n0時(shí)序網(wǎng)絡(luò)12k012n0......6/23/2024114.抗干擾編碼的分類(1)用途：檢錯(cuò)碼和糾錯(cuò)碼(2)干擾的性質(zhì)：糾正獨(dú)立錯(cuò)誤的編碼和糾正突發(fā)錯(cuò)誤的編碼

獨(dú)立錯(cuò)誤也稱為隨機(jī)錯(cuò)誤，是由隨機(jī)噪聲引起的，其特點(diǎn)是各碼元發(fā)生錯(cuò)誤與否是互相獨(dú)立的，因而一般不會(huì)成片地出現(xiàn)錯(cuò)誤。

突發(fā)錯(cuò)誤是由突發(fā)噪聲（脈沖噪聲、深衰落、接觸不良引起噪聲等）引起的，其特點(diǎn)是各碼元是否發(fā)生錯(cuò)誤存在某種相關(guān)性。通常稱突發(fā)錯(cuò)誤持續(xù)時(shí)間內(nèi)的碼元數(shù)目為突發(fā)長(zhǎng)度。(3)對(duì)信息的處理方式：分組碼和卷積碼(4)約束關(guān)系：線性碼和非線性碼(5)信息元的位置：系統(tǒng)碼和非系統(tǒng)碼6/23/2024125.差錯(cuò)控制系統(tǒng)的分類(1)ARQ(AutomaticRepeatreQuest)自動(dòng)反饋重傳采用檢錯(cuò)碼，接收端收到碼字后判斷在傳輸中有無錯(cuò)誤產(chǎn)生，并通過反饋信道把檢測(cè)結(jié)果告訴發(fā)送端。發(fā)端把收端認(rèn)為有錯(cuò)的消息再次傳送，直到收端認(rèn)為正確為止。優(yōu)點(diǎn)：譯碼設(shè)備簡(jiǎn)單，由于同一種碼的檢錯(cuò)能力比糾錯(cuò)能力要高得多，因而整個(gè)系統(tǒng)能獲得極低的誤碼率。缺點(diǎn)：應(yīng)用ARQ方式必須有一條從收端至發(fā)端的反饋信道，只適用于點(diǎn)對(duì)點(diǎn)的方式，并要求收、發(fā)兩端必須互相配合，其控制電路比較復(fù)雜，實(shí)時(shí)性也較差。6/23/202413(2)FEC(ForwardErrorCorrection)前向糾錯(cuò)采用糾錯(cuò)碼，接收端收到碼字后，自動(dòng)地糾正傳輸中的錯(cuò)誤。優(yōu)點(diǎn)：不需要反饋信道，既適用于點(diǎn)對(duì)點(diǎn)的方式，也適用于點(diǎn)對(duì)多點(diǎn)的方式，實(shí)時(shí)性較好，控制電路也比較簡(jiǎn)單。缺點(diǎn)：譯碼設(shè)備較復(fù)雜，編碼效率較低。(3)HFC(HybridErrorCorrection)混合糾錯(cuò)是前兩種方式的結(jié)合。發(fā)端發(fā)送的碼既能檢錯(cuò)、又有一定的糾錯(cuò)能力。收端譯碼時(shí)若發(fā)現(xiàn)錯(cuò)誤個(gè)數(shù)在碼的糾錯(cuò)能力以內(nèi)，則自動(dòng)進(jìn)行糾錯(cuò)；若錯(cuò)誤個(gè)數(shù)超過了碼的糾錯(cuò)能力，但能檢測(cè)出來，則通過反饋信道告知發(fā)方重發(fā)。6/23/2024144.2檢錯(cuò)碼6/23/202415一致監(jiān)督檢錯(cuò)碼也叫一致監(jiān)督校驗(yàn)碼或奇偶校驗(yàn)碼。1.原理：信息元（k位）：x1，x2，…，xk監(jiān)督元（1位）：xn=xk+1偶校驗(yàn)：奇校驗(yàn)：4.2.1一致監(jiān)督檢錯(cuò)碼6/23/2024162.漏檢概率奇偶校驗(yàn)碼只能發(fā)現(xiàn)碼字中的奇數(shù)個(gè)錯(cuò)誤，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。n為偶數(shù)：n為奇數(shù)：若，則6/23/202417定比碼也稱恒比碼、等重碼或范·德倫碼，每個(gè)碼字中“1”與“0”的比例是固定的，“1”的個(gè)數(shù)也是固定的。

1.五三定比碼五三定比碼每個(gè)碼字的碼長(zhǎng)為5，含有3個(gè)“1”和2個(gè)“0”的碼字作為許用碼字。

(1)許用碼字?jǐn)?shù)目：

禁用碼字?jǐn)?shù)目：4.2.2定比碼6/23/202418

(2)漏檢概率若“1”錯(cuò)成“0”的數(shù)目正好等于“0”錯(cuò)成“1”的數(shù)目，則五三定比碼不能發(fā)現(xiàn)這類錯(cuò)誤。一個(gè)碼字中有2位錯(cuò)誤，且其中1位“1”錯(cuò)成“0”，1位“0”錯(cuò)成“1”的概率為一個(gè)碼字中有4位錯(cuò)誤，且其中2位“1”錯(cuò)成“0”，2位“0”錯(cuò)成“1”的概率為因此，漏檢概率為當(dāng)時(shí)，6/23/202419(3)編碼效率

η=R/C=H/Hmax=log10/log32≈66%2.七三定比碼七三定比碼每個(gè)碼字的碼長(zhǎng)為7，含有3個(gè)“1”和4個(gè)“0”的碼字作為許用碼字。

(1)許用碼字?jǐn)?shù)目：

禁用碼字?jǐn)?shù)目：

(2)編碼效率

η=R/C=H/Hmax=log35/log128≈72%6/23/202420

(3)漏檢概率一個(gè)碼字中有2位錯(cuò)誤，且其中1位“1”錯(cuò)成“0”，1位“0”錯(cuò)成“1”的概率為一個(gè)碼字中有4位錯(cuò)誤，且其中2位“1”錯(cuò)成“0”，2位“0”錯(cuò)成“1”的概率為一個(gè)碼字中有6位錯(cuò)誤，且其中3位“1”錯(cuò)成“0”，3位“0”錯(cuò)成“1”的概率為因此，漏檢概率為當(dāng)時(shí)，6/23/2024214.3用于單向信道的簡(jiǎn)單糾錯(cuò)碼6/23/202422編碼效率：η=1/n(1)逐位重復(fù)：用于糾正隨機(jī)錯(cuò)誤。(2)逐段重復(fù)：還可用于糾正突發(fā)錯(cuò)誤。例如，10110100逐位重復(fù)，三重碼：111000111111000111000000逐段重復(fù)，四位一段，三重碼：10111011

101101000100

01004.3.1簡(jiǎn)單重復(fù)碼將信息重復(fù)多次，只要正確傳輸?shù)拇螖?shù)多于傳錯(cuò)的次數(shù)，則可以將錯(cuò)誤糾正過來。重復(fù)次數(shù)n通常為奇數(shù)。6/23/2024234.4糾一位錯(cuò)誤的漢明碼6/23/2024241.線性分組碼的定義若分組碼的監(jiān)督元與信息元之間是一種線性約束關(guān)系，則稱其為線性分組碼。(n,k)線性分組碼的碼率：η=k/n許用碼字?jǐn)?shù)目：2k禁用碼字?jǐn)?shù)目：2n-2k系統(tǒng)碼：[x1x2…xk

xk+1xk+2…xn]信息元監(jiān)督元6/23/2024252.線性分組碼的監(jiān)督矩陣線性分組碼監(jiān)督元與信息元之間的線性關(guān)系可以用二元域上的線性方程組描述。整理得：6/23/202426將方程組用矩陣方程來表示，可得監(jiān)督矩陣[H][H][C]T=[0]碼字向量[C]=[x1

x2…xn

]6/23/202427r×k子陣Pr×r單位陣Irr=n-k行：r個(gè)監(jiān)督元，r個(gè)監(jiān)督方程n列：n個(gè)碼元之間的監(jiān)督關(guān)系(n,k)系統(tǒng)線性分組碼監(jiān)督矩陣形式:(典型監(jiān)督矩陣或標(biāo)準(zhǔn)監(jiān)督矩陣)[H]=[P

Ir]6/23/2024283.線性分組碼的生成矩陣6/23/202429碼字[C]信息碼組[m]生成矩陣[G]由于對(duì)于矩陣A，B，C有因此[C]=[m][G]6/23/202430[G]=[Ik

PT](n,k)系統(tǒng)線性分組碼生成矩陣形式:(典型生成矩陣或標(biāo)準(zhǔn)生成矩陣)子陣PTk×k單位陣Ikk行×n列6/23/202431【例】已知線性分組碼的生成矩陣[G]，寫出信息碼組[m1]=[1000]，[m2]=[0100]，[m3]=[0010]，[m4]=[0001]，[m5]=[1100]，[m6]=[1110]，[m7]=[1111]對(duì)應(yīng)的各個(gè)碼字。

[C1]=[m1][G]=[1000][G]=[1000011][C2]=[m2][G]=[0100][G]=[0100101][C3]=[m3][G]=[0010][G]=[0010110][C4]=[m4][G]=[0001][G]=[0001111]解：6/23/202432

[C5]=[m5][G]=[1100][G]=[1100110][C6]=[m6][G]=[1110][G]=[1110000][C7]=[m7][G]=[1111][G]=[1111111](n,k)線性分組碼的2k個(gè)碼字構(gòu)成二元n重矢量空間中的一個(gè)k維子空間。(n,k)線性分組碼的生成矩陣由k個(gè)線性無關(guān)的碼字矢量組成，構(gòu)成k維子空間的一個(gè)基底，其線性組合可以生成所有的碼字。6/23/202433【例】已知線性分組碼的監(jiān)督矩陣為判斷其碼長(zhǎng)和信息位長(zhǎng)度，并寫出其生成矩陣[G]。解：r=3，n=7，

k=4[H]=[P

I3][G]=[I4

PT]6/23/2024344.線性分組碼的譯碼(1)錯(cuò)誤圖樣發(fā)送碼字：接收碼字：錯(cuò)誤圖樣：ei=1表明相應(yīng)位有錯(cuò)，ei=0表明相應(yīng)位無錯(cuò)。6/23/202435(2)校驗(yàn)矩陣定義[S]=[H][R]T為校驗(yàn)矩陣，也稱為校驗(yàn)子或伴隨式。若[S]=0，表明收到的碼字為許用碼字，譯碼器認(rèn)為接收碼字無錯(cuò)誤。若[S]≠0，表明收到的碼字為禁用碼字，可以判定接收碼字一定有錯(cuò)誤。由于因此校驗(yàn)子與發(fā)送碼字無關(guān)，而僅與錯(cuò)誤圖樣有關(guān)。6/23/202436(3)校驗(yàn)子與譯碼【例】(7,4)線性分組碼的監(jiān)督矩陣為(1)無錯(cuò)

[E]=[0000000](2)錯(cuò)一位

[E]=[1000000][E]=[0100000][E]=[0010000]

[S]=[H][E]T=[000]T…[S]=[H][E]T=[011]T[S]=[H][E]T=[101]T[S]=[H][E]T=[110]T6/23/202437若校驗(yàn)子為[0]，認(rèn)為收到的碼字沒有錯(cuò)誤；若校驗(yàn)子恰好等于[H]的第i列，認(rèn)為接收碼字的第i位發(fā)生了錯(cuò)誤。線性分組碼可以糾正1位錯(cuò)誤需滿足的條件：

[H]的各個(gè)列不同且不含有全0列；

2r-1≥n。6/23/2024385.漢明碼(1)漢明碼的定義對(duì)于任意正整數(shù)r≥3，存在有下列參數(shù)的線性分組碼：碼長(zhǎng)：n

≤2r-1信息位：k=n-r監(jiān)督位：r=n-k最小碼距：dmin=3

這種碼稱為漢明碼。若n

=2r-1稱為狹義漢明碼或完備漢明碼；若n

<2r-1稱為廣義漢明碼。(2)漢明碼[H]矩陣的構(gòu)造將2r-1非全0的r維列向量作為[H]的各列。6/23/202439【例】構(gòu)造(7,4)漢明碼的監(jiān)督矩陣。解：n=7，k=4，r=n-k=3。由于n

=2r-1，故為狹義漢明碼。將7個(gè)非全0的3維列向量作為[H]的各列即可。或系統(tǒng)碼非系統(tǒng)碼6/23/202440(3)漢明碼的錯(cuò)誤譯碼概率①狹義漢明碼狹義漢明碼可以糾正一位錯(cuò)誤，因此其錯(cuò)誤譯碼概率為：由于當(dāng)時(shí)，有因此當(dāng)時(shí)，有所以6/23/202441②廣義漢明碼

廣義漢明碼可以糾正一位錯(cuò)誤，還可以糾正部分2位及2位以上的錯(cuò)誤，因此其錯(cuò)誤譯碼概率：比如，(6,3)廣義漢明碼的監(jiān)督矩陣為錯(cuò)2位時(shí)：若第1位和第6位錯(cuò)，或者第2位和第5位錯(cuò)，或者第3位和第4位錯(cuò)，校驗(yàn)子均為[111]T。因此，不妨規(guī)定當(dāng)校驗(yàn)子為[111]T時(shí)，譯作第1位和第6位錯(cuò)。此時(shí)，該廣義漢明對(duì)于第1位和第6位錯(cuò)這種錯(cuò)兩位的情況也可以糾正。6/23/202442(4)增余漢明碼在漢明碼的基礎(chǔ)上，再增加一位監(jiān)督元，使?jié)h明碼的最小碼距dmin=4，可以在糾一位錯(cuò)的同時(shí)檢兩位錯(cuò)，這種線性分組碼稱為增余漢明碼。增加的監(jiān)督元通常取為原漢明碼所有碼元的模2和，也就是說增余漢明碼的[H]矩陣是在原漢明碼[H]矩陣的最右側(cè)加上一個(gè)全0列，再在下面加上一個(gè)全為1的行。6/23/202443(7,4)漢明碼(8,4)增余漢明碼[H]矩陣的各個(gè)列不同，且任何兩列之和不同于另一列，因此可以糾1位錯(cuò)的同時(shí)檢出2位錯(cuò)。增余漢明碼的構(gòu)成方法不唯一。

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

16/23/2024444.5循環(huán)碼6/23/2024451.循環(huán)碼的定義具有循環(huán)移位自閉性的線性分組碼稱為循環(huán)碼。所謂循環(huán)移位自閉性是指碼字集合中的任何一個(gè)碼字的循環(huán)移位也是該碼字集合中的一個(gè)碼字。若C(0)=[cn-1,cn-2,……c1,c0]∈C(C為許用碼字集合)

，

則C(1)=[cn-2,cn-3,……c0,cn-1]∈C。0000000001110101001110111010循環(huán)碼1001110101001111010011110100循環(huán)碼000001010011信息碼100101110111信息碼(7,3)系統(tǒng)循環(huán)碼6/23/2024462.循環(huán)碼的多項(xiàng)式描述一個(gè)(n,k)循環(huán)碼的碼字c=[cn-1,cn-2,……,c1,c0]可以用一個(gè)二元域上的n-1次多項(xiàng)式表示：

c(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0

ci

∈{0,1}

這個(gè)多項(xiàng)式稱為碼字多項(xiàng)式或碼多項(xiàng)式。碼字矢量的向左循環(huán)移位一次可以用x乘上C(x)后取模xn-1(或xn+1)來表示。模xn-1相當(dāng)于xn-1=0，即xn=1

xc(x)=x(cn-1xn-1+cn-2xn-2+……+c1x+c0)=cn-1xn+cn-2xn-1+……+c1x2+c0

x=cn-2xn-1+……+c1x2+c0

x+cn-1(模xn-1)6/23/2024473.循環(huán)碼的生成多項(xiàng)式定義：(n,k)循環(huán)碼中，次數(shù)最低的非0碼多項(xiàng)式是唯一的，其次數(shù)為r=n-k次。該多項(xiàng)式稱為循環(huán)碼的生成多項(xiàng)式。

g(x)=grxr+gr-1xr-1+……+g1x+g0（gr=g0=1）g(x),xg(x),x2g(x),…,xk-1g(x)為k個(gè)線性無關(guān)的碼字，可以作為該循環(huán)碼生成矩陣的k行。6/23/202448信息碼組[m]=[mk-1,mk-2,…,m0]對(duì)應(yīng)的碼多項(xiàng)式為：

c(x)=[mk-1,mk-2,…,m0][G(x)]=mk-1xk-1g(x)+mk-2xk-2g(x)+…+m0g(x)=m(x)g(x)結(jié)論：所有循環(huán)碼的碼多項(xiàng)式都是其生成多項(xiàng)式g(x)的倍式；反之，任何次數(shù)不大于n-1次的多項(xiàng)式也一定是碼多項(xiàng)式。6/23/2024494.循環(huán)碼的編碼(1)非系統(tǒng)循環(huán)碼c(x)=m(x)g(x)【例】已知(7,4)循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x+1，求信息碼組[0101]對(duì)應(yīng)的循環(huán)碼碼字。解：

m(x)=x2+1

c(x)=m(x)g(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1=x5+x2+x+1[C]=[0100111]6/23/202450(2)系統(tǒng)循環(huán)碼信息多項(xiàng)式m(x)=mk-1xk-1+mk-2xk-2+…+m0所對(duì)應(yīng)的系統(tǒng)循環(huán)碼的碼多項(xiàng)式c(x)應(yīng)滿足如下條件：①

c(x)的次數(shù)不大于n-1次，即可以表示c(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0；②

c(x)為g(x)的倍式；③

cn-1=mk-1，cn-2=mk-2，…，cn-k=m0。系統(tǒng)循環(huán)碼編碼步驟：

①

②

(r(x)次數(shù)≤n-k-1)

③6/23/202451由于因此可見，c(x)為g(x)的倍式，條件②滿足。6/23/202452【例】(7,4)循環(huán)碼g(x)=x3+x+1，求m=[1010]的系統(tǒng)循環(huán)碼碼字。解：m(x)=x3+x

xn-km(x)=x3(x3+x)=x6+x4

C(x)=xn-km(x)+r(x)=x6+x4+x+1；[C]=[1010011]x3x6+x4+x3

x3

除式x6+x4x3+x+1+1x3+x+1x+1被除式商式余式6/23/202453(3)如何確定g(x)?定理1：(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是xn-1的因式。定理2：若g(x)是一個(gè)n-k次多項(xiàng)式，且為xn-1的因式，則g(x)一定可以生成一個(gè)(n,k)循環(huán)碼。例如，x7-1=(x+1)(x3+x2+1)(x3+x+1)(7,6)循環(huán)碼：g(x)=(x+1)(7,4)循環(huán)碼：g(x)=x3+x2+1或g(x)=x3+x+1(7,3)循環(huán)碼：g(x)=(x+1)(x3+x2+1)

或g(x)=(x+1)(x3+x+1)(7,1)循環(huán)碼：g(x)=(x3+x2+1)(x3+x+1)結(jié)論：xn-1的諸因式?jīng)Q定了所有碼長(zhǎng)為n的循環(huán)碼。6/23/2024545.循環(huán)碼的譯碼發(fā)送碼字多項(xiàng)式：c(x)=cn-1xn-1+cn-2xn-2+……c1x+c0錯(cuò)誤圖樣多項(xiàng)式：e(x)=en-1xn-1+en-2xn-2+……e1x+e0接收碼字多項(xiàng)式：c’(x)=cn-1’xn-1+cn-2’xn-2+……+c1’x+c0’

c’(x)=c(x)+e(x)校驗(yàn)子多項(xiàng)式：s(x)≡c’(x)≡

e(x)[模g(x)]

s(x)=sr-1xr-1+sr-2xr-2+…+s0

——r-1次多項(xiàng)式若s(x)

=0，表明收到的碼字為許用碼字，譯碼器認(rèn)為接收碼字無錯(cuò)誤。若s(x)≠0，表明收到的碼字為禁用碼字，可以判定接收碼字一定有錯(cuò)誤。6/23/202455【例】(7,4)循環(huán)碼g(x)=x3+x+1，求接收碼字不錯(cuò)或只錯(cuò)一位時(shí)的校驗(yàn)子多項(xiàng)式。e(x)s(x)[s2,s1,s0]0000011001xx010x2x2100x3x+1011x4x2+x110x5x2+x+1111x6x2+11016/23/202456這個(gè)表給出了接收碼字不出錯(cuò)或只錯(cuò)一位時(shí)校驗(yàn)子多項(xiàng)式和校驗(yàn)子矢量的結(jié)果。根據(jù)這個(gè)表可以進(jìn)行譯碼。例如，發(fā)送碼字多項(xiàng)式為c(x)=x4+x2+x

接收碼字多項(xiàng)式為c’(x)=x4+x3+x2+x

g(x)=x3+x+1

校驗(yàn)子多項(xiàng)式為：s(x)≡c’(x)[模g(x)]=x+1

查表可知e(x)=x3

因此

c(x)=c’(x)+e(x)=x4+x2+x

發(fā)送碼字為00101106/23/2024576.截短循環(huán)碼通常xn-1只能分解出不多的幾個(gè)因式，因此使得給定長(zhǎng)度為n的循環(huán)碼的數(shù)量往往很少。為了克服這個(gè)缺點(diǎn)，出現(xiàn)了截短循環(huán)碼。對(duì)于一個(gè)(n,k)循環(huán)碼，若取所有前i個(gè)信息元均為0的碼字構(gòu)成一個(gè)子集(0<i<k)，其監(jiān)督位長(zhǎng)度不變，信息位長(zhǎng)度減少至k-i位，則得到一個(gè)(n-i,k-i)碼，稱為截短循環(huán)碼或縮短循環(huán)碼。截短循環(huán)碼是原循環(huán)碼的子集，因此它的最小碼距保證了它的糾錯(cuò)能力不會(huì)低于原來的(n,k)循環(huán)碼。6/23/202458截短循環(huán)碼的[H]矩陣可以從原碼的[H]矩陣中除去前i列而得到，[G]矩陣可以從原碼的[G]矩陣中除去前i列和前i行而得到。例如，可以由(7,4)循環(huán)碼構(gòu)成(5,2)截短循環(huán)碼。(7,4)循環(huán)碼(5,2)截短循環(huán)碼6/23/202459截短循環(huán)碼的[H]矩陣可以從原碼的[H]矩陣中除去前i列而得到，[G]矩陣可以從原碼的[G]矩陣中除去前i列和前i行而得到。例如，可以由(7,4)循環(huán)碼構(gòu)成(5,2)截短循環(huán)碼。(7,4)循環(huán)碼(5,2)截短循環(huán)碼6/23/2024604.6糾正獨(dú)立錯(cuò)誤的卷積碼6/23/202461卷積碼的最大特點(diǎn)是有記憶性，(n0,k0,m)卷積碼編碼器在j時(shí)刻輸出與j，j-1，j-2，…，j-m+1共m個(gè)單位時(shí)間的輸入有關(guān)。m