Код постоянного веса, равновесный код или код m-из-n — это код контроля и исправления ошибок, где все кодовые слова имеют один и тот же вес Хэмминга. Унитарный код и сбалансированный код являются двумя широко используемыми видами кодов постоянной ширины.
Теория тесно связана с теорией схем (таких как t-схемы и системы Штейнера). Большинство работ в этой области дискретной математики рассматривают бинарные коды постоянного веса.
Двоичные равновесные коды имеют некоторые приложения, включая псевдослучайную перестройку рабочей частоты в GSM сетях. Большинство штриховых кодов используют двоичный равновесный код для упрощения автоматической настройки порога яркости, при котором различаются чёрные и белые полосы. Большинство линейных кодов используют либо равновесный код, либо почти равновесный попарно-сбалансированный код. Помимо использования в качестве кодов коррекции ошибок, большое расстояние между кодовыми словами может быть использовано при проектировании асинхронных схем, таких как .
Коды с постоянным весом, такие как , могут обнаруживать все однонаправленные ошибки.
A(n, d, w) Основная проблема, касающаяся кодов постоянного веса следующая: каково максимальное количество кодовых слов в двоичном коде постоянного веса с длиной , расстоянием Хэмминга и весом ? Это число обозначается .
За исключением некоторых незначительных наблюдений, вычислить эти числа напрямую, как правило, невозможно. Верхние границы определяются несколькими важными теоремами, такими как теоремы Джонсона, а иногда лучшие верхние границы можно найти другими способами. Нижние границы чаще всего определяются путем демонстрации конкретных кодов, либо с использованием различных методов дискретной математики, либо путем интенсивного компьютерного поиска. Большая таблица таких рекордных кодов была опубликована в 1990 году, а расширение для более длинных кодов (но только для тех значений и , которые имеют отношение к применению GSM) было опубликовано в 2006 году.
Коды 1-из-N
Специальным случаем кодов с постоянным весом являются коды один-из-N, которые кодируют бит в кодовое слово из бит. Код один-из-двух использует кодовые слова 01 и 10 для кодировки битов '0' и '1'. Код один-из-четырёх может использовать слова 0001, 0010, 0100, 1000 для кодировки двух бит 00, 01, 10 и 11. Примером является двойное канальное кодирование и цепочечное соединение, используемые в схемах, нечувствительных к задержкам. Для этих кодов и .
Среди наиболее заметных применений кодов один-из-N можно отметить использует 1-из-2 кодировку; Фазово-импульсная модуляция использует 1-из-n кодировку; , и т.д.
Сбалансированный код
В теории кодирования сбалансированный код — это двоичный код с прямым исправлением ошибок в котором каждое кодовое слово содержит равное количество нулей и единиц. Сбалансированные коды были введены Дональдом Кнутот. Они являются подмножеством так называемых неупорядоченных кодов, которые обладают свойством, что позиции единиц в одном кодовом слове никогда не являются подмножеством позиций единиц в другом кодовом слове. Как и все неупорядоченные коды, сбалансированные коды подходят для обнаружения всех в закодированном сообщении. Сбалансированные коды обеспечивают особенно эффективное декодирование, которое может выполняться параллельно.
Среди наиболее заметных применений кодов сбалансированного веса можно выделить: использует 1-из-2 кодировку; использует 4-из-8 кодировку; представляет собой -из- кодировку (за исключением нулевого кодового слова), три-из-шести кодировка; и т.д.
«3-wire lane» кодирование, используемое в C-PHY можно считать обобщением равновесного кода на троичный случай — каждый провод передаёт и в любой момент времени один из трёх проводов передаёт низкий сигнал, один — средний, а один — высокий.
m-из-n кодировки
Код m-из-n — это разделимый код обнаружения ошибок с длиной слова в n бит, в котором каждое кодовое слово содержит ровно m единиц. Одиночная битовая ошибка приведёт к тому, что в кодовом слове будет либо , либо единиц. Примером кода m-из-n является , используемый почтовой службой США.
Простейшая реализация заключается в добавлении к исходным данным строки из единиц до тех пор, пока в них не появится m единиц, затем добавляются нули до получения длины n.
Пример:
+ 3-из-6 код Исходные 3-битные данные Добавленные биты 000 111 001 110 010 110011 100100 110101 100110 100111 000
Наиболее заметные применения кодов с постоянным весом, помимо уже упомянутых выше: Code 39 использует 3-из-9 кодировку Двоично-десятичный код использует 2-из-7 кодировку , и другие
Примечания
Литература
Ссылки Table of lower bounds on maintained by Andries Brouwer Table of upper bounds on maintained by Erik Agrell
Категория:Теория информации Категория:Обнаружение и устранение ошибок