現(xiàn)代通信原理技術(shù)與仿真差錯控制編碼PPT學(xué)習(xí)教案

1、會計學(xué)19.19.1差錯控制編碼原理差錯控制編碼原理9.1.19.1.1引起誤碼的原因與降低引起誤碼的原因與降低誤碼的常用方法誤碼的常用方法數(shù)字信號在實際通信過程中數(shù)字信號在實際通信過程中不可避免地會發(fā)生錯誤。這是因不可避免地會發(fā)生錯誤。這是因為，一方面通信系統(tǒng)的特性并非為，一方面通信系統(tǒng)的特性并非加性干擾。加性干擾。第1頁/共264頁對于乘性干擾，可以通過均對于乘性干擾，可以通過均衡器來消除碼間串?dāng)_的影響。隨衡器來消除碼間串?dāng)_的影響。隨機(jī)加性干擾通常由信道產(chǎn)生。根機(jī)加性干擾通常由信道產(chǎn)生。根據(jù)隨機(jī)加性干擾的不同特點(diǎn)，從據(jù)隨機(jī)加性干擾的不同特點(diǎn)，從差錯控制角度看，相應(yīng)的信道可差錯控制角度看，相

2、應(yīng)的信道可第2頁/共264頁突發(fā)信道：錯碼的出現(xiàn)是前突發(fā)信道：錯碼的出現(xiàn)是前后相關(guān)的。當(dāng)錯碼出現(xiàn)時，會在后相關(guān)的。當(dāng)錯碼出現(xiàn)時，會在短時間內(nèi)有一連串的大量錯碼，短時間內(nèi)有一連串的大量錯碼，而該時間過后又有較長的時間無而該時間過后又有較長的時間無錯碼。造成突發(fā)錯碼的原因是信錯碼。造成突發(fā)錯碼的原因是信道中存在隨機(jī)的強(qiáng)突發(fā)脈沖干擾，道中存在隨機(jī)的強(qiáng)突發(fā)脈沖干擾，為混合信道。為混合信道。第3頁/共264頁在介紹差錯控制方式之前，在介紹差錯控制方式之前，下面先了解一下降低誤碼、提高下面先了解一下降低誤碼、提高數(shù)字通信可靠性的幾種途徑。根數(shù)字通信可靠性的幾種途徑。根據(jù)實際通信系統(tǒng)對其可靠性的要據(jù)實際通信

3、系統(tǒng)對其可靠性的要求，可以用不同的方法提高通信求，可以用不同的方法提高通信的可靠性。的可靠性。(1) 適當(dāng)增加發(fā)送信號功率。適當(dāng)增加發(fā)送信號功率。增大信號的功率，即提高輸入端增大信號的功率，即提高輸入端無限增大。所以，此種方法在實無限增大。所以，此種方法在實際中受到了一定限制。際中受到了一定限制。第4頁/共264頁(2) 選擇抗噪聲性能好的調(diào)選擇抗噪聲性能好的調(diào)制解調(diào)方式。比如，在數(shù)字調(diào)制制解調(diào)方式。比如，在數(shù)字調(diào)制中移相鍵控中移相鍵控PSK比幅度鍵控比幅度鍵控ASK的誤碼率要小得多。所以在實際的誤碼率要小得多。所以在實際中多采用移相鍵控中多采用移相鍵控PSK，而很少，而很少采用幅度鍵控采用幅

4、度鍵控ASK。(3) 采用最佳接收。最佳接采用最佳接收。最佳接收可以使數(shù)字通信的誤碼率達(dá)到收可以使數(shù)字通信的誤碼率達(dá)到制方式。這是本章的主要內(nèi)容。制方式。這是本章的主要內(nèi)容。第5頁/共264頁9.1.29.1.2差錯控制編碼的基本方差錯控制編碼的基本方法與差錯控制方式法與差錯控制方式對于不同類型的信道，要采對于不同類型的信道，要采用不同的差錯控制方式。不同的用不同的差錯控制方式。不同的差錯控制編碼也要與相應(yīng)的差錯差錯控制編碼也要與相應(yīng)的差錯第6頁/共264頁第7頁/共264頁1. 1. 檢錯重發(fā)檢錯重發(fā)(ARQ)(ARQ)方式方式檢錯重發(fā)方式又稱為自動請檢錯重發(fā)方式又稱為自動請求重發(fā)方式。這種

5、差錯控制方式求重發(fā)方式。這種差錯控制方式在發(fā)送端對數(shù)據(jù)序列進(jìn)行分組編在發(fā)送端對數(shù)據(jù)序列進(jìn)行分組編碼，加入一定多余碼元使之具有碼，加入一定多余碼元使之具有一定的檢錯能力，成為能夠發(fā)現(xiàn)一定的檢錯能力，成為能夠發(fā)現(xiàn)錯誤的碼組。接收端收到碼組后，錯誤的碼組。接收端收到碼組后，候重發(fā)、返回重發(fā)和選擇重發(fā)。候重發(fā)、返回重發(fā)和選擇重發(fā)。ARQ方式的組成如圖方式的組成如圖9.2所示。所示。第8頁/共264頁第9頁/共264頁1) 停止等待停止等待ARQ停止等待停止等待ARQ是最簡單的是最簡單的ARQ系統(tǒng)，也稱為空閑系統(tǒng)，也稱為空閑RQ(idleRQ)。這種系統(tǒng)每發(fā)送一個分。這種系統(tǒng)每發(fā)送一個分第10頁/共26

6、4頁第11頁/共264頁2) 連續(xù)連續(xù)ARQ連續(xù)連續(xù)ARQ工作在全雙工方式，工作在全雙工方式，需要有一定的緩沖器容量。這種需要有一定的緩沖器容量。這種系統(tǒng)兩端同時發(fā)送信息，發(fā)送端系統(tǒng)兩端同時發(fā)送信息，發(fā)送端連續(xù)發(fā)送數(shù)據(jù)，并接收應(yīng)答信號，連續(xù)發(fā)送數(shù)據(jù)，并接收應(yīng)答信號，接收端連續(xù)接收數(shù)據(jù)并發(fā)送應(yīng)答接收端連續(xù)接收數(shù)據(jù)并發(fā)送應(yīng)答信號。連續(xù)信號。連續(xù)ARQ的工作原理如圖的工作原理如圖及處理及處理所帶來的延時，圖所帶來的延時，圖9.4中中N=5。第12頁/共264頁第13頁/共264頁3) 選擇重發(fā)選擇重發(fā)ARQ選擇重發(fā)選擇重發(fā)ARQ是由連續(xù)是由連續(xù)ARQ發(fā)展而來的，工作在全雙工方式，發(fā)展而來的，工作在全

7、雙工方式，第14頁/共264頁第15頁/共264頁2. 2. 前向糾錯前向糾錯(FEC)(FEC)方式方式在前向糾錯在前向糾錯(FEC)方式中，方式中，發(fā)送端發(fā)出的碼字不僅能夠發(fā)現(xiàn)發(fā)送端發(fā)出的碼字不僅能夠發(fā)現(xiàn)錯誤，而且能夠糾正錯誤。在接錯誤，而且能夠糾正錯誤。在接收端譯碼后，若沒有錯誤，則直收端譯碼后，若沒有錯誤，則直接輸出；若有錯誤，則在接收端接輸出；若有錯誤，則在接收端自動糾正后再輸出。這種方式不自動糾正后再輸出。這種方式不需要反向信道，特別適合于只能需要反向信道，特別適合于只能等通信中。等通信中。第16頁/共264頁3. 3. 混合糾錯檢錯混合糾錯檢錯(HEC)(HEC)方方式式混合糾錯

8、檢錯混合糾錯檢錯(HEC)方式是方式是將將ARQ方式和方式和FEC方式結(jié)合使用方式結(jié)合使用的一種方式。在混合糾錯檢錯系的一種方式。在混合糾錯檢錯系統(tǒng)中，發(fā)送端發(fā)出同時具有檢錯統(tǒng)中，發(fā)送端發(fā)出同時具有檢錯和糾錯能力的碼，接收端收到碼和糾錯能力的碼，接收端收到碼后，檢查錯誤情況，如果錯誤少后，檢查錯誤情況，如果錯誤少于糾錯能力，則自行糾正，即于糾錯能力，則自行糾正，即FEC方式；如果干擾嚴(yán)重，錯誤方式；如果干擾嚴(yán)重，錯誤動糾正錯碼；在錯碼較多時，采動糾正錯碼；在錯碼較多時，采用用ARQ方式自動請求重發(fā)。方式自動請求重發(fā)。第17頁/共264頁4. 4. 反饋校驗反饋校驗(IRQ)(IRQ)方式方式反

9、饋校驗反饋校驗(IRQ)方式也稱為方式也稱為信息反饋方式或回程校驗方式。信息反饋方式或回程校驗方式。在該方式中，發(fā)送端一邊發(fā)送碼在該方式中，發(fā)送端一邊發(fā)送碼字，一邊將發(fā)送的碼字在發(fā)送端字，一邊將發(fā)送的碼字在發(fā)送端緩沖存儲。當(dāng)接收端收到碼字后，緩沖存儲。當(dāng)接收端收到碼字后，效率很低。效率很低。第18頁/共264頁9.1.39.1.3糾錯編碼的基本原理糾錯編碼的基本原理1. 有擾信道的編碼定理有擾信道的編碼定理香農(nóng)有擾信道的編碼定理指香農(nóng)有擾信道的編碼定理指出：在有擾信道中只要信息的傳出：在有擾信道中只要信息的傳輸速率輸速率R小于信道容量小于信道容量C，總可，總可以找到一種編碼方法，使信息以以找到

10、一種編碼方法，使信息以任意小的差錯概率通過信道傳送任意小的差錯概率通過信道傳送到接收端，即誤碼率到接收端，即誤碼率Pe可以任意可以任意碼長碼長)；E(R)為誤碼指數(shù)。為誤碼指數(shù)。E(R)與與R、C有關(guān)，其關(guān)系可用曲線有關(guān)，其關(guān)系可用曲線表示，如圖表示，如圖9.6所示。所示。第19頁/共264頁第20頁/共264頁由式由式(9.1)及及E(R)與與R、C的關(guān)的關(guān)系曲線可以看出，要提高抗干擾系曲線可以看出，要提高抗干擾能力，減小誤碼率能力，減小誤碼率Pe，有以下兩，有以下兩種途徑：種途徑： (1) 在編碼長度在編碼長度n及信息的傳及信息的傳輸速率輸速率R一定時，為減小一定時，為減小Pe，可，可以增

11、加信道容量以增加信道容量C。由圖。由圖9.6可見，可見，功率功率P和系統(tǒng)帶寬和系統(tǒng)帶寬B來實現(xiàn)，即通來實現(xiàn)，即通過增加信號功率過增加信號功率P和系統(tǒng)帶寬和系統(tǒng)帶寬B可可以減小誤碼率。以減小誤碼率。第21頁/共264頁(2) 在信道容量在信道容量C及信息的傳及信息的傳輸速率輸速率R一定的情況下，由式一定的情況下，由式(9.1)可知，增加碼長可知，增加碼長n也可以使誤碼也可以使誤碼率率Pe指數(shù)減小，即通過增加信道指數(shù)減小，即通過增加信道第22頁/共264頁2. 2. 糾錯編碼原理糾錯編碼原理第23頁/共264頁最大似然譯碼準(zhǔn)則：在收到最大似然譯碼準(zhǔn)則：在收到碼碼r的條件下，計算的條件下，計算2k個

12、個(許用碼許用碼的個數(shù)的個數(shù))條件概率，其條件概率，其中中CL為許用碼字，若條件概率為許用碼字，若條件概率為最大，則認(rèn)為收到的碼字為最大，則認(rèn)為收到的碼字r就就是發(fā)送來的是發(fā)送來的C碼字。碼字。 式中式中: ri為接收碼字的第為接收碼字的第i位元素；位元素；CLi為許用碼字為許用碼字CL的第的第i位元素。位元素。LrPCLrPCLrPC第24頁/共264頁顯然，當(dāng)接收碼元出錯，即顯然，當(dāng)接收碼元出錯，即riCLi時，概率時，概率; 當(dāng)當(dāng)碼元接收正確，即碼元接收正確，即ri=CLi時，概時，概率。令率。令d為接收為接收(9.3)eLiiPCrP1ieLirPPC ee(1)n ddLrPPPC第

13、25頁/共264頁可見可見，由于，由于，隨隨d單調(diào)下降，因此，單調(diào)下降，因此，d越小，越小， 越大。越大。 越大表明接收到越大表明接收到12eP LrPCLrPCLrPC第26頁/共264頁9.1.49.1.4碼間距離碼間距離d d與檢錯糾錯能與檢錯糾錯能力力1 1 碼間距離碼間距離d d碼間距離碼間距離(code distances)是是一個碼組中任意兩個碼字之間對一個碼組中任意兩個碼字之間對應(yīng)位上碼元取值不同的位數(shù)，用應(yīng)位上碼元取值不同的位數(shù)，用位模位模2相加后相加后“1”的個數(shù)。的個數(shù)。10(,)()nijipjppd C Ccc第27頁/共264頁 一般兩個碼字的碼距計算方一般兩個碼字

14、的碼距計算方法為：設(shè)兩個碼字法為：設(shè)兩個碼字Ci、Cj分別為分別為101110 和和 101011，則碼距可按下，則碼距可按下式計算式計算: :101110:101011000101ijccd 第28頁/共264頁在一個碼組中，各碼字之間在一個碼組中，各碼字之間的距離不一定都相等，有的大，的距離不一定都相等，有的大，有的小。通常稱碼組中最小的碼有的小。通常稱碼組中最小的碼距為最小碼間距離，用距為最小碼間距離，用第29頁/共264頁對于三位編碼的碼間距離，對于三位編碼的碼間距離，可用三維幾何空間來說明。三位可用三維幾何空間來說明。三位編碼的碼字共有編碼的碼字共有23=8個，用三維個，用三維幾何空

15、間立方體的幾何空間立方體的8個頂點(diǎn)來表個頂點(diǎn)來表示，如圖示，如圖9.7所示。碼字之間的距所示。碼字之間的距離可用對應(yīng)兩頂點(diǎn)間沿立方體各離可用對應(yīng)兩頂點(diǎn)間沿立方體各說明。說明。第30頁/共264頁第31頁/共264頁2. 2. 最小距離最小距離d d0 0與檢錯糾錯與檢錯糾錯能力的關(guān)系能力的關(guān)系(1) 當(dāng)碼組僅用于檢測錯誤當(dāng)碼組僅用于檢測錯誤時，若要求檢測時，若要求檢測e個錯誤，則最個錯誤，則最小碼距為小碼距為d0=e+1(9.5)若要檢測若要檢測e個錯碼，則必須滿足個錯碼，則必須滿足d0e+1的要求。的要求。第32頁/共264頁第33頁/共264頁(2) 當(dāng)碼組僅用于糾正錯誤當(dāng)碼組僅用于糾正錯

16、誤時，為糾正時，為糾正t個錯誤，要求最小碼個錯誤，要求最小碼距為距為d0e+t(9.6)這可用圖這可用圖9.8(b)來說明。碼字來說明。碼字A發(fā)發(fā)生兩位錯，落在以生兩位錯，落在以A為圓心、以為圓心、以2為為5。所以糾正。所以糾正t個錯誤，必須滿個錯誤，必須滿足足d02t+1的要求。的要求。第34頁/共264頁(3) 當(dāng)碼組既要檢錯，又要當(dāng)碼組既要檢錯，又要糾錯時，為糾正糾錯時，為糾正t個錯誤，同時檢個錯誤，同時檢測測e個錯誤，要求的最小碼距為個錯誤，要求的最小碼距為d0e+t+1et(9.7)這可用圖這可用圖9.4(c)來說明。當(dāng)碼字來說明。當(dāng)碼字A也即最小碼距也即最小碼距d0e+t+1。第3

17、5頁/共264頁3 3 差錯控制編碼的效果差錯控制編碼的效果對于隨機(jī)錯誤的情況，假設(shè)對于隨機(jī)錯誤的情況，假設(shè)誤碼率為誤碼率為P， 且且P1。在碼長。在碼長為為n的碼字中剛好發(fā)生的碼字中剛好發(fā)生r個錯誤的個錯誤的概率為概率為2.110-5, P7(3)35P3=3.510-8。 !(1)(1)!()!rrn rrn rnnnP rC PPPPr nr第36頁/共264頁4 4 糾錯編碼的分類糾錯編碼的分類第37頁/共264頁第38頁/共264頁(1) 按照其實現(xiàn)的功能，糾按照其實現(xiàn)的功能，糾錯編碼可以分為檢錯碼和糾錯碼。錯編碼可以分為檢錯碼和糾錯碼。一般來說，能夠發(fā)現(xiàn)錯誤的碼稱一般來說，能夠發(fā)現(xiàn)

18、錯誤的碼稱為檢錯碼。在譯碼時不僅能夠發(fā)為檢錯碼。在譯碼時不僅能夠發(fā)現(xiàn)錯誤，而且能夠自動糾正錯誤，現(xiàn)錯誤，而且能夠自動糾正錯誤，通過譯碼產(chǎn)生正確的碼字，這樣通過譯碼產(chǎn)生正確的碼字，這樣稱為非線性碼。稱為非線性碼。第39頁/共264頁(3) 按照對信息碼元處理方按照對信息碼元處理方法的不同，糾錯編碼分為分組碼法的不同，糾錯編碼分為分組碼和卷積碼。分組碼是將和卷積碼。分組碼是將k個信息個信息碼元劃分為一組，然后由這碼元劃分為一組，然后由這k個碼元按照一定的規(guī)則產(chǎn)生個碼元按照一定的規(guī)則產(chǎn)生r個個監(jiān)督碼元，從而組成長度監(jiān)督碼元，從而組成長度n=k+r隨機(jī)錯誤的碼和糾突發(fā)錯誤的碼。隨機(jī)錯誤的碼和糾突發(fā)錯誤

19、的碼。第40頁/共264頁5. 5. 編碼效率編碼效率在分組碼編碼中，加入的監(jiān)在分組碼編碼中，加入的監(jiān)督位越多，檢錯糾錯能力越強(qiáng)。督位越多，檢錯糾錯能力越強(qiáng)。但這會使總的碼長增加，但這會使總的碼長增加，(即要即要傳輸?shù)奈粩?shù)增加傳輸?shù)奈粩?shù)增加)，從而使編碼，從而使編碼的效率降低。設(shè)碼字的信息碼元的效率降低。設(shè)碼字的信息碼元個數(shù)為個數(shù)為k，監(jiān)督碼元個數(shù)為，監(jiān)督碼元個數(shù)為r，總，總的碼元的個數(shù)的碼元的個數(shù)(即總的碼長即總的碼長)為為可見可見, 監(jiān)督位越多，編碼效率越監(jiān)督位越多，編碼效率越低。低。1knrrnnn 第41頁/共264頁9.29.2常用簡單差錯控制編碼常用簡單差錯控制編碼9.2.19.2

20、.1奇偶監(jiān)督碼奇偶監(jiān)督碼奇偶監(jiān)督碼奇偶監(jiān)督碼(也稱奇偶校驗也稱奇偶校驗第42頁/共264頁偶監(jiān)督碼是給信息位后增加偶監(jiān)督碼是給信息位后增加一位監(jiān)督位，使碼字中一位監(jiān)督位，使碼字中“1”的數(shù)的數(shù)目為偶數(shù)，滿足如下關(guān)系：目為偶數(shù)，滿足如下關(guān)系：(9.11)式中：式中：cn-1cn-2c1為信息位為信息位; c0為為碼字有錯，但檢測不到，所以這碼字有錯，但檢測不到，所以這種碼不能檢測偶數(shù)個錯。種碼不能檢測偶數(shù)個錯。12100nncccc第43頁/共264頁在編碼的過程中，監(jiān)督位是在編碼的過程中，監(jiān)督位是由信息位產(chǎn)生的，該編碼監(jiān)督位由信息位產(chǎn)生的，該編碼監(jiān)督位的產(chǎn)生方程為的產(chǎn)生方程為(9.12)奇監(jiān)督

21、碼是給信息位后增加奇監(jiān)督碼是給信息位后增加 (9.14)0121nncccc12101nncccc01211nncccc第44頁/共264頁奇偶監(jiān)督碼的編碼效率奇偶監(jiān)督碼的編碼效率較較高，尤其是當(dāng)碼長高，尤其是當(dāng)碼長n較大時這一較大時這一特點(diǎn)更為明顯。在特點(diǎn)更為明顯。在n值很大時編值很大時編碼效率趨近于碼效率趨近于1，即，即1111rnn 第45頁/共264頁9.2.29.2.2二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼也稱為方陣二維奇偶監(jiān)督碼也稱為方陣碼、行列監(jiān)督碼或水平碼、行列監(jiān)督碼或水平-垂直奇偶垂直奇偶監(jiān)督碼。其編碼方法是把監(jiān)督碼。其編碼方法是把m個信個信息碼字排列成一個方陣，每個碼息

22、碼字排列成一個方陣，每個碼字構(gòu)成方陣的一行，在每一行的字構(gòu)成方陣的一行，在每一行的9.10所示。所示。第46頁/共264頁第47頁/共264頁9.2.39.2.3恒比碼恒比碼恒比碼的特點(diǎn)是每個許用碼恒比碼的特點(diǎn)是每個許用碼含有相同數(shù)目的含有相同數(shù)目的“1”。在碼字中，。在碼字中，“1”與與“0”的個數(shù)之比是恒定的，的個數(shù)之比是恒定的，所以稱之為恒比碼。一個碼字中所以稱之為恒比碼。一個碼字中第48頁/共264頁我國電傳機(jī)傳輸漢字采用的我國電傳機(jī)傳輸漢字采用的是是“5中取中取3” 恒比碼，其碼長為恒比碼，其碼長為5，碼字中碼字中“1”的個數(shù)為的個數(shù)為3，稱為保，稱為保護(hù)電碼。碼長為護(hù)電碼。碼長為5

23、的二進(jìn)制數(shù)共的二進(jìn)制數(shù)共有有32種組合，選擇其中含有種組合，選擇其中含有3個個“1”的組合作為許用碼，所以的組合作為許用碼，所以列出了這兩種編碼。列出了這兩種編碼。第49頁/共264頁第50頁/共264頁9.39.3線線 性性 分分 組組 碼碼9.3.19.3.1線性分組碼的概念線性分組碼的概念數(shù)字通信系統(tǒng)的信源輸出是數(shù)字通信系統(tǒng)的信源輸出是由由“0”和和“1”組成的二進(jìn)制序列，組成的二進(jìn)制序列，在分組碼中，該二元信息序列被在分組碼中，該二元信息序列被分成碼元個數(shù)固定的一分成碼元個數(shù)固定的一組組信息，每組信息的碼元由組組信息，每組信息的碼元由k第51頁/共264頁所謂線性分組碼，就是一種所謂線

24、性分組碼，就是一種長度為長度為n，其中，其中2k個許用碼組個許用碼組(代代表信息的碼組表信息的碼組)中的任意兩個碼中的任意兩個碼組的模組的模2和仍為一個許用碼組的和仍為一個許用碼組的分組碼。這種長度為分組碼。這種長度為n，有，有2k個個第52頁/共264頁線性分組碼的構(gòu)成方法是：線性分組碼的構(gòu)成方法是：將信息序列分為每將信息序列分為每k位一組的信位一組的信息序列段，每一信息序列段按照息序列段，每一信息序列段按照一定規(guī)律添加一定規(guī)律添加r個監(jiān)督碼元，構(gòu)個監(jiān)督碼元，構(gòu)成總碼長為成總碼長為n=k+r的分組碼，記的分組碼，記為為(n, k)。在分組碼中，監(jiān)督碼元。在分組碼中，監(jiān)督碼元僅與本分組中的信息

25、碼元有關(guān)，僅與本分組中的信息碼元有關(guān)，各許用碼的集合構(gòu)成代數(shù)學(xué)中的各許用碼的集合構(gòu)成代數(shù)學(xué)中的群，又稱為群碼。群，又稱為群碼。第53頁/共264頁表表9.2示出了線性分組碼的一示出了線性分組碼的一種結(jié)構(gòu)。碼字的前一部分是連續(xù)種結(jié)構(gòu)。碼字的前一部分是連續(xù)第54頁/共264頁第55頁/共264頁9.3.29.3.2線性分組碼的監(jiān)督矩陣線性分組碼的監(jiān)督矩陣假定監(jiān)督碼元與信息碼元的假定監(jiān)督碼元與信息碼元的關(guān)系由下列線性方程組決定關(guān)系由下列線性方程組決定:265416530643cccccccccccc =排=排=排 第56頁/共264頁對式對式(9.16)移項后可得三個監(jiān)移項后可得三個監(jiān)督關(guān)系式督關(guān)系

26、式(該方程組在二元有限該方程組在二元有限域上求解，系數(shù)取值為域上求解，系數(shù)取值為“0”或或“1”):654265316430000cccccccccccc 排排排 第57頁/共264頁第58頁/共264頁將式將式(9.17)中的零系數(shù)項補(bǔ)上，中的零系數(shù)項補(bǔ)上，寫出系數(shù)可得：寫出系數(shù)可得：第59頁/共264頁把式把式(9.18)寫成矩陣形式如下寫成矩陣形式如下:第60頁/共264頁將式將式(9.16)寫成矩陣形式寫成矩陣形式:第61頁/共264頁令式令式(9.19)的系數(shù)矩陣為的系數(shù)矩陣為第62頁/共264頁進(jìn)一步分析進(jìn)一步分析H，利用矩陣分，利用矩陣分塊的方法，塊的方法，H可寫為可寫為第63頁

27、/共264頁其中其中, P見式見式(9.20)，I3為為3階階單位矩陣，即單位矩陣，即第64頁/共264頁對于對于(n，k)分組碼，分組碼，r=nk，H可寫為可寫為(9.25)第65頁/共264頁9.3.39.3.3線性分組碼的生成矩陣線性分組碼的生成矩陣生成矩陣是在已知信息碼元生成矩陣是在已知信息碼元時確定相應(yīng)的許用碼字時確定相應(yīng)的許用碼字C=c6c5c4c3c2c1c0的矩陣。由式的矩陣。由式第66頁/共264頁將式將式(9.26)寫成矩陣形式寫成矩陣形式:第67頁/共264頁對式對式(9.27)取轉(zhuǎn)置得：取轉(zhuǎn)置得：第68頁/共264頁式中：式中：第69頁/共264頁其中其中:(9.30)

28、第70頁/共264頁由式由式(9.29)得，得，G=IkQ ，其中，其中Ik為為k階單位矩階單位矩陣。這種形式的生成矩陣陣。這種形式的生成矩陣G是典是典型生成矩陣。同樣，典型生成矩型生成矩陣。同樣，典型生成矩陣的各行也是線性無關(guān)的。由典陣的各行也是線性無關(guān)的。由典型生成矩陣得出的碼字型生成矩陣得出的碼字C是信息是信息位在前、監(jiān)督位在后的系統(tǒng)碼。位在前、監(jiān)督位在后的系統(tǒng)碼。中一個，則另一個確定，其監(jiān)督中一個，則另一個確定，其監(jiān)督關(guān)系和它所對應(yīng)的碼也就確定了。關(guān)系和它所對應(yīng)的碼也就確定了。第71頁/共264頁在線性分組碼中，任意兩個在線性分組碼中，任意兩個許用碼字對應(yīng)位模許用碼字對應(yīng)位模2相加還是

29、此相加還是此碼組中的一個碼字，所以線性分碼組中的一個碼字，所以線性分組碼具有封閉性。對組碼具有封閉性。對(n，k)線性線性分組碼來說，其信息位長為分組碼來說，其信息位長為k，共有共有2k個不同組合的信息碼。設(shè)個不同組合的信息碼。設(shè)Cix、Cjx為其中兩個信息碼，由為其中兩個信息碼，由ij成矩陣為成矩陣為G的線性分組碼中的一的線性分組碼中的一個許用碼字。個許用碼字。第72頁/共264頁(n，k)線性分組碼線性分組碼A的生成的生成矩陣矩陣G的每一行都是碼組的每一行都是碼組A的一的一個許用碼字，它一定滿足個許用碼字，它一定滿足H矩陣矩陣所確定的所確定的r個監(jiān)督關(guān)系。如果把個監(jiān)督關(guān)系。如果把G當(dāng)作另一

30、個碼組當(dāng)作另一個碼組B的監(jiān)督矩陣，的監(jiān)督矩陣，把把H當(dāng)作碼組當(dāng)作碼組B的生成矩陣，則的生成矩陣，則碼組碼組B為為(n，nk)線性分組碼，線性分組碼，(9.32)第73頁/共264頁由于線性分組碼具有封閉性，由于線性分組碼具有封閉性，因此由碼距的定義可知，任意兩因此由碼距的定義可知，任意兩個許用碼字之間的距離必然是另個許用碼字之間的距離必然是另一個許用碼字的重量。所以，該一個許用碼字的重量。所以，該碼的最小重量碼的最小重量(除全除全“0”碼字外碼字外)必然是該線性分組碼的最小距離。必然是該線性分組碼的最小距離。(9.33)第74頁/共264頁由由CHT=0可見，當(dāng)可見，當(dāng)C取最小取最小重量的碼字

31、，即重量的碼字，即C中中“1”的個數(shù)的個數(shù)為為Wmin時，得到時，得到H中最小相關(guān)的中最小相關(guān)的列的數(shù)目，即列的數(shù)目，即H中小于或等于中小于或等于Wmin1 列是線性獨(dú)立的、不相列是線性獨(dú)立的、不相第75頁/共264頁9.3.49.3.4線性分組碼的伴隨式和線性分組碼的伴隨式和檢錯糾錯能力檢錯糾錯能力設(shè)發(fā)送端發(fā)出的許用碼為設(shè)發(fā)送端發(fā)出的許用碼為C=cn-1cn-2c1c0，它符合，它符合CHT=0 。假設(shè)經(jīng)過信道傳輸后。假設(shè)經(jīng)過信道傳輸后接收端收到的碼字為接收端收到的碼字為R=rn-1rn-2 r1r0。如果。如果R=C，把，把(9.34)第76頁/共264頁E稱為差錯序列或錯誤圖樣。稱為差錯

32、序列或錯誤圖樣。因為因為E表示表示R中具體哪一位發(fā)生中具體哪一位發(fā)生錯誤，即錯誤，即第77頁/共264頁其中，其中，S=sn-1sn-2s1s0，為為1r階行矢量。由式階行矢量。由式(9.35)可見，可見，S只與錯誤圖樣只與錯誤圖樣E有關(guān)，而與發(fā)送有關(guān)，而與發(fā)送的碼字的碼字C無關(guān)，這意味著無關(guān)，這意味著S與與E有有線性變換關(guān)系，能與線性變換關(guān)系，能與E一一對應(yīng)，一一對應(yīng)，可指示錯碼位置，所以可指示錯碼位置，所以S稱為監(jiān)稱為監(jiān)督矩陣為督矩陣為H的的(n，k)線性分組碼線性分組碼則必定有錯，由則必定有錯，由S可判斷出錯碼可判斷出錯碼的位置。的位置。第78頁/共264頁下面以下面以(7，4)碼為例進(jìn)

33、行說碼為例進(jìn)行說明。設(shè)明。設(shè)C=0001011,若傳輸中若傳輸中c3發(fā)生誤碼發(fā)生誤碼,即發(fā)生一位錯即發(fā)生一位錯,E=0001000,R=0000011,則由式則由式(9.35)可得：可得：第79頁/共264頁可見可見, ST剛好是錯誤圖樣剛好是錯誤圖樣E中中“1”所對應(yīng)的所對應(yīng)的H中的一列，即中的一列，即R的第的第i位有錯，則位有錯，則E的第的第i位為位為“1”，ST與與H中的第中的第i列相同。判斷出錯列相同。判斷出錯誤后，可利用誤后，可利用RE=C糾錯。糾錯。第80頁/共264頁當(dāng)當(dāng)S=0時，符合監(jiān)督關(guān)系式，時，符合監(jiān)督關(guān)系式，判斷接收到的碼無錯；當(dāng)判斷接收到的碼無錯；當(dāng)S=1時，時，不符合

34、監(jiān)督關(guān)系式，就認(rèn)為有錯。不符合監(jiān)督關(guān)系式，就認(rèn)為有錯。S的取值只有兩個，它只能表示的取值只有兩個，它只能表示無錯、有錯兩種狀態(tài)，而無法指無錯、有錯兩種狀態(tài)，而無法指出錯在哪一位，因此，它只能檢出錯在哪一位，因此，它只能檢錯，不能糾錯。如果再增加一位錯，不能糾錯。如果再增加一位r個可能的位置。個可能的位置。第81頁/共264頁由以上分析可知，對由以上分析可知，對(n，k)線性分組碼，有線性分組碼，有r=nk個監(jiān)督關(guān)個監(jiān)督關(guān)系式，有系式，有2r個不同的個不同的S。全。全0矢量矢量表示無錯，所以表示無錯，所以S最多可指出最多可指出2r第82頁/共264頁其中其中, Cin為組合數(shù)為組合數(shù), 即即第8

35、3頁/共264頁線性分組碼的主要性質(zhì)如下：線性分組碼的主要性質(zhì)如下：(1) 封閉性。封閉性是指碼封閉性。封閉性是指碼中任意兩個許用碼組之和中任意兩個許用碼組之和(逐位逐位模模2和和)仍為一個許用碼組。也就仍為一個許用碼組。也就是說，若是說，若C1和和C2為分組碼中的兩為分組碼中的兩第84頁/共264頁在通信傳輸過程中如果錯碼在通信傳輸過程中如果錯碼較多，已超過這種編碼的檢錯能較多，已超過這種編碼的檢錯能力，即力，即R變?yōu)榱硪辉S用碼組，則變?yōu)榱硪辉S用碼組，則式式(9.22)仍成立。由于線性分組仍成立。由于線性分組碼具有封閉性質(zhì)，因此由式碼具有封閉性質(zhì)，因此由式(9.34)中中R=CE可知，只有當(dāng)

36、可知，只有當(dāng)E=C，即錯誤碼組剛好等于任意許用碼即錯誤碼組剛好等于任意許用碼其中，其中，Wi是重量為是重量為i的許用碼組的許用碼組數(shù)目。數(shù)目。第85頁/共264頁9.3.59.3.5漢明碼漢明碼漢明碼是一種可以糾正單個漢明碼是一種可以糾正單個隨機(jī)錯誤的線性分組碼，它是一隨機(jī)錯誤的線性分組碼，它是一種完備碼，編碼效率很高。在式種完備碼，編碼效率很高。在式(9.37)中，令中，令t=1(即糾正一位錯即糾正一位錯)，并取等號得并取等號得:2r1=n(9.40)0t，n越越大，大，越高。越高。1121rrrn 第86頁/共264頁(9.42) (9.41) 第87頁/共264頁漢明碼只能糾正一位錯，其

37、漢明碼只能糾正一位錯，其最小碼距最小碼距d0=3。當(dāng)碼字中出現(xiàn)兩。當(dāng)碼字中出現(xiàn)兩位錯時，它檢測不出來，必然會位錯時，它檢測不出來，必然會造成錯判。如果在漢明碼的基礎(chǔ)造成錯判。如果在漢明碼的基礎(chǔ)上增加一位對所有碼元都進(jìn)行校上增加一位對所有碼元都進(jìn)行校驗的監(jiān)督碼元，則監(jiān)督碼元的位驗的監(jiān)督碼元，則監(jiān)督碼元的位同時也能檢測同時也能檢測2位錯。位錯。第88頁/共264頁增余漢明碼的構(gòu)成是增加一增余漢明碼的構(gòu)成是增加一位監(jiān)督碼元，使原漢明碼的最小位監(jiān)督碼元，使原漢明碼的最小碼重由奇數(shù)變?yōu)榕紨?shù)。其監(jiān)督矩碼重由奇數(shù)變?yōu)榕紨?shù)。其監(jiān)督矩陣可以由原漢明碼的監(jiān)督矩陣陣可以由原漢明碼的監(jiān)督矩陣H得到：得到：在最后一行添

38、加一行全在最后一行添加一行全1構(gòu)成的。構(gòu)成的。第89頁/共264頁如果把上述如果把上述(7，4)漢明碼變漢明碼變?yōu)閷?yīng)的為對應(yīng)的(8，4)增余漢明碼，則增余漢明碼，則其監(jiān)督矩陣為其監(jiān)督矩陣為第90頁/共264頁9.49.4循環(huán)碼循環(huán)碼9.4.19.4.1循環(huán)碼的循環(huán)特性與碼循環(huán)碼的循環(huán)特性與碼多項式多項式循環(huán)碼是線性分組碼的一個循環(huán)碼是線性分組碼的一個重要分支。循環(huán)碼除了具有線性重要分支。循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，碼的一般性質(zhì)外，還具有循環(huán)性，的應(yīng)用。的應(yīng)用。第91頁/共264頁對于一個對于一個(n，k)線性碼線性碼C，若其中的任一碼組向左或向右循若其中的任一碼組向左或向

39、右循環(huán)移動任意位后仍是環(huán)移動任意位后仍是C中的一個中的一個碼組，則稱碼組，則稱C是一個循環(huán)碼。循是一個循環(huán)碼。循環(huán)碼是一種線性分組碼，它除了環(huán)碼是一種線性分組碼，它除了具有線性分組碼的封閉性之外，具有線性分組碼的封閉性之外，還具有循環(huán)性。通常其前還具有循環(huán)性。通常其前k位是位是信息碼元，后信息碼元，后r位為監(jiān)督碼元，位為監(jiān)督碼元，移、右移多少位，得到的結(jié)果均移、右移多少位，得到的結(jié)果均為該循環(huán)碼中的一個碼字。為該循環(huán)碼中的一個碼字。第92頁/共264頁下式所示的碼字均為該循環(huán)下式所示的碼字均為該循環(huán)碼中的一個碼字碼中的一個碼字:第93頁/共264頁第94頁/共264頁為了便于用代數(shù)學(xué)的理論分為

40、了便于用代數(shù)學(xué)的理論分析計算循環(huán)碼，可把循環(huán)碼中的析計算循環(huán)碼，可把循環(huán)碼中的碼字用多項式來表示，稱為碼多碼字用多項式來表示，稱為碼多項式，也就是把碼字中各碼元的項式，也就是把碼字中各碼元的第95頁/共264頁其中其中, xi是碼元位置的標(biāo)記，它表是碼元位置的標(biāo)記，它表示由其系數(shù)所決定的碼元取值所示由其系數(shù)所決定的碼元取值所處的對應(yīng)位置，其系數(shù)只能取處的對應(yīng)位置，其系數(shù)只能取0或或1，運(yùn)算時其系數(shù)的運(yùn)算為模，運(yùn)算時其系數(shù)的運(yùn)算為模2運(yùn)算。例如，碼字運(yùn)算。例如，碼字1001110、0011101可用碼多項式表示為可用碼多項式表示為1001110 0011101=1010011第96頁/共264頁

41、在整數(shù)的按模運(yùn)算中，最熟在整數(shù)的按模運(yùn)算中，最熟悉的是模悉的是模2運(yùn)算，如運(yùn)算，如1+10(模模2)，1+21(模模2)等。對于模等。對于模n運(yùn)算，如果一個整數(shù)運(yùn)算，如果一個整數(shù)m可以表示可以表示為為稱稱m與與p是同余的。是同余的。,mpQpnnn（）第97頁/共264頁在多項式中同樣可以進(jìn)行類在多項式中同樣可以進(jìn)行類似的按模運(yùn)算，如似的按模運(yùn)算，如(9.49)其中其中: F(x)是冪次為是冪次為n的多項式的多項式; ( )( )( )( )( )F xR xQ xN xN x第98頁/共264頁碼多項式系數(shù)仍按模碼多項式系數(shù)仍按模2運(yùn)算，運(yùn)算，即只取值即只取值0和和1。比如。比如, x3被被

42、x3+1除除可得余式為可得余式為1， 于是有：于是有：x31(模模x3+1)(9.52) 第99頁/共264頁定理定理9.4.1若若T(x)是長為是長為n的的循環(huán)碼中某個許用碼組的碼多項循環(huán)碼中某個許用碼組的碼多項式，則式，則xiT(x)在按模在按模xn+1運(yùn)算下運(yùn)算下也是該循環(huán)碼中一個許用碼組的也是該循環(huán)碼中一個許用碼組的碼多項式。碼多項式。例如例如, (7，3)循環(huán)碼中許用碼循環(huán)碼中許用碼0011101左移左移3次后形成的。次后形成的。365377( )1111xT xxxxxx 第100頁/共264頁定理定理9.4.1證明如下：證明如下：設(shè)設(shè)T(x)=cn-1xn-1+cn-2xn-2+

43、c1x1+c0，那么有，那么有第101頁/共264頁其中其中, Ri(x)=cn-1-ixn-1+cn-2-ixn-2+c0 xi+cn-1xi-1+cn-i是是T(x)左左移移i位后形成的碼字。若把位后形成的碼字。若把i取不取不同的值重復(fù)做上述運(yùn)算，則可得同的值重復(fù)做上述運(yùn)算，則可得第102頁/共264頁9.4.2循環(huán)碼的生成多項式與生循環(huán)碼的生成多項式與生成矩陣成矩陣定理定理9.4.2在循環(huán)碼在循環(huán)碼(n, k)中，中，第103頁/共264頁一旦一旦g(x)確定，該確定，該(n, k)循環(huán)循環(huán)碼就被確定了。碼就被確定了。g(x)是循環(huán)碼中是循環(huán)碼中冪次最低的碼多項式。由它左移冪次最低的碼多

44、項式。由它左移就可產(chǎn)生其他碼多項式，比如就可產(chǎn)生其他碼多項式，比如xg(x)、x2g(x)、x3g(x)等。用等。用k第104頁/共264頁例如，有一個例如，有一個(7，3)循環(huán)碼循環(huán)碼(其最高次冪為其最高次冪為(n, k)次次)的碼字為的碼字為0010111，其生成多項式，其生成多項式g(x)=x4+x2+x+1，則利用式，則利用式(9.55)可得其生成矩陣可得其生成矩陣G(x)：第105頁/共264頁將此生成矩陣用系數(shù)表示，將此生成矩陣用系數(shù)表示，寫為生成矩陣寫為生成矩陣G:(9.57)第106頁/共264頁例如，對于例如，對于(7，3)循環(huán)碼，循環(huán)碼，設(shè)信息碼為設(shè)信息碼為c6c5c4，由

45、生成矩，由生成矩陣多項式可以寫出該循環(huán)碼的碼陣多項式可以寫出該循環(huán)碼的碼字字:第107頁/共264頁因此因此，已知信息碼，已知信息碼U=uk-1uk-2u1u0和和g(x)就可求得循環(huán)就可求得循環(huán)碼的所有碼多項式碼的所有碼多項式:T(x)=uk-1uk-2u1u0G(x)=u(x)g(x)第108頁/共264頁定理定理9.4.3循環(huán)碼循環(huán)碼(n, k)的生的生成多項式成多項式g(x)是是xn+1的一個因式。的一個因式。定理分析定理分析：g(x)是最高次冪是最高次冪為為nk次的碼多項式。次的碼多項式。xkg(x)是是最高次冪為最高次冪為n的多項式。利用定的多項式。利用定理理9.4.1對對xkg(

46、x)作模作模xn+1運(yùn)算，運(yùn)算，( )( )111knnxg xR xxx 第109頁/共264頁對上式移項得對上式移項得:xn+1=xkg(x)+I(x)g(x)=xk+I(x)g(x)=h(x)g(x)(9.61)即即g(x)是是xn+1的因式。式中的因式。式中n的因式作為生成多項式的因式作為生成多項式g(x)。1( )( )nxh xg x第110頁/共264頁例如例如, 對于對于(7，3)循環(huán)碼，循環(huán)碼，g(x)的最高次冪為的最高次冪為4, 可以從可以從x7+1中分解得到中分解得到g(x)。x7+1 可分解為可分解為x7+1=(x+1)(x3+x2+1)(x3+x+1)(9.62)第1

47、11頁/共264頁9.4.3循環(huán)碼的編碼與解碼循環(huán)碼的編碼與解碼1 循環(huán)碼的編碼循環(huán)碼的編碼在編碼時，首先要根據(jù)給定在編碼時，首先要根據(jù)給定的的(n, k)值選定生成多項式值選定生成多項式g(x)，即應(yīng)在即應(yīng)在xn+1的因式中選一個的因式中選一個nk次多項式作為次多項式作為g(x)。(9.65)第112頁/共264頁信息碼多項式信息碼多項式m(x)的最高次的最高次冪為冪為k1。將。將m(x)左移左移nk位成位成為為xn-km(x)，其最高次冪為，其最高次冪為n-1。xn-km(x)的前一部分為連續(xù)的前一部分為連續(xù)k位信位信息碼，后一部分為息碼，后一部分為r=nk位位“0”，r正好是監(jiān)督碼的位數(shù)

48、正好是監(jiān)督碼的位數(shù), 所以在它所以在它的后一部分添上監(jiān)督碼，就編出的后一部分添上監(jiān)督碼，就編出了相應(yīng)的系統(tǒng)碼。監(jiān)督碼由監(jiān)督了相應(yīng)的系統(tǒng)碼。監(jiān)督碼由監(jiān)督( )( )( )( )( )n kxm xr xq xg xg x第113頁/共264頁所得的余式所得的余式r(x)的最高次冪的最高次冪為為nk1，即，即r(x)=rn-k-1xn-k-1+rn-k-2xn-k-2+r1x1+r0將將r(x)作為監(jiān)督位的多項式，與作為監(jiān)督位的多項式，與xn-km(x)模模2相加，形成新的多項相加，形成新的多項式式:T(x)=xn-km(x)+r(x)x碼多項式，而且是系統(tǒng)碼。碼多項式，而且是系統(tǒng)碼。第114頁/

49、共264頁對對(7，3)循環(huán)碼選擇生成多循環(huán)碼選擇生成多項式項式g(x)=x4+x3+x2+1，設(shè)已知信，設(shè)已知信息碼為息碼為111, 則信息碼多項式為則信息碼多項式為第115頁/共264頁(2) 利用式利用式(9.66)所示的所示的做除法，求出余式做除法，求出余式r(x)。本例中。本例中為為( )( )( )( )( )n kxm xr xq xg xg x1123422234456xxxxxxxxxxx111010100100111011110000第116頁/共264頁(3) 構(gòu)成系統(tǒng)碼構(gòu)成系統(tǒng)碼T(x)=xn-km(x)+r(x)。本例中為。本例中為1110000+0100=11101

50、00。第117頁/共264頁第118頁/共264頁在編碼器工作之前先清零，在編碼器工作之前先清零，使寄存器的初態(tài)為零，使轉(zhuǎn)換開使寄存器的初態(tài)為零，使轉(zhuǎn)換開關(guān)關(guān)S1、S2均向下，均向下，S1使反饋線接使反饋線接通，通，S2使輸入直接加到輸出。開使輸入直接加到輸出。開始輸入三位信息碼。輸入的信息始輸入三位信息碼。輸入的信息碼碼m(x)一路直接送到輸出端，作一路直接送到輸出端，作為系統(tǒng)碼的前面一部分為系統(tǒng)碼的前面一部分(即信息即信息碼部分碼部分)，另一路送入除法器作，另一路送入除法器作9.5所示為上述編碼過程中各點(diǎn)的所示為上述編碼過程中各點(diǎn)的狀態(tài)變化過程。狀態(tài)變化過程。第119頁/共264頁第120

51、頁/共264頁通常對于一個通常對于一個(n, k)循環(huán)碼，循環(huán)碼，若設(shè)生成多項式為若設(shè)生成多項式為第121頁/共264頁第122頁/共264頁2. 循環(huán)碼的解碼循環(huán)碼的解碼循環(huán)碼的解碼分為檢錯和糾循環(huán)碼的解碼分為檢錯和糾錯兩種情況。只進(jìn)行檢錯的解碼錯兩種情況。只進(jìn)行檢錯的解碼其原理較簡單，它是利用任何碼其原理較簡單，它是利用任何碼( )( )( )( )( )R xr xq xg xg x第123頁/共264頁其中其中, r(x)為余式。若余式為余式。若余式r(x)為零，接收碼字為零，接收碼字R(x)能被整能被整除，則除，則R(x)=T(x)，判斷無錯碼，判斷無錯碼; 第124頁/共264頁若

52、要糾正錯誤，若要糾正錯誤， 則需要知道則需要知道錯誤圖樣錯誤圖樣E(x)，以便糾正錯誤。，以便糾正錯誤。原則上糾錯解碼可按以下步驟進(jìn)原則上糾錯解碼可按以下步驟進(jìn)行：行：(1) 用生成多項式用生成多項式g(x)除接收除接收碼字碼字R(x)=T(x)+E(x)，得到余式，得到余式r(x)。(2) 按余式按余式r(x)用查表的方法用查表的方法第125頁/共264頁下面通過下面通過(7，3)循環(huán)碼的糾循環(huán)碼的糾錯解碼器來說明其工作原理。錯解碼器來說明其工作原理。(7，3)糾錯解碼器如圖糾錯解碼器如圖9.13所示。它所示。它包含除法器、緩沖器、門電路及包含除法器、緩沖器、門電路及輸出前作模輸出前作模2運(yùn)

53、算的異或門。接運(yùn)算的異或門。接收到的碼字收到的碼字R(x)輸入后分為兩路：輸入后分為兩路：一路送入緩沖器暫存，另一路送一路送入緩沖器暫存，另一路送入除法器作除法。當(dāng)碼字全部進(jìn)入除法器作除法。當(dāng)碼字全部進(jìn)入除法器后，若入除法器后，若R(x)能被能被g(x)整整碼字正確；另一方面反饋回除法碼字正確；另一方面反饋回除法器，使各級移位寄存器清零。器，使各級移位寄存器清零。ea b c d第126頁/共264頁第127頁/共264頁實際中接收的碼字是連續(xù)不實際中接收的碼字是連續(xù)不斷輸入的，中間沒有停頓。為了斷輸入的，中間沒有停頓。為了使解碼器在移位糾錯時不丟失輸使解碼器在移位糾錯時不丟失輸?shù)?28頁/共

54、264頁9.4.4BCH碼碼BCH碼的最小碼距碼的最小碼距dmin2t+1，能糾，能糾t個錯誤。個錯誤。BCH碼是循環(huán)碼中重要的一類子碼，碼是循環(huán)碼中重要的一類子碼，它的生成多項式它的生成多項式g(x)與最小碼距與最小碼距第129頁/共264頁BCH碼的特點(diǎn)是能糾正多個碼的特點(diǎn)是能糾正多個隨機(jī)錯誤，可以根據(jù)給定的糾錯隨機(jī)錯誤，可以根據(jù)給定的糾錯能力找出生成多項式。能力找出生成多項式。 BCH碼碼分為兩類：本原分為兩類：本原BCH碼和非本原碼和非本原BCH碼。本原碼。本原BCH碼的碼長碼的碼長n=2m1，m3, 生成多項式生成多項式g(x)中含有最高次數(shù)為中含有最高次數(shù)為m的本原多項的本原多項式

55、；非本原式；非本原BCH碼的碼長碼的碼長m1。第130頁/共264頁BCH碼生成多項式：碼生成多項式：g(x)=LCMm1(x), m2(x), , m2t-1(x)(9.71)式中式中: t為可糾正的錯誤個數(shù)；為可糾正的錯誤個數(shù)；mi(x)為最小多項式；為最小多項式；LCM()是是指取括號內(nèi)所有多項式的最小公指取括號內(nèi)所有多項式的最小公g82g(x)=x3+x+1。第131頁/共264頁【例例9.1】構(gòu)造一個能糾正構(gòu)造一個能糾正3個錯誤、個錯誤、 碼長為碼長為15的的BCH碼。碼。解解： 由碼長與生成多項式的由碼長與生成多項式的關(guān)系可知，關(guān)系可知，n=15，t=3，m為為4，因為因為第132

56、頁/共264頁【例例9.2】非本原非本原BCH碼碼為為(23，12)，試求其生成多項式。，試求其生成多項式。解解： 對非本原對非本原BCH碼碼(23，第133頁/共264頁下面介紹幾種常見的下面介紹幾種常見的BCH碼。碼。 (1) 格雷格雷(Golay)碼。碼。BCH碼碼(23，12)是一個特殊的非本原是一個特殊的非本原BCH碼，稱為戈雷碼，它的最小碼，稱為戈雷碼，它的最小碼距碼距dmin=2t+1=7，能糾正，能糾正t=3個個錯誤，其生成多項式為錯誤，其生成多項式為119765第134頁/共264頁 (3) 縮短形式。幾乎所有的縮短形式。幾乎所有的循環(huán)碼都存在其另一種縮短形式循環(huán)碼都存在其另

57、一種縮短形式(ns, ks)。實際應(yīng)用中，可能。實際應(yīng)用中，可能需要的碼長不是需要的碼長不是2m1或它的因或它的因子，我們可以從子，我們可以從(2m1, k)碼中挑碼中挑出前出前s位為位為0的碼組構(gòu)成新的碼，的碼組構(gòu)成新的碼，這種碼的監(jiān)督位數(shù)不變，因此糾這種碼的監(jiān)督位數(shù)不變，因此糾錯能力保持不變，但是沒有了循錯能力保持不變，但是沒有了循環(huán)性。環(huán)性。(4) RS碼。碼。RS碼是碼是Reed-m(nk)比特；最小碼距比特；最小碼距d=2t+1或或m(2t+1)比特。比特。第135頁/共264頁RS碼非常適合于糾正突發(fā)錯碼非常適合于糾正突發(fā)錯誤。它可以糾正的錯誤圖樣為：誤。它可以糾正的錯誤圖樣為：總

58、長度總長度qi=(t2i1)m+2i1的的i個突發(fā)錯誤。個突發(fā)錯誤。對于一個長度為對于一個長度為2m1符號符號的的RS碼，每個符號都可以看成是碼，每個符號都可以看成是。22420,1,m 第136頁/共264頁例如，構(gòu)造一個能糾錯誤例如，構(gòu)造一個能糾錯誤t=3個，碼長為個，碼長為n=15，m=4的的RS碼。由碼。由RS碼的參數(shù)可知，該碼的參數(shù)可知，該碼的碼距碼的碼距d=2t+1=7，監(jiān)督位，監(jiān)督位第137頁/共264頁9.59.5卷積碼卷積碼9.5.19.5.1卷積碼編碼原理卷積碼編碼原理1. 1. 卷積碼的概念卷積碼的概念第138頁/共264頁2 卷積碼的結(jié)構(gòu)及原理卷積碼的結(jié)構(gòu)及原理1) 卷

59、積碼的結(jié)構(gòu)卷積碼的結(jié)構(gòu)圖圖9.14示出了卷積碼編碼器示出了卷積碼編碼器的一般結(jié)構(gòu)。它由輸入移位寄存的一般結(jié)構(gòu)。它由輸入移位寄存器、模器、模2加法器、輸出移位寄存加法器、輸出移位寄存器三部分構(gòu)成。輸入移位寄存器器三部分構(gòu)成。輸入移位寄存器共有共有N段，每段有段，每段有k級，共級，共Nk位位寄存器，信息序列由此不斷輸入。寄存器，信息序列由此不斷輸入。第139頁/共264頁輸入移位寄存器每移入輸入移位寄存器每移入k位，位，則輸出則輸出n個比特的編碼。所以，個比特的編碼。所以，卷積碼編碼效率為卷積碼編碼效率為n, , kn第140頁/共264頁第141頁/共264頁圖圖9.15所示是一個最簡單的所示是

60、一個最簡單的(2，1，2)卷積碼編碼器，它由兩卷積碼編碼器，它由兩個移位寄存器個移位寄存器D1、D2和模和模2相加相加電路組成。編碼器的輸入信息碼電路組成。編碼器的輸入信息碼位一方面可以直接輸出，另一方位一方面可以直接輸出，另一方第142頁/共264頁第143頁/共264頁第144頁/共264頁編碼器的工作過程是：移位編碼器的工作過程是：移位寄存器按信息位的節(jié)拍工作，輸寄存器按信息位的節(jié)拍工作，輸入一位信息，電子開關(guān)倒換一次，入一位信息，電子開關(guān)倒換一次，即前半拍即前半拍(半個輸入碼元寬半個輸入碼元寬)接通接通m端，后半拍接通端，后半拍接通c端。因此，若端。因此，若 1121232310iii