CRC性能分析与生成多项式选取的研究.doc

分类号 TP311

学校代号 10462

密 级 公开

学 号 07083051004

CRC
性
能
分
析
及
生
成
多
项
式
选
取
的
研
究

硕士学位论文

CRC性能分析及生成多项式选取的研究

魏

艳

学位申请人
：
魏 艳

导师姓名及职称
：
马吉明 教授

郑州轻工业学院

专业名称
：
计算机应用技术

学科门类
：
工 学

论文提交日期
：
2008年6月

A Dissertation Submitted to
Zhengzhou University of Light Industry
for the Academic Degree of Master
of Engineering Science

Analysis on CRC Performance and
Research on Polynomial Selection

Candidate:Wei Yan
Supervisor:Ma Ji-ming
Major:Computer Application and Technology

School of Computer and Communication Engineering
Zhengzhou University of Light Industry
Zhengzhou 450002, P.R.China
June 2008

郑州轻工业学院
学 位 论 文 原 创 性 声 明

本人郑重声明： 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中作出了明确的声明并表示了谢意。
本人学位论文与资料若有不实，愿意承担一切相关的法律责任。

学位论文作者签名：
年 月 日
----------------------------------------------------------
郑州轻工业学院
学位论文知识产权声明书

本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于郑州轻工业学院。学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为郑州轻工业学院。
保密论文待解密后适用本声明。

学位论文作者签名： 指导教师签名：
年 月 日 年 月 日

摘 要
循环冗余校验码(CRC)是一种常用的检错编码，它具有很强的检错能力，同时实现也较容易，因此在各种网络系统中得到了广泛应用。在嵌入式网络系统和其他应用环境中，CRC常常用于信息传输过程中的差错检测。
可是，目前常用的CRC生成多项式的差错检测能力并不是完全像人们认为的那么优秀，通过仿真实验研究，发现目前常用的生成多项式其综合检测能力有一定的局限性，要么是检错能力比其他一些生成多项式差，要么就是检错能力仅仅是在某些数据帧长度表现的比较优秀。而且这些缺点和局限性缺好像被忽略了。这在很大程度上是由于很少有资料和文献介绍以何种标准确定生成多项式的结构引起的。
对于上面提出的问题，本文从常用的生成多项式的检错性能分析出发，得出两个重要的结论：(1)生成多项式的比特数越大，其差错检测能力越强，漏检错误率越低；(2)生成多项式比特数相同的情况下，差错检测能力相同；漏检错误概率范围大致相同，但是对于不同的信道误码率，又有不同的漏检错误概率。这两个结论对后面更加深入的研究提供了理论依据和支持。
基于上述研究结论，通过对嵌入式网络系统特性的研究，在此应用背景下，重点研究了CRC的最小码距和漏检错误概率两个主要的性能影响因素对其检错性能的影响，选取部分3bits-16bits的生成多项式为研究样本，采用仿真方法获取不同形式的生成多项式的最小码距和漏检错误概率的具体数据，在对性能因素分析基础上，结合仿真数据，提出了一种CRC生成多项式选取方法，一方面作为对不同结构的生成多项式直观具体的评价方法，另一方面在特定应用环境下性能更优的生成多项式提供了具体的。
应用选取方法，以嵌入式网络系统常用的各种类型的生成多项式为主要考察样本，验证目前常用生成多项式存在一些局限性的同时，也筛选出了在嵌入式网络系统中性能较好的其它生成多项式，对今后工作的进一步深入开展具有较好的参考价值。
关键词：循环冗余校验码，生成多项式，嵌入式网络通信系统，仿真

ABSTRACT
Cyclic Redundancy Code (CRC) provides a first line of defense against data corruption in many networks and is commonly used for error detection in embedded networks and other applications.
Unfortunately, many commonly used CRC polynomials provide significantly less error detection capability than they might. An exhaustive exploration reveals that most previously published CRC polynomials are either inferior to alternatives or are only good choices for particular message lengths. Unfortunately these shortcomings and limitations often seem to be overlooked. This is largely because there is little published guidance and less quantitative data upon which to base tradeoff decisions.
To help improve this situation, first, this paper gives an analysis for the error detection capability of commonly used polynomials from the academic and emulator. It reveals two conclusions: (1) one is the size of CRCs is relate to the performance. (2)The structure of polynomials is also related to the error detection performance of polynomials.
This paper proposes “good” general purpose CRCs for error detection applications that encompass many current and future embedded network protocols.Describing a polynomial selection process for embedded network applications and proposes a set of good general purpose polynomials. Some new polynomials provide good performance for 3-to16-bit CRC.Through the particular emulational process, which validates the new polynomials have the strength error detection ability on one hand, and on the other hand ,proves the feasibility and validity of this method, provide us much more academic and data to our future work.
The application of the selection validates the localization of standards, and then provides some good performance polymomails for embedded networks.
Keywords: CRC, Polynomials, Embedded Networks, Simulation

37

目 录
第一章 绪论 1
1.1 立题背景 1
1.2 课题研究的意义 2
1.3 论文主要内容安排 3
1.4 小结 4
第二章 差错控制理论和系统仿真研究 5
2.1 差错控制编码相关 5
2.1.1 数字通信系统及信道模型 5
2.1.2 差错控制系统和编码的分类 6
2.1.3 循环码理论 7
2.1.4 缩短循环码 15
2.2 系统仿真研究 16
2.2.1 系统仿真的步骤 16
2.2.2 Matlab/Simulink仿真工具 18
2.2.3 S-函数简介 19
2.3 小结 20
第三章 循环冗余校验码的性能分析及仿真 21
3.1 性能分析 21
3.1.1 CRC检错原理分析 22
3.1.2 差错检测能力分析 22
3.1.3 漏检错误概率分析 23
3.2 仿真原理及方法 24
3.2.1 差错检测能力仿真 24
3.2.2 漏检错误率仿真 26
3.3 仿真结果 27
3.3.1 差错检测能力仿真结果 27
3.3.2 漏检错误概率仿真结果 28
3.4 结论 29
第四章 探究生成多项式的选取标准 31
4.1 应用背景 31
4.2 性能影响因素分析 32
4.2.1 汉明距离，码重以及漏检错误概率的关系 32
4.2.2 仿真数据分析 33
4.3 嵌入式网络系统中生成多项式的选取 35
4.3.1 生成多项式选取方法的理论依据和设计思想 35
4.3.2 生成多项式选取方法的具体步骤 36
4.4 结论 39
第五章 生成多项式选取方法的应用 41
5.1 方法的应用结果 41
5.2 方法应用结果的分析 42
5.2.1 8bits生成多项式的性能比较 42
5.2.2 12bits生成多项式的性能比较 44
5.2.3 16bits生成多项式的性能比较 48
5.2.4 小结 52
5.3 结论 52
第六章 结论及展望 55
6.1 论文主要完成的工作 55
6.2 存在的问题和不足 55
6.3 小结 56
参考文献 57
附录　攻读硕士学位期间发表论文目录 61
致谢 63

第一章 绪 论
第一章 绪论
1.1 立题背景
提高信息传输的可靠性和有效性，始终是通信领域研究和追求的目标。1948年，现代信息理论的奠基人C.E.Shannon在他的开创性论文“A mathematical theory of communication”[1-2]中首次阐明了在有噪信道中实现可靠通信的方法，提出了著名的有噪信道编码定理，通过某种编码方法，使得随着码长的增加误码率达到任意小。该理论奠定了差错控制码的基石。香农信道编码定理[1]：
1) R<C，当采用最大似然译码时，能以任意小的错误率Pr(E)传递速率为R的信息，码长N要足够大。
2) R>C，存在有效的编码方法实现满足Pb要求的速率为R的信息。香农证明码长N足够大时，随机选择的码有高概率为好码。
其中，C是信道容量，R是码率，高斯白噪声信道的信道容量C的计算方法如下：
(1-1)
式中，W是信道所提供的带宽，是信号功率，Es是信号能量，t是分组信号的持续时间即信号宽度，是单位频带的信号功率，是单位频带的噪声功率，是信噪比。
从对Shannon信道编码定理的分析中可以看出，Shannon在对定理的证明中引用了三个基本条件：
1) 采用随机编码、译码方式；
2) 编译码长度L→无穷，即码长无限；
3) 译码采用最大似然译码算法。
也就是说，在信道传输速率R不超过信道容量C的前提下，只有在码组长度无限长的码集合中随机的选择编码码字并且在接收端采用最大似然译码算法时，才能使误码率接近零。但是，最大似然译码的复杂性随编码长度指数增加，当编码码长趋于无穷大时，最大似然译码是不可能实现的。因此，构造物理可实现的编码方案及寻找有效译码算法一直是信道编码理论与技术研究的中心任务。
香农编码定理以后汉明(Hamming)，斯列宾(Slepian)，普兰奇(Prange)等学者专家，在50年代初，根据香农的思想，给出了一系列设计“好”码和有效译码的方法[3-4]。纠错码越来越受到大家的重视，同时无论在理论上还是实际中都得到了飞速发展。
目前常用的纠错编码按其码字结构形式和对信息序列处理方式的不同可分为两大类：分组码和卷积码。分组码是把信息序列按k位信息一组进行分组，每k位信息通过编码器变换成码长为n(n>k)的码字，每个码字的n位码元仅与本组k位信息有关，与其他码组无关。卷积码是把信息序列以k个为一组，通过编码器输出长为n(n ≥ k)的一个子码。但是该子码的n-k个校验元不仅与本子码的信息元有关，而且也与其前m个子码的信息元有关。
在通信系统中应用最广泛的分组码是汉明码和循环码[5-6]，1950年R. Hamming提出了第一个差错控制编码方案——二进制汉明码，多进制汉明码是由戈莱和科克(Cocke)发展而来的。1957年普兰奇(Prange)首先引入了循环码的概念及码多项式的表示方法，自此以后，分组码的理论，特别是循环码的理论得到了迅速发展。
循环码的显著优点是，它的编码和伴随式计算可以用简单的具有反馈连接的寄存器来实现。另外，由于循环码有良好的代数特性，人们可以用“代数”这个强有力的数学工具对循环码进行深入研究，并可找到各种简单有效的译码方法。
在实际应用中，常对一个循环码的码长和信息有所约束，因此缩短循环码随之产生，它是在(n,k)循环码的2k个码字中挑选出前i个信息位均为0值的码字(有2k-1个这样的码字)作为(n-i,k-i)缩短循环码的码字。这样就可以省去若干位不用传输，提高传输的效率。
循环冗余校验码是一类应用范围比较广的缩短循环码，而且本质上是一种系统码。随着它的广泛应用，有关它的原理、性能、理论分析及应用等各个方面的研究都取得了不同程度的进展。
1.2 课题研究的意义
目前循环冗余校验码是研究比较丰富的一个课题，目前两个主要的研究手段是理论分析和计算机仿真分析。
尽管国内外关于这类码的研究成果已经非常丰富，但是大多只是在既有标准上提出一些提高性能的方法，一些学术期刊出现过使用理论分析的方法对这类码的性能进行讨论的文章，研究的热点也是聚集在有关循环冗余校验码的编译码算法方面，希望通过各种高效的算法提高循环冗余校验码的校验速率。例如：CRC校验在USB控制器设计中的实现；EPON中校验码的并行算法实现；千兆以太网CRC 的算法与VLSI设计与实现等[7-9]。这些着眼于研究如何提高CRC校验算法的效率以及具体的算法实现方面，无论是应用范围和研究深度都有一定的局限性。因此深入的对这类编码性能进行研究就显得很有必要。
很少有人真正从CRC的校验性能方面进行研究，主要是由于目前为止关于生成多项式选取标准的文献或资料信息提供的比较少，有些文章中的理论分析并没有描述得十分清晰明白，难以让人继续讨论下去。人们并不真正了解为什么要选择目前常用的CRC码为标准的生成多项式，因此只有通过分析现有的生成多项式的性能因素，才能更好的分析出选择生成多项式的标准，从而为今后的生成多项式的研究提供更多更全面的研究资料，进而有机会构造出性能更优越的生成多项式。
同时由于理论研究和实现之间巨大差距的存在，单从理论上进行设计和分析是不够的。仿真研究将搭起理论和实现之间的桥梁，对编码的性能研究具有实际的指导意义。
1.3 论文主要内容安排
本文主要从CRC的性能理论分析入手，考察其各种性能影响因素，由于理论分析的方法只能获得宏观认识，所以借助仿真软件进行实验可以避开硬件实验的条件问题、编程实验的难度问题,从而可以快速、可视化地观察实验结果,具有省时低耗的优势。
首先通过对目前几种标准的CRC码性能的分析和总结，为后面的生成多项式的相关研究提供了可行性理论支持。
其次结合嵌入式网络通信系统的应用背景对3bits-16bits的生成多项式进行全面、详细的研究，提出一种选取“好”码的方法。方法的提出着重考虑在嵌入式网络通信系统的应用环境中生成多项式能达到最低漏检率，而且在较大的数据帧长度范围内都能够保持较好的校验性能。
最后通过仿真模型进一步验证了这些“好”码的性能，而且从另一个角度也证明了这种方法的可行性，不仅拓展了研究思路，也为下一步的研究奠定了理论基础。
本文主要内容安排如下：
第一章 介绍课题研究的背景和意义，及论文的主要内容，安排。
第二章 介绍差错控制理论和系统仿真的相关内容。
第三章 利用近世代数多项式理论对常用生成多项式性能进行分析，同时采用仿真实验的方法给出了不同标准的CRC码得检错能力和不可检测率、信道误码率之间的关系图，并从关系图中总结出了两个有关生成多项式选取的结论。
第四章 以第三章的研究内容为基础和依据，扩展研究范围，以嵌入式网络通信系统为应用背景，考虑在此背景下，影响生成多项式性能的主要因素。根据对各种因素的分析和仿真，提出了一种选取性能理想的生成多项式的方法，方法的提出扩展了对CRC性能研究的范围，为更深入研究CRC码性能打下基础。
第五章 利用上一章提出的选取方法，采用具体的仿真方法，以嵌入式网络系统环境中常见的生成多项式类型为考察对象，在验证目前标准生成多项式局限性的同时，也筛选出了一些性能较好的其它生成多项式。
第六章 总结整个论文的研究内容及结论，指出今后工作的方向和任务。
1.4 小结
本章着重介绍了课题的研究背景和意义，并提出了目前主要相关研究所存在的问题，基于存在的问题，介绍了课题的主要研究内容。最后给出了论文的主要章节安排。

第二章 差错控制理论和系统仿真研究
第二章 差错控制理论和系统仿真研究
2.1 差错控制编码相关
2.1.1 数字通信系统及信道模型
对于一个数字通信系统，如通信、雷达、遥测遥感、数字计算机的存储系统和内部运算以及计算机之间的数据传输等，都可归结为图2-1所示的模型。

图2-1 数字通信系统模型
Fig.2-1 The model of digital communication system

根据实际信道的统计特性可以划分为几种理想信道模型[10]：
二进制硬判决情况下，信道的信道转移概率矩阵可用
(2-1)
表示。如果，则称这种信道为二进制对称信道，简称BSC，BSC为随机信道。否则，称为不对称信道。若，则称为Z信道。
如果信道输入是二进制符号，而输出是离散的进制符号，其信道转移概率矩阵为
(2-2)
则这种信道为离散无记忆信道，简称DMC。BSC、DMC可以用图2-2表示。

图2-2 随机信道和离散无记忆信道
Fig.2-2 Random channel and discrete no memory channel

在作删除判决情况下，信道可用图2-3所示的模型表示，称为二进制删除信道，简称BEC。

图2-3 二进制删除信道
Fig.2-3 Binary delete channel

这三种信道模型都是实际信道的简化模型，研究中针对不同的传输特性，选用不同的模型。例如卫星信道一般可以看做BSC。
2.1.2 差错控制系统和编码的分类
在数字通信系统中，差错控制的方式有以下三类[10]：
重传反馈方式(ARQ)。通信系统中的ARQ方式的工作原理可以描述为：发送端发出检错码，接收端收到码元后，在译码器根据该码的编码规则，判决收到的码序列中有无错误产生，并通过反馈信道把判决结果用判决信号告诉发送端。发送端根据这些判决信号，把接收端认为有错的信息再次发送，直到接收端认为正确接收为止。ARQ方式一般适用于点对点的通信，译码设备较简单；检错码的检错能力比纠错码的纠错能力要高的多，因而整个系统的纠错能力较强；它的检错码的检错能力于信道干扰的变化基本无关，所以适用性较强。
前向纠错方式（FEC）。FEC方式的工作原理为：发送端发送纠错码，接收端收到码字后，通过纠错译码器不仅能自动地发现错误，而且能自动地纠正接收码字传输中的错误。因此，FEC方式具有对多用户的同播通信，译码的实时性较好，控制电路简单的优点。但同时也存在译码设备比较复杂，所用纠错码必须与信道的干扰情况相匹配，适应性差，编码效率较低的缺点。
联合纠错方式（HFC）。HFC方式是发送端发送的码不仅能够被检测出错误，而且具有一定的纠错能力。接收端收到码序列以后，首先检测错误情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果错误很多，超过码的纠错能力，但能检测出来，则接收端通过反馈信息，要求发端重新传送有错的信息。HFC克服了FEC方式译码设备复杂和ARQ方式实时性差的缺点，具有很强的纠错能力和适应性，因此得到广泛的应用。
上述三种方式，都要用编码来赋以差错控制功能，不论是自动纠错或者是只检错然后通过反馈重传来纠错的码字，统称之为纠错编码。根据不同的分类标准编码也会有不同的分类方法，具体分类如图2-4所示：

图2-4 信道编码分类
Fig.2-4 Category of channel coding

由图2-4可以看出根据监督元与信息组之间的关系，纠错编码可分为分组码和卷积码两大类。其中分组码是把信息序列按k位信息一组进行分组，每k位信息通过编码器变换成码长为n(n>k)的码字，每个码字的n位码元仅与本组k位信息有关，与其他码组无关。而卷积码虽然也是把信息序列按k0位信息一组进行分段，每段k0位信息通过编码器相应输出一个长为n0(n0>k0)的码段，但是该码段不仅与本段输入的k0位信息有关，而且也与前若干段信息元有关。
本文主要讨论的是分组码的一类重要的分支——循环码，它是线性分组码的一个子集，应用十分广泛。
2.1.3 循环码理论
循环码是线性分组码的一个重要子集，它有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现；同时循环码的性能也较好，具有较强的检错和纠错能力。它的编译码电路简单易于实现，循环冗余码与循环码有密切的关系，因此循环码特别引人注目，对它的研究也比较深入和系统。下面从编码理论方面讨论循环码。
循环码的结构完全建立在有限域的基础上，可以用近世代数的方法精确描述。循环码是1957年由普兰奇提出的，此后几十年中得到了充分研究和发展。起初，人们认识到并感兴趣的是循环码的外在特点，即循环码码字的循环移位仍然是码字，这个特点给循环码的编译码实现带来了便利。在以后的实践中，人们从循环群的角度，在代数结构、纠错性能控制等方面找到了循环码更加吸引人的优越之处。目前，实际差错控制系统中所使用的线性分组码几乎都是循环码或循环码的子类。
2.1.3.1 几个基本概念
1) 线性分组码
线性分组码中的线性是指码字中码元间的约束关系是线性的。而分组则是对编码方法而言的。即编码时将每k个信息位分为一组进行独立处理，变换成长度为n(n>k)的二进制码字。(n,k)线性分组码是把信息流的每k个码元分成一组，通过线性变换，映射成由n个码元组成的码字。从空间角度，每个码字可看成是n维线性空间中的一个矢量，n个码元正是n个矢量元素。码元的值取自字符集X={x0,x1,…,xq-1},当q=2时是二进制码，当q>2时是q进制码。二元分组码是最基本、最重要的。
k位二进制信息组有2k种组合，构成GF(2)上的k维k重矢量空间；而n位二进制数共有2n种组合，构成GF(2)上的n维n重矢量空间，通常2n>2k。纠错编码的任务是在n维n重矢量空间的2n种可能组合选择2k个构成一个子空间，或称许用码码集C，然后设法将k比特信息组一一对应的映射到许用码码集C，然后设法将k比特信息组一一对应地映射到许用码码集C。不同的编码算法对应不同的码集以及不同的映射算法，把这样得到的码称为(n , k)线性分组码。不编码时，一个二进制码元可携带1比特信息(传信率为1b/符号)；编码后，n个二进制码元携带k比特信息(传信率为(k/n)b/符号)。定义k/n=Rc为二元分组码的码率，或者说是效率。
在GF(2)上，汉明重量：n重矢量R中，非零元素的个数称为该n重的汉明距离，简称重量，用W(r)表示。汉明距离：逐位比较两个n重矢量R1和R2的对应各位，其中取值不同的元素个数称为R1和R2的汉明距离，用d(R1，R2)表示。
2) 信息码元与监督码元
信息码元又称为信息序列或信息位，这是发端由信息编码后得到的被传送的信息数据比特，通常以k表示。由信息码元组成的信息组为：M=(mk-1,mk-2,…,m0)，在二元码的情况下，每个信息码元m的取值只有0和1，故总的信息码字数共有2k个，即不同信息码元取值的组合共有2k。
监督码元又称为监督位或附加数据比特，这是为了检纠错码而在信道编码时加入的判断数据位。通常以r表示，即为：n= k+r或r=n-k。
经过分组编码后的编码又称为(n,k)码，即表示总码长为n位，其中信息码长(码元数)为k位，监督码长(码元数)为r=n-k。通常称其为长为n的码字。
3) 许用码字与禁用码字
信道编码后的总码长为n，总的码字数应为2n，即为2k+r。其中被传送的信息码字有2k，通常称为许用码字；其余的码字共有2n减去2k，不传送，称为禁用码字。发送端误码控制编码的任务正是寻求某种规则从总码字2n中选出许用码字；而接收端译码的任务则是利用相应的规则来判断及校正收到的码字是否符合许用码字。通常又把信息码元数目k与编码后的总码元数目(码字长度)n之比称为信道编码的编码效率或编码速率，表示为：R=k/n=k/(k+r),这是衡量纠错码性能的一个重要指标，一般情况下，监督位越多(即r越大)，检纠错能力越强，但相应的编码效率也随之降低了。
4) 码重与码距，最小码距
在分组编码后，每个码字中码元为“1”的数目称为码的重量，简称码重。两个码字对应位置上取值不同(1或0)的位数，称为码字的距离，简称码距，又称汉明距离，通常用d表示。例如：000与101之间的码距d=2；000与111之间的码距d=3.对于(n，k)码，许用码字为2k个，各码字之间距离最小值称为最小码距。
2.1.3.2 检错和纠错的基本原理
首先以三位二进制码组为例，说明检错纠错的基本原理。三位二进制码元共有8种可能的组合：000、001、010、011、100、101、110、111。如果这8种码组可能传递消息，若在传输过程中发生一个误码，则一种码组会错误地变成另一种码组。由于每一种码组都可能出现，没有多余的信息量，因此接收端不可能发现错误，以为发送的就是另一种码组。但若我们只选其中00、01、10、11四种信息，而第3位是附加的，这位附加的监督码元与前面两位码元一起，保证码组中“1”码的个数为偶数。除上述4种许用码组以外的另外4种不满足这种校验关系的码组即为上面提到的禁用码组，在编码后的发送码元中是不可能出现的。接收时一旦出现这些禁用码组，就表明传输过程中发生了错误。用这种简单的校验关系可以发现一个和三个错误，但不能纠正错误。
例如，当接收到的码组为010时，我们可以断定这是禁用码组，但无法判断原来是哪个码组出现错误。虽然原发送码组为101的可能性小（因为发生三个误码的情况极少），但不能绝对排除。即使传输过程中只发生一个误码，也有三种可能的发送码组：000、011、110。如果进一步将许用码组限制为两种：000和111，则不难看出，用这种方法可以发现所有两个以下的误码，如用来纠错，则可纠正一位错误。
对于上述三位码组例子，我们可以用一个三维立方体来表示，如图2-5所示。图中立方体各顶点分别表示8为码组，三位码元依次表示x、y、z轴的坐标。如果8种码组均为许用码组时，两码组间的最小距离为1，即这种编码的最小码距为1，常记作dmin=1.在选四种码组为许用码组情况下，最小码距dmin=2；采用两种许用码组时，dmin=3。由图2-5的立方体可见，码距即为从一个顶点沿立方体各边移到另一个顶点所经过的最少的边数。图中粗线表示000和111之间的一条最短途径。同理，不难验证上例中各种情况下的码距。
由上例可知，一种编码的最小码距直接关系到这种码的检错和纠错能力。因此最小码距是信道编码的一个重要参数。

图2-5 分组码的最小码距
Fig. 2-5 Minimum Hamming Distance of code
2.1.3.3 码多项式表示
循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码字经过循环移位后，所得到的码字仍然是许用码字。若(an-1,an-2，…,a1,a0)为一循环码字，则(an-2,an-3，…,a1,a0,an-1)、(a0,an-1，…,a1)、……还是许用码字。也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码字。表2-1给出了(7,3)循环码的全部码字。由此表可以直观看出这种码的循环特性。例如，将表2-1中的第二码字向右移一位，即得到第五码字；第六码字向右移一位，即得到第三码字。

表2-1 一种(7,3)循环码的全部码字
Tab.2-1 A kind of (7, 3) Circle code

序号
码字
信息位 a6a5a4
监督位a3a2a1a0
1
000
0000
2
001
0111
3
010
1110
4
011
1001
5
100
1011
6
101
1100
7
110
0101
8
111
0010

为了利用代数理论研究循环码，可以将码字用代数多项式来表示，这个多项式被称为码多项式，对于许用循环码A=(an-1,an-2，…,a1,a0),可以将它的码多项式表示为：
(2-3)
对于二进制码字，多项式的每个系数不是0就是1，x仅是码元位置的标志。因此，这里并不关心x的取值。而表2-1的任一码字可以表示为：

例如，在表中第七码字可以表示为：

在整数运算中，有模n运算。例如，在模2运算中，有1+1=2≡0(模2)，1+2=3≡1(模2)，2×3=6≡0(模2)等。因此，若一个整数m可以表示为：
(2-4)
其中，p<n, Q是整数
则在模n运算下，有m≡p(模n)，也就是说，在模n运算下，整数m等于其被n除所得的余数。
在码多项式运算中也有类似的按模运算法则。若任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，也就是说
(2-5)

则可以写为：F(x)≡R(x)(模N(x))。
这时，码多项式系数仍按模2运算，即只取值0和1，假设：
计算x4+x2+1除以x3+1的值可得：

注意，在上述运算中，由于是模2运算，因此，加法和减法是等价的，在式子中通常用加法运算符。这样也可以表示为：
≡(模x3+1)
在循环码中，若A(x)是一个长为n的许用码字，则xi A(x)在按模xn+1运算下，亦是一个许用码字，也就是假如：xi A(x) ≡Ai(x)亦是一个许用码字，并且，Ai(x)正是A(x)代表的码字向左循环移位i次的结果。例如，由表示的循环码，其码长n=7，现给定i=3，则：
其对应的码字为0101110，它正是表中第3码字。
上述分析和演算可以得到了一个重要的结论：一个长度为n的循环码，它必为按模(xn+1)运算的一个余式。
2.1.3.4 生成多项式和生成矩阵
循环码除全0码字外的其余码字称为生成多项式，用g(x)表示。可以证明生成多项式g(x)具有以下特性：
g(x)是一个常数项为1的r=n-k次多项式；
g(x)是xn+1的一个因式；
该循环码中其他码多项式都是g(x)的倍式。
为了保证构成的生成矩阵G的各行线性不相关，通常用g(x)来构造生成矩阵，这时，生成矩阵G(x)可以表示成为：
(2-6)
其中，因此，一旦生成多项式g(x)确定以后，该循环码的生成矩阵就可以确定，从而该循环码的所有码字就可以确定。显然，不符合G=[I,Q]形式，所以此生成矩阵不是典型形式，不过，可以通过简单的代数变换将它变成典型矩阵。
现在以表的(7,3)循环码为例，来构造它的生成矩阵和生成多项式，这个循环码主要参数为：n=7，k=3，r=4，从表中可以看到，其生成多项式可以用第1码字构造：

在上面的例子中，是利用表给出的(7,3)循环码的所有码字，构造了它的生成多项式和生成矩阵。但在实际循环码设计过程中，通常只给出码长和信息位数，这就需要设计生成多项式和生成矩阵，这时可以利用g(x)所具有基本特性进行设计。
首先，生成多项式g(x)是的一个因式，其次g(x)是一个r次因式，因此，就可以先对进行因式分解，找到他的r次因式。下面仍以(7,3)循环码为例进行分析。
第一步：对进行因式分解得：
第二步：构造生成多项式g(x)
为了求(7,3)循环码的生成多项式g(x)，要从式中找到r=n-k次的因子，不难看出，这样的因子有两个，即：

以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的循环码码字就不同。用式作为生成多项式产生的循环码即为表所列。
当然，在得到生成矩阵G和监督矩阵H的关系，得到监督矩阵H。除此之外，还可以利用循环码的特点来确定监督矩阵H。
由于(n , k)循环码中g(x)是的因式，因此可令：
(2-7)
这里h(x)称为监督多项式，与所表示的G(x)相对应，监督矩阵表示为：