Код постоянного веса

Метод кодирования данных в средствах связи

В теории кодирования код с постоянным весом , также называемый кодом m -of- n , представляет собой код обнаружения и исправления ошибок , в котором все кодовые слова имеют один и тот же вес Хэмминга . Горячий код и сбалансированный код — это два широко используемых типа кода с постоянным весом.

Эта теория тесно связана с теорией планов (таких как t -планы и системы Штейнера ). Большая часть работ в этой области дискретной математики посвящена двоичным кодам с постоянным весом.

Двоичные коды с постоянным весом имеют несколько применений, включая скачкообразную перестройку частоты в сетях GSM . ^[1] В большинстве штрих-кодов используется двоичный код постоянного веса, чтобы упростить автоматическую настройку порога яркости, который отличает черные и белые полосы. В большинстве линейных кодов используется либо код с постоянным весом, либо парный код несоответствия с почти постоянным весом . Помимо использования в качестве кодов исправления ошибок, большой интервал между кодовыми словами также может использоваться при разработке асинхронных схем , таких как схемы, нечувствительные к задержке .

Коды с постоянным весом, такие как коды Бергера , могут обнаруживать все однонаправленные ошибки.

А ( п , д , ш )

Основная проблема, касающаяся кодов с постоянным весом, заключается в следующем: каково максимальное количество кодовых слов в двоичном коде с постоянным весом с длиной , расстоянием Хэмминга и весом ? Этот номер называется . ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle w}$ ${\displaystyle A(n,d,w)}$

За исключением некоторых тривиальных наблюдений, обычно невозможно вычислить эти числа простым способом. Верхние границы задаются несколькими важными теоремами, такими как первая и вторая границы Джонсона ^[2] , а лучшие верхние границы иногда можно найти другими способами. Нижние границы чаще всего находятся путем демонстрации конкретных кодов либо с использованием различных методов дискретной математики, либо с помощью тщательного компьютерного поиска. Большая таблица таких рекордных кодов была опубликована в 1990 году ^[3] , а расширение к более длинным кодам (но только для тех значений и, которые актуальны для применения GSM) было опубликовано в 2006 году. ^[1] ${\displaystyle d}$ ${\displaystyle w}$

1 из N кодов

Особым случаем кодов с постоянным весом являются коды «один из N» , которые кодируют биты в кодовом слове, состоящем из битов. Код «один из двух» использует кодовые слова 01 и 10 для кодирования битов «0» и «1». Код «один из четырех» может использовать слова 0001, 0010, 0100, 1000 для кодирования двух битов 00, 01, 10 и 11. Примером является кодирование с двумя рельсами и звено цепи ^[4] , используемое в нечувствительных к задержке кодах. схемы. Для этих кодов и . ${\displaystyle \log _{2}N}$ ${\displaystyle N}$ ${\displaystyle n=N,~d=2,~w=1}$ ${\displaystyle A(n,d,w)=n}$

Некоторые из наиболее заметных применений одногорячих кодов включают в себя код двухфазной метки , использующий код 1 из 2; в позиционно-импульсной модуляции используется код «1 из n» ; декодер адреса и т. д.

Сбалансированный код

В теории кодирования сбалансированный код — это двоичный код с прямым исправлением ошибок , для которого каждое кодовое слово содержит равное количество нулевых и единицовых битов. Сбалансированные коды были введены Дональдом Кнутом ; ^[5] они представляют собой подмножество так называемых неупорядоченных кодов, которые представляют собой коды, обладающие тем свойством, что позиции единиц в кодовом слове никогда не являются подмножеством позиций единиц в другом кодовом слове. Как и все неупорядоченные коды, сбалансированные коды подходят для обнаружения всех однонаправленных ошибок в закодированном сообщении. Сбалансированные коды обеспечивают особенно эффективное декодирование, которое может осуществляться параллельно. ^{[5] [6] [7]}

Некоторые из наиболее заметных применений кодов сбалансированного веса включают в себя код двухфазной метки , использующий код 1 из 2; Кодирование 6b/8b использует код 4 из 8; код Адамара представляет собой код (за исключением нулевого кодового слова), код три из шести ; и т. д. ${\displaystyle 2^{k-1}}$ ${\displaystyle 2^{k}}$

Трехпроводное кодирование, используемое в MIPI C-PHY, можно рассматривать как обобщение кода с постоянным весом на троичный — каждый провод передает троичный сигнал , и в любой момент один из трех проводов передает низкий уровень, другой — низкий. передача среднего, а один передает высокий сигнал. ^[8]

m -of- n кодов

Код m -of- n — это разделимый код обнаружения ошибок с длиной кодового слова n бит, где каждое кодовое слово содержит ровно m экземпляров «единицы». Ошибка в один бит приведет к тому, что в кодовом слове будет либо m + 1 , либо m − 1 «единиц». Примером кода m -of- n является код 2 из 5, используемый Почтовой службой США .

Самая простая реализация — добавить к исходным данным строку единиц, пока она не будет содержать m единиц, а затем добавить нули, чтобы создать код длины n .

Пример:

Некоторые из наиболее заметных применений кодов с постоянным весом, помимо уже упомянутых выше кодов с одним горячим и сбалансированным весом, включают в себя код 39 , в котором используется код 3 из 9; Двоично-десятичный код использует код 2 из 7, код 2 из 5 и т. д.

Рекомендации

1. DH Smith, LA Hughes и S. Perkins (2006). «Новая таблица кодов постоянного веса длиной более 28». Электронный журнал комбинаторики 13 .
2. См. стр. 526–527 Ф. Дж. МакВильямса и NJA Слоана (1979). Теория кодов, исправляющих ошибки . Амстердам: Северная Голландия.
3. А. Э. Брауэр, Джеймс Б. Ширер, NJA Слоан и Уоррен Д. Смит (1990). «Новая таблица кодов постоянного веса». Транзакции IEEE теории информации 36 .
4. У. Дж. Бейнбридж; А. Бардсли; Р.В. Макгаффин. «Проектирование системы на кристалле с использованием самосинхронных сетей на кристалле».
5. DE Knuth (январь 1986 г.). «Эффективные сбалансированные коды» (PDF) . Транзакции IEEE по теории информации . 32 (1): 51–53. дои : 10.1109/TIT.1986.1057136.^{[ постоянная мертвая ссылка ]}
6. Сулейман Аль-Бассам; Белла Бозе (март 1990 г.). «О сбалансированных кодах». Транзакции IEEE по теории информации . 36 (2): 406–408. дои : 10.1109/18.52490.
7. К. Шухамер Имминк и Дж. Вебер (2010). «Очень эффективные сбалансированные коды». Журнал IEEE по избранным областям коммуникаций . 28 (2): 188–192. дои : 10.1109/jsac.2010.100207. S2CID  8596702 . Проверено 12 февраля 2018 г.
8. «Демистификация подсистемы MIPI C-PHY / DPHY - компромиссы, проблемы и внедрение» (зеркало)

Внешние ссылки

• Таблица нижних границ для A ( n , d , w ) {\displaystyle A(n,d,w)}, поддерживаемая Андрисом Брауэром
• Таблица верхних границ для A ( n , d , w ) {\displaystyle A(n,d,w)}, поддерживаемая Эриком Агреллом