Что представляет собой вертикальный и горизонтальный контроль по паритету

Методы обнаружения ошибок

Все методы обнаружения ошибок основаны на передаче в составе кадра данных служебной избыточной информации, по которой можно судить с некоторой степенью вероятности о достоверности принятых данных. Эту служебную информацию принято называть контрольной суммой или последовательностью контроля кадра — Frame Check Sequence, FCS.

Контрольная сумма вычисляется как функция от основной информации, причем необязательно только путем суммирования. Принимающая сторона повторно вычисляет контрольную сумму кадра по известному алгоритму и в случае ее совпадения с контрольной суммой, вычисленной передающей стороной, делает вывод о том, что данные были переданы через сеть корректно.

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

Контроль по паритету представляет собой наиболее простой, но наименее мощный алгоритм контроля. С его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в суммировании по модулю 2 всех бит контролируемой информации. Например, для данных 100101011 результатом контрольного суммирования будет значение 1. Результат суммирования представляет собой один бит данных, который пересылается вместе с контролируемой информацией. При искажении в процессе пересылки любого бита исходных данных (или контрольного разряда) результат суммирования будет отличаться от принятого контрольного разряда, что свидетельствует об ошибке. Однако двойная ошибка, например 110101010, будет неверно принята за корректные данные. Поэтому контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод редко применяется в вычислительных сетях из-за его большой избыточности и невысоких диагностических способностей.

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

Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является в настоящее время наиболее популярным методом контроля в вычислительных сетях. Данный метод основан на рассмотрении кадра в виде одного многоразрядного двоичного числа. В качестве контрольной информации рассматривается остаток от деления данного числа на известный делитель R. Обычно в качестве делителя выбирается семнадцати- или тридцатитрехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байта) или 32 разряда (4 байта).

При получении кадра данных приемник вычисляет остаток от деления на тот же делитель R, но при этом к данным кадра добавляется и содержащаяся в нем контрольная сумма. Если остаток от деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным. Существует модифицированная процедура вычисления остатка, приводящая к получению в случае отсутствия ошибок известного ненулевого остатка, что является более надежным показателем корректности.

Этот метод обладает более высокой вычислительной сложностью, но его диагностические возможности гораздо выше, чем у методов контроля по паритету. Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе бит. Метод обладает также невысокой степенью избыточности. Например, для кадра Ethernet размером в 1024 байт контрольная информация длиной в 4 байт составляет только 0,4 %.

Бит чётности

В вычислительной технике и сетях передачи данных би́том чётности (англ. Parity bit ) называют контрольный бит, служащий для проверки общей чётности двоичного числа (чётности количества единичных битов в числе).

Применение

В последовательной передаче данных часто используется формат 7 бит данных, бит чётности, один или два стоповых бита. Такой формат аккуратно размещает все 7-битные ASCII символы в удобный 8-битный байт. Также допустимы другие форматы: 8 бит данных и бит чётности.

В последовательных коммуникациях чётность обычно контролируется оборудованием интерфейса (например UART). Признак ошибки становится доступен процессору (и ОС) через статусный регистр оборудования. Восстановление ошибок обычно производится повторной передачей данных, подробности которого обрабатываются программным обеспечением (например, функциями ввода/вывода операционной системы)

Контроль некой двоичной последовательности (например, машинного слова) с помощью бита чётности также называют контролем по паритету. Контроль по паритету представляет собой наиболее простой и наименее мощный метод контроля данных. С его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Двойная ошибка, будет неверно принята за корректные данные. Поэтому контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод редко применяется в компьютерных сетях из-за невысоких диагностических способностей. Существует модификация этого метода — вертикальный и горизонтальный контроль по паритету. Отличие состоит в том, что исходные данные рассматриваются в виде матрицы, строки которой составляют байты данных. Контрольный разряд подсчитывается отдельно для каждой строки и для каждого столбца матрицы. Этот метод обнаруживает значительную часть двойных ошибок, однако обладает большей избыточностью. Он сейчас также почти не применяется при передаче информации по сети.

Полиномы CRC и бит чётности

Контроль по чётности фактически является специальным случаем проверки избыточности циклической суммы с полиномом x+1.

Примеры

Бит чётности или контрольный разряд формируется при выполнении операции «Исключающее-ИЛИ» поразрядно. Рассмотрим схему, использующую девятибитные кодовые слова, состоящие из восьми бит данных, за которыми следует бит чётности.

• Число 10111101 содержит 6 ‘1’ битов. Бит чётности будет 0, получаем кодовое слово 101111010.
• Число 01110011 содержит 5 ‘1’ битов. Бит чётности будет 1, получаем кодовое слово 011100111.
• Число 00000000 содержит 0 ‘1’ битов. Бит чётности будет 0, получаем кодовое слово 000000000.

Пустой или несуществующий поток битов также имеет ноль единичных битов, поэтому бит чётности будет 0.

См. также

• Чётность используется для восстановления данных в RAID.
• Parity RAM использует чётность для обнаружения ошибок памяти.
• Код Хемминга — следующий шаг после бита чётности.

Литература

• Генри С. Уоррен, мл.Глава 5. Подсчет битов // Алгоритмические трюки для программистов = Hacker’s Delight. — М .: «Вильямс», 2007. — С. 288. — ISBN 0-201-91465-4

• Компьютер

Организация беспроводных сетей

Существует три наиболее распространенных орудия борьбы с ошибками в процессе передачи данных:

• коды обнаружения ошибок;
• коды с коррекцией ошибок, называемые также схемами прямой коррекции ошибок (Forward Error Correction — FEC );
• протоколы с автоматическим запросом повторной передачи ( Automatic Repeat Request — ARQ ).

Код обнаружения ошибок позволяет довольно легко установить наличие ошибки. Как правило, подобные коды используются совместно с определенными протоколами канального или транспортного уровней, имеющими схему ARQ . В схеме ARQ приемник попросту отклоняет блок данных, в котором была обнаружена ошибка, после чего передатчик передает этот блок повторно. Коды с прямой коррекцией ошибок позволяют не только обнаружить ошибки, но и исправить их, не прибегая к повторной передаче. Схемы FEC часто используются в беспроводной передаче, где повторная передача крайне неэффективна, а уровень ошибок довольно высок.

1) Методы обнаружения ошибок

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

Избыточную служебную информацию принято называть контрольной суммой, или контрольной последовательностью кадра ( Frame Check Sequence , FCS ). Контрольная сумма вычисляется как функция от основной информации, причем не обязательно путем суммирования. Принимающая сторона повторно вычисляет контрольную сумму кадра по известному алгоритму и в случае ее совпадения с контрольной суммой, вычисленной передающей стороной, делает вывод о том, что данные были переданы через сеть корректно. Рассмотрим несколько распространенных алгоритмов вычисления контрольной суммы, отличающихся вычислительной сложностью и способностью обнаруживать ошибки в данных.

Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же время это наименее мощный алгоритм контроля, так как с его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в суммировании по модулю 2 всех битов контролируемой информации. Нетрудно заметить, что для информации, состоящей из нечетного числа единиц, контрольная сумма всегда равна 1 , а при четном числе единиц — 0 . Например, для данных 100101011 результатом контрольного суммирования будет значение 1 . Результат суммирования также представляет собой один дополнительный бит данных, который пересылается вместе с контролируемой информацией. При искажении в процессе пересылки любого бита исходных данных (или контрольного разряда) результат суммирования будет отличаться от принятого контрольного разряда, что говорит об ошибке. Однако двойная ошибка, например 110101010 , будет неверно принята за корректные данные. Поэтому контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод редко применяется в компьютерных сетях из-за значительной избыточности и невысоких диагностических способностей.

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

Циклический избыточный контроль ( Cyclic Redundancy Check — CRC ) является в настоящее время наиболее популярным методом контроля в вычислительных сетях (и не только в сетях; в частности, этот метод широко применяется при записи данных на гибкие и жесткие диски). Метод основан на рассмотрении исходных данных в виде одного многоразрядного двоичного числа. Например, кадр стандарта Ethernet, состоящий из 1024 байт, будет рассматриваться как одно число, состоящее из 8192 бит. Контрольной информацией считается остаток от деления этого числа на известный делитель R. Обычно в качестве делителя выбирается семнадцати- или тридцатитрехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байт) или 32 разряда (4 байт). При получении кадра данных снова вычисляется остаток от деления на тот же делитель R , но при этом к данным кадра добавляется и содержащаяся в нем контрольная сумма. Если остаток от деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным.

Этот метод обладает более высокой вычислительной сложностью, но его диагностические возможности гораздо шире, чем у методов контроля по паритету. Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе битов. Метод также обладает невысокой степенью избыточности. Например, для кадра Ethernet размером 1024 байта контрольная информация длиной 4 байта составляет только 0,4 %.

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

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

При применении любого избыточного кода не все комбинации кодов являются разрешенными. Например, контроль по паритету делает разрешенными только половину кодов. Если мы контролируем три информационных бита, то разрешенными 4-битными кодами с дополнением до нечетного количества единиц будут:

000 1, 001 0, 010 0, 011 1, 100 0, 101 1, 110 1, 111 0 , то есть всего 8 кодов из 16 возможных.

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

Можно доказать, что если мы сконструировали избыточный код с расстоянием Хемминга, равным n, такой код будет в состоянии распознавать (n-1) -кратные ошибки и исправлять (n-1)/2 -кратные ошибки. Так как коды с контролем по паритету имеют расстояние Хемминга, равное 2, они могут только обнаруживать однократные ошибки и не могут исправлять ошибки.

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

Наиболее часто в современных системах связи применяется тип кодирования, реализуемый сверхточным кодирующим устройством (Сonvolutional coder ), потому что такое кодирование несложно реализовать аппаратно с использованием линий задержки ( delay ) и сумматоров. В отличие от рассмотренного выше кода, который относится к блочным кодам без памяти, сверточный код относится к кодам с конечной памятью ( Finite memory code); это означает, что выходная последовательность кодера является функцией не только текущего входного сигнала, но также нескольких из числа последних предшествующих битов. Длина кодового ограничения ( Constraint length of a code) показывает, как много выходных элементов выходит из системы в пересчете на один входной. Коды часто характеризуются их эффективной степенью (или коэффициентом) кодирования (Code rate). Вам может встретиться сверточный код с коэффициентом кодирования 1/2. Этот коэффициент указывает, что на каждый входной бит приходится два выходных. При сравнении кодов обращайте внимание на то, что, хотя коды с более высокой эффективной степенью кодирования позволяют передавать данные с более высокой скоростью, они, соответственно, более чувствительны к шуму.

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

3) Методы автоматического запроса повторной передачи

В простейшем случае защита от ошибок заключается только в их обнаружении. Система должна предупредить передатчик об обнаружении ошибки и необходимости повторной передачи. Такие процедуры защиты от ошибок известны как методы автоматического запроса повторной передачи ( Automatic Repeat Request — ARQ ). В беспроводных локальных сетях применяется процедура «запрос ARQ с остановками» (stop-and-wait ARQ ).

увеличить изображение
Рис. 1.13. Процедура запрос ARQ с остановками

В этом случае источник, пославший кадр, ожидает получения подтверждения (Acknowledgement — ACK), или, как еще его называют, квитанции, от приемника и только после этого посылает следующий кадр. Если же подтверждение не приходит в течение тайм-аута, то кадр (или подтверждение) считается утерянным и его передача повторяется. На рис. 1.13 видно, что в этом случае производительность обмена данными ниже потенциально возможной; хотя передатчик и мог бы послать следующий кадр сразу же после отправки предыдущего, он обязан ждать прихода подтверждения.

Методы обнаружения ошибок

Для обнаружения ошибок применяются методы (техники кодирования), основанные па определении вероятности получения приемником достоверной кодовой комбинации. В качестве такой комбинации может выступать любая протокольная единица данных (PDU, Protocol Data Unit) — блок битов, передаваемый как единое целое и имеющий определенную структуру, включающую как саму передаваемую информацию, так и служебные данные. Служебную информацию принято называть контрольной суммой. Она вычисляется по специальным алгоритмам на основе информационных данных, причем не обязательно в виде суммирования.

Будем считать для определенности, что при передаче протокольных единиц данных контролируются кадры. В этом случае контрольную сумму называют контрольной последовательностью кадра. (FCS, Frame Check Sequence). Передатчик отправляет контрольную последовательность кадра как часть PDU. Приемник на своей стороне вычисляет FCS по известному алгоритму и сравнивает с переданной контрольной последовательностью. Если FCS передатчика и приемника совпадают, то принимается решение, что передача данных по сети выполнена корректно.

Основными методами контроля данных (обнаружения ошибок) являются следующие:

• — контроль по паритету;
• — вертикальный и горизонтальный контроль по паритету;
• — контроль контрольной суммой;
• — контроль циклическим избыточным кодом.

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

Контроль по паритету является наиболее простым и в то же время наименее мощным методом контроля. Он предназначен для обнаружения битовых ошибок данных. Его суть заключается в следующем. К информационным данным добавляется один контрольный бит (г = 1), который дополняет количество единичных бит до четного или нечетного значения. В первом случае говорят о контроле четности данных, во втором — о контроле нечетности. Соглашение о выборе вида контроля принимается заранее.

Для обнаружения ошибки все передаваемые биты блока (как информационные, так и контрольный) суммируются по модулю 2. При наличии ошибки в передаваемом блоке (как исходных, так и контрольном) результат суммирования будет отличаться от контрольного разряда, который был принят. Это свидетельствует о наличии ошибки. Однако, если ошибок было четное количество (две, четыре и т.д.), то такое искажение останется незамеченным. Из-за этой особенности данный метод контроля применяется к небольшим блокам данных, обычно байтам. В этом случае избыточность кода составляет 1/8, что является довольно значительным, поэтому в компьютерных сетях контроль но паритету используется редко.

Пример 5.3. Рассмотрим ситуацию нечетного контроля трех информационных бит. В этом случае кодовые слова будут состоять из 4 бит. Разрешенными кодовыми комбинациями будут следующие:

Пробелом отделен контрольный бит. ?

Пример 5.3 иллюстрирует два факта, верных для произвольного количества информационных бит:

• 1. При контроле по паритету только половина кодовых комбинаций оказывается разрешенной (8 кодов из 16 возможных).
• 2. Минимальное расстояние кода d_mm = 2, т.е. возможно только обнаруживать битовые ошибки, по нс исправлять их.

Вертикальный и горизонтальный контроль по парит,егпу во многом похож на рассмотренный выше метод с тем отличием, что информационные данные представляются (располагаются) в виде матрицы. Строками этой матрицы являются отдельные байты данных. Контрольные биты данных добавляются как для каждой строки, так и для каждого столбца (рис. 5.1).

Бит паритета «р» (горизонтальный контроль) добавляется к каждому передаваемому символу. Бит паритета вертикального контроля рассчитывается для каждой

Рис. 5.1. Вертикальный и горизонтальный контроль по паритету

позиции бита в символе. Вертикальные контрольные биты собираются в отдельный контрольный символ (байт).

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

Контрольная сумма представляет собой дополнительный код (см. пример 3.2) суммы всех байт кодового слова. Суммирование выполняется но модулю разрядности поля контрольного кода. Дополнение суммы происходит до нуля (до следующего за максимально возможным числом разрядной сетки, когда все разряды представляют собой двоичные единицы, например, FF).

Передатчик отправляет информационные данные и контрольную сумму. Прием- пик на своей стороне суммирует все байты или слова кадра,, включая контрольные биты. Суммирование выполняется по тому же модулю (разрядности поля контрольного кода). В результате должно получиться то же число 0 (следующее за FF). Отличие в значении позволяет сделать вывод, что при передаче была допущена ошибка.

Вычисление контрольных сумм является одним из самых простых способов контроля кадров (вероятность определения ошибок достигает 99,9%). При постоянной длине контрольного кода с увеличением количества информационных данных в одной PDU вероятность обнаружения ошибок снижается. Метод контрольных сумм применяется для выявления битовых ошибок.

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

Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является популярным методом обнаружения ошибок в СПД и других задачах, где не требуется исправление пакетных ошибок, например, при записи данных на жесткие и оптические носители.

Суть метода CRC заключается в следующем. На передатчике формируется п-бит- нос кодовое слово, состоящее из к информационных и г проверочных бит (поле FCS). До передачи кадра все проверочные биты имеют значение 0. Кадр целиком (все п бит, включая и обнуленные проверочные) в виде двоичного числа делится за некоторый делитель Р. Остаток от деления по модулю 2 помещается в иоле FCS. На стороне приемника принятый кадр целиком делится на тот же делитель Р. Если остаток от деления на приемнике равен 0, то принимается решение, что ошибок при передаче данных не произошло, иначе данные считаются искаженными.

Число бит в кадре может быть достаточно большим. Например, стандартный кадр Ethernet имеет длину 1024 байт, т.с. число будет содержать 8096 бит.

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

При практической реализации CRC значения бит представляются в виде многочленов от некоторой фиксированной переменной х. Коэффициентами многочленов являются двоичные числа, которые соответствуют передаваемым битам. Например, блок данных 10011010 представляется в виде многочлена 7-й степени с коэффициентами 1, 0, 0, 1, 1,0, 1,0 соответственно, т.е. х 7 + х 4 + х 2 + х.

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

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

В циклических кодах разрешенные комбинации имеют два важных с точки зрения реализации свойства:

• 1. Для разрешенной комбинации циклический побитовый сдвиг приводит к разрешенной комбинации. Именно этот факт и послужил основой для названия метода.
• 2. Все разрешенные комбинации (в полиномиальном представлении) делятся без остатка на некоторый полином Р(х).

Полином Р(х) называют образующим или порождающим полиномом. Вид образующего полинома определяется желаемой разрядностью остатка и способностью определять ошибки. Число проверочных бит обычно совпадает со степенью порождающего полинома. Младший и старший биты Р(х) должны быть равны 1. Имеются и другие требования к образующему полиному. Некоторые конкретные порождающие полиномы определены в стандартах международных организаций.

Алгоритм построения циклического кода (кодирование передаваемых данных) имеет следующий вид:

• 1. Передаваемый ^-битовый блок данных умножается на число 2 Г . Данная операция равносильна умножению полинома D(x), соответствующему А:-битовой последовательности, на полином х г . В результате длина битовой последовательности увеличивается на г разрядов, причем эти последние г разрядов (блок FCS) заполнены нулями.
• 2. Полученная последовательность бит (как информационных, так и проверочных) делится на образующий многочлен Р(х) с остатком Q(x). Количество разрядов остатка на единицу меньше, чем у Р(х).
• 3. Полученный остаток Q(x) складывается с полиномом D(x)x r . Данная операция равносильна размещению в битах FCS коэффициентов полинома Q(x). Полученная новая битовая последовательность (кадр) Т(х) = D(x)x r +Q(x) и должна быть передана но сети.

Нетрудно видеть, что передаваемый кадр должен делиться на образующий полином без остатка. Действительно, если некоторое число (делимое) делится на делитель с остатком, то при вычитании остатка из делимого полученный результат будет без остатка делиться на делитель. Если, например, разделить в десятичной системе счисления 210 278 на 10 941, то получится остаток 2 399. Если вычесть полученный остаток из делимого (210278), то результат 207879 будет нацело (т.е. без остатка) делиться на 10941.

Пример 5.4. Рассмотрим передачу блока данных 1011101. Этому блоку соответствует полином D(x) = х 6 + х 4 + х 3 + х 2 + 1. Пусть в качестве образующего полинома выбран Р(х) = х 4 4- х 4- 1, которому соответствует число 10011. Количество проверочных бит совпадает со степенью полинома Р(х), т.е. г = 4, последовательность передаваемых данных будет содержать п = 7 4- 4 = 11 бит.

Выполним умножение полинома D(x) на полином х 4 :

что соответствует битовой последовательности 10111010000.

Произведем деление полинома D(x)x 4 на образующий полином:

Остаток от деления D(x)x x на Р(х) равен Q(x) = х 2 + х, что соответствует числовому значению 110, которое и будет размещено в поле проверочных бит (так как их количество г = 4, то будет размещено число ОНО).

Передаче подлежит кадр, который в виде полинома является суммой Т(х) = = D + Q(x) = х 10 И- х 8 + х 7 + х 6 + х л 4- х 2 4- х, что соответствует числовому значению 10111010110.

Осуществим проверку, выполнив деление Т(х) на Р(х):

Таким образом, если был получен кадр 10111010110, то принимается решение, что ошибок при передаче не произошло. В противном случае полагается, что в данных имеются искажения. ?

Рассмотренный метод циклического избыточного контроля обладает большей вычислительной сложностью, нежели контроль но паритету и применение контрольных сумм, но имеет гораздо более высокие диагностические возможности. Кодирование CRC позволяет обнаружить все битовые ошибки, все двойные, ошибки нечетной кратности, а также пакетные ошибки. Вероятность нахождения ошибок оценивается в 99,9984%. Избыточность метода считается невысокой. Например, кадр в 1024 бит может иметь контрольные данные размером в 4 бита, что составляет 0,4%.

Дальнейшим развитием метода циклического избыточного контроля является ЕСС-коитроль (контроль достоверности с исправлением ошибок, Error Correction Code), позволяющий не только обнаруживать, но и исправлять некоторые ошибки.