Conversion of binary bitstream to and from ternary bitstream?

Question

I need to convert arbitary length binary into an exact ternary representation. Ideally, given an array of bits char buffer[n], the algorithm would be able to produce a array of trits(analog of bits), and vice versa. Is there such an algorithm?

I am aware of ways to convert individual int to ternary:

int nth_trit(int num, int n)
{
    for(int i = 0; i < n; i++)
        num /= 3;

    return num % 3;
}

Alas, with a bitstream even a long long long int wouldn't suffice. I think using a big integer library would suffice, although I'm not sure, and feel that there should be better way calculate the ternary representation.

A visual example:

// Conversion is simple(short stream)
Binary  - 0 1 0 0 1 0 0 1
Decimal -             7 3
Ternary -         2 2 0 1

// Conversion is hard(long stream)
Binary  - 1 0 1 0 0 0 0 1 ..........
Ternary - ? ? ?

The short stream is simple because, since it nicely fits into an int, the nth_trit function can be used, but the long stream doesn't, and so apart from using a big integer library, no easy solution occurs to me.

Answer 1

Your algorithm is not so good if the bit buffer is long because each output trit repeats all the divisions also needed for smaller values of n. So converting this algorithm to "bignum" arithmetic will not be what you want.

Another approach: scanning the bits left to right, each new one updates the previous value:

val = val * 2 + bit

A trinary number with n trits t[i] has the value

sum(i = 0 .. n-1) t[i] * 3^i

So a trinary representation of val updated for a new scanned bit becomes,

[ 2 * sum(i = 0 .. n-1) t[i] * 3^i ] + bit
    = bit + sum(i = 0 .. n-1) 2 * t[i] * 3^i 
    = 2 * t[0] + b + sum(i = 1 .. n) 2 * t[i] * 3^i

To make the code simple let's compute the trits in an array of unsigned chars. After they're done you can repack them any way you like.

#include <stdio.h>

// Compute the trit representation of the bits in the given
// byte buffer.  The highest order byte is bytes[0].  The
// lowest order trit in the output is trits[0].  This is 
// not a very efficient algorithm, but it doesn't use any
// division.  If the output buffer is too small, high order
// trits are lost.
void to_trits(unsigned char *bytes, int n_bytes, 
              unsigned char *trits, int n_trits)
{
  int i_trit, i_byte, mask;

  for (i_trit = 0; i_trit < n_trits; i_trit++)
    trits[i_trit] = 0;

  // Scan bits left to right.
  for (i_byte = 0; i_byte < n_bytes; i_byte++) {

    unsigned char byte = bytes[i_byte];

    for (mask = 0x80; mask; mask >>= 1) {
      // Compute the next bit.
      int bit = (byte & mask) != 0;

      // Update the trit representation
      trits[0] = trits[0] * 2 + bit;
      for (i_trit = 1; i_trit < n_trits; i_trit++) {
        trits[i_trit] *= 2;
        if (trits[i_trit - 1] > 2) {
          trits[i_trit - 1] -= 3;
          trits[i_trit]++;
        }
      }
    }
  }
}

// This test uses 64-bit quantities, but the trit 
// converter will work for buffers of any size.
int main(void)
{
  int i;

  // Make a byte buffer for an easy to recognize value.
  #define N_BYTES 7
  unsigned char bytes [N_BYTES] = 
    { 0xab, 0xcd, 0xef, 0xff, 0xfe, 0xdc, 0xba };

  // Make a trit buffer.  A 64 bit quantity may need up to 42 trits.
  #define N_TRITS 42
  unsigned char trits [N_TRITS];

  to_trits(bytes, N_BYTES, trits, N_TRITS);

  unsigned long long val = 0;
  for (i = N_TRITS - 1; i >= 0; i--) {
    printf("%d", trits[i]);
    val = val * 3 + trits[i];
  }
  // Should prinet value in original byte buffer.
  printf("\n%llx\n", val);

  return 0;
}