線性分組碼課件

1、關(guān)于線性分組碼1第一張，PPT共五十頁，創(chuàng)作于2022年6月2設(shè)傳輸一比特字符x=0或1 若傳輸過程中出現(xiàn)差錯(cuò),不能被發(fā)現(xiàn)引例第二張，PPT共五十頁，創(chuàng)作于2022年6月3引例0后附加字符0，1后附加1；即只有00和11被接受，且00視為0，11視為1；故： 如果有一位錯(cuò)誤發(fā)生，可以被檢出！第三張，PPT共五十頁，創(chuàng)作于2022年6月4如果通信過程中發(fā)現(xiàn)差錯(cuò)，可以通過要求對(duì)方重新發(fā)送來獲得正確的信息，即所謂的“數(shù)量換質(zhì)量”. 但是這在實(shí)時(shí)信息采集系統(tǒng)中可能是有困難的，因?yàn)樾畔⒃匆呀?jīng)發(fā)生變化；即使是在發(fā)方保留原信息樣本的情況下，也只有在差錯(cuò)率很低的條件下是比較可行的. 因?yàn)槿绻ㄐ艞l件比較惡劣，

2、差錯(cuò)出現(xiàn)頻繁，以至多次重發(fā)仍然得不到一份正確的信息. 這時(shí)，僅有“檢錯(cuò)”手段，已無能為力！引例第四張，PPT共五十頁，創(chuàng)作于2022年6月5引例0后附加字符00，1后附加11；即傳輸000相當(dāng)于傳送單字符0，111相當(dāng)于傳送單字符1；這時(shí)：發(fā)生不超過兩位的錯(cuò)誤均可被檢出；發(fā)生一位錯(cuò)誤可以被糾正.第五張，PPT共五十頁，創(chuàng)作于2022年6月6引例0后附加字符00，1后附加11；即傳輸000相當(dāng)于傳送單字符0，111相當(dāng)于傳送單字符1；這時(shí)：發(fā)生不超過兩位的錯(cuò)誤均可被檢出；發(fā)生一位錯(cuò)誤可以被糾正.糾錯(cuò)碼信息位校驗(yàn)位第六張，PPT共五十頁，創(chuàng)作于2022年6月7線性分組碼的基本概念分組碼分組碼是把信

3、源輸出的信息序列，以k個(gè)信息位分為一段，通過編碼器把這段信息位按一定規(guī)則f 產(chǎn)生r個(gè)校驗(yàn)位，輸出長(zhǎng)為n=k+r的一個(gè)碼字，所得碼字的全體.稱之為（n， k ）分組碼 ！ n表示碼長(zhǎng)， k表示信息位個(gè)數(shù). 第七張，PPT共五十頁，創(chuàng)作于2022年6月8引例0后附加字符00，1后附加11；即傳輸000相當(dāng)于傳送單字符0，111相當(dāng)于傳送單字符1；這時(shí)：發(fā)生不超過兩位的錯(cuò)誤均可被檢出；發(fā)生一位錯(cuò)誤可以被糾正.(3,1)分組碼信息位校驗(yàn)位第八張，PPT共五十頁，創(chuàng)作于2022年6月9（n， k ）分組碼若校驗(yàn)位與信息位之間的關(guān)系是線性的，即上述編碼規(guī)則是線性的，稱之為（n， k ）線性分組碼！ 第九張

4、，PPT共五十頁，創(chuàng)作于2022年6月10一、二元域GF(2)設(shè)0,1為一個(gè)二元集，在其上定義模2的加法和乘法運(yùn)算加法：乘法： 可見二元集0,1對(duì)上述定義的加法及乘法運(yùn)算封閉，并滿足一個(gè)“域”所要求的交換律、結(jié)合律、分配律等運(yùn)算規(guī)則，因此0,1對(duì)所規(guī)定的加法和乘法運(yùn)算構(gòu)成一個(gè)域，稱為二元域，記作GF(2).第十張，PPT共五十頁，創(chuàng)作于2022年6月11注 第十一張，PPT共五十頁，創(chuàng)作于2022年6月12稱碼為(n, k)碼.二、線性分組碼的定義及表示第十二張，PPT共五十頁，創(chuàng)作于2022年6月13若設(shè)碼字 ，則即校驗(yàn)位是由信息位線性組合得到.第十三張，PPT共五十頁，創(chuàng)作于2022年6月

5、14可見，碼字的三個(gè)校驗(yàn)元都由其前兩位線性組合得到，即可由線性方程組求得； 信息位k=2碼字?jǐn)?shù)M=4第十四張，PPT共五十頁，創(chuàng)作于2022年6月15線性編碼第十五張，PPT共五十頁，創(chuàng)作于2022年6月16例題1：下面是某個(gè)（n，k）線性二元碼的全部碼字x16=000000 x26=100011 x36=010101 x46=001111x56=110110 x66=101100 x76=011010 x86=111001求n、k的值；n=6;M=2k k=3.解：第十六張，PPT共五十頁，創(chuàng)作于2022年6月17例2、（5，2）線性二元碼的全部碼字設(shè)碼字 ， 可得第十七張，PPT共五十頁，

6、創(chuàng)作于2022年6月18改寫為用矩陣可表示成： 校驗(yàn)矩陣 與任一碼字的乘積為0 第十八張，PPT共五十頁，創(chuàng)作于2022年6月19線性分組碼的特性 2k個(gè)碼字完全可由其中一組k 個(gè)獨(dú)立的碼字組合而成； 生成矩陣從線性分組碼（n，k）中任取 k 個(gè)線性無關(guān)的碼字，以行的形式寫成矩陣G，則稱為該線性分組碼的生成矩陣. 第十九張，PPT共五十頁，創(chuàng)作于2022年6月20例題3：下面是一個(gè)（6，3）線性二元碼的全部碼字構(gòu)造它的一個(gè)生成矩陣.解：由k=3 個(gè)線性獨(dú)立的碼字組成：第二十張，PPT共五十頁，創(chuàng)作于2022年6月21例題3：下面是一個(gè)（6，3）線性二元碼的全部碼字驗(yàn)證：第二十一張，PPT共五十

7、頁，創(chuàng)作于2022年6月22說明第二十二張，PPT共五十頁，創(chuàng)作于2022年6月23 一個(gè)線性子空間可以有不同的但相互等價(jià)的基，亦即不同的G可以產(chǎn)生相同的線性碼，所以一個(gè)線性碼的生成矩陣不唯一。第二十三張，PPT共五十頁，創(chuàng)作于2022年6月24例4 矩陣為一個(gè)(7, 3) 碼.第二十四張，PPT共五十頁，創(chuàng)作于2022年6月25系統(tǒng)碼 若（n , k）線性分組碼的生成矩陣形如 G=(Ik A)其中Ik是k階單位陣，A為 階子陣，則稱這類碼為系統(tǒng)碼.特點(diǎn)：校驗(yàn)矩陣為H=( AT I(n-k) ) .三、系統(tǒng)編碼與校驗(yàn)矩陣第二十五張，PPT共五十頁，創(chuàng)作于2022年6月26例題3：下面是一個(gè)（6

8、，3）線性二元碼的全部碼字它的一個(gè)生成矩陣請(qǐng)寫出它的校驗(yàn)矩陣H.第二十六張，PPT共五十頁，創(chuàng)作于2022年6月27第二十七張，PPT共五十頁，創(chuàng)作于2022年6月28注：系統(tǒng)碼的碼字的前k個(gè)碼元就是它所載荷的數(shù)字消息，故系統(tǒng)碼的前k為稱為信息位，后n-k位稱為校驗(yàn)位.第二十八張，PPT共五十頁，創(chuàng)作于2022年6月29校驗(yàn)矩陣即結(jié)論：第二十九張，PPT共五十頁，創(chuàng)作于2022年6月30漢明距離： 指（n,k）分組碼中兩個(gè)碼字xn 、 yn對(duì)應(yīng)位取值不同的個(gè)數(shù)；記為d（xn ，yn）. 例： 第三十張，PPT共五十頁，創(chuàng)作于2022年6月31漢明距離： 指（n,k）分組碼中兩個(gè)碼字xn 、 y

9、n對(duì)應(yīng)位取值不同的個(gè)數(shù)；記為d（xn ， yn）. 例： 第三十一張，PPT共五十頁，創(chuàng)作于2022年6月32線性分組碼的最小距離： 稱（n,k）分組碼中任兩個(gè)碼字漢明距離的最小值，為該分組碼的最小距離d. （5,2）線性分組碼全部碼字：最小距離d=3. 漢明重量第三十二張，PPT共五十頁，創(chuàng)作于2022年6月33漢明(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)的列，譯碼比較方便將上

10、述非標(biāo)準(zhǔn)形式的 H 矩陣通過列初等置換變成標(biāo)準(zhǔn)形式的校驗(yàn)矩陣，糾錯(cuò)能力保持不變例：構(gòu)造一個(gè) 的 2 元漢明碼由于 故構(gòu)造的漢明碼為 線性分組碼漢明碼的編碼效率是很高的， 第三十三張，PPT共五十頁，創(chuàng)作于2022年6月34設(shè)一分組碼具有一致校驗(yàn)矩陣：求這個(gè)分組碼n=？k=？，共有多少個(gè)碼字？此分組碼的生成矩陣；向量101010是否是碼字？習(xí)題課（補(bǔ)充）第三十四張，PPT共五十頁，創(chuàng)作于2022年6月35解：設(shè)碼字C=(c5c4c3c2c1c0)，有習(xí)題課故得所以n=6，k=3，為(6,3)分組碼共有碼字2k=8個(gè)第三十五張，PPT共五十頁，創(chuàng)作于2022年6月36設(shè)一分組碼具有一致校驗(yàn)矩陣：求

11、這個(gè)分組碼n=？k=？，共有多少個(gè)碼字？此分組碼的生成矩陣；向量101010是否是碼字？習(xí)題課（補(bǔ)充）第三十六張，PPT共五十頁，創(chuàng)作于2022年6月37習(xí)題課由上式可得取一組線性無關(guān)的基礎(chǔ)解系，得到生成矩陣第三十七張，PPT共五十頁，創(chuàng)作于2022年6月38設(shè)一分組碼具有一致校驗(yàn)矩陣：求這個(gè)分組碼n=？k=？，共有多少個(gè)碼字？此分組碼的生成矩陣；向量101010是否是碼字？習(xí)題課（補(bǔ)充）第三十八張，PPT共五十頁，創(chuàng)作于2022年6月39習(xí)題課由可知，向量101010不是碼字第三十九張，PPT共五十頁，創(chuàng)作于2022年6月40說明第四十張，PPT共五十頁，創(chuàng)作于2022年6月41 一個(gè)線性子

12、空間可以有不同的但相互等價(jià)的基，亦即不同的G可以產(chǎn)生相同的線性碼，所以一個(gè)線性碼的生成矩陣不唯一。第四十一張，PPT共五十頁，創(chuàng)作于2022年6月42例2 設(shè)碼的生成矩陣為則共有兩個(gè)碼字，為一個(gè)(5, 1) 碼.第四十二張，PPT共五十頁，創(chuàng)作于2022年6月43系統(tǒng)碼消息G1 碼字G2 碼字000000 000000 000001111 000001 101010110 101010 011011001 101011 110100101 011100 110101010 011101 011110011 110110 101 111100 110111 000生成矩陣 G 的選擇不是惟一的；

13、如下面的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 , Hs第四十三張，PPT共五十頁，創(chuàng)作于2022年6月44線性分組碼的生成矩陣和

14、校驗(yàn)矩陣的關(guān)系由于 G 的每一行都是一個(gè)碼字，所以 G 的每一行 c i 都滿足：從而有： 在碼字集合不變的前提下，給定任何一個(gè)線性分組碼，通過其生成矩陣 G 實(shí)施行初等變換，均可以轉(zhuǎn)換為某個(gè)系統(tǒng)碼當(dāng)且僅當(dāng)線性分組碼一致校驗(yàn)矩陣 H 中任意 d - 1 個(gè)列線性無關(guān)而某 d 列線性相關(guān)時(shí)，線性分組碼的最小碼距為 dmin = d第四十四張，PPT共五十頁，創(chuàng)作于2022年6月45漢明(Hamming)碼漢明碼是一類能糾正一位差錯(cuò)的線性分組碼，其參數(shù)為：碼長(zhǎng)： 信息位長(zhǎng)： 校驗(yàn)位長(zhǎng)： 最小碼距： 漢明碼 H 矩陣的構(gòu)造方式：按 m 位的 2 進(jìn)制數(shù)的自然順序從左到右排列(不包括全 0 列)，當(dāng)發(fā)

15、生可糾的單個(gè)差錯(cuò)時(shí)，伴隨式為 H 矩陣中對(duì)應(yīng)的列，譯碼比較方便將上述非標(biāo)準(zhǔn)形式的 H 矩陣通過列初等置換變成標(biāo)準(zhǔn)形式的校驗(yàn)矩陣，糾錯(cuò)能力保持不變例：構(gòu)造一個(gè) 的 2 元漢明碼由于 故構(gòu)造的漢明碼為 線性分組碼漢明碼的編碼效率是很高的， 第四十五張，PPT共五十頁，創(chuàng)作于2022年6月46線性分組碼的描述設(shè)信息分組長(zhǎng)度為 ，在每一信息組后加上 4 個(gè)校驗(yàn)碼元，構(gòu)成 線性分組碼設(shè)該碼的碼字為 ，其中 為信息碼元， 為校驗(yàn)碼元， ；信息碼元和校驗(yàn)碼元可按下面方程組計(jì)算：消息碼字消息碼字000000 0000100100 1110001001 1101101101 0011010101 0111110

16、110 1001011011 1010111111 0100利用上式每給出一個(gè) 4 位的信息組，就可編出一個(gè)碼字，結(jié)果如表所示 模 2 加第四十六張，PPT共五十頁，創(chuàng)作于2022年6月476.2.1線性分組碼的描述 分組碼的編碼包括兩個(gè)基本步驟首先將信源的輸出序列分為 k 位一組的信息組然后信道編碼器根據(jù)一定的編碼規(guī)則將 k 位信息組變換成n 個(gè)碼元的碼字信息組和碼字用矩陣表示如下：信息組： k 位信息 碼字： n 個(gè)碼元 k 位信息位r = n - k 位校驗(yàn)位通常對(duì)編碼器附加一個(gè)線性約束條件，使得碼字的校驗(yàn)位與信息位之間呈線性關(guān)系，這種碼稱為 (n, k ) 線性分組碼采用線性分組碼進(jìn)行

17、信道編碼，就是給已知信息組按預(yù)定規(guī)則添加校驗(yàn)碼元以構(gòu)成碼字。在 k 個(gè)信息元之后附加 r = n - k 個(gè)校驗(yàn)碼元，使每個(gè)校驗(yàn)碼元是其中某些信息碼元的和第四十七張，PPT共五十頁，創(chuàng)作于2022年6月48線性分組碼的生成矩陣和一致校驗(yàn)矩陣在 (n, k ) 線性分組碼中，編碼器輸出的碼字可以由如下方程組來決定：如設(shè)：則方程組的矩陣表示為：c = mG所有滿足上式碼字(n 維向量)的全體構(gòu)成 (n, k) 線性分組碼 C生成矩陣生成矩陣 G 是一個(gè) k 行 n 列(n k)秩為 k 的矩陣，它 建立了消息向量與碼字的一一對(duì)應(yīng)關(guān)系，它起著編碼器的變換作用G 的每一行都是一個(gè)碼字，分別是 k 維消息向量組 1000, 01000, , 00010, 00001 所對(duì)應(yīng)的碼字m 是任意 k 維消息向量運(yùn)算：模 2 加、模 2 乘第