Cyclic Redundancy Checking (CRC) Part 3: Augmentation and Null CRC

CRC augmentation means appending as many zeros to the data as the degree of the generator polynomial, dividing that augmented value by the generator, and then placing the remainder (the checksum) in those zero positions. The transmitted word then divides exactly by the generator, so the receiver gets a null (zero) CRC result when nothing is corrupted, while the original data and the checksum both remain intact and easy to separate.

This is Part 3 of the series on cyclic redundancy checking. Part 1 and Part 2 cover the basics of polynomial division and checksum generation.

Key takeaways

• Augment the data with n zeros, where n is the degree of the generator polynomial (3 zeros for x³ + x² + 1).
• The remainder always has fewer than n bits, so it fits in the zero positions without disturbing the data.
• Data followed by its checksum divides exactly by the generator: a receiver checks for a zero remainder and then simply drops the last n bits.
• In CRC arithmetic, "add" means modulo-2 addition, which is a bitwise XOR with no carries.
• A hardware LFSR performs the augmentation implicitly, so the zeros never have to be shifted in.

Why a null CRC result is useful

Augmentation is a technique used to produce a null CRC result while preserving both the original data and the CRC checksum. In communication systems using cyclic redundancy checking, it is desirable to obtain a null CRC result for each transmission, because the simplified verification helps to speed up data handling: the receiver runs one division over everything it received and tests for zero, instead of recomputing a checksum and comparing it with a separate field.

The problem with the traditional approach

Traditionally, a null CRC result was generated by adding the cyclic redundancy checksum to the data and calculating the CRC on the new data. While this simplifies the verification, it has the unfortunate side effect of changing the data. Any node receiving the data+CRC result can verify that no corruption has occurred, but cannot extract the original data, because the checksum is not known. This can be overcome by transmitting the checksum along with the modified data, but any data-handling advantage gained in the verification process is offset by the additional steps needed to recover the original data.

How augmentation works

Augmentation allows the data to be transmitted along with its checksum and still obtain a null CRC result. As explained above, when the checksum is simply added to the data, the data changes. Augmentation avoids this by shifting the data left, or augmenting it with a number of zeros equal to the degree of the generator polynomial. When the CRC result for the shifted data is added, both the original data and the checksum are preserved.

Why it always works

Write the data as a polynomial M(x), the generator as G(x) of degree n, and the remainder as R(x). Shifting the data left by n places is multiplying by xⁿ. Polynomial division gives:

M(x) * x^n = Q(x) * G(x) + R(x)

In modulo-2 arithmetic, addition and subtraction are the same operation (XOR), so adding R(x) to both sides gives:

M(x) * x^n + R(x) = Q(x) * G(x)

The left side is exactly the transmitted word, data followed by checksum, and the right side is a multiple of G(x). Dividing it by G(x) therefore leaves a remainder of zero.

Worked example: 0xD6B5 with generator 1101

In this example the generator polynomial is x³ + x² + 1, or 1101 in binary. It has degree 3, so the data (0xD6B5) is shifted to the left by three places, that is, augmented by three zeros.

Step	Hex	Binary
Original data	0xD6B5	1101011010110101
Augmented with 3 zeros	0x6B5A8	1101011010110101 000
Remainder after dividing by 1101	0b101	101
Augmented data + remainder (transmitted)	0x6B5AD	1101011010110101 101

Note that the original data is still present within the augmented data: the top 16 bits are D6B5 and the bottom 3 bits are the augmentation, 000.

The long division

Each step XORs the generator under the leading 1 of the running value. Only four steps are needed for this data:

augmented data  1101011010110101000
XOR 1101   ->   0000011010110101000
XOR 1101   ->   0000000000110101000
XOR 1101   ->   0000000000000001000
XOR 1101   ->   0000000000000000101   remainder = 101

Calculating the CRC for the augmented data (0x6B5A8) with the generator 1101 gives a remainder of 101 (a polynomial of degree 2). Adding this to the augmented data gives:

0x6B5A8 + 0b101 = 1101011010110101000 + 101
                = 1101011010110101101
                = 0x6B5AD

Because the low three bits of the augmented data are zero, the modulo-2 addition here is the same as simply writing 101 into those bits.

Checking at the receiver

Calculating the CRC for 0x6B5AD gives a null result, which simplifies the verification. What is less obvious is that the original data is still preserved intact:

0x6B5AD = 1101011010110101 101
          Data = D6B5      CRC = 101

The degree of the remainder, the cyclic redundancy checksum, is always less than the degree of the generator polynomial. By augmenting the data with a number of zeros equal to the degree of the generator, we make sure the addition of the checksum does not affect the data bits.

In any communication system using cyclic redundancy checking, the same generator polynomial is used by both transmitting and receiving nodes to generate checksums and verify data. As the receiving node knows the degree of the generator polynomial, it is a simple task for it to verify the transmission by calculating the checksum and testing for zero, and then extract the data by discarding the last three bits.

If one bit is corrupted in transit, for example bit 7 of the data flips so that the received data reads D635, long division of the received 19-bit word gives a remainder of 101 instead of 000, and the receiver rejects the frame.

Implementing it in hardware: the LFSR shortcut

In hardware, CRCs are normally computed with a linear feedback shift register (LFSR). A common form XORs each incoming data bit with the top bit of the register before it feeds back into the taps. This form gives the same remainder as dividing the augmented data, without ever shifting in the n zeros, which saves n clock cycles per frame. The receiver uses the same circuit over data plus checksum and checks for zero.

`timescale 1ns/1ns
// Serial CRC-3, generator x^3 + x^2 + 1 (binary 1101), data MSB first.
// This LFSR form divides the message as if it had been augmented with
// three zeros, so the zeros never have to be shifted in.
module crc3_serial (
  input  wire       clk,
  input  wire       rst,
  input  wire       en,
  input  wire       din,
  output reg  [2:0] crc
);
  wire fb = crc[2] ^ din;
  always @(posedge clk) begin
    if (rst)     crc <= 3'b000;
    else if (en) crc <= {crc[1] ^ fb, crc[0], fb};   // taps for x^2 and x^0
  end
endmodule

A testbench that shifts in the example values, MSB first, prints:

CRC of 0xD6B5            = 101 (expect 101)
CRC of 0x6B5AD           = 000 (expect 000)
CRC with one bit flipped = 110 (non-zero)

The first line confirms that feeding only the 16 data bits gives the same 101 as long division of the augmented value. The second confirms the null result for data plus checksum. For the corrupted word this LFSR form reports 110 rather than the 101 from long division, because it effectively computes the remainder of the received word multiplied by x³. The exact non-zero value differs, but zero still means "no error detected" in both methods, which is all the receiver needs.

How this relates to real CRCs

The 3-bit generator used here is chosen to keep the arithmetic readable. Production protocols use longer generators, such as the 16-bit CRC-CCITT family or the 32-bit CRC used by Ethernet (IEEE 802.3). The augmentation principle is the same, but practical CRCs add details that change what the receiver sees:

• Initial value. Many CRCs preload the register with all ones instead of zeros, so that leading zero bytes in the data still affect the result.
• Final XOR. Many CRCs invert the remainder before sending it.
• Bit order. Some protocols send each byte least significant bit first, so the CRC is computed on reflected data.

With a preload and a final inversion, a correct frame no longer leaves zero in the receiver's register. It leaves a fixed, known constant (often called the residue or "magic number"), and the receiver compares against that constant instead of zero. The idea is unchanged: one pass over data plus checksum, then a single comparison.

Common mistakes

• Augmenting by the wrong number of zeros. The count is the degree of the generator (3 for 1101), not its number of bits (4).
• Using ordinary binary addition. CRC arithmetic is modulo 2 with no carries. Using normal subtraction during the division gives the wrong remainder.
• Shifting in zeros with an LFSR that already augments. If the circuit XORs the input with the feedback bit, adding n extra zeros computes a different remainder.
• Mismatched conventions between ends. Transmitter and receiver must agree on the generator, initial value, final XOR and bit order, or every frame will fail.

FAQ

Why does the checksum not overwrite any data bits?

The remainder of a division by a degree-n polynomial has at most n bits, and augmentation reserves exactly n zero bits at the end of the data. The checksum lands only in those positions.

Does the receiver need to know the checksum separately?

No. It divides everything it received by the same generator. A zero remainder means the frame is accepted, and the data is everything except the last n bits.

What errors can a degree-3 generator like 1101 catch?

Any generator with more than one term detects all single-bit errors, and a degree-n generator with a non-zero constant term detects all burst errors of length n or less. Longer generators are used in practice because they also catch most longer bursts and multiple-bit errors.

Is augmentation the same as appending the CRC?

In effect, yes. Appending the checksum after the data is the transmitted result of augmentation; the zeros are only a step in the calculation, and an LFSR skips that step.