CRC

From My wiki
Jump to: navigation, search

What is

CRC (Cyclic Redundancy Check) is a checksum algorithm to detect inconsistency of data, e.g. bit errors during data transmission. A checksum, calculated by CRC, is attached to the data to help the receiver to detect such errors.

CRC is based on division. The actual input data is interpreted as one long binary bit stream (divident) which is divided by another fixed binary number (divisor). The remainder of this division is the checksum value. However, reality is a bit more complicated. The binary numbers (divident and divisor) are not treated as normal integer values, but as binary polyonimals where the actual bits are used as coefficients.

Division of polynomials differs from integer division. Without going into detail, the underlying used aritmetic for CRC calculation is based on the XOR (Exclusive-OR) operation.

  • The divident is the complete input data (interpreted as binary stream).
  • The divisor, also called generator polynomial, is statically defined by the used CRC algorithm. CRC-n using a fixed defined generator polynom with (n+1) bits.
  • The CRC checksum value is defined as divident % divisor.

Source

Example

Input data is the byte 0xC2 = b11000010.

As generator polynomial (=divisor), let's use b100011101.

The divisor has 9 bits (therefore this is a CRC-8 polynomial), so append 8 zero bits to the input pattern.

Align the leading '1' of the divisor with the first '1' of the divident and perform a step-by-step school-like division, using XOR operation for each bit:


 1100001000000000
 100011101
 ---------
 010011001
  100011101
  ----------
  000101111
     100011101           (*)
     ---------
     001100101
       100011101
       ---------
       010001001
        100011101
        ---------
        000001111 = 0x0F

The actual CRC value is 0x0F (15).

Useful observations:

  • In each step, the leading '1' of the divisor is always aligned with the first '1' of the divident. This implies that the divisor does not move only 1 bit right per step, but sometimes also several steps (e.g. like in line (*).
  • The algorithms stops if the divisor zeroed out each bit of the actual input data (without padding bytes): The input data ranges from column A to H including. In the last step, column H and all prior columns contain 0, so the algorithm stops.
  • The remainder (= CRC) is the value 'below' the padding zero bits (column I to P). Because we added n padding bytes, the actual CRC value has also n bits.
  • Only the remainder in each step is of interest, the actual division result (quotient) is therefore not tracked at all.


Source (CRC-8)

Java

Main

package com.iaspp;

import com.iaspp.checksum.crc.Crc8;

public class Main {

	public static void main(String[] args) {
		test(new byte[] { (byte) 'T' }); // 0xab
		test(new byte[] { (byte) 0x03, (byte) 0x73 }); // 0x61
		test(new byte[] { (byte) 0x01, (byte) 0x3f, (byte) 'b' }); // 0x78
	}

	/*
	 * For tests only
	 */
	private static char[] hexDigits = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

	private static String hexString(byte b) {
		return hexDigits[0xf & (b >> 4)] + "" + hexDigits[b & 0xf];
	}

	private static void test(byte[] vec) {
		Crc8 crc = new Crc8();
		System.out.println(hexString(crc.computeCRC8(vec)));
	}
}

CRC-8

package com.iaspp.checksum.crc;

import java.io.Serializable;

public class Crc8 implements Serializable {

	private static final long serialVersionUID = 7530964900288429736L;

	private static final byte[] crctable;

	static {
		crctable = new byte[256];
		byte polynomial = 0x07; // 0x107 less the leading x^8

		for (int i = 0; i < 256; i++) {
			byte j = (byte) i;
			for (int k = 0; k < 8; k++) {
				j = (byte) ((j < 0) ? (j << 1) ^ polynomial : j << 1);
			}

			crctable[i] = j;
		}
	}

	public byte computeCRC8(byte[] data) {
		byte crcReg = 0;
		for (byte b : data) {
			crcReg = crctable[(crcReg ^ b) & 0xFF];
		}
		return crcReg;
	}
}

C++

Main

//============================================================================
// Name        : Codes.cpp
// Author      : Iago
// Version     :
// Copyright   : 
// Description :
//============================================================================

#include <iostream>
#include "Crc8.h"

using namespace std;
using namespace iaspp;
int main() {
	Crc8 crc;

	/*test(new byte[] { (byte) 'T' }); // 0xab
	 test(new byte[] { (byte) 0x03, (byte) 0x73 }); // 0x61
	 test(new byte[] { (byte) 0x01, (byte) 0x3f, (byte) 'b' }); // 0x78*/
	uint8_t input0[] = { 'T' };
	uint8_t input1[] = { 0x03, 0x73 };
	uint8_t input2[] = { 0x01, 0x3f, 'b' };

	cout << hex << +crc.checksum(input0, 1) << endl;
	cout << hex << +crc.checksum(input1, 2) << endl;
	cout << hex << +crc.checksum(input2, 3) << endl;

	return 0;
}

CRC-8

Header
/*
 * Crc8.h
 *
 *  Created on: Mar 29, 2019
 *      Author: Iago
 */

#ifndef CRC8_H_
#define CRC8_H_

#include <stdint.h>

namespace iaspp {

class Crc8 {
public:
	Crc8();
	~Crc8();
	uint8_t checksum(uint8_t input[], int size);
private:
	uint8_t crctable[256];

	void createTable();
};

} /* namespace iaspp */

#endif /* CRC8_H_ */
Implementation
/*
 * Crc8.cpp
 *
 *  Created on: Mar 29, 2019
 *      Author: Iago
 */

#include "Crc8.h"
#include <vector>

namespace iaspp {

Crc8::Crc8() {
	this->createTable();
}

Crc8::~Crc8(){

}

void Crc8::createTable() {
	uint8_t polynomial = 0x07;
	for (int i = 0; i < 256; i++) {
		int8_t j = (int8_t) i;
		for (int k = 0; k < 8; k++) {
			j = (uint8_t) ((j < 0) ? (j << 1) ^ polynomial : j << 1);
		}
		this->crctable[i] = j;
	}
}

uint8_t Crc8::checksum(uint8_t input[], int size) {
	uint8_t crcReg = 0;

	std::vector<uint8_t> data(input, input + size);

	for (uint8_t b : data) {
		crcReg = crctable[(crcReg ^ b) & 0xFF];
	}
	return crcReg;
}

}
/* namespace iaspp */

Links

Java Source