【正文】 ， 譯碼已不可靠 。? 比如，當收碼 R＝ (10100)時，根據碼表譯出的碼字是(10111)，與收碼 R的漢明距離是 2，然而收碼 R與全零碼字 (00000)的漢明距離也是 2，為什么不能譯成(00000)呢？? 事實上，碼表的第 8行本身就 不是唯一的 。注意在碼表計算過程中，伴隨式 (011)所對應的 4個差錯圖案中有兩個并列重量最輕，如果當時選的不是(00011)而是 (10100)，那么碼表第 7行就不是現在這樣了。? 因此：伴隨式的個數與 n、 k， n、 k與糾錯能力 t之間存在一定的數字關系！? [例 ]已知二元 (4， 2)系統(tǒng)碼 C， 生成矩陣與一致校驗矩陣分別為? 其 標準陣列 如表所示。? 該陣列的第一行是 4個碼字，其中零碼字排在左邊，? 然后在剩下的 12個碼字中，挑選一個重量最小的碼字，例如 (1000)，作為第二行的陪集首。將 (1000)與第一行中所有的碼字相加，就得到第二行。? 接著，在剩下的 8個矢量中選取 (0100)為第三行的陪集首，等等。? 在這個例子中，陪集首重量皆為 1的碼字，但對于其他的碼，陪集首的重量可能為 2， 3， 4， …… 。表 (4， 2)線性碼的標準陣列? 假定接收碼字 R＝ (1010)， 在表中的第 3行第 4列中找到了它，于是就可以把 R譯成位于第 4列的碼字 M＝ (1110)。? 顯然，位于第 3行的陪集首 (0100)是差錯圖樣 E， 表示信道第 2位有錯。? 由此可見，能否正確譯碼的關鍵在于信道差錯圖樣是否是陪集首。因為將 R譯為與它最接近的碼字 M， 所以符合最大似然譯碼準則。? 又例，設 (6， 3)碼的生成矩陣為表 (6， 3)線性碼的標準陣列 ? 用表中的標準陣列譯碼，可糾正一位差錯的全部差錯圖樣和一種兩位差錯的差錯圖樣。如發(fā)送碼字為 C＝ (101011)， E＝ (010000)， 則接收碼字 R＝ C＋ E＝(111011)。? 查看標準陣列可知它所在子集的估值? ＝ (101011)，因此譯碼正確。? 又如同一碼字，但它的差錯圖樣為 E＝ (001100)??? 它不在陪集首，由于 R＝ (101011)＋ (001100)＝(100111)， 與此 R對應的? ＝ (100110)≠C， 屬于錯誤譯碼。 標準陣列譯碼的簡化? 原則上講，用 標準陣列譯碼要存儲 2n個 n重碼字 。? 當 n很大時，這是不實際的。如當 C為碼長 100的二元碼時， C的標準陣列由 2100個陣元組成，譯碼器必須存儲它們，譯碼時還必須從中搜索接收碼字 R， 這在工程實踐上是很難實現的。然而標準陣列的下列性質可使譯碼過程簡化。? 定理 ：在標準陣列中， 一個陪集 (表中一行 )的所有 2k個 n重碼字有 相同的伴隨式 ，不同陪集的伴隨式互不相同。? 于是，任意 n重碼字的 伴隨式取決于 它在標準陣列中所在陪集的 陪集首陪集首 ；? 標準陣列的 陪集首和伴隨式是一一對應 的，因而碼的可糾 差錯圖樣 和伴隨式是一一對應的。? 因此： 實際譯碼器只需要存儲實際譯碼器只需要存儲 陪集首陪集首 集合即集合即可可 。? 證明? 設 H為給定 (n， k)線性碼的校驗矩陣，在陪集首為 Ey的陪集中的任意碼字 R為? ?? R＝ Ey＋ Ci， i＝ 1， 2， …， 2k? 其伴隨式為? S＝ RHT＝ (Ey＋ Ci)HT＝ EyHT＋ CiHT＝ EyHT ? 上式表明，陪集中任意碼字的伴隨式等于陪集首的伴隨式。因此，同一陪集中所有矢量的伴隨式相同。不同陪集中，由于陪集首不同，所以伴隨式也不同。標準陣列譯碼的步驟? 應用此對應關系可以構成比標準陣列 簡單得多的譯碼表，從而得到 (n， k)線性碼的一般 譯碼步驟 ： ?? (1)計算接收碼字 R的 伴隨式 ST＝ HRT。? (2)根據伴隨式和最大似然譯碼原則下的差錯圖樣一一對應的關系，利用伴隨式譯碼表，由伴隨式譯出 R的 差錯圖樣 E。? (3)將接收碼字減差錯圖樣，得發(fā)送碼字的 估值 。? 上述譯碼法稱為 伴隨式譯碼法 或 查表譯碼法 。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯誤概率。? 這種方法原則上可用于任何 (n， k)線性碼。? 實際上，實現譯碼的關鍵是第 2步－求差錯圖樣上，一般要用組合邏輯電路。當 nk較大時，組合邏輯電路將變得很復雜，甚至不切實際。? 參見參考教材 P254 例? 結論： 實際譯碼器只需要存儲陪集首集合即可。 碼距、糾錯能力、 MDC碼及重量譜? N重碼矢 c=(1,2,…c 1,c0)可與 N維矢量空間 XN中的一個 點 對應，全體碼字所對應的點構成矢量空間里的一個子集；? 發(fā)碼一定在這個子集里，傳輸無誤時的收碼也一定位于該子集（許用碼字）；? 當出現差錯時，接收的 N重矢量：– 對應到子集外空間某一點– 對應到該子集，卻對應到該子集的另一點上集合的觀點? 設 (n， k)線性碼用來糾錯，發(fā)送碼字取自于 2k個碼字 集合 {Ci}。 碼字經信道傳輸后，接收碼字 R可以是 2n個 n重矢量 中任一個矢量。? 任何譯碼方法，都是把 2n個 n重矢量劃分為 2k個互不相交的子集 D1， D2， … ， Ｄ 2k， 使得在每個子集中僅含一個碼字 。? 根據碼字和子集的一一對應關系，若接收碼字Rx落在子集 Dx中，就把 Rx譯為子集 Dx含有的碼字 Cx。 所以，當接收碼字 R與實際發(fā)送碼字在同一子集中時，譯碼就是正確的。 ?漢明重量? 在信道編碼中，定義碼字中非零碼元 (“1”)的數目為碼字的 漢明 (Hamming)重量 ，或 碼組 /碼字重量 ，簡稱重。? 顯然，不同碼字的漢明重量是不同的。例如“010”碼字的碼重為 1， “011”碼字的碼重為 2。? 非零碼字中，重量最小者稱為該碼的 最小最小 漢明重量 。漢明距離? 把兩個碼字中對應碼元位置上具有不同碼元的位數定義為 兩個碼字之間的 漢明 (Hamming)距離 ，或 碼字（組）距離 ，簡稱 碼距 。? 在一種編碼中，任意兩個合法碼字 (許用碼字 )間距離的最小值，即碼字集合中任意兩碼字間的最小距離，稱為這一編碼的 最小最小 漢明距離 ，以 dmin表示。td=7dmin=3d=5C1C2C3C4C5? 碼集各碼字間的距離是不同的，碼距最小者決定碼的特性，即： 最小碼字距離 dmin。? 用 d(C1， C2)表示兩個 n重 C C2之間的漢明距離，則 漢明距離 有以下三個性質：? (1)對稱性： d(C1， C2)=d(C2， C1)； ?? (2)非負性： d(C1， C2)≥0； ?? (3)滿足距離三角不等式： d(C1， C2)≤d(C1，C3)+d(C3， C2)。? 逐一計算各個碼字之間的漢明距離是非常麻煩的。? 由于線性分組碼的各個碼字之和滿足封閉性，因此， 兩個碼字之間漢明距離即為某一個（單個）碼字的漢明重量 ！? 定理 線性分組碼的 最小距離 等于碼集中 非零碼字的最小重量 ：? dmin=min{w(Ci)} Ci?C及 Ci?0? 定理 任何 最小距離 dmin的 線性分組碼 ，其最大 檢錯能力 為 (dmin1)，? 最大糾錯能力 t為? 在一般情況下，線性分組碼的檢錯、糾錯能力與最小碼距的數量關系有以下結論：? (1)檢測 e個錯碼，則要求最小碼距：? dmin － 1 ≥e? 或者說：? 若一種編碼的最小距離為 dmin， 則它最多能 檢出 (dmin1)個錯碼。? (2)糾正 t個錯碼，則要求最小碼距為：? （ dmin － 1 ） /2 ≥t? 或者說：? 若一種編碼的最小碼距為 dmin， 則它最多能 糾正 (dmin1)/2個錯碼。? (3)糾正 t個錯碼，同時能檢測 e(et)個錯碼，則要求最小碼距為? dmin≥e+t+1,et? 這里所述能糾正 t個錯碼，同時能檢測 e個錯碼的含義，是指：? 當錯碼不超過 t個時錯碼能自動予以糾正，而當錯碼超過 t個時，則不可能糾正錯誤，但仍可檢測 e個錯碼 ，這正是混合檢錯、糾錯的控制方式。? 例如，在 3位二元碼字中：如果 8種碼字都作為許用碼字時，任兩組碼間的最小距離 dmin = 1；如果只選 4種碼組為許用碼字時，最小碼距dmin=2， 若選用兩種許用碼字時， dmin=3。? 參見教材前面的例子 P132： dmin=3， 糾錯能力是 1，檢錯能力是 2。? 最小距離 dmin與 碼率 R是碼的兩個最主要參數， dmin表示了碼的糾錯能力。? 可以用 (n， k， d)表示最小距離為 d， 碼率R=k/n的線性分組碼。? 糾錯碼的 基本任務 之一就是構造出 R一定且dmin盡可能大的碼，或 dmin一定且 R盡可能大的碼。? 定理 (n,k)線性分組碼最小距離等于 dmin的充要條件是：校驗矩陣 H中有 (dmin1)列線性無關。? 定理 (n,k)線性分組碼的最小距離必定小于或等于 (nk+1)， 即：dmin?(nk+1) ? 例： (7， 4)線性碼? H＝? 各列都不相同，任意 2列之和不等于 0：故兩列線性無關；任意 2列之和一定等于矩陣中某一列：故任意 3列線性相關。? 所以該碼的最小距離為 3，小于 nk+1＝ 4。? 由定理 ： (n,k)線性碼最小距離 dmin的上邊界是 nk+1。? 如果設計的一種 (n,k)線性碼的 dmin達到了 nk+1， 就是達到了設計性能的極點。? 因此， dmin＝ nk+1的碼稱為 極大、最小距離碼 (MDC–Maximized minimum Distance Code)。? 總體的、平均的糾錯能力不但與最小距離有關，而且與其余碼距或者說與碼字的重量分布特性有關。 完備碼 (Perfect code)? 任何一個二元 (n,k)線性分組碼都有 2nk個伴隨式，假如該碼的糾錯能力是 t，則對于任何一個重量小于等于 t的差錯圖案，都應有一個伴隨式與之對應，也就是說，伴隨式的數目滿足條件? 上式稱作 漢明限 ，任何一個 糾 t碼 都應滿足上述條件。? 如果：二元 (n,k)線性分組碼正好能使等式? 成立，即該碼的伴隨式數目不多不少恰好和不大于 t個差錯的差錯圖樣的數目相等，相當于在標準譯碼陣列中能將所有重量不大于 t的差錯圖案選作陪集首，而沒有一個陪集首的重量大于 t，這時的 校驗位得到最充分的利用 。? 這樣的二元 (n,k)線性分組碼稱為 完備碼 。漢明碼 (Hamming Code)? 漢明碼是 1950年由漢明提出的一種能糾正 單個錯誤 (糾錯能力 t=1)的 線性分組碼 。? 它不僅性能好而且編譯碼電路非常簡單，易于工程實現，因此是工程中常用的一種糾錯碼。? 漢明碼不是指一個碼，而是代表 一類碼 。? 漢明碼的，既有二進制的，也有非二進制的。? 漢明碼是一種特殊的 (n， k， d)線性分組碼。對于二進制的碼元，漢明碼的參數 n， k和 d分別為? 碼長 ? 信息位數? 監(jiān)督位數? 最小距離? ? 碼率 ? 二進制時，漢明碼碼長 n和信息位 k服從以下規(guī)律：? (n,k)=(2m1,2m1m)? 其中 m=nk，是正整數。? 當 m＝ 8… 時，有漢明碼 (7,4)、(15,11)、 (31,26)、 (63,57)、 (127,120)、 (255,247)… 。? 漢明碼是完備碼，因為它滿足以下等式。漢明碼校驗矩陣的構成? 漢明碼的校驗矩陣 H具有特殊的性質，能使編碼的構造方法簡化。? 一個 (n,k)碼的校驗矩陣 H有 nk行、 n列，二進制時 nk個監(jiān)督碼元所能組成的 非全 0的列矢量總數是 2nk1,恰好和 校驗矩陣的列數 n=2m1相等。只要排列所有列，通過列置換將矩陣 H轉換成系統(tǒng)形式，就可以進一步得到相應的生成矩陣 G。例 構造一個 m=3的二元 (7， 4)漢明碼。解：先利用漢明碼的特性構造一個 (7， 4)漢明碼的校驗矩陣 H，再通過列置換將它變?yōu)橄到y(tǒng)形式： 0 0 0 1 1 1 1 列置換 1 1 1 0 1 0 0 H = 0 1 1 0 0 1 1 ? 0 1 1 1 0 1 0 = [PT I3] 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩陣 G為 1 0 0 0 1 0 1 G = [I4 ? P] = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 表 (7， 4)漢明碼? 由于漢明碼的 最小距離是 3，故漢明碼能糾正一個隨機錯誤或檢測兩個錯誤，且碼的校驗矩陣 H中任意兩列線性無關。? 漢明碼的校驗矩陣 H由一切 r(r=nk)維非零二元向量排列而成，即 H的列為所有非零的 r維向量組成，所以 H的各列在二元和之下是封閉的，一旦 r給定，就可構造出具體的 (n，