Что такое бит четности?
Бит четности, также известный как контрольный бит, является единственным битом, который может быть добавлен к двоичной строке. Он имеет значение 1 или 0, чтобы сделать общее число 1- битов четным («четная четность») или нечетным («нечетная четность»).
Цель бита четности — предоставить простой способ проверки на наличие ошибок позже. Когда данные хранятся или передаются в электронном виде, нередки случаи, когда биты «переворачиваются» — меняются с 1 на 0 или наоборот. Проверка четности может помочь обнаружить некоторые из этих ошибок. Например, чтобы проверить двоичную последовательность, которая имеет четную четность, можно подсчитать общее количество единиц. Если число единиц не является четным, вероятно, произошла ошибка.
Недостатком этого типа проверки ошибок является то, что он может обнаруживать только нечетное количество ошибок в последовательности. Если четное количество бит перевернуто, проверка на четность не поймает его.
Пример проверки на четность
- Данные 10101 получают четный бит четности1, что приводит к битовой последовательности 101011 .
- Эти данные передаются на другой компьютер. При передаче данные повреждены, и компьютер получает неверные данные 100011 .
- Принимающий компьютер вычисляет соотношение: 1 + 0 + 0 + 0 + 1 + 1 = 3 . Затем он выполняет 3 по модулю 2 (остаток от 3 делится на 2), ожидая результата 0, который будет указывать, что число является четным.
- Вместо этого он получает результат 3 по модулю 2 = 1, указывающий, что число нечетное. Поскольку он ищет числа с четной четностью, он просит исходный компьютер снова отправить данные.
- На этот раз данные поступают без ошибок: 101011 . Принимающий компьютер вычисляет 1 + 0 + 1 + 0 + 1 + 1 = 4 .
- 4 по модулю 2 = 0, что указывает на четность. Бит четности удаляется с конца последовательности, и данные 10101 принимаются.
Проверить биты, Условия аппаратного обеспечения, Отметить четность, Проверка четности, Пространственная четность
Бит четности
В вычислительной технике и сетях передачи данных би́том чётности называют контрольный бит, принимающий значения ‘0’ или ‘1’ и служащий для проверки общей чётности двоичного числа (чётности количества единичных битов в числе).
Содержание
Примеры
Бит чётности или контрольный разряд формируется при выполнении операции «Исключаюшее-ИЛИ» поразрядно. Рассмотрим схему, использующую девятибитные кодовые слова, состоящие из восьми бит данных, за которыми следует бит чётности.
- Число 10111101 содержит 6 ‘1’ битов. Бит чётности будет 0, получаем кодовое слово 101111010.
- Число 01110011 содержит 5 ‘1’ битов. Бит чётности будет 1, получаем кодовое слово 011100111.
- Число 00000000 не содержит ‘1’ битов. Бит чётности будет 0, получаем кодовое слово 000000000.
Пустой или несуществующий поток битов также имеет ноль единичных битов, поэтому бит чётности будет 0.
Применение
В последовательной передаче данных часто используется формат 7 бит данных, бит чётности, один или два стоповых бита. Такой формат аккуратно размещает все 7-битные UART). Признак ошибки становится доступен процессору (и ОС) через статусный регистр оборудования. Восстановление ошибок обычно производится повторной передачей данных, подробности которого обрабатываются программным обеспечением (например, функциями ввода/вывода операционной системы)
Полиномы CRC и бит чётности
Контроль по чётности фактически является специальным случаем проверки избыточности циклической суммы с полиномом x+1.
См. также
Литература
- Генри С. Уоррен, мл.Глава 5. Подсчет битов // Алгоритмические трюки для программистов = Hacker’s Delight. — М.: «Вильямс», 2007. — С. 288. — ISBN 0-201-91465-4
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое «Бит четности» в других словарях:
бит четности — Дополнительный бит, добавляемый в группу для того, чтобы общее число единиц в группе было четным или нечетным (в зависимости от протокола). [http://www.lexikon.ru/dict/net/index.html] Тематики сети вычислительные EN parity Bit … Справочник технического переводчика
бит четности — lyginumo bitas statusas T sritis automatika atitikmenys: angl. parity bit; parity check bit vok. Paritätsbit, n; Paritätskontrollbit, n rus. бит четности, m; контрольный двоичный разряд четности, m; проверочный двоичный разряд четности, m pranc.… … Automatikos terminų žodynas
бит четности (шины) — Линия (сигнал), по которой передается бит четности соответствующей шины системы, если в ней используется четность. [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в… … Справочник технического переводчика
бит контроля на четность — бит четности контрольный бит Контрольный бит, добавляемый к данным для контроля их верности таким образом, чтобы сумма двоичных единиц, составляющих данное, включая и единицу контрольного бита, всегда была четной (либо всегда нечетной). [Домарев… … Справочник технического переводчика
контрольный двоичный разряд четности — lyginumo bitas statusas T sritis automatika atitikmenys: angl. parity bit; parity check bit vok. Paritätsbit, n; Paritätskontrollbit, n rus. бит четности, m; контрольный двоичный разряд четности, m; проверочный двоичный разряд четности, m pranc.… … Automatikos terminų žodynas
проверочный двоичный разряд четности — lyginumo bitas statusas T sritis automatika atitikmenys: angl. parity bit; parity check bit vok. Paritätsbit, n; Paritätskontrollbit, n rus. бит четности, m; контрольный двоичный разряд четности, m; проверочный двоичный разряд четности, m pranc.… … Automatikos terminų žodynas
двоичный разряд четности — бит проверки на четность разряд контроля четности — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы бит проверки на четностьразряд контроля четности … Справочник технического переводчика
Контроль четности — В вычислительной технике и сетях передачи данных битом чётности называют контрольный бит, принимающий значения 0 или 1 и служащий для проверки общей чётности двоичного числа (чётности количества единичных битов в числе). Содержание 1 Примеры 2… … Википедия
генератор битов четности — генератор паритета Логическая схема, выполненная в виде сумматора по модулю 2, который генерирует “ложный” проверочный бит, добавляемый к исходным данным. Используется в системах, в которых протоколом предусматривается процедура проверки четности … Справочник технического переводчика
Виганд (интерфейс) — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
ЕГЭ – 2021, задание 5, часть 3. Элементы теории алгоритмов: бит четности и др. Практика
При решении заданий 5 ЕГЭ-2021, часть 2 рассматриваются несколько типов задач на алгоритмизацию. При этом нужно учесть,, что алгоритм — это четкий порядок действий, подлежащих выполнению, то есть при решении задач на алгоритмизацию следует внимательно читать условие задачи и точно, аккуратно и без спешки (в этом залог быстрого и точного решения задачи!) выполнять описанные в нем действия.
При этом обратим внимание, что одни и те же действия в разных задачах могут описываться разными условиями, например:
— "складываются все цифры двоичной записи числа" или "считается количество единиц в двоичной записи числа": поскольку сумма цифр двоичной записи числа равна количеству единиц в двоичном числе, то при решении задач быстрее и проще посчитать количество единиц в записи и получить результат для данного условия;
— "остаток от деления суммы (количества единиц) на два", "бит чётности", "четное число или нет" — в результате проверки всех этих условий проверяется остаток от деления числа на 2: по умолчанию это ноль для четного числа и единица — для нечетного. Но в условии задач этот результат может меняться, поэтому следует точно выполнять действия, заданные в алгоритме!
Следует также внимательно смотреть, какое из чисел – N или R – следует искать в данной задаче.
Пример 1 (ДЕМО – 2021)
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Строится двоичная запись числа N.
К этой записи дописываются справа ещё два разряда по следующему правилу:
складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 77) — число 78:
78 = 2 6 + 2 3 + 2 2 + 2 1 = 10011102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма
N = 100112 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – верно, так как количество единиц в числе N равно трем;
0 – верно, так как теперь в полученном результате уже 4 единицы.
Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 100112 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 100112 = 2 0 + 2 1 + 0 2 + 0 3 + 2 4 = 1 + 2 + 16 = 19.
Примечание: для быстрого и точного перевода числа из двоичной системы в десятичную я записываю степени с конца, чтобы не делать лишних действий и не допускать возможных ошибок.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Строится двоичная запись числа N.
К этой записи дописываются справа ещё два разряда по следующему правилу:
в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно;
к этой записи справа дописывается остаток от деления количества единиц на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 31 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 31) — число 32:
32 = 2 5 = 1000002
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 10002 и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – верно, так как количество единиц в числе N нечетно;
0 – неверно, так как остаток от деления количества единиц на 2 равен 1.
Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число искомое число R = 33 и проверяем его.
1. Переведем число 33 в двоичную систему счисления: 33 = 2 5 = 1000012
2. Для проверки, может ли данное число R быть результатом работы алгоритма,
отделяем от него справа две последние цифры (которые являются результатом
выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 10002
и цифры 01, которые получены в результате двух следующих шагов выполнения
0 – верно, так как количество единиц в числе N нечетно;
1 – верно, так как результат от деления количества единиц на 2 равен 1.
Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 110002 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 1100112 = 2 0 + 2 1 + 0 2 + 0 3 + 2 4 = 1 + 2 + 16 = 19.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Строится двоичная запись числа N.
К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 96. В ответе это число запишите в десятичной системе.
Решение 1 – короткое:
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) — число 97:
97 = 2 6 + 2 5 + 2 0 = 11000012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и получаем, что для числа N = 110002 последними цифрами должны быть 00, но тогда число R = 11000002 = 96 не удовлетворяет условию задачи.
Числа с двумя последними цифрами 01 (97 = 11000012), 10 (98 = 11000102) и 11 (99=11000112) также не подходят. Это значит, что нужно увеличивать само число N, тогда получаем N = 110012 и в результате работы алгоритма получим R = 11001102 = 102.
Тогда искомое число N = 110012 = 25
Решение 2 – длинное (обычное):
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) — число 97:
97 = 2 6 + 2 5 + 2 0 = 11000012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – верно, так как количество единиц в числе N четно;
1 –неверно, так как количество единиц в числе N четно.
Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число R = 98 и проверяем его.
Переведем в двоичную систему число 98:
98 = 2 6 + 2 5 + 2 1 = 11000102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – неверно, так как количество единиц в числе N четно;
0 – неверно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 99 и проверяем его.
Переведем в двоичную систему число 99:
= 2 6 + 2 5 + 2 1 + 2 0 = 11000112
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 11, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – неверно, так как количество единиц в числе N четно
1–верно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 100 и проверяем его.
Переведем в двоичную систему число100:
= 2 6 + 2 5 + 2 2 = 11001002
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – неверно, так как количество единиц в числе N нечетно
0 – неверно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 101 и проверяем его.
Переведем в двоичную систему число 101:
= 2 6 + 2 5 + 2 2 + 2 0 = 11001012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – неверно, так как количество единиц в числе N нечетно
1 – верно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 102 и проверяем его.
Переведем в двоичную систему число 102:
= 2 6 + 2 5 + 2 2 + 2 1 = 11001102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – верно, так как количество единиц в числе N нечетно
0 – верно, так как количество единиц в числе N четно.
Так как оба условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 100112 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 110012 = 2 0 + 0 1 + 0 2 + 2 3 + 2 4 = 1 + 8 + 16 = 25.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Складываются все цифры двоичной записи числа. Если сумма четная, то в конец числа (справа) дописывается 1, а если нечетная, то дописывается 0. Например, запись числа 10 преобразуется в запись 100;
3) К полученному результату применяется еще раз пункт 2 этого алгоритма.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите количество чисел R, которые могут быть получены в результате работы этого алгоритма, и лежат в диапазоне 16 ≤ R ≤ 32.
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону.
Переведем в двоичную систему первое число, удовлетворяющее условию задачи границы диапазона возможных чисел R:
Rmin = 2 4 = 100002
Rmax = 2 5 = 1000002
Соответственно получаем Nmin = 2 2 = 1002 и Nmax = 2 3 = 10002.
Далее берем все возможные числа N внутри данного диапазона (возможны только три варианта – 101, 110 и 111) и проверяем результат работы алгоритма над ними:
при N = 1012 возможно только одно R = 101102 = 22
при N = 1102 возможно только одно R = 110102 = 26
при N = 1112 возможно только одно R = 111002 = 28
Тогда всего получаем 5 подходящих чисел.
Автомат обрабатывает натуральное число N
1) Строится восьмибитная двоичная запись числа N–1.
2) Инвертируются разряды исходного числа (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
Для какого числа N результат работы алгоритма равен 113?
Переводим число 113 в двоичную систему счисления и получаем
N — 1 = 2 6 + 2 5 + 2 4 + 2 0 = 11100012
Дополняем его до восьми бит и инвертируем:
N — 1 = 011100012 = 100011102 = 2 1 + 2 2 + 2 3 + 2 7 = 142, тогда N = 142 + 1= 143.
Помехоустойчивое кодирование с иcпользованием различных кодов
Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т.п. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали.
Попытался все описать как можно легче для человека, который никогда не занимался кодированием информации, и без каких-либо особых математических формул.
Когда мы передаем сообщение от источника к приемнику, при передаче данных может произойти ошибка (помехи, неисправность оборудования и пр.). Чтобы обнаружить и исправить ошибку, применяют помехоустойчивое кодирование, т.е. кодируют сообщение таким образом, чтобы принимающая сторона знала, произошла ошибка или нет, и при могла исправить ошибки в случае их возникновения.
По сути, кодирование — это добавление к исходной информации дополнительной, проверочной, информации. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.
Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле:
Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).
Код с проверкой на четность
Проверка четности – очень простой метод для обнаружения ошибок в передаваемом пакете данных. С помощью данного кода мы не можем восстановить данные, но можем обнаружить только лишь одиночную ошибку.
В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно . Изменение этого бита (например с 0 на 1) сообщает о возникшей ошибке.
Ниже показана структурная схемы кодера для данного кода
Так как около 90% всех нерегулярных ошибок происходит именно с одиночным разрядом, проверки четности бывает достаточно для большинства ситуаций.
Код Хэмминга
В принципе, работа этого алгоритма разобрана очень детально в статье Код Хэмминга. Пример работы алгоритма, так что особо подробно описывать в этой статье не вижу смысла. Вместо этого приведу структурную схему кодера: 
и декодера 
(может быть, довольно запутано, но лучше начертить не получилось)
e0,e1,e2 опрделяются как функции, зависящие от принятых декодером бит k1 — k7:
Набор этих значений e2e1e0 есть двоичная запись позиции, где произошла ошибка при передаче данных. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 000), то исправляет ошибку.
Коды-произведения
В канале связи кроме одиночных ошибок, вызванных шумами, часто встречаются пакетные ошибки, вызванные импульсными помехами, замираниями или выпадениями (при цифровой видеозаписи). При этом пораженными оказываются сотни, а то и тысячи бит информации подряд. Ясно, что ни один помехоустойчивый код не сможет справиться с такой ошибкой. Для возможности борьбы с такими ошибками используются коды-произведения. Принцип действия такого кода изображён на рисунке: 
Передаваемая информация кодируется дважды: во внешнем и внутреннем кодерах. Между ними устанавливается буфер, работа которого показана на рисунке: 
Информационные слова проходят через первый помехоустойчивый кодер, называемый внешним, т.к. он и соответствующий ему декодер находятся по краям системы помехоустойчивого кодирования. Здесь к ним добавляются проверочные символы, а они, в свою очередь, заносятся в буфер по столбцам, а выводятся построчно. Этот процесс называется перемешиванием или перемежением.
При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода. В таком порядке информация передается по каналу связи или записывается куда-нибудь. Условимся, что и внутренний, и внешний коды – коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове (количество «кубиков» на рисунке не критично — это просто схема). На приемном конце расположен точно такой же массив памяти (буфер), в который информация заносится построчно, а выводится по столбцам. При возникновении пакетной ошибки (крестики на рисунке в третьей и четвертой строках), она малыми порциями распределяется в кодовых словах внешнего кода и может быть исправлена. 
Назначение внешнего кода понятно – исправление пакетных ошибок. Зачем же нужен внутренний код? На рисунке, кроме пакетной, показана одиночная ошибка (четвертый столбец, верхняя строка). В кодовом слове, расположенном в четвертом столбце — две ошибки, и они не могут быть исправлены, т.к. внешний код рассчитан на исправление одной ошибки. Для выхода из этой ситуации как раз и нужен внутренний код, который исправит эту одиночную ошибку. Принимаемые данные сначала проходят внутренний декодер, где исправляются одиночные ошибки, затем записываются в буфер построчно, выводятся по столбцам и подаются на внешний декодер, где происходит исправление пакетной ошибки.
Использование кодов-произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности.