第五讲——循环码.
- 格式：ppt
- 大小：134.00 KB
- 文档页数：18
文档推荐
-
第五讲 传播的基本过程页数:50
-
C语言第五讲ppt课件页数:18
-
最新C语言程序设计第五讲汇总页数:7
-
第五讲 队列(完成)页数:51
-
第五讲 单片机C语言(1)页数:30
-
第五讲——循环码.页数:18
下载文档原格式
合集下载
智能信息技术导论 循环码
智能信息技术导论 - 循环码一、概述循环码是一种在通信领域中广泛使用的编码方式。
它通过在数据中添加冗余位来实现错误检测和纠正的功能。
循环码在数字通信系统、计算机网络、存储系统等领域都有着重要的应用，是保障数据传输可靠性的重要技术手段之一。
二、循环码的原理循环码是一种线性块码，通过在数据位后面添加一系列的冗余位（也称为校验位）来构成编码后的数据。
冗余位的计算方式使循环码的编码、译码实现起来非常高效。
2.1 循环码的生成多项式循环码最重要的参数是生成多项式，它决定了编码和译码的方式。
生成多项式是一个不可分解的多项式，用于生成校验位。
在循环码中，校验位是通过数据位和生成多项式的模2乘法来计算得到的。
2.2 循环码的编码循环码的编码过程实际上就是将数据位和生成多项式进行一系列模2乘法的计算，并将结果作为校验位添加到数据位后面。
编码过程可以通过移位寄存器的方式实现，其中移位寄存器的初始状态为全0。
2.3 循环码的译码循环码的译码过程主要是通过计算接收到的编码数据位和生成多项式的模2除法来还原数据位。
译码过程中，接收到的编码数据位会与寄存器中的状态进行模2除法的计算，得到的结果会作为冗余位进行错误检测。
三、循环码的性质循环码具有许多重要性质，这些性质使得循环码在实际应用中具有较好的性能。
3.1 线性性质循环码满足线性性质，即两个编码字的异或结果仍然是一个有效的编码字。
这种性质使得循环码可以方便地进行编码和译码操作。
3.2 最小距离性质循环码的最小距离决定了它所能检测和纠正的错误的能力。
最小距离越大，循环码的纠错能力越强。
在设计循环码时，需要考虑到数据传输过程中可能出现的各种错误类型，以便选择合适的生成多项式和编码长度。
3.3 循环码的循环性循环码具有循环性，即将一个编码字进行循环移位后所得到的码字仍然是一个有效的编码字。
该性质使得循环码在传输过程中可以通过循环移位将错误传播到多个位上，从而提高错误的检测和纠正的能力。
差错控制编码-循环码.
伴随式（校正子）
0000 0001 0010 0101 1011 0110 1100 1000 0100 ?
错误图样和伴随式是一一对应的。
基于错误图样识别的译码器称为梅吉特译码器。错误图样识 别器是一个具有（n-k）个输入端的逻辑电路，原则上可以采 用查表的方法，根据校正子找到错误图样，利用循环码的上 述特性可以简化识别电路。梅吉特译码器特别适合于纠正2个 以下的随机独立错误。
第二步：构造生成多项式g（x） 为了求（7，3）循环码的生成多项式g(x)，要从上式中找 到r=n-k次的因子。不难看出，这样的因子有两个，即： 1式 2式
以上两式都可作为生成多项式用。不过，选用的生成多项式不 同，产生出的循环码码组就不同。用1式作为生成多项式产生的 循环码为上述表码所列。 当然，在得到生成矩阵G以后，可以通过线性变化，使之成为 典型矩阵，同时得到监督矩阵H。除此之外，还可以利用循环 码的特点来确定监督矩阵H。 由于（n,k）循环码中g(x)是 的因式，因此可令：
0 ei 1
E B A
其中E=［en-1,en-2,…,e1,e0］，且
当bi=ai 当bi≠ai
B A E
令S=BHT，称为伴随式或校正子。 若S=0,则为有效码字
S BH
T T T
S BH T
为求解B(x)整除g(x)的余式
( A E ) H EH
由此可见，伴随式S与错误图样E之间有确定的线性变换关 系。接收端译码器的任务就是从伴随式确定错误图样，然 后从接收到的码字中减去错误图样。 五、循环码的编码 在编码时，首先需要根据给定循环码的参数确定生成多项式 g(x)，也就是从 的因子中选一个（n-k）次多项式作为 g(x)；然后，利用循环码的编码特点，即所有循环码多项式 A(x)都可以被g(x)整除，来定义生成多项式g(x)。
循环码
a
b
c
u3u2u1u0
u3u2u1u0 c2 c1c0
a
b
c
除法过程： 除法过程：
u3u2u1u0
[ x { x ( x[ u3 x3 ]mod g(x) + u2x3 )mod g(x) + u1x3 }mod g(x) + u0x3 ]mod g(x)
1 0 u 0 1 0 1 1 ×3' c ' 0d 0 0
例如：( 7, 4 )循环码的生成多项式为：g(x)=( x3 + x + 1 )，求其系统码的生成矩阵 )循环码的生成多项式为 循环码的生成多项式为： )， 例如： 1）n = 7，k = 4，因此生成矩阵阶数：4×7。其中单位阵Ik为4×4，Q矩阵4×3 7， 4，因此生成矩阵阶数： 其中单位阵I 矩阵4
BCH码 BCH码
是一类能纠正多个随机错误的循环码 其生成多项式为： 其生成多项式为：
g ( x) = LCM [ m1 ( x), m3 ( x),L , m2t −1 ( x) ]
其中m 为素多项式， 为纠错个数，LCM表示取最小公倍数 其中mi(x)为素多项式，t为纠错个数，LCM表示取最小公倍数，最 表示取最小公倍数， 小码距d 2t 小码距d ≥ 2t+1 BCH码分为两种： BCH码分为两种： 码分为两种 1）本原BCH码：码长n = 2m - 1 本原BCH码 码长n 2）非本原BCH码：码长n为2m - 1的因子 非本原BCH码 码长n 其中m 其中m表示素多项式的次数
有y = c + e，即y(x) = c(x) + e(x) ，则： e， e(
CRC码 CRC码
即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验，具有 即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验， 实现简单，检错能力强。其原理为： 实现简单，检错能力强。其原理为： 然后除以生成多项式g 1）任意长的信息位向左移动r位，即xru(x)，然后除以生成多项式g(x)得到的 任意长的信息位向左移动r 余数附加在信息码之后形成码组c 然后进行发送； 余数附加在信息码之后形成码组c(x)，然后进行发送； 2）接收端接收到码组y(x)，然后除以g(x)，如果能整除则表示无错发生，否 接收端接收到码组y 然后除以g 如果能整除则表示无错发生， 则表示有错 详细过程： 详细过程： 1）信息位为u(x)，先向左移动r位，即xru(x)。求余式[xru(x)]mod g(x)= r(x) 信息位为u 先向左移动r 求余式[ 2）则将c(x) = xru(x) + r(x)发送出去 则将c 3）若用e(x)表示可能的错误，则接收到 y(x) = c(x) + e(x) = xru(x) + r(x)+e(x)， 若用e 表示可能的错误， )+e 那么校验方法： 那么校验方法： [y(x)]mod g(x)=[xru(x) + r(x) + e(x) ]mod g(x) = r(x) + r(x) + [ e(x) ]mod g(x) =[x
b
c
u3u2u1u0
u3u2u1u0 c2 c1c0
a
b
c
除法过程： 除法过程：
u3u2u1u0
[ x { x ( x[ u3 x3 ]mod g(x) + u2x3 )mod g(x) + u1x3 }mod g(x) + u0x3 ]mod g(x)
1 0 u 0 1 0 1 1 ×3' c ' 0d 0 0
例如：( 7, 4 )循环码的生成多项式为：g(x)=( x3 + x + 1 )，求其系统码的生成矩阵 )循环码的生成多项式为 循环码的生成多项式为： )， 例如： 1）n = 7，k = 4，因此生成矩阵阶数：4×7。其中单位阵Ik为4×4，Q矩阵4×3 7， 4，因此生成矩阵阶数： 其中单位阵I 矩阵4
BCH码 BCH码
是一类能纠正多个随机错误的循环码 其生成多项式为： 其生成多项式为：
g ( x) = LCM [ m1 ( x), m3 ( x),L , m2t −1 ( x) ]
其中m 为素多项式， 为纠错个数，LCM表示取最小公倍数 其中mi(x)为素多项式，t为纠错个数，LCM表示取最小公倍数，最 表示取最小公倍数， 小码距d 2t 小码距d ≥ 2t+1 BCH码分为两种： BCH码分为两种： 码分为两种 1）本原BCH码：码长n = 2m - 1 本原BCH码 码长n 2）非本原BCH码：码长n为2m - 1的因子 非本原BCH码 码长n 其中m 其中m表示素多项式的次数
有y = c + e，即y(x) = c(x) + e(x) ，则： e， e(
CRC码 CRC码
即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验，具有 即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验， 实现简单，检错能力强。其原理为： 实现简单，检错能力强。其原理为： 然后除以生成多项式g 1）任意长的信息位向左移动r位，即xru(x)，然后除以生成多项式g(x)得到的 任意长的信息位向左移动r 余数附加在信息码之后形成码组c 然后进行发送； 余数附加在信息码之后形成码组c(x)，然后进行发送； 2）接收端接收到码组y(x)，然后除以g(x)，如果能整除则表示无错发生，否 接收端接收到码组y 然后除以g 如果能整除则表示无错发生， 则表示有错 详细过程： 详细过程： 1）信息位为u(x)，先向左移动r位，即xru(x)。求余式[xru(x)]mod g(x)= r(x) 信息位为u 先向左移动r 求余式[ 2）则将c(x) = xru(x) + r(x)发送出去 则将c 3）若用e(x)表示可能的错误，则接收到 y(x) = c(x) + e(x) = xru(x) + r(x)+e(x)， 若用e 表示可能的错误， )+e 那么校验方法： 那么校验方法： [y(x)]mod g(x)=[xru(x) + r(x) + e(x) ]mod g(x) = r(x) + r(x) + [ e(x) ]mod g(x) =[x
循环码
① ②
15
循 环 码
2、校验矩阵 、
令校验多项式： 令校验多项式：h(x) = hkxk + hk-1xk-1 + … + h1x+h0
其反多项式： h*(x) = h0xk + h1xk-1 + … + hk-1x+hk 其反多项式：
循环码的一致校验矩阵的第一行为校验多项式的反多项 式的系数加上n-k-1个零组成，第二行为第一行向右平移 个零组成， 式的系数加上 个零组成 1位。以此类推得到其他各行。此矩阵为r ×n阶的。 位 以此类推得到其他各行。此矩阵为 阶的。 阶的
也就是码字0011101 对应的多项式，这个码字循环移 对应的多项式， 也就是码字 位后刚好可以得到其他码字。 位后刚好可以得到其他码字。 观察各个码多项式的关系
C2(x)=(x+1)C1(x)； C3(x)=x C1(x);…… ；
观察可发现， 观察可发现，其他的码多项式都可以写成g(x)的倍式。 再把信息序列写成多项式的形式，可得： 再把信息序列写成多项式的形式，可得：
首一多项式
2、性质： 、性质：
任一码多项式必是g(x) 的倍式： C(x) = m(x)g(x) 的倍式： ① 任一码多项式必是 任一次数≤ 的多项式m 与 相乘， ② 任一次数 k-1的多项式 (x)与g(x)相乘，必为码式 的多项式 相乘
回答前面三个问题
8
循 环 码
3、循环码的生成矩阵 、
码多项式、生成多项式及信息多项式的关系： 码多项式、生成多项式及信息多项式的关系： Ci(x) =mj(x)g(x) C=mG G为生成矩阵 为生成矩阵 i≠j
12
13
14
循环码是线性分组码的一个重要子集
i=0,1, …，k-1，，G2,i是长度为n的矢量，它的生成
函数 是G2,i(x)=xr+i+xr+i
G
m2 od GgG2(,2xk,1)1。 则k×Gn,阶H的矩标阵准：阵形式
G 2,0
是码C的一个生成矩阵。类似地，如果H2,j，是长度
2021/4/9 为r
H 2 H 2 T ,n 1 H 2 T ,1H 2 T ,0
⒉ 循环码的系统码 由上述定理，即可得到循环码产生系统码的方法：
将 且信最息低码 的❖❖移次CC至数=(xm)最为=Gx高r2r次m位(x，)+[xrm(求小x)]x于mrmr,o应(dx)为g的(x码余) 字数的，监且督最元高部次分数。
2021/4/9
13
例：已知(7,3)循环码的g(x)=x4+x3+x2+1，
h1 h2 h3
h2 h3 0
h3 0 0
0
0 0
由此可见，监督矩阵的第一行是码的监督多项式
h(x) 的
系数的反序排列，第二、三、四行是第一行的移位；
❖(n,hk*()x)循环码0的监0督1矩阵h1 hk1 1
H(n,k)
xh*(x)
0
xnk1h*(x) 1
1 h1 hk1 h1 hk1 1 h1 hk1 1 0
100
101 1100
111 0100
101
100 1011
110 1001
110
111 0010
100 1110
2021/4/9
111
110 0101
101 0011
7
⒉ 循环码的监督阵
❖ 设 g(x) 为 (n,k) 循环码的生成多项式，必为 (xn+1) 的因式，则有 xn+1=h(x)g(x)，式中 h(x) 为 k 次多项式，称为 (n,k) 循环码的监督 多项式。
循环码
码组 编号 信息位 a6 a5 a4 监督位 a3 a2 a1 a0 码组 编号
(模( x7 1))
信息位 a6 a5 a4 监督位 a3 a2 a1 a0
1
2 3 4
000
001 010 011
0000
0111 1110 1001
5
6 7 8
100
101 110 111
1011
1100 0101 0010
x4 x2 x 1
5 4 3 T ( x ) x x x 1 ； 码组（0111001）的码多项式为
码组（1110010）的码多项式为 T ( x ) x x x x ；
6 5 4
反之，若已知码多项式也可以求得对应的码组。 码多项式T(x)=x7+ x3+ x+1，则8位该组为 C=（10001011）。 码多项式T(x)=x5+ x3+ x2 + x1 ，则7位码组为 C=（0101110） 。
（2） 已知信息码，由生成多项式g(x)得到循环码 对长为k位的任意消息组 M=(mk-1,…, m1,m0)，其对
应的消息多项式为m(x)=mk-1xk-1+…+ m1x+m0
可乘以g(x)而构成n-1次的码多项式：
2016/6/24
T ( x) (mk 1 xk 1 m1 x m0 ) g( x) m( x) g( x)
即生成多项式：g(x) = x4 + x2 + x + 1。将此g(x)代入 （0010111）
x k 1 g ( x) k 2 x g ( x) G ( x) xg ( x) g ( x)
(模( x7 1))
信息位 a6 a5 a4 监督位 a3 a2 a1 a0
1
2 3 4
000
001 010 011
0000
0111 1110 1001
5
6 7 8
100
101 110 111
1011
1100 0101 0010
x4 x2 x 1
5 4 3 T ( x ) x x x 1 ； 码组（0111001）的码多项式为
码组（1110010）的码多项式为 T ( x ) x x x x ；
6 5 4
反之，若已知码多项式也可以求得对应的码组。 码多项式T(x)=x7+ x3+ x+1，则8位该组为 C=（10001011）。 码多项式T(x)=x5+ x3+ x2 + x1 ，则7位码组为 C=（0101110） 。
（2） 已知信息码，由生成多项式g(x)得到循环码 对长为k位的任意消息组 M=(mk-1,…, m1,m0)，其对
应的消息多项式为m(x)=mk-1xk-1+…+ m1x+m0
可乘以g(x)而构成n-1次的码多项式：
2016/6/24
T ( x) (mk 1 xk 1 m1 x m0 ) g( x) m( x) g( x)
即生成多项式：g(x) = x4 + x2 + x + 1。将此g(x)代入 （0010111）
x k 1 g ( x) k 2 x g ( x) G ( x) xg ( x) g ( x)
《循环码教学》课件
检测过程
在检测过程中，接收端将接收到的码字左移r位，然后除以生成多项式。如果余数为零，则认为传输过程中没有 发生错误；如果余数不为零，则认为传输过程中发生了错误。通过这种方式，循环码可以检测到单个或多个比特 错误。
03
循环码的编码与解码
编码过程
01
02
03
04
05
定义
选择生成多项式
生成多项式与信 息比特序…
编码与解码的实例演示
确定错误的位置为第4位（从右 往左数）。
纠正错误，将第4位由0改为1 ，得到纠正后的码字比特序列 1010101101。
将纠正后的码字比特序列与生 成多项式进行模2除法运算，得 到恢复的信息比特序列 1011001。
04
循环码的性能分析
误码率分析
误码率定义
影响因素
误码率是指接收端接收到的错误码元 与总码元数的比值，是衡量循环码性 能的重要指标。
影响循环码误码率的因素包括信噪比 、码长、编码方式和传输通道特性等 。
误码率计算
通过理论分析和仿真实验，可以计算 出不同条件下循环码的误码率，从而 评估其性能。
抗干扰性能分析
抗干扰能力评估
循环码具有良好的抗干扰性能， 能够有效地抵抗信道中的噪声和
干扰。
干扰抑制机制
循环码通过引入冗余和校验位，利 用编码规则对干扰进行检测和纠正 ，从而降低误码率。
添加校验位
得到码字比特序 列
循环码是一种线性码，其 编码过程是将信息比特序 列与一个生成多项式序列 进行模2除法运算，得到码 字比特序列。
根据给定的码长和纠错能 力，选择合适的生成多项 式。
将生成多项式与信息比特 序列逐位相乘，得到中间 比特序列。
根据中间比特序列和生成 多项式的系数，计算校验 位，并将其添加到中间比 特序列的末尾。
在检测过程中，接收端将接收到的码字左移r位，然后除以生成多项式。如果余数为零，则认为传输过程中没有 发生错误；如果余数不为零，则认为传输过程中发生了错误。通过这种方式，循环码可以检测到单个或多个比特 错误。
03
循环码的编码与解码
编码过程
01
02
03
04
05
定义
选择生成多项式
生成多项式与信 息比特序…
编码与解码的实例演示
确定错误的位置为第4位（从右 往左数）。
纠正错误，将第4位由0改为1 ，得到纠正后的码字比特序列 1010101101。
将纠正后的码字比特序列与生 成多项式进行模2除法运算，得 到恢复的信息比特序列 1011001。
04
循环码的性能分析
误码率分析
误码率定义
影响因素
误码率是指接收端接收到的错误码元 与总码元数的比值，是衡量循环码性 能的重要指标。
影响循环码误码率的因素包括信噪比 、码长、编码方式和传输通道特性等 。
误码率计算
通过理论分析和仿真实验，可以计算 出不同条件下循环码的误码率，从而 评估其性能。
抗干扰性能分析
抗干扰能力评估
循环码具有良好的抗干扰性能， 能够有效地抵抗信道中的噪声和
干扰。
干扰抑制机制
循环码通过引入冗余和校验位，利 用编码规则对干扰进行检测和纠正 ，从而降低误码率。
添加校验位
得到码字比特序 列
循环码是一种线性码，其 编码过程是将信息比特序 列与一个生成多项式序列 进行模2除法运算，得到码 字比特序列。
根据给定的码长和纠错能 力，选择合适的生成多项 式。
将生成多项式与信息比特 序列逐位相乘，得到中间 比特序列。
根据中间比特序列和生成 多项式的系数，计算校验 位，并将其添加到中间比 特序列的末尾。
循环码
8.5 循环码循环码是线性分组码中最重要的一个子类码，它的基本特点是编码电路及伴随式解码电路简单易行；循环码代数结构具有很多有用的特性，便于找到有效解码方法。
因此在实际差错控制系统中所使用的线性分组码，几乎都是循环码。
下面将介绍循环码的多项式表示及其性质，同时简介几种重要的循环码，CRC、BCH和R-S 码等。
8.5.1 循环码的描述1. 码多项式及其运算通式表示为：（8-69）于是称与为“同余”式，即[模]（8-70）如：则[模] 即能被整除利用这一运算原理，我们可对一个码字进行移位表示：如：的多项式表示为：使码组向左移2位（循环）则有对应多项式然后以去除得：这一结果表明，以作除法运算（称模）后，即与为同余因此，（模）应注意，利用这种同余式表示，必须加注（模），否则就不明确在什么条件下得到的这一同余关系式。
2.循环码的构成循环码的构成突出特点是只要是该码中的一个许用码组——码字，通过循环位其结果则可包括全部个非全0码字，如上面介绍的（7，3）分组码，从信码位0 0 1构成的码字（0011101）开始逐一向左（或者向右）移一位，可得其余6个码字：（0111010）、（1110100）、（1101001）、（1010011）、（0100111）、（1001110）。
若把这些码字写成码多项式，都具有同一个移位运算模式，并设（0011101）对应的码多项式，于是，有：（模)（8-71）这样，就构成了（7，3）循环码，如表8-4。
从表8-4看出，循环得到的（7，3）码，仍为系统码，信息码组均在表中码字的高位（左方）。
表8-4 （7，3）循环码移位（7，3）码码多项式（模）0 0 0 1 1 1 0 11 0 1 1 1 0 1 02 1 1 1 0 1 0 03 1 1 0 1 0 0 14 1 0 1 0 0 1 15 0 1 0 0 1 1 16 1 0 0 1 1 1 08.5.2 循环码生成多项式与生成矩阵1. 生成多项式由表8-4构成个非全0码字多项式的过程与结果看，我们从开始进行逐一循环，并以模运算，该码字正是信码组中最低位为1，对应码字多项式，在全部非全0码字中，它的最高位阶次也最低，并等于，即最高次项为，随后一系列码字都源于它的移位而形成，因此称其为生成多项式，即（8-72）然后再从的因式分解来进一步分析（8-73）我们可以将三个既约多项式因式任意组合成两个因式，可有（8-74）如：（8-75）（8-76）其中可以组合为二因式中包含最高次为4次的情况有两种，即展开式的第4及第5两组，都可以作为阶次最高为4的即（8-77）（8-78）在展开式中选用了其中一个（组合）因式为后，余下一个因式，则称其为循环码的监督多项式，如式（8-74）生成多项式与相应监督多项式乘积等于多项式。
第5章循环码
ca(x)={ca n-1 x n-1+ca n-2 x n-2+…+ca0} c∈GF(p) 则可以证明模F(x)的剩余类构成一个n维线
性空间， 称为剩余类线性结合代数。
在[n, k]循环码中，码字(an-1, an-2, …, a1, a0) 的多项式：a(x)=an-1xn-1+an-2xn-2+…+a1x+a0， 它 的循环移位一次后所得码字为(an-2, …, a1, an-1)， 相对应的码多项式表示为
问题 如何寻找k维循环子空间？
如何设计[n,k]循环码？
—— 利用多项式和有限域的概念
二、 码的多项式描述
从第二章可知，GF(p)上的所有n重构成一 个 线 性 空 间 Vn ， 其 中 每 个 矢 量 是 分 量 取 自 GF(p)上n重， 若将每个n重和系数取自GF(p)上 的多项式相对应：
定理 5.1.1 以多项式xn-1为模的剩余类线性 结合代数中， 其一个子空间V n，k是一个循环子空 间(循环码)的充要条件是：V n，k是一个理想。
结论：一个循环码是模xn-1多项式剩余类线性结合 代数中的一个理想；反之，其中的一个理想必是一 个循环码。
(Review)引理4.2.2 多项式环Fp[x]中的一切理想均是主 理想。
循环码是线性分组码中最重要的一个子类码，具 有如下性质：
严谨代数结构，性能易于分析；大部分线性码 是循环码；
其循环结构有利于编译码实现； 实际差错控制系统中所使用的线性分组码，几
乎都是循环码。
(Review)定义3.3.1 GF(2)上汉明码的H矩 阵的列， 是由不全为0， 且互不相同的二进制 m重组成。 该码有如下参数： n =2m-1， k =2m1-m， R=(2m-1-m)／(2m-1)， d=3。
性空间， 称为剩余类线性结合代数。
在[n, k]循环码中，码字(an-1, an-2, …, a1, a0) 的多项式：a(x)=an-1xn-1+an-2xn-2+…+a1x+a0， 它 的循环移位一次后所得码字为(an-2, …, a1, an-1)， 相对应的码多项式表示为
问题 如何寻找k维循环子空间？
如何设计[n,k]循环码？
—— 利用多项式和有限域的概念
二、 码的多项式描述
从第二章可知，GF(p)上的所有n重构成一 个 线 性 空 间 Vn ， 其 中 每 个 矢 量 是 分 量 取 自 GF(p)上n重， 若将每个n重和系数取自GF(p)上 的多项式相对应：
定理 5.1.1 以多项式xn-1为模的剩余类线性 结合代数中， 其一个子空间V n，k是一个循环子空 间(循环码)的充要条件是：V n，k是一个理想。
结论：一个循环码是模xn-1多项式剩余类线性结合 代数中的一个理想；反之，其中的一个理想必是一 个循环码。
(Review)引理4.2.2 多项式环Fp[x]中的一切理想均是主 理想。
循环码是线性分组码中最重要的一个子类码，具 有如下性质：
严谨代数结构，性能易于分析；大部分线性码 是循环码；
其循环结构有利于编译码实现； 实际差错控制系统中所使用的线性分组码，几
乎都是循环码。
(Review)定义3.3.1 GF(2)上汉明码的H矩 阵的列， 是由不全为0， 且互不相同的二进制 m重组成。 该码有如下参数： n =2m-1， k =2m1-m， R=(2m-1-m)／(2m-1)， d=3。
循环码I
hx hk x k hk1x k1 h0
g(x)决定生成矩阵，h(x)决定校验矩阵
生成矩阵
x k1gx, x k2 gx, , gx
g nk g nk1
g1 g0 0
0
G
0 0
gnk
g nk1
g1 g0 0 0
0
g nk
kn
校验矩阵
➢ 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-1 h*( x)的系数即可构成相应的校验矩阵
在主理想的所有元素中，至少可找到一个次数 最低的首一多项式g(x),即生成多项式
State Key Laboratory of Integrated Services Networks
问题三 如何寻找生成多项式g(x)？
循环码的构造
循环码 模多项式xn-1剩余类线性结合代数中的理想
生成多项式
两个定理
1 0 1 1 1 0 0 H 0 1 0 1 1 1 0
0 0 1 0 1 1 1
其16个码字: 1000110, 0100011, 1010001, 1101000, 0110100, 0011010, 0001101; 1001011, 1100101, 1110010, 0111001, 1011100, 0101110, 0010111; 1111111; 0000000
Example
在GF(2)上，求[7, 4]Hamming码 ➢n-k=3;
g(x)决定生成矩阵，h(x)决定校验矩阵
生成矩阵
x k1gx, x k2 gx, , gx
g nk g nk1
g1 g0 0
0
G
0 0
gnk
g nk1
g1 g0 0 0
0
g nk
kn
校验矩阵
➢ 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-1 h*( x)的系数即可构成相应的校验矩阵
在主理想的所有元素中，至少可找到一个次数 最低的首一多项式g(x),即生成多项式
State Key Laboratory of Integrated Services Networks
问题三 如何寻找生成多项式g(x)？
循环码的构造
循环码 模多项式xn-1剩余类线性结合代数中的理想
生成多项式
两个定理
1 0 1 1 1 0 0 H 0 1 0 1 1 1 0
0 0 1 0 1 1 1
其16个码字: 1000110, 0100011, 1010001, 1101000, 0110100, 0011010, 0001101; 1001011, 1100101, 1110010, 0111001, 1011100, 0101110, 0010111; 1111111; 0000000
Example
在GF(2)上，求[7, 4]Hamming码 ➢n-k=3;
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
• 对于循环码C1和C2，如果有C1C2，则称 C1为C2的子码 • 若g1(x)生成码C1，g2(x)生成码C2，而 g2(x)|g1(x)，即g1(x)可以被g2(x)整除，或 g2(x)是g1(x)的一个因子，则C1C2，即C1 为C2的子码
系统循环码
• 根据生成多项式g(x)可以直接对k-1次信息多项式 d(x)编码，即c(x)=d(x)g(x) mod xn-1，当g(x)可以 整除xn-1时，构成循环码。 • 系统码指的是在编码序列中包含所有信息位的编 码。上述方法形成的循环码不是系统码。 • 系统循环码的生成：C(x) = d(x)xn-k + r(x) 0 mod g(x)。即将信息序列左移n-k位，加上一个n-k-1次 的校验多项式r(x)，其中的r(x)= -d(x)xn-k mod g(x)。
循环码的译码
• 循环码译码时，可将错误图案按循环分 类，这样就可以对伴随式进行分类，类 数就要比图案数少得多。例如，只将首1 错误图案与相应的伴随式造表，通过多 次移位，总能出现相应的伴随式，此时 对首位纠正即可。
循环码的生成多项式
• （回顾）以xn-1为模的剩余类代数中，循环子 空间与理想等价。其生成元中次数最低的首一 多项式为生成多项式 • 循环码的生成多项式必为xn-1的因子，同一个 循环子空间可以有多个生成元，而所有这些生 成元都应与xn-1有公因式，此公因式化为首一 多项式即为其生成多项式。 • 反之，若g(x)|(xn-1)，则g(x)可以生成一个循环 码，且当g(x)为n-k次多项式时，可生成(n,k)码
回顾（3）
• 域的加法结构：域的特征、元素的周期、 素子域、基域与扩域 • 域的多项式结构：共轭根系、w的最小多 项式、本原多项式、用最小多项式根表 示的域、多项式的周期 • 剩余类线性结合代数，当以xn-1为模时， 循环子空间与理想等价，生成多项式。
有限域举例
• 构造一个4元环：整数环中的模4剩余类环 • 构造一个4元域：
BCH码
• 用GF(qm)中的n级元素的-1个连续幂次 为根的多项式生成的循环码称为BCH码。 它的自由距不小于。如果根集中有本原 元。则码长n=qm-1，称为本原BCH码
RS码
• GF(q)上的码长N=q-1的本原BCH码称RS 码 • RS码的符号域与根域相同 • RS码生成多项式g(x)=(x-m0) (xm0+1)…(x-m0+-2)，常取m0=1。其码距 为。即生成的码为(n,k,d)=(q-1, q-, )。 因此RS码被称为极大最小距离可分码。
例（续）
• 由于所要求的其它必含根2、3、4都包括在 这个共轭根系中，它们有相同的最小多项式 g(x)=m(x) =(x-)(x-2) (x-4) (x-8) (x-16) (x-9) (x-18) (x-13) (x-3) (x-6) (x-12) = x11 + x9 + x6 + x5 + x4 + x2 + 1 • 这部是著名的Golay码，能纠3个错，是一种 完备码。（上面的化简中要用到m()=0和 =89 ）
第五讲
循环码
回顾（1）
• 为了简化好码搜索、便于分析及简化译 码方法，在线性运算封闭约束的基础上， 又加入了循环封闭的约束 • 当循环码用多项式表示时，可以很好的 利用近世代数的知识，因此介绍了一些 基础知识和概念
回顾（2）
• 群：子群和陪集 • 环：子环、理想、主理想、多项式剩余 类环 • 域的乘法结构：域的乘法群是循环群、 元素的级、循环群的阶、生成元，域的 本原元
互反多项式与零空间
• 由于xn-1 可被g(x)整除，xn-1=g(x)h(x) • 若h(x)=htxt+ht-1xt-1+…+h1x+h0，则h*(x)= h0xt+h1xt-1+…+ht-1x+ht为h(x)的互反多项 式 • g(x)和h*(x)均可生成长度为n的循环码， 且互为零空间
子码
用生成项式的根定义循环码
• 研究表明，生成多项式有重根的码一般 都要比无重根的码差，因此只考虑无重 根的码，或构造无重根的多项式。 • GF(q)上多项式xn-1无重根的充要条件是n 与q互素。因此对GF(2)而言，充要条件 即为n为奇数。
合法码字与生成多项式的根
• 若g(x)有r个不相等的根，则每个根必为 每个码多项式的根，因此可将所有根代 入是否为零来验证是否为码多项式。 （此处的运算是在扩域GF(qm)上的）
用根形成生成多项式举例
• GF(211)中，为本原元，令=89，求以、 2、3、4为根的二进制循环码。的级 数为211-1=2047=8923，23=(89)23=1， 因此的级为23，如果以为根，则它的 共轭根系也为根：、2、4、8、16、 32=9、18、36=13、26=3、6、12。
• 每个根都可有一个最小多项式，而生成 多项式则是所有根的最小多项式的最小 公倍式 ei • 每个根都有级数ei，即 i 1 ，则码长 为所有级的最小公倍数 • 同一共轭根系的根在验证码字时的效果 相同，因此只需考虑其中一个即可
用指定的根求生成多项式
• 给定必含根，求生成多项式g(x)时，要先 找出各个根的最小多项式（可计算或查 表），然后求它们的公倍式。由于共轭 根系的最小多项式相同，因此首先要找 出必含根中包括哪几个共轭根系
– – – – 模4运算没有逆 4=22，因此可以从GF(2)形成扩域 找一个GF(2)一的2次不可约多项式：f(x)=x2+x+1 找到用多项式表示的GF(22)的另两个元素：a=x，b=x+1。（即 所有低于2次的多项式） – 定义GF(2)上的模f(x)运算，得到乘法表，显然a与b互逆。 – 可以验证a和b是f(x)的两个根，构成共轭根系，显然它们不属 于GF(2)，而属于扩域 – 由于乘法群的阶数22-1=3是一个素数，a和b的级都是3，因此 它们都是本原元，f(x)是一个GF(2)上的本原多项式
系统循环码
• 根据生成多项式g(x)可以直接对k-1次信息多项式 d(x)编码，即c(x)=d(x)g(x) mod xn-1，当g(x)可以 整除xn-1时，构成循环码。 • 系统码指的是在编码序列中包含所有信息位的编 码。上述方法形成的循环码不是系统码。 • 系统循环码的生成：C(x) = d(x)xn-k + r(x) 0 mod g(x)。即将信息序列左移n-k位，加上一个n-k-1次 的校验多项式r(x)，其中的r(x)= -d(x)xn-k mod g(x)。
循环码的译码
• 循环码译码时，可将错误图案按循环分 类，这样就可以对伴随式进行分类，类 数就要比图案数少得多。例如，只将首1 错误图案与相应的伴随式造表，通过多 次移位，总能出现相应的伴随式，此时 对首位纠正即可。
循环码的生成多项式
• （回顾）以xn-1为模的剩余类代数中，循环子 空间与理想等价。其生成元中次数最低的首一 多项式为生成多项式 • 循环码的生成多项式必为xn-1的因子，同一个 循环子空间可以有多个生成元，而所有这些生 成元都应与xn-1有公因式，此公因式化为首一 多项式即为其生成多项式。 • 反之，若g(x)|(xn-1)，则g(x)可以生成一个循环 码，且当g(x)为n-k次多项式时，可生成(n,k)码
回顾（3）
• 域的加法结构：域的特征、元素的周期、 素子域、基域与扩域 • 域的多项式结构：共轭根系、w的最小多 项式、本原多项式、用最小多项式根表 示的域、多项式的周期 • 剩余类线性结合代数，当以xn-1为模时， 循环子空间与理想等价，生成多项式。
有限域举例
• 构造一个4元环：整数环中的模4剩余类环 • 构造一个4元域：
BCH码
• 用GF(qm)中的n级元素的-1个连续幂次 为根的多项式生成的循环码称为BCH码。 它的自由距不小于。如果根集中有本原 元。则码长n=qm-1，称为本原BCH码
RS码
• GF(q)上的码长N=q-1的本原BCH码称RS 码 • RS码的符号域与根域相同 • RS码生成多项式g(x)=(x-m0) (xm0+1)…(x-m0+-2)，常取m0=1。其码距 为。即生成的码为(n,k,d)=(q-1, q-, )。 因此RS码被称为极大最小距离可分码。
例（续）
• 由于所要求的其它必含根2、3、4都包括在 这个共轭根系中，它们有相同的最小多项式 g(x)=m(x) =(x-)(x-2) (x-4) (x-8) (x-16) (x-9) (x-18) (x-13) (x-3) (x-6) (x-12) = x11 + x9 + x6 + x5 + x4 + x2 + 1 • 这部是著名的Golay码，能纠3个错，是一种 完备码。（上面的化简中要用到m()=0和 =89 ）
第五讲
循环码
回顾（1）
• 为了简化好码搜索、便于分析及简化译 码方法，在线性运算封闭约束的基础上， 又加入了循环封闭的约束 • 当循环码用多项式表示时，可以很好的 利用近世代数的知识，因此介绍了一些 基础知识和概念
回顾（2）
• 群：子群和陪集 • 环：子环、理想、主理想、多项式剩余 类环 • 域的乘法结构：域的乘法群是循环群、 元素的级、循环群的阶、生成元，域的 本原元
互反多项式与零空间
• 由于xn-1 可被g(x)整除，xn-1=g(x)h(x) • 若h(x)=htxt+ht-1xt-1+…+h1x+h0，则h*(x)= h0xt+h1xt-1+…+ht-1x+ht为h(x)的互反多项 式 • g(x)和h*(x)均可生成长度为n的循环码， 且互为零空间
子码
用生成项式的根定义循环码
• 研究表明，生成多项式有重根的码一般 都要比无重根的码差，因此只考虑无重 根的码，或构造无重根的多项式。 • GF(q)上多项式xn-1无重根的充要条件是n 与q互素。因此对GF(2)而言，充要条件 即为n为奇数。
合法码字与生成多项式的根
• 若g(x)有r个不相等的根，则每个根必为 每个码多项式的根，因此可将所有根代 入是否为零来验证是否为码多项式。 （此处的运算是在扩域GF(qm)上的）
用根形成生成多项式举例
• GF(211)中，为本原元，令=89，求以、 2、3、4为根的二进制循环码。的级 数为211-1=2047=8923，23=(89)23=1， 因此的级为23，如果以为根，则它的 共轭根系也为根：、2、4、8、16、 32=9、18、36=13、26=3、6、12。
• 每个根都可有一个最小多项式，而生成 多项式则是所有根的最小多项式的最小 公倍式 ei • 每个根都有级数ei，即 i 1 ，则码长 为所有级的最小公倍数 • 同一共轭根系的根在验证码字时的效果 相同，因此只需考虑其中一个即可
用指定的根求生成多项式
• 给定必含根，求生成多项式g(x)时，要先 找出各个根的最小多项式（可计算或查 表），然后求它们的公倍式。由于共轭 根系的最小多项式相同，因此首先要找 出必含根中包括哪几个共轭根系
– – – – 模4运算没有逆 4=22，因此可以从GF(2)形成扩域 找一个GF(2)一的2次不可约多项式：f(x)=x2+x+1 找到用多项式表示的GF(22)的另两个元素：a=x，b=x+1。（即 所有低于2次的多项式） – 定义GF(2)上的模f(x)运算，得到乘法表，显然a与b互逆。 – 可以验证a和b是f(x)的两个根，构成共轭根系，显然它们不属 于GF(2)，而属于扩域 – 由于乘法群的阶数22-1=3是一个素数，a和b的级都是3，因此 它们都是本原元，f(x)是一个GF(2)上的本原多项式