数据传输和储存，常见的校验方法说明及其应用实现
奇偶校验（Parity Check）
原理：
奇偶校验是一种简单的错误检测机制，通过增加一个校验位（奇偶位）来使整个数据包的1的数量为奇数或偶数。
- 仅能检测单比特错误，无法纠正错误。
- 实现简单，适用于低错误率的场景。
类型：
- 奇校验（Odd Parity）：整个数据包中1的数量为奇数。
- 偶校验（Even Parity）：整个数据包中1的数量为偶数。
示例：
假设数据包为1010001。
- 奇校验：原数据中1的数量为3（奇数），所以校验位为0，数据包变为
10100010。 - 偶校验：原数据中1的数量为3（奇数），所以校验位为1，数据包变为
10100011。
如果接收方收到的数据中1的数量不符合预期的奇偶性，则表示数据包存在错误。
应用场景：
- 低错误率的简单通信系统：例如串行通信协议（如RS-232），用于基本的硬件通信。
- 存储设备：用于检测内存中的单比特错误。
- 数据传输：用于简单的网络协议和设备间数据传输。
java实现
public class ParityCheck {
// 方法：计算奇校验位
public static int calculateOddParity(int[] data) {
int parity = 0;
for (int bit : data) {
parity ^= bit; // 异或操作
}
return parity;
}
// 方法：计算偶校验位
public static int calculateEvenParity(int[] data) {
int parity = 1;
for (int bit : data) {
parity ^= bit; // 异或操作
}
return parity;
}
// 方法：验证奇校验
public static boolean verifyOddParity(int[] dataWithParity) {
int parity = 0;
for (int bit : dataWithParity) {
parity ^= bit; // 异或操作
}
return parity == 0; // 奇校验：最终结果应为0
}
// 方法：验证偶校验
public static boolean verifyEvenParity(int[] dataWithParity) {
int parity = 1;
for (int bit : dataWithParity) {
parity ^= bit; // 异或操作
}
return parity == 0; // 偶校验：最终结果应为0
}
public static void main(String[] args) {
int[] data = {1, 0, 1, 0, 0, 1}; // 示例数据
// 计算奇校验位
int oddParity = calculateOddParity(data);
System.out.println("奇校验位: " + oddParity);
// 计算偶校验位
int evenParity = calculateEvenParity(data);
System.out.println("偶校验位: " + evenParity);
// 添加校验位到数据末尾（奇校验）
int[] dataWithOddParity = new int[data.length + 1];
System.arraycopy(data, 0, dataWithOddParity, 0, data.length);
dataWithOddParity[data.length] = oddParity;
// 添加校验位到数据末尾（偶校验）
int[] dataWithEvenParity = new int[data.length + 1];
System.arraycopy(data, 0, dataWithEvenParity, 0, data.length);
dataWithEvenParity[data.length] = evenParity;
// 验证奇校验
boolean isOddParityValid = verifyOddParity(dataWithOddParity);
System.out.println("奇校验结果: " + (isOddParityValid ? "有效" : "无效"));
// 验证偶校验
boolean isEvenParityValid = verifyEvenParity(dataWithEvenParity);
System.out.println("偶校验结果: " + (isEvenParityValid ? "有效" : "无效"));
}
}
CRC校验（Cyclic Redundancy Check）
原理：
CRC校验是一种更复杂的错误检测方法，通过将数据视为一个大多项式，然后对这个多项式进行模一个预定的生成多项式的除法操作，得到一个余数（CRC校验码）。这个余数被附加到数据末尾进行传输。
- 能检测多比特错误，通常用于数据链路层协议。
- 计算复杂度较高，但错误检测能力强。
示例：
假设数据包为1101011011，生成多项式为1011（对应于x^3 + x + 1）。
- 将数据末尾加上生成多项式的位数-1个0，即
1101011011000。 - 用生成多项式
1011对上述数据进行二进制除法，得到余数100。 - 余数作为校验码附加到数据末尾，即数据包变为
1101011011100。
接收方进行相同的除法操作，如果余数为0，则表示数据没有错误。
应用场景：
- 网络通信：广泛应用于网络层和数据链路层协议（如以太网、PPP、HDLC等）来检测传输数据中的错误。
- 存储设备：如硬盘、光盘等，用于数据块的错误检测。
- 无线通信：用于无线传输协议，保证数据完整性。
java代码实现
CRC-32
import java.util.zip.CRC32;
public class CRCCheck {
// 方法：计算CRC32校验码
public static long calculateCRC32(byte[] data) {
CRC32 crc32 = new CRC32();
crc32.update(data);
return crc32.getValue();
}
// 方法：验证CRC32校验码
public static boolean verifyCRC32(byte[] data, long expectedCRC) {
long calculatedCRC = calculateCRC32(data);
return calculatedCRC == expectedCRC;
}
public static void main(String[] args) {
String input = "Hello, world!"; // 示例输入数据
byte[] data = input.getBytes();
// 计算CRC32校验码
long crcValue = calculateCRC32(data);
System.out.println("CRC32校验码: " + Long.toHexString(crcValue));
// 验证CRC32校验码
boolean isValid = verifyCRC32(data, crcValue);
System.out.println("CRC32校验结果: " + (isValid ? "有效" : "无效"));
// 修改数据后验证CRC32
data[0] = 'h'; // 修改数据的第一个字节
isValid = verifyCRC32(data, crcValue);
System.out.println("修改后CRC32校验结果: " + (isValid ? "有效" : "无效"));
}
}CRC-8（对应于x^8 + x^2 + x + 1）
public class CRC8 {
// CRC-8 多项式 (x^8 + x^2 + x + 1)
private static final int POLYNOMIAL = 0x07;
// 初始化值
private static final int INITIAL_VALUE = 0x00;
// 方法：计算CRC-8校验码
public static int calculateCRC8(byte[] data) {
int crc = INITIAL_VALUE;
for (byte b : data) {
crc ^= b; // 异或操作
for (int i = 0; i < 8; i++) {
if ((crc & 0x80) != 0) {
crc = (crc << 1) ^ POLYNOMIAL;
} else {
crc <<= 1;
}
}
}
return crc & 0xFF; // 取低8位作为CRC-8校验码
}
// 方法：验证CRC-8校验码
public static boolean verifyCRC8(byte[] data, int expectedCRC) {
int calculatedCRC = calculateCRC8(data);
return calculatedCRC == expectedCRC;
}
public static void main(String[] args) {
String input = "Hello, CRC-8!"; // 示例输入数据
byte[] data = input.getBytes();
// 计算CRC-8校验码
int crcValue = calculateCRC8(data);
System.out.println("CRC-8校验码: " + Integer.toHexString(crcValue));
// 验证CRC-8校验码
boolean isValid = verifyCRC8(data, crcValue);
System.out.println("CRC-8校验结果: " + (isValid ? "有效" : "无效"));
// 修改数据后验证CRC-8
data[0] = 'h'; // 修改数据的第一个字节
isValid = verifyCRC8(data, crcValue);
System.out.println("修改后CRC-8校验结果: " + (isValid ? "有效" : "无效"));
}
}CRC-16（对应于x^16 + x^12 + x^5 + 1）
public class CRC16 {
// CRC-16-CCITT 多项式 (x^16 + x^12 + x^5 + 1)
private static final int POLYNOMIAL = 0x1021;
// 初始化值
private static final int INITIAL_VALUE = 0xFFFF;
// 方法：计算CRC-16校验码
public static int calculateCRC16(byte[] data) {
int crc = INITIAL_VALUE;
for (byte b : data) {
crc ^= (b << 8); // 将当前字节移位到高8位
for (int i = 0; i < 8; i++) {
if ((crc & 0x8000) != 0) {
crc = (crc << 1) ^ POLYNOMIAL;
} else {
crc <<= 1;
}
}
}
return crc & 0xFFFF; // 取低16位作为CRC-16校验码
}
// 方法：验证CRC-16校验码
public static boolean verifyCRC16(byte[] data, int expectedCRC) {
int calculatedCRC = calculateCRC16(data);
return calculatedCRC == expectedCRC;
}
public static void main(String[] args) {
String input = "Hello, CRC-16!"; // 示例输入数据
byte[] data = input.getBytes();
// 计算CRC-16校验码
int crcValue = calculateCRC16(data);
System.out.println("CRC-16校验码: " + Integer.toHexString(crcValue));
// 验证CRC-16校验码
boolean isValid = verifyCRC16(data, crcValue);
System.out.println("CRC-16校验结果: " + (isValid ? "有效" : "无效"));
// 修改数据后验证CRC-16
data[0] = 'h'; // 修改数据的第一个字节
isValid = verifyCRC16(data, crcValue);
System.out.println("修改后CRC-16校验结果: " + (isValid ? "有效" : "无效"));
}
}
海明码校验（Hamming Code）
原理：
海明码不仅能检测错误，还能纠正单比特错误。它通过在数据中插入多个校验位来实现。这些校验位的位置根据2的幂指数确定，并且每个校验位检查特定位置的位的组合。
- 能检测和纠正单比特错误，部分情况还能检测多比特错误。
- 适用于需要高可靠性的内存和存储系统。
示例：
假设数据包为1011。
- 确定需要插入的校验位位置。对于4位数据，需要3个校验位，位置为1, 2, 4。
- 在原数据中插入校验位，初步数据包变为
_ _ 1 _ 0 1 1。 - 计算校验位的值：
- 第1位校验位计算位置1, 3, 5, 7的位，得到
1。 - 第2位校验位计算位置2, 3, 6, 7的位，得到
0。 - 第4位校验位计算位置4, 5, 6, 7的位，得到
1。
- 第1位校验位计算位置1, 3, 5, 7的位，得到
- 最终数据包变为
1010111。
在接收时，如果发现校验位不一致，可以通过校验位的位置组合确定并纠正错误位。
应用场景：
- 内存错误检测和纠正：用于ECC（错误检测和纠正）内存，确保计算机内存中的数据完整性。
- 计算机网络：用于简单的数据链路层协议，确保数据包的完整性。
- 嵌入式系统：用于对可靠性要求较高的嵌入式系统中，检测和纠正单比特错误。
java代码实现
import java.util.ArrayList;
public class HammingCode {
// 方法：计算和插入校验位
public static int[] generateHammingCode(int[] data) {
int r = 0; // 校验位数量
int m = data.length; // 数据位数量
// 计算需要的校验位数量 r
while (Math.pow(2, r) < (m + r + 1)) {
r++;
}
int[] hammingCode = new int[m + r];
int j = 0;
// 插入校验位位置
for (int i = 0; i < hammingCode.length; i++) {
if (Math.pow(2, j) - 1 == i) {
hammingCode[i] = 0; // 暂时填0
j++;
} else {
hammingCode[i] = data[i - j];
}
}
// 计算校验位的值
for (int i = 0; i < r; i++) {
int position = (int) Math.pow(2, i);
int value = 0;
for (int k = position - 1; k < hammingCode.length; k += 2 * position) {
for (int l = k; l < k + position && l < hammingCode.length; l++) {
value ^= hammingCode[l];
}
}
hammingCode[position - 1] = value;
}
return hammingCode;
}
// 方法：验证海明码
public static int verifyHammingCode(int[] hammingCode) {
int r = 0;
// 计算校验位数量 r
while (Math.pow(2, r) < (hammingCode.length + 1)) {
r++;
}
int errorPosition = 0;
// 计算校验位并找出错误位置
for (int i = 0; i < r; i++) {
int position = (int) Math.pow(2, i);
int value = 0;
for (int k = position - 1; k < hammingCode.length; k += 2 * position) {
for (int l = k; l < k + position && l < hammingCode.length; l++) {
value ^= hammingCode[l];
}
}
if (value != 0) {
errorPosition += position;
}
}
return errorPosition;
}
public static void main(String[] args) {
int[] data = {1, 0, 1, 1}; // 示例数据
// 生成海明码
int[] hammingCode = generateHammingCode(data);
System.out.print("生成的海明码: ");
for (int bit : hammingCode) {
System.out.print(bit);
}
System.out.println();
// 验证海明码
int errorPosition = verifyHammingCode(hammingCode);
System.out.println("海明码校验结果: " + (errorPosition == 0 ? "无错误" : "错误位置：" + errorPosition));
// 模拟一个错误
hammingCode[2] ^= 1;
errorPosition = verifyHammingCode(hammingCode);
System.out.println("修改后海明码校验结果: " + (errorPosition == 0 ? "无错误" : "错误位置：" + errorPosition));
// 修正错误
if (errorPosition != 0) {
hammingCode[errorPosition - 1] ^= 1;
System.out.print("修正后的海明码: ");
for (int bit : hammingCode) {
System.out.print(bit);
}
System.out.println();
}
}
}
校验和（Checksum）
原理：
校验和是一种简单的错误检测方法，通过将数据分块后对每块数据进行求和操作，最后将和值附加到数据末尾进行传输。接收方重新计算和值，如果与接收到的和值一致，则表示数据没有错误。
示例：
假设数据包为1010001和1100101（两块数据）。
- 每块数据转为十进制：
1010001为81，1100101为101。 - 求和：
81 + 101 = 182。 - 将和值转为二进制：
182为10110110。 - 将和值附加到数据包末尾进行传输。
接收方对接收的数据重新计算和值，若一致，则数据无误。
应用场景：
- 互联网协议：如TCP/IP中的IPv4头部校验和、UDP校验和、TCP校验和，用于确保数据包头部和负载的完整性。
- 文件传输：在文件传输协议（如FTP）中，用于验证文件的完整性。
- 嵌入式系统：用于嵌入式设备的固件校验，确保代码和数据的正确性。
java代码实现
- 计算数据的校验和。
- 将校验和附加到数据的末尾进行传输。
- 接收方计算接收到的数据的校验和，并与传输的校验和进行比较，以验证数据完整性。
public class Checksum {
// 方法：计算校验和
public static int calculateChecksum(byte[] data) {
int checksum = 0;
for (byte b : data) {
checksum += (b & 0xFF); // 将byte转换为无符号int
}
// 将校验和限制在一个字节范围内（0-255）
checksum = checksum & 0xFF;
return checksum;
}
// 方法：验证校验和
public static boolean verifyChecksum(byte[] data, int expectedChecksum) {
int calculatedChecksum = calculateChecksum(data);
return calculatedChecksum == expectedChecksum;
}
public static void main(String[] args) {
String input = "Hello, Checksum!"; // 示例输入数据
byte[] data = input.getBytes();
// 计算校验和
int checksumValue = calculateChecksum(data);
System.out.println("校验和: " + Integer.toHexString(checksumValue));
// 验证校验和
boolean isValid = verifyChecksum(data, checksumValue);
System.out.println("校验和结果: " + (isValid ? "有效" : "无效"));
// 模拟一个错误
data[0] = 'h'; // 修改数据的第一个字节
isValid = verifyChecksum(data, checksumValue);
System.out.println("修改后校验和结果: " + (isValid ? "有效" : "无效"));
}
}
鲁棒哈希（Robust Hash）
原理：
哈希校验利用哈希函数将数据映射到一个固定长度的值（哈希值）。这种方法可以快速检测数据的完整性，但不能纠正错误。常见的哈希函数包括MD5、SHA-1、SHA-256等。
示例：
假设数据包为Hello, world!。
- 使用SHA-256哈希函数计算哈希值，得到
7f83b1657ff1fc53b92dc18148a1d65dfa13573eaa04c20e82e8f142b245e69d。 - 将哈希值附加到数据末尾进行传输。
接收方对接收的数据重新计算哈希值，若一致，则数据无误。
应用场景：
- 文件完整性校验：如MD5、SHA系列哈希算法，广泛用于校验文件下载和传输的完整性。
- 数据存储：用于校验数据库和文件系统中的数据完整性。
- 数字签名和证书：确保数据未被篡改，用于验证数据的真实性和完整性。
循环冗余校验（LRC）
原理：
纵向冗余校验（LRC）通过对数据每列的值进行求和操作，得到的结果作为校验码附加到数据末尾。适用于多块数据的校验。
示例：
假设数据包为：
1101 1011 0110
- 每列求和：
- 第1列：
1 + 1 + 0 = 2（取模2得到0） - 第2列：
1 + 0 + 1 = 2（取模2得到0） - 第3列：
0 + 1 + 1 = 2（取模2得到0） - 第4列：
1 + 1 + 0 = 2（取模2得到0）
- 第1列：
- 校验码为
0000。
将校验码附加到数据包末尾进行传输，接收方进行相同的列求和校验。
应用场景：
- 工业通信协议：如Modbus协议中，用于检测数据帧的错误。
- 数据记录和传输：用于某些存储和传输设备，确保数据块的一致性。
- 简单嵌入式系统：用于低资源需求的系统中，进行基本的错误检测。
瑞德-所罗门码（Reed-Solomon Code）
原理：
瑞德-所罗门码是一种广泛应用于通信和存储的纠错码，能够纠正多比特错误。通过将数据视为多项式，利用有限域上的多项式运算实现错误检测和纠正。
示例：
假设数据包为[1, 2, 3, 4]，生成多项式为[1, 0, 1]。
- 数据视为多项式
1 + 2x + 3x^2 + 4x^3。 - 生成多项式为
1 + x^2。 - 利用有限域上的多项式运算得到校验码，假设为
[2, 1]。 - 将校验码附加到数据包末尾进行传输。
接收方通过多项式除法和有限域运算检测和纠正错误。
应用场景：
- 光盘存储：如CD、DVD、Blu-ray，确保在读写过程中纠正错误。
- 数字电视和广播：用于地面、卫星和有线数字电视传输，保证视频和音频数据的完整性。
- 数据存储：用于RAID系统和固态硬盘中的数据纠错。
- 通信系统：如卫星通信、深空通信和移动通信，用于增强信号的可靠性。
博斯-乔杜里-霍克因码（BCH Code）
原理：
BCH码是一种适用于多比特错误纠正的编码方法，通过生成多项式和解码算法实现高效的错误检测和纠正。
示例：
假设数据包为[1011011]，生成多项式为x^4 + x + 1。
- 数据视为多项式
1 + 0x + 1x^2 + 1x^3 + 1x^4。 - 生成多项式为
x^4 + x + 1。 - 利用多项式除法得到校验码，假设为
[1101]。 - 将校验码附加到数据包末尾进行传输。
接收方通过多项式除法检测和纠正错误。
应用场景：
- NAND闪存：用于固态硬盘和存储卡中的数据纠错，确保高密度存储的可靠性。
- 卫星通信：用于深空探测器的通信系统，增强数据传输的可靠性。
- 移动通信：用于移动通信标准（如LTE、WiMAX）中的数据纠错，保证信号的稳定性。
- QR码：用于二维码中的数据纠错，提高条码扫描的可靠性。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ALLBS！
支付宝- 微信
- qq
评论