Бит чётности

Поделись знанием:
Перейти к: навигация, поиск

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





Применение

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

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

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

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

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

Примеры

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

Рассмотрим схему, использующую девятибитные кодовые слова, состоящие из восьми бит данных, за которыми следует бит чётности.

  • Число 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.

Отрывок, характеризующий Бит чётности

– Славно идут, – сказал кто то в свите Багратиона.
Голова колонны спустилась уже в лощину. Столкновение должно было произойти на этой стороне спуска…
Остатки нашего полка, бывшего в деле, поспешно строясь, отходили вправо; из за них, разгоняя отставших, подходили стройно два баталиона 6 го егерского. Они еще не поровнялись с Багратионом, а уже слышен был тяжелый, грузный шаг, отбиваемый в ногу всею массой людей. С левого фланга шел ближе всех к Багратиону ротный командир, круглолицый, статный мужчина с глупым, счастливым выражением лица, тот самый, который выбежал из балагана. Он, видимо, ни о чем не думал в эту минуту, кроме того, что он молодцом пройдет мимо начальства.
С фрунтовым самодовольством он шел легко на мускулистых ногах, точно он плыл, без малейшего усилия вытягиваясь и отличаясь этою легкостью от тяжелого шага солдат, шедших по его шагу. Он нес у ноги вынутую тоненькую, узенькую шпагу (гнутую шпажку, не похожую на оружие) и, оглядываясь то на начальство, то назад, не теряя шагу, гибко поворачивался всем своим сильным станом. Казалось, все силы души его были направлены на то,чтобы наилучшим образом пройти мимо начальства, и, чувствуя, что он исполняет это дело хорошо, он был счастлив. «Левой… левой… левой…», казалось, внутренно приговаривал он через каждый шаг, и по этому такту с разно образно строгими лицами двигалась стена солдатских фигур, отягченных ранцами и ружьями, как будто каждый из этих сотен солдат мысленно через шаг приговаривал: «левой… левой… левой…». Толстый майор, пыхтя и разрознивая шаг, обходил куст по дороге; отставший солдат, запыхавшись, с испуганным лицом за свою неисправность, рысью догонял роту; ядро, нажимая воздух, пролетело над головой князя Багратиона и свиты и в такт: «левой – левой!» ударилось в колонну. «Сомкнись!» послышался щеголяющий голос ротного командира. Солдаты дугой обходили что то в том месте, куда упало ядро; старый кавалер, фланговый унтер офицер, отстав около убитых, догнал свой ряд, подпрыгнув, переменил ногу, попал в шаг и сердито оглянулся. «Левой… левой… левой…», казалось, слышалось из за угрожающего молчания и однообразного звука единовременно ударяющих о землю ног.
– Молодцами, ребята! – сказал князь Багратион.
«Ради… ого го го го го!…» раздалось по рядам. Угрюмый солдат, шедший слева, крича, оглянулся глазами на Багратиона с таким выражением, как будто говорил: «сами знаем»; другой, не оглядываясь и как будто боясь развлечься, разинув рот, кричал и проходил.
Велено было остановиться и снять ранцы.
Багратион объехал прошедшие мимо его ряды и слез с лошади. Он отдал казаку поводья, снял и отдал бурку, расправил ноги и поправил на голове картуз. Голова французской колонны, с офицерами впереди, показалась из под горы.
«С Богом!» проговорил Багратион твердым, слышным голосом, на мгновение обернулся к фронту и, слегка размахивая руками, неловким шагом кавалериста, как бы трудясь, пошел вперед по неровному полю. Князь Андрей чувствовал, что какая то непреодолимая сила влечет его вперед, и испытывал большое счастие. [Тут произошла та атака, про которую Тьер говорит: «Les russes se conduisirent vaillamment, et chose rare a la guerre, on vit deux masses d'infanterie Mariecher resolument l'une contre l'autre sans qu'aucune des deux ceda avant d'etre abordee»; а Наполеон на острове Св. Елены сказал: «Quelques bataillons russes montrerent de l'intrepidite„. [Русские вели себя доблестно, и вещь – редкая на войне, две массы пехоты шли решительно одна против другой, и ни одна из двух не уступила до самого столкновения“. Слова Наполеона: [Несколько русских батальонов проявили бесстрашие.]