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

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

n (неотрицательный)	n (строго положительный)	Унарный код	Альтернатива
0	1	0	1
1	2	10	01
2	3	110	001
3	4	1110	0001
4	5	11110	00001
5	6	111110	000001
6	7	1111110	0000001
7	8	11111110	00000001
8	9	111111110	000000001
9	10	1111111110	0000000001

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

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

для $n=1,2,3,...$ .

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

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

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

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

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

Унарный код используется сегодня [ править ]

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

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

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

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

Стандартные унарные коды длины серии [ править ]

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

н	РЛ-код	Следующий код
1	1	0
2	11	00
3	111	000
4	1111	0000
5	11111	00000
6	111111	000000
7	1111111	0000000
8	11111111	00000000
9	111111111	000000000
10	1111111111	0000000000
...

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

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

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

н	Унарный код	Альтернатива
1	1	0
2	10	01
3	100	011
4	1000	0111
5	10000	01111
6	100000	011111
7	1000000	0111111
8	10000000	01111111
9	100000000	011111111
10	1000000000	0111111111
...

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

Симметричные унарные коды [ править ]

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

n (строго положительный)	Унарный код	Альтернатива	n (неотрицательный)
1	1	0	0
2	00	11	1
3	010	101	2
4	0110	1001	3
5	01110	10001	4
6	011110	100001	5
7	0111110	1000001	6
8	01111110	10000001	7
9	011111110	100000001	8
10	0111111110	1000000001	9
...

Канонические унарные коды [ править ]

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

н	Унарный код	Альтернатива
1	1	0
2	01	10
3	001	110
4	0001	1110
5	00001	11110
6	000001	111110
7	0000001	1111110
8	00000001	11111110
9	000000001	111111110
10	0000000000	1111111111

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

Обобщенное унарное кодирование [ править ]

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

н	Унарный код	Обобщенный унарный
0	0	0000000
1	10	0000111
2	110	0001110
3	1110	0011100
4	11110	0111000
5	111110	1110000
6	1111110	0010111
7	11111110	0101110
8	111111110	1011100
9	1111111110	0111001
10	11111111110	1110010
11	111111111110	0100111
12	1111111111110	1001110
13	11111111111110	0011101
14	111111111111110	0111010
15	1111111111111110	1110100

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

См. также [ править ]

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

Примечания [ править ]

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

Ссылки [ править ]

^ Фите, ИК; Сын, HS (2007). «Нейросетевые модели производства, обучения и кодирования пения птиц». В Сквайре, Л.; Олбрайт, Т.; Блум, Ф.; Гейдж, Ф.; Спитцер, Н. (ред.). Новая энциклопедия неврологии . Эльзевир .
^ Мур, Дж. М.; и др. (2011). «Конвергенция двигательных путей предсказывает размер репертуара слогов у осциновых птиц» . Учеб. Натл. акад. наук. США . 108 (39): 16440–16445. Бибкод : 2011PNAS..10816440M . дои : 10.1073/pnas.1102077108 . ПМК 3182746 . ПМИД 21918109 .
^ Как, С. (2015). «Обобщенное унарное кодирование». Схемы, системы и обработка сигналов . 35 (4): 1419–1426. дои : 10.1007/s00034-015-0120-7 . S2CID 27902257 .

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

[Fiete_2007-2] Фите, ИК; Сын, HS (2007). «Нейросетевые модели производства, обучения и кодирования пения птиц». В Сквайре, Л.; Олбрайт, Т.; Блум, Ф.; Гейдж, Ф.; Спитцер, Н. (ред.). Новая энциклопедия неврологии . Эльзевир .

[Moore_2011-3] Мур, Дж. М.; и др. (2011). «Конвергенция двигательных путей предсказывает размер репертуара слогов у осциновых птиц» . Учеб. Натл. акад. наук. США . 108 (39): 16440–16445. Бибкод : 2011PNAS..10816440M . дои : 10.1073/pnas.1102077108 . ПМК 3182746 . ПМИД 21918109 .

[Kak_2015-4] Как, С. (2015). «Обобщенное унарное кодирование». Схемы, системы и обработка сигналов . 35 (4): 1419–1426. дои : 10.1007/s00034-015-0120-7 . S2CID 27902257 .

[номер 1]

[1]

[2]

[3]