【正文】 第 3章 分組碼 第 3章 分組碼 糾、檢錯(cuò)編碼的基本概念 線性分組碼 循環(huán)碼 BCH碼 習(xí)題 第 3章 分組碼 糾、檢錯(cuò)編碼的基本概念 為了降低錯(cuò)誤概率 pe及使接收端具備檢錯(cuò)、糾錯(cuò)能力，我們這樣來(lái)對(duì)待傳消息進(jìn)行編碼。選碼 C1={00000， 11111}，作映射： 即消息中的每一符號(hào)比特按其重復(fù)的 5比特碼字來(lái)表示，并由發(fā)送端傳送。接收端按選大原則進(jìn)行譯碼，在接收的 5比特矢量中，哪個(gè)符號(hào)多就譯為哪個(gè)。例如接收為 10110，則譯為 11111。消息的編碼、譯碼關(guān)系見(jiàn)表 。 0 00 00 0 , 1 11 11 1??第 3章 分組碼 表 消息的編碼、譯碼關(guān)系 第 3章 分組碼 定義 ， x=(x1， x2， … ， xn)， y=(y1，y2， … ， yn)，稱(chēng) dist(x， y)=|{i|xi≠yi， i=1， 2， … ， n}| () 為碼字 x與 y的漢明距離。 碼字間的漢明距離滿(mǎn)足下列三角不等式： dist(x， y)≤dist(x， z)+dist(z， y) () 在一個(gè)碼中，任意兩個(gè)不同碼字間漢明距離的最小者稱(chēng)為這個(gè)碼的最小漢明距離。 C??x, y()C??x, y , z第 3章 分組碼 定義 設(shè)有碼 C，稱(chēng) () 為碼 C的最小漢明距離。 在一個(gè)碼中，碼字中非零碼元的數(shù)目也是一個(gè)重要的參數(shù)，這個(gè)參數(shù)通常稱(chēng)為碼字的漢明重量。 ? ?? ?dis t( ) m in dis t | ,CC? ? ? ?x, y x, y x y　第 3章 分組碼 定義 設(shè)有碼 C， ，稱(chēng) wt(x)=|{i|xi≠0， i=1， 2， … ， n}| () 為碼字 x的漢明重量。 定義 設(shè)有碼 C， 0 =(0， … ， 0) wt(C)=min{wt(x)|x∈ C， x≠0} () 為碼 C的最小漢明重量。 ? ?12, , , , nC x x x? ? ?xx第 3章 分組碼 例 設(shè)有碼 C2=(a1， a2， a3， a4， a5， a6， a7， a8)，式中 a1=(0000000) a2=(0011101) a3=(0100111) a4=(0111010) a5=(1001110) a6=(1010011) a7=(1101001) a8=(1110100) 求 dist(a2， a4)， dist(a3， a7)， wt(a8)， dist(C2)， wt(C2)。 解 dist(a2， a4)=4， dist(a3， a7)=4， wt(a8)=4， dist(C2)=4， wt(C2)=4 第 3章 分組碼 定義 設(shè)有碼 C，如果 ，有 x+y∈ C，則稱(chēng)碼 C是線性碼。 所有的這樣 2k個(gè)碼字構(gòu)成的集合稱(chēng)為分組碼。須注意一點(diǎn)， n－ k個(gè)校驗(yàn)元可以放在碼字中的任何位置，如果碼字前k位固定為信息碼，則這種分組碼稱(chēng)為系統(tǒng)分組碼，如圖 所示。 圖 系統(tǒng) (n， k)分組碼碼字結(jié)構(gòu) , C??xy第 3章 分組碼 定義 將 k位信息碼通過(guò)一定的規(guī)則添加 n－ k個(gè)校驗(yàn)元而形成長(zhǎng)為 n的碼字，如果所有這樣的碼字組成一個(gè)線性碼，則稱(chēng)為 (n， k)線性分組碼。 定義 稱(chēng) (n， k)線性分組碼的 為碼率。 kR n?第 3章 分組碼 例 構(gòu)造奇偶校驗(yàn)碼。對(duì) X={0， 1}的 k維擴(kuò)展信源Xk添加一位校驗(yàn)位形成一個(gè)長(zhǎng)為 k+1的碼字，即 且滿(mǎn)足關(guān)系： x1+x2+…+ xk+xk+1=0 (偶校驗(yàn) ) () 即信息碼 (x1x2… xk)中如有偶數(shù)個(gè) 1，則 xk+1=0，如有奇數(shù)個(gè) 1，則 xk+1=1。 或 x1+x2+…+ xk+xk+1=1 (奇校驗(yàn) ) () 即信息碼 (x1x2… xk)中如有偶數(shù)個(gè) 1，則 xk+1=1，否則 xk+1=0。 ? ? ? ?1 2 1 2 1k k kx x x x x x x ??第 3章 分組碼 解 僅討論偶校驗(yàn)，所得結(jié)論適合于奇校驗(yàn)。設(shè)發(fā)送碼字 (x1x2… xkxk+1)，接收矢量為 (y1y2… ykyk+1)，如果無(wú)錯(cuò)，則接收矢量應(yīng)滿(mǎn)足式 ()；如果產(chǎn)生奇數(shù)個(gè)錯(cuò)誤，則 y1+y2+…+ yk+yk+1=1， 因?yàn)橐粋€(gè)碼元 x發(fā)生錯(cuò)誤意味著這個(gè)碼元變?yōu)閤+1，為討論方便，不防設(shè) y1， y2， … ， y2r+1發(fā)生錯(cuò)誤，于是 y1+y2+…+ yk+yk+1=(1+x1)+(1+x2)+…+(1+ x2r+1)+x2r+2+…+ xk+xk+1 =(2r+1)+(x1+x2+…+ xk+xk+1) =2r+1=1 (mod2) 說(shuō)明不滿(mǎn)足式 ()，從而發(fā)現(xiàn)錯(cuò)誤，但無(wú)法判別哪些碼元、多少碼元出錯(cuò)，所以無(wú)糾錯(cuò)能力。 第 3章 分組碼 如果是偶數(shù)個(gè)錯(cuò)誤，則有 y1+y2+…+ yk+yk+1=2r+(x1+x2+…+ xk+xk+1)=2r=0 (mod2) 說(shuō)明滿(mǎn)足式 ()，因而無(wú)法檢出錯(cuò)誤。 綜合起來(lái)，奇偶校驗(yàn)碼能檢奇數(shù)個(gè)錯(cuò)誤，不能檢偶數(shù)個(gè)錯(cuò)誤，無(wú)糾錯(cuò)能力，碼率為 。 111kRkn? ? ??第 3章 分組碼 定理 在一個(gè)線性分組碼中，碼的最小漢明距離等于碼的最小漢明重量。 證明 設(shè) C是線性分組碼，則 0∈ C，再設(shè) x∈ C，滿(mǎn)足wt(x)=wt(C)，即有 dist(C)≤dist(x， 0)=wt(x)=wt(C) 另一方面，設(shè) x， y∈ C且 dist(x， y)=dist(C)，因?yàn)? ，且 wt(z)=dist(x， y)， 所以 wt(C)≤wt(z)=dist(x， y)=dist(C) 故 dist(C)=wt(C) de f C??z x y第 3章 分組碼 定理 對(duì)一個(gè)二元 (n， k)線性分組碼 C，有 (1) 能糾正 t個(gè)錯(cuò)誤的充要條件是 dist(C)=2t+1； (2) 能檢測(cè) s個(gè)錯(cuò)誤的充要條件是 dist(C)=s+1； (3) 能糾正 t個(gè)錯(cuò)誤，并能發(fā)現(xiàn) s(st)個(gè)錯(cuò)誤的充要條件是dist(C)=t+s+1。 證明 只證結(jié)論 (1)，其余省略。設(shè)發(fā)送碼字為 x，接收矢量為 y， z是 C中不等于 x的任意碼字。 ① 必要性。假設(shè) x傳送后發(fā)生了 r(≤t)個(gè)錯(cuò)誤，則有 dist(x， y)=r≤t 由漢明距離的三角不等式 ()，有 dist(z， y)≥dist(x， z)－ dist(x， y) ≥dist(C)－ dist(x， y)=2t+1－ r≥t+1 () 第 3章 分組碼 式 ()說(shuō)明接收矢量 y最像碼 C中的 x，按選大原則，接收端能正確譯出碼 x，即糾正了矢量 y中的 r個(gè)錯(cuò)誤。 ② 充分性。使用反證法。假設(shè) dist(C)2t+1，那么必定存在兩個(gè)不同的碼字 x=(x1， x2， … ， xn)和 z=(z1， z2， … ， zn)滿(mǎn)足 dist(x， z)2t+1。由碼字間距離的定義， x與 z間至多有2t個(gè)碼元對(duì)應(yīng)不同，分兩種情況來(lái)討論。 情況 1：設(shè) x與 z間有 2r′(2t+1)個(gè)碼元對(duì)應(yīng)不同。不妨設(shè) ， j=1， 2， … ， 2r′。取矢量 y=(y1， y2， … ， yn)，式中： jjiixz?第 3章 分組碼 于是 ，由 r′≤t得到 dist(x， y)=r′≤t 且 dist(z， y)=r′≤t () ? ?, 1 , 2 , , 1 , , 2, 1 , 2 , , , 1 , 2 , , 2jjjjiiiik k k jy x j ry z j r ry x z k n k i j r? ???????? ? ????? ? ? ? ??? 且第 3章 分組碼 情況 2：設(shè) x與 z間有 2r′+1(2t+1)個(gè)碼元對(duì)應(yīng)不同。不妨設(shè) ， j=1， 2， … ， 2r′+1。取矢量 y=(y1， y2， … ，yn)，式中： 于是 ，由 r′≤t－ 1得到 dist(x， y)=r′+1≤t 且 dist(z， y)=r′≤t－ 1 () jjiixz?? ?, 1 , 2 , , 1 , , 2 , 2 1, 1 , 2 , , , 1 , 2 , , 2 1jjjjiiiik k k jy x j ry z j r r ry x z k n k i j r? ?????? ? ?? ? ? ????? ? ? ? ? ??? 且第 3章 分組碼 線 性 分 組 碼 線性分組碼的編碼方法 1. (n， k)線性分組碼的校驗(yàn)矩陣 H 構(gòu)造線性分組碼的關(guān)鍵在于校驗(yàn)元的選取規(guī)則，雖然有相同的信息碼和相同的校驗(yàn)元數(shù)目，但不同校驗(yàn)元的選取規(guī)則所產(chǎn)生的線性分組碼的糾、檢錯(cuò)能力是不同的。為了說(shuō)明問(wèn)題，我們來(lái)考慮在信源 X={0， 1}的三維擴(kuò)展信源 X3上編一組 (7， 3)線性分組碼，校驗(yàn)元按滿(mǎn)足下列約束方程來(lái)選取，即 第 3章 分組碼 式中， (c6， c5， c4， c3， c2， c1， c0)為 (7， 3)線性分組碼的任意一個(gè)碼字， (c6， c5， c4)為信息碼。 6 4 36 5 4 26 5 15400000c c cc c c cc c cc c c? ? ???? ? ? ???? ? ??? ? ? ??() 第 3章 分組碼 為了便于討論，將式 ()寫(xiě)成矩陣形式： 簡(jiǎn)記為 HcT=0T () () 65432101 0 1 1 0 0 0 01 1 1 0 1 0 0 01 1 0 0 0 1 0 00 1 1 0 0 0 1 0ccccccc??????? ? ? ???? ? ? ???? ? ? ????? ? ? ???? ? ? ???? ? ? ???????第 3章 分組碼 式中： c=(c6， c5， c4， c3， c2， c1， c0) 0=(0， 0， 0， 0) 式 ()是重要的，一個(gè)長(zhǎng)度為 7的矢量是 (7， 3)線性分組碼的碼字的充要條件是滿(mǎn)足式 ()。因此，式 ()和矩陣 H是進(jìn)行編碼的關(guān)鍵。 () 1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1?????????H第 3章 分組碼 一般地， (n， k)線性分組碼是通過(guò)下面的方程來(lái)獲得校驗(yàn)元的，即 將其寫(xiě)成矩陣形式，有 HcT=0T () () ? ?? ?? ? ? ? ? ? ? ? ? ?11 1 12 2 1 1 01121 1 22 2 1 2 0211 2 1 01 2 1000n n nnn n nnnnn k n k n k n n k nh c h c h c h ch c h c h c h ch c h c h c h c?? ??? ???? ? ? ? ?? ? ? ? ???? ? ? ? ????? ? ? ? ? ??第 3章 分組碼 式中： () ? ?? ?? ? ? ? ? ? ? ? ? ?11 12 11121 22 2211 2 1nnnnn k n k n k n n k nh h h hh h h hh h h h??? ? ? ? ??????????H? ?1 2 1 0, , , ,nnc c c c???c第 3章 分組碼 定義 稱(chēng)式 ()為校驗(yàn)方程，稱(chēng)矩陣 H為校驗(yàn)矩陣。 由線性代數(shù)的知識(shí)我們知道，經(jīng)過(guò)行初等變換校驗(yàn)矩陣H可以轉(zhuǎn)化為如下形式： 式中， In－ k是 n－ k階單位矩陣。 ? ? ? ? ? ?? ?11 12 121 22 212de f1 0 00 1 000 0 1,kkn k n k n k kn