第七講糾錯編碼

第七講

差錯控制編碼現(xiàn)代通信理論信源信源編碼信道編碼調(diào)制發(fā)轉(zhuǎn)換器媒質(zhì)收轉(zhuǎn)換器解調(diào)信道譯碼信源譯碼信宿目的：提高信息傳輸?shù)牡目煽啃院陀行?，始終是通信工作所追求的目標(biāo)，糾錯編碼是提高信息傳輸可靠性的一種重要手段。第一部分差錯控制編碼的概念差錯控制編碼屬于信道編碼提高通信系統(tǒng)的可靠性，降低誤碼率，減少發(fā)射功率，提高接收機(jī)的靈敏度等等。信道容量：信息通過信道傳輸，單位時間內(nèi)信道上所能傳輸?shù)淖畲笮畔⒘浚葱畔⑺俾仕俾剩┓Q為信道容量。對于加性高斯白噪聲信道有：C=Blog2(1+S/N)；香農(nóng)信道編碼理論：通過對信息進(jìn)行適當(dāng)?shù)木幋a，一個含有噪聲的信道所引起的差錯可以減小到任一期望的水平，而又不會犧牲信息的發(fā)射速率；對于有噪聲的信道，存在可以實現(xiàn)可靠通信的信道編碼。它能在發(fā)送速率

R<C時達(dá)到所期望的任意小的水平，若R>C，則無差錯傳輸是不可能的。隨機(jī)性差錯：由高斯噪聲引起，差錯是隨機(jī)的且相互間是獨立出現(xiàn)的。突發(fā)性差錯：由脈沖性干擾引起，在短暫的時間內(nèi)出現(xiàn)大量的差錯，而這些短暫時間之后卻又存在較長的無誤碼區(qū)間?；旌闲圆铄e：即存在隨機(jī)差錯又有突發(fā)性差錯。

在信息序列之后附加一些監(jiān)督碼元，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，接收端按照既定的規(guī)則檢驗出關(guān)聯(lián)關(guān)系，如這種規(guī)則受到破壞，將會發(fā)現(xiàn)錯誤，乃至糾正錯誤。二、差錯控制的基本方法一、差錯類型隨機(jī)性差錯和突發(fā)性差錯通常采用不同的糾錯編碼方法。檢錯與糾錯能力與最小碼距d0有密切關(guān)系：許用碼組禁用碼組00011110

許用碼組禁用碼組000001010100111101110011可以用來檢測出一位錯誤可糾正一位或檢測兩位錯誤AB0123d0AB01234

5d02.

為了糾正t個錯誤：d0≥2t＋11.

為了檢測e個錯誤：d0≥e＋1；3.

為了同時檢測e個錯誤，糾正t個錯誤：d0≥e＋t＋1ABd0ettA

0B

1

無檢錯與糾錯能力三、差錯控制方式2.前向糾錯（FEC）

可以糾正錯誤

發(fā)

收3.混和糾錯（HEC）

可以發(fā)現(xiàn)和糾正錯誤

發(fā)

收

應(yīng)答信號

比較：譯碼復(fù)雜性、實時性和占用傳輸鏈路(單向還是雙向)1.檢錯重發(fā)（ARQ）（包括停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)）

能夠發(fā)現(xiàn)錯誤

發(fā)收

應(yīng)答信號ARQ：自動重復(fù)請求發(fā)送1233123ACKNAKACK等待時間發(fā)送端接收端123456234567891011123456234567891011從碼組2開始重發(fā)NAKACK發(fā)現(xiàn)錯誤停發(fā)等候重發(fā)返回重發(fā)1234562789101121234562789101112重發(fā)碼組2NAKACK發(fā)現(xiàn)錯誤選擇重發(fā)

四、糾錯碼分類1.

分組碼與卷積碼：分組碼：將信息碼分組，為每組信息碼后面附加若干位監(jiān)督碼元，且監(jiān)督碼元僅監(jiān)督本碼組中的信息位。

K個信息位r個監(jiān)督位碼長n＝k＋r卷積碼：也是先將信息序列分組，后面附加監(jiān)督位，但是監(jiān)督位不但與本碼組的信息位有關(guān)，還與前面碼組的信息位有關(guān)，或者說監(jiān)督位不僅監(jiān)督本碼組的信息位還監(jiān)督其它碼組的信息位。2.

系統(tǒng)碼與非系統(tǒng)碼系統(tǒng)碼：

就是信息位在前，監(jiān)督位在后的碼字。非系統(tǒng)碼:

信息位與監(jiān)督位之間無特定的位置關(guān)系。五、常用的簡單糾錯編碼1.

奇偶校驗設(shè)信息位每組長度為n-1位，增加一位監(jiān)督位，n位編碼構(gòu)成以下約束關(guān)系：接收端計算：奇偶校驗可以用來檢測單個或奇數(shù)個錯誤2.縱向奇偶校驗（LRC）－用于檢測突發(fā)錯誤1110011111011101001110011010100111100111110111010011100110101001縱向排列原始數(shù)據(jù)1110011111011101001110011010100110101010突發(fā)錯誤接收方檢驗是否滿足LRC。LRC

10101010監(jiān)督碼元

信息碼元

0101101100010101001000110000111100011100001111111100010011111110110000監(jiān)督碼元00111000010監(jiān)督碼元

10010113.水平垂直奇偶校驗它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個錯誤以及長度不大于列數(shù)（或行數(shù)）的突發(fā)錯誤六、差錯控制編碼的效用

假設(shè)在隨機(jī)信道中發(fā)“0”和發(fā)“1”的概率相同，可以證明，在碼長為n的碼組中恰好發(fā)生r個錯誤的概率為：可見采用差錯控制編碼，即使僅能糾正（或檢測）1～2個錯誤，就能使誤碼率下降幾個數(shù)量級。當(dāng)碼長n＝7，誤碼率P＝10

-3時:則有：第二部分線性分組碼若監(jiān)督位增加到2位，就可增加一個監(jiān)督方程式，接收時就可計算2個校正子S1和S2，共有四種可能，除了00表示無錯以外，其余3種就可以表示一位錯碼的的具體位置了。這里

S稱為校正子，若S＝0，表示無錯，S＝1表示有錯誤，由于只用了一位監(jiān)督位

a0，因此只能表示有錯與無錯。奇偶校驗碼就是一種效率很高的線性分組碼分組碼中，信息位和監(jiān)督位之間由線性方程組聯(lián)系的編碼稱作線性分組碼，或者說監(jiān)督碼元是由信息碼元的線性組合而產(chǎn)生。一般說來對于，對于r個監(jiān)督位，可以計算r個校正子，它可以指出種錯誤圖樣，即個錯誤位置，因此對于(n，k)碼。要想指出一位錯碼的所有可能位置，則要求：設(shè)分組碼中（n，k）中k＝4，為了糾正一位錯誤，則，取r＝3，則n＝7，用表示，用表示由3個監(jiān)督方程式計算得到的校正子，并假設(shè)這3個校正子與誤碼對應(yīng)的關(guān)系如下表所示：若糾正

t個錯誤一、線性分組碼的構(gòu)成：校正子表

S1S2S3誤碼位置

S1S2S3

誤碼位置

001a0

101

a4

010

a1

110a5

100

a2

111a6

011

a3

000

無錯因此接收端計算下面3個校驗關(guān)系，可確定誤碼的位置發(fā)送端構(gòu)成偶校驗關(guān)系監(jiān)督位由信息位的線性組合得到：許用碼組信息位

監(jiān)督位

信息位監(jiān)督位

0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111二、線性分組碼的生成和監(jiān)督矩陣1.監(jiān)督矩陣即：其中：

其中P為r×k階矩陣，Ir為r×r階單位陣，具有H0形式稱為典型形式的監(jiān)督矩陣；線性代數(shù)理論告訴我們，典型形式的監(jiān)督矩陣各行一定是線性無關(guān)的，非典型形式的監(jiān)督矩陣可以通過矩陣的初等變換轉(zhuǎn)化為典型形式的監(jiān)督矩陣。2.生成矩陣對于所有的編碼與信息位的關(guān)系：則其中Q為K

×

r

階矩陣，I

k為k階單位陣具有典型化形式

G0=[Ik，Q]

的生成矩陣稱為典型生成矩陣它與典型化形式H0=[P，Ir]的關(guān)系為：

結(jié)論：線性分組碼的特性：1)

任意兩個許用碼組之和仍為許用碼組－封閉性2)碼的最小距離等于非零碼的最小重量。1)由典型化的生成矩陣產(chǎn)生的是系統(tǒng)碼組；2)典型化的生成矩陣的各行也必定是線性無關(guān)的，每一行都是一個許用碼組，k行許用碼組經(jīng)過運算可以生成2k

個不同的碼組；3)非典型形式的生成矩陣經(jīng)過運算也一定可化為典型形式。三、線性分組碼的伴隨式譯碼發(fā)送碼組為A，接收碼組為R設(shè)E為傳輸錯誤圖樣，則：R－A＝E計算校正子或者校正子S只與E有關(guān)，若接收碼字R中第i位有錯，那么導(dǎo)出的伴隨式恰好是矩陣H的第i列相同的位置。利用伴隨式不僅可以判決接收碼字中是否有錯，而且可以指出差錯的位置。對于前面的例子，一位錯誤圖樣為（1000000)，（0100000)，(0010000),(0001000)，(0000100)，(0000001)，(0000001)……….第三部分循環(huán)碼一、特點：循環(huán)碼是一種具有循環(huán)移位特性的線性分組碼，這類碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性質(zhì)帶來的其它性能和特征，并可以用不太長的碼長來實現(xiàn)，循環(huán)碼本身的特性使編譯設(shè)備比較容易實現(xiàn)。1.碼多項式：即：若C＝[Cn-1Cn-2……..C1C0]

是一個碼字，則C的每次循環(huán)移位:[Cn-2Cn-3……..C0Cn-1][C0Cn-1Cn-2……C2C1]都是一個碼字?！?7，3)循環(huán)碼序號信息碼000000000000010011101001101110101311111101002110110100131011010011401001001115710010011106碼多項式移位次數(shù)(7.3)循環(huán)碼

按模運算規(guī)則：模n運算下，一整數(shù)m等于其被n除得到的余數(shù)．模２運算中，１＋１＝２＝０２＊３＝６＝０

一般的講，若一整數(shù)m可表示為：則：（模n）對于多項式:2.按模運算

可以證明在循環(huán)碼中,若是一個碼長為n的許用碼組多項式，則在模運算下亦是許用碼組，即若有則也是一個許用碼組前面的（7，3）1110100碼多項式為左移一位的多項式1110100左移一位的碼組1101001對應(yīng)的多項式顯然：

二、循環(huán)碼的生成多項式對于線性分組碼來說只要找到它的生成矩陣就可確定所有的編碼碼字，而它的生成矩陣的每一行都是一個許用碼組，循環(huán)碼的某一個碼字循環(huán)移位可得到它的碼字。只要找到這個碼字就可以得到生成矩陣。這個碼字稱為生成多項式（碼字）結(jié)論：(1)一個(n,k)循環(huán)碼的每一個碼多項式也必然是按模xn+1運算后某個余式，即一個(n,k)循環(huán)碼的所有碼字都可以通過k個許用碼多項式循環(huán)移位得到。(2)

循環(huán)碼完全由其碼組長度n及生成多項式

g

(x)決定。(2)

(n-k)循環(huán)碼的生成多項式g

(x)是xn+1的因式；定理：(1)

在一個(n,k)循環(huán)碼中，存在一個唯一的最低次碼多項式，其次數(shù)為

r=n-k，且常數(shù)項必須為１，即生成多項式：(3)

若g

(x)是一個(n-k)次多項式，且是xn+1的因式，則g

(x)

一定能生成一個(n,k)循環(huán)碼。(4)

所有碼多項式C

(x)

必定能被g

(x)

整除，即:

就是說階數(shù)小于（n-1)能被

g

(x)整除的每個多項式都是循環(huán)碼的許用碼組，或必是

g

(x)的倍式因：則：上式表明多項式應(yīng)該是的一個(n－k)次因式

生成多項式(7,k)循環(huán)碼(n.k)dg

(x)

h

(x)

(7.6)

2(7.4)

3(7.3)

4(7.1)

6

生成矩陣可寫為：例：對于一個（７，４）循環(huán)碼，則由生成多項式：構(gòu)成的生成矩陣為：典型陣為：監(jiān)督矩陣三、循環(huán)碼的系統(tǒng)碼的編碼實現(xiàn)系統(tǒng)碼組中的最左邊的k位是信息碼元，隨后是n－k位的監(jiān)督碼元，即碼多項式為:因此：

有

m

(x)

xn-k

除法求余得到r

(

x)例：已知（７，４）循環(huán)碼的生成多項式為若信息碼為１００１，求編碼碼字因此即編碼碼組為：１００１０１１解：

S0

S1＋輸入m。

S2＋。。。。。K1K2輸出ef輸入移

存

器反饋輸出

mS0S1S2

ef

000000110111011110011010111011001100000101000001000000反饋

e=S2-1+m0(n,k)循環(huán)碼編碼器Sn-k-1s1s0輸出。。。。。。K1K2f輸入四：循環(huán)碼的譯碼校正子計算電路錯誤圖樣識別n級緩存器輸入糾錯后輸出1

2…………….(n-k)監(jiān)督矩陣對于最高位錯誤，校正子為:

a

b

c

七級緩存器糾錯后輸出門(7.4)循環(huán)碼完整譯碼器輸出門5四級緩存器a

b

c門1a

b

c門2門3門4輸入交織碼：將能糾正t個錯誤的碼作為方陣的行碼，m個行碼組構(gòu)成一個方陣，這種交織碼保證可以糾正t個突發(fā)長度為m的突發(fā)錯誤來自編碼器的讀入碼字比特

至調(diào)制器的讀出比特

交織度m第四部分糾正和檢測突發(fā)錯誤的分組碼---交織碼

編碼器輸出時，按列的順序自左至右讀出，這時的序列為:在接收端，將上述過程逆向重復(fù)，即把收到的序列按列寫入存儲器再按行讀出，這時就仍然恢復(fù)成原來的(n,k)分組碼交織碼實際上是一種時間擴(kuò)散技術(shù)，當(dāng)交織度足夠大時，就把突發(fā)錯誤離散成隨機(jī)錯誤，從而被分組碼所糾正,但是m受到傳輸時延的限制。因而(m

n,m

k)也是循環(huán)碼，(n,

k)碼中每一個碼組在(m

n,m

k)碼中對應(yīng)有一個碼組，它們有相同的碼重只是各碼元相隔

m位。

采用循環(huán)碼構(gòu)造交織碼時，不必用陣列就能實現(xiàn)編碼，假設(shè)交織碼每行為(n,k)循環(huán)碼，其生成多項式為，則必定能除盡。交織度為m的交織碼(m

n,m

k)，其生成多項式為，它的物理意義是在的各項之間插入(m-1)個0，顯然能除盡

。

例：用生成多項式為的（7，4）線性分組碼，構(gòu)成交織度為3的（21，12）交織碼，求交織碼的生成多項式及監(jiān)督矩陣。＋＋輸入(7,4)碼編碼器＋＋輸入(21，12)碼編碼器交織碼譯碼時，必須將碼元排列成n×m陣列，然后分別獨立的對其進(jìn)行譯碼。第五部分卷積碼(n，k，N)每次輸入k比特12….k12….k12...k12…k1….k..….2k.....3k….…Nk+++n個模2加法器編碼輸出

卷積編碼器的一般形式N約束度，nN為編碼的約束長度，一般k，n是比較小的整數(shù)。它是一種非分組碼，對于許多實際情況其性能優(yōu)于分組碼。一、卷積碼的圖解表示++輸入序列(2,1,3)卷積碼編碼器輸出TTT001100000011111111111111100101000100010101011010100010101000baaaabbcdcdabcd(每輸入0或1時輸出狀態(tài))(2,1,3)卷積碼編碼的樹狀圖

(2,1,3)卷積碼編碼的邏輯關(guān)系：1101011010001100adbc

(2,1,3)卷積碼編碼的狀態(tài)圖a,b,c,d

為移位寄存器狀態(tài)輸出碼

110101000110011111101100輸入碼

110111001000狀態(tài)

abdcbddcabcaaabcd

(2,1,3)卷積碼編碼的編碼過程及路徑二、卷積碼的解析表示：如輸入序列為1101110….，可得：生成多項式即輸出為：卷積碼的距離特性：最小碼距：卷積碼中長度為nN(N為約束長度)的編碼后序列之間的最小漢明距離。最小自由距：卷積碼中任意長編碼后序列之間的最小漢明距離。采用哪種距離作為糾錯能力的度量與譯碼算法有關(guān)：1.當(dāng)譯碼算法僅限于處理長度為nN的接收序列時，最小碼距是重要考量，如門限譯碼。2.當(dāng)譯碼所考察的編碼后序列長度大于nN時，最小自由距是重要考量，如維特比譯碼或序列譯碼算法。第六部分網(wǎng)格編碼調(diào)制(TCM)提出：糾錯碼可在不提高功率的條件下降低誤碼率，但付出的代價是占用帶寬增加。將編碼和調(diào)制結(jié)合的TCM是解決同時節(jié)省帶寬和功率的途徑之一。這種方法可在保持信息速率和帶寬不變的條件能獲得3dB~6dB的功率增益。傳統(tǒng)的數(shù)字傳輸系統(tǒng)中，糾錯碼和調(diào)制是各自獨立設(shè)計并實現(xiàn)的，譯碼和解調(diào)也是如此。糾錯碼需要冗余度，編碼增益是靠降低信息傳輸速率來獲得的，在功率受限的信道中，功率利用率可用頻帶利用率來換取，在帶寬受限的信道中，則可通過加大調(diào)制信號集來為糾錯碼提供所需的冗余度，以避免信息傳輸速率因加糾錯編碼而降低，但若編碼和調(diào)制獨立分別設(shè)計，則得不到令人滿意的結(jié)果。例如沒有采用糾錯編碼的QPSK調(diào)制和采用2/3碼率卷積編碼及硬判決維特比譯碼的8PSK調(diào)制，兩個系統(tǒng)的信息傳輸速率相同，如果QPSK系統(tǒng)工作在誤比特率為10-5情況，則在相同的信噪比情況下，8PSK解調(diào)器輸出的原始誤碼率超過10-2，這是由于8PSK信號具有更小的信號空間距離的原因，這樣，在譯碼時，需要復(fù)雜的64狀態(tài)維特比譯碼器，8PSK才能與無編碼的QPSK系統(tǒng)差不多。漢明距離：碼組間的最小距離決定編碼的糾錯能力；歐氏距離：相平面中相鄰矢量最小距離決定干擾造成的誤碼。

最佳的編碼調(diào)制系統(tǒng)應(yīng)按照編碼序列的歐氏距離為調(diào)制設(shè)計的量度，這就要求將編碼器和調(diào)制器當(dāng)作一個統(tǒng)一的整體進(jìn)行綜合設(shè)計，使得編碼