Cyclic redundancy check (CRC)

Overview

A cyclic redundancy check is a checksum computed over a message's bytes and sent along with it. The receiver recomputes it and compares. The paper describes its CRC as a way to confirm that a message was not changed in transit and that sender and receiver hold the same message [arxiv:1906.10641 §II.C.1]. Only one source in this wiki covers CRC so far, the MAVLink survey, so every statement below comes from that paper's description of its own checksum.

Variants

CRC-16 with a per-message seed (MAVLink 1.0 and 2.0)

The checksum is a 16-bit CRC named by the paper as the ITU X.25 / SAE AS-4 hash 1906.10641 §II.C.1. It is computed over the frame's bytes after the start byte, which the paper says is 6+n+1 bytes, where n is the payload length. The last of these bytes is a seed, which the paper describes as a per-message value 1906.10641 §II.C.1. The two checksum bytes, CKA and CKB, are placed at the end of the frame 1906.10641 tab. II. MAVLink 2.0 keeps a checksum that the paper calls similar to the 1.0 one 1906.10641 §II.C.2. Card: MAVLink in a Nutshell: A Survey.

The seed table is not in the paper. An implementation therefore needs the protocol specification it targets to get the seed for each message ID 1906.10641 §II.C.1.

When to use which

The wiki has only one source, so the table compares the situations that the MAVLink paper addresses, not CRC variants against each other.

Implementation sketch

Checksum test for one MAVLink 1.0 frame. The seed table is an input because the paper does not give it.

# Check one MAVLink 1.0 frame's checksum  [arxiv:1906.10641 §II.C.1]
# Input:  frame (bytes, start byte first), seed_table (msg_id -> seed)
# Output: True if the frame's checksum matches

def checksum_ok(frame, seed_table):
    # CRC covers the bytes after the start byte, up to the payload end
    # [arxiv:1906.10641 §II.C.1]; the paper's byte count is 6+n+1
    body = frame[1:-2]
    msg_id = frame[5]
    # The seed is the per-message value appended after the body
    # [arxiv:1906.10641 §II.C.1]; the paper does not list the table
    seed = seed_table[msg_id]
    crc = crc16_x25(body + bytes([seed]))
    # Compare with CKA and CKB  [arxiv:1906.10641 tab. II]
    # Byte order of the two checksum bytes is not stated
    return crc == read_u16(frame[-2:])

Contradictions

• Byte count. The paper gives the CRC input as 6+n+1 bytes after the start byte 1906.10641 §II.C.1. Its own field list gives five header bytes after the start byte (length, sequence, system, component, message ID), which makes the input 5+n+1 bytes. The paper does not resolve this, so check it against the specification or against recorded traffic.
• Does signing cover the checksum? One part of the paper lists the CRC as an input to the signature 1906.10641 §IV.B.1, and a table lists it too 1906.10641 tab. V. The description of the signature block itself lists only the message, timestamp and key [arxiv:1906.10641 §II.C.2]. The paper does not give the exact input order, so an implementation cannot take it from the paper alone.
• Checksum byte order. The paper says the signing of the checksum bytes runs from least significant bit to most significant bit [arxiv:1906.10641 tab. II], without saying what that means for the 16-bit value.

Papers

• MAVLink in a Nutshell: A Survey: describes the MAVLink 1.0 and 2.0 checksum (CRC-16 with a per-message seed) and states how it differs from the optional packet signature.