奇偶校验码
奇偶校验码的定义
奇偶校验码也是一种校验码，它用来检测数据传输过程中是否发生错误，是众多校验码中最为简单的一种。
顾名思义，它有两种校验方法：奇校验和偶校验
奇校验：原始码流+校验位 总共有奇数个1
偶校验：原始码流+校验位 总共有偶数个1
错误检测能力

奇校验 正确码流 11000001
错1位 11000011 变成了偶数个1，能检测出错误
错2位 11000010 变成了奇数个1，检测不出错误
错3位 11001010 变成了偶数个1，能检测出错误


偶校验 正确码流 01000001
错1位 01000011 变成了奇数个1，能检测出错误
错2位 01000010 变成了偶数个1，检测不出错误
错3位 01001010 变成了奇数个1，能检测出错误

海明校验码
海明校验码的定义
​        海明码（Hamming Code）是利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的确定位置插入k个校验位，通过扩大码距来实现检错和纠错。对于数据位n的数据，加入k位的校验码,它应满足：2^k>=n+k+1。
海明校验码的详解

Q：求信息1011的海明码。





n值
最小k值




1
2


2～4
3


5～11
4


12～26
5


27～57
6


58～120
7


Step 1.根据公式 2^k >= m+k +1 或者看图可得，信息1011的长度n=4， 2^k >= k+5 , ==>k=3 ;
Step 2.求校验码的位置。海明校验码方法中，校验码的位置是固定的，从20位，21 位 , 2^2位 … 2^n位 ,总个数为K位，所以可得，校验码的位置在第1位、第2位、第4位，分别用R1、R2、R3表示；
Step 3.画图表。分别把七个位置用H1~H7来表示，注意把高位的数据填到高的位置。




位置
H1
H2
H3
H4
H5
H6
H7




信息码


1

1
0
1


校验码
R1
R2

R3





Step 4.计算校验位的值
H3 ：3 -->0 1 1
H5 ：3 -->1 0 1
H6 ：3 -->1 1 0
H7 ：3 -->1 1 1
异或运算，即同0异1的原则
R1分组为最末列（1） 为1的信息位   ==> R1=H3⊕H5⊕H7=1⊕1⊕1=1
R2分组为中间列（2） 为1的信息位   ==> R2=H3⊕H6⊕H7=1⊕0⊕1=0
R3分组为第一列（4） 为1的信息位   ==> R3=H5⊕H6⊕H7=1⊕0⊕1=0
完善图表如下：




位置
H1
H2
H3
H4
H5
H6
H7




信息码


1

1
0
1


校验码
1
0

0





即海明码从高位至低位为1010101。
Step 5.纠错
校验方程：
S1=R1⊕H3⊕H5⊕H7
S2=R2⊕H3⊕H6⊕H7
S3=R3⊕H5⊕H6⊕H7
接收到：1010101
S1=R1⊕H3⊕H5⊕H7=1⊕1⊕1⊕1=0
S2=R2⊕H3⊕H6⊕H7=0⊕1⊕0⊕1=0
S3=R3⊕H5⊕H6⊕H7=0⊕1⊕0⊕1=0
从高位S3到低位S1为000 => 数据无错误
接收到： 1000101
S1=R1⊕H3⊕H5⊕H7=1⊕0⊕1⊕1=1
S2=R2⊕H3⊕H6⊕H7=0⊕0⊕0⊕1=1
S3=R3⊕H5⊕H6⊕H7=0⊕1⊕0⊕1=0
从高位S3到低位S1为011 => 第3位数据（H3）错误

PS：海明码的纠错能力—1位blt，检错能力—2位bit，海明码在实际使用中，需加上“全校验位”，对整体进行偶校验。

循环冗余校验码
循环冗余校验码的定义
CRC循环冗余校验码是数据通信中的一种查错校验码。
循环冗余检查对数据进行多项式计算，将计算结果附加在帧后面，接收数据的设备执行模2运算，保证数据传输的正确性和完整性。
模2除法
①不向上借位，只要除数和被除数的位数相同就可进行计算，不比较它们的大小；
②模2运算中用到了模2减法，与逻辑异或相似：

1-1=0， 1-0=1， 0-1=1 ， 0-0=0
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NqWzLuaj-1598679134110)(https://s1.ax1x.com/2020/08/28/dI8xBV.png)]
CRC校验的步骤
（1）选择一个生成多项式，作为对接收的帧进行除法运算时的除数，生成多项式可以写为二进制形式；

生成多项式的要求：

①最高位和最低位必须为1；

②当CRC码的任何一位发生错误时，新帧除生成多项式后余数不为0；

③不同位发生错误时，余数应该是不同的；
生成多项式转化为二进制形式：

如x5+x3+x2+1，写为二进制：101101

（2）计算CRC校验码位数k=生成多项式位数-1，在要发送的数据帧后加k个0，除第一步用生成多项式转化的二进制数（使用模2除法），得到的余数即为CRC校验码；

模2除时，余数的位数必须只比除数少一位，不能省略0

（3）把得到的校验码CRC加到原数据帧后，构成一个新数据帧发送到接收端，接收端将新帧除以之前选择的除数（模2除法），如果没有余数，则表明该数据帧在传输过程中没有出错，否则出错；
CRC校验详解

Q：假设CRC生成多项式G(X)=X5+X4+X+1,要发送的二进制数据帧为100101110，求CRC校验码

①把生成多项式转换为二进制数：110011；
②由生成多项式的位数为6可知，CRC校验码的位数为5，所以在数据帧后加5个0，变为10010111000000，将这个数使用模2除法除以生成多项式110011，得到余数即CRC校验码11010；
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2D84Ft4J-1598679134115)(https://s1.ax1x.com/2020/08/28/dIGQ9H.png)]

    
奇偶校验码
组成奇偶校验码的基本方法：在n位有效信息位上增加一个二进制校验位，构成一个n+1位奇偶校验码
奇校验：使n+1位的奇偶校验码中1的个数为奇数
 偶校验：使n+1位的奇偶校验码中1的个数为偶数 
只能发现无法修改
 
海明校验码：
多重校验  分成多组 每一组做奇偶校验

可以发现并纠错
 

转载于:https://www.cnblogs.com/dream-to-pku/p/11615995.html

（一）校验码——校验码基础知识

码距：任何一种编码都由需要码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距
码字：定义有效的算编码的形式
例如：用4位二进制表示16中状态，则有4个不同的码字，此时码距为1（0000->0001）

（二）校验码——奇偶校验


奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码


奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数


偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数

例如：3位二进制，可表示8种不同的码字，（000,001,010,011,100,101,110,111），码距为1

如果我们此时用奇校验来传递数据：加上校验位之后，信息正确后的数据（0001,0010,0100,011,1000,1011,1101,1110）


对于校验，很多时候，都是通过增大码距，来传递信息的

例如：对于，我们想传递110 ，奇校验之后1101 ，传递正确

如果，我们在传递过程中，数据发生了改变100，奇校验之后1001，传递错误，“1”为偶数

如果，我们在传递过程中，数据发生了改变101，奇校验之后1011，校验正确，传递错误

因此：奇偶校验，只可检查1位（奇位都可以）的错误，不可纠错


（三）校验码——循环校验码CRC

CRC校验，可检错，不可纠错


CRC的编码方式是：在k位信息码之后拼接r位校验码


应用CRC码的关键是如何从k位信息位简便地得到r位校验码（编码），以及如何从k+r位信息码判断是否出错


循环冗余校验码编码规律如下：

把待编码的N位有效信息表示为多项式M(X)
把M(X)左移K位，得到M(X)×XK,这样空出了K位，以便拼接K位余数（即校验码）
选取一个K+1位的产生多项式G(X)，对M(X)×XK做模2除
把左移K位以后的有效信息与余数R(X)做模2加减，拼接为CRC码，此时的CRC码共有N+K位



把接收到的CRC码用约定的生成多项式G(X)去除，如果正确，则余数为0；如果某一位出错，则余数不为0


不同的位数出错其余数不同，余数和出错位序号之间有唯一的对应关系


模2除法：

模2除法是指在做除法运算的过程中不计算进位的除法







（四）校验码——海明校验码

海明校验，可检错，也可纠错

原理：在有效信息位中加入几个校验位形成海明码，使码距比较均匀拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供依据
2r >= m+r+1
m 有效信息位位数（一般会直接给出）
r （求取） 编码位数  一般求至少需要多少位数
海明校验：主要是对于不同的分组当中，都会涉及到相同的校验位置（交叉），由于一个位置出错，会引起其他校验位置发生改变，根据交叉，锁定出错位置，从而纠错




——时人不识凌云木，直待凌云始道高——

最近在学习的时候偶然看到了海明码校验，就想着自己写一下。

先来抄一下百度~

汉明码（Hamming Code），是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，当计算机存储或移动数据时，可能会产生数据位错误，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM）。

海明码的算法这里就不多废话了，直接上代码（只是简易的实现一下，实现的方法有很多，大佬们不喜勿喷，）
public static void main(String[] args) {
		String yuanma = "1011";//输入源码
		int length = yuanma.length();
		int n = getN(yuanma, length);
		
		//定义H、S、P
		String[] H = new String[length + n + 1];
		String[] S = new String[length];
		int[] P = new int[n];
		
		
		for (int i = 0; i < length; i++) {
			S[i] = yuanma.substring(i, i + 1);
		}
		//计算校验位
		int j = 0;
		int k = 0;
		for (int i = 1; i < H.length; i++) {
			if (i <= n) {
				int e = (int) Math.pow(2, i - 1);
				H[e] = "P" + i;
				P[k] = e;
				k = k + 1;
			}
		}
		for (int i = 1; i < H.length; i++) {
			if (H[i] == null) {
				H[i] = S[S.length - j - 1];
				j += 1;
			}
		}
		System.out.print("H:");
		for (int i = 1; i < H.length; i++)
			System.out.print(H[i] + " ");
		System.out.println("");
		System.out.print("P:");
		for (int i = 0; i < P.length; i++)
			System.out.print(P[i] + " ");
		System.out.println("");
		//插入对应校验位
		for (int r = 0; r < P.length; r++) {
			List<String> list = new ArrayList<String>();
			//跨几取几
			int e = P[r];
			//是否取/跨标识
			int f = 0;
			int m = e;
			for (int t = e; t < H.length; t++) {
				if (e > f && m == e) {
					list.add(H[t]);
					f = f + 1;
					if (e == f)
						m = 0;
				} else {
					f = 0;
					m = m + 1;
				}
			}
//			System.out.println(list);
			int num = 0;
			for (int i = 1; i < list.size(); i++) {
				if (list.get(i).equals("1")) {
					num = num + 1;
				}
			}
			int qq = r + 1;
			if (num % 2 != 0) {
				System.out.println("P" + qq + "=" + 1);
			} else {
				System.out.println("P" + qq + "=" + 0);
			}

		}

	}

	/**
	 *   计算校验位个数
	 * @param hmm
	 * @param length
	 * @return
	 */
	public static int getN(String hmm, int length) {
		int n = 1;
		while (true) {
			if (Math.pow(2, n) - n >= length + 1) {
				break;
			} else {
				n += 1;
			}
		}
		return n;
	}

最后倒序输出H，替换P在H的位置即为最终结果