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

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

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

現(xiàn)在是17頁\一共有45頁\編輯于星期四17線性分組碼的特性

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

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

k

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

現(xiàn)在是18頁\一共有45頁\編輯于星期四18例題3：下面是一個（6，3）線性二元碼的全部碼字構(gòu)造它的一個生成矩陣.解：由k=3個線性獨立的碼字組成：現(xiàn)在是19頁\一共有45頁\編輯于星期四19例題3：下面是一個（6，3）線性二元碼的全部碼字驗證：現(xiàn)在是20頁\一共有45頁\編輯于星期四20說明現(xiàn)在是21頁\一共有45頁\編輯于星期四21一個線性子空間可以有不同的但相互等價的基，亦即不同的G可以產(chǎn)生相同的線性碼，所以一個線性碼的生成矩陣不唯一。現(xiàn)在是22頁\一共有45頁\編輯于星期四22例4矩陣為一個(7,3)碼.現(xiàn)在是23頁\一共有45頁\編輯于星期四23系統(tǒng)碼

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

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

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

例：

現(xiàn)在是29頁\一共有45頁\編輯于星期四29漢明距離：指（n,k）分組碼中兩個碼字xn、

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

yn）.

例：

現(xiàn)在是30頁\一共有45頁\編輯于星期四30線性分組碼的最小距離：稱（n,k）分組碼中任兩個碼字漢明距離的最小值，為該分組碼的最小距離d.

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

漢明重量現(xiàn)在是31頁\一共有45頁\編輯于星期四31漢明(Hamming)碼漢明碼是一類能糾正一位差錯的線性分組碼，其參數(shù)為：碼長：信息位長：

校驗位長：最小碼距：

漢明碼H

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

m

位的

2

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

0

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

H

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

H

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

2

元漢明碼由于故構(gòu)造的漢明碼為線性分組碼漢明碼的編碼效率是很高的，現(xiàn)在是32頁\一共有45頁\編輯于星期四32設(shè)一分組碼具有一致校驗矩陣：①求這個分組碼n=？k=？，共有多少個碼字？②此分組碼的生成矩陣；③向量101010是否是碼字？習(xí)題課（補充）現(xiàn)在是33頁\一共有45頁\編輯于星期四33解：①設(shè)碼字C=(c5c4c3c2c1c0)，有習(xí)題課故得所以n=6，k=3，為(6,3)分組碼．共有碼字2k=8個現(xiàn)在是34頁\一共有45頁\編輯于星期四34設(shè)一分組碼具有一致校驗矩陣：①求這個分組碼n=？k=？，共有多少個碼字？②此分組碼的生成矩陣；③向量101010是否是碼字？習(xí)題課（補充）現(xiàn)在是35頁\一共有45頁\編輯于星期四35習(xí)題課②由上式可得取一組線性無關(guān)的基礎(chǔ)解系，得到生成矩陣現(xiàn)在是36頁\一共有45頁\編輯于星期四36設(shè)一分組碼具有一致校驗矩陣：①求這個分組碼n=？k=？，共有多少個碼字？②此分組碼的生成矩陣；③向量101010是否是碼字？習(xí)題課（補充）現(xiàn)在是37頁\一共有45頁\編輯于星期四37習(xí)題課③由可知，向量101010不是碼字．現(xiàn)在是38頁\一共有45頁\編輯于星期四38說明現(xiàn)在是39頁\一共有45頁\編輯于星期四39一個線性子空間可以有不同的但相互等價的基，亦即不同的G可以產(chǎn)生相同的線性碼，所以一個線性碼的生成矩陣不唯一。現(xiàn)在是40頁\一共有45頁\編輯于星期四40例2設(shè)碼的生成矩陣為則共有兩個碼字，為一個(5,1)碼.現(xiàn)在是41頁\一共有45頁\編輯于星期四41系統(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)碼，其生成矩陣和一致校驗矩陣分別記為

Gs

,Hs現(xiàn)在是42頁\一共有45頁\編輯于星期四42線性分組碼的生成矩陣

和校驗矩陣的關(guān)系由于G的每一行都是一個碼字，所以G的每一行c

i

都滿足： 從而有：

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

d

-

1

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

dmin

=

d現(xiàn)在是43頁\一共有45頁\編輯于星期四43漢明(Hamming)碼漢明碼是一類能糾正一位差錯的線性分組碼，其參數(shù)為：碼長：信息位長：

校驗位長：最小碼距：

漢明碼H

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

m

位的

2

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

0

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

H

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

H

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

2

元漢明碼由于故構(gòu)造的漢明碼為線性分組碼漢明碼的編碼效率是很高的，現(xiàn)在是44頁\一共有45頁\編輯于星期四44線性分組碼的描述設(shè)信息分組長度為

，在每一信息組后加上

4

個校驗碼元，構(gòu)成線性分組碼 設(shè)該碼的碼字為