【正文】 錯(cuò)誤圖樣 E=[0001000] 接收到的序列 B=[0000011]，校正子可以由下式計(jì)算得到： ? ??????????????????????????1000100011101010111111100000THBS=(0 1 1) 指示 a3有錯(cuò)誤。 47 校正子 如果不出現(xiàn)誤碼，校正子 S=0。 校正子 S可以根據(jù)接收序列和 H矩陣來計(jì)算。發(fā)送碼組在傳輸過程中出現(xiàn)了誤碼，接收端收到了 B矩陣，也是一 n列的行矩陣。 ?????????????1101000101010001100101110001G 這個(gè)新矩陣 G稱為生成矩陣，因?yàn)榭捎伤a(chǎn)生整個(gè)碼組 A。 或者用下式來計(jì)算，式中的矩陣是 P的轉(zhuǎn)置矩陣，稱為 Q矩陣。如果用虛線分為兩部分，左邊為 P矩陣，是一個(gè) r*k階矩陣；右邊為 Ir矩陣，是一個(gè) r*r階單位方陣。 線性分組碼有三個(gè)重要的運(yùn)算式： 監(jiān)督矩陣 、 生成矩陣 和 校正子 。 41 線性分組碼 線性分組碼定義：分組碼中 信息碼元 和 監(jiān)督碼元 是用線性方程聯(lián)系起來的一種差錯(cuò)控制碼。監(jiān)督碼的計(jì)算方程見下式。 （ 4）設(shè)監(jiān)督位為 n，反饋移位寄存器由 n位的本原多項(xiàng)式設(shè)計(jì)。 （ 2） 4位數(shù)據(jù)發(fā)完后，斷開 S1，將 S2擲向上端，開始送監(jiān)督 位。 346035614562aaaaaaaaaaaa????????? 7位數(shù)據(jù)按 a6,a5,…a1,a0 的順序一起發(fā)送，在接收端按校正子（伴隨式）的組合來判斷在哪一位出現(xiàn)了錯(cuò)誤，并實(shí)時(shí)糾正（將相應(yīng)位取非）。 034631356224561aaaaSaaaaSaaaaS????????????S1 S2 S3 錯(cuò)碼位置0 0 1 a00 1 0 a11 0 0 a20 1 1 a31 0 1 a41 1 0 a51 1 1 a60 0 0 無錯(cuò)36 （ 7， 4）漢明碼舉例 如果傳送 a6,a5,a4,a3共 4位數(shù)據(jù)，要求能自動(dòng)糾正單個(gè)誤碼，須增加 3位監(jiān)督碼 a2,a1,a0。 （因?yàn)橐m t位錯(cuò)誤， dmin大于 2t+1) 最小漢明距離 d=3 下表是 糾錯(cuò)一位 的一般漢明碼結(jié)構(gòu)。 漢明碼（ n,k)是一種可用于糾單個(gè)隨機(jī)錯(cuò)誤的循環(huán)編碼。 這里稱 S為校正子（校驗(yàn)子），又稱伴隨式。 021 ... aaaS nn ???? ?? 在接收端譯碼時(shí)，若 S=0，就認(rèn)為無錯(cuò)。 32 漢明（ Hamming)碼 漢明碼是 1950年由美國(guó)貝爾實(shí)驗(yàn)室漢明提出來的，是第一個(gè)設(shè)計(jì)用來糾正錯(cuò)誤的線性分組碼，漢明碼被廣泛用于數(shù)字通信和數(shù)據(jù)存儲(chǔ)系統(tǒng)中。 101011； 211001； 310110； 411010； 500111； 610101； 711100；801110； 910011； 1001101。 我國(guó)電傳機(jī)傳輸漢字電碼的通信中，廣泛采用五單位數(shù)字保護(hù)電碼。 31 恒比碼 在恒比碼中，每個(gè)碼組中“ 1”（或“ 0”）的個(gè)數(shù)相同，因而稱為等重碼。例如一個(gè)碼組的信息碼元為 1010111，其中有 5個(gè)“ 1”，用二進(jìn)制表示為 101，將它作為監(jiān)督碼元附加在信息碼元之后，傳輸碼組為 1010111101。發(fā)送時(shí)按列序順次傳送，接收端恢復(fù)成方陣后進(jìn)行奇偶校驗(yàn)，如： 傳送順序?yàn)?111010110011100001…101011 ，它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個(gè)誤碼。以此來抗突發(fā)性錯(cuò)誤。接收端仍將碼元排成發(fā)送時(shí)的方形陣式，然后再進(jìn)行奇偶校驗(yàn)。 奇偶校驗(yàn)碼只能發(fā)現(xiàn)奇數(shù)個(gè)誤碼，對(duì)檢測(cè)突發(fā)錯(cuò)誤不適用。 編碼規(guī)則是：首先將要傳送的信息分成組，然后將各位二進(jìn)制信息加監(jiān)督位用模 2和。為了檢查字符傳輸過程中是否有誤，常在 7比特碼組后碼組后加 1位作為奇偶校驗(yàn)位。在一般情況下，對(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ò)碼，又稱奇偶校驗(yàn)碼，在計(jì)算機(jī)數(shù)據(jù)通信中得到廣泛應(yīng)用。 如果只有 2個(gè)碼組可用，分別選（ 111，000）（ 100， 011）（ 110， 001）（ 101，010），各點(diǎn)之間相差 3個(gè)邊長(zhǎng)，最小碼距為 3。 24 25 對(duì)于如圖所示的 3位二進(jìn)制碼，如果 8個(gè)碼組可用，（ 000， 001， 010， 011， 100， 101，110， 111），各點(diǎn)之間最小相差 1個(gè)邊長(zhǎng)，最小碼距為 1。 碼距 ：兩個(gè)碼組中對(duì)應(yīng)碼位上具有的不同二進(jìn)制碼元的個(gè)數(shù)定義為兩個(gè)碼組的距離（漢明距，簡(jiǎn)稱碼距），如 111和 000，碼距為3， 111和 100碼距為 2， 111和 110碼距為 1。 23 碼距與檢錯(cuò)和糾錯(cuò)能力 定義： 碼重 ：碼組中非零碼元的個(gè)數(shù)。如將 000（晴）誤傳成 101（云）。 22 4個(gè)狀態(tài)只用 2位二進(jìn)制碼就可以表達(dá)，所增加的第 3位，就稱為監(jiān)督碼元。 21 以一組二進(jìn)制碼為例 三位二進(jìn)制碼元有 8個(gè)碼組，如果用來表示天氣的 8種情況 000（晴）， 001（雷）， 010（雹）， 011（陰）， 100（風(fēng)）， 101（云），110（雨）， 111（雪），如果有一個(gè)誤碼，接收端以為是另一條信息，這種編碼沒有檢錯(cuò)和糾錯(cuò)能力。 糾錯(cuò)編碼的的基本思想就是在被傳送的信息碼元中附加一些監(jiān)督碼元，在兩者之間建立某種校驗(yàn)關(guān)系，當(dāng)這種校驗(yàn)關(guān)系因傳輸錯(cuò)誤而受到破壞時(shí)，可以被發(fā)現(xiàn)并予以糾正 。 20 檢錯(cuò)和糾錯(cuò)的基本原理 香農(nóng)著名的信道編碼定理指出：對(duì)于一個(gè)給定的有擾信道，若信道容量為 C，只要發(fā)送端以低于C的速率 R發(fā)送信息，則一定存在一種編碼方法，使編碼錯(cuò)誤概率 P隨著碼長(zhǎng) n的增加，按指數(shù)下降到任意小的值。其中代數(shù)碼建立在近代數(shù)學(xué)基礎(chǔ)上，是目前發(fā)展最為完善的編碼，其中線性碼是是代數(shù)碼的一個(gè)最重要