Код запятой
Эта статья в значительной степени или полностью опирается на один источник . ( апрель 2024 г. ) |
Код с запятой — это тип кода без префикса, в котором запятая , определенный символ или последовательность символов, встречается в конце кодового слова и никогда не встречается в противном случае. [1] Это интуитивный способ выражения массивов.
Например, кодирование Фибоначчи — это код с запятой, в котором запятая 11
. 11
и 1011
являются действительными кодовыми словами Фибоначчи, но 101
, 0111
, и 11011
нет.
Примеры
[ редактировать ]- Унарное кодирование , в котором стоит запятая
0
. Это позволяет использовать значения NULL (когда код и запятая представляют собой одно целое).0
, значение может быть равно NULL или 0). - Кодирование Фибоначчи , в котором запятая
11
. - Все коды Хаффмана можно преобразовать в коды с запятыми, добавив перед ними
1
ко всему коду и используя один0
как код и запятая.
Символ | Код | Код запятой |
---|---|---|
Запятая | - (Н/Д) | 0 |
0 | 00 | 100 |
1 | 01 | 101 |
2 | 10 | 110 |
3 | 11 | 111 |
Определение слова - это количество символов, оканчивающихся запятой, что эквивалентно пробелу .
- Аксиома 50% запятых во всех данных. Можно показать, что все подразумеваемые данные, в частности биективные данные переменной длины, состоят ровно на 50% из запятых.
Все зашифрованные данные или соответствующим образом обработанные данные одинаковой длины обладают так называемой подразумеваемой вероятностью .
Такие данные, которые можно назвать «общими данными», можно анализировать с использованием любого чередующегося унарного кода в качестве заголовков, где дополнительные биективные биты (равные длине только что прочитанного унарного кода) считываются как данные, в то время как унарный код служит введением или заголовком. для данных. Этот заголовок служит запятой. Данные можно считывать в режиме чередования между каждым битом заголовка или в режиме после чтения, когда данные считываются только после того, как весь унарный код заголовка прочитан, как кодирование Чен-Хо .
С помощью методов случайного блуждания и статистического суммирования можно увидеть, что все общие данные имеют заголовок или запятую длиной в среднем 2 бита, а данные - еще 2 бита (минимум 1).
Это также позволяет использовать недорогой алгоритм увеличения базы перед передачей в недвоичных каналах связи, таких как каналы связи с основанием 3 или 5.
н | РЛ-код | Следующий код | Биективные данные (не NULL) | Запятые |
---|---|---|---|---|
1 | 1 ? | 0 ? | ? (1=1,2=2) | , |
2 | 1 ? 1 ? | 0 ? 0 ? | ?? (3,4,5,6=11,12,21,22) | ,, |
3 | 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? | ??? | ,,, |
4 | 1 ? 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? 0 ? | ???? | ,,,, |
5 | 1 ? 1 ? 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? 0 ? 0 ? | ????? | ,,,,, |
6 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? | ?????? | ,,,,,, |
7 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? | ??????? | ,,,,,,, |
8 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? | ???????? | ,,,,,,,, |
9 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? | ????????? | ,,,,,,,,, |
10 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? | ?????????? | ,,,,,,,,,, |
... |
Где '?' равно «1» или «2» для значения биективной цифры, которая не требует дальнейшей обработки.
Конечно, мы используем одну запятую для разделения каждого поля данных, тем самым показывая, что все данные на 50% состоят из запятых. Это хорошо видно из подразумеваемой вероятности 50% для 0
код в кодах базы Хаффмана 3: 0
, 10
, 11
(чистая 2/3 или 66,66% запятых) или код запятой с основанием 5, показанный выше. Коэффициент стоимости за символ связи с более высокой базой должен поддерживать близкие к логарифмическим значениям. для данных и менее 2 битов для символа запятой для обеспечения экономической эффективности.
Этот метод гарантирует наличие «1» или «2» после каждого «0» (запятая), и это свойство может быть полезно при проектировании проблем синхронизации при передаче. Преобразование известного двоичного значения в троичное может оказаться довольно дорогостоящим, если только стоимость троичного бита не будет уменьшена до уровня, аналогичного стоимости двоичного бита, поэтому этот бит можно мультиплексировать в отдельный двоичный канал, если затраты совпадают (для этого может потребоваться чтение дополнительного ' хвостовая/конечная часть 2-битных чистых данных для двоичного канала (после первого бита первого изменения, поскольку это не мгновенно декодируемый код, просто читайте, если используется мгновенно декодируемый унарный код), чтобы быть похожим на 2 средних троичных бита, оставшиеся в первичном канале, эквивалентны бит до того, как будут учтены сравнения затрат).
Без учета мультиплексирования этот метод имеет эффективность чтения 3 троичных цифр при чтении 4 двоичных битов или 1,33 бита. Или
- Аксиома о 66,66% (2/3) запятых во всех данных. Можно показать, что все подразумеваемые данные, в частности данные переменной длины, состоят ровно на 66,66% (2/3) запятых.
н | РЛ-код | Следующий код | Биективные данные (имеет NULL) | Запятые |
---|---|---|---|---|
1 | 1 | 0 | НОЛЬ (или 0) | , |
2 | 1 ? 1 | 0 ? 0 | ? (1=1,2=2) | ,, |
3 | 1 ? 1 ? 1 | 0 ? 0 ? 0 | ?? (3,4,5,6=11,12,21,22) | ,,, |
4 | 1 ? 1 ? 1 ? 1 | 0 ? 0 ? 0 ? 0 | ??? | ,,,, |
5 | 1 ? 1 ? 1 ? 1 ? 1 | 0 ? 0 ? 0 ? 0 ? 0 | ???? | ,,,,, |
6 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 | 0 ? 0 ? 0 ? 0 ? 0 ? 0 | ????? | ,,,,,, |
7 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 | ?????? | ,,,,,,, |
8 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 | ??????? | ,,,,,,,, |
9 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 | ???????? | ,,,,,,,,, |
10 | 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 | 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 ? 0 | ????????? | ,,,,,,,,,, |
... |
Где '?' равно «1» или «2» для значения биективной цифры, которая не требует дальнейшей обработки. Этот метод приводит к статистическому сходству с простым «предполагаемым чтением» кодов Хаффмана по основанию 3: 0
, 10
, 11
(чистые 2/3 или 66,66% запятых).
С помощью методов случайного блуждания и статистического суммирования можно увидеть, что все общие данные имеют заголовок или запятую в среднем из 2 битов, а данные - из дополнительного 1 бита (минимум 0).
Это не гарантирует наличия «1» или «2» после каждого «0» (запятая) — свойства, которое может быть полезно при проектировании проблем синхронизации при передаче.
Этот метод имеет эффективность чтения 2 троичных цифр при чтении 3 двоичных битов или 1,5 двоичных битов на троичную цифру. Или
- 34,375% | 31,25% (~ 1/3) пишут запятые для повышения эффективности с помощью числового разделения. Подразумеваемые операции чтения и записи с использованием методов числового разделения (числа «m», разделенные на «n» разделов, приводят к перестановкам n^m), аналогично Чен-Хо и Герцу. кодирование показывает большую эффективность как чтения, так и записи, аналогично почти случайному распределению. Таким образом, использование кодов теряет смысл, а использование более высоких оснований становится более важным. Аналогично, запятая для записи становится любым числом в базе, запятая для чтения — это заголовок, показанный ниже, коды по основанию 4 Хаффмана:
0
,10
,110
,111
.
Основное преимущество этого метода, помимо более высокой эффективности, заключается в том, что не требуется базового преобразования, которое потребовало бы сначала прочитать весь поток, а затем преобразовать. Недостаток заключается в том, что средняя длина числа становится больше, что похоже на генерацию случайных чисел, а проблемы синхронизации, которые управляют троичной передачей, выходят на первый план. При m=2 и n=2 мы получаем, не забывая, что значение '(2)' по существу равно 0 битам:
Двоичное кодирование | Троичные цифры | ||||||||
---|---|---|---|---|---|---|---|---|---|
ЧТЕНИЕ — кодовое пространство (128 состояний) | б3 | б2 | б1 | б0 | Закодированные значения | Описание | ЗАПИСЫ - События (100 состояний) | ||
50% (64 штата) | 0 | а | б | (0–1) (0–1) | Две младшие цифры | 44,44% (45 штатов) | |||
25% (32 штата) | 1 | 0 | а | (2) (0–1) | Одна нижняя цифра, на одну большую цифру | 22,22% (22 штата) | |||
12,5% (16 штатов) | 1 | 1 | 0 | б | (0–1) (2) | 22,22% (22 штата) | |||
12,5% (16 штатов) | 1 | 1 | 1 | (2) (2) | Две старшие цифры | 11,11% (11 штатов) |
Таким образом, этот метод имеет эффективность чтения 2 троичных цифр для чтения двоичные биты или 1,5625 двоичных битов на троичную цифру. Или .
Эффективность записи 2 троичных цифр для записи бит или 1,61 двоичный бит/троичная цифра, или
- Кардинальные числа для эффективного преобразования оснований. Поскольку было установлено, что коды с запятыми очень похожи на преобразование оснований, единственной проблемой является эффективность и время, прямое преобразование/отображение 19 двоичных битов. числа до 12 троичных тритов цифры позволяют добиться эффективности или эффективность в зависимости от метода расчета. Это работает, потому что и ≃ . Это, конечно, скорее теоретическая конструкция, и в ней не упоминается время при попытке применить ее к методам тройной передачи. Однако оно оставляет коды для разработки с учетом проблем времени.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Уэйд, Грэм (8 сентября 1994 г.). Кодирование и обработка сигналов . Издательство Кембриджского университета. п. 56. ИСБН 978-0-521-42336-6 .