Теория информации


Совершенные и квазисовершенные коды - часть 3


Ее столбцы с номерами 3, 5, 6 и 7 образуют единичную подматрицу. Столбцы с номерами 1, 2 и 4 соответствуют уравнениям для вычисления контрольных бит, например, уравнению соответствует столбец 1101, т.е. для вычисления первого контрольного разряда берутся 1, 2 и 4 биты исходного сообщения или биты 3, 5 и 7 кода.

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

Коды Хэмминга накладывают ограничения на длину слов сообщения: эта длина может быть только числами вида : 1, 4, 11, 26, 57, Но в реальных системах информация передается байтам или машинными словами, т.е. порциями по 8, 16, 32 или 64 бита, что делает использование совершенных кодов не всегда подходящим. Поэтому в таких случаях часто используются квазисовершенные коды.

Квазисовершенные -коды, исправляющие одну ошибку, строятся следующим образом. Выбирается минимальное так, чтобы

Каждое кодовое слово такого кода будет содержать

контрольных разрядов. Из предыдущих соотношений следует, что

Каждому из разрядов присваивается слева-направо номер от 1 до . Для заданного слова сообщения составляются контрольных сумм по модулю 2 значений специально выбранных разрядов кодового слова, которые помещаются в позиции-степени 2 в нем: для

выбираются разряды, содержащие биты исходного сообщения, двоичные числа-номера которых имеют в -м разряде единицу. Для суммы это будут, например, разряды 3, 5, 7 и т.д., для суммы - 3, 6, 7 и т.д. Таким образом, для слова сообщения будет построено кодовое слово . Обозначим сумму по модулю 2 разрядов полученного слова, соответствующих контрольной сумме

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




Начало  Назад  Вперед



Книжный магазин