第7-8章-分組碼和卷積碼

1、第七第七-八章八章 分組碼和卷積碼分組碼和卷積碼1線性分組碼線性分組碼卷積碼卷積碼信道編碼原理：信道編碼原理：只要只要 R C，就存在一種編譯碼方式能夠?qū)崿F(xiàn)在，就存在一種編譯碼方式能夠?qū)崿F(xiàn)在 R 的速率下傳輸信的速率下傳輸信息，而且誤碼率還能夠任意小。息，而且誤碼率還能夠任意小。但是，這里只證明了存在性，并沒有給出如何實現(xiàn)！但是，這里只證明了存在性，并沒有給出如何實現(xiàn)！即使是隨機編碼的方式，也只能在編碼長度無窮大時才能夠獲得任即使是隨機編碼的方式，也只能在編碼長度無窮大時才能夠獲得任意小的誤碼率！意小的誤碼率！7.1 基本定義基本定義2基本概念：基本概念：u 由一組固定長度的碼字矢量組成。由一

2、組固定長度的碼字矢量組成。 碼長碼長矢量元數(shù)的個數(shù)矢量元數(shù)的個數(shù) n。u 碼字元素選自由碼字元素選自由q個元素組成的字符集（二進制分組碼，非二進個元素組成的字符集（二進制分組碼，非二進制分組碼）制分組碼）長度為長度為n的碼字的碼字2n個碼字個碼字k個信息比特個信息比特2k種組合種組合(n, k) 碼碼映射映射nkRc u 信息比特與碼字之間的關(guān)系信息比特與碼字之間的關(guān)系碼率：碼率：7.1 基本定義基本定義3有限域，也稱伽羅華域（有限域，也稱伽羅華域（Galios Field）：二進制加法和乘法）：二進制加法和乘法的有限集合。的有限集合。+01001110X010001011. 基域：基域：mq

3、p GF(50, 1, 2, 3, 4 ) )模模 5 的加法和乘法運算的加法和乘法運算擴域：擴域：mqp 2. 有限域上的多項式：有限域上的多項式：2012()mmg Xgg Xg Xg X GF( )igp 首一（首一（Monic）多項式：）多項式：1mg 既約多項式：多項式無法寫成兩個低次多項式的乘積。既約多項式：多項式無法寫成兩個低次多項式的乘積。22+1(1)XX 7.1 基本定義基本定義43. 擴域：本原多項式擴域：本原多項式GF(4)域的加法和乘法：域的加法和乘法：2+1XX +01XX+1001XX+1110X+1XXXX+101X+1X+1X10 x01XX+10000010

4、1XX+1X0XX+11X+10X+11X2=1XX 7.1 基本定義基本定義54. 本原元和本原多項式本原元和本原多項式GF(2m) )mg(X)2X2+X+13X3+X+14X4+X+15X5+X+16X6+X+17X7+X+18X8+X4+X3+X2+19X9+X4+110X10+X3+111X11+X2+112X12+X6+X4+X+17.2 線性分組碼的一般性質(zhì)線性分組碼的一般性質(zhì)6任何碼字都是任何碼字都是 G 的矢量的矢量 的線性組合：的線性組合：生成矩陣和奇偶校驗矩陣生成矩陣和奇偶校驗矩陣假設：假設：k個信息比特個信息比特碼字（碼字（n位）位）編碼運算：編碼運算：矩陣形式：矩陣形

5、式：j = 1, nG 生成矩陣生成矩陣mumcGmmcu kjmkjmjmmjgxgxgxc 2211 ig11221kmmiimmmkkicu gugugug knkknnggggggggg212222111211k21gggG7.2 線性分組碼的一般性質(zhì)線性分組碼的一般性質(zhì)7(n, k) 線性碼的對偶碼線性碼的對偶碼l是一種是一種 (n, n-k) 線性碼，有線性碼，有 2n-k 個碼矢量個碼矢量l生成矩陣生成矩陣 H，由，由 n-k 個線性無關(guān)的碼矢量組成個線性無關(guān)的碼矢量組成由于對由于對(n, k)碼的每個碼字都成立，于是：碼的每個碼字都成立，于是：(n, k)碼碼(n, k) 碼任

6、意一個碼字碼任意一個碼字 Cm 都正交于矩陣都正交于矩陣H的每一行的每一行l(wèi)對偶碼對偶碼 (n, n-k)正交于正交于l H矩陣用于譯碼器檢查收到的碼字矩陣用于譯碼器檢查收到的碼字 c 是否滿足是否滿足 cHt = 0H 矩陣稱為矩陣稱為 (n,k) 碼的一致校驗矩陣碼的一致校驗矩陣 （簡稱校驗矩陣）（簡稱校驗矩陣）c H0tm GH0t 7.2 線性分組碼的一般性質(zhì)線性分組碼的一般性質(zhì)87.2.2 線性分組碼的重量和距離特性線性分組碼的重量和距離特性l 碼字的重量：碼字里非零碼元的數(shù)量碼字的重量：碼字里非零碼元的數(shù)量l 碼字間的漢明距離：兩個碼字間不同碼元的個數(shù)碼字間的漢明距離：兩個碼字間不

7、同碼元的個數(shù)l 碼的最小距離碼的最小距離l 線性分組碼的最小重量與奇偶校驗矩陣列之間的相關(guān)性有關(guān)線性分組碼的最小重量與奇偶校驗矩陣列之間的相關(guān)性有關(guān)( )w c1212min12,min(,)c cC ccdd c c l 碼的最小重量碼的最小重量min,0min( )c C cww c 7.2 線性分組碼的一般性質(zhì)線性分組碼的一般性質(zhì)97.2.3 重量分布多項式重量分布多項式l 碼的重量分布多項式（碼的重量分布多項式（WEP）：）：多項式的系數(shù)是該碼字中不同重量的碼字的個數(shù)多項式的系數(shù)是該碼字中不同重量的碼字的個數(shù)l對于正交對于正交 FSK 調(diào)制有調(diào)制有l(wèi) 假設發(fā)送的是全零碼字，則對于假設發(fā)

8、送的是全零碼字，則對于 BPSK 調(diào)制有調(diào)制有2E()4()mbcmdsR w c min0()1nniiiiii dA ZA ZA Z2E()2()mbcmdsR w c 7.2 線性分組碼的一般性質(zhì)線性分組碼的一般性質(zhì)107.2.4 線性分組碼的差錯概率線性分組碼的差錯概率l 碼字差錯概率：碼字差錯概率：定義定義min020( )mmmnecicCi dcPPA P i 01Y(|0) (|)minciimiiyPp yp yc Y=(|0) (|1)yp yp y ()02=( ()mmw ccmPP w c min(21)dkeP 7.3 一些特殊的線性分組碼一些特殊的線性分組碼117

9、.3.1 重復碼重復碼： (n, 1) 碼，全碼，全0 或者全或者全11/cRn mindn 7.3.2 漢明漢明 (n, k) 碼碼：2121mcmmR 21, 21mmnkm (1)/2(1)/21()(1)(1)(1)1nnnA ZZnZZn 7.3.3 最大長度碼最大長度碼：漢明碼的對偶碼：漢明碼的對偶碼21, )mm （1()1(21)mmA ZZ 7.3.4 Reed-Muller碼碼：min02 , , 2rmm rimnkdi 7.4 線性分組碼的最佳軟判決譯碼線性分組碼的最佳軟判決譯碼12有效碼字間的最佳檢測，如相關(guān)度量計算有效碼字間的最佳檢測，如相關(guān)度量計算jcjrn 主要

10、問題：碼字數(shù)量巨大，導致計算量巨大主要問題：碼字數(shù)量巨大，導致計算量巨大1( ,)(21)nmmmjjjCMC r ccr min0/(21)cbR dNkePe 7.5 線性分組碼的硬判決譯碼線性分組碼的硬判決譯碼13先逐個碼元進行判決后，再進行譯碼先逐個碼元進行判決后，再進行譯碼1. 最小距離（最大似然）譯碼最小距離（最大似然）譯碼判決后的碼字可能不是一個有效碼字，尋找與該碼字距離最小判決后的碼字可能不是一個有效碼字，尋找與該碼字距離最小的有效碼字作為譯碼的結(jié)果的有效碼字作為譯碼的結(jié)果2. 伴隨式和標準陣列伴隨式和標準陣列mycettsyHeH 7.5.2. 硬判決譯碼硬判決譯碼min(1

11、)/ 2td糾錯能力：糾錯能力：7.6 硬判決與軟判決譯碼的性能比較硬判決與軟判決譯碼的性能比較147.7 線性分組碼最小距離的邊界線性分組碼最小距離的邊界157.7.1 辛格爾頓（辛格爾頓（Singleton）界）界：min1dnk 7.7.2 漢明界漢明界：min(1)/22011logdcinRni 7.7.3 普洛特金（普洛特金（Plotkin）界）界：對于：對于 q 元，元，1min1kkkdqqnq 1min221kkdn 對于對于 二進制，二進制，7.8 修改的線性分組碼修改的線性分組碼167.8.1 縮短和伸長縮短和伸長7.8.2 刪余和擴展刪余和擴展7.8.3 刪信和增廣刪信

12、和增廣7.9 循環(huán)碼循環(huán)碼17l循環(huán)碼循環(huán)碼是線性碼的一個子集。是線性碼的一個子集。 碼字碼字碼字碼字 C 的所有循環(huán)移位都是碼字的所有循環(huán)移位都是碼字循環(huán)碼的碼字多項式表示：循環(huán)碼的碼字多項式表示： n-1次多項式，用它與碼字次多項式，用它與碼字 C 聯(lián)系起來聯(lián)系起來特點：特點：若兩邊同乘若兩邊同乘 X：Xc(X) 除于除于 Xn+1：其中：其中：代表碼字：代表碼字：c1(X) 是是Xc(X)除于除于Xn+1的余式，因此：的余式，因此： 0121 Cccccnn 121210()nnnnc XcXcXc Xc 121210()nnnnXc XcXcXc Xc X (1)1()()11nnnX

13、c XCXcXX 1122301()nnnnncXcXcXc Xc （）12301 nnnccccc （）1()() mod1nc XXc XX7.9 循環(huán)碼循環(huán)碼18l 生成多項式生成多項式111()1n kn kn kg XXgXg X l 信息多項式：長度為信息多項式：長度為k121210()kkkku XuXuXu Xu l 碼字多項式：長度為碼字多項式：長度為n()() (), 1,2,2kmmcXuX g Xm 生成多項式生成多項式 g(X) 必須是必須是 Xn+1 的因式，例如的因式，例如323+1(1)(1)(1)nXXXXXX 系統(tǒng)循環(huán)碼：系統(tǒng)循環(huán)碼：-()()()()()n

14、 kXu Xr XQ Xg Xg X()()()n kc XXu Xr X 7.9 循環(huán)碼循環(huán)碼19l 循環(huán)碼編碼器：移位寄存器循環(huán)碼編碼器：移位寄存器l 循環(huán)碼的譯碼循環(huán)碼的譯碼7.10 BCH碼碼7.11 RS碼碼uBCH碼的生成多項式由碼的生成多項式由 的因式構(gòu)成的因式構(gòu)成特點：特點：u循環(huán)碼的一個大類循環(huán)碼的一個大類 ； （二進制，非二進制）（二進制，非二進制）u二進制二進制BCH碼：碼：m 和和 t 是任意正整數(shù)，是任意正整數(shù)， u非二進制非二進制BCH碼：包括碼：包括Reed-Solomon碼碼12 mnmtkn 12min td3 m112 mp8.1 卷積碼的構(gòu)造卷積碼的構(gòu)造2

15、0l二進制數(shù)據(jù)移位輸入到編碼器，沿著移存器每次移動二進制數(shù)據(jù)移位輸入到編碼器，沿著移存器每次移動 k 比特；比特；l每個每個 k 比特長的輸入序列對應一個比特長的輸入序列對應一個 n 比特長的輸出序列；碼率比特長的輸出序列；碼率 Rc=k/nlK（移存器的級數(shù)）稱為卷積碼的約束長度。（移存器的級數(shù)）稱為卷積碼的約束長度。編碼器由編碼器由 K 級移存器（每級級移存器（每級 k 比特）和比特）和 n 個模個模2加法器組成加法器組成編碼過程：編碼過程：卷積碼的描述方法：樹圖、網(wǎng)格圖、狀態(tài)圖卷積碼的描述方法：樹圖、網(wǎng)格圖、狀態(tài)圖8.2 卷積碼的譯碼卷積碼的譯碼21卷積碼譯碼卷積碼譯碼l卷積碼沒有固定長

16、度，有記憶，采用序列譯碼；卷積碼沒有固定長度，有記憶，采用序列譯碼；l譯碼器是一個最大似然序列估計器；譯碼器是一個最大似然序列估計器；l譯碼過程：搜遍網(wǎng)格圖找出最可能的序列譯碼過程：搜遍網(wǎng)格圖找出最可能的序列l(wèi)譯碼度量：硬判決譯碼度量：硬判決漢明距離；軟判決漢明距離；軟判決歐氏距離歐氏距離8.3 二進制卷積碼的距離特性二進制卷積碼的距離特性228.9 Turbo碼和迭代譯碼碼和迭代譯碼23l編碼器結(jié)構(gòu)：編碼器結(jié)構(gòu)：由兩個并聯(lián)的卷積編碼器組成，第由兩個并聯(lián)的卷積編碼器組成，第2級編碼器前串接了一個交織器級編碼器前串接了一個交織器交織器：信息比交織器：信息比特進入下一級編特進入下一級編碼器之前對它

17、們碼器之前對它們重新排序重新排序?qū)ΧM制卷積編碼器輸出的校對二進制卷積編碼器輸出的校驗比特進行刪余處理，目的是驗比特進行刪余處理，目的是為了提高碼率為了提高碼率帶交織的并行級聯(lián)卷積碼帶交織的并行級聯(lián)卷積碼 Turbo8.9 Turbo碼和迭代譯碼碼和迭代譯碼24特色之一：特色之一：兩個編碼器與交織結(jié)合的效果：兩個編碼器與交織結(jié)合的效果：使碼字變得相對稀疏，即各碼字極少有離它很靠近的鄰碼。使碼字變得相對稀疏，即各碼字極少有離它很靠近的鄰碼。交織導致緊鄰碼字數(shù)量的減少，由此使編碼增益提高。交織導致緊鄰碼字數(shù)量的減少，由此使編碼增益提高。已經(jīng)證明，當交織器長度為已經(jīng)證明，當交織器長度為 N 時，緊鄰

18、碼字的數(shù)目減少時，緊鄰碼字的數(shù)目減少 N 倍倍特色之二：特色之二：使用基于使用基于MAP準則的迭代譯碼準則的迭代譯碼8.9 Turbo碼和迭代譯碼碼和迭代譯碼25Turbo碼的性能碼的性能l影響影響Turbo碼性能的一個重要因素碼性能的一個重要因素交織長度（交織增益）交織長度（交織增益）l大交織產(chǎn)生的問題：譯碼時延；計算復雜大交織產(chǎn)生的問題：譯碼時延；計算復雜帶交織的串行級聯(lián)卷積碼帶交織的串行級聯(lián)卷積碼 1998年年 Benedetto另一種級聯(lián)卷積碼另一種級聯(lián)卷積碼在低誤碼率時，具有比并行級聯(lián)碼更好的性能在低誤碼率時，具有比并行級聯(lián)碼更好的性能使用足夠大的交使用足夠大的交織器，采用織器，采用

19、MAP迭代譯碼迭代譯碼Turbo碼的性能碼的性能可以非常接近可以非常接近Shannon限限8.11 LDPC碼碼26LDPC碼：具有稀疏校驗矩陣的線性分組碼碼：具有稀疏校驗矩陣的線性分組碼LDPC碼的硬譯碼和軟譯碼碼的硬譯碼和軟譯碼8.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM27背景背景l(fā)分組碼和卷積碼：性能的改善是通過擴大傳輸信號帶寬為分組碼和卷積碼：性能的改善是通過擴大傳輸信號帶寬為代價而獲得的；代價而獲得的；l這種情況主要適用于功率受限信道的設計。這種情況主要適用于功率受限信道的設計。如如 (24, 12) Golay碼：碼： 當當 b=10 時，編碼增益時，編碼增益=5dB 但這個編碼增益

20、以傳輸信號帶寬增大但這個編碼增益以傳輸信號帶寬增大1倍而獲得。倍而獲得。l采用軟判決譯碼的二進制采用軟判決譯碼的二進制 (n, k) 分組碼，與不編碼系統(tǒng)相比，分組碼，與不編碼系統(tǒng)相比，所得到的性能改善約為：所得到的性能改善約為：如何解決帶限信道的編碼問題？如何解決帶限信道的編碼問題？要求：不擴展帶寬而獲得編碼增益。要求：不擴展帶寬而獲得編碼增益。dB )/2lnlog(10minbckdR 8.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM28分析分析： （假設一次傳輸假設一次傳輸 2 個比特的情況）個比特的情況）編碼編碼要使編碼后與不編碼要使編碼后與不編碼QPSK具有具有同樣的數(shù)據(jù)吞吐量同樣的數(shù)據(jù)吞

21、吐量l不編碼系統(tǒng)：不編碼系統(tǒng)：QPSK ，4個點的信號星座個點的信號星座 ，每個符號攜帶，每個符號攜帶 2 比特比特l采用采用 2/3 的編碼系統(tǒng)：的編碼系統(tǒng)：必須必須結(jié)合如結(jié)合如8PSK的調(diào)制使用的調(diào)制使用2信息比特信息比特3編碼比特編碼比特l引出的問題：引出的問題： 與與QPSK星座相比，要保持相同的星座相比，要保持相同的Pe ，8PSK星座要求的信星座要求的信號功率必須增加號功率必須增加4dB！如何補償由于信號集擴大而產(chǎn)生的這種要求？如何補償由于信號集擴大而產(chǎn)生的這種要求？8.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM29兩種解決方案：兩種解決方案：l按照傳統(tǒng)的方法按照傳統(tǒng)的方法 編碼與調(diào)制分

22、別獨立設計編碼與調(diào)制分別獨立設計u通過增大編碼符號間的最小歐氏距離來彌補信號集擴大造成通過增大編碼符號間的最小歐氏距離來彌補信號集擴大造成的損失。的損失。u要求編碼器必須提供要求編碼器必須提供 4 dB以上的編碼增益才能補償這一要求。以上的編碼增益才能補償這一要求。 u措施：措施： 通過采用大約束長度的卷積碼，大分組長度的分組碼。通過采用大約束長度的卷積碼，大分組長度的分組碼。l編碼與調(diào)制結(jié)合在一起設計編碼與調(diào)制結(jié)合在一起設計 網(wǎng)格編碼調(diào)制的核心思想網(wǎng)格編碼調(diào)制的核心思想l編碼調(diào)制集成的關(guān)鍵：編碼調(diào)制集成的關(guān)鍵：找到一種有效的辦法，將編碼比特映射到信號點集，而使最小找到一種有效的辦法，將編碼比

23、特映射到信號點集，而使最小歐式距離最大。歐式距離最大。8.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM30途徑：分集映射途徑：分集映射l分集：分集： 遵循遵循“最小歐氏距離逐級增大最小歐氏距離逐級增大”的原則的原則第第1次分集：分為次分集：分為2個子集，每子集個子集，每子集4點，點，第第2次分集：兩個子集又進一步劃分，次分集：兩個子集又進一步劃分，最后一次分集得到最后一次分集得到8個子集，每個子集僅包含個子集，每個子集僅包含一個信號點一個信號點8PSK：各點間相隔的最小歐氏距離為：各點間相隔的最小歐氏距離為：將信號星座分割成子集，使子集中兩個信號點之間的最將信號星座分割成子集，使子集中兩個信號點之間的

24、最小歐氏距離隨著每次分集變大。小歐氏距離隨著每次分集變大。 765. 0)22(8sin20 d 21 d 22 d8.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM31l每次子集隔點選取每次子集隔點選取l對矩形信號星座而言，每一級分集可使最小歐氏距離增加對矩形信號星座而言，每一級分集可使最小歐氏距離增加 倍。倍。l第一次分集后，點間距離從第一次分集后，點間距離從 增加到增加到16QAM信號星座的分集信號星座的分集 2 2222/1 iidd8.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM32編碼過程：編碼過程：l 映射（編碼）映射（編碼）k2個未編碼比個未編碼比特用來在各子特用來在各子集中選擇某一集中選擇某一

25、信號點。信號點。信息輸入信息輸入m比比特分為兩路特分為兩路從編碼器得出的從編碼器得出的n比特用來選擇子比特用來選擇子集（在分集后信集（在分集后信號星座的號星座的2n個子個子集中選擇其一）集中選擇其一）k1k28.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM33分兩步實現(xiàn)：分兩步實現(xiàn)：譯碼譯碼 （軟判決譯碼）（軟判決譯碼）l子集譯碼子集譯碼確定每一子集中的最佳信號點；確定每一子集中的最佳信號點； （即確定每個子集中離接收信號點最近的點）（即確定每個子集中離接收信號點最近的點）l路徑譯碼路徑譯碼 將每個子集選出的信號點及相應的平方距離量度對應到將每個子集選出的信號點及相應的平方距離量度對應到Viterbi算法的分支中，在網(wǎng)格圖中找出一條信號路徑，該算法的分支中，在網(wǎng)格圖中找出一條信號路徑，該路徑與接收信號序列的距離平方之和最小。路徑與接收信號序列的距離平方之和最小。8.12 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制TCM34性能性能 （網(wǎng)格編碼調(diào)制所能獲得的編碼增益一覽）（網(wǎng)格編碼調(diào)制所能獲得的編碼增益一覽）碼率為碼率為1/2，一維，一維PAM調(diào)制時：調(diào)制時：當當 Pe 在在 10-610-8 范圍時，范圍時，128狀態(tài)可獲得狀態(tài)可獲得 5.8dB 的編碼