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

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

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

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

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

А ( п , д , ш )

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

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

1 из N кодов

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

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

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

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

Некоторые из наиболее заметных применений кодов сбалансированного веса включают: код двухфазной метки использует код 1 из 2; Кодирование 6b/8b использует код 4 из 8;код Адамара – это $2^{k-1}$ из $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 .

Пример:

код 3 из 6
Исходные 3 бита данных	Добавленные биты
000	111
001	110
010	110
011	100
100	110
101	100
110	100
111	000

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

Ссылки

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

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

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

[smith-1] Перейти обратно: ^а ^б Д. Х. Смит, Л. А. Хьюз и С. Перкинс (2006). « Новая таблица кодов постоянного веса длиной более 28 ». Электронный журнал комбинаторики 13 .

[2] См. стр. 526–527 Ф. Дж. МакВильямса и NJA Слоана (1979). Теория кодов, исправляющих ошибки . Амстердам: Северная Голландия.

[brouwer-3] А. Э. Брауэр, Джеймс Б. Ширер, NJA Слоан и Уоррен Д. Смит (1990). «Новая таблица кодов постоянного веса». Транзакции IEEE теории информации 36 .

[4] У. Дж. Бейнбридж; А. Бардсли; Р.В. Макгаффин. «Проектирование системы на кристалле с использованием самосинхронных сетей на кристалле» .

[knuth-5] Перейти обратно: ^а ^б Д. Е. Кнут (январь 1986 г.). «Эффективные сбалансированные коды» (PDF) . Транзакции IEEE по теории информации . 32 (1): 51–53. дои : 10.1109/TIT.1986.1057136 . ^{[ постоянная мертвая ссылка ]}

[optimal-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 - компромиссы, проблемы и внедрение» ( зеркало )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]