Generating CRC Diagrams with Pikchr and Bash

I recently helped a friend sort out a bug in a CRC function that revolved around using the wrong hexadecimal encoding for the CRC's generator polynomial. Wikipedia's article on the mathematics of CRCs names three different ways to represent or encode the same generator polynomial \(G(x)\) as a hexadecimal constant. Even though they all encode the same polynomial, the source code for a CRC implementation needs to match the chosen polynomial encoding in order to function properly.

In a future update or post I'll describe how exactly a C implementation should change depending on the encoding of the generator polynomial. In the meantime, I can highly recommend the CRC chapter in the second edition of Hacker's Delight by Henry S. Warren, Jr. as a good introduction to practical CRC implementations, though it only describes one polynomial encoding format. Todd K. Moon's ECC book describes the CRC math more in depth, but leaves implementation as an exercise to for the reader (rightfully so, considering it's use as a textbook) and does not discuss alternative encoding formats either. Philip Koopman's CRC Polynomial Zoo does provide encoded CRC polynomials in different formats, but does not provide example code for each format.

The three named polynomial encoding formats on Wikipedia are:

Wikipedia also points out that the "reciprocal" of a generator polynomial \(G(x)\), \(x^n G(x^{-1})\), has the same error detection abilities as the original generator polynomial. It names two encoding formats for the reciprocal:

So there are five different ways to interpret a hex constant like 0x1021 as the generator polynomial of a CRC.

Polynomial encoding design decisions

A polynomial of degree \(n\) has up to \(n+1\) terms, \(x^0\) through \(x^n\). So a \(GF(2)\) polynomial of degree 8 needs 9 bits to represent all of the coefficients. However, in a CRC generator polynomial the coefficients of the \(x^0\) and \(x^n\) terms are always 1, so they can be left out without losing any information. Thus a polynomial of degree 8 can fit in an 8-bit byte if either the \(x^0\) or \(x^n\) term are left out. The choice of which term to omit is one difference between the different polynomial encodings.

The other difference is whether the the MSB of the hex constant holds the most significant term of the polynomial (\(x^n\)) or the least significant (\(x^0\)). This determines whether the remainder register's bits must be shifted left or right.

Diagram generating script

To help the sort out my friend's bug I manually drew a circuit diagram using the Pikchr language to illustrate how the code was implementing a digital circuit for computing the CRC.

crc_0x8c.svg

Figure 1: Hex poly 0x8c, ascending, implicit \(x^8\). Click to see source.

I later wrote a script that can automatically generate the circuit diagrams from a polynomial. It takes a polynomial in different formats and converts it to a circuit diagram that uses right shifts. The bits inside the remainder register's flip-flop blocks correspond to the bits in an ascending polynomial encoding with an implicit \(x^n\) term.

For the purposes of this script, an "ascending" polynomial encoding has the least significant term in the MSB of the hex constant, such that printing the hex constant as a binary number reads left to right from \(x^0\) to \(x^n\). Perhaps it makes more sense for an ascending polynomial to have \(x^0\) in the LSB, but we write numbers on paper big-endian, and this is just the sort of arbitrary coordinate system decision that gives rise to these kinds of bugs in the first place.

Also, since \(x^0=1\), I say that an encoding that omits that term has an "implicit one". And since a polynomial whose highest degree term has a coefficient of 1 is called a "monic polynomial", I call that term the "monic term", for lack of a better word. Thus, an encoding that omits that term has an "implicit monic" term.

Finally, in my script I call Wikipedia's "Normal" encoding a "Forward" encoding, since it's the opposite of "Reverse" and both -n and -d flags were taken in the command line options. 

#!/bin/bash

# crc_diagram.sh draws circuit diagrams for a CRC hexadecimal
# polynomial.
# Copyright (C) 2022 Remington Furman
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <https://www.gnu.org/licenses/>.

usage () {
    cat <<EOF
Usage: $1 (-p powers | -h poly) [args]
  Explicit representation:
    -p powers  Use comma separated list of powers to set polynomial,
               ignore hexadecimal related arguments

  Hexadecimal representation:
    -h poly    Hexadecimal representation of polynomial
    Representation presets:
    -f         Forward/normal     polynomial format
    -r         Reverse            polynomial format
    -k         Koopman            polynomial format
    -c         reCiprocal         polynomial format
    -v         reVerse reciprocal polynomial format
    Representation parameters:
    -a         Ascending  polynomial (MSB is x^0) (default)
    -d         Descending polynomial (MSB is x^n)
    -n degree  Polynomial degree (x^N)
    -o         One   term (x^0) is implicit (default: explicit)
    -m         Monic term (x^n) is implicit (default: explicit)

  Diagram options:
    -l         Left shift the diagram (default: right)

  Miscellaneous:
    -u         Usage (help)
EOF
}


# Helper functions
dec () {
    # Convert number to decimal.
    printf "%d" "$1"
}
bin () {
    # Convert number to binary.
    bc <<<"obase=2;$(dec $1)"
}

superscript () {
    if true ; then
        # Replace digits with Unicode superscript characters.
        sed 'y/0123456789/⁰¹²³⁴⁵⁶⁷⁸⁹/' <<< "$1"
    else
        # Prefix digits with ^.
        echo "^${1}"
    fi
}


# Set default parameters.
POLY_HEX=
IMPLICIT_ONE=    # Blank if the term is already included in the hex poly,
IMPLICIT_MONIC=  # otherwise 1.
ASCENDING=true   # MSB of hex constant holds x^0.
                 # (It's ascending left to right when printed in binary.)
DEGREE=          # Necessary when degree can't be inferred from format.
FWD="right"      # Plot shift direction.
REV="left"       # Opposite of shift direction.


# Read command line arguments.
optstring="p:h:frkcvadn:omlu"
while getopts ${optstring} arg; do
    case ${arg} in
        p)                      # Explicit polynomial representation
            declare -i POLY_INT=0
            IFS=',' read -ra POWERS <<< "${OPTARG}"
            for i in "${POWERS[@]}"; do
                ((POLY_INT |= 1<<"$i"))
            done
            POLY_BIN=$(bin "$POLY_INT" | rev)
            ;;
        h)
            POLY_HEX="${OPTARG}"
            ;;
        f)                      # Forward / Normal preset
            IMPLICIT_ONE=
            IMPLICIT_MONIC=1
            ASCENDING=false
            ;;
        r)                      # Reverse preset
            IMPLICIT_ONE=
            IMPLICIT_MONIC=1
            ASCENDING=true
            ;;
        k)                      # Koopman preset
            IMPLICIT_ONE=1
            IMPLICIT_MONIC=
            ASCENDING=false
            ;;
        c)                      # Reciprocal preset
            IMPLICIT_ONE=
            IMPLICIT_MONIC=1
            ASCENDING=false
            ;;
        v)                      # Reverse reciprocal preset
            IMPLICIT_ONE=
            IMPLICIT_MONIC=1
            ASCENDING=true
            ;;
        a)
            ASCENDING=true
            ;;
        d)
            ASCENDING=false
            ;;
        n)
            # Use this to determine length of polynomial when it can't
            # be inferred:
            #   Ascending  with implicit x^0, or
            #   Descending with implicit x^n.
            DEGREE="${OPTARG}"
            ;;
        o)
            IMPLICIT_ONE=1
            ;;
        m)
            IMPLICIT_MONIC=1
            ;;
        l)
            FWD="left"
            REV="right"
            ;;
        u)
            usage $0
            exit
            ;;
    esac
done


# Determine the explicit ascending binary representation of the
# polynomial from the command line arguments.
if [ -n "$POLY_BIN" ] ; then
    # We already have the explicit representation.
    POLY_HEX=
else
    # Convert the hexadecimal representation into an explicit
    # ascending binary representation.

    declare -i POLY_INT="${POLY_HEX}"
    if   "$ASCENDING" && [ -n "$IMPLICIT_ONE" ] ||
       ! "$ASCENDING" && [ -n "$IMPLICIT_MONIC" ]; then
        # Can't infer polynomial degree, so we need it from the user.

        if [ -z "$DEGREE" ] ; then
            >&2 echo "Can't infer polynomial degree. Please provide '-n degree' flag."
            exit 1
        else
            # Use DEGREE to add all implied bits to the polynomial.
            if "$ASCENDING" ; then
                if [ -n "$IMPLICIT_MONIC" ] ; then
                    ((POLY_INT <<= 1))
                    ((POLY_INT  |= 1))
                    IMPLICIT_MONIC=
                fi
                IMPLICIT_ONE=   # This term will be explicit soon.
            else
                if [ -n "$IMPLICIT_ONE" ] ; then
                    ((POLY_INT <<= 1))
                    ((POLY_INT  |= 1))
                    IMPLICIT_MONIC=
                fi
                IMPLICIT_MONIC= # This term will be explicit soon.
            fi
            ((POLY_INT |= 1<<"$DEGREE"))
        fi
    fi

    POLY_BIN=$(bin "${POLY_INT}")

    if ! $ASCENDING ; then
        POLY_BIN=$(echo "${POLY_BIN}" | rev)
    fi
    POLY_BIN="${IMPLICIT_ONE}${POLY_BIN}${IMPLICIT_MONIC}"

fi

# Make sure we have a polynomial of at least degree 1.
if (("${#POLY_BIN}" < 2)) ; then
    >&2 echo "Error: Supplied polynomial too short."
    exit 1
fi


# Pretty print polynomial.
POLY="x$(superscript 0)"  # or POLY="1", if you prefer
for i in $(seq 1 $(("${#POLY_BIN}" - 1))) ; do
    BIT="${POLY_BIN:$i:1}"
    if [ "$BIT" -eq 1 ] ; then
        POLY+=" + x$(superscript $i)"
    fi
done
echo "# ${POLY_HEX:+$POLY_HEX -> }$POLY_BIN -> $POLY"

# bit, term
flipflop () {
    echo "arrow \"\" \"$2\" big big"
    echo "box \"$1\" big big"
}

# Pikchr label
tap () {
    echo "arrow"
    echo "$1: circle \"+\" big big"
}

# Generate Pikchr diagram.
echo "boxwid = 0.5in; boxht = 0.5in;"

# Shift register and XOR taps
echo "# Shift register and XOR taps"
echo "$FWD"
echo -n "Start: "
flipflop "1" "x$(superscript 0)"

POLY_DEGREE=$(("${#POLY_BIN}" - 1))
for i in $(seq 1 $(("$POLY_DEGREE" - 1))) ; do
    BIT="${POLY_BIN:$i:1}"
    if [ "$BIT" -eq 1 ] ; then
        TAP_LABEL="Tap${i}"
        TAPS+="$TAP_LABEL "
        tap "$TAP_LABEL"
    fi
    flipflop "$BIT" "x$(superscript $i)"
done

# Input
echo "# Input"
echo "arrow \"\" \"x$(superscript ${POLY_DEGREE})\" big big"
echo "Input: circle \"+\" big big"
echo "arrow <- from Input.s down"
echo "line $REV \"Input\" big big \"\""

# Feedback network
echo "# Feedback network"
echo "FB: line from Input.n up \\"
echo "    then $REV until even with Start.start \\"
echo "    then to Start.start"

for TAP in ${TAPS} ; do
    echo "arrow <- from ${TAP}.n up until even with FB.n; dot"
done

Here's a Makefile that generates diagrams for all the example polynomial encodings listed on Wikipedia: 

TARGETS=normal.svg reverse.svg koopman.svg recip.svg revrecip.svg \
        parity.svg parity2.svg

all: $(TARGETS) diagrams.html

clean:
        rm -f $(TARGETS) $(TARGETS:.svg=.pikchr) diagrams.html

normal.pikchr:
        ./crc_diagram.sh -h 0x1021 -f -n 16 > $@

reverse.pikchr:
        ./crc_diagram.sh -h 0x8408 -r > $@

koopman.pikchr:
        ./crc_diagram.sh -h 0x8810 -k > $@

recip.pikchr:
        ./crc_diagram.sh -h 0x0811 -c -n 16 > $@

revrecip.pikchr:
        ./crc_diagram.sh -h 0x8810 -v > $@

parity.pikchr:
        ./crc_diagram.sh -p 0,1 > $@

parity2.pikchr:
        ./crc_diagram.sh -o -m -n 1 > $@

%.svg: %.pikchr
        pikchr --svg-only $^ > $@

diagrams.html: $(TARGETS)
        ./diagrams.sh $(TARGETS) > $@

It's fun that the script works with the "degenerate" case of a parity check circuit (polynomial \(1 + x\)), where you can tell the script that both the \(1\) and \(x\) are implicit terms in a polynomial of degree 1 and it will do the right thing.

parity.svg

Figure 2: Hex poly 0x11. Click to see source.

The script pretty prints the mathematical expression for the polynomial in the Pikchr output so that you can check that the hex constant has been interpreted correctly. It's also possible to pass the script the polynomial directly, with the -p flag followed by a comma separated list of the powers of each term in the polynomial in any order you please.

More examples can be found in diagrams.html. All the code is in crc_diagrams.tar.gz.

Philip Koopman's CRC polynomial zoo

I must mention Philip Koopman's wonderful CRC Polynomial Zoo, which lists many different CRC generator polynomials by their minimum Hamming Distance for different input message lengths. The Notes page describes the polynomial formats used there. For example, one listing shows:

(0xe7; 0x1cf) <=> (0xf3; 0x1e7)

In the notation used in this post, those encodings are from left to right:

  • Koopman: descending, implicit 1
  • Descending, explicit 1
  • Reverse: ascending, implicit monic (\(x^n\))
  • Descending, explicit monic (\(x^n\))

Koopman's format is neat because the degree of the polynomial can be inferred from the hex constant. It can also be inferred from the "Reverse" format, but not from the "Normal" format. The script will warn you if the degree can't be inferred and ask you to provide the -n degree flag.

Update: Falstad circuit simulation

Here's an interactive version of one of these diagrams, manually drawn using the excellent Falstad circuit simulator:

crc_0x8c_reverse_falstad_light.svg

You can upload this text file into the Falstad simulator to try it yourself.

© Copyright 2024, Remington Furman

blog@remcycles.net

@remcycles@subdued.social