【正文】 乘法群 ：運(yùn)算“ *”為乘法運(yùn)算。 群及其性質(zhì) 一．群的概念 定義 ：設(shè) G是非空集合，在 G中規(guī)定一種運(yùn)算“ * ”， , , *a b G a b G? ? ?，即運(yùn)算 *在 G中是封閉的。 證明： 12c c C??，11 2 1 2 1 2 1 20( ) ( 0 ) ( )n iiid c c c c d c c w c c??? ? ? ? ? ??， ，由于 C是線性碼，故 ，即線性分組碼中任意兩個(gè)碼矢量間的距離等于另一個(gè)碼矢的重量，即 12()c c C??1 2 1 2 3( ) ( ) ( )d c c w c c w c? ? ?， 3 1 2()c c c C? ? ?故 ? ? ? ?1 2 1 2 1 2 3 3 3m i n ( ) m i n ( ) 0d c c c c C c c w c c C c? ? ? ? ?， ， ， ，信息論與編碼 二．線性分組碼的檢、糾錯(cuò)能力與 H矩陣的關(guān)系 定理：設(shè) C是線性分組碼， H是它的校驗(yàn)矩陣，那么碼 C的最小重量就等于H中線性相關(guān)的最小列數(shù)。 2()r V n F r C? ? ?，的充要條件是： 即： 0THr??信息論與編碼 4．生成矩陣 G與校驗(yàn)矩陣 H的梯形矩陣的關(guān)系 （ 1）每個(gè)線性分組碼的生成矩陣存在唯一的 k n的梯形矩陣； （ 2）每個(gè)線性分組碼的校驗(yàn)矩陣存在唯一的 (nk) n的梯形矩陣； （ 3）如 G有 [ Ik P ]的形式，則 H有 [ PT Ink ]的形式（條件：在 F2中）。 信息論與編碼 2．對(duì)偶碼 生成矩陣 G的 k行矢量組成 Vn(F2)的 k維子空間（碼字空間 C）； 校驗(yàn)矩陣 H的 nk個(gè)行矢量組成 Vn(F2)的 nk維的子空間 (C的對(duì)偶子空間 C⊥ )。 （ 3）與非系統(tǒng)碼相比，系統(tǒng)碼編碼過程及所需設(shè)備可以簡化。 （ 5）生成矩陣 G中的每一個(gè)行矢量，不僅僅是張成 k維線性空間的 基底矢量，本身也是一個(gè)碼字。 信息論與編碼 2．線性分組碼的矩陣描述： 設(shè) 0 1 1kg g g ?， ， ， 是（ n， k）線性分組碼中 k個(gè)線性無關(guān)的非零碼字， 0 1 1 ( 2 )ku u u G F? ?， ， ，則（ n， k）線性分組碼 2k個(gè)碼字中的任一碼字 可表示為 c0 0 1 1 1 1kkc u g u g u g??? ? ? ?用矩陣表示： 010 1 11() kkggc u G u u ug????????? ? ???????：長為 k的序列，構(gòu)成 2k個(gè)不同的消息。 12 kv v v， ， ，結(jié)論：（ n， k）線性分組碼可由 k個(gè)線性獨(dú)立的碼字組成的基底張成。 則 1 2 3 1a a a? ? ? (0 1 0 ) (1 0 0 ) (1 1 0 )線性相關(guān)的充要條件 ：在線性空間中，對(duì)于矢量 存在著一個(gè)矢量 ，它可以表示為其余矢量的線性組合。 c ac V? c③ 分配律成立： ,u v V a b F? ? ? ?， ，( ) ( )a u v a u a v a b u a u b u? ? ? ? ? ?( ) ( ) 1 1a b v a b v v v F? ? ? ?，④ 若 ,a b F v V??， 有 則稱 V是域 F上的一個(gè) n維線性空間 （矢量空間），表示為： Vn（ F） 信息論與編碼 2．子空間 線性空間 Vn(F)中矢量 的所有線性組合所構(gòu)成的集合 S是 Vn(F)的子空間。 ? ?m i n i j i jm in ( ) , ,d d c c c c C i j? ? ?，dmin是衡量碼的檢、糾錯(cuò)能力的一個(gè)重要的參數(shù)。 r r ic rjc jcr r?jcr② 極大似然譯碼基礎(chǔ)：收到的字是從一個(gè)碼字經(jīng)錯(cuò)傳盡可能少的位而來的可能性較從一個(gè)碼字經(jīng)錯(cuò)傳較多的位而來的可能性要大。 ? 每個(gè)碼字對(duì)應(yīng)于該重錯(cuò)誤圖樣的接收字集合，與其它碼字的錯(cuò)誤重?cái)?shù)低的接收字集合中，不包含公共元素。 稱 為 錯(cuò)誤圖樣 。（兩個(gè)極端） 3．糾錯(cuò)編碼理論的中心任務(wù) ：在重復(fù)碼和奇偶校驗(yàn)碼之間尋找一些性能良好的碼，使編碼效率和檢、糾錯(cuò)能力得到統(tǒng)一。 在接收到一個(gè)字中 1的個(gè)數(shù)不是偶數(shù)時(shí)，就可以確定接收的不是碼字。 消息 ：長為 k的二元碼元序列，用 表示。 ? ?? ?0 1 n 1c c c， ， ，幾個(gè)概念： 碼字 ：對(duì)應(yīng)于消息的長 n的 2k個(gè)碼元序列，用 表示。隨機(jī)錯(cuò)誤與突發(fā)錯(cuò)誤并存的信道，稱為 組合信道 或 復(fù)合信道 。在無記憶信道中，錯(cuò)誤是隨機(jī)產(chǎn)生的，因此被稱作 隨機(jī)錯(cuò)誤 ，無記憶信道也被稱為 隨機(jī)信道（ random channel） 。 卷積碼 ：把信息序列以每 k個(gè)分組，通過編碼器輸出長為 n（ n ? k）的一個(gè)子碼。 三．糾錯(cuò)碼的分類 常用的糾錯(cuò)碼按其碼字結(jié)構(gòu)形式和對(duì)信息序列處理方式的不同可分成兩大類： 分組碼 和 卷積碼 。收端譯碼時(shí)若發(fā)現(xiàn)錯(cuò)誤個(gè)數(shù)在碼的糾錯(cuò)能力以內(nèi)，則自動(dòng)進(jìn)行糾錯(cuò)；若錯(cuò)誤個(gè)數(shù)超過了碼的糾錯(cuò)能力，但能檢測出來，則通過反饋信道告知發(fā)方重發(fā)。 缺點(diǎn) ：應(yīng)用 ARQ方式必須有一條從收端至發(fā)端的反饋信道。 缺點(diǎn) ：是譯碼設(shè)備較復(fù)雜；編碼效率較低。 ⑴ 檢錯(cuò)碼 ：能發(fā)現(xiàn)錯(cuò)誤但不能糾正錯(cuò)誤的碼； ⑵ 糾錯(cuò)碼 ：不僅能發(fā)現(xiàn)錯(cuò)誤而且還能糾正錯(cuò)誤的碼。 ? 信源編碼的目的是壓縮冗余度，提高信息的傳輸速率。因此，如何控制差錯(cuò)、提高數(shù)據(jù)傳輸和存儲(chǔ)的可靠性，成為現(xiàn)代數(shù)字通信系統(tǒng)設(shè)計(jì)工作者面臨的重要課題。在此基礎(chǔ)上，介紹了一種典型的線性分組碼：漢明碼。本章首先介紹有關(guān)糾錯(cuò)碼的基本概念，然后重點(diǎn)論述線性分組碼的定義及其編譯碼理論。 糾錯(cuò)編碼的基本概念 一．信道糾錯(cuò)編碼 近年來，隨著計(jì)算機(jī)、衛(wèi)星通信及高速數(shù)據(jù)網(wǎng)的飛速發(fā)展，數(shù)據(jù)的交換、處理和存儲(chǔ)技術(shù)得到了廣泛的應(yīng)用，人們對(duì)數(shù)據(jù)傳輸和存儲(chǔ)系統(tǒng)的可靠性提出了越來越高的要求。 這里所講的糾錯(cuò)編碼即信道編碼，與信源編碼一樣都是一種編碼，但兩者的作用是完全不同的。 2．差錯(cuò)控制系統(tǒng)的分類 按其糾錯(cuò)能力的不同可分為兩種： 檢錯(cuò)碼 和 糾錯(cuò)碼 。 優(yōu)點(diǎn) ：是不需要反饋信道；能進(jìn)行一個(gè)用戶對(duì)多個(gè)用戶的同時(shí)通信，特別適合于移動(dòng)通信；譯碼實(shí)時(shí)性較好，控制電路也比較簡單。 信息論與編碼 優(yōu)點(diǎn) ：譯碼設(shè)備簡單，在多余度一定的情況下，碼的檢錯(cuò)能力比糾錯(cuò)能力要高得多，因而整個(gè)系統(tǒng)能獲得極低的誤碼率。發(fā)端發(fā)送的碼既能檢錯(cuò)、又有一定的糾錯(cuò)能力。主要有： ⑴ 滿足用戶對(duì)誤碼率的要求； ⑵ 有盡可能高的信息傳輸速率； ⑶ 有盡可能簡單的編譯碼算法且易于實(shí)現(xiàn)； (4) 可接受的成本。 n： 碼長 ； k： 信息位的數(shù)目 ； R = k / n： 分組碼碼率 。 在無記憶信道中，噪聲對(duì)傳輸碼元的影響是相互獨(dú)立的，即每一個(gè)差錯(cuò)的出現(xiàn)與其前后是否有錯(cuò)無關(guān)，如圖所示。 01011 p1q1p1p1S1S2q2q1 q21 q11 q21 p101011 p2p2p21 p2好 好 好好 好 好p1 p2就實(shí)際信道而言，由于其干擾的復(fù)雜性，往往是兩種錯(cuò)誤并存。 消息集： ? ?? ?0 1 k 1 i 2u u u u F?， ， ，序列個(gè)數(shù)： 2k 設(shè)長為 n的二元碼元序列集為： ? ?? ?0 1 n 1c c c n k?， ， ，序列個(gè)數(shù)： 2n ≥2k 設(shè)消息集是長為 k的二元消息序列集，表示如下： 信息論與編碼 1．分組編碼： 在長為 n的二元序列集中 選出與消息序列數(shù) 2k相同數(shù)目的碼元序列，并使兩者一一對(duì)應(yīng)。 字 ：所有長為 n的二元序列。碼率： 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ù)。 ② 奇偶校驗(yàn)碼： R = (n1)/n，編碼效率最高，檢糾錯(cuò)能力最低。 信息論與編碼 三．錯(cuò)誤圖樣 對(duì)應(yīng)著 n為碼字，長為 n的二元序列 0 1 1 2( , )nie e e e e F???， ， ，? 當(dāng)