Коды обнаруживающие ошибки




Начнем а небольшого примера. Пусть у нас есть канал с единичными ошибкой с частотой 10-6 на бит. Если мы хотим исправлять единичные ошибки при передаче блока в 1000 бит, то нам потребуется 10 контрольных бит. При передаче 1 Мбит данных, потребуется 10 000 контрольных бит. В тоже время для обнаружения единичной ошибки достаточно одного бита четности. Поэтому, если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1001 бит дополнительно или с повторной передачей 2002 бит, вместо 10,000 бит в случае кода с исправлением ошибки.

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

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

Поэтому на практике применяют другую технику, которая называется полиномиальными кодами или циклическим избыточным кодом (CyclicRedundancyCode) или CRC кодом.

CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. битовая строка - коэффициенты полинома степени . Самый левый бит строки - коэффициент при старшей степени. Например, строка 110001 представляет полином .

Полиномиальная арифметика выполняется по модулю 2. Сложение и вычитание происходит без переноса разрядов. Так, что обе это операции эквивалентны EXCLUSIVE OR. Например,

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

Использование полиномиальных кодов при передаче заключается в следующем. Отправитель и получатель заранее договариваются о конкретном генераторе полиномов , у него коэффициенты при старшем члене и при младшем члене должны быть равны 1. Пусть степень равна r. Для вычисления контрольной суммы блока из m бит надо чтобы обязательно . Идея состоит в том, чтобы добавить контрольную сумму к передаваемому блоку, рассматриваемому как полином так, чтобы передаваемый блок с контрольной суммой был кратен . Когда получатель получает блок с контрольной суммой, он делит его на . Если есть остаток, то были ошибки при передаче.

Алгоритм вычисления контрольной суммы:

1) Добавить нулей в конец блока так, что он теперь содержит m+r разрядов и соответствует полиному ;

2) Разделить по модулю 2 полином на ;

3) Вычесть остаток (длина которого всегда не более r разрядов) из строки, соответствующей , по модулю 2. Результат и есть блок с контрольной суммой (назовем его ).

Этот метод позволяет отлавливать одиночные ошибки. Групповые ошибки длины не более . Нечетное число отдельных ошибок.

Существует три международных стандарта на вид :

.

CRC-12 используется для передачи символов из 6 разрядов. Два остальных - для 8 разрядных. CRC-16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечетное число изолированных ошибок с вероятностью 99,997%.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: