西安电子科技大学：《信息论与编码理论基础》课程PPT教学课件（编码部分）循环码

State Key Laboratory of Integrated Services Networks 国家重点实验室 循环码 (I)

State Key Laboratory of Integrated Services Networks 循 环 码 （I）

N 国家重点实验室 内容 。循环码的定义 ·循环码的生成多项式和校验多项式 ·循环码的生成矩阵和校验矩阵 ·循环码的系统码形式 。特殊的循环码

内容 循环码的定义 循环码的生成多项式和校验多项式 循环码的生成矩阵和校验矩阵 循环码的系统码形式 特殊的循环码

国家重点实验室 定义 。设C是一个n.线性分组码，C是其中的一个码 字，若C的左（右）循环移位得到的n维向量也是CH 中的一个码字，则称C是循环码。 。(alternative))设'mk∈'n是n维空间的一个k维子空 间，若对任一 v=(an-l,an-2,…,ao)∈'nk 恒有 V1=(an-2,an-1,ao,an-1)EVn.k 则称V为循环子空间或循环码

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

国家垂点实验室 Example 。Example:7,4 Hamming码的H矩阵 「1011100 H=0101110 0010111 其16个码字：1000110,0100011,1010001,1101000， 0110100,0011010,0001101;1001011,1100101, 1110010,0111001,1011100,0101110,0010111; 1111111,0000000

Example Example: [7, 4]Hamming码的H矩阵 其16个码字: 1000110, 0100011, 1010001, 1101000, 0110100, 0011010, 0001101; 1001011, 1100101, 1110010, 0111001, 1011100, 0101110, 0010111; 1111111; 0000000 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1     =   H

State Key Laboratory of Integrated Services Networks 国家重点实验室 问题一 如何寻找k维循环子空间？ 如何设计[n,循环码？ 一利用多项式和有限域的概念

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

国家重点实验室 循环码的构造 GFp)上的n维向量与GFp)上的多项式之间有一一对应的关系 an-ix"-+an-2x"-2+...+ao=f(x) an-1,an-2,…,a0 。a∈GF(p) ● 模n多项式Fx)的剩余类构成一个多项式剩余类环Flx/Fx),若 在环中再定义一个数乘运算，即 can-1xn-l+an-2x-2+…+a0） =ca-1x-1+can-2xn-2++ca0,c∈GF(p） 则模Fx)的剩余类构成一个n维线性空间，定义为剩余类结合代数

循环码的构造 GF(p)上的n维向量与GF(p)上的多项式之间有一一对应的关系 模n 多项式F(x)的剩余类构成一个多项式剩余类环Fp [x]/F(x)，若 在环中再定义一个数乘运算，即 则模F(x)的剩余类构成一个n维线性空间，定义为剩余类结合代数。 (a a a ) a GF(p) n−1 , n−2 ,  , 0 , i  ( ) ca x ca x ca c GF(p) c a x a x a n n n n n n n n = + + +  + + + − − − − − − − − , 0 2 2 1 1 0 2 2 1 1   a x a x a f (x) n n n n + + + = − − − − 0 2 2 1 1 

State Key Laboratory of Integrated Services Networks 国家重点实验室 问题一转化为 如何从模多项式x"-1的剩余类结合 代数中寻找循环子空间？

State Key Laboratory of Integrated Services Networks 问题一转化为 如何从模多项式x n -1的剩余类结合 代数中寻找循环子空间？

国家重点实验室 循环码的构造 。定理：以多项式x"-1为模的剩余类线性结合代数 中，其一个子空间Vk为循环子空间（或循环码）的 充要条件是：Vk是一个理想。 循环码是模x”-1的剩余类线性结合代数中的一个 理想。反之，其中的一个理想必是循环码

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

State Key Laboratory of Integrated Services Networks 国家重点实验室 问题二 如何从多项式剩余类环中 寻找理想？

State Key Laboratory of Integrated Services Networks 问题二 如何从多项式剩余类环中 寻找理想？

国家重点实验室 循环码的构造 ·多项式剩余类环中任何一个理想都是主理想 一主理想中的所有元素可由某一个元素的倍式 构成 ·在主理想的所有元素中，至少可找到一个次数 最低的首一多项式gx),即生成多项式

多项式剩余类环中任何一个理想都是主理想— —主理想中的所有元素可由某一个元素的倍式 构成 在主理想的所有元素中，至少可找到一个次数 最低的首一多项式g(x),即生成多项式 循环码的构造