Capturing and Decoding AIS with Gnu Radio, Universal Radio Hacker and Gnu Octave

Gary Schafer, September 2024

I was working on a post discussing the "gain" setting on SDRs when we had a day of really nice weather. Like, picture perfect weather. I grabbed the laptop, a RTL-SDR, a simple dipole antenna, and the wife, and hightailed it to Fort Smallwood Park, just south of Baltimore. It's at the mouth of where the Patapsco River feeds into the Chesapeake Bay. It's also southeast of the now-fallen Francis Scott Key Bridge.

The reason I went to the park with laptop, SDR and antenna was to capture some AIS signals. I've been thinking of looking at these signals for some time. You might be wondering, "Why? There are tons of programs that will let you automatically demod and decode such signals." True enough. But they don't explain how it works. I intend to correct that with this post.

Reference Material

Pretty much everything in this post came from the document "M.1371 : Technical characteristics for an automatic identification system using time division multiple access in the VHF maritime mobile frequency band", available on the ITU website.

Overview of AIS

AIS or "Automatic Identification System" is a ship-based transmission system that is similar to the ADS-B system in aircraft. It's intended to keep ships from essentially running into each other. The primary broadcasts occur on two frequencies, 161.975 MHz and 162.025 MHz.

Signal Characteristics

The basics of the transmission are:

• Modulation: 2FSK
• Encoding: NRZ-S
• Symbol (Baud) Rate: 9600 Hz
• Modulation Index: 0.5 (this is the reason it is called "minimum shift keying" or "MSK")
• Filtering: Gaussian, with BT = 0.3
• Multiplexing: TDMA
• Time Slot Duration: 26.67 msec. (NOTE: One minute (60 seconds) is divided into 2250 slots. Thus, one slot is 60 / 2250 = 26.67 msec)
• Framing:
• Ramp up: 8 bits
• Preamble: 24 bits
• Start flag: 8 bits
• Data: 168 bits (basic transmission)
• FCS: 16 bits
• End flag: 8 bits
• Buffer: 24 bits
• TOTAL: 256 bits (one slot or 26.67 msec x 9600 baud = 256)

The general steps for creation of the signal are:

1. Create the message according to the message type. A basic message will be 168 bits long.
2. Change the bitstream from MSB to LSB. This occurs on a byte (8 bit) boundary.
3. Calculate the FCS and append it to the data field.
4. Perform bit stuffing on the waveform. This ensures that no part of the data field will have any runs of 1s that will cause the receiver to mistake it for either the start or end flags.
5. Append the preamble, start flag and end flag.
6. Encode with NRZ-S.
7. Filter and modulate onto the carrier with 2FSK.

Collecting the Signals

I used my laptop, SDR and antenna setup on a picnic table at the park. Again, this was just southeast of Baltimore and is right at the intersection of the Patapsco River and the Chesapeake Bay.

For the collection, I used a simple Gnu Radio Companion flowgraph that captured raw IQ samples. I didn't want to process onsite. I wanted to collect now, process later. To that end, I used the flowgraph shown below.

Processing the Signals

There were three steps to processing the signals. The first was to filter the signals to just one channel. I used another Gnu Radio Companion flowgraph to do this. The second step was to use Universal Radio Hacker to demodulate and strip off the NRZ-S encoding. The last step was to use Gnu Octave to decode the bitstream.

Filtering with Gnu Radio Companion

I created another Gnu Radio Companion flowgraph to process the raw IQ captured at Fort Smallwood Park to create two files, one each for the two, primary RF channels used by AIS. One was for 161.975 MHz. The other was for 162.025 MHz. Note that I didn't use a Gaussian filter; rather just a simple windowed-sinc filter set to 12 kHz of bandwidth. The output sample rate was reduced to 48 kHz, and saved to another file.

Demodulating with Universal Radio Hacker

I used Universal Radio Hacker to demodulate the signal, remove the DC offset, then strip off the NRZ-S line encoding. I loaded the IQ file (consisting of complex 32-bit floating point samples at 48 kHz sample rate). I selected one of the stronger signals using the "Analog" signal view. The demodulation and removal of the DC bias was straightforward. I set the modulation to FSK, the number samples / symbol to 5 (48000 / 9600), and the error tolerance to 1. Using the "Demodulated" signal view, I adjusted the DC bias.

We need to talk about the demodulation for a moment. There are two aspects to this, and they are related. First, the modulation is not just FSK, but MSK, where the "M" means "minimum". This term refers to the fact that the deviation is the minimum required for the two tones (the upper frequency and lower frequency created by the frequency shift) to be "coherently orthogonal". (NOTE: That last bit comes from "Principles of Communications: Systems, Modulation and Noise", R.E. Ziemer & W.H. Tranter, Houghton-Mifflin, 1985). What this means is that it can also be demodulated similar to QPSK or OQPSK. URH doesn't provide a means to demodulate it this latter way (at least, not that I've found). Which means we have to use the FSK demodulator. This leads to the second issue. The signal is "Gaussian" filtered. A filtered FSK signal will have demodulated amplitudes that do not go all the way to their maximums or minimums. Look at the image above showing the demodulated waveform. The peaks do not reach their maximums or minimums when it is alternating "101" or "010". Frequency demodulating this type of waveform means that the DC offset has to be carefully managed; otherwise, bit errors occur. URH doesn't have a way to manage this on a burst-by-burst basis. So, I had to adjust the DC offset for each burst individually. Further, if you look at the code for any of the AIS programs, you'll most likely see a function, section or routine that tries to minimize the DC bias in the signal.

Overview of NRZ-S Encoding

So, after applying the FSK demodulator, this gets me to the raw bitstream. However, according to the specification:

The NRZI waveform is used for data encoding. The waveform is specified as giving a change in the level when a zero (0) is encountered in the bit stream.

Here's what that means. The concept of "bits" is an abstraction. Hardware doesn't know what a "bit" is. It only knows voltages and currents. A basic bitstream shows "bits" as an absolute amplitude, typically with a "1" as a high amplitude and a "0" as a low amplitude. This type of encoding is called "non-return to zero - level" or "NRZ-L".

An adaptation of this is to perform differential encoding. A differential encoding means that, rather than looking at the absolute levels, the critical part is the transitions, meaning when the bitstream transitions from a high amplitude to a low amplitude, or a low amplitude to a high amplitude. This leads to a version called "NRZ-M" or "non-return to zero - mark". This means that a "1" (1 = mark) is represented by a transition, while a "0" means no transition. The opposite version is "NRZ-S" or "non-return to zero - space". This means a "0" is represented by a transition, while a "1" is no transition.

But the standard says (literally) "NRZI". This means "non-return to zero - inverted". (NOTE: In Universal Radio Hacker, there's an option called "Non Return to Zero + Inverted". This is NOT the same as "NRZI".) What's NRZI, then? That's just a general way of saying "differential", but it doesn't say what a transition means (1 or 0). That's why the standard has to state which bit is sent in a transition. In this case, a "0" (zero). This means it is "non-return to zero - space"."

Which leads to a problem. Universal Radio Hacker doesn't have a setting for "NRZI" or "NRZ-S". Fortunately, it has the means to make it.

Making a NRZ-S Decoder in URH

From the "Analysis" window, the default "Decoding" is "Non Return to Zero (NRZ)", which is another way of saying "non return to zero - level". This means that, based on the amplitudes of the demodulated waveform, a high amplitude is a "1" and a low amplitude is a "0". Clicking on the "Decoding" option of "Non Return to Zero (NRZ)", it opens a dropdown menu. I selected the bottom option, the ellipsis (three periods in a row). This opens the "Decoding" window.

The NRZ-S is a differential encoding. We can apply this decoding by clicking-and-dragging the "Differential" option to the "Your Decoding" window. With "Differential", URH treats a transition (meaning a "01" or "10" combination in the raw bitstream) as a "1", while no transition ("00" or "11" in the original bitstream) as a "0". This would be a "NRZ-M" decoding. But this can be changed to a NRZ-S by then applying a "Invert" to the list. This means click-and-drag the "Invert" option to the "Your Decoding" List.

Finally, you can save this list of options by clicking on the "Save" button at the top of the window. I named it as "NRZ-S".

Closing the "Decoding" window, it's now possible to select the "NRZ-S" decoding option. This now makes it possible to see the preamble (the "01" bit sequence repeated 12 times) as well as the start flag (bit sequence "01111110").

Processing with Gnu Octave

At this point, I needed to program. If you haven't heard me say it before, I'll say it again: I'm a lousy programmer. In this case, my programming method of choice is Gnu Octave. I copied all of the bits between the start and end flags to a simple text file. I used the text editor to create the Gnu Octave script.

rawBits="00010010000010100001010
10110001000011011000000001000000
00101011100111000101111101100111
00011001100110111011010010001100
11111011010010111110101001100111
10110000000001100000100010001101
0101";

Bit Unstuffing

As I mentioned above, there's a "Start Flag". That consists of the bit sequence "01111110" (or 0x7e in hex). That tells the system "What comes after this is data." The data goes til it finds another bit sequence "01111110". This is the "End Flag". Everything in between is data. But this leads to a problem. What if this very string (01111110) is in the data? To prevent this, the transmitter does something called "bit stuffing". If it finds the sequence "011111", it adds a 0 right after, so the output bit sequence will be 0111110. Now the maximum run of 1s will be five within the data itself. The flags are now preserved as the only 6 1s in a row. But this messes with the data. The receiver has to remove these added 0s before reading the data.

Here's how I approached the problem of trying to find where bit stuffing occurred. Since the transmitter adds a 0 after a run of 5 1s, it makes sense to remove any 0s after 5 1s. I decided to use a basic correlation. The easiest way I found to do correlation was using a convolution. These two things are related. A convolution is a correlation with one of the signals reversed in time. But if the signal is the same whether its reversed or not, it doesn't really matter. ANYWAY, I used the sequence "0111110" for my search. The code was this:

% Take the string of 1s and 0s and convert them to numbers

for ii=1:length(rawBits);
    numBits(ii)=str2num(rawBits(ii));
endfor

% Remove zero stuffing. AIS uses modified HDLC which starts
% and ends with a 01111110 (0x7e). To ensure that the data
% does not accidentally display 6 1s in a row, it adds a 0
% (zero stuffing) after every 5 consecutive 1s. On the
% receive side, these have to be removed.
%
% This part of the script uses a pattern of 5 1s and a 0 to
% correlate where such string of 1s occur. It then uses their
% positions within the number array to remove the 0s
% immediately following the string of 1s.

% Convolve the bitstream with the array 0111110. This is the
% same as correlating with 0111110.

peakBits=conv(numBits,[0 1 1 1 1 1 0]); % This line correlates
                                        % 5 1's to find peaks.

% This for loop counts up consecutive 1s. If it gets to 5,
% it adds that position to the vector of zero stuffed positions.

k=0;
for (ii=1:length(peakBits))
    if(peakBits(ii)==5) % Did it count to 5? If yes, then...
        k=k+1;          % Add to the counter
        peak(k)=ii;     % Add the position to the vector
    endif
endfor

% This for loop goes through the bitstream. When it comes to
% the position of a stuffed zero (determined from the previous
% for loop), it skips the zero that comes after, effectively
% removing it.

peak(k+1)=length(numBits)+1;
k=1; % counter for the vector of peak positions
c=1; % Counter for the output bitstream
for (ii=1:length(numBits))
    if (peak(k)==ii)  % If the counter comes to one of the
                      % stuffed zero positions, skip adding
                      % the zero to the output bitstream
        k=k+1;   % Go to the next zero stuffed position
    else
        procBits(c)=numBits(ii); % If not at a zero stuffed
                                 % position, add the current
                                 % bit to the output bitstream
        c=c+1;  % Increment the counter for the output bitstream
    endif
endfor

Running the script gave me an array (named peakBits in the script above) in which any value of "5" meant that it found where bit stuffing had occurred.

Calculate the CRC Checksum

At this point, I'd love to talk about how I figured out the CRC-CCITT checksum that AIS uses. BUT, despite almost a week of attempts, I've yet to figure out how to make it actually work. I realize this is a problem on my end, but I'm frustrated because it doesn't seem like that difficult of a problem.

Alas...

Convert LSB to MSB

Assuming that the data field passes the CRC, the AIS specification calls for the bitstream to be converted from LSB to MSB.

% This for loop converts the numeric bits back to a string,
% which will be easier for calculating the message fields.

tempBits="";
for (ii=1:length(procBits))
    tempBits=[tempBits num2str(procBits(ii))];
endfor

% The next for loop reverses the bit order within each byte.
% AIS transmits each byte as LSB, but processes based on MSB.
% This converts the LSB -> MSB.

bits="";
for (ii=1:numPad)
    k=(ii-1)*8;
    bits=[bits fliplr(tempBits((k+1):(k+8)))];
endfor

Reading the Data

Finally, FINALLY, we're at a point where we can actually, for-real, honest-to-your-deity-of-choice read the actual data. To do this, I read the data out based on the specification. For the code below, I only added code to read message types 1,2 3 and 18. NOTE: I was just trying to understand how to get to this point, not actually write a program to handle everything..

The data values are either unsigned integers (MMSI, speed over ground (SOG), course over ground (COG), etc) or twos complement (latitude and longitude).

% Decode the portions of the message

% Message bits are encoded either as:
% - unsigned integers: for numbers that are only positive
% - 2s complement: for numbers that are positive or negative.

% The first two fields read (Msg ID and MMSI) are the same for every
% message. After that, the message number determines how to read
% each field.
msgId=bin2dec(bits(1:6))  % Message ID is first 6 bits (1 - 6)
mmsi=bin2dec(bits(9:38))   % MMSI is bits 9 - 38.
switch (msgId)
    case {1,2,3}
        posAcc=str2num(bits(61))
        mapLon=bin2dec(bits(63:89));
        mapLon=mapLon-(2^27*str2num(bits(62)));
        mapLon=mapLon/600000
        mapLat=bin2dec(bits(91:116));
        mapLat=mapLat-((2^26)*(str2num(bits(90))));
        mapLat=mapLat/600000
        navStat=bin2dec(bits(39:42))
        sog=bin2dec(bits(51:60))/10
        cog=bin2dec(bits(117:128))/10
        rotTurn=bin2dec(bits(44:50));
        rotTurn=rotTurn-(2^7*str2num(bits(43)));
        if (rotTurn==-128)
            rotTurn="N/A"
        else
            rotTurn
        endif
        trueHead=bin2dec(bits(129:137));
        if (trueHead==511)
            trueHead="N/A"
        else
            trueHead
        endif
        timeStamp=bin2dec(bits(138:143))
    case 18
        mapLon=bin2dec(bits(59:85));
        mapLon=mapLon-(2^27*str2num(bits(58)));
        mapLon=mapLon/600000
        mapLat=bin2dec(bits(87:112));
        mapLat=mapLat-((2^26)*(str2num(bits(86))));
        mapLat=mapLat/600000
endswitch

Running this for a data burst containing message type #1, I got the following:

msgId = 1
mmsi = 367165450
posAcc = 1
mapLon = -76.42102666666666
mapLat = 39.17403333333333
navStat = 0
sog = 6.900000000000000
cog = 110
rotTurn = 0
trueHead = 114
timeStamp = 24

That was a good decode! The critical part to me was the latitude and longitude. Those points were right off of Fort Smallwood Park in the Chesapeake Bay. Further, the other numbers made sense. So, it worked!

Summary

There you have it. In order to demodulate and decode a AIS signal, you perform the following steps:

1. Capture the signals, with the primary frequencies being at 161.975 MHz and 162.025 MHz.
2. Filter and isolate the bursts.
3. Frequency demodulate the burst.
4. Minimize the DC offset to the greatest extent possible.
5. Convert the amplitudes to a NRZ-L waveform.
6. Apply a NRZ-S decoder.
7. Remove the bit stuffing.
8. Perform the CRC. NOTE: According to the specification, actual systems have to simply drop the packet if it does not pass the CRC.
9. Convert from LSB to MSB.
10. Read the data based on the message type.