北郵通信原理課件A-11差錯控制

北郵通信原理課件A-11差錯控制第一頁，共99頁。11.1概述數(shù)字信道上誤碼原因——信道傳輸特性不理想；信道加性噪聲的影響。解決辦法1——針對信道特性不理想合理設(shè)計基帶信號的碼型和波形，消除碼間串?dāng)_。采用時域、頻域均衡，修正信道特性。解決辦法2——針對信道加性噪聲的影響加大發(fā)射功率，提高信噪比選擇恰當(dāng)?shù)恼{(diào)制解調(diào)方式。解決辦法3——差錯控制編碼誤碼率仍不能滿足要求，則采用信道編碼（即差錯控制編碼），發(fā)現(xiàn)差錯，進(jìn)行修正，進(jìn)一步降低誤碼率。代價：增加冗余編碼，編碼效率下降第二頁，共99頁。概述一、差錯控制編碼二、信源編碼與信道編碼三、信道的分類四、差錯控制方法五、糾錯碼、檢錯碼舉例六、差錯控制編碼分類第三頁，共99頁。一、差錯控制編碼在信息碼元中按一定規(guī)則增加一些監(jiān)督碼元，并利用信息碼元與監(jiān)督碼元間的關(guān)系來發(fā)現(xiàn)、糾正誤碼的方法。監(jiān)督位越多，檢（糾）錯能力越強(qiáng)，但傳輸速率越高，要求帶寬越大。編成

n個比特的碼

字k個信息比

特編碼效率R

第四頁，共99頁。二、信源編碼與信道編碼信源編碼1、其碼型要適合于在信道中傳輸2、盡量減少信源的冗余度。盡可能用最少的信息比特來表示信源，提高通信系統(tǒng)的有效性。3、如哈夫曼編碼、話音PCM編碼、話音圖象壓縮編碼等。信道編碼1、通過對傳輸信息加入冗余信息的方式來達(dá)到差錯控制的目的，從而提高通信系統(tǒng)的可靠性。2、如奇偶校驗碼、循環(huán)校驗碼、卷積碼等。第五頁，共99頁。三、信道的分類根據(jù)加性干擾引起錯碼分布規(guī)律的不同，將信道分為三類隨機(jī)信道：錯碼隨機(jī)出現(xiàn)，錯碼間相互獨立，一般由信道的加性隨機(jī)噪聲引起。突發(fā)信道：誤碼集中出現(xiàn)，如信道上有脈沖干擾，信道衰落，光盤上的一條劃痕?；旌闲诺溃杭扔型话l(fā)錯誤又有隨機(jī)差錯。不同類型的信道，應(yīng)采用不同的差錯控制。第六頁，共99頁。四、差錯控制方法發(fā)送端差錯控制編碼：在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強(qiáng)的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號。例如奇偶校驗。接收端差錯控制譯碼：利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，從而拋棄錯誤信息，或進(jìn)而糾正錯誤。第七頁，共99頁。差錯控制方法（續(xù)）1.

前向糾錯方式（FEC）信源

編碼器

正向信道(糾錯)解碼器

收信者發(fā)送端將信息序列編碼成能夠糾正錯誤的碼，接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果有錯自動糾正特點：使用糾錯編碼，難度大，但實時性好，適于隨機(jī)信道；只需要正向信道，可用于單工和廣播通信中。例如：移動蜂窩電話系統(tǒng)。第八頁，共99頁。差錯控制方法(續(xù))2.檢錯重發(fā)方式（ARQ）信源解碼器(檢錯)收信者緩存指令產(chǎn)生器正錯確誤輸刪出除重發(fā)控制反向信道編碼器 緩存 正向信道正錯確誤刪重除發(fā)收端在接收到的信碼中發(fā)現(xiàn)錯碼時，通知發(fā)端重發(fā)，直到正確接收為止。特點：使用檢錯編碼，易實現(xiàn)，但實時性差，適于突發(fā)信道；還需要反向信道，只能用于點對點通信中；信道質(zhì)量差時，會陷入“重發(fā)陷阱”。第九頁，共99頁。確認(rèn)/重傳機(jī)制舉例接收碼組ACK ACKNAKACKACKNAKt1 2 3345534556ACK

t有錯碼組有錯碼組停止等待ARQ系統(tǒng)發(fā)送碼組1 2 3拉后ARQ系統(tǒng)接收數(shù)據(jù)有錯碼組有錯碼組10111212345675678991011ACK1NAK5NAK9ACK5發(fā)送數(shù)據(jù)12345675678910119101112重發(fā)碼組重發(fā)碼組第十頁，共99頁。差錯控制方法(續(xù))ARQ方式優(yōu)點：（1）只需少量的附加碼元即可獲得較低的輸出誤碼率。（2）適應(yīng)信道統(tǒng)計差錯特性強(qiáng)。（3）結(jié)構(gòu)較糾錯編解碼器簡單。ARQ方式缺點：（1）需要反向信道。（2）信道干擾大時，需要不斷重發(fā)，通信效率低。（3）不太適合實時性較強(qiáng)系統(tǒng)第十一頁，共99頁。差錯控制方法(續(xù))3.反饋檢驗方式信源正向信道收信者緩存緩存輸出指令比較器 反向信道收端把收到的數(shù)據(jù)序列全部送回發(fā)端，發(fā)端比較發(fā)出和送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)是否錯誤，如果有錯，發(fā)端重發(fā)數(shù)據(jù)序列，直到發(fā)端沒有發(fā)現(xiàn)錯誤。特點：不用差錯控制編碼，但效率低。第十二頁，共99頁。差錯控制方法(續(xù))4.混合方式（HEC）信源正向信道收信者反向信道ARQ發(fā) FEC

發(fā)FEC

收ARQ收特點：內(nèi)層使用FEC，糾正隨機(jī)差錯，減少重發(fā)次數(shù)；外層使用ARQ，重發(fā)無法糾正的突發(fā)差錯。需要糾檢結(jié)合的編碼第十三頁，共99頁。差錯控制方法(續(xù))FEC與ARQ的結(jié)合發(fā)端發(fā)出同時具有檢錯和糾錯能力的碼，收端收到后，檢查錯誤情況：如果錯誤在糾錯能力之內(nèi)，則自動糾正；若超出糾錯能力，但在檢錯能力之內(nèi)，則經(jīng)反向信道要求重發(fā)。在實時性和譯碼復(fù)雜性方面是FEC和ARQ的折衷。第十四頁，共99頁。五、糾錯碼、檢錯碼舉例例：信源信息為通過/不通過，信源編碼為通過（0）/不通過（1），無糾檢錯能力

信道編碼：通過（00）/不通過（11），有檢錯能力

信道編碼：通過（000）/不通過（111），有糾1位錯，或檢2位錯能力結(jié)論：增加碼的冗余度（監(jiān)督碼位數(shù)），可以增加糾錯編碼的糾錯能力。第十五頁，共99頁。六、差錯控制編碼分類按功能分：檢錯碼和糾錯碼按監(jiān)督碼元與信息碼元關(guān)系分：線性碼與非線性碼按信息碼元與監(jiān)督碼元之間的約束關(guān)系不同分：分組碼與卷積碼按信息碼元在編碼后是否保持原來的信號形式分：系統(tǒng)碼與非系統(tǒng)碼按糾正差錯的類型分：糾正隨機(jī)錯誤的碼與糾正突發(fā)錯誤的碼按碼元的取值分：二進(jìn)制碼與多進(jìn)制碼第十六頁，共99頁。11.2糾錯編碼的基本原理一、分組碼結(jié)構(gòu)二、糾（檢）錯能力三、編碼效率四、糾檢錯編碼的性能舉例第十七頁，共99頁。一、分組碼結(jié)構(gòu)(n,

k)分組碼（系統(tǒng)碼結(jié)構(gòu)）一個碼字

n位(n=k

+r) an-1 an-2ar-1… ar …a0信息碼元

k位 監(jiān)督碼元r位監(jiān)督碼元又稱監(jiān)督位，分組碼的監(jiān)督碼元只監(jiān)督本碼組中的信息碼元第十八頁，共99頁。分組碼結(jié)構(gòu)(續(xù))碼長：碼字中碼元的數(shù)目碼間距離（d）：兩個碼組，對應(yīng)位的碼元不同的個數(shù),又稱漢明距離。用于表示兩個碼組的差異。碼重：分組碼中，1的數(shù)目稱為碼組的重量兩個碼組的距離為其模2和碼組的碼重an-1 an-2… arar-1…a0第十九頁，共99頁。分組碼結(jié)構(gòu)(續(xù))最小距離（d0）：一種編碼中，各個碼組間距離的最小值。ni1j,kd0

Min

(aji

aki)aji表示第j個碼組的第i位碼元。漢明距離是度量一種編碼檢錯和糾錯能力的一種測度糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。an-1 an-2ar-1… ar …a0第二十頁，共99頁。分組碼結(jié)構(gòu)(續(xù))碼距的幾何意義（n=3）8個碼組間最小碼距d0=14個碼組000、011、101、110間最小碼距d0=22個碼組000、111間最小碼距d0=3(0,0,0)(1,0,1)(1,0,0)(0,0,1)(0,1,0)(1,1,1)(1,1,0)(0,1,1)第二十一頁，共99頁。舉例說明：傳送A（通過）、B（不通過）兩個消息編碼一：消息A----“0”；消息B----“1”最小碼距1若傳輸中產(chǎn)生錯碼（“0”錯成“1”或“1”錯成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯糾錯能力。分組碼結(jié)構(gòu)(續(xù))第二十二頁，共99頁。編碼二：消息A----“00”；消息B----“11”最小碼距2若傳輸中產(chǎn)生一位錯碼，則變成“01”或“10”，收端判決為有錯（因“01”“10”為禁用碼組），但無法確定錯碼位置，不能糾正，該編碼具有檢出一位錯碼的能力。這表明增加一位冗余碼元后碼具有檢出一位錯碼的能力分組碼結(jié)構(gòu)(續(xù))第二十三頁，共99頁。編碼三：消息A----“000”；消息B----“111”最小碼距3傳輸中產(chǎn)生一位或兩位錯碼，都將變成禁用碼組，收端判決傳輸有錯。該編碼具有檢出兩位錯碼的能力。在產(chǎn)生一位錯碼（錯1位概率遠(yuǎn)遠(yuǎn)大于錯2位、3位概率）情況下，收端可根據(jù)“大數(shù)”法則進(jìn)行正確判決，能夠糾正這一位錯碼。該編碼具有糾正一位錯碼的能力。例如收到110，認(rèn)為是111。這表明增加兩位冗余碼元后碼具有檢出兩位錯碼或糾正一位錯碼的能力。第二十四頁，共99頁。二、糾（檢）錯能力一種編碼的最小距離直接影響編碼的糾錯、檢錯能力。一種編碼，若其最小距離為d0能檢測e個錯誤時，e+1

d0能糾正t個錯誤時，2t+1

d0能糾正t

個錯誤，并同時檢測出e個錯誤時，e+t+

1

d0

(e>

t

)第二十五頁，共99頁。糾（檢）錯能力（續(xù)）為了檢測e個錯誤，要求最小碼距dmin

e

10 1 2 3ABedminA、B都為許用碼；A發(fā)生e個錯；B不能在半徑為e的環(huán)內(nèi)，否則收到B無法判斷是否為錯碼；第二十六頁，共99頁。糾（檢）錯能力（續(xù)）為了糾正t個錯誤，要求最小碼距

d

min

2

t

10 1 2 34 5ABtd

mintA,B都為許用碼A,B都發(fā)生t個錯A,B的糾錯范圍不相交第二十七頁，共99頁。糾（檢）錯能力（續(xù)）tte1AB為了糾正t個錯誤，同時檢測e個錯誤，要求最小碼距d

min

e

t

1

(

e

t

)第二十八頁，共99頁。例

d0=7檢錯方式 e=?糾錯方式 t=?糾檢結(jié)合方式e=?,

t=?第二十九頁，共99頁。三、編碼效率kn k

rR

k

第三十頁，共99頁。四、糾檢錯編碼的性能舉例假設(shè)在隨機(jī)信道中發(fā)送“0‖/‖1‖時的錯誤概率都等于p，且p<<1，則在碼長為n的碼組中恰好發(fā)生r個錯碼的概率為：p

rn!r!(n

r)!p (r

)

C

r

p

r

(1

p)n

r n n例如，當(dāng)碼長n=7時，p=10-3則有2

5p7(2)

21p

2.1

10

3p7(1)

7p7

10 ;3

8p7(3)

35

p 3.5

10

結(jié)論：隨機(jī)信道中，糾正或檢測碼組中1-2個錯誤，可使誤碼率下降幾個數(shù)量級。代價是帶寬加大第三十一頁，共99頁。11.3常用的簡單編碼奇偶校驗碼——監(jiān)督位只有一位奇校驗——編碼后該碼組中1的個數(shù)為奇數(shù)偶校驗——編碼后該碼組中1的個數(shù)為偶數(shù)只能發(fā)現(xiàn)奇數(shù)個錯誤，不能檢測偶數(shù)個錯誤。最小碼距為2用于隨機(jī)信道二維奇偶校驗碼（方陣碼）可以發(fā)現(xiàn)某一行或某一列上的所有奇數(shù)個錯誤可以發(fā)現(xiàn)長度不大于行數(shù)（或列數(shù)）的突發(fā)錯誤。用于突發(fā)信道第三十二頁，共99頁。常用的簡單編碼（續(xù)）恒比碼每個碼組中均含有相同數(shù)目的“1”碼和“0”碼例：用5個比特碼字表示10個阿拉伯?dāng)?shù)字。從32個可能碼字中挑出10個“1‖的個數(shù)為3個的碼字編碼能檢測出所有1個和奇數(shù)個錯誤，并能部分檢測出偶數(shù)個錯誤（成對交換錯則檢測不出）用在電傳、電報阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼101011610101211001711100310110801110411010910011500111001101第三十三頁，共99頁。常用的簡單編碼（續(xù)）正反碼編碼規(guī)則：信息位有奇數(shù)個1，監(jiān)督位=信息位信息位有偶數(shù)個1，監(jiān)督位=信息位舉例信息位為11001，碼組為1100111001信息位為10001，碼組為1000101110第三十四頁，共99頁。11.4線性分組碼一、基本概念二、線性碼的校驗三、漢明碼四、線性分組碼一般原理第三十五頁，共99頁。一、幾個基本概念代數(shù)碼：建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱為代數(shù)碼。例如奇偶校驗碼。分組碼：先將信息碼分組，然后給每組信碼附加若干監(jiān)督碼的編碼稱為分組碼，用(n,k)表示，k是信息碼的位數(shù)，n是編碼組總位數(shù)，又稱為碼長，r=n-k為監(jiān)督位數(shù)。線性碼：線性碼中信息位和監(jiān)督位是按一組線性方程構(gòu)成的。線性碼是一種代數(shù)碼。奇偶監(jiān)督碼是最簡單的線性碼。線性分組碼：信息碼分組后，附加的監(jiān)督碼和信息碼由一些線性代數(shù)方程聯(lián)系著的編碼稱為線性分組碼。第三十六頁，共99頁。二、線性碼的校驗線性分組碼：監(jiān)督碼與信息碼間用線性方程聯(lián)系運算規(guī)則——加法為模2加，乘法為二進(jìn)制乘法；碼組間運算是各個相應(yīng)比特位上的運算

1+1=0、1+0=1、0+1=1、0+0=0

1x1=1,1x0=0, 0x0=0,0x1=0第三十七頁，共99頁。線性碼的校驗（續(xù)）碼的監(jiān)督（校驗）方法例：對于偶校驗碼的監(jiān)督關(guān)系：

...

a

0S

an1

an

2如果S=1，則認(rèn)為傳輸時出錯；S=0，則認(rèn)為無誤傳輸。上式稱為監(jiān)督關(guān)系，S稱為校驗子。問題：為了能糾一位錯，k位信息至少需要多少位的監(jiān)督信息，如何設(shè)計？第三十八頁，共99頁。線性碼的校驗（續(xù)）r個監(jiān)督位對應(yīng)r個監(jiān)督關(guān)系式可以有r個校驗子能指示一位錯碼的

2r-1個可能位置。若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k。用r個監(jiān)督位表示一位錯碼的n種可能位置條件是：如果取k=4，則可以確定r>=3，n=k+r=7。因此，可以用3個校驗子來確定傳輸?shù)?個位置是否出錯。2r

1

n或

2r

k

r

1第三十九頁，共99頁。三、漢明碼能夠糾正一位錯碼且編碼效率較高的線性分組碼條件：對于(n,k)碼，要求2r–1n。

例如:(7,4),(15,11),(31,26)碼第四十頁，共99頁。漢明碼(續(xù))

例：(7,4)

漢明碼1.設(shè)計校驗子的錯誤圖樣校驗子S1S2S3000 001 010 011100 101 110 111錯碼位 無置 錯a0 a1 a3a2a45a a6(a6a5a4a3a2a1a0

)0346313562S

a

a

a

a 0S1

a6

a5

a4

a2

0于是有S

a

a

a

a

0,第四十一頁，共99頁。漢明碼(續(xù))2.監(jiān)督關(guān)系式03462 6 5 3 1

3

a

a

a

a

0S

a

a

a

a 0,SS1

a6

a5

a4

a2

034603561

a

a

aaa

a

a

a3.編碼規(guī)則a2

a6

a5

a4第四十二頁，共99頁。漢明碼(續(xù))（7，4）碼的所有碼組。a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111114 3603561

a

a

aaa

a

a

aa2

a6

a5

a4第四十三頁，共99頁。漢明碼(續(xù))4.解碼和糾錯根據(jù)接受碼組計算校驗子，按錯誤圖樣糾錯后，取前k位信息位。最小距離d0

=3，可糾1位錯，檢2位錯，不能同時糾檢錯。編碼效率k/n

(2r

1

r)/(2r1)

1

r/(2r1)

1

r/n當(dāng)

n

很大

時，編碼速率接近1。第四十四頁，共99頁。四、線性分組碼的一般原理1.

監(jiān)督關(guān)系式監(jiān)督矩陣線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼，由校驗關(guān)系式，可得一組線性方程1

a6

1

a51

a4

0

a3

1

a2

0

a1

0

a0

01

a6

1

a5

0

a4

1

a30

a2

1

a1

0

a0 01

a6

0

a5

1

a4

1

a3

0

a2

0

a1

1

a0

03 6 4 3 02 6 5 3 1

a

a

a

a

0S

a

a

a

a

0,SS1

a6

a5

a4

a20第四十五頁，共99頁。寫成矩陣的形式：

00111 1 1 0

1

01 0 1 0 10 1 1 0 03

5

a1

a

1a2

0a

00a4

a a6

HAT

0T 或 AHT

0即PIrH（監(jiān)督矩陣） ·

0

AT=OTH中每行1的位置表示相應(yīng)碼元之間的監(jiān)督關(guān)系。只要監(jiān)督矩陣確定，信息位與監(jiān)督位的關(guān)系就確定。線性分組碼的設(shè)計就是設(shè)計監(jiān)督矩陣(即錯誤圖樣)。第四十六頁，共99頁。線性分組碼的一般原理（續(xù)）監(jiān)督矩陣H的特點r×n階矩陣監(jiān)督矩陣H確定了編碼時監(jiān)督碼元與信息碼元的關(guān)系把具有[P·Ir]形式的H矩陣稱為典型形式的監(jiān)督矩陣，其中P為r

×k階矩陣,

Ir為r

×r階單位方陣H矩陣的各行應(yīng)線性無關(guān)。矩陣若能寫成典型形式，則其各行一定線性無關(guān)第四十七頁，共99頁。線性分組碼的一般原理（續(xù)）2.生成矩陣——將監(jiān)督位與信息位的關(guān)系寫成另一種矩陣形式

3

4

5

0

1

2

1111 1 11 00 1

aa

a

0 a6

a

a

1a111001

1 11 101a2

a1a0

a6

a5a4a3或者2 6 5 4a1

a6

a5

a3a0

a6

a4

a3a

a

a

a第四十八頁，共99頁。101001100011010011[a6

a5a4a3a2

a1a0

]

a6a5a4a3

G稱為碼的生成矩陣。由生成矩陣同樣可以確定編碼的碼組。線性分組碼的一般原理（續(xù)）0 1 0 1 00 0 1 0 1IkQA = M·G（生成矩陣）第四十九頁，共99頁。線性分組碼的一般原理（續(xù)）生成矩陣G特點k ×n階矩陣編碼方法完全由生成矩陣G確定把具有[Ik·Q]形式的G矩陣稱為典型形式的生成矩陣，其中，Ik為k×k階單位方陣，Q為k×r階矩陣由典型生成矩陣產(chǎn)生的分組碼一定是系統(tǒng)碼G矩陣的各行應(yīng)線性無關(guān)，各行本身就是一個碼組,

任一碼組都是G的各行的線性組合第五十頁，共99頁。生成矩陣G與監(jiān)督矩陣H的關(guān)系若H=[PIr]，稱為典型監(jiān)督矩陣。若G=[IkQ]，稱為典型生成矩陣。由典型生成矩陣得到的碼稱為系統(tǒng)碼。則Q=PT計算系統(tǒng)碼的方法？線性分組碼的一般原理（續(xù)）第五十一頁，共99頁。3.

錯碼矩陣（錯誤圖樣）假設(shè)發(fā)送碼組為A，接收碼組為B，則發(fā)送碼組和接收碼組之差為B-A=E它就是傳輸中產(chǎn)生的錯碼行矩陣，E=[en-1en-2…e0]其中錯碼矩陣E稱為錯誤圖樣。接收時B=A+Eie

=i iO 當(dāng)b=a1 當(dāng)b≠ai i例如發(fā)送碼組A=00110101錯碼矩陣E=00100000則 接收碼組B=00010101線性分組碼的一般原理（續(xù)）第五十二頁，共99頁。4.

接收判決接收到B后，計算校正子S=B·HT。T T若B=A（無誤碼），則S=B·H =A·H =O；若B≠A（有誤碼），則S=B·HT=(A+E)·HT=E·HT

，S?=OS為校正子，與錯誤圖樣E有線性關(guān)系。若S與E一一對應(yīng)，則由S可以確定錯誤位置。如何根據(jù)H計算錯誤圖樣，實現(xiàn)糾錯？根據(jù)S=E·HT

，可以用E去算S—E對應(yīng)表線性分組碼的一般原理（續(xù)）第五十三頁，共99頁。性質(zhì)：封閉性：任意兩許用碼組之和（逐位模2和）仍為一許用碼組。證明：設(shè)A，B為任意兩個許用碼組，H為監(jiān)督矩陣則：AHT=0，BHT=0所以 （A+B）HT=0所以 （A+B）也是許用碼組碼的最小距離等于非零碼的最小碼重。證明：設(shè)A，B為任意兩個許用碼組由碼距定義，A，B的距離=（A+B）的重量由封閉性，

（A+B）也是許用碼組所以，最小碼距=最小碼重（非0碼）線性分組碼的一般原理（續(xù)）第五十四頁，共99頁。舉例例1：線性分組碼(7,3),已知典型生成矩陣G:100111001001110011101C6C5C4C3C2C1C0碼重0000000000111014010011140111010410011104101001141101001411101004列出編碼表方法1：3位信息位，000-111，用生成矩陣算檢驗位方法2：生成矩陣行運算最小碼距=4，糾檢錯能力？第五十五頁，共99頁。

0 1100 0當(dāng)信息位為0001時，（1）試求其后的監(jiān)督位。（2）監(jiān)督矩陣H（3）最小碼距和糾、檢錯能力00011100110101000101舉例例2：設(shè)（7,4）線性碼的生成矩陣G為：1 1第五十六頁，共99頁。a4 a3

G解：（1）

A

a6 a51010A

000

1

[0001011]001100011100110101000101第五十七頁，共99頁。（2）監(jiān)督矩陣HG=[Ik·Q]，H=[P·Ir]其中P=QT，可得監(jiān)督矩陣H為：111110100101010011001101根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系：0001000111001101010001011第五十八頁，共99頁。e=d0

-1=2t=d0-1

12e

t

1

d0 e

t該碼可以檢2位錯該碼可以糾1位錯該碼不能同時用于檢錯與糾錯（3）d0 3第五十九頁，共99頁。11.5循環(huán)碼滿足封閉循環(huán)特性的線性分組碼若(an-1,an-2…,a1,a0)是一(n,k)循環(huán)碼的碼組，則(an-2,an-3,…,a1,a0,an-1)…(a0,an-1,an-2,an-3,……,a2

,a1)也都是該循環(huán)碼的碼組。例：(7,3)循環(huán)碼碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010第六十頁，共99頁。循環(huán)碼一、循環(huán)碼的表示方法二、生成矩陣和生成多項式第六十一頁，共99頁。一、循環(huán)碼的表示方法碼多項式長為n的碼組

(an-1an-2…a2a1a0)可由碼多項式T(x)=an-1xn-1+an-2xn-2+…+a2x2+a1x+a0表示。x表示碼元的位置，系數(shù)ai對應(yīng)碼元的值。碼多項式的按模運算：

F(x)≡R(x) （模N(x)）系數(shù)間運算服從模2規(guī)則，以“+‖代替“-‖。Nx

Nx

Fx

Qx

Rx第六十二頁，共99頁。碼多項式按模運算舉例碼多項式系數(shù)按模2運算，即系數(shù)只取0和1。例如，x3被(x3+1)除，得到余項1。所以有同理

1 （模(x3

1)）x3x4

x21

x2

x

1x x3

+

1 x4x4+x2 +

1+

xx2+x

+1（模(x3

1)）在模2運算中，用加法代替減法，故余項不是x2

–x+1，而是x2+x+

1。第六十三頁，共99頁。循環(huán)碼的表示方法(續(xù))循環(huán)碼特點碼字左移一位，相當(dāng)于乘x(以xn+1為模

)T(x)是一個許用碼組，若xiT(x)≡T’(x)(模xn+1)，則T’(x)

也是許用碼組，且為T(x)碼組向左循環(huán)移位i次的結(jié)果。結(jié)論：N位循環(huán)碼的碼組必是按照模xn+1運算的一個余式第六十四頁，共99頁。二、生成矩陣和生成多項式生成矩陣的每一行都是一個碼組，且是K行n列矩陣，因此，若能找到K個線性不相關(guān)的已知碼組，就能構(gòu)成生成矩陣G。用g(x)表示（n，k）循環(huán)碼中前K-1位都為“0‖的碼組，則g(x)，

xg(x),x2

g(x),xk-1

g(x)都是碼組，并且這K個碼組是線性無關(guān)的，他們就可以用來構(gòu)成此循環(huán)碼的生成矩陣G。定義這個n-k次多項式g(x)為碼的生成多項式第六十五頁，共99頁。生成矩陣和生成多項式(續(xù))g(x)滿足：4.生成矩陣G為：5.G是非典型陣g(x)G(x)

xk

2g(x)1．g(x)|T(x)2．g(x)=xr+…+1，最高次冪r=n–k3．g(x)是

xn+1的因式

xk

1

g(x)第六十六頁，共99頁。解：對（7,3）循環(huán)碼，n=7，k=3, r=4第一步：對x7+1進(jìn)行因式分解得：.....(1)x7+1=(x+1)(x3+x2+1)(x3+x+1)第二步：構(gòu)造r次生成多項式g(x)。要從式（1）中找到r=n-k=4次的因子,這樣的因子有兩個：(x+1)(x3+x2+1)=x4+x2+x+1……………(a)(x+1)(x3+x+1)=x4+x3+x2+1……………(b)第三步：若按(a)構(gòu)成生成多項式:生成多項式為：g(x)=x4+x2+x+1[例]求（7，3）循環(huán)碼的生成多項式和生成矩陣。第六十七頁，共99頁。將第1行與第3行模2加作為第1行，則有

101110001011100010111G

x4

x2

x

1 x6

x4

x3

x2

g(x) x2

g(x)G(

X)

xg(x)

x5

x3

x2

xTh成矩陣為：為典型Th成矩陣101G

100101010111001011第六十八頁，共99頁。若按(b)構(gòu)成Th成多項式:

111010 0011101 0001110 1G

x4

x3

x21

g(x) Th成多項式為：g(x)=

x4+x3+x2+1Th成矩陣為：x2

g(x)

x6

x5

x4

x2

G(X

)

xg

(x)

x5

x4

x3

x

100111001001110011101G

進(jìn)行線性變換，得典型Th成矩陣為：第六十九頁，共99頁。[例]已知（7，4）循環(huán)碼的全部碼組為：試寫出該循環(huán)碼的生成多項式g(x)和生成矩陣G，并將G化成典型矩陣。第七十頁，共99頁。解：n=7，k=4，n-k=33上述碼組中的(n-k)=3次碼多項式為第2組，它所對應(yīng)的碼多項式g(x)即為生成多項式：g(x)=x3+x+1。生成矩陣為：x3g(x)

x6

x4

x3

x2g(x)

x5

x3

x2

G(x)

x1g(x)

x4

x2

x

g(x)x

x

1

101100010001010101100

0

100111001011000101100 001011000101 1第七十一頁，共99頁。三、循環(huán)碼的編碼根據(jù)(n,k)值從xn+1的因式中選定一個r次多項式做為生成多項式g(x)。設(shè)信息碼的多項式為m(x),最高次冪k–1,做xn-

km(x)。3. 運算,Q(x)為商式，r(x)為余式。4. 則T(x)=xn-km(x)+

r(x)=

Q(x)g(x)為循環(huán)碼多項式，即以余式r(x)為監(jiān)督位?？捎贸ㄆ鳎◣Х答伒木€性移位寄存器）來實現(xiàn)。Q(x)g(x)

g(x)r(x)xnkm(x)第七十二頁，共99頁。x2

1x 1)(x2

x4

x2

x

1 x4

x2

x

1x6

x5g(x)xnkm(x)

即余式r(x)=x2+1于是，對應(yīng)碼組T(x)=xn-km(x)+r(x）=x6+x5+

x2+1編碼為1100101[例]設(shè)（7，3）循環(huán)碼的生成多項式為g(x)=x4+x2+x+1，待編碼信息位為110，求對應(yīng)循環(huán)碼碼組。解：m(x)=x2+x，xn-k

m(x)=x4(x2+x)=x6+x5第七十三頁，共99頁。四、循環(huán)碼的解碼和糾檢錯1.解碼無誤碼時，前k位為信息位。第七十四頁，共99頁。循環(huán)碼的解碼和糾檢錯(續(xù))檢錯判決：S(x)=0，無差錯；S(x)

0，有差錯。2.

檢錯設(shè)：接收碼多項式為R(x)

T(x)

E(x)

Q(x)g(x)

E(x)余式余式

g(x)

g(x)記：校驗子S(x)

E(x)

R(x)

第七十五頁，共99頁。循環(huán)碼的解碼和糾檢錯(續(xù))3.糾錯當(dāng)監(jiān)督位足夠長時，循環(huán)碼也可糾錯。例：g(x)=x3+x2+1的(7,4)循環(huán)碼可糾正一位錯碼，錯誤圖樣為：校驗子S(x) x2+x x+1 x2+x+1 x2+1x2x 1 0錯碼位置E(x)X6 x5 x4 x3 x2 x11 無錯誤圖樣的計算方法：給定E(x)，S(x)=E(x)

/g(x) 的余式第七十六頁，共99頁。11.6卷積碼一、卷積碼原理二、卷積碼編碼器三、卷積碼的圖形描述四、

卷積碼的譯碼——維特比譯碼第七十七頁，共99頁。一、卷積碼原理<-----------------------N*k---------------------->碼組1 碼組2 碼組N12…k12..k1..12..k輸入m輸入移位寄存器

加法器輸出移位寄存器輸出Y123…n卷積碼編碼器結(jié)構(gòu)（n，k，N）卷積碼第七十八頁，共99頁。卷積碼原理(續(xù))編碼約束度：N稱為編碼約束度編碼約束長度：

nN稱為編碼約束長度。編碼效率：Rc=

k/n第七十九頁，共99頁。二、卷積碼編碼器

以（3，1，3）卷積碼為例初態(tài)000輸入mj…mj…m2m1 mjmj-1mj-2輸出yj…y1jy2jy3j… 123M1M2M3第八十頁，共99頁。卷積碼編碼器(續(xù))輸出與輸入的關(guān)系是：21

111

1

y31

m1

y

m

y

m1232222212y

m

m

m

yy

mj

2j

1j3jj1j

m

m

m

y

mj

mj

2

y2j

m

y(j

3)輸入mj

輸出yjj…m…m

m2 11j2j3j…y y y …321M1mjM2mj-1M3mj-2第八十一頁，共99頁。三、卷積碼的圖形描述1、樹狀圖——最直接的表示法由樹狀圖可以看出，該編碼存在4種狀態(tài)：狀態(tài)M2M3a b c d00 10 01 11第八十二頁，共99頁。000111001110011000111001110011100010101y y y142434100111011001101010y13y23y33000000001110y y y1222

32信息位1101ba起點信息位111y11y21y31000abcdabcdabcdabcd上半部下半部10a狀態(tài)M2M30

010c 0

1d 11abcdabcdac100b010110d101↑0↓1↓1↑0↑0↓1

111 輸入mj

輸出yjmjj…m

…m2m1…y y y1j2j3j…321M1 M2 M3mj-1 mj-2第八十三頁，共99頁。卷積碼的圖形描述(續(xù))2、狀態(tài)圖——最簡單的表示法取出已達(dá)到穩(wěn)定狀態(tài)的一節(jié)樹圖，得到狀態(tài)圖a(00)b(10)c(01)d(11)當(dāng)前狀態(tài) 下一狀態(tài)000001011010101100110111acdb000001010101110100111011abcd―0‖;―1‖輸入mj

輸出yjmjj…m

…m2m1…y1jy2jy3j…321M1

M2 M3mj-1 mj-2第八十四頁，共99頁。卷積碼的圖形描述(續(xù))3、網(wǎng)格圖（格狀圖、籬笆圖）

——用于解碼把狀態(tài)圖在時間上展開，得到網(wǎng)格圖。輸入信息位為1101…時輸出編碼序列是：111110010100

…acdb000001010101110100111011110110110010010101101001abcd000111000111000111011100001000111011100001第八十五頁，共99頁。卷積碼的圖形描述(續(xù))N*k個0輸入信息位為1101（000）時輸出編碼序列111110010100(001011

000)acd4、為保證輸入的信息位完全通過移存器，需補b000010101100 001111 110011110110110010010101101110010101001abcdabcd000111000111000111011100001000111011100001000111011100001第八十六頁，共99頁。四、維特比譯碼門限譯碼大數(shù)邏輯譯碼維特比譯碼概率譯碼序列譯碼卷積碼的譯碼第八十七頁，共99頁。維特比譯碼(續(xù))1、最大似然算法譯碼把已接收序列與所有可能的發(fā)送序列比較，選擇碼距最小的作為發(fā)送序列。第八十八頁，共99頁。維特比譯碼(續(xù))2、維特比譯碼（VB算法譯碼）思路：不是一次將全部碼組收齊后一起比較，而是收一段，比較一段，選擇一段有最大似然可能的碼段，從而達(dá)到整個碼序列是一個有最大似然值的序列。第八十九頁，共99頁。維特比譯碼(續(xù))(n,k,N)碼，共有2k(N-1)種狀態(tài)，每個狀態(tài)節(jié)點有2k條入支路，2k條出支路。將匯集在第N級每節(jié)點上的兩條路徑表示的序列與接收序列比較，保留碼距小的，丟棄碼距大的，保證在第N級節(jié)點上只留下2N-1條幸存路徑。在以后的各級上，采用同樣的方法比較—選擇，保留2N-1條幸存路徑。（當(dāng)兩條路徑的碼距相同時，任意選擇一條）當(dāng)發(fā)送序列接收完畢后，在網(wǎng)格圖的終結(jié)處加上N個已知信息（一般用0）作為結(jié)束信息，從而確定最終的幸存路徑。第九十頁，共99頁。維特比譯碼(續(xù))

例：（3，1，3）卷積碼發(fā)送信息位為1101為使移存器中的信息位全部移出，在信息位后面加入了3個“0‖