【正文】 信息論與編碼 循環(huán)碼 上次課小結(jié)： ? 線性分組碼的一些概念：域、矢量空間、線性 分組碼； ? 生成矩陣和校驗(yàn)矩陣 ? 伴隨式與譯碼：伴隨式的定義、標(biāo)準(zhǔn)陣列譯碼 表。 信息論與編碼 循環(huán)碼 ? 循環(huán)碼是線性分組碼中最重要的一類碼。 ? 循環(huán)碼的特點(diǎn)是： 碼集 C中任意一個碼字經(jīng)循環(huán)移位后仍然是碼字 。 ? 由于構(gòu)成碼集 C的 k維 n重矢量空間的基底也一定是碼字，因此， k個基底可以是同一個基底經(jīng)循環(huán)移位得到。所以，只用一個基底就可以表示一個碼的特征，也就不需要用矩陣來描述。 信息論與編碼 循環(huán)碼 描述循環(huán)碼的重要的數(shù)學(xué)工具是多項(xiàng)式。 設(shè)一個碼字為 ，可以用一個稱為 碼多項(xiàng)式 的多項(xiàng)式來表示，多項(xiàng)式的系數(shù)就是碼字的各個碼元的值，指數(shù)項(xiàng)表示碼元在碼字中所處的位置，即 對于二進(jìn)制碼， 。 ],[ 021 cccC nn ????012211)( cxcxcxcxC nnnn ????? ???? ?}1,0{?ic信息論與編碼 循環(huán)碼 當(dāng) C所對應(yīng)的碼字循環(huán)移位 1位后，得到對應(yīng)的多項(xiàng)式為 所以，可以用多項(xiàng)式乘以 x來表示一次循環(huán)移位，因此有： 0122110 )( cxcxcxcxC nnnn ????? ???? ?1023121 )( ????? ????? nnnnn cxcxcxcxC ?)()( 01 xxCxC ? )1m o d ( ?nx021 , ccc nn ???循環(huán)移 1位 1032 , ??? nnn cccc ?信息論與編碼 循環(huán)碼 以此類推。 )1m o d ()1m o d ()1m o d ()()()()()()()()(1n210121021201???????????nnnnnn xxxxCxxxCxCxCxxxCxCxxCxC???位：移位：移位：移? 因?yàn)橐粋€碼字經(jīng)過 n次循環(huán)移位后又變回自身，所以一個碼字經(jīng)循環(huán)移位最多產(chǎn)生 n個碼字。 ? 而對于碼長為 n的碼字，共有 個不同的碼字，因此，不可能由一個碼字經(jīng)循環(huán)移位得到所有可能的碼字。 ? 但是，可以由一個基底矢量經(jīng)循環(huán)移位得到所有 k個基底矢量，所有的碼字都可以由這 k個基底的線性組合構(gòu)成。 k2信息論與編碼 循環(huán)碼 信息論與編碼 循環(huán)碼 因此，設(shè) 對應(yīng)一個碼字，則其線性組合： 其中， A(x)是任意多項(xiàng)式， 是一個碼多項(xiàng)式。也就是說， 任意一個碼多項(xiàng)式與一個多項(xiàng)式之積，仍然是一個碼多項(xiàng)式 。 上述運(yùn)算是在模運(yùn)算的前提下，即 )(0 xC)()()()()()()()()(00112210011j0220210xCxAxCxaxaxaaxCxaxCxaxxCaxCaxCjjj?????????????????)(0 xC)1m o d ( ?nx信息論與編碼 循環(huán)碼 從多項(xiàng)式的性質(zhì)出發(fā)，根據(jù)近世代數(shù)理論，可以得到以下結(jié)論： (1)一個 (n,k)循環(huán)碼的碼多項(xiàng)式是模 (xn+1)乘運(yùn)算下多項(xiàng)式交換環(huán)的一個主理想子環(huán)，反之，多項(xiàng)式交換環(huán)的一個主理想子環(huán)一定可以產(chǎn)生一個循環(huán)碼。而主理想子環(huán)中的所有碼多項(xiàng)式都可以由其中一個元素(碼多項(xiàng)式 )的倍式組成，這個元素稱為該主理想子環(huán)的生成元，或稱它為對應(yīng)循環(huán)碼的生成多項(xiàng)式。生成多項(xiàng)式不是唯一的，但總有一個是最低的。 信息論與編碼 循環(huán)碼 （ 2） GF(2)上的（ n， k）循環(huán)碼中，存在著唯一的一個次數(shù)最低（ nk次）的首一（即第一項(xiàng)的系數(shù)為 1）碼多項(xiàng)式 g(x)： 使得所有的碼多項(xiàng)式都是 g(x)的倍式，即 且所有小于 n次的 g(x)的倍式都是碼多項(xiàng)式。 g(x)稱為 生成多項(xiàng)式 。 1)( 12211 ?????? ????? xgxgxgxxg knknkn ?)()()( xgxmxC ?信息論與編碼 循環(huán)碼 （ 3）（ n， k）循環(huán)碼的生成多項(xiàng)式 g(x)一定是 的因子，寫為 ，或 。 反之，如果 g(x)是 的（ nk）次因子，則 g(x)一定是（ n， k）循環(huán)碼的生成多項(xiàng)式。 1?nx 1|)( ?nxxg)()(1 xhxgx n ??1?nx信息論與編碼 循環(huán)碼 ? （ n， k）循環(huán)碼的構(gòu)造方法為： （ 1）對 做因式分解，找出其（ nk）次因子； （ 2）以該（ nk）次因子為生成多項(xiàng)式 g(x)，與信息多項(xiàng)式 m(x)相乘，得到的多項(xiàng)式C(x)=m(x)g(x)即為碼多項(xiàng)式。 1?nx信息論與編碼 循環(huán)碼 例題：研究一個長度為 7的循環(huán)碼的構(gòu)成方法。 解：根據(jù)上面的循環(huán)碼編碼方法，首先對 做因式分解，得到 17 ?x)1)(1)(1(1 3237 ??????? xxxxxx信息論與編碼 循環(huán)碼 所以， 的因子共有以下幾種： ：次數(shù)為 1（ 1個）； ， ：次數(shù)為 3（ 2個）； ， ：次數(shù)為 4（ 2個）； ：次數(shù)為 6（ 1個）； 如果給定了 n和 k，那么只能選用滿足要求的（ nk）次多項(xiàng)式作為生成多項(xiàng)式，本題中沒有要求 k，可以選用不同的多項(xiàng)式做生成多項(xiàng)式，當(dāng)然會得到不同的碼集。 17 ?x)1( ?x)1( 23 ?? xx )1( 3 ?? xx)1)(1( 23 ??? xxx )1)(1( 3 ??? xxx)1)(1( 233 ???? xxxx信息論與編碼 循環(huán)碼 設(shè)選取 為生成多項(xiàng)式，則 nk=3， k=4，所以信息多項(xiàng)式為 信息碼組共有 16種不同的組合，因此，共有 16個碼字。 例如 則循環(huán)編碼后的碼多項(xiàng)式為 對應(yīng)的碼字為（ 0101110）。 )1()( 23 ??? xxxg1)( 32231 ???? xmxmxmxm)0 1 1 0()( 0123 ?? mmmmmxxxxxxxxxC ???????? 235232 )1)(()(信息論與編碼 循環(huán)碼 ?相同地，可以得到不同信息組的時候的碼字?？梢钥闯?，碼集中有四組碼字循環(huán) 信息比特 碼字 （循環(huán) 1） 信息比特 碼字 （循環(huán) 2） 信息比特 碼字 （循環(huán) 3和 4） 0001 0010 0100 1000 1101 0111 1110 0001101 0011010 0110100 1101000 1010001 0100011 1000110 0011 0110 1100 0101 1010 1001 1111 0010111 0101110 1011100 0111001 1110010 1100101 1001011 0000 1011 0000000 1111111 信息論與編碼 循環(huán)碼 一致校驗(yàn)多項(xiàng)式 如果 分解為 ，選 g(x)為生成多項(xiàng)式，則 h(x)稱為碼的一致校驗(yàn)多項(xiàng)式，階次為 k，和校驗(yàn)矩陣類似，校驗(yàn)多項(xiàng)式滿足： 當(dāng)然，也可以選擇 h(x)為碼生成多項(xiàng)式，則 g(x)就 是一致校驗(yàn)多項(xiàng)式。 因此，由 g(x)生成的（ n， k）碼和由 h(x)生成的（ n， k）碼互為對偶碼。 1?nx )