Как найти бит четности

From Wikipedia, the free encyclopedia

A parity bit, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes), although they can also be applied separately to an entire message string of bits.

The parity bit ensures that the total number of 1-bits in the string is even or odd.^[1] Accordingly, there are two variants of parity bits: even parity bit and odd parity bit. In the case of even parity, for a given set of bits, the bits whose value is 1 are counted. If that count is odd, the parity bit value is set to 1, making the total count of occurrences of 1s in the whole set (including the parity bit) an even number. If the count of 1s in a given set of bits is already even, the parity bit’s value is 0. In the case of odd parity, the coding is reversed. For a given set of bits, if the count of bits with a value of 1 is even, the parity bit value is set to 1 making the total count of 1s in the whole set (including the parity bit) an odd number. If the count of bits with a value of 1 is odd, the count is already odd so the parity bit’s value is 0. Even parity is a special case of a cyclic redundancy check (CRC), where the 1-bit CRC is generated by the polynomial x+1.

Parity[edit]

In mathematics parity can refer to the evenness or oddness of an integer, which, when written in its binary form, can be determined just by examining only its least significant bit.

In information technology parity refers to the evenness or oddness, given any set of binary digits, of the number of those bits with value one. Because parity is determined by the state of every one of the bits, this property of parity—being dependent upon all the bits and changing its value from even to odd parity if any one bit changes—allows for its use in error detection and correction schemes.

In telecommunications the parity referred to by some protocols is for error-detection. The transmission medium is preset, at both end points, to agree on either odd parity or even parity. For each string of bits ready to transmit (data packet) the sender calculates its parity bit, zero or one, to make it conform to the agreed parity, even or odd. The receiver of that packet first checks that the parity of the packet as a whole is in accordance with the preset agreement, then, if there was a parity error in that packet, requests a re-transmission of that packet.

In computer science the parity stripe or parity disk in a RAID provides error-correction. Parity bits are written at the rate of one parity bit per n bits, where n is the number of disks in the array. When a read error occurs, each bit in the error region is recalculated from its set of n bits. In this way, using one parity bit creates «redundancy» for a region from the size of one bit to the size of one disk. See § Redundant Array of Independent Disks below.

In electronics, transcoding data with parity can be very efficient, as XOR gates output what is equivalent to a check bit that creates an even parity, and XOR logic design easily scales to any number of inputs. XOR and AND structures comprise the bulk of most integrated circuitry.

Error detection[edit]

If an odd number of bits (including the parity bit) are transmitted incorrectly, the parity bit will be incorrect, thus indicating that a parity error occurred in the transmission. The parity bit is only suitable for detecting errors; it cannot correct any errors, as there is no way to determine which particular bit is corrupted. The data must be discarded entirely, and re-transmitted from scratch. On a noisy transmission medium, successful transmission can therefore take a long time, or even never occur. However, parity has the advantage that it uses only a single bit and requires only a number of XOR gates to generate. See Hamming code for an example of an error-correcting code.

Parity bit checking is used occasionally for transmitting ASCII characters, which have 7 bits, leaving the 8th bit as a parity bit.

For example, the parity bit can be computed as follows. Assume Alice and Bob are communicating and Alice wants to send Bob the simple 4-bit message 1001.

This mechanism enables the detection of single bit errors, because if one bit gets flipped due to line noise, there will be an incorrect number of ones in the received data. In the two examples above, Bob’s calculated parity value matches the parity bit in its received value, indicating there are no single bit errors. Consider the following example with a transmission error in the second bit using XOR:

There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd number of bit errors. If an even number of bits have errors, the parity bit records the correct number of ones, even though the data is corrupt. (See also Error detection and correction.) Consider the same example as before with an even number of corrupted bits:

Bob observes even parity, as expected, thereby failing to catch the two bit errors.

Usage[edit]

Because of its simplicity, parity is used in many hardware applications where an operation can be repeated in case of difficulty, or where simply detecting the error is helpful. For example, the SCSI and PCI buses use parity to detect transmission errors, and many microprocessor instruction caches include parity protection. Because the I-cache data is just a copy of main memory, it can be disregarded and re-fetched if it is found to be corrupted.

In serial data transmission, a common format is 7 data bits, an even parity bit, and one or two stop bits. This format accommodates all the 7-bit ASCII characters in an 8-bit byte. Other formats are possible; 8 bits of data plus a parity bit can convey all 8-bit byte values.

In serial communication contexts, parity is usually generated and checked by interface hardware (e.g., a UART) and, on reception, the result made available to a processor such as the CPU (and so too, for instance, the operating system) via a status bit in a hardware register in the interface hardware. Recovery from the error is usually done by retransmitting the data, the details of which are usually handled by software (e.g., the operating system I/O routines).

When the total number of transmitted bits, including the parity bit, is even, odd parity has the advantage that the all-zeros and all-ones patterns are both detected as errors. If the total number of bits is odd, only one of the patterns is detected as an error, and the choice can be made based on which is expected to be the more common error.

RAID array[edit]

Parity data is used by RAID arrays (redundant array of independent/inexpensive disks) to achieve redundancy. If a drive in the array fails, remaining data on the other drives can be combined with the parity data (using the Boolean XOR function) to reconstruct the missing data.

For example, suppose two drives in a three-drive RAID 5 array contained the following data:

To calculate parity data for the two drives, an XOR is performed on their data:

The resulting parity data, 10111001, is then stored on Drive 3.

Should any of the three drives fail, the contents of the failed drive can be reconstructed on a replacement drive by subjecting the data from the remaining drives to the same XOR operation. If Drive 2 were to fail, its data could be rebuilt using the XOR results of the contents of the two remaining drives, Drive 1 and Drive 3:

as follows:

The result of that XOR calculation yields Drive 2’s contents. 11010100 is then stored on Drive 2, fully repairing the array.

XOR logic is also equivalent to even parity (because a XOR b XOR c XOR … may be treated as XOR(a,b,c,…) which is an n-ary operator which is true if and only if an odd number of arguments are true). So the same XOR concept above applies similarly to larger RAID arrays with parity, using any number of disks. In the case of a RAID 3 array of 12 drives, 11 drives participate in the XOR calculation shown above and yield a value that is then stored on the dedicated parity drive.

Extensions and variations on the parity bit mechanism «double,» «dual,» or «diagonal» parity, are used in RAID-DP.

History[edit]

A parity track was present on the first magnetic-tape data storage in 1951. Parity in this form, applied across multiple parallel signals, is known as a transverse redundancy check. This can be combined with parity computed over multiple bits sent on a single signal, a longitudinal redundancy check. In a parallel bus, there is one longitudinal redundancy check bit per parallel signal.

Parity was also used on at least some paper-tape (punched tape) data entry systems (which preceded magnetic-tape systems). On the systems sold by British company ICL (formerly ICT) the 1-inch-wide (25 mm) paper tape had 8 hole positions running across it, with the 8th being for parity. 7 positions were used for the data, e.g., 7-bit ASCII. The 8th position had a hole punched in it depending on the number of data holes punched.

See also[edit]

• BIP-8
• Parity function
• Single-event upset
• 8-N-1
• Check digit

References[edit]

External links[edit]

• Different methods of generating the parity bit, among other bit operations

Бит четности, также известный как контрольный бит, является единственным битом, который может быть добавлен к двоичной строке. Он имеет значение 1 или 0, чтобы сделать общее число 1- битов четным («четная четность») или нечетным («нечетная четность»).

Цель бита четности — предоставить простой способ проверки на наличие ошибок позже. Когда данные хранятся или передаются в электронном виде, нередки случаи, когда биты «переворачиваются» — меняются с 1 на 0 или наоборот. Проверка четности может помочь обнаружить некоторые из этих ошибок. Например, чтобы проверить двоичную последовательность, которая имеет четную четность, можно подсчитать общее количество единиц. Если число единиц не является четным, вероятно, произошла ошибка.

Недостатком этого типа проверки ошибок является то, что он может обнаруживать только нечетное количество ошибок в последовательности. Если четное количество бит перевернуто, проверка на четность не поймает его.

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

1. Данные 10101 получают четный бит четности 1, что приводит к битовой последовательности 101011 .
2. Эти данные передаются на другой компьютер. При передаче данные повреждены, и компьютер получает неверные данные 100011 .
3. Принимающий компьютер вычисляет соотношение: 1 + 0 + 0 + 0 + 1 + 1 = 3 . Затем он выполняет 3 по модулю 2 (остаток от 3 делится на 2), ожидая результата 0, который будет указывать, что число является четным.
4. Вместо этого он получает результат 3 по модулю 2 = 1, указывающий, что число нечетное. Поскольку он ищет числа с четной четностью, он просит исходный компьютер снова отправить данные.
5. На этот раз данные поступают без ошибок: 101011 . Принимающий компьютер вычисляет 1 + 0 + 1 + 0 + 1 + 1 = 4 .
6. 4 по модулю 2 = 0, что указывает на четность. Бит четности удаляется с конца последовательности, и данные 10101 принимаются.

Проверить биты, Условия аппаратного обеспечения, Отметить четность, Проверка четности, Пространственная четность

Бит четности является параметром со значением 0 или 1 , который используется в способе обнаружения ошибок передачи , в которой 0 или 1 добавляется к каждой группе 7-8 битов (байт). Цель состоит в том, чтобы каждый байт всегда имел нечетное общее количество «1» или четное общее количество «1» в соответствии с установленной четностью.

Четность — это метод обнаружения ошибок, используемый в асинхронной связи. Он используется для проверки целостности каждого байта в передаваемом потоке. Например, если установлена ​​нечетная четность, любой байт, полученный из передачи с общим числом «1», который является четным, должен содержать ошибку.

Источник: pixabay.com

Используются два типа проверки на четность: проверка на четность, при которой бит четности 1 добавляется, если в предыдущем байте имеется нечетное общее количество битов «1», и проверка на четность, когда выполняется обратное. С помощью этого метода вы сможете узнать только то, что произошла ошибка, но вы не узнаете, где произошла ошибка.

Для чего нужен бит четности?

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

Следовательно, необходимо реализовать некоторый метод, чтобы проверить, ошибочны ли полученные коды или байты.

Однако как получатель может узнать, ошибочен ли полученный код? Получатель не может узнать код до его получения.

Например, предположим, что отправитель передает код 01100110, но после прохождения через зашумленную линию получатель получает код 00100110. Получатель не будет знать, что он получил код с ошибкой во втором бите.

Получатель не может знать, что сообщение содержит ошибку в первом бите, потому что это будет означать, что получатель уже знает сообщение от передатчика до передачи.

Контроль ошибок

Проблема, с которой приемник может проверить наличие ошибки, может быть решена с помощью кодирования с контролем ошибок.

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

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

Бит четности для каждого байта устанавливается так, чтобы все байты имели нечетное число или четное число битов «1».

пример

Предположим, что два диска обмениваются данными с проверкой четности, которая является наиболее распространенной формой проверки четности.

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

Приемник проверяет каждый байт, чтобы убедиться, что он имеет четное количество битов «1». Если в байте обнаружено нечетное количество битов «1», приемник будет знать, что во время передачи произошла ошибка.

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

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

Проверка четности — самый простой метод обнаружения ошибок связи.

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

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

Как это работает?

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

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

Метод четной четности

Этот метод указывает, что добавляемый бит четности должен быть таким, чтобы общая сумма «1» в окончательном коде была четной. Например:

Следовательно, для первого 7-битного кода: 0010010 с четным количеством «1» (2) переданный 8-битный код будет: 00100100 с четным количеством «1» (2).

Для 7-битного кода 1110110 с нечетным количеством «1» (5) переданный 8-битный код будет 11101101 с четным количеством «1» (6).

После того, как получатель получит 8 битов, он проверит количество «1» в полученном коде, если количество «1» четное, это означает, что ошибки нет, если количество нечетное, это означает, что ошибка.

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

В случае ошибки приемник предупредит передатчик, чтобы он отправил код еще раз.

Не безошибочный

Однако у этих методов контроля четности есть недостаток: если код 1110110 преобразуется шумом линии в 11111001, вызывая 2-битную ошибку, то этот метод не может обнаружить, что ошибка произошла.

Четность хороша при обнаружении ошибок и всегда обнаруживает любое нечетное количество ошибок в полученном байте. Однако при четном количестве ошибок средство проверки четности не сможет найти ошибку.

Ссылки

1. Ванги Бил (2019). Проверка четности. Webopedia. Взято с: webopedia.com.
2. Группа исследований электроники (2019). Четность символов. Взято с: erg.abdn.ac.uk.
3. Словарь (2019) .. Бит паритета. Взято с сайта vocabulary.com.
4. Ангмс (2013). Самый простой код контроля ошибок — Parity Bit. Взято с сайта angms.science.
5. Кристенсон, (2011). Определение бита четности. Techterms. Взято с: techterms.com.

Бит четности

Полезное

Время на прочтение
5 мин

Количество просмотров 121K

Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т.п. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали.

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

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

По сути, кодирование — это добавление к исходной информации дополнительной, проверочной, информации. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.
Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле:

k/(i+k), где
k — количество проверочных бит,
i — количество информационных бит.

Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).

Код с проверкой на четность

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

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

и и декодера

Пример:

Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10110 (изменился второй бит)
Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка.

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

Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10010 (изменились 2 и 3 биты)
В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку.

Так как около 90% всех нерегулярных ошибок происходит именно с одиночным разрядом, проверки четности бывает достаточно для большинства ситуаций.

Код Хэмминга

Как говорилось в предыдущей части, очень много для помехоустойчивого кодирования сделал Ричард Хэмминг. В частности, он разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит. Для каждого числа проверочных символов используется специальная маркировка вида (k, i), где k — количество символов в сообщении, i — количество информационных символов в сообщении. Например, существуют коды (7, 4), (15, 11), (31, 26). Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой подпоследовательности данных. Рассмотрим сразу на примере, когда количество информационных бит i в блоке равно 4 — это код (7,4), количество проверочных символов равно 3. Классически, эти символы располагаются на позициях, равных степеням двойки в порядке возрастания:

первый проверочный бит на 2⁰ = 1;
второй проверочный бит на 2¹ = 2;
третий проверочный бит на 2² = 4;

но можно и разместить их в конце передаваемого блока данных (но тогда формула для их расчета будет другая).
Теперь рассчитаем эти проверочные символы:

r1 = i1 + i2 + i4
r2 = i1 + i3 + i4
r3 = i2 + i3 + i4

Итак, в закодированном сообщении у нас получится следующее:

r1 r2 i1 r3 i2 i3 i4

В принципе, работа этого алгоритма разобрана очень детально в статье Код Хэмминга. Пример работы алгоритма, так что особо подробно описывать в этой статье не вижу смысла. Вместо этого приведу структурную схему кодера:

и декодера

(может быть, довольно запутано, но лучше начертить не получилось)

e0,e1,e2 опрделяются как функции, зависящие от принятых декодером бит k1 — k7:

e0 = k1 + k3 + k5 + k7 mod 2
e1 = k2 + k3 + k6 + k7 mod 2
e2 = k4 + k5 + k6 + k7 mod 2

Набор этих значений e2e1e0 есть двоичная запись позиции, где произошла ошибка при передаче данных. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 000), то исправляет ошибку.

Коды-произведения

В канале связи кроме одиночных ошибок, вызванных шумами, часто встречаются пакетные ошибки, вызванные импульсными помехами, замираниями или выпадениями (при цифровой видеозаписи). При этом пораженными оказываются сотни, а то и тысячи бит информации подряд. Ясно, что ни один помехоустойчивый код не сможет справиться с такой ошибкой. Для возможности борьбы с такими ошибками используются коды-произведения. Принцип действия такого кода изображён на рисунке:

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

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

При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода. В таком порядке информация передается по каналу связи или записывается куда-нибудь. Условимся, что и внутренний, и внешний коды – коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове (количество «кубиков» на рисунке не критично — это просто схема). На приемном конце расположен точно такой же массив памяти (буфер), в который информация заносится построчно, а выводится по столбцам. При возникновении пакетной ошибки (крестики на рисунке в третьей и четвертой строках), она малыми порциями распределяется в кодовых словах внешнего кода и может быть исправлена.

Назначение внешнего кода понятно – исправление пакетных ошибок. Зачем же нужен внутренний код? На рисунке, кроме пакетной, показана одиночная ошибка (четвертый столбец, верхняя строка). В кодовом слове, расположенном в четвертом столбце — две ошибки, и они не могут быть исправлены, т.к. внешний код рассчитан на исправление одной ошибки. Для выхода из этой ситуации как раз и нужен внутренний код, который исправит эту одиночную ошибку. Принимаемые данные сначала проходят внутренний декодер, где исправляются одиночные ошибки, затем записываются в буфер построчно, выводятся по столбцам и подаются на внешний декодер, где происходит исправление пакетной ошибки.

Использование кодов-произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности.

P.S.: Плотно занимался этой темой 3 года назад, когда писал дипломный проект, возможно что-то упустил. Все исправления, замечания, пожелания — пожалуйста через личные сообщения