Cyclic redundancy checks

The amaranth.lib.crc module provides facilities for computing cyclic redundancy checks (CRCs) in software and in hardware.

Introduction

The essentials of a CRC computation are specified with an Algorithm object, which defines CRC width, polynomial, initial value, input/output reflection, and output XOR. Many commonly used CRC algorithms are available in the catalog module, while most other CRC designs can be accommodated by manually constructing an Algorithm.

An Algorithm is specialized for a particular data width to obtain Parameters, which fully define a CRC computation. Parameters.compute() computes a CRC in software, while Parameters.create() creates a Processor that computes a CRC in hardware.

Examples

from amaranth.lib.crc import Algorithm
from amaranth.lib.crc.catalog import CRC16_CCITT, CRC16_USB


# Compute a CRC in hardware using the predefined CRC16-CCITT algorithm and a data word
# width of 8 bits (in other words, computing it over bytes).
m.submodules.crc16_ccitt = crc16_ccitt = CRC16_CCITT().create()

# Compute a CRC in hardware using the predefined CRC16-USB algorithm and a data word
# width of 32 bits.
m.submodules.crc16_usb = crc16_usb = CRC16_USB(32).create()

# Compute a CRC in software using a custom CRC algorithm and explicitly specified data word
# width.
algo = Algorithm(crc_width=16, polynomial=0x1021, initial_crc=0xffff,
    reflect_input=False, reflect_output=False, xor_output=0x0000)
assert algo(data_width=8).compute(b"123456789") == 0x29b1

Algorithms and parameters

class amaranth.lib.crc.Algorithm(*, crc_width, polynomial, initial_crc, reflect_input, reflect_output, xor_output)

Essential parameters for cyclic redundancy check computation.

The parameter set is based on the Williams model from “A Painless Guide to CRC Error Detection Algorithms”.

For a reference of standard CRC parameter sets, refer to:

  • reveng’s catalogue, which uses an identical parameterisation;

  • crcmod’s list of predefined functions, but remove the leading ‘1’ from the polynominal, XOR the “Init-value” with “XOR-out” to obtain initial_crc, and where “Reversed” is True, set both reflect_input and reflect_output to True;

  • CRC Zoo, which contains only polynomials; use the “explicit +1” form of polynomial but remove the leading ‘1’.

Many commonly used CRC algorithms are available in the catalog module, which includes all entries in the reveng catalogue.

The essential parameters on their own cannot be used to perform CRC computation, and must be combined with a specific data word width. This can be done using algo(data_width), which returns a Parameters object.

Parameters:

  • crc_width (int) – Bit width of CRC word. Also known as “width” in the Williams model.

  • polynomial (int) – CRC polynomial to use, crc_width bits long, without the implicit x ** crc_width term. Polynomial is always specified with the highest order terms in the most significant bit positions; use reflect_input and reflect_output to perform a least significant bit first computation.

  • initial_crc (int) – Initial value of CRC register at reset. Most significant bit always corresponds to the highest order term in the CRC register.

  • reflect_input (bool) – If True, the input data words are bit-reflected, so that they are processed least significant bit first.

  • reflect_output (bool) – If True, the output CRC is bit-reflected, so that the least-significant bit of the output is the highest-order bit of the CRC register. Note that this reflection is performed over the entire CRC register; for transmission you may want to treat the output as a little-endian multi-word value, so for example the reflected 16-bit output 0x4E4C would be transmitted as the two octets 0x4C, 0x4E, each transmitted least significant bit first.

  • xor_output (int) – The output CRC will be the CRC register XOR’d with this value, applied after any output bit-reflection.

__call__(data_width=8)

Combine these essential parameters with a data word width to form complete parameters.

Returns:

Parameters(self, data_width)

Return type:

Parameters

class amaranth.lib.crc.Parameters(algorithm, data_width=8)

Complete parameters for cyclic redundancy check computation.

Contains the essential Algorithm parameters, plus the data word width.

A Parameters object can be used to directly compute CRCs using the compute() method, or to construct a hardware module using the create() method.

Parameters:

  • algorithm (Algorithm) – CRC algorithm to use. Specifies the CRC width, polynomial, initial value, whether to reflect the input or output words, and any output XOR.

  • data_width (int) – Bit width of data words.

residue()

Obtain the residual value left in the CRC register after processing a valid trailing CRC.

compute(data)

Compute the CRC of all data words in data.

Parameters:

data (iterable of int) – Data words, each of which is data_width bits wide.

create()

Create a hardware CRC generator with these parameters.

Returns:

Processor(self)

Return type:

Processor

CRC computation

class amaranth.lib.crc.Processor

Hardware cyclic redundancy check generator.

This module generates CRCs from an input data stream, which can be used to validate an existing CRC or generate a new CRC. It is configured by the Parameters class, which can handle most types of CRCs.

The CRC value is updated on any clock cycle where valid is asserted, with the updated value available on the crc output on the subsequent clock cycle. The latency is therefore one clock cycle, and the throughput is one data word per clock cycle.

The CRC is reset to its initial value whenever start is asserted. start and valid may be asserted on the same clock cycle, in which case a new CRC computation is started with the current value of data.

When data_width is 1, a classic bit-serial CRC is implemented for the given polynomial in a Galois-type shift register. For larger values of data_width, a similar architecture computes every new bit of the CRC in parallel.

The match_detected output may be used to validate data with a trailing CRC (also known as a codeword in coding theory). If the most recently processed data word(s) form the valid CRC of all the previous data words since start was asserted, the CRC register will always take on a fixed value known as the residue. The match_detected output indicates whether the CRC register currently contains this residue.

Parameters:

parameters (Parameters) – Parameters used for computation.

Attributes:

  • start (Signal(), in) – Assert to indicate the start of a CRC computation, re-initialising the CRC register to the initial value. May be asserted simultaneously with valid or by itself.

  • data (Signal(data_width), in) – Data word to add to CRC when valid is asserted.

  • valid (Signal(), in) – Assert when data is valid to add the data word to the CRC.

  • crc (Signal(crc_width), out) – Registered CRC output value, updated one clock cycle after valid becomes asserted.

  • match_detected (Signal(), out) – Asserted if the current CRC value indicates a valid codeword has been received.

Predefined algorithms

The following predefined CRC algorithms are available: