Преобразование потоковых данных в троичные (база-3)
При наличии синхронизированного 3-уровневого (-1,0,+1) канала между двумя устройствами, каков наиболее эффективный для потока способ преобразования потока битов в представление канала и из него?
Текущий метод состоит в том, чтобы взять 3 двоичных разряда и преобразовать их в два числа. Я считаю, что это теряет 11% возможностей канала (поскольку 1 из 9 возможных пар никогда не используется). Я подозреваю, что группировка может уменьшить эти потери, но этот проект использует 8-битные устройства, поэтому размеры моей группы ограничены.
Я хотел бы использовать divmod-3, но у меня нет всего двоичного потока, доступного в какой-либо одной точке. Есть ли метод для "добавочного" divmod3, который может начинаться в LSB?
Как неподготовленное предположение, я предполагаю, что должен быть подход формы "проанализировать следующие 3 бита, удалить один бит, изменить один бит" - но я не смог найти что-то работающее.
2 ответа
Попробуйте упаковать 11 бит (2048 кодов) в 7 трит (2187 кодов), вы получите менее 1% накладных расходов. Есть несколько методов. Первый прост: таблица поиска. Второй - это divmod-3. В-третьих, это какая-то битовая / тритовая основа, как показано ниже.
Первый этап: упаковать первые 9 бит по схеме 3-бит-2-трит:
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 будет использоваться в дальнейшем
Второй этап: использование более сложной логики для упаковки 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%), но, похоже, это превышение.
Не могли бы вы поделиться некоторыми идеями с http://en.wikipedia.org/wiki/Arithmetic_coding?