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

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

Начнем а маленького примера. Пусть у нас есть канал с единичными ошибкой с частотой 10-6 на бит. Если мы желаем исправлять единичные ошибки при передаче блока в 1000 бит, то нам будет нужно 10 контрольных бит. При передаче 1 Мбит данных, будет нужно 10 000 контрольных бит. В тоже время для обнаружения единичной ошибки довольно 1-го бита Коды обнаруживающие ошибки четности. Потому, если мы применим технику повторной передачи, то на передачу 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%.


koefficient-scepleniya-i-koefficient-treniya.html
koefficient-tekushej-likvidnosti.html
koefficient-tyazhesti-karti.html