編碼原理 習題 含答案或提示

糾錯編碼課程習題及解答提示

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

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

01A-l

證明奇校驗碼的檢錯能力與偶奇校驗碼的檢錯能力相同,但奇校驗碼不是線性分組碼。

證明提示：

奇數(shù)個差錯的發(fā)生總導致校驗方程不滿足。全0向量不是奇校驗碼碼字。

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

入100011

TT_h00011

-00101

的01110」

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

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

解題提示：

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

h100011

H=h+h10010

*21

h+h10100

31

h+h+h01000

L423」

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

11213423

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

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

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

[h+h-h010001

||「九31010°

7

H=3I=pQ/I

I/1+A1001olr

2h'1000jj

3.一個糾錯碼的全部消息與碼字的對應關(guān)系如下：

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

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

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

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

(4)構(gòu)造該碼在BSC上的標準陣列；

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

消息比特差錯概率。

解題提示：

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

_logMlog42

(2)碼長為向量長，即"=5。碼字數(shù)為4,故區(qū)=q=」=_。最小非零碼字的

〃55

重量為min緲=d=3。

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

Loomj

「111101

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

(4)標準陣列見題表(3.1)o

題表(3.1)標準陣列

^=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)的標準陣列譯碼，記X是標堆陣列中碼字，對應的列，E是包括尢錯圖案和全

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

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

IF，

r€Ck-|red"弋七

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

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

4L」

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

bH

長為2,則應有

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

IFBBb

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

(6)碼字差錯概率計算中

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

消息比特差錯概率：

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

(7)碼字差錯概率計算中

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

消息比特差錯概率：

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

47

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

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

證明提示：

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

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

是偶數(shù)重碼字。

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

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

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

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

1

1jIjIl00I

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

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

(1)求衰落導致的突發(fā)差錯的突發(fā)比特長度。

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

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

(4)若用某個BCH碼交織來糾正突發(fā)差錯并限定交織深度不大于256?求合適的碼長和BCH碼

生成多項式。

解題提示：

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

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

長漢明碼均可。

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

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

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

(2)求該碼的一致校驗多項式h(x);

(3)證明該碼等價為一個偶校驗碼。

解題提示：

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

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

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

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),一致校驗式h(x)和最小碼距d。

解題提示：

(1)行等價生成矩陣為

■11110000

01111000

00111100

00011110

00001111

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

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

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

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

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

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