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

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

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

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

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

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

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

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

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

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

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

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

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