【文章內(nèi)容簡(jiǎn)介】 組碼的碼字集合只有 2k種 。 所以 ， 分組碼的編碼問(wèn)題就是定出一套規(guī)則 ， 以便從 2n個(gè) n重中選出 2k個(gè)碼字 ， 不同的選取規(guī)則就得到不同的碼 。 我們稱被選取的 2k個(gè) n重為許用碼組 ， 其余的 2n2k個(gè)為禁用碼組 。 稱 R＝ k／ n為 碼率 ， 表示 (n， k)分組碼中 ， 信息位在碼字中所占的比重 。 R是衡量分組碼有效性的一個(gè)基本參數(shù) 。 第一章 糾錯(cuò)碼的基本概念 40 圖 1 13是一個(gè) (2, 1, 2)卷積碼編碼器 。 若輸入的信息序列以 k0＝ 1個(gè)碼元分段輸入 ， 則輸出以 n0＝ 2個(gè)碼元為一段輸出 ， 如輸入的信息序列 M＝ (1 1 0 1 0 0)， 輸出的碼序列為 C＝ (11， 10， 10， 00， 01， 11， 00， …)。 可知隨著信息元的不斷輸入 ，輸出的是一個(gè)半無(wú)限長(zhǎng)的碼序列 ， 由此可如下定義卷積碼 。 圖 1 13 一個(gè) (2， 1， 2)卷積碼編碼器 第一章 糾錯(cuò)碼的基本概念 41 定義 (n0， k0， m)卷積碼 是對(duì)每段 k0長(zhǎng)的信息組以一定的規(guī)則增加 r0＝ n0k0個(gè)校驗(yàn)元 ， 組成長(zhǎng)為 n0的碼段 。 n0k0個(gè)校驗(yàn)元不僅與本段的信息元有關(guān) ， 且與前 m段的信息元有關(guān) ， 當(dāng)信息元不斷輸入時(shí) ， 輸出的碼序列是一個(gè)半無(wú)限長(zhǎng)序列 。 (n0， k0， m)卷積碼的 碼率 R＝ k0／ n0 。 與分組碼的碼長(zhǎng) n相對(duì)應(yīng) ， 在卷積碼中稱 nc＝ n0(m+1)為 編碼約束長(zhǎng)度 ， 說(shuō)明 k0個(gè)信息元從輸入編碼器到離開時(shí)在碼序列中影響的碼元數(shù)目 ， 如圖 1 13中 (2， 1， 2)卷積碼的 nc ＝ 6。 第一章 糾錯(cuò)碼的基本概念 42 二 、 由圖 12可知 ， 信道輸出的 R是一個(gè)二 (或 q)進(jìn)制序列 ， 而譯碼器的輸出是一個(gè)信息序列 M的估值序列 。 譯碼器的基本任務(wù)就是根據(jù)一套譯碼規(guī)則 ， 由接收序列 R給出與發(fā)送的信息序列 M最接近 (最好是相同 )的估值序列 。 由于 M與碼字 C之間存在一一對(duì)應(yīng)關(guān)系 ， 所以這等價(jià)于譯碼器根據(jù)R產(chǎn)生一個(gè) C的估值序列 。 顯然 ， 當(dāng)且僅當(dāng) C＝ C時(shí) ， ＝ M，這時(shí)譯碼器正確譯碼 。 M?M?C? M?第一章 糾錯(cuò)碼的基本概念 43 如果譯碼器輸出的 ≠C， 則譯碼器產(chǎn)生了錯(cuò)誤譯碼 。 之所以產(chǎn)生錯(cuò)誤譯碼是由于：信道干擾很嚴(yán)重 ， 超過(guò)了碼本身的糾錯(cuò)能力；其次 ， 由于譯碼設(shè)備的故障 (這點(diǎn)本書不予討論 )。 當(dāng)給定接收序列 R時(shí) ， 譯碼器的條件譯碼錯(cuò)誤概率定義為 C?)|?()|( RCCPREP ??所以譯碼器的錯(cuò)誤譯碼概率 ??RE RPREPP )()|(第一章 糾錯(cuò)碼的基本概念 44 P(R)是接收 R的概率 ， 與譯碼方法無(wú)關(guān) ， 所以譯碼錯(cuò)誤概率最小的最佳譯碼規(guī)則是使 ?m in m in ( | ) m in ( | )? ?m in ( | ) m a x ( | )EP P E R P C C RP C C R P C C R? ? ?? ? ?因此 ， 如果譯碼器對(duì)輸入的 R， 能在 2k個(gè)碼字中選擇一個(gè)使 最大的碼字 Ci作為 C的估值序列 ，則這種譯碼規(guī)則一定使譯碼器輸出錯(cuò)誤概率最小 ， 稱這種譯碼規(guī)則為最大后驗(yàn)概率譯碼 。 )2,2,1)(|?( ki iRCCP ??? C?（ ） 第一章 糾錯(cuò)碼的基本概念 45 由貝葉斯公式 )()|()()|(RPCRPCPRCP iii ?可知 ， 若發(fā)端發(fā)送每個(gè)碼字的概率 P(Ci)均相同 ， 且由于 P(R)與譯碼方法無(wú)關(guān) ， 所以 kk iiii CRPRCP2,2,12,2,1)|(m ax)|(m ax?? ???對(duì) DMC而言 1( | ) ( | )ni j i jjP R C P r c?? ?（ ） （ ） 這里碼字 Ci＝ (ci1， ci2， …， cin)， i＝ 1， 2， … ， 2k。 第一章 糾錯(cuò)碼的基本概念 46 一個(gè)譯碼器的譯碼規(guī)則若能在 2k個(gè)碼字 C中選擇某一個(gè) Ci使式 ()成為最大 ， 則這種譯碼規(guī)則稱為最大似然譯碼 (MLD)，P(R|C)稱為似然函數(shù) ， 相應(yīng)的譯碼器稱為最大似然譯碼器 。 由于logbx與 x是單調(diào)關(guān)系 ， 因此式 ()與式 ()可寫成 1 , 2 , , 2 1 , 2 , , 2 1m a x l o g ( | ) m a x l o g ( | )kknb i b j i jiijP R C p r c?? ?? ?稱 logbP(R|C)為對(duì)數(shù)似然函數(shù)或似然函數(shù) 。 對(duì)于 DMC信道 ， MLD是使譯碼錯(cuò)誤概率最小的一種最佳譯碼準(zhǔn)則或方法 ， 但此時(shí)要求發(fā)端發(fā)送每一碼字的概率 P(Ci)(i＝ 1， 2， …,2k)均相等 ， 否則 MLD不是最佳的 。 在以后的討論中 ， 都認(rèn)為 P(Ci)均近似相等 。 第一章 糾錯(cuò)碼的基本概念 47 三 、 漢明 (Hamming) 定義 兩個(gè) n重 x、 y之間 ， 對(duì)應(yīng)位取值不同的個(gè)數(shù) ， 稱為它們之間的 漢明距離 ， 用 d(x， y)表示 。 例如 ， 若 x: (10101)， y: (01111)， 則 d(x， y)＝ 3 。 定義 n重 x中非零碼元的個(gè)數(shù) ， 稱為它的 漢明重量 ， 簡(jiǎn)稱重量 ， 用 w(x)表示 。 例如 ， 若 x: (10101)， 則 w(x)＝ 3。 若 y: (01111)， 則 w(y)＝ 4，等等 。 第一章 糾錯(cuò)碼的基本概念 48 定義 (n， k)分組碼中 ， 任兩個(gè)碼字之間距離的最小值 ， 稱為該分組碼的最小漢明距離 d0， 簡(jiǎn)稱 最小距離 例如 (3,2)碼 ， n＝ 3， k＝ 2， 共有 22＝ 4個(gè)碼字： 000， 011， 101， 110， 顯然 d0＝ 2。 d0是 (n， k)分組碼的另一個(gè)重要參數(shù) 。 它表明了分組碼抗干擾能力的大小 。 以后將看到： d0越大 ， 碼的抗干擾能力越強(qiáng) ， 在同樣譯碼方法下它的譯碼錯(cuò)誤概率越小 。 由上可知 ， R和 d0是 (n， k)分組碼的兩個(gè)最重要參數(shù) 。 糾錯(cuò)編碼的基本任務(wù)之一就是構(gòu)造出 R一定 、 d0盡可能大的碼 ， 或 d0一定 、 R盡可能高的碼 。 下面用幾個(gè)具體例子說(shuō)明碼的 R、 d0以及譯碼錯(cuò)誤概率之間的關(guān)系 。 0 , ( , )m i n { ( , ) }x y C n kd d x y??第一章 糾錯(cuò)碼的基本概念 49 例 重復(fù)碼 重復(fù)碼是 k＝ 1的 (n， 1)碼 ， 它的編碼規(guī)則是 (n1)個(gè)校驗(yàn)元是信息元的重復(fù) ， 設(shè)信息元為 1， 則校驗(yàn)元 ci＝1(i=0， 1， 2， …， n2)。 由于 k＝ 1， 相應(yīng)的許用碼字只有 2k＝ 2個(gè) (00…0)和 (11…1)。 設(shè)它們通過(guò) BSC傳輸 ， 信道的轉(zhuǎn)移概率為 pe。 通常情況下 ， pe≤， 因此在傳輸中沒有錯(cuò)誤的可能性比出現(xiàn)一個(gè)錯(cuò)誤的可能性大 ， 出現(xiàn)一個(gè)錯(cuò)誤的可能性比出現(xiàn)兩個(gè)錯(cuò)誤的大 ， 等等 。 也就是說(shuō)信道錯(cuò)誤圖樣 E中 ， 出現(xiàn)重量最輕的圖樣可能性最大 。 第一章 糾錯(cuò)碼的基本概念 50 P(w(E)＝ 0)＞ P(w(E)＝ 1)＞ P(w(E)＝ 2)＞ … 或 ??????? ?? 221 )1()1()1( neeneene ppppp 由 E＝ RC及式 ()可知 ， MLD譯碼器尋求與 R的漢明距離最小的碼字 Ci， 為最可能發(fā)送的碼字而接收 ， 這就是最小漢明距離譯碼 。 在重復(fù)碼情況下這種譯碼方案就是根據(jù)收到序列中