Математические байки

Да — такие коды (передаваемая информация группируется в блоки фиксированного размера) называются блочными. Ещё — если мы захотим работать с блоками большого размера, то у нас должен получиться большой "алфавит". В общей ситуации его даже просто хранить может быть не очень удобно. Поэтому — есть такой удобный подкласс блочных кодов, линейные коды. У которых разрешённый набор блоков это линейное подпространство в F_2^n.

А нельзя ли исправить одну ошибку в блоке с меньшим падением скорости? Можно, и самый простой такой код это код Хэмминга.

Можно просто каждый бит повторять по 3 раза: код {000,111} позволяет не только заметить, но и исправить одну ошибку. Но — скорость канала при этом падает втрое.

Тогда, если при передаче произойдёт одна ошибка, мы не сможем сказать, где она произошла, но — по крайней мере, мы её заметим (и сможем потом "переспросить" у отправителя этот блок).

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

Давайте объединим передаваемые биты в блоки. И пусть блок может быть не любым — а только одним из разрешённых кодовых слов, которые мы постараемся сделать как можно более непохожими друг на друга. Тогда, даже если где-то при передаче произойдёт ошибка — мы сможем её заметить, а может быть, даже исправить.

А именно — представим себе, что мы передаём сигнал из 0 и 1 по каналу, где время от времени возникают помехи, и в результате время от времени вместо 0 приходит 1 или наоборот. Как с этим бороться?

Второй способ построить решётку E_8 связан с кодами, исправляющими ошибки. (Да, Александр Шень читал целый курс об них — https://www.youtube.com/watch?v=DNCpIo1Gjco — но мне понадобится из этого довольно немного.)

Кстати — чётные решётки с кообъёмом 1 бывают только в пространствах, размерность которых делится на 8. И это нетривиальное утверждение, которое доказывается через модулярные формы — о чём я точно скажу, но не прямо сейчас.

Ибо меньшё 2 чётных чисел нет.

А значит, наименьшая возможная длина вектора из решётки E_8 — это корень из 2!

Проверить это несложно: =8*(1/4)=2, в \Lambda тоже все квадраты чётные (потому что сумма квадратов целых чисел сравнима с их суммой и потому по определению \Lambda чётна). Наконец, скалярное произведение v с любым вектором u из \Lambda целое, а в формуле для квадрата суммы есть двойка: =k^2 + + 2k .

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

Интересно, что эта решётка будет чётной : квадраты длин всех её векторов чётные.

Мы и получаем искомую решётку:

А теперь добавим к этой решётке её же, сдвинутую на вектор v=(1/2,1/2,...,1/2).

Так вот — давайте эту решётку построим. Для этого сначала выделим в Z^8 подрешётку \Lambda индекса 2 — вектора с чётной суммой цифр. При этом кообъём удвоится (потому что мы оставили только половину узлов)

Для оптимальной решётки наименьшее расстояние будет в \sqrt{2} раз больше — так что упаковка получится в \sqrt{2}^8=2^4=16 раз более плотной!

И естественно, что получается величина, инвариантная относительно гомотетии. Поэтому можно либо ограничиться решётками, у которых d_{min}=1, и минимизировать кообъём, либо наоборот, ограничиться решётками с единичным кообъёмом, и максимизировать d_{min}. Так вот, давайте пока примем именно второй подход. Так, если мы возьмём просто кубическую упаковку Z^8, то d_{min} будет равен 1.