【正文】 理指出：對于一個給定的有擾信道，若信道容量為 C，只要發(fā)送端以低于C的速率 R發(fā)送信息，則一定存在一種編碼方法，使編碼錯誤概率 P隨著碼長 n的增加，按指數下降到任意小的值。 即可以通過增加冗余編碼來降低誤碼率 。 糾錯編碼的的基本思想就是在被傳送的信息碼元中附加一些監(jiān)督碼元，在兩者之間建立某種校驗關系，當這種校驗關系因傳輸錯誤而受到破壞時，可以被發(fā)現并予以糾正 。 這種檢錯和糾錯能力是用信息量的冗余度來換取的。 21 以一組二進制碼為例 三位二進制碼元有 8個碼組，如果用來表示天氣的 8種情況 000（晴）， 001（雷）， 010（雹）， 011（陰）， 100（風）， 101（云），110（雨）， 111（雪），如果有一個誤碼，接收端以為是另一條信息，這種編碼沒有檢錯和糾錯能力。 如果這 8種碼組只用來傳送 4條信息，即只準使用其中的 4種碼組 000（晴）， 011（陰）， 101（云）， 110（雨），如果有一位誤碼，不會在接收端產生誤判，會檢出錯誤。 22 4個狀態(tài)只用 2位二進制碼就可以表達，所增加的第 3位，就稱為監(jiān)督碼元。增加 1位監(jiān)督碼元，只能檢出 1位誤碼，對于上例，如果有 2位誤碼，將發(fā)生誤判。如將 000（晴）誤傳成 101（云）。 要抗多位誤碼，就要增加監(jiān)督碼元的個數，即增加冗余度。 23 碼距與檢錯和糾錯能力 定義： 碼重 ：碼組中非零碼元的個數。如 001，碼重為 1； 011，碼重為 2。 碼距 ：兩個碼組中對應碼位上具有的不同二進制碼元的個數定義為兩個碼組的距離（漢明距，簡稱碼距），如 111和 000，碼距為3， 111和 100碼距為 2， 111和 110碼距為 1。 最小碼距 ：對于許用的 n個碼組，各碼組之間最小的碼距稱為最小碼距。 24 25 對于如圖所示的 3位二進制碼，如果 8個碼組可用，（ 000， 001， 010， 011， 100， 101，110， 111），各點之間最小相差 1個邊長，最小碼距為 1。 如果只有 4個碼組可用，選（ 010， 111，100， 001）或（ 110， 011， 000， 101），各點之間相差 2個邊長，最小碼距為 2。 如果只有 2個碼組可用，分別選（ 111，000）（ 100， 011）（ 110， 001）（ 101，010），各點之間相差 3個邊長，最小碼距為 3。 26 碼距與檢錯和糾錯能力 如上所述，一種編碼的最小碼距直接關系到這種碼的檢錯和糾錯能力，因此最小碼距是信道編碼的一個重要參數。在一般情況下，對于分組碼有如下結論： （ 1）在一個碼組內檢測個 e誤碼，要求最小碼距 dmin=e+1 （ 2）在一個碼組內糾正個 t誤碼，要求最小碼距 dmin=2t+1 （ 3）在一個碼組內糾正 t個誤碼，同時檢測 e個 (e=t)誤碼（當誤碼數大于 t時就不能糾錯，只能檢測 e個誤碼），要求最小碼距 dmin=t+e+1 27 幾種實用的簡單檢錯碼 奇偶監(jiān)督碼 這是一種最簡單的檢錯碼，又稱奇偶校驗碼，在計算機數據通信中得到廣泛應用。七單位國際 5層字母表、美國信息交換碼 ASCII字母表中都用 7比特碼組表示 128種字符，如字符 A的編碼為 1000001。為了檢查字符傳輸過程中是否有誤，常在 7比特碼組后碼組后加 1位作為奇偶校驗位。使得 8位碼組（一個字節(jié)）中的“ 1”的個數為奇數或偶數，如果為奇數，稱為奇校驗碼；偶數時，稱為偶校驗碼。 編碼規(guī)則是：首先將要傳送的信息分成組，然后將各位二進制信息加監(jiān)督位用模 2和。選擇正確的監(jiān)督位，使模 2和為“ 0”（偶校驗），為“ 1”（奇校驗）。 奇偶校驗碼只能發(fā)現奇數個誤碼，對檢測突發(fā)錯誤不適用。 28 水平奇偶監(jiān)督碼 將經過奇偶監(jiān)督編碼的碼元按行排成方陣，但傳送時則按列進行的順序傳送。接收端仍將碼元排成發(fā)送時的方形陣式，然后再進行奇偶校驗。如： 發(fā)送時按順序傳送 111011100110000…10101 。以此來抗突發(fā)性錯誤。 29 水平垂直奇偶校驗碼 在水平奇偶監(jiān)督碼的基礎上，對方陣中的每一列也進行奇偶校驗。發(fā)送時按列序順次傳送，接收端恢復成方陣后進行奇偶校驗，如： 傳送順序為 111010110011100001…101011 ，它能發(fā)現某一行或某一列上所有奇數個誤碼。 30 群計數碼 監(jiān)督碼組中“ 1”的個數構成所謂群計數碼。例如一個碼組的信息碼元為 1010111，其中有 5個“ 1”，用二進制表示為 101，將它作為監(jiān)督碼元附加在信息碼元之后，傳輸碼組為 1010111101。 為了提高檢突發(fā)錯誤的能力，也可以仿照水平奇偶方法，將信息排成方陣，按列發(fā)送。 31 恒比碼 在恒比碼中，每個碼組中“ 1”（或“ 0”）的個數相同，因而稱為等重碼。檢測時，只要計算每個碼組中“ 1”的數目是否對，就能判斷有無錯誤。 我國電傳機傳輸漢字電碼的通信中，廣泛采用五單位數字保護電碼。每個碼組長度為 5，共有 25=32種組合，其中“ 1”的個數為 3的編碼正好 10個，分別代表阿拉伯數字（ 1~10）。 101011； 211001； 310110； 411010； 500111； 610101； 711100；801110； 910011； 1001101。 在國際 ARQ電報通信系統(tǒng)中，它采用 3個“ 1”、 4個“ 0”的恒比碼， 7中取 3共有 35個許用碼組，分別代表 26個字母及其它符號。 32 漢明（ Hamming)碼 漢明碼是 1950年由美國貝爾實驗室漢明提出來的，是第一個設計用來糾正錯誤的線性分組碼，漢明碼被廣泛用于數字通信和數據存儲系統(tǒng)中。 對于奇偶校驗的偶校驗，我們用下式作為作為 監(jiān)督方程。 021 ... aaaS nn ???? ?? 在接收端譯碼時，若 S=0，就認為無錯。 若 S=1，就認為有錯。 這里稱 S為校正子（校驗子），又稱伴隨式。 33 漢明（ Hamming)碼 在上例中，由于只有一位監(jiān)督碼元，一個監(jiān)督方程，所以只能檢錯，無法糾錯。 漢明碼（ n,k)是一種可用于糾單個隨機錯誤的循環(huán)編碼。一般漢明碼的參數如下： 碼長 n=2r1 信息位 k=2r1r 監(jiān)督位