Введение
Граница параметров блочного кода
In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.
В математике и информатике, в области теории кодирования, граница Хамминга — это ограничение на параметры произвольного блочного кода: она также известна как граница упаковки сфер или объемная граница, исходя из интерпретации в терминах упаковки шаров в метрике Хамминга в пространство всех возможных кодовых слов. Она устанавливает важное ограничение на эффективность, с которой любой код, исправляющий ошибки, может использовать пространство, в котором расположены его кодовые слова. Код, достигающий границы Хамминга, называется совершенным кодом.
In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.
Основные сведения о кодах исправления ошибок
Оригинальное сообщение и его закодированная версия состоят из алфавита, содержащего q букв. Каждое кодовое слово содержит n букв. Оригинальное сообщение (длиной m) короче n букв. Сообщение преобразуется в кодовое слово длиной n с помощью алгоритма кодирования, передается по зашумленному каналу и, наконец, декодируется приемником. Процесс декодирования интерпретирует искаженное кодовое слово, которое просто называют словом, как наиболее близкое действительное кодовое слово к принятой последовательности из n букв. Математически существует ровно qm возможных сообщений длиной m, и каждое сообщение можно рассматривать как вектор длины m. Схема кодирования преобразует m-мерный вектор в n-мерный вектор. Существует ровно qm допустимых кодовых слов, но может быть принято любое из qn слов, поскольку зашумленный канал может исказить одну или несколько из n букв при передаче кодового слова.
Предварительные определения
Алфавит – это набор символов с элементами. Множество строк длины над алфавитом обозначается (в этом множестве строк содержится различных строк). -арный блочный код длины – это подмножество строк над алфавитом, где алфавит – любой алфавит, содержащий элементов. (Выбор алфавита не влияет на результат, при условии, что размер алфавита равен .)
Коды совершенства
Коды, достигающие границы Хамминга, называются совершенными кодами. Примеры включают коды, имеющие только одно кодовое слово, и коды, представляющие собой всё пространство. Другой пример дают повторные коды, где каждый символ сообщения повторяется нечетное фиксированное число раз для получения кодового слова при q = 2. Все эти примеры часто называют тривиальными совершенными кодами. В 1973 году Тиетявяйнен доказал, что любой нетривиальный совершенный код над алфавитом, являющимся степенью простого числа, имеет параметры кода Хамминга или кода Голея. Совершенный код можно интерпретировать как код, в котором шары радиуса Хамминга t с центрами в кодовых словах точно заполняют пространство (t – радиус покрытия = радиус упаковки). Квазисовершенный код – это код, в котором шары радиуса Хамминга t с центрами в кодовых словах не пересекаются, а шары радиуса t+1 покрывают пространство, возможно, с некоторыми перекрытиями. Другими словами, код является квазисовершенным, если его радиус покрытия на единицу больше радиуса упаковки.