Методы коррекции ошибок

Прямой коррекцией ошибок (Forward Error Correction, FEC) называется такая техника кодирования, которая позволяет нс только определить, что данные были искажены при передаче, но и исправить ошибочные биты. Кодирование с прямой коррекцией предполагает большую избыточность, нежели кодирование, только обнаруживающее искажения данных.

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

При получении кодового слова контрольные г бит рассчитываются на приемнике заново. Полученная последовательность сравнивается с рассчитанной путем побитового сложения, но модулю 2. Последовательность бит, получаемая в результате подобного сравнения, называется синдромом. Фактически синдром представляет из себя г-битовое двоичное число в диапазоне значений от 0 до 2^Г — 1 (всего возможно 2^Г).

Предполагается, что при передаче? ьбитового кодового слова можно допустить ошибку только в одном бите, следовательно, всего может быть п комбинаций ошибочных бит. Все они должны соответствовать как минимум одной из 2^Г проверочных комбинаций. Кроме того, как минимум одна проверочная комбинация должна соответствовать ситуации, когда ошибок в передаче данных не произошло. Таким образом, число проверочных комбинаций 2^Г должно быть не меньше, чем значение п 4- 1:

Соотношение (5.4) позволяет найти минимальное количество контрольных бит г, которые следует выбрать из n-битного кадра (п = г + к) для гарантированного обнаружения битовой ошибки в к информационных бит. Это соотношение также означает, что для (п, к) —кодов значения п и к должны выбираться не совсем произвольно, но с учетом (5.4). Например, допустимым будет код (11,7), но (11,8) будет недопустимым.

Расположение контрольных бит в передаваемом кадре в принципе не имеет значения. Их можно располагать как перед информационными битами, так после них и даже чередуя с ними. Однако для того, чтобы по ненулевому синдрому можно было определить и исправить ошибочный бит, контрольные биты располагают в позициях степеней двойки: 1,2,4,… 2^Г. Остальные к бит заполняются информационными данными.

Рис. 5.2. Расположение бит данных и контрольных бит: а) в переданном блоке;

б) в принятом блоке Вычисление контрольных бит выполняется по следующему алгоритму:

• 1. Контрольным битам первоначально присваивают нулевые значения.
• 2. Каждый номер единичного бита информационных данных (не стоящих в позициях степеней двойки) записывается в двоичном коде. Так, если 9-й бит равен 1, то соответствующее ему двоичное значение номера 1001.
• 3. Ко всем номерам предыдущего шага применяют операцию побитового сложения по модулю 2.
• 4. Число, получаемое на шаге 3, записывается в контрольные биты.

Пример 5.5. Пусть требуется передать 8-битовый блок информационных данных. В соответствии с (5.4) минимальным количеством контрольных бит будет г = 4, т. е. передаваемый кадр будет содержать п = к + г = 12 бит. Имеем (12,8)-код Хеммиига.

Четыре контрольных бита будут располагаться в разрядах с номерами степеней двойки: 1,2,4,8. Эти биты первоначально обнуляются.

В биты с номерами 3,5, б, 7,9,10,11,12 будут записаны информационные данные. Пусть передается блок данных 111 001 (рис. 5.2).

Значение 1 имеют четыре бита (в таблице затенены). Двоичное представление номеров разрядов побитово складываются по модулю 2:

В результате получаются четыре контрольных бита — 0111 (код Хемминга). Следовательно, передаче подлежит блок 1 101 001 111 (рис. 5.2, а). ?

На стороне приемника выполняется следующий алгоритм:

• 1. Заново вычисляются контрольные биты.
• 2. Вычисляется синдром (побитовое сложение по модулю 2 полученных и рассчитанных контрольных бит).
• 3. Число, соответствующее двоичному представлению синдрома, и будет номером бита, в котором произошла ошибка.

Пример 5.6. Предположим, что третий бит данных (разряд 6) был передан с ошибкой и изменил значение с 0 на 1. Тогда приемником будет получен следующий блок: 1 101 101 111 (рис. 5.2, б).

Код Хемминга:

Вычисляем синдром: 0111 0 0001 = ОНО. Результат ненулевой, значит, при передаче данных произошла ошибка. Двоичному числу синдрома соответствует номер разряда G, следовательно, ошибка произошла в 6-м разряде. Для коррекции достаточно инвертировать этот бит. ?

Рассмотренный код также называют кодом исправления однобитовых ошибок (Single Error Correcting, SEC). Существуют модификации этого кода, который позволяет исправлять битовые ошибки и обнаруживать ошибки кратности 2 (Single Error Correcting, Double Error Detecting, SEC-DED). Отличие от кода SEC состоит в том, что к передаваемому кодовому слову добавляется еще один бит, который является битом четности всего передаваемого блока.

Недостатком кодов Хемминга является неспособность обнаружить и исправить длинные последовательности ошибочных бит (пакетные ошибки). Для их исправления широко применяют коды с минимальным расстоянием Хемминга d_mп ^ 5 (d_mxn ^ 2 -t_u+ -1−1). В качестве наиболее известных кодов можно указать коды, разработанные Боузом, Чоудхури и Хоквингемом (коды БЧХ), и коды Рида-Соломона. Они нашли широкое применение в беспроводных каналах. Эти коды обнаруживают и корректируют любое число ошибок.

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