Чтобы приемнику заниматься не только обнаружением, но и исправлением ошибок в блоке бит необходимо организовать их некоторую круговую поруку. Расположим информационные биты в квадратную матрицу, а проверочные биты четности расставляем по окончанию строк и столбцов.
Каким образом проверочные биты (биты проверки на четность) контролируют строки и столбцы было объяснено в прошлом выпуске.
Конечно же, эта матрица все еще остается последовательностью из 15 бит, только некоторые из них проверочные и не относятся к полезной информации.
От такой более сложной зависимости бит друг от друга получается весьма полезный эффект. Любая одиночная ошибка в блоке бит вызывает последующие ошибки при проверке четности в строке и столбце и что самое главное, номер строки и номер столбца однозначно указывают на то место, где произошла ошибка.
Информация, выделенная и переработанная после проверок четности, указывающая на позицию ошибочного бита называется синдромом ошибки. В данном примере в блоке всего 15 бит, из них полезных, несущих информацию пользователя всего 9. Хоть и в рассмотренном примере совершен качественный скачок развития и теперь есть возможность не только обнаруживать, но и исправлять ошибки, все же такое кодирование весьма далеко от идеала.
Человек, заточивший код до абсолютной эффективности
Теорию и практику помехоустойчивого кодирования довел до абсолюта Ричард Хэмминг в конце 40-х и начале 50-х годов, кроме того с тех пор еще много ученых добились на этом поприще немалых успехов. Однако, давайте вернемся к истокам.
Ричард Хэмминг довел количество полезных информационных бит до 11 в том же самом блоке из 15 бит. Проверочные биты располагаются в позициях 1,2,4 и 8.
Первый проверочный бит это результат вычисления четности в последовательности из семи бит, выделенных желтым цветом. В нашем матричном представлении это два не соседних столбца.
Второй проверочный бит это результат проверки на четность семи бит в средних соседних столбцах.
Мы переходим проверочному биту в позиции 4. Это результат проверки на четность в двух не соседних строках. Вполне закономерно, что проверочный бит в позиции 8 вычисляется путем вычисления четности в двух смежных строках.
Вся эта схема придумана только затем, чтобы каждая отдельная битовая ошибка вызывала свою комбинацию ошибок при проверке четности, из которой, в свою очередь можно вытащить синдром ошибки, указывающий на то место, где сигнал был побит помехами.
Если ошибка произойдет при приеме одиннадцатого бита, то это непременно отразится на проверках 1, 2 и 4. Именно в эти подмножества проверки на четность входит одиннадцатый бит.
Задачей декодера приемника является вычисление синдрома ошибки на основании ошибок проверки на четность. Чем меньше вычислений производится, тем декодер более эффективный.
Еще разок для закрепления. В принятом блоке бит все четыре проверки на четность ошибочные, необходимо вычислить в каком из бит произошла ошибка и исправить ее.
Декодер производит необходимые вычисления и получает синдром ошибок. Простой побитовой операцией "исключающего или" принятого блока бит с синдромом ошибки приемник приходит к правильному ответу.
Приношу свои извинения за рябящую в глазах схему. Код Хемминга позволяет исправлять одиночные ошибки в блоках бит, снабженных проверочной частью. По счастью, в большинстве случаев мощность сигнала намного больше мощности шума и вероятность ошибки не очень высока, но это не означает того, что по какой-то случайности не может произойти двух и более ошибок в одном блоке.
На этот случай предусмотрены более сильные кодовые конструкции с большими размерами блоков и не менее значительными проверочными частями. Студентами радиотехнических специальностей в высших учебных заведениях изучается невероятно захватывающая теория построения кодовых конструкций по заранее известным характеристикам. Например, можно построить код, умеющий исправлять до трех ошибок в одном блоке. Решение задачи даст все необходимые ответы, а кроме того, позволит создать эффективный декодер.
В следующий раз мы рассмотрим конструкцию простейшего декодера и, наконец-то, разберемся как система сотовой связи поколения 1G могла контролировать качество канала связи.
Поддержите статью лайком если понравилось и подпишитесь чтобы ничего не пропускать.
Также не обойдите вниманием канал на YouTube . Подписки и лайки будут приятным ответом от аудитории.
