2. Граница Хэмминга

Допустим, мы пользуемся словами длиной n и наш код состоит из N таких слов.

Если код исправляет d ошибок, то шары Хэмминга с центрами в кодовых словах и радиусами d попарно не пересекаются. Объем шара (то есть количество слов в нем) нетрудно вычислить. Сколько слов отстают от центра шара на заданное расстояние k? Разумеется, столько, сколькими способами можно выбрать те k позиций из n возможных, в которых произойдут помехи. Это число способов называется числом сочетаний из п по k и обозначается C^k_n. Для того чтобы его записать, нам понадобятся произведения вида

k ? (k ? 1) ? … ? 2 ? 1.

Такое произведение принято обозначать записью

k!

и она читается как k факториал. Легко увидеть, что, конечно, 1! = 1, и принято считать, что 0! = 1. Заметим, что факториал уже встречался нам в главе 2 в разделе «Проклятие размерности». Там мы показали, что факториал растет очень быстро. Например, 25! – это колоссальное число.

Число сочетаний вычисляется по формуле

Мы приводим вывод этой известной формулы ниже, в приложении 3. Легко проверить, скажем, что C?_n, и действительно мы можем выбрать одну позицию из n ровно n способами.

Значит, всего внутри шара

слов. Здесь слагаемое C⁰_n=1 – это число слов, отстоящих от центра на расстояние 0. Такое слово только одно – сам центр. Поскольку шары с центрами в кодовых словах попарно не пересекаются, то всего в них находится

различных слов. Но это количество заведомо не превосходит числа всех возможных кодовых слов, которое, как мы уже знаем, равно 2n. Таким образом,

Эта формула и есть граница Хэмминга. В нашем примере, когда n = 10, d = 2, получаем

Всего последовательностей длины 10 ровно 2¹⁰ = 1024. Получается, что максимальное количество кодовых слов не превышает 1024 ? 56 ? 18,2857. Поскольку число кодовых слов целое, оно не больше 18.