Category Archives: Timestamps

Timestamps pt 4 – Adaptive Time Base

When dates and times are manually entered we may need only some of the following: year, month, day, time zone, hour, minute, second. Although the timestamp may have millisecond resolution, high resolution data may be inconsequential. For example a list of birthdays requires only year, month and day. Time zone, hour, minute, second and milliseconds are no factor and are implicitly set to zero. When exchanging data with a server or another application it would be desirable to send only the data we need and no more. This can be done with an adaptive time base.

Color My Data proposes an Eight-Bit Compressed Binary Format (CBF-8) coder / decoder which generates a policy indicator (DATETIME) followed by zero or more base-64 digits as follows:

  • digit 1 – years range -32 to +31 step 64 years bias 2000
  • digit 2 – years range 0 to 63 step 1 year
  • digit 3 – months range 1 to 12 step 1 month
  • digit 4 – days range 1 to 31 step 1 day
  • digit 5 – time zone range -24 to +24 step 30 minutes
  • digit 6 – MSB time zone range 0 to 1 step 15 minutes
  • digit 6 – five bits hour range 0 to 23 step 1 hour
  • digit 7 – minutes range 0 to 59 step 1 minute
  • digit 8 – seconds range 0 to 59 step 1 second
  • digit 9 – subseconds range 0 to 62 step 16 milliseconds
  • digit 10 – subseconds range 0 to 63 step 250 microseconds
  • digits 11 to n – subseconds range 0 to 63 step 250 x 6410-n microseconds.

The DATETIME policy causes CBF-8 to use MSB alignment which ignores trailing zeros. As trailing zeros increase, both the number of encoded digits and the effective clock frequency decrease. Returning to the birthday example, a four-byte (digit) stream may generate any birthday between Jan 1 28 BC and Dec 31 4047 AD with a resolution of one day. A seven-byte (digit) increases the clock rate from one cycle per day to one cycle per minute by adding time zone, hours and minutes (and nothing more). On the other extreme increasing the clock rate to 2GHz (500 picosecond period) would typically take 15 digits.

The input arguments for encoding timestamps are the minute of epoch 2000-01-01T00:00Z mm2K() and sec() from the previous post and the time-zone, a value between -48 and +48 that scales to -12:00 to +12:00 in 15 minute increments.

CBF8#append(OutputStream sink, int mm2K, double sec, byte timeZone);

The CBF8Decoder supports verification of the DATETIME policy, access to the array of base-64 digits and the number of encoded digits. This greatly simplifies the conversion to human readable formats. The timestamp class uses these data to decode mm2K and sec.

int mm2K(CBF8Decoder);
double sec(CBF8Decoder);

Advantages:

  • encoded data are portable across all implementations
  • timestamp splits into year, month, day, hour, minute, second and subsecond
  • split data is easy to format for human readability
  • encoded data require fewer bytes than formatted text
  • only significant digits are encoded
  • number of digits adapts to clock rate

Disadvantages:

  • Computationally intensive relative to addition / subtraction due to numerous integer remainder and integer divide operations.
  • Base-64 digits above F (15) not easy to relate to decimal digits
  • .

Suggested Use Cases:

Peer to peer and client-server data exchanges. Splitting data for formatted data input / output.

Timestamps Pt 3 – Configurable Time Base

The speed of light is approximately 186 miles per millisecond. In a distance measurement application (e.g. radar) the round trip distance is 93 miles per millisecond. If each clock cycle is one millisecond, the distance can be no more precise than 93 miles. This realization argues for higher clock rates. A one megahertz clock improves range resolution to about a tenth of a mile; a one gigahertz clock improves range resolution to about six inches (e.g. ground penetrating radar).

By introducing a configurable clock, portability is broken even more than when we introduced T0 in the previous post. To address the portability issue consider breaking the time into two parts: minutes and seconds. Let the minutes be referenced to a start minute M0 at the same time as the clock counter is referenced to the start time T0. When constructing the timestamp object let us specify M0, T0 the clock rate in Hertz and an implementation of the interface now(). This interface returns the raw number of clock cycles since some initial time as in the following example.

long now() {

return System.currentTimeMillis();

}

The product of the clock rate and 60 is the number of clock cycles in one minute. Let us call that value ONE_MINUTE.

Let us calculate the unsigned remainder (modulus) on dividing now() by ONE_MINUTE. Dividing the modulus by ONE_MINUTE yields a fraction of one minute between 0 up to but not including 1.0. The product of 60 and this value yields the number of seconds after the current minute, a portable value that is independent of the clock rate.

Subtracting the modulus from the dividend yields a value that ONE_MINUTE can evenly divide. The resulting quotient when added to M0 is the minute of epoch. So long as everyone agrees on the epoch beginning, this value is also portable and independent of all configurable parameters.

The year 2000 is a leap year exception to the 100 year leap year exception to the every fourth year leap year. For that reason, I chose 2000-01-01T00:00Z as the epoch reference; named the minute of epoch mm2K and implemented the following functions.

Timestamp set(int mm2K, double sec);
int mm2K();
double sec();

Advantages:

  • Configurable time bases work with any clock rate
  • Timestamps with different clock rates can be compared to one another

Disadvantages:

  • Integer division is computationally intensive relative to addition or subtraction
  • Data exchange increases from 64 to 96 bits
  • Still not human readable

Suggested Use Case:

Creating timelines from different systems may require comparing timestamps with different clock rates. Since mm2K and sec are portable they are used to implement the interface java.io.Comparable<Timestamp>

Timestamps Pt 2 – Reducing Storage Size

Automated data-loggers may need to generate thousands if not millions of timestamps per day. If we could reduce the size of the timestamp 50% or more, the memory savings become significant. In the previous post we showed that nearly 15 bits (about 16000 days) can be discarded if we simply measure time relative to a configurable start time T0. More redundant bits can be eliminated if we shorten the amount of time before the clock rolls over. However, this requires that T0 be reset periodically. Here is how storage size affects the maximum time between T0 resets.

  • 2 bytes about 1.1 minutes
  • 3 bytes about 4.66 hours
  • 4 bytes about 49.7 days

Advantages

  • Significant Reduction in Storage Size
  • Well suited for high frequency data logging
  • Subtraction of T0 is not computationally intensive

Disadvantages

  • Without T0; the time is no longer portable
  • Adding T0 doubles the amount of data to be ported.
  • Doesn’t address light speed distance measurement
  • Still requires processing for human readability

Suggested Use Case

Confine usage to data storage and retrieval as in the following example.

store(System.currentTimeMillis()-this.T0, rowData, row);
long then = load(rowData, row) + this.T0;

Timestamps pt 1 – One Size Does Not Fit All

For Java programmers the function

long t = System.currentTimeMillis();

assigns t the number of milliseconds that have elapsed since midnight Jan 01 1970. It takes 10 bits to represent a second. Add 17 bits for 86400 seconds in a day and 9 bits for 365 days in a year and it leaves 28 bits for about 268 million years worth of time measurement. Over that period of time the earths rotation rate will have slowed and how we think of time will have changed radically. Let us discuss this representation’s advantages and disadvantages.

Advantages:

  • Minimizes amount of time needed to record the time
  • Suitable for many applications including data logging
  • Portable across numerous implementations

Disadvantages:

  • It is a thousand to a million times too coarse for lightspeed distance measurement. (e.g. radar)
  • More than 16000 days have elapsed since Jan 1 1970 necessitating nearly 15 bits of redundant data with present day data-loggers.
  • It is difficult to relate to year, month, day, hour, minute, second without additional processing.

Suggested Use Case:

Getting or setting the time as in the following example:

Timestamp set(long t); //sets timestamp
long longValue(); //gets value of t