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

И из пополненного кода Хэмминга получается как раз решётка E_8, решётка Коркина-Золотарёва!

Оказывается, что если мы начали унимодулярного кода — получится унимодулярная (т.е. с кообъёмом 1) решётка. Если с дважды чётного кода — чётная решётка.

Давайте теперь применим такую общую конструкцию. Пусть есть линейный код C, то есть подпространство в F_2^n. Возьмём его прообраз при отображении "приведения по модулю 2" Z^n-> F_2^n. Получится решётка — более того, подрешётка в Z^n. И теперь сожмём её в корень из 2 раз.

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

(отсюда — http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf )

И кстати — несколько более сложные, но аналогичные коды реально применялись для связи с далёкими зондами:

Скорость передачи упала ровно вдвое — мы теперь передаём 4 бита за блок длиной 8. Зато кодовое расстояние возросло до 4, поэтому мы можем не только исправить одну ошибку, но и обнаружить (хоть и не исправить) две.

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

А во-вторых, видно, как показывать фокус: нужно просто иметь такую матрицу записанной, складывать по модулю 2 те столбцы, про которые был ответ "да" — и сумма будет равна тому столбцу, в котором отвечающий соврал. Или нулевому столбцу, если он такой возможностью не воспользовался.

Отсюда, во-первых, видно, что кодовое расстояние действительно не меньше 3: все столбцы разные и ненулевые, поэтому сумма mod 2 никаких <=2 не будет нулевой.

Да, и если уж об этом зашла речь, давайте я скажу, что проверочной матрицей кода называется матрица, где по строчкам записан базис ортогонального дополнения к коду. Она проверочная — потому что если её умножить на правильное сообщение, то будет вектор из одних нулей. Несложно увидеть, что проверочная матрица к коду с порождающей матрицей (Id_k | A) это матрица (A^* | Id_{n-k}). В частности, для кода Хэмминга проверочной матрицей будет

Вопросы, разумеется, в виде заранее подготовленных карточек — "есть ли твоё число на этой карточке". У нас в Ренне обычно среди прочего бывает и такое на стенде математиков на днях науки; дети радостно пользуются разрешением соврать — я помню буквально два-три случая, когда при показе этого фокуса на все вопросы отвечали честно. :) (Вот тут есть реализация этого на смайликах — http://xavier.toonywood.org/popularization/applets/hamming.html — правда, с вопросами по-французски)

Этот код позволяет в блоке длины 7 передать 4 бита, и при этом исправляет одну ошибку. Стандартный фокус, который с его помощью делается — игра "загадай число от 1 до 15 и ответь на 7 вопросов; отвечая, можно один раз соврать, а я всё равно угадаю загаданное число".

Так вот, код Хэмминга — линейный блочный код с кодовым расстоянием (т.е. наименьшим расстоянием между элементами кода), равным 3, и потому позволяет исправить одну ошибку. И вот его порождающая матрица:

Матрица, в которую (по строкам — так удобнее) записан базис этого подпространства, называется порождающей матрицей линейного кода. Если применить метод Гаусса, перевыбрав базис, то можно привести порождающую матрицу к виду M=(Id_k | что-то); это будет означать, что первые k бит это собственно передаваемая информация, а оставшиеся n-k это своеобразная "контрольная сумма".