【正文】 信息論與編碼 第七章 線性分組碼 信息論與編碼 內(nèi)容提要 目前，幾乎所有得到實(shí)際應(yīng)用的糾錯(cuò)碼都是線性的。本章首先介紹有關(guān)糾錯(cuò)碼的基本概念，然后重點(diǎn)論述線性分組碼的定義及其編譯碼理論。在此基礎(chǔ)上，介紹了一種典型的線性分組碼：漢明碼。 掌握內(nèi)容：線性分組碼的概念，生成矩陣，校驗(yàn)矩陣，最小距離，伴隨式，標(biāo)準(zhǔn)陣列等。 信息論與編碼 167。 糾錯(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ù)目煽啃浴? 信息論與編碼 二．差錯(cuò)控制系統(tǒng)模型及分類 1．差錯(cuò)控制系統(tǒng)模型 糾 錯(cuò) 碼編 碼 器糾 錯(cuò) 碼譯 碼 器編 碼 信 道u?信 源信 宿噪 聲 源c? E y? u??模型突出了以控制差錯(cuò)為目的的糾錯(cuò)碼編、譯碼器，因此也稱為差錯(cuò)控制系統(tǒng) 。 2．差錯(cuò)控制系統(tǒng)的分類 按其糾錯(cuò)能力的不同可分為兩種： 檢錯(cuò)碼 和 糾錯(cuò)碼 。 ⑴ 檢錯(cuò)碼 ：能發(fā)現(xiàn)錯(cuò)誤但不能糾正錯(cuò)誤的碼； ⑵ 糾錯(cuò)碼 ：不僅能發(fā)現(xiàn)錯(cuò)誤而且還能糾正錯(cuò)誤的碼。 信息論與編碼 按差錯(cuò)控制系統(tǒng)類型，可分為 前向糾錯(cuò) 、 重傳反饋 和 混合糾錯(cuò) 等三種方式。 ⑴ 前向糾錯(cuò) (FEC)方式 ： FEC (Forward Error Control) 方式是發(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 (Automatic Repeat Request) 方式是：發(fā)端發(fā)出能夠發(fā)現(xiàn)錯(cuò)誤的碼（檢錯(cuò)碼），收端譯碼器收到后，判斷在傳輸中有無錯(cuò)誤產(chǎn)生，并通過反饋信道把撿測(cè)結(jié)果告訴發(fā)端。發(fā)端把收端認(rèn)為有錯(cuò)的消息再次傳送，直到收端認(rèn)為正確接收為止。 信息論與編碼 優(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 (Hybrid Error Control) 方式是上述兩種方式的結(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)。 信息論與編碼 在設(shè)計(jì)差錯(cuò)控制系統(tǒng)時(shí)，選擇何種實(shí)現(xiàn)方式，應(yīng)綜合考慮各方面的因素。主要有： ⑴ 滿足用戶對(duì)誤碼率的要求； ⑵ 有盡可能高的信息傳輸速率； ⑶ 有盡可能簡(jiǎn)單的編譯碼算法且易于實(shí)現(xiàn)； (4) 可接受的成本。 三．糾錯(cuò)碼的分類 常用的糾錯(cuò)碼按其碼字結(jié)構(gòu)形式和對(duì)信息序列處理方式的不同可分成兩大類： 分組碼 和 卷積碼 。 信息論與編碼 分組碼 ：把信息序列以每 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（ n ? k）的一個(gè)子碼。但是該子碼的 n－ k個(gè)校驗(yàn)元不僅與本子碼的信息元有關(guān)，而且也與其前 m個(gè)子碼的信息元有關(guān)。 信息論與編碼 四．差錯(cuò)類型 討論碼字序列通過離散信道時(shí)發(fā)生的情況，信道分為 無記憶信道 和 有記憶信道 。 在無記憶信道中，噪聲對(duì)傳輸碼元的影響是相互獨(dú)立的，即每一個(gè)差錯(cuò)的出現(xiàn)與其前后是否有錯(cuò)無關(guān)，如圖所示。在無記憶信道中，錯(cuò)誤是隨機(jī)產(chǎn)生的，因此被稱作 隨機(jī)錯(cuò)誤 ，無記憶信道也被稱為 隨機(jī)信道（ random channel） 。 01011 pe1 pepepe信息論與編碼 有記憶信道中，各種干擾所造成的錯(cuò)誤往往不是單個(gè)地，而是成群、成串地出現(xiàn)，表現(xiàn)出錯(cuò)誤之間有相關(guān)性，稱為 突發(fā)錯(cuò)誤 。下圖就是這種信道的一個(gè)模型。 01011 p1q1p1p1S1S2q2q1 q21 q11 q21 p101011 p2p2p21 p2好 好 好好 好 好p1 p2就實(shí)際信道而言，由于其干擾的復(fù)雜性，往往是兩種錯(cuò)誤并存。隨機(jī)錯(cuò)誤與突發(fā)錯(cuò)誤并存的信道，稱為 組合信道 或 復(fù)合信道 。 信息論與編碼 167。 分組碼及檢、糾錯(cuò)能力的獲得 一．分組碼定義 設(shè)消息或數(shù)據(jù)以二進(jìn)制形式表示，并以 F2 = { 0 , 1 }表示這個(gè)二元集。 消息集： ? ?? ?0 1 k 1 i 2u u u u F?， ， ，序列個(gè)數(shù)： 2k 設(shè)長(zhǎng)為 n的二元碼元序列集為： ? ?? ?0 1 n 1c c c n k?， ， ，序列個(gè)數(shù)： 2n ≥2k 設(shè)消息集是長(zhǎng)為 k的二元消息序列集，表示如下： 信息論與編碼 1．分組編碼： 在長(zhǎng)為 n的二元序列集中 選出與消息序列數(shù) 2k相同數(shù)目的碼元序列，并使兩者一一對(duì)應(yīng)。 ? ?? ?0 1 n 1c c c， ， ，幾個(gè)概念： 碼字 ：對(duì)應(yīng)于消息的長(zhǎng) n的 2k個(gè)碼元序列，用 表示。 c選出的 2k個(gè)碼元序列稱為 許用碼組 ，另外的 2n 2k個(gè)為 禁用碼組 。 碼 ：所有碼字的集合，用 C表示。 字 ：所有長(zhǎng)為 n的二元序列。 消息 ：長(zhǎng)為 k的二元碼元序列，用 表示。 u信息論與編碼 2．消息 與碼字 的映射關(guān)系（函數(shù)關(guān)系） cu? ?? ?? ?0 0 0 1 k 11 1 0 1 k 11 1 0 1 k 1nnc f u u uc f u u uc f u u u?????????? ??， ， ， ， ， ， ，線性分組碼 ： 與 呈線性關(guān)系（ fi為線性函數(shù)） 0 1 n 1c c c， ， ， 0 1 k 1u u u， ， ，非線性分組碼 ： 與 不呈線性關(guān)系（ fi為非線性函數(shù)） 0 1 n 1c c c， ， ， 0 1 k 1u u u， ， ，對(duì)于消息為 k位，碼長(zhǎng)為 n的線性分組碼稱（ n， k）線性分組碼。 信息論與編碼 【 例 】 一個(gè)原始數(shù)字消息 u0 編碼規(guī)則： 001010ncucucu???? ????? ??000 , 0 0 01 , 1 1 1nucuc????k = 1，故為（ n， 1）碼，稱（ n， 1）重復(fù)碼。碼率： R = 1/n 【 例 】 編碼規(guī)則 0011221 0 2 n 2nnncucucuc u u u??????????? ??? ? ? ???構(gòu)成一個(gè)（ n， n 1）線性分組碼： R = (n1)/n （加法為模 2加） 信息論與編碼 由最后一個(gè)方程： 2 2 1110 0 000n n nn i n i ii i ic u c u c? ? ???? ? ?? ? ? ? ? ?? ? ?（奇）偶校驗(yàn)碼 ：碼字中 1的個(gè)數(shù)為偶數(shù)。 在接收到一個(gè)字中 1的個(gè)數(shù)不是偶數(shù)時(shí)，就可以確定接收的不是碼字。這種碼能檢出奇數(shù)個(gè)錯(cuò)誤，但不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。 比較上面兩例編碼方案： ①