Convert streaming data to triple (base-3)

Question

Given a 3-level (-1.0, + 1) channel clock between two devices, what is the most efficient stream for converting a bit stream into and out of a channel?

The current method is to take 3 binary bits and convert them to two trits. I believe that this takes up 11% of the channel’s capabilities (since 1 out of 9 possible pairs is never used). I suspect that grouping may reduce this waste, but this project uses 8-bit devices, so the size of my group is limited.

I would like to use divmod-3, but I do not have the entire binary stream available anywhere. Is there a method for incremental divmod3 that can start with LSB?

As an inexplicable assumption, I assume that there should be an approach of the form “analyze the next 3 bits, delete one bit, change one bit” - but I could not find something workable.

Answer 1

Try packing 11 bits (2048 codes) in 7 trits (2187 codes), you will get less than 1% of the overhead. There are several methods. The first one is simple: a lookup table. The second is divmod-3. Thirdly, this is a little mythology, as shown below.

First step: first pack the first 9 bits using a 3-bit-2-trit scheme:

abc def ghi jk => mn pq rs jk (mn, pq, rs are trit pairs) bits trits 0ab -> ab 10a -> Za 11a -> aZ (i'll use Z is for -1 for compactness) 

ZZ state will be used further

Second stage: using more complex logic for packing 6 tracks and 2 bits in 7 trits:

 mn pq rs 0k -> mn pq rs k mn pq rs 10 -> mn pq rs Z mn pq rZ 11 -> mn pq ZZ r mn pq r0 11 -> mn ZZ pq r mn pq r1 11 -> ZZ mn pq r 

Unused Codes:

 ZZ ZZ xx x ZZ xx ZZ x xx ZZ ZZ x 

UPD other suitable packing ratios: 19b → 11t (~ 0.1% overhead), 84b → 53t (~ 0.0035% overhead), but seem to exceed.

Answer 2

Could you pinch some ideas from http://en.wikipedia.org/wiki/Arithmetic_coding ?