 | Эта статья требует дополнительных ссылок для проверки . ( январь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
| 7 бит данных | (количество 1 бит) | 8 бит, включая четность | |
|---|---|---|---|
| четный | странный | ||
| 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, в результате чего общее количество вхождений единиц во всем наборе (включая бит четности) становится четным. Если счетчик единиц в данном наборе битов уже четный, значение бита четности равно 0. В случае нечетной четности кодирование меняется на противоположное. Для данного набора битов, если количество битов со значением 1 является четным, значение бита четности устанавливается в 1, делая общее количество единиц во всем наборе (включая бит четности) нечетным числом. Если количество битов со значением 1 нечетное, счетчик уже нечетный, поэтому значение бита четности равно 0. Четность является частным случаем циклического контроля избыточности (CRC), где 1-битный CRC генерируется с помощью вмногочлен x +1.
Если бит присутствует в точке, в противном случае выделенной для бита четности, но не используется для проверки четности, он может называться битом четности метки, если бит четности всегда равен 1, или битом четности пространства, если бит всегда равен 0 В таких случаях, когда значение бита является постоянным, его можно назвать битом контроля четности, даже если его функция не имеет ничего общего с проверкой четности. [2] Функция таких битов зависит от конструкции системы, но примеры функций для таких битов включают в себя управление синхронизацией или идентификацию пакета как имеющего значение данных или адреса. [3] Если его фактическое значение бита не имеет отношения к его функции, бит представляет собой термин «безразличие» . [4]
Четность [ править ]
В математике четность относится к четности или нечетности целого числа, которое для двоичного числа определяется только младшим значащим битом .
В телекоммуникациях и вычислениях четность относится к четности или нечетности числа битов со значением один в заданном наборе битов и, таким образом, определяется значением всех битов. Это свойство зависимости от всех битов и изменения значения при изменении любого одного бита позволяет использовать его в схемах обнаружения и исправления ошибок.
В телекоммуникациях четность некоторых протоколов относится к схеме обнаружения ошибок , где контрольный бит, вычисляемый отправителем для каждого пакета, равен нулю или единице, в зависимости от того, использует ли он четность или нечетность, так что получатель может обнаружить ошибку четности и запросить повторную передачу всего пакета.
В компьютерных технологиях хранения данных четность относится к схеме исправления ошибок для повторного вычисления точного значения каждого бита отсутствующего байта или отсутствующего блока или для репликации каждого бита отказавшего диска хранения для восстановления на замена диска. В этом случае либо защитные биты четности, либо соответствующие им биты восстановленных данных вычисляются с помощью логики XOR , которая напоминает четность, даже если алгоритмы, которые они составляют, сильно отличаются.
Обнаружение ошибки [ править ]
Если нечетное количество битов (включая бит четности) передается неправильно, бит четности будет неправильным, что указывает на то, что при передаче произошла ошибка четности . Бит четности подходит только для обнаружения ошибок; он не может исправить ошибки, так как невозможно определить, какой именно бит поврежден. Данные должны быть полностью отброшены и повторно переданы с нуля . Таким образом, в шумной среде передачи успешная передача может занять много времени или даже не произойти. Однако у четности есть то преимущество, что она использует только один бит и требует для генерации только нескольких вентилей XOR . См. Пример кода с исправлением ошибок в коде Хэмминга .
Проверка битов на четность иногда используется для передачи символов ASCII , которые имеют 7 бит, при этом 8-й бит остается битом четности.
Например, бит четности можно вычислить следующим образом. Предположим, что Алиса и Боб обмениваются данными, и Алиса хочет отправить Бобу простое 4-битное сообщение 1001.
| Тип битовой четности | Сценарий успешной передачи |
|---|---|
| Четный паритет | Алиса хочет передать: 1001 Алиса вычисляет значение бита четности: 1 + 0 + 0 + 1 (mod 2) = 0 Алиса добавляет бит четности и отправляет: 10010 Боб получает: 10010 Боб вычисляет четность: 1 + 0 + 0 + 1 + 0 (mod 2) = 0 Боб сообщает о правильной передаче после наблюдения ожидаемого равномерного результата. |
| Нечетная четность | Алиса хочет передать: 1001 Алиса вычисляет значение бита четности: 1 + 0 + 0 + 1 (mod 2) = 0 Алиса добавляет бит четности и отправляет: 1001 1 Боб получает: 10011 Боб вычисляет общую четность: 1 + 0 + 0 + 1 + 1 (mod 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 используют четность для обнаружения ошибок передачи, а многие кеши инструкций микропроцессора включают защиту четности. Поскольку данные I-кэша являются просто копией основной памяти , их можно не принимать во внимание и повторно выбирать, если обнаруживается, что они повреждены.
При последовательной передаче данных общий формат - это 7 бит данных, бит четности и один или два стоповых бита . Этот формат вмещает все 7-битные символы ASCII в 8-битный байт. Возможны другие форматы; 8 бит данных плюс бит четности могут передавать все 8-битные байтовые значения.
В контексте последовательной связи четность обычно генерируется и проверяется аппаратным обеспечением интерфейса (например, UART ), и при приеме результат становится доступным для процессора, такого как CPU (и, например, также, для операционной системы ), через бит состояния в аппаратном регистре в интерфейсе оборудования. Восстановление после ошибки обычно осуществляется путем повторной передачи данных, детали которой обычно обрабатываются программным обеспечением (например, процедурами ввода-вывода операционной системы).
Когда общее количество переданных битов, включая бит четности, является четным, нечетная четность имеет то преимущество, что обе комбинации из нулей и все единицы обнаруживаются как ошибки. Если общее количество битов нечетное, только один из шаблонов обнаруживается как ошибка, и выбор может быть сделан на основе того, какая, как ожидается, будет более распространенной ошибкой.
Резервный массив независимых дисков [ править ]
Данные четности используются некоторым избыточным массивом независимых дисков (RAID) уровней для достижения избыточности . Если диск в массиве выходит из строя, оставшиеся данные на других дисках можно объединить с данными четности (с помощью логической функции XOR ) для восстановления недостающих данных.
Например, предположим, что два диска в массиве RAID 5 с тремя дисками содержат следующие данные:
Привод 1: 01101101
Привод 2: 11010100
Чтобы вычислить данные о четности для двух дисков, над их данными выполняется XOR:
01101101
XOR 11010100
_____________
10111001
Полученные данные четности, 10111001 , затем сохраняются на Диске 3.
Если какой-либо из трех дисков выйдет из строя, содержимое отказавшего диска можно восстановить на новом диске, подвергнув данные с оставшихся дисков той же операции XOR. Если диск 2 выйдет из строя, его данные можно будет восстановить, используя результаты XOR содержимого двух оставшихся дисков, диска 1 и диска 3:
Привод 1: 01101101
Привод 3: 10111001
следующим образом:
10111001
XOR 01101101
_____________
11010100
Результат этого вычисления 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-й позиции было пробито отверстие в зависимости от количества пробитых отверстий для данных.
См. Также [ править ]
- БИП-8
- Функция четности
- Одно событие расстроено
- 8-N-1
- Контрольная цифра
Ссылки [ править ]
- ^ Ziemer, RodgerE .; Трантер, Уильям Х. Принципы коммуникации: системы, модуляция и шум (седьмое изд.). Хобокен, Нью-Джерси. ISBN 9781118078914. OCLC 856647730 .
- ^ "В чем разница между использованием четности меток или пробелов и без четности" .[ ненадежный источник? ]
- ^ "Какова цель Stick Parity?" .
- ^ "Serial Communications" , Сб-дайджест , получено 23 марта 2020 г.
Внешние ссылки [ править ]
- Различные методы генерации бита четности, среди других битовых операций
