Коды Хемминга

Коды Хемминга— простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, чтосиндром

, где— принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

Общий метод декодирования линейных кодов

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова соответствует наиболее вероятное переданное слово. Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора вычисляетсясиндром. Поскольку, где— кодовое слово, а— вектор ошибки, то. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Линейные циклические коды Линейные циклические коды

Несмотря на то, что декодирование линейных кодов значительно проще декодирования большинства нелинейных, для большинства кодов этот процесс всё ещё достаточно сложен. Циклические коды, кроме более простого декодирования, обладают и другими важными свойствами.

Циклическим кодом является линейный код, обладающий следующим свойством: если является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово представляется в виде полинома. При этом циклический сдвиг кодового слова эквивалентен умножению многочлена напо модулю.

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то естьмогут принимать значения0или1.

Коды crc

Коды CRC(циклическая избыточная проверка) являютсясистематическимикодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деленияна. Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома задаёт конкретный код CRC.

9 Код с исправлением одиночной ошибки. Код Хеллмана.

1. Код с исправлением одиночной ошибки.

Если кодовые комбинации составлены так, что они отличаются друг от друга на кодовое расстояние d ≥3, то они образуют корректирующий код, который позволяет по имеющейся в кодовой комбинации избыточности обнаруживать и исправлять ошибки.

Корректирующие коды делятся на систематические и несистематические. Систематически или линейным, кодом называется код, имеющий постоянную длину и четкое деление всех кодовых элементов на информационные k и контрольные m элементы, занимающие определенные места в комбинациях. Составление корректирующих кодов производится примерно по следующему правилу. Сначала определяется количество контрольных символов m, которое следует добавить к данной кодовой комбинации, состоящей из k информационных символов. Далее устанавливается место, где эти контрольные символы должны быть расставлены в комбинации, и их состав, то есть является ли данный контрольный символ 1 или 0. На приеме обычно применяется проверка на четность определенной части разрядов.

2. Код Хеллмана

Генерация ключа

В системе Меркля-Хеллмана ключи состоят из последовательностей. Открытый ключ представляет собой «сложную» последовательность, закрытый ключ состоит из «простой» или супервозрастающей последовательности, а также двух дополнительных чисел – множителя и модуля, которые используются как для преобразования супервозрастающей последовательности в «сложную» (генерация открытого ключа), так и для преобразования суммы подмножества «сложной» последовательности в сумму подмножества «простой» (расшифровка). Последняя задача решается за полиномиальное время.

Шифрование

Сначала исходный текст необходимо представить в двоичном виде и разбить его на блоки, равные по длине с открытым ключом. Далее из последовательности, образующей открытый ключ, выбираются только те элементы, которые по порядку соответствуют 1 в двоичной записи исходного текста, игнорируя при этом элементы, соответствующие 0 биту. После этого элементы полученного подмножества складываются. Найденная в результате сумма и есть шифротекст.

Расшифровка

Расшифровка является возможной в силу того, что множитель и модуль, используемые для генерации открытого ключа из супервозрастающей последовательности, используются также и для преобразования шифротекста в сумму соответствующих элементов супервозрастающей последовательности. Далее, с помощью простого жадного алгоритма, можно расшифровать сообщение, используя O(n) арифметических операций.