Контроль четности. Двумерный контроль четности

Возможно, простейшая форма обнаружения ошибок заключается в использовании одного бита четности. Предположим, что на рис. 5.4 передаваемые данные D имеют длину d разрядов. При проверке на четность отправитель просто добавляет к данным один бит, значение которого вычисляется как сумма всех d разрядов данных по модулю 2. В этом случае количество единиц в получающемся в результате числе всегда будет четным. Применяются также схемы, в которых контрольный бит инвертируется, в результате чего количество единиц в получающемся в результате числе всегда будет нечетным. На рис. 5.5 изображена схема проверки на четность, а единственный бит четности хранится в отдельном поле.

Действия, выполняемые получателем при использовании такой схемы, также очень просты. Получатель должен всего лишь сосчитать количество единиц в полученных d + 1 разрядах. Если при проверке на четность получатель обнаруживает, что в принятых им данных нечетное количество единичных разрядов, он понимает, что произошла ошибка, по меньшей мере, в одном разряде. В общем случае это означает, что в полученных данных инвертировано нечетное количество разрядов (произошла ошибка нечетной кратности).

Что произойдет, если в полученном пакете данных произойдет четное количество однобитовых ошибок? В этом случае получатель не сможет обнаружить ошибку. Если вероятность ошибки в одном разряде мала и можно предположить, что ошибки в отдельных разрядах возникают независимо друг от друга, тогда вероятность нескольких ошибок в одном пакете крайне мала. В таком случае единственного бита четности может быть достаточно. Однако практические наблюдения показали, что в действительности ошибки не являются независимыми, а часто группируются в пакеты ошибок. В случае пакетных ошибок вероятность того, что получатель не обнаружит ошибку в пакете, может приблизиться к величине 50 %. Очевидно, в такой ситуации требуется более надежная схема обнаружения ошибок! Но прежде чем перейти к изучению схем обнаружения ошибок, применяемых на практике, рассмотрим простую схему, которая обобщает предыдущую схему одноразрядного контроля четности и помогает понять принцип работы методов исправления ошибок.

На рис. 5.6 показано двухмерное обобщение одноразрядной схемы проверки на четность. В данной схеме d разрядов пакета данных разделяются на г строк и j столбцов, образуя прямоугольную матрицу. Значение четности вычисляется для каждой строки и каждого столбца. Получающиеся в результате i +j +1 битов четности образуют разряды обнаружения ошибок кадра канального уровня.

Предположим теперь, что в исходном блоке данных из d разрядов происходит однократная ошибка. В такой двухмерной схеме контроля четности об ошибке будут одновременно сигнализировать контрольные разряды строки и столбца. Таким образом, получатель сможет не только обнаружить сам факт ошибки, но и по номерам строки и столбца найти поврежденный бит данных и исправить его! На рисунке показан пример, в котором поврежден бит в позиции (2, 2) — он изменил свое значение с 1 на 0. Такую одиночную ошибку получатель может не только обнаружить, но и исправить. Хотя нас, в первую очередь, интересует обнаружение и исправление ошибок в исходных d разрядах, данная схема позволяет также обнаруживать и исправлять одиночные ошибки в самих битах четности. Кроме того, данная двухмерная схема контроля четности позволяет обнаруживать (но не исправлять!) любые комбинации из двух одиночных ошибок (то есть двойные ошибки) в пакете.

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