5 / 63 · Теория

XOR и XNOR: равенство, различие и чётность

Различайте двухвходовый XOR и многовходовую чётность и объясняйте ограничения обнаружения ошибок.

Элемент, определяющий различие двух битов

XOR равен 1, если два входа различны, XNOR — если одинаковы.

a\oplus b=\overline a b+a\overline b,\qquad \overline{a\oplus b}=ab+\overline a\,\overline b

OR и XOR совпадают при 00, 01 и 10, но различаются при 11. В обозначении XOR перед OR добавлена ещё одна кривая. У XNOR также есть кружок инверсии^{Инверсия — операция NOT, меняющая 0 на 1 и 1 на 0. Черта над формулой означает применение NOT ко всему выражению под ней. Подробнее} на выходе.

Сравните OR и XOR при 11

XOR · Таблица истинности
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

Для трёх и более входов это уже не «ровно один»

XOR ассоциативен, поэтому $a\oplus b\oplus c$ можно вычислять последовательно. Результат равен 1 при нечётном числе единиц на входах. При 111 тоже получается 1, поэтому обобщение «ровно один вход равен 1» неверно.

Выход sum полного сумматора — эта трёхвходовая чётность^{Чётность указывает, чётно или нечётно число единичных битов. Проверка чётности обнаруживает ошибки в нечётном числе битов, но может пропустить ошибки в чётном числе.}, а cout показывает, есть ли минимум две единицы. Задайте ниже 111: sum=1, cout=1, целочисленная сумма $1+2\times1=3$ .

Три входа: нечётность и большинство — разные функции

a + b + cin = sum + 2 × cout

Чётность обнаруживает определённые классы ошибок

Для данных $d_3d_2d_1d_0=1011$ бит чётного паритета $p=d_3\oplus d_2\oplus d_1\oplus d_0=1$ . XOR всех данных вместе с p равен 0. Если при передаче инвертируется нечётное число битов, общий XOR станет 1, обнаружив ошибку. Чётное число инверсий может остаться незамеченным; один бит паритета также не позволяет определить место ошибки.

Проверка равенства битовых строк

Равенство векторов A и B можно проверить, объединив побитовые XOR через OR:

equal=\overline{\bigvee_i(A_i\oplus B_i)}

При хотя бы одном несовпадении OR равен 1. Инверсия всего результата даёт 1 лишь при совпадении всех битов. Реализация «все результаты XOR ещё раз соединить через XOR» ошибочна: два несовпадения взаимно погашаются.

Попробуйте сами

Найдите A XOR B и результат проверки равенства при A=1010, B=1001. Что пойдёт не так, если определять равенство свёрткой полученной битовой строки через XOR?

Прочитать объяснение

XOR даёт 0011, равенство — 0. Два несовпадения при XOR-свёртке взаимно погашаются до 0, а инверсия ошибочно даст равенство=1. Биты несовпадения нужно свёртывать через OR.