Бит четности , или контрольный бит , — это бит, добавляемый к строке двоичного кода . Биты четности — это простая форма кода обнаружения ошибок . Биты четности обычно применяются к наименьшим единицам протокола связи, обычно к 8-битным октетам (байтам), хотя их также можно применять отдельно ко всей строке битов сообщения.
Бит четности гарантирует, что общее количество единичных битов в строке будет четным или нечетным . [1] Соответственно, существует два варианта битов четности: четный бит четности и нечетный бит четности . В случае четной четности для заданного набора битов подсчитываются биты, значение которых равно 1. Если это количество нечетное, значение бита четности устанавливается равным 1, что делает общее количество вхождений единиц во всем наборе (включая бит четности) четным числом. Если количество единиц в заданном наборе бит уже четное, значение бита четности равно 0. В случае нечетной четности кодирование меняется на обратное. Для заданного набора битов, если количество битов со значением 1 четное, значение бита четности устанавливается равным 1, что делает общее количество единиц во всем наборе (включая бит четности) нечетным числом. Если количество битов со значением 1 нечетно, то количество уже нечетно, поэтому значение бита четности равно 0. Четность — это особый случай циклического избыточного кода (CRC), где 1-битный CRC генерируется полиномом x +1 .
В математике четность может относиться к четности или нечетности целого числа, которое, если записать его в двоичной форме , можно определить, просто проверив только его младший бит .
В информационных технологиях четность относится к четности или нечетности, заданной любым набором двоичных цифр, числа тех битов со значением 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-массивами ( избыточный массив независимых/недорогих дисков ) для достижения избыточности . Если диск в массиве выходит из строя, оставшиеся данные на других дисках можно объединить с данными четности (используя функцию Boolean XOR ) для восстановления недостающих данных.
Например, предположим, что два диска в трехдисковом массиве RAID 4 содержат следующие данные:
Для вычисления данных четности для двух дисков над их данными выполняется операция 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: отсутствует местоположение издателя ( ссылка )