第七章 線性分組碼

第七章線性分組碼1第1頁，共61頁，2023年，2月20日，星期三內(nèi)容提要

目前，幾乎所有得到實際應(yīng)用的糾錯碼都是線性的。本章首先介紹有關(guān)糾錯碼的基本概念，然后重點論述線性分組碼的定義及其編譯碼理論。在此基礎(chǔ)上，介紹了一種典型的線性分組碼：漢明碼。掌握內(nèi)容：線性分組碼的概念，生成矩陣，校驗矩陣，最小距離，伴隨式，標(biāo)準(zhǔn)陣列等。2第2頁，共61頁，2023年，2月20日，星期三§7.1糾錯編碼的基本概念一．信道糾錯編碼

近年來，隨著計算機、衛(wèi)星通信及高速數(shù)據(jù)網(wǎng)的飛速發(fā)展，數(shù)據(jù)的交換、處理和存儲技術(shù)得到了廣泛的應(yīng)用，人們對數(shù)據(jù)傳輸和存儲系統(tǒng)的可靠性提出了越來越高的要求。因此，如何控制差錯、提高數(shù)據(jù)傳輸和存儲的可靠性，成為現(xiàn)代數(shù)字通信系統(tǒng)設(shè)計工作者面臨的重要課題。香農(nóng)第二定理指出，當(dāng)信息傳輸速率低于信道容量時，通過某種編譯碼方法，就能使錯誤概率為任意小。目前已有了許多有效的編譯碼方法，并形成了一門新的技術(shù)——糾錯編碼技術(shù)。這里所講的糾錯編碼即信道編碼，與信源編碼一樣都是一種編碼，但兩者的作用是完全不同的。信源編碼的目的是壓縮冗余度，提高信息的傳輸速率。信道編碼的目的是提高信息傳輸時的抗干擾能力以增加信息傳輸?shù)目煽啃浴?第3頁，共61頁，2023年，2月20日，星期三二．差錯控制系統(tǒng)模型及分類

1．差錯控制系統(tǒng)模型模型突出了以控制差錯為目的的糾錯碼編、譯碼器，因此也稱為差錯控制系統(tǒng)。2．差錯控制系統(tǒng)的分類按其糾錯能力的不同可分為兩種：檢錯碼和糾錯碼。

⑴檢錯碼：能發(fā)現(xiàn)錯誤但不能糾正錯誤的碼；⑵糾錯碼：不僅能發(fā)現(xiàn)錯誤而且還能糾正錯誤的碼。

4第4頁，共61頁，2023年，2月20日，星期三按差錯控制系統(tǒng)類型，可分為前向糾錯、重傳反饋和混合糾錯等三種方式。

⑴前向糾錯(FEC)方式：FEC(ForwardErrorControl)方式是發(fā)端發(fā)送有糾錯能力的碼（糾錯碼），接收端收到這些碼后，通過糾錯譯碼器自動地糾正傳輸中的錯誤。

優(yōu)點：是不需要反饋信道；能進行一個用戶對多個用戶的同時通信，特別適合于移動通信；譯碼實時性較好，控制電路也比較簡單。缺點：是譯碼設(shè)備較復(fù)雜；編碼效率較低。⑵重傳反饋(ARQ)方式:ARQ(AutomaticRepeatRequest)方式是：發(fā)端發(fā)出能夠發(fā)現(xiàn)錯誤的碼（檢錯碼），收端譯碼器收到后，判斷在傳輸中有無錯誤產(chǎn)生，并通過反饋信道把撿測結(jié)果告訴發(fā)端。發(fā)端把收端認(rèn)為有錯的消息再次傳送，直到收端認(rèn)為正確接收為止。5第5頁，共61頁，2023年，2月20日，星期三優(yōu)點：譯碼設(shè)備簡單，在多余度一定的情況下，碼的檢錯能力比糾錯能力要高得多，因而整個系統(tǒng)能獲得極低的誤碼率。缺點：應(yīng)用ARQ方式必須有一條從收端至發(fā)端的反饋信道。并要求信源產(chǎn)生信息的速率可以進行控制，收、發(fā)兩端必須互相配合，其控制電路比較復(fù)雜，傳輸信息的連貫性和實時性也較差。⑶混合糾錯(HEC)方式：

HEC(HybridErrorControl)方式是上述兩種方式的結(jié)合。發(fā)端發(fā)送的碼既能檢錯、又有一定的糾錯能力。收端譯碼時若發(fā)現(xiàn)錯誤個數(shù)在碼的糾錯能力以內(nèi)，則自動進行糾錯；若錯誤個數(shù)超過了碼的糾錯能力，但能檢測出來，則通過反饋信道告知發(fā)方重發(fā)。這種方式在一定程度上避免了FEC方式譯碼設(shè)備復(fù)雜和ARQ方式信息連貫性差的缺點。

6第6頁，共61頁，2023年，2月20日，星期三

在設(shè)計差錯控制系統(tǒng)時，選擇何種實現(xiàn)方式，應(yīng)綜合考慮各方面的因素。主要有：⑴滿足用戶對誤碼率的要求；⑵有盡可能高的信息傳輸速率；⑶有盡可能簡單的編譯碼算法且易于實現(xiàn)；(4)可接受的成本。三．糾錯碼的分類

常用的糾錯碼按其碼字結(jié)構(gòu)形式和對信息序列處理方式的不同可分成兩大類：分組碼和卷積碼。

7第7頁，共61頁，2023年，2月20日，星期三分組碼：把信息序列以每k個碼元分組，編碼器將每個信息組按一定規(guī)律產(chǎn)生r個多余的碼元（稱為校驗元），形成一個長為n=k+r的碼字。對于k個碼元分組，共有2k個不同的信息組，編碼器輸出長n的2k個碼字，這2k個長為n的碼字構(gòu)成的集合稱為一個（n，k）分組碼。n：碼長；k：信息位的數(shù)目；R=k/n：分組碼碼率。

卷積碼：把信息序列以每k個分組，通過編碼器輸出長為n（nk）的一個子碼。但是該子碼的n－k個校驗元不僅與本子碼的信息元有關(guān)，而且也與其前m個子碼的信息元有關(guān)。8第8頁，共61頁，2023年，2月20日，星期三四．差錯類型

討論碼字序列通過離散信道時發(fā)生的情況，信道分為無記憶信道和有記憶信道。在無記憶信道中，噪聲對傳輸碼元的影響是相互獨立的，即每一個差錯的出現(xiàn)與其前后是否有錯無關(guān)，如圖所示。在無記憶信道中，錯誤是隨機產(chǎn)生的，因此被稱作隨機錯誤，無記憶信道也被稱為隨機信道（randomchannel）。

9第9頁，共61頁，2023年，2月20日，星期三有記憶信道中，各種干擾所造成的錯誤往往不是單個地，而是成群、成串地出現(xiàn)，表現(xiàn)出錯誤之間有相關(guān)性，稱為突發(fā)錯誤。下圖就是這種信道的一個模型。

就實際信道而言，由于其干擾的復(fù)雜性，往往是兩種錯誤并存。隨機錯誤與突發(fā)錯誤并存的信道，稱為組合信道或復(fù)合信道。

10第10頁，共61頁，2023年，2月20日，星期三§7.2分組碼及檢、糾錯能力的獲得

一．分組碼定義

設(shè)消息或數(shù)據(jù)以二進制形式表示，并以F2={0,1}表示這個二元集。消息集：

序列個數(shù)：2k

設(shè)長為n的二元碼元序列集為：

序列個數(shù)：2n≥2k

設(shè)消息集是長為k的二元消息序列集，表示如下：11第11頁，共61頁，2023年，2月20日，星期三1．分組編碼：在長為n的二元序列集中選出與消息序列數(shù)2k相同數(shù)目的碼元序列，并使兩者一一對應(yīng)。

幾個概念：碼字：對應(yīng)于消息的長n的2k個碼元序列，用表示。選出的2k個碼元序列稱為許用碼組，另外的2n-2k個為禁用碼組。

碼：所有碼字的集合，用C表示。

字：所有長為n的二元序列。

消息：長為k的二元碼元序列，用表示。

12第12頁，共61頁，2023年，2月20日，星期三2．消息與碼字的映射關(guān)系（函數(shù)關(guān)系）

線性分組碼：與呈線性關(guān)系（fi為線性函數(shù)）

非線性分組碼：與呈線性關(guān)系（fi為線性函數(shù)）

對于消息為k位，碼長為n的線性分組碼稱（n，k）線性分組碼。

13第13頁，共61頁，2023年，2月20日，星期三【例】一個原始數(shù)字消息u0

編碼規(guī)則：

k=1，故為（n，1）碼，稱（n，1）重復(fù)碼。碼率：R=1/n

【例】編碼規(guī)則

構(gòu)成一個（n，n-1）線性分組碼：R=(n-1)/n

（加法為模2加）

14第14頁，共61頁，2023年，2月20日，星期三由最后一個方程：

（奇）偶校驗碼：碼字中1的個數(shù)為偶數(shù)。

在接收到一個字中1的個數(shù)不是偶數(shù)時，就可以確定接收的不是碼字。這種碼能檢出奇數(shù)個錯誤，但不能發(fā)現(xiàn)偶數(shù)個錯誤。比較上面兩例編碼方案：①重復(fù)碼：R=1/n，編碼效率最低，檢糾錯能力最高。②奇偶校驗碼：R=(n-1)/n，編碼效率最高，檢糾錯能力最低。（兩個極端）

3．糾錯編碼理論的中心任務(wù)：在重復(fù)碼和奇偶校驗碼之間尋找一些性能良好的碼，使編碼效率和檢、糾錯能力得到統(tǒng)一。

15第15頁，共61頁，2023年，2月20日，星期三二．分組碼檢、糾錯能力的獲得【例】（2，1）重復(fù)碼（2，1）重復(fù)碼可以檢出一個錯誤，但錯誤不能糾正。

16第16頁，共61頁，2023年，2月20日，星期三（3，1）重復(fù)碼

（3，1）重復(fù)碼可以檢出最多不超過兩個錯誤，能糾正一個錯誤，但不能檢出3個錯誤。

17第17頁，共61頁，2023年，2月20日，星期三三．錯誤圖樣對應(yīng)著n為碼字，長為n的二元序列

當(dāng)ei=1時，表明碼字中第i位ci發(fā)生錯誤；當(dāng)ei=0時，表明碼字中第i位ci沒有錯誤。

稱為錯誤圖樣。

中“1”的個數(shù)表示產(chǎn)生錯誤的個數(shù)，稱錯誤圖樣的錯誤重數(shù)（t）。

設(shè)為碼字在傳輸過程中發(fā)生錯誤而得到的接收字，則

18第18頁，共61頁，2023年，2月20日，星期三【例】（2，1）重復(fù)碼

（3，1）重復(fù)碼19第19頁，共61頁，2023年，2月20日，星期三§7.3漢明距離和分組碼的檢、糾錯能力

一．漢明距離1．定義：設(shè)是集合Vn（F2）（n維向量空間）中的任意兩個字，令

ai，bi取自G(F2)(0，1)

規(guī)定表示字的各對應(yīng)碼元之間不相同的個數(shù)，則

稱為之間的漢明距離，簡稱距離。

20第20頁，共61頁，2023年，2月20日，星期三例如：

說明：

①收到接收字后，通過計算與各碼字之間的漢明距離，如與某一碼字的漢明距離最小，則與碼字最像，譯碼器將譯成。②極大似然譯碼基礎(chǔ)：收到的字是從一個碼字經(jīng)錯傳盡可能少的位而來的可能性較從一個碼字經(jīng)錯傳較多的位而來的可能性要大。故通過判斷漢明距離來譯碼，符合極大似然譯碼規(guī)則。如：pe＝10-5，則錯一位的概率：pe＝10-5，錯兩位的概率：pe＝10-1021第21頁，共61頁，2023年，2月20日，星期三【例】有碼字

如接收字：

判斷該接收字最有可能的碼字。

2．漢明距離的性質(zhì)①自反性：

②對稱性：

③三角不等式：

22第22頁，共61頁，2023年，2月20日，星期三二．分組碼的檢、糾錯能力與最小漢明距離之間的關(guān)系1．碼的最小距離碼C中不同碼字之間距離的最小值稱碼C的最小距離。

dmin是衡量碼的檢、糾錯能力的一個重要的參數(shù)。2．碼的檢、糾錯能力與dmin的關(guān)系①若dmin≥t+1，則碼C可以檢出所有不多于t重的錯誤；

23第23頁，共61頁，2023年，2月20日，星期三②若dmin≥2t+1，則碼C可以糾正所有不多于t重的錯誤；

③若dmin≥2t1

+t2+1，則碼C可以糾正所有不多于t1重的錯誤，并能檢出所有的從（t1+1）到（t1+t2）重的錯誤。

24第24頁，共61頁，2023年，2月20日，星期三§7.4線性分組碼及其矩陣描述

一．基本概念1．線性空間定義：如果域F上的n重元素集合V滿足下述條件時，

①V關(guān)于加法構(gòu)成阿貝爾群；

②對V中任何元素和F中的任何元素a，，稱V中元素為矢量（向量），F(xiàn)中元素a稱純量（標(biāo)量），稱乘a運算為數(shù)乘。

③分配律成立：④若

有

則稱V是域F上的一個n維線性空間（矢量空間），表示為：Vn（F）

25第25頁，共61頁，2023年，2月20日，星期三2．子空間

線性空間Vn(F)中矢量的所有線性組合所構(gòu)成的集合S是Vn(F)的子空間。

3．線性相關(guān)和線性無關(guān)設(shè)是線性空間Vn(F)中的一組非全零矢量，當(dāng)且僅當(dāng)存在有一組不全為零的純量，使

成立時，稱這組矢量線性相關(guān)，否則，稱這組矢量線性無關(guān)（線性獨立）。

即：若

線性無關(guān)，若等式成立，必有

26第26頁，共61頁，2023年，2月20日，星期三如：（1）

則

故線性無關(guān)。

（2）

故線性無關(guān)。

則

線性相關(guān)的充要條件：在線性空間中，對于矢量存在著一個矢量，它可以表示為其余矢量的線性組合。27第27頁，共61頁，2023年，2月20日，星期三4．矢量空間（線性空間）的基底如果存在一組線性無關(guān)的矢量，這些矢量的線性組合的集合可以構(gòu)成一個矢量空間，則稱這組矢量為這個矢量空間的基底。

n維矢量空間包含n個基底，也可以說，n個基底“張成”n維矢量空間。如果是n維矢量空間Vn(F)中k個線性無關(guān)的矢量，則這些矢量線性組合的集合可構(gòu)成Vn(F)的一個子空間，這k個矢量為子空間的基底。

結(jié)論：（n，k）線性分組碼可由k個線性獨立的碼字組成的基底張成。

碼矢量：由（n，k）線性分組碼的每個碼字構(gòu)成的矢量（碼字）字矢量：n維線性空間任一個字構(gòu)成的矢量。28第28頁，共61頁，2023年，2月20日，星期三二．線性分組碼的矩陣描述1．定義：（線性分組碼的模型）設(shè)Vn(F2)是定義在F2上的一個n維的矢量空間，而C是它的一個k維的子空間，則稱C是碼長為n，消息位為k的線性分組碼或（n，k）線性分組碼?！纠浚?，3）分組碼C

編碼規(guī)則：

用矩陣表示：

組成矩陣的三個6維的行矢量是線性無關(guān)的，它構(gòu)成了V6(F2)上的一個3維子空間，故C是（6，3）線性分組碼。29第29頁，共61頁，2023年，2月20日，星期三2．線性分組碼的矩陣描述：設(shè)

是（n，k）線性分組碼中k個線性無關(guān)的非零碼字，

則（n，k）線性分組碼2k個碼字中的任一碼字可表示為用矩陣表示：：長為k的序列，構(gòu)成2k個不同的消息。

生成矩陣

30第30頁，共61頁，2023年，2月20日，星期三【例】（7，3）線性分組碼，k=3，2k=8（消息）則：

如：

31第31頁，共61頁，2023年，2月20日，星期三3．系統(tǒng)碼：信息位以不變的形式在碼組中出現(xiàn)的碼稱為系統(tǒng)碼（出現(xiàn)的位置一般在前面）。如：前例（7，3）線性分組碼一般性結(jié)論：（1）每一個線性分組碼都有一個與之等價的系統(tǒng)碼存在；（2）（n，k）線性分組碼系統(tǒng)碼的生成矩陣是一個k×k的單位陣[Ik]和一個k×(n-k)矩陣[Pk×n-k]組合而成的。（3）與非系統(tǒng)碼相比，系統(tǒng)碼編碼過程及所需設(shè)備可以簡化。32第32頁，共61頁，2023年，2月20日，星期三4．生成矩陣的性質(zhì)（1）如果G是一個生成矩陣，那么與G行等價的任一矩陣也是生成矩陣。

初等行變換：任意兩行交換；將任一行加到另一行；將任一行同乘一個數(shù)。

【例】（6，3）線性分組碼對G作初等行變換：33第33頁，共61頁，2023年，2月20日，星期三（2）每個線性分組碼都有唯一的梯形生成矩陣（3）一個矢量空間的基底不止一個，G不唯一，各個G編出的碼相同，但各消息對應(yīng)的碼字不同。

三．線性分組碼的校驗矩陣1．校驗矩陣【例】（6，3）線性分組碼在碼字中c0、c1、c2是信息位，c3、c4、c5是冗余位（校驗位）

34第34頁，共61頁，2023年，2月20日，星期三由校驗位方程得：用矩陣表示即

（H為n－k行n列的矩陣）

35第35頁，共61頁，2023年，2月20日，星期三【例】（1）（n，1）重復(fù)碼，k＝1

（2）（n，n-1）奇偶校驗碼

36第36頁，共61頁，2023年，2月20日，星期三結(jié)論：一般的（n，k）線性分組碼C總可以從該碼的編碼規(guī)則中選出（n-k）個獨立校驗位方程，如將它們寫成齊次線性方程的形式，則它們可以用矩陣表示為：

簡記為：

（H(n－k)×n為線性分組碼的校驗矩陣）。

說明：（1）矩陣H的n-k個行矢量是線性獨立的，它們組成了Vn（F2）上的一個n-k維的子空間。（2）

H的行空間與G的行空間是相互正交的（對偶的）。

37第37頁，共61頁，2023年，2月20日，星期三2．對偶碼生成矩陣G的k行矢量組成Vn(F2)的k維子空間（碼字空間C）；校驗矩陣H的n-k個行矢量組成Vn(F2)的n-k維的子空間(C的對偶子空間C⊥)。

對偶碼定義：C⊥是Vn（F2）的一個子空間，它的維數(shù)維n-k，因此可以把C⊥看作是一個二元（n，n-k）線性分組碼，并把它稱為C的對偶碼。

結(jié)論：設(shè)C是（n，k）線性分組碼，其生成矩陣維G，那么碼C的對偶碼C⊥的生成矩陣H就是碼C的校驗矩陣。3．線性分組碼的譯碼問題由于生成矩陣和校驗矩陣的行空間是對偶的，因此我們可以利用這種對偶特性來判斷接收到的任一矢量是否為碼矢量，這在原則上提供了一種解決線性分組碼的譯碼問題的途徑。

的充要條件是：

即：

38第38頁，共61頁，2023年，2月20日，星期三4．生成矩陣G與校驗矩陣H的梯形矩陣的關(guān)系（1）每個線性分組碼的生成矩陣存在唯一的k×n的梯形矩陣；（2）每個線性分組碼的校驗矩陣存在唯一的(n-k)×n的梯形矩陣；（3）如G有[Ik

P]的形式，則H有[PT

In-k]的形式（條件：在F2中）。

【例】

39第39頁，共61頁，2023年，2月20日，星期三§7.5線性分組碼的檢、糾錯能力

一．碼字重量1．定義

設(shè)，令為碼字中不為零碼元的個數(shù)，即

稱為碼字的漢明重量，簡稱重量。

2．最小重量：碼C中非零碼字重量的最小值

40第40頁，共61頁，2023年，2月20日，星期三3．任一碼字的重量都可以看作是該碼字與0碼字之間的漢明距離

4．定理：任一線性分組碼的最小距離等于它的最小重量。

證明：

由于C是線性碼，故，即線性分組碼中任意兩個碼矢量間的距離等于另一個碼矢的重量，即

故

41第41頁，共61頁，2023年，2月20日，星期三二．線性分組碼的檢、糾錯能力與H矩陣的關(guān)系定理：設(shè)C是線性分組碼，H是它的校驗矩陣，那么碼C的最小重量就等于H中線性相關(guān)的最小列數(shù)。因此，如果H中的2t個和小于2t個列的任一子集都線性無關(guān)，而H中有2t+1個列線性相關(guān)，那么碼C就是糾正t個錯誤的糾錯碼，或能檢出2t個錯誤的檢錯碼?！纠浚?，4）線性分組碼

線性相關(guān)的最小列數(shù)為3

故：wmin(C)=3

推論：如果H的任意小于等于t個列的線性組合都不相同，那么wmin(C)≥2t+1，即C是能糾正重數(shù)小于等于t的糾錯碼。42第42頁，共61頁，2023年，2月20日，星期三§7.6群及其性質(zhì)

一．群的概念定義：設(shè)G是非空集合，在G中規(guī)定一種運算“*”，，即運算*在G中是封閉的。

同時要求：（2）

，對一切的

，使a*e=a，e為恒元；

（1）

，有

結(jié)合律；

（3）

，有a*a-1=e，存在逆元a-1。

，若以上條件均滿足，稱G對于“*”運算是一個群。交換群（阿貝爾群）：a*b=b*a(滿足交換律)加法群：運算“*”為加法運算。e：零元素乘法群：運算“*”為乘法運算。e：單位元有限群：G中只含有有限個元，元的個數(shù)稱群的階。

43第43頁，共61頁，2023年，2月20日，星期三二．子群和陪集展開1．子群：設(shè)G是一個群，而G0是G的一個非空子集，若G0在G規(guī)定的運算下滿足群的條件，則G0是G的子群。

2．群按子群展開（陪集展開）設(shè)加群G的子群

展開步驟：

（1）把H的元依次排在第一行；（2）取不屬于H的G中的任一元，記為g1，將它與H中的元依次相加，結(jié)果記為，并依次排在第二行；

（3）再取不屬于H又不屬于g1+H的G中的任一元g2，將它與H中的元依次相加，結(jié)果記為，并依次排在第三行；

（4）按步驟繼續(xù)下去，直到排完G中所有的元。

44第44頁，共61頁，2023年，2月20日，星期三Hh1=eh2...hrg1+Hg1g1+h2...g1+hrg2+Hg2g2+h2...g2+hr...gn+Hgngn+h2...gn+hr把叫做H的一個陪集。而g稱為該陪集的一個代表元或陪集首（e，g1，g2，...，gn）。45第45頁，共61頁，2023年，2月20日，星期三【例】V4（F2）的模2加群：子群H={0000，0101，1110，1011}，陪集展開。H00000101111010110110＋H01100011100011011111＋H11111010000101000010＋H0010011111001001結(jié)論：（1）G的每一個僅在子群H的一個陪集中（2）設(shè)G是個交換群，H是它的一個子群，那么G可以唯一地表示為H的一些兩兩沒有公共元的陪集的并。

46第46頁，共61頁，2023年，2月20日，星期三§7.7線性碼的伴隨式譯碼和標(biāo)準(zhǔn)陣列一．群碼1．定義：所有構(gòu)成群的碼稱為群碼。

2．定理：二元分組碼對于碼字的模2加法成群的充要條件：碼是線性的。

二．伴隨式1．伴隨式（校驗子）對任一錯誤圖樣，接受字可表示為：

由于

是碼字，

，故

稱為接收字的伴隨式或校驗子，它是一個n-k維的行矢量。47第47頁，共61頁，2023年，2月20日，星期三2．定理：任意兩個長n的二元矢量，如果對群碼C的校驗矩陣有相同的伴隨式，即，那么屬同一個陪集（有相同的陪集首）。三．標(biāo)準(zhǔn)陣列：在全部長為n的二元序列按線性碼C的陪集展開中，陪集首可以用該陪集中的任意序列擔(dān)任，而不會改變此陪集的元，只是他們的排列次序有所變動。

標(biāo)準(zhǔn)陣列：全體長n的二元序列按線性碼C的以陪集中最小重量的字作為陪集首的陪集展開就稱為C的標(biāo)準(zhǔn)陣列。

48第48頁，共61頁，2023年，2月20日，星期三【例】（4，2）線性碼C={0000，0101，1110，1011}，其標(biāo)準(zhǔn)陣列為

碼字伴隨式0000010111101011100010011111001001010100000110101111111000110101100011其校驗矩陣為

，計算其伴隨式，如表。

說明：對于（4，2）線性碼，碼字的最小重量為2，可以糾正一個錯誤，實際上按標(biāo)準(zhǔn)陣列展開的陪集為碼字錯誤圖樣為陪集首的接收字，由于可以糾正一個錯誤，因此譯碼時對單個錯誤可以正確譯碼。49第49頁，共61頁，2023年，2月20日，星期三四．伴隨式譯碼

1．標(biāo)準(zhǔn)陣列法：

按標(biāo)準(zhǔn)陣列的陪集展開實際上就構(gòu)成了線性碼的譯碼表，因此完全可以通過標(biāo)準(zhǔn)陣列來譯碼。其中，陪集首就是線性碼可以糾錯的錯誤圖樣。2．伴隨式譯碼（1）原理：對于碼C的同一陪集，有相同的伴隨式和陪集首(錯誤圖樣），因此，只要知道伴隨式與陪集首的對應(yīng)關(guān)系，通過計算接收字的伴隨式，就可以知道錯誤圖樣，從而進行譯碼。

（2）方法：計算接收字的伴隨式：；根據(jù)算得得伴隨式找到對應(yīng)的陪集首（錯誤圖樣）；根據(jù)錯誤圖樣譯碼并輸出碼字：

（3）優(yōu)點：不用記住整張譯碼表（標(biāo)準(zhǔn)陣列），只需記住伴隨式與陪集首相對應(yīng)的表。

50第50頁，共61頁，2023年，2月20日，星期三【例】（7，3）線性分組碼

能檢出3重錯誤，糾正1重錯誤。

51第51頁，共61頁，2023年，2月20日，星期三如：（一個錯）如兩個錯：

，但無伴隨式與之對應(yīng)，不能糾正。

52第52頁，共61頁，2023年，2月20日，星期三§7.7漢明碼

一．基本概念漢明碼：一類能糾單個錯誤的糾錯碼。

二．糾單個錯誤的線性分組碼【例】（7，4）線性碼

53第53頁，共61頁，2023年，2月20日，星期三（1）H中列為非全零元素；

（2）H中任意兩列都不相同，但存在相加等于0的三個列的子集。

H中線性相關(guān)的最小列數(shù)為3，故，該碼是糾單個錯誤的碼。定理：C是一個線性分組碼，H是校驗矩陣，C是可以糾單個錯誤的糾錯碼的充要條件：（1）H中沒有元素全為0的列矢量；（2）H中任