Спирина, М.С. Дискретная математика

ценного сигналов (т.е. код ошибки) или прибавление 1 к исходно­ му. Обозначим код ошибки Е. Тогда х Ф у = Е. Прибавив (Ф) к обеим частям равенствах, получим у =х® Е, что уже было описано. При­ бавим к последнему равенству Е и получим у® Е= (х ® Е) ® Е=х. Видим, что если выходное сообщение еще раз пропустить через тот же самый канал связи, то восстановится исходное. В технике механизм действия помех на кодовые слова из 0 и 1 практически не связан с самим передаваемым сигналом, а связан в основном с внешними воздействиями на передающую технику. Например, при передаче сообщения произошла ошибка в опре­ деленном разряде. Тогда при передаче другого сообщения с боль­ шой вероятностью помеха произойдет в том же разряде, что и в первый раз. Пусть передавали двоичное слово 101001, а получили 110001, т.е. ошибка произошла на втором и третьем разряде. Если такая ошибка произойдет повторно, то восстановится исходное сооб­ щение, поскольку двойная инверсия дает исходный аргумент: х =х. Действительно, в первый раз : передавали 101001 ошибка 011000 получили 110001 во второй ра з : передавали 110001 ошибка 011000 получили 101001 Напомним, что здесь использовалась операция М2 в каждом разряде. Так как совпали первое слово при передаче в первом со ­ общении и последнее слово при передаче во втором сообщении, то первоначальное сообщение восстановлено: две одинаковые ошибки взаимно уничтожили друг друга. Поэтому для коррекции нужно полученное сообщение еще раз прогнать через канал связи. Эти идеи развил Вернан для построения абсолютно надежного шифра —одноразового блокнота. Пусть сообщение П зашифрова­ но в виде кортежа из 0 и 1. Нужно придумать случайный ключ ошибки К и сложить его с помощью операции М2 с начальным сообщением П. Полученное сообщение Ш вторично сложить с ключом ошиб­ ки К. Тогда в первом действии П ® К = Ш, во втором действии Ш ® К = П © К ® К = П © 0 = П. Две взаимно-обратные ошибки уничтожили друг друга, и передаваемое письмо П пришло к нам без изменений. Клод Шеннон доказал, что такой шифр является абсолютно надежным. Например, пусть наш алфавит содержит лишь буквы а, м, р, т. Поставим в соответствие а — 00, м — 01, р — 10, т — 11. Пусть передается буква М (П = 01) с ошибкой (ключ ошибки К = 11). Тогда принимаемое сообщение имеет вид Ш = П ® К = = 01 Ф 11 = 10, а число 10 соответствует букве р. Угадаем передан­ 323