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