【正文】 0”的個數(shù)剛好相等 ， 此時若按大數(shù)準則無法作出判斷 ， 造成譯碼失敗 ， 這種譯碼稱為 不完備譯碼 。 這種譯碼方案就是大數(shù)準則譯碼 。 在重復碼情況下這種譯碼方案就是根據(jù)收到序列中 0和1的多少 ， 來判斷信息組是 0還是 1。 也就是說信道錯誤圖樣 E中 ， 出現(xiàn)重量最輕的圖樣可能性最大 。 設它們通過 BSC傳輸 ， 信道的轉(zhuǎn)移概率為 pe。 0 , ( , )m i n { ( , ) }x y C n kd d x y??第一章 糾錯碼的基本概念 49 例 重復碼 重復碼是 k＝ 1的 (n， 1)碼 ， 它的編碼規(guī)則是 (n1)個校驗元是信息元的重復 ， 設信息元為 1， 則校驗元 ci＝1(i=0， 1， 2， …， n2)。 糾錯編碼的基本任務之一就是構(gòu)造出 R一定 、 d0盡可能大的碼 ， 或 d0一定 、 R盡可能高的碼 。 以后將看到： d0越大 ， 碼的抗干擾能力越強 ， 在同樣譯碼方法下它的譯碼錯誤概率越小 。 d0是 (n， k)分組碼的另一個重要參數(shù) 。 若 y: (01111)， 則 w(y)＝ 4，等等 。 定義 n重 x中非零碼元的個數(shù) ， 稱為它的 漢明重量 ， 簡稱重量 ， 用 w(x)表示 。 第一章 糾錯碼的基本概念 47 三 、 漢明 (Hamming) 定義 兩個 n重 x、 y之間 ， 對應位取值不同的個數(shù) ， 稱為它們之間的 漢明距離 ， 用 d(x， y)表示 。 對于 DMC信道 ， MLD是使譯碼錯誤概率最小的一種最佳譯碼準則或方法 ， 但此時要求發(fā)端發(fā)送每一碼字的概率 P(Ci)(i＝ 1， 2， …,2k)均相等 ， 否則 MLD不是最佳的 。 第一章 糾錯碼的基本概念 46 一個譯碼器的譯碼規(guī)則若能在 2k個碼字 C中選擇某一個 Ci使式 ()成為最大 ， 則這種譯碼規(guī)則稱為最大似然譯碼 (MLD)，P(R|C)稱為似然函數(shù) ， 相應的譯碼器稱為最大似然譯碼器 。 當給定接收序列 R時 ， 譯碼器的條件譯碼錯誤概率定義為 C?)|?()|( RCCPREP ??所以譯碼器的錯誤譯碼概率 ??RE RPREPP )()|(第一章 糾錯碼的基本概念 44 P(R)是接收 R的概率 ， 與譯碼方法無關 ， 所以譯碼錯誤概率最小的最佳譯碼規(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? ? ?? ? ?因此 ， 如果譯碼器對輸入的 R， 能在 2k個碼字中選擇一個使 最大的碼字 Ci作為 C的估值序列 ，則這種譯碼規(guī)則一定使譯碼器輸出錯誤概率最小 ， 稱這種譯碼規(guī)則為最大后驗概率譯碼 。 M?M?C? M?第一章 糾錯碼的基本概念 43 如果譯碼器輸出的 ≠C， 則譯碼器產(chǎn)生了錯誤譯碼 。 由于 M與碼字 C之間存在一一對應關系 ， 所以這等價于譯碼器根據(jù)R產(chǎn)生一個 C的估值序列 。 第一章 糾錯碼的基本概念 42 二 、 由圖 12可知 ， 信道輸出的 R是一個二 (或 q)進制序列 ， 而譯碼器的輸出是一個信息序列 M的估值序列 。 (n0， k0， m)卷積碼的 碼率 R＝ k0／ n0 。 圖 1 13 一個 (2， 1， 2)卷積碼編碼器 第一章 糾錯碼的基本概念 41 定義 (n0， k0， m)卷積碼 是對每段 k0長的信息組以一定的規(guī)則增加 r0＝ n0k0個校驗元 ， 組成長為 n0的碼段 。 若輸入的信息序列以 k0＝ 1個碼元分段輸入 ， 則輸出以 n0＝ 2個碼元為一段輸出 ， 如輸入的信息序列 M＝ (1 1 0 1 0 0)， 輸出的碼序列為 C＝ (11， 10， 10， 00， 01， 11， 00， …)。 R是衡量分組碼有效性的一個基本參數(shù) 。 我們稱被選取的 2k個 n重為許用碼組 ， 其余的 2n2k個為禁用碼組 。 第一章 糾錯碼的基本概念 38 圖 1 12 利用分組碼的數(shù)字通信模型 第一章 糾錯碼的基本概念 39 n長序列的可能排列總共有 2n種 (每一 n長序列稱為 n重 )， 而(n， k)分組碼的碼字集合只有 2k種 。 定義 分組碼是對每段 k位長的信息組 ， 以一定規(guī)則增加r=nk個校驗元 ， 組成長為 n的序列： (1， 2， …， c1， c0)， 稱這個序列為碼字 (碼組 、 碼矢 )。 第一章 糾錯碼的基本概念 36 圖 1 11 糾錯碼分類 第一章 糾錯碼的基本概念 37 167。 此外 ， 在分組碼中按照碼的結(jié)構(gòu)特點 ， 又可分為 循環(huán)碼 與非循環(huán)碼 。 (5) 按照對每個信息元保護能力是否相等可分為 等保護 糾錯碼與 不等保護 (UEP)糾錯碼 。 (3) 按照糾正錯誤的類型可分為糾正 隨機 (獨立 )錯誤的碼 、 糾正 突發(fā) 錯誤的碼和糾正 同步 錯誤的碼 ， 以及既能糾正隨機錯誤又能糾正突發(fā)錯誤的碼 。 若校驗元與信息元之間的關系是線性關系 (滿足線性疊加原理 )， 則稱為 線性碼 ；否則 ， 稱為 非線性碼 。 因此卷積碼用 (n0， k0， m)表示 。 卷積碼 是把信源輸出的信息序列 ， 以 k0個 (k0通常小于 k)碼元分為一段 ， 通過編碼器輸出長為 n0(≥k0)一段的碼段 。 因此每一碼組的校驗元僅與本組的信息元有關 ， 而與別組無關 。 除了上述的劃分方法以外， 通常還按以下方式對糾錯碼進行分類： 第一章 糾錯碼的基本概念 33 (1) 按照對信息元處理方法的不同 ， 分為分組碼與卷積碼兩大類 。 第一章 糾錯碼的基本概念 31 圖 1 10 差錯控制的基本方式 第一章 糾錯碼的基本概念 32 二 、 糾錯碼的分類 上述各種差錯控制系統(tǒng)中所用到的碼 ， 不外乎是能在譯碼器自動發(fā)現(xiàn)錯誤的檢錯碼 ， 或者不僅能發(fā)現(xiàn)錯誤而且能自動糾正錯誤的糾錯碼 ， 或者能糾正刪除錯誤的糾刪碼 。 為了便于比較 ， 我們把上述幾種方式用圖 1 10所示的框圖表示 。 第一章 糾錯碼的基本概念 30 除了上述三種主要方式以外 ， 還有所謂狹義信息反饋系統(tǒng)(IRQ)。 如果錯誤很多 ， 超過了碼的糾錯能力 ， 但能檢測出來 ， 則接收端通過反饋信道 ， 要求發(fā)端重新傳送有錯的消息 。 這種方式是發(fā)送端發(fā)送的碼不僅能夠被檢測出錯誤 ， 而且還具有一定的糾錯能力 。 但由于這種方式能同播 ， 特別適用于軍用通信 ， 并且隨著編碼理論的發(fā)展和大規(guī)模集成電路成本的不斷降低 ， 譯碼設備有可能做得越來越簡單 ， 成本越來越低 ， 因而在實際的數(shù)字通信中逐漸得到廣泛應用 。 第一章 糾錯碼的基本概念 28 優(yōu)點 ：不需要反饋信道 ， 能進行一個用戶對多個用戶的同播通信 ， 譯碼實時性較好 ， 控制電路比 ARQ的簡單 。 第一章 糾錯碼的基本概念 27 (2) 前向糾錯方式 (FEC)。 缺點： 控制電路比較復雜；連貫性和實時性較差 。 如圖 19所示 。 第一章 糾錯碼的基本概念 25 167。 若為突發(fā)信道 ， 則在錯誤圖樣 E中 ， 第一個 1與最后一個 1之間的長度稱為突發(fā)長度 ， 其圖樣稱為突發(fā)圖樣 。 用式子可表示成： 第一章 糾錯碼的基本概念 24 發(fā)送序列 C: 1111100000 錯誤圖樣 E： 0110110000 接收序列 R： 1001010000 + 即 R＝ C