Tricky Circuit

Чётность и слепое пятно

Один бит замечает часть ошибок

Чётность описывает, чётно или нечётно количество битов 1. Проверочный бит дополняет данные так, чтобы общее количество единиц вместе с ним было чётным.

Открыть интерактивный опыт

ЭКСПЕРИМЕНТАЛЬНЫЙ СТОЛ

Меняй настройки схемы, предсказывай показания и проверяй решение задания. Это учебные модели; допущения объяснены в каждом уроке.

Войди, чтобы сохранять прогресс. Прогресс гостя хранится на этом устройстве.

Открыть лабораторию в полном окне

Почему это работает

Идеальная двоичная логика: 0 — низкий уровень, 1 — высокий, а не измеренное напряжение. Питание, ток, нагрузка выхода и задержка не моделируются; рисунки показывают функции, а не выводы микросхем.

b0, b1, b2 — данные, N — число единиц. P — добавленный бит чётности: P = b0 ⊕ b1 ⊕ b2. ⊕ — XOR, Exclusive OR, исключающее ИЛИ. N + P всегда чётно. Опыт создаёт бит, а не моделирует передачу с помехами.

Сложность

  1. Собери · Собери

    Включи b0 = 1, b1 = 0 и b2 = 0. Получи P = 1 и общее число единиц 2.

    Нужна подсказка?

    b0 = 1; b1 = 0; b2 = 0 → P = 1; N + P = 2

  2. Исследуй · Измени входы

    Задай b0 = 1, b1 = 1 и b2 = 0. Получи P = 0 и общее число единиц 2.

    Нужна подсказка?

    b0 = 1; b1 = 1; b2 = 0 → P = 0; N + P = 2

  3. Реши сам · Реши задачу

    Задай b0 = 1, b1 = 1 и b2 = 1. Получи P = 1 и общее число единиц 4.

    Нужна подсказка?

    b0 = b1 = b2 = 1 → P = 1; N + P = 4

Дополнительные материалы и карточки схем

Один бит замечает часть ошибок

Добавь к сообщению маленькую проверку. Лишний бит позволяет заметить нечётное число изменённых битов, но не восстановить сообщение.

N = b0 + b1 + b2; P = b0 ⊕ b1 ⊕ b2; N + P ∈ {0, 2, 4}

Для нечётного числа единиц P = 1, для чётного P = 0. Дополнительный бит исправляет чётность количества, а не значение сообщения.

Полезная закономерность

Один изменённый бит в защищённом слове, включая сам бит чётности, нарушает проверку. Нечётное число изменений тоже.

За пределами модели

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

Ошибка, которой стоит избежать

Успешная проверка не доказывает правильность данных. Новый P после правки входов создаёт новое верное слово, а не проверяет старое переданное.

В слове с верной чётностью изменились два разных бита. Проверка…

  1. обязательно провалится
  2. может пройти с неверными данными
  3. исправит оба бита
Читать дальше

Два изменения дважды меняют чётность: она снова чётная. Такая ошибка не обнаруживается.

Собери

Задай b0 = 1, b1 = 0, b2 = 0. Одной единице нужен P = 1, всего будет две.

N = 1; P = 1; N + P = 2

Измени входы

Задай все три бита равными 1. P = 1 даёт четыре единицы.

N = 3; P = 1; N + P = 4

Попробуй другой путь

Запиши верное слово «данные плюс P». На бумаге измени один бит, затем два, оставляя исходный P, если не меняешь его самого. Сосчитай единицы.

ti.com