More fun with Python: Navigational tricks – AIS NMEA encoding/decoding

Image

In my – for my age and current professional activities – somewhat perhaps ‘weird’ quest to learn a (for me) new programming language – after all it’s almost 20 years since I did any serious professional programming, and particularly when considering that I nowadays spend most of my professional time with powerpoint, excel and in meetings – it might appear weird that  I’ve spent some evenings and weekends lately with Python, the programming language.

For whatever reason, after I mastered (sort of) languages such as C, C++, Ada, UML and a number of scripting languages for some 20 years ago, I have not felt the urge to learn a new one.

Until a few weeks ago, when I wanted to collect and analyze massive amounts of data from Twitter. For whattever reason, I chose Python – there was no evaluation process, no previous knowledge, I just decided to go with Python… And now, after  a few weeks, I’m happy I did!

As frequent readers of my blog have noticed, until now, to learn Python, I’ve spent some time and effort trying to use the language to extract Twitter feeds, in order to do Social Network Analysis (SNA).

That exercise (documented in earlier posts on this blog), extracting and manipulating massive amounts of text strings, made me appreciate the power of Python:  IMO Python is a great, easy to learn and yet very powerful  language for processing text, with many built-in data types and constructs making text processing very convenient.  Furthermore, there’s a *lot* of external modules, for many problem domains,  written by enthusiast’s around the world – the greatness of Open Source!

So now, having learned the basics of Python’s capabilities by manipulating text, I wanted to see if Python also would prove to be as convenient for low level coding, real ‘bit banging’ close to the bare metal. After all, being a hard core low level hacker at heart, bit banging is what makes me tick – there’s nothing as rewarding as seeing a led on a board flicking based on your programming…. !:-)

Therefore, I’ve spent some time over the past weekend trying to use Python to create valid NMEA sentences with embedded AIS information.

If you own a boat, you might know what NMEA and AIS are, but for those of you who are not sea going folks, here’s a brief summary:

NMEA is an international standard for communication between different types of navigational instruments onboard a ship or boat. Basically, NMEA-compliant devices onboard, such as logs, wind instruments, plotters, GPS’s, radars etc are able to communicate using NMEA standard.

AIS is also an international standard for maritime navigation aids, based on Håkan Lans‘ patent on SDTMA communication protocol. For practical purposes, the best way to understand AIS is that it allows ships or boats to “see” each other, by regularly broadcasting navigational information. This is very convenient, particularly since AIS, asop to radar, can “see” behind bends and obstacles.

Another interesting dimension of SDTMA is its self-organizing characteristic, that is, there’s no ‘central command & control’, as in any traditional organizational hierarchy, instead decisions are made truly autonomously – a great example of a self-governing organization!

So, what I set out to do, was to create, programmaticly, valid NMEA sentences containing valid AIS information.

That turned out to be a bigger challenge than I had initially thought, since it turned out that there’s really not much of official documentation available, on neither NMEA nor AIS, on the net, at least as I’ve been able to find. So therefore, the challenge, originally intended to be learning bit banging with Python, actually turned out to be figuring out the ins and outs of the NMEA and AIS standards, i.e. to understand how these standards work.

Fortunately, there are a number of people who’ve treaded the same path before me, and documented their efforts on the net (links below), so with these ‘unofficial’ documents, I managed to produce a Python program that is capable of producing valid NMEA/AIS strings, i.e. strings that would be accepted by NMEA compliant navigation equipment, e.g for displaying ‘fake’ (or real) position data for fake or real ships.

Basically, what I wanted to do was as follows:

Imagine you are responsible for navigation onboard a ship equipped with modern navigational equipment ‘talking’ NMEA internally, and also equipped with an AIS transponder and receiver. If you are like me, then you might want to understand how that technology you are dependent on, and using on a daily basis, actually works.

Here’s the gist of it (if you want to learn the nitty gritty details, pls have a look at the links below, and the code I’ve pasted on the next page):

Onboard the ship, various instruments collect data about the ship’s various parameters, such as position (GPS), speed (log), heading/course (compass), wind (anemometer) etc etc – even water temperature is defined in the NMEA standard…  This collected data is communicated among the instruments onboard, in particular, to the various displays on the bridge.

Some of this data is also transmitted (broadcasted) over the VHF radio band to other ships in the vicinity, and this is where AIS comes in: basically, AIS defines the ship broadcast messaging.

So, since AIS info is transmitted over radio, the data to be transmitted, e.g position, course and speed info,  is packed into sequences of bits, zero’s and one’s in layman’s terms, according to a specified protocol.

When this stream of bits reaches a receiver, e.g onboard some other ship, the AIS receiver must decode and unpack the bitstream into some more meaningful structure, typically a NMEA sentence.

So, onboard the ‘sending’ ship, the AIS transmitter collects and packs navigational info into a bitstream, like below:

00000100010000010101010101010101010101000101010101010101010110000101001001100

10111000000001000100101010100010000000001010101010101010101000101001010001010

10101010101010

and broadcasts these bits over VHF radio.

On the receiving side, i.e. any ship within the radio horizon of the transmitting ship, equipped with an AIS receiver, the task of that receiver is to make sense of these bits. Therefore, the receiver uses the protocols to translate this bitstream to an NMEA message, consumable by the onboard navigational equipment. It does so by decoding the received bitstream into  six bit chunks, each chuck corresponding to a unique character in a special version of ASCII, namely six bit ascii, that the onboard NMEA based equipment can read. In the example above, the message consists of 168 bits, and with 6 bits in each chunk, there are going to be 28 six bit ascii characters in the message after translation.

These translated NMEA-sentences might look like below:

!AIVDM,1,1,,A,1007R@130NQDJ7tQw@hSQ2knP000,0*09

The first part of the message, “!AIVDM”, defines the message being an AIS message, then there follows metadata about the type of the message and the actual AIS payload, which starts after the “,,A,”, and continues uptil the “,0*”. If you count those characters, you’ll find that there are 28 of them, i.e. exactly as many as there are 6 bit chunks in the 168 bit bitstream. The “09” at the end is the message checksum .

Without going into too much detail on the structure of these NMEA-sentences (if you are interested, you can find info on how to decode them in the links below, or reading my Python program), what this NMEA sentence does is that it contains info about the sending ship, it’s position, speed, course etc, to all ships within the radio horizon.

This information is then displayed on the various navigation systems on the bridge of the ship, helping the navigation staff onboard to do their job.

After this exercise, I’m fully convinced that Python is a great language not only for ‘high level’ processing of boring ‘IT-stuff’, but also a great language for the really interesting stuff, like low level bit banging! Of course, Python being interpreted, there are performance issues that might make the language less than suitable in some specific domains, but for this type of “batch” processing, it’s simply great.

Below, some technical links on NMEA and AIS. I’m very greatful to the authors of these pages for the information that enabled me to ‘hack’ the obscure protocols!

Bosun’s Mate

Eric S. Raymond

Digital Yacht

it-digin’s

RL.se

The code below is for illustration purposes only, no guarantees given nor implied…. after all, it’s written by a grumpy old man, with no real knowledge of Python nor AIS or NMEA, not having done any serious programming in decades….

import bitstring

#ais NMEA payload encoding
payloadencoding = {0:’0′,1:’1′,2:’2′,3:’3′,4:’4′,5:’5′,6:’6′,7:’7′,8:’8′,9:’9′,10:’.’,11:’,’,12:'<‘,13:’=’,14:’>’,15:’?’,16:’@’,17:’A’,

18:’B’,19:’C’,20:’D’,21:’E’,22:’F’,23:’G’,24:’H’,25:’I’,26:’J’,27:’K’,28:’L’,29:’M’,30:’N’,31:’O’,32:’P’,

33:’Q’,34:’R’,35:’S’,36:’T’,37:’U’,38:’V’,39:’W’,40:”`”,41:’a’,42:’b’,43:’c’,44:’d’,45:’e’,46:’f’,47:’g’,

48:’h’,49:’i’,50:’j’,51:’k’,52:’l’,53:’m’,54:’n’,55:’o’,56:’p’,57:’q’,58:’r’,59:’s’,60:’t’,61:’u’,62:’v’,63:’w’}

# create AIS-string decoding map
reverseencoding = dict()

for k,e in payloadencoding.iteritems():
reverseencoding[e] = k
#

# ais message bit structure, 168 bits
typ = bitstring.BitString (‘0b000001’)
rep = bitstring.BitString (‘0b00’)
mmsi = bitstring.BitString (‘0b010000010101010101010101010101’)
stat = bitstring.BitString (‘0b0001’)
rot = bitstring.BitString (‘0b01010101’)
sog = bitstring.BitString (‘0b0101010101’)
pa = bitstring.BitString (‘0b1’)
lon = bitstring.BitString (‘0b0000101001001100101110000000’) #18E
lat = bitstring.BitString (‘0b010001001010101000100000000’) #60N
cog = bitstring.BitString (‘0b010101010101’)
hdg = bitstring.BitString (‘0b010101010’)
ts = bitstring.BitString (‘0b001010’)
mi = bitstring.BitString (‘0b01’)
spa = bitstring.BitString (‘0b010’)
raim = bitstring.BitString (‘0b0’)
radio = bitstring.BitString (‘0b0101010101010101010’)

bitstream = bitstring.BitString(typ+rep+mmsi+stat+rot+sog+pa+lon+lat+cog+hdg+ts+mi+spa+raim+radio)

def unpackbitstream(bits168): #bitstream -> AIS payload map
payload = dict()

typ = bits168[0:6]
rep = bits168[6:8]
mmsi = bits168[8:38]
stat = bits168[38:42]
rot = bits168[42:50]
sog = bits168[50:60]
pa = bits168[60:61]
lon = bits168[61:89]
lat = bits168[89:116]
cog = bits168[116:128]
hdg = bits168[128:137]
ts = bits168[137:143]
mi = bits168[143:145]
spare = bits168[145:148]
raim = bits168[148:149]
radio = bits168[149:168]

payload[‘type’] = typ
payload[‘repeat’] = rep
payload[‘mmsi’] = mmsi
payload[‘status’] = stat
payload[‘turn’] = rot
payload[‘speed’] = sog
payload[‘accuracy’] = pa
payload[‘lon’] = lon
payload[‘lat’] = lat
payload[‘course’] = cog
payload[‘heading’] = hdg
payload[‘second’] = ts
payload[‘maneuver’] = mi
payload[‘spare’] = spare
payload[‘raim’] = raim
payload[‘radio’] = radio

return payload

def nmeaChecksum(s): # str -> two hex digits in str
chkSum = 0
subStr = s[1:len(s)]

for e in range(len(subStr)):
chkSum ^= ord((subStr[e]))

hexstr = str(hex(chkSum))[2:4]
if len(hexstr) == 2:
return hexstr
else:
return ‘0’+hexstr

# join NMEA pre- and postfix to payload string
def joinNMEAstrs(payloadstr): #str -> str
tempstr = ‘!AIVDM,1,1,,A,’ + payloadstr + ‘,0’
chksum = nmeaChecksum(tempstr)
tempstr += ‘*’
tempstr += chksum
return tempstr

# encode bitstream to 6bit ascii string
def aisencode (aisstr): #BitString -> string
l = 0
r = 6 # six bit chunks
aisnmea = []

for i in range (0,28): #168 bits in 28 chunks of 6
chunk1 = aisstr[l:r]
char = str(chunk1.uint)
intie = int(char)
aisnmea.append(payloadencoding[intie])
l += 6
r +=6

aisstr = ”.join(aisnmea)
return aisstr

def bin6(x): # int -> 6 binary digits
return ”.join(x & (1 << i) and ‘1’ or ‘0’ for i in range(5,-1,-1))

# convert vector of ints to bitstring
def intvec2bitstring(aisvec): #intvec -> Bitstring
nmeanums = []

for i in range(len(aisvec)):
nmeanums.append(bin6(aisvec[i]))
bitstring = ”.join(nmeanums)
return bitstring

# decode AIS string to int vector
def aisdecode(aisstr): #string -> numvec
numvec = []
numstr = ”

for i in aisstr:
key = i
code = reverseencoding[key]
numvec.append(code)

return numvec

# create a map with all AIS elements as keys
def pack(packmap,type, repeat,mmsi,status,turn,speed,accuracy,lon,lat,course,heading,second,maneuver,spare,raim,radio): #map,normal ints -> packmap
packmap[‘type’] = bitstring.BitString(uint=type,length=6)
packmap[‘repeat’] = bitstring.BitString(uint=repeat,length=2)
packmap[‘mmsi’] = bitstring.BitString(uint=mmsi,length=30)
packmap[‘status’] = bitstring.BitString(uint=status,length=4)
packmap[‘turn’] = bitstring.BitString(uint=turn,length=8)
packmap[‘speed’] = bitstring.BitString(uint=speed,length=10)
packmap[‘accuracy’] = bitstring.BitString(uint=accuracy,length=1)
packmap[‘lon’] = bitstring.BitString(uint=lon,length=28)
packmap[‘lat’] = bitstring.BitString(uint=lat,length=27)
packmap[‘course’] = bitstring.BitString(uint=course,length=12)
packmap[‘heading’] = bitstring.BitString(uint=heading,length=9)
packmap[‘second’] = bitstring.BitString(uint=second,length=6)
packmap[‘maneuver’] = bitstring.BitString(uint=maneuver,length=2)
packmap[‘spare’] = bitstring.BitString(uint=spare,length=3)
packmap[‘raim’] = bitstring.BitString(uint=raim,length=1)
packmap[‘radio’] = bitstring.BitString(uint=radio,length=19)

return packmap

# create a bitstring from a map
def unpack(packmap): #map -> bitstring
bitstr =bitstring.BitString = packmap[‘type’]
bitstr.append(packmap[‘repeat’])
bitstr.append(packmap[‘mmsi’])
bitstr.append(packmap[‘status’])
bitstr.append(packmap[‘turn’])
bitstr.append(packmap[‘speed’])
bitstr.append(packmap[‘accuracy’])
bitstr.append(packmap[‘lon’])
bitstr.append(packmap[‘lat’])
bitstr.append(packmap[‘course’])
bitstr.append(packmap[‘heading’])
bitstr.append(packmap[‘second’])
bitstr.append(packmap[‘maneuver’])
bitstr.append(packmap[‘spare’])
bitstr.append(packmap[‘raim’])
bitstr.append(packmap[‘radio’])

return bitstr

##testing the above functions

print ‘bitstream:’
print bitstream.bin,’length:’,bitstream.len

encodedstr = aisencode(bitstream)
print ‘encoded string:’
print encodedstr,’length:’,len(encodedstr)

decodedvec = aisdecode(encodedstr)

bitstr = intvec2bitstring(decodedvec)
print ‘decoded bitstream:’
print bitstr,’length:’,len(bitstr)

print joinNMEAstrs(encodedstr)

unpackedmap = unpackbitstream(bitstr)

unpackedmap[‘lat’] = bitstring.BitString(uint=27000000,length=27)

for k,v in unpackedmap.iteritems():
print k,v

newmap = dict()
newmap = pack(newmap,1,0,123456,1,12,30,1,11063550,35639490,900,89,59,1,0,0,0)

newstream = unpack(newmap)
print ‘newstream:’
print newstream.bin,’length:’,newstream.len

newencode = aisencode(newstream)

print ‘newencodedstring:’
print newencode, ‘length:’,len(newencode)
print joinNMEAstrs(newencode)

Advertisements

About swdevperestroika

High tech industry veteran, avid hacker reluctantly transformed to mgmt consultant.
This entry was posted in development, software and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s