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

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

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

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

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

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

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

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

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

k

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

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

一個線性子空間可以有不同的但相互等價的基，亦即不同的G可以產(chǎn)生相同的線性碼，所以一個線性碼的生成矩陣不唯一。23第23頁，共47頁，2023年，2月20日，星期一例4矩陣為一個(7,3)碼.24第24頁，共47頁，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頁，共47頁，2023年，2月20日，星期一例題3：下面是一個（6，3）線性二元碼的全部碼字它的一個生成矩陣請寫出它的校驗(yàn)矩陣H.26第26頁，共47頁，2023年，2月20日，星期一27第27頁，共47頁，2023年，2月20日，星期一注：系統(tǒng)碼的碼字的前k個碼元就是它所載荷的數(shù)字消息，故系統(tǒng)碼的前k為稱為信息位，后n-k位稱為校驗(yàn)位.28第28頁，共47頁，2023年，2月20日，星期一校驗(yàn)矩陣即結(jié)論：29第29頁，共47頁，2023年，2月20日，星期一漢明距離：指（n,k）分組碼中兩個碼字xn、

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

例：

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

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

yn）.

例：

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

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

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

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

漢明碼H

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

m

位的

2

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

0

列)，當(dāng)發(fā)生可糾的單個差錯時，伴隨式為

H

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

H

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

2

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

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

G

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

和G2

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

(n

-

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

n

個數(shù)字)，譯碼時僅需對前k

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

(6,

3)

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

G2

生成的碼，其前

k

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

Gs

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

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

的每一行都是一個碼字，所以G

的每一行c

i都滿足：

從而有：

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

d

-

1

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

dmin

=

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

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

漢明碼H

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

m

位的

2

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

0

列)，當(dāng)發(fā)生可糾的單個差錯時，伴隨式為

H

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

H

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

2

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

，在每一信息組后加上

4

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

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

為校驗(yàn)碼元，

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