CRC算法从数学原理到软件硬件实现
是的,CRC算法并不是什么高深的玩意,但你确定你弄懂了它,或者说你甚至都没弄懂给你一个CRC多项式怎样自己写代码来实现这个CRC算法。本文将以个人的学习笔记为纲,简单讨论一下CRC的数学原理,然后再试着介绍一下它在软件和硬件中的实现思路,当然还会给出C语言和verilog语言以及VHDL语言的源代码程序,保证工程可用^)^。
首先我本人并不擅长数学,数学公式会降低文章的可读性,但从事计算机或电子相关行业,那么或多或少要涉及到一点二进制数学,是的我们只讨论二进制数学(我并不知道这个名词是否正确,但我相信你明白我说的)。
异或的定义和性质
首先我们来回故一下异或的定义和性质, 以下引自百度百科
异或逻辑的关系是:当AB不同时,输出P=1;当AB相同时,输出P=0。“⊕”是异或运算符号,异或逻辑也是与或非逻辑的组合,其逻辑表达式为:
P=A⊕B
由图1可知,异或运算的规则是
0⊕0=0,0⊕1=1
1⊕0=1,1⊕1=0
口诀1:相同取0,相异取1
口诀2:
输入A取0,则输出p=输入B
输入A取1,则输出p=输入B的反
事实上,XOR 在英文里面的定义为either one (is one), but not both, 也即只有一个为真(1)时,取真(1)。
Galois 域和模2算法
What is Galois域? 别被这个词吓住,我们并不会讨论它的数学含义更不会做数学推导,我们只是用一下它给出的一些小结论而已。
软件CRC算法的实现
1.单bit法
2.查表法
硬件CRC算法的实现
1. LSFR及其数学等效式
2. LSFR和CRC的联系以及单比特CRC算法
3. LSFR实现CRC的并行算法
先占个坑,放到这里