西安电子科技大学：循环码（PPT课件讲稿）

State Key Laboratory of Integrated Serv ices Networks 国家重点实验室 循环码(Ⅰ)

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

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

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

国家重点实验室 定义 设C是一个4线性分组码,C1是其中的一个码 字,若C1的左(右)循环移位得到的n维向量也是CH 中的一个码字,则称C是循环码。 ●( ( alternative)设Vnk∈Vn是n维空间的一个k维子空 间,若对任 n-15n 2 aa)∈ k 恒有 2,0n-1 ao. d ∈ n 则称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矩阵 100 H=010 001011 其16个码字:100010,010001,1010001,1101000 0110100,0011010,0001101;1001011,1100101, l110010,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 Serv ices Networks 国家重点实验室 问题 如何寻找k维循环子空间? 如何设计[mn,k]循环码? 利用多项式和有限域的概念

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

国家重点实验室 循环码的构造 °GF(p)上的m维向量与GF()上的多项式之间有一一对应的关系 n-1 n-2 x+a n-2 x"-+∴+ (an1,an2,…a0),a1∈GF(p) 模n多项式F(x)的剩余类构成一个多项式剩余类环FxJ/F(x),若 在环中再定义一个数乘运算,即 2 十anx 0 2 Car n-1+Cc1n-2 +…+caa,C∈GF 则模F(x)的剩余类构成一个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 Serv ices Networks 国家重点实验室 问题一转化为 如何从模多项式x-1的剩余类结合 代数中寻找循环子空间?

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

国家重点实验室 循环码的构造 ●定理:以多项式w-1为模的剩余类线性结合代数 中,其一个子空间V为循环子空间(或循环码)的 充要条件是:Vnk是一个理想。 ●循环码是模x-1的剩余类线性结合代数中的一个 理想。反之,其中的一个理想必是循环码

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

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

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

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

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