Помехоустойчивые коды: бит чётности, расстояние Хэмминга, код Хэмминга

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

Что нужно сделать: Шесть задач — по одной на каждый вопрос темы, и все сразу на странице: решай в любом порядке. Ответил верно — вопрос закрыт. Ошибся — сразу видно, как это решается, а вопрос остаётся открытым: кнопка «Новые числа» даёт ту же задачу с другими данными, и её можно сдать ещё раз. Сколько закрыл, столько и наработал. Времени нужно около пятнадцати минут: код Хэмминга удобнее расписывать на черновике по позициям.
Отметка и добор: Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Кнопка «Получить код» внизу страницы появляется, как только закрыто три вопроса: можно забрать код сразу, а можно дорешать оставшиеся и получить код получше — решать самому, до какой отметки добирать.
Ответ — целое число или двоичное слово: Число — без единиц измерения: 3, а не 3 ошибки. Двоичное слово — все биты подряд, вместе с нулями в начале: 0110100. На КЕГЭ ответ читает машина, и здесь так же.
Как сдать: В конце появится код работы и кнопка «Сдать работу»: впишешь код ученика, кнопка сама откроет форму с уже вписанным кодом. Переписывать код руками не надо — на этом чаще всего и ошибаются.
Не успел на уроке: Открой эту же страницу дома и пройди целиком: вариант будет другой, а сдаётся всё так же — одним кодом.

Вопросы темы

наработано на—

Подсказка: помехоустойчивые коды

Зачем нужны помехоустойчивые коды

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

Бит чётности

К блоку дописывают один бит так, чтобы единиц стало чётное число. Пришёл блок с нечётным числом единиц — ошибка. Ловит одну ошибку (и любое нечётное их число), но не показывает где; две ошибки не видит.

Расстояние Хэмминга

Число позиций, в которых два слова одинаковой длины различаются: между 10110 и 11100 оно равно 2. Кодовое расстояние d — наименьшее расстояние между парами кодовых слов.

код с расстоянием d	сколько ошибок
обнаруживает	d − 1
исправляет	(d − 1) : 2 нацело
чтобы исправлять t ошибок	нужно d ≥ 2t + 1

Код с повторением

Каждый бит передаётся три раза: 1 → 111, 0 → 000. Приёмник решает по большинству: 101 — это 1. Здесь d = 3: одна ошибка в тройке исправляется. Цена — сообщение втрое длиннее.

Код Хэмминга (7,4)

Четыре информационных бита и три контрольных, исправляет одну ошибку. Позиции считаются с 1 слева направо; контрольные биты стоят на степенях двойки.

позиция	1	2	3	4	5	6	7
что стоит	к1	к2	д1	к4	д2	д3	д4

к1 делает чётным число единиц на позициях 1, 3, 5, 7;
к2 — на позициях 2, 3, 6, 7;
к4 — на позициях 4, 5, 6, 7.

Поиск ошибки: проверить три группы принятого слова. Номера контрольных битов, у которых чётность нарушена, сложить — получится номер искажённой позиции (сбой в группах 1 и 4 — ошибка в бите 5). Этот бит инвертировать. Для m информационных битов нужно r контрольных: 2^r ≥ m + r + 1.

Материалы подготовлены с использованием технологий искусственного интеллекта.