第二十四講第六節(jié)線性分組碼

第二十四講第六節(jié)線性分組碼1第1頁(yè)，共47頁(yè)，2023年，2月20日，星期一設(shè)傳輸一比特字符x=0或1

若傳輸過(guò)程中出現(xiàn)差錯(cuò),不能被發(fā)現(xiàn)引例2第2頁(yè)，共47頁(yè)，2023年，2月20日，星期一引例0后附加字符0，1后附加1；即只有00和11被接受，且00視為0，11視為1；故：如果有一位錯(cuò)誤發(fā)生，可以被檢出！3第3頁(yè)，共47頁(yè)，2023年，2月20日，星期一如果通信過(guò)程中發(fā)現(xiàn)差錯(cuò)，可以通過(guò)要求對(duì)方重新發(fā)送來(lái)獲得正確的信息，即所謂的“數(shù)量換質(zhì)量”.但是這在實(shí)時(shí)信息采集系統(tǒng)中可能是有困難的，因?yàn)樾畔⒃匆呀?jīng)發(fā)生變化；即使是在發(fā)方保留原信息樣本的情況下，也只有在差錯(cuò)率很低的條件下是比較可行的.因?yàn)槿绻ㄐ艞l件比較惡劣，差錯(cuò)出現(xiàn)頻繁，以至多次重發(fā)仍然得不到一份正確的信息.這時(shí)，僅有“檢錯(cuò)”手段，已無(wú)能為力！引例4第4頁(yè)，共47頁(yè)，2023年，2月20日，星期一引例0后附加字符00，1后附加11；即傳輸000相當(dāng)于傳送單字符0，111相當(dāng)于傳送單字符1；這時(shí)：發(fā)生不超過(guò)兩位的錯(cuò)誤均可被檢出；發(fā)生一位錯(cuò)誤可以被糾正.5第5頁(yè)，共47頁(yè)，2023年，2月20日，星期一引例0后附加字符00，1后附加11；即傳輸000相當(dāng)于傳送單字符0，111相當(dāng)于傳送單字符1；這時(shí)：發(fā)生不超過(guò)兩位的錯(cuò)誤均可被檢出；發(fā)生一位錯(cuò)誤可以被糾正.糾錯(cuò)碼信息位校驗(yàn)位6第6頁(yè)，共47頁(yè)，2023年，2月20日，星期一線性分組碼的基本概念分組碼分組碼是把信源輸出的信息序列，以k個(gè)信息位分為一段，通過(guò)編碼器把這段信息位按一定規(guī)則f產(chǎn)生r個(gè)校驗(yàn)位，輸出長(zhǎng)為n=k+r的一個(gè)碼字，所得碼字的全體.稱之為（n，k）分組碼！

n表示碼長(zhǎng)，k表示信息位個(gè)數(shù).7第7頁(yè)，共47頁(yè)，2023年，2月20日，星期一引例0后附加字符00，1后附加11；即傳輸000相當(dāng)于傳送單字符0，111相當(dāng)于傳送單字符1；這時(shí)：發(fā)生不超過(guò)兩位的錯(cuò)誤均可被檢出；發(fā)生一位錯(cuò)誤可以被糾正.(3,1)分組碼信息位校驗(yàn)位8第8頁(yè)，共47頁(yè)，2023年，2月20日，星期一（n，k）分組碼若校驗(yàn)位與信息位之間的關(guān)系是線性的，即上述編碼規(guī)則是線性的，稱之為（n，k）線性分組碼！

9第9頁(yè)，共47頁(yè)，2023年，2月20日，星期一一、二元域——GF(2)設(shè){0,1}為一個(gè)二元集，在其上定義模2的加法和乘法運(yùn)算加法：乘法：

可見二元集{0,1}對(duì)上述定義的加法及乘法運(yùn)算封閉，并滿足一個(gè)“域”所要求的交換律、結(jié)合律、分配律等運(yùn)算規(guī)則，因此{(lán)0,1}對(duì)所規(guī)定的加法和乘法運(yùn)算構(gòu)成一個(gè)域，稱為二元域，記作GF(2).10第10頁(yè)，共47頁(yè)，2023年，2月20日，星期一注11第11頁(yè)，共47頁(yè)，2023年，2月20日，星期一稱碼為(n,k)碼.二、線性分組碼的定義及表示12第12頁(yè)，共47頁(yè)，2023年，2月20日，星期一若設(shè)碼字，則即校驗(yàn)位是由信息位線性組合得到.13第13頁(yè)，共47頁(yè)，2023年，2月20日，星期一可見，碼字的三個(gè)校驗(yàn)元都由其前兩位線性組合得到，即可由線性方程組求得；信息位k=2碼字?jǐn)?shù)M=414第14頁(yè)，共47頁(yè)，2023年，2月20日，星期一線性編碼15第15頁(yè)，共47頁(yè)，2023年，2月20日，星期一例題1：下面是某個(gè)（n，k）線性二元碼的全部碼字x16=000000x26=100011x36=010101x46=001111x56=110110x66=101100x76=011010x86=111001求n、k的值；n=6;M=2kk=3.解：16第16頁(yè)，共47頁(yè)，2023年，2月20日，星期一例2、（5，2）線性二元碼的全部碼字設(shè)碼字，可得17第17頁(yè)，共47頁(yè)，2023年，2月20日，星期一改寫為用矩陣可表示成：校驗(yàn)矩陣與任一碼字的乘積為0

18第18頁(yè)，共47頁(yè)，2023年，2月20日，星期一線性分組碼的特性

2k個(gè)碼字完全可由其中一組k個(gè)獨(dú)立的碼字組合而成；

生成矩陣從線性分組碼（n，k）中任取

k

個(gè)線性無(wú)關(guān)的碼字，以行的形式寫成矩陣G，則稱為該線性分組碼的生成矩陣.

19第19頁(yè)，共47頁(yè)，2023年，2月20日，星期一例題3：下面是一個(gè)（6，3）線性二元碼的全部碼字構(gòu)造它的一個(gè)生成矩陣.解：由k=3個(gè)線性獨(dú)立的碼字組成：20第20頁(yè)，共47頁(yè)，2023年，2月20日，星期一例題3：下面是一個(gè)（6，3）線性二元碼的全部碼字驗(yàn)證：21第21頁(yè)，共47頁(yè)，2023年，2月20日，星期一說(shuō)明22第22頁(yè)，共47頁(yè)，2023年，2月20日，星期一

一個(gè)線性子空間可以有不同的但相互等價(jià)的基，亦即不同的G可以產(chǎn)生相同的線性碼，所以一個(gè)線性碼的生成矩陣不唯一。23第23頁(yè)，共47頁(yè)，2023年，2月20日，星期一例4矩陣為一個(gè)(7,3)碼.24第24頁(yè)，共47頁(yè)，2023年，2月20日，星期一系統(tǒng)碼

若（n,k）線性分組碼的生成矩陣形如

G=(IkA)其中Ik是k階單位陣，A為階子陣，則稱這類碼為系統(tǒng)碼.特點(diǎn)：校驗(yàn)矩陣為H=(ATI(n-k)).三、系統(tǒng)編碼與校驗(yàn)矩陣25第25頁(yè)，共47頁(yè)，2023年，2月20日，星期一例題3：下面是一個(gè)（6，3）線性二元碼的全部碼字它的一個(gè)生成矩陣請(qǐng)寫出它的校驗(yàn)矩陣H.26第26頁(yè)，共47頁(yè)，2023年，2月20日，星期一27第27頁(yè)，共47頁(yè)，2023年，2月20日，星期一注：系統(tǒng)碼的碼字的前k個(gè)碼元就是它所載荷的數(shù)字消息，故系統(tǒng)碼的前k為稱為信息位，后n-k位稱為校驗(yàn)位.28第28頁(yè)，共47頁(yè)，2023年，2月20日，星期一校驗(yàn)矩陣即結(jié)論：29第29頁(yè)，共47頁(yè)，2023年，2月20日，星期一漢明距離：指（n,k）分組碼中兩個(gè)碼字xn、

yn對(duì)應(yīng)位取值不同的個(gè)數(shù)；記為d（xn，yn）.

例：

30第30頁(yè)，共47頁(yè)，2023年，2月20日，星期一漢明距離：指（n,k）分組碼中兩個(gè)碼字xn、

yn對(duì)應(yīng)位取值不同的個(gè)數(shù)；記為d（xn，

yn）.

例：

31第31頁(yè)，共47頁(yè)，2023年，2月20日，星期一線性分組碼的最小距離：稱（n,k）分組碼中任兩個(gè)碼字漢明距離的最小值，為該分組碼的最小距離d.

（5,2）線性分組碼全部碼字：最小距離d=3.

漢明重量32第32頁(yè)，共47頁(yè)，2023年，2月20日，星期一漢明(Hamming)碼漢明碼是一類能糾正一位差錯(cuò)的線性分組碼，其參數(shù)為：碼長(zhǎng)：信息位長(zhǎng)：

校驗(yàn)位長(zhǎng)：最小碼距：

漢明碼H

矩陣的構(gòu)造方式：按

m

位的

2

進(jìn)制數(shù)的自然順序從左到右排列(不包括全

0

列)，當(dāng)發(fā)生可糾的單個(gè)差錯(cuò)時(shí)，伴隨式為

H

矩陣中對(duì)應(yīng)的列，譯碼比較方便將上述非標(biāo)準(zhǔn)形式的

H

矩陣通過(guò)列初等置換變成標(biāo)準(zhǔn)形式的校驗(yàn)矩陣，糾錯(cuò)能力保持不變例：構(gòu)造一個(gè)的

2

元漢明碼由于故構(gòu)造的漢明碼為線性分組碼漢明碼的編碼效率是很高的，33第33頁(yè)，共47頁(yè)，2023年，2月20日，星期一設(shè)一分組碼具有一致校驗(yàn)矩陣：①求這個(gè)分組碼n=？k=？，共有多少個(gè)碼字？②此分組碼的生成矩陣；③向量101010是否是碼字？習(xí)題課（補(bǔ)充）34第34頁(yè)，共47頁(yè)，2023年，2月20日，星期一解：①設(shè)碼字C=(c5c4c3c2c1c0)，有習(xí)題課故得所以n=6，k=3，為(6,3)分組碼．共有碼字2k=8個(gè)35第35頁(yè)，共47頁(yè)，2023年，2月20日，星期一設(shè)一分組碼具有一致校驗(yàn)矩陣：①求這個(gè)分組碼n=？k=？，共有多少個(gè)碼字？②此分組碼的生成矩陣；③向量101010是否是碼字？習(xí)題課（補(bǔ)充）36第36頁(yè)，共47頁(yè)，2023年，2月20日，星期一習(xí)題課②由上式可得取一組線性無(wú)關(guān)的基礎(chǔ)解系，得到生成矩陣37第37頁(yè)，共47頁(yè)，2023年，2月20日，星期一設(shè)一分組碼具有一致校驗(yàn)矩陣：①求這個(gè)分組碼n=？k=？，共有多少個(gè)碼字？②此分組碼的生成矩陣；③向量101010是否是碼字？習(xí)題課（補(bǔ)充）38第38頁(yè)，共47頁(yè)，2023年，2月20日，星期一習(xí)題課③由可知，向量101010不是碼字．39第39頁(yè)，共47頁(yè)，2023年，2月20日，星期一說(shuō)明40第40頁(yè)，共47頁(yè)，2023年，2月20日，星期一

一個(gè)線性子空間可以有不同的但相互等價(jià)的基，亦即不同的G可以產(chǎn)生相同的線性碼，所以一個(gè)線性碼的生成矩陣不唯一。41第41頁(yè)，共47頁(yè)，2023年，2月20日，星期一例2設(shè)碼的生成矩陣為則共有兩個(gè)碼字，為一個(gè)(5,1)碼.42第42頁(yè)，共47頁(yè)，2023年，2月20日，星期一系統(tǒng)碼消息G1碼字G2碼字000000000000000001111000001101010110101010011011001101011110100101011100110101010011101011110011110110101111100110111000生成矩陣

G

的選擇不是惟一的；如下面的G1

和G2

都可作為同一個(gè)(6,3)碼的生成矩陣，所對(duì)應(yīng)的碼字如右表所示：系統(tǒng)碼的編碼器僅需存儲(chǔ)k

(n

-

k)個(gè)數(shù)字(非系統(tǒng)碼要存儲(chǔ)k

n

個(gè)數(shù)字)，譯碼時(shí)僅需對(duì)前k

個(gè)信息位糾錯(cuò)即可恢復(fù)信息；可見系統(tǒng)碼的編碼和譯碼比較簡(jiǎn)單，而性能與非系統(tǒng)碼一樣，所以系統(tǒng)碼得到了十分廣泛的應(yīng)用雖然二者用了不同形式的生成矩陣，卻都是

(6,

3)

線性分組碼，因此它們的檢錯(cuò)和糾錯(cuò)能力是一樣的，但是

G2

生成的碼，其前

k

位與消息碼完全相同，這種碼稱為系統(tǒng)碼，其生成矩陣和一致校驗(yàn)矩陣分別記為

Gs

,Hs43第43頁(yè)，共47頁(yè)，2023年，2月20日，星期一線性分組碼的生成矩陣

和校驗(yàn)矩陣的關(guān)系由于G

的每一行都是一個(gè)碼字，所以G

的每一行c

i都滿足：

從而有：

在碼字集合不變的前提下，給定任何一個(gè)線性分組碼，通過(guò)其生成矩陣G實(shí)施行初等變換，均可以轉(zhuǎn)換為某個(gè)系統(tǒng)碼當(dāng)且僅當(dāng)線性分組碼一致校驗(yàn)矩陣H中任意

d

-

1

個(gè)列線性無(wú)關(guān)而某d列線性相關(guān)時(shí)，線性分組碼的最小碼距為

dmin

=

d44第44頁(yè)，共47頁(yè)，2023年，2月20日，星期一漢明(Hamming)碼漢明碼是一類能糾正一位差錯(cuò)的線性分組碼，其參數(shù)為：碼長(zhǎng)：信息位長(zhǎng)：

校驗(yàn)位長(zhǎng)：最小碼距：

漢明碼H

矩陣的構(gòu)造方式：按

m

位的

2

進(jìn)制數(shù)的自然順序從左到右排列(不包括全

0

列)，當(dāng)發(fā)生可糾的單個(gè)差錯(cuò)時(shí)，伴隨式為

H

矩陣中對(duì)應(yīng)的列，譯碼比較方便將上述非標(biāo)準(zhǔn)形式的

H

矩陣通過(guò)列初等置換變成標(biāo)準(zhǔn)形式的校驗(yàn)矩陣，糾錯(cuò)能力保持不變例：構(gòu)造一個(gè)的

2

元漢明碼由于故構(gòu)造的漢明碼為線性分組碼漢明碼的編碼效率是很高的，45第45頁(yè)，共47頁(yè)，2023年，2月20日，星期一線性分組碼的描述設(shè)信息分組長(zhǎng)度為

，在每一信息組后加上

4

個(gè)校驗(yàn)碼元，構(gòu)成線性分組碼

設(shè)該碼的碼字為，其中為信息碼元，

為校驗(yàn)碼元，

；信息碼元和校驗(yàn)碼元可按下面方程組計(jì)算：消息碼字消息碼字0