【文章內(nèi)容簡介】 陪集中無相同的矢量。 例 設(shè) (6， 3)線性分組碼的校驗(yàn)矩陣為 完成標(biāo)準(zhǔ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中共有 56個矢量，選最小重量矢量 v2=(100000)，并與 C中每一個碼字相加，得到陪集 B1。 V6－ C－ B1共有 48個矢量，選最小重量矢量 v3=(010000)，得到陪集 B2。如此繼續(xù)下去，構(gòu)成標(biāo)準(zhǔn)陣列，見表 。 第 3章 分組碼 表 例 第 3章 分組碼 根據(jù)表 ， n維線性空間 Vn中任意一矢量都可以表示為(n， k)線性分組碼中的某個碼字與一個陪集首之和。用數(shù)學(xué)語言表示，即 ，存在 (n， k)線性分組碼中的碼字 ci和陪集首 vi滿足： y=ci+vi () 計算矢量 y的伴隨式，有 由式 ()，我們可得如下結(jié)論。 nV??yT T T T Ti i i? ? ? ?S Hy Hc Hv Hv() 第 3章 分組碼 定理 在標(biāo)準(zhǔn)陣列中，同一陪集的所有矢量的伴隨式相同，不同陪集的伴隨式不同，每一個伴隨式取決于陪集首。 定理 對應(yīng)的關(guān)系，因此，把存儲標(biāo)準(zhǔn)陣列改為存儲伴隨式及對應(yīng)的陪集首，存儲量將大幅度降低。譯碼時，首先求接收矢量y的伴隨式，并找到所對應(yīng)的陪集首 v，然后譯碼為 y+v。這種譯碼方法與查找標(biāo)準(zhǔn)陣列表譯碼方法等價。 第 3章 分組碼 例 已知的 (6， 3)線性分組碼及校驗(yàn)矩陣 H同例，求 (6， 3)線性分組碼的伴隨式與陪集首的對應(yīng)表，并譯出接收矢量 (100101)對應(yīng)的碼字。 解 根據(jù)表 ，全部陪集首實(shí)質(zhì)上就是子集 D1，陪集首 (000000)的伴隨式 S1=(000)，陪集首 (100000)的伴隨式 S2= (011)， … ，見表 。 第 3章 分組碼 表 例 第 3章 分組碼 當(dāng)接收矢量為 (100101)時，對應(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個矢量下降為 16個矢量。一般地，需要存儲的陪集首為 2n－ k個 n維矢量，需要存儲的伴隨式為 2n－ k個 n－ k維矢量。而標(biāo)準(zhǔn)陣列需要儲存 2n個 n維矢量，節(jié)約的存儲量是非?？捎^的。 (n， k)線性分組碼的譯碼過程如圖 。 第 3章 分組碼 圖 譯碼過程 第 3章 分組碼 循 環(huán) 碼 循環(huán)碼的編碼方法 1. 循環(huán)碼的定義及多項式描述 在介紹循環(huán)碼的定義之前，我們先來定義一個矢量變換算子，即左移循環(huán)算子。 定義 設(shè)矢量 c=(－ 1， － 2， … ， c1， c0)∈ Vn，變換 L將矢量 c變?yōu)?Vn中另一個矢量 Lc，且滿足關(guān)系： Lc=(－ 2， － 3， … ， c1， c0， － 1) () 那么，稱變換 L為左移循環(huán)算子。 第 3章 分組碼 結(jié)合左移循環(huán)算子和例 (7， 3)線性分組碼 C2，讀者不難發(fā)現(xiàn)， C2中的碼字有下述特點(diǎn)： 一般地， Lic=L(L(…(L( c)…))) ， L0c=c。例如 ， L2a4= L(L(a4))=L(a8)=a7。簡單地說， C2中的碼字在左移循環(huán)算子變換下仍是 C2中的碼字，本節(jié)要討論的就是具有這種特性的線性分組碼，稱為循環(huán)碼。 L L L L L L L4 8 7 6 3 5 2 4L11??? ??? ??? ??? ??? ??? ??????a a a a a a a aaa第 3章 分組碼 定義 一個線性分組碼 C，如果 ，有 Lc∈ C，則稱線性分組碼 C為循環(huán)碼。 為了研究循環(huán)碼的特性，我們引入稱為碼字多項式的多項式來描述一個碼字，這個多項式與碼字間建立了一一對應(yīng)的關(guān)系，即 例 求例 (7， 3)線性分組碼 C2的全部碼字多項式。 解 C2的全部碼字多項式見表 。 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的全部碼字多項式 第 3章 分組碼 2. 循環(huán)碼的生成多項式與生成矩陣 定義 如果一個循環(huán)碼的所有碼字多項式都是一個次數(shù)最低的多項式 g(x)的倍數(shù)，那么稱 g(x)為這個循環(huán)碼的生成多項式。 定理 每個 (n， k)循環(huán)碼中，生成多項式 g(x)一定存在并且唯一，生成多項式 g(x)的次數(shù) deg(g(x))=n－ k并且具有以下形式： g(x)=gn－ kxn－ k+gn－ k－ 1xn－ k－ 1+…+ g1x+g0 () 每個次數(shù)不超過 n－ 1且是 g(x)的倍數(shù)的多項式是這個循環(huán)碼的碼字多項式。 既然生成多項式存在，那么如何來尋找呢？ 第 3章 分組碼 定理 每一個 (n， k)循環(huán)碼的生成多項式 g(x)一定整除 xn－ 1，即 g(x)|xn－ 1。反過來， 如果多項式 g(x)次數(shù)deg(g(x))=n－ k，并且 g(x)|xn－ 1，則多項式 g(x)一定能生成一個 (n， k)循環(huán)碼。 有了生成多項式 g(x)，每一個 (n， k)循環(huán)碼可以由生成多項式來簡單表出，其全部碼字多項式為 0， g(x)， xg(x)， x2g(x)， … ， xn－ 2g(x)， xn－ 1g(x) () 生成多項式用式 ()表示 , 因?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)碼的生成多項式及生成矩陣。 解 根據(jù)定理 ，首先將 x7－ 1進(jìn)行因式分解： x7－ 1=(x+1)(x3+x2+1)(x3+x+1) 滿足本例要求的答案有兩個： (1) 生成多項式取 g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1 生成矩陣為 11 0 1 1 1 0 00 1 0 1 1 1 00 0 1 0 1 1 1?????????G第 3章 分組碼 (2) 生成多項式取 g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1 生成矩陣為 21 1 1 0 1 0 00 1 1 1 0 1 00 0 1 1 1 0 1???????G第 3章 分組碼 3. 循環(huán)碼的校驗(yàn)多項式與校驗(yàn)矩陣 設(shè) g(x)是 (n， k)循環(huán)碼的生成多項式，由定理 ，存在一個次數(shù)為 k的多項式 h(x)使 xn－ 1=h(x)g(x) () 定義 稱滿足式 ()的 k次多項式 h(x)為 (n， k)循環(huán)碼的校驗(yàn)多項式。 設(shè)校驗(yàn)多項式為 h(x)=hkxk+hk－ 1xk－ 1+…+ h1x+h0 () 將式 ()和式 ()代入式 ()，在模 xn－ 1下，g(x)h(x)=0，從而得到方程組 第 3章 分組碼 式中 ， i=1， 2， … ， n－ 1。 ? ?001 0 0 10 1 11 0 2 1 110001i i n ki n kn n k n kk n khgh g h gh g h g h gh g h g h ghg?? ??? ? ? ??? ????????? ? ? ????? ? ? ? ?????() 第 3章 分組碼 將式 ()寫成矩陣形式，有 GHT=0 () 稱矩陣 H為 (n， k)循環(huán)碼的校驗(yàn)矩陣。 式 ()中， 第 3章 分組碼 () ? ?010 1 20 1 10 0 00 0 00 0 0kkkk n k nh h hh h h hh h h h? ???????????H ? ?1nk ??? ?1nk ??個 0個 0? ?12LLLnknkn k n???????????????????????hhhh第 3章 分組碼 例 求例 g2(x)對應(yīng)的校驗(yàn)多項式及校驗(yàn)矩陣。 解 校驗(yàn)多項式為 校驗(yàn)矩陣為 ? ? ? ? 3221 1nxh x x xgx?? ? ? ?1 0 1 1 0 0 00 1 0 1 1 0 00 0 1 0 1 1 00 0 0 1 0 1 1?????????H第 3章 分組碼 4. 系統(tǒng)循環(huán)碼的編碼實(shí)現(xiàn) 1) 信息元多項式與校驗(yàn)元多項式的關(guān)系 由信息碼構(gòu)成的多項式稱為信息元多項式，由校驗(yàn)元構(gòu)成的多項式稱為校驗(yàn)元多項式。設(shè)一個 (n， k)循環(huán)碼的生成多項式為 g(x)，信息碼 (mk－ 1， mk－ 2， … ， m1， m0)，我們來確定循環(huán)碼的碼字校驗(yàn)元。因?yàn)榭紤]系統(tǒng)循環(huán)碼，所以碼字結(jié)構(gòu)為 c=(mk－ 1， mk－ 2， … ， m1， m0， － k－ 1， － k－ 2， … ， c1， c0) 第 3章 分組碼 信息元多項式和校驗(yàn)元多項式分別為 m(x)=mk－ 1xk－ 1+mk－ 2xk－ 2+…+ m1x+m0 r(x)=－ k－ 1xn－ k－ 1+－ k－ 2xn－ k－ 2+…+ c1x+c0 于是，碼字 c的碼字多項式為 c(x)=mk－ 1xn－ 1+mk－ 2xn－ 2+…+ m1xn－ k－ 1+m0xn－ k +－ k－ 1xn－ k－ 1+…+ c1x+c0=xn－ km(x)+r(x) () 根據(jù)生成多項式的定義， c(x)是生成多項式 g(x)的倍數(shù)，即存在一個多項式 q(x)滿足： xn－ km(x)+r(x)=q(x)g(x) () 第 3章 分組碼 2) 基于生成多項式的循環(huán)碼的編碼實(shí)現(xiàn) 除法電路由移位寄存器、模 2加法器和邏輯門組成，除法電路結(jié)構(gòu)取決于生成多項式 g(x)，一般結(jié)構(gòu)如圖 。其中，當(dāng) gi=1時