第五章 循环码.

Presentation on theme: "第五章 循环码."— Presentation transcript:

1 第五章 循环码

2 要求掌握的内容 根据多项式会写循环码的生成矩阵和校验矩阵 会写循环码生成和校验矩阵的系统形式 会画循环码的编码电路
由生成多项式的根定义循环码

3 第一节 循环码 定义 循环码的生成多项式和校验多项式 循环码的生成矩阵和校验矩阵 循环码的系统码形式

4 一、循环码定义

5 定义1：设CH是一个[n.k]线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。
定义2：设 是n维空间的一个k维子空间， 若对任一 恒有 则称Vn,k为循环子空间或循环码

6 问题一 如何寻找k维循环子空间？ 如何设计[n,k]循环码？
—— 利用多项式和有限域的概念

7 注： 1、GF(p)上的n维向量与GF(p)上的多项式之间有一一对应的关系 2、模n 多项式F(x)的剩余类构成一个多项式剩余类环Fp[x]/F(x)，若在环中再定义一个数乘运算，即 则模F(x)的剩余类构成一个n维线性空间，定义为剩余类线性结合代数。

8 问题一转化为 如何从模多项式xn-1的剩余类结合代数中寻找循环子空间？

9 定理 以多项式xn-1为模的剩余类线性结合代数中，其一个子空间Vn, k为循环子空间(或循环码)的充要条件是：Vn,k是一个理想。

10 问题二 如何从多项式剩余类环中 寻找理想？

11 由于 1、多项式剩余类环中任何一个理想都是主理想——主理想中的所有元素可由某一个元素的倍式构成 2、在主理想的所有元素中，至少可找到一个次数最低的首一多项式g(x),即生成多项式 定义：生成多项式g(x)是模xn-1剩余类代数中，一个理想的次数最低的非零首一多项式，它是理想或循环码的生成元。

12 问题三 如何寻找生成多项式g(x)？

13 循环码 模多项式xn-1剩余类线性结合代数中的理想 生成多项式

14 二、生成多项式和校验多项式

15 两个定理 定理1:GF(q)(q为素数或素数的幂)上的[n,k]循环码中，存在唯一的n-k次首一多项式g(x)，每一个码多项式C(x)必是g(x)的倍式，每一个小于等于(n-1)次的g(x)的倍式一定是码多项式

16 两个定理 定理2:GF(q)(q为素数或素数的幂)上[n,k]循环码的生成多项式g(x)一定是xn-1的n-k次因式： xn-1= g(x) h(x)。 反之，若g(x)为n-k次多项式，且xn-1能被g(x)整除，则g(x)一定能生成一个[n,k]循环码

17 两个结论 结论2:若C(x)是一个码多项式，则 反之，若 ，则C(x)必是一个码多项式
结论1:找一个[n,k]循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。 结论2:若C(x)是一个码多项式，则 反之，若 ，则C(x)必是一个码多项式

18 GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试求一个[7,4]循环码。
Examples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试求一个[7,4]循环码。 g(x)、 xg(x)、x2 g(x)、 x3g(x)、

19 三、循环码的生成矩阵和校验矩阵

20 g(x)决定生成矩阵，h(x)决定校验矩阵

21

22

23 四、循环码的系统码 —— 模g(x)的除法问题

24

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

26 表示ri(x)的系数

27

28 循环码的编码原理(1) 基本步骤([n,k]) 1、分解多项式xn-1=g(x)h(x) 2、选择其中的n-k次多项式g(x)为生成多项式
3、由g(x)可得到k个多项式g(x), xg(x),…xk-1g(x) 4、取上述k个多项式的系数即可构成相应的生成矩阵 5、取h(x)的互反多项式h*(x),取h*( x), xh*( x),… xn-k-1h*( x) 的系数即可构成相应的校验矩阵

29 循环码的编码原理(2) 可选择k个线性无关的信息组 (1,0,0,…,0) xk-1， (0,1,0,0,…0) xk-2,
…(0,0,0,…,0,1) 1

30 表示ri(x)的系数

31 由生成多项式的根定义循环码 设码的生成多项式 g(x)=xr+gr-1xr-1+…+g1x+g0, gi∈GF(q)
考虑g(x)无重根的情况，即要求xn-1无重根。

32 定理 在GF(q)上多项式xn-1无重根的充要条件是(n,q)=1
在GF(2)上要保证g(x)无重根的条件是xn-1中的n是奇数，因此二进制循环码中，码长是奇数。

33 g(x)=(x-a1)(x-a2)…(x-ar)， ai≠aj，ai∈GF(qm)
每一码多项式必以a1,a2,…,ar为根。则 C(ai)=cn-1ain-1+cn-2ain-2+…+c1ai+c0=0

34 g(x)=LCM(m1(x),m2(x),…,mr(x))
回顾共轭根系的概念 设f(x)=fkxk+fk-1xk-1+…+f0, fi∈GF(p)。若p特征域的元素w是方程 f(x)的根，f(w)=0,则对于一切自然数n, wp^n也必是f(x)的根。 共轭根系 最小多项式：系数取自GF(p)上，且以w为根的所有首一多项式 中，次数最低的多项式称为w的最小多项式，记为m(x)

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

36 一、多项式乘法和除法电路

37

38 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)编码时会用到)

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

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

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

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

43 二、循环码编码电路

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

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

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

47 输入m(x)是信息序列，g(x)为生成多项式
gn-k-2 b1 gn-k-1 gn-k 输出C(x) 输入m(x) m0,m1,…mk 乘g(x)运算电路 mk-1 gn-k-1 mk-1 gn-k 输入m(x)是信息序列，g(x)为生成多项式 mk-1 g0 mk-1 g1

48 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)

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

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

51 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)的实现电路

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

53 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)

54 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)

55 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

56 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)

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

58 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

59 第三节 几类特殊的循环码 最小循环码 缩短循环码 准循环码 双环循环码

60 特殊的循环码 最小循环码 缩短循环码 准循环码 双环循环码 一个理想中不再含有任何的非零理想，此理想对应的循环码称为最小循环码或既约循环码
对循环码缩短得到的码 取[n, k]循环码中前i位信息位为0的码字，得到一个[n-i, k-i]缩短循环码 准循环码 一个[mn0, mk0]线性分组码，若它的任一码字左移或右移循环移位n0次后，得到的码仍是该码的一个码字，则称这类码为准循环码 双环循环码 由两个循环矩阵Ik和P阵组成的G=[Ik P]生成的码

61 Example [8, 4]码双循环码形式 [8, 4]码准循环码形式（n0=2）

62 Examples:设[7,4]循环码的生成多项式为
g(x)=x3+x2+1，试 1)写出它的校验多项式h(x) 2)求出的生成矩阵和校验矩阵 3) 求出系统码的生成矩阵和校验矩阵 4) 画出(n-k)级系统码编码电路和k级编码电路

63 1) h(x)=(xn-1)/g(x)=x4+x2+x+1
2) h*(x)=x4+x3+x2+1

64

65