hk h1
0
0
hk 1 hk
hk 2 hk 1
0 0 hk n k n
27
循环码的系统码
—— 模g(x)的除法问题
2018/10/20
28
Cx mxx
n k
rx 0
mod g x
rx Cx mxx
2018/10/20 21
两个结论
结论1:找一个[n,k]循环码，即是找一个n-k 次首一多项式g(x)，且g(x)必是xn-1的因式。
g x C x 结论2:若C(x)是一个码多项式，则 反之，若 g x Cx ，则C(x)必是一个码多项式
2018/10/20
22

Examples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试求一个[7,4]循环码。
2018/10/20
n k
mxx
n k
mod g x
29
由于生成矩阵G中的k行要求线性无关，因此 在求余式时，可选择k个线性无关的信息组 (1,0,0,…,0) xk-1， (0,1,0,0,…0) xk-2, …(0,0,0,…,0,1) 1
r1 ( x) x
k 1 nk
x
x
n1
mod( g ( x))
mod( g ( x))
r2 ( x) x k 2 x nk x n2 rk ( x) x 0 x nk x nk
2018/10/20
mod( g ( x))
30
~ 1 0 0 r1 x ~ 0 1 0 r2 x G 0 0 1 ~ r x k
a n1 , a n2 , , a0 ,
ai GF p
an1 x n1 an2 x n2 a0 f x
2、模n 多项式F(x)的剩余类构成一个多项式剩余 类环Fp[x]/F(x)，若在环中再定义一个数乘运算， 即
c a n 1 x n 1 a n 2 x n 2 a 0 ca n 1 x n 1 ca n 2 x n 2 ca 0 , c GF p
2018/10/20
2
§7.4 一些特殊的线性分组码
定义6.2.1 如果任一个接收向量y，都有唯一的码字u满足d(y, u)≤t，则称该码为t阶完备码。 命题 当一个(N，L)线性分组码是t阶完备码时，所有不同伴随 式所对应的陪集首恰好是所有重量不超过t的N维向量。 注意：不同伴随式的个数为2N-L，重量不超过t的N维向量的个 数为 t t k N L k C 此时应该 2 C N N
~ ri x 表示ri(x)系数
2018/10/20 31
H P I nk

T

I n k
T ~ T T ~ ~ r1 ( x) , r2 ( x) , rk ( x)
2018/10/20


32
循环码的编码原理(1)
基本步骤([n,k])
1、分解多项式xn-1=g(x)h(x)
第七章：线性分组码
§7.1 §7.2 §7.4 §7.5 分组码的概念 线性分组码 循环码 卷积码
2018/10/20
1
§7.4 一些特殊的线性分组码
本节介绍几种重要的线性分组码。
一、二元Hamming码

N=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)线性分组码。 其一致校验矩阵是如下的m×(2m-1)阶矩阵H： H的(2m-1)列恰好是(2m-1)个非全0的m维向量。
2018/10/20
6
§7.4 一些特殊的线性分组码
三、Golay码 Golay码是线性(23, 12)码，最小距离为7。将其增加一个全 校验位扩展为二元线性（24,12）码，最小距离为8。表 6.4.1给出了Golay码和扩展Golay码的重量分布。
2018/10/20
7
§7.4 一些特殊的线性分组码
循环码要求掌握的内容


根据多项式会写循环码的生成矩阵和校 验矩阵 会写循环码生成和校验矩阵的系统形式 会画循环码的编码电路 由生成多项式的根定义循环码
2018/10/20
8
§7.4 一些特殊的线性分组码

定义 循环码的生成多项式和校验多项式 循环码的生成矩阵和校验矩阵 循环码的系统码形式
2018/10/20 33
循环码的编码原理(2)
可选择k个线性无关的信息组 (1,0,0,…,0) xk-1， (0,1,0,0,…0) xk-2, …(0,0,0,…,0,1) 1
r1 ( x) x k 1 x nk x n1 r2 ( x) x k 2 x nk x n2 rk ( x) x 0 x nk x nk
2018/10/20 16
问题三 如何寻找生成多项式g(x)？
2018/10/20
17
循环码
模多项式xn-1剩余类线性结合代数中的理 想
生成多项式
2018/10/20
18
生成多项式和校验多项式
2018/10/20
19
两个定理
定理1(p147):GF(q)(q为素数或素数的幂) 上的[n,k]循环码中，存在唯一的n-k次首一 多项式g(x)，每一个码多项式C(x)必是g(x) 的倍式，每一个小于等于(n-1)次的g(x)的 倍式一定是码多项式
2018/10/20
9
定义1：设CH是一个[n.k]线性分组码，C1是其 中的一个码字，若C1的左(右)循环移位得到的n 维向量也是CH中的一个码字，则称CH是循环码。 定义2：设 若对任一
恒有
v1 a n2 , a n1 , , a0 , a n1 Vn,k
v a n1 , a n2 , , a0 Vn,k
是 n维空间的一个k维子空间， Vn,k Vn
则称Vn,k为循环子空间或循环码
2018/10/20
10
问题一 如何寻找k维循环子空间？ 如何设计[n,k]循环码？
—— 利用多项式和有限域的概念
2018/10/20
11

注： 1、GF(p)上的n维向量与GF(p)上的多项式之间有 一一对应的关系
br-2
a0,a1,…ak
以Hadmard矩阵Mn的所有行作为所有的码字，得到的码就是 Hadamad码。 Hadamad码的参数如下： 共有n个码字，因此共有n个信息，因此信息长为logn=m。 码长为n。 编码效率为R=m/n=m/2m。 dmin=2m-1=n/2。 生成矩阵为Mn的任意m个非全0行构成的m×n阶矩阵。（？）
2018/10/20
mod( g ( x)) mod( g ( x))
mod( g ( x))
34
~ 1 0 0 r1 x ~ 0 1 0 r2 x G 0 0 1 ~ r x k
2018/10/20
26
h* ( x) h0 x k h1 x k 1 hk x
nk 1 *
h x, x
n k 2 *
h x, , h x
*
h0 h1 0 h0 H 0
2018/10/20
hk 1 h1 0 h0
g(x)决定生成矩阵，h(x)决定校验矩阵
2018/10/20
25
x k 1 g x, x k 2 g x, , g x
g1 g0 0 0 g n k g n k 1 g n k g n k 1 g1 g 0 0 0 0 G 0 0 g g g g g nk n k 1 2 1 0 k n
C x Ax Bx a k br x k r a k 1br a k br 1 x k r 1 a k br 2 a k 1br 1 a k 2 br x k r 2 a k br i a k 1br (i 1) a k i br x k r i a1b0 a 0 b1 x a 0 b0
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)
的系数即可构成相应的校验矩阵
g(x)、 xg(x)、x2 g(x)、 x3g(x)、
2018/10/20
23
循环码的生成矩阵和校验矩阵
2018/10/20
24
x n 1 g xhx
g x g nk x nk g nk 1 x nk 1 g 0
hx hk x k hk 1 x k 1 h0
循环码是模xn-1的剩余类线性结合代数中 的一个理想。
2018/10/20
14
问题二 如何从多项式剩余类环中 寻找理想？
2018/10/20
15
由于 1、多项式剩余类环中任何一个理想都是 主理想——主理想中的所有元素可由某 一个元素的倍式构成 2、在主理想的所有元素中，至少可找到 一个次数最低的首一多项式g(x),即生成 多项式
~ ri x 表示ri(x)的系数
2018/10/20 35
循环码的编码

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

2018/10/20
36
多项式乘法和除法电路
2018/10/20