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

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

В теории кодирования код постоянного веса , также называемый кодом m -из -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» , которые кодируют биты в кодовом слове битов. Код «один из двух» использует кодовые слова 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; код Адамара, являющийся кодом 1 из 2 (за исключением нулевого кодового слова), код три из шести и т. д. ${\displaystyle 2^{k-1}}$ ${\displaystyle 2^{k}}$

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

м-из-нкоды

Код m -из -n — это разделяемый код обнаружения ошибок с длиной кодового слова n бит, где каждое кодовое слово содержит ровно m экземпляров «единицы». Ошибка в одном бите приведет к тому, что кодовое слово будет иметь либо m + 1 , либо m − 1 «единиц». Примером кода m -из -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 в FJ MacWilliams и NJA Sloane (1979). Теория кодов, исправляющих ошибки . Амстердам: Северная Голландия.
3. AE Brouwer, James B. Shearer, NJA Sloane и Warren D. Smith (1990). "Новая таблица кодов постоянного веса". Труды IEEE по теории информации 36 .
4. WJ Bainbridge; A. Bardsley; RW McGuffin. «Проектирование систем на кристалле с использованием самосинхронизирующихся сетей на кристалле».
5. DE Knuth (январь 1986 г.). "Эффективные сбалансированные коды" (PDF) . IEEE Transactions on Information Theory . 32 (1): 51–53. doi :10.1109/TIT.1986.1057136.^{[ постоянная мертвая ссылка ]}
6. Сулейман Аль-Бассам; Белла Бозе (март 1990 г.). «О сбалансированных кодах». Труды IEEE по теории информации . 36 (2): 406–408. doi :10.1109/18.52490.
7. K. Schouhamer Immink и J. Weber (2010). «Очень эффективные сбалансированные коды». IEEE Journal on Selected Areas in Communications . 28 (2): 188–192. doi :10.1109/jsac.2010.100207. S2CID  8596702. Получено 12.02.2018 .
8. «Демистификация подсистемы MIPI C-PHY / DPHY — компромиссы, проблемы и принятие» (зеркало)

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

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