【正文】 ，則稱為 (n， k)線性分組碼。 kR n?第 3章 分組碼 例 構(gòu)造奇偶校驗(yàn)碼。 或 x1+x2+…+ xk+xk+1=1 (奇校驗(yàn) ) () 即信息碼 (x1x2… xk)中如有偶數(shù)個(gè) 1，則 xk+1=1，否則 xk+1=0。設(shè)發(fā)送碼字 (x1x2… xkxk+1)，接收矢量為 (y1y2… ykyk+1)，如果無錯(cuò)，則接收矢量應(yīng)滿足式 ()；如果產(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) 說明不滿足式 ()，從而發(fā)現(xiàn)錯(cuò)誤，但無法判別哪些碼元、多少碼元出錯(cuò)，所以無糾錯(cuò)能力。 綜合起來，奇偶校驗(yàn)碼能檢奇數(shù)個(gè)錯(cuò)誤，不能檢偶數(shù)個(gè)錯(cuò)誤，無糾錯(cuò)能力，碼率為 。 證明 設(shè) C是線性分組碼，則 0∈ C，再設(shè) x∈ C，滿足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章 分組碼 定理 對一個(gè)二元 (n， k)線性分組碼 C，有 (1) 能糾正 t個(gè)錯(cuò)誤的充要條件是 dist(C)=2t+1； (2) 能檢測 s個(gè)錯(cuò)誤的充要條件是 dist(C)=s+1； (3) 能糾正 t個(gè)錯(cuò)誤，并能發(fā)現(xiàn) s(st)個(gè)錯(cuò)誤的充要條件是dist(C)=t+s+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章 分組碼 式 ()說明接收矢量 y最像碼 C中的 x，按選大原則，接收端能正確譯出碼 x，即糾正了矢量 y中的 r個(gè)錯(cuò)誤。使用反證法。由碼字間距離的定義， x與 z間至多有2t個(gè)碼元對應(yīng)不同，分兩種情況來討論。不妨設(shè) ， j=1， 2， … ， 2r′。不妨設(shè) ， j=1， 2， … ， 2r′+1。為了說明問題，我們來考慮在信源 X={0， 1}的三維擴(kuò)展信源 X3上編一組 (7， 3)線性分組碼，校驗(yàn)元按滿足下列約束方程來選取，即 第 3章 分組碼 式中， (c6， c5， c4， c3， c2， c1， c0)為 (7， 3)線性分組碼的任意一個(gè)碼字， (c6， c5， c4)為信息碼。因此，式 ()和矩陣 H是進(jìn)行編碼的關(guān)鍵。 由線性代數(shù)的知識我們知道，經(jīng)過行初等變換校驗(yàn)矩陣H可以轉(zhuǎn)化為如下形式： 式中， In－ k是 n－ k階單位矩陣。我們知道線性空間中每一個(gè)矢量都可以通過一組基來線性表示。 顯然， G的秩為 k。 ? ?? ?? ?11 12 121 22 212nknkkk k n kq q qq q qq q q???????? ??????Q? ?1 2 1 0, , , , , , ,kkm m m m??? ? ? ?c m G () 第 3章 分組碼 讀者不難驗(yàn)證，例 (7， 3)線性分組碼 C2的生成矩陣 G為 式中： () ? ?31 0 0 1 1 1 00 1 0 0 1 1 1 ,0 0 1 1 1 0 1????????G I Q1 1 1 00 1 1 11 1 0 1?????????Q第 3章 分組碼 3. 生成矩陣 G與校驗(yàn)矩陣 H間的關(guān)系 同一個(gè) (n， k)線性分組碼 C既可以用校驗(yàn)矩陣來表示，又可以用生成矩陣來表示，這說明兩者間一定存在某種關(guān)系。 以線性空間的觀點(diǎn)，式 ()表明校驗(yàn)矩陣 H的全部行向量與生成矩陣 G的全部行向量是彼此正交的。式 ()的圖示說明見圖 。 解 根據(jù)式 ()，系統(tǒng) (7， 3)線性分組碼的碼字有如下形式： ? ? ? ?6 5 4 3 2 1 0 2 1 11 0 0 1 1 1 00 1 0 0 1 1 10 0 1 1 1 0 1c c c c c c c m m m?????????第 3章 分組碼 校驗(yàn)元用信息碼來表示，有 系統(tǒng) (7， 3)線性分組碼的編碼實(shí)現(xiàn)電路如圖 。 例 構(gòu)造一個(gè)單糾錯(cuò)線性分組碼。因?yàn)?a， b∈ Vn， a與 b是線性無關(guān)的，否則 a+b=0，所以 a=b與 Vn中任意兩個(gè)矢量不相同矛盾。因此，我們可以構(gòu)造一個(gè)校驗(yàn)矩陣： {( 0 , 0 , , 0 , 0) , ( 0 , 0 , , 0 , 1 ) , , ( 1 , 1 , , 1 , 1 ) }nV ?, n??Vαβ第 3章 分組碼 即 H的列由 Vn中全體不為零的矢量的轉(zhuǎn)置構(gòu)成。線性分組碼的譯碼有伴隨式譯碼和標(biāo)準(zhǔn)陣列譯碼兩種基本譯碼方法。因此， HyT的結(jié)果是譯碼的關(guān)鍵。 對一個(gè)接收矢量 y，與發(fā)送碼字相比，要么出錯(cuò)，要么正確，因此，接收矢量 y可以表示為 y=(－ 1+en－ 1， － 2+en－ 2， … ， c1+e1， c0+e0) 式中：如果 y中 ri無錯(cuò)，則 ei=0；如果 ri有錯(cuò)，則 ei=1。顯然，如果 e=0，則接收矢量y是正確碼字。式 ()可簡化為 12 1ti i ie e e? ? ? ?? ?120 , , 0 , , , , , 0iiee?e12Ttn i n i n i? ? ?? ? ? ?S h h h() 第 3章 分組碼 總結(jié)上面的分析，我們得到如下結(jié)論： (1) 校驗(yàn)子由錯(cuò)誤圖樣決定，與發(fā)送的碼字無關(guān)。如伴隨式 S=0，則無錯(cuò)；否則，有錯(cuò)。 第 3章 分組碼 例 考慮例 (7， 3)線性分組碼 C2，發(fā)送碼字 a5=(1001110)，分別就下述接收矢量進(jìn)行譯碼。 第 3章 分組碼 解 (7， 3)線性分組碼 C2的校驗(yàn)矩陣為式 ()。這種譯碼方法就是標(biāo)準(zhǔn)陣列譯碼。每一行都稱為陪集，第一列稱為陪集首。 定理 n維線性空間 Vn中任意一矢量必定出現(xiàn)于標(biāo)準(zhǔn)陣列中，并且僅出現(xiàn)一次，同一陪集中無相同的矢量。 0 1 1 1 0 01 0 1 0 1 01 1 0 0 0 1?????????H第 3章 分組碼 解 首先，求出 (6， 3)線性分組碼的全部碼字，生成矩陣為 (6， 3)線性分組碼的碼字與信息碼間的關(guān)系為 將［ m2， m1， m0］取遍空間 {0， 1}3={000， 001， 010， 011， 100， 101， 110， 111} 1 0 0 0 1 10 1 0 1 0 10 0 1 1 1 0?????????G? ? ? ? ? ?5 4 3 2 1 0 2 1 0 2 1 0 1 0 2 0 2 1, , , , ,c c c c c c m m m m m m m m m m m m? ? ? ? ?G第 3章 分組碼 得到 (6， 3)線性分組碼 C的碼字為 000000 001110 010101 011011 100011 101101 110110 111000 其次，構(gòu)造標(biāo)準(zhǔn)陣。 V6－ C－ B1共有 48個(gè)矢量，選最小重量矢量 v3=(010000)，得到陪集 B2。 第 3章 分組碼 表 例 第 3章 分組碼 根據(jù)表 ， n維線性空間 Vn中任意一矢量都可以表示為(n， k)線性分組碼中的某個(gè)碼字與一個(gè)陪集首之和。 nV??yT T T T Ti i i? ? ? ?S Hy Hc Hv Hv() 第 3章 分組碼 定理 在標(biāo)準(zhǔn)陣列中，同一陪集的所有矢量的伴隨式相同，不同陪集的伴隨式不同，每一個(gè)伴隨式取決于陪集首。譯碼時(shí)，首先求接收矢量y的伴隨式，并找到所對應(yīng)的陪集首 v，然后譯碼為 y+v。 第 3章 分組碼 例 已知的 (6， 3)線性分組碼及校驗(yàn)矩陣 H同例，求 (6， 3)線性分組碼的伴隨式與陪集首的對應(yīng)表，并譯出接收矢量 (100101)對應(yīng)的碼字。 第 3章 分組碼 表 例 第 3章 分組碼 當(dāng)接收矢量為 (100101)時(shí)，對應(yīng)的伴隨式為 查表 ，對應(yīng)的陪集首 v=(001000)，故譯出發(fā)送的碼字為 (100101)＋ (001000)＝ (101101) T100 1 1 1 0 0 101 0 1 0 1 0 111 1 0 0 0 1 001??????? ? ? ???? ? ? ??? ??? ? ? ???? ? ? ?? ? ? ???????S第 3章 分組碼 讀者不難發(fā)現(xiàn)，例 果是相同的，但存儲量由表 64個(gè)矢量下降為 16個(gè)矢量。而標(biāo)準(zhǔn)陣列需要儲存 2n個(gè) n維矢量，節(jié)約的存儲量是非?？捎^的。 第 3章 分組碼 圖 譯碼過程 第 3章 分組碼 循 環(huán) 碼 循環(huán)碼的編碼方法 1. 循環(huán)碼的定義及多項(xiàng)式描述 在介紹循環(huán)碼的定義之前，我們先來定義一個(gè)矢量變換算子，即左移循環(huán)算子。 第 3章 分組碼 結(jié)合左移循環(huán)算子和例 (7， 3)線性分組碼 C2，讀者不難發(fā)現(xiàn)， C2中的碼字有下述特點(diǎn)： 一般地， Lic=L(L(…(L( c)…))) ， L0c=c。簡單地說， C2中的碼字在左移循環(huán)算子變換下仍是 C2中的碼字，本節(jié)要討論的就是具有這種特性的線性分組碼，稱為循環(huán)碼。 為了研究循環(huán)碼的特性，我們引入稱為碼字多項(xiàng)式的多項(xiàng)式來描述一個(gè)碼字，這個(gè)多項(xiàng)式與碼字間建立了一一對應(yīng)的關(guān)系，即 例 求例 (7， 3)線性分組碼 C2的全部碼字多項(xiàng)式。 C??c121 2 1 0 1 2 1 0( , , , , ) ( ) nnn n n nc c c c c x c x c x c x c??? ? ? ?? ? ? ? ? ? ?c第 3章 分組碼 表 (7， 3)線性分組碼 C2的全部碼字多項(xiàng)式 第 3章 分組碼 2. 循環(huán)碼的生成多項(xiàng)式與生成矩陣 定義 如果一個(gè)循環(huán)碼的所有碼字多項(xiàng)式都是一個(gè)次數(shù)最低的多項(xiàng)式 g(x)的倍數(shù)，那么稱 g(x)為這個(gè)循環(huán)碼的生成多項(xiàng)式。 既然生成多項(xiàng)式存在，那么如何來尋找呢？ 第 3章 分組碼 定理 每一個(gè) (n， k)循環(huán)碼的生成多項(xiàng)式 g(x)一定整除 xn－ 1，即 g(x)|xn－ 1。 有了生成多項(xiàng)式 g(x)，每一個(gè) (n， k)循環(huán)碼可以由生成多項(xiàng)式來簡單表出，其全部碼字多項(xiàng)式為 0， g(x)， xg(x)， x2g(x)， … ， xn－ 2g(x)， xn－ 1g(x) () 生成多項(xiàng)式用式 ()表示 , 因?yàn)?g(x), xg(x), x2g(x), … ，xk－ 2g(x)， xk－ 1g(x)為循環(huán)碼的一組基，所以 (n， k)循環(huán)碼的生成矩陣可以表示為 第 3章 分組碼 ? ?? ?100111021 2 3 1 01 2 2 1 0100 0 0 0 00 0 0 000000 0 0kn k n knkn k n k n knkn k n k n kkgg g gggggg g g g ggg g g g g g?? ? ??? ? ? ? ? ??? ? ? ? ?????????????G12LLLkkkn????????????????????gggg() 第 3章 分組碼 例 求 (7， 3)循環(huán)碼的生成多項(xiàng)式及生成矩陣。 設(shè)校驗(yàn)多項(xiàng)式為 h(x)=hkxk+hk－ 1xk－ 1+…+ h1x+h0