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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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