|
|
| |
|
|
| |
|
AN #174 - Kixlines - Tetrasexagesimal number compression to speed up serial communication |
|
by Natalius Kiedro
' _ _ _ _
' | | _(_)_ _| (_)_ __ ___ ___
' | |/ / \ \/ / | | '_ \ / _ \/ __|
' | <| |> <| | | | | | __/\__ \
' |_|\_\_/_/\_\_|_|_| |_|\___||___/
'
' A tetrasexagesimal number format
' and how to compress numbers for
' standard serial communication.
'
' by Natalius Kiedro, March 2010
' Natalius272 at yahoo dot de
'
' _________________________________________________________________________
' |Please direct questions on Kixline applications to the AR7212 subforum of|
' |the BASCOM forum. Non commercial code utilization only. Commercial utili-|
' |zation requires contacting the author via the email address given above. |
' ===========================================================================
'
' Keywords: KIX kixlines coding encryptation GPS AHRS IMU AR7212 autopilot
'
'
' Summary
' =======
' Kixlines contain numbers on the base/radix 64. Numbers are converted into the
' tetrasexagesimal KIX format by taking consecutive chunks of 6 bits from the LSB
' side of 1 byte, 2 bytes (words/integers) or 4 bytes (long integers) and assigning
' these chunks to readable ASCII characters. This is similar to Base64-encoding; KIX
' however uses an alphabet which is linearily mapped to the order of characters in the
' ASCII alphabet. KIX digits range from "0" (ASCII48) to "o" (ASCII 48+63 = 117).
' This note introduces elementary operations for the encoding and decoding of KIX-
' based numbers in various number types. Transparent ASCII-based number are often
' very space consuming. A NMEA 183 message, for example, used for GPS strings may
' take more than 70 bytes for just a few numbers. On the other side, the binary format
' needs input-output software different from what is used for standard ASCII and is
' often more cumbersome than standard text I/O. KIX can be understood as an expanded
' HEX with 6 instead of 4-bit-"nibbles". By choosing proper variable types, KIX can
' be as space-efficient as binary while being readable and printable by standard textI/O.
' KIX is recommended for situations where data exchange between components of a system
' is rate limiting as compared to the processing of data within such components.
' Such situations often arise in wireless networks or bandwidth shared point to point
' connections, such as telemetry and remote controlled applications. As example it is
' shown how to compress $GPGGA and $GPRMC for RC-flight applications.
'
' Indroduction
' ============
' Code standards have something special. Once they are fixed they don't evolve anymore.
' Only little changes might occur. The oldest example we know is the genetic code which
' was fixed around 3+/-1 gigayears ago. Nobody knows exactly when, where, and why. The
' code assigns triplets of bases in DNA to amino-acid "letters" in proteins. It
' contains "control characters" such as those for the start and stop of a genetic
' message to be translated into a protein. Once the code was fixed, cellular life (as
' we know it) started to evolve on our planet. Code fixation events seem to enable new
' ways of doing things, let systems interchange information with other systems in a
' different way. What would we do, for example, without ASCII and HEX today?
'
' Standard ASCII defines a 7 bit code, as only the lower characters (0..127) are
' really "fixed". Many "standards" exist for the upper 127 characters, mainly due to
' the fact that diffent human languages also require different characters. Attempts
' to unify things (e.g. Unicode) necessarily have to leave the 8-bit coding range.
' While "localization" above 8-bit is acceptable for characters describing human
' languages, "the language of numbers" should be universal and print on a Japanese
' computer exactly as on a French, Canadian one Russion ones. Standard ASCII just
' offers the digits "0" to "9", as well as seperators like comma, space, and dots
' which already come with a context-dependant meaning. For example, decimal seperators
' like dots and commas are context-dependant; American and German bankers reverse
' their meaning. The only universal standard for representing numbers - only binary
' numbers however - is HEX using the digit "0..9" and "A..F".
'
' The goal of kixlines is to have a number format which is text-processable
' like HEX and standard ASCII but more compact than these format. If we reserve 6 bit
' of information for a digit (64 characters), we have the lower 32 control characters
' of ASCII to maintain compatibility with standard text I/O, and further 31 characters
' to encode "meaning". As a result of "meaning characters" or the latters missing,
' Kixlines may look (and then in a way are) encrypted as:
'
' hg500Ab:Ac8U;xCbTVaDA19FhkRoM5fg[/__0R>
'
' as well as "structured" similar to HEX:
'
' 0[Ga cB@b 01A` 000o 0[0] 0000 oooo 0F0F
'
' Each 4-character item in the latter line represents 3 bytes of information.
' What is fascinating to me is the fact that the genetic code is also a tetrasexa-
' gesimal one - the total number of possible base tripletts is 64 - only twenty of
' these encode amino acids.
'
' The KIX digit alphabet
' ======================
' The following table shows the ordering of KIX digits mapped to ASCII/DEC and HEX:
'
' SYM KIX ASC HEX SYM KIX ASC HEX SYM KIX ASC HEX SYM KIX ASC HEX
' 0 0 48 30 @ 16 64 40 P 32 80 50 ` 48 96 60
' 1 1 49 31 A 17 65 41 Q 33 81 51 a 49 97 61
' 2 2 50 32 B 18 66 42 R 34 82 52 b 50 98 62
' 3 3 51 33 C 19 67 43 S 35 83 53 c 51 99 63
' 4 4 52 34 D 20 68 44 T 36 84 54 d 52 100 64
' 5 5 53 35 E 21 69 45 U 37 85 55 e 53 101 65
' 6 6 54 36 F 22 70 46 V 38 86 56 f 54 102 66
' 7 7 55 37 G 23 71 47 W 39 87 57 g 55 103 67
' 8 8 56 38 H 24 72 48 X 40 88 58 h 56 104 68
' 9 9 57 39 I 25 73 49 Y 41 89 59 i 57 105 69
' : 10 58 3A J 26 74 4A Z 42 90 5A j 58 106 6A
' ; 11 59 3B K 27 75 4B [ 43 91 5B k 59 107 6B
' < 12 60 3C L 28 76 4C \ 44 92 5C l 60 108 6C
' = 13 61 3D M 29 77 4D ] 45 93 5D m 61 109 6D
' > 14 62 3E N 30 78 4E ^ 46 94 5E n 62 110 6E
' ? 15 63 3F O 31 79 4F _ 47 95 5F o 63 111 6F
'
' The symbols "0".."o" are assigned to KIX-values 0..63 (ASCII 48..11 or 30..6F in
' HEX) making up a tetrasexagesimal number scheme.
'
' Base-64 coding has been previously employed (e.g. for generating MIME
' attachments in Emails) or within data encryptation (e.g. PGP). The base-64
' alphabet which is in use in these schemes however starts with capital "A" as
' zero and puts the decimal digits to the high side of Base-64-digits followed by
' "+" (ASCII 43) and "/" (ASCII 47). This is inconsistent with the ordering of
' ASCII which puts "0..9" (ASCII 48-57) before "A..Z" (ASCII 65-90) followed by
' "a..z" (ASCII 97-122). To decrease the overhead of coding and decoding and to
' make things as straightforward as possible, digits in the KIX alphabet reflect
' ASCII order directly. Decoding a KIX digit from ASC only means the substraction
' of 48 while coding means just the addition of 48. The absence of any further
' analysis per digit makes the KIX format particularily attractive for the com-
' pression of numbers on small microcontrollers.
'
' Unfortunately, ASCII is not grouped in a way that capital and small letters
' follow the decimal digits directly. This is due to the fact that the English
' language has 26 instead of 32 letters. This in turn caused that the ASCII fathers
' needed to fill the gaps with special characters that don't appear to us (as
' humans) as "ordered" as the "ABC" or the "0..9" we learn as childs in the first
' school days. We need "fool's bridges" to memorize special characters. Here are
' two "fool's bridges" for characters which separate decimal digits from capital
' letters, and for characters between capital and small letters. These are:
'
' :;<=>?@ "Eyes with a smile are smaller, equal, or larger than
' questions in emails"
'
' [\]^_` "My home has a left wall, stairs, a right wall, a roof,
' a basement, and a chimney"
'
' If one now remembers:
'
' "Digits have no eyes but capital letters have a home for small letters"
'
' one has got an idea how ASCII symbols are ordered in the range of the KIX digits;-)
'
'
' Let's start: How to encode numbers in KIX?
' ==========================================
' Here is source snippet in BASCOM. Let us assume that the integer array Master()
' contains numbers between -384 and +384, and that Master(Dx7throttle) is -350. Iby,
' Jby, Kby, Lby, ..., Iwo, Jwo, Kwo, Lwo... are what I like to call "general over-
' writables", viz. globals that are used for temporary storage over and over again.
' This helps to speed up BASCOM and to keep the code rather small.
'
' Iwo = 512 ' Iwo = 512
' Iwo = Iwo + Master(dx7throttle) ' Iwo = 512 - 350 = 162 = &B0000000010100010
' Jwo = Iwo And &B0000000000111111 ' Jwo = &B0000000000100010 = 34
' Kwo = Iwo And &B0000111111000000 ' Kwo = &B0000000010000000 = 128
' Rotate Kwo , Right , 6 ' Kwo = &B0000000000000010 = 2
' Jby = Jwo ' Jby = &B00100010 = 34
' Jby = Jby + 48 ' Jby = 34 + 48 = 82
' Kby = Kwo ' Kby = &B00000010 = 2
' Kby = Kby + 48 ' Kby = 2 + 48 = 50
' Lst = Chr(kby) + Chr(jby) ' Lst = "2";"R"
' Print #2 , Lst; ' ====> 2R
'
' So, -350 comes out as 2R, 2 characters less. The binary format would also use 2 bytes.
' Of course, the addition of 512 in the beginning requires your knowledge that the
' numbers in the array are less than 10bit - if the receiving end shares this knowledge
' as a "code key", it will add the 512 to the decoded 2R to arrive at -350.
'
' There are numerous ways to improve the snippet. More elegant is a dedicated
' byte array instead of the general overwritables kby and jby. If this is overlayed
' with an ASCIIZ string, the BASCOM CHR conversion and string concatenation does not
' need to be carried out anymore. More efficient is to do the bit shifting and the
' logical AND using $ASM...
'
' Here is another example. Imagine that you have converted GPS-time from NMEA into the
' long integer Ggatime with millisec resolution. Do it for yourself (one time please)
' manually - what is the KIX outcome, if Ggatime is 42123456?
'
' Ilo = Ggatime / 10
' Jlo = Ilo And &B00000000000000000000000000111111
' Klo = Ilo And &B00000000000000000000111111000000
' Llo = Ilo And &B00000000000000111111000000000000
' Mlo = Ilo And &B00000000111111000000000000000000
' Rotate Klo , Right , 6
' Rotate Llo , Right , 12
' Rotate Mlo , Right , 18
' Jby = Jlo
' Jby = Jby + 48
' Kby = Klo
' Kby = Kby + 48
' Lby = Llo
' Lby = Lby + 48
' Mby = Mlo
' Mby = Mby + 48
' Lst = Chr(mby) + Chr(lby) + Chr(kby) + Chr(jby)
' Print #2 , Lst;
'
' Variable Types recommended for KIX
' ==================================
' The low granularity of current variable types (1,2,4,8 byte-wise: byte, word/integer,
' long, ...) is optimal for the data processing in current computers but is expected to
' be suboptimal if not the processing but the transmission of data is the overall
' bottleneck of a multi-component system. 6-bit-chunks of data can lead to a more
' fine-grained structuring of number space than 8-bit chunks, especially when the
' latter are concatenated in an exponential (1,2,4,8,..) instead of linear
' (1,2,3,4,5,6,7,8) fashion. For a digital computer it makes perfect sense to go the
' exponential road, but I/O of numbers may enjoy higher granularity, especially if we
' look at microcontrollers in sensor-networks, wireles remote control and such things.
' This in turn, requires more types of variables to be defined.
'
' So lets go the practical way: Instead of defining number space by bytes/word,integers/
' longs/single/double or whatsoever, let us use multiples of 6-bit characters to do it.
' Remember that every digit holds a number between 0 and 63, so:
'
' Type KW1, range : 0 to o (= 0 to 63)
' KW2, range : 00 to oo (= 0 to 4095)
' KW3, range : 000 to ooo (= 0 to 262143)
' KW4, range : 0000 to oooo (= 0 to 16777215)
' KW5, range : 00000 to ooooo (= 0 to 1073741823)
' KI1, range : 0 to o (= -31 to +31)
' KI2, range : 00 to oo (= -2047 to +2047)
' KI3, range : 000 to ooo (= -131071 to +131071)
' KI4, range : 0000 to oooo (= -8388607 to +8388607)
' KI5, range : 00000 to ooooo (= -536870911 to +536870911)
'
' KW1 means a KIX word with one character, KWn for n characters accordingly.
' KI1 means a KIX integer with one characters, KIn for n characters
' accordingly.
'
' The above types should hold for a while. If not, just expand them whenever needed.
' As microcontrollers and embedded computers typically do not need to deal not with
' really huge numbers (such as the number of hydrogen atoms in our universe, 1E+80)
' floating point numbers can be encoded in a more realistic fixed point format. Well,
' if not, you are free to define your own KF12 format.
'
' Comma or Comma-free?
' ====================
' The genetic code is an example for a "comma free" code - base triplets called codons
' are concatenated without seperators. I borrowed the term just to indicate absence of
' seperators not necessarily commas (literally).
'
' Transparent formats such as NMEA 183 often contain separators such as commas or spaces
' to let us read such messages directly. "Readable HEX" also contains blanks to help us
' recognizing which nibble belongs to which byte. KIX can be as readable as HEX if we
' put blanks between numbers - as in the example above. This however gives sense only
' for the representation of binary information - although it helps to compress readings.
' Strings of 4 characters compress exactly 3 bytes of information, simply because 3 * 8
' = 4 * 6.
'
' My recommendation is to use the remaining readable characters of the ASCII Alphabet
' to encode "meaning". These characters are:
'
' SP!"#$%&'()*+,-./ (ASCII 32..47),
' pqrstuvwxyz{|}~ (ASCII 112..126)
'
' The following as number-preceeding seperators indicating the type and format of the
' next KIX number:
'
' SP (ASCII 32) for a "binary" KIX format grouped in 4 characters
' encoding 3 bytes as well for word based (ordinal,
' non-signed) KIX numbers of type KW1..KW5
' ! (ASCII 33) for KIX integers KI1..KI5
'
' Kixlines to be processed using standard ASCII-I/O should be identifyable at least by
' a stop character. Reserve:
'
' <CR> (ASCII 13) as the stop character.
'
' The remaining characters may find applications at a later stage. They may encode
' fixed formatting of words or integers to be interpreted as fixed-point numbers.
' They may encode logical or arithmetic operations on Kix numbers or they may encode a
' given type of message for the kixline. Once the general idea has been grasped, there
' is plenty of room to define new contexts.
'
' One of the most foreseeable application of KIX numbers are comma-free kixlines. These
' allow two things: Compression combined with "poor man's encryptation". Comma-free
' kixlines are smaller and faster to process on small microcontrollers but require
' the knowledge how the digits are grouped into individual numbers on both the sender's
' and the receiver's side. This knowledge define a second layer of coding/decoding
' which can be described as a table.
'
' Here is an example:
' -----------------------------------
' NR ITEM TYP POS LEN .XX
' -----------------------------------
' (1) GUI characters (CHR , 1 , 4 , 0)
' (2) Warning dec (DEC , 5 , 1 , 0)
' (3) Signal dec (DEC , 6 , 1 , 0)
' (4) Autonomous dec (DEC , 7 , 1 , 0)
' (5) Flightmode dec (DEC , 8 , 1 , 0)
' (6) Master Thr (KW2 , 9 , 2 , 0)
' (7) Master Ail (KW2 ,11 , 2 , 0)
' (8) Master Ele (KW2 ,13 , 2 , 0)
' (9) Master Rud (KW2 ,15 , 2 , 0)
' (10) Bat_V (KW3 ,17 , 3 , 2)
' (11) Bat_I (KW3 ,20 , 3 , 2)
' (12) Temp (KI2 ,23 , 2 , 1)
' (13) RPM (KW3 ,25 , 3 , 1)
' (14) Airspeed (KW3 ,28 , 3 , 1)
' (15) Pulse (KW2 ,31 , 2 , 0)
' (16) reserved (KW2 ,33 , 2 , 0)
' (17) GPS time (KW4 ,35 , 4 , 2)
' (18) Dlate (KI3 ,39 , 3 , 1)
' (19) Dlone (KI3 ,42 , 3 , 1)
' (20) Dalte (KI3 ,45 , 3 , 1)
' (21) roll (KI2 ,48 , 2 , 1)
' (22) pitch (KI2 ,50 , 2 , 1)
' (23) yaw (KI2 ,52 , 2 , 1)
' (24) speed over gnd (KW3 ,54 , 3 , 1)
' (25) Nsat (KW1 ,57 , 1 , 0)
' (26) Horiz Dil (KW2 ,58 , 2 , 1)
' (27) Fix (DEC ,60 , 1 , 0)
' (28) reserved (KW4 ,61 , 4 , 0)
' (29) * (CHR ,65 , 1 , 0)
' (30) Checksum (HEX ,66 , 2 , 0)
'
' Note that such Kixlines may contain information outside KIX words and integers:
' "Printable" CHR (ASCII 32..126), DEC (ASCII 48..57), and HEX (ASCII 48..57, 61..66).
' The latter require the substring lenght LEN which is redundant at the level of
' KIX-types. POS is also redundant as it is given by the sum of previous LENs.
' XX in the table defines how many decimal digits follow after the decimal seperator.
'
' Decoding simple Kixlines
' ========================
' If the receiving end is a PC - e.g. connected via a wireless link to the Kixline
' sender - one can do it like in the snippets below (PBWIN8.0). The Kixline is first
' handled to a KIX parser which uses the above table as a "codec" information. The
' parser calls a KIX analyzer which converts the actual KIX number into its decimal
' pendant:
'
' SUB Kixparse (BYVAL Kixline AS STRING)
' ..
' CALL Kixalyze ("DEC" , 5 , 1 , 0) : Warning = Kixlng
' CALL Kixalyze ("DEC" , 6 , 1 , 0) : Signal = Kixlng
' CALL Kixalyze ("DEC" , 7 , 1 , 0) : Autonomous = Kixlng
' CALL Kixalyze ("DEC" , 8 , 1 , 0) : Fltmode = Kixlng
' CALL Kixalyze ("KW2" , 9 , 2 , 0) : JoyU = Kixlng
' CALL Kixalyze ("KW2" ,11 , 2 , 0) : JoyX = Kixlng
' CALL Kixalyze ("KW2" ,13 , 2 , 0) : JoyY = Kixlng
' CALL Kixalyze ("KW2" ,15 , 2 , 0) : JoyZ = Kixlng
' CALL Kixalyze ("KW3" ,17 , 3 , 2) : BatV = Kixdbl
' CALL Kixalyze ("KW3" ,20 , 3 , 2) : BatA = Kixdbl
' ..
' END SUB
'
' SUB Kixalyze (BYVAL Kixins AS STRING, BYVAL Kixbeg AS LONG, BYVAL Kixlen AS LONG,_
' BYVAL Kixdec AS LONG)
' LOCAL Kix AS STRING, I1$, I2$, I3$, I4$, I$, J$, Kixnum AS LONG
' Kix = MID$(Kixline, Kixbeg, Kixlen)
' SELECT CASE Kixins
' CASE "CHR"
' Kixstr = Kix
' CASE "HEX"
' Kixlng = VAL("&H" & Kix)
' CASE "DEC"
' Kixlng = VAL(Kix)
' CASE "KW1"
' Kixlng = ASC (Kix) - 48
' CASE "KW2"
' Kixlng = ASC (MID$(Kix, 2, 1)) - 48
' Kixlng = Kixlng + 64 * (ASC (MID$(Kix, 1, 1)) - 48)
' CASE "KW3"
' Kixlng = ASC (MID$(Kix, 3, 1)) - 48
' Kixlng = Kixlng + 64 * (ASC (MID$(Kix, 2, 1)) - 48)
' Kixlng = Kixlng + 4096 * (ASC (MID$(Kix, 1, 1)) - 48)
' CASE "KW4"
' Kixlng = ASC (MID$(Kix, 4, 1)) - 48
' Kixlng = Kixlng + 64 * (ASC (MID$(Kix, 3, 1)) - 48)
' Kixlng = Kixlng + 4096 * (ASC (MID$(Kix, 2, 1)) - 48)
' Kixlng = Kixlng + 262144 * (ASC (MID$(Kix, 1, 1)) - 48)
' ..
' CASE "KI2"
' Kixlng = ASC (MID$(Kix, 2, 1)) - 48
' Kixlng = Kixlng + 64 * (ASC (MID$(Kix, 1, 1)) - 48)
' Kixlng = Kixlng - 2047
' CASE "KI3"
' Kixlng = ASC (MID$(Kix, 3, 1)) - 48
' Kixlng = Kixlng + 64 * (ASC (MID$(Kix, 2, 1)) - 48)
' Kixlng = Kixlng + 4096 * (ASC (MID$(Kix, 1, 1)) - 48)
' Kixlng = Kixlng - 131071
' ..
' CASE ELSE
' END SELECT
' Kixdbl = Kixlng * 10^-Kixdec
' END SUB
'
' If the receiving end is a microcontroller it is better to analyze the Kix number
' not by string processing and numerical operation but by bit shifting as follows.
' Let's assume that we are dealing with the KIX number "abcd", type KW4. Let us put
' this string into four (plus zero for ASCIIZ) consecutives bytes in memory:
'
'
' ASCIIZ -------a -------b -------c -------d 00000000
' ASCII (dec) 97 98 99 100
' Binary 01100001 01100010 01100011 01100100
' Byte Vars overlay V1 V2 V3 V4
' -48 for V1..V4 gives 00110001 00110010 00110011 00110100
' generally (A..D as bits) 00AAAAAA 00BBBBBB 00CCCCCC 00DDDDDD
'
' Rotate V2&V4 left, 2, gives 00110001 11001000 00110011 11010000
' generally 00AAAAAA BBBBBB00 00CCCCCC DDDDDD00
'
' Integer Vars overlay I1 I2
' Rotate I1 right, 2, gives 00001100 01110010 00110011 11010000
' Rotate I2 left, 2, gives 00001100 01110010 11001111 01000000
' generally 0000AAAA AABBBBBB CCCCCCDD DDDD0000
'
' Long Integer overlay L1
' Rotate L1 right, 4, gives 00000000 11000111 00101100 11110100
' generally 00000000 AAAAAABB BBBBCCCC CCDDDDDD
'
' example, decimal equivalent 13053172
' 100-48 +(99-48)*64 + (98-48)*4096 + (97-48)*262144 = 13053172
'
' If "abcd" were defined as KI4 one would need to substract 8388607 to arrive at the
' result. The above algorithm "evaporates" all of the two leading zeros in each byte
' just by simple bit shifting. For a KW5 number the operation would look as follows
' after the subtraction of 48 - here only in general form:
'
' After -48: 00AAAAAA 00BBBBBB 00CCCCCC 00DDDDDD 00EEEEEE
' C&E byte shifts 00AAAAAA 00BBBBBB CCCCCC00 00DDDDDD EEEEEE00
' I1&I2 shifts 00AAAAAA 0000BBBB BBCCCCCC DDDDDDEE EEEE0000
' L1 shift 00AAAAAA 00000000 BBBBBBCC CCCCDDDD DDEEEEEE
' A-byte copy 00AAAAAA 00AAAAAA BBBBBBCC CCCCDDDD DDEEEEEE
' Result in L1 00AAAAAA BBBBBBCC CCCCDDDD DDEEEEEE
'
' From an original ASCII string of 5 character we can thus generate numbers as
' large as 1073741823 with 10 decimal digits. What is now a bit confusing is that
' the order of bytes in memory does not reflect the logical order of a "humanized"
' bitstring as shown above. For us, the most significant bit of a bitstring is almost
' left. For AVR microcontrollers, the directions left and right are the same at the
' level of bits in a byte but reversed when it comes to the order of bytes. The most
' significant byte is at a higher address than the least significant one. Maybe that
' this "counterintuitive" ordering was seen by Atmel engineers when they introduced
' the Xmega line of processors with 16bit-registers.
'
' Application Example:
' ====================
' The following one brought me to think about Kixlines: Imagine that your micro is
' short in UARTs, that you have lots of sensors like those required for autonomous
' flight. In the AR7212x mentioned in AN#171, two UARTs are used for the 2.4 GHz
' satellites (unidirectional), one (bidirectionally) for a small commercially RC gadget
' called Unilog which brings in voltage, current, airspeed and altitude (from a baro-
' metric sensor), and one UART is shared for GPS (NMEA instream) and telemetry
' (outstream). Outstream is limited to an effective rate of 9600bps, not very much for
' the info specified in the above "codec" table. For a transmission of data as "real
' time" as possible, a more efficient packing of data sent to ground was a must.
' Recently Kixlines became even more attractive, as the "port sharing trick" may be
' also applicable for a new generation of MEMS-accelerometer/gyro/magnetometer sensors
' (e.g. CHRobotic's CHR6dm and Sparkfun's Razor) which deliver the Euler Angles (yaw,
' pitch, roll) usable for the autopilot in the AR7212x. Sensors which just "stream"
' (like the Razor) may enjoy sharing the UART with an GPS "instream".
' For "localized" GPS applications such as RC-flight a maximal spatial distance of
' +/-2047m is sufficient as even the largest electric glider will be hard to recognize
' more than 1Km away. The horizontal dilution (GPS error) usually exceeds 1m, so that
' a resolution of 1m seems adequate. A range of -2km to +2km just needs the KI2 format.
' The same format may encode Euler angles (yaw, pitch, roll) ranging from -180.0° to
' 180.0° or 0 to 360.0° alternatively. Text readable messages for transporting orientation
' or position may be thus as short of as 6 chars + Start + Stop = 8 characters. Roughly
' a tenth of a NMEA string. While positional information is 10 Hz max (about 800 bps),
' Euler angles will need an update every servo cycle (45 Hz equivalent to about 3600 bps).
' 4400 bps needed in toto max(!) should "just" fit into the 4800 bps of a rate-limiting
' standard GPS module. As the bottleneck and limitation of UART-sharing is the slowest
' device, Kixline messages should be no problem when using more advanced
' GPS equipment.
'
' The code below shows how to produce kixlines which code the difference of latitute,
' longitude and altitude in meters from the point where the GPS found its first fix.
' These data are taken from the NMEA $GPGGA messages. In addition it packs speed over
' ground and heading from $GPRMC into the kixline. You may run it without a GPS module
' in the Bascom simulator to see how it works. At the hardware side you just need a micro
' with ONE(!) UART. Connect it as follows to generate a hardware translator:
'
' nc _____________________ _____________________ nc
' | | | | | |
' ___|___|___ ___|___|___ ___|___|___
' | RX TX | | RX TX | | RX TX |
' | | | | | |
' | NMEA | | NMEA2KIX | | KIX |
' | Talker | |Translator | | Listener |
' | | | | | |
' |__Gnd_Vcc__| |__Gnd_Vcc__| |__Gnd_Vcc__|
' | | | | | |
' Vcc _____ | __|____________________ | __|____________________ | __|
' | | |
' Gnd ______|_________________________|_________________________|
'
'
' It is a straightforward task to have the translator also producing Kixline messages
' from its own sensors (e.g. for yaw, pitch, roll) - coding and decoding is fast!
'
'
$regfile = "m1280def.dat"
$crystal = 11059200
$hwstack = 64
$swstack = 32
$framesize = 64
Declare Sub Kixencode()
Declare Sub Kixdecode()
Declare Sub Loby2bin()
Declare Sub Findhome()
Declare Sub Ggaparse()
Declare Sub Rmcparse()
Declare Sub Homeset()
Declare Sub Gpstime2millisec()
Declare Sub Late_lone_dec_conversion()
Declare Sub Example()
Declare Sub Mainloop()
Const Kix2 = 2047 'for making KI2 integers
Const Kix3 = 131071 'for making KI3 integers
Const Kix4 = 8388607 'for making KI4 integers
Const Kix5 = 536870911 'for making KI5 integers
'General overwritables
Dim Iby As Byte , Jby As Byte , Kby As Byte
Dim Ilo As Long , Jlo As Long , Klo As Long
Dim Ist As String * 15 , Jst As String * 15 , Kst As String * 15
Dim Isi As Single , Jsi As Single , Ksi As Single , Lsi As Single
'Globals Kix
Dim Kixinlo As Long
Dim Kixlo(5) As Long
Dim Kixloby(6) As Byte
Dim Kixout As String * 5 At Kixloby(1) Overlay
Dim Kixinby(6) As Byte
Dim Kixin As String * 5 At Kixinby(1) Overlay
Dim Kixint1 As Integer At Kixinby(1) Overlay
Dim Kixint2 As Integer At Kixinby(3) Overlay
Dim Kixdeclo As Long At Kixin Overlay
Dim Kixlineout As String * 50
Dim Kixlinein As String * 50
Dim Intflag As Byte
'Globals Gps
Dim Gpsst As String * 80
Dim Commas(16) As String * 10
Dim Gpsreadyflag As Byte
Dim Rmcvalidflag As Byte
Dim Ggatime As Long
Dim Ggalate As Long
Dim Ggalone As Long
Dim Ggaalte As Integer
Dim Ggahode As Integer
Dim Ggafixe As Byte
Dim Ggasate As Byte
Dim Late2m As Single
Dim Lone2m As Single
Dim Hometime As Long
Dim Homelate As Long
Dim Homelone As Long
Dim Homealte As Long
Dim Rmcspeed As Long
Dim Rmcheading As Long
Dim Dlate As Long
Dim Dlone As Long
Dim Dalte As Long
Dim Dots(2) As String * 15
Dim Loopist As String * 1
Config Com1 = 4800 , Synchrone = 0 , Parity = None , Stopbits = 1 , Databits = 8 , Clockpol = 0
Enable Interrupts
Enable Serial
Example
''Coding and decoding of a kixline with five numbers up to the KI5/KW5 format:
''The transparent pendant might contain a total of 50 decimal digits. Even with so
''many digits, coding takes 591 µs - decoding takes 279 µs. This is roughly the
''time needed to calculate the distance D between 2 points in 3D space
''(D=SQR(DX*DX+DY*DY+DZ*DZ)) which takes 359 µs. Transporting a single 70 char
''NMEA message from the talker to the translator takes about 140 ms at 4800 bps,
''280 ms for both messages. The transport of the kixline excerpting these messages
''(12 characters) takes about 25ms from the translator to the listener, roughly a
''tenth of time needed for the NMEA messages. Encoding and decoding is negligible
''(less than 1 ms for both together).
'Mainloop
'Decomment mainloop if you want to play around with your own translator.
End
'*******************************************************************************
'********************************** Kix encoder ********************************
'*******************************************************************************
Sub Kixencode()
Kixlo(1) = Kixinlo And &B00000000000000000000000000111111
Kixlo(2) = Kixinlo And &B00000000000000000000111111000000
Kixlo(3) = Kixinlo And &B00000000000000111111000000000000
Kixlo(4) = Kixinlo And &B00000000111111000000000000000000
Kixlo(5) = Kixinlo And &B00111111000000000000000000000000
Jby = 0
For Iby = 1 To 5
Rotate Kixlo(iby) , Right , Jby
Jby = Jby + 6
Kby = Kixlo(iby)
Kixloby(iby) = Kby + 48
Next Iby
'Print Kixout
End Sub
'*******************************************************************************
'******** Kix decoder ********
'******** Copy this code + variable definitions to the Kixline listener ********
'*******************************************************************************
Sub Kixdecode
'Kixin = "dcba0"
'Print "0abcd"
'Loby2bin
For Iby = 1 To 5
Kixinby(iby) = Kixinby(iby) - 48
Next Iby
'Print "-48"
'Loby2bin
Rotate Kixinby(3) , Left , 2
Rotate Kixinby(1) , Left , 2
'Print "V3 & V5 left 2"
'Loby2bin
Rotate Kixint1 , Left , 2
Rotate Kixint2 , Right , 2
'Print "I1 Right2, I2 Left 2"
'Loby2bin
Rotate Kixdeclo , Right , 4
'Print "L1 Right 4"
'Loby2bin
Kixinby(4) = Kixinby(5)
Kixinby(5) = 0
Jby = Kixinby(4) And &B00100000
If Intflag = 1 Then 'note that this flag decides whether
If Jby = &B00100000 Then 'the Kix output is in a long integer
Kixinby(4) = Kixinby(4) Or &B11000000 'format
'Loby2bin
End If
End If
'Print Kixdeclo
End Sub
'*******************************************************************************
'***************** For following the course of decoding ************************
'*******************************************************************************
Sub Loby2bin
For Iby = 1 To 5
Kby = 6 - Iby
Print Bin(kixinby(kby)) ; " ";
Next Iby
Print Bin(jby)
End Sub
'*******************************************************************************
'** Example for those who just want to test the code in the Bascom simulator ***
'*******************************************************************************
Sub Example()
Gpsst = "$GPGGA,120757,5152.8557,N,00205.7338,E,1,06,2.5,121.954,M,49.4,M,,*XX"
Print "This is the GPS GGA string at the homepoint:"
Print Gpsst
Ggaparse
Findhome
Gpsst = "$GPGGA,120859,5152.7133,N,00205.8130,E,1,06,2.5,459.123,M,49.4,M,,*XX"
Print "This is one GPS GGA string during flight:"
Print Gpsst
Ggaparse
Gpsst = "$GPRMC,120859,A,5152.7133,N,00205.8130,E,073.8,231.8,130694,004.2,W*XX"
Print "This is the GPS RMC string for the same fix:"
Print Gpsst
Rmcparse
Dlate = Ggalate - Homelate : Isi = Dlate : Isi = Isi * Late2m : Dlate = Isi
Dlone = Ggalone - Homelone : Isi = Dlone : Isi = Isi * Lone2m : Dlone = Isi
Dalte = Ggaalte - Homealte
Print "Now let's make a kixline which codes DX, DY, DZ from home in Meter,"
Print "as well as heading in ° and speed over ground in km/h."
Print "Kixline coding started..."
Kixlineout = "x" 'example how how code a message type
Kixinlo = Dlate + Kix2 : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KI2.0
Kixinlo = Dlone + Kix2 : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KI2.0
Kixinlo = Dalte + Kix2 : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KI2.0
Kixinlo = Rmcheading : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KW2.1
Kixinlo = Rmcspeed : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KW2.1
Print "This is the kixline:"
Print
Print Kixlineout
Print
Kixlinein = Kixlineout : Intflag = 0
Print "Kixline received - decoding.."
Kixin = Mid(kixlinein , 2 , 2) + "000" : Kixdecode : Dlate = Kixdeclo - Kix2
Kixin = Mid(kixlinein , 4 , 2) + "000" : Kixdecode : Dlone = Kixdeclo - Kix2
Kixin = Mid(kixlinein , 6 , 2) + "000" : Kixdecode : Dalte = Kixdeclo - Kix2
Kixin = Mid(kixlinein , 8 , 2) + "000" : Kixdecode : Rmcheading = Kixdeclo
Kixin = Mid(kixlinein , 10 , 2) + "000" : Kixdecode : Rmcspeed = Kixdeclo
Print "Difference X from home [m]: " ; Dlate
Print "Difference Y from home [m]: " ; Dlone
Print " Altitude Z over home [m]: " ; Dalte
Isi = Dlate : Jsi = Dlone : Ksi = Dalte
Isi = Isi * Isi : Jsi = Jsi * Jsi : Ksi = Ksi * Ksi
Isi = Isi + Jsi : Isi = Isi + Ksi : Isi = Sqr(isi) : Ilo = Isi
Print " Distance from home [m]: " ; Ilo
Isi = Rmcheading / 10
Print " Heading [°]: " ; Fusing(isi , "#.#")
Isi = Rmcspeed / 10
Print " Speed over ground [km/h]: " ; Fusing(isi , "#.#")
End Sub
'*******************************************************************************
'***************************** Main loop (to be tested) ************************
'*******************************************************************************
Sub Mainloop
Do
Iby = Ischarwaiting()
If Iby <> 0 Then
Iby = Inkey()
Loopist = Chr(iby)
If Loopist = "$" Then
Gpsst = Loopist
Elseif Loopist = Chr(13) Then '
Ist = Left(gpsst , 6)
If Ist = "$GPGGA" Then
Ggaparse
Elseif Ist = "$GPRMC" Then
Rmcparse
'Make Kixline:
Kixlineout = "x" 'example o how to code a message type x
Kixinlo = Dlate + Kix2 : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KI2.0
Kixinlo = Dlone + Kix2 : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KI2.0
Kixinlo = Dalte + Kix2 : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KI2.0
Kixinlo = Rmcheading : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KW2.1
Kixinlo = Rmcspeed : Kixencode : Kixlineout = Kixlineout + Left(kixout , 2) 'KW2.1
Print Kixlineout
Else
'Do nothing
End If
Elseif Loopist = Chr(10) Then 'Line feed
'Do nothing
Else
Gpsst = Gpsst + Loopist
End If
Else
'........
'Do other things like reading ADC, SPI, I2C, etc.
'........
End If
Loop
End Sub
'*******************************************************************************
'*************************** Parse NMEA GGA string *****************************
'*******************************************************************************
Sub Ggaparse()
'Sentence GGA
'Function: Global Positioning Fix Data
'Example: $GPGGA,120757,5152.985,N,00205.733,W,1,06,2.5,121.9,M,49.4,M,,*52 (64)
'
'NMEA3.01 $GPGGA,115108.618,8960.000000,N,0000.000000,E,0,0,,137.000,M,13.000,M,,*40 (74)
' 2 3 4 5 6 7 8 9 10 11 12 13 14 15
'Synopsis:
' 2 time of fix (hhmmss)
' 3 latitude
' 4 N/S
' 5 longitude
' 6 E/W
' 7 Fix quality (0=invalid, 1=GPS fix, 2=DGPS fix)
' 8 number of satellites being tracked
' 9 horizontal dilution of position
'10 altitude above sea level
'11 M (meters)
'12 height of geoid (mean sea level) above WGS84 ellipsoid
'13 time in seconds since last DGPS update
'14 DGPS station ID number
'15 checksum
Iby = Split(gpsst , Commas(1) , ",")
If Iby <> 14 Then Exit Sub
'Kst = Commas(2) : Gpstime2millisec 'Time
Kst = Commas(3) : Late_lone_dec_conversion : Ggalate = Ilo 'Latitude
If Commas(4) = "S" Then Ggalate = 0 - Ggalate 'N/S
Kst = Commas(5) : Late_lone_dec_conversion : Ggalone = Ilo 'Longitude
If Commas(6) = "W" Then Ggalone = 0 - Ggalone 'E/W
Ggafixe = Val(commas(7)) 'Fix quality
Ggasate = Val(commas(8)) 'Number of sats
'Isi = Val(commas(9)): Isi = 10 * Isi: Ggahode = Isi
Ggaalte = Val(commas(10))
'Incr Iby
End Sub
'*******************************************************************************
'*************************** Parse NMEA RMC string *****************************
'*******************************************************************************
Sub Rmcparse()
'Sentence RMC
'Function: Recommended minimum specific GPS transit data
'eg3. $GPRMC,220516,A,5133.82,N,00042.24,W,173.8,231.8,130694,004.2,W*70
' 2 3 4 5 6 7 8 9 10 11 12 13
'
' 2 220516 Time Stamp
' 3 A validity - A-ok, V-invalid
' 4 5133.82 current Latitude
' 5 N North/South
' 6 00042.24 current Longitude
' 7 W East/West
' 8 173.8 Speed in knots
' 9 231.8 True course
' 10 130694 Date Stamp
' 11 004.2 Variation
' 12 W East/West
' 13 *70 checksum
Rmcvalidflag = 0
Iby = Split(gpsst , Commas(1) , ",")
If Iby <> 12 Then Exit Sub
'Kst = Commas(2): Gpstime2millisec 'Time
If Commas(3) = "A" Then Rmcvalidflag = 1 'Validity
'Kst = Commas(4) : Late_lone_dec_conversion : Ggalate = Ilo 'Latitude
'If Commas(5) = "S" Then Ggalate = 0 - Ggalate 'N/S
'Kst = Commas(6) : Late_lone_dec_conversion : Ggalone = Ilo 'Longitude
'If Commas(7) = "S" Then Ggalone = 0 - Ggalone 'E/W
Isi = Val(commas(8)) : Isi = Isi * 18.53 : Rmcspeed = Isi 'speed in 10 * Km/h
Isi = Val(commas(9)) : Isi = Isi * 10 : Rmcheading = Isi 'heading in 10 * °
'Incr Iby
'NOTE THAT YOU NEED TO ADOPT GGAPARSE AND RMCPARSE ACCORDING TO YOUR
'GPS MODULE. FORMATTING IS SLIGHTLY DIFFERENT. SOME DEVICES HAVE FOUR
'OTHERS HAVE 6 DECIMAL DIGITS FOLLOWING THE DECIMAL SEPARATOR. MY
'ADVICE: STAY AT BASCOM'S SPLIT COMMAND IF SPEED COUNTS.
End Sub
'*******************************************************************************
'**************************** GPS Time to millisec *****************************
'*******************************************************************************
Sub Gpstime2millisec()
'Find Time and convert into seconds (long)
'Ggatime = 3600 * Val(mid(gpsparseist , 1 , 2))
'+ 60 * Val(mid(gpsparseist , 3 , 2))
'+ Val(gpsparseist , 5 , 2))
'Ggatim0 = 0
Ist = Mid(kst , 1 , 2) 'h
Jlo = Val(ist)
Jlo = 3600 * Jlo
Ilo = Jlo
Ist = Mid(kst , 3 , 2) 'm
Jlo = Val(ist)
Jlo = 60 * Jlo
Ilo = Ilo + Jlo
Ist = Mid(kst , 5 , 2) 's
Jlo = Val(ist)
Ilo = Ilo + Jlo
Ggatime = 1000 * Ilo 'NEW Ki!!! FEB 2010 Time now in Millisec!!!!
Iby = Instr(kst , ".")
If Iby = 0 Then
Ilo = 0
Else
Ist = Right(kst , 3)
Ist = Ist + "000"
Ist = Left(ist , 3)
Ilo = Val(ist)
End If
Ggatime = Ggatime + Ilo
End Sub
'*******************************************************************************
'******** Latitude and longitude conversion from °°MM.SSSS to °°xxxxxx *********
'*******************************************************************************
Sub Late_lone_dec_conversion()
'Zby = Len(kst) '5125.6558 = 51° 25.6558' has len 9
Iby = Split(kst , Dots(1) , ".") 'Dots(1) = "5125" Dots(2) = "6558"
Ist = Left(dots(1) , 2) 'Xst = "51"
Jst = Right(dots(1) , 2) 'Yst = "25"
Jst = Jst + Dots(2) 'Yst = "256558"
Ilo = Val(ist) 'Ilo = 51
Ilo = Ilo * 1000000 'Ilo = 51000000
Jlo = Val(jst) 'Jlo = 256558
Jlo = Jlo * 10 'Jlo = 2565580
Jlo = Jlo / 6 'Jlo = 427596
Ilo = Ilo + Jlo 'Ilo = 51427569
End Sub
'*******************************************************************************
'*************************** Find Home GPS Position ****************************
'*******************************************************************************
Sub Findhome()
If Gpsreadyflag = 0 Then 'If no first fix found so far
If Ggafixe >= 1 And Ggasate >= 4 Then 'test if sufficient number of sats
Gpsreadyflag = 1 'let first fix found
Hometime = Ggatime 'determine home position
Homelate = Ggalate
Homelone = Ggalone
Homealte = Ggaalte
Homeset
Gpsreadyflag = 1
End If
End If
End Sub
'*******************************************************************************
'*********** Homeset: Calculate navigation parameter from home GPS *************
'*******************************************************************************
'DON'T USE IBY, JBY, JST, KST
Sub Homeset()
'FROM: http://williams.best.vwh.net/avform.htm
'
'Local, flat earth approximation
'If you stay in the vicinity of a given fixed point (lat0,lon0), it may be a good
'enough approximation to consider the earth as "flat", and use a North, East, Down
'rectangular coordinate system with origin at the fixed point. If we call the
'changes in latitude and longitude dlat=lat-lat0, dlon=lon-lon0
''(Here treating North and East as positive!), then
' distance_North=R1*dlat
' distance_East=R2*cos(lat0)*dlon
'
'R1 and R2 are called the meridional radius of curvature and the radius of curva-
'ture in the prime vertical, respectively.
' R1=a(1-e^2)/(1-e^2*(sin(lat0))^2)^(3/2)
' R2=a/sqrt(1-e^2*(sin(lat0))^2)
'
'a is the equatorial radius of the earth (=6378.137000km for WGS84),
'and e^2=f*(2-f) with the flattening f=1/298.257223563 for WGS84.
'
'In the spherical model used elsewhere in the Formulary, R1=R2=R, the earth's
'radius. (using R=1 we get distances in radians, using R=60*180/pi distances are
' in nm.)
'
'In the flat earth approximation, distances and bearings are given by the usual
'plane trigonometry formulae, i.e:
'
' distance = sqrt(distance_North^2 + distance_East^2)
' bearing to (lat,lon) = mod(atan2(distance_East, distance_North), 2*pi)
' (= mod(atan2(cos(lat0)*dlon, dlat), 2*pi) in the spherical case)
'
'These approximations fail in the vicinity of either pole and at large distances.
'The fractional errors are of order (distance/R)^2.
Isi = 1 / 298.257223563 'f = 0.00335281
Jsi = 2 - Isi '2-f = 1.9966472
Isi = Isi * Jsi 'Isi = e^2 = f*(2-f) = 0.00669438
Jsi = Homelate 'Jsi = 51427596
Jsi = Homelate / 1000000 'Jsi = 51.428
Jsi = Deg2rad(jsi) 'Jsi = lat0 = 0.448790
Lone2m = Cos(jsi) 'Lone2m = 0.90097275
Jsi = Sin(jsi) 'Jsi = sin(lat0) = 0.433876
Jsi = Jsi * Jsi 'Jsi = (sin(lat0))^2 = 0.18824844
Jsi = Isi * Jsi 'Jsi = e^2 * (sin(lat0))^2 = 0.0012602
Jsi = 1 - Jsi 'Jsi = 1 - e^2 * (sin(lat0))^2 = 0.9987398
Jsi = Sqr(jsi) 'Jsi = sqr(1 - e^2 * (sin(lat0))^2) = 0.9993697
Ksi = Jsi ^ 3 'Ksi = (1 - e^2 * (sin(lat0))^2)^(3/2) = 0.9981103
Isi = 1 - Isi 'Isi = 1-e^2 = 0.9933056
Isi = Isi / Ksi 'Isi = (1-e^2)/(1 - e^2 * (sin(lat0))^2)^(3/2) = 0.9951862
Late2m = 6378137 * Isi 'Late2m = R1 = a * (1-e^2)/(1 - e^2 * (sin(lat0))^2)^(3/2) = 6347434
Lsi = 1 / 1000000 'Lsi for dlat = 1
Lsi = Deg2rad(lsi) 'Lsi = dlat = 1.745329252e-8
Late2m = Late2m * Lsi 'Late2m = 0.1107836 meter per unit
Jsi = 6378137 / Jsi 'Jsi = R2=a/sqrt(1-e^2*(sin(lat0))^2) = 6382160
Jsi = Jsi * Lsi 'Jsi 0.1113897 meter per unit
Lone2m = Lone2m * Jsi '0.100359084 meter per unit at latitude
End Sub
|
|
|
| |
|
|
|
