第七講差錯控制編碼ppt課件

1、現(xiàn)代通信原理2010.92011.1,主要內容,差錯編碼的概念 差錯控制的基本方法 線性分組碼的概念及基本原理 漢明碼 循環(huán)碼 BCH碼 交織的概念,為什么要進行差錯編碼？ 差錯控制的幾種基本方法各有何優(yōu)缺點？ 如何構造一個漢明碼？ 如何構造循環(huán)碼？ 如何構造BCH碼？ 為什么要采用交織,研究對象,研究對象在數(shù)字通信系統(tǒng)中的位置,差錯控制,為什么要采用差錯控制 噪聲所導致的傳輸差錯與信息可靠傳輸需求的矛盾 在普通通信設備中，噪聲是不可消除的 此外，碼間串擾（ISI），多接入干擾（MAI）和鄰小區(qū)干擾（ICI）等均可能導致誤碼 匹配濾波，最佳判決等手段均不可能消除差錯 問題：是否可能實現(xiàn)可靠傳輸

2、？或者至少降低傳輸?shù)牟铄e率？ 解決問題的方法：差錯控制,差錯控制的基本方法,三種基本方法 反饋檢驗 檢錯重發(fā)ARQ 前向糾錯FEC 反饋檢驗最原始的差錯控制 需要雙向信道，和前向信道有相同的通信容量 引入較大的停頓，不實時 反饋信道可靠時，可以糾正任何錯誤,差錯控制的基本方法,檢錯重發(fā)網(wǎng)絡常用的方式 差錯判決放在接收端，只反饋差錯狀態(tài) 自動請求重發(fā)，有效減少反饋量 同樣難以適用于實時業(yè)務 多種實現(xiàn)方式停發(fā)等候、返回重發(fā)、選擇重發(fā),差錯控制的基本方法,前向糾錯FEC 無需反饋信道 直接在接收端對錯誤進行糾正，發(fā)端無需知道錯誤的狀態(tài) 適用于實時業(yè)務 無需重傳，發(fā)端不用存儲，收端即時解碼，發(fā)送的速率

3、恒定 依靠糾錯編碼信道編碼 通過在碼流中引入有結構的冗余信息，糾正在傳輸中出現(xiàn)的錯誤,信道編碼,一個簡單的例子 對稱二進制信道BSC 1個比特，只傳1次，差錯概率 1個比特，重復傳送3次，接收端做多數(shù)判決，錯誤概率,付出或代價：增加了傳輸?shù)娜哂?，降低了傳輸?shù)男?收入或增益：提高了傳輸?shù)目煽啃?，降低了誤碼率,信道編碼,概念 Channel Coding：通過合理的增加冗余信息，糾正信道傳輸中可能出現(xiàn)的錯誤，也稱為糾錯碼：Error Correction Coding 信道編碼的評價標準 糾錯性能能糾正什么樣的錯誤？能糾正多少錯誤？最終的誤比特率性能如何？ 代價增加了多少冗余的比特？信息比特占整

4、個碼流的百分比即碼率如何？ 糾錯碼的理論基礎 基于代數(shù)理論的結構，便于譯碼,信道編碼,重要性 信息系統(tǒng)不可或缺的重要技術 移動通信 深空通信與探測 可靠計算 存儲設備,信道編碼的分類,按功能分 檢錯碼：僅能檢錯 糾錯碼：僅能糾錯 按信息碼元和監(jiān)督碼元之間的校驗關系分 線性碼：監(jiān)督碼元與信息碼元之間線性關系 非線性碼：監(jiān)督碼元與信息碼元之間非線性關系 按信息碼元和監(jiān)督碼元之間的約束方式分 分組碼：監(jiān)督碼元僅與當前碼組相關 卷積碼：監(jiān)督碼元與當前及以前碼組都有關系 按照信息碼元在編碼后是否保持原來形式 系統(tǒng)碼：信息碼元編碼后不變 非系統(tǒng)碼：信息碼元改變,信道編碼的香農(nóng)定理,有擾離散信道的編碼定理

5、存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到編碼器的二進制碼元速率），則一定存在一種編碼方式，使編碼的錯誤概率隨著碼長n的增加將按指數(shù)下降到任意小的值 兩個結論 如碼長及發(fā)送信息速率一定，可以通過增大信道容量，使錯誤概率減小 如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯誤概率減小,給出了努力的方向，但怎么做,信道編碼的基本原理,看一個例子 如用三位二進制編碼來代表八個字母 000 A100E 001 B101F 010C110G 011D111H 不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤 如用三位二進制碼傳四個字母 000 A011B101 C11

6、0D 發(fā)生一位錯誤，準用碼字將變成禁用碼字，接收端就能知 道出錯，但是不能糾錯,信道編碼的基本原理,如用三位二進制碼傳二個字母 000 A111B 檢兩個錯誤，糾正一個錯誤。 結論 具有檢錯或糾錯的碼組，其所用的比特數(shù)必須大于信息碼組原來的比特數(shù)，引入冗余度； 引入的冗余必須具有一定的結構，才能進行檢錯及糾錯,信道編碼的基本原理,幾個基本概念 碼字 二進制序列 碼重(weight) 一個碼組中“1”的數(shù)目 碼距(distance) 兩個碼組之間對應位置上1、0不同的位數(shù) 又叫漢明(Hamming)距 10 1 1 0 碼重：3 01 1 00 碼重： 2 碼距：3,信道編碼的基本原理,檢錯和糾

7、錯能力與碼距的關系 考慮碼字000 錯成001，Hamming距1，概率 錯成101，Hamming距2，概率 錯成111，Hamming距3，概率 總結 兩個碼字的Hamming距離越大，則一個碼字誤判成另一個碼字的可能性越小 碼距與檢錯、糾錯能力緊密相關,信道編碼的基本原理,檢錯和糾錯能力與碼距的關系 先考慮檢測碼字是否出錯？可檢測e個誤碼 一個碼字出錯后不會變成另一個正確的碼字，即可判斷出錯； 如果一個碼字內出現(xiàn)e個錯誤，則正確碼字之間的間距必須大于e,信道編碼的基本原理,檢錯和糾錯能力與碼距的關系 考慮單個碼字的糾錯可糾正t個錯誤 碼字出現(xiàn)t個錯誤仍能正確判別的原則是：其他碼字的各種錯

8、誤情況不會進入到本碼字t為半徑的圓內； 其他碼字可能的最大圓的半徑也為t，則要求正確碼字之間的碼距大于2t,信道編碼的基本原理,檢錯和糾錯能力與碼距的關系 考慮既檢錯又糾錯檢測e個錯誤，糾t個錯誤 檢測e個錯誤，要求碼字間距大于e 考慮糾t個錯誤，則此時間距要考慮的不是正確碼字之間的距離。而是正確碼字和可能的錯誤碼字之間的距離，所以在檢錯基礎上還需要加t,信道編碼的基本原理,檢錯和糾錯能力與碼距的關系 總結 在一個碼組內檢測e個誤碼，則要求最小的碼間距 在一個碼組內糾正t個誤碼，則要求的最小碼間距 在一個碼組內糾正t個錯誤，同時檢測e個錯誤，則要求的最小碼間距,信道編碼的基本原理,信道編碼的準

9、則 可靠性準則能糾正更多的錯誤 最大化最小碼距 有效性準則 給出盡可能多的需用碼字 碼率盡可能高 碼率k/n，k為信息位數(shù)，n為總碼長,分組碼,概念 編碼后的碼元序列每n為分為一組，其中k個信息碼元，r個附加的監(jiān)督碼元，而且監(jiān)督碼元僅與本組的信息碼元有關，而與其他碼組的的信息碼元無關 二進制序列分段，每段k個，針對每段按照一定規(guī)則附加r個監(jiān)督碼元 分組碼的優(yōu)點 容易以系統(tǒng)的數(shù)學理論進行建模分析 實現(xiàn)電路簡單，復雜度低 線性分組碼 信息碼元和監(jiān)督碼元之間的關系可以用線性方程表示,分組碼,檢錯分組碼的例子 奇偶監(jiān)督碼 偶監(jiān)督 奇監(jiān)督 如果以上關系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)個錯誤，但不能檢

10、測偶數(shù)個錯誤。 最小碼距為 dmin=2 檢錯能力不高,分組碼,水平奇偶監(jiān)督碼 將碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時按列的順序傳送，接收時仍將碼字排列成發(fā)送時方陣形式，然后按行進行奇偶校驗 在不增加冗余度時，不僅能發(fā)現(xiàn)某一行上奇數(shù)個錯誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯誤 沒有增加冗余度，但通過增加碼長提高了檢錯能力 最小碼距dmin=2,線性分組碼,概念 信息碼元和監(jiān)督碼元可以使用線性方程聯(lián)系 主要性質 任意兩個需用碼組之和（模2和）仍為需用碼組 最小碼距為非零碼的最小碼重 先看一個例子 構造一個（7，4）線性分組碼，能糾正1位錯誤 1位錯誤可能出現(xiàn)在7個碼位中的任何一位上，錯誤

11、的情形有7種，加上無錯，共8種狀態(tài)需要知識 構造3位校正子，共8種組合，正好可以指示7種錯誤和無錯的狀態(tài),線性分組碼,任意設計一種錯誤位置和校正子的對應關系 由上表得到校正子與各碼元關系,線性分組碼,由校正子關系確定編碼方程，保證無誤碼及校正子為000，并由此解出監(jiān)督碼元的編碼方程 由此得到許用碼組 最小碼距3 糾1個錯 檢2個錯,線性分組碼,糾錯 對錯誤碼組計算校正子，根據(jù)校正子與錯誤位置的對應關系糾正錯誤 接收到的碼字為1101110，計算校正子為100，對應錯誤位置為3，則譯碼輸出為1100110,線性分組碼,線性系統(tǒng)分組碼的矩陣表示 編碼過程 編碼過程可以看成信息序列與一個矩陣的相乘，

12、這個矩陣成為生成矩陣 （n，k）線性分組碼，A為n維行向量，X為信息序列構成的k維行向量，I為kXk的單位矩陣，Q為kXr的矩陣 典型形式的生成矩陣，生成的一定是系統(tǒng)碼,線性分組碼,線性系統(tǒng)分組碼的矩陣表示 檢錯的矩陣表示 出錯的條件 監(jiān)督矩陣,線性分組碼,線性系統(tǒng)分組碼的矩陣表示 校正子計算的矩陣表示 接收信號的表示 校正子的計算校正子與錯誤圖樣有確定的關系 糾錯：根據(jù)錯誤圖樣與校正子的關系確定錯誤位置進行糾正,線性分組碼,線性系統(tǒng)分組碼的矩陣表示 校正子與誤碼位置的關系 對于糾1比特錯誤的校正子（以書11-24的校驗矩陣為例,按上述矩陣方式構成的線性系統(tǒng)分組碼的監(jiān)督矩陣的每列實際上是按照碼

13、字順序給出了每個比特的校驗子,線性分組碼,利用矩陣構造線性系統(tǒng)分組碼 第一個問題：先構造生成矩陣還是監(jiān)督矩陣？ 回顧第一個例子，監(jiān)督矩陣確定了如何糾錯，是構造者自己確定的，是根本，因此先確定監(jiān)督矩陣 線性系統(tǒng)碼的監(jiān)督矩陣的形式是確定的，要確定的是Q Q的列確定了信息位的校驗子（可任意確定，各列不同，且須與I中的列不同），I確定了監(jiān)督位的校驗子,線性分組碼,利用矩陣構造線性系統(tǒng)分組碼 第二步：由監(jiān)督矩陣得到生成矩陣 第三步：由生成矩陣可得許用碼組,線性分組碼,線性分組碼的分析（n. k）中n和k如何確定 只考慮糾正一位錯誤 線性分組碼的基本思想：用校正子指示錯誤位置 校正子有r位，可以指示的錯誤

14、圖樣 線性分組碼碼長為n位，如果只考慮一位錯誤，共有錯誤情況n種，還需要一種指示用于表征沒出錯，共需指示n+1種情況 能夠糾正1位錯誤需要滿足的關系式,等號成立時的特殊情況的碼稱為漢明碼,線性分組碼,線性分組碼的分析 考慮糾正t位錯誤 按照同樣的分析，可得到 信息碼元的位數(shù)（d為最小碼距） 線性分組碼存在的界吉爾伯特界,漢明界，r的最小值,普洛特金界，k的最大值,吉爾伯特界，r的最大值,線性分組碼,漢明碼（hanming） 能糾正單個錯誤的線性分組碼 碼長 監(jiān)督碼位 信息碼位 最小碼距 碼率,循環(huán)碼,概念 是一種線性分組碼，通常是系統(tǒng)碼 具有循環(huán)性質，即需用碼組經(jīng)過若干位的循環(huán)移位后仍未需用碼

15、組 實現(xiàn)簡單，可用帶反饋的移位寄存器實現(xiàn) 糾錯能力強，可糾正突發(fā)錯誤 循環(huán)碼的數(shù)學描述方式 多項式 矩陣 二元域上的預算：加法和乘法，注意與普通的數(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)性 左移k位的情況 按循環(huán)碼的循環(huán)特性，新的碼字可以描述為 按照二指域的多項式計算驗證上式,循環(huán)碼,循環(huán)碼的循環(huán)性 循環(huán)性的一般描述 循環(huán)碼的構造 信息碼組的多項式表示為M(D)，則循環(huán)碼編碼后

16、的碼組多項式為 g(D)為生成多項式 g(D)是n-k階多項式 G(D)能被 整除,循環(huán)碼,循環(huán)碼的構造 生成多項式 每一個g(D)對應一個循環(huán)碼，階數(shù)低于n且能被g(D)整除的一組多項式就構成一個循環(huán)碼 循環(huán)碼（n,k)的構造：給定g(D)，根據(jù)g(D)的階數(shù)確定M(D)的最高階數(shù)，所有M(D)和g(D)相乘得到的就是循環(huán)碼的許用碼組 g(D)尋找： 的因式保證循環(huán)性,循環(huán)碼,循環(huán)碼的構造 一個例子,循環(huán)碼,循環(huán)碼的生成矩陣和監(jiān)督矩陣,非系統(tǒng)碼！ 如何變成系統(tǒng)碼,循環(huán)碼,循環(huán)碼的生成矩陣和監(jiān)督矩陣 系統(tǒng)循環(huán)碼的矩陣形式應該什么樣子,G(D)如何構造，保證循環(huán)性,循環(huán)碼,循環(huán)碼的生成矩陣和監(jiān)督

17、矩陣 考慮系統(tǒng)碼的碼多項式 如果生成多項式為g(D)，由循環(huán)碼的生成規(guī)則可知g(D)和r(D)的階數(shù)相同，則按照二值域上的運算規(guī)則有 考慮k個特殊的信息碼字，即只有一個1的k個特殊碼字有對應的監(jiān)督碼多項式 由此，生成矩陣的每行對應的碼多項式,就是我們希望的,循環(huán)碼,循環(huán)碼的生成矩陣和監(jiān)督矩陣 總結系統(tǒng)碼的生成矩陣 根據(jù)g(D)求各行r(D); 由各行r(D)，根據(jù)標準形式寫出生成矩陣 系統(tǒng)碼的監(jiān)督矩陣,循環(huán)碼,系統(tǒng)循環(huán)碼的編碼器 系統(tǒng)循環(huán)碼的碼多項式 只需要求出r(D) 系統(tǒng)循環(huán)碼的編碼可以采用多項式長除的方法，利用線性反饋移位寄存器實現(xiàn),循環(huán)碼,循環(huán)碼的譯碼 定義誤差多項式 校正子的定義和計

18、算,和編碼一樣，可用反饋移位寄存器,循環(huán)碼,循環(huán)碼的譯碼 由校正子確定錯誤圖樣 例如：對于1位錯誤，如錯誤在第i位，則校正子為 譯碼結果,循環(huán)碼,循環(huán)碼的譯碼,BCH碼,上述循環(huán)碼有一個問題沒有講？ 循環(huán)碼的碼距 循環(huán)碼是線性分組碼，線性分組碼的碼距的求解方法可以直接應用 碼距和生成多項式的關系如何？ 確定碼距后能否快速確定生成多項式？ BCH碼的特點 BCH碼是循環(huán)碼 具有糾多個隨機錯誤的能力 構造容易 由碼的最小距離，可以很快得到碼的生成多項式,BCH碼,本原BCH碼 碼長為 生成多項式 最小碼距,LCM：最小公倍數(shù) ：最小多項式,由碼長及碼距可快速確定生成多項式,線性分組碼的擴展與縮短,

19、線性分組碼的擴展 在原有碼組基礎上增加一位校驗位，對所有碼字進行校驗，碼距增加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ā)送碼元的時間順序 將原本相鄰的碼元在時間上的距離最大化 時間上相鄰的突發(fā)錯誤屬于不同的碼組，可分別糾錯,交織編碼,交織碼的糾錯能力 交織碼的結構碼組方陣 行：分組碼的一個碼組 列：交織的深度i 糾錯能力 分組碼：糾正t個隨機錯誤交織碼：糾正tXi個突發(fā)錯誤 分組碼：糾正b個突發(fā)錯誤交織碼：糾正bXi個突發(fā)錯誤,交織編碼,交織碼的解碼 豎著寫入，橫著讀出 交織的代價：延時增大,其他信道編碼,常用其他