# 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:

- Normal
- Reverse
- Koopman

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:

- Reciprocal
- Reverse 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.

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.

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:

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