强力推荐:CRC 校验一探究竟(源码+非常详细的技术文章)

来源：EETOP论坛 作者：曹嘉辉

本文共28页，由于文章中有较多的数学公式，不太便于微信编辑，所以这里仅给出第一章的内容，大家可以到论坛下载该技术文章及代码。

http://bbs.eetop.cn/thread-878883-1-1.html

也可以直接前往github 下载verilog源码:

https://github.com/cjhonlyone/A-guide-of-CRC

1. 原理

1.1 差错控制编码

按功能分，有检错码、纠错码和纠删码。检错码只能检测误码；纠错码只可以纠正误码；而纠删码既可以检测误码也可以纠正误码，如果无法纠正就发出一个错误指示或者简单删除误码。

按信息码元与附加监督码元之间的检验关系分，有线性码和非线性码。信息码元与监督码元之间的关系为线性关系，满足一组线性方程式，就称为线性码；反之是非线性码。

按信息码元与监督码元之间的约束方式不同可以分为分组码与卷积码。在分组码中，编码后的码元序列每n位为一组，里面包含k个信息码元，r个附加监督码元，n=k+r，监督码元只与本组的信息码有关，与其他组的信息码无关；卷积码的监督码元不仅与本组信息码有关，还与前面码组的信息码元有关。

按信息码元在编码后是否保持原来的形式不变可以分为系统码与非系统码。系统码中信息码元被编码后保持不变，而非系统码的信息码元被编码后则被改变。

1.2 线性分组码

线性分组码中的信息码元与监督码元由线性方程联系起来，主要性质如下：

（1）任意两许用码组之和（模2和）仍为一许用码组，线性码具有封闭性。

（2）码的最小距离等于非零码的最小重量（非零码元的数目为码的重量）。

1.2.1 监督矩阵

这里A_(1×k)是信息码元，A_(1×r)是监督码元。

H是监督矩阵，表面信息码元与监督码元之间的校验关系完全由H决定，可以写为[P_(r×k) | I_(r×r)]形式的监督矩阵称为典型监督矩阵。典型监督矩阵的各行一定是线性无关的。

1.2.2 生成矩阵

Q是典型监督矩阵中P的转置。

在Q的前面补上k阶单位矩阵I即为生成矩阵G。

因为由它可以从信息码元A_(1×k)生成整个码组A，所以称它为生成矩阵。

1.3 循环码

循环码是线性分组码的一个重要子类，并且易于用带反馈的移位寄存器实现。

循环码的特点：

（1）循环码中任一许用码组经过循环移位后仍为一许用码组。

（2）线性分组码的封闭性。

可以用码多项式来表示一个码组：

A=(a_(n-1),a_(n-2),?,a_1,a_0)

可以表示为：

A(x)=a_(n-1) x^(n-1)+a_(n-2) x^(n-2)+?+a_1 x^1+a_0

x是一个实变量，它的幂次代表移位的次数。上述码组左移一位记作：

A^((1))=(a_(n-2),a_(n-3),?,a_0,a_(n-1))

它的码多项式为：

A^((1)) (x)=a_(n-2) x^(n-1)+a_(n-3) x^(n-2)+?+a_0 x^1+a_(n-1)

由此可知，左移i位的码组的码多项式为：

■(A(x)x^i&=Q(x)(x^n+1)+A^((i)) (x)@A^((i)) (x)&=A(x)x^i mod (x^n+1))

Q(x)是x^i A(x)除以x^n+1的商式，A^((i)) (x)是所得的余式。

1.3.1 循环码的生成多项式

(n,k)循环码的信息码组M(x)有2^k个，因此循环码许用码组A(x)也有2^k个。

类似于之前的生成矩阵有：A(x)=M(x)g(x)

M(x)为不大于k-1阶的多项式，A(x)是不大于n-1阶的多项式，因此g(x)是一个n-k阶的多项式。

x^k g(x)=Q(x)(x^n+1)+g^((k)) (x)

g^((k)) (x)是g(x)左移k位所得，由上一个公式可知它是g(x)的倍式：

g^((k)) (x)=M(x)g(x)

所以有：

因此g(x)一定是x^n+1的因式。

1.3.2 循环码的生成矩阵

取G(x)为：

当输入信息码元为[m_(k-1),m_(k-2),?,m_0]时：

由此可知所有码多项式A(x)必为g(x)的倍式。

1.3.3 系统循环码

这样生成的循环码并不是系统码，系统码要求码的左k位为信息码元，随后是n-k位监督码元，相当于码多项式为：

其中R(x)=r_(n-k-1) x^(n-k-1)+?+r_1 x+r_0是监督吗多项式，对应监督码元(r_(n-k-1),?,r_0)。

把R(x)移到等号右边，M(x)x^(n-k)移到等号左边，就变成了一个被除数等于商乘除数加余数的形式：

构造系统循环码时只需要将信息码元M(x)升n-k阶，也就是乘以D^(n-k)，然后以g(x)为模，所得余式R(x)即为监督码元。

系统码的生成矩阵必为典型形式G=[I_k Q]，与单位矩阵I_k每行对应的信息多项式为：

m_i (x)=m_i x^(k-i)=x^(k-i), i=1,2,?,k

相应的监督多项式为：

r_i (x)=x^(k-i) x^(n-k)=x^(n-i) mod g(x)

得到生成矩阵中每行的码多项式为：

C_i (x)=x^(n-i)+r_i (x)

因此系统循环码的生成矩阵一般表示为：

1.4 CRC码

1.4.1 实现原理

循环冗余校验（Cyclic redundancy check, CRC）码，是一种系统循环码。

系统循环码的构成为：

这里信息多项式是 M(x)，生成多项式是 g(x)，R(x)即为我们所需要的CRC校验码。M(x)x^(n-k)表示在信息码后面加上n-k个零。A(x)是系统循环码，高k位为信息码，低n-k位为监督码。

R(x)=M(x)x^(n-k) mod g(x)

可以知道系统循环码较容易的实现方式是将信息码升n-k次幂后除以生成多项式，然后将所得余式放在升幂后的信息多项式后。

这种实现过程主要使用的就是多项式除法。

1.4.2 模2除法

例2

依然使用上面的生成多项式，唯一的区别是我们给信息码前面补8个0，相当于发送00H,00H,41H

可以很容易看到，在信息码前面加零是对最后的余式没有影响的，最后得到的依然是相同的R(x)

以下省略后面的章节。

............

作者已将本文和代码发布在EETOP论坛，大家可以前往论坛下载：

http://bbs.eetop.cn/thread-878883-1-1.html

也可以直接前往github 下载verilog源码:

https://github.com/cjhonlyone/A-guide-of-CRC