Monday, December 17, 2007
Update: Quiet
Just an update to let you know that I am still here, but virtually no progress made in last couple of months - mostly for business (new position, weeks abroad in other offices) and personal (birth of new child, house renovations planning, etc). In the interim I've noticed that SparkFun are no longer listing V1.0 of the GPS Logger, which is a bit of a pity since the Lassen iQ has lower power consumption than the EM-406, but the latter board design (V2.4) is more superior (as, in fact, are various other aspects of the EM-406). I hope to have some time over the holiday break to do some work and provide updates. If you are reading this and have suggestions for any priority items, please leave comments. Otherwise, Happy Holidays!
Tuesday, July 10, 2007
Release: GPS Logger MG - Release 0.94b
I've produced an interim release, this has a couple of I/O performance improvements, and allows both 'file' and 'pass' modes to be active concurrently (so you can use real-time GPS through the serial port, while also logging to flash). In addition, I've also now included a CHANGES file, taken directly from the project's svn commit log. This gives you very fine detail about what's happened between releases. Get it from the links to the side.
Wednesday, June 27, 2007
Release: GPS Logger MG - Release 0.94
Release 0.94 is available! You can read the release note to the side, and download both the release package and userguide. Feedback is welcome!
Tuesday, May 22, 2007
Testing: Output format statistics
I have just polished up code and data and run a comparative test, the results are interesting.
The large GPS sample data was first run through 'NMEA' format, selecting only GGA sentences. There are in total 2898111 sentences, which approximates 33 days, 13 hours, 1 minute and 51 seconds of positioning data if captured continuously at 1 second intervals. There are no invalid (i.e. non-lock, no position) sentences in here: they're all valid with usable data.
I then used this resulting data to test KML and CSV formats, using text and binary encoding options, and compression.
In NMEA mode, with GGA sentences: 190M file (2898111 lines).
In KML mode: 60M file (2643355 lines).
In CSV mode, with text encoding, and lon,lat,alt elements: 60M file.
In CSV mode, with binary encoding (no compress), and lon,lat,alt elements: 25M file.
In CSV mode, with binary encoding (compressed), and lon,lat,alt elements: 7.9M file.
When repeated with 'compress=true', the resulting output files are:
In NMEA mode, as above: 27M.
In KML mode, as above: 11M.
In CSV mode, with text encoding, as above: 11M.
In CSV mode, with binary encoding (no compress), as above: 12M.
In CSV mode, with binary encoding (compressed), as above: 5.8M.
I'll discuss this in further detail later, but it indicates the success of the generic and binary compression features. Consider about 1 month of data at 8M (using binary encoding, with compression, which happens to be the best-bang-for-buck), you could get 64 months on a 512M SD card, or 5.3 years. What an overkill! Remember that it's not about preserving card size, it's about preserving card writes, and thus power efficiency.
The large GPS sample data was first run through 'NMEA' format, selecting only GGA sentences. There are in total 2898111 sentences, which approximates 33 days, 13 hours, 1 minute and 51 seconds of positioning data if captured continuously at 1 second intervals. There are no invalid (i.e. non-lock, no position) sentences in here: they're all valid with usable data.
I then used this resulting data to test KML and CSV formats, using text and binary encoding options, and compression.
In NMEA mode, with GGA sentences: 190M file (2898111 lines).
In KML mode: 60M file (2643355 lines).
In CSV mode, with text encoding, and lon,lat,alt elements: 60M file.
In CSV mode, with binary encoding (no compress), and lon,lat,alt elements: 25M file.
In CSV mode, with binary encoding (compressed), and lon,lat,alt elements: 7.9M file.
When repeated with 'compress=true', the resulting output files are:
In NMEA mode, as above: 27M.
In KML mode, as above: 11M.
In CSV mode, with text encoding, as above: 11M.
In CSV mode, with binary encoding (no compress), as above: 12M.
In CSV mode, with binary encoding (compressed), as above: 5.8M.
I'll discuss this in further detail later, but it indicates the success of the generic and binary compression features. Consider about 1 month of data at 8M (using binary encoding, with compression, which happens to be the best-bang-for-buck), you could get 64 months on a 512M SD card, or 5.3 years. What an overkill! Remember that it's not about preserving card size, it's about preserving card writes, and thus power efficiency.
Thursday, May 17, 2007
Progress: update for 0.94 release
Work for the 0.94 release is coming along. Most of the main work has been completed: (a) porting emulator to Linux, to support both FreeBSD & Linux; (b) porting firmware to GPS Logger V2.4, to support both V1.0 and V2.4; (c) supporting generic and binary compression for output data; (d) PC based application testing for both V1.0 and V2.4. There are also a bunch of smaller scale additions and modifications that I won't go into here right now.
All I have to complete now are some performance cleanups (some code inlining thanks to a gprof analysis), some emulator cleanups (clean termination at end of input files) and a round of testing. The testing can't be understated: I need to (a) test code against GPS sample data, (b) produce compression statistics from same data, (c) test power consumption for this and original firmwares, (d) general code review and functional testing.
I have also decided on the roadmap for future releases: the next one, a 0.96, will focus exclusively on reworking and extending the GPS data handling, by (a) the logger programming the GPS module for specific sentence, powersave and other features; (b) support sparkfun V2.4 firmware features (hold off, etc); (c) customisable filenames with date/timestamps; (d) a separate utility tool for conversion from raw/nmea to kml/csv with binary/text encoding and using compression; (e) power/performance improvements as necessary. Beyond that, a 0.98 release will be entirely dedicated to power/performance optimisations and improvements, and additional debug/inteface features (e.g. I may add in an xmodem download feature (so you can extract logs without having to remove the SD card). After 0.98 comes 1.00, when all should be stable, working and optimal.
I hope to have a 0.94 release ready in the next 3-4 weeks. Let me know now if there's anything you're interested in.
All I have to complete now are some performance cleanups (some code inlining thanks to a gprof analysis), some emulator cleanups (clean termination at end of input files) and a round of testing. The testing can't be understated: I need to (a) test code against GPS sample data, (b) produce compression statistics from same data, (c) test power consumption for this and original firmwares, (d) general code review and functional testing.
I have also decided on the roadmap for future releases: the next one, a 0.96, will focus exclusively on reworking and extending the GPS data handling, by (a) the logger programming the GPS module for specific sentence, powersave and other features; (b) support sparkfun V2.4 firmware features (hold off, etc); (c) customisable filenames with date/timestamps; (d) a separate utility tool for conversion from raw/nmea to kml/csv with binary/text encoding and using compression; (e) power/performance improvements as necessary. Beyond that, a 0.98 release will be entirely dedicated to power/performance optimisations and improvements, and additional debug/inteface features (e.g. I may add in an xmodem download feature (so you can extract logs without having to remove the SD card). After 0.98 comes 1.00, when all should be stable, working and optimal.
I hope to have a 0.94 release ready in the next 3-4 weeks. Let me know now if there's anything you're interested in.
Discussion: to GGA or RMC
I noticed with the GPS Logger V1.0 using Trimble Lassen iQ, that the default output sentences were GGA and VTG. This provided the necessary position and velocity information. It also provide a timestamp (UTC), but not a datestamp. So, for a proper datestamp I either needed an additional RMC or ZDA sentence.
With the GPS Logger V2.4, using US Globalsat EM-406, there are a whole bunch of default sentences, one of which is RMC. Now, RMC sounds great: it has validity field, position, velocity, timestamp, datestamp, but it lacks an altitude. Just that one extra field would have made all the difference.
So, in any case, not in this version of GPS Logger MG, but in a future version, the GPS module (either Lassen iQ or EM-406) will be programmed at start up to only spit out the bare minimum sentences necessary. That's easy with the EM-406 out of the box, because it supports an inbound interface. For the Lassen iQ, it needs to be pre-configured to accepted TSIP on the port.
With the GPS Logger V2.4, using US Globalsat EM-406, there are a whole bunch of default sentences, one of which is RMC. Now, RMC sounds great: it has validity field, position, velocity, timestamp, datestamp, but it lacks an altitude. Just that one extra field would have made all the difference.
So, in any case, not in this version of GPS Logger MG, but in a future version, the GPS module (either Lassen iQ or EM-406) will be programmed at start up to only spit out the bare minimum sentences necessary. That's easy with the EM-406 out of the box, because it supports an inbound interface. For the Lassen iQ, it needs to be pre-configured to accepted TSIP on the port.
Tuesday, May 15, 2007
Internals: Supporting binary output compression
I have been working on improving the CSV format’s binary encoding to reduce the volume of data being logged, which will reduce SD card writes and thus improve power performance. The following is an attempt to explain how compressed binary encoding can produce an 8x size improvement over text encoding.
Approach
The logger is designed to capture and output positioning data (i.e. longitude, latitude, altitude, timestamp, etc) at a regular rate. The native encoding of this data is absolute. For example, the absolute encoding of a latitude position requires 28 bits (a 1 bit sign, a 7 bit integral degree, and a 20 bit fractional degree).
However, the logger is typically moving at a velocity. This velocity has practical limits as it is unlikely to be faster than the fastest vehicle known to humans, and will typically be much less (e.g. walking, cycling or driving speeds). Each positioning data that is output will be at some offset to the proceeding data.
This could mean that while large numbers are required to express absolute positions, much lower numbers are required to express the relative offset between them. For example, consider an airplane that is moving at 939km/h in the latitude direction only, with a logger onboard that is generating positioning data every 1 second. With each latitude degree being about 111km, then the absolute latitude changes by 0.00235 at each interval. This relative offset can be encoded in about 12 bits, which is 50% more efficient than the 28 bits required for the absolute encoding.
That is the first decision: to use relative offsets.
If relative offsets are to be used, how should they be encoded? The simple approach is to store the offset value itself. A more complex, but ultimately more adaptive and optimal, approach is to use a statistical bit encoder (e.g. huffman, arithmetic, etc) and store the resulting bitstream. For now, the simple approach will suffice.
That’s the second decision: to store the actual relative offsets.
The next problem is in the handling large relative offsets (e.g. an extended interval with no coverage, say inside a moving vehicle, a road/rail tunnel, or a baggage compartment). In these cases, the relative offset soon becomes a large as an absolute position. There needs to be a limit to the size of the relative offset, which if exceeded, causes an absolute position to be used. These should be infrequent cases.
That’s the third decision: to allow both absolute positions and relative offsets.
The number of bits required to encode an absolute position is fixed, but should this also be the case for relative offsets? A variable size would require some form of length or terminal indicator to be used. This would be mandatory for the complex approach above as the statistical bit encoders produce variable length outputs, but can be chosen either way for the sample approach. For now, the simplest option of a fixed bit size will be used.
That’s the fourth decision: to use fixed (pre-determined) bit sizes for relative offsets.
This begs the next question: what should the fixed bit sizes be? One approach is to calculate the theoretical limits to a relative offset (e.g. the maximum speed of vehicles). Another approach is to use empirical observations, and 700MB of GPS sample data is available to help with that. By analysing the relative offsets, an optimal fixed bit size can be computed.
That’s the fifth decision: to empirically determine the fixed bit sizes for the relative offsets.
There’s one final implementation detail: how are absolute or relative entries distinguished in the output. There could be an absolute/relative indicator specified (a) for the entire entry (i.e. all fields in the entry have the same encoding), or (b) for individual fields (e.g. an absolute altitude, but a relative timestamp). Additionally, the indicator could be specified for (1) each entry/field, or (2) only when the current run changes (e.g. a relative indicator, then 50 altitudes relative encoded, then an absolute indicator, etc). For simplicity, the indicator is chosen to be a single bit (0 for absolute, 1 for relative), and specified on each field (b) at each time (1).
That’s the sixth decision: to use a one bit indicator on every field in every entry to indicate its encoding method.
Analysis
The fixed bit sizes for the relative offset encoding were derived from the 700MB of GPS sample data. The NMEA GPGGA sentences in the data were converted into binary format with absolute encoding, resulting in 2,083,953 entries. The relative offsets were computed and turned into a cumulative histogram.
The histogram showed the number of entries that could be encoded within a given range of values, i.e. a particular number of bits. For example, the altitude field had 1,394,639 fields of offset 0, 1,963,859 of offset 0-1, and 2,082,057 fields of offset 0-127. This means that 99.90902% of offsets can be encoded as relative offsets within 7 bits (0-127), and the remaining would need to be encoded as absolute positions.
From this, it is easy to calculate the average bit size. For instance, the altitude field is 17 bits with absolute encoding (a 1 bit absolute indicator, a 1 bit sign, and a 15 bit absolute height), or (2 + n) bits with relative encoding (a 1 bit relative indicator, a 1 bit sign, and an #bits bit relative height). With this, the total output (encoded) size of all altitudes is (#values[n] * (2 + n)) + ((#total - #values[n]) * 17), where #total is 2,083,953 and #values[n] is obtained from the histogram. Dividing the total output size by the total number of entries gives the average bit per entry. It’s just a matter of looking at what number of bits (n) results in the lowest average bit per entry.
When this analysis is carried out for all positional fields:
With all fields having absolute encoding, an entry requires 94 bits. If all fields have relative encoding, this drops to 25 bits, giving a best case compression factor of 26.60%. However, the sample data shows that the best case is not always achieved, and on average, an entry requires 29.50 bits, giving an average case compression factor of 31.38%. That is a factor of 3 reduction in size and possibly (a tenuous extrapolation) a factor of 3 increase in power performance.
In summary, consider logging at 1 second intervals in CSV format, storing longitude, latitude, altitude and a timestamp. With text encoding, approximately 31 bits are required per entry, which fills the 24K onboard file cache in 13.2 minutes. With the original, uncompressed, binary encoding, 90 bits are used, filling the cache in 36.4 minutes. With the compressed binary encoding, 29.50 bits are used, filling the cache in 111.1 minutes. The compressed binary encoding can give an 8x size improvement over text encoding, possibly resulting in an 8x power improvement.
Approach
The logger is designed to capture and output positioning data (i.e. longitude, latitude, altitude, timestamp, etc) at a regular rate. The native encoding of this data is absolute. For example, the absolute encoding of a latitude position requires 28 bits (a 1 bit sign, a 7 bit integral degree, and a 20 bit fractional degree).
However, the logger is typically moving at a velocity. This velocity has practical limits as it is unlikely to be faster than the fastest vehicle known to humans, and will typically be much less (e.g. walking, cycling or driving speeds). Each positioning data that is output will be at some offset to the proceeding data.
This could mean that while large numbers are required to express absolute positions, much lower numbers are required to express the relative offset between them. For example, consider an airplane that is moving at 939km/h in the latitude direction only, with a logger onboard that is generating positioning data every 1 second. With each latitude degree being about 111km, then the absolute latitude changes by 0.00235 at each interval. This relative offset can be encoded in about 12 bits, which is 50% more efficient than the 28 bits required for the absolute encoding.
That is the first decision: to use relative offsets.
If relative offsets are to be used, how should they be encoded? The simple approach is to store the offset value itself. A more complex, but ultimately more adaptive and optimal, approach is to use a statistical bit encoder (e.g. huffman, arithmetic, etc) and store the resulting bitstream. For now, the simple approach will suffice.
That’s the second decision: to store the actual relative offsets.
The next problem is in the handling large relative offsets (e.g. an extended interval with no coverage, say inside a moving vehicle, a road/rail tunnel, or a baggage compartment). In these cases, the relative offset soon becomes a large as an absolute position. There needs to be a limit to the size of the relative offset, which if exceeded, causes an absolute position to be used. These should be infrequent cases.
That’s the third decision: to allow both absolute positions and relative offsets.
The number of bits required to encode an absolute position is fixed, but should this also be the case for relative offsets? A variable size would require some form of length or terminal indicator to be used. This would be mandatory for the complex approach above as the statistical bit encoders produce variable length outputs, but can be chosen either way for the sample approach. For now, the simplest option of a fixed bit size will be used.
That’s the fourth decision: to use fixed (pre-determined) bit sizes for relative offsets.
This begs the next question: what should the fixed bit sizes be? One approach is to calculate the theoretical limits to a relative offset (e.g. the maximum speed of vehicles). Another approach is to use empirical observations, and 700MB of GPS sample data is available to help with that. By analysing the relative offsets, an optimal fixed bit size can be computed.
That’s the fifth decision: to empirically determine the fixed bit sizes for the relative offsets.
There’s one final implementation detail: how are absolute or relative entries distinguished in the output. There could be an absolute/relative indicator specified (a) for the entire entry (i.e. all fields in the entry have the same encoding), or (b) for individual fields (e.g. an absolute altitude, but a relative timestamp). Additionally, the indicator could be specified for (1) each entry/field, or (2) only when the current run changes (e.g. a relative indicator, then 50 altitudes relative encoded, then an absolute indicator, etc). For simplicity, the indicator is chosen to be a single bit (0 for absolute, 1 for relative), and specified on each field (b) at each time (1).
That’s the sixth decision: to use a one bit indicator on every field in every entry to indicate its encoding method.
Analysis
The fixed bit sizes for the relative offset encoding were derived from the 700MB of GPS sample data. The NMEA GPGGA sentences in the data were converted into binary format with absolute encoding, resulting in 2,083,953 entries. The relative offsets were computed and turned into a cumulative histogram.
The histogram showed the number of entries that could be encoded within a given range of values, i.e. a particular number of bits. For example, the altitude field had 1,394,639 fields of offset 0, 1,963,859 of offset 0-1, and 2,082,057 fields of offset 0-127. This means that 99.90902% of offsets can be encoded as relative offsets within 7 bits (0-127), and the remaining would need to be encoded as absolute positions.
From this, it is easy to calculate the average bit size. For instance, the altitude field is 17 bits with absolute encoding (a 1 bit absolute indicator, a 1 bit sign, and a 15 bit absolute height), or (2 + n) bits with relative encoding (a 1 bit relative indicator, a 1 bit sign, and an #bits bit relative height). With this, the total output (encoded) size of all altitudes is (#values[n] * (2 + n)) + ((#total - #values[n]) * 17), where #total is 2,083,953 and #values[n] is obtained from the histogram. Dividing the total output size by the total number of entries gives the average bit per entry. It’s just a matter of looking at what number of bits (n) results in the lowest average bit per entry.
When this analysis is carried out for all positional fields:
- Longitude: since 99.9762% of integral parts of the degree are at offset 0, specify that relative encoding can only occur if the integral field is unchanged. The fractional part of the degree is optimally encoded in 9 bits (37.55%), rather than 8 bits (45.64%) or 10 bits (40.20%).
- Latitude: since 99.9968% of integral parts of the degree are at offset 0, specify that relative encoding can only occur if the integral field is unchanged. The fractional part of the degree is optimally encoded in 8 bits (35.68%) rather than 7 bits (45.72%) or 9 bits (38.17%).
- Altitude: The value is optimally encoded in 1 bit (22.39%) rather than 0 bits (40.95%) or 2 bits (24.50%) or 3 bits (29.77%).
- Timestamp: The value is optimally encoded in 1 bit (20.46%) rather than 0 bits (99.99%) or 2 bits (20.64%) or 3 bits (24.21%).
With all fields having absolute encoding, an entry requires 94 bits. If all fields have relative encoding, this drops to 25 bits, giving a best case compression factor of 26.60%. However, the sample data shows that the best case is not always achieved, and on average, an entry requires 29.50 bits, giving an average case compression factor of 31.38%. That is a factor of 3 reduction in size and possibly (a tenuous extrapolation) a factor of 3 increase in power performance.
In summary, consider logging at 1 second intervals in CSV format, storing longitude, latitude, altitude and a timestamp. With text encoding, approximately 31 bits are required per entry, which fills the 24K onboard file cache in 13.2 minutes. With the original, uncompressed, binary encoding, 90 bits are used, filling the cache in 36.4 minutes. With the compressed binary encoding, 29.50 bits are used, filling the cache in 111.1 minutes. The compressed binary encoding can give an 8x size improvement over text encoding, possibly resulting in an 8x power improvement.
Subscribe to:
Posts (Atom)