Problems to be solved at home. Обязательные задачи для решения дома

Problems for the course «Error correcting codes (HSE)»
Задачи по курсу Коды с исправлением ошибок.

Deadline Jan. 28, Срок сдачи — 28 января:

1. Prove that from any [n,k,d,q]-code (n is the code words length, k is
the dimension of the code, d is the minimal Hamming distance between code words (the minimal Hamming
distance), q is the cardinality of the alphabet)
one can construct a [n-1,k,d-1,q]-code (for d>1).
Доказать, что если существует код с параметрами n,k,d,q (где n
длина кодовых слов, q размер алфавита, d кодовое расстояние, k
логарифм количества кодовых слов), то
существует код с параметрами n-1,k,d-1,q (предполагается, что d>1).

2. Construct a polynomial time algorithm for correcting 2 erasures in the Hamming code.
Докажите, что при q=2 и четном d существует и обратное преобразование:
код с параметрами [n-1,k,d-1,2] можно преобразовать в код с параметрами [n,k,d,2].

Deadline Feb. 4, Срок сдачи — 4 февраля:

3. For Reed — Solomon codes, construct a polynomial time algorithm
that corrects e errors and b erasures for all a,b such that
2e+b is less than d.
Постройте алгоритм, который за полиномиальное от n
количество операций исправляет в коде Рида-Соломона e ошибок
и b стираний, для любых
данных e,b, удовлетворяющих неравенству 2e+b меньше d.

4. Assume that q is a power of a prime and n>=q. Show that
the cardinality of the Hamming ball of radius r in the
space of strings of length n over the q-letter alphabet is
at most q^{2r}. Conclude that for such n,q the Singleton bound is
stronger than the volume bound.
Докажите, что если q есть степень простого чилсла и не меньше n,
то мощность шара Хэмминга радиуса r в пространстве
слов длины над алфавитом из q букв не превосходит q^{2r} (задачу
можно решить без длинных подсчетов, используя оценку Хэмминга
и код Рида-Соломона). Выведите отсюда, что для таких q оценка
Синглтона сильнее оценки Хэмминга.

Deadline Feb. 11, Срок сдачи — 11 февраля:

5. Assume that q is a power of a prime and C is a linear subspace
with basis e_1,…,e_k of the n-dimensional vector space over the field of cardinality q.
Show that the minimal Hamming distance of C is more than d if and only if
for all i the vector e_i is outside every ball of radius d
centered at a linear combination of vectors e_1,…,e_{i-1}.
Пусть q есть степень простого числа, а C есть линейное пространство
n-мерного пространства над
полем из q элементов, натянутое на вектора e_1,…,e_k. Докажите, что кодовое
расстояние C больше d тогда и только тогда, когда для всех i вектор
e_i не принадлежит ни одному из шаров радиуса d с центром в некоторой
линейной комбинации векторов e_1,…,e_{i-1}.

6. Assume that q is a power of a prime
and q^{k-1}*V is less than q^n. Show that there is an [n,k,d+1,q] code.
Пусть q есть степень простого числа и q^{k-1}*V меньше q^n, где
V обозначает объем шара радиуса d в пространстве слов длины n над q-буквенным
алфавитом. Докажите, что тогда существует код с параметрами n,k,d+1,q.

Deadline Feb. 18. Срок сдачи — 18 февраля:

7. Find 9 code words over a 3-letter alphabet
such that Hamming distance between any pair of them is
at least 2. Найдите 9 кодовых слов длины 3 в трехбуквенном алфавите,
расстояние Хэмминга между
любой парой которых не меньше двух.

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

Deadline Feb. 25. Срок сдачи — 25 февраля:

9. Find the rate (k/n) of the Forney code that
has minimal Hamming distance d where d/n= 0.03, 0.04, 0.06, 0.09, 0.15, 0.25
Найдите скорость передачи (эффективность) кода Форни
при следующих значениях относительного кодового расстояния:
0.03, 0.04, 0.06, 0.09, 0.15, 0.25

10. Buid a generalized Wozencraft code with the rate k/n=3/4.
Постройте обобщённый код Возенкрафта со скоростью передачи 3/4.

Deadline March 4. Срок сдачи — 4 марта

11. For all k construct a [n=k+1,k,d=2,q=2] code.
On which side of the Gilbert curve is that code?
On which side of the Singleton curve is that code?
Постройте бинарный код с параметрами k, n=k+1, d=2 (для произвольного k).
С какой стороны от границы Гилберта находится этот код (при достаточно больших k)?
С какой стороны от границы Синглтона находится этот код?

12. Construct a [n=12, k=4, d=6, q=2] code.
Постройте бинарный код с параметрами k=4, n=12, d=6.

Deadline March 11. Срок сдачи — 11 марта

13. What parameters has the concatenated code where the outer code is the Reed — Solomon with the rate
1/2, the alphabet of q=2^{21} symbols and code length n=2^{21} and the inner code is
the BCH codes with the minimal Hamming distance 6?

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

14. Prove that there is a [n=15, k=7, d=5, q=2] code.

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

Deadline March 18. Срок сдачи — 18 марта

15. Assume that a code with parameters n,k,q is capable to correct b erasures by a list of size L.
Show that q^{b+k-n} <= L. Пусть код с параметрами n,k,q способен исправлять b стираний списком размера L. Докажите, что q^{b+k-n} <= L.

16. Assume that b+k <= n. Prove that there is a code with parameters n,k,q capable to correct b erasures by a list of size L=O(n log q). Пусть, наоборот, b+k <= n. Докажите, что существует код с параметрами n,k,q, способный исправлять b стираний списком размера L=O(n log q).

Deadline April 1. Срок сдачи — 1 апреля

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

Prove that any code with parameters q, n, k and minimal Hamming
distance d = n(1-1/q)(1-\epsilon) is capable to decode
by a list of size O(nq) correcting n(1-1/q)(1-\sqrt{\epsilon}) errors.

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

Prove that every code with minimal Hamming distance 16 and code word length 25
is capable to decode
by a list of size 51 correcting 10 errors.

Deadline April 8. Срок сдачи — 8 апреля

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

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