第九章差錯控制編碼

第九章差錯控制編碼第一頁，共101頁。引言1糾錯編碼的基本原理2常用的簡單編碼3線性分組碼4循環(huán)碼5第9章差錯控制編碼67卷積碼網(wǎng)格編碼調(diào)制2008.82第二頁，共101頁。9.1引言信道解調(diào)信源編碼加密調(diào)制解密譯碼信宿噪聲同步系統(tǒng)信源編碼信道編碼差錯控制ASKFSKPSKDPSK數(shù)字通信的組成A/D數(shù)據(jù)壓縮2008.83第三頁，共101頁。數(shù)字通信中的編碼分為：信道編碼：信源編碼：為提高信號傳輸?shù)挠行远扇〉拇胧?。為提高信號傳輸?shù)目煽啃远扇〉拇胧?。亦稱差錯控制編碼。2008.84第四頁，共101頁。

在通信過程中，會受到各種外來干擾，如脈沖干擾，隨機噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信號失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯誤，稱之為差錯。2008.85第五頁，共101頁。差錯的兩大類型：

隨機性錯誤：前后出錯位之間無一定關(guān)系，隨機、離散出現(xiàn)。

突發(fā)性錯誤：差錯成串出現(xiàn)，且有一定相關(guān)性。實際信道中，上述兩種錯誤常同時存在。

2008.86第六頁，共101頁。合理的設(shè)計基帶信號時域/頻域均衡發(fā)射功率的提高采用信道編碼都能有效的提高傳輸可靠性。2008.87第七頁，共101頁。差錯控制

在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強的原始數(shù)字信號變?yōu)閹б?guī)律性或加強了規(guī)律性的數(shù)字信號，信道譯碼器則利用這些規(guī)律性來鑒別是否發(fā)生錯誤，或進(jìn)行錯誤糾正。2008.88第八頁，共101頁。

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

所發(fā)碼具有糾錯能力，收端接收后自動糾錯，無需反向信道。實時性好，但譯碼設(shè)備復(fù)雜，傳輸效率↓。信源FEC編碼信道FEC譯碼信宿（2）信息反饋法IF信息信號信息信號發(fā)端收端

方法和設(shè)備簡單，無需糾檢錯編譯系統(tǒng)。但需要雙向信道，傳輸效率↓、實時性差。2008.89第九頁，共101頁。

(3)檢錯重發(fā)法ARQ

所發(fā)碼具有檢錯能力，收端接收后判決是否出錯，通過反向信道發(fā)送判決結(jié)果，發(fā)端據(jù)此決定是否重發(fā)。譯碼設(shè)備簡單，對突發(fā)錯誤有效，要求有反饋信道。信源編碼器正向信道譯碼器信宿緩存器重發(fā)控制器反向信道重發(fā)判決器工作過程：發(fā)送——檢測——回復(fù)——重發(fā)或發(fā)送新的數(shù)據(jù)2008.810第十頁，共101頁。①停止等待方式

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

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

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

2008.811第十一頁，共101頁。

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

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

2008.812第十二頁，共101頁。2987654321029876543210ACK0ACK1NACK2ACK3ACK4ACK5ACK2ACK6

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

③選擇重發(fā)方式

2008.813第十三頁，共101頁。反饋信道ARQFEC

編碼器正向信道FEC

譯碼器ARQ

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

(4)混合方式

2008.814第十四頁，共101頁。（1）根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分：

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

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

系統(tǒng)碼，非系統(tǒng)碼（3）糾錯碼的分類2008.815第十五頁，共101頁。根據(jù)碼的用途分：

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

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

代數(shù)碼，幾何碼，算術(shù)碼（6）本課程主要討論糾隨機錯誤的二進(jìn)制線性分組碼。2008.816第十六頁，共101頁。9、2糾錯編碼的基本原理1、幾個術(shù)語碼長：碼組中碼元的數(shù)目，常用n表示；碼距：兩等長碼字C1、C2對應(yīng)位上取值不同的數(shù)目，又稱為漢明(Hamming)距離，記為d(c1,c2)。碼重：碼組中非零碼元的數(shù)目，記為W；最小碼距：在分組碼(n,k)中，任意兩個碼字之間漢明距離的最小值，記為dmin。碼距的大小關(guān)系到編碼的檢糾錯能力。2008.817第十七頁，共101頁。n=3時，碼距的幾何說明：（a2a1a0

）a2a1a0（110）（011

）d=2110011（111）（000

）d=30001112008.818第十八頁，共101頁。A、B兩消息，可用一位二進(jìn)制數(shù)表示，A=1、B=0出錯時無法判定。例

增加一個監(jiān)督位，取11→A、00→B,若收到01或10時，

可知發(fā)生了錯誤，但不能糾正錯誤。再增加一個監(jiān)督位，取111→A、000→B,如一位錯：B→001A→110；若兩位錯011,110則只能發(fā)現(xiàn)不能糾錯

因此這種（3.1）碼，能糾正一個錯，發(fā)現(xiàn)兩個錯。

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

可以看出：差錯控制是以犧牲傳輸效率為代價而換取了傳輸質(zhì)量的提高的。糾檢錯能力與加入的監(jiān)督元數(shù)目成正比。

2、糾錯或檢錯的原理2008.819第十九頁，共101頁。分組碼的三個參數(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)成的碼組稱為分組碼。2008.820第二十頁，共101頁。

3、分組碼的糾(檢)錯能力與最小碼距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+12008.821第二十一頁，共101頁。糾（檢）錯能力的幾何解釋

A1

d0eA2（a）

A1

A2

d0et（c）

A1

d0tA2（b）A2t2008.822第二十二頁，共101頁。例：一個碼集，只有兩個許用碼：0000、1111，試求其糾、檢錯能力和編碼效率。2008.823第二十三頁，共101頁。4、對糾錯編碼的要求糾、檢錯能力強，編碼效率高，碼長短，編碼規(guī)律簡單。例：一個碼集，只有兩個許用碼：0000、1111，試求其糾檢錯能力和編碼效率。解：根據(jù)碼距的定義，則該碼集d0=4，1/用于檢錯，e≤d0

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

e+t+1（e＞t）取：e=2，t=1，則可滿足上式，即可檢2個錯誤同時糾一個錯；R=k/n=1/4編碼效率：2008.824第二十四頁，共101頁。5.差錯控制編碼的效用

假設(shè)在隨機信道中，發(fā)送“0”和“1”的錯誤概率相等，都等于p，且p＜＜1，在碼長為n的碼組中，發(fā)生r個錯誤的概率為：2008.825第二十五頁，共101頁。例如：當(dāng)n=7，p=10ˉ3時，則有：

由此可見，即使僅能糾正1-2個錯誤，也可使誤碼率下降幾個數(shù)量級。所以差錯控制編碼具有較大的實際應(yīng)用價值。2008.826第二十六頁，共101頁。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）2008.827第二十七頁，共101頁。系統(tǒng)帶寬和信噪比的矛盾：由上節(jié)所述的糾錯編碼原理可知，為了減少接收錯誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結(jié)果使發(fā)送序列增長，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關(guān)。2008.828第二十八頁，共101頁。編碼性能舉例未采用糾錯編碼時， 若接收信噪比等于

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

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

10-5，圖中B點。這樣， 不增大發(fā)送功率 就能 降低誤碼率約一個半 數(shù)量級。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)2008.829第二十九頁，共101頁。由圖還可以看出，若 保持誤碼率在10-5， 圖中C點，未采用編 碼時，約需要信噪比

Eb/n0=10.5dB。在 采用這種編碼時，約 需要信噪比7.5dB，圖 中D點?？梢怨?jié)省功率

2dB。通常稱這2dB為

編碼增益。上面兩種情況付出的代 價是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)2008.830第三十頁，共101頁。傳輸速率和Eb/n0的關(guān)系 對于給定的傳輸系統(tǒng) 式中，RB為碼元速率。 若希望提高傳輸速率， 由上式看出勢必使信 噪比下降，誤碼率增 大。假設(shè)系統(tǒng)原來工作 在圖中C點，提高速率后 由C點升到E點。但加用 糾錯編碼后，仍可將誤碼 率降到D點。這時付出的 代價仍是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)2008.831第三十一頁，共101頁。9-3常用的簡單編碼1、奇偶監(jiān)督碼：

k=n-1,r=1的線性碼。特點：碼組中的1個數(shù)是奇數(shù)（奇監(jiān)督碼）或偶數(shù)（偶監(jiān)督碼）。偶監(jiān)督時，要滿足：奇監(jiān)督時，要滿足：兩者的校驗?zāi)芰ο嗤?，均只能檢測出奇數(shù)個錯誤。R=k/n=n-1/n=1-1/n編碼效率：2008.832第三十二頁，共101頁。序碼字序碼字號信息碼元監(jiān)督元號信息碼元監(jiān)督元

a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110

碼長5的偶監(jiān)督碼2008.833第三十三頁，共101頁。

偶監(jiān)督碼編碼器a4a3a2a1+信息組a0a1a2a3a4碼字2008.834第三十四頁，共101頁。b3b0b1b2b4+接收碼組BS檢錯信號偶監(jiān)督碼的檢錯電路2008.835第三十五頁，共101頁。例：一數(shù)據(jù)序列：

{11100

10111

01101

10001

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

∣2008.836第三十六頁，共101頁。例：一數(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ù)個錯誤，也不能糾錯。∣∣∣

∣2008.837第三十七頁，共101頁。2、水平垂直奇偶校驗碼：

又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點：對水平方向和垂直方向的碼元同時實施奇偶監(jiān)督。110010100000100001101001111000011100111000001010101010111000111100行列監(jiān)督碼2008.838第三十八頁，共101頁。適于監(jiān)測突發(fā)錯誤：逐行傳輸時，能檢測長度bm+1的突發(fā)錯誤;逐列傳輸時,能檢測長度bL+1的突發(fā)錯誤；還能糾正一些僅在一行中的單個錯誤。其中m為行數(shù)，L為列數(shù)2008.839第三十九頁，共101頁。3、恒比碼：

又稱等重碼或定1碼。特點：碼組中0，1的個數(shù)保持不變。若碼長為n，碼重為w，則此碼的碼字個數(shù)為：Cnw，禁用碼字個數(shù)為：2n-Cnw例如：我國的電報，每個漢字用四個10進(jìn)制數(shù)表示，每位10進(jìn)制數(shù)就采用3：2恒比碼構(gòu)成的5位碼組來表示。碼字的個數(shù)C53=10檢錯能力較強，可檢出所有奇數(shù)和部分偶數(shù)錯誤。2008.840第四十頁，共101頁。數(shù)字碼字0123456789011010101111001101101101000111101011110001110100113:2恒比碼如：我國的電報，每個漢字用四個10進(jìn)制數(shù)表示，每位10進(jìn)制數(shù)就采用3：2恒比碼構(gòu)成的5位碼組來表示。碼字的個數(shù)C53=102008.841第四十一頁，共101頁。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/22008.842第四十二頁，共101頁。9.4線性分組碼9.4.1基本概念

可用線性方程組表述碼的規(guī)律性的分組碼稱為線性分組碼。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集合構(gòu)成代數(shù)學(xué)中的群，因此，又稱為群碼。2008.843第四十三頁，共101頁。

1.含有全零碼字。

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

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

（由此性質(zhì)可以方便的確定出線性分組碼的最小碼距，進(jìn)而明確其糾錯能力。）在群中只有一種運算，就是模2和。線性分組碼的性質(zhì)：2008.844第四十四頁，共101頁。

奇偶監(jiān)督碼是一種最簡單的線性碼，我們曾經(jīng)作了偶校驗的例子。稱為監(jiān)督方程。接收時，為了檢測傳輸時是否有錯，還要做同樣的計算：這里S稱為校正子，上式也稱伴隨式。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯誤。2008.845第四十五頁，共101頁。當(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-12008.846第四十六頁，共101頁。2n-k-1++……+=對于能糾正t個錯誤的線性分組碼(n,k)應(yīng)滿足：是錯i位的個數(shù)。如果滿足，則有可能構(gòu)造出糾正一位或一位以上的線性碼。i=1時，

即對于碼組長度為n，信息碼元k位，監(jiān)督元r，2008.847第四十七頁，共101頁。下面我們通過例子來說明如何構(gòu)造線性碼。

思考：

設(shè)(n，k)中，k=4，要求能糾一位錯，取

r=？2008.848第四十八頁，共101頁。

解：

(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恰好滿足,故可糾一位錯。2008.849第四十九頁，共101頁。設(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=02008.850第五十頁，共101頁。于是得到(7，4)線性分組碼如下：

序碼字號信息元

監(jiān)督元

8100011191001100101010010111011001121100001131101010141110100151111111

序碼字號信息元

監(jiān)督元

00000000100010112001010130011110401001105010110160110011701110002008.851第五十一頁，共101頁。9.4.2監(jiān)督矩陣將前面的監(jiān)督方程改寫成矩陣的形式，

C=[C6C5C4C3C2C1C0]可看成為編碼矢量，于是有：記做：監(jiān)督方程2008.852第五十二頁，共101頁。H--監(jiān)督矩陣

不滿足以上關(guān)系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。2/H矩陣各行是線性無關(guān)的。行數(shù)---監(jiān)督元的個數(shù)r列數(shù)---碼組長度nIr為r階單位陣1/當(dāng)有H=[PIr]時稱為典型矩陣，2008.853第五十三頁，共101頁。利用監(jiān)督方程，我們可以對線性碼的封閉性加以證明即H陣與編碼碼字的轉(zhuǎn)置乘積為0，可用來作為判斷接收碼組是否錯的依據(jù)。2008.854第五十四頁，共101頁。

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

A1+A2帶入監(jiān)督方程，有：因此，A1+A2亦為許用碼組。2008.855第五十五頁，共101頁。9.4.3生成矩陣

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

編碼

2008.858第五十八頁，共101頁。設(shè)信息組生成矩陣編碼碼組2008.859第五十九頁，共101頁。1）由G和信息組即可產(chǎn)生全部碼字.通過典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。2008.860第六十頁，共101頁。

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

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

(3)確定最小碼距及檢錯能力。例：設(shè)已知2008.861第六十一頁，共101頁。解：求H，需確定P，應(yīng)將已知的那個G轉(zhuǎn)換成典型形式，求出Q，再利用求出G。H=[PIr]=2008.862第六十二頁，共101頁。

(2)

設(shè)C=于是有：監(jiān)督元與信息元的關(guān)系式2008.863第六十三頁，共101頁。用三位二進(jìn)制數(shù)的所有8種狀態(tài)帶入，可得到所有碼字如右表。

序號碼字

00000001001011201011030111014100101510111061100117111000(3)確定最小碼距及檢錯能力所以有：d0=3可用于檢兩位錯或糾一位錯。利用性質(zhì)知：最小碼距d0等于非零碼字的最小重量即d0=wmin2008.864第六十四頁，共101頁。9.4.4校正子S發(fā)送端經(jīng)過編碼后給出：接收端收到的碼組為：兩者的差記為：表示第i位無錯表示第i位有錯E稱為錯誤圖樣。共有2n個錯誤圖樣。當(dāng)E為全零錯誤圖樣時，R=C沒有傳輸錯誤;2008.865第六十五頁，共101頁?？衫肊檢出或糾正錯誤；傳輸中的錯誤超出了可糾錯的范圍。但可能有兩種情況：(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)。2008.866第六十六頁，共101頁。構(gòu)造標(biāo)準(zhǔn)陣列的一般方法如下：1）用概率譯碼確定各伴隨式S對應(yīng)的差錯圖案E，共對；2）表格為列，行，先確定第一行和第一列，第一行為個碼字，第一列為；3）各列對應(yīng)的元素為第一列的和該列的之和；陪集首

譯碼時，計算伴隨式S，查表獲得錯誤圖樣E，最后恢復(fù)出發(fā)送碼字C＝E＋R。2008.867第六十七頁，共101頁。例：已知監(jiān)督矩陣：若接收為：R=[0000011]，試確定是否錯誤，若接收錯誤，試進(jìn)行糾錯。2008.868第六十八頁，共101頁。R=[0000011]，解：計算校正子2008.869第六十九頁，共101頁。000001010100011101110111誤碼位置無錯

C0C1C2C3C4C5C6S1S2S3錯誤圖樣：

E=[0001000]對照校正子與誤碼位置，確定錯誤圖樣：2008.870第七十頁，共101頁。于是：R`=R+E=[0000011]+[0001000]由于，當(dāng)只發(fā)生一位錯碼時，矩陣E中只有一個非零元素，與H的轉(zhuǎn)置相乘的結(jié)果是選出其中的一列，即校正子與H矩陣的哪一列相同，則該列即為碼元發(fā)生錯誤的位置。

=[0001011]2008.871第七十一頁，共101頁。(n，k)線性分組碼編、譯碼過程小結(jié)：

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

求出所有碼字，且為系統(tǒng)碼。H0=[PIr]G0=[IkQ]求出典型生成矩陣；2008.872第七十二頁，共101頁。譯碼過程：1）由收到的碼組R計算校正子S；2）由S判決是否有錯并通過找出錯誤圖樣；3）按照R+E=C計算并還原C；4）將碼組C還原成原信息組M。2008.873第七十三頁，共101頁。9.4.5漢明碼漢明碼是用于糾一位錯誤的線性分組碼。特點：最小碼距：

糾錯能力：編碼效率：2008.874第七十四頁，共101頁。例n=15的漢明碼，其監(jiān)督位為多少？編碼效率為多少？2008.875第七十五頁，共101頁。解：于是其信息位有15-4=11位此漢明碼為（15，11）碼編碼效率：其監(jiān)督位有15-11=4位2008.876第七十六頁，共101頁。

漢明碼是線性分組碼，因此其監(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)造2008.877第七十七頁，共101頁。得到的漢明碼如下所示：信息位監(jiān)督位信息位監(jiān)督位a6a5a4a300000001001000110100010101100111a2a1a0000011101110110101011000a6a5a4a310001001101010101100110111101111a2a1a01111000100010010101001112008.878第七十八頁，共101頁。（7，4）漢明碼編碼器a6a5a4a3信息組a0a1a2a3a4碼字++a5a6+2008.879第七十九頁，共101頁。完備碼

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

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

因此，漢明碼也是糾一位錯的線性分組碼中，編碼效率最高的。2008.880第八十頁，共101頁。

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

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

該式亦稱為漢明界，它給出已知k和t時，所需要的監(jiān)督位數(shù)。2008.881第八十一頁，共101頁。

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

通常選擇碼重最小的矢量優(yōu)先。例試構(gòu)造一個k=5的可糾一個錯的線性分組碼1/計算最短的碼長；2/構(gòu)造H；3/求生成矩陣G；4/求信息組為(10101)的編碼碼字C。2008.882第八十二頁，共101頁。解：1/因為t等于1,且要求k=5,可用試探法確定n設(shè)：n-k=3，則不滿足糾錯要求；

設(shè)：n-k=4，則滿足糾錯要求；于是取n=9，此時r=n-k=4，(9,5)線性分組碼2008.883第八十三頁，共101頁。2/r=4，四位碼共有種狀態(tài)，除全零外都可用于構(gòu)造H矩陣。

為了構(gòu)造典型矩陣，選1000，0100，0010，0001四碼組，然后從其余的11個碼組中，再選出5個，通常按照碼重從小到大選擇。PIr實際只需9個2008.884第八十四頁，共101頁。4/M=[1010

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

Ik于是有：2008.885第八十五頁，共101頁。9.5循環(huán)碼9.5.1循環(huán)碼原理

循環(huán)碼是線性分組碼的一個重要子類，也是目前研究最成熟的一類碼。它不僅有封閉性，且還有循環(huán)性。(n，k)碼組則將所有碼元向左循環(huán)一位，得到的：也是許用碼組是許用碼組。即2008.886第八十六頁，共101頁。

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

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

同一循環(huán)圈內(nèi)，碼字的重量相同2008.887第八十七頁，共101頁。序號碼字

0000000100100120100103011011410010051