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

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

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

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

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

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

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

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

Среди наиболее заметных применений кодов один-из-N можно отметить

Двухфазный код использует 1-из-2 кодировку;

Фазово-импульсная модуляция использует 1-из-n кодировку;

Дешифратор адреса,

и т.д.

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

Среди наиболее заметных применений кодов сбалансированного веса можно выделить:

Двухфазный код использует 1-из-2 кодировку;

6b/8b кодирование использует 4-из-8 кодировку;

Код Адамара представляет собой ${\displaystyle 2^{k-1}}$-из-${\displaystyle 2^{k}}$ кодировку (за исключением нулевого кодового слова),

три-из-шести кодировка;

и т.д.

«3-wire lane» кодирование, используемое в MIPI C-PHY^[9] можно считать обобщением равновесного кода на троичный случай — каждый провод передаёт троичный сигнал и в любой момент времени один из трёх проводов передаёт низкий сигнал, один — средний, а один — высокий^[10].

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

Простейшая реализация заключается в добавлении к исходным данным строки из единиц до тех пор, пока в них не появится m единиц, затем добавляются нули до получения длины n.

Пример:

Наиболее заметные применения кодов с постоянным весом, помимо уже упомянутых выше:

Code 39 использует 3-из-9 кодировку

Двоично-десятичный код использует 2-из-7 кодировку

2-из-5 кодировка,

и другие

• Table of lower bounds on ${\displaystyle A(n,d,w)}$ maintained by Andries Brouwer
• Table of upper bounds on ${\displaystyle A(n,d,w)}$ maintained by Erik Agrell