The Toils o AIS: A Case S udy in
Applica ion P o ocol Design And Analysis
E ic S. Raymond <[email p o ec ed]>, Ku Schweh <[email p o ec ed]>
2011; Ve sion 0.2
h p://doi.o g/10.5281/zenodo.17328241
In oduc ion
The au ho s ha e w i en se e al decode s and codecs o he a he complex AIS p o ocol used
by ma ine sa e y and na iga ion sys ems. Based on his expe ience, we pu o wa d some
lessons lea ned and design p inciples ha we hink should be heeded in he ex ension o AIS
and he design o u u e applica ion p o ocols. We also o e p agma ic ad ice o hose
implemen ing decode s o AIS and simila applica ion p o ocols.
O e iew o AIS
The Ma ine Au oma ic Iden i ica ion Sys em (AIS) is a so wa e, ha dwa e, and adio coding
p o ocol ha allows ships o b oadcas na iga ional and o he s a us in o ma ion o use in
collision a oidance, na iga ion, and a ic managemen . Ea ly design wo k on AIS was done
p ima ily by Sweden; he In e na ional Associa ion o Ligh house Au ho i ies (IALA) p oposed
he concep o he In e na ional Ma i ime O ganiza ion (IMO) in 1995 [IALA2004]. The co e AIS
s anda d is now main ained by he In e na ional Telecommunica ions Union (ITU) in associa ion
wi h IMO [ITU1374].
Bo h he design o AIS and he p ocess by which i e ol ed a e ep esen a i e o a la ge class o
applica ion p o ocols in he eal wo ld, especially hose conce ned wi h geoloca ion and
geog aphic in o ma ion sys ems. A ma ked ea u e o AIS, howe e , is ha due o he haza ds o
ope a ion a sea, he in o ma ion i handles can be immedia ely li e-c i ical. This gi es so wa e
de ec s in decode s a special signi icance and aises he s akes in ou design analysis.
The physical laye o AIS uses a sel o ganizing (SO) a ian o Time Di ision Mul iple Access
(TDMA) packe adio scheme o a oid collisions among AIS ansmi e s se ing ei he o wo
ope a ing equencies [LANS1996]. Fo he analysis in his pape , he physical laye can be
la gely igno ed and AIS iewed as a mechanism o passing bina y da ag ams in ei he an
add essed o b oadcas mode. Fo AIS pu poses an "add ess" is a Ma i ime Mobile Se ice
Iden i y (MMSI), a 9-digi nume ic ag associa ed wi h a ship o sho e s a ion.
The bina y da ag ams ha e a ixed heade con aining a dispa ch ield ( he ype) ollowed by
in o ma ion whose o ma ing a ies by ype in complex ways. Payload in o ma ion is encoded
mainly as packed nume ic bi ields o leng hs a ying om 1 o 30 bi s; hese may be
in e p e ed as boolean lags, unsigned o signed wo’s-complemen big-endian in ege s, indices
in o con olled ocabula ies, o (implici ly, ia scaling o mulas) as ixed-poin eal numbe s.
Some messages ha e longe egions ha a e in e p e ed as cha ac e s ings o ea ed as
opaque bina y blobs o be passed o om o o helpe applica ions.
Typical da a i ems o be ex ac ed om AIS bi ields include la i udes, longi udes, essel cou se
and speed, capabili ies o he ansmi ing essel o s a ion, and wea he o sa e y condi ions.
Some message ields a e passed solely o he AIS sys em’s own housekeeping unc ions.
In p ac ice, so wa e enginee s a e unlikely o encoun e AIS da ag ams in aw bina y o m. AIS
ecei e s commonly make hem a ailable o e RS422, RS232 and USB po s in an
ASCII-a mo ed by e-s eam o m called AIVDM/AIVDO, a p o ile o a ian o he NMEA o ma
commonly used in shipboa d na iga ion and con ol sys ems.
The design o AIS is op imized o make e icien use o sca ce adio bandwid h. In his i
esembles a g ea many applica ion p o ocols which igh -pack e e y bi - ei he ou o a ional
economy o (mo e commonly) because he designe ’s men al habi s we e o med in a ime
when bandwid h was a mo e expensi e han i is oday.
Raymond main ains a p og amme ’s-eye iew o he de ails o AIS/AIVDM/AIVDO in
[RAYMOND1]. Since ha documen is a ailable om any b owse , we choose no o bu den his
pape wi h duplica i e de ails abou da ag am o ma s (bu see he layou o he Common
Na iga ion Block in he nex sec ion o a ep esen a i e example, he payload o he h ee mos
common message ypes). We will e e o [RAYMOND1] equen ly, and eade s a e assumed o
be amilia wi h i be o e p oceeding.
Complexi y kills
I is ha dly news ha so wa e de ec a es ise wi h he complexi y o he so wa e. So wa e
bugs equen ly a ise om unplanned in e ac ions be ween di e en pa s o a codebase. I
ollows ha de ec a es scale oughly as he squa e o codebase size. I is well known [MMM]
ha bugs end o clus e a he in e aces be ween code w i en by di e en people; hus, de ec s
also ise as he squa e o he numbe o code s on a p ojec .
In li e-c i ical sys ems such as AIS, so wa e de ec s can kill people. So wa e complexi y should
he e o e be iewed as an ac ual dange , a cause o a oidable dea hs. Simplici y sa es li es.
The bene i s o so wa e simplici y in non-li e-c i ical sys ems, while less d ama ic, a e no less
eal. De ec s incu downs eam p oblems and main enance cos s; hus, so wa e complexi y
should be iewed as a bu den ha does no end when he p ojec ships, bu which con inues o
incu cos s o e he en i e se ice li e o he so wa e.
Complex applica ion p o ocols equi e complex so wa e o in e p e hem. Thus, applica ion
p o ocol complexi y en ails so wa e complexi y, which en ails quad a ically ising de ec a es,
which in li e-c i ical sys ems implies a oidable dea hs.
Acco dingly, a cen al p oblem wi h AIS - and many o he applica ion p o ocols esembling i - is
ha i is exceedingly complex.
The p oblem is well indica ed by he bulk o he base speci ica ion, [ITU1371]. In he cu en
Ve sion 4 he e a e 27 message ypes wi h leng hs a ying om 72 o 1008 bi s, desc ibed by
142 pages o dense s anda dsese. I is supplemen ed by wo In e na ional Ma ine O ganiza ion
ci cula s ([IMO236] and [IMO289]) de ining 24 addi ional message sub ypes in 78 addi ional
pages o s anda dsese. The AIVDM/AIVDO ASCII packe o ma is desc ibed in ye ano he
s anda d, [IEC-PAS]. When aking in o accoun he sub messages, he speci ica ions allow o
mo e han 262K message ypes.
The e is a common pa aph ase o a quo e by Albe Eins ein ha ad ises us o "Make
e e y hing as simple as possible, bu no simple ." Some pa o AIS’s complexi y is essen ial o
i s unc ion. Fo example, any applica ion p o ocol ha con eys nume ic da a has o ha e ules
abou how i is ep esen ed in he bi s. O he pa s o i s complexi y a e acciden al, simply a
esul o un o una e design decisions.
The mos p e alen cause o bad p o ocol-design decisions is no indi idual incompe ence, bu
a he a ious so s o cul u al blindness a ec ing he design p ocess. Expe ienced so wa e
enginee s lea n o ecognize - and d ead - he signs o an applica ion p o ocol designed by
domain specialis s who do no unde s and how o a oid acciden al complexi y, o g a ely
unde weigh i s cos s.
We will ana omize in de ail he acciden al complexi y o AIS. In so doing, we in end o illus a e
by in e sion how applica ion-p o ocol designe s can a oid cos ly and dange ous mis akes.
How complexi y ises
Analyzing da ag ams in a p o ocol like AIS is o mally simila o pa sing a con ex - ee g amma
(CFG). The goal, in bo h cases, is o diges a se ial s eam o incoming bi s om an ex e nal
sou ce in o an in e nal ep esen a ion ha uses he na i e da a o ma s o he in e p e ing
compu e . This in e nal ep esen a ion may hen be used in any numbe o ways (e.g.
isualiza ion, epo gene a ion, and in e p e a ion as a command sequence).
Pa sing echniques o CFGs ound in ex ual o ma s such as compu e languages and
documen ma kups a e a much-s udied a ea o compu e science, well-desc ibed in classics
such as [ASU]. Though i is less p ac iced, applica ion o hese same echniques o bina y
da ag ams and s eams emains alid o p ac ical pu poses and o es ima ions o algo i hmic
complexi y. Tools such as [ASN.1] desc ibe bina y by e-s eam p o ocols in his s yle. Wha
speci ically conce ns us in his pape is o unde s and how o hold he complexi y o he pa sing
s age o a minimum.
A CFG’s complexi y (and he complexi y o associa ed pa se s) is p opo ional o he numbe o
p oduc ions (pa sing ules) equi ed o desc ibe i . The analog o a e minal symbol in he
g amma is a bi ield leng h and ype, whe e ype in his con ex includes no jus nume ic kind
bu associa ed in e p e i e da a like o se s, scaling cons an s, and con olled- ocabula y lis s.
Fu he , complexi y in CFGs ends o ha e a Pa e o’s-law-like dis ibu ion: small i egula i ies
and excep ion cases in some 20% o he language p oduces la ge ipple e ec s in he di icul y
o pa sing he o he 80%. Acco dingly, ano he class o p oblem o look ou o is excep ion
cases o gene al ules.
Wi h his model in mind, le us ou he AIS message ypes in sequence, as an implemen e
gene ally would, looking a he speci ic ways hey add complexi y o he implied CFG. Fo he
momen , igno e he many issues abou he in en o y o e minal symbols (bi ield ypes and
in e p e a ions), jus as we would no mally igno e mos lexical issues in es ima ing he pa se
complexi y o a con en ional ex ual CFG. The bounda ies among e minal symbol ypes a e
dispu able, and he coun s we gi e below should be conside ed app oxima ions o
scale-es ima ion pu poses.
Types 1 h ough 4: Fixed-leng h elici y
Begin by conside ing he i s h ee AIS message ypes desc ibed in Table 45 o [ITU1371]-4,
g ouped as "Posi ion Repo Class A", bu igno e he ailing communica ion s a e. These di e
only in ype numbe and i s in e p e a ion, which is ou side he pa se ’s scope. They can
he e o e be ega ded as one p oduc ion in he g amma ; in [RAYMOND1] i is called he
Common Na iga ion Block (CNB).
Field
Len
Desc ip ion
Type
Uni s and
Meaning
0-5
6
Message Type
unsigned in
Cons an : 1-3
6-7
2
Repea Indica o
unsigned in
Message epea
coun
8-37
30
MMSI
unsigned in
9 decimal digi s
38-41
4
Na iga ion
S a us
enume a ed
Moo ed, unde
way, e c.
42-49
8
Ra e o Tu n
(ROT)
signed eal
Deg ees pe
minu e
50-59
10
Speed O e
G ound (SOG)
unsigned eal
Me e s pe
second
60-60
1
Posi ion
Accu acy
boolean
High-accu acy
lag
61-88
28
Longi ude
signed eal
Minu es/10000
89-115
27
La i ude
signed eal
Minu es/10000
116-127
12
Cou se O e
G ound (COG)
unsigned eal
Deg ees om
ue no h.
128-136
9
T ue Heading
(HDG)
unsigned in
Deg ees om
ue no h.
137-142
6
Time S amp
unsigned in
Second o UTC
imes amp
143-144
2
Maneu e
Indica o
enume a ed
145-147
3
Spa e
No used
148-148
1
RAIM lag
boolean
Recei e
Au onomous
In eg i y
Moni o ing
enabled and
alid?
149-167
19
Radio s a us
a iable
s uc u e
S a us bi s o
cell adio
The CNB is ixed-leng h and has a ixed sequence o six een ields, spanning six een ypes, in
160 bi s. I is hus dead-simple o pa se. In C, one could easily decode he bi s wi h no mo ing
pa s ( o mally, no con ol logic) by eading he en i e da ag am in o memo y (whe e i would
ake up a g and o al o 20 by es) and cas ing i in o a s uc u e ull o bi ields (which, on a
li le-endian machine, would alas ha e o be lipped end- o-end).
F om a eliabili y-enginee ing poin o iew, his is a bes case scena io and a e y p omising
s a . Howe e , see la e discussion o ield-speci ica ion issues o some oubling p oblems
wi h indi idual ields in hese h ee messages
Message ype 4, "Base S a ion Repo ", is also ixed-leng h and ixed-sequence and can hus
also be pa sed wi h no mo ing pa s. While i in oduces nine new ield ypes (including ou i s
con olled ocabula y index) he inc ease in o e all complexi y is low.
Type 5: The six-bi blunde
Wi h message ype 5, "Ship s a ic and oyage ela ed da a", complexi y begins o ise. This ype
is s ill ixed-leng h wi h a ixed sequence o 21 ields, and in oduces only i e new ypes. Th ee
o he Type 5 ields (Call Sign, Vessel Name, and Des ina ion) a e cha ac e -s ing da a in a
64-bi subse o ASCII packed as 6-bi nybbles. Un o una ely, i is d ama ically mo e complex o
decode his oddly packed s ings han he ixed-leng h nume ics and lag bi s we’ e been
dealing wi h so a .
This is a pa adigm o he so o ixa ion on igh es -possible bi packing ha makes so wa e
enginee s blanch. Be o e his 6-bi da a can be used, i needs o be unpacked in o con en ional
8-bi by es. No only ha e we los he simplici y o being able o decode he message jus by
s a ically slicing i in o ixed-leng h bi ields, he mo ing pa s o he unpacking logic u n ou o
be easy o ge w ong in ways ha a e icky o diagnose. This is no me ely heo e ical c i icism;
Raymond ound a longs anding bug in a p eexis ing AIS decode ([GNU-AIS]) exac ly he e.
The ac ha hese s ings a en’ coded in by e-aligned 8-bi ASCII o UTF-8 is he i s se ious
blob o acciden al complexi y in AIS. The 6-bi da a occupies 262 bi s o a 424-bi message
o ma in 47 nybbles. The cos o 8-bi -ASCII would ha e been a 22% inc ease in message
leng h, bu going om 2 o 2.34 slo s ( equi ing 3 slo s o ansmi ). A he ype 5 ansmission
in e al and da a a es p esc ibed in [ITU1371] his implies an addi ional ansmission cos o
0.004% o he VHF da a link a ailable slo s. Fo 100 ships in an AIS cell, he o e all cos would
be 0.37% o he a ailable slo s.
[ITU1374]-4 alludes o an in e na ional p ocess unde way o alloca ing wo mo e AIS channels.
These channels may be a much highe equencies han VHF and a o d much mo e han
9600bps bandwid h as hey will be op imized o sa elli e ecep ion.
Thus, he designe s o AIS incu ed a subs an ial inc ease in he complexi y o decode s in o de
o sa e he equi alen o wo en hs o one pe cen o a du y cycle. This is ou i s "Ne e , e e
do his!" I is a blunde ha could only a ise om being ixa ed on ha dwa e-laye economy while
igno ing he de ec - a e implica ions and es ing cos s o he so wa e laye .
Fu he mo e, o e ime bandwid h ends o become less expensi e while de ec - and
main enance- ela ed cos s in so wa e end o emain s eady o ising. Thus, he choice ha was
a bad adeo in 1998 when [ITU1371] i s issued looks wo se oday, en yea s la e . I will look
s ill wo se en yea s om now.
Type 6 and 8: Dynamic alloca ion is no you iend
Wi h ype 6, "Add essed bina y message", wo mo e o ms o complexi y a e in oduced. One is
mino and a guably essen ial; he o he is majo and comple ely acciden al. We’ll conside ypes
6 and 8 oge he , as ype 8 is s uc u ed in essen ially he same way as 6 excep o omi ing
des ina ion in o ma ion and housekeeping in o ma ion o poin - o-poin ansmission; i is
ins ead designed o b oadcas messages.
The mino inc emen is ha message ypes 6 and 8 ha e a bi leng h ha is a iable a he han
ixed. These messages a e a w appe a ound a bina y payload o up o 920 ( ype 6) o 952
( ype 8) bi s, which is he las ield.
In he speci ic con ex o AIS, his so o a iable-leng h payload poses no special di icul y.
Because he message leng h ops ou a 1008 bi s = 126 by es, i is easible o unpack i in a
s a ic bu e o maximum size and igno e he iny amoun o was e space.
This is no in gene al ue o applica ion p o ocols wi h bulkie payloads, o which handling
a iable-leng h da ag ams o en equi es dynamic memo y alloca ion. And, in languages like C
o C wi hou au oma ic ga bage collec ion, dynamic-memo y alloca ion is a no o ious sou ce o
de ec s. Indeed, many audi s o la ge C/C codebases ha e ound i o be he single wo s sou ce
o da a co up ion, secu i y p oblems, and c ash bugs. On he o he hand, languages which
a oid his p oblem h ough suppo o a iable-ex en da a s uc u es and ga bage collec ion a e
o en oo bulky o i in embedded deploymen s o oo subjec o GC- ela ed s alls o be sui able
o eal- ime use.
Applica ion-p o ocol designe s should he e o e hink wice be o e incu ing his complexi y as a
side e ec o hei designs. Bu a leas his is o en essen ial complexi y, a kind ha is en ailed
in he applica ion equi emen s.
Type 6 and 8 con inued: O e ex ension is you enemy
Un o una ely, in e p e a ion o ypes 6 and 8 in oduces ano he kind o complexi y ha is
comple ely acciden al and (in he AIS con ex ) a wo se. In e p e a ion o he bina y payload is
bo h a iable and ambiguous.
Ea ly e sions o he base AIS speci ica ion ese ed 16 bi s be o e he ac ual payload as an
"applica ion iden i ie ". This was subdi ided in o a 10-bi "designa ed a ea code" (DAC) and a
six-bi " unc ional iden i ie " (FID). The in en ion o ypes 6 and 8 a ha ime appea s o ha e
been as a condui o p i a e and enc yp ed da a. The wo ld’s Coas Gua ds and Na ies a e
known o use AIS his way ("blue o ce AIS" o E-AIS). The e was no complexi y inc emen o
gene al-pu pose decode s in his scheme; any ex a bu den ell on p i a e applica ions
gene a ing and in e p e ing hose payloads.
All his changed when he ITU delega ed con ol o message 6 and 8 layou s o egional
au ho i ies by DAC. These messages hen became an ex ension mechanism ha con olling
au ho i ies o a designa ed a ea could use o de ine hei own payload o ma s wi hou
ex ending o e ising he base s anda d. The S . Law ence Seaway (DACs 366 and 316) and
he In e na ional Ma i ime Au ho i y (DAC 1) p omp ly did so.
While his may ha e been bu eauc a ically con enien , he esul was a con using p oli e a ion
o public message sub ypes, some pushed h ough wi hou adequa e e iew ( o example,
[IMO236] con ains ob ious signs o d a ing e o s in he FID=12 "Numbe o pe sons on boa d"
speci ica ion). As o ea ly 2011 he e a e 24 such sub ypes in he in e na ional DAC alone,
equi ing app oxima ely as much addi ional complexi y as he en i e y o [ITU1371].
I he esul had been o p ese e ixed- ield simplici y o each message ype while me ely
bloa ing he o e all olume o decode s, he implica ions o complexi y and de ec loads would
ha e been wo ying bu eadily manageable. Bu he damage did no end he e.
Be o e, he only ield o an AIS message ha could ac as a dispa ch o di e en bi ield
sequences was he message- ype ield in he heade . Unde he new ules, he payload pa in
hese so-called " unc ional" messages o ype 6 and 8 could ha e any numbe o di e en bi ield
sequences depending on he join alue o wo mo e dispa ch ields, DAC and FID.
In one pa icula ly eg egious example o misdesign, he IMO289 "Wea he Obse a ion F om
Ship" (DAC = 1, FID = 21) sp ou ed wo a ian s and a ou h dispa ch ield, a lag a bi o se
56 ("Type o wea he epo ")!
The inc emen o he minimum complexi y o decode s was qui e la ge, la ge in ac han he
jump om he packed-sixbi blunde . Bu he damage didn’ e en end he e, as ships unde he
ju isdic ion o some Designa ed A eas began sending IMO ex ension messages wi h IMO236 o
IMO289 FIDs pai ed wi h local DACs o he han 1. I became impossible o eliably dis inguish
IMO special messages om poo ly-documen ed local con en ions wi hou a g owing excep ion
lis .
The con usion had become comple e. And his is be o e we e en en e in o he addi ional
complexi y o he ac ual special-message payloads, which we shall no a emp o ully desc ibe
he e. Su icien ly masochis ic eade s can ind he de ails in [RAYMOND1] and [IMO289].
All his complexi y appea s, qui e unde s andably, o ha e s alled ou adop ion o he IMO
special-message ypes. In sea ches o da a om [AISHUB] and [NAIS], which pools AIS epo s
o o e 150 AIS ecei e s sca e ed all o e he wo ld, we ha e ye o unambiguously de ec
any o he 19 messages desc ibed in IMO289 aside om hese h ee: 8:1:11 (Me /Hyd o
dep eca ed), 8:1:26 (En i onmen al), 8:1:22 (A ea No ice - b oadcas ) in wo yea s o ying ( he
la e wo a e om USCG es bed ecei e s in Tampa, FL and P o ince own, MA). I is highly
doub ul ha he e is enough olume o mo i a e endo s o AIS ecei e s o unde ake he
expensi e ask o upg ading hei i mwa e and display applica ions.
All o his complexi y - and he inc eased de ec a e i implies - appea s o ha e been
sel -de ea ing, loaded on o li le o no pu pose and equi ing decode implemen a ions o
include essen ially useless code in o de o check o s anda ds-con o mance boxes.
Had he ITU/IMO s uck wi h i s single o iginal ex ension mechanism ( he ype ield in he heade )
and added only new message ypes wi h a ixed bi ield sequence, i seems a mo e likely ha
hese messages would ha e achie ed use ul deploymen .
Types 6 and 8: Poin de ec s
A emp ing o desc ibe all he design de ec s in he IMO ex ension messages would ce ainly
exhaus he eade ’s pa ience and possibly endange his o he sani y. Bu some o he simple
ones dese e examina ion because hey can be used o illus a e sound design p inciples by
nega i e example.
Some o he ype 6 and 8 ex ension messages ea u e ailing a iable-leng h a ays o eco d
s uc u es. One o he simple examples is Rou e In o ma ion; he add essed and b oadcas
e sions ha e a ixed-leng h heade ollowed by 1 o 16 la i ude/longi ude pai s ep esen ing
waypoin s. Ano he is Tidal Window, wi h 1 o 3 mo e complex ailing s uc u es ep esen ing
idal-cu en condi ions.
In gene al, when AIS messages ha e a iable-leng h ailing sec ions he ac ual leng h o he
aile is implici om he message’s o e all bi leng h. Tidal Window, in pa icula , is o ganized
his way, Bu Rou e In o ma ion is an excep ion; he las ield in he ixed-leng h pa is a
waypoin coun .
The e a e wo p oblems wi h his. Fi s , he exis ence o ha waypoin coun ield iola es he
Single Poin o T u h p inciple. I is edundan wi h he message bi -leng h, and may e en
Lesson: Supposing you mus design a packed-bina y p o ocol ha con ains embedded s ing
da a, don’ y o ge cu e wi h cha ac e encodings o sa e space. You can’ squeeze ou
enough bi s o be wo h he downs eam pain you will cause.
Each o he o he design de ec s in he AIS p o ocol iola es a egula i y ha was implici ly
p esen in all da ag am layou s p e ious o he one in which i i s occu ed, escala ing pa sing
complexi y o all message ypes.
1. Message ypes 6 and 8 b oke he ule ha he p o ocol has exac ly one dispa ch ield
and each ype has a ixed ( hough possibly ail- a iable) bi ield sequence. In doing his,
hey added a second ex ension mechanism o he p o ocol, and handed o con ol o
a ious po ions o he ex ension space. The esul ing mess eaches se e al impo an
lessons:
Lesson: Dispa ch ields ( hose which change he logic low o he pa se) a e complexi y and
de ec a ac o s. The complexi y cos o ha ing mul iple dispa ch ields ises no addi i ely bu
mul iplica i ely. Well-designed applica ion p o ocols ha e jus one, pe iod.
Lesson: One p o ocol-ex ension mechanism may be jus igh , bu wo is ce ainly oo many.
Lesson: Bewa e especially o ex ension mechanisms ha encou age local op ions and do no
en o ce a common namespace in hei dispa ch ields. Such mechanisms a e likely o u n you
p o ocol in o an unmanageable hai ball in sho o de .
Lesson: Su e no hy p o ocol design o all in o he hands o bu eauc a s, o hey will smo he
i in ea u es.
1. Message ype 21 poin lessly spli a s ing ield in wo. This is a mino de ec compa ed o
he o he in elici ies.
Lesson: Don’ do his. I adds de ec -a ac ing mo ing pa s o he code and complica es
es ing.
1. Message ype 22 no only con ained a second dispa ch ield, i loca ed ha ield a e he
payload sec ion i con olled.
Lesson: Dispa ch ields should always p ecede any payload o which hey modi y he bi ield
sequence. O he wise you will o eclose en i e classes o simple and ligh weigh s eam-pa sing
echniques. (This is a pe ec example o a poin de ec in design ha imposes la ge complexi y
cos s no jus o he p ocessing o ha indi idual message ype bu o all ypes.)
1. Message ype 24 has wo in e nal dispa ch ields con olling a ian sec ions, and is spli
ac oss wo da ag ams. In addi ion o he no mal complexi y cos s o handling a ian
sec ions, his equi es a con o ming pa se o main ain agile s a e be ween da ag ams
and in oduces lo s o icky edge cases.
Lesson: Ne e do his! The amoun o s a e ulness ha he ne wo k laye s unde nea h you
applica ion p o ocol imposes on you will be a se e e enough sou ce o bugs and edge cases;
delibe a ely agmen ing you applica ion p o ocol’s uni s o meaning o in i e mo e is asking o
ouble.
1. Message ype 25 con ains op ional ields ha a e no a ixed o se s, adding complexi y
ha migh be conside ed a mino design de ec .
2. Message ype 26 con ains a a iable-leng h payload ield ha is no he las one in he
message, complica ing he handling o a iable-leng h ields in s eam pa se s. This
migh be conside ed a mino design de ec .
3. A huge p oli e a ion o ield ypes and a ian s c ea es excessi e complexi y in decode s.
Lesson: Minimize he numbe o ield ypes. Good p ac ice is o he e o be jus one ype pe
na u al kind; e.g. in a geoloca ion p o ocol all longi udes should be encoded wi h he same
leng h, signedness, and special alues. Di o all la i udes, bea ings, imes amp ields, e c.
1. The "Special Manoeu e" ield in he CNB has unspeci ied seman ics. The (lack o )
speci ica ion does no include e en a hando o a egis y o documen desc ibing he
use o he ield, so e en i " egional au ho i ies" we e o de ine i , decode implemen o s
would ha e no way o ind he de ini ion(s).
Lesson: Ne e do his! The e ec o his design e o is ha e en i some egional au ho i y
a emp s o pu a meaning on he ield, he e o is e ec i ely ce ain o ail.
1. Special-casing o MMSIs c ea es a bug ulne abili y ela ed o mis- ecogni ion o SART
p e ixes.
Lesson: Don’ make an elabo a e, mul i-special-case decode o a ield ca y in o ma ion ha
should be passed ia mul iple ields wi h simple decode speci ica ions.
1. Ra e o Tu n in he CNB uses an unnecessa ily excep ional scaling o mula. And Rou e
In o ma ion uses an excep ional mechanism o speci ying he elemen coun o a ailing
a ay.
Lesson: Keep excep ion cases o a dead minimum. Remembe ha one iny speci ica ion
excep ion ha ’s easy o a human being o p ocess can make he p o ocol in ac able o pa se
gene a o s. A good way o hink abou he downs eam impac is ha each excep ion case
doubles he o e all cos o coding and es ing, and co espondingly doubles he expec ed de ec
a e.
1. The RAIM and Posi ion Accu acy ields occu ing in se e al messages ha e become
essen ially meaningless and possibly dange ously misleading. They cos code
complexi y wi hou con eying use ul in o ma ion.
Lesson: Bewa e o magic numbe s in ield de ini ions (like he "10 me e s" in he de ini ion o
Posi ion Accu acy) because echnology can change hem and likely will. Make he ield say wha
you mean in a u u e-p oo way (like, ac ually gi ing me e s o e o es ima e a 95% con idence)
e en i ha cos s a ew bi s o space.
1. AIS imes amps a e incomple e, equi ing ou -o -band in o ma ion when keeping
sen ence logs.
Lesson: Ne e , e e de ine a imes amp ield ha isn’ a comple e da e/ ime s amp in UTC. No
excep ions, because you will come o eg e e e y single one.
Fu he no e: I you choose any imes amp o ma o he han ISO8601, ha is p obably a design
de ec in i sel . The ad an ages o a o ma ha is eadable, eadily usable as a da abase key,
and o which lexicog aphic so o de co esponds wi h ime o de a e la ge.
To hese de ec s could be added ano he la ge one ha in a sense p ecedes all o hem. A he
iny da a olumes o AIS, he s yle o packed-bi bina y p o ocols o which AIS is an example is a
colossal e o o misdi ec ed and p ema u e op imiza ion, leading o igidi y and unnecessa y
o e complexi y. See [TEXTUALITY] o a mo e de ailed a gumen o his posi ion.
A ale o ou decode s
Ha ing iden i ied he ailings in he o iginal design o he AIS p o ocol, and explained how hese
cause p oblems and how bes o a oid hem, we shall nex examine he ways in which AIS’s
design de ec s hinde ed he de elopmen o ac ual AIS decode s, and how he au ho s coped.
The au ho s ha e w i en ou AIS decode s in h ee di e en languages. We desc ibe hem he e
in his o ical o de .
To pu his lis in pe spec i e, i should be no ed ha AIS decode s a e a a e species o
so wa e. Web sea ches u n up ew hi s, and mos o hose only in e p e a subse o he
na iga ional message ypes a he han co e ing he ull ITU1371 s anda d and ex ensions. I is
likely ha he implemen a ions we lis he e ep esen a subs an ial ac ion o all he decode s in
exis ence ha a e a o nea ull con o mance.
noaada a
Noaada a was designed p ima ily as a esea ch ool o explo e me hods o wo king wi h AIS
messages and he da a con ained wi hin he many message ypes. De elopmen began in ea ly
2007. Schweh chose o d i e his decode om a p o ocol-desc ip ion minilanguage. This
a chi ec u e was aimed a easy gene a ion o language-na i e pa se s and o he ools, including
SQL schema gene a o s and ansla ion ools o con aine o ma s such as GeoJSON and
YAML. A minilanguage-d i en pa se would also g ea ly educe he e o equi ed o suppo
new ITU-s anda d messages and expe imen al messages.
This o iginal a chi ec u al ision o noaada a disin eg a ed wi h he ho ible ine i abili y o a
G eek agedy unde he weigh o AIS’s speci ica ions. We will desc ibe he p ocess in some
de ail he e because i shows exac ly wha he downs eam cos s o in insic p o ocol complexi y
look like in ac ual p ac ice.
The i s majo design decision was wha p o ocol-desc ip ion language o use. Schweh
conside ed bu ejec ed ASN.1 and bdec, inding hem cumbe some and a poo i o AIS’s
ex emely bi -o ien ed layou . Schewh chose o design a specialized minilanguage exp essed
as a cus om XML applica ion. As he AIS message s anda d is w i en in MS Wo d and Excel as
ee o m English ex , he i s majo ask was o hand- ansla e he con en o he s anda d in o
a se o XML message-layou de ini ions.
An ini ial ba ie o ac ually doing any hing wi h he XML message de ini ions was ha XML
pa se gene a o s also p o ed cumbe some and poo ly sui ed o he ask. W i ing a comple e
XML schema in any o he h ee majo schema languages - [RelaxNG], [Schema on], XML
Schema De ini ion [XSD] - would ha e consumed mo e ime han a ailable o a single
esea che who had no expe ience in XML schemas. E en supposing he commi men o do so
could ha e been sus ained, DTDs o e so li le le e age as o be poin less o checking a
documen o ma as hea ily s uc u ed as he ask equi ed.
Ea ly e sions o noaada a he e o e used lxml, an elemen - ee XML API w i en in Py hon, o
di ec ly walk he XML ee o message de ini ions as noaada a decoded each incoming AIS
message. Bu while walking he XML ee du ing he ac ual pa sing is compac in e ms o
numbe o lines o code, i is ex emely slow. La e e sions o nooada a add essed he
pe o mance p oblem by spli ing he pa se in o wo s ages: a code gene a o ead he XML
and emi ed s a ic Py hon code ha could decode and encode AIS messages.
The code-gene a ion p ocess added i s own laye o complexi y. The gene a o uses he FIX
empla ing language, b inging he numbe o o malisms being juggled o h ee (Py hon, XML,
FIX) and causing he p ocess o modi ying he Py hon ou pu o be mo e annoying han i should
ha e been.
A each s age in he p ocess, he in insic complexi y and i egula i y o AIS ende ed
inadequa e he ools o high-le el desc ip ion o he p o ocol and o ced Schweh in o using
p og essi ely mo e ad-hoc and complex implemen a ion me hods. No only did he XML
message de ini ions ail o cap u e AIS’s s uc u e, i g adually became appa en ha no
minilanguage wi h a desc ip ion complexi y subs an ially less han ha o a hand-coded pa se
could do so.
As he p ospec o an XML de ini ion language wi h he ull capabili y o handle all he odd
condi ional cases eceded, Schweh s a ed o o k copies o he gene a ed Py hon o add
suppo o condi ional da a based on alues in ields and inspec ing he leng hs o messages
when necessa y. This, o cou se, sub e ed he o iginal a chi ec u e.
By he ime Raymond w o e a c i ique o he code in 2009 o Schweh i was al eady clea ha
he noaada a codebase was ou o con ol. When ime came o implemen he IMO289
en i onmen and zone messages in la e 2010, he XML de ini ion sys em comple ely collapsed.
Nea he beginning o he de elopmen e o , Schweh and Alexande [IHO2007] had p oposed
an ini ial XML de ini ion language in an a emp o engage he AIS s anda ds communi y. While
pe sonal eedback om indi idual membe s o ha communi y was posi i e, he s anda ds
communi y ne e o mally engaged i , c i icized i , o helped de elop i . Tha lack o in e es pu
he seal on he collapse o he a chi ec u e, emo ing he mo i a ion o any escue e o .
All o he p oblems wi h noaada a ha we ha e desc ibed so a we e en ailed by he design o
AIS. I is wo h no ing one o he ha is pe haps mo e a unc ion o implemen a ion: despi e a
good deal o e o pu in o ime op imiza ion, he code is oo slow. As o ea ly 2011 i canno
handle eal ime da a om he NAIS ne wo k eed.
A la ge po ion o his speed issue comes om using he pu e Py hon Bi Vec o lib a y
[Bi Vec o ]. While his lib a y makes wo king wi h bi s e y easy, i is no designed o speed. In
2009 Raymond eimplemen ed he Bi Vec o in e ace using Py hon’s a ay ype and achie ed
subs an ial pe o mance gains, bu i s ill p o ed a bo leneck in his Py hon decode , sugges ing
ha we’ll need a ew mo e cycles o Moo e’s Law be o e any an in e p e ed language is up o
mee ing he h oughpu equi emen s o his ask.
This pe o mance p oblem could be add essed by c ea ing a cBi Vec o implemen a ion ha
p esen s he same in e ace, bu knows how o e icien ly c ea e sub-slices o bi ec o s using
copy-on-w i e s o age managemen .
Despi e all hese sys emic p oblems, noaada a has p o en success ul as a esea ch ool:
gene a ing es cases o AIS lib a ies, c ea ing ini ial SQL da abase de ini ions, demons a ing
he po en ial o XML de ini ions o p oduce mo e iendly HTML documen a ion wi h an XSLT
ans o ma ion, demons a ion o how a egis y could enable all so wa e endo s o handle an
explosion o AIS message ypes, explo ing he concep o au oma ic es ing o new message
p oposals, and so o h.
The noaada a sui e was also ex emely use ul in he p ocess o alida ing he nex wo decode s
we shall examine.
Noaada a also sugges ed s a egies o op imiza ion o AIS da a p ocessing based on he ask
a hand. Fo example, acking ships in eal ime migh only equi e p ocessing a small po ion o
he class A and B messages. I he ex e nal ime s amp can be us ed (no always he case in
NAIS), hen he e may be no need o look a he iming da a o quick-look isualiza ions. Deep
s a is ical analysis o AIS da a equi es looking a mos o all o he da a on he channel o
unde s and which da a can be used and wha p oblems mus be add essed in he analysis.
GPSD
GPSD is an open-sou ce moni o ing daemon o GPSes and o he kinema ic/geode ic senso s.
I u ns he aw ake om senso s in o JSON messages on a well-known TCP/IP po , insula ing
clien applica ions om he g ubby de ails o endo p o ocols and ha dwa e qui ks. Besides
being a s ock piece o in as uc u e on Linux and *BSD lap ops unning loca ion-awa e
applica ions, i is ex emely widely deployed in embedded sys ems including cellphones,
scien i ic eleme y packages, and au onomous obo ic ehicles including a DARPA G and
Challenge en y and he Woods Hole Ins i u e’s deep-di ing Ne eus subma ine.
One o us (Raymond) de eloped an in e es in AIS h ough GPSD, o which he is he p ojec
lead. He began wo k on suppo ing senso s epo ing AIVDM/AIVDO in GPSD in 2009, and
compiled [RAYMOND1] as pa o his e o o pull oge he enough in o ma ion o do a p ope
implemen a ion. Schweh con ibu ed ad ice and es loads, and he au ho s became
acquain ed h ough coope a ing o imp o e his so wa e.
The GPSD AIVDM d i e is implemen ed in app oxima ely a housand lines o C. A ime o
w i ing i has es ed suppo o AIS message ypes 1-15, 18-21, and 24. I has un es ed suppo
o ypes 16-17, 22-23, 25-27 and mos o he IMO ex ension messages, many o which ha e
no ye been obse ed in he wild. Con o mance was es ed by compa ison wi h epo s om
Schweh ’s noaada a d i e ope a ing on samples om [AISHUB] and elsewhe e.
Mos o he d i e is hand-coded, because a he ime i was cons uc ed he au ho belie ed AIS
was oo i egula o an a emp a d i e code gene a ion based on a p o ocol speci ica ion o
wo k. This belie was based pa ly on expe ience wi h Schweh ’s noaada a code.
Howe e , in ea ly 2011 Raymond buil a small sui e o code gene a o s ha ake any
message-layou able om [RAYMOND1] as inpu and gene a e snippe s o C and Py hon code
as ou pu . These snippe s include a C s uc u e decla a ion o he unpacked message da a,
and d i e code o ex ac he bi s in o he s uc u e. While hese code gene a o s canno
p oduce all o he he high-le el logic equi ed o he AIVDM d i e , hey do eliably au oma e
he mos iddly and de ec -p one pa s o da ag am analysis.
The design p oblems o AIS ha e no p e en ed his d i e om pa sing he ull ange o
message ypes, mainly because hand-coded C allows an app oach o using b u e o ce o
o e powe hose p oblems. The esul ing code is ha dly elegan , bu i wo ks o p oduc ion
uses.
The in insic complexi y o AIS has aken i s oll, howe e . GPSD epo s AIS sen ences as
equi alen JSON objec s. GPSD ships a lib a y o C clien applica ions ha unma shals he
JSON in o C s uc u es, using a cus om JSON pa se ha uses only s a ic-ex en s o age. The
JSON gene a ed by ce ain IMO ex ension messages (no ably A ea No ice and En i onmen al)
is so complex ha he lib a y JSON pa se b eaks on i and p obably canno be ex ended o
wo k wi hou using dynamic s o age.
As o May 2011 he GPSD AIVDM d i e is he mos capable AIS decode a ailable in open
sou ce. Despi e he d i e ’s p oblems and limi a ions, ield expe ience wi h o he
implemen a ions and he known di icul y o con o ming wi h he mu kie co ne s o he AIS
s anda ds cause he au ho s o s ongly suspec ha he GPSD AIVDM d i e is he mos
capable AIS decode a ailable anywhe e. The au ho s a e no pleased o eassu ed by his
e alua ion, conside ing i mainly a e lec ion o he shambolic s a e o he AIS s anda ds.
ais.py
ais.py is an undis ibu ed de elope ool in he eposi o y o he GPSD p ojec . Raymond w o e i
as a check on he p ojec ’s C decode , using as di e en an implemen a ion s a egy as he could
imagine and a emp ing o a oid noaada a’s p oblems. I is no in ended as a p oduc ion ool.
ais.py is app oxima ely a housand lines o Py hon code, which includes ex ensi e
epo -gene a ion ea u es as well as he da ag am analysis. Mos o he code consis s o lis s o
decla a ions in a iny domain-speci ic language adap ed o desc ibing he layou o AIS
da ag ams; hese a e in e p e ed by 250 lines o a ela i ely simple execu ion loop.
While his app oach is a mo e elegan han ad-hoc C code and in many ways mo e success ul
han noaada a, i uns headlong in o AIS’s design e o s. The execu ion loop is essen ially a
ecu si e s eam pa se and canno handle he pos -posi ioned dispa ch ield in message ype
22. I canno me ge he A and B pa s o message ype 24. I canno handle he embedded
a iable-leng h s ing ield in message ype 26 ( hough his could be ixed ela i ely easily by
ex ending he mini language). I handles he spli s ing ield in message ype 21 only ia a
a he emba assing kluge. And i does no handle he IMO specials o ype 6 and 8 a all.
As wi h noaada a, ais.py shows ha in a collision be ween decla a i e speci ica ion and he ugly
eali ies o AIS, decla a i e speci ica ion does no a e e y well.
ais.py also has a pe o mance p oblem un ela ed o AIS complexi y; on PC ha dwa e gene ally
a ailable a p esen (May 2011) i is no as enough o handle a eal- ime s eam om AISHub.
This is an issue wi h he pe o mance o bi - ec o ope a ions unde Py hon, and would p obably
be eplica ed in any o he sc ip ing language.
libais
Libais is a C++ hand coded pa se o AIS messages. I was w i en o eplace noaada a o he
ERMA / GeoPla o m esponse o Deepwa e Ho izon [Schweh 2011] when noaada a was no
able o keep up wi h he eal ime olume o AIS a ic om 5000 essels in he NAIS ne wo k.
The design is a hand-w i en, e y simple objec -o ien ed class ee using inhe i ance. A
CPy hon in e ace is p o ided ha e u ns a dic iona y o each AIS message.
D awing lessons om he implemen a ions
Lesson: Do a e e ence implemen a ion be o e you publish an applica ion p o ocol as a
s anda d.
No applica ion p o ocol wi h as many design p oblems as AIS has would ha e made i ou o
commi ee i a e e ence decode had been in de elopmen in pa allel wi h he speci ica ion;
implemen a ion p oblems would ha e h own hem in o sha p elie .
The IETF (In e ne Enginee ing Task Fo ce) has a cus om o no allowing a ne wo k p o ocol
design o be published as a p oposed s anda d un il i has a leas wo con o ming
implemen a ions. This would be a good p ac ice o e e yone else o emula e.
We would go e en u he and say ha as a bes p ac ice, he e e ence implemen a ion should
be open sou ce. In his way, hi d pa ies can see exac ly wha deg ee o complexi y is equi ed
o implemen he s anda d, exe ing a aluable p essu e owa ds simplici y.
Lesson: Design you p o ocol wi h a small and consis en se o idioms
Bo h o he au ho s had plans o gene a e an AIS decode wi h a leas condi ionally p o able
co ec ness om a decla a i e speci ica ion. Bo h e o s ( he noaada a decode and ais.py)
ailed because AIS is jus plain oo i egula o be cap u ed his way.
We ecommend ha applica ion-p o ocol designe s should, as a ou ine pa o hei p ocess,
ende he design as a speci ica ion in [ASN.1] o [BDEC]. I his p ocess is pain ul and complex,
w i ing a decode will also be pain ul and complex, and he design should be conside ed b oken
un il ha is ixed.
Lesson: Ship you s anda d wi h es pai s.
Bo h au ho s ind ha , e en as mis-designed as pa s o AIS a e, he single mos us a ing
hing abou w i ing AIS decode s is no any one o hose design p oblems o e en all o hem
oge he . The wo s p oblem is ou inabili y o e i y ha he code we w i e is co ec .
This p oblem could be qui e easily be ixed by a aching o he s anda d a se o es pai s - ha
is, an example bina y da ag am in each o e e y possible a ia ion o message shape oge he
wi h a ex ual, human- eadable decode o ha da ag am.
Shipping es pai s wi h a s anda d has pa icula impo ance in applica ion p o ocols o
li e-c i ical so wa e, whe e mis akes can easily kill. Bu i ’s good p ac ice e e ywhe e. The
combina ion o o icial es pai s wi h an open-sou ce e e ence implemen a ion is he mos
e ec i e means we know o o ensu e ha a s anda d is implemen ed co ec ly and comple ely.
Lesson: Closed, paywalled s anda ds endange li es.
While w i ing ou decode s we had occasion o e alua e abou a dozen o he s. Fo some, such
as [GNU-AIS], we could ead sou ce code; o o he s, we could only see sample esul s and
ead documen a ion.
The comple eness and co ec ness o hese implemen a ions was gene ally poo . Mos could
handle only a small subse o he AIS messages - ypically 1, 2, 3, and 5. We ound bugs on
e en he mos supe icial examina ion. I quickly became e iden ha hese limi a ions we e a
esul o he ac ual s anda ds being ela i ely expensi e and inaccessible; implemen e s had
been educed o ying o e e se-enginee he s anda d om in o ma ion ha had leaked ou
abou i , and no uncommonly made e o s in doing so.
While ha si ua ion was alle ia ed by he publica ion o [RAYMOND1] and la e by an ITU policy
change ha made [ITU1371] a ailable as a ee download, hose poo implemen a ions a e s ill
wi h us. Someday, incau ious use o one o hem migh well kill somebody.
The lesson is clea . Making a s anda d expensi e o ge damages he quali y o a emp ed
implemen a ions. This is la -ou unaccep able when he s anda d is li e-c i ical. E en when i is
no , we can expec he cos s and damages imposed by paywalling o g ea ly exceed he
maximum e enue anyone can e e expec o collec om i ; he economis ’s concep o
"deadweigh loss" applies wi h pa icula o ce he e.
Ways o wa d o AIS
The AIS p o ocol’s design p oblems will no be easily sol ed. Implemen a ions a e widely
dispe sed and o en di icul o access o i mwa e upg ades, so he deploymen p oblem is
signi ican . Some majo de ec s, such as he handling o s ing da a, a e oo deeply embedded
o be emo ed. Bu he e a e s eps ha could be aken o imp o e he quali y o decode s and
p e en u he p oli e a ion o dange ous complexi y.
A i al i s s ep would be publica ion o a de ini i e se o es pai s in conjunc ion wi h he
s anda d and any u u e ex ensions. The ITU should also manda e ha all ex ensions by
ju isdic ion au ho i ies also publish comple e se s o es pai s. Wi h such a con o mance sui e o
es agains , quali y and b ead h o con o mance in AIS decode s would imp o e d ama ically
and apidly.
The single poin de ec wi h he la ges ipple e ec on complexi y o implemen a ion is p obably
he pos -posi ioned dispa ch ield in message ype 22. Dep eca ing his message and eplacing
i wi h a be e -s uc u ed one would e en ually enable a signi ican educ ion in decode
complexi y.
Mos o he es o ou guidance o designe s o u u e AIS messages should be ob ious om
he design ules we’ e poin ed ou . Dispa ch ields a e complexi y poison, so keep hem o a
ba e minimum; don’ spli s ing ields; a oid ields wi h a iable o se s; don’ spli message
layou s ac oss mul iple da ag ams.
Again, li e-c i ical sys ems concen a e he mind wonde ully. We canno s ess s ongly enough
ha , in an applica ion domain like AIS’s, bad p o ocol-design decisions a e no me ely annoying
bu , because o he way hey eed h ough in o inc eased code complexi y and de ec a es,
ac ually dange ous.
Re e ences
(Incomple e)
● [RAYMOND1] AIVDM/AIVDO P o ocol Decoding
● [ITU1371] ITU Recommenda ion on he Technical Cha ac e is ics o a Uni e sal
Shipbo ne Au oma ic Iden i ica ion Sys em (AIS) using Time Di ision Mul iple Access in
he Ma i ime Mobile Band.
● [IMO236] IMO Ci cula 236: Guidance on he Applica ion o AIS Bina y Messages (May
2004)
● [IMO289] IMO SN.1/Ci c.289 Guidance on he Use o AIS Applica ion-Speci ic Messages
(June 2010)
● [CATB] The Ca hed al and he Bazaa
● [IEC-PAS] IEC-PAS 61162-100, "Ma i ime na iga ion and adiocommunica ion
equipmen and sys ems" The ASCII a mo ing is desc ibed on page 26 o Annex C, Table
C-1.
● [AISHUB] AIS Hub, he AIS da a sha ing cen e
● [TEXTUALITY] The Impo ance o Being Tex ual.
● [ASN.1] ASN.1
● [bdec] bdec
● [GNU-AIS] GNU AIS - Au oma ic Iden i ica ion Sys em o Linux
● [MMM] B ooks, J. F ed (1995) "The My hical Man-Mon h: Essays in So wa e
Enginee ing", Addison-Wesley, ISBN 0-201-83595-9.
● [ASU] Aho, A.V., Se hi, R. and Ullman ,J.D. (1986) "Compile s: p inciples, echniques,
and ools." Addison-Wesley Longman, ISBN 0-201-10088-6.
● [IALA2004] FIX
● [LANS1996] Hakan Lans, “Posi ion indica ing sys em,” Pa en US5506587A
