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

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

Все, что мы говорили о письменности, относится и к другим видам информации. Чем больше ее избыточность, тем более помехоустойчивой она является. А нельзя ли искусственно ввести избыточность в цифровую информацию, представленную двоичными цифрами 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" строго определенных информационных битов.

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

Таким образом, это будет 0. Шестой бит складывается из суммы первого, третьего и четвертого: 

. Аналогичным путем найдем значение седьмого бита: . Итак, после символов 1011 передаются символы 010. Точно так же после второй четверки информационных битов 0010 следуют контрольные биты 110. Теперь запишем передаваемые последовательности все вместе: 10110100010110.

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

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

В соответствии с ним нужно для каждой принятой 7-разрядной кодовой комбинации подсчитывать контрольное число. Это 3-разрядное двоичное число и укажет сразу на номер бита, который был принят ошибочно. Проверим предлагаемое правило на наших "искаженных" комбинациях. Для первой из них сумма "по модулю 2" четвертого - седьмого битов равна 0, сумма второго, третьего, шестого и седьмого битов даст в результате 1, а сумма первого, третьего, пятого и седьмого битов - тоже 1. Итак, контрольное число имеет вид 011. Но ведь это двоичное представление числа 3! Значит, ошибочно принят третий бит. Его значение нужно заменить на противоположное, т. е. 0 заменить на 1. Если мы подсчитаем контрольное число для второй 7-разрядной комбинации, оно будет равно (проверьте самостоятельно!) 100. Это двоичный код числа 4, и, следовательно, ошибка произошла в четвертом символе. Исправить ее легко, заменив символ на противоположный.

А если ошибочно принят не информационный, а один из контрольных битов? Нетрудно убедиться, что будет обнаружена и эта ошибка. В самом деле, для принятой комбинации 1011000 (ошибка в шестом разряде) двоичное число составит 110, что соответствует десятичному числу 6. Надо ли говорить о том, что в системах передачи цифровой информации все операции - образования контрольных битов на передающей станции, вычисления контрольных чисел и исправления соответствующих битов на приемной станции - выполняются устройствами, собранными из микросхем, таких как сумматоры "по модулю 2", счетчики, дешифраторы и т. п.