Задачи и дополнения

1. Сравнить коды V_5,6 и V_5,10, а также коды V_6,8 ... V_6,12 по их способности исправлять двойные замещения вида 0 → 1.

2. Для кода V_{n, n+1} сформулировать признак исправимости замещения двух или большего числа символов. Каким будет этот признак для кода V_{n, 2n}?

3. Найти алгоритм исправления (исправимого) двойного замещения для кодов V_{n, n+1} и V_{n, 2n}.

4. Коды V_{n, k} можно использовать для исправления одиночных замещений вида 1 → 0). Каково в этом случае правило декодирования?

5. Построив код V_7,8, убедиться, что на местах с номерами 3, 5, 6, 7 встречаются всевозможные наборы из нулей и единиц и, значит, символы с этими номерами играют роль информационных.

6. Утверждение задачи 5 можно обобщить на случай любого кода V_{n, n+1}, для которого n = 2^m - 1.

Рассмотрим m позиций с номерами 1, 2, ..., 2^m-1. Выберем произвольную комбинацию из нулей и единиц в оставшихся n-m позициях. Тогда существует единственное заполнение позиций 1, 2, ..., 2^m, для которого получившееся слово удовлетворяет условию (2), т. е. является кодовым. Отсюда вытекает, что число слов кода V_{n, n+1} равно 2^n-m, т. е. совпадает с числом слов в коде Хемминга длины n = 2^m - 1.

7. Пусть k ≥ n + 1 есть простое число. Через V˜_{n, k} обозначим код, состоящий из всех слов υ = x₁ х₂ ... х_n, для которых выполняются два соотношения:

Построить код V˜_6,7. Убедиться, что он исправляет любые одиночные и двойные замещения вида 0 → 1.

8. Показать, что всякий код V˜_{n, k} (см. задачу 7) исправляет любые одиночные и двойные замещения вида 0 → 1. Сохранится ли это свойство для составного k?