Преобразование потоковых данных в троичные (база-3)

Question

С учетом синхронизированного 3-уровневого (-1,0, + 1) канала между двумя устройствами, каков наиболее эффективный для потока способ преобразования потока битов в представление канала и из него?

Текущий метод состоит в том, чтобы взять 3 двоичных бита и преобразовать их в два трита.Я полагаю, что это теряет 11% возможностей канала (поскольку 1 из 9 возможных пар никогда не используется).Я подозреваю, что группировка может уменьшить эти потери, но этот проект использует 8-битные устройства, поэтому размеры моей группы ограничены.

Я хотел бы использовать divmod-3, но у меня нет всего двоичного файлапоток доступен в любой точке.Есть ли метод для «добавочного» divmod3, который может начинаться в LSB?

Как нетренированное предположение, я полагаю, что должен быть подход типа «проанализировать следующие 3 бита, удалить один бит, изменить один бит» - но я не смог найти что-то работающее.

Answer 1

Попробуйте упаковать 11 бит (2048 кодов) в 7 трит (2187 кодов), вы получите менее 1% накладных расходов.Есть несколько методов.Первый прост: таблица поиска.Второй - это divmod-3.Третий - это некоторая основная битовая / тритиальная схема, как показано ниже.

Первый этап: упаковать первые 9 битов, используя схему 3-бит-в-2-трит.

Второй этап: использование более сложной логики для упаковки 6 троитов и 2 битов в 7 тритов:

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

Неиспользуемые коды:

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

UPD другие подходящие отношения упаковки: 19b -> 11т (накладные расходы ~ 0,1%), 84b -> 53т (накладные расходы ~ 0,0035%), но, похоже, это превышение.

Answer 2

Не могли бы вы ущипнуть некоторые идеи из http://en.wikipedia.org/wiki/Arithmetic_coding?