數據通信原理課件

《數據通信原理課件》由會員分享，可在線閱讀，更多相關《數據通信原理課件（81頁珍藏版）》請在裝配圖網上搜索。

1、第三章第三章 差錯控制差錯控制 本章首先討論差錯控制的基本概念及原本章首先討論差錯控制的基本概念及原理，介紹簡單的差錯控制協(xié)議，然后詳細介紹理，介紹簡單的差錯控制協(xié)議，然后詳細介紹幾種簡單的差錯控制編碼、漢明碼、循環(huán)碼，幾種簡單的差錯控制編碼、漢明碼、循環(huán)碼，并具體分析了線性分組碼的一般特性，最后探并具體分析了線性分組碼的一般特性，最后探討了卷積碼的相關內容。討了卷積碼的相關內容。3.1 差錯控制的基本概念及原理差錯控制的基本概念及原理3.1.1 3.1.1 差錯控制的基本概念差錯控制的基本概念1.差錯分類差錯分類:隨機差錯、突發(fā)差錯隨機差錯、突發(fā)差錯 隨機差錯又稱獨立差錯，它是指那些獨立地、

2、隨機差錯又稱獨立差錯，它是指那些獨立地、稀疏地和互不相關地發(fā)生的差錯。稀疏地和互不相關地發(fā)生的差錯。突發(fā)差錯是指一串串，甚至是成片出現的差錯，突發(fā)差錯是指一串串，甚至是成片出現的差錯，差錯之間有相關性，差錯出現是密集的。差錯之間有相關性，差錯出現是密集的。例：數據序列例：數據序列 1 0 1 1 0 0 0 1 1 1 0 1 這一串為突發(fā)差錯（中間可能有不錯的碼）這一串為突發(fā)差錯（中間可能有不錯的碼）例例1發(fā)送數據序列：發(fā)送數據序列：1 0 0 1 0 1 1 1 0 0 1接收數據序列：接收數據序列：1 1 1 1 1 0 0 1 1 1 0差錯序列：差錯序列：0 1 1 0 1 1 1

3、0 1 1 1“0”表示沒錯；表示沒錯；“1”表示有錯表示有錯2.差錯控制的基本思路差錯控制的基本思路差錯控制的基本思路是：差錯控制的基本思路是：在發(fā)送端被傳送的信在發(fā)送端被傳送的信息碼序列（本身無規(guī)律）的基礎上，按照一息碼序列（本身無規(guī)律）的基礎上，按照一定的規(guī)則加入若干監(jiān)督碼元后進行傳輸，這定的規(guī)則加入若干監(jiān)督碼元后進行傳輸，這些加入的碼元與原來的信息碼序列之間存在些加入的碼元與原來的信息碼序列之間存在著某種確定的約束關系。在接收數據時，檢著某種確定的約束關系。在接收數據時，檢驗信息碼元與監(jiān)督碼元之間的既定的約束關驗信息碼元與監(jiān)督碼元之間的既定的約束關系，如該關系遭到破壞，則收端可以發(fā)現傳

4、系，如該關系遭到破壞，則收端可以發(fā)現傳輸中的錯誤，乃至糾正錯誤。輸中的錯誤，乃至糾正錯誤。此過程叫此過程叫信息碼信息碼+監(jiān)督碼監(jiān)督碼=碼組碼組 r +k =n差錯控制編碼差錯控制編碼或糾錯編碼或或糾錯編碼或信道編碼信道編碼3.差錯控制方式差錯控制方式檢錯重發(fā)檢錯重發(fā)ARQ前向糾錯前向糾錯FEC混合糾錯檢錯混合糾錯檢錯HEC信息反饋信息反饋IRQ（1）檢錯重發(fā)）檢錯重發(fā)(ARQ)（自動重發(fā)請求）（自動重發(fā)請求）ARQ的思路的思路ARQ是在發(fā)送端對數據序列進行分組編碼，加入一定是在發(fā)送端對數據序列進行分組編碼，加入一定監(jiān)督碼元使之具有一定的檢錯能力，成為能夠發(fā)現監(jiān)督碼元使之具有一定的檢錯能力，成為

5、能夠發(fā)現錯誤的碼組。接收端收到碼組后，按一定規(guī)則對其錯誤的碼組。接收端收到碼組后，按一定規(guī)則對其進行有無錯誤的判別，并把判決結果進行有無錯誤的判別，并把判決結果(應答信號應答信號)通通過反向信道送回發(fā)送端。如有錯誤，發(fā)送端把前面過反向信道送回發(fā)送端。如有錯誤，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認為已正確發(fā)出的信息重新傳送一次，直到接收端認為已正確接收到信息為止。接收到信息為止。ARQ的重發(fā)方式的重發(fā)方式ARQ有有3種重發(fā)方式，即停發(fā)等候重發(fā)，返回重發(fā)和種重發(fā)方式，即停發(fā)等候重發(fā)，返回重發(fā)和選擇重發(fā)。選擇重發(fā)。三種重發(fā)方式三種重發(fā)方式a.停止等待協(xié)議停止等待協(xié)議 當重發(fā)方式采用停發(fā)等

6、候重發(fā)時，應該遵循停止等待當重發(fā)方式采用停發(fā)等候重發(fā)時，應該遵循停止等待協(xié)議。協(xié)議。停止等待協(xié)議規(guī)定：停止等待協(xié)議規(guī)定：發(fā)送端每發(fā)送一個數據幀（對應一個碼組）就暫停下發(fā)送端每發(fā)送一個數據幀（對應一個碼組）就暫停下來，等待接收端的應答。接收端收到數據幀進行差錯檢測，來，等待接收端的應答。接收端收到數據幀進行差錯檢測，若數據幀沒錯，就向發(fā)送端返回一個確認幀若數據幀沒錯，就向發(fā)送端返回一個確認幀ACK，發(fā)送端再，發(fā)送端再發(fā)送下一個數據幀；若接收端檢驗出數據幀有錯，就向發(fā)送發(fā)送下一個數據幀；若接收端檢驗出數據幀有錯，就向發(fā)送端返回一個否認幀端返回一個否認幀NAK，發(fā)送端重發(fā)剛才所發(fā)數據幀，直到，發(fā)送端

7、重發(fā)剛才所發(fā)數據幀，直到沒錯為止。沒錯為止。b.連續(xù)連續(xù)ARQ協(xié)議協(xié)議 連續(xù)連續(xù)ARQ協(xié)議的重發(fā)方式是返回重發(fā)，即發(fā)送端從出協(xié)議的重發(fā)方式是返回重發(fā)，即發(fā)送端從出錯數據幀及以后的各幀都要重發(fā)。錯數據幀及以后的各幀都要重發(fā)。c.選擇重發(fā)選擇重發(fā)ARQ協(xié)議協(xié)議 選擇重發(fā)選擇重發(fā)ARQ協(xié)議的重發(fā)方式是選擇重發(fā)，即發(fā)送端協(xié)議的重發(fā)方式是選擇重發(fā)，即發(fā)送端只重發(fā)出錯數據幀。只重發(fā)出錯數據幀。停止等待停止等待(協(xié)議算法協(xié)議算法)重發(fā)重發(fā)數據幀在實際鏈路上傳輸有四種情況，如圖所示。數據幀在實際鏈路上傳輸有四種情況，如圖所示。ARQ的優(yōu)缺點的優(yōu)缺點u需反向信道，實時性差需反向信道，實時性差u編碼效率較高編碼效

8、率較高u譯碼設備較簡單譯碼設備較簡單（2）前向糾錯（）前向糾錯（FEC）（自動糾錯）（自動糾錯）FEC的思路的思路前向糾錯系統(tǒng)中，發(fā)送端的信道編碼器將輸入前向糾錯系統(tǒng)中，發(fā)送端的信道編碼器將輸入數據序列變換成能夠糾正錯誤的碼，接收端數據序列變換成能夠糾正錯誤的碼，接收端的譯碼器根據編碼規(guī)律檢驗出錯誤的位置并的譯碼器根據編碼規(guī)律檢驗出錯誤的位置并自動糾正。自動糾正。FEC的優(yōu)缺點的優(yōu)缺點不需要反向信道，實時性好。不需要反向信道，實時性好。缺點是所選擇的糾錯碼必須與信道的錯碼特缺點是所選擇的糾錯碼必須與信道的錯碼特性密切配合，否則很難達到降低錯碼率的要性密切配合，否則很難達到降低錯碼率的要求；求；

9、譯碼設備復雜；而要求附加的監(jiān)督碼也較多，譯碼設備復雜；而要求附加的監(jiān)督碼也較多，傳輸效率就低。傳輸效率就低。(3)混合糾錯檢錯（混合糾錯檢錯（HEC）HEC的思路的思路混合糾錯檢錯方式是前向糾錯方式和檢錯重發(fā)混合糾錯檢錯方式是前向糾錯方式和檢錯重發(fā)方式的結合。在這種系統(tǒng)中，發(fā)送端發(fā)出同方式的結合。在這種系統(tǒng)中，發(fā)送端發(fā)出同時具有檢錯和糾錯能力的碼，接收端收到碼時具有檢錯和糾錯能力的碼，接收端收到碼后，檢查錯誤情況，如果錯誤少于糾錯能力，后，檢查錯誤情況，如果錯誤少于糾錯能力，則自行糾正；如果干擾嚴重，錯誤很多，超則自行糾正；如果干擾嚴重，錯誤很多，超出糾正能力，但能檢測出來，則經反向信道出糾正

10、能力，但能檢測出來，則經反向信道要求發(fā)端重發(fā)。要求發(fā)端重發(fā)。HEC的優(yōu)缺點的優(yōu)缺點混合糾錯檢錯方式在實時性和譯碼復雜性方面混合糾錯檢錯方式在實時性和譯碼復雜性方面是前向糾錯和檢錯重發(fā)方式的折衷，因而近是前向糾錯和檢錯重發(fā)方式的折衷，因而近年來，在數據通信系統(tǒng)中采用較多。年來，在數據通信系統(tǒng)中采用較多。(4)信息反饋（信息反饋（IRQ）IRQ的思路的思路信息反饋方式信息反饋方式(IRQ)在發(fā)送端不進行糾錯編碼，接收在發(fā)送端不進行糾錯編碼，接收端把收到的數據序列端把收到的數據序列全部全部由反向信道送回發(fā)端，發(fā)由反向信道送回發(fā)端，發(fā)端自己比較發(fā)送的數據序列與送回的數據序列，從端自己比較發(fā)送的數據序列

11、與送回的數據序列，從而發(fā)現是否有錯誤，并把認為錯誤的數據序列的原而發(fā)現是否有錯誤，并把認為錯誤的數據序列的原數據再次傳送，直到發(fā)端沒有發(fā)現錯誤為止。數據再次傳送，直到發(fā)端沒有發(fā)現錯誤為止。IRQ的優(yōu)缺點的優(yōu)缺點這種方式的優(yōu)點是不需要糾錯、檢錯的編譯器，設這種方式的優(yōu)點是不需要糾錯、檢錯的編譯器，設備簡單。備簡單。缺點是需要和前向信道相同的反向信道，實時性差。缺點是需要和前向信道相同的反向信道，實時性差。發(fā)送端需要一定容量的存儲器以存儲發(fā)送碼組，環(huán)發(fā)送端需要一定容量的存儲器以存儲發(fā)送碼組，環(huán)路時延越大，數據速率越高，所需存儲容量越大。路時延越大，數據速率越高，所需存儲容量越大。練習練習差錯控制方

12、式中差錯控制方式中 不需反向信道的是不需反向信道的是 實時性最好的是實時性最好的是 不需信道編譯碼器的是不需信道編譯碼器的是 用得最多的是用得最多的是 前向糾錯前向糾錯FEC 前向糾錯前向糾錯FEC 信息反饋信息反饋IRQ 混合糾錯檢錯混合糾錯檢錯HEC3.1.2 3.1.2 差錯控制的基本原理差錯控制的基本原理1.差錯控制的原理差錯控制的原理傳兩個消息傳兩個消息（1）發(fā)）發(fā)1位碼位碼 10 01無糾檢錯能力（2）發(fā)）發(fā)2位碼位碼 1110 0001可檢錯可檢錯1位位（3）發(fā)）發(fā)3位碼位碼 1 1 1 0 0 0可糾錯可糾錯1位位可檢錯可檢錯2位位收發(fā)兩端約定，收發(fā)兩端約定，當收到兩個以上的當

13、收到兩個以上的1時，認為發(fā)的是時，認為發(fā)的是111；當收到兩個以上的當收到兩個以上的0時，認為發(fā)的是時，認為發(fā)的是000。1 1 1 110 0 0 0 001若無以上約定，若無以上約定，111000110l 糾錯編碼之所以具有檢錯和糾錯能力，糾錯編碼之所以具有檢錯和糾錯能力，是因為在信息碼之外附加了監(jiān)督碼，即碼的是因為在信息碼之外附加了監(jiān)督碼，即碼的檢錯和糾錯能力是用信息量的冗余度來換取檢錯和糾錯能力是用信息量的冗余度來換取的。的。l 加入監(jiān)督碼越多，碼的檢錯、糾錯能力加入監(jiān)督碼越多，碼的檢錯、糾錯能力越強，但信息傳輸效率下降也越多。越強，但信息傳輸效率下降也越多。l 在糾錯編碼中將信息傳輸

14、效率也稱為編在糾錯編碼中將信息傳輸效率也稱為編碼效率，定義為碼效率，定義為nkR（3-1）2.漢明距離與檢錯和糾錯能力的關系漢明距離與檢錯和糾錯能力的關系（1）幾個概念）幾個概念碼組的重量碼組的重量碼組中非零碼元的數目為碼組碼組中非零碼元的數目為碼組的重量，簡稱碼重。的重量，簡稱碼重。碼距碼距把兩個碼組中對應碼位上具有不同二把兩個碼組中對應碼位上具有不同二進制碼元的個數定義為兩碼進制碼元的個數定義為兩碼 組的距離，簡稱碼組的距離，簡稱碼距。距。例：例：11010 10001 碼距是碼距是3漢明距離漢明距離在一種編碼中，任意兩個許用碼在一種編碼中，任意兩個許用碼組間距離的最小值，稱為這一編碼的漢

15、明距離，組間距離的最小值，稱為這一編碼的漢明距離，以以 表示。表示。mind例：一碼組集合例：一碼組集合min5,4,3,6,?detmin2d 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 03334223.糾錯編碼的分類糾錯編碼的分類(1)按碼組的功能分，有檢錯碼和糾錯碼兩類。按碼組的功能分，有檢錯碼和糾錯碼兩類。(2)按碼組中監(jiān)督碼元與信息碼元之間的關系分，按碼組中監(jiān)督碼元與信息碼元之間的關系分，有線性碼和非線性碼兩類。有線性碼和非線性碼兩類。(3)按照信息碼元與監(jiān)督碼元的約束關系，又可按照信息碼元與監(jiān)督碼元的約束關系，又可分為分組碼和卷積碼兩類。分為分組碼

16、和卷積碼兩類。(4)按照信息碼元在編碼前后是否保持原來的形按照信息碼元在編碼前后是否保持原來的形式不變，可劃分為系統(tǒng)碼和非系統(tǒng)碼。式不變，可劃分為系統(tǒng)碼和非系統(tǒng)碼。(5)按糾正差錯的類型可分為糾正隨機錯誤的碼按糾正差錯的類型可分為糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼。和糾正突發(fā)錯誤的碼。(6)按照每個碼元取值來分，可分為二進制碼與按照每個碼元取值來分，可分為二進制碼與多進制碼。多進制碼。3.2 簡單的差錯控制編碼簡單的差錯控制編碼3.2.1 3.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼(編碼規(guī)則)設碼組長度為設碼組長度為n，表示為，表示為 ()，其中前其中前n-1位為信息碼元，第位為信息碼元，第n位為監(jiān)督位

17、位為監(jiān)督位a0。0121,aaaann2、監(jiān)督方程、監(jiān)督方程0110 naaa1110 naaa偶檢驗的監(jiān)督關系（偶監(jiān)督方程）偶檢驗的監(jiān)督關系（偶監(jiān)督方程）在奇校驗的監(jiān)督關系在奇校驗的監(jiān)督關系（奇監(jiān)督方程奇監(jiān)督方程）1、概念概念偶監(jiān)督碼偶監(jiān)督碼-信息碼與監(jiān)督碼合在一起信息碼與監(jiān)督碼合在一起“1”的的個數是偶數個數是偶數奇監(jiān)督碼奇監(jiān)督碼-信息碼與監(jiān)督碼合在一起信息碼與監(jiān)督碼合在一起“1”的的個數是奇數個數是奇數只能發(fā)現單個或奇數個錯誤，只能發(fā)現單個或奇數個錯誤，不能檢測出偶數個錯誤不能檢測出偶數個錯誤3.2.1 3.2.1 水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼 水平奇偶監(jiān)督碼的水平奇偶監(jiān)督碼的構成思路構

18、成思路是：將信息碼序列是：將信息碼序列按行排成方陣，每行后面加一個奇或偶監(jiān)督編碼，按行排成方陣，每行后面加一個奇或偶監(jiān)督編碼，即每行為一個奇偶監(jiān)督碼組即每行為一個奇偶監(jiān)督碼組(見表見表3-2，以偶監(jiān)督為，以偶監(jiān)督為例例)，但發(fā)送時則按列的順序傳輸：，但發(fā)送時則按列的順序傳輸：11101110011000010101，接收端仍將碼元排成，接收端仍將碼元排成與發(fā)送端一樣的方陣形式，然后按行進行奇偶校驗。與發(fā)送端一樣的方陣形式，然后按行進行奇偶校驗。表表3-2 水平偶監(jiān)督碼水平偶監(jiān)督碼 信信 息息 碼碼 元元 監(jiān)督碼元監(jiān)督碼元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1

19、0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 10101*檢錯能力檢錯能力（1）可發(fā)現某一行上所有奇數個錯誤）可發(fā)現某一行上所有奇數個錯誤（2）能檢測出所有長度不大于方陣中行數的）能檢測出所有長度不大于方陣中行數的突發(fā)錯誤突發(fā)錯誤討論：討論：水平奇偶監(jiān)督碼是檢錯碼，屬于線性分組水平奇偶監(jiān)督碼是檢錯碼，屬于線性分組碼。碼。3.2.2 3.2.2 二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼 二維奇偶監(jiān)督碼是將水平奇偶監(jiān)督碼推廣而得，二維奇偶監(jiān)督碼是將水平奇偶監(jiān)督碼推廣而得，又稱水平垂直奇偶監(jiān)督碼、行列監(jiān)督碼和方陣碼。又稱水平垂直奇

20、偶監(jiān)督碼、行列監(jiān)督碼和方陣碼。它的方法是在水平監(jiān)督基礎上對表它的方法是在水平監(jiān)督基礎上對表3-2方陣中每一方陣中每一列再進行奇偶校驗，就可得表列再進行奇偶校驗，就可得表3-3（以偶監(jiān)督為例）（以偶監(jiān)督為例）所示的方陣。發(fā)送是按列或按行的順序傳輸。接收所示的方陣。發(fā)送是按列或按行的順序傳輸。接收端重新將碼元排成發(fā)送時方陣形式，然后每行、每端重新將碼元排成發(fā)送時方陣形式，然后每行、每列都進行奇偶校驗。列都進行奇偶校驗。表表3-3 二維偶監(jiān)督碼二維偶監(jiān)督碼 信信 息息 碼碼 元元 監(jiān)督碼元監(jiān)督碼元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1

21、 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 監(jiān)督碼元監(jiān)督碼元 101010 1 1 0 1 1 0 0 0 11*檢錯能力檢錯能力（1）可發(fā)現某行或某列上奇數個錯誤。）可發(fā)現某行或某列上奇數個錯誤。（2）能檢測出所有長度不大于方陣中行數）能檢測出所有長度不大于方陣中行數（或列數）的突發(fā)錯誤（或列數）的突發(fā)錯誤（3）能檢測出偶數個錯誤。但若偶數個錯誤）能檢測出偶數個錯誤。但若偶數個錯誤恰好分布在矩陣的四個頂點上時，這樣的偶恰好分布在矩陣的四個頂點上時，這樣的偶數個錯誤是檢測不出來的。數個錯誤是檢測不出來的。（4）可以糾正某些錯誤，當某行某列均

22、不滿）可以糾正某些錯誤，當某行某列均不滿足監(jiān)督關系，可判定該行該列交叉位置的碼足監(jiān)督關系，可判定該行該列交叉位置的碼元有錯，從而糾正這一位上的錯誤。元有錯，從而糾正這一位上的錯誤。討論：二維奇偶監(jiān)督碼是檢錯碼或糾錯碼，討論：二維奇偶監(jiān)督碼是檢錯碼或糾錯碼，屬于線性分組碼。屬于線性分組碼。3.3 漢明碼及線性分組碼漢明碼及線性分組碼 3.3.1 3.3.1 漢明碼漢明碼1、（n,k）漢明碼）漢明碼 r與與n的關系為的關系為2121rrnkr 或例題例題（2）糾檢錯）糾檢錯方法方法-接收端收到（接收端收到（7，4）漢明碼，由下述）漢明碼，由下述方程計算校正子，然后查表方程計算校正子，然后查表3-4

23、可知此碼組是否可知此碼組是否有錯以及差錯的確切位置有錯以及差錯的確切位置 s1 s2 s3 s1 s2 s3 錯碼位置錯碼位置 0 0 0 0 0 0 無錯無錯 0 0 1 0 0 1 a0 a0 0 1 0 0 1 0 a1 a1 1 0 0 1 0 0 a2 a2 0 1 1 0 1 1 a3 a3 1 0 1 1 0 1 a4 a4 1 1 0 1 1 0 a5 a5 1 1 1 1 1 1 a6 a6 表表3-4 較正子與錯碼位置較正子與錯碼位置*例：接收端收到某（例：接收端收到某（7，4）漢明碼為）漢明碼為1001010，此（此（7，4）漢明碼是否有錯？錯碼位置如何？）漢明碼是否有錯

24、？錯碼位置如何？討論討論 漢明距離漢明距離 編碼效率編碼效率3.3.2 3.3.2 線性分組碼線性分組碼2.線性分組碼的主要性質線性分組碼的主要性質 (1)封閉性封閉性 所謂封閉性，是指一種線性分組碼中的所謂封閉性，是指一種線性分組碼中的任意兩個碼組之逐位模任意兩個碼組之逐位模2和仍為這種碼中的另和仍為這種碼中的另一個許用碼組。一個許用碼組。線性碼是指信息位和監(jiān)督位滿足一組線性方程線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼，分組碼是監(jiān)督碼僅對本碼組起監(jiān)督作用，的碼，分組碼是監(jiān)督碼僅對本碼組起監(jiān)督作用，既是線性碼又是分組碼稱為線性分組碼。既是線性碼又是分組碼稱為線性分組碼。(2)碼的最小距離等

25、于非零碼的最小重量（除了碼的最小距離等于非零碼的最小重量（除了全全0碼組之外）碼組之外）因為線性分組碼具有封閉性，因而兩個碼組因為線性分組碼具有封閉性，因而兩個碼組之間的距離必是另一碼組的重量。之間的距離必是另一碼組的重量。循環(huán)碼是線性分組碼中一類重要的碼。循環(huán)碼是線性分組碼中一類重要的碼。3.4.1 3.4.1 循環(huán)碼的循環(huán)特性循環(huán)碼的循環(huán)特性 循環(huán)碼的循環(huán)性是指循環(huán)碼中任一許用碼組經循環(huán)碼的循環(huán)性是指循環(huán)碼中任一許用碼組經過循環(huán)移位后過循環(huán)移位后(將最右端的碼元移至左端，或反之將最右端的碼元移至左端，或反之)所得到的碼組仍為它的一個許用碼組。所得到的碼組仍為它的一個許用碼組。表表3-6給出

26、一種給出一種(7，3)循環(huán)碼的全部碼組，由循環(huán)碼的全部碼組，由此表可直觀看出這種碼的循環(huán)性。例如，表中的第此表可直觀看出這種碼的循環(huán)性。例如，表中的第2碼組向右循環(huán)移一位即得到第碼組向右循環(huán)移一位即得到第5碼組，第碼組，第2碼組向碼組向左循環(huán)移一位即得到第左循環(huán)移一位即得到第3碼組。碼組。3.4 循環(huán)碼循環(huán)碼表表3-6 （7，3）循環(huán)碼的碼組）循環(huán)碼的碼組456aaa0123aaaa456aaa 碼組碼組編號編號 信息位信息位 監(jiān)督位監(jiān)督位 碼組碼組編號編號 信息位信息位 監(jiān)督位監(jiān)督位 1 1 2 2 3 3 4 4 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0

27、1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 5 5 6 6 7 7 8 8 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0123aaaa0123aaaa1.碼的多項式碼的多項式若碼組若碼組 ，則相應的多項式表示為則相應的多項式表示為 ),(0121aaaaAnn00112211)(xaxaxaxaxAnnnn3.4

28、.2 循環(huán)碼的生成多項式和生成矩陣循環(huán)碼的生成多項式和生成矩陣例例1：A=10110116432()1A xxxxx例例2：已知：已知 ，寫出對應，寫出對應的碼組的碼組(n=7)。653()1A xxxx解：解：A=1101001 循環(huán)碼的循環(huán)碼的2 k個碼組中，有一個碼組前個碼組中，有一個碼組前k-1位碼元位碼元均為均為0，第，第k位碼元為位碼元為1，第，第n位（最后一位）碼元位（最后一位）碼元為為1，此碼組對應的多項式。，此碼組對應的多項式。例：求表例：求表3-6（7，3）循環(huán)碼的生成多項式。）循環(huán)碼的生成多項式。表表3-6（7，3）循環(huán)碼對應生成多項式的碼組為）循環(huán)碼對應生成多項式的碼組

29、為第第3個碼組個碼組0010111，生成多項式為，生成多項式為42()1g xxxx2、循環(huán)碼的生成多項式、循環(huán)碼的生成多項式3.生成矩陣生成矩陣G由循環(huán)碼的生成多項式由循環(huán)碼的生成多項式g(x)可得到生成矩陣可得到生成矩陣G(x)，為，為)()()()()(21xgxxgxgxxgxxGkk轉換后，典型的生成矩陣為轉換后，典型的生成矩陣為QIGk生成矩陣生成矩陣可以通過線性變換將非典型的生成矩陣可以通過線性變換將非典型的生成矩陣轉換為典型的生成矩陣，具體方法是：轉換為典型的生成矩陣，具體方法是：任意幾行模二加取代某一行。任意幾行模二加取代某一行。例例將三位信息碼將三位信息碼 （000、001

30、、010、011111）與典型的生成矩陣）與典型的生成矩陣G相乘便可得到全相乘便可得到全部碼組，即表部碼組，即表3-6所示。所示。456aaa 信息字段為信息字段為K位，校驗字段為位，校驗字段為R位，位，碼字長度碼字長度為為N(N=K+R)位位 V(x)=xR m(x)+r(x)m(x)為為K次信息多項式，次信息多項式，r(x)為為R次校驗多項式次校驗多項式例如：信息字段代碼為例如：信息字段代碼為:1011001 :1011001 對應對應 m(xm(x)=x)=x6 6+x+x4 4+x+x3 3+1+1 g(xg(x)=x)=x4 4+x+x3 3+1+1 為生成多項式為生成多項式 g(x

31、g(x)的代碼為的代碼為:11001:11001校驗碼生成的另一種方法校驗碼生成的另一種方法 信息字段移位信息字段移位：x x4 4 m(x)=x m(x)=x1010+x+x8 8+x+x7 7+x+x4 4 1011001 101100100000000校驗字段形成：（二進制除）校驗字段形成：（二進制除）取余數取余數 11001 10110010000 11001 10110010000 得：得：10101010傳輸字段：傳輸字段：1011001101100110101010校驗校驗：接收字段接收字段/相同的生成碼（二進制除），相同的生成碼（二進制除），除盡（正確），除盡（正確），否則（錯

32、）否則（錯）Binary Division常用的常用的CRC生成多項式生成多項式g(x)為為:CRC16=x16+x15+x2+1 R=16，IBM專用專用 CRC16=x16+x12+x5+1 R=16，CCITT專用專用 CRC32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 R=32,LAN中常用中常用3.5 卷積碼卷積碼1.卷積碼的概念卷積碼的概念在分組碼中，任何一段規(guī)定時間內編碼器產生的在分組碼中，任何一段規(guī)定時間內編碼器產生的n個個碼元的一個碼組，其監(jiān)督位完全決定于這段時間中碼元的一個碼組，其監(jiān)督位完全決定于這段時間中輸入的

33、輸入的k個信息位，這個碼組中的個信息位，這個碼組中的n-k個監(jiān)督位僅對個監(jiān)督位僅對本碼組起監(jiān)督作用。本碼組起監(jiān)督作用。卷積碼則不然，編碼器在任何一段規(guī)定時間內產生的卷積碼則不然，編碼器在任何一段規(guī)定時間內產生的n個碼元，其監(jiān)督位不僅取決于這段時間中的個碼元，其監(jiān)督位不僅取決于這段時間中的k個信個信息位，而且還取決于前息位，而且還取決于前N-1段規(guī)定時間內的信息位。段規(guī)定時間內的信息位。換句話說，監(jiān)督位不僅對本碼組起監(jiān)督作用，還對換句話說，監(jiān)督位不僅對本碼組起監(jiān)督作用，還對前前N-1個碼組也起監(jiān)督作用。個碼組也起監(jiān)督作用。這段這段N時間內的碼元數目時間內的碼元數目nN稱為這種卷積碼的約束長稱為這

34、種卷積碼的約束長度。通常把卷積碼記作度。通常把卷積碼記作(n,k,N)，其編碼效率，其編碼效率 卷積碼的基本概念卷積碼的基本概念2 卷積碼的編碼卷積碼的編碼簡單例子：由簡單例子：由2個移位寄存器和個移位寄存器和1個模個模2加電路加電路構成（構成（2，1，2）卷積碼編碼器）卷積碼編碼器D1D2+m1m2m3m4m5m6tm1 c1 m2 c2 m3 c3 m4 c4 m5 c5 m6 c6tmcmi.m1.0.m2.m1.m3.m2.mi-1ci+1=mi+m(i+1)2 卷積碼的解碼卷積碼的解碼D1D2+D3與與門門.m1.c1 0S0.mi+10.m2.c2.m1.S1S0.m3.m2.c3

35、.S2S1.mi.ci+1SiSi-1S0=0 +m1+c1S1=m1+m2+c2S2=m2+m3+c3S3=m3+m4+c4校正子校正子Si=mi+m(i+1)+ci+1此為門限解碼，屬于代數解碼，此為門限解碼，屬于代數解碼，適于約束長度較短的卷積碼；另一類為概率解碼適于約束長度較短的卷積碼；另一類為概率解碼（2，1，3）卷積碼編碼器）卷積碼編碼器m1m2m3+.c1 c2C1=m1+m2+m3C2=m1+m3輸入輸入比特比特狀態(tài)比狀態(tài)比特特輸入序列輸入序列輸出序列輸出序列.m2m3=00(左左)輸入輸入m1=000移位后移位后10001001110010(左左)輸入輸入m1=1011100

36、10011100100111001001110010011100100111卷積碼的樹狀圖卷積碼的樹狀圖（2，1，3）卷積）卷積碼的樹狀圖碼的樹狀圖.a(m3m2)(左左)輸入輸入m1=0a.c1c2=00 ba b c da b(左左)輸入輸入m1=1 c d a b c da b c d a b c d a b cda b c d0000001111111111101010010111000110當輸入序列當輸入序列為為11010時，輸出時，輸出碼元序列？碼元序列？11 01 01 00 10輸入為輸入為0110時，時，輸出碼元輸出碼元序列？序列？000 111 101 011（2，1，3

37、）卷積碼的網格圖（籬笆圖）卷積碼的網格圖（籬笆圖）a b c d（2，1，3）卷積碼的狀態(tài)圖）卷積碼的狀態(tài)圖0，實線；，實線；1，虛線，虛線00=a 01=b10=c 11=d00=a 01=b 10=c 11=d0011111001100100卷積碼的譯碼方法卷積碼的譯碼方法代數譯碼利用編碼本身得代數結構進行解碼，代數譯碼利用編碼本身得代數結構進行解碼，并不考慮信道的統(tǒng)計特性。其主要特點是算并不考慮信道的統(tǒng)計特性。其主要特點是算法簡單，易于實現，但是它的誤碼性能要比法簡單，易于實現，但是它的誤碼性能要比概率譯碼差。其譯碼方法是從線性碼的監(jiān)督概率譯碼差。其譯碼方法是從線性碼的監(jiān)督子出發(fā)，找到一

38、組特殊的能夠檢查信息位置子出發(fā)，找到一組特殊的能夠檢查信息位置是否發(fā)生錯誤的方程組，從而實現糾錯譯碼。是否發(fā)生錯誤的方程組，從而實現糾錯譯碼。概率譯碼的基本思想是：把已經接收到的序列概率譯碼的基本思想是：把已經接收到的序列與所有可能的發(fā)送序列相比較，選擇其中漢與所有可能的發(fā)送序列相比較，選擇其中漢明距離最小的一個序列作為發(fā)送序列。維特明距離最小的一個序列作為發(fā)送序列。維特比譯碼是目前用得較多的一種譯碼方法。比譯碼是目前用得較多的一種譯碼方法。舉例說明維特比譯碼工作原理舉例說明維特比譯碼工作原理維特比提出了一種算法：譯碼器不是在籬笆圖上一次就維特比提出了一種算法：譯碼器不是在籬笆圖上一次就計算和

39、比較計算和比較 2Lk 條路徑，而是接收一段，就計算、比條路徑，而是接收一段，就計算、比較一段，從而在每個狀態(tài)時，選擇進入該狀態(tài)的最可較一段，從而在每個狀態(tài)時，選擇進入該狀態(tài)的最可能的分支。能的分支。維特比譯碼的基本思想：將接收序列維特比譯碼的基本思想：將接收序列 R R 與籬笆圖上的與籬笆圖上的路徑逐分支地比較，比較的長度一般取路徑逐分支地比較，比較的長度一般取(56)mn，然然后留下與后留下與 R R 距離最小的路徑，稱為幸存路徑，而去掉距離最小的路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑逐分支地延長并其余可能的路徑，并將這些幸存路徑逐分支地延長并存儲起來。存儲起來。幸存路

40、徑的數目等于狀態(tài)數：幸存路徑的數目等于狀態(tài)數：2km 以以(2,1,2)非系統(tǒng)碼為例說明維特比譯碼的基本思想：非系統(tǒng)碼為例說明維特比譯碼的基本思想：設發(fā)送序列設發(fā)送序列 C C 為全為全0；接收序列接收序列 R R=10,00,01,00,00,00,00,維特比譯碼的基本原理維特比譯碼的基本原理假設譯碼器的初始狀態(tài)為全假設譯碼器的初始狀態(tài)為全0；第0個時刻：接收序列的第接收序列的第0個分支個分支 R R0=10 進入譯碼器。進入譯碼器。從從 S0 狀態(tài)有兩個分支，它們是狀態(tài)有兩個分支，它們是 00 和和 11，R R0與這兩與這兩個分支比較，比較的結果和到達的狀態(tài)如表個分支比較，比較的結果和

41、到達的狀態(tài)如表 9.2 所示：所示：每個狀態(tài)每個狀態(tài)/節(jié)點都有兩個存儲器：節(jié)點都有兩個存儲器：路徑存儲器：存儲該狀態(tài)的部分路徑；路徑存儲器：存儲該狀態(tài)的部分路徑；路徑值存儲器：存儲達到該狀態(tài)的部分路徑值路徑值存儲器：存儲達到該狀態(tài)的部分路徑值(累加累加距離距離)。維特比譯碼的基本原理維特比譯碼的基本原理表9.2 幸 存 路 徑 第0 分 支 的 距 離 到 達 狀 態(tài) 0 0 11 1 1 S0 S1 第一個時刻：進入譯碼器的接收碼組進入譯碼器的接收碼組 R R1=00 和此時刻和此時刻出發(fā)的的四條分支比較，比較結果和達到狀態(tài)如表四條分支比較，比較結果和達到狀態(tài)如表9.3所示：所示：從第一個時

42、刻到第二個時刻：共有四條路徑，到達共有四條路徑，到達S0,S1,S2和和S3。在第二個時刻以前譯碼器不做任何選擇和判決。在第二個時刻以前譯碼器不做任何選擇和判決。每個狀態(tài)的路徑存儲器存儲下此時刻的幸存路徑：存儲下此時刻的幸存路徑：0000,0011,1110,1101；每個狀態(tài)的路徑值存儲器存儲了此時刻到達該狀態(tài)的幸存存儲了此時刻到達該狀態(tài)的幸存路徑累加值路徑累加值(累加距離累加距離)。維特比譯碼的基本原理維特比譯碼的基本原理表 9.3 上次距離 幸存路徑 延長分支 本分支距離 累加距離 到達狀態(tài) 1 3 2 2 0000 0011 1110 1101 00 11 10 01 11 00 01

43、 10 1 1 2 0 1 1 0 2 2 2 5 3 3 3 2 4 S0 S1 S2 S3 S0 S1 S2 S3 從第二個時刻起：第二個接收碼組第二個接收碼組 R R2=01 進入譯碼器，從籬進入譯碼器，從籬笆圖上可見，從第二個時刻到第三個時刻，進入每個狀態(tài)笆圖上可見，從第二個時刻到第三個時刻，進入每個狀態(tài)的分支有兩個（或者說在第三個時刻，進入每個狀態(tài)的路的分支有兩個（或者說在第三個時刻，進入每個狀態(tài)的路徑有兩條）。譯碼器將接收碼組徑有兩條）。譯碼器將接收碼組 R R2 與進入每個狀態(tài)的兩個與進入每個狀態(tài)的兩個分支進行比較和判決，選擇一個累加距離（部分路徑值）分支進行比較和判決，選擇一個

44、累加距離（部分路徑值）最小的路徑作為進入該狀態(tài)的幸存路徑。這樣的幸存路徑最小的路徑作為進入該狀態(tài)的幸存路徑。這樣的幸存路徑共四條，比較和判決的過程如下：共四條，比較和判決的過程如下：維特比譯碼的基本原理維特比譯碼的基本原理經過比較后選擇：部分路徑部分路徑 000000為到達為到達 S0 狀態(tài)的幸存路徑；狀態(tài)的幸存路徑；部分路徑部分路徑 000011為到達為到達 S1 狀態(tài)的幸存路徑；狀態(tài)的幸存路徑；部分路徑部分路徑 110101為到達為到達 S2 狀態(tài)的幸存路徑；狀態(tài)的幸存路徑；部分路徑部分路徑 001101為到達為到達 S3 狀態(tài)的幸存路徑。狀態(tài)的幸存路徑。按照上述方法，接收序列的諸碼組依次

45、進入譯碼器，按照上述方法，接收序列的諸碼組依次進入譯碼器，每個時刻進入一個碼組，沿著籬笆圖對每個狀態(tài)按部每個時刻進入一個碼組，沿著籬笆圖對每個狀態(tài)按部分路徑值（累加距離）的大小，選擇一條幸存路徑。分路徑值（累加距離）的大小，選擇一條幸存路徑。在每個狀態(tài)上進行判決時，可能出現進入這一狀態(tài)的在每個狀態(tài)上進行判決時，可能出現進入這一狀態(tài)的兩條路徑的距離值相同，這時可以任選其一，因為對兩條路徑的距離值相同，這時可以任選其一，因為對以后的判決而言，無論選擇那一條路徑，累加距離是以后的判決而言，無論選擇那一條路徑，累加距離是相同的。相同的。對本例而言，按上述算法進行到對本例而言，按上述算法進行到第十一個分

46、支后，四條路分支后，四條路徑的前面分支都合并在一起。所以，只要譯碼深度足夠，徑的前面分支都合并在一起。所以，只要譯碼深度足夠，就可達到較低的錯誤概率。一般，約為就可達到較低的錯誤概率。一般，約為(56)mn，所以所以，維特比譯碼的延時可達，維特比譯碼的延時可達(56)m 個單位時刻（每個單位個單位時刻（每個單位時刻為時刻為 n 個碼元長度）就可以對第個碼元長度）就可以對第0個接收碼組的信息元個接收碼組的信息元進行判決。依此類推，對接收序列中的諸碼組進行譯碼。進行判決。依此類推，對接收序列中的諸碼組進行譯碼。維特比譯碼的一次運算：維特比譯碼的一次運算：計算每個輸入分支的度量值（分支距離、累加距離

47、）；計算每個輸入分支的度量值（分支距離、累加距離）；比較各部分路徑的度量值，選擇一條作為幸存路徑。比較各部分路徑的度量值，選擇一條作為幸存路徑?；h笆圖中共有籬笆圖中共有 2km 個狀態(tài)，因此，維特比譯碼的計算量與編個狀態(tài)，因此，維特比譯碼的計算量與編碼存儲碼存儲 m 成指數關系變化，所以采用維特比算法譯碼的卷成指數關系變化，所以采用維特比算法譯碼的卷積碼，其積碼，其 m 不能選的太大。不能選的太大。維特比譯碼的基本原理維特比譯碼的基本原理 維特比譯碼的基本原理維特比譯碼的基本原理 維特比譯碼的基本原理維特比譯碼的基本原理7.6 維特比譯碼的基本原理維特比譯碼的基本原理7.6 維特比譯碼的基本原

48、理維特比譯碼的基本原理 維特比譯碼的基本原理維特比譯碼的基本原理 總結維特比算法的步驟總結維特比算法的步驟在第在第 j(j=m)個時刻以前，譯碼器計算所有的長為個時刻以前，譯碼器計算所有的長為 m 個分支的部個分支的部分路徑值，對進入分路徑值，對進入 2km 個狀態(tài)的每一條部分路徑都保留。個狀態(tài)的每一條部分路徑都保留。第第 m 個時刻開始，對進入每一個狀態(tài)的部分路徑進行計算，這個時刻開始，對進入每一個狀態(tài)的部分路徑進行計算，這樣的路徑有樣的路徑有 2k 條，挑選具有最大部分路徑值的部分路徑為幸條，挑選具有最大部分路徑值的部分路徑為幸存路徑，刪去進入該狀態(tài)的其它路徑，然后，幸存路徑向前延存路徑，

49、刪去進入該狀態(tài)的其它路徑，然后，幸存路徑向前延長一個分支。長一個分支。重復第二步的計算、比較和判決過程。若輸入接收序列長為重復第二步的計算、比較和判決過程。若輸入接收序列長為(L+m)k，其中，后其中，后 m 段是人為加入的全段是人為加入的全0段，則譯碼一直進段，則譯碼一直進行到行到(L+m)個時刻為止。個時刻為止。若進入某個狀態(tài)的部分路徑中，有兩條的部分路徑值相等，則可若進入某個狀態(tài)的部分路徑中，有兩條的部分路徑值相等，則可任選其一作為幸存路徑。任選其一作為幸存路徑。維特比譯碼的基本原理維特比譯碼的基本原理小結小結R=k/n第三節(jié)第三節(jié) 簡單的差錯控制編碼簡單的差錯控制編碼奇偶監(jiān)督碼、水平奇

50、偶監(jiān)督碼、二維奇偶監(jiān)督奇偶監(jiān)督碼、水平奇偶監(jiān)督碼、二維奇偶監(jiān)督碼的構成思路、檢錯能力碼的構成思路、檢錯能力第四節(jié)第四節(jié) 漢明碼及線性分組碼漢明碼及線性分組碼1 漢明碼漢明碼 r與與n的關系的關系 （7，4）漢明碼（監(jiān)督方程、糾檢錯方法、）漢明碼（監(jiān)督方程、糾檢錯方法、幾個要點）幾個要點）2 線性分組碼的概念、主要性質線性分組碼的概念、主要性質 第五節(jié)第五節(jié) 循環(huán)碼循環(huán)碼 碼組碼組A碼的多項式碼的多項式 循環(huán)特性循環(huán)特性生成多項式（最高冪次）概念、求法生成多項式（最高冪次）概念、求法 生成矩陣生成矩陣 第六節(jié)第六節(jié) 卷積碼卷積碼 基本概念、約束長度、編碼效率基本概念、約束長度、編碼效率作業(yè)作業(yè)P1291，3，4，5，7，8，9，12，13，15,16（除（除15題外寫在書上）題外寫在書上）