?v(1)(x)??v(1)(x)?mod?xn?1??nn? ?x?vx?v(x?1)modx?1??????n?1? ?n? ??x?v?x??mod?x?1??(i)inv(x)?x?v(x)modx?1?, i?0,1,2,,n?1?????＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码定义
? 循环码C（Cyclic Code）：任意码字均是另一个码字的
循环移位的分组码。
C?c c?(c?)(i);c??C, i?0
??? 线性分组循环码（简称为循环码）：具有线性分组码特
性的循环码。 循环码简例
例11.27 二元3/5等比码是一个非线性的循环码，
?(00111),(01110),(11100),(11001),(10011)?C???
?(10101),(01011),(10110),(01101),(11010)?例11.28 CA是线性循环码，CB是非循环的线性分组码，CC是非线性的循环码。
CA??(000),(110),(011),(101)?
CB??(000),(100),(011),(111)? CC??(000),(100),(010),(001)?
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码多项式表示
? 码多项式（码式）：码字向量c的表示多项式c(x)， ? 循环码
C(x)?c(x)c(x)?b(i)(x); b(i)(x)?C(x), i?0
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 例11.29 对例11.27的二元3/5等比码，有，
???x2?x3?x4,x?x2?x3,1?x?x2,???C(x)??1?x?x4,1?x3?x4,1?x3?x4,??x?x3?x4,1?x2?x3,x?x2?x4,1?x?x3???
234(i)??c(x)?x?x?x??????c(x), i,j?0,1,2,3,4?34(j)??c(x)??1?x?x???＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的存在性
定理11.5.1（循环码存在性定理）： ?n,k?线性循环码
C?x?中，
11-36
（1）必存在一个非零的、首一的、最低次数为r的码式g?x?；
（2）g?x?是唯一的； （3）g?x?的零次项g0?0； （4）r?n?k；
（5）次数小于等于n?1的多项式c?x?是码式当且仅当c?x?是g?x?的倍式。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
生成多项式
? 生成多项式g?x?（Generator Polynomial），简称生成式：
循环码存在性定理11.5.1所确定的唯一的首一的最低次
的码式。 ?
?n,k?线性循环码，
C?x???c?x?c?x??a?x?g?x?, ??a?x??k?，
??g?x??r
?
定理11.5.2（生成式构造定理） g?x?是?n,k?循环码
生成式当且仅当g?x?是xn?1的r?n?k次因式。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
校验多项式
? 一致校验多项式（Parity Check Polynomial，简称校验式）
h(x)：xn?1?g(x)h(x)。
???h?x??(xn?1)g(x)?h0?h1x??hk?1k?1x?hkkx??k?n??g(x)?n?r
? 对于c(x)?a(x)g(x)，有
c(x)h(x)?a(x)g(x)h(x)?0mod?xn?1?。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码码例（1/3）
例11.30 n?7的二元循环码由x7?1的任意因式生成
x7?1?x7?1??x?1??x3?x2?1??x3?x?1?
? （7,4）循环码A，
g?x??x3?x2?1，h(x)??x?1??x3?x?1?
c?x???a0?a1x?a32x2?a3x??x3?x2?1?
? （7,4）循环码B，g?x??x3?x?1，
c?x???a0?a231x?a2x?a3x3??x?x?1?
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码码例（2/3）－例11.30续
4-37
? （7,3）循环码A，g?x??x?x?1?x?1?，
3??c?x???a0?a1x?a2x2??x4?x2?x?1?
? （7,1）循环码（7-重复码），
g?x???x3?x?1??x3?x?1?，h(x)??x?1?，
c?x??a0??x6?x5?x4?x3?x2?x?1?
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码码例（3/3）
? （7,6）循环码（等价偶校验码），g?x??x?1，
c?x???a0?a1x?a2x2?a3x3?a4x4?a5x5??x?1??a0??a0?a1?x??a1?a2?x2?
??a2?a3?x3??a3?a4?x4??a4?a5?x5?a5x6循环码是由生成式g(x)和码长n两者共同界定的线性分组
码，循环码的码参数值不可能连续分布。
例11.31 F2上x5?1只有x?1和x4?x3?x2?x?1两个因式，所以不存在码长n?5，信息位长k?2和3的线性循环码，但存在非线性的(5,3)循环码，如3/5等比码。
循环码的生成矩阵（1/2）
?g?x??w(0)??g0,g1,,gr?1,gr,0,,0,0???1??xg?x??w??0,g0,,gr?2,gr?1,gr,,0,0? ???xk?1g?x??w?k?1???0,0,,0,g,g,,g,g?01r?1r?? ?
w, w?1?, 1, w?k?1?线性无关。
k?1k?1?w, w??, , w???的线性组合一对一对应
?g, xg, , xg?的线性组合。 ??1?＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的生成矩阵（2/2）
? 故w, w, 阵G?g0g1, w?k?1??是?n,k?循环码的一个生成矩
grk?n，
?w(0)?gr?1gr000??g0g1g2?w(1)??0g0g1g2gr?1gr00?G??????????(k?1)000ggggg??012r?1r???k?n?w?k?n?
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的校验矩阵（1/5）
11-38
? 一方面由
b?x??c?x?h?x??a?x?g?x?h?x??a?x?xn?a?x?
b0? b1x? b2x2??bk?1xk?1 ?bkxk?bk?1xk?1??bn?k?1k?n?k?1xk? ?bn?1nxn?bn?1x??bn?k?1n?k?1x
??an?k?10xn?a?11xn??ak?1x? ??a0?a1x??a?1k?1xk?得到， bk?0,bk?1?0,,bn?1?0
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的校验矩阵（2/5）
? 另一方面由
c?x?h?x???cn?10?c1x??cn?1x??h0?h1x??hkxk?n??1?k ??i??c
j?h?ii?j? xi?0?j?0?得校验方程式组，
?khi?cn?i?j?0,1?j?n?k?r
i?0＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的校验矩阵（3/5）
? 定义向量组?h?j? j?1,2,,r?为，
h?j??（0,,0,hk,hk?1,,h1,h0,0,,0）r?jj?1
??h?j?h?j?j0,1,,h??n?j,,h?j?h?j?n?2,n?1?＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的校验矩阵（4/5）
? 展开校验方程组得到，
0?h0cn?j?h1cn?j?1??hk?1cn?j?k?1?hkcn?j?k?0?cn?1?0?cn?2??0?cn?j?0?cn?j?1?h0cn?j?h1cn?j?1??hk?1cn?j?k?1?hkcn?j?k?0?cn?j?k?1?0?cn?j?k?2??0?c1?0?c0对 j?1,2,,r，
c?h?j??c?j??j?n?1?hn?1?cn?2?hn?2? ?c?j?c?j? 1?h1?0?h0?0＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的校验矩阵（5/5）
? 线性无关向量组?h?j? j?1,2,,r?为行向量构成
r?n矩阵H是?n,k?循环码的一个一致校验矩阵
4-39
H?hkhk?1h1h0r?n。
?h(r)?h1h0000??hkhk?1?h(r?1)??0hkhk?1h1h000?H??????
????(1)00hhhh??kk?110??r?n?h??r?n?＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的生成矩阵和校验矩阵例（1/3）
例11.32 例11.30中各循环码的G和H。
? （7,4）循环码A，h?x??x4?x3?x2?1，
?1G??0?0?0010010101101011000110?110100?0?, H??10111010? ?0??0011101?1?注意H是所有二进制3元组构成非零列向量的矩阵，可
见此码是m?3的汉明码。
循环码的生成矩阵和校验矩阵例（2/3）
42? （7,4）循环码B，h?x??x?x?x?1，此码仍是
m?3的汉明码，
?1011011G??11011?101???11101??, H??11101?
11101??1??3? （7,3）循环码A，h?x??x?x?1，
?1011??11101?011? G??11101?, H??1101111101???1011???＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
循环码的生成矩阵和校验矩阵例（3/3）
? （7,1）循环码，h?x??x?1，此码为重复码，
?11?11??11G??1111111?, H??? 11?11??11???65432? （7,6）循环码，h?x??x?x?x?x?x?x?1。
G是（7,1）循环码的H，而H是（7,1）循环码的G。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
11-40