教材西安電子科技大學(xué)出版社TEXTBOOK通信原理與通信技術(shù)(第五版)張衛(wèi)鋼一編著選用高等學(xué)校電子信息類系列教材1微信公眾號(hào)2差錯(cuò)控制編碼問題：數(shù)字通信除了對波形失真不敏感外，還有一個(gè)優(yōu)點(diǎn)就是可以利用編碼這種“軟”方法對信號(hào)傳輸中出現(xiàn)的錯(cuò)碼進(jìn)行檢

查甚至糾正。那么,檢/糾錯(cuò)的機(jī)理是什么?如何實(shí)現(xiàn)呢?3檢錯(cuò)和糾錯(cuò)原理常用的檢錯(cuò)碼線性分組碼循環(huán)碼結(jié)語差錯(cuò)控制方式差錯(cuò)控制編碼的分類目錄CONTENT8.28.38.48.58.68.7差錯(cuò)控制編碼的概念8.88.1差錯(cuò)控制編碼的概念

8.1.1信源編碼因數(shù)字通信系統(tǒng)信源一般輸出的是模擬信息(信號(hào)),所以信源編碼器的主要任務(wù)就是“模/數(shù)轉(zhuǎn)換”,比如PCM

調(diào)制就是一種信源編碼技術(shù)；若信源輸出為離散信息(信號(hào))(圖1-6也可看作是一個(gè)數(shù)據(jù)通信系統(tǒng)),則信源編碼器的主要任務(wù)就是把離散信息變成信息代碼，可稱之為“離/數(shù)轉(zhuǎn)換”,比如，若離散信息“真”和“假”用符號(hào)

“T”

和“F”表示，則信源編碼就是將符號(hào)“T”和

“F”變換成“0”和“1”、“000”和“111”或其它信息碼。顯然，信

源編碼器的輸出就是只包含信息的數(shù)字基帶信號(hào)，簡稱信息碼。因此，可定義：信息碼：只攜帶通信信息的0、1序列。信源編碼：把信源輸出的信息變換成信息碼的過程或方法。無需贅言，信源譯碼是信源編碼的逆過程。不管是“模/數(shù)轉(zhuǎn)換”還是“離/數(shù)轉(zhuǎn)換”,都希望盡量減少編碼冗余度(字長),以提高編碼效率，進(jìn)而提高通信系統(tǒng)的有效性(比如，上例中的編碼應(yīng)取0和1)。因此，信源編碼遵循的原則就是編碼字長盡量短或編碼效率盡量高。58.1

差錯(cuò)控制編碼的概念

8.1.2信道編碼不管是模擬通信系統(tǒng)還是數(shù)字通信系統(tǒng)，都存在因干擾和信道傳輸特性不好對信號(hào)造成的不良影響(見圖8-1)。對模擬通信系統(tǒng)而言，信號(hào)波形發(fā)生的畸變會(huì)導(dǎo)致模擬信息失真并且畸變的

波形很難糾正回來。因此，只能采取各種防干擾、抗干擾措施盡量將干擾降到最低程度以保證通

信質(zhì)量；而對數(shù)字通信系統(tǒng)來說，

一定程度的波形畸變不會(huì)影響對數(shù)字信息的接收，因?yàn)槲覀冎?/p>

關(guān)心數(shù)字信號(hào)電平的高低而不太在乎其波形的失真(允許一定的“量變”),也就是說，數(shù)字通

信系統(tǒng)對干擾或信道特性不良的寬容度比模擬通信系統(tǒng)大(這也就是數(shù)字通信比模擬通信抗干擾

能力強(qiáng)的主要原因)。當(dāng)然，若干擾或信道特性不好超過一定限度，波形失真的量變轉(zhuǎn)化為質(zhì)變，

也會(huì)使數(shù)字通信系統(tǒng)產(chǎn)生誤碼，從而引起信息傳輸錯(cuò)誤。6信道干擾(a)模擬系統(tǒng)干擾示意圖信道干擾n(t)(b)

數(shù)字系統(tǒng)干擾示意圖圖8-

1

兩種通信系統(tǒng)干擾示意圖f(t)+n(t)畸變0畸變0▲

f(t)模擬信號(hào)0▲

f(t)

數(shù)字信號(hào)差錯(cuò)控制編碼的概念

8.1.2信道編碼n(t)8.1

差錯(cuò)控制編碼的概念

8.1.2信道編碼香農(nóng)在1848年和1957年發(fā)表的《通信的數(shù)學(xué)理論》、《適用于有擾信道的編碼理論某些成果》兩篇論文中提出了關(guān)于有擾信道中信息傳輸?shù)闹匾碚摗戕r(nóng)第二定理。對于一個(gè)給定的有擾信道，若該信道容量為C,則只要信道中的信息傳輸速率R小于C,就一定存在一種編碼方式，使編碼后的誤碼率隨著碼長n

的增加按指數(shù)下降到任意小的值?；蛘哒f只

要R<C,就存在傳輸速率為R的糾錯(cuò)碼。該定理雖然沒有明確指出如何對數(shù)據(jù)信息進(jìn)行糾錯(cuò)編碼，也沒有給出具有糾錯(cuò)能力的通信系

統(tǒng)的實(shí)現(xiàn)方法，但奠定了信道編碼的理論基礎(chǔ)并從理論上指出了信道編碼的努力方向。根據(jù)香農(nóng)定理可知，數(shù)字通信系統(tǒng)除了可采取與模擬系統(tǒng)同樣的措施降低干擾和信道不良對信號(hào)造成的影響之外，還可通過對所傳信息碼的特殊處理檢測或糾正錯(cuò)碼，以進(jìn)一步降低誤碼率，

提高通信的可靠性，這種特殊處理就是“差錯(cuò)控制編碼”技術(shù)。因此，數(shù)字通信系統(tǒng)可以從硬件上的抗干擾和軟件上的差錯(cuò)控制編碼兩個(gè)途徑提高通信系統(tǒng)的可靠性。8差錯(cuò)控制編碼的概念

8.1.2信道編碼差錯(cuò)控制編碼也叫信道編碼，主要任務(wù)就是對信源編碼器輸出的信息碼按一定數(shù)學(xué)規(guī)則加入一些攜帶錯(cuò)碼信息的冗余碼元(校驗(yàn)碼元或監(jiān)督碼元),形成“信息+錯(cuò)碼信息”的數(shù)據(jù)碼，供

收信端的信道譯碼器檢出或糾正通信過程中出現(xiàn)的錯(cuò)碼。因此，可定義：監(jiān)督碼元：附在信息碼后面用以攜帶錯(cuò)碼信息的碼元。信道編碼：按某種數(shù)學(xué)規(guī)則將信息碼元與監(jiān)督碼元編排在一起的過程或方法。編碼碼型：信源編碼器或信道編碼器輸出的數(shù)據(jù)碼格式?；蛘哒f，信道編碼器的任務(wù)就是編制一種具有檢/糾錯(cuò)能力的編碼碼型或數(shù)據(jù)序列。比如，數(shù)據(jù)序列11001100、10101010和1101001就是一種由3個(gè)碼字構(gòu)成的偶校驗(yàn)編碼碼型，其中，

無下劃線碼元是信息碼元，有下劃線碼元就是監(jiān)督碼元。9差錯(cuò)控制編碼的概念

8.1.2信道編碼信道編碼碼型與信源編碼碼型的形式相似，但編碼規(guī)則不同。比如，第6章出現(xiàn)的自然碼、折疊碼和格雷碼三種信源編碼碼型是按不同的碼元排列規(guī)律編制的；而后面介紹的分組碼和卷積碼兩種信道編碼碼型則是按碼元之間的不同數(shù)學(xué)關(guān)系設(shè)計(jì)的。可用圖8-2描述信源編碼和信道編碼概念。圖(a)

的信源編碼器將模擬信息轉(zhuǎn)換為0-1代碼序列(模-

數(shù)轉(zhuǎn)換);圖(b)的信源編碼器將數(shù)字信息A

、B

、C

、D分別轉(zhuǎn)換為00、01、10、

11代碼序列(離-數(shù)轉(zhuǎn)換);兩圖的信道編碼器都將信源編碼器輸出的單極性NRZ

碼轉(zhuǎn)換為雙

極性歸零碼并附帶1位偶校驗(yàn)碼送到信道上(陰影碼為校驗(yàn)碼)。圖(c)

為類比圖。顯然，信源編碼的目的是將通信信息數(shù)字化，信道編碼的目的是將通信信息可靠化。108.1

差錯(cuò)控制編碼的概念

8.1.2信道編碼根據(jù)第6章可知，信道編碼器輸出的基帶信號(hào)通常要經(jīng)碼型變換后才能送入信道傳輸(比如，圖8-2中的單極性碼變雙極性碼),即信道編碼器后面要有一個(gè)碼型變換器?？梢姡铄e(cuò)控制編碼從數(shù)據(jù)碼構(gòu)造角度提高可靠性，而碼型變換從數(shù)據(jù)碼傳輸角度提高可靠性；差錯(cuò)控制編碼注

重?cái)?shù)據(jù)碼的內(nèi)在規(guī)律性，而碼型變換強(qiáng)調(diào)數(shù)據(jù)碼的外在表現(xiàn)形式。二者雖然側(cè)重點(diǎn)和方法不同，

但實(shí)施對象和目的是一致的，且緊密相連都處在信號(hào)傳輸階段(信道中)。因此，在概念上可

把碼型變換看作信道編碼的一個(gè)分支，或者說，信道編碼應(yīng)該包含差錯(cuò)控制編碼和碼型變換兩

部分內(nèi)容，這樣，圖1-6的系統(tǒng)功能才更加準(zhǔn)確和完善。11為了強(qiáng)調(diào)信道編碼的差錯(cuò)控制功能，可把“碼型變換”稱為“線

路編碼”,這樣，信道編碼就等同于差錯(cuò)控制編碼了。據(jù)此，數(shù)字/

數(shù)據(jù)通信系統(tǒng)的編譯碼流程如圖8-

3所示。比如，信息字符

“A”

通過

信源編碼器變?yōu)樵紗螛O性不歸零碼00;然后經(jīng)過信道編碼器變?yōu)榫?/p>

有奇校驗(yàn)功能的單極性不歸零碼

001;最后經(jīng)過線路編碼器變成雙

極性歸零碼001。三個(gè)譯碼器完成

編碼器的逆變換任務(wù)。

12雙極性帶偶校驗(yàn)位

的數(shù)字基帶信號(hào)雙極性帶偶校驗(yàn)位

的數(shù)字基帶信號(hào)這樣就顛不破了運(yùn)輸(通信)數(shù)據(jù)信號(hào)

(NRZ)10111信道

編碼(a)

模擬信源數(shù)據(jù)信號(hào)

(NRZ)000

11o

11信道

編碼(b)

數(shù)字信源模擬信息數(shù)字信息A

B雞蛋(信碼)包裝(編碼)(c)

信道編碼類比圖圖8-2

信源編碼、信道編碼示意圖差錯(cuò)控制編碼的概念

8.1.2信道編碼信源

編碼信源

編碼圖8-3數(shù)字通信系統(tǒng)編譯碼流程綜上所述，可以認(rèn)為(1)信源編碼模塊實(shí)現(xiàn)信息到原始數(shù)字基帶信號(hào)的轉(zhuǎn)換。(2)信道編碼模塊實(shí)現(xiàn)原始數(shù)字基帶信號(hào)到差錯(cuò)控制基帶信號(hào)的轉(zhuǎn)換。(3)線路編碼模塊實(shí)現(xiàn)差錯(cuò)控制基帶信號(hào)到匹配信道基帶信號(hào)的轉(zhuǎn)換。001001傳輸介質(zhì)差錯(cuò)控制編碼的概念

8.1.2信道編碼A消息A消息信

源

譯

碼信

源

編

碼信

道

譯

碼信

道

編

碼線

路

譯

碼線

路

編

碼001001000013收信端可糾正錯(cuò)誤的碼信道譯碼器(a)

前向糾錯(cuò)

(FEC)能夠發(fā)現(xiàn)錯(cuò)誤的碼信道譯碼器應(yīng)答信號(hào)(b)檢錯(cuò)重發(fā)

(ARQ)能夠發(fā)現(xiàn)并可糾正錯(cuò)誤的碼信道譯碼器應(yīng)答信號(hào)

差錯(cuò)控制方式前向糾錯(cuò)(FEC)、

檢錯(cuò)重發(fā)(ARQ)和混合糾錯(cuò)(HEC)是常用的三種差錯(cuò)控制方式。(c)

混合糾錯(cuò)

(HEC)圖8-4

常用三種差錯(cuò)控制系統(tǒng)示意圖發(fā)信端信道編碼器發(fā)信端信道編碼器發(fā)信端信道編碼器信息碼信息碼信息碼信息碼信息碼信息碼收信端收信端14差錯(cuò)控制方式在前向糾錯(cuò)系統(tǒng)中，發(fā)信端將信息碼經(jīng)信道編碼后變成含有糾錯(cuò)信息的碼，然后通過信道發(fā)送出去；收信端收到這些碼字后，根據(jù)與發(fā)信端約定好的編碼規(guī)則，通過譯碼能自動(dòng)發(fā)現(xiàn)并糾正

因傳輸帶來的數(shù)據(jù)錯(cuò)誤。前向糾錯(cuò)方式只要求單向信道，因此適合于只能提供單向信道的場合和

一點(diǎn)發(fā)送多點(diǎn)接收的廣播方式。因?yàn)椴恍枰o發(fā)信端反饋信息，所以接收信號(hào)的延時(shí)小、實(shí)時(shí)性

好。這種系統(tǒng)的缺點(diǎn)是設(shè)備復(fù)雜且成本高。檢錯(cuò)重發(fā)系統(tǒng)的發(fā)信端將信息碼編成含有檢錯(cuò)信息的碼字發(fā)送到信道，收信端收到一個(gè)碼字

后進(jìn)行檢驗(yàn)，將有無錯(cuò)碼的結(jié)果通過反向信道反饋給發(fā)信端作為對發(fā)信端的應(yīng)答。發(fā)信端根據(jù)收

到的應(yīng)答信號(hào)做出是繼續(xù)發(fā)送新的數(shù)據(jù)還是把出錯(cuò)的數(shù)據(jù)重發(fā)的決定。檢錯(cuò)重發(fā)系統(tǒng)根據(jù)工作方式又可分為三種，即停發(fā)等候重發(fā)系統(tǒng)、返回重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)。15發(fā)信端1

碼組

2

2

3

4t收信端傳輸

ACK

傳輸

NAK傳

輸

ACK

傳輸

ACK2*

2

3(a)

停發(fā)等候重發(fā)示意圖發(fā)信端1

2

3

4

5

6

2

34

5

6

78

9

1011

12

13收信端傳

輸

NAK

傳輸3

4

5

6

2

34

5

6

78

9

10

11

12

13(b)

返回重發(fā)示意圖發(fā)信端工

23

45

6

27

89

10

11

12

13141516傳

輸

`

NAK

傳輸收信端2

3

45

6

27

8

9

10

11

12

13

14

1516(c)

選擇重發(fā)示意圖圖8-5檢錯(cuò)重發(fā)的三種工作方式16

差錯(cuò)控制方式差錯(cuò)控制方式混合糾錯(cuò)方式是前向糾錯(cuò)方式與檢錯(cuò)重發(fā)方式的結(jié)合，見圖8-4(c)。

其內(nèi)層采用FEC

糾正部分差錯(cuò)；外層采用ARQ重傳那些雖已檢出但并末糾正的差錯(cuò)。該方式在實(shí)時(shí)性和譯碼復(fù)雜性

方面是前向糾錯(cuò)與檢錯(cuò)重發(fā)方式的折衷，適用于環(huán)路延遲大的高速數(shù)據(jù)傳輸系統(tǒng)。17

差錯(cuò)控制編碼分類根據(jù)不同的衡量標(biāo)準(zhǔn)，差錯(cuò)控制編碼主要有如下分類。(1)根據(jù)編碼功能可分為檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼。只能完成檢錯(cuò)功能的叫檢錯(cuò)碼；具有糾

錯(cuò)能力的叫糾錯(cuò)碼；既可檢錯(cuò)也可糾錯(cuò)的是糾刪碼。(2)根據(jù)信息碼元與監(jiān)督碼元的關(guān)系可分為線性碼和非線性碼。滿足線性關(guān)系的(監(jiān)督碼元

是信息碼元的線性組合)被稱為線性碼；不存在線性關(guān)系的就是非線性碼。(3)根據(jù)信息碼元與監(jiān)督碼元的約束方式可分為分組碼和卷積碼。在分組碼中，編碼前先把

信息序列分為k位一組，然后用一定規(guī)則附加m位監(jiān)督碼元，形成n=k+m位的碼字，監(jiān)督碼元僅

與本碼字的信息碼元有關(guān)而與其它碼字的信息碼元無關(guān)。但在卷積碼中，碼字中的監(jiān)督碼元不但

與本碼字信息碼元有關(guān)，還與前面碼字的信息碼元有約束關(guān)系，就像鏈條那樣一環(huán)扣一環(huán)，因此，

卷積碼又被稱為連環(huán)碼或鏈碼。18差錯(cuò)控制編碼分類(4)根據(jù)信息碼與監(jiān)督碼的排列形式分為系統(tǒng)碼和非系統(tǒng)碼。所有碼字的k

信息位和m監(jiān)督

位排列順序一致且互不相混的是系統(tǒng)碼，反之就是非系統(tǒng)碼。(5)根據(jù)錯(cuò)碼的形式可分為糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。顧名思義，前者用于糾正

因信道中隨機(jī)干擾引起的誤碼，后者主要對付信道中出現(xiàn)的突發(fā)錯(cuò)誤。(6)根據(jù)是否具有循環(huán)性可分為循環(huán)碼和非循環(huán)碼。若分組碼中任一碼字的碼元循環(huán)移位

后仍然是這組碼的碼字，則這組碼就是循環(huán)碼。反之，就是非循環(huán)碼。顯然，一種編碼可以具有多類性。本章主要介紹糾正隨機(jī)錯(cuò)誤的二進(jìn)制線性分組碼。19檢錯(cuò)和糾錯(cuò)原理先介紹數(shù)字通信中碼元的兩種錯(cuò)誤形式。(1)隨機(jī)差錯(cuò)，見圖8-6

(b)

。也稱為單比特差錯(cuò)，是由隨機(jī)/起伏噪聲引起的碼元錯(cuò)誤。

其特點(diǎn)是碼元中任意一位或幾位發(fā)生從0變1或從1變0的錯(cuò)誤是相互獨(dú)立的，彼此之間沒有聯(lián)

系；一般不會(huì)引起成片的碼元錯(cuò)誤。(2)突發(fā)差錯(cuò)，見圖8-6(c)

。由突發(fā)噪聲引起的碼元錯(cuò)誤，比如閃電、電器開關(guān)的瞬態(tài)、

磁帶缺陷等都屬于突發(fā)噪聲。該錯(cuò)誤的特點(diǎn)是各錯(cuò)誤碼元之間存在相關(guān)性，因此是成片出現(xiàn)，

也就是說突發(fā)錯(cuò)誤是一個(gè)錯(cuò)誤序列，該序列的首部和尾部碼元都是錯(cuò)的，中間的碼元有錯(cuò)的

也有對的，但錯(cuò)的碼元相對較多，錯(cuò)誤序列的長度(包括首和尾在內(nèi)的錯(cuò)誤所波及的段落長

度)稱為突發(fā)長度。20發(fā)送碼

0接收碼

0

0

0

0(b)

單比特差錯(cuò)發(fā)送碼

0

0

0

1

0101接收碼

000

11

001010—突發(fā)差錯(cuò)長度(8比特)

→

?(a)

差錯(cuò)分類

(c)

突發(fā)差錯(cuò)圖8-

6通信差錯(cuò)及分類

檢錯(cuò)和糾錯(cuò)原理單比特差錯(cuò)

突發(fā)差錯(cuò)起伏

噪

聲脈沖

噪聲通信差錯(cuò)21檢錯(cuò)和糾錯(cuò)原理假設(shè)要發(fā)送一組具有四個(gè)狀態(tài)的數(shù)據(jù)信息(一個(gè)電壓信號(hào)的四個(gè)值，1V、2V、3V、4V)。我們首先要用二進(jìn)制碼對數(shù)據(jù)信息進(jìn)行編碼，顯然，用2位二進(jìn)制碼就可完成，編碼表如下：從表8-1可見，任何一組碼不管是一位還是兩位發(fā)生錯(cuò)誤，都會(huì)使該碼字變成另外一組信息碼，從而引起信息傳輸錯(cuò)誤?？梢?，以這種編碼形式得到的數(shù)字信號(hào)在傳輸過程中不具備檢錯(cuò)

和糾錯(cuò)的能力，這是我們所不希望的。表8-2位二進(jìn)制編碼表數(shù)據(jù)信息1V2V3V4V數(shù)據(jù)編碼0001101122檢錯(cuò)和糾錯(cuò)原理為了表8-1碼的缺點(diǎn)，可在每個(gè)碼字后面再加1位碼元，變成3位碼字。這樣，在3位碼字的8種組合中只有4組是許用碼字，其余4種被稱為禁用碼字，編碼表變成表8-2。在許用碼字000、011、101、110中，右邊加上的1位碼元就是監(jiān)督碼元，它的加入原則是使碼字中1的個(gè)數(shù)為偶數(shù)，這樣監(jiān)督碼元就和前面2位信息碼元發(fā)生了關(guān)系。這種編碼方式稱為偶校驗(yàn)(Evenparity),反之，如果加入原則是使碼字中1的個(gè)數(shù)為奇數(shù)，則編碼方式稱為奇校驗(yàn)(Odd

parity)。表8-23位二進(jìn)制編碼表數(shù)據(jù)信息1V2V3V4V××××數(shù)據(jù)編碼000

011

101110001010

100111238.4

檢錯(cuò)和糾錯(cuò)原理通過增加一位監(jiān)督碼元，可以檢出1位或3位錯(cuò)誤(3位出錯(cuò)的概率極小),但無法糾正錯(cuò)誤。能否通過增加監(jiān)督碼元的位數(shù)來增加檢錯(cuò)位數(shù)或?qū)崿F(xiàn)糾錯(cuò)功能呢?比如在表8-2中再加1位

監(jiān)督碼元變成4位編碼(見表8-3),看看情況如何。表8-34位二進(jìn)制編碼表數(shù)據(jù)信息1V2V3V4V××××數(shù)據(jù)編碼0000011010101100000100101000111101000111101111010011111010010101顯然，簡單地增加一位監(jiān)督碼元并沒有提高檢錯(cuò)與糾錯(cuò)能力，那么,檢錯(cuò)與糾錯(cuò)能力到底與什么有關(guān)呢?在回答這個(gè)問題之前，先介紹兩個(gè)新概念——碼元的漢明(Hamming)距離

和碼元的漢明重量。24

檢錯(cuò)和糾錯(cuò)原理漢明距離：兩個(gè)碼字中對應(yīng)碼位上碼元不同的位數(shù)，簡稱碼距或漢明距。研究表明，一種編碼方式的檢錯(cuò)和糾錯(cuò)能力與許用碼字中的最小碼距有關(guān)，即(1)在一個(gè)碼字內(nèi)要想檢出e位誤碼，要求最小碼距為

(8.4-1)(2)在一個(gè)碼字內(nèi)要想糾正t位誤碼，要求最小碼距為

(8.4-2)(3)在一個(gè)碼字內(nèi)要想糾正t位誤碼，同時(shí)檢測出e

位誤碼(e>t),要求最小碼距為

e>t

(8.4-3)258.4

檢錯(cuò)和糾錯(cuò)原理所謂能糾正t位誤碼，同時(shí)檢測出e位誤碼的意思是指當(dāng)錯(cuò)碼不超過t位時(shí)，錯(cuò)碼能夠自動(dòng)糾正，當(dāng)錯(cuò)碼超過t位時(shí)，則不能糾正錯(cuò)誤，但仍可檢測出e

位誤碼，這正是混和檢錯(cuò)糾錯(cuò)的控制方式。顯然，要提高編碼的糾、檢錯(cuò)能力，不能僅靠簡單地增加監(jiān)督碼元位數(shù)(即冗余度),更重要的是要加大最小碼距(即碼字之間的差異程度),而最小碼距的大小與編碼的冗余度是

有關(guān)的。最小碼距增大，碼元的冗余度就增大，但碼元的冗余度增大，最小碼距不一定增大。

因此，一種編碼方式具有檢錯(cuò)和糾錯(cuò)能力的必要條件是信息編碼必須有冗余，而檢錯(cuò)和糾錯(cuò)

能力的大小由最小碼距決定。

另外，檢錯(cuò)要求的冗余度比糾錯(cuò)要低。268.4

檢錯(cuò)和糾錯(cuò)原理【例8-1】設(shè)有一編碼集為1100110,0111010,1011101。求最小碼距。若用于檢錯(cuò)，能檢出幾位錯(cuò)碼?若用于糾錯(cuò)，能糾正幾位錯(cuò)碼?若用于混合糾檢錯(cuò)，能糾、檢幾位錯(cuò)碼?【解】因?yàn)槿齻€(gè)碼距分別為d(1100110,0111010)=4,d(1100110,1011101)=5,d(0111010,1011101)=5所以，最小碼距

dmin=4若用于檢錯(cuò)，則由dmin≥e+1可得

e=3,即能檢出3位錯(cuò)碼；若用于糾錯(cuò)，則由dmin≥2t+1可得

t=1,即能糾正1位錯(cuò)碼；若用于混合糾檢錯(cuò)，則由dmin≥e+t+1(e>t)可得t=1,e=2,即能糾正1位錯(cuò)碼，同時(shí)檢出2位錯(cuò)碼。27顯然，編碼的冗余度越大，編碼效率就越低，即通信系統(tǒng)可靠性的提高是以降低有效性(編碼效率)來換取的，而差錯(cuò)控制編碼的努力方向就是尋找好的編碼方法，在一定的差錯(cuò)控制能力

要求下，使得編碼效率盡量高，譯碼方法盡量簡單。漢明重量：

一個(gè)碼字中非零碼元的個(gè)數(shù)，簡稱碼重。比如，碼字100110的碼重為3,0110的碼重是2。它反映一個(gè)碼字中“1”和“0”的“比重”。8.

檢錯(cuò)和糾錯(cuò)原理編碼效率：信息碼位數(shù)k與差錯(cuò)控制碼位數(shù)n

之比，用R。表示。(8.4-4)288.5

幾種常用的檢錯(cuò)碼8.5.1奇偶校驗(yàn)碼奇偶校驗(yàn)碼是數(shù)據(jù)通信中最常見的一種簡單檢錯(cuò)碼

，

其編碼規(guī)則是

：

把信息碼先分組

，

形成多

個(gè)

許

用

碼

字，

在

每

一

個(gè)

許

用

碼

字

最

后(

最

低

位

)

加

上

一

位

監(jiān)

督

碼

元

即

可

。

加

上

監(jiān)

督

碼

元

后

使

該

碼

字

中

1

的

數(shù)目

為

奇

數(shù)

的

編

碼

稱

為

奇

校

驗(yàn)

碼

，

為

偶

數(shù)

的

編

碼

稱

為

偶

校

驗(yàn)

碼

。

根

據(jù)

編

碼

分

類

，

可

知

奇偶校驗(yàn)碼屬于

一

種檢錯(cuò)、線性、分組系統(tǒng)碼。奇偶校驗(yàn)碼的監(jiān)督關(guān)系可用以下公式進(jìn)行表述。對于偶校驗(yàn)碼必須保證an-1④an-2④an-3④

…④a?=0

(8.5-1)a?=an-1④an-2④an-3④

…④a?

(8.5-2)298.5

幾種常用的檢錯(cuò)碼對于奇校驗(yàn)碼必須保證an-1④an-2④an-3④

…④a?=1

(8.5-3)a?=an-1④an2④an-3④

…④a?④1

(8.5-4)根據(jù)奇偶校驗(yàn)的規(guī)則可以看到，當(dāng)碼字中的誤碼為偶數(shù)時(shí)，校驗(yàn)失效。因此，簡單的奇偶校驗(yàn)碼只能檢測出奇數(shù)個(gè)位發(fā)生錯(cuò)誤的碼字。假設(shè)兩個(gè)碼字同為奇數(shù)(或偶數(shù))碼字，如果兩組碼只有1位不同，則它們的奇偶性就不同，這與假設(shè)相矛盾；如果兩組碼有2位不同，則它們的奇偶性不變。再假設(shè)兩個(gè)碼字奇偶性不同，如果兩組碼只有1位不同，則它們就變成奇偶性相同的碼，這與假設(shè)相矛盾；如果兩組

碼有2位不同，則它們的奇偶性不變。換句話說，因?yàn)闃?gòu)造不出碼距為1的奇偶校檢碼，所以，奇偶校驗(yàn)碼的最小碼距只能為2。

308.5幾種常用的檢錯(cuò)碼

8.5.2水平奇偶校驗(yàn)碼為克服上述簡單奇偶校驗(yàn)碼檢錯(cuò)能力不高且不能檢測突發(fā)錯(cuò)誤的缺點(diǎn)，可以將經(jīng)過簡單奇偶校驗(yàn)編碼的碼字按行排列成方陣，每一行是一個(gè)碼字，若有n個(gè)碼字則方陣就有n行。如果按碼字逐行傳輸?shù)脑挘瑒t檢錯(cuò)能力沒有改變。但若發(fā)信端按列傳輸：000100111010010010101.

…1001011(如表中箭頭所示),收信端按列接收后再按行還原

成發(fā)信端的方陣，然后按行進(jìn)行偶校驗(yàn)，則糾錯(cuò)能力就會(huì)發(fā)生變化。觀察該表可見，因?yàn)槭侵鹆邪l(fā)送，在一列中不管出現(xiàn)幾個(gè)誤碼(偶數(shù)個(gè)或奇數(shù)個(gè)),對應(yīng)

在每一行都只是一位誤碼，所以都可以通過水平偶校驗(yàn)檢驗(yàn)出來；但對于每一行(一個(gè)碼字)

而言仍然只能檢出所有奇數(shù)個(gè)錯(cuò)誤。與簡單奇偶校驗(yàn)編碼相比，這種方法的最大優(yōu)點(diǎn)是可以

檢出所有長度小于行數(shù)(碼字?jǐn)?shù))的突發(fā)錯(cuò)誤。31信息碼元

監(jiān)督(校驗(yàn))碼元碼

組

10101101100

1碼

組

20101010010

0碼組300110000110碼組411000111001碼

組

500111工11工10碼

組

60001001111

1碼組711101100001幾種常用的檢錯(cuò)碼表8-4水平偶校驗(yàn)碼32信息碼元

監(jiān)督(校驗(yàn))碼元碼組1010110110個(gè)0

1碼組20101010010

0碼組30011000011

0碼組41100011100

1碼組50011111111

0碼組60001001111

1碼組71110110000

1監(jiān)督碼元001→11000L01

08.5

幾種常用的檢錯(cuò)碼

8.5.3二維奇偶校驗(yàn)碼在上述水平奇偶校驗(yàn)編碼的基礎(chǔ)上，若再加上垂直奇偶校驗(yàn)編碼就構(gòu)成二維奇偶校驗(yàn)碼。比如對表8-4的7個(gè)碼字再加上一行就構(gòu)成二維偶校驗(yàn)碼，如表8-5所示。表8-5二維偶校驗(yàn)碼33表8-6群計(jì)數(shù)碼碼字信息碼元監(jiān)督(校驗(yàn))碼元碼字101011011000101碼字201010100100100碼字300110000110100碼字411000111000101碼字500111111111000碼字600010011110101碼字7111011000001018.5

幾種常用的檢錯(cuò)碼

8.5.4群計(jì)數(shù)碼奇偶校驗(yàn)碼是通過添加監(jiān)督位將碼字的碼重配成奇數(shù)或偶數(shù)。而群計(jì)數(shù)碼的編碼原則是先算出信息碼字的碼重，然后用二進(jìn)制計(jì)數(shù)法將碼重作為監(jiān)督碼元添加到信息碼字的后面。該碼屬于非線性分組系統(tǒng)碼，除了能檢出碼字中奇數(shù)個(gè)錯(cuò)誤之外，還能檢出偶數(shù)個(gè)0變1或1變0的錯(cuò)誤。除了無法檢出1變0和0變1成對出現(xiàn)的誤碼外，可以檢出其它所有形式的錯(cuò)誤。348.5幾種常用的檢錯(cuò)碼

8.5.5恒比碼恒比碼的編碼原則是從確定碼長的碼字中挑選那些“1”和“0”個(gè)數(shù)的比值一樣的碼字作為許用碼字。這種碼通過計(jì)算接收碼字中“1”的個(gè)數(shù)是否正確，就可檢測出有無錯(cuò)誤。不難看出這種碼的最小碼距是2,它能夠檢出碼字中所有奇數(shù)個(gè)錯(cuò)誤和部分偶數(shù)個(gè)錯(cuò)誤。該碼也是非線性分組碼，但不是系統(tǒng)碼，其主要優(yōu)點(diǎn)是簡單，適用于對電傳機(jī)或其它鍵盤設(shè)

備產(chǎn)生的字母和符號(hào)進(jìn)行編碼。表8-7五單位保護(hù)電碼表

阿拉伯?dāng)?shù)字

編碼

阿拉伯?dāng)?shù)字

編碼

0

01101

5

00111

1

01011

6

10101

2

11001

7

11100

3

10110

8

01110

4

11010

9

10011

358.6

線性分組碼

8.6.1線性分組碼的概念對于信源輸出的2k個(gè)離散消息，信源編碼器可以用k位二進(jìn)制碼對它們進(jìn)行編碼，形成2k個(gè)具有k位碼元的碼字，這些碼字被稱為信息碼字，通常用矩陣D

表示。若在每個(gè)k位信息碼字后面添加m位碼元，就會(huì)形成2k

個(gè)n位碼字(n=k+m)

。而添加的m

個(gè)碼元不攜帶欲傳送的信息，被稱為監(jiān)督碼元或校驗(yàn)碼元。定義分組碼：由信息碼字附加監(jiān)督碼元后所構(gòu)成的碼字集合，通常用矩陣C表示。顯然，如果分組碼的各碼字之間沒有關(guān)系的話(彼此獨(dú)立或線性無關(guān)),則對于大的k

值或n

值，編碼設(shè)備會(huì)極為復(fù)雜，因?yàn)榫幋a設(shè)備必須儲(chǔ)存2k個(gè)字長為n

的碼字。鑒于此，需要構(gòu)造

碼字之間有某種關(guān)系的分組碼，使得2個(gè)碼字中的一些碼字可以通過另一些碼字的組合得到，

從而降低編碼的復(fù)雜性，線性分組碼應(yīng)運(yùn)而生。定義：線性分組碼：信息碼元與監(jiān)督碼元滿足一組線性方程的分組碼。368.

線性分組碼

8.6.1線性分組碼的概念不能用線性方程組描述的分組碼就是非線性分組碼。通常，把長度為n,有2個(gè)碼字的線性分組碼稱為“(n,k)線性碼”。線性分組碼有兩個(gè)重要特性：(1)

封閉性。即任意兩個(gè)許用碼字之模2和仍為—許用碼字，這個(gè)性質(zhì)隱含著線性分組碼

必須包含全零碼字這一結(jié)論；(2)

碼字的最小碼距等于非零碼的最小碼重。利用這一特性，可以迅速方便地找出一種線

性分組碼的最小碼距，從而判斷該碼的檢/糾錯(cuò)能力。378.6

線性分組碼

8.6.1線性分組碼的概念在(n,k)碼中，雖然有2k個(gè)碼字，但因?yàn)橛辛司€性條件，2k個(gè)碼字中只有k

個(gè)獨(dú)立，其余的都可以通過這k

個(gè)獨(dú)立碼字的線性組合而得到(模2加),因此，編碼設(shè)備不再需要儲(chǔ)存2k

個(gè)字長為n

的碼字，而只需保存k

個(gè)線性無關(guān)的碼字即可。比如，一個(gè)n=7,k=3

的分組碼共有8個(gè)碼字C?,C?,…,C?,

可記為C=[c6,C5,C4,C?,C?,C?,C?],

其中c?,C?C?為信息碼，其余為監(jiān)督碼。若該分組碼每個(gè)碼字中的各位滿足線性條件388.6

線性分組碼

8.6.1線性分組碼的概念則對3個(gè)信息碼字001、010和100可構(gòu)造出3個(gè)線性無關(guān)的分組碼字

C?=0011101、C?=0100111

和

C?=1001110。其余四個(gè)碼字(不包含全零碼字

C?=0000000)

均可由這三個(gè)碼字線性組合而成：C?=0111010=C?+C?=0011101+0100111;C?=1010011=C?+C?=0011101+1001110;C?=1101001=C?+C?=0100111+1001110;C?=1110100=C?+C?+C?=0011101+0100111+1001110。因此，對于該(7,3)碼，編碼設(shè)備只需存儲(chǔ)

C?、C?和C?

三個(gè)碼字即可。398.

線性分組碼

8.6.1線性分組碼的概念設(shè)有一(n,k)線性分組碼[Cn-1,Cn-2,…,C?],其中信息碼為[dK-1,dk-2,…,d?],碼字格式及類比圖見圖8-8(a)

和

(b)。把具有這種結(jié)構(gòu)的線性分組碼稱為線性分組系統(tǒng)碼。n位線性分組碼元C一Cn-2

Cn-k

C?

C?(b)

線性分組碼類比圖圖8-8

線性分組碼格式

40d<?dk-2●d?d?●人k位信息碼元

m=n-k位監(jiān)督碼元(冗余碼元)(a)線性分組碼格式8.6

線

性

分

組

碼

8.6.2線性分組碼的編碼根據(jù)圖8-8,可將分組碼和信息碼用向量或矩陣表示為C=[cn-1Cn-2…Co]C=[c?C?…Cn]D=[dk-1dk-2…d?]D=[d?d?…dk]則每一個(gè)分組碼碼字可以由信息碼元的線性組合而成，即有(8.6-1)(8.6-2)418.6

線性分組碼

8.6.2線性分組碼的編碼上述各式描述了一個(gè)分組碼碼字與一個(gè)信息碼碼字之間的關(guān)系。42即C=D·G

(8.6-3)G

稱為生成矩陣，是一個(gè)k×n階矩陣，具體形式為8.6

線性分組碼

8.6.2線性分組碼的編碼將上述C

與D的n

個(gè)關(guān)系式用矩陣表示為438.6

線性分組碼

8.6.2線性分組碼的編碼該矩陣又可分解為兩個(gè)子矩陣(8.6-4)44這樣，分組碼C又可表示為C=D[IkQ]

(8.6-5)上述各式中的C和D

可以是由一個(gè)碼字構(gòu)成的行向量，也可以是由2k個(gè)行向量構(gòu)成的2k×n階分組碼矩陣或2k×k階信息碼矩陣。8.6

線性分組碼

8.6.2線性分組碼的編碼其中I

是k×k

階單位陣，Q為k×m階矩陣，即45線性分組碼

8.6.2線性分組碼的編碼需要強(qiáng)調(diào)的是，(1)生成矩陣G

的行數(shù)和列數(shù)分別是信息碼D的位數(shù)k

和分組碼C的位數(shù)n。(2)上述各式中的C和D

可以是由一個(gè)碼字構(gòu)成的行向量，也可以是由2個(gè)行向量構(gòu)成

的2k×n階分組碼矩陣和2k×k階信息碼矩陣。式(8

.

6

-

3)說明，(n,k)

線性碼完全由生成矩陣G

的k行元素決定，即任何一個(gè)分組碼碼字都是G元素的線性組合。因

(n,k)線性碼中的任何k

個(gè)線性無關(guān)碼字都可用來構(gòu)成生成矩陣G,故

G

的各行都線性無關(guān)。若各行之間有線性相關(guān)的，就不可能由G生成2k個(gè)不同碼字了。其實(shí)，G的各行本身就是一個(gè)碼字。若給定k個(gè)線性無關(guān)碼字，則可直接構(gòu)成G矩陣并生成其余碼字。典型生成矩陣：能夠分塊為I和Q的生成矩陣G。非典型生成矩陣：不能夠分塊為I和Q的生成矩陣G。468.6

線性分組碼

8.6.2線性分組碼的編碼由典型生成矩陣G

產(chǎn)生的線性分組碼C是系統(tǒng)碼，其特征是前k

位元素與信息碼完全相同，我們常用的是典型生成矩陣。非典型生成矩陣G

所產(chǎn)生的線性分組碼C

就是非系統(tǒng)碼。非典型生

成矩陣通過矩陣初等行變換也可以轉(zhuǎn)化為典型生成矩陣。系統(tǒng)碼編碼器只需存儲(chǔ)

k×m個(gè)元素(非系統(tǒng)碼要存儲(chǔ)k×n個(gè)),就可根據(jù)信息向量(矩陣)生成相應(yīng)的分組碼碼字(分組碼矩陣),從而降低了編碼復(fù)雜性，提高了編碼效率。因系統(tǒng)碼的編/譯碼器比較簡單且檢/糾錯(cuò)性能與非系統(tǒng)碼相同，故我們只討論系統(tǒng)碼。478.6

線性分組碼

8.6.2線性分組碼的編碼【例8-2】給定一個(gè)(7,4)線性分組碼的生成矩陣：若信息碼為d=[1101],

求該信息碼的線性分組編碼C?！窘狻扛鶕?jù)式(8-6)可得48

線性分組碼

8.6.2線性分組碼的編碼即對信息碼[1101]的線性分組編碼為[0001101]。注意：矩陣乘法采用模2乘和模2加。上式也可寫成：C=1·g?④1·g?

田0

·g?④1·g?=[1000110]④[0100011]④[0001101]=[1101000]由以上討論可知，編碼前的信息碼字共有2k種組合，而編碼后的碼字因附加了m

位校驗(yàn)碼元而有2”種組合，顯然，2”>2k,

說

明C與D的關(guān)系不唯一。因此，優(yōu)選矩陣Q就可得到既有較強(qiáng)

檢/糾錯(cuò)能力，又容易實(shí)現(xiàn)且編碼效率較高的一種線性分組碼。498.6

線性分組碼

8.6.2線性分組碼的編碼為了評價(jià)線性分組碼的差錯(cuò)控制能力，只需求出分組碼中非零碼的最小碼重(等于碼字的最小碼距),然后利用式(8.4-1)、(8.4-2)和(8.4-3)計(jì)算即可?！纠?-3】已知線性(6,3)碼的生成矩陣為求：兩組線性分組碼及其差錯(cuò)控制能力。·508.6

線性分組碼

8.6.2線性分組碼的編碼【解】因?yàn)閗=3,

所以信息碼碼字矩陣(3×8階)為則由式(8-6)可得出分組碼碼字矩陣分別為51可見，分組碼C?的前3位與信息碼不完全相同，是非系統(tǒng)碼；而分組碼C?

的前3位與信息碼完全相同，是系統(tǒng)碼。不考慮全零碼，

C?

和C?

的最小碼重都為3,即最小碼距dmin=3。根據(jù)式(8.4-1)、(8.4-2)和(8.4-3)可知兩組分組碼都能夠檢2位錯(cuò)，糾1位錯(cuò)，但不能同時(shí)糾1位錯(cuò)檢1位錯(cuò)。8.6

線性分組碼

8.6.2線性分組碼的編碼52Cm](8.6-6)(8.6-7)該式可變?yōu)榫仃囅喑诵问?，?8.6-8)是m×k

階矩陣，可用P

表示，即下面簡要介紹譯碼原理。從式(8.6-4)式可得C=D[IkQ]=[D

DQ]=[DCm=DQ式(8.6-7)兩邊模二加Cm,

可

得

：DQ

田Cm=0,令

,則有。其中QP=Q或

Q=PT線性分組碼

8.6.3線性分組碼的譯碼538.6

線性分組碼

8.6.3線性分組碼的譯碼則有

(8.6-10)通常，把H

稱為一致校驗(yàn)矩陣或一致監(jiān)督矩陣。具有[PI]形式的H矩陣稱為典型形式的監(jiān)督矩陣。由典型形式的監(jiān)督矩陣及信息碼元很容易算出各監(jiān)督碼元。線性代數(shù)理論告訴我們，典型形式監(jiān)督矩陣各行一定是線性無關(guān)的，因此，由它可以得到m

個(gè)獨(dú)立的監(jiān)督位。非典型形式的監(jiān)督矩陣可以通過行運(yùn)算或列互換化為典型形式，除非非典型形

式監(jiān)督矩陣的各行不是線性無關(guān)的。比較式(8.6-4)和式(8.6-10)可見，借助式(8.6-9)可由校驗(yàn)矩陣H

何以求得生成矩陣G,

反之亦然。548.6

線性分組碼

8.6.3線性分組碼的譯碼將式(8

.6-6)和HT

代入式(8.6-8)可得CHT=0(8.6-11)該式說明任何碼字和校驗(yàn)矩陣H

的轉(zhuǎn)置相乘，其結(jié)果為m

位零向量。設(shè)收信端接收碼字為R,將

R帶入式(8.6-11)計(jì)算。若結(jié)果為零，說明沒有錯(cuò)碼，即R=C。

可見，校驗(yàn)矩陣能夠檢測碼字的正確性，“校驗(yàn)”之名由此而來。可以推導(dǎo)出校驗(yàn)矩陣H與生成矩陣G滿足GHT=HGT=0

(8.6-12)設(shè)行向量R=[r?r?…rn]是收信端收到的碼字。因?yàn)樾诺栏蓴_會(huì)產(chǎn)生誤碼，則接收向量R和發(fā)送向量C就會(huì)有差別。若用向量E=[e?

e?…e,]

表示這種差別，則三者的關(guān)系為E=R+C

(8.6-13)55E

的碼重就是誤碼的個(gè)數(shù)，因此，希望E

的碼重越小越好。式(8.6-13)也可寫為R=E+C(8.6-14)定義矩陣S為R的伴隨式S=RHT(8.6-15)則由式(8.6-11)、(8.6-14)和(8.6-15)得S=(E+C)HT=EHT+CHT=EHT式(8.6-16)表明伴隨式S

只與錯(cuò)誤圖樣E

有關(guān)而和發(fā)送碼字無關(guān)。(8.6-16)8.6

線性分組碼

8.6.3線性分組碼的譯碼這里的“+”號(hào)仍為模2加。若R

中的某一位r;與C

中的相同位c;一

樣時(shí)，E中的e=0;若不同(即出現(xiàn)誤碼),則e=1?？梢娤蛄縀

能夠反映誤碼情況，因此，稱之為錯(cuò)誤向量或錯(cuò)誤圖樣。56線性分組碼

8.6.3線性分組碼的譯碼當(dāng)通信雙方確定了信道編碼后，生成矩陣G

和與之緊密相關(guān)的監(jiān)督矩陣H

也就隨之而定。對于收信端而言，它可以知道生成矩陣G、

監(jiān)督矩陣H以及接收到的行向量R。為了譯碼，收信端先利用式(8.6-15)求出伴隨式S,

然后利用式(8.6-16)解出錯(cuò)誤圖樣E,

最后根據(jù)式(8.6-13)或(8.6-14)解出發(fā)送碼字C。圖8-9給出編碼與譯碼示意圖。D

C

SEC信道

根據(jù)S=EHT發(fā)信端編碼

G

HT

收信端譯碼圖8-9線性分組碼編碼與譯碼示意圖【例8-4】設(shè)發(fā)送序列為11010100111,接收序列為01101011011.求差錯(cuò)圖樣和突發(fā)長度。解：由式8.6-10得錯(cuò)誤圖樣E=R+C=11010100111+01101011011=10111111100可見，E中的第一個(gè)“1”到最后一個(gè)“1”共有9個(gè)碼，因此，突發(fā)長度為9。R578.6

線性分組碼

8.6.4漢明碼漢明碼是由美國數(shù)學(xué)家漢明(Richard

Wesley

Hamming)于1950年提出的一種可糾正1位隨機(jī)錯(cuò)碼的線性分組碼。前面出現(xiàn)的漢明距離、漢明重量都是他提出的概念。漢明碼的主要參數(shù)如下：(1)碼字長度：n=2-1。(2)信息碼長度：

k=2'-1-r。(3)監(jiān)督碼長度：r=n-k,r

是不小于3的任意整數(shù)。(4)最小碼距：(5)糾錯(cuò)能力：糾正1位隨機(jī)錯(cuò)碼或檢測2位隨機(jī)錯(cuò)碼。(6)編碼效率：

。顯然，若字長

n很大，則R。接近于1。588.7

循

環(huán)

碼8.7.1循環(huán)碼的概念循環(huán)碼：任一碼字向左/向右循環(huán)移動(dòng)任意位后仍是其中一個(gè)碼字的(n,k)線

性

碼

。循環(huán)碼也是一種分組碼，前k

位為信息碼元，后r

位為監(jiān)督碼元。它除了具有線性分組碼的封閉性之外，還有一個(gè)獨(dú)特的循環(huán)特性，即任一許用碼字經(jīng)過循環(huán)移位后(左移或右移)所

得到的碼字仍為一許用碼字。用代數(shù)編碼理論可把循環(huán)碼字中各碼元當(dāng)作一個(gè)多項(xiàng)式的系數(shù)，即把一個(gè)長為n

的碼字表示為(8.7-1)59循環(huán)碼d(x)稱為碼多項(xiàng)式，變量x稱為元素，其冪次對應(yīng)元素的位置，它的系數(shù)即為元數(shù)的取值(我們不關(guān)心x本身的取值),系數(shù)之間的加法和乘法仍服從模2規(guī)則。比如

一個(gè)(7,3)循環(huán)碼(見表8-8)中第7個(gè)碼字為(1100101),則該碼字可表示為C?(x)=1·x?+1·x?+0·x?+0·x3+1·x2+0·x+1=x?+x?+x2+1(8.7-2)表

8

-

8

一

種(

7

,

3

)

循

環(huán)

碼

的

全

部

碼

字碼字序號(hào)信息位C?C?C?監(jiān)督位C?C?C?C7碼字序號(hào)信息位C?C?C?監(jiān)督位C?C?C?C?1000000051001011200101116101110030101110711001014011100181110010可見，該碼的信息位與監(jiān)督位排列順序一致、分明，因此是一種系統(tǒng)碼。60表8-9(7,4)循環(huán)碼碼字碼字序號(hào)信息碼k?k?k?k?系統(tǒng)碼C?C?C?C?C?C?C?非系統(tǒng)碼C?C?C?C?C?C?C?10000000000000000002000100010110001011300100010110001011040011001110100111015010001001110101100601010101100010011170110011000101110108011101110100110001910001000101101100010100110011101010011111010101001110011101210111011000100010113110011000101110100141101110100111111111511101110100110001016111111111111101001對一組4位信息碼字，附加3位監(jiān)督碼元可編成兩種

(不只兩種)循環(huán)碼見表

8-9。循環(huán)碼61

循環(huán)碼可見，對于16個(gè)信息碼字，系統(tǒng)碼和非系統(tǒng)碼都具有16個(gè)相同的編碼碼字，但與信息碼的對應(yīng)(映射)關(guān)系不一樣。系統(tǒng)碼的前4位都是信息碼，而后3位都是監(jiān)督碼元，二者涇

渭分明。非系統(tǒng)碼從第5組開始就“亂”了，雖然每組信息碼仍有一個(gè)確定的編碼碼字與之

對應(yīng)，但已經(jīng)沒有了系統(tǒng)碼那種涇渭分明的結(jié)構(gòu)。因一般只研究系統(tǒng)碼，故可直接說循環(huán)碼

是一種系統(tǒng)碼。注意：對于一個(gè)(n,k)線性碼C,根據(jù)不同方法(生成矩陣)可以有包含系統(tǒng)碼和非系統(tǒng)碼在內(nèi)的多種編碼形式，但系統(tǒng)碼是唯一的，其余的都是非系統(tǒng)碼。62循環(huán)碼

8.7.2循環(huán)碼的生成如果在

(n,k)

循環(huán)碼的2k

個(gè)碼字中，取出一個(gè)前面(k-1)位皆為“0”的碼字，用次數(shù)為n-k的多項(xiàng)式g(x)

表示，則根據(jù)循環(huán)性可知，g(x)

、xg(x)

、

均是碼字，而且這

k個(gè)碼字是線性無關(guān)的。因此，可以用它們構(gòu)成此循環(huán)碼的生成矩陣G?！径ɡ?】在一個(gè)(n,k)循環(huán)碼中，存在唯一的n-k次碼多項(xiàng)式

g(x),它的形式為

(8.7-3)一旦確定了g(x),

全部(n,k)

循環(huán)碼就被確定了，因此，g(x)

也被稱為生成多項(xiàng)式。這樣，循環(huán)碼的生成矩陣就可以寫為63例如，在表8-8所給出的循環(huán)碼中，n=7,k=3,n-k=4?？梢?，唯一的一個(gè)四次多項(xiàng)式代表的碼字是第二個(gè)碼字0010111,其對應(yīng)的碼多項(xiàng)式就是生成多項(xiàng)式

g(x)=x?+x2+x+1。將此g(x)代入式(8.7-4),得到(8.7-5)循環(huán)碼

8.7.2循環(huán)碼的生成(8.7-4)64與式(8.6-4)相比較，它不符合G=[1kQ]形式，即該生成矩陣不是典型形式，但是可通過線性變換轉(zhuǎn)換為典型形式的生成矩陣。根據(jù)式(8.6-3),可以寫出該循環(huán)碼碼字為循

環(huán)

碼8.7.2循環(huán)碼的生成即有=(c?x2+C?x+C?)·g(x)

(8.7-7)(8.7-6)65

循環(huán)碼

8.7.2循環(huán)碼的生成【定理2】在循環(huán)碼中，所有的碼多項(xiàng)式都能被

g(x)整除。該定理表明下式成立c(x)=d(x)g(x)

(8.7-8)由式(8.7-8)可以看出：(1)任一循環(huán)碼多項(xiàng)式都是g(x)的倍式，即能被

g(x)整除。由此推論：任一次數(shù)不大于

k-1

的多項(xiàng)式與g(x)的乘積都是碼多項(xiàng)式。(2)若找到

g(x)

并已知

d(x),

就可生成全部碼字。顯然，鑒別一個(gè)接收碼字是否是原碼字，只要驗(yàn)證它是否能被

g(x)

整除即可。因此，定理2為循環(huán)碼的編碼和譯碼提供了依據(jù)和方法。66

循環(huán)碼

8.7.2循環(huán)碼的生成那么如何尋找生成多項(xiàng)式g(x)

呢?【定理3】循環(huán)碼的生成多項(xiàng)式

g(x)

是

x”+1

的因式。由定理3可知，從x”+1的因式分解中可以找出一個(gè)(n-k)次且常數(shù)項(xiàng)不為零的因式g(x)作為n位長循環(huán)碼的生成多項(xiàng)式。例如，(x?+1)可以分解為為了求(7,3)循環(huán)碼的生成多項(xiàng)式

g(x),要從上式中得到一個(gè)四次因式。不難看出，這樣的因式有兩個(gè)，即(8.7-9)67以上兩式都可作為生成多項(xiàng)式用。不過，選用的生成多項(xiàng)式不同，產(chǎn)生的循環(huán)碼字也不同。用式(8.7-11)作為生成多項(xiàng)式產(chǎn)生的碼

即為表8-9所列的循環(huán)碼。(x+1)(x3+x2+1)=x?+x2+x+1(x+1)(x3+x+1)=x?+x3+x2+1循環(huán)碼

8.7.2循環(huán)碼的生成(8.7-10)(8.7-11)68循環(huán)碼

8.7.3循環(huán)碼的編碼循環(huán)碼可以按下面的思路編碼：(1)根據(jù)給定的(n,k)

值選定生成多項(xiàng)式g(x);(2)根據(jù)定理2的式c(x)=d(x)g(x),

就可以對給定的信息碼d(x)

進(jìn)行編碼。但這樣生成的碼并非系統(tǒng)碼。根據(jù)系統(tǒng)碼的概念，系統(tǒng)碼碼多項(xiàng)式為

)

(8.7-12)69循環(huán)碼

8.7.3循環(huán)碼的編碼根據(jù)定理2,系統(tǒng)碼的碼多項(xiàng)式可以寫成r(x)=x”-kd(x)

(8.7-13)可見，構(gòu)造系統(tǒng)循環(huán)碼時(shí)，只需將信息碼多項(xiàng)式

d(x)

升

n-k次冪(乘以x"-k)變?yōu)閤”-?kd(x),

然

后

用

8(x)

除以x"-kd(x),

所得的余式

r(x)即為監(jiān)督碼元多項(xiàng)式。因此，系統(tǒng)循環(huán)碼的編碼過程就是用除法求余的過程。70根據(jù)上述原理，系統(tǒng)循環(huán)碼編碼步驟可歸納如下：第一步：用

x”-k

乘d(x)。第二步：用

g(x)

除x”-kd(

x),得到商Q(x)

和余式r(x),即第三步：將r(x)

加進(jìn)x”?kd(x)

即得編出的碼字c(x)=x”-kd(x)+r(x)(8.7-14)(8.7-15)循環(huán)碼

8.7.3循環(huán)碼的編碼71【例8-5】已知一種(7,3)循環(huán)碼的全部碼字為0000000

0101110

1001011

11001010010111

011100110111001110010試

求

：(1)該循環(huán)碼的生成多項(xiàng)式

g(x)

、

典型生成矩陣

G和典型監(jiān)督矩陣

H

;(2)若信息碼為110,按除法電路的工作過程編出相應(yīng)的碼字。循環(huán)碼

8.7.3循環(huán)碼的編碼72

循

環(huán)

碼

8.7.3循環(huán)碼的編碼【

解

】(

1

)已

知n=7,k=3,n-k=4。根據(jù)生成多項(xiàng)式

g(x)

對應(yīng)前面

k-1位皆為0的碼字——0010111,可得g(x)=x?+x2+x+1由式(8