计算器系统基础知识-校验码

1.奇偶校验码

  通过在编码中增加一位奇数校验位来使编码中1的个数为奇数(奇校验)或者为偶数(偶校验)，从而使码距变为2。
  常见的奇偶校验码有三种：水平奇偶校验码、垂直奇偶校验码和水平垂直校验码。
  以下是奇偶校验码的示例：

public class ParityCheck {public static String generateOddParity(String data) {StringBuilder parity = new StringBuilder();for (int i = 0; i < data.length(); i++) {int par = 0; // 记录奇数位的个数for (int j = 0; j < 8; j++) {if (((data.charAt(i) >> j) & 1) == 1) {par++;}}parity.append((par % 2 == 0) ? '0' : '1'); // 如果奇数位个数为偶数则补1，否则补0}return parity.toString();}public static String generateEvenParity(String data) {StringBuilder parity = new StringBuilder();for (int i = 0; i < data.length(); i++) {int par = 0; // 记录偶数位的个数for (int j = 0; j < 8; j++) {if (((data.charAt(i) >> j) & 1) == 1) {par++;}}parity.append((par % 2 == 0) ? '0' : '1'); // 如果偶数位个数为偶数则补1，否则补0}return parity.toString();}public static void main(String[] args) {String data = "Hello"; // 示例数据String oddParity = generateOddParity(data);String evenParity = generateEvenParity(data);System.out.println("Odd Parity: " + oddParity);System.out.println("Even Parity: " + evenParity);}
}

2.海明码

  海明码是由贝尔实验室的Richard Hamming设计的，是一种利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的特定位置上插入K个校验位，通过扩大码距来实现检错和纠错。
  设数据位为n位,校验位为k位，则n和k必须满足以下关系：
           $2^k-1>=n+k$

public class HammingCode {// 计算海明码的位数public static int calculateHammingCodeLength(int dataBits, int parityBits) {return dataBits + parityBits;}// 生成海明码public static int[] generateHammingCode(int[] dataCode, int[] parityCode, int[] hammingCode, int dataBits, int parityBits) {for (int i = 0; i < dataBits; i++) {hammingCode[i] = dataCode[i];}for (int i = 0; i < parityBits; i++) {hammingCode[dataBits + i] = parityCode[i];}return hammingCode;}// 检查海明码是否有错误public static boolean checkHammingCode(int[] hammingCode, int dataBits, int parityBits) {for (int i = 0; i < parityBits; i++) {int mask = 1 << (dataBits + i);int sum = 0;for (int j = 0; j < dataBits; j++) {if ((hammingCode[j] & mask) != 0) {sum++;}}if (sum % 2 != hammingCode[dataBits + i]) {return false;}}return true;}// 纠错海明码public static boolean correctHammingCode(int[] hammingCode, int dataBits, int parityBits) {for (int i = 0; i < parityBits; i++) {int mask = 1 << (dataBits + i);int sum = 0;for (int j = 0; j < dataBits; j++) {if ((hammingCode[j] & mask) != 0) {sum++;}}if (sum % 2 != hammingCode[dataBits + i]) {hammingCode[dataBits + i] = 1 - hammingCode[dataBits + i]; // 翻转错误位return true;}}return false;}public static void main(String[] args) {int dataBits = 3; // 数据位数int parityBits = 2; // 奇偶校验位数int totalBits = calculateHammingCodeLength(dataBits, parityBits);int[] dataCode = {0, 0, 1}; // 数据码字int[] parityCode = new int[parityBits]; // 奇偶校验码字int[] hammingCode = new int[totalBits]; // 海明码// 生成海明码generateHammingCode(dataCode, parityCode, hammingCode, dataBits, parityBits);// 检查海明码是否有错误boolean isValid = checkHammingCode(hammingCode, dataBits, parityBits);System.out.println("Is the Hamming Code valid? " + isValid);// 模拟一位错误hammingCode[1] = 1 - hammingCode[1];// 纠错海明码boolean isCorrected = correctHammingCode(hammingCode, dataBits, parityBits);System.out.println("Was the error corrected? " + isCorrected);// 打印纠正后的海明码for (int code : hammingCode) {System.out.print(code);}}
}

3.循环冗余校验码

  循环冗余校验码（又叫CRC校验码）广泛应用于数据通信领域和磁介质存储系统中。它利用生成多项式为k个数据位产生r个校验码来进行编码。循环冗余校验码由两部分组成，一部分为信息码，另一部分为校验码。如果信息码占$k$位，则校验码就占$n-k$位，其中，n为CRC码的字长，所以又称为$(n,k)$码。在求CRC编码时，采用的是模2运算，模2加减运算的规则是按位运算，不发生错位和进位。
  CRC校验码常用的类别有以下几种：
   (1)CRC-8: 生成多项式为$X8+X2+X+1$
   (2)CRC-16: 生成多项式为$X16+X15+X2+1$,一般常用于modbus协议
   (3)CRC-32：生成多项式为：$X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1$,一般常用于ZIP, RAR, IEEE 802 LAN/FDDI等。

  以下是关于CRC-16的应用示例：

import java.nio.charset.StandardCharsets;public class CRC16 {public static int crc16Ccitt(byte[] data) {int crc = 0xFFFF; // 初始值for (byte b : data) {for (int i = 0; i < 8; i++) {boolean bit = ((b >> (7 - i) & 1) == 1);boolean c15 = ((crc >> 15 & 1) == 1);crc <<= 1;if (c15 ^ bit) {crc ^= 0x1021; // CRC-CCITT多项式}}}return crc & 0xFFFF; // 确保结果是16位}public static void main(String[] args) {String data = "Hello, CRC!";int crc = crc16Ccitt(data.getBytes(StandardCharsets.UTF_8));String hexCrc = Integer.toHexString(crc);System.out.println("CRC16-CCITT Checksum: " + (hexCrc.length() == 4 ? "0x" + hexCrc : hexCrc));}
}