數(shù)據(jù)通信原理3課件

第三章差錯(cuò)控制本章首先討論差錯(cuò)控制的基本概念及原理，介紹簡(jiǎn)單的差錯(cuò)控制協(xié)議，然后詳細(xì)介紹幾種簡(jiǎn)單的差錯(cuò)控制編碼、漢明碼、循環(huán)碼，并具體分析了線性分組碼的一般特性，最后探討了卷積碼的相關(guān)內(nèi)容。第三章差錯(cuò)控制本章首先討論差錯(cuò)控制3.1差錯(cuò)控制的基本概念及原理3.1.1差錯(cuò)控制的基本概念1.差錯(cuò)分類:隨機(jī)差錯(cuò)、突發(fā)差錯(cuò)隨機(jī)差錯(cuò)又稱獨(dú)立差錯(cuò)，它是指那些獨(dú)立地、稀疏地和互不相關(guān)地發(fā)生的差錯(cuò)。突發(fā)差錯(cuò)是指一串串，甚至是成片出現(xiàn)的差錯(cuò)，差錯(cuò)之間有相關(guān)性，差錯(cuò)出現(xiàn)是密集的。例：數(shù)據(jù)序列1

01100011101

××××××××這一串為突發(fā)差錯(cuò)（中間可能有不錯(cuò)的碼）3.1差錯(cuò)控制的基本概念及原理3.1.1差錯(cuò)控制的基本概例1發(fā)送數(shù)據(jù)序列：10010111001接收數(shù)據(jù)序列：11111001110差錯(cuò)序列：01101110111“0”表示沒錯(cuò)；“1”表示有錯(cuò)例1發(fā)送數(shù)據(jù)序列：10010112.差錯(cuò)控制的基本思路差錯(cuò)控制的基本思路是：在發(fā)送端被傳送的信息碼序列（本身無規(guī)律）的基礎(chǔ)上，按照一定的規(guī)則加入若干監(jiān)督碼元后進(jìn)行傳輸，這些加入的碼元與原來的信息碼序列之間存在著某種確定的約束關(guān)系。在接收數(shù)據(jù)時(shí)，檢驗(yàn)信息碼元與監(jiān)督碼元之間的既定的約束關(guān)系，如該關(guān)系遭到破壞，則收端可以發(fā)現(xiàn)傳輸中的錯(cuò)誤，乃至糾正錯(cuò)誤。此過程叫信息碼+監(jiān)督碼=碼組r+k=n差錯(cuò)控制編碼或糾錯(cuò)編碼或信道編碼2.差錯(cuò)控制的基本思路差錯(cuò)控制的基本思路是：在發(fā)送端被傳送的3.差錯(cuò)控制方式檢錯(cuò)重發(fā)ARQ前向糾錯(cuò)FEC混合糾錯(cuò)檢錯(cuò)HEC信息反饋IRQ3.差錯(cuò)控制方式檢錯(cuò)重發(fā)ARQ（1）檢錯(cuò)重發(fā)(ARQ)（自動(dòng)重發(fā)請(qǐng)求）①ARQ的思路ARQ是在發(fā)送端對(duì)數(shù)據(jù)序列進(jìn)行分組編碼，加入一定監(jiān)督碼元使之具有一定的檢錯(cuò)能力，成為能夠發(fā)現(xiàn)錯(cuò)誤的碼組。接收端收到碼組后，按一定規(guī)則對(duì)其進(jìn)行有無錯(cuò)誤的判別，并把判決結(jié)果(應(yīng)答信號(hào))通過反向信道送回發(fā)送端。如有錯(cuò)誤，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為已正確接收到信息為止。②ARQ的重發(fā)方式ARQ有3種重發(fā)方式，即停發(fā)等候重發(fā)，返回重發(fā)和選擇重發(fā)。（1）檢錯(cuò)重發(fā)(ARQ)（自動(dòng)重發(fā)請(qǐng)求）三種重發(fā)方式a.停止等待協(xié)議當(dāng)重發(fā)方式采用停發(fā)等候重發(fā)時(shí)，應(yīng)該遵循停止等待協(xié)議。停止等待協(xié)議規(guī)定：發(fā)送端每發(fā)送一個(gè)數(shù)據(jù)幀（對(duì)應(yīng)一個(gè)碼組）就暫停下來，等待接收端的應(yīng)答。接收端收到數(shù)據(jù)幀進(jìn)行差錯(cuò)檢測(cè)，若數(shù)據(jù)幀沒錯(cuò)，就向發(fā)送端返回一個(gè)確認(rèn)幀ACK，發(fā)送端再發(fā)送下一個(gè)數(shù)據(jù)幀；若接收端檢驗(yàn)出數(shù)據(jù)幀有錯(cuò)，就向發(fā)送端返回一個(gè)否認(rèn)幀NAK，發(fā)送端重發(fā)剛才所發(fā)數(shù)據(jù)幀，直到?jīng)]錯(cuò)為止。b.連續(xù)ARQ協(xié)議連續(xù)ARQ協(xié)議的重發(fā)方式是返回重發(fā)，即發(fā)送端從出錯(cuò)數(shù)據(jù)幀及以后的各幀都要重發(fā)。c.選擇重發(fā)ARQ協(xié)議選擇重發(fā)ARQ協(xié)議的重發(fā)方式是選擇重發(fā)，即發(fā)送端只重發(fā)出錯(cuò)數(shù)據(jù)幀。三種重發(fā)方式a.停止等待協(xié)議停止等待(協(xié)議算法)重發(fā)

數(shù)據(jù)幀在實(shí)際鏈路上傳輸有四種情況，如圖所示。停止等待(協(xié)議算法)重發(fā)

數(shù)據(jù)幀在實(shí)際鏈路上傳輸有四種情況，數(shù)據(jù)通信原理3課件③ARQ的優(yōu)缺點(diǎn)需反向信道，實(shí)時(shí)性差編碼效率較高譯碼設(shè)備較簡(jiǎn)單③ARQ的優(yōu)缺點(diǎn)需反向信道，實(shí)時(shí)性差（2）前向糾錯(cuò)（FEC）（自動(dòng)糾錯(cuò)）①FEC的思路前向糾錯(cuò)系統(tǒng)中，發(fā)送端的信道編碼器將輸入數(shù)據(jù)序列變換成能夠糾正錯(cuò)誤的碼，接收端的譯碼器根據(jù)編碼規(guī)律檢驗(yàn)出錯(cuò)誤的位置并自動(dòng)糾正。②FEC的優(yōu)缺點(diǎn)●不需要反向信道，實(shí)時(shí)性好?！袢秉c(diǎn)是所選擇的糾錯(cuò)碼必須與信道的錯(cuò)碼特性密切配合，否則很難達(dá)到降低錯(cuò)碼率的要求；●譯碼設(shè)備復(fù)雜；而要求附加的監(jiān)督碼也較多，傳輸效率就低。（2）前向糾錯(cuò)（FEC）（自動(dòng)糾錯(cuò)）(3)混合糾錯(cuò)檢錯(cuò)（HEC）①HEC的思路混合糾錯(cuò)檢錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合。在這種系統(tǒng)中，發(fā)送端發(fā)出同時(shí)具有檢錯(cuò)和糾錯(cuò)能力的碼，接收端收到碼后，檢查錯(cuò)誤情況，如果錯(cuò)誤少于糾錯(cuò)能力，則自行糾正；如果干擾嚴(yán)重，錯(cuò)誤很多，超出糾正能力，但能檢測(cè)出來，則經(jīng)反向信道要求發(fā)端重發(fā)。

②HEC的優(yōu)缺點(diǎn)混合糾錯(cuò)檢錯(cuò)方式在實(shí)時(shí)性和譯碼復(fù)雜性方面是前向糾錯(cuò)和檢錯(cuò)重發(fā)方式的折衷，因而近年來，在數(shù)據(jù)通信系統(tǒng)中采用較多。(3)混合糾錯(cuò)檢錯(cuò)（HEC）(4)信息反饋（IRQ）①IRQ的思路信息反饋方式(IRQ)在發(fā)送端不進(jìn)行糾錯(cuò)編碼，接收端把收到的數(shù)據(jù)序列全部由反向信道送回發(fā)端，發(fā)端自己比較發(fā)送的數(shù)據(jù)序列與送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)是否有錯(cuò)誤，并把認(rèn)為錯(cuò)誤的數(shù)據(jù)序列的原數(shù)據(jù)再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯(cuò)誤為止。②IRQ的優(yōu)缺點(diǎn)●這種方式的優(yōu)點(diǎn)是不需要糾錯(cuò)、檢錯(cuò)的編譯器，設(shè)備簡(jiǎn)單。●缺點(diǎn)是需要和前向信道相同的反向信道，實(shí)時(shí)性差。●發(fā)送端需要一定容量的存儲(chǔ)器以存儲(chǔ)發(fā)送碼組，環(huán)路時(shí)延越大，數(shù)據(jù)速率越高，所需存儲(chǔ)容量越大。(4)信息反饋（IRQ）練習(xí)差錯(cuò)控制方式中不需反向信道的是實(shí)時(shí)性最好的是不需信道編譯碼器的是用得最多的是前向糾錯(cuò)FEC前向糾錯(cuò)FEC信息反饋IRQ混合糾錯(cuò)檢錯(cuò)HEC練習(xí)差錯(cuò)控制方式中3.1.2差錯(cuò)控制的基本原理

1.差錯(cuò)控制的原理傳兩個(gè)消息（1）發(fā)1位碼

1→00→1無糾檢錯(cuò)能力（2）發(fā)2位碼

11→1000→01可檢錯(cuò)1位3.1.2差錯(cuò)控制的基本原理

1.差錯(cuò)控制的原理傳兩個(gè)消息（3）發(fā)3位碼

111000可糾錯(cuò)1位可檢錯(cuò)2位收發(fā)兩端約定，當(dāng)收到兩個(gè)以上的1時(shí)，認(rèn)為發(fā)的是111；當(dāng)收到兩個(gè)以上的0時(shí)，認(rèn)為發(fā)的是000。

111→110

000→001若無以上約定，111000→110（3）發(fā)3位碼可糾錯(cuò)1位可檢錯(cuò)2位收發(fā)兩端約定，1糾錯(cuò)編碼之所以具有檢錯(cuò)和糾錯(cuò)能力，是因?yàn)樵谛畔⒋a之外附加了監(jiān)督碼，即碼的檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度來換取的。加入監(jiān)督碼越多，碼的檢錯(cuò)、糾錯(cuò)能力越強(qiáng)，但信息傳輸效率下降也越多。在糾錯(cuò)編碼中將信息傳輸效率也稱為編碼效率，定義為（3-1）糾錯(cuò)編碼之所以具有檢錯(cuò)和糾錯(cuò)能力，是因?yàn)樵谛畔?.漢明距離與檢錯(cuò)和糾錯(cuò)能力的關(guān)系

（1）幾個(gè)概念碼組的重量——碼組中非零碼元的數(shù)目為碼組的重量，簡(jiǎn)稱碼重。碼距——把兩個(gè)碼組中對(duì)應(yīng)碼位上具有不同二進(jìn)制碼元的個(gè)數(shù)定義為兩碼組的距離，簡(jiǎn)稱碼距。例：1101010001碼距是3漢明距離——在一種編碼中，任意兩個(gè)許用碼組間距離的最小值，稱為這一編碼的漢明距離，以表示。2.漢明距離與檢錯(cuò)和糾錯(cuò)能力的關(guān)系

（1）幾個(gè)概念碼組的重量例：一碼組集合10111110010001011010333422例：一碼組集合101113334223.糾錯(cuò)編碼的分類(1)按碼組的功能分，有檢錯(cuò)碼和糾錯(cuò)碼兩類。(2)按碼組中監(jiān)督碼元與信息碼元之間的關(guān)系分，有線性碼和非線性碼兩類。(3)按照信息碼元與監(jiān)督碼元的約束關(guān)系，又可分為分組碼和卷積碼兩類。(4)按照信息碼元在編碼前后是否保持原來的形式不變，可劃分為系統(tǒng)碼和非系統(tǒng)碼。(5)按糾正差錯(cuò)的類型可分為糾正隨機(jī)錯(cuò)誤的碼和糾正突發(fā)錯(cuò)誤的碼。(6)按照每個(gè)碼元取值來分，可分為二進(jìn)制碼與多進(jìn)制碼。3.糾錯(cuò)編碼的分類3.2簡(jiǎn)單的差錯(cuò)控制編碼

3.2.1奇偶監(jiān)督碼(編碼規(guī)則)設(shè)碼組長(zhǎng)度為n，表示為()，其中前n-1位為信息碼元，第n位為監(jiān)督位a0。3.2簡(jiǎn)單的差錯(cuò)控制編碼

3.2.1奇偶監(jiān)督碼(編碼規(guī)則2、監(jiān)督方程偶檢驗(yàn)的監(jiān)督關(guān)系（偶監(jiān)督方程）在奇校驗(yàn)的監(jiān)督關(guān)系（奇監(jiān)督方程）1、概念偶監(jiān)督碼---信息碼與監(jiān)督碼合在一起“1”的個(gè)數(shù)是偶數(shù)奇監(jiān)督碼---信息碼與監(jiān)督碼合在一起“1”的個(gè)數(shù)是奇數(shù)2、監(jiān)督方程偶檢驗(yàn)的監(jiān)督關(guān)系（偶監(jiān)督方程）只能發(fā)現(xiàn)單個(gè)或奇數(shù)個(gè)錯(cuò)誤，不能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤只能發(fā)現(xiàn)單個(gè)或奇數(shù)個(gè)錯(cuò)誤，3.2.1水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼的構(gòu)成思路是：將信息碼序列按行排成方陣，每行后面加一個(gè)奇或偶監(jiān)督編碼，即每行為一個(gè)奇偶監(jiān)督碼組(見表3-2，以偶監(jiān)督為例)，但發(fā)送時(shí)則按列的順序傳輸：111011100110000…10101，接收端仍將碼元排成與發(fā)送端一樣的方陣形式，然后按行進(jìn)行奇偶校驗(yàn)。表3-2水平偶監(jiān)督碼信息碼元監(jiān)督碼元

11100110001101001101100001110100010000101100111011

10101*******3.2.1水平奇偶監(jiān)督碼信檢錯(cuò)能力（1）可發(fā)現(xiàn)某一行上所有奇數(shù)個(gè)錯(cuò)誤（2）能檢測(cè)出所有長(zhǎng)度不大于方陣中行數(shù)的突發(fā)錯(cuò)誤討論：

水平奇偶監(jiān)督碼是檢錯(cuò)碼，屬于線性分組碼。

檢錯(cuò)能力（1）可發(fā)現(xiàn)某一行上所有奇數(shù)個(gè)錯(cuò)誤討論：

水平奇偶監(jiān)3.2.2二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼是將水平奇偶監(jiān)督碼推廣而得，又稱水平垂直奇偶監(jiān)督碼、行列監(jiān)督碼和方陣碼。它的方法是在水平監(jiān)督基礎(chǔ)上對(duì)表3-2方陣中每一列再進(jìn)行奇偶校驗(yàn)，就可得表3-3（以偶監(jiān)督為例）所示的方陣。發(fā)送是按列或按行的順序傳輸。接收端重新將碼元排成發(fā)送時(shí)方陣形式，然后每行、每列都進(jìn)行奇偶校驗(yàn)。表3-3二維偶監(jiān)督碼信息碼元監(jiān)督碼元

11100110001101001101100001110100010000101100111011

監(jiān)督碼元

1010101101100011*******3.2.2二維奇偶監(jiān)督碼二維奇偶監(jiān)檢錯(cuò)能力（1）可發(fā)現(xiàn)某行或某列上奇數(shù)個(gè)錯(cuò)誤。（2）能檢測(cè)出所有長(zhǎng)度不大于方陣中行數(shù)（或列數(shù)）的突發(fā)錯(cuò)誤（3）能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤。但若偶數(shù)個(gè)錯(cuò)誤恰好分布在矩陣的四個(gè)頂點(diǎn)上時(shí)，這樣的偶數(shù)個(gè)錯(cuò)誤是檢測(cè)不出來的。（4）可以糾正某些錯(cuò)誤，當(dāng)某行某列均不滿足監(jiān)督關(guān)系，可判定該行該列交叉位置的碼元有錯(cuò)，從而糾正這一位上的錯(cuò)誤。討論：二維奇偶監(jiān)督碼是檢錯(cuò)碼或糾錯(cuò)碼，屬于線性分組碼。檢錯(cuò)能力（1）可發(fā)現(xiàn)某行或某列上奇數(shù)個(gè)錯(cuò)誤。討論：二維奇偶監(jiān)3.3漢明碼及線性分組碼

3.3.1漢明碼1、（n,k）漢明碼r與n的關(guān)系為3.3漢明碼及線性分組碼1、（n,k）漢明碼數(shù)據(jù)通信原理3課件例題例題（2）糾檢錯(cuò)

方法------接收端收到（7，4）漢明碼，由下述方程計(jì)算校正子，然后查表3-4可知此碼組是否有錯(cuò)以及差錯(cuò)的確切位置（2）糾檢錯(cuò)

方法------接收端收到（7，4）漢明碼，由

s1s2s3錯(cuò)碼位置

000無錯(cuò)

001

a0

010a1

100a2

011a3

101a4

110a5

111a6表3-4較正子與錯(cuò)碼位置**s1s2s3例：接收端收到某（7，4）漢明碼為1001010，此（7，4）漢明碼是否有錯(cuò)？錯(cuò)碼位置如何？例：接收端收到某（7，4）漢明碼為1001010，此（7，4討論①漢明距離

②編碼效率討論①漢明距離

②編碼效率數(shù)據(jù)通信原理3課件3.3.2線性分組碼2.線性分組碼的主要性質(zhì)

(1)封閉性所謂封閉性，是指一種線性分組碼中的任意兩個(gè)碼組之逐位模2和仍為這種碼中的另一個(gè)許用碼組。線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼，分組碼是監(jiān)督碼僅對(duì)本碼組起監(jiān)督作用，既是線性碼又是分組碼稱為線性分組碼。3.3.2線性分組碼2.線性分組碼的主要性質(zhì)(2)碼的最小距離等于非零碼的最小重量（除了全0碼組之外）因?yàn)榫€性分組碼具有封閉性，因而兩個(gè)碼組之間的距離必是另一碼組的重量。(2)碼的最小距離等于非零碼的最小重量（除了循環(huán)碼是線性分組碼中一類重要的碼。

3.4.1循環(huán)碼的循環(huán)特性循環(huán)碼的循環(huán)性是指循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后(將最右端的碼元移至左端，或反之)所得到的碼組仍為它的一個(gè)許用碼組。表3-6給出一種(7，3)循環(huán)碼的全部碼組，由此表可直觀看出這種碼的循環(huán)性。例如，表中的第2碼組向右循環(huán)移一位即得到第5碼組，第2碼組向左循環(huán)移一位即得到第3碼組。3.4循環(huán)碼循環(huán)碼是線性分組碼中一類重要的碼。

3.4.1循環(huán)碼的循表3-6（7，3）循環(huán)碼的碼組

碼組編號(hào)信息位監(jiān)督位

碼組編號(hào)信息位監(jiān)督位

1234

000001010011

0000011111101001

5678

100101110111

1011110001010010表3-6（7，3）循環(huán)碼的碼組信息位數(shù)據(jù)通信原理3課件1.碼的多項(xiàng)式若碼組

，則相應(yīng)的多項(xiàng)式表示為

3.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣3.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣?yán)?：A=1011011例2：已知，寫出對(duì)應(yīng)的碼組(n=7)。解：A=1101001例1：A=1011011例2：已知循環(huán)碼的2k個(gè)碼組中，有一個(gè)碼組前k-1位碼元均為0，第k位碼元為1，第n位（最后一位）碼元為1，此碼組對(duì)應(yīng)的多項(xiàng)式。例：求表3-6（7，3）循環(huán)碼的生成多項(xiàng)式。表3-6（7，3）循環(huán)碼對(duì)應(yīng)生成多項(xiàng)式的碼組為第3個(gè)碼組0010111，生成多項(xiàng)式為2、循環(huán)碼的生成多項(xiàng)式循環(huán)碼的2k個(gè)碼組中，有一個(gè)碼組前k-1位碼元例3.生成矩陣G由循環(huán)碼的生成多項(xiàng)式g(x)可得到生成矩陣G(x)，為轉(zhuǎn)換后，典型的生成矩陣為3.生成矩陣G轉(zhuǎn)換后，典型的生成矩陣為生成矩陣可以通過線性變換將非典型的生成矩陣轉(zhuǎn)換為典型的生成矩陣，具體方法是：任意幾行模二加取代某一行。生成矩陣可以通過線性變換將非典型的生成矩陣轉(zhuǎn)換為典型的生成矩例例將三位信息碼（000、001、010、011…111）與典型的生成矩陣G相乘便可得到全部碼組，即表3-6所示。將三位信息碼（00數(shù)據(jù)通信原理3課件

信息字段為K位，校驗(yàn)字段為R位，碼字長(zhǎng)度為N(N=K+R)位

V(x)=xRm(x)+r(x)m(x)為K次信息多項(xiàng)式，

r(x)為R次校驗(yàn)多項(xiàng)式例如：信息字段代碼為:1011001對(duì)應(yīng)m(x)=x6+x4+x3+1g(x)=x4+x3+1為生成多項(xiàng)式g(x)的代碼為:11001校驗(yàn)碼生成的另一種方法信息字段為K位，校驗(yàn)字段為R位，碼字長(zhǎng)度為N(N=K+R

信息字段移位：

x4m(x)=x10+x8+x7+x4—10110010000校驗(yàn)字段形成：（二進(jìn)制除）取余數(shù)

1100110110010000得：1010傳輸字段：10110011010校驗(yàn)：接收字段/相同的生成碼（二進(jìn)制除），除盡（正確），否則（錯(cuò)）信息字段移位：BinaryDivisionBinaryDivision常用的CRC生成多項(xiàng)式g(x)為:CRC16=x16+x15+x2+1R=16，IBM專用

CRC16=x16+x12+x5+1R=16，CCITT專用

CRC32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1R=32,LAN中常用數(shù)據(jù)通信原理3課件3.5卷積碼1.卷積碼的概念在分組碼中，任何一段規(guī)定時(shí)間內(nèi)編碼器產(chǎn)生的n個(gè)碼元的一個(gè)碼組，其監(jiān)督位完全決定于這段時(shí)間中輸入的k個(gè)信息位，這個(gè)碼組中的n-k個(gè)監(jiān)督位僅對(duì)本碼組起監(jiān)督作用。卷積碼則不然，編碼器在任何一段規(guī)定時(shí)間內(nèi)產(chǎn)生的n個(gè)碼元，其監(jiān)督位不僅取決于這段時(shí)間中的k個(gè)信息位，而且還取決于前N-1段規(guī)定時(shí)間內(nèi)的信息位。換句話說，監(jiān)督位不僅對(duì)本碼組起監(jiān)督作用，還對(duì)前N-1個(gè)碼組也起監(jiān)督作用。這段N時(shí)間內(nèi)的碼元數(shù)目nN稱為這種卷積碼的約束長(zhǎng)度。通常把卷積碼記作(n,k,N)，其編碼效率3.5卷積碼1.卷積碼的概念卷積碼的基本概念卷積碼的基本概念數(shù)據(jù)通信原理3課件2卷積碼的編碼簡(jiǎn)單例子：由2個(gè)移位寄存器和1個(gè)模2加電路構(gòu)成（2，1，2）卷積碼編碼器D1D2+m1m2m3m4m5m6tm1c1m2c2m3c3m4c4m5c5m6c6tmcmi.m1.0.m2.m1.m3.m2.mi-1ci+1

=mi+m(i+1)2卷積碼的編碼簡(jiǎn)單例子：由2個(gè)移位寄存器和1個(gè)模2加電路構(gòu)2卷積碼的解碼D1D2+++D3與門.m1’.c1’0S0.mi+1’0.m2’.c2’.m1’.S1S0.m3’.m2’.c3’.S2S1.mi’.ci+1’SiSi-1S0=0+m1’+c1’S1=m1’+m2’+c2’S2=m2’+m3’+c3’S3=m3’+m4’+c4’校正子Si=mi’+m(i+1)’+ci+1’此為門限解碼，屬于代數(shù)解碼，適于約束長(zhǎng)度較短的卷積碼；另一類為概率解碼2卷積碼的解碼D1D2+++D3與.m1’.c1’0S（2，1，3）卷積碼編碼器m1m2m3++.c1c2C1=m1+m2+m3C2=m1+m3輸入比特狀態(tài)比特輸入序列輸出序列（2，1，3）卷積碼編碼器m1m2m3++.c1.m2m3=00(左)輸入m1=000移位后10001001110010(左)輸入m1=101110010011100100111001001110010011100100111卷積碼的樹狀圖.m2m3=00(左)輸入00移位后100010011100（2，1，3）卷積碼的樹狀圖.a(m3m2)(左)輸入m1=0a.c1c2=00babcdab(左)輸入m1=1cdabcdabcdabcdabcdabcd0000001111111111101010010111000110當(dāng)輸入序列為11010…時(shí)，輸出碼元序列？1101010010…（2，1，3）卷積碼的樹狀圖.a(m3m2)(左)輸入a.c輸入為0110…時(shí)，輸出碼元序列？000111101011輸入為000111101（2，1，3）卷積碼的網(wǎng)格圖（籬笆圖）abcd（2，1，3）卷積碼的網(wǎng)格圖（籬笆圖）abcd（2，1，3）卷積碼的狀態(tài)圖0，實(shí)線；1，虛線00=a01=b10=c11=d00=a01=b10=c11=d0011111001100100（2，1，3）卷積碼的狀態(tài)圖0，實(shí)線；1，虛線00=a01卷積碼的譯碼方法代數(shù)譯碼利用編碼本身得代數(shù)結(jié)構(gòu)進(jìn)行解碼，并不考慮信道的統(tǒng)計(jì)特性。其主要特點(diǎn)是算法簡(jiǎn)單，易于實(shí)現(xiàn)，但是它的誤碼性能要比概率譯碼差。其譯碼方法是從線性碼的監(jiān)督子出發(fā)，找到一組特殊的能夠檢查信息位置是否發(fā)生錯(cuò)誤的方程組，從而實(shí)現(xiàn)糾錯(cuò)譯碼。概率譯碼的基本思想是：把已經(jīng)接收到的序列與所有可能的發(fā)送序列相比較，選擇其中漢明距離最小的一個(gè)序列作為發(fā)送序列。維特比譯碼是目前用得較多的一種譯碼方法。卷積碼的譯碼方法代數(shù)譯碼利用編碼本身得代數(shù)結(jié)構(gòu)進(jìn)行解碼，并不

舉例說明維特比譯碼工作原理維特比提出了一種算法：譯碼器不是在籬笆圖上一次就計(jì)算和比較2Lk條路徑，而是接收一段，就計(jì)算、比較一段，從而在每個(gè)狀態(tài)時(shí)，選擇進(jìn)入該狀態(tài)的最可能的分支。維特比譯碼的基本思想：將接收序列R與籬笆圖上的路徑逐分支地比較，比較的長(zhǎng)度一般取(5~6)mn，然后留下與R距離最小的路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑逐分支地延長(zhǎng)并存儲(chǔ)起來。幸存路徑的數(shù)目等于狀態(tài)數(shù)：2km以(2,1,2)非系統(tǒng)碼為例說明維特比譯碼的基本思想：設(shè)發(fā)送序列C為全0；接收序列R=[10,00,01,00,00,00,00,…]

維特比譯碼的基本原理舉例說明維特比譯碼工作原理維特比譯碼的基本原理假設(shè)譯碼器的初始狀態(tài)為全0；第0個(gè)時(shí)刻：接收序列的第0個(gè)分支R0=10進(jìn)入譯碼器。從S0狀態(tài)有兩個(gè)分支，它們是00和11，R0與這兩個(gè)分支比較，比較的結(jié)果和到達(dá)的狀態(tài)如表9.2所示：每個(gè)狀態(tài)/節(jié)點(diǎn)都有兩個(gè)存儲(chǔ)器：路徑存儲(chǔ)器：存儲(chǔ)該狀態(tài)的部分路徑；路徑值存儲(chǔ)器：存儲(chǔ)達(dá)到該狀態(tài)的部分路徑值(累加距離)。

維特比譯碼的基本原理假設(shè)譯碼器的初始狀態(tài)為全0；維特比譯碼的基本原理第一個(gè)時(shí)刻：進(jìn)入譯碼器的接收碼組R1=00和此時(shí)刻出發(fā)的四條分支比較，比較結(jié)果和達(dá)到狀態(tài)如表9.3所示：從第一個(gè)時(shí)刻到第二個(gè)時(shí)刻：共有四條路徑，到達(dá)S0,S1,S2和S3。在第二個(gè)時(shí)刻以前譯碼器不做任何選擇和判決。每個(gè)狀態(tài)的路徑存儲(chǔ)器存儲(chǔ)下此時(shí)刻的幸存路徑：0000,0011,1110,1101；每個(gè)狀態(tài)的路徑值存儲(chǔ)器存儲(chǔ)了此時(shí)刻到達(dá)該狀態(tài)的幸存路徑累加值(累加距離)。

維特比譯碼的基本原理第一個(gè)時(shí)刻：進(jìn)入譯碼器的接收碼組R1=00和此時(shí)刻出發(fā)的從第二個(gè)時(shí)刻起：第二個(gè)接收碼組R2=01進(jìn)入譯碼器，從籬笆圖上可見，從第二個(gè)時(shí)刻到第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的分支有兩個(gè)（或者說在第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的路徑有兩條）。譯碼器將接收碼組R2與進(jìn)入每個(gè)狀態(tài)的兩個(gè)分支進(jìn)行比較和判決，選擇一個(gè)累加距離（部分路徑值）最小的路徑作為進(jìn)入該狀態(tài)的幸存路徑。這樣的幸存路徑共四條，比較和判決的過程如下：

維特比譯碼的基本原理從第二個(gè)時(shí)刻起：第二個(gè)接收碼組R2=01進(jìn)入譯碼器，從籬經(jīng)過比較后選擇：部分路徑

000000為到達(dá)S0

狀態(tài)的幸存路徑；部分路徑000011為到達(dá)

S1狀態(tài)的幸存路徑；部分路徑110101為到達(dá)S2狀態(tài)的幸存路徑；部分路徑001101為到達(dá)S3

狀態(tài)的幸存路徑。按照上述方法，接收序列的諸碼組依次進(jìn)入譯碼器，每個(gè)時(shí)刻進(jìn)入一個(gè)碼組，沿著籬笆圖對(duì)每個(gè)狀態(tài)按部分路徑值（累加距離）的大小，選擇一條幸存路徑。在每個(gè)狀態(tài)上進(jìn)行判決時(shí)，可能出現(xiàn)進(jìn)入這一狀態(tài)的兩條路徑的距離值相同，這時(shí)可以任選其一，因?yàn)閷?duì)以后的判決而言，無論選擇那一條路徑，累加距離是相同的。經(jīng)過比較后選擇：對(duì)本例而言，按上述算法進(jìn)行到第十一個(gè)分支后，四條路徑的前面分支都合并在一起。所以，只要譯碼深度足夠，就可達(dá)到較低的錯(cuò)誤概率。一般，約為(5~6)mn，所以，維特比譯碼的延時(shí)可達(dá)(5~6)m個(gè)單位時(shí)刻（每個(gè)單位時(shí)刻為n個(gè)碼元長(zhǎng)度）就可以對(duì)第0個(gè)接收碼組的信息元進(jìn)行判決。依此類推，對(duì)接收序列中的諸碼組進(jìn)行譯碼。維特比譯碼的一次運(yùn)算：計(jì)算每個(gè)輸入分支的度量值（分支距離、累加距離）；比較各部分路徑的度量值，選擇一條作為幸存路徑。籬笆圖中共有2km個(gè)狀態(tài)，因此，維特比譯碼的計(jì)算量與編碼存儲(chǔ)m成指數(shù)關(guān)系變化，所以采用維特比算法譯碼的卷積碼，其m不能選的太大。

維特比譯碼的基本原理對(duì)本例而言，按上述算法進(jìn)行到第十一個(gè)分支后，四條路維特比譯

維特比譯碼的基本原理維特比譯碼的基本原理

維特比譯碼的基本原理維特比譯碼的基本原理7.6維特比譯碼的基本原理7.6維特比譯碼的基本原理7.6維特比譯碼的基本原理7.6維特比譯碼的基本原理

維特比譯碼的基本原理維特比譯碼的基本原理

總結(jié)維特比算法的步驟在第j(j=m)個(gè)時(shí)刻以前，譯碼器計(jì)算所有的長(zhǎng)為m個(gè)分支的部分路徑值，對(duì)進(jìn)入2km個(gè)狀態(tài)的每一條部分路徑都保留。第m個(gè)時(shí)刻開始，對(duì)進(jìn)入每一個(gè)狀態(tài)的部分路徑進(jìn)行計(jì)算，這樣的路徑有2k條，挑選具有最大部分路徑值的部分路徑為幸存路徑，刪去進(jìn)入該狀態(tài)的其它路徑，然后，幸存路徑向前延長(zhǎng)一個(gè)分支。重復(fù)第二步的計(jì)算、比較和判決過程。若輸入接收序列長(zhǎng)為(L+m)k，其中，后m段是人為加入的全0段，則譯碼一直進(jìn)行到(L+m)個(gè)時(shí)刻為止。若進(jìn)入某個(gè)狀態(tài)的部分路徑中，有兩條的部分路徑值相等，則可任選其一作為幸存路徑。

維特比譯碼的基本原理總結(jié)維特比算法的步驟維特比譯碼的基本原理小結(jié)小結(jié)R=k/nR=k/n第三節(jié)簡(jiǎn)單的差錯(cuò)控制編碼

奇偶監(jiān)督碼、水平奇偶監(jiān)督碼、二維奇偶監(jiān)督碼的構(gòu)成思路、檢錯(cuò)能力

第四節(jié)漢明碼及線性分組碼

1漢明碼r與n的關(guān)系

（7，4）漢明碼（監(jiān)督方程、糾檢錯(cuò)方法、幾個(gè)要點(diǎn)）

2線性分組碼的概念、主要性質(zhì)

第三節(jié)簡(jiǎn)單的差錯(cuò)控制編碼

奇偶監(jiān)督碼、水平奇偶監(jiān)督碼、二第五節(jié)循環(huán)碼

碼組A碼的多項(xiàng)式

循環(huán)特性

生成多項(xiàng)式（最高冪次）概念、求法

生成矩陣

第六節(jié)卷積碼

基本概念、約束長(zhǎng)度、編碼效率

第五節(jié)循環(huán)碼

碼組A作業(yè)P1291，3，4，5，7，8，9，12，13，15,16（除15題外寫在書上）作業(yè)P129第三章差錯(cuò)控制本章首先討論差錯(cuò)控制的基本概念及原理，介紹簡(jiǎn)單的差錯(cuò)控制協(xié)議，然后詳細(xì)介紹幾種簡(jiǎn)單的差錯(cuò)控制編碼、漢明碼、循環(huán)碼，并具體分析了線性分組碼的一般特性，最后探討了卷積碼的相關(guān)內(nèi)容。第三章差錯(cuò)控制本章首先討論差錯(cuò)控制3.1差錯(cuò)控制的基本概念及原理3.1.1差錯(cuò)控制的基本概念1.差錯(cuò)分類:隨機(jī)差錯(cuò)、突發(fā)差錯(cuò)隨機(jī)差錯(cuò)又稱獨(dú)立差錯(cuò)，它是指那些獨(dú)立地、稀疏地和互不相關(guān)地發(fā)生的差錯(cuò)。突發(fā)差錯(cuò)是指一串串，甚至是成片出現(xiàn)的差錯(cuò)，差錯(cuò)之間有相關(guān)性，差錯(cuò)出現(xiàn)是密集的。例：數(shù)據(jù)序列1

01100011101

××××××××這一串為突發(fā)差錯(cuò)（中間可能有不錯(cuò)的碼）3.1差錯(cuò)控制的基本概念及原理3.1.1差錯(cuò)控制的基本概例1發(fā)送數(shù)據(jù)序列：10010111001接收數(shù)據(jù)序列：11111001110差錯(cuò)序列：01101110111“0”表示沒錯(cuò)；“1”表示有錯(cuò)例1發(fā)送數(shù)據(jù)序列：10010112.差錯(cuò)控制的基本思路差錯(cuò)控制的基本思路是：在發(fā)送端被傳送的信息碼序列（本身無規(guī)律）的基礎(chǔ)上，按照一定的規(guī)則加入若干監(jiān)督碼元后進(jìn)行傳輸，這些加入的碼元與原來的信息碼序列之間存在著某種確定的約束關(guān)系。在接收數(shù)據(jù)時(shí)，檢驗(yàn)信息碼元與監(jiān)督碼元之間的既定的約束關(guān)系，如該關(guān)系遭到破壞，則收端可以發(fā)現(xiàn)傳輸中的錯(cuò)誤，乃至糾正錯(cuò)誤。此過程叫信息碼+監(jiān)督碼=碼組r+k=n差錯(cuò)控制編碼或糾錯(cuò)編碼或信道編碼2.差錯(cuò)控制的基本思路差錯(cuò)控制的基本思路是：在發(fā)送端被傳送的3.差錯(cuò)控制方式檢錯(cuò)重發(fā)ARQ前向糾錯(cuò)FEC混合糾錯(cuò)檢錯(cuò)HEC信息反饋IRQ3.差錯(cuò)控制方式檢錯(cuò)重發(fā)ARQ（1）檢錯(cuò)重發(fā)(ARQ)（自動(dòng)重發(fā)請(qǐng)求）①ARQ的思路ARQ是在發(fā)送端對(duì)數(shù)據(jù)序列進(jìn)行分組編碼，加入一定監(jiān)督碼元使之具有一定的檢錯(cuò)能力，成為能夠發(fā)現(xiàn)錯(cuò)誤的碼組。接收端收到碼組后，按一定規(guī)則對(duì)其進(jìn)行有無錯(cuò)誤的判別，并把判決結(jié)果(應(yīng)答信號(hào))通過反向信道送回發(fā)送端。如有錯(cuò)誤，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為已正確接收到信息為止。②ARQ的重發(fā)方式ARQ有3種重發(fā)方式，即停發(fā)等候重發(fā)，返回重發(fā)和選擇重發(fā)。（1）檢錯(cuò)重發(fā)(ARQ)（自動(dòng)重發(fā)請(qǐng)求）三種重發(fā)方式a.停止等待協(xié)議當(dāng)重發(fā)方式采用停發(fā)等候重發(fā)時(shí)，應(yīng)該遵循停止等待協(xié)議。停止等待協(xié)議規(guī)定：發(fā)送端每發(fā)送一個(gè)數(shù)據(jù)幀（對(duì)應(yīng)一個(gè)碼組）就暫停下來，等待接收端的應(yīng)答。接收端收到數(shù)據(jù)幀進(jìn)行差錯(cuò)檢測(cè)，若數(shù)據(jù)幀沒錯(cuò)，就向發(fā)送端返回一個(gè)確認(rèn)幀ACK，發(fā)送端再發(fā)送下一個(gè)數(shù)據(jù)幀；若接收端檢驗(yàn)出數(shù)據(jù)幀有錯(cuò)，就向發(fā)送端返回一個(gè)否認(rèn)幀NAK，發(fā)送端重發(fā)剛才所發(fā)數(shù)據(jù)幀，直到?jīng)]錯(cuò)為止。b.連續(xù)ARQ協(xié)議連續(xù)ARQ協(xié)議的重發(fā)方式是返回重發(fā)，即發(fā)送端從出錯(cuò)數(shù)據(jù)幀及以后的各幀都要重發(fā)。c.選擇重發(fā)ARQ協(xié)議選擇重發(fā)ARQ協(xié)議的重發(fā)方式是選擇重發(fā)，即發(fā)送端只重發(fā)出錯(cuò)數(shù)據(jù)幀。三種重發(fā)方式a.停止等待協(xié)議停止等待(協(xié)議算法)重發(fā)

數(shù)據(jù)幀在實(shí)際鏈路上傳輸有四種情況，如圖所示。停止等待(協(xié)議算法)重發(fā)

數(shù)據(jù)幀在實(shí)際鏈路上傳輸有四種情況，數(shù)據(jù)通信原理3課件③ARQ的優(yōu)缺點(diǎn)需反向信道，實(shí)時(shí)性差編碼效率較高譯碼設(shè)備較簡(jiǎn)單③ARQ的優(yōu)缺點(diǎn)需反向信道，實(shí)時(shí)性差（2）前向糾錯(cuò)（FEC）（自動(dòng)糾錯(cuò)）①FEC的思路前向糾錯(cuò)系統(tǒng)中，發(fā)送端的信道編碼器將輸入數(shù)據(jù)序列變換成能夠糾正錯(cuò)誤的碼，接收端的譯碼器根據(jù)編碼規(guī)律檢驗(yàn)出錯(cuò)誤的位置并自動(dòng)糾正。②FEC的優(yōu)缺點(diǎn)●不需要反向信道，實(shí)時(shí)性好?！袢秉c(diǎn)是所選擇的糾錯(cuò)碼必須與信道的錯(cuò)碼特性密切配合，否則很難達(dá)到降低錯(cuò)碼率的要求；●譯碼設(shè)備復(fù)雜；而要求附加的監(jiān)督碼也較多，傳輸效率就低。（2）前向糾錯(cuò)（FEC）（自動(dòng)糾錯(cuò)）(3)混合糾錯(cuò)檢錯(cuò)（HEC）①HEC的思路混合糾錯(cuò)檢錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合。在這種系統(tǒng)中，發(fā)送端發(fā)出同時(shí)具有檢錯(cuò)和糾錯(cuò)能力的碼，接收端收到碼后，檢查錯(cuò)誤情況，如果錯(cuò)誤少于糾錯(cuò)能力，則自行糾正；如果干擾嚴(yán)重，錯(cuò)誤很多，超出糾正能力，但能檢測(cè)出來，則經(jīng)反向信道要求發(fā)端重發(fā)。

②HEC的優(yōu)缺點(diǎn)混合糾錯(cuò)檢錯(cuò)方式在實(shí)時(shí)性和譯碼復(fù)雜性方面是前向糾錯(cuò)和檢錯(cuò)重發(fā)方式的折衷，因而近年來，在數(shù)據(jù)通信系統(tǒng)中采用較多。(3)混合糾錯(cuò)檢錯(cuò)（HEC）(4)信息反饋（IRQ）①IRQ的思路信息反饋方式(IRQ)在發(fā)送端不進(jìn)行糾錯(cuò)編碼，接收端把收到的數(shù)據(jù)序列全部由反向信道送回發(fā)端，發(fā)端自己比較發(fā)送的數(shù)據(jù)序列與送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)是否有錯(cuò)誤，并把認(rèn)為錯(cuò)誤的數(shù)據(jù)序列的原數(shù)據(jù)再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯(cuò)誤為止。②IRQ的優(yōu)缺點(diǎn)●這種方式的優(yōu)點(diǎn)是不需要糾錯(cuò)、檢錯(cuò)的編譯器，設(shè)備簡(jiǎn)單?！袢秉c(diǎn)是需要和前向信道相同的反向信道，實(shí)時(shí)性差?！癜l(fā)送端需要一定容量的存儲(chǔ)器以存儲(chǔ)發(fā)送碼組，環(huán)路時(shí)延越大，數(shù)據(jù)速率越高，所需存儲(chǔ)容量越大。(4)信息反饋（IRQ）練習(xí)差錯(cuò)控制方式中不需反向信道的是實(shí)時(shí)性最好的是不需信道編譯碼器的是用得最多的是前向糾錯(cuò)FEC前向糾錯(cuò)FEC信息反饋IRQ混合糾錯(cuò)檢錯(cuò)HEC練習(xí)差錯(cuò)控制方式中3.1.2差錯(cuò)控制的基本原理

1.差錯(cuò)控制的原理傳兩個(gè)消息（1）發(fā)1位碼

1→00→1無糾檢錯(cuò)能力（2）發(fā)2位碼

11→1000→01可檢錯(cuò)1位3.1.2差錯(cuò)控制的基本原理

1.差錯(cuò)控制的原理傳兩個(gè)消息（3）發(fā)3位碼

111000可糾錯(cuò)1位可檢錯(cuò)2位收發(fā)兩端約定，當(dāng)收到兩個(gè)以上的1時(shí)，認(rèn)為發(fā)的是111；當(dāng)收到兩個(gè)以上的0時(shí)，認(rèn)為發(fā)的是000。

111→110

000→001若無以上約定，111000→110（3）發(fā)3位碼可糾錯(cuò)1位可檢錯(cuò)2位收發(fā)兩端約定，1糾錯(cuò)編碼之所以具有檢錯(cuò)和糾錯(cuò)能力，是因?yàn)樵谛畔⒋a之外附加了監(jiān)督碼，即碼的檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度來換取的。加入監(jiān)督碼越多，碼的檢錯(cuò)、糾錯(cuò)能力越強(qiáng)，但信息傳輸效率下降也越多。在糾錯(cuò)編碼中將信息傳輸效率也稱為編碼效率，定義為（3-1）糾錯(cuò)編碼之所以具有檢錯(cuò)和糾錯(cuò)能力，是因?yàn)樵谛畔?.漢明距離與檢錯(cuò)和糾錯(cuò)能力的關(guān)系

（1）幾個(gè)概念碼組的重量——碼組中非零碼元的數(shù)目為碼組的重量，簡(jiǎn)稱碼重。碼距——把兩個(gè)碼組中對(duì)應(yīng)碼位上具有不同二進(jìn)制碼元的個(gè)數(shù)定義為兩碼組的距離，簡(jiǎn)稱碼距。例：1101010001碼距是3漢明距離——在一種編碼中，任意兩個(gè)許用碼組間距離的最小值，稱為這一編碼的漢明距離，以表示。2.漢明距離與檢錯(cuò)和糾錯(cuò)能力的關(guān)系

（1）幾個(gè)概念碼組的重量例：一碼組集合10111110010001011010333422例：一碼組集合101113334223.糾錯(cuò)編碼的分類(1)按碼組的功能分，有檢錯(cuò)碼和糾錯(cuò)碼兩類。(2)按碼組中監(jiān)督碼元與信息碼元之間的關(guān)系分，有線性碼和非線性碼兩類。(3)按照信息碼元與監(jiān)督碼元的約束關(guān)系，又可分為分組碼和卷積碼兩類。(4)按照信息碼元在編碼前后是否保持原來的形式不變，可劃分為系統(tǒng)碼和非系統(tǒng)碼。(5)按糾正差錯(cuò)的類型可分為糾正隨機(jī)錯(cuò)誤的碼和糾正突發(fā)錯(cuò)誤的碼。(6)按照每個(gè)碼元取值來分，可分為二進(jìn)制碼與多進(jìn)制碼。3.糾錯(cuò)編碼的分類3.2簡(jiǎn)單的差錯(cuò)控制編碼

3.2.1奇偶監(jiān)督碼(編碼規(guī)則)設(shè)碼組長(zhǎng)度為n，表示為()，其中前n-1位為信息碼元，第n位為監(jiān)督位a0。3.2簡(jiǎn)單的差錯(cuò)控制編碼

3.2.1奇偶監(jiān)督碼(編碼規(guī)則2、監(jiān)督方程偶檢驗(yàn)的監(jiān)督關(guān)系（偶監(jiān)督方程）在奇校驗(yàn)的監(jiān)督關(guān)系（奇監(jiān)督方程）1、概念偶監(jiān)督碼---信息碼與監(jiān)督碼合在一起“1”的個(gè)數(shù)是偶數(shù)奇監(jiān)督碼---信息碼與監(jiān)督碼合在一起“1”的個(gè)數(shù)是奇數(shù)2、監(jiān)督方程偶檢驗(yàn)的監(jiān)督關(guān)系（偶監(jiān)督方程）只能發(fā)現(xiàn)單個(gè)或奇數(shù)個(gè)錯(cuò)誤，不能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤只能發(fā)現(xiàn)單個(gè)或奇數(shù)個(gè)錯(cuò)誤，3.2.1水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼的構(gòu)成思路是：將信息碼序列按行排成方陣，每行后面加一個(gè)奇或偶監(jiān)督編碼，即每行為一個(gè)奇偶監(jiān)督碼組(見表3-2，以偶監(jiān)督為例)，但發(fā)送時(shí)則按列的順序傳輸：111011100110000…10101，接收端仍將碼元排成與發(fā)送端一樣的方陣形式，然后按行進(jìn)行奇偶校驗(yàn)。表3-2水平偶監(jiān)督碼信息碼元監(jiān)督碼元

11100110001101001101100001110100010000101100111011

10101*******3.2.1水平奇偶監(jiān)督碼信檢錯(cuò)能力（1）可發(fā)現(xiàn)某一行上所有奇數(shù)個(gè)錯(cuò)誤（2）能檢測(cè)出所有長(zhǎng)度不大于方陣中行數(shù)的突發(fā)錯(cuò)誤討論：

水平奇偶監(jiān)督碼是檢錯(cuò)碼，屬于線性分組碼。

檢錯(cuò)能力（1）可發(fā)現(xiàn)某一行上所有奇數(shù)個(gè)錯(cuò)誤討論：

水平奇偶監(jiān)3.2.2二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼是將水平奇偶監(jiān)督碼推廣而得，又稱水平垂直奇偶監(jiān)督碼、行列監(jiān)督碼和方陣碼。它的方法是在水平監(jiān)督基礎(chǔ)上對(duì)表3-2方陣中每一列再進(jìn)行奇偶校驗(yàn)，就可得表3-3（以偶監(jiān)督為例）所示的方陣。發(fā)送是按列或按行的順序傳輸。接收端重新將碼元排成發(fā)送時(shí)方陣形式，然后每行、每列都進(jìn)行奇偶校驗(yàn)。表3-3二維偶監(jiān)督碼信息碼元監(jiān)督碼元

11100110001101001101100001110100010000101100111011

監(jiān)督碼元

1010101101100011*******3.2.2二維奇偶監(jiān)督碼二維奇偶監(jiān)檢錯(cuò)能力（1）可發(fā)現(xiàn)某行或某列上奇數(shù)個(gè)錯(cuò)誤。（2）能檢測(cè)出所有長(zhǎng)度不大于方陣中行數(shù)（或列數(shù)）的突發(fā)錯(cuò)誤（3）能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤。但若偶數(shù)個(gè)錯(cuò)誤恰好分布在矩陣的四個(gè)頂點(diǎn)上時(shí)，這樣的偶數(shù)個(gè)錯(cuò)誤是檢測(cè)不出來的。（4）可以糾正某些錯(cuò)誤，當(dāng)某行某列均不滿足監(jiān)督關(guān)系，可判定該行該列交叉位置的碼元有錯(cuò)，從而糾正這一位上的錯(cuò)誤。討論：二維奇偶監(jiān)督碼是檢錯(cuò)碼或糾錯(cuò)碼，屬于線性分組碼。檢錯(cuò)能力（1）可發(fā)現(xiàn)某行或某列上奇數(shù)個(gè)錯(cuò)誤。討論：二維奇偶監(jiān)3.3漢明碼及線性分組碼

3.3.1漢明碼1、（n,k）漢明碼r與n的關(guān)系為3.3漢明碼及線性分組碼1、（n,k）漢明碼數(shù)據(jù)通信原理3課件例題例題（2）糾檢錯(cuò)

方法------接收端收到（7，4）漢明碼，由下述方程計(jì)算校正子，然后查表3-4可知此碼組是否有錯(cuò)以及差錯(cuò)的確切位置（2）糾檢錯(cuò)

方法------接收端收到（7，4）漢明碼，由

s1s2s3錯(cuò)碼位置

000無錯(cuò)

001

a0

010a1

100a2

011a3

101a4

110a5

111a6表3-4較正子與錯(cuò)碼位置**s1s2s3例：接收端收到某（7，4）漢明碼為1001010，此（7，4）漢明碼是否有錯(cuò)？錯(cuò)碼位置如何？例：接收端收到某（7，4）漢明碼為1001010，此（7，4討論①漢明距離

②編碼效率討論①漢明距離

②編碼效率數(shù)據(jù)通信原理3課件3.3.2線性分組碼2.線性分組碼的主要性質(zhì)

(1)封閉性所謂封閉性，是指一種線性分組碼中的任意兩個(gè)碼組之逐位模2和仍為這種碼中的另一個(gè)許用碼組。線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼，分組碼是監(jiān)督碼僅對(duì)本碼組起監(jiān)督作用，既是線性碼又是分組碼稱為線性分組碼。3.3.2線性分組碼2.線性分組碼的主要性質(zhì)(2)碼的最小距離等于非零碼的最小重量（除了全0碼組之外）因?yàn)榫€性分組碼具有封閉性，因而兩個(gè)碼組之間的距離必是另一碼組的重量。(2)碼的最小距離等于非零碼的最小重量（除了循環(huán)碼是線性分組碼中一類重要的碼。

3.4.1循環(huán)碼的循環(huán)特性循環(huán)碼的循環(huán)性是指循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后(將最右端的碼元移至左端，或反之)所得到的碼組仍為它的一個(gè)許用碼組。表3-6給出一種(7，3)循環(huán)碼的全部碼組，由此表可直觀看出這種碼的循環(huán)性。例如，表中的第2碼組向右循環(huán)移一位即得到第5碼組，第2碼組向左循環(huán)移一位即得到第3碼組。3.4循環(huán)碼循環(huán)碼是線性分組碼中一類重要的碼。

3.4.1循環(huán)碼的循表3-6（7，3）循環(huán)碼的碼組

碼組編號(hào)信息位監(jiān)督位

碼組編號(hào)信息位監(jiān)督位

1234

000001010011

0000011111101001

5678

100101110111

1011110001010010表3-6（7，3）循環(huán)碼的碼組信息位數(shù)據(jù)通信原理3課件1.碼的多項(xiàng)式若碼組

，則相應(yīng)的多項(xiàng)式表示為

3.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣3.4.2循環(huán)碼的生成多項(xiàng)式和生成矩陣?yán)?：A=1011011例2：已知，寫出對(duì)應(yīng)的碼組(n=7)。解：A=1101001例1：A=1011011例2：已知循環(huán)碼的2k個(gè)碼組中，有一個(gè)碼組前k-1位碼元均為0，第k位碼元為1，第n位（最后一位）碼元為1，此碼組對(duì)應(yīng)的多項(xiàng)式。例：求表3-6（7，3）循環(huán)碼的生成多項(xiàng)式。表3-6（7，3）循環(huán)碼對(duì)應(yīng)生成多項(xiàng)式的碼組為第3個(gè)碼組0010111，生成多項(xiàng)式為2、循環(huán)碼的生成多項(xiàng)式循環(huán)碼的2k個(gè)碼組中，有一個(gè)碼組前k-1位碼元例3.生成矩陣G由循環(huán)碼的生成多項(xiàng)式g(x)可得到生成矩陣G(x)，為轉(zhuǎn)換后，典型的生成矩陣為3.生成矩陣G轉(zhuǎn)換后，典型的生成矩陣為生成矩陣可以通過線性變換將非典型的生成矩陣轉(zhuǎn)換為典型的生成矩陣，具體方法是：任意幾行模二加取代某一行。生成矩陣可以通過線性變換將非典型的生成矩陣轉(zhuǎn)換為典型的生成矩例例將三位信息碼（000、001、010、011…111）與典型的生成矩陣G相乘便可得到全部碼組，即表3-6所示。將三位信息碼（00數(shù)據(jù)通信原理3課件

信息字段為K位，校驗(yàn)字段為R位，碼字長(zhǎng)度為N(N=K+R)位

V(x)=xRm(x)+r(x)m(x)為K次信息多項(xiàng)式，

r(x)為R次校驗(yàn)多項(xiàng)式例如：信息字段代碼為:1011001對(duì)應(yīng)m(x)=x6+x4+x3+1g(x)=x4+x3+1為生成多項(xiàng)式g(x)的代碼為:11001校驗(yàn)碼生成的另一種方法信息字段為K位，校驗(yàn)字段為R位，碼字長(zhǎng)度為N(N=K+R

信息字段移位：

x4m(x)=x10+x8+x7+x4—10110010000校驗(yàn)字段形成：（二進(jìn)制除）取余數(shù)

1100110110010000得：1010傳輸字段：10110011010校驗(yàn)：接收字段/相同的生成碼（二進(jìn)制除），除盡（正確），否則（錯(cuò)）信息字段移位：BinaryDivisionBinaryDivision常用的CRC生成多項(xiàng)式g(x)為:CRC16=x16+x15+x2+1R=16，IBM專用

CRC16=x16+x12+x5+1R=16，CCITT專用

CRC32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1R=32,LAN中常用數(shù)據(jù)通信原理3課件3.5卷積碼1.卷積碼的概念在分組碼中，任何一段規(guī)定時(shí)間內(nèi)編碼器產(chǎn)生的n個(gè)碼元的一個(gè)碼組，其監(jiān)督位完全決定于這段時(shí)間中輸入的k個(gè)信息位，這個(gè)碼組中的n-k個(gè)監(jiān)督位僅對(duì)本碼組起監(jiān)督作用。卷積碼則不然，編碼器在任何一段規(guī)定時(shí)間內(nèi)產(chǎn)生的n個(gè)碼元，其監(jiān)督位不僅取決于這段時(shí)間中的k個(gè)信息位，而且還取決于前N-1段規(guī)定時(shí)間內(nèi)的信息位。換句話說，監(jiān)督位不僅對(duì)本碼組起監(jiān)督作用，還對(duì)前N-1個(gè)碼組也起監(jiān)督作用。這段N時(shí)間內(nèi)的碼元數(shù)目nN稱為這種卷積碼的約束長(zhǎng)度。通常把卷積碼記作(n,k,N)，其編碼效率3.5卷積碼1.卷積碼的概念卷積碼的基本概念卷積碼的基本概念數(shù)據(jù)通信原理3課件2卷積碼的編碼簡(jiǎn)單例子：由2個(gè)移位寄存器和1個(gè)模2加電路構(gòu)成（2，1，2）卷積碼編碼器D1D2+m1m2m3m4m5m6tm1c1m2c2m3c3m4c4m5c5m6c6tmcmi.m1.0.m2.m1.m3.m2.mi-1ci+1

=mi+m(i+1)2卷積碼的編碼簡(jiǎn)單例子：由2個(gè)移位寄存器和1個(gè)模2加電路構(gòu)2卷積碼的解碼D1D2+++D3與門.m1’.c1’0S0.mi+1’0.m2’.c2’.m1’.S1S0.m3’.m2’.c3’.S2S1.mi’.ci+1’SiSi-1S0=0+m1’+c1’S1=m1’+m2’+c2’S2=m2’+m3’+c3’S3=m3’+m4’+c4’校正子Si=mi’+m(i+1)’+ci+1’此為門限解碼，屬于代數(shù)解碼，適于約束長(zhǎng)度較短的卷積碼；另一類為概率解碼2卷積碼的解碼D1D2+++D3與.m1’.c1’0S（2，1，3）卷積碼編碼器m1m2m3++.c1c2C1=m1+m2+m3C2=m1+m3輸入比特狀態(tài)比特輸入序列輸出序列（2，1，3）卷積碼編碼器m1m2m3++.c1.m2m3=00(左)輸入m1=000移位后10001001110010(左)輸入m1=101110010011100100111001001110010011100100111卷積碼的樹狀圖.m2m3=00(左)輸入00移位后100010011100（2，1，3）卷積碼的樹狀圖.a(m3m2)(左)輸入m1=0a.c1c2=00babcdab(左)輸入m1=1cdabcdabcdabcdabcdabcd0000001111111111101010010111000110當(dāng)輸入序列為11010…時(shí)，輸出碼元序列？1101010010…（2，1，3）卷積碼的樹狀圖.a(m3m2)(左)輸入a.c輸入為0110…時(shí)，輸出碼元序列？000111101011輸入為000111101（2，1，3）卷積碼的網(wǎng)格圖（籬笆圖）abcd（2，1，3）卷積碼的網(wǎng)格圖（籬笆圖）abcd（2，1，3）卷積碼的狀態(tài)圖0，實(shí)線；1，虛線00=a01=b10=c11=d00=a01=b10=c11=d0011111001100100（2，1，3）卷積碼的狀態(tài)圖0，實(shí)線；1，虛線00=a01卷積碼的譯碼方法代數(shù)譯碼利用編碼本身得代數(shù)結(jié)構(gòu)進(jìn)行解碼，并不考慮信道的統(tǒng)計(jì)特性。其主要特點(diǎn)是算法簡(jiǎn)單，易于實(shí)現(xiàn)，但是它的誤碼性能要比概率譯碼差。其譯碼方法