Унарное кодирование

Энтропийное кодирование

Унарное кодирование , ^{[nb 1]} или унарная система счисления , а также иногда называемое кодом термометра , является энтропийным кодированием , которое представляет натуральное число , n , с кодом длины n  + 1 (или n ), обычно с n единицами, за которыми следует ноль (если натуральное число понимается как неотрицательное целое число ) или с n  − 1 единицами, за которыми следует ноль (если натуральное число понимается как строго положительное целое число ). Например, 5 представляется как 111110 или 11110. Некоторые представления используют n или n  − 1 нулей, за которыми следует единица. Единицы и нули взаимозаменяемы без потери общности . Унарное кодирование является как кодом без префиксов, так и самосинхронизирующимся кодом .

Унарное кодирование является оптимально эффективным кодированием для следующего дискретного распределения вероятностей

${\displaystyle \operatorname {P} (n)=2^{-n}\,}$

для . ${\displaystyle n=1,2,3,...}$

При посимвольном кодировании он оптимален для любого геометрического распределения.

${\displaystyle \operatorname {P} (n)=(k-1)k^{-n}\,}$

для которого k ≥ φ = 1,61803398879..., золотое сечение , или, в более общем смысле, для любого дискретного распределения, для которого

${\displaystyle \operatorname {P} (n)\geq \operatorname {P} (n+1)+\operatorname {P} (n+2)\,}$

для . Хотя это оптимальное посимвольное кодирование для таких распределений вероятностей, кодирование Голомба достигает лучшей возможности сжатия для геометрического распределения, поскольку оно не рассматривает входные символы независимо, а скорее неявно группирует входы. По той же причине арифметическое кодирование лучше работает для общих распределений вероятностей, как в последнем случае выше. ${\displaystyle n=1,2,3,...}$

Унарный код, используемый сегодня

Примеры использования унарного кода включают в себя:

• В коде Голомба-Райса для кодирования частной части кодового слова Голомба используется унарное кодирование.
• В UTF-8 унарное кодирование используется в начальном байте многобайтовой последовательности для указания количества байтов в последовательности, чтобы длину последовательности можно было определить без проверки последующих байтов.
• Мгновенно обучаемые нейронные сети используют унарное кодирование для эффективного представления данных.

Унарное кодирование в биологических сетях

Унарное кодирование используется в нейронных цепях, ответственных за производство птичьего пения . ^{[1] [2]} Ядро в мозге певчих птиц, которое играет роль как в обучении, так и в производстве птичьего пения, — это HVC ( высокий вокальный центр ). Командные сигналы для различных нот в птичьем пении исходят из разных точек HVC. Это кодирование работает как пространственное кодирование, которое является эффективной стратегией для биологических цепей из-за его присущей простоты и надежности.

Стандартные унарные коды длин серий

Все двоичные данные определяются способностью представлять унарные числа в виде чередующихся серий из 1 и 0. Это соответствует стандартному определению унарных чисел, т. е. N цифр одного и того же числа 1 или 0. Все серии по определению имеют по крайней мере одну цифру и, таким образом, представляют строго положительные целые числа .

Эти коды гарантированно завершаются корректно на любой длине данных (при чтении произвольных данных) и в (отдельном) цикле записи допускают использование и передачу дополнительного бита (того, который используется для первого бита), сохраняя при этом общую и целочисленную длину унарного кода, равную N.

Уникально декодируемые непрефиксные унарные коды

Ниже приведен пример уникально декодируемых унарных кодов, которые не являются префиксными кодами и не поддаются мгновенному декодированию (для декодирования требуется опережающий просмотр).

Эти коды также (при записи беззнаковых целых чисел) позволяют использовать и передавать дополнительный бит (тот, который используется для первого бита). Таким образом, они способны передавать 'm' целых чисел * N унарных бит и 1 дополнительный бит информации в пределах m*N бит данных.

Симметричные унарные коды

Следующий набор унарных кодов симметричен и может быть прочитан в любом направлении. Он также мгновенно декодируется в любом направлении.

Канонические унарные коды

Для унарных значений, где максимум известен, можно использовать канонические унарные коды, которые имеют несколько числовую природу и отличаются от кодов на основе символов. Это включает в себя начало с числового '0' или '-1' ( ) и максимального количества цифр, затем для каждого шага уменьшая количество цифр на единицу и увеличивая/уменьшая результат на числовую '1'. ${\displaystyle \operatorname {2} ^{n}-1\,}$

Канонические коды могут потребовать меньше времени обработки для декодирования, когда они обрабатываются как числа, а не как строки. Если количество кодов, требуемых на длину символа, отличается от 1, т. е. требуется больше неунарных кодов некоторой длины, это можно сделать путем численного увеличения/уменьшения значений без уменьшения длины в этом случае.

Обобщенное унарное кодирование

Обобщенная версия унарного кодирования была представлена ​​Субхашем Каком для представления чисел гораздо более эффективно, чем стандартное унарное кодирование. ^[3] Вот пример обобщенного унарного кодирования для целых чисел от 0 до 15, требующего всего 7 бит (где три бита произвольно выбираются вместо одного в стандартном унарном кодировании, чтобы показать число). Обратите внимание, что представление является циклическим, где используются маркеры для представления более высоких целых чисел в более высоких циклах.

Обобщенное унарное кодирование требует предварительного указания диапазона представляемых чисел, поскольку этот диапазон определяет количество необходимых бит.

Смотрите также

• Унарная система счисления

Примечания

1. Эквивалентом термина «унарный код» в немецкой научной литературе является « BCD-Zählcode », что можно перевести как « двоично-десятичный код счета». Его не следует путать с похожим немецким термином « BCD-Code », который в английском языке переводится как BCD-код .

Ссылки

1. Fiete, IR; Seung, HS (2007). "Нейросетевые модели создания, обучения и кодирования пения птиц". В Squire, L.; Albright, T.; Bloom, F.; Gage, F.; Spitzer, N. (ред.). Новая энциклопедия нейронауки . Elsevier .
2. Мур, Дж. М.; и др. (2011). «Конвергенция моторных путей предсказывает размер репертуара слогов у певчих птиц». Proc. Natl. Acad. Sci. USA . 108 (39): 16440–16445. Bibcode : 2011PNAS..10816440M. doi : 10.1073/pnas.1102077108 . PMC 3182746. PMID  21918109 . 
3. Kak, S. (2015). «Обобщенное унарное кодирование». Схемы, системы и обработка сигналов . 35 (4): 1419–1426. doi :10.1007/s00034-015-0120-7. S2CID  27902257.