循 环 码 （II）.

Presentation on theme: "循 环 码 （II）."— Presentation transcript:

1 循 环 码 （II）

2 内容 多项式乘法和除法电路 循环码的编码电路(乘法和除法)

3 多项式乘法 多项式乘法

4 多项式乘法电路 a0,a1,…ak 乘B(x)运算电路 (利用校验多项式h(x)编码时会用到) b0 b1 b2 br-2 br-1 br
输出C(x) 输入A(x) a0,a1,…ak 乘B(x)运算电路 (利用校验多项式h(x)编码时会用到) 例5.11

5 多项式乘法电路 a0,a1,…ak 输出C(x) akb0 akb1 akbr-2 akbr-1 b1 b2 br-2 b1 b0 br-1
输入A(x) a0,a1,…ak 乘B(x)运算电路

6 多项式除法 多项式除法 除式 B(x) 商式 被除式 A(x) … …

7 多项式除法电路 a0,a1,…ak -b1 b1 br-1 输出商q(x) 输入A(x) -b2 -br-1 -b0 除B(x)运算电路
ak-r+1 ak-r+2 ak-1 ak a0,a1,…ak 除B(x)运算电路 除式B(x)构成电路，被除式A(x)的系数依次送入电路

8 多项式相乘相除电路 a0,a1,…ak h0 h1 h2 hr-2 b1 hr-1 hr 输入A(x) -g1 gr-1 输出商q(x)
乘H(x), 除g(x)运算电路

9 多项式相乘相除电路 当H(x)、G(x)次数不同时 输出 1 x x3 ＋ ＋ ＋ 1 x2 输入

10 循环码编码电路 循环码编码电路 n-k 级编码器 基本原理：利用生成多项式g(x) 若要求编成非系统码形式，则利用乘法电路
若要求编成系统码形式，则利用除法电路

11 n-k级乘法电路(非系统码形式) 取g(x), xg(x), …, xk-1g(x)的系数可构成生成矩阵G

12 n-k级乘法电路(非系统码形式) 若信息序列 m=(mk-1, mk-2, …, m0),则mG对应的n维向量为：
该n维向量正是多项式m(x)g(x)的系数

13 n-k级乘法电路(非系统码形式) m0,m1,…mk 输入m(x)是信息序列，g(x)为生成多项式 输出C(x) mk-1 g1
mk-1 gn-k-1 mk-1 gn-k mk-1 g0 g1 g2 gn-k-2 g0 gn-k-1 b1 gn-k b1 输入m(x) m0,m1,…mk 乘g(x)运算电路 输入m(x)是信息序列，g(x)为生成多项式

14 Example GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1，试画一个[7,4]循环码的n-k级乘法编码电路。 ＋ ＋ 输出c(x) 输入m(x)

15 循环码的系统码 由于生成矩阵G中的k行要求线性无关，因此在求余式时，可选择k个线性无关的信息组 (1,0,0,…,0) xk-1
…(0,0,0,…,0,1) 1

16 循环码的系统码 表示ri(x)的系数

17 n-k级乘法电路（系统码形式） 对任意信息多项式m(x), xn-km(x)除以g(x)可得余式r(x)，m(x)的系数为信息序列m，r(x) 的系数为m对应的校验比特 若信息序列 m=(mk-1, mk-2,…m0)；对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+…+m0 因此，循环码的系统码电路是信息多项式m(x)乘xn-k,除以g(x)的实现电路

18 n-k级乘法电路（系统码形式） m0,m1,…mk-1 门1 gn-k-1 -g0 -g1 -g2 输入m(x)
乘xn-k除g(x)运算电路 门1 门2

19 Example GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1，试画一个[7,4]循环码的n-k级系统码形式的乘法编码电路。 门1 门2 ＋ ＋ 输出c(x) 输入m(x)

20 k 级编码器 基本原理：利用校验多项式h(x)；为系统码编码电路 若信息序列 m=(mk-1, mk-2,…m0)
对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+…+m0 码多项式C(x)= m(x)g(x),且C(x)为系统码 h(x)C(x)= h(x)m(x)g(x) = m(x)(xn-1) = m(x)xn-m(x) = mk-1xn+k-1+ mk-2xn+k-2+…+m0xn -(mk-1xk-1+mk-2xk-2+…m0)

21 k 级编码器 h(x)C(x)的乘积中，xn-1, xn-2,… xk次的系数为零
h0 cn-1 +h1 cn …+hk cn-1-k=0 h0 cn-2 +h1 cn …+hk cn-2-k=0 h0 cn-3 +h1 cn …+hk cn-3-k=0 h0 ck +h1 ck-1 + …+hk c0=0

22 k 级编码器 由于hk=1 cn-1-k = - (h0 cn-1 +h1 cn-1-1 + …+hk-1 cn-1-(k-1))
cn-k-(n-k) = - (h0 ck +h1 ck-1 + …+hk-1 c1)

23 k 级编码器 循环码k级编码电路 -h0 -h1 -h2 -hk-2 b1 -hk-1 输入信息 门 cn-1 cn-2 cn-k-1

24 Example GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1， h(x)= x4+x2+x+1。试画一个[7,4]循环码的k级系统码形式的编码电路。 ＋ 输入m(x) 输出c(x) 门 1 x x4 x2