第七講差錯控制編碼課件

現(xiàn)代通信原理

2010.9~2011.1現(xiàn)代通信原理

2010.9~2011.1主要內(nèi)容差錯編碼的概念差錯控制的基本方法線性分組碼的概念及基本原理漢明碼循環(huán)碼BCH碼交織的概念為什么要進行差錯編碼？差錯控制的幾種基本方法各有何優(yōu)缺點？如何構(gòu)造一個漢明碼？如何構(gòu)造循環(huán)碼？如何構(gòu)造BCH碼？為什么要采用交織？主要內(nèi)容差錯編碼的概念為什么要進行差錯編碼？研究對象研究對象在數(shù)字通信系統(tǒng)中的位置研究對象研究對象在數(shù)字通信系統(tǒng)中的位置3差錯控制為什么要采用差錯控制噪聲所導致的傳輸差錯與信息可靠傳輸需求的矛盾在普通通信設(shè)備中，噪聲是不可消除的此外，碼間串擾（ISI），多接入干擾（MAI）和鄰小區(qū)干擾（ICI）等均可能導致誤碼匹配濾波，最佳判決等手段均不可能消除差錯問題：是否可能實現(xiàn)可靠傳輸？或者至少降低傳輸?shù)牟铄e率？解決問題的方法：差錯控制差錯控制為什么要采用差錯控制差錯控制的基本方法三種基本方法反饋檢驗檢錯重發(fā)ARQ前向糾錯FEC反饋檢驗——最原始的差錯控制需要雙向信道，和前向信道有相同的通信容量引入較大的停頓，不實時反饋信道可靠時，可以糾正任何錯誤差錯控制的基本方法三種基本方法差錯控制的基本方法檢錯重發(fā)——網(wǎng)絡(luò)常用的方式差錯判決放在接收端，只反饋差錯狀態(tài)自動請求重發(fā)，有效減少反饋量同樣難以適用于實時業(yè)務(wù)多種實現(xiàn)方式——停發(fā)等候、返回重發(fā)、選擇重發(fā)差錯控制的基本方法檢錯重發(fā)——網(wǎng)絡(luò)常用的方式差錯控制的基本方法前向糾錯FEC無需反饋信道直接在接收端對錯誤進行糾正，發(fā)端無需知道錯誤的狀態(tài)適用于實時業(yè)務(wù)無需重傳，發(fā)端不用存儲，收端即時解碼，發(fā)送的速率恒定依靠糾錯編碼——信道編碼通過在碼流中引入有結(jié)構(gòu)的冗余信息，糾正在傳輸中出現(xiàn)的錯誤差錯控制的基本方法前向糾錯FEC信道編碼一個簡單的例子對稱二進制信道BSC1個比特，只傳1次，差錯概率1個比特，重復(fù)傳送3次，接收端做多數(shù)判決，錯誤概率付出或代價：增加了傳輸?shù)娜哂啵档土藗鬏數(shù)男适杖牖蛟鲆妫禾岣吡藗鬏數(shù)目煽啃?，降低了誤碼率信道編碼一個簡單的例子付出或代價：增加了傳輸?shù)娜哂?，降低了傳信道編碼概念ChannelCoding：通過合理的增加冗余信息，糾正信道傳輸中可能出現(xiàn)的錯誤，也稱為糾錯碼：ErrorCorrectionCoding信道編碼的評價標準糾錯性能——能糾正什么樣的錯誤？能糾正多少錯誤？最終的誤比特率性能如何？代價——增加了多少冗余的比特？信息比特占整個碼流的百分比即碼率如何？糾錯碼的理論基礎(chǔ)基于代數(shù)理論的結(jié)構(gòu)，便于譯碼信道編碼概念信道編碼重要性信息系統(tǒng)不可或缺的重要技術(shù)移動通信深空通信與探測可靠計算存儲設(shè)備…信道編碼重要性信道編碼的分類按功能分檢錯碼：僅能檢錯糾錯碼：僅能糾錯按信息碼元和監(jiān)督碼元之間的校驗關(guān)系分線性碼：監(jiān)督碼元與信息碼元之間線性關(guān)系非線性碼：監(jiān)督碼元與信息碼元之間非線性關(guān)系按信息碼元和監(jiān)督碼元之間的約束方式分分組碼：監(jiān)督碼元僅與當前碼組相關(guān)卷積碼：監(jiān)督碼元與當前及以前碼組都有關(guān)系按照信息碼元在編碼后是否保持原來形式系統(tǒng)碼：信息碼元編碼后不變非系統(tǒng)碼：信息碼元改變信道編碼的分類按功能分信道編碼的香農(nóng)定理有擾離散信道的編碼定理存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到編碼器的二進制碼元速率），則一定存在一種編碼方式，使編碼的錯誤概率隨著碼長n的增加將按指數(shù)下降到任意小的值兩個結(jié)論如碼長及發(fā)送信息速率一定，可以通過增大信道容量，使錯誤概率減小如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯誤概率減小給出了努力的方向，但怎么做？信道編碼的香農(nóng)定理有擾離散信道的編碼定理給出了努力的方向，但信道編碼的基本原理看一個例子如用三位二進制編碼來代表八個字母

000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H

不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤如用三位二進制碼傳四個字母

000 A 011 B 101 C 110 D發(fā)生一位錯誤，準用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。信道編碼的基本原理看一個例子信道編碼的基本原理如用三位二進制碼傳二個字母

000 A 111 B 檢兩個錯誤，糾正一個錯誤。結(jié)論具有檢錯或糾錯的碼組，其所用的比特數(shù)必須大于信息碼組原來的比特數(shù)，引入冗余度；引入的冗余必須具有一定的結(jié)構(gòu)，才能進行檢錯及糾錯信道編碼的基本原理如用三位二進制碼傳二個字母信道編碼的基本原理幾個基本概念碼字二進制序列碼重(weight)一個碼組中“1”的數(shù)目碼距(distance)

兩個碼組之間對應(yīng)位置上1、0不同的位數(shù) 又叫漢明(Hamming)距

10110碼重：3 01100 碼重：2 碼距：3信道編碼的基本原理幾個基本概念信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系考慮碼字000錯成001，Hamming距1，概率錯成101，Hamming距2，概率錯成111，Hamming距3，概率總結(jié)兩個碼字的Hamming距離越大，則一個碼字誤判成另一個碼字的可能性越小碼距與檢錯、糾錯能力緊密相關(guān)信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系先考慮檢測碼字是否出錯？——可檢測e個誤碼一個碼字出錯后不會變成另一個正確的碼字，即可判斷出錯；如果一個碼字內(nèi)出現(xiàn)e個錯誤，則正確碼字之間的間距必須大于e信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系考慮單個碼字的糾錯——可糾正t個錯誤碼字出現(xiàn)t個錯誤仍能正確判別的原則是：其他碼字的各種錯誤情況不會進入到本碼字t為半徑的圓內(nèi)；其他碼字可能的最大圓的半徑也為t，則要求正確碼字之間的碼距大于2t信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系考慮既檢錯又糾錯——檢測e個錯誤，糾t個錯誤檢測e個錯誤，要求碼字間距大于e考慮糾t個錯誤，則此時間距要考慮的不是正確碼字之間的距離。而是正確碼字和可能的錯誤碼字之間的距離，所以在檢錯基礎(chǔ)上還需要加t信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系總結(jié)在一個碼組內(nèi)檢測e個誤碼，則要求最小的碼間距在一個碼組內(nèi)糾正t個誤碼，則要求的最小碼間距在一個碼組內(nèi)糾正t個錯誤，同時檢測e個錯誤，則要求的最小碼間距信道編碼的基本原理檢錯和糾錯能力與碼距的關(guān)系信道編碼的基本原理信道編碼的準則可靠性準則——能糾正更多的錯誤最大化最小碼距有效性準則給出盡可能多的需用碼字碼率盡可能高碼率k/n，k為信息位數(shù)，n為總碼長信道編碼的基本原理信道編碼的準則分組碼概念編碼后的碼元序列每n為分為一組，其中k個信息碼元，r個附加的監(jiān)督碼元，而且監(jiān)督碼元僅與本組的信息碼元有關(guān)，而與其他碼組的的信息碼元無關(guān)二進制序列分段，每段k個，針對每段按照一定規(guī)則附加r個監(jiān)督碼元分組碼的優(yōu)點容易以系統(tǒng)的數(shù)學理論進行建模分析實現(xiàn)電路簡單，復(fù)雜度低線性分組碼信息碼元和監(jiān)督碼元之間的關(guān)系可以用線性方程表示分組碼概念分組碼檢錯分組碼的例子奇偶監(jiān)督碼偶監(jiān)督奇監(jiān)督如果以上關(guān)系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)個錯誤，但不能檢測偶數(shù)個錯誤。最小碼距為dmin=2檢錯能力不高分組碼檢錯分組碼的例子分組碼水平奇偶監(jiān)督碼將碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時按列的順序傳送，接收時仍將碼字排列成發(fā)送時方陣形式，然后按行進行奇偶校驗在不增加冗余度時，不僅能發(fā)現(xiàn)某一行上奇數(shù)個錯誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯誤沒有增加冗余度，但通過增加碼長提高了檢錯能力最小碼距dmin=2分組碼水平奇偶監(jiān)督碼24線性分組碼概念信息碼元和監(jiān)督碼元可以使用線性方程聯(lián)系主要性質(zhì)任意兩個需用碼組之和（模2和）仍為需用碼組最小碼距為非零碼的最小碼重先看一個例子構(gòu)造一個（7，4）線性分組碼，能糾正1位錯誤1位錯誤可能出現(xiàn)在7個碼位中的任何一位上，錯誤的情形有7種，加上無錯，共8種狀態(tài)需要知識構(gòu)造3位校正子，共8種組合，正好可以指示7種錯誤和無錯的狀態(tài) 線性分組碼概念線性分組碼任意設(shè)計一種錯誤位置和校正子的對應(yīng)關(guān)系由上表得到校正子與各碼元關(guān)系線性分組碼任意設(shè)計一種錯誤位置和校正子的對應(yīng)關(guān)系26線性分組碼由校正子關(guān)系確定編碼方程，保證無誤碼及校正子為000，并由此解出監(jiān)督碼元的編碼方程由此得到許用碼組最小碼距3糾1個錯檢2個錯線性分組碼由校正子關(guān)系確定編碼方程，保證無誤碼及校正子為00線性分組碼糾錯對錯誤碼組計算校正子，根據(jù)校正子與錯誤位置的對應(yīng)關(guān)系糾正錯誤 接收到的碼字為1101110，計算校正子為100，對應(yīng)錯誤位置為3，則譯碼輸出為1100110線性分組碼糾錯線性分組碼線性系統(tǒng)分組碼的矩陣表示編碼過程編碼過程可以看成信息序列與一個矩陣的相乘，這個矩陣成為生成矩陣（n，k）線性分組碼，A為n維行向量，X為信息序列構(gòu)成的k維行向量，I為kXk的單位矩陣，Q為kXr的矩陣典型形式的生成矩陣，生成的一定是系統(tǒng)碼線性分組碼線性系統(tǒng)分組碼的矩陣表示線性分組碼線性系統(tǒng)分組碼的矩陣表示檢錯的矩陣表示出錯的條件監(jiān)督矩陣線性分組碼線性系統(tǒng)分組碼的矩陣表示線性分組碼線性系統(tǒng)分組碼的矩陣表示校正子計算的矩陣表示接收信號的表示校正子的計算——校正子與錯誤圖樣有確定的關(guān)系糾錯：根據(jù)錯誤圖樣與校正子的關(guān)系確定錯誤位置進行糾正線性分組碼線性系統(tǒng)分組碼的矩陣表示線性分組碼線性系統(tǒng)分組碼的矩陣表示校正子與誤碼位置的關(guān)系對于糾1比特錯誤的校正子（以書11-24的校驗矩陣為例）按上述矩陣方式構(gòu)成的線性系統(tǒng)分組碼的監(jiān)督矩陣的每列實際上是按照碼字順序給出了每個比特的校驗子！線性分組碼線性系統(tǒng)分組碼的矩陣表示按上述矩陣方式構(gòu)成的線性系線性分組碼利用矩陣構(gòu)造線性系統(tǒng)分組碼第一個問題：先構(gòu)造生成矩陣還是監(jiān)督矩陣？回顧第一個例子，監(jiān)督矩陣確定了如何糾錯，是構(gòu)造者自己確定的，是根本，因此先確定監(jiān)督矩陣線性系統(tǒng)碼的監(jiān)督矩陣的形式是確定的，要確定的是QQ的列確定了信息位的校驗子（可任意確定，各列不同，且須與I中的列不同），I確定了監(jiān)督位的校驗子線性分組碼利用矩陣構(gòu)造線性系統(tǒng)分組碼線性分組碼利用矩陣構(gòu)造線性系統(tǒng)分組碼第二步：由監(jiān)督矩陣得到生成矩陣第三步：由生成矩陣可得許用碼組線性分組碼利用矩陣構(gòu)造線性系統(tǒng)分組碼線性分組碼線性分組碼的分析——（n.k）中n和k如何確定只考慮糾正一位錯誤線性分組碼的基本思想：用校正子指示錯誤位置校正子有r位，可以指示的錯誤圖樣線性分組碼碼長為n位，如果只考慮一位錯誤，共有錯誤情況n種，還需要一種指示用于表征沒出錯，共需指示n+1種情況能夠糾正1位錯誤需要滿足的關(guān)系式等號成立時的特殊情況的碼稱為漢明碼線性分組碼線性分組碼的分析——（n.k）中n和k如何確定等線性分組碼線性分組碼的分析考慮糾正t位錯誤按照同樣的分析，可得到信息碼元的位數(shù)（d為最小碼距）線性分組碼存在的界——吉爾伯特界漢明界，r的最小值普洛特金界，k的最大值吉爾伯特界，r的最大值線性分組碼線性分組碼的分析漢明界，r的最小值普洛特金界，k的線性分組碼漢明碼（hanming）能糾正單個錯誤的線性分組碼碼長監(jiān)督碼位信息碼位最小碼距碼率線性分組碼漢明碼（hanming）循環(huán)碼概念是一種線性分組碼，通常是系統(tǒng)碼具有循環(huán)性質(zhì)，即需用碼組經(jīng)過若干位的循環(huán)移位后仍未需用碼組實現(xiàn)簡單，可用帶反饋的移位寄存器實現(xiàn)糾錯能力強，可糾正突發(fā)錯誤循環(huán)碼的數(shù)學描述方式多項式矩陣二元域上的預(yù)算：加法和乘法，注意與普通的數(shù)學上的多項式運算的不同循環(huán)碼概念循環(huán)碼循環(huán)碼的循環(huán)性循環(huán)碼的多項式表示循環(huán)碼循環(huán)碼的循環(huán)性循環(huán)碼循環(huán)碼的循環(huán)性左移一位與循環(huán)碼的多項式表示相比較，上式顯然不能表示一個循環(huán)碼組，對這一表達式進行變形余式可以表示一個新的碼字，是循環(huán)左移一位形成的新的碼字循環(huán)碼循環(huán)碼的循環(huán)性余式可以表示一個新的碼字，是循環(huán)左移一位循環(huán)碼循環(huán)碼的循環(huán)性左移k位的情況按循環(huán)碼的循環(huán)特性，新的碼字可以描述為按照二指域的多項式計算驗證上式循環(huán)碼循環(huán)碼的循環(huán)性循環(huán)碼循環(huán)碼的循環(huán)性循環(huán)性的一般描述循環(huán)碼的構(gòu)造信息碼組的多項式表示為M(D)，則循環(huán)碼編碼后的碼組多項式為g(D)為生成多項式g(D)是n-k階多項式G(D)能被整除循環(huán)碼循環(huán)碼的循環(huán)性循環(huán)碼循環(huán)碼的構(gòu)造生成多項式每一個g(D)對應(yīng)一個循環(huán)碼，階數(shù)低于n且能被g(D)整除的一組多項式就構(gòu)成一個循環(huán)碼循環(huán)碼（n,k)的構(gòu)造：給定g(D)，根據(jù)g(D)的階數(shù)確定M(D)的最高階數(shù)，所有M(D)和g(D)相乘得到的就是循環(huán)碼的許用碼組g(D)尋找：的因式——保證循環(huán)性循環(huán)碼循環(huán)碼的構(gòu)造循環(huán)碼循環(huán)碼的構(gòu)造一個例子循環(huán)碼循環(huán)碼的構(gòu)造循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣非系統(tǒng)碼！如何變成系統(tǒng)碼？循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣非系統(tǒng)碼！循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣系統(tǒng)循環(huán)碼的矩陣形式應(yīng)該什么樣子？？G(D)如何構(gòu)造，保證循環(huán)性？循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣？G(D)如何構(gòu)造，保證循環(huán)循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣考慮系統(tǒng)碼的碼多項式如果生成多項式為g(D)，由循環(huán)碼的生成規(guī)則可知g(D)和r(D)的階數(shù)相同，則按照二值域上的運算規(guī)則有考慮k個特殊的信息碼字，即只有一個1的k個特殊碼字有對應(yīng)的監(jiān)督碼多項式由此，生成矩陣的每行對應(yīng)的碼多項式就是我們希望的！循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣就是我們希望的！循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣總結(jié)系統(tǒng)碼的生成矩陣根據(jù)g(D)求各行r(D);由各行r(D)，根據(jù)標準形式寫出生成矩陣系統(tǒng)碼的監(jiān)督矩陣循環(huán)碼循環(huán)碼的生成矩陣和監(jiān)督矩陣循環(huán)碼系統(tǒng)循環(huán)碼的編碼器系統(tǒng)循環(huán)碼的碼多項式只需要求出r(D)系統(tǒng)循環(huán)碼的編碼可以采用多項式長除的方法，利用線性反饋移位寄存器實現(xiàn)循環(huán)碼系統(tǒng)循環(huán)碼的編碼器循環(huán)碼循環(huán)碼的譯碼定義誤差多項式校正子的定義和計算和編碼一樣，可用反饋移位寄存器循環(huán)碼循環(huán)碼的譯碼和編碼一樣，可用反饋移位寄存器循環(huán)碼循環(huán)碼的譯碼由校正子確定錯誤圖樣例如：對于1位錯誤，如錯誤在第i位，則校正子為譯碼結(jié)果循環(huán)碼循環(huán)碼的譯碼循環(huán)碼循環(huán)碼的譯碼循環(huán)碼循環(huán)碼的譯碼BCH碼上述循環(huán)碼有一個問題沒有講？循環(huán)碼的碼距循環(huán)碼是線性分組碼，線性分組碼的碼距的求解方法可以直接應(yīng)用碼距和生成多項式的關(guān)系如何？確定碼距后能否快速確定生成多項式？BCH碼的特點BCH碼是循環(huán)碼具有糾多個隨機錯誤的能力構(gòu)造容易由碼的最小距離，可以很快得到碼的生成多項式BCH碼上述循環(huán)碼有一個問題沒有講？BCH碼本原BCH碼碼長為生成多項式最小碼距

LCM：最小公倍數(shù)：最小多項式由碼長及碼距可快速確定生成多項式BCH碼本原BCH碼LCM：最小公倍數(shù)由碼長及碼距可快速確定線性分組碼的擴展與縮短線性分組碼的擴展在原有碼組基礎(chǔ)上增加一位校驗位，對所有碼字進行校驗，碼距增加1擴展線性分組碼的監(jiān)督矩陣擴展循環(huán)碼的生成多項式線性分組碼的擴展與縮短線性分組碼的擴展線性分組碼的擴展與縮短縮短線性分組碼(n,k)線性分組碼的碼長和信息位同時縮短s位，形成新的(n-s,k-s)分組碼為縮短線性分組碼縮短線性分組碼的監(jiān)督矩陣：去掉元監(jiān)督矩陣的前s列即可線性分組碼的擴展與縮短縮短線性分組碼交織編碼為什么要采用交織？前述的線性分組碼只能糾正零散隨機錯誤通信系統(tǒng)中往往存在不可抗拒的突發(fā)錯誤無線信道的衰落引起的誤碼突發(fā)強干擾引起的錯誤…如何對抗突發(fā)的的錯誤思想：將突發(fā)錯誤化解為零散的錯誤交織編碼交織編碼為什么要采用交織？交織編碼交織的基本思想交織編碼交織的基本思想交織編碼交織編碼的基本原理為了對付突發(fā)的信道差錯，交織器改變發(fā)送碼元的時間順序?qū)⒃鞠噜彽拇a元在時間上的距離最大化時間上相鄰的突發(fā)錯誤屬于不同的碼組，可分別糾錯交織編碼交織編碼的基本原理交織編碼交織碼的糾錯能力交織碼的結(jié)構(gòu)——碼組方陣行：分組碼的一個碼組列：交織的深度i糾錯能力分組碼：糾正t個隨機錯誤——交織碼：糾正tXi個突發(fā)錯誤分組碼：糾正b個突發(fā)錯誤——交織碼：糾正bXi個突發(fā)錯誤交織編碼交織碼的糾錯能力交織編碼交