第七講糾錯編碼.

1、第第 七七 講講 差錯控制編碼差錯控制編碼現(xiàn)代通信理論現(xiàn)代通信理論信信源源信信源源編編碼碼信信道道編編碼碼調(diào)調(diào)制制發(fā)發(fā)轉(zhuǎn)轉(zhuǎn)換換器器媒媒質(zhì)質(zhì)收收轉(zhuǎn)轉(zhuǎn)換換器器解解調(diào)調(diào)信信道道譯譯碼碼信信源源譯譯碼碼信信宿宿目的：目的：提高信息傳輸?shù)牡目煽啃院陀行裕冀K是通信工作所追提高信息傳輸?shù)牡目煽啃院陀行裕冀K是通信工作所追求的目標(biāo)，糾錯編碼是提高信息傳輸可靠性的一種重要手段。求的目標(biāo)，糾錯編碼是提高信息傳輸可靠性的一種重要手段。第一部分第一部分 差錯控制差錯控制編碼的概念編碼的概念差錯控制編碼屬于信道編碼差錯控制編碼屬于信道編碼 提高通信系統(tǒng)的可靠性，降低誤碼率，減少發(fā)射功率，提高提高通信系統(tǒng)的可靠性，

2、降低誤碼率，減少發(fā)射功率，提高接收機的靈敏度等等。接收機的靈敏度等等。 信道容量：信道容量：信息通過信道傳輸，單位時間內(nèi)信道上所能傳輸信息通過信道傳輸，單位時間內(nèi)信道上所能傳輸?shù)淖畲笮畔⒘浚葱畔⑺俾仕俾剩┓Q為信道容量。對于加性的最大信息量（即信息速率速率）稱為信道容量。對于加性高斯白噪聲信道有：高斯白噪聲信道有：C=Blog2(1+S/N)； 香農(nóng)信道編碼理論：香農(nóng)信道編碼理論：通過對信息進行適當(dāng)?shù)木幋a，一個含有通過對信息進行適當(dāng)?shù)木幋a，一個含有噪聲的信道所引起的差錯可以減小到任一期望的水平，而又噪聲的信道所引起的差錯可以減小到任一期望的水平，而又不會犧牲信息的發(fā)射速率；不會犧牲信息的發(fā)射速

3、率； 對于有噪聲的信道，存在可以實現(xiàn)可靠通信的信道編碼。它對于有噪聲的信道，存在可以實現(xiàn)可靠通信的信道編碼。它能在發(fā)送速率能在發(fā)送速率 RC，則無差錯傳輸是不可能的。則無差錯傳輸是不可能的。隨機性差錯：隨機性差錯：由高斯噪聲引起，差錯是隨機的且相互間是獨立出現(xiàn)的。由高斯噪聲引起，差錯是隨機的且相互間是獨立出現(xiàn)的。突發(fā)性差錯：突發(fā)性差錯：由脈沖性干擾引起，在短暫的時間內(nèi)出現(xiàn)大量的差錯，而由脈沖性干擾引起，在短暫的時間內(nèi)出現(xiàn)大量的差錯，而這些短暫時間之后卻又存在較長的無誤碼區(qū)間。這些短暫時間之后卻又存在較長的無誤碼區(qū)間?；旌闲圆铄e：混合性差錯：即存在隨機差錯又有突發(fā)性差錯。即存在隨機差錯又有突發(fā)性

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

5、許用碼組 禁用碼組禁用碼組 00 01 11 10 許用碼組許用碼組 禁用碼組禁用碼組 000 001 010 100 111 101 110 011可以用來檢測出一位錯誤可以用來檢測出一位錯誤可糾正一位或檢測兩位錯誤可糾正一位或檢測兩位錯誤AB0 1 2 3d0AB0 1 2 3 4 5d02. 為了糾正為了糾正 t 個錯誤：個錯誤： d0 2t11. 為了檢測為了檢測 e 個錯誤個錯誤： d0 e1；3. 為了同時檢測為了同時檢測 e 個錯誤，糾正個錯誤，糾正 t 個錯誤個錯誤： d0 et1ABd0ettA 0B 1 無檢錯與糾錯能力無檢錯與糾錯能力三、三、差錯控制方式差錯控制方式2.

6、前向糾錯前向糾錯（FEC） 可以糾正錯誤可以糾正錯誤 發(fā)發(fā) 收收3. 混和糾錯混和糾錯（HEC） 可以發(fā)現(xiàn)和糾正錯誤可以發(fā)現(xiàn)和糾正錯誤 發(fā)發(fā) 收收 應(yīng)答信號應(yīng)答信號 比較：比較：譯碼復(fù)雜性、實時性和占用傳輸鏈路譯碼復(fù)雜性、實時性和占用傳輸鏈路(單向還是雙向單向還是雙向)1. 檢錯重發(fā)檢錯重發(fā)（ARQ）（包括停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)）包括停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)） 能夠發(fā)現(xiàn)錯誤能夠發(fā)現(xiàn)錯誤 發(fā)發(fā) 收收 應(yīng)答信號應(yīng)答信號ARQ：自動重復(fù)請求發(fā)送：自動重復(fù)請求發(fā)送1233123ACKNAKACK等待時間等待時間發(fā)送端發(fā)送端接收端接收端1 2 3 4 5 6 2 3 4 5 6 7 8

7、 9 10 111 2 3 4 5 6 2 3 4 5 6 7 8 9 10 11從碼組從碼組2開始重發(fā)開始重發(fā)NAKACK發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤停發(fā)等候重發(fā)停發(fā)等候重發(fā)返回重發(fā)返回重發(fā)1 2 3 4 5 6 2 7 8 9 10 1 12 1 2 3 4 5 6 2 7 8 9 10 1112重發(fā)重發(fā)碼組碼組2 2NAKACK發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤選擇重發(fā)選擇重發(fā) 四、四、 糾錯碼糾錯碼1. 分組碼與卷積碼分組碼與卷積碼：分組碼：分組碼：將信息碼分組，為每組信息碼后面附加若干位監(jiān)督碼元，且將信息碼分組，為每組信息碼后面附加若干位監(jiān)督碼元，且監(jiān)督碼元僅監(jiān)督本碼組中的信息位。監(jiān)督碼元僅監(jiān)督本碼組中的信息位。

8、1na2nara1ra0a K個信息位個信息位r個監(jiān)督位個監(jiān)督位碼長碼長nkr卷積碼：卷積碼：也是先將信息序列分組，后面附加監(jiān)督位，但是監(jiān)督位不但與也是先將信息序列分組，后面附加監(jiān)督位，但是監(jiān)督位不但與本碼組的信息位有關(guān)，還與前面碼組的信息位有關(guān)，或者說監(jiān)督位不僅本碼組的信息位有關(guān)，還與前面碼組的信息位有關(guān)，或者說監(jiān)督位不僅監(jiān)督本碼組的信息位還監(jiān)督其它碼組的信息位。監(jiān)督本碼組的信息位還監(jiān)督其它碼組的信息位。2. 系統(tǒng)碼與非系統(tǒng)碼系統(tǒng)碼與非系統(tǒng)碼系統(tǒng)碼：系統(tǒng)碼：就是信息位在前，監(jiān)督位在后的碼字。就是信息位在前，監(jiān)督位在后的碼字。非系統(tǒng)碼非系統(tǒng)碼: : 信息位與監(jiān)督位之間無特定的位置關(guān)系信息位與監(jiān)

9、督位之間無特定的位置關(guān)系。五、五、常用的簡單糾錯編碼常用的簡單糾錯編碼1. 奇偶校驗奇偶校驗偶校驗偶校驗00121 aaaann設(shè)信息位每組長度為設(shè)信息位每組長度為n-1-1位，增加一位監(jiān)督位，位，增加一位監(jiān)督位，n n位編碼構(gòu)成位編碼構(gòu)成以下約束關(guān)系：以下約束關(guān)系： 錯錯誤誤正正確確100121aaaaSnn接收端計算：接收端計算：奇偶校驗可以用來檢測單個或奇數(shù)個錯誤奇偶校驗可以用來檢測單個或奇數(shù)個錯誤2. 縱向奇偶校驗（縱向奇偶校驗（LRC）用于檢測突發(fā)錯誤）用于檢測突發(fā)錯誤11100111 11011101 00111001 1010100111100111110111010011100

10、110101001縱向排列縱向排列原始數(shù)據(jù)原始數(shù)據(jù)11100111 11011101 00111001 10101001 10101010突發(fā)錯誤突發(fā)錯誤接收方檢驗是否滿足接收方檢驗是否滿足LRC。LRC 10101010監(jiān)督碼元監(jiān)督碼元 信信 息息 碼碼 元元 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 監(jiān)督碼元監(jiān)督碼元 0 0 1 1 1 0 0 0 0 1

11、 0監(jiān)督碼元監(jiān)督碼元 1 0 0 1 0 1 13. 水平垂直奇偶校驗水平垂直奇偶校驗它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個錯誤它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個錯誤以及長度不大于列數(shù)（或行數(shù)）的突發(fā)錯誤以及長度不大于列數(shù)（或行數(shù)）的突發(fā)錯誤六、六、 差錯控制編碼的效用差錯控制編碼的效用 假設(shè)在隨機信道中發(fā)假設(shè)在隨機信道中發(fā)“0”0”和發(fā)和發(fā)“1”1”的概率相同，可以證的概率相同，可以證明，在碼長為明，在碼長為n n的碼組中恰好發(fā)生的碼組中恰好發(fā)生r r個錯誤的概率為：個錯誤的概率為：rrnrrnnprnrnppCrP)!)!( (! ! !) )( () )( (. .

12、) )( (pP8371053353 . .) )( (pP可見采用差錯控制編碼，即使僅能糾正（或檢測）可見采用差錯控制編碼，即使僅能糾正（或檢測）12個錯誤，就能使誤碼率下降幾個數(shù)量級。個錯誤，就能使誤碼率下降幾個數(shù)量級。3710771 pP) )( (當(dāng)碼長當(dāng)碼長 n7 ，誤碼率誤碼率 P10 -3時時 :則有：則有：第二部分第二部分 線性分組碼線性分組碼若監(jiān)督位增加到若監(jiān)督位增加到2位位，就可增加一個監(jiān)督方程式，接收時就可，就可增加一個監(jiān)督方程式，接收時就可計算計算2個校正子個校正子S1和和S2，共有四種可能，除了，共有四種可能，除了00表示無錯以外，表示無錯以外，其余其余3種就可以表示

13、一位錯碼的的具體位置了。種就可以表示一位錯碼的的具體位置了。這里這里 S 稱為校正子，若稱為校正子，若S0，表示無錯，表示無錯，S1表示有錯誤，表示有錯誤，由于只用了一位監(jiān)督位由于只用了一位監(jiān)督位 a0，因此只能表示有錯與無錯。，因此只能表示有錯與無錯。0121aaaaSnn 奇偶校驗碼就是一種效率很高的線性分組碼奇偶校驗碼就是一種效率很高的線性分組碼分組碼中，信息位和監(jiān)督位之間由線性方程組聯(lián)系的編碼稱作線分組碼中，信息位和監(jiān)督位之間由線性方程組聯(lián)系的編碼稱作線性分組碼，或者說監(jiān)督碼元是由信息碼元的線性組合而產(chǎn)生。性分組碼，或者說監(jiān)督碼元是由信息碼元的線性組合而產(chǎn)生。 一般說來對于，對于一般說

14、來對于，對于r個監(jiān)督位，可以計算個監(jiān)督位，可以計算r個校正子，它可以個校正子，它可以指出指出 種錯誤圖樣，即種錯誤圖樣，即 個錯誤位置，因此對于個錯誤位置，因此對于(n，k)碼。碼。要想指出一位錯碼的所有可能位置，則要求：要想指出一位錯碼的所有可能位置，則要求：12 r12 rrknCnr 1123 r0123456aaaaaaa123SSS設(shè)分組碼中設(shè)分組碼中（n，k）中中k4，為了糾正一位錯誤，則，為了糾正一位錯誤，則 ，取取r3，則，則n7，用，用 表示，用表示，用 表示表示由由3個監(jiān)督方程式計算得到的校正子，并假設(shè)這個監(jiān)督方程式計算得到的校正子，并假設(shè)這3個校正子與誤個校正子與誤碼對應(yīng)

15、的關(guān)系如下表所示：碼對應(yīng)的關(guān)系如下表所示： tiinrC112若糾正若糾正 t 個錯誤個錯誤一、線性分組碼的構(gòu)成：一、線性分組碼的構(gòu)成：校正子表校正子表 S1S2S3 誤碼位置誤碼位置 S1S2S3 誤碼位置誤碼位置 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6 0 1 1 a3 0 0 0 無錯無錯034631356224561aaaaSaaaaSaaaaS 發(fā)送端構(gòu)成偶校驗關(guān)系發(fā)送端構(gòu)成偶校驗關(guān)系 000034613562456aaaaaaaaaaaa監(jiān)督位由信息位的線性組合得到：監(jiān)督位由信息位的線性組合得到： 34603561

16、4562aaaaaaaaaaaa許用碼組許用碼組信息位信息位 監(jiān)督位監(jiān)督位 信息位信息位 監(jiān)督位監(jiān)督位 0 0 0 0 0 0 0 1 0 0 0 111 0 0 0 1 0 1 1 1 0 0 1 100 0 0 1 0 1 0 1 1 0 1 0 010 0 0 1 1 1 1 0 1 0 1 1 001 0 1 0 0 1 1 0 1 1 0 0 001 0 1 0 1 1 0 1 1 1 0 1 010 0 1 1 0 0 1 1 1 1 1 0 100 0 1 1 1 0 0 0 1 1 1 1 1113456aaaa012aaa3456aaaa012aaa 001102031415

17、061000112031405161000102130415161aaaaaaaaaaaaaaaaaaaaa 00010011010101011001011101234567Taaaaaaaa線性分組碼的生成和監(jiān)督矩陣線性分組碼的生成和監(jiān)督矩陣監(jiān)督矩陣監(jiān)督矩陣TTHA0 即即： 0123456Aaaaaaaa 0000 100110101010110010111H其中：其中： rIPH 1001101010101100101110其中其中P為為rk 階矩陣，階矩陣， Ir 為為rr階單位陣階單位陣，具有具有H0 形式稱為形式稱為典型形式的監(jiān)督矩陣；典型形式的監(jiān)督矩陣；線性代數(shù)理論告訴我們，典型

18、形式的監(jiān)督矩陣各行一定是線線性代數(shù)理論告訴我們，典型形式的監(jiān)督矩陣各行一定是線性無關(guān)的，非典型形式的監(jiān)督矩陣可以通過矩陣的初等變換性無關(guān)的，非典型形式的監(jiān)督矩陣可以通過矩陣的初等變換轉(zhuǎn)化為典型形式的監(jiān)督矩陣。轉(zhuǎn)化為典型形式的監(jiān)督矩陣。 34634565634560123456aaaaaaaaaaaaaaaaaaaa對于所有的編碼對于所有的編碼與信息位的關(guān)系：與信息位的關(guān)系： 34563463564563456012345601234561111111111111aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaATTT Gaaaaaaaa 345634561101000101010

19、001100101110001 GaaaaA 3456則則 QIGk 1101000101010001100101110001其中其中Q為為K r 階矩陣階矩陣，I k為為k階單位陣階單位陣具有典型化形式具有典型化形式 G0 = Ik，Q 的生成矩陣稱為典型生成矩陣的生成矩陣稱為典型生成矩陣 它與典型化形式它與典型化形式 H0 = P，Ir 的關(guān)系為：的關(guān)系為： TTPQQP 或或, ,結(jié)論：結(jié)論：線性分組碼的特性：線性分組碼的特性：1) 任意兩個許用碼組之和仍為許用碼組封閉性任意兩個許用碼組之和仍為許用碼組封閉性2) 碼的最小距離等于非零碼的最小重量。碼的最小距離等于非零碼的最小重量。1)

20、由典型化的生成矩陣產(chǎn)生的是系統(tǒng)碼組；由典型化的生成矩陣產(chǎn)生的是系統(tǒng)碼組；2) 典型化的生成矩陣的各行也必定是線性無關(guān)的，每一行都是一典型化的生成矩陣的各行也必定是線性無關(guān)的，每一行都是一個許用碼組，個許用碼組，k 行許用碼組經(jīng)過運算可以生成行許用碼組經(jīng)過運算可以生成 2k 個不同的碼組；個不同的碼組；3) 非典型形式的生成矩陣經(jīng)過運算也一定可化為典型形式。非典型形式的生成矩陣經(jīng)過運算也一定可化為典型形式。三、三、線性分組碼的伴隨式譯碼線性分組碼的伴隨式譯碼.,021rrrRnn.,021eeeEnn發(fā)送碼組為發(fā)送碼組為A，接收碼組為接收碼組為R設(shè)設(shè)E為傳輸錯誤圖樣為傳輸錯誤圖樣，則則：RAET

21、TTTTEHEHAHHEARHS ) )( (計算校正子計算校正子TTHES 或者或者校正子校正子S只與只與E有關(guān)，若接收碼字有關(guān)，若接收碼字R中第中第i位有錯，那么導(dǎo)出的伴隨位有錯，那么導(dǎo)出的伴隨式式 恰好是矩陣恰好是矩陣H的第的第i i列相同的位置。利用伴隨式不列相同的位置。利用伴隨式不僅可以判決接收碼字中是否有錯，而且可以指出差錯的位置。僅可以判決接收碼字中是否有錯，而且可以指出差錯的位置。TTHES 61110000001100110101010110010111HHET 對于前面的例子，一位錯誤圖樣為對于前面的例子，一位錯誤圖樣為（1000000)，（，（0100000)，(0010

22、000), (0001000)，(0000100)，(0000001)，(0000001)50110000010101100111010101110100H 01001000000100110101010110010111H .一、特點：一、特點：循環(huán)碼是一種具有循環(huán)移位特性的線性分組碼，這循環(huán)碼是一種具有循環(huán)移位特性的線性分組碼，這類碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性質(zhì)帶來類碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性質(zhì)帶來的其它性能和特征，并可以用不太長的碼長來實現(xiàn)，循環(huán)碼本的其它性能和特征，并可以用不太長的碼長來實現(xiàn)，循環(huán)碼本身的特性使編譯設(shè)備比較容易實現(xiàn)。身的特性使編譯設(shè)

23、備比較容易實現(xiàn)。1. 碼多項式：碼多項式：012211cxcxcxcxCnnnn ) )( (即：若即：若CCn-1Cn-2.C1C0 是一個碼字，則是一個碼字，則C的每次循環(huán)的每次循環(huán)移位移位:Cn-2Cn-3.C0Cn-1C0Cn-1Cn-2C2C1 都是一個碼字。都是一個碼字。）模（模（17 x,.,., , ,29871xxxxx ) 1(2346236xxxxxxxx) 1(23422456xxxxxxxx) 1(1234525xxxxxxx) 1(12343356xxxxxxx1234xxx) 1(234345xxxxxxxx) 1(1234446xxxxxxx序號序號 信息碼信息

24、碼0 000 0000000 1 001 0011101 02 011 0111010 13 111 1110100 24 110 1101001 35 101 1010011 46 010 0100111 57 100 1001110 6 碼多項式碼多項式移位移位次數(shù)次數(shù)(7.3)循環(huán)碼循環(huán)碼 rqnmnrnrqnm 或或) )( (rm 則：則： （模（模n）)( ( ) )( () )( () )( () )( () )( () )( (xgxrxFxrxgxqxF模模則則 2456xxxx 3567xxxx1356 xxx）（模模17x)(xC)(xCX 1nx) )( () )( (

25、xCxCxii )(xCi3567xxxx ) )( (2456xxxxx1356 xxx）（模模17x 1111 xgxgxxgknknkn) )( ( 0C xg x( )( )模模 )() 1()(xCxxgxnk因：因：)()()()(1kknxxhxgxCxgxx則：則：)(xg) 1(nx (7, k)循環(huán)碼循環(huán)碼(n . k) d g (x) h (x) (7.6) 2(7.4) 3(7.3) 4(7.1) 6323323332432423233231111111111111111xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx ()()()()()()()()()或

26、或或或或或或或)()()()()(0121xgxxgxxgxxgxxGk1)(23xxxg00011010011010011010011010001)(2334245356xxxxxxxxxxxxG00011010010111010001110001100G1001110010011100111010H監(jiān)督矩陣監(jiān)督矩陣011011)()()(rxrxmxmxrxxmxCknknknnkkn）（模)()()()()(xgxxmxcxxmxrknkn)()()()()(xgxrxqxgxmxkn有有 m (x) xn-k 除法求余得到除法求余得到 r ( x)1)(23xxxg1)(1111) 1

27、()()(23232333xxrxxxxxxxxxxxgxmxkn1)(3 xxm11) 1()(13633xxxxxxxC解：解： S0 S1輸入輸入m。 S2。K1K2輸出輸出ef輸入輸入 移移 存存 器器 反饋反饋 輸出輸出 m S0 S1 S2 e f f 0 0 0 0 0 00 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1

28、0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 反饋反饋 e= S2-1+ m0(n ,k)循環(huán)碼編碼器循環(huán)碼編碼器10 gSn-k-1s12gs01g輸出輸出。K1K2f1kngkng輸入輸入四：循環(huán)碼的譯碼四：循環(huán)碼的譯碼) )( () )( () )( () )( () )( (xgxxgxxSEHRHSTT模模模模ER 校正子計算電路校正子計算電路 錯誤圖樣識別錯誤圖樣識別 n 級級 緩緩 存存 器器輸入輸入糾錯后輸出糾錯后輸出1 2 . (n -k) 1001110010011100111010H監(jiān)督矩陣監(jiān)督矩陣對于最高位錯誤，校正子為

29、對于最高位錯誤，校正子為: :) )( () )( (, ,) )( (xgxxExxxS模模62 a b c 七七 級級 緩緩 存存 器器糾錯后輸出糾錯后輸出門門(7.4) 循環(huán)碼完整譯碼器循環(huán)碼完整譯碼器輸出輸出門門5 四四 級級 緩緩 存存 器器 a b c門門1 a b c門門2門門3門門4輸入輸入交織碼：交織碼：將能糾正將能糾正t個錯誤的碼作為方陣的行碼，個錯誤的碼作為方陣的行碼，m個行碼組構(gòu)成個行碼組構(gòu)成一個方陣，這種交織碼保證可以糾正一個方陣，這種交織碼保證可以糾正t個個突發(fā)長度為突發(fā)長度為m的突發(fā)錯誤的突發(fā)錯誤mnmnmn147592681 來自來自編碼編碼器的器的讀入讀入碼字

30、碼字比特比特 至調(diào)制器的讀出比特至調(diào)制器的讀出比特 交織度交織度m第四部分第四部分 糾正和檢測突發(fā)錯誤的分組碼糾正和檢測突發(fā)錯誤的分組碼-交織碼交織碼 mnmnmn5621141516789123 編碼器輸出時，按列的順序自左至右讀出，這時的序列為編碼器輸出時，按列的順序自左至右讀出，這時的序列為: :在接收端，將上述過程逆向重復(fù)，即把收到的序列按列寫入在接收端，將上述過程逆向重復(fù)，即把收到的序列按列寫入存儲器再按行讀出，這時就仍然恢復(fù)成原來的存儲器再按行讀出，這時就仍然恢復(fù)成原來的 (n,k) 分組碼分組碼 交織碼實際上是一種時間擴散技術(shù)，當(dāng)交織度足夠大時，交織碼實際上是一種時間擴散技術(shù)，當(dāng)

31、交織度足夠大時，就把突發(fā)錯誤離散成隨機錯誤，從而被分組碼所糾正就把突發(fā)錯誤離散成隨機錯誤，從而被分組碼所糾正, ,但是但是m受到傳輸時延的限制。受到傳輸時延的限制。 因而因而 (m n, m k) 也是循環(huán)碼也是循環(huán)碼，(n, k) 碼中每一個碼組在碼中每一個碼組在(m n , m k) 碼中對應(yīng)有一個碼組，它們有相同的碼重只是各碼碼中對應(yīng)有一個碼組，它們有相同的碼重只是各碼元相隔元相隔 m位位。) )( (xg) )( (xg1 nx) )( () )( (mmxgxg ) )( (xg) )( (mxg11 mnnmxx ) )( (mn 采用循環(huán)碼構(gòu)造交織碼時，不必用采用循環(huán)碼構(gòu)造交織碼

32、時，不必用 陣列就能實現(xiàn)編陣列就能實現(xiàn)編碼，假設(shè)交織碼每行為碼，假設(shè)交織碼每行為(n, k)循環(huán)碼，其生成多項式為循環(huán)碼，其生成多項式為 ，則則 必定能除盡必定能除盡 。交織度為。交織度為m的交織碼的交織碼(m n, m k)，其，其生成多項式為生成多項式為 ，它的物理意義是在，它的物理意義是在 的各項的各項之間插入之間插入(m-1)個個0，顯然，顯然 能除盡能除盡 。 1)(23xxxg16903233333 xxxxxxgxg) )( () )( () )( () )( () )( (例例：用生成多項式為：用生成多項式為 的的（7，4）線性分線性分組碼，構(gòu)成交織度為組碼，構(gòu)成交織度為3的的

33、（21，12）交織碼，求交織碼的生成多交織碼，求交織碼的生成多項式及監(jiān)督矩陣。項式及監(jiān)督矩陣。輸入輸入(7,4)碼編碼器碼編碼器輸入輸入(21，12)碼編碼器碼編碼器 交織碼譯碼時，必須將碼元排列成交織碼譯碼時，必須將碼元排列成 nm 陣列，然后分別陣列，然后分別獨立的對其進行譯碼。獨立的對其進行譯碼。第五部分第五部分 卷積碼卷積碼 (n，k，N)每次輸入每次輸入 k比特比特1 2 . k 1 2 . k 1 2 . k 1 2 k1 . k . 2k . . 3k . Nk+n個模個模2加法器加法器編碼輸出編碼輸出 卷積編碼器的一般形式卷積編碼器的一般形式N約束度，約束度，nN為編碼的約束長

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

35、卷積碼編碼的邏輯關(guān)系：卷積碼編碼的邏輯關(guān)系：1101011010001100adbc (2,1,3)卷積碼編碼的狀態(tài)圖卷積碼編碼的狀態(tài)圖a, b, c, d 為移位寄存器狀態(tài)為移位寄存器狀態(tài)輸出碼輸出碼 11 01 01 00 01 10 01 11 11 10 11 00輸入碼輸入碼 1 1 0 1 1 1 0 0 1 0 0 0狀態(tài)狀態(tài) a b d c b d d c a b c a aa bcd (2,1,3)卷積碼編碼的編碼過程及路徑卷積碼編碼的編碼過程及路徑 222111xxGxxxG) )( () )( (二、卷積碼的解析表示：二、卷積碼的解析表示：如輸入序列為如輸入序列為1101

36、110.，可得：，可得： 75543211111xxxxxxxxxMxGxy) )()( () )( () )( () )( ( 7642543222111xxxxxxxxxxxMxGxy) ) )( ( () )( () )( () )( ( 生成多項式生成多項式即輸出為：即輸出為：111010111000010132221223121111 ) ), , ,( () ), , ,( (, , , , , , ,yyyyyyyy01001111101010001323122211211 ) ), , , , , , ,( (, , , , , , ,yyyyyyy卷積碼的距離特性：卷積碼的距

37、離特性：最小碼距：最小碼距：卷積碼中長度為卷積碼中長度為nN(N為約束長度為約束長度)的編碼后序列的編碼后序列 之間的最小漢明距離。之間的最小漢明距離。) )( (minmind最小自由距最小自由距：卷積碼中任意長：卷積碼中任意長編碼后序列之間的最小漢明距離。編碼后序列之間的最小漢明距離。) )( (freed采用哪種距離作為糾錯能力的度量與譯碼算法有關(guān)：采用哪種距離作為糾錯能力的度量與譯碼算法有關(guān)：1. 當(dāng)譯碼算法僅限于處理長度為當(dāng)譯碼算法僅限于處理長度為nN的接收序列時，最小碼距的接收序列時，最小碼距 是重要考量，如門限譯碼。是重要考量，如門限譯碼。) )( (minmind2 .當(dāng)譯碼所

38、考察的編碼后序列長度大于當(dāng)譯碼所考察的編碼后序列長度大于nN時，最小自由距時，最小自由距 是重要考量，如維特比譯碼或序列譯碼算法。是重要考量，如維特比譯碼或序列譯碼算法。) )( (freed第六部分第六部分 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制 (TCM)提出：提出：糾錯碼可在不提高功率的條件下降低誤碼率，但付出的代價是占用帶寬糾錯碼可在不提高功率的條件下降低誤碼率，但付出的代價是占用帶寬增加。將編碼和調(diào)制結(jié)合的增加。將編碼和調(diào)制結(jié)合的TCM是解決同時節(jié)省帶寬和功率的途徑之一。這是解決同時節(jié)省帶寬和功率的途徑之一。這種方法可在保持信息速率和帶寬不變的條件能獲得種方法可在保持信息速率和帶寬不變的條件能獲得

39、3dB6dB的功率增益。的功率增益。 傳統(tǒng)的數(shù)字傳輸系統(tǒng)中，糾錯碼和調(diào)制是各自獨立設(shè)計并實現(xiàn)的，譯碼和傳統(tǒng)的數(shù)字傳輸系統(tǒng)中，糾錯碼和調(diào)制是各自獨立設(shè)計并實現(xiàn)的，譯碼和解調(diào)也是如此。糾錯碼需要冗余度，編碼增益是靠降低信息傳輸速率來獲得的，解調(diào)也是如此。糾錯碼需要冗余度，編碼增益是靠降低信息傳輸速率來獲得的，在功率受限的信道中，功率利用率可用頻帶利用率來換取，在帶寬受限的信道在功率受限的信道中，功率利用率可用頻帶利用率來換取，在帶寬受限的信道中，則可通過加大調(diào)制信號集來為糾錯碼提供所需的冗余度，以避免信息傳輸中，則可通過加大調(diào)制信號集來為糾錯碼提供所需的冗余度，以避免信息傳輸速率因加糾錯編碼而降低

40、，但若編碼和調(diào)制獨立分別設(shè)計，則得不到令人滿意速率因加糾錯編碼而降低，但若編碼和調(diào)制獨立分別設(shè)計，則得不到令人滿意的結(jié)果。的結(jié)果。 例如沒有采用糾錯編碼的例如沒有采用糾錯編碼的QPSK調(diào)制和采用調(diào)制和采用2/3碼率卷積編碼及硬判決維特碼率卷積編碼及硬判決維特比譯碼的比譯碼的8PSK 調(diào)制，兩個系統(tǒng)的信息傳輸速率相同，如果調(diào)制，兩個系統(tǒng)的信息傳輸速率相同，如果QPSK系統(tǒng)工作在系統(tǒng)工作在誤比特率為誤比特率為10-5情況，則在相同的信噪比情況下，情況，則在相同的信噪比情況下，8PSK解調(diào)器輸出的原始誤碼解調(diào)器輸出的原始誤碼率超過率超過10-2，這是由于，這是由于8PSK信號具有更小的信號空間距離的

41、原因，這樣，在譯信號具有更小的信號空間距離的原因，這樣，在譯碼時，需要復(fù)雜的碼時，需要復(fù)雜的64狀態(tài)維特比譯碼器，狀態(tài)維特比譯碼器，8PSK才能與無編碼的才能與無編碼的QPSK系統(tǒng)差系統(tǒng)差不多。不多。漢明距離：漢明距離：碼組間的最小距離決定編碼的糾錯能力；碼組間的最小距離決定編碼的糾錯能力；歐氏距離：歐氏距離：相平面中相鄰矢量最小距離決定干擾造成的誤碼。相平面中相鄰矢量最小距離決定干擾造成的誤碼。 最佳的編碼調(diào)制系統(tǒng)應(yīng)按照編碼序列的歐氏距離為調(diào)制設(shè)計的量度，最佳的編碼調(diào)制系統(tǒng)應(yīng)按照編碼序列的歐氏距離為調(diào)制設(shè)計的量度，這就要求將編碼器和調(diào)制器當(dāng)作一個統(tǒng)一的整體進行綜合設(shè)計，使得這就要求將編碼器和

42、調(diào)制器當(dāng)作一個統(tǒng)一的整體進行綜合設(shè)計，使得編碼器和調(diào)制器級聯(lián)后產(chǎn)生的編碼序列具有最大的歐氏距離，這種最編碼器和調(diào)制器級聯(lián)后產(chǎn)生的編碼序列具有最大的歐氏距離，這種最佳設(shè)計就是對信號空間的最佳分割，稱為網(wǎng)格編碼調(diào)制佳設(shè)計就是對信號空間的最佳分割，稱為網(wǎng)格編碼調(diào)制(TCM) 對于限帶信道，有兩類網(wǎng)格編碼調(diào)制，第一類將卷積碼和多電平對于限帶信道，有兩類網(wǎng)格編碼調(diào)制，第一類將卷積碼和多電平(或多相位或多相位)信號組合起來，它由信號組合起來，它由Ungerboeck最先提出，第二類是采用特最先提出，第二類是采用特定調(diào)制指數(shù)或頻偏的連續(xù)相位頻移鍵控定調(diào)制指數(shù)或頻偏的連續(xù)相位頻移鍵控(CPFSK)。我們這里只介紹第。我們這里只介紹第一類一類TCM，它具有兩個基本特征：