分組碼與卷積信道碼ppt課件

1、分組碼與卷積信道碼分組碼與卷積信道碼讀書報告讀書報告專業(yè)：通信與信息系統(tǒng)學號：0820190087姓名：顧杰第八章：分組碼與卷積信道碼第八章：分組碼與卷積信道碼l本章主要內(nèi)容：l 1、線性分組碼l 2、卷積碼l 3、*帶限信道的編碼調(diào)制-網(wǎng)格編碼調(diào)制什么是線性分組碼？ 若編碼規(guī)則僅局限在本碼組之內(nèi)，即本碼組的校驗元僅與本碼組的信息元相關(guān)，則稱這類碼為分組碼。 對于分組碼，如果校驗元和信息元的關(guān)系是一種線性關(guān)系，即能夠用一線性代數(shù)方程表示，那么稱這種分組碼為線性分組碼。線性分組碼的表示 線性分組碼一般用符號(n, k)表示，其中n為碼字的長度，k為每個碼字中信息碼元的數(shù)目。 定義 為線性分組碼的

2、碼率 ，即nkcRnkRc線性分組碼的基本特性 設(shè) 是某(n, k)分組碼的任意兩個碼字，這兩個碼字的差別是用對應(yīng)元素上不相同元素的個數(shù)來衡量的，這種度量稱為碼字間的Hamming 間隔，記作 。 個碼字集合中的最小值稱為該碼的最小Hamming距離，用 表示。 定義一個碼字中所有非零元素的個數(shù)為該碼字的Hamming重量。線性分組碼的最小Hamming距離等于最小Hamming重量。jiCC ,ijdkM2mind線性分組碼的生成矩陣和奇偶校驗矩陣 在(n, k)線性分組碼中，假設(shè) 為編碼器的輸入信息碼元序列， 為編碼器的輸出序列，則編碼器的輸入輸出關(guān)系可以表示為： 式中，G為該線性分組碼的

3、生成矩陣。 任何矩陣都可以表示成生成矩陣行向量的線性組合。生成矩陣可化成“系統(tǒng)形式”：21mkmmmxxxX21mnmmmcccCGXCmmkknkkknknkpppppppppPIG212222111211100000100001線性分組碼的生成矩陣和奇偶校驗矩陣 校驗矩陣常用符號H表示，一種碼的校驗矩陣等于該碼的對偶碼的生成矩陣，因此對于(n, k) 線性分組碼，它的校驗矩陣H和生成矩陣G滿足 這里的0代表一個由全零元素組成的 維矩陣。 假定(n, k) 線性分組碼是系統(tǒng)碼，則其校驗矩陣可表示為： 式中 為P的轉(zhuǎn)置矩陣。 )(knkknTIPHTP0HG幾種特殊的線性分組碼lHamming

4、碼lHadamard碼lGolay碼循環(huán)碼 在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它除了具有線性分組碼的一般特點外，還具有循環(huán)性：循環(huán)碼中任一碼字的碼元循環(huán)移位左移或右移后仍是該碼的一個碼字。其編碼和譯碼的電路較簡單，且檢、糾錯能力較強，目前已成為研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。循環(huán)碼 理論研究時常用多項式來表示循環(huán)碼，即有： 式中： 為循環(huán)碼的任一碼字。對于二進制碼，多項式的每個系數(shù)不是0就是1。 可以用一個n-k次的生成多項式 產(chǎn)生一個循環(huán)碼。(n, k)循環(huán)碼的生成多項式一定是多項式 的因子，其通式為：012211)(cpcpcpcpCnnnn0121ccccCn

5、n)(pg) 1(np1)(111pgpgppgknknkn循環(huán)碼 定義一個消息多項式 如下： 這里 代表k位信息比特。則由該k位信息比特生成的碼字為： 可以證明上式滿足循環(huán)特性。 BCH是循環(huán)碼中一種重要的碼型，能夠糾正多比特錯誤。)(pX012211)(xpxpxpxpXkkkk0121xxxxkk)()()(pgpXpCmm)22 , 1(km線性分組碼的最佳軟判決譯碼 線性分組碼的最佳軟判決譯碼是通過使用匹配率濾波器作為最佳接收機并后接一個譯碼器實現(xiàn)的，譯碼器用來生成與M種碼字對應(yīng)的M個判決變量。 令 表示發(fā)送任一指定碼字后匹配濾波器的n個輸出取樣。假設(shè)信號采用BPSK傳輸，則當碼字的

6、第j比特是1時： 當碼字的第j比特是0時： 其中 表示傳輸碼字的一個比特所需的信號能量，變量 表示取樣瞬間的高斯白噪聲。 ), 2 , 1(njrjjcjnrjcjnrcjn線性分組碼的最佳軟判決譯碼 根據(jù)已知的M中可能發(fā)送的碼字和接收到 值，最佳譯碼器形成M個相關(guān)度： 式中：便是第i個碼字第j個位置上的比特。最佳譯碼器選擇相關(guān)度均值最大的碼字作為譯碼輸出。 最佳軟判決譯碼的算法比較簡單，但當碼字數(shù)量很大時計算量就會變得無法接受，巨大的計算量降低了其在工程中適用度。 jrjnjijiircCrCCM) 12(),(1),2 , 1(Mi線性分組碼的硬判決譯碼 針對軟判決譯碼巨大的計算量，硬判決

7、譯碼將模擬樣值量化，然后用數(shù)字方式實現(xiàn)譯碼，這種方法的一種實現(xiàn)方式是最小距離譯碼，也稱最大似然譯碼。 譯碼方案：來自解調(diào)器的與接收碼字對應(yīng)的n個比特被送往譯碼器，譯碼器將接收的碼字和M種可能發(fā)送的碼字進行比較，把與接收碼字漢明距離最小的判決為譯碼碼字。線性分組碼的硬判決譯碼 使用校驗矩陣H是一種有效的硬判決譯碼方法。假定 是發(fā)送碼字，Y是解調(diào)器輸出的接收碼字，一般Y可以表示為： 其中，e代表一個任意的二進制差錯矢量，那么 式中，(n-k)維矢量S叫做差錯圖案的伴隨式。由于S, H, Y是可知的，所以最終可以求出發(fā)送碼字 。 mCeCYmSeHeHHCHeCYHTTTmTmT)(mC硬判決譯碼和

8、軟判決譯碼的性能比較l軟判決譯碼和硬判決譯碼碼字差錯概率比較l 軟判決譯碼差錯概率上邊界：l 硬判決譯碼差錯概率精確值：l 在 范圍內(nèi)，硬判決譯碼和軟判決譯碼的碼字差錯概率性能約相差2dB，且軟判決譯碼性能較好。)2lnexp()2() 1(minminkdRdRQMPcbcbMmmmmmmMppmppmP233023234)1 (231)1 (23621010MP硬判決譯碼和軟判決譯碼的性能比較l軟判決譯碼和硬判決譯碼單位比特最小信噪比 比較l 在碼率 趨近于零的極限時，硬判決譯碼和軟判決譯碼的信噪比 值相差約為2dB。隨著碼率的增大，兩種譯碼技術(shù)的單位比特最小信噪比 差值越來越小，當 時，

9、差值約為1.5dB。cRbbb8 . 0cR卷積碼的定義 線性碼分為分組碼和卷積碼，卷積碼又稱連環(huán)碼，由埃里亞斯于1955年首次提出。 若本碼組的校驗元不僅與本碼組的信息元相關(guān)，而且還與本碼組相鄰的前幾個碼組的信息元相關(guān)，則稱這類碼為卷積碼。 卷積碼的表示 卷積碼一般用符號 表示，稱m為編碼存貯，它表示輸入信息子組在編碼器中滯留的單元時間；稱m+1為編碼約束度，表示編碼過程中相互約束的子碼個數(shù)；稱 為編碼約束長度，表示編碼過程中互相約束的碼元個數(shù)。 ),(00mkn0) 1(nm 卷積碼的描述方法l解析表示法l 1、離散卷積法l 2、生成矩陣法l 3、碼多項式法l圖形表示法l 1、樹圖法l 2

10、、網(wǎng)格圖法l 3、狀態(tài)圖法卷積碼的樹圖表示碼率為1/3，K=3卷積碼的樹圖卷積碼的網(wǎng)格圖和狀態(tài)圖表示110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100abcd000111101110010011100001碼率為1/3，K=3卷積碼的網(wǎng)格圖碼率為1/3，K=3卷積碼的狀態(tài)圖卷積碼的編碼編碼輸出每次輸入k比特1k1k1k1k 1 k2k3kNk 12nNk級移存器n個模2加法器每輸入k比特旋轉(zhuǎn)1周卷積碼編碼器卷積碼的譯碼l卷積碼有三種主要的譯碼方法：序

11、列譯碼、門限譯碼和最大似然譯碼。1957年伍成克拉夫(Wozencraft)提出了一種有效的譯碼方法，即序列譯碼。1963年梅西(Massey)提出了一種性能稍差，但比較實用的門限譯碼方法。1967年維特比(Viterbi)提出了最大似然譯碼法，它又稱為維特比譯碼。門限譯碼是一種代數(shù)譯碼法，序列譯碼和維特比最大似然譯碼都是概率譯碼。l代數(shù)譯碼利用編碼本身得代數(shù)結(jié)構(gòu)進行解碼，并不考慮信道的統(tǒng)計特性。比如門限譯碼，它以分組碼理論為基礎(chǔ)，其主要特點是算法簡單，易于實現(xiàn)，但是它的誤碼性能要比概率譯碼差。它的譯碼方法是從線性碼的監(jiān)督子出發(fā)，找到一組特殊的能夠檢查信息位置是否發(fā)生錯誤的方程組，從而實現(xiàn)糾錯

12、譯碼。l概率譯碼的基本思想是：把已經(jīng)接收到的序列與所有可能的發(fā)送序列相比較，選擇其中漢明距離最小的一個序列作為發(fā)送序列。維特比譯碼是目前用得較多的一種譯碼方法。它是一種最大似然譯碼，其譯碼的復(fù)雜性均隨m按指數(shù)增長。最大似然譯碼對存儲器級數(shù)較小的卷積碼很容易實現(xiàn)，被廣泛地應(yīng)用于現(xiàn)代通信中。隨著大規(guī)模集成電路技術(shù)的發(fā)展，對存儲器級數(shù)較大的卷積碼也可以采用最大似然譯碼。目前維特比譯碼已經(jīng)得到了廣泛的應(yīng)用。卷積碼的最佳譯碼-維特比算法 不像分組碼那樣有固定的長度n，卷積碼基本是一個有限狀態(tài)機，因此它的最佳譯碼器是一個最大似然序列估計器。卷積碼的譯碼就是遍歷網(wǎng)格圖找出最可能的序列。根據(jù)解調(diào)器后的譯碼器執(zhí)

13、行軟判決或硬判決，遍歷網(wǎng)格圖時所用的度量可以是Hamming距離，也可以是歐氏距離。 維特比譯碼算法的實現(xiàn)l基本原理：譯碼器將接收到的序列和所有可能的發(fā)送序列作比較，選擇其中漢明距離最小的序列當作是現(xiàn)在的發(fā)送序列。l例：假設(shè)卷積碼為(n , k, m) = (3, 1, 2)碼l 現(xiàn)在的發(fā)送信息位為1101l為了使移存器中的信息位全部移出，在信息位后面加入了3個“0”，即1101000l編碼后的發(fā)送序列：111 110 010 100 001 011 000l接收序列：111 010 010 110 001 011 000 (紅色為錯碼)l對于 (3, 1, 2)卷積碼，發(fā)送序列的約束長度 ，

14、 所以首先需考察3個信息段，即考察接收序列的前3n=9位“111 010 010”。31 mN維特比譯碼算法的實現(xiàn)l解碼第1步l由網(wǎng)格圖可見，沿路徑每一級有4種狀態(tài)a, b, c和d。每種狀態(tài)只有兩條路徑可以到達。故4種狀態(tài)共有8條到達路徑。l比較網(wǎng)格圖中的這8條路徑和接收序列之間的漢明距離。例如，由出發(fā)點狀態(tài)a經(jīng)過3級路徑后到達狀態(tài)a的兩條路徑中上面一條為“000 000 000”。它和接收序列“111 010 010的漢明距離等于5；下面一條為“111 001 011”,它和接收序列的漢明距離等于3。110110110110011011011010010010101101101001001

15、001001abcdabcd000000000000000111111111111111100100100維特比譯碼算法的實現(xiàn)l將這8個比較結(jié)果列表如下：l比較到達每個狀態(tài)的兩條路徑的漢明距離，將距離小的一條路徑保留，稱為幸存路徑。這樣，就剩下4條路徑了，即表中第2, 4, 6和8條路徑。 是4111 110 101abdd8否6000 111 110aabd7是1111 110 010abdc6否7000 111 001aabc5是4111 001 100abcb4否6000 000 111aaab3是3111 001 011abca2否5000 000 000aaaa1幸存否？漢明距離對應(yīng)

16、序列途徑序號維特比譯碼算法的實現(xiàn)l解碼第2步：繼續(xù)考察接收序列中的后繼3個比特“110” l計算4條幸存路徑上增加1級后的8條可能路徑的漢明距離。計算結(jié)果列于下表中。 l表中總距離最小為2，其路徑是abdc+b，相應(yīng)序列為111 110 010 100。它和發(fā)送序列相同，故對應(yīng)發(fā)送信息位1101。 否62dd4abdd+d8是40bd4abcb+d7是51dc4abdd+c6否73bc4abcb+c5是21cb1abdc+b4否41ab3abca+b3是32ca1abdc+a2否52aa3abca+a1幸存否？總距離新增距離新增路徑段原幸存路徑的距離途徑序號維特比譯碼算法的實現(xiàn)l按照上表中的幸

17、存路徑畫出的網(wǎng)格圖示于下圖中。l圖中粗線路徑是距漢明離最小(等于2)的路徑。abcd011010010101001abcd111100100110110維特比譯碼算法的實現(xiàn)l在編碼時，信息位后面加了3個“0”。若把這3個“0仍然看作是信息位，則可以按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。圖中的粗線仍然是漢明距離最小的路徑。 110011010010101101001001abcdabcd000 111100100000 011011001101維特比譯碼算法的實現(xiàn)l若已知這3個碼元是為結(jié)尾而補充的）“0”，則在解碼時就預(yù)先知道在接收這3個“0碼元后，路徑必然應(yīng)該回到狀態(tài)a。而

18、由圖可見，l由于只有兩條路徑可以回到a狀態(tài)，所以這時上圖可以簡化成：1 100 110 100 101 011 010 010 01abcdabcd0 00 1 111 001 000 00 0 110 110 011 011 100 110 100 101 011 010 010 01abcdabcd0 00 1 111 001 000 00 0 110 110 01維特比譯碼算法的實現(xiàn)l在上例中卷積碼的約束長度為N = 3，需要存儲和計算8條路徑的參量。l由此可見，維特比算法的復(fù)雜度隨約束長度N按指數(shù)形式 增長。故維特比算法適合約束長度較小 的編碼。對于約束長度大的卷積碼，可以采用其他解碼算法。N2)10(N卷積碼軟判決譯碼的差錯概率 加性高斯白噪聲信道中使用軟判決譯碼時維特比算法的差錯概率性