743  Error Detection: CRC and Checksums

NoteLearning Objectives

By the end of this section, you will be able to:

  • Understand error detection fundamentals: Explain why IoT networks need mechanisms to detect data corruption
  • Compare CRC and checksums: Differentiate between simple checksums and CRC for error detection capability
  • Calculate CRC values: Understand the polynomial division process behind CRC computation
  • Identify error detection limitations: Recognize what types of errors each mechanism can and cannot detect
  • Choose appropriate algorithms: Select the right error detection method based on reliability requirements and resource constraints

743.1 Prerequisites

Before diving into this chapter, you should be familiar with:

  • Transport Fundamentals: Understanding TCP vs UDP trade-offs and basic acknowledgment concepts provides essential context for error detection
  • Reliability Overview: The parent chapter introducing all five pillars of IoT reliability
  • Binary and Hexadecimal: Familiarity with bitwise operations is essential for understanding checksum calculations
ImportantWhy Error Detection Matters

Wireless channels are inherently noisy. Electromagnetic interference from motors, microwaves, and other devices can flip bits during transmission. Signal fading in multipath environments corrupts data randomly. Without error detection, your temperature sensor might report 125C instead of 25C due to a single bit flip - and your system would have no way to know the data is wrong.

743.2 Error Detection Fundamentals

Time: ~15 min | Level: Intermediate | Unit: P07.REL.U02

Error detection identifies when data has been corrupted during transmission. The sender computes a mathematical function over the data and appends the result (checksum or CRC). The receiver performs the same computation - if the results differ, corruption occurred.

743.2.1 The Error Detection Process

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor':'#2C3E50','primaryTextColor':'#fff','primaryBorderColor':'#16A085','lineColor':'#16A085','secondaryColor':'#E67E22'}}}%%
sequenceDiagram
    participant S as Sender
    participant C as Channel
    participant R as Receiver

    Note over S: Original Data: "HELLO"

    S->>S: Calculate check value<br/>from data bytes

    S->>C: Send: Data + Check Value

    Note over C: Transmission<br/>(may introduce errors)

    C->>R: Receive data

    R->>R: Recalculate check value<br/>from received data

    alt Check values match
        R-->>R: Data accepted as valid
    else Check values differ
        R-->>S: Request retransmission
    end

Figure 743.1: Error detection workflow: sender calculates check value, channel may corrupt data, receiver verifies by recalculating.

743.2.2 Types of Transmission Errors

Error Type Description Example Detection Difficulty
Single bit One bit flipped 0x48 becomes 0x49 Easy
Burst error Multiple consecutive bits flipped 0x4845 becomes 0x3912 Moderate
Byte swap Two bytes exchange positions 0x1234 becomes 0x3412 Hard for checksums
Insertion Extra byte added β€œAB” becomes β€œACB” Moderate
Deletion Byte removed β€œABC” becomes β€œAC” Moderate

743.3 Simple Checksum Algorithms

The simplest approach is to sum all bytes in the message. Several variants exist with different trade-offs.

743.3.1 Sum-of-Bytes Checksum

uint8_t calculateChecksum(const uint8_t* data, size_t length) {
    uint8_t sum = 0;
    for (size_t i = 0; i < length; i++) {
        sum += data[i];
    }
    return sum;
}

Advantages: - Extremely fast (single addition per byte) - Minimal code size - Works on any processor

Disadvantages: - Cannot detect byte reordering (addition is commutative) - Poor burst error detection - Weak against certain error patterns

743.3.2 Internet Checksum (One’s Complement)

Used in IP, TCP, and UDP headers, this algorithm treats data as 16-bit words and performs one’s complement addition:

uint16_t internetChecksum(const uint16_t* data, size_t wordCount) {
    uint32_t sum = 0;

    for (size_t i = 0; i < wordCount; i++) {
        sum += data[i];
    }

    // Fold 32-bit sum to 16 bits (add carry bits)
    while (sum >> 16) {
        sum = (sum & 0xFFFF) + (sum >> 16);
    }

    return ~sum;  // One's complement
}

Key property: The checksum of the data plus its checksum equals 0xFFFF (all ones), making verification simple.

WarningChecksum Weakness: Byte Swap

Simple checksums cannot detect when bytes are transposed:

Original:  0x12 + 0x34 = 0x46
Swapped:   0x34 + 0x12 = 0x46  (same checksum!)

This is why TCP/IP uses checksums for headers (where errors are unlikely) but CRC for link-layer frames (where bit errors are common).

743.4 Cyclic Redundancy Check (CRC)

CRC provides much stronger error detection by treating the data as a polynomial and dividing by a fixed generator polynomial. The remainder becomes the CRC value.

743.4.1 How CRC Works Conceptually

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor':'#2C3E50','primaryTextColor':'#fff','primaryBorderColor':'#16A085','lineColor':'#16A085','secondaryColor':'#E67E22'}}}%%
flowchart TB
    subgraph Input["Data as Polynomial"]
        DATA["Message: 11010011<br/>= x^7 + x^6 + x^4 + x + 1"]
    end

    subgraph Process["Division Process"]
        SHIFT["Append n zeros<br/>(n = polynomial degree)"]
        DIV["XOR-divide by<br/>generator polynomial"]
        REM["Remainder = CRC"]
    end

    subgraph Poly["Generator Polynomial"]
        GEN["CRC-8: x^8 + x^2 + x + 1<br/>= 0x107 (binary: 100000111)"]
    end

    subgraph Output["Result"]
        CRC["CRC value appended<br/>to message"]
    end

    DATA --> SHIFT
    SHIFT --> DIV
    GEN --> DIV
    DIV --> REM
    REM --> CRC

    style Input fill:#2C3E50,stroke:#16A085,color:#fff
    style Process fill:#16A085,stroke:#2C3E50,color:#fff
    style Poly fill:#E67E22,stroke:#2C3E50,color:#fff
    style Output fill:#2C3E50,stroke:#16A085,color:#fff

Figure 743.2: CRC calculation process: message treated as polynomial, divided by generator polynomial, remainder is the CRC.

743.4.2 CRC-16 Implementation

#define CRC16_POLYNOMIAL  0x1021  // CRC-CCITT
#define CRC16_INITIAL     0xFFFF

uint16_t calculateCRC16(const uint8_t* data, size_t length) {
    uint16_t crc = CRC16_INITIAL;

    for (size_t i = 0; i < length; i++) {
        crc ^= ((uint16_t)data[i] << 8);

        for (int bit = 0; bit < 8; bit++) {
            if (crc & 0x8000) {
                crc = (crc << 1) ^ CRC16_POLYNOMIAL;
            } else {
                crc = crc << 1;
            }
        }
    }

    return crc;
}

743.4.3 Common CRC Polynomials

CRC Type Polynomial Width Used In
CRC-8 0x07 8 bits I2C, SMBus
CRC-16-CCITT 0x1021 16 bits Bluetooth, USB, X.25
CRC-16-IBM 0x8005 16 bits Modbus, USB
CRC-32 0x04C11DB7 32 bits Ethernet, ZIP, PNG

743.5 CRC vs Checksum Comparison

Feature Simple Checksum CRC-16 CRC-32
Computation Sum of bytes Polynomial division Polynomial division
Size 1-2 bytes 2 bytes 4 bytes
Burst Error Detection Poor Good (16+ bits) Excellent (32+ bits)
Single Bit Errors 100% 100% 100%
Two Bit Errors ~50% 100% 100%
Byte Swap Detection 0% 100% 100%
CPU Cycles (8-bit MCU) ~2 per byte ~40 per byte ~80 per byte
Code Size ~20 bytes ~100 bytes ~200 bytes

743.5.1 When to Use Each

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor':'#2C3E50','primaryTextColor':'#fff','primaryBorderColor':'#16A085','lineColor':'#16A085','secondaryColor':'#E67E22'}}}%%
flowchart TD
    START["Need Error Detection"] --> Q1{"Critical data?<br/>(safety, financial)"}

    Q1 -->|Yes| CRC32["Use CRC-32"]
    Q1 -->|No| Q2{"Noisy channel?<br/>(wireless, long cables)"}

    Q2 -->|Yes| CRC16["Use CRC-16"]
    Q2 -->|No| Q3{"Resource constrained?<br/>(tiny MCU, battery)"}

    Q3 -->|Yes| CHECKSUM["Use Simple Checksum"]
    Q3 -->|No| CRC16B["Use CRC-16"]

    style CRC32 fill:#E67E22,stroke:#2C3E50,color:#fff
    style CRC16 fill:#16A085,stroke:#2C3E50,color:#fff
    style CRC16B fill:#16A085,stroke:#2C3E50,color:#fff
    style CHECKSUM fill:#7F8C8D,stroke:#2C3E50,color:#fff

Figure 743.3: Decision tree for selecting error detection algorithm based on requirements.

743.6 CRC Error Detection Capabilities

743.6.1 What CRC Detects

CRC is guaranteed to detect:

  1. All single-bit errors - Any single bit flip is caught
  2. All double-bit errors - Any two bit flips anywhere in the message
  3. All odd-number bit errors - 1, 3, 5, … bit flips
  4. All burst errors shorter than CRC width - CRC-16 catches all bursts up to 16 bits

743.6.2 Undetectable Errors

No error detection is perfect. CRC may miss:

  • Burst errors longer than CRC width - Detection probability is 1 - 2^(-n) for n-bit CRC
  • Specific polynomial multiples - Errors that produce valid remainders
TipPractical Reliability

For CRC-32 with random errors: - Probability of undetected error = 2^(-32) = 0.00000000023% - For 1 billion messages, expect ~0.2 undetected corruptions

This is why CRC is combined with other mechanisms (sequence numbers, ACKs) for critical applications.

743.7 Hardware CRC Acceleration

Many IoT microcontrollers include hardware CRC units that compute CRC in a single clock cycle per byte:

// ESP32 hardware CRC example
#include "esp_rom_crc.h"

uint32_t fastCRC32(const uint8_t* data, size_t length) {
    // Hardware-accelerated CRC-32
    return esp_rom_crc32_le(0, data, length);
}

uint16_t fastCRC16(const uint8_t* data, size_t length) {
    // Hardware-accelerated CRC-16/CCITT
    return esp_rom_crc16_le(0, data, length);
}

743.7.1 Performance Comparison

Method Cycles per Byte 100-byte Message
Software CRC-32 ~80 8000 cycles
Hardware CRC-32 ~1 100 cycles
Software CRC-16 ~40 4000 cycles
Hardware CRC-16 ~1 100 cycles
TipBest Practice: Check Your MCU

Before implementing software CRC, check if your microcontroller has hardware support: - ESP32: Yes (ROM functions) - STM32: Yes (CRC peripheral) - nRF52: Yes (CRC peripheral) - ATmega328: No (software only)

743.8 Knowledge Check

Question: A simple sum-of-bytes checksum will FAIL to detect which type of error?

  1. Single bit flip in one byte
  2. Two bytes swapping positions
  3. All bits in one byte flipped
  4. Addition of an extra zero byte
Click for answer

Answer: B) Two bytes swapping positions

When two bytes swap positions (e.g., 0x12 0x34 becomes 0x34 0x12), the sum remains identical because addition is commutative. CRC detects this because polynomial division considers bit positions, not just values.

Question: CRC-16 is GUARANTEED to detect:

  1. All errors up to 16 bits anywhere in the message
  2. All burst errors up to 16 consecutive bits
  3. 50% of all possible error patterns
  4. Only single-bit errors
Click for answer

Answer: B) All burst errors up to 16 consecutive bits

CRC-n is guaranteed to detect all burst errors of n bits or fewer. For longer bursts, detection probability is very high but not 100%. CRC also detects all single-bit, double-bit, and odd-number bit errors.

Question: For a battery-powered sensor sending temperature readings over a noisy 433 MHz radio link, which error detection is most appropriate?

  1. No error detection (saves power)
  2. Simple 8-bit checksum
  3. CRC-16
  4. CRC-32
Click for answer

Answer: C) CRC-16

Noisy wireless channels require strong error detection (rules out A and B). CRC-16 provides excellent burst error detection suitable for radio links. CRC-32 is overkill for sensor data and wastes power - the 2 extra bytes per message add up over thousands of transmissions.

743.9 Summary

This chapter covered error detection mechanisms for IoT networks:

Key Concepts:

  • Checksums provide basic error detection with minimal overhead
  • CRC uses polynomial division for much stronger error detection
  • Burst errors are common in wireless channels - CRC handles them well
  • Hardware acceleration makes CRC nearly free on modern MCUs

Trade-offs:

Mechanism Overhead Detection Best For
8-bit checksum 1 byte Weak Resource-constrained, reliable channels
CRC-16 2 bytes Strong Typical IoT wireless
CRC-32 4 bytes Excellent Critical data, Ethernet

What is Next: The Retry Mechanisms and Sequence Numbers chapter covers how to recover from errors once detected.

NoteCross-Reference Links