差錯編碼控制精品課件

1、差錯編碼控制第1頁，共53頁，2022年，5月20日，4點52分，星期三9.1 概述9.1.1 信道編碼9.1.2 差錯控制方式9.1.3 糾錯碼的分類9.1.4 糾錯編碼的基本原理第2頁，共53頁，2022年，5月20日，4點52分，星期三9.1 概 述 9.1.1 信道編碼 在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字信號的有效性以及為了使模擬信號數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率， 提高數(shù)字通信的可靠性而采取的編碼。 數(shù)字信號在傳輸過程中，加性噪聲、碼間串?dāng)_等都會產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，

2、以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。第3頁，共53頁，2022年，5月20日，4點52分，星期三9.1.2 差錯控制方式 圖 9-1 差錯控制方式 第4頁，共53頁，2022年，5月20日，4點52分，星期三 1. 檢錯重發(fā)方式 檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(Automatic Repeat Request)。 由發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中無錯誤產(chǎn)生，如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康摹Ｆ涮攸c是需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效， 但實

3、時性差，主要在計算機數(shù)據(jù)通信中得到應(yīng)用。 海上通信NBDP第5頁，共53頁，2022年，5月20日，4點52分，星期三 2. 前向糾錯方式 前向糾錯方式記作FEC(Forword ErrorCorrection)。發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。其特點是單向傳輸，實時性好，但譯碼設(shè)備較復(fù)雜。 海上衛(wèi)星通信Inmarsat-A第6頁，共53頁，2022年，5月20日，4點52分，星期三 3. 混合糾錯方式 混合糾錯方式記作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查

4、差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力， 但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此， 近年來得到廣泛應(yīng)用。海上衛(wèi)星通信 Inmarsat-C第7頁，共53頁，2022年，5月20日，4點52分，星期三 另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。具有脈沖干擾的信道是典型的突發(fā)信道， 錯誤是成串成群出現(xiàn)的，即在短時間內(nèi)出現(xiàn)大量錯誤。短波信道和對流層散射信道是混合信道的典型例子

5、，隨機錯誤和成串錯誤都占有相當(dāng)比例。對于不同類型的信道，應(yīng)采用不同的差錯控制方式。 第8頁，共53頁，2022年，5月20日，4點52分，星期三9.1.3 糾錯碼的分類 (1) 根據(jù)糾錯碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。 (2) 根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)， 而且還與前面若干組的信息元有關(guān)。 (3) 根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。 第

6、9頁，共53頁，2022年，5月20日，4點52分，星期三9.1.4 糾錯編碼的基本原理 1. 分組碼 分組碼一般可用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元， 組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應(yīng)地可得到2k個不同的碼字，稱為許用碼組。其余 2n-2k個碼字未被選用，稱為禁用碼組。 krn第10頁，共53頁，2022年，5月20日，4點52分，星期三 在分組碼中，非零碼元的數(shù)目稱為碼字的漢明(Hammi

7、ng)重量， 簡稱碼重。例如，碼字 10110，碼重w=3。 兩個等長碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個碼組的漢明(Hamming)距離， 簡稱碼距。例如 11000 與 10011之間的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d表示。最小碼距是碼的一個重要參數(shù)， 它是衡量碼檢錯、糾錯能力的依據(jù)。 第11頁，共53頁，2022年，5月20日，4點52分，星期三2. 檢錯和糾錯能力 若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡單重復(fù)， 則稱該分組碼為重復(fù)碼。它是一種簡單實用的檢錯碼， 并有一定的糾錯能力。例如(2,1)重復(fù)碼，兩個許用碼組是 00 與 11

8、，d0=2，收端譯碼，出現(xiàn) 01、10 禁用碼組時，可以發(fā)現(xiàn)傳輸中的一位錯誤。如果是(3,1)重復(fù)碼，兩個許用碼組是 000 與111, d0=3; 當(dāng)收端出現(xiàn)兩個或三個 1 時，判為 1，否則判為 0。此時，可以糾正單個錯誤，或者該碼可以檢出兩個錯誤。 第12頁，共53頁，2022年，5月20日，4點52分，星期三 碼的最小距離d0直接關(guān)系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi): (1) 檢測e個隨機錯誤，則要求碼的最小距離d0e+1; (2) 糾正t個隨機錯誤， 則要求碼的最小距離d02t+1; (3) 糾正t個同時檢測e(t)個隨機錯誤，則要求碼的最小距離d0t+e+1

9、。 t1eAB第13頁，共53頁，2022年，5月20日，4點52分，星期三 3. 編碼效率 用差錯控制編碼提高通信系統(tǒng)的可靠性， 是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:R=k/n其中, k是信息元的個數(shù)，n為碼長。 對糾錯碼的基本要求是: 檢錯和糾錯能力盡量強； 編碼效率盡量高；編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。 第14頁，共53頁，2022年，5月20日，4點52分，星期三9.2 常用的幾種簡單分組碼9.2.1 奇偶監(jiān)督碼 奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元， 使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，

10、它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。 第15頁，共53頁，2022年，5月20日，4點52分，星期三設(shè)碼字A=an-1,an-2,a1,a0，對偶監(jiān)督碼有 奇監(jiān)督碼情況相似， 只是碼組中“1”的數(shù)目為奇數(shù)， 即滿足條件 而檢錯能力與偶監(jiān)督碼相同。 奇偶監(jiān)督碼的編碼效率R為 第16頁，共53頁，2022年，5月20日，4點52分，星期三9.2.2 行列監(jiān)督碼 圖 9-2 (66,50)行列監(jiān)督碼 第17頁，共53頁，2022年，5月20日，4點52分，星期三9.2.3 恒比碼 碼字中 1 的數(shù)目與 0 的數(shù)目保持恒定比例的碼稱為恒比碼

11、。 由于恒比碼中，每個碼組均含有相同數(shù)目的 1 和 0，因此恒比碼又稱等重碼，定 1 碼。這種碼在檢測時，只要計算接收碼元中 1 的數(shù)目是否正確，就知道有無錯誤。 目前我國電傳通信中普遍采用 32 碼，又稱“5 中取 3”的恒比碼，即每個碼組的長度為 5，其中 3 個“1”。這時可能編成的不同碼組數(shù)目等于從 5 中取 3 的組合數(shù) 10，這 10 個許用碼組恰好可表示 10 個阿拉伯?dāng)?shù)字，如表 9 - 1 所示。而每個漢字又是以四位十進制數(shù)來代表的。實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。 第18頁，共53頁，2022年，5月20日，4點52分，星期三表 9-1 32 恒比碼 第

12、19頁，共53頁，2022年，5月20日，4點52分，星期三9.3 線 性 分 組 碼 現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點。設(shè)其碼字為A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是監(jiān)督元， 可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。 第20頁，共53頁，2022年，5月20日，4點52分，星期三表 9-2 (7,4)碼的碼字表 第21頁，共53頁，2022年，5月20日，4點52分，星期三9.3.2 監(jiān)督矩陣H和生成矩陣G 第22頁，共53頁，2022年，5月20日，4點52分，星期三 其中,P為rk階矩陣，Ir為rr階單位矩陣。可以寫成H=

13、P Ir形式的矩陣稱為典型監(jiān)督矩陣。 HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯的依據(jù)。 并簡記為 第23頁，共53頁，2022年，5月20日，4點52分，星期三若把監(jiān)督方程補充為下列方程 第24頁，共53頁，2022年，5月20日，4點52分，星期三可改寫為矩陣形式 第25頁，共53頁，2022年，5月20日，4點52分，星期三第26頁，共53頁，2022年，5月20日，4點52分，星期三9.3.3 伴隨式(校正子)S 設(shè)發(fā)送碼組A=an-1,an-2,a1,a0，在傳輸過程中可能發(fā)生誤碼。接收碼組B=bn-1,bn-2,b1,b0，則收發(fā)碼組之差定義

14、為錯誤圖樣E， 也稱為誤差矢量， 即 其中E=en-1,en-2,e1,e0，且 當(dāng)bi=ai 當(dāng)biai 令S=BHT，稱為伴隨式或校正子。 第27頁，共53頁，2022年，5月20日，4點52分，星期三表 9-3 (7,4)碼S與E的對應(yīng)關(guān)系 第28頁，共53頁，2022年，5月20日，4點52分，星期三9.4 循 環(huán) 碼 表 9-4 (7,3)循環(huán)碼 第29頁，共53頁，2022年，5月20日，4點52分，星期三 在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式(以降冪順序排列)為 第30頁，共53頁，2022年，5月20日，4點52分，星期三9.4.

15、1 生成多項式及生成矩陣 如果一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n,k)循環(huán)碼中任意碼多項式A(x)都是最低次碼多項式的倍式。如表 9-4 的(7,3)循環(huán)碼中， 第31頁，共53頁，2022年，5月20日，4點52分，星期三其它碼多項式都是g(x)的倍式， 即 第32頁，共53頁，2022年，5月20日，4點52分，星期三循環(huán)碼的生成矩陣常用多項式的形式來表示 第33頁，共53頁，2022年，5月20日，4點52分，星期三例如(7,3)循環(huán)碼，n=7, k=3, r=4, 其生成多項式及生成矩陣分別為 第34頁，共53頁，2022年，5月20日

16、，4點52分，星期三9.4.2 監(jiān)督多項式及監(jiān)督矩陣 為了便于對循環(huán)碼編譯碼，通常還定義監(jiān)督多項式， 令 其中g(shù)(x)是常數(shù)項為 1 的r次多項式，是生成多項式；h(x)是常數(shù)項為 1 的k次多項式，稱為監(jiān)督多項式。同理，可得監(jiān)督矩陣H 第35頁，共53頁，2022年，5月20日，4點52分，星期三是h(x)的逆多項式。例如(9，3)循環(huán)碼，g(x)=x4+x3+x2+1，則 其中 第36頁，共53頁，2022年，5月20日，4點52分，星期三第37頁，共53頁，2022年，5月20日，4點52分，星期三9.4.3 編碼方法和電路 在編碼時，首先要根據(jù)給定的(n,k)值選定生成多項式g(x)，

17、即應(yīng)在xn+1的因式中選一r=n-k次多項式作為g(x)。設(shè)編碼前的信息多項式m(x)為 循環(huán)碼的碼多項式可表示為 第38頁，共53頁，2022年，5月20日，4點52分，星期三圖 9-3 (7,3)循環(huán)碼編碼電路 第39頁，共53頁，2022年，5月20日，4點52分，星期三表 9-5 (7,3)循環(huán)碼的編碼過程 第40頁，共53頁，2022年，5月20日，4點52分，星期三9.4.4 譯碼方法和電路 圖 9-4 (7,3)循環(huán)碼譯碼電路 第41頁，共53頁，2022年，5月20日，4點52分，星期三9.5 卷 積 碼 9.5.1 基本概念 圖 9-5 卷積碼(2,1,2)編碼器 第42頁，

18、共53頁，2022年，5月20日，4點52分，星期三 起始狀態(tài)，各級移位寄存器清零，即S1S2S3為000。S1等于當(dāng)前輸入數(shù)據(jù)，而移位寄存器狀態(tài)S2S3存儲以前的數(shù)據(jù)，輸出碼字C由下式確定 表 9-6 (2,1,2)編碼器的工作過程 第43頁，共53頁，2022年，5月20日，4點52分，星期三9.5.2 卷積碼的描述 1. 樹圖 圖 9-6 (2,1,2)碼的樹圖 第44頁，共53頁，2022年，5月20日，4點52分，星期三2. 狀態(tài)圖 圖 9 -7 (2,1,2)碼的狀態(tài)圖 第45頁，共53頁，2022年，5月20日，4點52分，星期三3. 格圖 圖 9-8 (2,1,2)碼的格圖 第

19、46頁，共53頁，2022年，5月20日，4點52分，星期三9.5.3 卷積碼的譯碼 1. 維特比譯碼 圖 9-9 維特比譯碼格圖 第47頁，共53頁，2022年，5月20日，4點52分，星期三 2. 序列譯碼 當(dāng)m很大時，可以采用序列譯碼法。 其過程如下： 譯碼先從碼樹的起始節(jié)點開始，把接收到的第一個子碼的n個碼元與自始節(jié)點出發(fā)的兩條分支按照最小漢明距離進行比較， 沿著差異最小的分支走向第二個節(jié)點。在第二個節(jié)點上，譯碼器仍以同樣原理到達下一個節(jié)點，以此類推，最后得到一條路徑。若接收碼組有錯，則自某節(jié)點開始，譯碼器就一直在不正確的路徑中行進，譯碼也一直錯誤。因此，譯碼器有一個門限值，當(dāng)接收碼元與譯碼器所走的路徑上的碼元之間的差異總數(shù)超過門限值時，譯碼器判定有錯，并且返回試走另一分支。經(jīng)數(shù)次返回找出一條正