第七章 線性分組碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一．分組碼定義

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

序列個(gè)數(shù)：2k

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

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

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

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

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

字：所有長(zhǎng)為n的二元序列。

消息：長(zhǎng)為k的二元碼元序列，用表示。

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

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

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

對(duì)于消息為k位，碼長(zhǎng)為n的線性分組碼稱（n，k）線性分組碼。

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

編碼規(guī)則：

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

【例】編碼規(guī)則

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

（加法為模2加）

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

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

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

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

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

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

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

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

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

稱為錯(cuò)誤圖樣。

中“1”的個(gè)數(shù)表示產(chǎn)生錯(cuò)誤的個(gè)數(shù)，稱錯(cuò)誤圖樣的錯(cuò)誤重?cái)?shù)（t）。

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

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

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

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

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

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

稱為之間的漢明距離，簡(jiǎn)稱距離。

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

說明：

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

如接收字：

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

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

②對(duì)稱性：

③三角不等式：

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

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

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

③若dmin≥2t1

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

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

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

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

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

③分配律成立：④若

有

則稱V是域F上的一個(gè)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)存在有一組不全為零的純量，使

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

即：若

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

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

則

故線性無關(guān)。

（2）

故線性無關(guān)。

則

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

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

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

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

編碼規(guī)則：

用矩陣表示：

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

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

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

生成矩陣

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）每一個(gè)線性分組碼都有一個(gè)與之等價(jià)的系統(tǒng)碼存在；（2）（n，k）線性分組碼系統(tǒng)碼的生成矩陣是一個(gè)k×k的單位陣[Ik]和一個(gè)k×(n-k)矩陣[Pk×n-k]組合而成的。（3）與非系統(tǒng)碼相比，系統(tǒng)碼編碼過程及所需設(shè)備可以簡(jiǎn)化。32第32頁，共61頁，2023年，2月20日，星期三4．生成矩陣的性質(zhì)（1）如果G是一個(gè)生成矩陣，那么與G行等價(jià)的任一矩陣也是生成矩陣。

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

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

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

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

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

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

（2）（n，n-1）奇偶校驗(yàn)碼

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

簡(jiǎn)記為：

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

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

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

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

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

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

的充要條件是：

即：

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

P]的形式，則H有[PT

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

【例】

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

一．碼字重量1．定義

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

稱為碼字的漢明重量，簡(jiǎn)稱重量。

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

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

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

證明：

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

故

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

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

故：wmin(C)=3

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

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

同時(shí)要求：（2）

，對(duì)一切的

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

（1）

，有

結(jié)合律；

（3）

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

，若以上條件均滿足，稱G對(duì)于“*”運(yùn)算是一個(gè)群。交換群（阿貝爾群）：a*b=b*a(滿足交換律)加法群：運(yùn)算“*”為加法運(yùn)算。e：零元素乘法群：運(yùn)算“*”為乘法運(yùn)算。e：?jiǎn)挝辉邢奕海篏中只含有有限個(gè)元，元的個(gè)數(shù)稱群的階。

43第43頁，共61頁，2023年，2月20日，星期三二．子群和陪集展開1．子群：設(shè)G是一個(gè)群，而G0是G的一個(gè)非空子集，若G0在G規(guī)定的運(yùn)算下滿足群的條件，則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è)陪集。而g稱為該陪集的一個(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的每一個(gè)僅在子群H的一個(gè)陪集中（2）設(shè)G是個(gè)交換群，H是它的一個(gè)子群，那么G可以唯一地表示為H的一些兩兩沒有公共元的陪集的并。

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

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

二．伴隨式1．伴隨式（校驗(yàn)子）對(duì)任一錯(cuò)誤圖樣，接受字可表示為：

由于

是碼字，

，故

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

標(biāo)準(zhǔn)陣列：全體長(zhǎng)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其校驗(yàn)矩陣為

，計(jì)算其伴隨式，如表。

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

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

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

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

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

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

能檢出3重錯(cuò)誤，糾正1重錯(cuò)誤。

51第51頁，共61頁，2023年，2月20日，星期三如：（一個(gè)錯(cuò)）如兩個(gè)錯(cuò)：

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

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

一．基本概念漢明碼：一類能糾單個(gè)錯(cuò)誤的糾錯(cuò)碼。

二．糾單個(gè)錯(cuò)誤的線性分組碼【例】（7，4）線性碼

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

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

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