Бит четности

7 бит данных	(количество 1 бит)	8 бит, включая четность
7 бит данных	(количество 1 бит)	даже	странный
0000000	0	0000000 0	0000000 1
1010001	3	1010001 1	1010001 0
1101001	4	1101001 0	1101001 1
1111111	7	1111111 1	1111111 0

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

Бит четности гарантирует, что общее количество единиц 1 бит в строке будет четным или нечетным . ^[1] Соответственно, существует два варианта битов четности: бит четности и бит нечетности . В случае четности для заданного набора битов считаются биты, значение которых равно 1. Если этот счетчик нечетный, значение бита четности устанавливается равным 1, что делает общее количество вхождений единиц во всем наборе (включая бит четности) четным. Если количество единиц в данном наборе бит уже четное, значение бита четности равно 0. В случае нечетной четности кодирование меняется на противоположное. Для данного набора битов, если количество битов со значением 1 четное, значение бита четности устанавливается равным 1, что делает общее количество единиц во всем наборе (включая бит четности) нечетным числом. Если количество битов со значением 1 нечетное, это число уже нечетное, поэтому значение бита четности равно 0. Четность — это особый случай проверки циклическим избыточным кодом (CRC), когда 1-битный CRC генерируется многочлен +1 x .

Паритет

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

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

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

В информатике полоса четности или диск четности в RAID обеспечивает ошибок исправление . Биты четности записываются из расчета один бит четности на n бит, где n — количество дисков в массиве. При возникновении ошибки чтения каждый бит в области ошибки пересчитывается из набора из n битов. Таким образом, использование одного бита четности создает «избыточность» для региона размером от одного бита до размера одного диска. См. § Резервный массив независимых дисков ниже.

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

Обнаружение ошибок

Если нечетное количество битов (включая бит четности) передается неправильно, бит четности будет неправильным, что указывает на то, что ошибка четности при передаче произошла . Бит четности подходит только для обнаружения ошибок; он не может исправить какие-либо ошибки, поскольку невозможно определить, какой именно бит поврежден. Данные необходимо полностью удалить и передать заново . Поэтому в зашумленной среде передачи успешная передача может занять много времени или даже никогда не произойти. Однако преимущество четности заключается в том, что она использует только один бит и требует для генерации всего нескольких элементов XOR . См. «Код Хэмминга» для примера кода, исправляющего ошибки.

Проверка битов четности иногда используется для передачи символов ASCII , которые имеют 7 бит, оставляя 8-й бит в качестве бита четности.

Например, бит четности можно вычислить следующим образом. Предположим, Алиса и Боб общаются, и Алиса хочет послать Бобу простое 4-битное сообщение 1001.

Тип битовой четности	Успешный сценарий передачи
Равный паритет	Алиса хочет передать: 1001 и 1011. Алиса вычисляет значение бита четности: 1+0+0+1 (против 2) = 0 1+0+1+1 (против 2) = 1 Алиса добавляет бит четности и отправляет: 1001 0 и 1011 1 Боб получает: 10010 и 10111. Боб вычисляет четность: 1+0+0+1+0 (модуль 2) = 0 1+0+1+1+1 (модуль 2) = 0 Боб сообщает о правильной передаче, увидев ожидаемый ровный результат.
Нечетная четность	Алиса хочет передать: 1001 и 1011. Алиса вычисляет значение бита четности: 1+0+0+1 (+1 против 2) = 1 1+0+1+1 (+1 против 2) = 0 Алиса добавляет бит четности и отправляет: 1001 1 и 1011 0 Боб получает: 10011 и 10110. Боб вычисляет общую четность: 1+0+0+1+1 (против 2) = 1 1+0+1+1+0 (модуль 2) = 1 Боб сообщает о правильной передаче, увидев ожидаемый нечетный результат.

Этот механизм позволяет обнаруживать однобитовые ошибки, поскольку если один бит инвертируется из-за линейного шума, в полученных данных будет неправильное количество единиц. В двух приведенных выше примерах вычисленное Бобом значение четности соответствует биту четности в полученном значении, что указывает на отсутствие ошибок в одном бите. Рассмотрим следующий пример с ошибкой передачи во втором бите с использованием XOR:

Тип ошибки четности битов	Сценарий неудачной передачи
Равный паритет Ошибка во втором бите	Алиса хочет передать: 1001 Алиса вычисляет значение бита четности: 1^0^0^1 = 0. Алиса добавляет бит четности и отправляет: 10010. ...ОШИБКА ПЕРЕДАЧИ... Боб получает: 1 1 010 Боб вычисляет общую четность: 1^1^0^1^0 = 1. Боб сообщает о неправильной передаче, увидев неожиданный странный результат.
Равный паритет Ошибка в бите четности	Алиса хочет передать: 1001 Алиса вычисляет четное значение: 1^0^0^1 = 0. Алиса отправляет: 10010 ...ОШИБКА ПЕРЕДАЧИ... Боб получает: 1001 1 Боб вычисляет общую четность: 1^0^0^1^1 = 1. Боб сообщает о неправильной передаче, увидев неожиданный странный результат.

Существуют ограничения на паритетные схемы. Бит четности гарантированно обнаруживает только нечетное количество битовых ошибок. Если четное количество бит содержит ошибки, бит четности записывает правильное количество единиц, даже если данные повреждены. (См. также «Обнаружение и исправление ошибок» .) Рассмотрим тот же пример, что и раньше, но с четным числом поврежденных битов:

Тип ошибки четности битов	Сценарий неудачной передачи
Равный паритет Два поврежденных бита	Алиса хочет передать: 1001 Алиса вычисляет четное значение: 1^0^0^1 = 0. Алиса отправляет: 10010 ...ОШИБКА ПЕРЕДАЧИ... Боб получает: 1 1 01 1 Боб вычисляет общую четность: 1^1^0^1^1 = 0. Боб сообщает о правильной передаче, хотя на самом деле она неверна.

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

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

Из-за своей простоты четность используется во многих аппаратных приложениях, в которых операция может быть повторена в случае возникновения затруднений или полезно просто обнаружить ошибку. Например, шины SCSI и PCI используют четность для обнаружения ошибок передачи, а многих микропроцессоров инструкций кэши включают защиту по четности. Поскольку данные кэша инструкций являются всего лишь копией основной памяти , их можно игнорировать и загрузить повторно, если окажется, что они повреждены.

При последовательной передаче данных общий формат — 7 бит данных, бит четности и один или два стоповых бита . Этот формат объединяет все 7-битные символы ASCII в 8-битный байт. Возможны другие форматы; 8 бит данных плюс бит четности могут передавать все 8-битные байтовые значения.

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

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

RAID-массив

Данные четности используются массивами RAID ( резервный массив независимых/недорогих дисков ) для достижения избыточности . Если один из дисков массива выходит из строя, оставшиеся данные на других дисках можно объединить с данными четности (с помощью логической функции XOR ) для восстановления недостающих данных.

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

Диск 1:	01101101
Диск 2:	11010100

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

	01101101
БЕСПЛАТНО	11010100
	10111001

Полученные данные четности, 10111001 , затем сохраняются на диске 3.

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

Диск 1:	01101101
Диск 3:	10111001

следующее:

	01101101	Диск 1
БЕСПЛАТНО	10111001	Драйв 3
	11010100	Реконструированный проезд 2

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

Логика XOR также эквивалентна четности (поскольку XOR когда b XOR c XOR ... может рассматриваться как XOR( a , b , c ,...), который является n-арным оператором, который истинен тогда и только тогда, нечетное число аргументов истинно). Таким образом, та же самая концепция XOR, описанная выше, применима аналогично к более крупным массивам RAID с четностью, использующим любое количество дисков. В случае массива RAID 3 из 12 дисков 11 дисков участвуют в вычислении XOR, показанном выше, и дают значение, которое затем сохраняется на выделенном диске четности.

используются расширения и вариации механизма битов четности «двойная», «двойная» или «диагональная» четность В RAID-DP .

История

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

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

См. также

Ссылки

^ Цимер, Роджер Э.; Трантер, Уильям Х. (17 марта 2014 г.). Принципы связи: системы, модуляция и шум (Седьмое изд.). Хобокен, Нью-Джерси. ISBN 9781118078914 . OCLC 856647730 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

Внешние ссылки

Различные методы генерации бита четности, среди других битовых операций.

[1] Цимер, Роджер Э.; Трантер, Уильям Х. (17 марта 2014 г.). Принципы связи: системы, модуляция и шум (Седьмое изд.). Хобокен, Нью-Джерси. ISBN 9781118078914 . OCLC 856647730 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[1]