счете к иероглифическому письму. Каждый иероглиф обладает большой информативностью, запись с их помощью занимает небольшое пространство. Но вместе с тем, небольшая ошибка в начертании иероглифа приводит к тому, что информация воспринимается неверно. Так, увеличение информативности знаков повышает вероятность ошибочного их понимания. (За все нужно платить!) Вторая тенденция в развитии письменности заключалась в стремлении к безошибочной передаче содержания текста. Результатом явилось создание буквенного, или алфавитного, письма. Эта система письма позволяет в большинстве случаев правильно понять текст, даже если в нем пропущено или искажено несколько букв. Такое свойство алфавитного письма называют избыточностью . Конечно, избыточность удлиняет запись (некоторые буквы можно было бы выкинуть из нее без ущерба для содержания), но зато она уменьшает вероятность ошибочного понимания текста при его искажении.

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

Все, что мы говорили о письменности, относится и к другим видам информации. Чем больше ее избыточность, тем более помехоустойчивой она является. А нельзя ли искусственно ввести избыточность в цифровую информацию, представленную двоичными цифрами О и 1? Можно, но за это придется платить . Поясним, в чем тут дело. Например, в коде Бодо каждая буква заменяется 5-разрядным двоичным кодом, т.е. пятью битами О и 1. Данный код не является избыточным, так как искажение любого бита приводит к декодированию вместо переданной другой буквы, т.е. к ошибке. Сделать код избыточным можно одним путем: добавить дополнительные биты к уже имеющимся. Но это приведет к тому, что каждая буква будет теперь передаваться медленнее. Так, введение в информацию избыточности влечет за собой снижение скорости ее передачи. Вот об этой плате и шла речь выше. Тем не менее разработчики цифровых систем передачи часто вполне сознательно идут на такой шаг - делают информацию избыточной с тем, чтобы обнаружить ошибки в принятых комбинациях двоичных символов, а если возможно, то и исправить их.

На приемной станции цифровой системы передачи можно подсчитать число ошибочных решений, принятых регенератором, не зная даже, какой конкретный бит принят неверно. Покажем на примере кода Бодо, как это делается. Предположим, что передаются две комбинации цифр: 10101 и 01100. В них все биты являются нужными , из-

быточности в этой информации нет. Введем ее искусственно: к информационным битам добавим шестой - контрольный, но сделаем это так, чтобы сумма единиц в передаваемой комбинации была четной. Для первой комбинации цифр контрольный бит нужно выбрать равным 1, а для второй - 0. Итак, в линию поступают уже не 5-, а 6-разрядные группы битов: 10101,1 и 01100,0 (запятую мы ввели условно, чтобы чисто зрительно отделить контрольный бит от информационных). Если теперь помеха исказит сигнал и какой-то бит будет принят неверно, т.е. вместо 1 регенератор выдаст О или, наоборот, вместо О будет зарегистрирована 1, то независимо от разряда кодовой комбинации, в котором это произошло, сумма единиц уже будет четной. Таким образом, наличие ошибки будет зафиксировано. Действительно, легко обнаруживается, что комбинация вида 00101,1 не могла быть передана, поскольку сумма единиц в ней нечетная. Точно так же ошибочными являются комбинации: 10101,0 и 01101,0.

А кто подсчитает сумму единиц в принятой комбинации двоичных цифр? Одно из правил двоичной арифметики - суммирование по модулю 2 . Вот эти действия:

080 = 0, 180 = 1,081=1,181=0.

Знак плюс в кружочке отличает их от обычного двоичного суммирования. Существует и микросхема, которая выполняет указанные действия. О ней мы тоже говорили - это сумматор по модулю 2 . Просуммировать все цифры в кодовой комбинации очень просто: очередная цифра, поступающая на такой сумматор, складывается с результатом предыдущего суммирования. Если число единиц в этом наборе цифр нечетное, то в результате суммирования на выходе микросхемы появится 1 (О Ф О 8 1 8 О 8 18 1=1), при четном числе единиц - О (1 8081808181=0). Вряд ли стоит пояснять, что наличие на выходной ножке единичного импульса - признак ошибочного решения, принятого регенератором. Остается только подсчитать (с помощью другой микросхемы - двоичного счетчика), сколько раз появлялась единица за все время передачи, - и вероятность ошибки определена!

Разумеется, введение в информацию столь малой избыточности не позволяет обнаружить все ошибки, например замену двух О одновременно двумя 1 и т.п., при которых свойство четности не нарушается. Для этих целей нужны коды с большей избыточностью (см. глава 12). Речь пойдет о так называемом коде Хэмминга, в котором после каждых четырех информационных битов в линию посылаются три контрольных. Как получаются контрольные биты? Пронумеруем подряд от 1 до 7 все разряды (как информационные, так и контрольные) образовавшегося кодового слова. Информационные биты будут иметь при этом номера с 1-го по 4-й, а контрольные - с 5-го по 7-й. Правило получения контрольных битов дано в табл. 5.1.

Таблица 5.1. Правило формирования контрольных битов

Пусть нам надлежит передать двоичную последовательность 10110010. Попробуем защитить ее от действия помех, используя код Хэмминга. После первой четверки информационных битов 1011 необходимо вставить контрольные. Пятый, передаваемый в линию, бит получаем, суммируя в соответствии с табл. 5.1 2-й, 3-й и 4-й биты: О ® 1 ® 1 = 0.

Таким образом, это будет 0. Шестой бит складывается из суммы 1-го, 3-го и 4-го: 1 ® 1 ® 1 = 1. Аналогичным путем найдем значение 7-го бита: 1 ® О ® 1 = 0. Итак, после символов 1011 передаются символы 010. Точно так же после второй четверки информационных битов 0010 следуют контрольные биты 110. Теперь запишем передаваемые последовательности все вместе: 1011, 010, 0010, 110. Здесь, как и ранее, запятая введена лишь для удобства зрительного восприятия.

Возникают следующие вопросы: как теперь узнать, произошла ли при передаче кодовой комбинации по линии ошибка или нет? Если произошла, то в каком разряде? Как эту ошибку исправить?

Предположим, что регенератором приемной станции была зафиксирована такая последовательность: 1001, 010, 0011, 110. Очевидно, что в первой комбинации ошибочно принят третий бит, а во второй комбинации - четвертый. Но это ясно для нас с вами. На приеме подобный вывод должен быть сделан автоматически, по заранее известному правилу. Такое правило приведено в табл. 5.2. В соответствии с ним нужно для каждой принятой 7-разрядной кодовой комбинации подсчитывать контрольное число. Это 3-разрядное двоичное число и указывает сразу на номер бита, который был принят ошибочно. Проверим предлагаемое правило на наших искаженных комбинациях. Для первой из них сумма по модулю 2 4 - 7-го битов равна О, сумма 2-го, 3-го, 6-го и 7-го битов даст в результате 1, а сумма 1-го, 3-го, 5-го и 7-го битов - тоже 1. Итак, контрольное число имеет вид 011. Но ведь это двоичное представление числа 3! Значит, ошибочно принят третий бит. Его значение нужно заменить на противоположное, т.е. О заменить на 1. Если мы подсчитаем контрольное число для второй 7-разрядной комбинации, оно будет равно (проверьте самостоятельно) 100. Это двоичный код числа 4, и, следовательно, ошибка произошла в четвертом символе. Исправить ее легко, заменив символ на противоположный.