循環(huán)碼的多項(xiàng)式描述課件

1、循環(huán)碼的多項(xiàng)式描述2、循環(huán)碼的生成多項(xiàng)式3、系統(tǒng)循環(huán)碼4、多項(xiàng)式運(yùn)算電路5、循環(huán)碼的編碼電路6、循環(huán)碼的譯碼7、循環(huán)漢明碼8、縮短循環(huán)碼循環(huán)碼(1)循環(huán)碼的性質(zhì)循環(huán)碼是線性分組碼的一個(gè)重要子類；由于循環(huán)碼具有優(yōu)良的代數(shù)結(jié)構(gòu)，使得可用簡單的反饋移位寄存器實(shí)現(xiàn)編碼和伴隨式計(jì)算，并可使用多種簡單而有效的譯碼方法；循環(huán)碼是研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。(2)循環(huán)碼的定義循環(huán)碼：如果(n,k)線性分組碼的任意碼矢C=(Cn－1,Cn－2,…,C0)

的i次循環(huán)移位，所得矢量C(i)=(Cn－1－i,Cn－2－i,…,C0,Cn－1,…,Cn－i)

仍是一個(gè)碼矢，則稱此線性碼為(n,k)循環(huán)碼。碼多項(xiàng)式的模(xn+1)運(yùn)算0和1兩個(gè)元素模2運(yùn)算下構(gòu)成域。碼矢C循環(huán)i次所得碼矢的碼多項(xiàng)式

C(x)乘以x，再除以(xn+1)，得上式表明：碼矢循環(huán)一次的碼多項(xiàng)式C(1)(x)是原碼多項(xiàng)式C(x)乘以x除以(xn+1)的余式。寫作因此，

C(x)的i次循環(huán)移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式，即結(jié)論：循環(huán)碼的碼矢的i次循環(huán)移位等效于將碼多項(xiàng)式乘xi后再模(xn+1)。(1)循環(huán)碼的生成矩陣根據(jù)循環(huán)碼的循環(huán)特性，可由一個(gè)碼字的循環(huán)移位得到其它的非0碼字。在(n,k)循環(huán)碼的2k個(gè)碼字中，取前(k－1)位皆為0的碼字g(x)（其次數(shù)r=n－k），再經(jīng)(k－1)次循環(huán)移位，共得到k個(gè)碼字:g(x),xg(x),…,xk－1g(x)

這k個(gè)碼字顯然是相互獨(dú)立的，可作為碼生成矩陣的k行，于是得到循環(huán)碼的生成矩陣G(x)(2)循環(huán)碼的生成多項(xiàng)式碼的生成矩陣一旦確定，碼就確定了；這就說明：(n,k)循環(huán)碼可由它的一個(gè)(n－k)次碼多項(xiàng)式g(x)來確定；所以說g(x)生成了(n,k)循環(huán)碼，因此稱g(x)為碼的生成多項(xiàng)式。定理6.3.3(定理6.3.2的逆定理)：在一個(gè)(n,k)線性碼中，如果全部碼多項(xiàng)式都是最低次的(n－k)次碼多項(xiàng)式的倍式，則此線性碼為一個(gè)(n,k)循環(huán)碼。

注：一般說來，這種循環(huán)碼仍具有把(n,k)線性碼碼中任一非0碼矢循環(huán)移位必為一碼矢的循環(huán)特性，但從一個(gè)非0碼矢出發(fā)，進(jìn)行循環(huán)移位，就未必能得到碼的所有非0碼矢了。所以稱這種循環(huán)碼為推廣循環(huán)碼。碼字循環(huán)關(guān)系圖單純循環(huán)碼的碼字循環(huán)圖：(7,3)循環(huán)碼推廣循環(huán)碼的碼字循環(huán)圖：(6,3)循環(huán)碼定理：(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是(xn+1)的因式，即xn+1=h(x)g(x)。定理：若g(x)是一個(gè)(n－k)次多項(xiàng)式，且為(xn+1)的因式，則g(x)生成一個(gè)(n,k)循環(huán)碼。結(jié)論：當(dāng)求作一個(gè)(n,k)循環(huán)碼時(shí)，只要分解多項(xiàng)式(xn+1)，從中取出(n－k)次因式作生成多項(xiàng)式即可。舉例：求(7,3)循環(huán)碼的生成多項(xiàng)式。[解]：分解多項(xiàng)式xn+1，取其4次因式作生成多項(xiàng)式x7+1=(x+1)(x3+x2+1)(x3+x+1)可將一次和任一個(gè)三次因式的乘積作為生成多項(xiàng)式，因而可取

g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1

或g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1(5)循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式：設(shè)g(x)為(n,k)循環(huán)碼的生成多項(xiàng)式，必為(xn+1)的因式，則有xn+1=h(x)g(x)，式中h(x)為k次多項(xiàng)式，稱為(n,k)循環(huán)碼的監(jiān)督多項(xiàng)式。(n,k)循環(huán)碼也可由其監(jiān)督多項(xiàng)式完全確定。舉例：(7,3)循環(huán)碼x7+1=(x3+x+1)(x4+x2+x+1)4次多項(xiàng)式為生成多項(xiàng)式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g03次多項(xiàng)式是監(jiān)督多項(xiàng)式h(x)=x3+x+1=h3x3+h2x2+h1x+h0上式中，列陣的元素是生成多項(xiàng)式g(x)的系數(shù)，是一個(gè)碼字，那么第一個(gè)矩陣則為(7,3)循環(huán)碼的監(jiān)督矩陣，即循環(huán)碼監(jiān)督矩陣的構(gòu)成由式(6.3.2)可見，監(jiān)督矩陣的第一行是碼的監(jiān)督多項(xiàng)式h(x)的系數(shù)的反序排列，第二、三、四行是第一行的移位；可用監(jiān)督多項(xiàng)式的系數(shù)來構(gòu)成監(jiān)督矩陣(n,k)循環(huán)碼的監(jiān)督矩陣對(duì)偶問題如果xn+1=h(x)g(x)，其中g(shù)(x)為(n－k)

次多項(xiàng)式，以g(x)為生成多項(xiàng)式，則生成一個(gè)(n,k)循