信息論與編碼原理_第9章_循環(huán)碼

1、第1頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng第2頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng9.1 循環(huán)碼的多項(xiàng)式描述循環(huán)碼的多項(xiàng)式描述9.2 循環(huán)碼的循環(huán)碼的生成多項(xiàng)式生成多項(xiàng)式9.3 系統(tǒng)循環(huán)碼系統(tǒng)循環(huán)碼9.4 多項(xiàng)式運(yùn)算電路多項(xiàng)式運(yùn)算電路9.5 循環(huán)碼的循環(huán)碼的編碼電路編碼電路9.6 循環(huán)碼的循環(huán)碼的譯碼譯碼9.7 循環(huán)漢明碼循環(huán)漢明碼9.8 縮短循環(huán)碼縮短循環(huán)碼9.9 循環(huán)碼的其它譯碼方法循環(huán)碼的其它

2、譯碼方法9.10 BCH 碼和碼和 RS 碼碼第3頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循環(huán)碼的性質(zhì)循環(huán)碼的性質(zhì)(2) 循環(huán)碼的定義循環(huán)碼的定義(3) 碼多項(xiàng)式碼多項(xiàng)式(4) 舉例舉例第4頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循環(huán)碼的性質(zhì)循環(huán)碼的性質(zhì) 循環(huán)碼是線(xiàn)性分組碼的一個(gè)重要子類(lèi)；循環(huán)碼是線(xiàn)性分組碼的一個(gè)重要子類(lèi)； 由于循環(huán)碼具有由于循環(huán)碼具有優(yōu)良的代數(shù)結(jié)構(gòu)優(yōu)良的代數(shù)結(jié)構(gòu)，可用簡(jiǎn)單

3、的反饋移，可用簡(jiǎn)單的反饋移位寄存器實(shí)現(xiàn)編碼和伴隨式計(jì)算，并可使用多種簡(jiǎn)單而位寄存器實(shí)現(xiàn)編碼和伴隨式計(jì)算，并可使用多種簡(jiǎn)單而有效的譯碼方法；有效的譯碼方法； 循環(huán)碼是研究最循環(huán)碼是研究最深入深入、理論最、理論最成熟成熟、應(yīng)用最、應(yīng)用最廣泛廣泛的一的一類(lèi)線(xiàn)性分組碼。類(lèi)線(xiàn)性分組碼。第5頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 循環(huán)碼的定義循環(huán)碼的定義 循環(huán)碼：循環(huán)碼：如果如果 (n,k) 線(xiàn)性分組碼的任意碼字：線(xiàn)性分組碼的任意碼字：C C=(cn1,cn2,c0) 的的 i 次循環(huán)移位，所得矢量：次

4、循環(huán)移位，所得矢量：C C(i)=(cn1i,cn2i,c0,cn1,cni) 仍是一個(gè)碼字，則稱(chēng)此線(xiàn)性碼為仍是一個(gè)碼字，則稱(chēng)此線(xiàn)性碼為 (n,k) 循環(huán)碼。循環(huán)碼。第6頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 碼多項(xiàng)式碼多項(xiàng)式 碼多項(xiàng)式：碼多項(xiàng)式：為了運(yùn)算的方便，將碼字的各分量作為多項(xiàng)式的系數(shù)，為了運(yùn)算的方便，將碼字的各分量作為多項(xiàng)式的系數(shù)，把碼字表示成多項(xiàng)式，稱(chēng)為碼多項(xiàng)式。其一般表示式為：把碼字表示成多項(xiàng)式，稱(chēng)為碼多項(xiàng)式。其一般表示式為：C(x)=cn1xn1+cn2xn2+c0 碼多項(xiàng)式

5、碼多項(xiàng)式 i 次循環(huán)移位的表示方法次循環(huán)移位的表示方法 記碼多項(xiàng)式記碼多項(xiàng)式 C(x) 的一次左移循環(huán)為的一次左移循環(huán)為 C(1)(x) ，i 次左移循環(huán)為次左移循環(huán)為 C(i)(x) ininiininnininnnnnnnnncxcxcxcxcxcxCcxcxcxcxcxCccxcxcxC110112211)(10212312(1)012211)()()(第7頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 碼多項(xiàng)式碼多項(xiàng)式 碼多項(xiàng)式的模碼多項(xiàng)式的模 (xn+1) 運(yùn)算運(yùn)算q 0 和和 1 兩個(gè)元

6、素模兩個(gè)元素模 2 運(yùn)算下構(gòu)成域。運(yùn)算下構(gòu)成域。q 若若 p 為素?cái)?shù)，則整數(shù)全體在模為素?cái)?shù)，則整數(shù)全體在模 p 運(yùn)算下的剩余類(lèi)全體運(yùn)算下的剩余類(lèi)全體 在模在模 p 下構(gòu)成域。下構(gòu)成域。 1,3,2,1,0 p1010001001110010 第8頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 碼多項(xiàng)式碼多項(xiàng)式 碼多項(xiàng)式的模碼多項(xiàng)式的模 (xn+1) 運(yùn)算運(yùn)算q 以以 p=3 為模的剩余類(lèi)全體為模的剩余類(lèi)全體q 模模 3 運(yùn)算的規(guī)則如下：運(yùn)算的規(guī)則如下：120221010000210102202112

7、100210 第9頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 碼多項(xiàng)式碼多項(xiàng)式 碼多項(xiàng)式的模碼多項(xiàng)式的模 (xn+1) 運(yùn)算運(yùn)算q 碼字碼字 C C 循環(huán)循環(huán) i 次所得碼字的碼多項(xiàng)式：次所得碼字的碼多項(xiàng)式：q C(x) 乘以乘以 x，再除以，再除以 (xn+1)，得：，得：ininininnininnnncxcxcxcxcxCcxcxcxC 1102211)(02211)()(1)(11)()1(1102123121 nnnnnnnnnnxxCcxcxcxcxcxccxxxC第10頁(yè)2021-

8、12-13Department of Electronics and Information, NCUT Song Peng(3) 碼多項(xiàng)式碼多項(xiàng)式 碼多項(xiàng)式的模碼多項(xiàng)式的模 (xn+1) 運(yùn)算運(yùn)算q 上式表明：上式表明：碼字循環(huán)一次的碼多項(xiàng)式碼字循環(huán)一次的碼多項(xiàng)式 C(1)(x) 是原碼多項(xiàng)式是原碼多項(xiàng)式 C(x)乘以乘以 x 除以除以 (xn+1) 的余式。寫(xiě)作：的余式。寫(xiě)作：q C(x) 的的 i 次循環(huán)移位次循環(huán)移位 C(i)(x) 是是 C(x) 乘以乘以 xi 除以除以 (xn+1) 的余式，的余式，即：即：q 結(jié)論：結(jié)論：循環(huán)碼的碼字的循環(huán)碼的碼字的 i 次循環(huán)移位等效于將碼多項(xiàng)

9、次循環(huán)移位等效于將碼多項(xiàng)式乘式乘 xi 后再模后再模 (xn+1)。）（模（模1)()()1( nxxCxxC）（模模1)()()( niixxCxxC第11頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 舉例：舉例：(7,3) 循環(huán)碼循環(huán)碼可由任一個(gè)碼字，比如可由任一個(gè)碼字，比如 (0011101) 經(jīng)過(guò)循環(huán)移位，得到經(jīng)過(guò)循環(huán)移位，得到其它其它 6 個(gè)非個(gè)非 0 0 碼字；碼字；可由相應(yīng)的碼多項(xiàng)式可由相應(yīng)的碼多項(xiàng)式 (x4+x3+x2+1)，乘以，乘以 xi(i=1,2,6)，再模再模 (x7+1

10、) 運(yùn)算得到其它運(yùn)算得到其它 6 個(gè)非個(gè)非 0 0 碼多項(xiàng)式。移位過(guò)碼多項(xiàng)式。移位過(guò)程和相應(yīng)的多項(xiàng)式運(yùn)算如表程和相應(yīng)的多項(xiàng)式運(yùn)算如表8.1所示。所示。第12頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 舉例：舉例：(7,3) 循環(huán)碼循環(huán)碼第13頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣(2) 循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式(3) 生成多項(xiàng)式和碼多項(xiàng)式的關(guān)系生成

11、多項(xiàng)式和碼多項(xiàng)式的關(guān)系(4) 如何尋找一個(gè)合適的生成多項(xiàng)式如何尋找一個(gè)合適的生成多項(xiàng)式(5) 循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣第14頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣循環(huán)碼的循環(huán)特性循環(huán)碼的循環(huán)特性：可由一個(gè)碼字的循環(huán)移位得到其它的非：可由一個(gè)碼字的循環(huán)移位得到其它的非 0 0 碼碼字。在字。在 (n,k) 循環(huán)碼的循環(huán)碼的 2k 個(gè)碼字中，取前個(gè)碼字中，取前 (k1) 位皆為位皆為 0 的碼字的碼字 g(x)（次數(shù)（次數(shù) r=n

12、k），再經(jīng)），再經(jīng) (k1) 次循環(huán)移位，共得到次循環(huán)移位，共得到 k 個(gè)碼字：個(gè)碼字： g(x), xg(x), , xk1g(x) 這這 k 個(gè)碼字是相互獨(dú)立的，可作為碼生成矩陣的個(gè)碼字是相互獨(dú)立的，可作為碼生成矩陣的 k 行，得到行，得到循環(huán)循環(huán)碼的生成矩陣碼的生成矩陣 G(x)。矩陣中的元素是多項(xiàng)式：矩陣中的元素是多項(xiàng)式： 010211101121)()()()()(gxgxgxgxgxgxgxgxgxgxxgxgxxgxxGknknknknkknknkk第15頁(yè)2021-12-13Department of Electronics and Information, NCUT Song

13、 Peng(1) 循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣將矩陣中的多項(xiàng)式改寫(xiě)成對(duì)應(yīng)的將矩陣中的多項(xiàng)式改寫(xiě)成對(duì)應(yīng)的 n 重矢量形式：重矢量形式： 01個(gè)個(gè) k 0101010100000000000ggggggggggggknknknknGG01個(gè)個(gè) k第16頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式碼的生成矩陣一旦確定，碼就確定了；碼的生成矩陣一旦確定，碼就確定了；(n,k) 循環(huán)碼可由它的一個(gè)循環(huán)碼可由它的一個(gè) (nk) 次碼多項(xiàng)式次碼多項(xiàng)式 g(x) 來(lái)確來(lái)確

14、定；定；g(x) 生成了生成了 (n,k) 循環(huán)碼，循環(huán)碼，稱(chēng)稱(chēng) g(x) 為碼的生成多項(xiàng)式。為碼的生成多項(xiàng)式。 g(x)是一個(gè)是一個(gè)(nk)次首次首1多項(xiàng)式多項(xiàng)式0111)(gxgxgxxgknknkn 第17頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多項(xiàng)式生成多項(xiàng)式和和碼多項(xiàng)式碼多項(xiàng)式的關(guān)系的關(guān)系定理定理8.2.1：在在 (n,k) 循環(huán)碼中，生成多項(xiàng)式循環(huán)碼中，生成多項(xiàng)式 g(x)是惟一的是惟一的(nk)次碼多次碼多項(xiàng)式項(xiàng)式,且次數(shù)是最低的。且次數(shù)是最低的。證明證明： 先證先證在在

15、(n,k) 循環(huán)碼系統(tǒng)中存在循環(huán)碼系統(tǒng)中存在 (nk) 次碼多項(xiàng)式。次碼多項(xiàng)式。因?yàn)樵谝驗(yàn)樵?2k 個(gè)信個(gè)信息組中有一個(gè)信息組為息組中有一個(gè)信息組為 ，它的對(duì)應(yīng)碼多項(xiàng)式的次數(shù)為：，它的對(duì)應(yīng)碼多項(xiàng)式的次數(shù)為： n1(k1)=nk (nk) 次碼多項(xiàng)式是最低次碼多項(xiàng)式。次碼多項(xiàng)式是最低次碼多項(xiàng)式。v 若若 g(x) 不是最低次碼多項(xiàng)式，那么設(shè)更低次的碼多項(xiàng)式為不是最低次碼多項(xiàng)式，那么設(shè)更低次的碼多項(xiàng)式為 g(x) ，其次數(shù)為其次數(shù)為 (nk1)。 g(x) 的前面的前面 k 位為位為 0，即，即 k 個(gè)信息位全為個(gè)信息位全為 0，而監(jiān)督位不為而監(jiān)督位不為 0，這對(duì)線(xiàn)性碼來(lái)說(shuō)是不可能的，因此，這對(duì)線(xiàn)

16、性碼來(lái)說(shuō)是不可能的，因此 g(x) 是最低是最低次的碼多項(xiàng)式，次的碼多項(xiàng)式，即即 gnk 必為必為 1。10001個(gè)個(gè) k第18頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多項(xiàng)式生成多項(xiàng)式和和碼多項(xiàng)式碼多項(xiàng)式的關(guān)系的關(guān)系定理定理8.2.1：在在 (n,k) 循環(huán)碼中，生成多項(xiàng)式循環(huán)碼中，生成多項(xiàng)式 g(x)是惟一的是惟一的(nk)次碼多次碼多項(xiàng)式項(xiàng)式,且次數(shù)是最低的。且次數(shù)是最低的。證明證明： (nk) 次碼多項(xiàng)式是最低次碼多項(xiàng)式。次碼多項(xiàng)式是最低次碼多項(xiàng)式。v g0=1，否則經(jīng)，否則經(jīng) (

17、n1) 次左移循環(huán)后將得到低于次左移循環(huán)后將得到低于 (nk) 次的碼多項(xiàng)式。次的碼多項(xiàng)式。v g(x) 是惟一的是惟一的 (nk) 次多項(xiàng)式。如果存在另一個(gè)次多項(xiàng)式。如果存在另一個(gè) (nk) 次碼多項(xiàng)式，次碼多項(xiàng)式，設(shè)為設(shè)為 g(x) ，根據(jù)線(xiàn)性碼的封閉性，則，根據(jù)線(xiàn)性碼的封閉性，則 g(x) + g(x) 也必為一個(gè)碼多項(xiàng)式。也必為一個(gè)碼多項(xiàng)式。由于由于 g(x)和和 g(x) 的次數(shù)相同，它們的和式的的次數(shù)相同，它們的和式的 (nk) 次項(xiàng)系數(shù)為次項(xiàng)系數(shù)為0，那么，那么 g(x) + g(x) 是一個(gè)次數(shù)低于是一個(gè)次數(shù)低于 (nk) 次的碼多項(xiàng)式，前面已證明次的碼多項(xiàng)式，前面已證明 g(

18、x) 的次的次數(shù)是最低的，因此數(shù)是最低的，因此 g(x) 不能存在，所以不能存在，所以 g(x) 是惟一的是惟一的 (nk) 次碼多項(xiàng)式。次碼多項(xiàng)式。第19頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多項(xiàng)式生成多項(xiàng)式和和碼多項(xiàng)式碼多項(xiàng)式的關(guān)系的關(guān)系定理定理8.2.2：在在 (n,k) 循環(huán)碼中，每個(gè)碼多項(xiàng)式循環(huán)碼中，每個(gè)碼多項(xiàng)式 C(x) 都是都是 g(x) 的倍式；的倍式；而每個(gè)為而每個(gè)為 g(x) 倍式且次數(shù)小于或等于倍式且次數(shù)小于或等于 (n1) 的多項(xiàng)式，必是一個(gè)碼的多項(xiàng)式，必是一個(gè)

19、碼多項(xiàng)式。多項(xiàng)式。證明證明： 設(shè)設(shè) mm=(mk1,mk2,m0) 為任一信息組，為任一信息組，G(x) 為該為該 (n,k) 循環(huán)碼循環(huán)碼的的生成矩陣，則相應(yīng)的碼多項(xiàng)式為：生成矩陣，則相應(yīng)的碼多項(xiàng)式為：C(x)=mmG(x)：)()()()()()(),()(0221121021xgmxmxmxgxxgxgxxgxmmmxCkkkkkkkk 第20頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多項(xiàng)式生成多項(xiàng)式和和碼多項(xiàng)式碼多項(xiàng)式的關(guān)系的關(guān)系定理定理8.2.2：在在 (n,k) 循環(huán)碼中，每個(gè)

20、碼多項(xiàng)式循環(huán)碼中，每個(gè)碼多項(xiàng)式 C(x) 都是都是 g(x) 的倍式；的倍式；而每個(gè)為而每個(gè)為 g(x) 倍式且次數(shù)小于或等于倍式且次數(shù)小于或等于 (n1) 的多項(xiàng)式，必是一個(gè)碼的多項(xiàng)式，必是一個(gè)碼多項(xiàng)式。多項(xiàng)式。證明證明： 循環(huán)碼的任一碼多項(xiàng)式為循環(huán)碼的任一碼多項(xiàng)式為 g(x) 的倍式。的倍式。 凡是為凡是為 g(x) 的倍式且次數(shù)小于或等于的倍式且次數(shù)小于或等于 (n1) 的多項(xiàng)式，一定能分的多項(xiàng)式，一定能分解成上式的形式，因而它就是信息多項(xiàng)式：解成上式的形式，因而它就是信息多項(xiàng)式：m(x)=(mk1xk1+mk2 1xk2+m0) 并由生成矩陣并由生成矩陣 G(x) 所生成的碼多項(xiàng)式。所

21、生成的碼多項(xiàng)式。第21頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多項(xiàng)式生成多項(xiàng)式和和碼多項(xiàng)式碼多項(xiàng)式的關(guān)系的關(guān)系定理定理8.2.3( (定理定理8.2.2的逆定理的逆定理) )：在一個(gè)在一個(gè) (n,k) 線(xiàn)性碼中，線(xiàn)性碼中，如果全部碼多項(xiàng)式都是最低次的如果全部碼多項(xiàng)式都是最低次的 (nk) 次碼多項(xiàng)式的倍式，次碼多項(xiàng)式的倍式，則此線(xiàn)性碼為一個(gè)則此線(xiàn)性碼為一個(gè) (n,k) 循環(huán)碼。循環(huán)碼。注注：一般說(shuō)來(lái)，這種循環(huán)碼仍具有把一般說(shuō)來(lái)，這種循環(huán)碼仍具有把 (n,k) 線(xiàn)性碼碼中任線(xiàn)性碼碼中任一非

22、一非 0 0 碼字循環(huán)移位必為一碼字的循環(huán)特性，但從一個(gè)碼字循環(huán)移位必為一碼字的循環(huán)特性，但從一個(gè)非非 0 0 碼字出發(fā)，進(jìn)行循環(huán)移位，就未必能得到碼的所有碼字出發(fā)，進(jìn)行循環(huán)移位，就未必能得到碼的所有非非 0 0 碼字了。所以稱(chēng)這種循環(huán)碼為碼字了。所以稱(chēng)這種循環(huán)碼為推廣循環(huán)碼推廣循環(huán)碼。第22頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多項(xiàng)式生成多項(xiàng)式和和碼多項(xiàng)式碼多項(xiàng)式的關(guān)系的關(guān)系 碼字循環(huán)關(guān)系圖碼字循環(huán)關(guān)系圖q 單純循環(huán)碼的單純循環(huán)碼的碼字循環(huán)圖：碼字循環(huán)圖：(7,3)循環(huán)碼循環(huán)碼第23

23、頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多項(xiàng)式生成多項(xiàng)式和和碼多項(xiàng)式碼多項(xiàng)式的關(guān)系的關(guān)系 碼字循環(huán)關(guān)系圖碼字循環(huán)關(guān)系圖q 推廣循環(huán)碼的推廣循環(huán)碼的碼字循環(huán)圖：碼字循環(huán)圖： (6,3)循環(huán)碼循環(huán)碼第24頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何尋找一個(gè)合適的生成多項(xiàng)式如何尋找一個(gè)合適的生成多項(xiàng)式循環(huán)碼的碼多項(xiàng)式等于信息多項(xiàng)式乘以生成多項(xiàng)式：循環(huán)碼的碼多項(xiàng)式等于信息多項(xiàng)式乘以生成多項(xiàng)式：

24、對(duì)一個(gè)循環(huán)碼只要生成多項(xiàng)式一旦確定，碼就確定了，編碼問(wèn)題對(duì)一個(gè)循環(huán)碼只要生成多項(xiàng)式一旦確定，碼就確定了，編碼問(wèn)題就解決了。就解決了。作一循環(huán)碼的關(guān)鍵，就在于尋找一個(gè)適當(dāng)?shù)纳啥囗?xiàng)式。作一循環(huán)碼的關(guān)鍵，就在于尋找一個(gè)適當(dāng)?shù)纳啥囗?xiàng)式。)()()()()()(),()(0221121021xgmxmxmxgxxgxgxxgxmmmxCkkkkkkkk 第25頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何尋找一個(gè)合適的生成多項(xiàng)式如何尋找一個(gè)合適的生成多項(xiàng)式定理定理8.2.4： (n,k) 循環(huán)碼的生

25、成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式 g(x) 是是 (xn+1)的因式，即：的因式，即： xn+1=h(x) g(x)。證明證明： 由于由于 xk g(x) 是是 n 次多項(xiàng)式，可表示為：次多項(xiàng)式，可表示為：xk g(x)=1 (xn+1)+ g(k)(x) (8.2.1)v 式中式中 g(k)(x) 是多項(xiàng)式是多項(xiàng)式 g(x) 乘以乘以 xk 除以除以 (xn+1) 的余式。的余式。v 根據(jù)循環(huán)碼的移位關(guān)系，它是根據(jù)循環(huán)碼的移位關(guān)系，它是 g(x) 循環(huán)移位循環(huán)移位 k 次所得到的多項(xiàng)次所得到的多項(xiàng)式，因而式，因而 g(k)(x) 是是 g(x) 的倍式。的倍式。 設(shè)：設(shè)：g(k)(x)=m(x)g

26、(x) 代入式代入式(8.2.1)得：得：(xn+1)=xk+m(x)g(x) 即：即：g(x) 是是 (xn+1) 的因式。的因式。歐幾里德除法：設(shè) b 是正整數(shù)，則任意正整數(shù) a b 皆可惟一地表示成：a=qb+r 0r b第26頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何尋找一個(gè)合適的生成多項(xiàng)式如何尋找一個(gè)合適的生成多項(xiàng)式定理定理8.2.5：若若 g(x) 是一個(gè)是一個(gè) (nk) 次次 多項(xiàng)式，且為多項(xiàng)式，且為(xn+1) 的因式，則的因式，則 g(x) 生成一個(gè)生成一個(gè) (n,k)

27、循環(huán)碼。循環(huán)碼。證明證明：由于由于 g(x) 是一個(gè)是一個(gè) (nk) 次多項(xiàng)式，且為次多項(xiàng)式，且為 (xn+1) 的因式，所以：的因式，所以：g(x), x g(x), xk1 g(x) 是是 k 個(gè)次數(shù)小于個(gè)次數(shù)小于 n，并且彼此獨(dú)立的多項(xiàng)，并且彼此獨(dú)立的多項(xiàng)式；式； )()()()()(21xgxxgxgxxgxxGkk將此多項(xiàng)式用作碼的生成矩陣的將此多項(xiàng)式用作碼的生成矩陣的 k 行，得到行，得到 (n,k) 線(xiàn)性碼的生成矩陣；線(xiàn)性碼的生成矩陣；第27頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(4

28、) 如何尋找一個(gè)合適的生成多項(xiàng)式如何尋找一個(gè)合適的生成多項(xiàng)式定理定理8.2.5：若若 g(x) 是一個(gè)是一個(gè) (nk) 次次 多項(xiàng)式，且為多項(xiàng)式，且為(xn+1) 的因式，則的因式，則 g(x) 生生成一個(gè)成一個(gè) (n,k) 循環(huán)碼。循環(huán)碼。證明證明： 設(shè)信息組設(shè)信息組 mm=(mk1,mk2,m0)，則相應(yīng)的碼字為：，則相應(yīng)的碼字為： C(x)=m m G(x)=(mk1xk1+mk2 1xk2+m0) g(x)= m(x) g(x)v C(x) 的次數(shù)的次數(shù)n1；v m(x) 是是 2k 個(gè)信息多項(xiàng)式的表示式；個(gè)信息多項(xiàng)式的表示式；v 所以：所以：C(x) 即為相應(yīng)即為相應(yīng) 2k 個(gè)碼多項(xiàng)

29、式的表示式。個(gè)碼多項(xiàng)式的表示式。 因此：因此：g(x) 生成一個(gè)生成一個(gè) (n,k) 線(xiàn)性碼。線(xiàn)性碼。 C(x) 是是 (nk) 次多項(xiàng)式次多項(xiàng)式 g(x) 的倍式，所以的倍式，所以 g(x) 生成一個(gè)生成一個(gè) (n,k)循環(huán)碼。循環(huán)碼。第28頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何尋找一個(gè)合適的生成多項(xiàng)式如何尋找一個(gè)合適的生成多項(xiàng)式定理定理8.2.5：若若 g(x) 是一個(gè)是一個(gè) (nk) 次次 多項(xiàng)式，且為多項(xiàng)式，且為(xn+1) 的因式，則的因式，則 g(x) 生成一個(gè)生成一個(gè) (

30、n,k) 循環(huán)碼。循環(huán)碼。 結(jié)論：結(jié)論：求作一個(gè)求作一個(gè) (n,k) 循環(huán)碼時(shí)，只要分解多項(xiàng)式循環(huán)碼時(shí)，只要分解多項(xiàng)式(xn+1) ，從中取出，從中取出(nk)次因式作生成多項(xiàng)式即可。次因式作生成多項(xiàng)式即可。 例：例：求求 (7,3) 循環(huán)碼的生成多項(xiàng)式。循環(huán)碼的生成多項(xiàng)式。解解：v 分解多項(xiàng)式分解多項(xiàng)式 x7+1，取其，取其 4 次因式作生成多項(xiàng)式：次因式作生成多項(xiàng)式：x7+1= (x+1) (x3+x2+1) (x3+x+1)v 可將一次和任一個(gè)三次因式的乘積作為生成多項(xiàng)式，可?。嚎蓪⒁淮魏腿我粋€(gè)三次因式的乘積作為生成多項(xiàng)式，可?。篻1(x)= (x+1) (x3+x2+1) = x4+x

31、2+x+1 或或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1第29頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣 循環(huán)碼的監(jiān)督多項(xiàng)式循環(huán)碼的監(jiān)督多項(xiàng)式：設(shè)設(shè) g(x) 為為 (n,k) 循環(huán)碼的生成多項(xiàng)式，必為循環(huán)碼的生成多項(xiàng)式，必為 (xn+1) 的因式，則有：的因式，則有：xn+1=h(x) g(x)，式中式中 h(x) 為為 k 次多項(xiàng)式，稱(chēng)次多項(xiàng)式，稱(chēng)為為 (n,k) 循環(huán)碼的監(jiān)督多項(xiàng)式。循環(huán)碼的監(jiān)督多項(xiàng)式。

32、 (n,k) 循環(huán)碼也可由其監(jiān)督多項(xiàng)式完全確定。循環(huán)碼也可由其監(jiān)督多項(xiàng)式完全確定。 舉例舉例：(7,3) 循環(huán)碼：循環(huán)碼：x7+1= (x3+x+1)(x4+x2+x+1)q 4 次多項(xiàng)式為生成多項(xiàng)式：次多項(xiàng)式為生成多項(xiàng)式：g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0 3 次多項(xiàng)式是監(jiān)督多項(xiàng)式：次多項(xiàng)式是監(jiān)督多項(xiàng)式：h(x)=x3+x+1=h3x3+h2x2+h1x+h0第30頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式和

33、監(jiān)督矩陣 循環(huán)碼的監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣 由等式由等式 x7+1= h(x) g(x) 兩兩 端同次項(xiàng)系數(shù)相等得：端同次項(xiàng)系數(shù)相等得： 將上面的方程組寫(xiě)成將上面的方程組寫(xiě)成 矩陣形式：矩陣形式： 0000332463223145312213044302112033hghgxhghghgxhghghghgxhghghghgx的的系系數(shù)數(shù)：的的系系數(shù)數(shù)：的的系系數(shù)數(shù)：的的系系數(shù)數(shù)：Tggggghhhhhhhhhhhhhhhh0 0 0123432103210321032100000000000000001223331)(hxhxhxhxxxh 01223344241)(gxgxgxgxgxxxx

34、g 第31頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣 循環(huán)碼的監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣上式中，列陣的元素是生成多項(xiàng)式上式中，列陣的元素是生成多項(xiàng)式 g(x) 的系數(shù)，是一個(gè)碼字，那的系數(shù)，是一個(gè)碼字，那么第一個(gè)矩陣則為么第一個(gè)矩陣則為 (7,3) 循環(huán)碼的循環(huán)碼的監(jiān)督矩陣，監(jiān)督矩陣，即：即：)2 . 2 . 8(0000000000003210321032103210)3 , 7( hhhhhhhhhhhhhhhhHH第32頁(yè)2021-1

35、2-13Department of Electronics and Information, NCUT Song Peng(5) 循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣 循環(huán)碼監(jiān)督矩陣的構(gòu)成循環(huán)碼監(jiān)督矩陣的構(gòu)成由式由式 (8.2.2) 可見(jiàn)，監(jiān)督矩陣的第一行是碼的監(jiān)督多項(xiàng)式可見(jiàn)，監(jiān)督矩陣的第一行是碼的監(jiān)督多項(xiàng)式 h(x) 的系的系數(shù)的數(shù)的反序排列，反序排列，第二、三、四行是第一行的移位；第二、三、四行是第一行的移位；可用監(jiān)督多項(xiàng)式的系數(shù)來(lái)構(gòu)成監(jiān)督矩陣：可用監(jiān)督多項(xiàng)式的系數(shù)來(lái)構(gòu)成監(jiān)督矩陣： 其中其中h*(x) 表示表示 h(x) 的反多項(xiàng)式的反多項(xiàng)式)3 . 2 . 8(000

36、1011001011001011001011000)()()()(*3*2*)3 , 7( xhxxhxxxhxhHH第33頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣 循環(huán)碼監(jiān)督矩陣的構(gòu)成循環(huán)碼監(jiān)督矩陣的構(gòu)成(n,k) 循環(huán)碼的監(jiān)督矩陣：循環(huán)碼的監(jiān)督矩陣： 0011101101100)()()(11111111*1*),(kkkkknknhhhhhhhhxhxxxhxhHH第34頁(yè)2021-12-13Department of Elect

37、ronics and Information, NCUT Song Peng(5) 循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣 對(duì)偶問(wèn)題對(duì)偶問(wèn)題如果如果 xn+1=h(x) g(x)，其中，其中 g(x) 為為 (nk) 次多項(xiàng)式，以次多項(xiàng)式，以 g(x)為生成為生成多項(xiàng)式，則生成一個(gè)多項(xiàng)式，則生成一個(gè) (n,k) 循環(huán)碼；循環(huán)碼；以以 h(x) 為生成多項(xiàng)式，則生成為生成多項(xiàng)式，則生成 (n,nk) 循環(huán)碼；循環(huán)碼；這兩個(gè)循環(huán)碼互為對(duì)偶碼。這兩個(gè)循環(huán)碼互為對(duì)偶碼。第35頁(yè)2021-12-13Department of Electronics and Information, N

38、CUT Song Peng(1) 系統(tǒng)循環(huán)碼構(gòu)成系統(tǒng)循環(huán)碼構(gòu)成信息向量信息向量：mm=(mk1,mk2,m0)信息多項(xiàng)式信息多項(xiàng)式：m(x)=mk1xk1+mk2 xk2+m0 碼多項(xiàng)式碼多項(xiàng)式的高次冪部分等于的高次冪部分等于 m(x)，即：，即： C(x)=cn1xn1+ cnkxnk+ cnk1xnk1 +c1x +c0 =xnk m(x)+q(x) （q(x)的次數(shù)的次數(shù)nk）校驗(yàn)位多項(xiàng)式校驗(yàn)位多項(xiàng)式：q(x)由于碼多項(xiàng)式是生成多項(xiàng)式的倍式，所以：由于碼多項(xiàng)式是生成多項(xiàng)式的倍式，所以：C(x)= xnkm(x)+q(x)=a(x)g(x)0 （mod g(x)）q(x)=C(x)+ xn

39、km(x)xnkm(x) （mod g(x)）第36頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 系統(tǒng)循環(huán)碼構(gòu)成系統(tǒng)循環(huán)碼構(gòu)成 循環(huán)碼的系統(tǒng)碼形式為循環(huán)碼的系統(tǒng)碼形式為：C(x)= xnkm(x)+ (xnkm(x) mod g(x) 系統(tǒng)循環(huán)碼構(gòu)造過(guò)程步驟系統(tǒng)循環(huán)碼構(gòu)造過(guò)程步驟q 信息多項(xiàng)式乘信息多項(xiàng)式乘 xnk： xnkm(x)q 對(duì)對(duì) xnkm(x) 求余式求余式：q(x)xnkm(x) (mod g(x)q 求碼多項(xiàng)式求碼多項(xiàng)式：C(x)=xnkm(x)+ ( xnkm(x) mod g(

40、x) =xnkm(x)+ q(x)第37頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 舉例舉例例例6.3.5：在由：在由 g(x)=x4+x3+x2+1生成的生成的 (7,3) 循環(huán)碼中，求循環(huán)碼中，求信息組信息組m=(101)的對(duì)應(yīng)碼多項(xiàng)式。的對(duì)應(yīng)碼多項(xiàng)式。1)()() 1()(462437 xxrxgxxxxxmx得得到到余余式式：，除除以以于于是是碼碼多多項(xiàng)項(xiàng)式式為為：1)()()(464 xxxxrxmxxC第38頁(yè)2021-12-13Department of Electronics a

41、nd Information, NCUT Song Peng(1) 多項(xiàng)式加法電路多項(xiàng)式加法電路(2) 多項(xiàng)式乘法電路多項(xiàng)式乘法電路(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路第39頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 多項(xiàng)式加法電路多項(xiàng)式加法電路多項(xiàng)式多項(xiàng)式 a(x)=anxn+an1xn1+a1x+a0 表示的是時(shí)間序列表示的是時(shí)間序列a a=(an,an1,a1,a0)，因此多項(xiàng)式的計(jì)算表現(xiàn)為對(duì)時(shí)間序列的操作；，因此多項(xiàng)式的計(jì)算表現(xiàn)為對(duì)時(shí)間序列的操作；對(duì)二進(jìn)制多項(xiàng)式系數(shù)的基對(duì)二進(jìn)制多項(xiàng)式系數(shù)

42、的基本操作為模本操作為模 2 加和模加和模 2 乘；乘；電路圖運(yùn)算符號(hào)的意義：電路圖運(yùn)算符號(hào)的意義：第40頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 多項(xiàng)式加法電路多項(xiàng)式加法電路 A(x) 與與 B(x) 的相加電路的相加電路第41頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 多項(xiàng)式乘法電路多項(xiàng)式乘法電路多項(xiàng)式乘以多項(xiàng)式乘以 x 等價(jià)為時(shí)間序列等價(jià)為時(shí)間序列 a a 延遲一位；延遲一位；多項(xiàng)式多項(xiàng)式

43、 a(x) 與多項(xiàng)式與多項(xiàng)式 g(x) 的乘等價(jià)為的乘等價(jià)為 a(x) 的不同位移后的相加：的不同位移后的相加：a(x)g(x)=a(x)(g1(x)+ g2(x)= a(x)g1(x)+ a(x)g2(x) 多項(xiàng)式乘法電路：多項(xiàng)式乘法電路：設(shè)多項(xiàng)式的低位在前，電路中所有寄存器初態(tài)設(shè)多項(xiàng)式的低位在前，電路中所有寄存器初態(tài)為為 0。第42頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 多項(xiàng)式乘法電路多項(xiàng)式乘法電路多項(xiàng)式多項(xiàng)式乘法電路：乘法電路：第43頁(yè)2021-12-13Department of E

44、lectronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路當(dāng)當(dāng) g(x) =1，多項(xiàng)式，多項(xiàng)式 a(x) 模模 g(x) 的余式為的余式為 0，電路如圖所示。，電路如圖所示。第44頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路當(dāng)當(dāng) g(x)是單向式是單向式 g(x)=xk， a(x) 模模 g(x) 的余式的次數(shù)小于的余式的次數(shù)小于 k，進(jìn)入，進(jìn)入電路的輸入順序?yàn)殡娐返妮斎腠樞驗(yàn)?an,an1,a1,a0。a

45、(x)ak1xk1+ak2xk2+a1x+a0 (mod xk) 運(yùn)算電路如圖所示。運(yùn)算電路如圖所示。第45頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路由于由于 xk1 mod(x+1), k=0,1,2,。若。若 a(x) 的次數(shù)為的次數(shù)為 n，則：，則：a(x) = an1+an2+a1+a0（mod(x+1)） q0（mod 2） 運(yùn)算電路如圖所示：運(yùn)算電路如圖所示：第46頁(yè)2021-12-13Department of Electronics and Info

46、rmation, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路同樣由長(zhǎng)除法得：同樣由長(zhǎng)除法得： 運(yùn)算電路如圖所示：運(yùn)算電路如圖所示： niiiniiiniiiniiiaqaqxqqaaxa5 , 3 , 114 , 2 , 002105 , 3 , 14 , 2 , 0)1(mod()(其其中中：第47頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路多項(xiàng)式多項(xiàng)式 a(x) 模模 (x2+x+1) 的運(yùn)算電路如圖所示：的運(yùn)算電路如圖所示：第48頁(yè)2021

47、-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路一般的多項(xiàng)式模一般的多項(xiàng)式模 g(x)=grxr+gr1xr1+g1x+g0 的運(yùn)算電路如圖所的運(yùn)算電路如圖所示。示。移位寄存器初態(tài)全為移位寄存器初態(tài)全為0；當(dāng)當(dāng) a(x) 輸入完后，移位寄存器內(nèi)容輸入完后，移位寄存器內(nèi)容 (qr1, , q1, q0) 就是余式：就是余式：q(x)=qr1xr1+ qr2xr2+ +q1x+q0 a(x) (mod g(x)第49頁(yè)2021-12-13Department of Electronic

48、s and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路 多項(xiàng)式除法電路的構(gòu)造多項(xiàng)式除法電路的構(gòu)造q 多項(xiàng)式除法電路是一個(gè)由除式（這里就是生成多項(xiàng)式多項(xiàng)式除法電路是一個(gè)由除式（這里就是生成多項(xiàng)式 g(x)） g(x)=gnkxnk+gnk1xnk1+g1x+g0 所確定的所確定的反饋移位寄存器。反饋移位寄存器。q 除法電路的構(gòu)造方法除法電路的構(gòu)造方法l 移位寄存器的級(jí)數(shù)等于除式的次數(shù)移位寄存器的級(jí)數(shù)等于除式的次數(shù) nk；l 移位寄存器的反饋抽頭，由除式的各項(xiàng)系數(shù)移位寄存器的反饋抽頭，由除式的各項(xiàng)系數(shù) gi(i=0,1,nk) 決定：決定： 當(dāng)某個(gè)抽

49、頭當(dāng)某個(gè)抽頭=0時(shí)，對(duì)應(yīng)的反饋斷開(kāi)；時(shí)，對(duì)應(yīng)的反饋斷開(kāi)； 當(dāng)某個(gè)抽頭當(dāng)某個(gè)抽頭=1時(shí)，對(duì)應(yīng)的反饋接通。時(shí)，對(duì)應(yīng)的反饋接通。 完成除法所需的移位次數(shù)等于被除式的次數(shù)加完成除法所需的移位次數(shù)等于被除式的次數(shù)加1。第50頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路 多項(xiàng)式除法電路舉例多項(xiàng)式除法電路舉例q 利用除法電路完成兩個(gè)多項(xiàng)式除法運(yùn)算，求其余式的過(guò)程和將利用除法電路完成兩個(gè)多項(xiàng)式除法運(yùn)算，求其余式的過(guò)程和將兩個(gè)多項(xiàng)式進(jìn)行長(zhǎng)除運(yùn)算是完全一致的；兩個(gè)多項(xiàng)式進(jìn)行長(zhǎng)除運(yùn)算是完全

50、一致的；q (x5+x2)(x4+x3+x +1) 的長(zhǎng)除運(yùn)算過(guò)程：的長(zhǎng)除運(yùn)算過(guò)程：)(11)()()()(1133442452534第二余式第二余式第一余式第一余式除式除式被除式被除式商式商式 xxxxxxxxxxxxxxxx第51頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路 多項(xiàng)式除法電路舉例多項(xiàng)式除法電路舉例q(x5+x2)(x4+x3+x +1) 的長(zhǎng)除運(yùn)算過(guò)程：的長(zhǎng)除運(yùn)算過(guò)程：l每做一次除法運(yùn)算，被除式（或前次除法的余式）的首項(xiàng)被抵每做一次除法運(yùn)算，被除式（

51、或前次除法的余式）的首項(xiàng)被抵消，因而除法電路中每做一次除法運(yùn)算，最高項(xiàng)就移到寄存器消，因而除法電路中每做一次除法運(yùn)算，最高項(xiàng)就移到寄存器之外而丟掉；之外而丟掉；除式除首項(xiàng)外的其它各項(xiàng)系數(shù)都要加到被除式或前次運(yùn)算的余除式除首項(xiàng)外的其它各項(xiàng)系數(shù)都要加到被除式或前次運(yùn)算的余式中去，而除法電路的反饋正是按除式的規(guī)律連接的，恰好完式中去，而除法電路的反饋正是按除式的規(guī)律連接的，恰好完成所需的加法運(yùn)算。成所需的加法運(yùn)算。第52頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路 多項(xiàng)式除

52、法電路舉例多項(xiàng)式除法電路舉例q (x5+x2)(x4+x3+x +1) 運(yùn)算電路工作過(guò)程：運(yùn)算電路工作過(guò)程： 各級(jí)預(yù)先清零，被除式系數(shù)由移位寄存器第一級(jí)輸入，經(jīng)各級(jí)預(yù)先清零，被除式系數(shù)由移位寄存器第一級(jí)輸入，經(jīng) 4 次次移位后，最高項(xiàng)的系數(shù)到達(dá)移位寄存器右端出現(xiàn)反饋信號(hào)；移位后，最高項(xiàng)的系數(shù)到達(dá)移位寄存器右端出現(xiàn)反饋信號(hào)； 第一次對(duì)被除式作除法，下一個(gè)移位脈沖加入時(shí)，被除式首項(xiàng)第一次對(duì)被除式作除法，下一個(gè)移位脈沖加入時(shí)，被除式首項(xiàng) x5 移出寄存器，相當(dāng)于首項(xiàng)被抵消，反饋信號(hào)按除式規(guī)律與被除移出寄存器，相當(dāng)于首項(xiàng)被抵消，反饋信號(hào)按除式規(guī)律與被除式相應(yīng)項(xiàng)進(jìn)行式相應(yīng)項(xiàng)進(jìn)行模模 2 加加，移位寄存器

53、新的內(nèi)容即為第一余式；，移位寄存器新的內(nèi)容即為第一余式；第53頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路 多項(xiàng)式除法電路舉例多項(xiàng)式除法電路舉例q (x5+x2)(x4+x3+x +1) 運(yùn)算電路工作過(guò)程：運(yùn)算電路工作過(guò)程： 第一余式的首項(xiàng)第一余式的首項(xiàng) x4 的系數(shù)到達(dá)電路的末級(jí)，出現(xiàn)反饋信號(hào)，準(zhǔn)的系數(shù)到達(dá)電路的末級(jí)，出現(xiàn)反饋信號(hào)，準(zhǔn)備作第二次除法，當(dāng)下一個(gè)移位脈沖加入時(shí)，第一余式的首項(xiàng)移備作第二次除法，當(dāng)下一個(gè)移位脈沖加入時(shí)，第一余式的首項(xiàng)移出寄存器被丟掉，反饋信

54、號(hào)又把除式出寄存器被丟掉，反饋信號(hào)又把除式(除首項(xiàng)外除首項(xiàng)外)加到第一余式，得加到第一余式，得到第二余式（即所求余式）；到第二余式（即所求余式）； 為了使被除式全部移入寄存器，除法求余所需要的移位次數(shù)等為了使被除式全部移入寄存器，除法求余所需要的移位次數(shù)等于被除式次數(shù)加于被除式次數(shù)加 1。第54頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多項(xiàng)式除法電路多項(xiàng)式除法電路 多項(xiàng)式除法電路舉例多項(xiàng)式除法電路舉例q 表表 8.4.1 列出了電路的運(yùn)算過(guò)程列出了電路的運(yùn)算過(guò)程第55頁(yè)2021-12-13De

55、partment of Electronics and Information, NCUT Song Peng9.5.1 非系統(tǒng)碼編碼電路非系統(tǒng)碼編碼電路9.5.2 系統(tǒng)碼編碼電路系統(tǒng)碼編碼電路(1) 系統(tǒng)碼編碼的基本原理系統(tǒng)碼編碼的基本原理(2) 用用 (nk) 級(jí)移位寄存器實(shí)現(xiàn)的編碼電路級(jí)移位寄存器實(shí)現(xiàn)的編碼電路(3) 用用 k 級(jí)移位寄存器實(shí)現(xiàn)的編碼電路級(jí)移位寄存器實(shí)現(xiàn)的編碼電路第56頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng 循環(huán)碼碼多項(xiàng)式是生成多項(xiàng)式的倍式。循環(huán)碼碼多項(xiàng)式是生成多項(xiàng)式的倍式。

56、 非系統(tǒng)編碼電路非系統(tǒng)編碼電路/循環(huán)碼乘法編碼電路循環(huán)碼乘法編碼電路q 輸入輸入 a(x)=m(x)， m(x)的次數(shù)的次數(shù) kq 輸出輸出 a(x)g(x)=C(x)即是碼式，即是碼式，C(x)的次數(shù)的次數(shù) n9.5循環(huán)碼的編碼電路第57頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng 舉例：生成舉例：生成 (7,4) 漢明碼的生成多項(xiàng)式為漢明碼的生成多項(xiàng)式為 g(x)=x3+ x2+1，非系統(tǒng)編，非系統(tǒng)編碼電路如圖所示。電路共工作碼電路如圖所示。電路共工作 7 個(gè)時(shí)鐘節(jié)拍。個(gè)時(shí)鐘節(jié)拍。9.5循環(huán)碼的編碼

57、電路第58頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng 舉例：生成舉例：生成 (7,4) 漢明碼的生成多項(xiàng)式為漢明碼的生成多項(xiàng)式為 g(x)=x3+ x2+1，非系統(tǒng)編，非系統(tǒng)編碼電路如圖所示。電路共工作碼電路如圖所示。電路共工作 7 個(gè)時(shí)鐘節(jié)拍。個(gè)時(shí)鐘節(jié)拍。 由表可見(jiàn)，當(dāng)由表可見(jiàn)，當(dāng) m(x)=x3 + x時(shí)，非系統(tǒng)碼字時(shí)，非系統(tǒng)碼字 C(x) 為：為： C(x)= x6 + x5 +x4 + x =(x3+x)(x3 + x2 +1)9.5循環(huán)碼的編碼電路第59頁(yè)2021-12-13Departme

58、nt of Electronics and Information, NCUT Song Peng(1) 系統(tǒng)碼編碼的基本原理系統(tǒng)碼編碼的基本原理 求生成多項(xiàng)式求生成多項(xiàng)式 g(x)：分解多項(xiàng)式分解多項(xiàng)式 (xn+1)，取，取 (nk)次次 因式作生成多因式作生成多項(xiàng)式項(xiàng)式 g(x)，一般可通過(guò)查表完成。，一般可通過(guò)查表完成。 利用利用 g(x) 實(shí)現(xiàn)編碼實(shí)現(xiàn)編碼q 設(shè)設(shè)信息多項(xiàng)式信息多項(xiàng)式為：為：m(x)=mk1xk1+mk2 xk2+m0q 設(shè)設(shè)監(jiān)督多項(xiàng)式監(jiān)督多項(xiàng)式為：為：q(x)=qr1xr1+qr2 xr2+q0q (n,k) 循環(huán)碼的循環(huán)碼的碼多項(xiàng)式碼多項(xiàng)式為：為： C(x)=cn1

59、xn1+cn2xn2+cnkxnk +cnk1xnk1+c1x+c0 前前 k 項(xiàng)系數(shù)為信息位，后項(xiàng)系數(shù)為信息位，后 r= nk 項(xiàng)為校驗(yàn)位。項(xiàng)為校驗(yàn)位。q 所以：所以：cn1xn1+cnkxnk=xnk(mk1xk1+m0)=xnkm(x) cnk1xnk1+c0=qr1xr1+q0=q(x)9.5循環(huán)碼的編碼電路第60頁(yè)2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 用用 (nk) 級(jí)移位寄存器實(shí)現(xiàn)的編碼電路級(jí)移位寄存器實(shí)現(xiàn)的編碼電路 循環(huán)碼編碼電路結(jié)構(gòu)和工作原理循環(huán)碼編碼電路結(jié)構(gòu)和工作原理q 工

60、作原理工作原理：二元二元 (n,k) 循環(huán)碼的編碼是將信息多項(xiàng)式循環(huán)碼的編碼是將信息多項(xiàng)式 m(x) 乘乘 xnk 后再除以生成多項(xiàng)式后再除以生成多項(xiàng)式 g(x) 求出它的余式，即為監(jiān)督位多項(xiàng)式求出它的余式，即為監(jiān)督位多項(xiàng)式 q(x)。C(x)= xnkm(x)+（xnkm(x) mod g(x)）q 二元二元 (n,k) 循環(huán)碼的編碼電路就是以循環(huán)碼的編碼電路就是以 g(x) 為除式的除法電路，而為除式的除法電路，而輸入的被除式為輸入的被除式為 xnkm(x) 。q 實(shí)際的編碼電路如圖實(shí)際的編碼電路如圖 8.5.3 所示。所示。 其級(jí)數(shù)等于其級(jí)數(shù)等于 g(x) 的次數(shù)的次數(shù) (nk) ； 反