第九章差錯(cuò)控制編碼

第9章差錯(cuò)控制編碼南京航空航天大學(xué)信息科學(xué)與技術(shù)學(xué)院通信原理教研組第9章 差錯(cuò)控制編碼2008.82copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組7引言糾錯(cuò)編碼的基本原理3

常用的簡單編碼4

線性分組碼5

循環(huán)碼6

卷積碼網(wǎng)格編碼調(diào)制9.1

引言信道解調(diào)信源編碼加密調(diào)制解密譯碼信宿噪聲同步系統(tǒng)ASKFSKPSKDPSK數(shù)字通信的組成A/D信源編碼

數(shù)據(jù)壓縮信道編碼 差錯(cuò)控制2008.83copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2008.8

copyright

信息科學(xué)與技術(shù)學(xué)院通信原理教研組

4采用信道編碼在通信過程中，會(huì)受到各種外來干擾，如脈沖干擾，隨機(jī)噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信號失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯(cuò)誤，稱之為差錯(cuò)。隨機(jī)性錯(cuò)誤：前后出錯(cuò)位之間無一定關(guān)系，隨機(jī)、離散出現(xiàn)。突發(fā)性錯(cuò)誤：差錯(cuò)成串出現(xiàn)，且有一定相關(guān)性。差錯(cuò)的兩大類型：都能有效的提高傳輸可靠性。合理的設(shè)計(jì)基帶信號時(shí)域/頻域均衡發(fā)射功率的提高數(shù)字通信中的編碼信源編碼：為提高信號傳輸?shù)挠行远扇〉拇胧Ｐ诺谰幋a：為提高信號傳輸?shù)目煽啃远扇〉拇胧?亦稱差錯(cuò)控制編碼。差錯(cuò)控制在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強(qiáng)的原始數(shù)字信號變?yōu)閹б?guī)律性或加強(qiáng)了規(guī)律性的數(shù)字信號，信道譯碼器則利用這些規(guī)律性來鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行錯(cuò)誤糾正。2008.85copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1、差錯(cuò)控制方法（1）前向糾錯(cuò)法FEC所發(fā)碼具有糾錯(cuò)能力，收端接收后自動(dòng)糾錯(cuò)，無需反向信道。實(shí)時(shí)性好，但譯碼設(shè)備復(fù)雜，傳輸效率↓。信源FEC編碼信道FEC譯碼信宿2008.86copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組（2）信息反饋法IF信息信號信息信號發(fā)端收端方法和設(shè)備簡單，無需糾檢錯(cuò)編譯系統(tǒng)。但需要雙向信道，傳輸效率↓、實(shí)時(shí)性差。2008.87copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組(3)檢錯(cuò)重發(fā)法ARQ所發(fā)碼具有檢錯(cuò)能力，收端接收后判決是否出錯(cuò)，通過反向信道發(fā)送判決結(jié)果，發(fā)端據(jù)此決定是否重發(fā)。信源編碼器正向信道譯碼器信宿緩存器重發(fā)控制器

反向信道

重發(fā)判決器譯碼設(shè)備簡單，對突發(fā)錯(cuò)誤有效，要求有反饋信道。工作過程：發(fā)送——檢測——回復(fù)——重發(fā)或發(fā)送新的數(shù)據(jù)2008.88copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1223221①停止等待方式發(fā)送端2008.89copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組接收端ARQ的三種實(shí)現(xiàn)方式：特點(diǎn)：半雙工工作，簡單，要求的緩存量小，但等待時(shí)間較長，傳輸效率↓②連續(xù)重發(fā)方式012345234560

1

2

3

4

5

2

3

4

5

6退N步方式：從出錯(cuò)幀開始重發(fā)優(yōu)缺點(diǎn)：傳輸效率↑，但重發(fā)的N幀中，大部分為正確，所以仍有浪費(fèi)。發(fā)端緩存必須可存N幀。2008.810copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組0123452678990

1

2

3

4

5

2

6

7

8只對出錯(cuò)信息重發(fā)，因此傳輸效率大大提高。但收發(fā)兩端都要有足夠的存儲(chǔ)空間。2008.811copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組③選擇重發(fā)方式反饋信道ARQFEC編碼器正向信道FEC譯碼器ARQ編碼既有糾錯(cuò)能力也有檢錯(cuò)能力，收端收到信息碼組后在收端進(jìn)行檢測。在糾錯(cuò)范圍內(nèi)：糾正；超出范圍：通過ARQ方式進(jìn)行重發(fā)。(4)混合方式2008.812copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組（1）根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分：線性碼，非線性碼根據(jù)監(jiān)督碼元是否僅與本組信息元有關(guān)分組碼，卷積碼（2）根據(jù)糾錯(cuò)碼組中信息元是否隱蔽分：系統(tǒng)碼，非系統(tǒng)碼2008.813copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組（3）糾錯(cuò)碼的分類根據(jù)碼的用途分：檢錯(cuò)碼，糾錯(cuò)碼（4）（5）

根據(jù)碼元的取值：二進(jìn)制碼，多進(jìn)制碼根據(jù)構(gòu)造編碼的數(shù)學(xué)方法：代數(shù)碼，幾何碼，算術(shù)碼2008.814copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組（6）本課程主要討論糾隨機(jī)錯(cuò)誤的二進(jìn)制線性分組碼。糾錯(cuò)碼的發(fā)展概況2008.815copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組通信的數(shù)學(xué)理論，Shannon(1948)漢明碼，Hamming

(1950)級連碼，F(xiàn)orney(1966)卷積碼及有效譯碼，(60年代)RS碼及有效譯碼，(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo碼，Berrou(1993)LDPC碼，Gallager(1963),Macky(1996)空時(shí)編碼,Tarokh(2000)9.2

糾錯(cuò)編碼的基本原理2008.816copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1、幾個(gè)術(shù)語碼長：碼組中碼元的數(shù)目，常用n表示；碼重：碼組中非零碼元的數(shù)目，記為W；碼距：兩等長碼字C1、C2對應(yīng)位上取值不同的數(shù)目，又稱為漢明(Hamming)距離，記為

d(c1,c2)。n=3時(shí)，碼距的幾何說明：2

1

0（

a

a

a

）a2a0（

110）

（

011

）d=2110011（

111）

（

000

）d=3000111最小碼距：在分組碼(n,k)中，任意兩個(gè)碼字之間漢明距離的最小值，記為dmin。最小碼距的大小關(guān)系到編碼的檢糾錯(cuò)能力。2008.817copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組a1010101100001發(fā)送序列C:(1111011000)接收序列R:()比較C和R，可寫出另一個(gè)序列E：1001001110R

=

C

+

E序列E定義為錯(cuò)誤圖樣(Error

Pattern)2008.818copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組錯(cuò)誤圖樣：A、B兩消息，可用一位二進(jìn)制數(shù)表示，A=1、B=0出錯(cuò)時(shí)無法判定

增加一個(gè)監(jiān)督位，取11→A、00→B2008.819copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組許用碼組：00，11禁用碼組：01，10能夠糾正一個(gè)錯(cuò)誤，發(fā)現(xiàn)兩個(gè)錯(cuò)誤若收到01或10時(shí)，可知發(fā)生了錯(cuò)誤，但不能糾正錯(cuò)誤。

再增加一個(gè)監(jiān)督位，取111→A、000→B許用碼組：000，111禁用碼組：001,

010,

100,

011,

101,

110如一位錯(cuò)能夠糾正錯(cuò)誤；若兩位錯(cuò)，則只能發(fā)現(xiàn)不能糾錯(cuò)2、糾錯(cuò)或檢錯(cuò)的原理因此2008.820copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組這種（3,1）碼，能糾正一個(gè)錯(cuò)，發(fā)現(xiàn)兩個(gè)錯(cuò)。但是(3,1)碼中，數(shù)據(jù)位僅為1位，監(jiān)督位為兩位，傳輸效率↓↓可以看出：差錯(cuò)控制是以犧牲傳輸效率為代價(jià)而換取了傳輸質(zhì)量的提高的。糾檢錯(cuò)能力與加入的監(jiān)督元方式和數(shù)目有關(guān)。an-1an-2……arar-1……a0k個(gè)信息元r個(gè)監(jiān)督元碼長：n=k+rR=k/n為編碼效率，d0一定(糾錯(cuò)能力一定)時(shí)，k/n大，效率高。2008.821copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組對被傳輸?shù)男畔⑿蛄蟹纸M，每組為k個(gè)信息元，對每組按某種關(guān)系附加(n-k)個(gè)監(jiān)督碼元(校驗(yàn))，形成為

n位的碼字。這種方法構(gòu)成的碼組稱為分組碼。分組碼的三個(gè)參數(shù)碼長n，信息位k，最小距離d0

，用符號(n,k,d0)表示3、分組碼4、分組碼的糾(檢)錯(cuò)能力與最小碼距d0的關(guān)系任一（n，k）分組碼，若要在碼字內(nèi)能：1/

檢測e個(gè)隨機(jī)錯(cuò)誤，則要求：d0

≥e+12/

糾正t個(gè)隨機(jī)錯(cuò)誤，則要求：

d0

≥2t+13/

糾正t個(gè)同時(shí)檢測e(e>t)個(gè)隨機(jī)錯(cuò)誤，則要求：

d0

≥

e+t+12008.822copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1糾（檢）錯(cuò)能力的幾何解釋A1d0eA2（a）A1eA2td0（c）A1td0（b）AA2

211

t2008.823copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-1]一個(gè)碼集，只有兩個(gè)許用碼：0000、1111，試求其糾、檢錯(cuò)能力和編碼效率。2008.824copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組解：根據(jù)碼距的定義，則該碼集d0

=4，1/用于檢錯(cuò)，e≤d0

–1=3，即可檢3個(gè)錯(cuò)誤；2/用于糾錯(cuò)，t≤(d0–1)/2=3/2，取整，即可糾1個(gè)錯(cuò)誤；3/同時(shí)用于糾、檢錯(cuò)，

d0

≥

e+t+1

（e＞t）2008.825copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組?。篹=2，t=1，則可滿足上式，即可檢2個(gè)錯(cuò)誤同時(shí)糾一個(gè)錯(cuò)；編碼效率：R=k/n=1/44、對糾錯(cuò)編碼的要求2008.826copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組糾、檢錯(cuò)能力強(qiáng)，編碼效率高，碼長短，編碼規(guī)律簡單。5.差錯(cuò)控制編碼的效用假設(shè)在隨機(jī)信道中，發(fā)送“0”和“1”的錯(cuò)誤概率相等，都等于p，且p＜＜1，在碼長為

n的碼組中，發(fā)生r個(gè)錯(cuò)誤的概率為：n!2008.827copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組prP

(r)

=

Cr

pr

(1-

p)n-r

?n

nr

!(n

-

r)!n!prr

!(n

-

r)!P

(r)

=

Cr

pr

(1-

p)n-r

?n

n例如：當(dāng)n=7，p=10-3時(shí)，則有：7P

(1)

?

7

p

=

7

·10-377!2!(7

-

2)!p2

=

21·

p2

=

2.1·10-5P

(2)

?72008.828copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組7!3!(7

-3)!p3

=

35·

p3

=

3.5·10-8P

(3)

?由此可見，即使僅能糾正1-2個(gè)錯(cuò)誤，也可使誤碼率下降幾個(gè)數(shù)量級。所以差錯(cuò)控制編碼具有較大的實(shí)際應(yīng)用價(jià)值。6.有擾信道編碼定理（Shannon第二定理）2008.829copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組對于給定的有擾信道，若信道容量為C，只要發(fā)送端以低于C的信息速率Rb發(fā)送信息，則一定存在一種編碼方法，使得譯碼錯(cuò)誤概率P隨著碼長n的增加，按指數(shù)下降至任意小的值，表示為P￡e-nE(Rb)E(Rb)為誤差指數(shù)，Rb<C時(shí)，E(Rb)>0。Rbmax=C=Blog2(1+S/N)

（bit/s）碼長n和信息速率Rb一定時(shí)，隨C?fi

誤差指數(shù)E(Rb)?fi

P↓隨指數(shù)下降。其中C=Blog2(1+S/N)（bit/s）在C和Rb一定時(shí)(Rb

<C)，隨碼長n?fi

P

隨指數(shù)下降(Pfi

0)。數(shù)字傳輸系統(tǒng)中，無誤碼傳輸?shù)淖罡咝畔⑺俾蔙bmax=C=Blog2(1+S/N)

（bit/s）2008.830copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組兩個(gè)結(jié)論：編碼性能舉例未采用糾錯(cuò)編碼時(shí)，若接收信噪比等于

7dB，編碼前誤碼率約為8·10-4，圖中A點(diǎn)，在采用糾錯(cuò)編碼后，誤碼率降至約4-5·10 ，圖中B點(diǎn)。這樣，增大發(fā)送功率,就能降低誤碼率約一個(gè)半數(shù)量級。10-610-510-210-110-3Pe10-4A?編碼后B信噪比(dB)2008.831copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組由圖還可以看出，若保持誤碼率在10-5，圖中C點(diǎn)，未采用編碼時(shí)，約需要信噪比Eb

/n0

=9.5

dB。在采用這種編碼時(shí)，約需要信噪比7.5

dB，圖中D點(diǎn)。可以節(jié)省功率2

dB。通常稱這2

dB為編碼增益。上面兩種情況付出的代10-510-210-110-3Pe10-4??CD編碼后10-6價(jià)是帶寬增大。信噪比(dB)信息科學(xué)與技術(shù)學(xué)院通信原理教研組2008.832copyright傳輸速率和Eb/n0的關(guān)系對于給定的傳輸系統(tǒng)式中，RB為碼元速率。若希望提高傳輸速率，由上式看出勢必使信噪比下降，誤碼率增大。假設(shè)系統(tǒng)原來工作在圖中C點(diǎn)，提高速率后由C點(diǎn)升到E點(diǎn)。但加用糾錯(cuò)編碼后，仍可將誤碼率降到D點(diǎn)。這時(shí)付出的代價(jià)仍是帶寬增大。10-610-510-410-310-210-1編碼后Pe???C2008.833copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組DE信噪比(dB)9-3

常用的簡單編碼1、奇偶監(jiān)督碼：k=n-1,r=1的線性碼。特點(diǎn)：碼組中的1個(gè)數(shù)是奇數(shù)（奇監(jiān)督碼）或偶數(shù)（偶監(jiān)督碼）。偶監(jiān)督時(shí)，要滿足：an-1

ˉ

an-2

ˉ

ˉ

a0

=

0奇監(jiān)督時(shí)，要滿足：an-1

ˉ

an-2

ˉ

ˉ

a0

=1兩者的校驗(yàn)?zāi)芰ο嗤荒軝z測出奇數(shù)個(gè)錯(cuò)誤。編碼效率：R=k/n=n-1/n=1-1/n2008.834copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組碼長5的偶監(jiān)督碼序號碼字信息碼元監(jiān)督元序號碼

字信息碼元監(jiān)督元a4

a3

a2

a1a0a4

a3

a2

a1a000

0

0

0081

0

0

0110

0

0

1191

0

0

1020

0

1

01101

0

1

0030

0

1

10111

0

1

1140

1

0

01121

1

0

0050

1

0

10131

1

0

1160

1

1

00141

1

1

0170

1

1

11151

1

1

102008.835copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組偶監(jiān)督碼編碼器a4a3a2a1+信息組a0a1a2a3a4碼字a0

=

a4

ˉ

a3

ˉ

a2

ˉ

a12008.836copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組4

3

2

1

0b3b0b1

b2b4+接收碼組BS檢錯(cuò)信號2008.837copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組無錯(cuò)1

有錯(cuò)s

=

b

ˉ

b

ˉ

b

ˉ

b

ˉ

b

=

0偶監(jiān)督碼的檢錯(cuò)電路[例9-2]：一數(shù)據(jù)序列：{11100

∣10111

∣01101

∣10001∣

10101}試對其進(jìn)行（6，5）偶校驗(yàn)編碼，寫出碼序列并分析其抗干擾能力2008.838copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組一數(shù)據(jù)序列：2008.839copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組的運(yùn)算并作：

a0

=

a5

ˉ

a4

ˉ

a3ˉ

a2

ˉ

a1可得出編碼數(shù)據(jù)序列：{111001∣101110∣011011∣100010∣101011}只能檢測出奇數(shù)個(gè)錯(cuò)誤，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤，也不能糾錯(cuò)。{11100∣

10111

∣01101

∣10001∣

10101}試對其進(jìn)行（6，5）偶校驗(yàn)編碼，寫出碼序列并分析其抗干擾能力解：（6，5）,將數(shù)據(jù)序列每5碼元分組，2、水平垂直奇偶校驗(yàn)碼：又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點(diǎn)：對水平方向和垂直方向的碼元同時(shí)實(shí)施奇偶監(jiān)督。1

1

0

0

1

0

1

0

0

000

1

0

0

0

0

1

1

0

100

1

1

1

1

0

0

0

0

111

0

0

1

1

1

0

0

0

001

0

1

0

1

0

1

0

1

011

1

0

0

0

1

1

1

1

0

0行列監(jiān)督碼2008.840copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組適于監(jiān)測突發(fā)錯(cuò)誤：逐行傳輸時(shí)，能檢測長度b

￡

M+1的突發(fā)錯(cuò)誤;逐列傳輸時(shí),能檢測長度b￡L+1的突發(fā)錯(cuò)誤；還能糾正一些僅在一行中的單個(gè)錯(cuò)誤。1

1

0

0

1

0

1

0

0

000

1

0

0

0

0

1

1

0

100

1

1

1

1

0

0

0

0

111

0

0

1

1

1

0

0

0

001

0

1

0

1

0

1

0

1

011

1

0

0

0

1

1

1

1

0

0L＝5，M＝10的行列監(jiān)督碼2008.841copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組其中M為行數(shù)，L為列數(shù)3、恒比碼：又稱等重碼或定1碼。特點(diǎn)：碼組中0，1的個(gè)數(shù)保持不變。若碼長為n，碼重為w，則此碼的碼字個(gè)數(shù)為：Cnw，禁用碼字個(gè)數(shù)為：2n

-Cnw碼字的個(gè)數(shù)C53

=10檢錯(cuò)能力較強(qiáng)，可檢出所有奇數(shù)和部分偶數(shù)錯(cuò)誤。2008.8

copyright

信息科學(xué)與技術(shù)學(xué)院通信原理教研組

42檢錯(cuò)能力較強(qiáng)，可檢出所有奇數(shù)和部分偶數(shù)錯(cuò)誤。適用于傳輸電報(bào)或其他鍵盤設(shè)備產(chǎn)生的字母或符號，但不適合信源發(fā)出的是二進(jìn)制隨機(jī)數(shù)字序列的場合。數(shù)字碼

字0011011010112110013101104110105001116101017111008011109100112008.843copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組如：我國的電報(bào)，每個(gè)漢字用四個(gè)10進(jìn)制數(shù)表示，每位10進(jìn)制數(shù)就采用3：2恒比碼構(gòu)成的5位碼組來表示。碼字的個(gè)數(shù)C53

=103:2

恒比碼作業(yè)：11001→11001∣1100110001→10001∣011102008.844copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組4、正反碼：簡單的可糾錯(cuò)編碼，信元數(shù)等于監(jiān)督元數(shù)特點(diǎn)：信息位中，有奇數(shù)個(gè)1時(shí)，監(jiān)督位重復(fù)信息位；信息位中，有偶數(shù)個(gè)1時(shí)，監(jiān)督位取信息位的反碼；例：(n,k) 其中k=n/2 編碼效率：

R=k/n=1/2可糾一位、檢測所有兩位錯(cuò)和部分兩位以上的錯(cuò)誤。9.4

線性分組碼2008.845copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4.1基本概念可用線性方程組表述碼的規(guī)律性的分組碼稱為線性分組碼。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集合構(gòu)成代數(shù)學(xué)中的群，因此，又稱為群碼。含有全零碼字。任意兩個(gè)許用碼字之和仍是一個(gè)許用碼字。（封閉性）最小碼距d0等于非零碼字的最小重量即

d0=Wmin（由此性質(zhì)可以方便的確定出線性分組碼的最2008.846copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組小碼距，進(jìn)而明確其糾錯(cuò)能力。）在群中只有一種運(yùn)算，就是模2和。線性分組碼的性質(zhì)：奇偶監(jiān)督碼是一種最簡單的線性碼，我們曾經(jīng)作了偶校驗(yàn)的例子。

a

ˉ

a

ˉ

ˉ

a

=

02008.847copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組n-1

n-2

0稱為監(jiān)督方程。接收時(shí)，為了檢測傳輸時(shí)是否有錯(cuò)，還要做同樣的計(jì)算：04

3

2

1s

=

b

ˉ

b

ˉ

b

ˉ

b

ˉ

b無錯(cuò)1

有錯(cuò)s

=

0這里S稱為校正子，上式也稱伴隨式。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯(cuò)誤。當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。2008.848copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組我們把接收碼組R與發(fā)射碼組C的差稱為錯(cuò)誤圖樣，用E表示：E=C-R，或者C=R+E(n,k)中，信息碼為k位，可傳輸M=2k種信息，當(dāng)增加r位的監(jiān)督位后，有2n種狀態(tài)，但只取2k種為許用狀態(tài)，其他為禁用，(n,k)碼可檢測的錯(cuò)誤圖樣數(shù)為

2n-2kr位監(jiān)督碼除了用全“0”表示無錯(cuò)外，可表示2r

-1種錯(cuò)誤圖樣。(n,k)碼可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為：2n-k

-1=2r-1不可檢測的錯(cuò)誤圖樣數(shù)為2k-1n

n

n2008.849copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組inci=12

n-k-1?c1

+

c2

+……+ct

=對于能糾正t

個(gè)錯(cuò)誤的線性分組碼(nt,k)應(yīng)滿足：nc

i是錯(cuò)i

位的個(gè)數(shù)。ni=1時(shí)，c1=

n即對于碼組長度為n，信息碼元k位，監(jiān)督元r，如果滿足2r

-1

?n，則有可能構(gòu)造出糾正一位或一位以上的線性碼。思考：2008.850copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-3]設(shè)(n，k)中，k=4，要求能糾一位錯(cuò)，取r=？解：(n，k)線性分組碼，k=4，要求能糾一位錯(cuò)，現(xiàn)取r=3，可指示23-1=7種錯(cuò)誤，碼長n=4+3=7，2008.851copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組表示為：

C=[C6C5C4C3C2C1C0]恰好滿足2r

-1=n

,故可糾一位錯(cuò)。其中C6C5C4C3為信息碼元，C2C1C0為監(jiān)督元由r=3，可有三個(gè)監(jiān)督方程和校正子，設(shè)為s1s2s3誤碼位置無錯(cuò)

C0C1C2C3C4C5C6S1S2S3000001010100011101110111C1=C6+C5+C3C0=C6+C4+C3←監(jiān)督元與信息元之間的線性方程組2008.852copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組設(shè)s1s2s3三位校正子與誤碼位置的對應(yīng)關(guān)系為：s1=C2+C6+C5+C4=0s2=C1+C6+C5+C3=0s3=C0+C6+C4+C3=0于是監(jiān)督碼元C2C1C0應(yīng)由以下監(jiān)督方程決定。C2=C6+C5+C4于是得到(7，4)線性分組碼如下：序號碼

字信息元監(jiān)督元891011121314151

0

0

01

0

0

11

0

1

01

0

1

11

1

0

01

1

0

11

1

1

01

1

1

11

1

11

0

00

1

00

0

10

0

10

1

01

0

01

1

1序號碼

字信息元監(jiān)督元012345670

0

0

00

0

0

10

0

1

00

0

1

10

1

0

00

1

0

10

1

1

00

1

1

10

0

00

1

11

0

11

1

01

1

01

0

10

1

10

0

02008.853copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4.2

監(jiān)督矩陣C6

C5

1

1

1

0

1

0

0C4

0

1

1

0

1

0

1

0C3

=

0

1

0

1

1

0

0 1

C2

0C1

C0

00113

5

C1

C0

1

C2

1

1

1

0

1

01

0

1

0

1

0C

=

00

1

1

0

00C4

C

將前面的監(jiān)督方程改寫成矩陣的形式，

C=[C6C5C4C3C2C1C0]可看成為編碼矢量，于是有：C6

記做：HC

T

=

0TCH

T

=

0監(jiān)督方程2008.854copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1

1

1 0

P

=

1

1

0 1

1

0

1 1

P

=不滿足以上關(guān)系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。2/H矩陣各行是線性無關(guān)的。行數(shù)---監(jiān)督元的個(gè)數(shù)r列數(shù)---碼組長度nH--監(jiān)督矩陣1/

當(dāng)有H=[P

Ir]時(shí)稱為典型矩陣，Ir為r階單位陣1

0

0I

=

0

1

0

0

0

11110

1001101

I

=

0101011

0012008.855copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組即H陣與編碼碼字的轉(zhuǎn)置乘積為0，可用來作為判斷接收碼組是否錯(cuò)的依據(jù)。利用監(jiān)督方程，我們可以對線性碼的封閉性加以證明2008.856copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組3/

H

CT

=OT

,設(shè)監(jiān)督方程A1、A2均為線性碼集合中的許用碼2008.857copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組組，因此有 令兩許用碼組相加A

H

=01

2T

TA

H

=0A1+A2帶入監(jiān)督方程，有：(A

+A

)HT

=A

HT

+A

HT

=01

2

1

2因此，A1+A2亦為許用碼組。9.4.3

生成矩陣C2=C6+C5+C4C1=C6+C5+C3當(dāng)給出信息組后，如何方便迅速地求出整個(gè)編碼碼組，即如何生成編碼矢量？由監(jiān)督元與信息元之間的關(guān)系：C6

C2

1

1

1

0

C

=

1

1

0

1C5

1

C

C

1

0

1

1

4

0C3

4

32008.858copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組5

012

11C

C

C

0C6

C

11

1

1C

=

1

1

00

1C

C C

]PT345[C2

C1

C0]=[C6

CC0=C6+C4+C3或者可以寫成：copyright

信息科學(xué)與技術(shù)學(xué)院通信原理教研組59[C2

C1

C0

]

=[C6

C5

C4

C3

]Q令PT

=Q則有：G矩陣列數(shù)----碼組長度n每行本身就是一個(gè)許用碼組HGT

=

0TGH

T

=

0于是有：2008.8給Q的左邊，加一個(gè)k×k階的單位矩陣，則構(gòu)成：G=[Ik

Q]稱為生成矩陣，且為典型形式。典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。行數(shù)----信息元的個(gè)數(shù)k2008.8

copyright

信息科學(xué)與技術(shù)學(xué)院通信原理教研組60信息碼元監(jiān)督位信息位編碼fi一般情況，定義線性分組碼的碼字有如下形式：碼字kn

-

kkn系統(tǒng)形式的線性分組碼cn-1

cn-2

cn-k

=

mk

-1

mk

-2

m0cn-k

-1

c0

)n

-

kfiM

G0M

=

(

mk

-1

mk

-2

m0

)編碼C

=

(

cn-1

cn-2

cn

-kk碼字的前面

k

位為信息位，后面

n

-位k

為監(jiān)督位2008.8copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組61000111001101010001011

100

G

=

1

001

生成矩陣編碼碼組C

=

M

Gc5

c4

c3設(shè)信息組

M

=

c6.1）由G和信息組即可產(chǎn)生全部碼字.1

1 1

1

1

0Q

=

=

PT1

0 1

0

1 1

1

1 1

1

1

001Q

=

=

PT101

1

1

0

0 0

0

1

0 0

I

k

=

0

0

1 0

0

0

0 1

I

k

1

0

0 0

0

1

00

10

00

=

0

0

01

G稱為典型生成矩陣。通過典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。2008.862copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組G

為k

·

n

階矩陣，各行線性無關(guān)G

=

I

k

Q

2008.863copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組0

0

1

0

1

1G=1

0

0

1

0

10

1

0

1

1

0（1）試確定(n,k)，并求H；

寫出監(jiān)督元與信息元的關(guān)系式及該（n,k）碼的全部碼字；確定最小碼距及檢錯(cuò)能力。[例9-4]設(shè)已知

0

0

1

0

1

10

1

0

1

1

01

0

0

1

0

1解：求H，需確定P，應(yīng)將已知的那個(gè)G轉(zhuǎn)換成典型形式，求出Q，再利用PT

=Q

求出G。

0

1

0

1

1

00

0

1

0

1

1G=1

0

0

1

0

1

0

1

0

1

1

00

0

1

0

1

11

0

0

1

0

12008.864copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1101

1

0

1

0

01

1

0

10

1

0

0rI

]

=0H=[P

Ir]=

[QT(2)2008.865copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2

4

0001HC

T

=

01

1

0

1

01

1

0

10

1

0

0c0

c1

c

0c3

=

0c

設(shè)C=0[c5

c4

c3

c2

c1

c]101

0

0

1

0

11

0

1

10

1

0

15

4

3

0于是有：

C

=

M

G

=[c

c c

]0監(jiān)督元與信息元的關(guān)系式c5

用三位二進(jìn)制數(shù)的所有8種狀態(tài)帶入，可得到所有碼字如右表。序號碼字012345670

0

0

0

0

00

0

1

0

1

10

1

0

1

1

00

1

1

1

0

11

0

0

1

0

11

0

1

1

1

01

1

0

0

1

11

1

1

0

0

0(3)確定最小碼距及檢錯(cuò)能力利用性質(zhì)知：最小碼距d0等于非零碼字的最小重量即d0=wmin所以有：d0=3可用于檢兩位錯(cuò)或糾一位錯(cuò)。2008.866copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4.4

校正子S2008.867copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組發(fā)送端經(jīng)過編碼后給出：c=[cn-1接收端收到的碼組為：R

=[rn-1兩者的差記為：

c1

c0]

r1

r0]

e1

e0]cn-2rn-2en-2E

=R-C

=[en-1iii

iie

=1

r

?

c0

r

=

c表示第i位無錯(cuò)表示第i

位有錯(cuò)E稱為錯(cuò)誤圖樣。共有2n個(gè)錯(cuò)誤圖樣。當(dāng)E為全零錯(cuò)誤圖樣時(shí)，R=C

沒有傳輸錯(cuò)誤;HRT

?

0THRT

=0T可利用E檢出或糾正錯(cuò)誤；傳輸中的錯(cuò)誤超出了可糾錯(cuò)的范圍。這時(shí)的錯(cuò)誤圖樣稱為不可檢測的錯(cuò)誤圖樣(n,k)可檢測的錯(cuò)誤圖樣數(shù)為2n

-2k(n,k)可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為2n-k

-12008.868copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組校正子S

的計(jì)算S

=

RHT

=

(C

+

E)HT

=

CHT

+

EHT

=

EHT即校正子只與錯(cuò)誤圖樣E有關(guān)。檢錯(cuò)：當(dāng)S=0時(shí)，認(rèn)為E=0，當(dāng)S?0時(shí)，認(rèn)為E?0,一般來講，E=0，則R=C，可滿足監(jiān)督方程E≠0，則R≠C，不滿足監(jiān)督方程可能有兩種情況：標(biāo)準(zhǔn)陣列表D1D2D3D

k2C1

=0C2C3C

k2E2E2

+C2E2

+C3E2

+C2kE3E3

+C2E3

+C3E3

+C2kE

n-k2E2n-k

+C2E2n-k

+C3E2n-k

+C2k第一個(gè)元素。1（1）

(

n

,

k

)碼的2k

個(gè)碼字排在第一行，全零碼字C

=

0排在E1

?陪集陪集首排列方法2008.869copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2008.8

copyright

信息科學(xué)與技術(shù)學(xué)院通信原理教研組

70D1D2D3D

k2C1

=0C2C3C

k2E2E2

+C2E2

+C3E2

+C2kE3E3

+C2E3

+C3E3

+C2kE

n-k2E2n-k

+C2E2n-k

+C3E2n-k

+C2kE1

?陪集陪集首剩下的2n

-2k

個(gè)n

重中選擇重量較小的n

重作為錯(cuò)誤圖樣E2放在C1

下面，并將E2

+Ci

放在Ci

下面構(gòu)成第二行。繼續(xù)以上過程，用完所有n

重。每行第一個(gè)n

重是前面未出現(xiàn)過的，且希望重量盡可能小。構(gòu)造標(biāo)準(zhǔn)陣列的一般方法如下：用概率譯碼確定各伴隨式S對應(yīng)的差錯(cuò)圖案E，共2n

對；表格為2k

列，2n-k行，先確定第一行和第一列，第一行為2k個(gè)2008.871copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組i碼字c

j，第一列為E

；E3）各列對應(yīng)的元素為第一列的

i

和該列的

j

之和；C陪集首C0C1C

k2

-1S0

fi

E0E0

+

C0

=

0E0+

C1=

C1E0

+

C2k

-1

=

C2k

-1S1

fi

E1E1

+

C0

=

E1E1

+

C1E1

+

C2k

-1S2n-k-1fi

E

n-k2-1E

n-k2-1+C0

=

E2n-k-1E2n-k-1+

C1E2n-k-1+

C

k2

-1譯碼時(shí)，計(jì)算伴隨式S，查表獲得錯(cuò)誤圖樣E，最后恢復(fù)出發(fā)送碼字C＝E＋R。[例9-5]已知監(jiān)督矩陣：1

1

1

0

1

0

0

H

=

1

1

0

1

0

1

01

0

1

1

0

0

11100

1

0

10

1

1

0

01

1

1

0

1

0

0H

=

1

1若接收為：R=[0000011]，試確定是否錯(cuò)誤，若接收錯(cuò)誤，試進(jìn)行糾錯(cuò)。2008.872copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組0111011

1

1100

0

0

1

1]0

1

1

=[0

1

1]

=

EH

T00

1

00

0

11

1

1

0

1

0

0

H

=

1

1

0

1

0

1

01

0

1

1

0

0

11100

1

0

10

1

1

0

01

1

1

0

1

0

0H

=

1

1R=[

0

0

0

0

0

1

1

]，解：計(jì)算校正子S

=

RH

T

=[0

02008.873copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1

0

11

1

01

1

1C5C6S1

S2

S3

誤碼位置0

0

無錯(cuò)0

0

1

C00

1

0

C10

0

C20

1

1

C3C4錯(cuò)誤圖樣：2008.874copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組E=[

0

0

0

1

0

0

0

]對照校正子與誤碼位置，確定錯(cuò)誤圖樣：[0

1

1]

=

EH

T于是：R`=R+E=[

0

0

0

0

0

1

1

]+[

0

0

0

1

0

0

0

]只發(fā)生一位錯(cuò)碼時(shí)，矩陣E中只有2008.875copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組一個(gè)非零元素，與H的轉(zhuǎn)置相乘的結(jié)果是選出其中的一列，即校正子與H矩陣的哪一列相同，則該列即為碼元發(fā)生錯(cuò)誤的位置。由于

S

=

E，H當(dāng)T=[

0

0

0

1

0

1

1

](n，k)線性分組碼編、譯碼過程小結(jié)：2008.876copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組編碼過程：設(shè)線性分組碼為(n，k)，mk-2信息碼為：

M

=[mk-1

m1

m0]2)

由C=MG0

求出所有碼字，且為系統(tǒng)碼。1)

根據(jù)生成矩陣或監(jiān)督矩陣，H0=[P

Ir]G0=[Ik

Q]PT=

Q求出典型生成矩陣；譯碼過程：2008.877copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1）由收到的碼組R計(jì)算校正子S；S

=

RHTST或

=

HRT由S判決是否有錯(cuò)并通過S

=EHT

找出錯(cuò)誤圖樣；按照

R+E=C

計(jì)算并還原

C；將碼組C還原成原信息組M。9.4.5

漢明碼漢明碼是用于糾一位錯(cuò)誤的線性分組碼。特點(diǎn)：最小碼距：糾錯(cuò)能力：n

=

2r

-1d0

=3t

=1編碼效率：r2008.878copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組n

nnk n

-rR

==

=1-當(dāng)n很大時(shí)，R

??[例9-6]2008.879copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組n=15的漢明碼，其監(jiān)督位為多少？編碼效率為多少？=

n

+1

=

16，r

=

42008.880copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組解：

由n

=

2r

-1，可知：2r此漢明碼為（15，11）碼編碼效率：R

=k

/n

=11/15

?73%于是其信息位有15-4=11位其監(jiān)督位有15-11=4位例，r=3H矩陣的n列由除了全零以外的2r

-個(gè)1r位碼構(gòu)成，每碼組出現(xiàn)一次且全部出現(xiàn)。（H不唯一）2008.881copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組0010101

0001011

1000111

G

=

0100110

1011001

1110100

H

=

1101010

構(gòu)造漢明碼是線性分組碼，因此其監(jiān)督矩陣同樣有n列、r行，當(dāng)監(jiān)督位數(shù)給定后，即可構(gòu)造出漢明碼。得到的漢明碼如下所示：2008.882copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101000101001101100001010110111010100110011111010001110001111111（7，4）漢明碼編碼器a6a5a4a3信息組a0a1a2a3a4碼字++a5a6+2008.883copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組完備碼2008.884copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組糾正單個(gè)錯(cuò)誤的漢明碼中，r位校正子碼組與誤碼圖樣一一對應(yīng)，最充分地利用了監(jiān)督位所能提供的信息。因此，漢明碼也是糾一位錯(cuò)的線性分組碼中，編碼效率最高的。在一般情況下，對于能糾正t個(gè)錯(cuò)誤的線性分組碼(n，k)，應(yīng)滿足以下不等式：tintnnnn-krC+Ci=121-1?C2

-1=

2++C

=2008.885copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組tinn

n

nr n-kC2

t12

-1

=

2

-1

?

C+C

++C

=上式取等號時(shí)，校正子與誤碼不超過t個(gè)i=的1所有圖樣一一對應(yīng)，監(jiān)督碼元得到最充分的利用，這種線性分組碼即完備碼。漢明碼就是一種完備碼。該式亦稱為漢明界，它給出已知k和t時(shí)，所需要的監(jiān)督位數(shù)。除漢明碼外，迄今為止，找到的唯一能糾正多個(gè)錯(cuò)誤的完備碼為(23，12)戈雷碼。

t=32r

-1

>n時(shí)，可任選其中n個(gè)來構(gòu)成H陣的n列但此時(shí)構(gòu)成的則非漢明碼。2008.886copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組通常選擇碼重最小的矢量優(yōu)先。[例9-6]

試構(gòu)造一個(gè)k=5的可糾一個(gè)錯(cuò)的線性分組碼1/ 計(jì)算最短的碼長；2/ 構(gòu)造H；3/ 求生成矩陣G；4/ 求信息組為(10101)的編碼碼字C。解：

1/

因?yàn)閠

等于1,

且要求k=5,

可用試探法確定n2008.887copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組設(shè)：n-k=3，則2n-k

-1=23

-1=7<n=3+5=8不滿足糾錯(cuò)要求；設(shè)：n-k=4，則2n-k

-1=24

-1=15>n=4+5=9滿足糾錯(cuò)要求；于是取n=9，此時(shí)r=n-k=4，(9,

5)線性分組碼都可用于構(gòu)造H矩陣。2/ r=4，四位碼共有24

=16

種狀態(tài)，除全零外

0

0

1

0

1

0

0

0

10

1

0

1

1

0

0

1

01

0

0

1

0

0

1

0

0為了構(gòu)造典型矩陣，選1000，0100，0010，0001四碼組，然后從其余的11個(gè)碼組中，再選出5個(gè)，通常按照碼重從小到大選擇。1

1

1

0

0

1

0

0

0H=P2008.888copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組Ir實(shí)際只需9個(gè)00101000000011010001010100100001001100010011G

=[IkQ]

=

04/M=[1

0

1

0

1]C=MG=[1

0

1

0

1

0

1

1

0]Q已知Q

=

PTIk3/

求生成矩陣于是有：2008.889copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.5

循環(huán)碼2008.890copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.5.1

循環(huán)碼原理循環(huán)碼是線性分組碼的一個(gè)重要子類，也是目前研究最成熟的一類碼。它不僅有封閉性，且還有循環(huán)性。(n，k)碼組Ca

=[Cn-1Cn-2

C1C0

]則將所有碼元向左循環(huán)一位，得到的：Cb

=[Cn-2Cn-3

C1C0Cn-1

]也是許用碼組是許用碼組。即C

=[Ci

Ci-1

C0C1Cn-1

Ci+1]序號

碼

字0 0

0

0

0

0

0

01

0

0

1

1

1

0

1

2 0

1

0

0

1

1

13

0111010

4 1

0

0

1

1

1

05 1

0

1

0

0

1

16 1

1

0

1

0

0

17 1

1

1

0

1

0

0（7，3）循環(huán)碼W=00W=4若線性分組碼的

任一碼組循環(huán)移位所

得碼組仍在該碼組集

中，則此碼為循環(huán)碼。循環(huán)碼的循環(huán)圈數(shù)≥21673422008.891copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組5同一循環(huán)圈內(nèi)，碼字的重量相同序號碼字012345670

0

0

0

0

00

0

1

0

0

10

1

0

0

1

00

1

1

0

1

11

0

0

1

0

01

0

1

1

0

11

1

0

1

1

01

1

1

1

1

1（6，3）循環(huán)碼0W=01

W=2

2453W=467W=62008.892copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組★

由于具有循環(huán)性，編譯碼設(shè)備較簡單；★可以用代數(shù)的方法分析和設(shè)計(jì)編碼。2008.893copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組10-已5知-碼2組：C

循環(huán)碼的多項(xiàng)式表示=

[Cn

-1Cn-2

C1C0

]設(shè)x為一個(gè)任意的實(shí)變量，其冪次代表移位的次數(shù)，以Ci

作為多項(xiàng)式的系數(shù)，則可以得到碼多項(xiàng)式：C(x)

=Cn-2xn-1

+Cn-1xn-2

C

x

+C

]1

0循環(huán)碼的特點(diǎn)C(x)

=

C xn-1

+C

xn-2

C

x

+C

]n-1

n-2

1

0每循環(huán)一位，相當(dāng)于碼多項(xiàng)式乘以x，仍為許用碼組n-3n-2xn-1

+CC(1)

(x)

=

Cxn-2

C

x2

+C

x

+C

]1

0

n-11、生成多項(xiàng)式與生成矩陣循環(huán)碼中次數(shù)最低的多項(xiàng)式（全0碼字除外）稱為生成多項(xiàng)式

g(x)。0

0

1

1

1

0

1

C(x)

=

x4

+

x3

+

x2

+10

1

1

1

0

1

0

C(x)

=

x5

+

x4

+

x3

+

x例：2008.894copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組即：2008.895copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組g

(

x

)G

=

x

k

-

2

g

(

x

)

那么，g(x)，xg(x)，x2

g(x)xk

-1g(x)

都是許用碼組，而這k個(gè)碼組是線性無關(guān)的。于是用它們組成的矩陣則為生成矩陣

x

k

-1

g

(

x

)

xg

(

x

)M

=[mn-1mn-2

m1m0

]設(shè)信息碼組為：其對應(yīng)多項(xiàng)式為：m(x)=mk-1xk-1

+m

xk-2

++m

x

+mk-2

1

02008.896copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

x

g(x)

g(x)xk

-2

g(x)

xk

-1

g(x)=[mn-1mn-2

m1m0

]xk-2

++m

x+m

]g(x)1

0=[m

xk-1

+mk-1

k-2=

m(x)g(x)則編碼碼組為：C(x)

=

MG(x)由上式可看出：用G(x)生成的碼字，都是g(x)的倍式，都可以被g(x)整除。如何尋找生成多項(xiàng)式？已知編碼碼組為：C(x)=m(x)g(x)生成多項(xiàng)式是一個(gè)n-k次的多項(xiàng)式，且本身也是一個(gè)許用碼組：C'(x)=g(x)xkC'(x)為一個(gè)n次多項(xiàng)式，它是在模xn

-1運(yùn)算下的一個(gè)許用碼組，即：分子分母均為n次，故

Q(x)=12008.897copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組xkC'

(x)

C(x)xn

-1

=Q(x)

+

xn

-1于是上式成為：xkC'(x)=[xn

-1]+C(x)將C(x)=m(x)g(x)、C'(x)=g(x)帶入xk

C'

(x)

=[xn

-1]

+C(x)xn

-1

=

g

(

x)[

xk

+

m(

x)]

=

g

(

x)h(

x)有就是說：

g

(

x)是xn

-1的一個(gè)因式。g(x)的三個(gè)特性：g

(x

)為n

-k次多項(xiàng)式g

(x

)的常數(shù)項(xiàng)不為零g

(

x)是xn

-1的一個(gè)因式也就是說，尋找g(x)的過程，就是對xn

-1進(jìn)行因式分解的過程。2008.898copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-8]x7

-1=(x+1)(x3+x2

+1)(x3

+x+1)為了尋找(7，3)循環(huán)碼的生成多項(xiàng)式，只需找出

(n-k)=(7-3)=4次的因式即可。(x

+1)(x3

+

x2

+1)

=

x4

+

x2

+

x

+1(x

+1)(x3

+

x

+1)

=

x4

+

x3

+

x2

+1兩者均可，但將產(chǎn)生出不同的編碼碼組。2008.899copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組(7，6)碼：(7，1)碼：(7，4)碼：g(x)

=

x

+1g(x)

=

x3

+

x2

+1g(x)

=

x3

+

x

+1g(x)

=(x3

+

x2

+1)(x3

+

x

+1)9.5.2

循環(huán)碼的編、譯碼方法1、循環(huán)碼的編碼方法首先根據(jù)給定的(n,k)選定生成多項(xiàng)式g(x)并求出G(x)；由C(x)=MG(x)可以生成所有碼字，但不是系統(tǒng)碼；

生成系統(tǒng)碼的步驟如下：，即在信息碼后附加n-k個(gè)零；1/

做m

(x

)x

n

-k如：m=110，

n-k=7-3=4時(shí)，m(x)

=

x2

+xm(x)xn-k

=

x4

(x2

+

x)

=

x6

+

x5相當(dāng)于：11000002008.8100copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2/

用g(x)除得到商Q(x)和余式r(x)m(

x)

xn-kr(

x)g

(

x)

g

(x)=

Q(

x)

+m(x)

xn-k余式r(x)的次數(shù)必小于g(x)的次數(shù)n-k，將此余式加于信息位之后，成為編碼多項(xiàng)式。3/

編出