В теории кодирования , A - код постоянного веса , также называется м -of- п - код , является обнаружение и исправление ошибок кода , где все кодовые слова одни и те же вес Хэмминга . Один горячий код и сбалансированный код широко используются два вида постоянного веса кода.
Теория тесно связана с теорией конструкций (таких как t- конструкции и системы Штейнера ). Большая часть работы в этой очень важной области дискретной математики связана с двоичными кодами постоянного веса.
Двоичные коды с постоянным весом имеют несколько применений, включая скачкообразную перестройку частоты в сетях GSM . [1] В большинстве штрих-кодов используется двоичный код с постоянным весом, чтобы упростить автоматическую установку порогового значения. В большинстве линейных кодов используется либо код с постоянным весом, либо парный код несоответствия с почти постоянным весом . Помимо использования в качестве кодов исправления ошибок, большое пространство между кодовыми словами также можно использовать при проектировании асинхронных схем, таких как схемы, нечувствительные к задержке .
Коды с постоянным весом, как и коды Бергера , могут обнаруживать все однонаправленные ошибки.
А ( п , д , ш )
Центральная проблема, связанная с кодами постоянного веса, заключается в следующем: каково максимальное количество кодовых слов в двоичном коде постоянного веса с длиной , Расстояние Хэмминга , а вес ? Этот номер называется.
За исключением некоторых тривиальных наблюдений, обычно невозможно вычислить эти числа прямым способом. Верхние оценки даются несколькими важными теоремами, такими как первая и вторая границы Джонсона , [2], а лучшие верхние оценки иногда можно найти другими способами. Нижние границы чаще всего находят путем отображения конкретных кодов либо с использованием различных методов из дискретной математики, либо путем интенсивного компьютерного поиска. Большая таблица таких рекордных кодов была опубликована в 1990 г. [3] и расширена до более длинных кодов (но только для этих значений а также которые актуальны для приложения GSM) был опубликован в 2006 г. [1]
Коды 1 из N
Особым случаем кодов с постоянным весом являются коды, состоящие из N , которые кодируют бит в кодовом слове биты. Код «один из двух» использует кодовые слова 01 и 10 для кодирования битов «0» и «1». Код «один из четырех» может использовать слова 0001, 0010, 0100, 1000 для кодирования двух битов 00, 01, 10 и 11. Примером является кодирование с двумя направляющими и звено цепи [4], используемое в нечувствительных к задержке схемы. Для этих кодов а также .
Некоторые из наиболее заметных применений одноразовых кодов включают в себя двухфазный код метки, использующий код 1 из 2; Позиционно-импульсная модуляция использует код 1 из n ; адресный декодер и т. д.
Сбалансированный код
В теории кодирования , A сбалансированный код является двоичным прямым исправлением ошибок кода , для которого каждое кодовое слово содержит равное число нулевых и единичных битов. Сбалансированные коды были введены Дональдом Кнутом ; [5] они представляют собой подмножество так называемых неупорядоченных кодов, которые представляют собой коды, обладающие тем свойством, что позиции единиц в кодовом слове никогда не являются подмножеством позиций единиц в другом кодовом слове. Как и все неупорядоченные коды, сбалансированные коды подходят для обнаружения всех однонаправленных ошибок в закодированном сообщении. Сбалансированные коды обеспечивают особенно эффективное декодирование, которое может выполняться параллельно. [5] [6] [7]
Некоторые из наиболее заметных применений кодов со сбалансированным весом включают в себя двухфазный код метки, использующий код 1 из 2; При кодировании 6b / 8b используется код 4 из 8; код Адамара является из код (кроме нулевого кодового слова), код три из шести ; и т.п.
Трехпроводное кодирование дорожек, используемое в MIPI C-PHY, можно рассматривать как обобщение кода с постоянным весом на троичный - каждый провод передает троичный сигнал , и в любой момент один из 3 проводов передает низкий уровень, один - передает средний, а один передает высокий сигнал. [8]
m -of- n кодов
An M -of- п код является разъемные обнаружения ошибок кода с длиной кодового слова из п битов, где каждый кодовое слово содержит ровно т экземпляров «один». Одна битовая ошибка приведет к тому, что кодовое слово будет иметь либо m + 1, либо m - 1 «единиц». Пример кода m -of- n - это код 2 из 5, используемый Почтовой службой США .
Самая простая реализация - добавить строку из единиц к исходным данным до тех пор, пока она не будет содержать m единиц, а затем добавить нули для создания кода длины n .
Пример:
Исходные 3 бита данных | Добавленные биты |
---|---|
000 | 111 |
001 | 110 |
010 | 110 |
011 | 100 |
100 | 110 |
101 | 100 |
110 | 100 |
111 | 000 |
Некоторые из наиболее заметных применений кодов с постоянным весом, помимо уже упомянутых выше кодов с одним горячим и сбалансированным весом, включают: Code 39 использует код 3 из 9; В двоично-десятичном кодированном десятичном коде используется код 2 из 7, код 2 из 5 и т. д.
Рекомендации
- ^ a b Д. Х. Смит, Л. А. Хьюз и С. Перкинс (2006). « Новая таблица кодов постоянного веса для длины более 28 ». Электронный журнал комбинаторики 13 .
- ^ См. Стр. 526–527 из FJ MacWilliams и NJA Sloane (1979). Теория кодов, исправляющих ошибки . Амстердам: Северная Голландия.
- ^ AE Брауэр, Джеймс Б. Ширер, NJA Sloane и Уоррен Д. Смит (1990). «Новая таблица кодов постоянного веса». IEEE Transactions of Information Theory 36 .
- ^ WJ Bainbridge; А. Бардсли; RW McGuffin. «Проектирование системы на кристалле с использованием самосинхронных сетей на кристалле» .
- ^ а б Д. Кнут (январь 1986 г.). «Эффективные сбалансированные коды» (PDF) . IEEE Transactions по теории информации . 32 (1): 51–53. DOI : 10.1109 / TIT.1986.1057136 .[ постоянная мертвая ссылка ]
- ^ Сулейман аль-Бассам; Белла Бозе (март 1990 г.). «О сбалансированных кодах». IEEE Transactions по теории информации . 36 (2): 406–408. DOI : 10.1109 / 18.52490 .
- ^ К. Шухамер Имминк и Дж. Вебер (2010). «Очень эффективные сбалансированные коды» . Журнал IEEE по избранным областям коммуникаций . 28 : 188–192. DOI : 10,1109 / jsac.2010.100207 . Проверено 12 февраля 2018 . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Демистификация подсистемы MIPI C-PHY / DPHY - компромиссы, проблемы и принятие» ( зеркало )
Внешние ссылки
- Таблица нижних границ А ( п , d , ш ) {\ Displaystyle А (п, д, ш)} поддерживается Андриес Брауэр (обновлением ранее таблиц по Neil Sloane и EM Дожди )
- Таблица верхних границ А ( п , d , ш ) {\ Displaystyle А (п, д, ш)} поддерживается Эриком Агреллом