Project 6: The Ship Tracker (AIS Decoder)

Decode AIS messages from VHF maritime channels to recover vessel identity and position.

Quick Reference

Attribute Value
Difficulty Expert
Time Estimate 3-4 weeks
Main Programming Language Python (Alternatives: C, Rust)
Alternative Programming Languages C++
Coolness Level Very High
Business Potential Medium-High (maritime monitoring)
Prerequisites FM demod, filters, bit parsing
Key Topics GMSK demod, NRZI, HDLC framing, CRC

1. Learning Objectives

By completing this project, you will:

  1. Demodulate GMSK AIS signals into a clean bitstream.
  2. Recover symbol timing for 9.6 kbps AIS.
  3. Implement NRZI decoding and bit de-stuffing.
  4. Detect HDLC frames and validate CRC.
  5. Parse AIS message types and extract vessel data.

2. All Theory Needed (Per-Concept Breakdown)

2.1 GMSK Demodulation and Symbol Timing Recovery

Fundamentals

AIS uses Gaussian Minimum Shift Keying (GMSK) at 9.6 kbps on two VHF channels (161.975 and 162.025 MHz). GMSK is a constant-envelope modulation similar to FM, where data is encoded as smooth phase transitions. This means you can demodulate AIS using an FM discriminator to get a baseband signal, then recover bits by slicing at the correct symbol timing. Because AIS is narrowband, you must filter to about 12.5 kHz around the channel before demod.

Deep Dive into the Concept

GMSK can be viewed as FSK filtered by a Gaussian filter to limit bandwidth. The “BT” product (bandwidth-time) defines how smooth the transitions are. AIS uses BT=0.4. The smoother the transitions, the smaller the bandwidth, but the harder it is to recover symbols in noise. A standard FM discriminator yields a baseband signal where positive voltage corresponds to a phase increasing, and negative voltage corresponds to decreasing. This baseband is not a clean square wave; it is a smooth waveform. To decode it, you need to sample at the correct time and apply a slicer.

Symbol timing recovery is crucial. At 9.6 kbps, each symbol is about 104 microseconds. If you sample too early or too late, you get errors. A simple approach is to oversample (e.g., 96 kHz or 192 kHz) and use a zero-crossing or early-late gate to align sampling. A more robust method is a Gardner or Mueller-Muller timing recovery loop, which uses timing error estimates to adjust the sampling phase. For this project, a simpler early-late method may be sufficient if signal strength is good.

AIS signals are transmitted in bursts, and the channel is shared. You may receive overlapping signals or bursts with weak SNR. A good demodulator applies a narrow filter before the discriminator to improve SNR and reduce interference. Additionally, you should implement automatic gain control or normalization to stabilize the discriminator output amplitude.

How this fits on projects

  • You will implement GMSK demod in §5.10.
  • Timing recovery concepts are reused in P08 (POCSAG) and P09 (GSM).

Definitions & key terms

  • GMSK: Gaussian Minimum Shift Keying.
  • BT product: Bandwidth-time product controlling Gaussian filter.
  • FM discriminator: Converts frequency deviation to voltage.
  • Symbol timing: Correct sample phase for bit decisions.

Mental model diagram (ASCII)

RF -> LPF -> FM demod -> Smooth baseband -> Timing recovery -> Bit slicer

How it works (step-by-step, with invariants and failure modes)

  1. Tune and filter around AIS channel.
  2. FM demodulate to baseband.
  3. Normalize amplitude.
  4. Recover symbol timing.
  5. Slice to bits.

Failure modes:

  • Incorrect timing -> random bits.
  • Wide filter -> adjacent channel interference.

Minimal concrete example

# discriminator output to bits
samples = fm_demod
bits = (samples[phase::samples_per_symbol] > 0).astype(int)

Common misconceptions

  • “GMSK requires a special demod.” FM discriminator is sufficient.
  • “Timing doesn’t matter if you oversample.” It still matters.

Check-your-understanding questions

  1. Why is GMSK used instead of FSK?
  2. What does BT control?
  3. Why is symbol timing recovery needed?

Check-your-understanding answers

  1. It reduces spectral splatter and fits narrowband channels.
  2. The smoothness of transitions and bandwidth.
  3. Correct sampling phase is required for bit decisions.

Real-world applications

  • Maritime AIS tracking and collision avoidance.
  • Narrowband data links.

Where you’ll apply it

  • This project: §3.4, §5.10.
  • Also used in: P09 GSM.

References

  • “Practical SDR” Ch. 9
  • Rice, “Digital Communications” Ch. 7

Key insights

GMSK demod is FM demod plus careful timing recovery.

Summary

You learned how to demodulate GMSK and recover symbols for AIS.

Homework/Exercises to practice the concept

  1. Generate synthetic GMSK and demod with FM discriminator.
  2. Offset sampling phase and measure bit errors.
  3. Compare narrow vs wide filters for AIS.

Solutions to the homework/exercises

  1. Demod output should show smooth transitions.
  2. Offsets increase error rate.
  3. Narrow filter improves SNR and decoding.

2.2 NRZI, HDLC Framing, Bit Stuffing, and CRC

Fundamentals

AIS frames use HDLC-like framing with NRZI encoding and bit stuffing. NRZI encodes a 1 as “no transition” and a 0 as “transition” (or vice versa depending on convention). To recover bits, you must detect transitions. Bit stuffing ensures that the HDLC flag pattern (0x7E = 01111110) does not occur inside the data. After five consecutive ones, a zero is inserted and must be removed on decode. CRC-16 validates the frame.

Deep Dive into the Concept

HDLC framing starts and ends with the flag 0x7E. This provides a recognizable boundary. NRZI encoding helps with clock recovery because it guarantees transitions when there are zeros. However, if long runs of ones occur, there would be no transitions and timing recovery would drift. To prevent this, the transmitter inserts a zero after five consecutive ones. The receiver must detect these stuffed zeros and remove them. If you fail to remove them, the decoded payload will be shifted and CRC will fail.

After de-stuffing, you compute CRC-16 (CCITT) over the payload and compare with the received CRC. AIS uses a specific polynomial (0x1021). Bit ordering is critical; AIS bits are typically transmitted MSB-first. You must confirm your bit order when computing CRC. One reliable approach is to validate against known AIS frames from sample captures.

AIS messages include a 6-bit message type field at the start. Different message types encode different data (position, static data, safety messages). For a first decoder, implement message types 1, 2, and 3 (position reports). These contain MMSI, latitude, longitude, speed, and heading. Some fields are signed and require two’s complement decoding.

How this fits on projects

  • You will implement de-stuffing and CRC in §5.10.
  • Similar framing and CRC appear in P04 (ADS-B) and P08 (POCSAG BCH).

Definitions & key terms

  • NRZI: Non-Return-to-Zero Inverted encoding.
  • Bit stuffing: Inserting bits to prevent accidental flag patterns.
  • HDLC flag: 0x7E frame delimiter.
  • CRC-16: 16-bit cyclic redundancy check.

Mental model diagram (ASCII)

Bits -> NRZI decode -> De-stuff -> Find 0x7E -> CRC -> Parse AIS

How it works (step-by-step, with invariants and failure modes)

  1. Decode NRZI transitions into bits.
  2. Remove stuffed zeros after five 1s.
  3. Detect HDLC flag boundaries.
  4. Compute CRC-16 and validate.
  5. Parse AIS payload.

Failure modes:

  • Wrong NRZI convention -> scrambled data.
  • Missing de-stuffing -> CRC fails.

Minimal concrete example

# NRZI decode
bits = []
prev = samples[0]
for s in samples[1:]:
    bits.append(0 if s != prev else 1)
    prev = s

Common misconceptions

  • “HDLC flag is always byte-aligned.” It is bit-aligned.
  • “CRC is optional.” It is essential for reliability.

Check-your-understanding questions

  1. Why is bit stuffing needed in HDLC?
  2. What does NRZI provide?
  3. What happens if you remove the wrong stuffed bits?

Check-your-understanding answers

  1. To prevent accidental flag sequences in data.
  2. More transitions for clock recovery.
  3. Payload becomes misaligned and CRC fails.

Real-world applications

  • AIS and maritime communications.
  • Many packet radio systems using HDLC framing.

Where you’ll apply it

  • This project: §3.7, §5.10.
  • Also used in: P08 POCSAG.

References

  • ITU-R M.1371 AIS specification
  • Rice, “Digital Communications” Ch. 8

Key insights

Reliable AIS decoding is as much about framing and CRC as it is about demodulation.

Summary

You learned how to undo NRZI, remove stuffed bits, and validate frames with CRC.

Homework/Exercises to practice the concept

  1. Encode a sample payload with NRZI and bit stuffing, then decode it.
  2. Test CRC-16 on known AIS frames.
  3. Decode AIS type 1 messages and verify MMSI.

Solutions to the homework/exercises

  1. Decoding should recover the original payload.
  2. CRC should match known examples.
  3. MMSI should match published values.

3. Project Specification

3.1 What You Will Build

An AIS decoder that tunes to 161.975/162.025 MHz, demodulates GMSK, and outputs decoded vessel data.

3.2 Functional Requirements

  1. Tune to AIS channels and filter to 12.5 kHz bandwidth.
  2. FM demodulate and recover symbol timing.
  3. NRZI decode and de-stuff bits.
  4. Detect HDLC frames and validate CRC-16.
  5. Parse AIS message types 1/2/3 and output MMSI, position, speed.

3.3 Non-Functional Requirements

  • Performance: Decode at least one valid message per minute on live data.
  • Reliability: CRC reject rate < 5% for strong signals.
  • Usability: Clear output and options for channel A/B.

3.4 Example Usage / Output

$ python ais_decoder.py --freq 162.025e6 --fs 2.4e6
[AIS] MMSI=235123456 LAT=51.50 LON=0.10 SOG=12.3

3.5 Data Formats / Schemas / Protocols

  • Output JSON lines: 
    {"mmsi":235123456,"lat":51.50,"lon":0.10,"sog":12.3}

3.6 Edge Cases

  • Weak signals causing timing errors.
  • Overlapping AIS messages.
  • MMSI or position fields invalid.

3.7 Real World Outcome

Live map-ready vessel reports from local AIS transmissions.

3.7.1 How to Run (Copy/Paste)

python ais_decoder.py --input ais.iq --fs 2400000 --freq 162.025e6

3.7.2 Golden Path Demo (Deterministic)

Use a known AIS capture. Expected: valid CRC, correct MMSI and position.

3.7.3 CLI Transcript (Exact)

$ python ais_decoder.py --input test_ais.iq --fs 2400000
[AIS] MMSI=123456789 LAT=37.774 LON=-122.419 SOG=10.1

3.7.4 Failure Demo

$ python ais_decoder.py --input noisy_ais.iq --fs 2400000
[WARN] No valid AIS frames detected
[EXIT] code=3

4. Solution Architecture

4.1 High-Level Design

IQ -> Tune/LPF -> FM demod -> Timing -> NRZI -> De-stuff -> CRC -> Parse

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————| | Channel Filter | Isolate AIS channel | FIR width | | Demod | FM discriminator | Sample rate | | Timing | Symbol sync | Early-late vs Gardner | | Parser | AIS fields | Message type focus |

4.3 Data Structures (No Full Code)

class AisMessage:
    mmsi: int
    lat: float
    lon: float

4.4 Algorithm Overview

Key Algorithm: AIS Decode Chain

  1. Demodulate to baseband.
  2. Recover timing and slice bits.
  3. NRZI decode and de-stuff.
  4. Detect flags and validate CRC.
  5. Parse AIS fields.

Complexity Analysis:

  • Time: O(N)
  • Space: O(N) buffer

5. Implementation Guide

5.1 Development Environment Setup

pip install numpy scipy

5.2 Project Structure

ais/
├── src/
│   ├── main.py
│   ├── demod.py
│   ├── timing.py
│   ├── framing.py
│   └── parser.py
└── tests/

5.3 The Core Question You’re Answering

“How do you decode GMSK bursts and recover framed messages from ships?”

5.4 Concepts You Must Understand First

  1. GMSK demod & timing (§2.1)
  2. NRZI + HDLC framing (§2.2)

5.5 Questions to Guide Your Design

  1. How will you detect channel A vs B?
  2. What timing recovery method is robust enough for AIS?
  3. How will you validate MMSI and position fields?

5.6 Thinking Exercise

Write out the HDLC flag in bits and show how bit stuffing prevents false flags.

5.7 The Interview Questions They’ll Ask

  1. Why does AIS use two channels?
  2. What does NRZI provide?
  3. What is MMSI?

5.8 Hints in Layers

  1. Use FM discriminator to get baseband.
  2. Recover timing via zero-crossings.
  3. Detect 0x7E and de-stuff.
  4. Verify CRC and parse type 1 messages.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | GMSK | Rice | Ch. 7 | | Framing | Rice | Ch. 8 |

5.10 Implementation Phases

Phase 1: Foundation (5-7 days)

Goals: Demodulate and recover bits. Checkpoint: Recognize HDLC flags in a known capture.

Phase 2: Core Functionality (7-10 days)

Goals: CRC validation and parsing. Checkpoint: Decode MMSI and position for known frame.

Phase 3: Polish & Edge Cases (5-7 days)

Goals: Robust decoding on live data. Checkpoint: Steady output for 10+ minutes.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | Timing recovery | Simple vs Gardner | Simple first | Easier to implement | | Output format | Text vs JSON | JSON lines | Map integration |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———|———|———-| | Unit | NRZI and de-stuff | Synthetic frames | | Integration | End-to-end | Recorded AIS IQ | | Edge | Noise bursts | CRC rejection |

6.2 Critical Test Cases

  1. Known AIS frame with valid CRC.
  2. Stuffed-bit sequence decoding.
  3. Weak signal should not produce false positives.

6.3 Test Data

Public AIS IQ samples with known MMSI.

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |———|———|———-| | Wrong NRZI polarity | CRC failures | Swap transition logic | | Timing drift | Random bit errors | Add clock recovery | | No filter | Adjacent channel interference | Narrow LPF |

7.2 Debugging Strategies

  • Plot baseband eye diagram.
  • Compare decoded bits to known frames.

7.3 Performance Traps

  • Using heavy FIR at full rate without decimation.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Decode message type 5 (static data).

8.2 Intermediate Extensions

  • Dual-channel AIS decoding (A and B).

8.3 Advanced Extensions

  • Build a live vessel map.

9. Real-World Connections

9.1 Industry Applications

  • Maritime traffic monitoring.
  • Port logistics and safety systems.
  • aisdecoder libraries in various languages.
  • GNU Radio AIS blocks.

9.3 Interview Relevance

  • Demonstrates framing, CRC, and timing recovery.

10. Resources

10.1 Essential Reading

  • ITU-R M.1371 AIS spec
  • Rice, “Digital Communications” Ch. 7-8

10.2 Video Resources

  • AIS decoding tutorials (SDR community)

10.3 Tools & Documentation

  • aisdecoder (reference implementations)

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain GMSK and NRZI.
  • I can compute CRC-16 for AIS frames.

11.2 Implementation

  • I decode AIS position reports reliably.
  • Output is parseable by mapping tools.

11.3 Growth

  • I can extend decoding to more AIS message types.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Decode AIS frames with valid CRC.
  • Output MMSI and position.

Full Completion:

  • Robust decoding on live channels.

Excellence (Going Above & Beyond):

  • Dual-channel decoding and live map visualization.