Бит четности - Parity bit
 | эта статья нужны дополнительные цитаты для проверка. (Январь 2013) (Узнайте, как и когда удалить этот шаблон сообщения) |
| 7 бит данных | (количество 1 бит) | 8 бит, включая четность | |
|---|---|---|---|
| даже | странный | ||
| 0000000 | 0 | 00000000 | 00000001 |
| 1010001 | 3 | 10100011 | 10100010 |
| 1101001 | 4 | 11010010 | 11010011 |
| 1111111 | 7 | 11111111 | 11111110 |
А бит четности, или же проверить бит, это кусочек добавлен к строке бинарный код. Биты четности используются как простейшая форма код обнаружения ошибок. Биты четности обычно применяются к самым маленьким блокам протокола связи, обычно 8-битным. октеты (байты), хотя они также могут применяться отдельно ко всей цепочке битов сообщения.
Бит четности гарантирует, что общее количество единиц в строке равно четным или нечетным.[1] Соответственно, есть два варианта битов четности: бит четности и бит нечетной четности. В случае четности для данного набора битов подсчитываются вхождения битов, значение которых равно 1. Если этот счетчик нечетный, значение бита четности устанавливается в 1, в результате чего общее количество вхождений единиц во всем наборе (включая бит четности) становится четным. Если счетчик единиц в данном наборе битов уже является четным, значение бита четности равно 0. В случае нечетной четности кодирование меняется на противоположное. Для данного набора битов, если количество битов со значением 1 является четным, значение бита четности устанавливается в 1, что делает общее количество единиц во всем наборе (включая бит четности) нечетным числом. Если количество битов со значением 1 нечетное, счет уже нечетный, поэтому значение бита четности равно 0. Четность - это частный случай циклическая проверка избыточности (CRC), где 1-битный CRC генерируется многочлен Икс+1.
Если бит присутствует в точке, иначе выделенной для бита четности, но не используется для проверки четности, он может называться маркировать бит четности если бит четности всегда равен 1, или бит четности пространства если бит всегда равен 0. В таких случаях, когда значение бита постоянно, его можно назвать придерживаться бит четности хотя его функция не имеет ничего общего с четностью.[2] Функция таких битов зависит от конструкции системы, но примеры функций для таких битов включают в себя управление синхронизацией или идентификацию пакета как имеющего значение данных или адреса.[3] Если его фактическое значение бита не имеет отношения к его функции, бит составляет срок безразличия.[4]
Паритет
В математике паритет относится к четности или нечетности целого числа, которое для двоичное число определяется только младший бит. В телекоммуникациях и вычислительной технике четность относится к четности или нечетности числа битов со значением один в заданном наборе битов и, таким образом, определяется значением всех битов. Его можно рассчитать через XOR сумма битов, дающая 0 для четности и 1 для нечетной четности. Это свойство зависимости от всех битов и изменения значения при изменении любого одного бита позволяет использовать его в обнаружение ошибок схемы.
Обнаружение ошибок
Если нечетное количество бит (включая бит четности) переданный неправильно, бит четности будет неправильным, что указывает на то, что ошибка четности произошло в передаче. Бит четности подходит только для обнаружения ошибок; это не может правильный любые ошибки, так как невозможно определить, какой именно бит поврежден. Данные должны быть полностью отброшены, и ретранслировать с нуля. Следовательно, в шумной среде передачи успешная передача может занять много времени или даже не произойти. Однако у четности есть то преимущество, что она использует только один бит и требует только нескольких Ворота 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 Алиса добавляет бит четности и отправляет: 10011 Боб получает: 10011 Боб вычисляет общую четность: 1 + 0 + 0 + 1 + 1 (mod 2) = 1 Боб сообщает о правильной передаче после наблюдения ожидаемого нечетного результата. |
Этот механизм позволяет обнаруживать одиночные битовые ошибки, потому что, если один бит перевернут из-за шума линии, в полученных данных будет неправильное количество единиц. В двух приведенных выше примерах вычисленное Бобом значение четности совпадает с битом четности в полученном значении, что указывает на отсутствие одиночных битовых ошибок. Рассмотрим следующий пример с ошибкой передачи во втором бите с использованием XOR:
| Тип битовой ошибки четности | Сценарий неудачной передачи |
|---|---|
| Четный паритет Ошибка во втором бите | Алиса хочет передать: 1001 Алиса вычисляет значение бита четности: 1 ^ 0 ^ 0 ^ 1 = 0 Алиса добавляет бит четности и отправляет: 10010 ... ОШИБКА ПЕРЕДАЧИ ... Боб получает: 11010 Боб вычисляет общую четность: 1 ^ 1 ^ 0 ^ 1 ^ 0 = 1 Боб сообщает о неправильной передаче после получения неожиданного нечетного результата. |
| Четный паритет Ошибка в бите четности | Алиса хочет передать: 1001 Алиса вычисляет значение четности: 1 ^ 0 ^ 0 ^ 1 = 0 Алиса отправляет: 10010 ... ОШИБКА ПЕРЕДАЧИ ... Боб получает: 10011 Боб вычисляет общую четность: 1 ^ 0 ^ 0 ^ 1 ^ 1 = 1 Боб сообщает о неправильной передаче после получения неожиданного нечетного результата. |
Есть ограничение на схемы четности. Бит четности гарантированно обнаруживает нечетное количество битовых ошибок. Если четное количество битов содержит ошибки, бит четности записывает правильное количество единиц, даже если данные повреждены. (Смотрите также обнаружение и исправление ошибок.) Рассмотрим тот же пример, что и раньше, с четным числом поврежденных битов:
| Тип битовой ошибки четности | Сценарий неудачной передачи |
|---|---|
| Четный паритет Два поврежденных бита | Алиса хочет передать: 1001 Алиса вычисляет значение четности: 1 ^ 0 ^ 0 ^ 1 = 0 Алиса отправляет: 10010 ... ОШИБКА ПЕРЕДАЧИ ... Боб получает: 11011 Боб вычисляет общую четность: 1 ^ 1 ^ 0 ^ 1 ^ 1 = 0 Боб сообщает о правильной передаче, хотя на самом деле неверной. |
Боб, как и ожидалось, наблюдает четность, тем самым не обнаруживая двух битовых ошибок.
Применение
Из-за своей простоты четность используется во многих аппаратное обеспечение приложения, в которых операция может быть повторена в случае затруднения, или где полезно простое обнаружение ошибки. Например, SCSI и Шины PCI использовать четность для обнаружения ошибок передачи, и многие микропроцессор инструкция тайники включить защиту четности. Поскольку I-cache данные - это просто копия основная память, его можно проигнорировать и повторно загрузить, если обнаружится, что он поврежден.
В серийный передача данных, общий формат - 7 бит данных, бит четности и один или два стоповые биты. Этот формат поддерживает все 7-битные ASCII символы в 8-битном байте. Возможны другие форматы; 8 бит данных плюс бит четности могут передавать все 8-битные байтовые значения.
В контексте последовательной связи четность обычно генерируется и проверяется аппаратным обеспечением интерфейса (например, UART ) и, при приеме, результат предоставляется процессор такие как ЦП (и то же самое, например, Операционная система ) через бит состояния в регистр оборудования в интерфейс аппаратное обеспечение. Восстановление после ошибки обычно осуществляется путем повторной передачи данных, детали которой обычно обрабатываются программным обеспечением (например, процедурами ввода-вывода операционной системы).
Когда общее количество переданных битов, включая бит четности, является четным, нечетная четность имеет то преимущество, что обе комбинации из нулей и все единицы обнаруживаются как ошибки. Если общее количество битов нечетное, только один из шаблонов обнаруживается как ошибка, и выбор может быть сделан на основе того, какая, как ожидается, будет более распространенной ошибкой.
Избыточный массив независимых дисков
Данные о четности используются некоторыми избыточный массив независимых дисков (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 применима аналогично к большим массивам с использованием любого количества дисков. В случае массива RAID 3 из 12 дисков 11 дисков участвуют в вычислении XOR, показанном выше, и выдают значение, которое затем сохраняется на выделенном диске четности.
Расширения и вариации механизма битов четности «двойная», «двойная» или «диагональная» четность используются в RAID-DP.
История
«Трек паритета» присутствовал на первом хранение данных на магнитной ленте в 1951 г. Четность в этой форме, применяемая к нескольким параллельным сигналам, известна как поперечный контроль избыточности. Это можно комбинировать с проверкой четности, вычисляемой по нескольким битам, отправляемым в одном сигнале, проверка продольного дублирования. В параллельной шине на каждый параллельный сигнал приходится один бит проверки продольным избыточным кодом.
Четность также использовалась хоть на какой-то бумажной ленте (перфолента ) системы ввода данных (предшествовавшие системам на магнитной ленте). В системах, продаваемых британской компанией ICL (ранее ICT), бумажная лента шириной 1 дюйм (25 мм) имела 8 отверстий, проходящих через нее, причем 8-е было для проверки четности. Для данных использовалось 7 позиций, например, 7-битный ASCII. В 8-й позиции было пробито отверстие в зависимости от количества пробитых отверстий для данных.
Смотрите также
Рекомендации
- ^ Ziemer, RodgerE .; Трантер, Уильям Х. Принципы связи: системы, модуляция и шум (Седьмое изд.). Хобокен, Нью-Джерси. ISBN 9781118078914. OCLC 856647730.
- ^ «В чем разница между использованием четности меток или пробелов и без четности».[ненадежный источник? ]
- ^ "Какова цель Stick Parity?".
- ^ «Последовательная связь», Сб-дайджест, получено 2020-03-23