現(xiàn)代通信理論第八講糾錯編碼

第八講

差錯控制編碼現(xiàn)代通信理論一、差錯類型隨機性差錯：由高斯噪聲引起，差錯是隨機的且相互之間是獨立出現(xiàn)的。突發(fā)性差錯：由脈沖性干擾引起，在短暫的時間內(nèi)出現(xiàn)大量的差錯，而這些短暫時間之后卻又存在較長的無誤碼區(qū)間?；旌闲圆铄e：即存在隨機差錯又有突發(fā)性差錯二、差錯控制的基本方法

在信息序列之后附加一些監(jiān)督碼元，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，接收端按照既定的規(guī)則檢驗出關(guān)聯(lián)關(guān)系，如這種規(guī)則受到破壞，將會發(fā)現(xiàn)錯誤，乃至糾正錯誤。第一部分糾錯編碼的概念提高信息傳輸?shù)牡目煽啃院陀行?，始終是通信工作所追求的目標(biāo)，糾錯編碼是提高信息傳輸可靠性的一種重要手段差錯控制編碼屬于信道編碼信道容量：信息通過信道傳輸，單位時間內(nèi)信道上所能傳輸?shù)淖畲笮畔⒘浚葱畔⑺俾仕俾剩┓Q為信道容量。對于加性高斯白噪聲信道有：通過對信息進(jìn)行適當(dāng)?shù)木幋a，一個含有噪聲的信道所引起的差錯可以減小到任一期望的水平，而又不會犧牲信息的發(fā)射速率，這就是香農(nóng)信道編碼理論。對于有噪聲的信道，存在可以實現(xiàn)可靠通信的信道編碼。它能在發(fā)送速率R<C時達(dá)到所期望的任意小的水平,若R>C,則無差錯傳輸是不可能的。檢錯與糾錯能力

與最小碼距d0有密切關(guān)系：

許用碼組禁用碼組A00001B

11110

許用碼組禁用碼組

000001010100111101110011可以用來檢測出一位錯誤可糾正一位或檢測兩位錯誤AB0123d

0AB01234

5d

02.

為了糾正t個錯誤：d02t＋11.

為了檢測e個錯誤：d0e＋13.為了同時檢測e個錯誤，糾正t個錯誤：d0e＋t＋1ABd0ett三差錯控制方式1.檢錯重發(fā)（ARQ）(包括停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā))

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

發(fā)收

應(yīng)答信號

2.前向糾錯（FEC）

可以糾正錯誤

發(fā)收

3.混合糾錯（HEC）

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

發(fā)收

應(yīng)答信號

比較：譯碼復(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è)在隨機信道中發(fā)“0”和發(fā)“1”的概率相同，可以證明，在碼長為n的碼組中恰好發(fā)生r個錯誤的概率為：當(dāng)碼長n＝7，誤碼率時

則有：可見采用差錯控制編碼，即使僅能糾正（或檢測）1～2個錯誤，就能使誤碼率下降幾個數(shù)量級。第二部分線性分組碼分組碼中，信息位和監(jiān)督位之間由線性方程組聯(lián)系的編碼稱作線性分組碼，或者說監(jiān)督碼元是由信息碼元的線性組合而產(chǎn)生。若監(jiān)督位增加到2位，就可增加一個監(jiān)督方程式，接收時就可計算2個校正子和，共有四種可能，除了00表示無錯以外，其余3種就可以表示一位錯碼的的具體位置了。這里S稱為校正子，若S＝0，表示無錯，S＝1表示有錯誤，由于只用了一位監(jiān)督位，因此只能表示有錯與無錯。奇偶校驗碼就是一種效率很高的線性分組碼一般說來對于，對于r個監(jiān)督位，可以計算r個校正子，它可以指出種錯誤圖樣，即個錯誤位置，因此對于（n，k）碼。要想指出一位錯碼的所有可能位置，則要求：一、線性分組碼的構(gòu)成：設(shè)分組碼中（n，k）中k＝4，為了糾正一位錯誤，則，取r＝3，則n＝7，用表示，用表示由3個監(jiān)督方程式計算得到的校正子，并假設(shè)這3個校正子與誤碼對應(yīng)的關(guān)系如下表所示：若糾正t個錯誤校正子表

S1S2S3

誤碼位置

S1S2S3

誤碼位置

001

101

010

110

100

111

011

000

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

監(jiān)督位

信息位監(jiān)督位

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

其中P為

階矩陣，

為

階單位陣，

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

×

r階矩陣，I

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

的生成矩陣稱為典型生成矩陣它與典型化形式的關(guān)系為：

結(jié)論：由典型化的生成矩陣產(chǎn)生的是系統(tǒng)碼組；典型化的生成矩陣的各行也必定是線性無關(guān)的，每一行都是一個許用碼組，k行許用碼組經(jīng)過運算可以生成2個不同的碼組；非典型形式的生成矩陣經(jīng)過運算也一定可化為典型形式。k線性分組碼的特性：1)

任意兩個許用碼組之和仍為許用碼組－封閉性2)碼的最小距離等于非零碼的最小重量。三、線性分組碼的伴隨式譯碼發(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)。若

是一個碼字，則C的每次循環(huán)移位都是一個碼字。1.碼多項式：例：(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)碼的每一個碼多項式也必然是按模運算后某個余式，即一個(n，k)循環(huán)碼的所有碼字都可以通過k個許用碼多項式循環(huán)移位得到。2)循環(huán)碼完全由其碼組長度n及生成多項式

g

(x)決定.2.(n－k)循環(huán)碼的生成多項式g

(x)是的因式；定理：1.在一個(n，k)循環(huán)碼中，存在一個唯一的最低次碼多項式，其次數(shù)為

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

3.若是一個(n－k)次多項式，且是的因式，則

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

所有碼多項式必定能被整除，

即

就是說階數(shù)小于（n-1)能被整除的每個多項式都是循環(huán)碼的許用碼組，或必是的倍式因：則：上式表明多項式應(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)

x

除法求余得到r

(

x)n

－

k例：已知（７，４）循環(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級緩存器輸入糾錯后輸出12…………….(n-k)監(jiān)督矩陣對于最高位錯誤，校正子為:

a

b

c

七

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