Разное

Бит четности: Бит чётности — это… Что такое Бит чётности?

Содержание

Бит чётности — это… Что такое Бит чётности?

В вычислительной технике и сетях передачи данных би́том чётности (англ. Parity bit) называют контрольный бит, служащий для проверки общей чётности двоичного числа (чётности количества единичных битов в числе).

Применение

В последовательной передаче данных часто используется формат 7 бит данных, бит чётности, один или два стоповых бита. Такой формат аккуратно размещает все 7-битные ASCII символы в удобный 8-битный байт. Также допустимы другие форматы: 8 бит данных и бит чётности.

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

Контроль некой двоичной последовательности (например, машинного слова) с помощью бита чётности также называют контролем по паритету. Контроль по паритету представляет собой наиболее простой и наименее мощный метод контроля данных. С его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Двойная ошибка, будет неверно принята за корректные данные. Поэтому контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод редко применяется в компьютерных сетях из-за невысоких диагностических способностей. Существует модификация этого метода — вертикальный и горизонтальный контроль по паритету. Отличие состоит в том, что исходные данные рассматриваются в виде матрицы, строки которой составляют байты данных. Контрольный разряд подсчитывается отдельно для каждой строки и для каждого столбца матрицы. Этот метод обнаруживает значительную часть двойных ошибок, однако обладает большей избыточностью. Он сейчас также почти не применяется при передаче информации по сети.

Полиномы CRC и бит чётности

Контроль по чётности фактически является специальным случаем проверки избыточности циклической суммы с полиномом x+1.

Примеры

Бит чётности или контрольный разряд формируется при выполнении операции «Исключающее-ИЛИ» поразрядно. Рассмотрим схему, использующую девятибитные кодовые слова, состоящие из восьми бит данных, за которыми следует бит чётности.

  • Число 10111101 содержит 6 ‘1’ битов. Бит чётности будет 0, получаем кодовое слово 101111010.
  • Число 01110011 содержит 5 ‘1’ битов. Бит чётности будет 1, получаем кодовое слово 011100111.
  • Число 00000000 содержит 0 ‘1’ битов. Бит чётности будет 0, получаем кодовое слово 000000000.

Пустой или несуществующий поток битов также имеет ноль единичных битов, поэтому бит чётности будет 0.

См. также

  • Чётность используется для восстановления данных в RAID.
  • Parity RAM использует чётность для обнаружения ошибок памяти.
  • Код Хемминга — следующий шаг после бита чётности.

Литература

  • Генри С. Уоррен, мл. Глава 5. Подсчет битов // Алгоритмические трюки для программистов = Hacker’s Delight.  — М.: «Вильямс», 2007. — С. 288. — ISBN 0-201-91465-4

Бит четности — Parity bit

Бит добавляется к двоичной строке и используется как код обнаружения ошибок

7 бит данных(количество 1 бит)8 бит, включая четность
четныйстранный
000000000000000 00000000 1
101000131010001 11010001 0
110100141101001 01101001 1
111111171111111 11111111 0

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

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

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

Паритет

В математике четность относится к четности или нечетности целого числа, которое для двоичного числа определяется только младшим значащим битом . В телекоммуникациях и вычислительной технике четность относится к четности или нечетности числа битов со значением один в заданном наборе битов и, таким образом, определяется значением всех битов. Его можно вычислить с помощью суммы битов 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

Алиса добавляет бит четности и отправляет: 1001 1

Боб получает: 10011

Боб вычисляет общую четность: 1 + 0 + 0 + 1 + 1 (mod 2) = 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 применяется аналогично к большим массивам, использующим любое количество дисков. В случае массива RAID 3 из 12 дисков 11 дисков участвуют в вычислении XOR, показанном выше, и выдают значение, которое затем сохраняется на выделенном диске четности.

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

История

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

Четность также использовалась по крайней мере в некоторых системах ввода данных с бумажной ленты ( перфоленты ) (которые предшествовали системам с магнитной лентой). auchCRCHi[uIndex] ;
uchCRCHi = auchCRCLo[uIndex] ;
}
return (uchCRCHi << 8 | uchCRCLo) ;

/* Table of CRC values for high–order byte */
static unsigned char auchCRCHi[] = {
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81,
0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01,
0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81,
0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01,
0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81,
0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01,
0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81,
0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01,
0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81,
0x40
};
/* Table of CRC values for low–order byte */
static char auchCRCLo[] = {
0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06, 0x07, 0xC7, 0x05, 0xC5, 0xC4,
0x04, 0xCC, 0x0C, 0x0D, 0xCD, 0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09,
0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A, 0x1E, 0xDE, 0xDF, 0x1F, 0xDD,
0x1D, 0x1C, 0xDC, 0x14, 0xD4, 0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3,
0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3, 0xF2, 0x32, 0x36, 0xF6, 0xF7,
0x37, 0xF5, 0x35, 0x34, 0xF4, 0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A,
0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29, 0xEB, 0x2B, 0x2A, 0xEA, 0xEE,
0x2E, 0x2F, 0xEF, 0x2D, 0xED, 0xEC, 0x2C, 0xE4, 0x24, 0x25, 0xE5, 0x27, 0xE7, 0xE6, 0x26,
0x22, 0xE2, 0xE3, 0x23, 0xE1, 0x21, 0x20, 0xE0, 0xA0, 0x60, 0x61, 0xA1, 0x63, 0xA3, 0xA2,
0x62, 0x66, 0xA6, 0xA7, 0x67, 0xA5, 0x65, 0x64, 0xA4, 0x6C, 0xAC, 0xAD, 0x6D, 0xAF, 0x6F,
0x6E, 0xAE, 0xAA, 0x6A, 0x6B, 0xAB, 0x69, 0xA9, 0xA8, 0x68, 0x78, 0xB8, 0xB9, 0x79, 0xBB,
0x7B, 0x7A, 0xBA, 0xBE, 0x7E, 0x7F, 0xBF, 0x7D, 0xBD, 0xBC, 0x7C, 0xB4, 0x74, 0x75, 0xB5,
0x77, 0xB7, 0xB6, 0x76, 0x72, 0xB2, 0xB3, 0x73, 0xB1, 0x71, 0x70, 0xB0, 0x50, 0x90, 0x91,
0x51, 0x93, 0x53, 0x52, 0x92, 0x96, 0x56, 0x57, 0x97, 0x55, 0x95, 0x94, 0x54, 0x9C, 0x5C,
0x5D, 0x9D, 0x5F, 0x9F, 0x9E, 0x5E, 0x5A, 0x9A, 0x9B, 0x5B, 0x99, 0x59, 0x58, 0x98, 0x88,
0x48, 0x49, 0x89, 0x4B, 0x8B, 0x8A, 0x4A, 0x4E, 0x8E, 0x8F, 0x4F, 0x8D, 0x4D, 0x4C, 0x8C,
0x44, 0x84, 0x85, 0x45, 0x87, 0x47, 0x46, 0x86, 0x82, 0x42, 0x43, 0x83, 0x41, 0x81, 0x80,
0x40
};
}
}

Как проверить, имеет ли значение четность битов или нечетность?

x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;

предполагая, что вы знаете, что ints 32 бита. = x >> 1:

( a b ac bd АПФ bdf aceg bdfh )
исключающее или
( 0 a b ac bd АПФ bdf aceg )

результат следующие биты:

( a ab abc abcd abcde abcdef abcdefgh abcdefgh )


мы накопили все биты в исходном слове, XOR’D вместе, в наименее значимом бит. Таким образом, этот бит теперь равен нулю, если и только если во входном слове было четное число 1 бит (четность). Тот же процесс работает на 32-разрядных целых чисел (но требует двух дополнительных изменений, которые мы пропустили в этой демонстрации).

последняя строка кода просто удаляет все, кроме наименее значимого бита (& 1), а затем переворачивает его (~x). Таким образом, результат равен 1, Если четность входного слова была четной или нулевой в противном случае.

Цифровые комбинированные схемы — CoderLessons. com

Комбинационные схемы состоят из логических элементов. Эти схемы работают с двоичными значениями. Выход (ы) комбинационной схемы зависит от комбинации имеющихся входов. На следующем рисунке показана блок-схема комбинационной схемы.

Эта комбинационная схема имеет n входных переменных и m выходов. Каждая комбинация входных переменных будет влиять на выходные данные.

Методика расчета комбинационных цепей

  • Найдите требуемое количество входных переменных и выходов из заданных спецификаций.

  • Сформулируйте таблицу Истины . Если есть n входных переменных, то будет 2n возможных комбинаций. Для каждой комбинации входных данных найдите выходные значения.

  • Найдите логические выражения для каждого вывода. При необходимости упростите эти выражения.

  • Реализуйте вышеупомянутые логические выражения, соответствующие каждому выводу, используя логические элементы .

Найдите требуемое количество входных переменных и выходов из заданных спецификаций.

Сформулируйте таблицу Истины . Если есть n входных переменных, то будет 2n возможных комбинаций. Для каждой комбинации входных данных найдите выходные значения.

Найдите логические выражения для каждого вывода. При необходимости упростите эти выражения.

Реализуйте вышеупомянутые логические выражения, соответствующие каждому выводу, используя логические элементы .

Преобразователи кода

Мы обсудили различные коды в главе под названием коды. Преобразователи, которые преобразуют один код в другой, называются преобразователями кода . Эти преобразователи кода в основном состоят из логических элементов.

пример

Конвертер двоичного кода в код Грея

Давайте реализуем конвертер, который преобразует 4-битный двоичный код WXYZ в его эквивалентный код Грея ABCD.

В следующей таблице показана таблица истинности 4-разрядного двоичного кода в преобразователь кода Грея.

Двоичный код WXYZ WXYZ Серый код ABCD
0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000

Из таблицы Truth мы можем записать логические функции для каждого выходного бита кода Грея, как показано ниже.

$$ A = \ sum m \ left (8,9,10,11,12,13,14,15 \ right) $$

$$ B = \ sum m \ left (4,5,6,7,8,9,10,11 \ right) $$

$$ C = \ sum m \ left (2,3,4,5,10,11,12,13 \ right) $$

$$ D = \ sum m \ left (1,2,5,6,9,10,13,14 \ right) $$

Упростим перечисленные выше функции, используя 4 переменные K-Maps.

На следующем рисунке показана 4-х переменная K-Map для упрощения булевой функции A.

Сгруппировав 8 смежных, мы получили $ A = W $.

На следующем рисунке показана 4-переменная K-Map для упрощения булевой функции B.

Есть две группы из 4 смежных. После группировки мы получим B как

$$ B = {W} ‘X + W {X}’ = W \ oplus X $$

Точно так же мы получим следующие логические функции для C & D после упрощения.

$$ C = {X} ‘Y + X {Y}’ = X \ oplus Y $$

$$ D = {Y} ‘Z + Y {Z}’ = Y \ oplus Z $$

На следующем рисунке показана принципиальная схема преобразователя 4-битного двоичного кода в код Грея.

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

Генератор четности

Существует два типа генераторов битов четности, основанных на типе генерируемого бита четности. Даже генератор четности генерирует бит четности. Аналогично, генератор нечетной четности генерирует бит нечетной четности.

Четный генератор четности

Теперь давайте реализуем четный генератор четности для 3-битного двоичного входа WXY. Он генерирует четный бит четности P. Если на входе присутствует нечетное число единиц, то четный бит четности P должен быть равен 1, чтобы результирующее слово содержало четное число единиц. Для других комбинаций ввода, даже четного бита, P должно быть ‘0’. В следующей таблице показана таблица истинности генератора четности.

Двоичный вход WXY Четный бит P
000 0
001 1
010 1
011 0
100 1
101 0
110 0
111 1

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

$$ P = {W} ‘{X}’ Y + {W} ‘Х {У}’ + W {X} {Y} ‘+ WXY $$

$ \ Rightarrow P = {W} ‘\ left ({X}’ Y + X {Y} ‘\ right) + W \ left ({X}’ {Y} ‘+ XY \ right) $

$ \ Rightarrow P = {W} ‘\ left (X \ oplus Y \ right) + W {\ left (X \ oplus Y \ right)}’ = W \ oplus X \ oplus Y $

На следующем рисунке показана принципиальная схема четного генератора четности.

Эта схема состоит из двух вентилей типа « исключающее ИЛИ» , каждый из которых имеет два входа. Первый вентиль ExclusiveOR имеет два входа W & X и выдает выход W ⊕ X. Этот выход задается как один вход второго вентиля Exclusive-OR. Другим входом этого второго логического элемента «Исключающее ИЛИ» является Y, который выдает выход W ⊕ X ⊕ Y.

Генератор нечетных четностей

Если на входе присутствует четное число единиц, то нечетный бит четности, P должен быть равен 1, чтобы результирующее слово содержало нечетное число единиц. Для других комбинаций ввода, нечетного бита четности, P должно быть ‘0’.

Выполните ту же процедуру генератора четности для реализации генератора нечетности. Принципиальная схема генератора нечетной четности показана на следующем рисунке.

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

Проверка четности

Существует два типа проверок четности в зависимости от типа проверяемой четности. Четная проверка четности проверяет ошибку в передаваемых данных, которые содержат биты сообщения наряду с четной четностью. Аналогичным образом, проверка нечетной четности проверяет ошибку в передаваемых данных, которая содержит биты сообщения наряду с нечетной четностью.

Четный паритет

Теперь давайте реализуем схему проверки четности. Предположим, что 3-битный двоичный вход передает WXY вместе с четным битом четности P. Таким образом, результирующее слово (данные) содержит 4 бита, которые будут получены в качестве входных данных проверки четности.

Он генерирует четный бит проверки четности, E. Этот бит будет нулевым, если полученные данные содержат четное количество единиц. Это означает, что в полученных данных нет ошибок. Этот бит проверки четности будет равен единице, если полученные данные содержат нечетное число единиц. Это означает, что в полученных данных произошла ошибка.

В следующей таблице показана таблица истинности проверки четности.

4-битные полученные данные WXYP Четный контроль четности, бит E
0000 0
0001 1
0010 1
0011 0
0100 1
0101 0
0110 0
0111 1
1000 1
1001 0
1010 0
1011 1
1100 0
1101 1
1110 1
1111 0

Из приведенной выше таблицы истинности мы можем заметить, что значение бита для проверки четности равно ‘1’, когда в полученных данных присутствует нечетное число единиц. Это означает, что булева функция бита проверки четности является нечетной функцией . Функция Exclusive-OR удовлетворяет этому условию. Следовательно, мы можем напрямую записать булеву функцию четного бита проверки четности как

$$ E = W \ oplus X \ oplus Y \ oplus P $$

На следующем рисунке показана принципиальная схема проверки четности.

Эта схема состоит из трех вентилей типа « исключающее ИЛИ» , каждый из которых имеет два входа. Ворота первого уровня выдают выходные данные $ W \ oplus X $ & $ Y \ oplus P $. Вентиль Exclusive-OR, который находится на втором уровне, производит вывод $ W \ oplus X \ oplus Y \ oplus P $

Проверка нечетности

Предположим, что 3-битный двоичный вход передает WXY вместе с нечетным битом четности P. Таким образом, результирующее слово (данные) содержит 4 бита, которые будут получены в качестве входных данных проверки нечетной четности.

Он генерирует нечетный бит проверки четности, E. Этот бит будет нулевым, если полученные данные содержат нечетное количество единиц. Это означает, что в полученных данных нет ошибок. Этот бит нечетной проверки на четность будет равен единице, если полученные данные содержат четное количество единиц. Это означает, что в полученных данных произошла ошибка.

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

Вышеприведенная принципиальная схема состоит из вентилей Ex-OR на первом уровне и вентиля Ex-NOR на втором уровне. Поскольку нечетная четность прямо противоположна четной четности, мы можем разместить инвертор на выходе проверки четности. В этом случае первый, второй и третий уровни содержат два вентиля Ex-OR, один вентиль Ex-OR и один инвертор соответственно.

Контроль четности

Это один из
стандартов, введенных IBM, в соответствии
с которым информация в банках памяти
хранится фрагментами по девять битов,
причем восемь из них (составляющих один
байт) предназначены собственно для
данных, а девятый является битом
четности
(parity).
Использование девятого бита позволяет
схемам управления памятью на аппаратном
уровне контролировать целостность
каждого байта данных. Если обнаруживается
ошибка, работа компьютера останавливается
и на экран выводится сообщение о
неисправности. Если вы работаете на
компьютере под управлением Windows или
OS/2, то при возникновении ошибки контроля
четности сообщение, возможно, не появится,
а просто произойдет блокировка системы.

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

Принцип работы проверки четности

При разработке
схемы контроля четности IBM установила,
что значение бита четности задается
таким, чтобы количество единиц во всех
девяти разрядах (восемь разрядов данных
и разряд четности) было нечетным.
Другими словами, когда байт (8 бит) данных
заносится в память, специальная схема
контроля четности (микросхема,
установленная на системной плате или
на плате памяти) подсчитывает количество
единиц в байте. Если оно четное, на выходе
микросхемы формируется сигнал логической
единицы, который сохраняется в
соответствующем разряде памяти как
девятый бит (бит четности). Количество
единиц во всех девяти разрядах при этом
становится нечетным. Если же количество
единиц в восьми разрядах исходных данных
нечетное, то бит четности равен 0 и сумма
двоичных цифр в девяти разрядах также
остается нечетной.

Рассмотрим
конкретный пример (имейте в виду, что
разряды в байте нумеруются начиная с
нуля).

Разряд данных: 0 1
2 3 4 5 6 7 Бит четности

Значение бита: 1
0 1 1 0 0 1 1 0

В данном случае
общее число единичных битов данных
нечетное (5), поэтому бит четности должен
быть равен нулю, чтобы количество единиц
во всех девяти разрядах было нечетным.

Рассмотрим еще
один пример.

Разряд данных: 0 1
2 3 4 5 6 7 Бит четности

Значение бита: 0
0 1 1 0 0 1 1 1

В этом примере
общее число единичных битов данных
четное (4), поэтому бит четности должен
быть равен единице, чтобы количество
единиц во всех девяти разрядах, как и в
предыдущем примере, было нечетным.

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

В компьютере IBM
PC: PARITY СНЕСК х

В компьютере IBM
XT: PARITY СНЕСК х yyyyy (z)

В компьютере IBM PC
и последних моделях XT: PARITY СНЕСК х yyyyy

Здесь x
может принимать
значения 1
(ошибка произошла
на системной плате) или 2
(ошибка произошла
в разъеме расширения). Символы yyyyy

это шестнадцатеричное число от 00000 до
FFFFF, указывающее адрес байта, в котором
произошла ошибка. Символ z
может принимать
значение S
(ошибка четности
в системном блоке) или e
(ошибка четности
в корпусе-расширителе). (IBM
разработала корпуса-расширители для
компьютеров PC и XT, чтобы увеличить
количество разъемов расширения.)

При обнаружении
ошибки схема контроля четности на
системной плате формирует немаскируемое
прерывание
(Non-maskable
Interrupt

NMI),
по которому основная работа прекращается
и инициируется специальная процедура,
записанная в BIOS. В результате ее выполнения
экран очищается и в левом верхнем углу
выводится сообщение об ошибке. Текст
сообщения зависит от типа компьютера.
В некоторых старых компьютерах IBM при
выполнении указанной процедуры
приостанавливается работа процессора,
компьютер блокируется и пользователю
приходится перезапускать его с помощью
кнопки сброса или выключать и через
некоторое время вновь включать питание.
При этом, естественно, теряется вся
несохраненная информация. (Немаскируемое
прерывание 
это системное предупреждение, которое
программы не могут проигнорировать.)

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

Определение бита четности

Бит четности — это бит со значением 0 или 1, который добавляется к блоку данных с целью обнаружения ошибок. Он придает данным четную или нечетную четность, которая используется для проверки целостности данных.

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

Бит четности для каждого пакета данных вычисляется перед передачей данных. Ниже приведены примеры того, как будет вычисляться бит четности с использованием настроек четности и нечетности.

Нечетная четность:

  • Начальное значение: 1010101 (четыре единицы)
  • Добавлен бит четности: 1
  • Переданное значение: 10101011
  • Результат: нечетная четность (пять единиц)
Четность:

  • Начальное значение: 1010101 (четыре единицы)
  • Добавлен бит четности: 0
  • Передаваемое значение: 10101010
  • Результат: четность (четыре единицы)

Значение бита четности зависит от начальной четности данных.Например, двоичное значение 10000000 имеет нечетную четность. Следовательно, 0 будет добавлен, чтобы сохранить четность нечетной, и 1 будет добавлен, чтобы получить значение четной четности.

Хотя проверка четности является полезным способом проверки данных, это не надежный метод. Например, значения 1010 и 1001 имеют одинаковую четность. Следовательно, если значение 1010 передано и получено 1001, ошибка не будет обнаружена. Это означает, что проверки четности не являются 100% надежными при проверке данных. Тем не менее, маловероятно, что более одного бита будет неправильным в небольшом пакете данных.Пока изменен только один бит, возникнет ошибка. Следовательно, проверки четности наиболее надежны при использовании пакетов небольшого размера.

Обновлено: Ma

Что такое бит четности?

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

Биты четности используются как форма проверки ошибок во время
передача информации. Когда старые модемы передаются
данные по сети или устройству связи, данные были закодированы
в ряд единиц и нулей, называемых битами (современные модемы
отправлять информацию пакетами и разными способами проверять на наличие ошибок,
поэтому бит четности не нужен).Один бит может описать только два
возможные состояния: 0 (выключено) или 1 (включено). Таким образом, для
опишите букву или цифру. Всего используется семь битов
описать набор символов ASCII, который включает
буквы и цифры, составляющие этот документ.

Буква «A», например, имеет код ASCII 65, который в двоичном формате
1000001. Обратите внимание, что каждая двоичная цифра соответствует степени двойки,
и 65, что составляет два в шестой степени плюс два в нулевой степени,
имеет единицы только в шестом и нулевом столбцах двоичного
представление.Буква C с кодовым значением 67 имеет двоичную
последовательность 1000011.

Поскольку шум или электрические помехи иногда могут мешать работе
передача данных, полезно иметь способ легко обнаруживать
ошибки в информации при обмене. Один из способов сделать это —
добавить восьмой бит к передаваемым символам, это называется четностью
немного. Бит четности выбирается таким, чтобы все правильно передавалось
у символов будет четное или нечетное количество единиц. Таким образом, если
ноль были помещены в начало кода для буквы A, в результате чего
01000001, единица будет помещена перед кодом для C, что даст 11000011.

Показанные здесь префиксы создают двоичные коды с четным числом
единицы (и нули), поэтому добавленный бит называется битом четности.
Также можно выбрать ведущие единицы и нули, чтобы всегда получать нечетные
числа единиц и нулей, и эта схема называется нечетной четностью.
Знакомые настройки в коммуникационных программах — E7, в котором используется один
бит четности и семь битов данных, и N8, что указывает на отсутствие четности
бит и использование всех восьми бит для передачи данных.

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

Что такое бит четности?

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

Человек, держащий компьютер

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

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

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

определение бита четности и синонимы бита четности (английский)

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

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

Существует два варианта битов четности: бит четности и бит нечетности . При использовании четности бит четности устанавливается в 1, если количество единиц в данном наборе битов (не включая бит четности) нечетное, что делает количество единиц во всем наборе битов (включая бит четности) четный. Если количество единиц в данном наборе битов уже четное, оно устанавливается в 0. При использовании нечетной четности бит четности устанавливается в 1, если количество единиц в данном наборе битов (не включая четность bit) является четным, при этом количество единиц во всем наборе битов (включая бит четности) остается нечетным.И когда количество установленных битов уже является нечетным, бит нечетной четности устанавливается в 0. Другими словами, бит четности будет установлен в «1», если количество 1s + 1 является четным, и бит нечетной четности будет установлен в «1», если количество единиц +1 нечетное.

Проверка на четность — это особый случай контроля с помощью циклического избыточного кода (CRC), когда 1-битный CRC генерируется полиномом x +1.

Если бит четности присутствует, но не используется, он может называться , метка четности (когда бит четности всегда равен 1) или , проверка четности пространства (бит всегда равен 0).

Четность

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

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

Если нечетное количество битов (включая бит четности) передается неправильно, бит четности будет неправильным и, таким образом, указывает на ошибку при передаче. 1 = 0
B сообщает о правильной передаче, хотя на самом деле неверно.

B, как и ожидалось, наблюдает четность, тем самым не обнаруживая двух битовых ошибок.

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

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

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

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

RAID

Данные четности используются некоторыми уровнями 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, показанном выше, и выдают значение, которое затем сохраняется на выделенном диске четности.

История

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

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

С другой стороны, Сеймур Крей, ведущий разработчик суперкомпьютеров, презирал проекты паритета. Он считал, что это плохо спроектировано — если вы спроектируете свои пути передачи данных надежными, вам не придется тратить ресурсы на паритетных началах. Его знаменитая цитата по этому поводу (примерно 1963 г.) была «Паритет для фермеров» (после употребления термина «паритет» в Новом курсе).После того, как он позже включил биты четности в CDC 7600, Крей, по общему мнению, сказал: «Я узнал, что многие фермеры покупают компьютеры».

См. Также

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

Синонимы битов четности, антонимы битов четности

Таким образом, закодированные оценочные данные также включают три части, которые состоят из битового сигнала данных [x.sub.i, k], битового сигнала четности [x.sub.p1, k] кода 1 и битового сигнала четности [x.sub.p2, k] кода 2. В вычислениях одним из простейших методов обнаружения ошибок является включение бита четности.Бит четности — это дополнительный бит, который добавляется к последовательности битов, используемых для определения того, произошла ли ошибка. [Математическое выражение не воспроизводится] и r [2.sub.t] являются де-отображенными мягкими битами, соответствующими биполярному эквивалент чередующихся систематических битов, [математическое выражение не воспроизводится] и битов второй четности, [P.sub.2t] соответственно. Существует два способа представления LDPC для приложений DSC: (1) по (N, M), где N (вход) — количество информационных битов, а M (выход) — количество синдромов; то есть, только синдромы передаются (2) посредством (K, N — K), где K (вход) — количество информационных битов, а N — K (выход) — количество битов четности; то есть передаются только биты четности.После того, как мы сгенерировали биты четности, у нас есть часть модуляции канала: систематически кодированные выходные биты канала, биты четности, переданные из связанного компонентного кодера, и информация от другого компонентного декодера о вероятных значениях рассматриваемых битов. количество битов изменяется во время передачи данных, например, при сохранении информации на CD или DVD, или в файле, тогда бит четности будет неправильным и, таким образом, укажет, что произошла ошибка.Биты четности добавляются для обнаружения некорректных битов, которые вводятся в процессе передачи. Схема обнаружения ошибок, которая генерирует биты четности путем полиномиального кодирования цифровых сигналов, добавляет эти биты четности к цифровому сигналу и использует алгоритмы декодирования, которые обнаруживают ошибки в принятый цифровой сигнал: скорость передачи данных, биты данных и четности, дуплекс, управление потоком и эмуляция терминала — это лишь некоторые из параметров, которые должны быть правильно согласованы. Эти каналы связи имеют ширину 32 бита с двумя дополнительными битами четности.Работая на частоте 8 МГц, каждая ссылка передает данные со скоростью 32 МБ в секунду. Турбокодер имеет три выхода: u — последовательность информационных битов и [p.sub.1], [p.sub.2] — последовательности бит четности. Для обнаружения ошибок, в отличие от [2], где использовался «джинновый» циклический избыточный контроль (CRC), мы использовали 16-битный код CRC. Биты четности генерируются для квантованного случайного сигнала X и передаются на сторону декодера. Например, давайте рассмотрим 32 бита как исходный вход, тогда после кодирования с помощью M-RSE-IDE (39, 32) расширенный код Хэмминга становится 39 и 195 после пятикратного дублирования с битом четности.Таким образом, QMEC представляет собой схему кодирования (195, 32) для данных шириной 32 бита. Например, RAID 4 и 5 делают это, распределяя данные по нескольким устройствам, а затем вычисляя четность каждого бита в каждой соответствующей полосе данных (по сути, независимо от того, сумма битов четная или нечетная) и записывает бит четности в резервное устройство.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *