бит четности в кодах обнаруживающих ошибку это

Два поврежденных бита

Алиса вычисляет значение четности: 1 ^ 0 ^ 0 ^ 1 = 0

Алиса отправляет: 10010

Боб получает: 1 1 01 1

Боб вычисляет общую четность: 1 ^ 1 ^ 0 ^ 1 ^ 1 = 0

Боб сообщает о правильной передаче, хотя на самом деле неверной.

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

использование

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

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

RAID-массив

Например, предположим, что два диска в массиве RAID 5 с тремя дисками содержат следующие данные:

Чтобы вычислить данные о четности для двух дисков, над их данными выполняется XOR:

Если какой-либо из трех дисков выйдет из строя, содержимое отказавшего диска может быть восстановлено на заменяющем диске, подвергнув данные с оставшихся дисков той же операции XOR. Если диск 2 выйдет из строя, его данные можно будет восстановить, используя результаты XOR содержимого двух оставшихся дисков, диска 1 и диска 3:

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

История

Четность также использовалась, по крайней мере, в некоторых системах ввода данных с бумажной ленты ( перфоленты ) (которые предшествовали системам с магнитной лентой). В системах, продаваемых британской компанией ICL (ранее ICT), бумажная лента шириной 1 дюйм (25 мм) имела 8 отверстий, проходящих через нее, причем 8-е было для проверки четности. Для данных использовалось 7 позиций, например, 7-битный ASCII. В 8-й позиции было пробито отверстие в зависимости от количества пробитых отверстий для данных.

Источник

Помехоустойчивое кодирование с иcпользованием различных кодов

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

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

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

По сути, кодирование — это добавление к исходной информации дополнительной, проверочной, информации. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.
Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле:

k/(i+k), где
k — количество проверочных бит,
i — количество информационных бит.

Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).

Код с проверкой на четность

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

Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10110 (изменился второй бит)
Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка.

Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10010 (изменились 2 и 3 биты)
В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку.

Так как около 90% всех нерегулярных ошибок происходит именно с одиночным разрядом, проверки четности бывает достаточно для большинства ситуаций.

Код Хэмминга

первый проверочный бит на 2 0 = 1;
второй проверочный бит на 2 1 = 2;
третий проверочный бит на 2 2 = 4;

r1 = i1 + i2 + i4
r2 = i1 + i3 + i4
r3 = i2 + i3 + i4

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

и декодера

(может быть, довольно запутано, но лучше начертить не получилось)

e0,e1,e2 опрделяются как функции, зависящие от принятых декодером бит k1 — k7:

e0 = k1 + k3 + k5 + k7 mod 2
e1 = k2 + k3 + k6 + k7 mod 2
e2 = k4 + k5 + k6 + k7 mod 2

Набор этих значений e2e1e0 есть двоичная запись позиции, где произошла ошибка при передаче данных. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 000), то исправляет ошибку.

Коды-произведения

В канале связи кроме одиночных ошибок, вызванных шумами, часто встречаются пакетные ошибки, вызванные импульсными помехами, замираниями или выпадениями (при цифровой видеозаписи). При этом пораженными оказываются сотни, а то и тысячи бит информации подряд. Ясно, что ни один помехоустойчивый код не сможет справиться с такой ошибкой. Для возможности борьбы с такими ошибками используются коды-произведения. Принцип действия такого кода изображён на рисунке:

Передаваемая информация кодируется дважды: во внешнем и внутреннем кодерах. Между ними устанавливается буфер, работа которого показана на рисунке:

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

При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода. В таком порядке информация передается по каналу связи или записывается куда-нибудь. Условимся, что и внутренний, и внешний коды – коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове (количество «кубиков» на рисунке не критично — это просто схема). На приемном конце расположен точно такой же массив памяти (буфер), в который информация заносится построчно, а выводится по столбцам. При возникновении пакетной ошибки (крестики на рисунке в третьей и четвертой строках), она малыми порциями распределяется в кодовых словах внешнего кода и может быть исправлена.

Назначение внешнего кода понятно – исправление пакетных ошибок. Зачем же нужен внутренний код? На рисунке, кроме пакетной, показана одиночная ошибка (четвертый столбец, верхняя строка). В кодовом слове, расположенном в четвертом столбце — две ошибки, и они не могут быть исправлены, т.к. внешний код рассчитан на исправление одной ошибки. Для выхода из этой ситуации как раз и нужен внутренний код, который исправит эту одиночную ошибку. Принимаемые данные сначала проходят внутренний декодер, где исправляются одиночные ошибки, затем записываются в буфер построчно, выводятся по столбцам и подаются на внешний декодер, где происходит исправление пакетной ошибки.

Использование кодов-произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности.

Источник

Контроль четности

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

Содержание

Примеры

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

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

Применение

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

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

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

См. также

Литература

Полезное

Смотреть что такое «Контроль четности» в других словарях:

контроль четности — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN odd even check … Справочник технического переводчика

поблочный контроль четности — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN block parity … Справочник технического переводчика

поперечный контроль четности — — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в целом EN horisontal parity … Справочник технического переводчика

продольный контроль четности — — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в целом EN vertical parity … Справочник технического переводчика

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

контроль по модулю n — контроль по остатку Простой метод обнаружения ошибок, основанный на анализе некоторого набора данных или участка программы. Если этот набор представляет собой совокупность блоков длиной m бит, то берется сумма по модулю n, где n = 2**m, и… … Справочник технического переводчика

контроль по остатку — контроль по модулю n Простой метод обнаружения ошибок, основанный на анализе некоторого набора данных или участка программы. Если этот набор представляет собой совокупность блоков длиной m бит, то берется сумма по модулю n, где n=2**m, и ставится … Справочник технического переводчика

контроль по четности — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN even odd checkeven parity check … Справочник технического переводчика

контроль по четности блока данных — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN madnie parity check … Справочник технического переводчика

контроль по четности — lyginumo kontrolė statusas T sritis automatika atitikmenys: angl. even odd check; even parity check; odd even check; odd parity check; parity check; parity detection vok. Gerade Ungerade Kontrolle, f; Paritätskontrolle, f; Paritätsprüfung, f rus … Automatikos terminų žodynas

Источник

• ← ушиб мягких тканей левой голени код по мкб 10
• дистрофия роговицы код мкб →