【正文】 碼）：上式經(jīng)過移項運算，解出監(jiān)督位給定信息位后，可以直接按上式算出監(jiān)督位 ， 結(jié)果見下表：17第 11章差錯控制編碼信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0信息位a6 a5 a4 a3監(jiān)督位a2 a1 a00000 000 1000 1110001 011 1001 1000010 101 1010 0100011 110 1011 0010100 110 1100 0010101 101 1101 0100110 011 1110 1000111 000 1111 11118第 11章差錯控制編碼216。這就意味著 a2 、 a a5和 a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：同理， a a a5和 a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：以及 a0、 a a4 和 a6構(gòu)成偶數(shù)監(jiān)督關(guān)系16第 11章差錯控制編碼216。可見，漢明碼是一種高效碼。因此，這種碼能夠糾正 1個錯碼或檢測 2個錯碼。由于校正子 S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。p 在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位 a0，它和信息位 an1 … a1一起構(gòu)成一個代數(shù)式：在接收端解碼時，實際上就是在計算若 S = 0，就認為無錯碼；若 S = 1，就認為有錯碼。12第 11章差錯控制編碼n 漢明碼能夠糾正 1位錯碼且編碼效率較高的一種線性分組碼。u 線性分組碼 ：按照一組線性方程構(gòu)成的分組碼 。u 線性碼 ：按照一組線性方程構(gòu)成的代數(shù)碼。 例如，若信息位為 11001，則碼組為 1100111001；若信息位為 10001，則碼組為 1000101110。 當(dāng)信息位有偶數(shù)個 “1”時，監(jiān)督位是信息位的反碼。其編碼規(guī)則為：216。其中的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與信息碼元相同或者相反則由信息碼中 “1”的個數(shù)而定。對于信源來的二進制隨機數(shù)字序列，這種碼就不適合使用了。u 這種碼在檢測時，只要計算接收碼組中 “1”的數(shù)目是否對，就知道有無錯碼。9第 11章差錯控制編碼n 恒比碼u 在恒比碼中，每個碼組均含有相同數(shù)目的 “1”（和 “0”）。奇數(shù)監(jiān)督碼與偶數(shù)監(jiān)督碼相似，只不過其碼組中 “1”的數(shù)目為奇數(shù)：8第 11章差錯控制編碼n 二維奇偶監(jiān)督碼（方陣碼）u 二維奇偶監(jiān)督碼的構(gòu)成它是先把上述奇偶監(jiān)督碼的若干碼組排成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位，如下圖所示圖中 a01 a02 ? a0m為 m行奇偶監(jiān)督碼中的 m個監(jiān)督位。這種編碼能夠檢測奇數(shù)個錯碼。6第 11章差錯控制編碼u 碼距和檢糾錯能力的關(guān)系p 一種編碼的最小碼距 d0的大小直接關(guān)系著這種編碼的檢錯和糾錯能力p 為檢測 e個錯碼，要求最小碼距 d0 ? e + 1p 為了糾正 t個錯碼，要求最小碼距 d0 ? 2t + 1p 為糾正 t個錯碼，同時檢測 e個錯碼，要求最小碼距 7第 11章差錯控制編碼l n 奇偶監(jiān)督碼u 奇偶監(jiān)督碼分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩種，兩者的原理相同。p 最小碼距 ：把某種編碼中各個碼組之間距離的最小值稱為最小碼距 (d0)。碼距又稱 漢明距離 。 5第 11章差錯控制編碼u 分組碼的碼重和碼距p 碼重 ：把碼組中 “1”的個數(shù)目稱為碼組的重量，簡稱 碼重。p 在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。u 理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。u 編碼效率 (簡稱 碼率 ) ：設(shè)編碼序列中信息碼元數(shù)量為 k，總碼元數(shù)量為 n，則比值 k/n 就是碼率。u 多余度 ：就是指增加的監(jiān)督碼元多少。1第 11章差錯控制編碼l 概述n 信道分類：從差錯控制角度看u 隨機信道：錯碼的出現(xiàn)是隨機的 u 突發(fā)信道：錯碼是成串集中出現(xiàn)的u 混合信道：既存在隨機錯碼又存在突發(fā)錯碼 n 差錯控制技術(shù)的種類u 檢錯重發(fā)u 前向糾錯 u 反饋校驗u 檢錯刪除 2第 11章差錯控制編碼n 差錯控制編碼：常稱為 糾錯編碼u 監(jiān)督碼元： 在發(fā)送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監(jiān)督碼元。 u 不同的編碼方法，有不同的 檢錯 或 糾錯 能力。例如，若編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，則這種編碼的多余度為 1/3。u 冗余度： 監(jiān)督碼元數(shù) (nk) 和信息碼元數(shù) k 之比。3第 11章差錯控制編碼 糾錯編碼的基本原理u 分組碼的結(jié)構(gòu)p 將信息碼分組，為每組 信息碼 附加若干 監(jiān)督碼 的編碼稱為 分組碼 。 p 信息位和監(jiān)督位的關(guān)系：舉例如下信息位 監(jiān)督位晴 00 0云 01 1陰 10 1雨 11 04第 11章差錯控制編碼p 分組碼的一般結(jié)構(gòu)u 分組碼的符號： (n, k)p N － 碼組的總位數(shù)，又稱為碼組的長度（碼長），p k － 碼組中信息碼元的數(shù)目，p n – k ＝ r － 碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。p 碼距 ：把兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱 碼距 。p 例如， “000”＝晴， “011”＝云， “101”＝陰， “110”＝雨，4個碼組之間，任意兩個的距離均為 2。例如，上面的編碼的最小碼距 d0 = 2。在偶數(shù)監(jiān)督碼中，無論信息位多少，監(jiān)督位只有 1位，它使碼組中 “1”的數(shù)目為偶數(shù)，即滿足下式條件：式中 a0為監(jiān)督位，其他位為信息位。在接收端，按照上式求 “模 2和 ”，若計算結(jié)果為 “1”就說明存在錯碼，結(jié)果為 “0”就認為無錯碼。1 2 ? c1 c0為按列進行第二次編碼所增加的監(jiān)督位，它們構(gòu)成了一監(jiān)督位行。由于 “1”的數(shù)目與 “0”的數(shù)目之比保持恒定，故得此名。u 恒比碼的主要優(yōu)點是簡單和適于用來傳輸電傳機或其他鍵盤設(shè)備產(chǎn)生的字母和符號。10第 11章差錯控制編碼n 正反碼u 正反碼的編碼：p 它是一種簡單的能夠糾正錯碼的編碼。p 例如，若碼長 n = 10，其中信息位 k = 5，監(jiān)督位 r = 5。 當(dāng)信息位中有奇數(shù)個 “1”時，監(jiān)督位是信息位的簡單重復(fù)；216。216。11第 11章差錯控制編碼l 線性分組碼n 基本概念u 代數(shù)碼 ： 建立在代數(shù)學(xué)基礎(chǔ)上的編碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。本節(jié)將以 漢明碼 為例引入線性分組碼的一般原理。u 漢明碼的構(gòu)造原理?，F(xiàn)將上式稱為 監(jiān)督關(guān)系式 ， S稱為 校正子 。 13第 11章差錯控制編碼p 如果希望用 r個監(jiān)督位構(gòu)造出 r個監(jiān)督關(guān)系式來指示 1位錯碼的 n種可能位置，則要求14第 11章差錯控制編碼p 例： 以分組碼 (n, k)中的（ 7,4）漢明碼為例 ， 用 S S2和 S3表示 3個監(jiān)督關(guān)系式中的校正子，則 S S2和 S3的值與錯碼位置的對應(yīng)關(guān)系可以規(guī)定如下表所列：S1 S2 S3 錯碼位置 S1 S2 S3 錯碼位置001 a0 101 a4010 a1 110 a5100 a2 111 a6011 a3 000 無錯碼漢明碼的最小碼距 d0 = 3。由于碼率 k/n = (n r) /n =1 – r/n，故當(dāng) n很大和 r