...И мир загадочный за занавесом цифр. Цифровая связь

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

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

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

А кто подсчитает сумму единиц в принятой комбинации двоичных цифр? - может возникнуть вопрос у читателя.

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

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

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

Речь пойдет о так называемом коде Хэмминга, в котором после каждых четырех информационных битов в линию посылается три контрольных бита. Такая сильная избыточность делает код поистине чудодейственным. Но обо всем по порядку...

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

Каждый из них образуется путем сложения "по модулю 2" строго определенных информационных битов.