循環(huán)碼的生成

1、循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個(gè)碼組。例：一種(7, 3)循環(huán)碼的全部碼組如下 表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。 碼組碼組編號(hào)編號(hào)信息位信息位監(jiān)督位監(jiān)督位碼組碼組編號(hào)編號(hào)信息位信息位監(jiān)督位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010循環(huán)碼的概念一般情況 若(an-1 an-2 a0)是循環(huán)碼的一個(gè)碼組，則循環(huán)移位后的碼組： (an-2 an-3 a0 an-1) (an-3 an-4 an-1

2、an-2) (a0 an-1 a2 a1) 仍然是該編碼中的碼組。多項(xiàng)式表示法一個(gè)長(zhǎng)度為n的碼組(an-1 an-2 a0)可以表示成 上式中x 的值沒(méi)有任何意義，僅用它的冪代表碼元的位置。例：碼組1 1 0 0 1 0 1可以表示為 012211)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT循環(huán)碼的生成 l有了生成矩陣G，就可以由k個(gè)信息位得出整個(gè)碼組：例：式中，生成矩陣G的每一行都是一個(gè)碼組。l因此，若能找到 k 個(gè)已知的碼組，就能構(gòu)成矩陣G。如前所述，這k個(gè)已知碼組必須是線性不相關(guān)的。l在循環(huán)碼中，一個(gè)(n, k)碼有2k個(gè)不同的碼組。若用g(x

3、)表示其中前(k-1)位皆為“0”的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這k個(gè)碼組是線性無(wú)關(guān)的。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣G。G34560123456aaaaaaaaaaaA0110001101001011001001111000QGkI Il在循環(huán)碼中除全“0”碼組外，再?zèng)]有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線性碼中顯然是不可能的。l因此，g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n - k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n, k)碼中次數(shù)為(n k)

4、的唯一一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n k)，即連續(xù)“0”的個(gè)數(shù)多于(k 1)。顯然，這是與前面的結(jié)論矛盾的。l我們稱(chēng)這唯一的(n k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n, k)循環(huán)碼就被確定了。l因此，循環(huán)碼的生成矩陣G可以寫(xiě)成l例： 上表中的編碼為(7, 3)循環(huán)碼，n = 7, k = 3, n k = 4，其中唯一的一個(gè)(n k) = 4次碼多項(xiàng)式代表的碼組是第二碼組0010111，與它對(duì)應(yīng)的碼多項(xiàng)式，即生成多項(xiàng)式，為g(x) = x4 + x2 + x + 1。 )()()()()(21xgxxgxgxxgxxkkG碼組編碼組編號(hào)號(hào)信息位信息位監(jiān)督位監(jiān)督位碼組編碼組編號(hào)號(hào)信息位信息位監(jiān)督位監(jiān)督位A6a5a4a3a2a1a0a6a5a4A3a2a