編碼原理 習(xí)題 含答案或提示

糾錯(cuò)編碼課程習(xí)題及解答提示

/.奇校驗(yàn)碼碼字是。=(加0，?，''，4?0?其中奇校驗(yàn)位P滿足方程?

m+m+，，+6+p=lmod2

01A-l

證明奇校驗(yàn)碼的檢錯(cuò)能力與偶奇校驗(yàn)碼的檢錯(cuò)能力相同,但奇校驗(yàn)碼不是線性分組碼。

證明提示：

奇數(shù)個(gè)差錯(cuò)的發(fā)生總導(dǎo)致校驗(yàn)方程不滿足。全0向量不是奇校驗(yàn)碼碼字。

2.一個(gè)(6,2)線性分組碼的一致校驗(yàn)矩陣為

入100011

TT_h00011

-00101

的01110」

㈤求力」=123,4使該碼的最小碼距4而0230

(2)求該碼的系統(tǒng)碼生成矩陣Gs及其所有4個(gè)碼字。

解題提示：

(1)對(duì)H作行初等變換得

h100011

H=h+h10010

*21

h+h10100

31

h+h+h01000

L423」

要使最小碼距等于3,有力，人+6h+h+h中任意兩項(xiàng)為1,其余為零。當(dāng)要使最

11213423

小碼距大于3,有力；々+q，4+&q+力，+4中三項(xiàng)或四項(xiàng)均為1,其余為零。有上述關(guān)系可以

求得一組或多組關(guān)于,,i=1,2,3,4的解。

(2)對(duì)〃'作行初等變換得

[h+h-h010001

||「九31010°

7

H=3I=pQ/I

I/1+A1001olr

2h'1000jj

3.一個(gè)糾錯(cuò)碼的全部消息與碼字的對(duì)應(yīng)關(guān)系如下：

(00)—(00000)-(01)—(00111).(10)—(11110)?(11)—(11001)

(1)證明該碼是線性分組碼；

(2)求該碼的碼長(zhǎng)，編碼效率和最小碼距；

(3)求該碼的生成矩陣和一致校驗(yàn)矩陣；

(4)構(gòu)造該碼在BSC上的標(biāo)準(zhǔn)陣列；

(5)若在轉(zhuǎn)移概率P=10-3的BSC上消息等概發(fā)送?求用標(biāo)準(zhǔn)陣列譯碼后的碼字差錯(cuò)概率和

消息比特差錯(cuò)概率。

解題提示：

(1)任意兩個(gè)碼字的和是另一個(gè)碼字且全零向量為碼字。

_logMlog42

(2)碼長(zhǎng)為向量長(zhǎng)，即"=5。碼字?jǐn)?shù)為4,故區(qū)=q=」=_。最小非零碼字的

〃55

重量為min緲=d=3。

(3)因?yàn)榇a字?jǐn)?shù)為4,任意兩非零碼字構(gòu)成生成矩陣的行向量G=?按G與H正交的

Loomj

「111101

條件，解得H的一種可能情況等于I11000L

(4)標(biāo)準(zhǔn)陣列見(jiàn)題表(3.1)o

題表(3.1)標(biāo)準(zhǔn)陣列

^=00000r=00111,=11110,=11001

0123

e=(X)(XK)()(K)(X)001111111011001

0

e=00001000010011011111110c0

1

e=00010(XX)108)1(11110011011

2

e=0010000100000111101011101

3

e=01000010(X)011111011010001

4

e=1000010000101110111001001

5

e=100101(X)1()101(10110001011

6

e

:=1010010100100110101001101

⑸按題解(4)的標(biāo)準(zhǔn)陣列譯碼，記X是標(biāo)堆陣列中碼字，對(duì)應(yīng)的列，E是包括尢錯(cuò)圖案和全

部可糾正差錯(cuò)圖案的集合、那么碼字差錯(cuò)概.為「]

P")=1一乜P")尸(廠=c+ewN)=l—2P(c)Zp?

IF，

r€Ck-|red"弋七

=1-乙P(e)i(Re)均勻分布，信道差錯(cuò)均勻分布)

=1-1x4：，仁力)+5力(1_/>>+2/>2(1_/))]

4L」

記消息比特差錯(cuò)概率為P(e),消息向量差錯(cuò)概率為PQ),注意到該瑪是非系統(tǒng)碼以及消息向量

bH

長(zhǎng)為2,則應(yīng)有

P?=P")=1-P(C)=1-("P??

IFBBb

P(e)=1-^1-PW=1-(“』+2/>-5尸+27>3

(6)碼字差錯(cuò)概率計(jì)算中

P(q)=0.8x0.8,P(f)=P(r2)=0.8x0.2,P(0=0.2x0.2

ZP(e)=(1-/>>+5/>(l+2^2(1

消息比特差錯(cuò)概率：

1—(0.818/>(1—/>)—(O.218力(1—力)一(0.81(1—力)一(0.21(1—力)

(7)碼字差錯(cuò)概率計(jì)算中

P(c)=P(c)=P(c)=P(c)=U4

01?2'

1-P-P-P-P-P-1(1-10-4)-1(1-10-2)

0102H121044

消息比特差錯(cuò)概率：

-J_(]-10-2)-8x10-4x(1-10-4)-8x10-2x(1-10-2)

47

此題，恰有碼字差錯(cuò)概率和消息比特差錯(cuò)概率相等。

4.證明線性分組碼的碼字重量或者為偶數(shù)(包括0)或者恰好一半為偶數(shù)(包括0)另一半為奇數(shù)。

證明提示：

若碼字重量全為奇數(shù)，則碼不含全零碼字，故不是線性碼。

若碼字重量全為偶數(shù)，則任意兩偶數(shù)重量的碼字c與c'相加仍為偶數(shù)重碼字，故所有碼字均可以

是偶數(shù)重碼字。

若M。個(gè)偶數(shù)重量的碼字集合{c}{c}和個(gè)奇數(shù)重量碼字為集合{〃},則根據(jù)二元線性分組碼的

任意碼字重量滿足w“(c+c')=w(c)+卬“(。')一2%(。、。')可得：對(duì)固定的奇數(shù)重碼字c；有

c；+{c}q{(/},所以k；+{c}卜又對(duì)任意奇數(shù)重碼字c'j,/=由

c+c'W6而有，Q+d|j=2,3,…，M}q{c}-{e},所以M-1<M-1,由此證明M=Me

1

1jIjIl00I

5.一個(gè)通信系統(tǒng)消息比特速率為1°Kbps,信道為衰落信道?在衰落時(shí)間(最大為2ms)內(nèi)可以

認(rèn)為完全發(fā)生數(shù)據(jù)比特傳輸差錯(cuò)。

(1)求衰落導(dǎo)致的突發(fā)差錯(cuò)的突發(fā)比特長(zhǎng)度。

(2)若采用漢明碼和交織編碼方法糾正突發(fā)差錯(cuò),求漢明碼的碼長(zhǎng)和交織深度。

(3)若用分組碼交織糾正突發(fā)差錯(cuò)并限定交織深度不大于256?求合適的碼長(zhǎng)和最小碼距。

(4)若用某個(gè)BCH碼交織來(lái)糾正突發(fā)差錯(cuò)并限定交織深度不大于256?求合適的碼長(zhǎng)和BCH碼

生成多項(xiàng)式。

解題提示：

(1)突發(fā)長(zhǎng)度為b=10x103x2x10-3=2°bits。

(2)漢明碼可糾正亡=1個(gè)差錯(cuò)，所以交織深度。為匕/￡=20。由于沒(méi)有延遲限制，所以任何碼

長(zhǎng)漢明碼均可。

(3)由b=Ox￡4256x￡W256x[(d-l)p],以及d4〃-k+l設(shè)計(jì)。

6.若循環(huán)碼以g(X)=1+X為生成多項(xiàng)式,則

(1)證明g(x)可以構(gòu)成任意長(zhǎng)度的循環(huán)碼；

(2)求該碼的一致校驗(yàn)多項(xiàng)式h(x);

(3)證明該碼等價(jià)為一個(gè)偶校驗(yàn)碼。

解題提示：

(1)由xn-1=(X-1)(X〃T+Xn-2+Xn-3+''+1),1+X總是X〃一1的因子。

(2)一致效驗(yàn)多項(xiàng)式為力(X)=Xn-1/g(X)=1+X+X2+''

(3)對(duì)生成矩陣作行初等變換總能獲得偶校驗(yàn)碼的生成矩陣形式。

oOOOOO

OOO1OO

翁旬崎交換->

00,???1100010

0

000????0110001

一(n-1)xn-

7.已知(8,5)線性分組碼的生成矩陣為

1OoOo111-

o1OOo1Oo

oO1Ooo10-

oOo1OOO1-

I

OOOO1111J

(1)證明該碼為循環(huán)碼；

(2)求該碼的生成式g(x),一致校驗(yàn)式h(x)和最小碼距d。

解題提示：

(1)行等價(jià)生成矩陣為

■11110000

01111000

00111100

00011110

00001111

(2)生成多項(xiàng)式為g(X)=1+X+X2+X3,校驗(yàn)多項(xiàng)式為/?(X)=1+X+X4+X5,最小碼距為2。

8.ATM協(xié)議對(duì)幀頭4字節(jié)(32比特)地址和路由信息校驗(yàn)所用的8比特CRC碼生成多項(xiàng)式為

g(x)=X8+X2+X+1,在實(shí)際應(yīng)用中是以此碼構(gòu)造_個(gè)最小碼距為d=4的(40,32)

碼?討論其構(gòu)造方法。

解題提示：利用循環(huán)碼縮短方法。

9.對(duì)如下圖(E-9A)和圖(E-9B)兩卷積碼分別做: