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