Бит четности , или проверочный бит , добавляется к строке двоичного кода . Биты четности представляют собой простую форму кода обнаружения ошибок . Биты четности обычно применяются к наименьшим единицам протокола связи, обычно к 8-битным октетам (байтам), хотя их также можно применять отдельно ко всей строке битов сообщения.
Бит четности гарантирует, что общее количество единиц 1 бит в строке будет четным или нечетным . [1] Соответственно, существует два варианта битов четности: бит четности и бит нечетности . В случае четности для заданного набора битов считаются биты, значение которых равно 1. Если этот счетчик нечетный, значение бита четности устанавливается равным 1, что делает общее количество появлений единиц во всем наборе (включая бит четности) четным. Если количество единиц в данном наборе бит уже четное, значение бита четности равно 0. В случае нечетной четности кодирование меняется на противоположное. Для данного набора битов, если количество битов со значением 1 четное, значение бита четности устанавливается равным 1, что делает общее количество единиц во всем наборе (включая бит четности) нечетным числом. Если количество битов со значением 1 нечетное, это число уже нечетное, поэтому значение бита четности равно 0. Четность — это особый случай проверки циклическим избыточным кодом (CRC), где 1-битный CRC генерируется многочлен x +1 .
В математике четность может относиться к четности или нечетности целого числа, которое, записанное в двоичной форме , можно определить, просто исследовав только его младший бит .
В информационных технологиях четность относится к четности или нечетности для любого набора двоичных цифр количества битов со значением один. Поскольку четность определяется состоянием каждого из битов, это свойство четности - зависеть от всех битов и изменять свое значение с четного на нечетное при изменении любого одного бита - позволяет использовать его в схемах обнаружения и исправления ошибок. .
В телекоммуникациях четность, упоминаемая в некоторых протоколах, предназначена для обнаружения ошибок . Среда передачи предварительно настроена в обеих конечных точках для согласования либо нечетной, либо четной четности. Для каждой строки битов, готовой к передаче (пакета данных), отправитель вычисляет бит четности, нулевой или один, чтобы привести ее в соответствие с согласованной четностью, четной или нечетной. Получатель этого пакета сначала проверяет, что четность пакета в целом соответствует заданному соглашению, затем, если в этом пакете была ошибка четности, запрашивает повторную передачу этого пакета.
В информатике полоса четности или диск четности в RAID обеспечивает исправление ошибок . Биты четности записываются из расчета один бит четности на n бит, где n — количество дисков в массиве. При возникновении ошибки чтения каждый бит в области ошибки пересчитывается из набора из n битов. Таким образом, использование одного бита четности создает «избыточность» для региона размером от одного бита до размера одного диска. См. § Резервный массив независимых дисков ниже.
В электронике перекодирование данных с четностью может быть очень эффективным, поскольку элементы XOR выводят то, что эквивалентно проверочному биту, который создает четную четность, а логическая схема XOR легко масштабируется для любого количества входов. Структуры XOR и AND составляют основную часть большинства интегральных схем.
Если нечетное количество битов (включая бит четности) передается неправильно , бит четности будет неправильным, что указывает на то, что при передаче произошла ошибка четности . Бит четности подходит только для обнаружения ошибок; он не может исправить какие-либо ошибки, поскольку невозможно определить, какой именно бит поврежден. Данные необходимо полностью удалить и передать заново . Поэтому в зашумленной среде передачи успешная передача может занять много времени или даже никогда не произойти. Однако четность имеет то преимущество, что она использует только один бит и требует для генерации всего нескольких элементов XOR . См. «Код Хэмминга» для примера кода, исправляющего ошибки.
Проверка битов четности иногда используется для передачи символов ASCII , которые имеют 7 бит, оставляя 8-й бит в качестве бита четности.
Например, бит четности можно вычислить следующим образом. Предположим, Алиса и Боб общаются, и Алиса хочет послать Бобу простое 4-битное сообщение 1001.
Этот механизм позволяет обнаруживать одиночные битовые ошибки, поскольку если один бит инвертируется из-за линейного шума, в полученных данных будет неправильное количество единиц. В двух приведенных выше примерах вычисленное Бобом значение четности соответствует биту четности в полученном значении, что указывает на отсутствие ошибок в одном бите. Рассмотрим следующий пример с ошибкой передачи во втором бите с использованием XOR:
Существуют ограничения на паритетные схемы. Бит четности гарантированно обнаруживает только нечетное количество битовых ошибок. Если четное количество бит содержит ошибки, бит четности записывает правильное количество единиц, даже если данные повреждены. (См. также «Обнаружение и исправление ошибок» .) Рассмотрим тот же пример, что и раньше, но с четным числом поврежденных битов:
Боб, как и ожидалось, соблюдает четность, поэтому не может обнаружить две битовые ошибки.
Из-за своей простоты четность используется во многих аппаратных приложениях, в которых операция может быть повторена в случае возникновения затруднений или полезно просто обнаружить ошибку. Например, шины SCSI и PCI используют контроль четности для обнаружения ошибок передачи, а кэши инструкций многих микропроцессоров включают защиту четности. Поскольку данные кэша инструкций представляют собой всего лишь копию основной памяти , их можно игнорировать и загрузить повторно, если окажется, что они повреждены.
При последовательной передаче данных общий формат — 7 бит данных, бит четности и один или два стоповых бита . Этот формат объединяет все 7-битные символы ASCII в 8-битный байт. Возможны другие форматы; 8 бит данных плюс бит четности могут передавать все 8-битные байтовые значения.
В контексте последовательной связи четность обычно генерируется и проверяется аппаратным обеспечением интерфейса (таким как UART ), а при приеме результат становится доступным процессору, такому как ЦП (а также, например, операционной системе ) через бит состояния в аппаратном регистре аппаратного интерфейса . Восстановление после ошибки обычно выполняется путем повторной передачи данных, детали которых обычно обрабатываются программным обеспечением (например, процедурами ввода-вывода операционной системы).
Когда общее количество передаваемых битов, включая бит четности, четное, нечетная четность имеет то преимущество, что как шаблоны «все нули», так и шаблоны «все единицы» обнаруживаются как ошибки. Если общее количество битов нечетное, только один из шаблонов обнаруживается как ошибка, и выбор можно сделать на основе ожидаемой более распространенной ошибки.
Данные четности используются массивами RAID ( резервный массив независимых/недорогих дисков ) для достижения избыточности . Если один из дисков массива выходит из строя, оставшиеся данные на других дисках можно объединить с данными четности (с помощью логической функции XOR ) для восстановления недостающих данных.
Например, предположим, что два диска в массиве RAID 5 из трех дисков содержат следующие данные:
Чтобы вычислить данные четности для двух дисков, над их данными выполняется XOR:
Полученные данные четности, 10111001 , затем сохраняются на диске 3.
В случае сбоя любого из трех дисков содержимое неисправного диска можно восстановить на новом диске, подвергнув данные с остальных дисков той же операции XOR. Если диск 2 выйдет из строя, его данные можно будет восстановить, используя результаты XOR содержимого двух оставшихся дисков, диска 1 и диска 3:
следующее:
Результат этого вычисления 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-й позиции было пробито отверстие в зависимости от количества пробитых отверстий для данных.
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )