Задачи по курсу Коды с исправлением ошибок

1. Доказать, что если существует код с параметрами n,k,d,q (где n
длина кодовых слов, q размер алфавита, d кодовое расстояние, k
логарифм количества кодовых слов), то
существует код с параметрами n-1,k,d-1,q (предполагается, что d>1).

2. Докажите, что при q=2 и четном d существует и обратное преобразование:
код с параметрами [n-1,k,d-1,2] можно преобразовать в код с параметрами [n,k,d,2].

3. Постройте алгоритм, который за полиномиальное от n
количество операций исправляет в коде Рида-Соломона e ошибок
и b стираний, для любых
данных e,b, удовлетворяющих неравенству 2e+b меньше d.

4. Докажите, что если q есть степень простого чилсла и не меньше n,
то мощность шара Хэмминга радиуса r в пространстве
слов длины над алфавитом из q букв не превосходит q^{2r} (задачу
можно решить без длинных подсчетов, используя оценку Хэмминга
и код Рида-Соломона). Выведите отсюда, что для таких q оценка
Синглтона сильнее оценки Хэмминга.

5. Пусть q есть степень простого числа, а C есть линейное пространство
n-мерного пространства над
полем из q элементов, натянутое на вектора e_1,…,e_k. Докажите, что кодовое
расстояние C больше d тогда и только тогда, когда для всех i вектор
e_i не принадлежит ни одному из шаров радиуса d с центром в некоторой
линейной комбинации векторов e_1,…,e_{i-1}.

6. Пусть q есть степень простого числа и q^{k-1}*V меньше q^n, где
V обозначает объем шара радиуса d в пространстве слов длины n над q-буквенным
алфавитом. Докажите, что тогда существует код с параметрами n,k,d+1,q.

7. Найдите 9 кодовых слов длины 3 в трехбуквенном алфавите,
расстояние Хэмминга между
любой парой которых не меньше двух.

8. А можно ли найти 10 кодовых слов с теми же свойствами?

9. Найдите скорость передачи (эффективность) кода Форни
при следующих значениях относительного кодового расстояния:
0.03, 0.04, 0.06, 0.09, 0.15, 0.25

10. Постройте обобщённый код Возенкрафта со скоростью передачи 3/4.

11. Постройте бинарный код с параметрами k, n=k+1, d=2 (для произвольного k).
С какой стороны от границы Гилберта находится этот код (при достаточно больших k)?
С какой стороны от границы Синглтона находится этот код?

12. Постройте бинарный код с параметрами k=4, n=12, d=6.

13. Каковы параметры каскадного кода, в котором внешним является
код Рида-Соломона со скоростью 1/2 и длиной кодовых слов и мощностью алфавита
q=n=2^{21}, а внутренним — код БЧХ с
минимальным расстоянием 6?

14. Докажите, что существует бинарный код с параметрами k=7, n=15, d=5.

15. Пусть код с параметрами n,k,q способен исправлять b стираний списком размера L.
Докажите, что q^{b+k-n} <= L.

16. Пусть, наоборот, b+k <= n. Докажите, что существует код с параметрами n,k,q, способный исправлять b стираний списком размера L=O(n log q).

17. Докажите, что любой код с параметрами q, n, k и кодовым расстоянием
d = n(1-1/q)(1-\epsilon) способен декодировать списком размера O(nq) с исправлением n(1-1/q)(1-\sqrt{\epsilon}) ошибок.

18. Докажите, что для любого алфавита любой код с кодовым расстоянием 16
и длиной кодовых слов 25 можно декодировать кодовые слова списком размера 51 с исправлением 10 ошибок.

19. Доказать, что кривая Элайеса-Бассалыго
(ее уравнение k/n+H(1/2-sqrt{1-2d/n}/2)=1) лежит левее прямой k/n+2d/n=1

20. Доказать, что кривая Элайеса-Бассалыго лежит левее кривой Хэмминга
(для двухбуквенного алфавита и с точностью до бесконечно малых).