【正文】 信息論與編碼 循環(huán)碼 上次課小結(jié)： ? 線性分組碼的一些概念：域、矢量空間、線性 分組碼； ? 生成矩陣和校驗矩陣 ? 伴隨式與譯碼：伴隨式的定義、標(biāo)準(zhǔn)陣列譯碼 表。 信息論與編碼 循環(huán)碼 ? 循環(huán)碼是線性分組碼中最重要的一類碼。 ? 循環(huán)碼的特點是： 碼集 C中任意一個碼字經(jīng)循環(huán)移位后仍然是碼字 。 ? 由于構(gòu)成碼集 C的 k維 n重矢量空間的基底也一定是碼字，因此， k個基底可以是同一個基底經(jīng)循環(huán)移位得到。所以，只用一個基底就可以表示一個碼的特征，也就不需要用矩陣來描述。 信息論與編碼 循環(huán)碼 描述循環(huán)碼的重要的數(shù)學(xué)工具是多項式。 設(shè)一個碼字為 ，可以用一個稱為 碼多項式 的多項式來表示，多項式的系數(shù)就是碼字的各個碼元的值，指數(shù)項表示碼元在碼字中所處的位置，即 對于二進(jìn)制碼， 。 ],[ 021 cccC nn ????012211)( cxcxcxcxC nnnn ????? ???? ?}1,0{?ic信息論與編碼 循環(huán)碼 當(dāng) C所對應(yīng)的碼字循環(huán)移位 1位后，得到對應(yī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???位：移位：移位：移? 因為一個碼字經(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)是任意多項式， 是一個碼多項式。也就是說， 任意一個碼多項式與一個多項式之積，仍然是一個碼多項式 。 上述運(yùn)算是在模運(yùn)算的前提下，即 )(0 xC)()()()()()()()()(00112210011j0220210xCxAxCxaxaxaaxCxaxCxaxxCaxCaxCjjj?????????????????)(0 xC)1m o d ( ?nx信息論與編碼 循環(huán)碼 從多項式的性質(zhì)出發(fā)，根據(jù)近世代數(shù)理論，可以得到以下結(jié)論： (1)一個 (n,k)循環(huán)碼的碼多項式是模 (xn+1)乘運(yùn)算下多項式交換環(huán)的一個主理想子環(huán)，反之，多項式交換環(huán)的一個主理想子環(huán)一定可以產(chǎn)生一個循環(huán)碼。而主理想子環(huán)中的所有碼多項式都可以由其中一個元素(碼多項式 )的倍式組成，這個元素稱為該主理想子環(huán)的生成元，或稱它為對應(yīng)循環(huán)碼的生成多項式。生成多項式不是唯一的，但總有一個是最低的。 信息論與編碼 循環(huán)碼 （ 2） GF(2)上的（ n， k）循環(huán)碼中，存在著唯一的一個次數(shù)最低（ nk次）的首一（即第一項的系數(shù)為 1）碼多項式 g(x)： 使得所有的碼多項式都是 g(x)的倍式，即 且所有小于 n次的 g(x)的倍式都是碼多項式。 g(x)稱為 生成多項式 。 1)( 12211 ?????? ????? xgxgxgxxg knknkn ?)()()( xgxmxC ?信息論與編碼 循環(huán)碼 （ 3）（ n， k）循環(huán)碼的生成多項式 g(x)一定是 的因子，寫為 ，或 。 反之，如果 g(x)是 的（ nk）次因子，則 g(x)一定是（ n， k）循環(huán)碼的生成多項式。 1?nx 1|)( ?nxxg)()(1 xhxgx n ??1?nx信息論與編碼 循環(huán)碼 ? （ n， k）循環(huán)碼的構(gòu)造方法為： （ 1）對 做因式分解，找出其（ nk）次因子； （ 2）以該（ nk）次因子為生成多項式 g(x)，與信息多項式 m(x)相乘，得到的多項式C(x)=m(x)g(x)即為碼多項式。 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）次多項式作為生成多項式，本題中沒有要求 k，可以選用不同的多項式做生成多項式，當(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è)選取 為生成多項式，則 nk=3， k=4，所以信息多項式為 信息碼組共有 16種不同的組合，因此，共有 16個碼字。 例如 則循環(huán)編碼后的碼多項式為 對應(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)碼 一致校驗多項式 如果 分解為 ，選 g(x)為生成多項式，則 h(x)稱為碼的一致校驗多項式，階次為 k，和校驗矩陣類似，校驗多項式滿足： 當(dāng)然，也可以選擇 h(x)為碼生成多項式，則 g(x)就 是一致校驗多項式。 因此，由 g(x)生成的（ n， k）碼和由 h(x)生成的（ n， k）碼互為對偶碼。 1?nx )