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

糾錯編碼課程習題及解答提示奇校驗碼碼字是cm0

,m,",m1 k

,p)，其中奇校驗位p滿足方程，m m0 1

"

k

p1mod2證明奇校驗碼的檢錯能力與偶奇校驗碼的檢錯能力相同，但奇校驗碼不是線性分組碼。證明提示：奇數(shù)個差錯的發(fā)生總導致校驗方程不滿足。全0向量不是奇校驗碼碼字。一個(6,2線性分組碼的一致校驗矩陣為h 1 0 0 0 11 Hhh

0 0 0 1 120 0 1 0 123 h 0 1 1 1 04求hi

使該碼的最小碼距

min

3。求該碼的系統(tǒng)碼生成矩陣Gs及其所有4解題提示：對H作行初等變換得H

h1hh

1 0 0 0 11 0 0 1 0 2 1 hh 3

1 0 1 0 0hhh 0 1 0 0 04 2 3要使最小碼距等于3h,

h,,

hh

h中任意兩項為1，其余為零。當要使最1 1 2 1 3 4 2 3小碼距大于3，有h,1

hh1 2

, h1 3

hh4

h中三項或四項均為1，其余為零。有上述關系可以3求得一組或多組關于hi

,i1,2,3,4的解。H作行初等變換得hhh

100110010100014 2 3 hh

1 0 1 0 0

T H 3 1

Q I hh

kr r 2 1h1一個糾錯碼的全部消息與碼字的對應關系如下：(00)—(00000)，(01)—(00111)，(10)—(11110)，(11)—(11001)證明該碼是線性分組碼；求該碼的碼長，編碼效率和最小碼距；求該碼的生成矩陣和一致校驗矩陣；構造該碼在BSC上的標準陣列；若在轉(zhuǎn)移概率p103的BSC消息比特差錯概率。解題提示：任意兩個碼字的和是另一個碼字且全零向量為碼字。log M

log4 2碼長為向量長，即n5。碼字數(shù)為4，故R q 2 。最小非零碼字的n 5 5重量為minwd3。00114，任意兩非零碼字構成生成矩陣的行向量G11110G0011 11110條件，解得H的一種可能情況等于11000。0110標準陣列見題表3.。c＝00000c＝000000c＝001111c＝111102c＝110013e0e1e2e3e4e5e6e7＝0000000000001111111011001＝0000100001001101111111000＝0001000010001011110011011＝0010000100000111101011101＝0100001000011111011010001＝1000010000101110111001001＝1001010010101010110001011＝1010010100100110101001101按題解Ac

cE是包括無錯圖案和全部可糾正差錯圖案的集合，那么碼字差錯概率為P(e)1P(c)P(rceA)1P(c)P(e)W c

1P(c)P(e)

(P(c)均勻分布，信道差錯均勻分布) 11 41p55p1p42p21p34 記消息比特差錯概率為P(eP(e2，則應有

bP(e)PW

(e)1P11P(e)W12p5p22p3

B(c)11P(e)2bP(e)1b碼字差錯概率計算中

1pP(c0

)0.80.8，P(c1

)P(c2

)0.80.2，P(c3

)0.20.2消息比特差錯概率：

P(e)1p55p1p42p21p3eE10.828p1p0.228p1p0.821p20.221p2

P(c0

)P(c1

)P(c11

)P(c3

1 1 1P P

P P P 1104 11021 1 1

01 02

11 12 10 4 41 1104 1102 81041104 810211024 4此題，恰有碼字差錯概率和消息比特差錯概率相等。證明線性分組碼的碼字重量或者為偶數(shù)（0）或者恰好一半為偶數(shù)（包括0）證明提示：若碼字重量全為奇數(shù)，則碼不含全零碼字，故不是線性碼。c與c是偶數(shù)重碼字。若M 個偶數(shù)重量的碼字集和MccH1c

個奇數(shù)重量碼字為集合c，則根據(jù)二元線性分組碼的任意碼字重量滿足wH

c'w

cwH

'2wH

c'可得：對固定的奇數(shù)重碼字c有1，所以1c，所以1

M

。又對任意奇數(shù)重碼字c

j2,3,M，由01 j 101cc

而有，cc

j2,3,,M

，所以

1M

1M

M。1 j 1 j 1 1 0 0 1一個通信系統(tǒng)消息比特速率為10Kbps，信道為衰落信道，在衰落時間（最大為2ms）認為完全發(fā)生數(shù)據(jù)比特傳輸差錯。求衰落導致的突發(fā)差錯的突發(fā)比特長度。若采用漢明碼和交織編碼方法糾正突發(fā)差錯，求漢明碼的碼長和交織深度。若用某個BCH碼交織來糾正突發(fā)差錯并限定交織深度不大于256，求合適的碼長和BCH生成多項式。解題提示：（1）突發(fā)長度為b101032103

20bits。（2）漢明碼可糾正t＝1個差錯，所以交織深度D為b/t20長漢明碼均可。（3）由bDt256t256d2，以及dnk1設計。若循環(huán)碼以g(x)1x為生成多項式，則證明g(x可以構成任意長度的循環(huán)碼；求該碼的一致校驗多項式hx；解題提示：（1）由xn1(x1)xn1xn2xn3"1)，1x總是xn1的因子。一致效驗多項式為h(x)xn1/g(x)1xx2"xn1。對生成矩陣作行初等變換總能獲得偶校驗碼的生成矩陣形式。1 1 0 " " 0 0 0 1 0 " 0 0 0 1 1 " " 0 0 0

0 1

" 0 0 等換 0 0 0 " " 1 1 0 0 0 " 0 0

0 0 " " 0 1 1

(n1)n

0 0

" 0 1

(n1)n已知線性分組碼的生成矩陣為1 0 0 00 1 0 0G0 0 1 00 0 0 10 0 0 0

0 1 10 1 00 0 10 0 01 1 1

100，11證明該碼為循環(huán)碼；求該碼的生成式g(x)，一致校驗式h(x)和最小碼距d 。解題提示：行等價生成矩陣為1000000

001101110001111000111100011110001110001

58g(x)1xx2x3，校驗多項式為h(x)1xx4x52。ATM協(xié)議對幀頭4字節(jié)比特）地址和路由信息校驗所用的8比特CRC碼生成多項式為的g(x)x8x2x的碼，討論其構造方法。

，在實際應用中是以此碼構造一個最小碼距為

d4

(40,32)解題提示：利用循環(huán)碼縮短方法。對如下圖和圖兩卷積碼分別做：v(x)1消息u(x)消息u(x)v(x)圖E-9A圖E-9Bv(x)2G(x)GRKM。求自由距離df。畫出開放型的狀態(tài)轉(zhuǎn)移圖，柵格圖。求消息u(100110)的卷積碼碼字序列v(v0

,v,v1

,)。在柵格圖上畫出消息u(100110)的編碼路徑。若消息u(100110)的相應碼字序列 v(v0

,v,v1

,)在BSC上傳送，差錯圖案是e(1000