Добавим к каждому его кодовому слову β1 β 2 β 3 … β n - дополнительный бит β n+1
такой, чтобы β1 + β 2 + β 3 … + β n + β n+1 = 0. (*)
Здесь сумма берется по модулю 2, то есть 1 + 1 = 0.
В полученном двоичном коде порядка n+1,еслипри передаче кодовых слов произойдет изменение в одном из символов β i, то равенство (*)нарушится, что приведет к обнаружению ошибки. Добавленный символ β n+1 называется символом четности.
Коды, которые позволяют при передаче сообщений обнаруживать ошибки, называются кодами с обнаружением ошибок. Ошибки, которые возникают при передаче сообщений, обычно называют помехами. Код, полученный из равномерного двоичного кода порядка nдобавлением символа четности, является кодом с обнаружением ошибок.
Теперь по произвольному равномерному двоичному коду порядка nс кодовыми словами β1 β 2 β 3 … β n построим равномерный двоичный код порядка n·k, для произвольного целого k > 1, с кодовыми словами β1 β1… β1 β 2 β 2…β 2 β 3 … β n β n …β n , где каждый символ β iповторяется подряд k раз. Полученный код также является кодом с обнаружением ошибок, но такой код позволяет не только обнаружить, что ошибка есть, но и позволяет обнаружить, в каком месте кодового слова произошла ошибка, а значит, позволяет исправить эту ошибку. Коды, которые позволяют при передаче сообщений исправлять ошибки, называются кодами с исправлением ошибок.
Коды с обнаружением и с исправлением ошибок являются избыточными кодами. Коды с k– кратным повторением символов, в зависимости от значения k, позволяют исправлять даже по несколько ошибок, но такие коды из-за увеличения длины сообщение в kраз, очень замедляют передачу сообщений и поэтому практически неудобны.
Приведем пример кода с исправлением ошибок, обладающий минимальной для таких кодов избыточностью. Он получается из оптимального двоичного равномерного кода добавлением дополнительных символов к кодовым словам, при помощи которых можно найти и исправить одну ошибку, если она появилась при передаче кодового слова.
Пусть исходный код имеет порядок 4, с кодовыми словами β1 β2 β3 β 4 .
Добавим к каждому кодовому слову три дополнительных символа β5 β6 β7 , таких что
β5 = β2 + β3 + β4 , β6 = β1 + β3 + β4 , β7 = β1 + β2 + β4 .Здесь также сумма берется по модулю 2. Теперь в новом коде будем передавать кодовые слова вида: β1 β2 β3 β4 β5 β6 β7 .Предположим, что при передаче в новом кодовом слове произошла ошибка в одном из символов β4 , β5 , β6илиβ7. Тогда достаточно подсчитать сумму: S1 = β4 + β5 + β6 +β7 , чтобы обнаружить ошибку. Действительно, если ошибка есть, то S1 = 1, если ошибки нет, то S1 = 0(объясните самостоятельно: почему?).
Чтобы обнаружить и исправить ошибку при передаче сообщений в полученном коде, нужно вычислить три суммы:
S1 = β4 + β5 + β6 +β7 ,
S2 = β2 + β3 + β6 +β7 ,
S3 = β1 + β3 + β5 +β7 .
Если все эти суммы равны нулю: S1 = S2 = S3 = 0, то ошибки при передачи кодового слова не было. А если хотя бы одна из этих сумм равна 1, то ошибка есть. Интересно, что двоичный код S1S2S3 , рассматриваемый как двоичное число указывает на место положения ошибки в коде, а значит, эту ошибку можно исправить. Например, пусть ошибка произошла в 5-ом разряде кодового слова, то есть изменилось значение β5 . Тогда, очевидно, S1 = 1, S2 = 0, S3 = 1и S1S2S3 = 1012 = 510 , то есть получили место положения ошибки, которую можно исправить.
Показанный здесь код – это код Хемминга длины 7 с четырьмя информационными символами.
В общем случае можно построить код Хемминга с исправлением одной ошибки длины
2m-1с m дополнительными символами и с m проверяющими суммами, указывающими на место положения ошибки. Число информационных символов в таком коде равно
2m– 1 - m .
Задача 8. Определить положение одиночной ошибки в искаженном кодовом слове 1100011кода Хемминга длины 7.
Задача 9. Постройте код Хемминга порядка 3, исправляющий ошибку. Покажите, как в таком коде находится место ошибки.
Задача 10.Равномерный код состоит из всех слов длины N из букв алфавита, содержащего M букв. Его перекодировали в равномерный код из слов алфавита, содержащего P букв. Какой минимальный порядок имеет полученный код?
