第九章差錯控制編碼sxq

第9章

差錯控制編碼南京航空航天大學(xué)信息科學(xué)與技術(shù)學(xué)院通信原理教研組引言1糾錯編碼的基本原理2常用的簡單編碼3線性分組碼4循環(huán)碼5第9章差錯控制編碼67卷積碼網(wǎng)格編碼調(diào)制2copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.1引言信道解調(diào)信源編碼加密調(diào)制解密譯碼信宿噪聲同步系統(tǒng)信源編碼信道編碼差錯控制ASKFSKPSKDPSK數(shù)字通信的組成A/D數(shù)據(jù)壓縮3copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組采用信道編碼在通信過程中，會受到各種外來干擾，如脈沖干擾，隨機噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信號失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯誤，稱之為差錯。

隨機性錯誤：前后出錯位之間無一定關(guān)系，隨機、離散出現(xiàn)。突發(fā)性錯誤：差錯成串出現(xiàn)，且有一定相關(guān)性。差錯的兩大類型：

合理的設(shè)計基帶信號時域/頻域均衡都能有效的提高傳輸可靠性。發(fā)射功率的提高4copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組數(shù)字通信中的編碼信道編碼：信源編碼：為提高信號傳輸?shù)挠行远扇〉拇胧樘岣咝盘杺鬏數(shù)目煽啃远扇〉拇胧?亦稱差錯控制編碼。在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強的原始數(shù)字信號變?yōu)閹б?guī)律性或加強了規(guī)律性的數(shù)字信號，信道譯碼器則利用這些規(guī)律性來鑒別是否發(fā)生錯誤，或進(jìn)行錯誤糾正。差錯控制5copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

1、差錯控制方法（1）前向糾錯法FEC

所發(fā)碼具有糾錯能力，收端接收后自動糾錯，無需反向信道。實時性好，但譯碼設(shè)備復(fù)雜，傳輸效率↓。信源FEC編碼信道FEC譯碼信宿6copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組（2）信息反饋法IF信息信號信息信號發(fā)端收端

方法和設(shè)備簡單，無需糾檢錯編譯系統(tǒng)。但需要雙向信道，傳輸效率↓、實時性差。7copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組(3)檢錯重發(fā)法ARQ

所發(fā)碼具有檢錯能力，收端接收后判決是否出錯，通過反向信道發(fā)送判決結(jié)果，發(fā)端據(jù)此決定是否重發(fā)。譯碼設(shè)備簡單，對突發(fā)錯誤有效，要求有反饋信道。信源編碼器正向信道譯碼器信宿緩存器重發(fā)控制器反向信道重發(fā)判決器工作過程：發(fā)送——檢測——回復(fù)——重發(fā)或發(fā)送新的數(shù)據(jù)8copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組①停止等待方式

3221221ACKACKNACK發(fā)送端接收端

ARQ的三種實現(xiàn)方式：

特點：半雙工工作，簡單，要求的緩存量小，但等待時間較長，傳輸效率↓

9copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

②連續(xù)重發(fā)方式

6543254321065432543210ACK0ACK1NACK2ACK2ACK3退N步方式：從出錯幀開始重發(fā)優(yōu)缺點：傳輸效率↑，但重發(fā)的N幀中，大部分為正確，所以仍有浪費。發(fā)端緩存必須可存N幀。

10copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2987654321029876543210ACK0ACK1NACK2ACK3ACK4ACK5ACK2ACK6

只對出錯信息重發(fā)，因此傳輸效率大大提高。但收發(fā)兩端都要有足夠的存儲空間。

③選擇重發(fā)方式

11copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組反饋信道ARQFEC

編碼器正向信道FEC

譯碼器ARQ

編碼既有糾錯能力也有檢錯能力，收端收到信息碼組后在收端進(jìn)行檢測。在糾錯范圍內(nèi)：糾正；超出范圍：通過ARQ方式進(jìn)行重發(fā)。

(4)混合方式12copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組（1）根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分：

線性碼，非線性碼根據(jù)監(jiān)督碼元是否僅與本組信息元有關(guān)

分組碼，卷積碼（2）根據(jù)糾錯碼組中信息元是否隱蔽分：

系統(tǒng)碼，非系統(tǒng)碼（3）糾錯碼的分類13copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組根據(jù)碼的用途分：

檢錯碼，糾錯碼（4）根據(jù)碼元的取值：

二進(jìn)制碼，多進(jìn)制碼（5）根據(jù)構(gòu)造編碼的數(shù)學(xué)方法：

代數(shù)碼，幾何碼，算術(shù)碼（6）本課程主要討論糾隨機錯誤的二進(jìn)制線性分組碼。14copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組糾錯碼的發(fā)展概況通信的數(shù)學(xué)理論，Shannon(1948)漢明碼，Hamming(1950)級連碼，F(xiàn)orney(1966)卷積碼及有效譯碼，(60年代)RS碼及有效譯碼，(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo碼，Berrou(1993)LDPC碼，Gallager(1963),Macky(1996)空時編碼,Tarokh(2000)15copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.2糾錯編碼的基本原理1、幾個術(shù)語碼長：碼組中碼元的數(shù)目，常用n表示；碼距：兩等長碼字C1、C2對應(yīng)位上取值不同的數(shù)目，又稱為漢明(Hamming)距離，記為d(c1,c2)。碼重：碼組中非零碼元的數(shù)目，記為W；16copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組n=3時，碼距的幾何說明：（a2a1

a0

）a2a1a0（110）（011

）d=2110011（111）（000

）d=3000111最小碼距：在分組碼(n,k)中，任意兩個碼字之間漢明距離的最小值，記為dmin。最小碼距的大小關(guān)系到編碼的檢糾錯能力。01010110000117copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組發(fā)送序列C:(1111011000)接收序列R:(0110010110)比較C和R，可寫出另一個序列E：1001001110R=C+E

序列E定義為錯誤圖樣(ErrorPattern)錯誤圖樣：18copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組A、B兩消息，可用一位二進(jìn)制數(shù)表示，A=1、B=0出錯時無法判定增加一個監(jiān)督位，取11→A、00→B再增加一個監(jiān)督位，取111→A、000→B許用碼組：00，11禁用碼組：01，10若收到01或10時，可知發(fā)生了錯誤，但不能糾正錯誤。許用碼組：000，111禁用碼組：001,010,100,011,101,110如一位錯能夠糾正錯誤；若兩位錯，則只能發(fā)現(xiàn)不能糾錯2、糾錯或檢錯的原理19copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組因此這種（3,1）碼，能糾正一個錯，發(fā)現(xiàn)兩個錯。

但是(3,1)碼中，數(shù)據(jù)位僅為1位，監(jiān)督位為兩位，傳輸效率↓↓

可以看出：差錯控制是以犧牲傳輸效率為代價而換取了傳輸質(zhì)量的提高的。糾檢錯能力與加入的監(jiān)督元方式和數(shù)目有關(guān)。20copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組分組碼的三個參數(shù)碼長n，信息位k，最小距離d0，

用符號(n,k,d0)表示k個信息元an-1an-2……arar-1……

a0r個監(jiān)督元碼長：n=k+rR=k/n為編碼效率，d0一定(糾錯能力一定)時，k/n大，效率高。

對被傳輸?shù)男畔⑿蛄蟹纸M，每組為k個信息元，對每組按某種關(guān)系附加(n-k)個監(jiān)督碼元(校驗)，形成為n位的碼字。這種方法構(gòu)成的碼組稱為分組碼。3、分組碼21copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組4、分組碼的糾(檢)錯能力與最小碼距d0的關(guān)系

任一（n，k）分組碼，若要在碼字內(nèi)能：

1/檢測e個隨機錯誤，則要求：

d0≥e+1

2/糾正t個隨機錯誤，則要求：

d0≥2t+1

3/糾正t個同時檢測e(e>t)個隨機錯誤，則要求：d0≥e+t+122copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1糾（檢）錯能力的幾何解釋

A1

d0eA2（a）

A1

A2

d0et（c）

A1

d0tA2（b）A2t1123copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-1]一個碼集，只有兩個許用碼：0000、1111，試求其糾、檢錯能力和編碼效率。24copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組解：根據(jù)碼距的定義，則該碼集d0=4，1/用于檢錯，e≤d0

–1=3，即可檢3個錯誤；2/用于糾錯，t≤(d0–1)/2=3/2，取整，即可糾1個錯誤；3/同時用于糾、檢錯，d0≥

e+t+1（e＞t）?。篹=2，t=1，則可滿足上式，即可檢2個錯誤同時糾一個錯；R=k/n=1/4編碼效率：25copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組4、對糾錯編碼的要求糾、檢錯能力強，編碼效率高，碼長短，編碼規(guī)律簡單。26copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組5.差錯控制編碼的效用

假設(shè)在隨機信道中，發(fā)送“0”和“1”的錯誤概率相等，都等于p，且p＜＜1，在碼長為n的碼組中，發(fā)生r個錯誤的概率為：27copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組例如：當(dāng)n=7，p=10-3時，則有：

由此可見，即使僅能糾正1-2個錯誤，也可使誤碼率下降幾個數(shù)量級。所以差錯控制編碼具有較大的實際應(yīng)用價值。28copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組6.有擾信道編碼定理（Shannon第二定理）

對于給定的有擾信道，若信道容量為C，只要發(fā)送端以低于C的信息速率Rb發(fā)送信息，則一定存在一種編碼方法，使得譯碼錯誤概率P隨著碼長n的增加，按指數(shù)下降至任意小的值，表示為Pe-nE(Rb)E(Rb)為誤差指數(shù)，Rb<C時，E(Rb)>0。Rbmax=C=Blog2(1+S/N)（bit/s）29copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

1.碼長n和信息速率Rb一定時，隨C誤差指數(shù)E(Rb)P↓隨指數(shù)下降。其中C=Blog2(1+S/N)（bit/s）

2.在C和Rb一定時(Rb<C)，隨碼長nP隨指數(shù)下降(P0)。數(shù)字傳輸系統(tǒng)中，無誤碼傳輸?shù)淖罡咝畔⑺俾?/p>

Rbmax=C=Blog2(1+S/N)（bit/s）

兩個結(jié)論：30copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組編碼性能舉例未采用糾錯編碼時， 若接收信噪比等于

7dB，編碼前誤碼率 約為810-4，圖中A

點，在采用糾錯編碼 后，誤碼率降至約4

10-5，圖中B點。這樣，增大發(fā)送功率,就能降低誤碼率約一個半數(shù)量級。10-610-510-410-310-210-1編碼后PeAB信噪比(dB)31copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組由圖還可以看出，若保持誤碼率在10-5，圖中C點，未采用編碼時，約需要信噪比Eb/n0=9.5dB。在采用這種編碼時，約需要信噪比7.5dB，圖中D點?？梢怨?jié)省功率2dB。通常稱這2dB為編碼增益。上面兩種情況付出的代 價是帶寬增大。10-610-510-410-310-210-1PeCD信噪比(dB)編碼后32copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組傳輸速率和Eb/n0的關(guān)系對于給定的傳輸系統(tǒng)式中，RB為碼元速率。 若希望提高傳輸速率， 由上式看出勢必使信噪比下降，誤碼率增大。假設(shè)系統(tǒng)原來工作在圖中C點，提高速率后由C點升到E點。但加用糾錯編碼后，仍可將誤碼率降到D點。這時付出的代價仍是帶寬增大。10-610-510-410-310-210-1編碼后PeCDE信噪比(dB)33copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9-3常用的簡單編碼1、奇偶監(jiān)督碼：

k=n-1,r=1的線性碼。特點：碼組中的1個數(shù)是奇數(shù)（奇監(jiān)督碼）或偶數(shù)（偶監(jiān)督碼）。偶監(jiān)督時，要滿足：奇監(jiān)督時，要滿足：兩者的校驗?zāi)芰ο嗤荒軝z測出奇數(shù)個錯誤。R=k/n=n-1/n=1-1/n編碼效率：34copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

碼長5的偶監(jiān)督碼序碼字序碼字號信息碼元監(jiān)督元號信息碼元監(jiān)督元

a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110

35copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

偶監(jiān)督碼編碼器a4a3a2a1+信息組a0a1a2a3a4碼字36copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組b3b0b1b2b4+接收碼組BS檢錯信號偶監(jiān)督碼的檢錯電路37copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-2]：一數(shù)據(jù)序列：

{11100

10111

01101

10001

10101}試對其進(jìn)行（6，5）偶校驗編碼，寫出碼序列并分析其抗干擾能力∣∣∣

∣38copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組一數(shù)據(jù)序列：

{11100

10111

01101

10001

10101}試對其進(jìn)行（6，5）偶校驗編碼，寫出碼序列并分析其抗干擾能力解：（6，5）,將數(shù)據(jù)序列每5碼元分組，并作：的運算可得出編碼數(shù)據(jù)序列：{111001∣101110∣011011∣100010∣101011}只能檢測出奇數(shù)個錯誤，不能發(fā)現(xiàn)偶數(shù)個錯誤，也不能糾錯。∣∣∣

∣39copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2、水平垂直奇偶校驗碼：

又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點：對水平方向和垂直方向的碼元同時實施奇偶監(jiān)督。110010100000100001101001111000011100111000001010101010111000111100行列監(jiān)督碼40copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組適于監(jiān)測突發(fā)錯誤：逐行傳輸時，能檢測長度bM+1的突發(fā)錯誤;逐列傳輸時,能檢測長度bL+1的突發(fā)錯誤；還能糾正一些僅在一行中的單個錯誤。110010100000100001101001111000011100111000001010101010111000111100L＝5，M＝10的行列監(jiān)督碼其中M為列數(shù)，L為行數(shù)41copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組3、恒比碼：

又稱等重碼或定1碼。特點：碼組中0，1的個數(shù)保持不變。若碼長為n，碼重為w，則此碼的碼字個數(shù)為：Cnw，禁用碼字個數(shù)為：2n-Cnw碼字的個數(shù)C53=10檢錯能力較強，可檢出所有奇數(shù)和部分偶數(shù)錯誤。檢錯能力較強，可檢出所有奇數(shù)和部分偶數(shù)錯誤。適用于傳輸電報或其他鍵盤設(shè)備產(chǎn)生的字母或符號，但不適合信源發(fā)出的是二進(jìn)制隨機數(shù)字序列的場合。42copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組數(shù)字碼字0123456789011010101111001101101101000111101011110001110100113:2恒比碼如：我國的電報，每個漢字用四個10進(jìn)制數(shù)表示，每位10進(jìn)制數(shù)就采用3：2恒比碼構(gòu)成的5位碼組來表示。碼字的個數(shù)C53=1043copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組作業(yè)：4、正反碼：

簡單的可糾錯編碼，信元數(shù)等于監(jiān)督元數(shù)特點：信息位中，有奇數(shù)個1時，監(jiān)督位重復(fù)信息位；信息位中，有偶數(shù)個1時，監(jiān)督位取信息位的反碼；可糾一位、檢測所有兩位錯和部分兩位以上的錯誤。例：11001→11001∣1100110001→10001∣01110(n,k)其中k=n/2編碼效率：R=k/n=1/244copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4線性分組碼9.4.1基本概念

可用線性方程組表述碼的規(guī)律性的分組碼稱為線性分組碼。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集合構(gòu)成代數(shù)學(xué)中的群，因此，又稱為群碼。45copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

1.含有全零碼字。

2.任意兩個許用碼字之和仍是一個許用碼字。（封閉性）

3.最小碼距d0等于非零碼字的最小重量即d0=Wmin

（由此性質(zhì)可以方便的確定出線性分組碼的最小碼距，進(jìn)而明確其糾錯能力。）在群中只有一種運算，就是模2和。線性分組碼的性質(zhì)：46copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

奇偶監(jiān)督碼是一種最簡單的線性碼，我們曾經(jīng)作了偶校驗的例子。稱為監(jiān)督方程。接收時，為了檢測傳輸時是否有錯，還要做同樣的計算：這里S稱為校正子，上式也稱伴隨式。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯誤。47copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。r位監(jiān)督碼除了用全“0”表示無錯外，可表示種錯誤圖樣。(n,k)碼可糾錯的錯誤圖樣數(shù)為：

我們把接收碼組R與發(fā)射碼組C的差稱為錯誤圖樣，用E表示：E=C-R，或者C=R+E

(n,k)中，信息碼為k位，可傳輸M=2k種信息，當(dāng)增加r位的監(jiān)督位后，有2n種狀態(tài)，但只取2k種為許用狀態(tài)，其他為禁用，(n,k)碼可檢測的錯誤圖樣數(shù)為2n-2k2n-k-1=2r-1不可檢測的錯誤圖樣數(shù)為2k-148copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2n-k-1++……+=對于能糾正t個錯誤的線性分組碼(n,k)應(yīng)滿足：是錯i位的個數(shù)。如果滿足，則有可能構(gòu)造出糾正一位或一位以上的線性碼。i=1時，

即對于碼組長度為n，信息碼元k位，監(jiān)督元r，49copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

思考：[例9-3]設(shè)(n，k)中，k=4，要求能糾一位錯，取r=？50copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

解：

(n，k)線性分組碼，k=4，要求能糾一位錯，現(xiàn)取r=3，可指示23-1=7種錯誤，碼長n=4+3=7，表示為：C=[C6C5C4C3C2C1C0]其中C6C5C4C3為信息碼元，C2C1C0為監(jiān)督元由r=3，可有三個監(jiān)督方程和校正子，設(shè)為s1s2s3恰好滿足,故可糾一位錯。51copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組設(shè)s1s2s3三位校正子與誤碼位置的對應(yīng)關(guān)系為：000001010100011101110111誤碼位置無錯

C0C1C2C3C4C5C6S1S2S3于是監(jiān)督碼元C2C1C0應(yīng)由以下監(jiān)督方程決定。C2=C6+C5+C4C1=C6+C5+C3C0=C6+C4+C3←監(jiān)督元與信息元之間的線性方程組s1=C2+C6+C5+C4=0s2=C1+C6+C5+C3=0s3=C0+C6+C4+C3=052copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組于是得到(7，4)線性分組碼如下：

序碼字號信息元

監(jiān)督元

8100011191001100101010010111011001121100001131101010141110100151111111

序碼字號信息元

監(jiān)督元

000000001000101120010101300111104010011050101101601100117011100053copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4.2監(jiān)督矩陣將前面的監(jiān)督方程改寫成矩陣的形式，

C=[C6C5C4C3C2C1C0]可看成為編碼矢量，于是有：記做：監(jiān)督方程54copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組H--監(jiān)督矩陣

不滿足以上關(guān)系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。2/H矩陣各行是線性無關(guān)的。行數(shù)---監(jiān)督元的個數(shù)r列數(shù)---碼組長度nIr為r階單位陣1/當(dāng)有H=[PIr]時稱為典型矩陣，55copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組利用監(jiān)督方程，我們可以對線性碼的封閉性加以證明即H陣與編碼碼字的轉(zhuǎn)置乘積為0，可用來作為判斷接收碼組是否錯的依據(jù)。56copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

設(shè)監(jiān)督方程A1、A2均為線性碼集合中的許用碼組，因此有令兩許用碼組相加

A1+A2帶入監(jiān)督方程，有：因此，A1+A2亦為許用碼組。57copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4.3生成矩陣

當(dāng)給出信息組后，如何方便迅速地求出整個編碼碼組，即如何生成編碼矢量？C2=C6+C5+C4C1=C6+C5+C3C0=C6+C4+C3由監(jiān)督元與信息元之間的關(guān)系：或者可以寫成：58copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組令則有：給Q的左邊，加一個k×k階的單位矩陣，則構(gòu)成：G=[IkQ]稱為生成矩陣，且為典型形式。典型G矩陣行數(shù)----信息元的個數(shù)k列數(shù)----碼組長度n每行本身就是一個許用碼組于是有：矩陣和非典型矩陣之間可以轉(zhuǎn)換。59copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組碼字的前面k位為信息位，后面位為監(jiān)督位一般情況，定義線性分組碼的碼字有如下形式：信息碼元監(jiān)督位信息位編碼碼字系統(tǒng)形式的線性分組碼

編碼

60copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組設(shè)信息組生成矩陣編碼碼組61copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組1）由G和信息組即可產(chǎn)生全部碼字.通過典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。62copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

（1）試確定(n,k)，并求H；

(2)寫出監(jiān)督元與信息元的關(guān)系式及該（n,k）碼的全部碼字；

(3)確定最小碼距及檢錯能力。[例9-4]設(shè)已知63copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組解：求H，需確定P，應(yīng)將已知的那個G轉(zhuǎn)換成典型形式，求出Q，再利用求出G。H=[PIr]=64copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

(2)

設(shè)C=于是有：監(jiān)督元與信息元的關(guān)系式65copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組用三位二進(jìn)制數(shù)的所有8種狀態(tài)帶入，可得到所有碼字如右表。

序號碼字

00000001001011201011030111014100101510111061100117111000(3)確定最小碼距及檢錯能力所以有：d0=3可用于檢兩位錯或糾一位錯。利用性質(zhì)知：最小碼距d0等于非零碼字的最小重量即d0=wmin66copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4.4校正子S發(fā)送端經(jīng)過編碼后給出：接收端收到的碼組為：兩者的差記為：表示第i位無錯表示第i位有錯E稱為錯誤圖樣。共有2n個錯誤圖樣。當(dāng)E為全零錯誤圖樣時，R=C沒有傳輸錯誤;67copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組可利用E檢出或糾正錯誤；傳輸中的錯誤超出了可糾錯的范圍?？赡苡袃煞N情況：(n,k)可檢測的錯誤圖樣數(shù)為2n-2k(n,k)可糾錯的錯誤圖樣數(shù)為2n-k-1這時的錯誤圖樣稱為不可檢測的錯誤圖樣一般來講，E=0，則R=C，可滿足監(jiān)督方程E≠0，則R≠C，不滿足監(jiān)督方程檢錯：當(dāng)S=0時，認(rèn)為E=0，當(dāng)S0時，認(rèn)為E0,校正子S的計算即校正子只與錯誤圖樣E有關(guān)。68copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組標(biāo)準(zhǔn)陣列表排列方法陪集陪集首69copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組陪集陪集首70copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組構(gòu)造標(biāo)準(zhǔn)陣列的一般方法如下：1）用概率譯碼確定各伴隨式S對應(yīng)的差錯圖案E，共對；2）表格為列，行，先確定第一行和第一列，第一行為個碼字，第一列為；3）各列對應(yīng)的元素為第一列的和該列的之和；陪集首

譯碼時，計算伴隨式S，查表獲得錯誤圖樣E，最后恢復(fù)出發(fā)送碼字C＝E＋R。71copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-5]

已知監(jiān)督矩陣：若接收為：R=[0000011]，試確定是否錯誤，若接收錯誤，試進(jìn)行糾錯。72copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組R=[0000011]，解：計算校正子73copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組000001010100011101110111誤碼位置無錯

C0C1C2C3C4C5C6S1S2S3錯誤圖樣：

E=[0001000]對照校正子與誤碼位置，確定錯誤圖樣：74copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組于是：R`=R+E=[0000011]+[0001000]由于，當(dāng)只發(fā)生一位錯碼時，矩陣E中只有一個非零元素，與H的轉(zhuǎn)置相乘的結(jié)果是選出其中的一列，即校正子與H矩陣的哪一列相同，則該列即為碼元發(fā)生錯誤的位置。

=[0001011]75copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組(n，k)線性分組碼編、譯碼過程小結(jié)：

編碼過程：設(shè)線性分組碼為(n，k)，信息碼為：1)根據(jù)生成矩陣或監(jiān)督矩陣，2)由C=MG0

求出所有碼字，且為系統(tǒng)碼。H0=[PIr]G0=[IkQ]求出典型生成矩陣；76copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組譯碼過程：1）由收到的碼組R計算校正子S；2）由S判決是否有錯并通過找出錯誤圖樣；3）按照R+E=C計算并還原C；4）將碼組C還原成原信息組M。77copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.4.5漢明碼漢明碼是用于糾一位錯誤的線性分組碼。特點：最小碼距：

糾錯能力：編碼效率：78copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-6]n=15的漢明碼，其監(jiān)督位為多少？編碼效率為多少？79copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組解：于是其信息位有15-4=11位此漢明碼為（15，11）碼編碼效率：其監(jiān)督位有15-11=4位80copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

漢明碼是線性分組碼，因此其監(jiān)督矩陣同樣有n列、r行，當(dāng)監(jiān)督位數(shù)給定后，即可構(gòu)造出漢明碼。例，r=3

H矩陣的n列由除了全零以外的個r位碼構(gòu)成，每碼組出現(xiàn)一次且全部出現(xiàn)。（H不唯一）構(gòu)造81copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組得到的漢明碼如下所示：信息位監(jiān)督位信息位監(jiān)督位a6a5a4a300000001001000110100010101100111a2a1a0000011101110110101011000a6a5a4a310001001101010101100110111101111a2a1a011110001000100101010011182copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組（7，4）漢明碼編碼器a6a5a4a3信息組a0a1a2a3a4碼字++a5a6+83copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組完備碼

糾正單個錯誤的漢明碼中，r位校正子碼組與誤碼圖樣一一對應(yīng)，最充分地利用了監(jiān)督位所能提供的信息。

在一般情況下，對于能糾正t個錯誤的線性分組碼(n，k)，應(yīng)滿足以下不等式：

因此，漢明碼也是糾一位錯的線性分組碼中，編碼效率最高的。84copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

上式取等號時，校正子與誤碼不超過t個的所有圖樣一一對應(yīng)，監(jiān)督碼元得到最充分的利用，這種線性分組碼即完備碼。

除漢明碼外，迄今為止，找到的唯一能糾正多個錯誤的完備碼為(23，12)戈雷碼。t=3漢明碼就是一種完備碼。

該式亦稱為漢明界，它給出已知k和t時，所需要的監(jiān)督位數(shù)。85copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

但此時構(gòu)成的則非漢明碼。

通常選擇碼重最小的矢量優(yōu)先。[例9-6]試構(gòu)造一個k=5的可糾一個錯的線性分組碼1/計算最短的碼長；2/構(gòu)造H；3/求生成矩陣G；4/求信息組為(10101)的編碼碼字C。86copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組解：1/因為t等于1,且要求k=5,可用試探法確定n設(shè)：n-k=3，則不滿足糾錯要求；

設(shè)：n-k=4，則滿足糾錯要求；于是取n=9，此時r=n-k=4，(9,5)線性分組碼87copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2/r=4，四位碼共有種狀態(tài)，除全零外都可用于構(gòu)造H矩陣。

為了構(gòu)造典型矩陣，選1000，0100，0010，0001四碼組，然后從其余的11個碼組中，再選出5個，通常按照碼重從小到大選擇。PIr實際只需9個88copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組4/M=[1010

1]C=MG=[101010110]Q3/求生成矩陣已知

Ik于是有：89copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.5循環(huán)碼9.5.1循環(huán)碼原理

循環(huán)碼是線性分組碼的一個重要子類，也是目前研究最成熟的一類碼。它不僅有封閉性，且還有循環(huán)性。(n，k)碼組則將所有碼元向左循環(huán)一位，得到的：也是許用碼組是許用碼組。即90copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組

若線性分組碼的任一碼組循環(huán)移位所得碼組仍在該碼組集中，則此碼為循環(huán)碼。（7，3）循環(huán)碼序號碼字

0000000010011101201001113011101041001110510100116110100171110100循環(huán)碼的循環(huán)圈數(shù)≥2W=00W=42156734

同一循環(huán)圈內(nèi)，碼字的重量相同91copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組序號碼字

00000001001001201001030110114100100510110161101107111111（6，3）循環(huán)碼W=00W=2124W=4536W=6792copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組★由于具有循環(huán)性，編譯碼設(shè)備較簡單；★可以用代數(shù)的方法分析和設(shè)計編碼。10-5-2循環(huán)碼的多項式表示已知碼組：設(shè)x為一個任意的實變量，其冪次代表移位的次數(shù)，以Ci作為多項式的系數(shù)，則可以得到碼多項式：循環(huán)碼的特點93copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組每循環(huán)一位，相當(dāng)于碼多項式乘以x，仍為許用碼組01110101、生成多項式與生成矩陣

循環(huán)碼中次數(shù)最低的多項式（全0碼字除外）稱為生成多項式g(x)。0011101例：即：94copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組那么，都是許用碼組，而這k個碼組是線性無關(guān)的。于是用它們組成的矩陣則為生成矩陣設(shè)信息碼組為：其對應(yīng)多項式為：95copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組則編碼碼組為：由上式可看出：用G(x)生成的碼字，都是g(x)的倍式，都可以被g(x)整除。96copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組如何尋找生成多項式？已知編碼碼組為：生成多項式是一個n-k次的多項式，且本身也是一個許用碼組：為一個n次多項式，它是在模運算下的一個許用碼組，即：分子分母均為n次，故Q(x)=1于是上式成為：97copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組有就是說：g(x)的三個特性：也就是說，尋找g(x)的過程，就是對進(jìn)行因式分解的過程。98copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-8]

為了尋找(7，3)循環(huán)碼的生成多項式，只需找出(n-k)=(7-3)=4次的因式即可。兩者均可，但將產(chǎn)生出不同的編碼碼組。(7，6)碼：(7，1)碼：(7，4)碼：99copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.5.2循環(huán)碼的編、譯碼方法1、循環(huán)碼的編碼方法首先根據(jù)給定的(n,k)選定生成多項式g(x)并求出G(x)；由C(x)=MG(x)可以生成所有碼字，但不是系統(tǒng)碼；生成系統(tǒng)碼的步驟如下：1/

做，即在信息碼后附加n-k個零；如：m=110，n-k=7-3=4時，相當(dāng)于：1100000100copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2/用g(x)除得到商Q(x)和余式r(x)

余式r(x)的次數(shù)必小于g(x)的次數(shù)n-k，將此余式加于信息位之后，成為編碼多項式。3/編出碼組

它必能被g(x)整除。101copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組[例9-9]（7，3）碼，選定解：m=110，試編碼。編出碼組為：1100101102copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2、循環(huán)碼的譯碼方法設(shè)接收碼組為：對應(yīng)多項式為R(x)1/用生成多項式g(x)除R(x)，當(dāng)傳輸無錯時，必能整除。

因此，當(dāng)r’(x)=0，則R(x)無錯。如果僅是檢錯，可給出結(jié)論。103copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組2/如果用于糾錯，需進(jìn)一步按余式r’(x)用查表法或運算求出錯誤圖樣E(x)；3/根據(jù)錯誤圖樣做：C’(x)=R(x)-E(x)完成糾錯。例：（7，3）碼，選定接收碼組為：0010101，是判斷是否有錯？解：r’(x)=111，傳輸有錯誤。104copyright信息科學(xué)與技術(shù)學(xué)院通信原理教研組9.5.3截短循環(huán)碼截短目的：在設(shè)計糾錯編碼方案時，常常信息位數(shù)k、碼長n和糾錯能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。這時，可以采用將碼長截短的方法，得出滿足要求的編碼。截短方法：設(shè)給定一個(n,k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i(0<i<k)個信息位全為“0”，于是它變成僅有2k-i種碼組。然后從中刪去這i位全“0”的信息位，最終得到一個(n–i,k–i)的線性碼。將這種碼稱為截短循環(huán)碼。截短循環(huán)碼性能：循環(huán)碼截短前后至少具有相同的糾錯能力，并且編解碼方法仍和截短前的方法一樣。例：要求構(gòu)造一個能夠糾正1位錯碼的(13,9)碼。這時可以由(15,11)循環(huán)碼的11種碼組中選出前