Для начала рассмотрим последовательности длины 5. Сколькими способами мы можем выбрать первый элемент последовательности? Очевидно, что вариантов 2: ноль или единица. Теперь давайте посмотрим на второй элемент. Для него у нас тоже есть два варианта, причем при любом выборе первого элемента последовательности. Значит, число способов выставить друг за другом первые два элемента равно четырем. Точно так же для каждого из этих четырех вариантов есть два способа выбрать третий элемент последовательности и так далее. В итоге для кодового слова длины 5 получаем

Аналогично число разных последовательностей длины 4 равно 2⁴ = 16, а число разных последовательностей длины 8 равно 2⁸ = 256. Для любой заданной длины n получаем 2ⁿ разных последовательностей из нулей и единиц.

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

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

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

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.

Мы рассмотрим число сочетаний на примере, связанном с кодированием. Давайте попробуем сосчитать, сколько существует слов длины n и веса k, k ≤ n. Напомним, что слово – это запись из нулей и единиц, а его вес – это количество единиц. Значит, нам нужно выбрать из n позиций k штук для расстановки на этих k выбранных позициях единиц. При этом ясно, что как только позиции будут выбраны, кодовое слово определяется однозначно. Выбрали, скажем, из шести позиций первую, четвертую и пятую – все, появилось кодовое слово 100110.

Хорошо, допустим, есть n позиций. Выбираем из них любую. Это можно сделать n способами. Для каждого из этих n способов выбора первой позиции из оставшихся n − 1 позиций снова выбираем любую. Для этого уже есть только n − 1 вариант. Итого количество способов зафиксировать первую и вторую позиции для единиц равно n (n − 1). Точно так же три позиции можно последовательно выбрать одним из n (n − 1) (n − 2) способов. И так далее. Для данного k будет всего

n (n − 1) (n − 2) × … × (n − k + 1)

вариантов. Это и есть ответ? Не совсем!

Заметим, что в нашем примере, где n = 6 и k = 3, мы могли сначала выбрать, например, первую позицию, затем – четвертую и наконец – пятую, а могли сперва выбрать четвертую позицию, затем – пятую и лишь в конце – первую. И для каждого из подобных вариантов у нас получится одно и то же кодовое слово 100110. Сколько же раз в нашей формуле n (n − 1) (n − 2) × … × (n − k + 1) мы тем самым посчитали одно и то же кодовое слово? Смотрите, получая эту формулу, мы выбирали какие-то последовательности номеров позиций: допустим, это были 1-4-5, 1-5-4, 5-1-4, 5-4-1, 4-1-5, 4-5-1. Видно, что все эти последовательности дают одно и то же слово из нулей и единиц. И видно, что их 6. Чтобы снова прийти к этому выводу не путем унылого перебора (которым мы сейчас занимались), а «весело и с умом», надо рассудить так: из трех чисел 1, 4, 5 мы можем сначала выбрать любое (3 варианта); затем вслед за ним расположить второе уже только одним из двух способов, а третье выбирается однозначно. Рассуждение дает нужный результат: число способов упорядочить числа 1, 4, 5 равно 3 × 2 × 1 = 6. Аналогично для любого k возникает формула k (k − 1) × … × 2 × 1 = k!. Напомним: по принятой в математике конвенции 0! = 1.

Что же мы имеем в итоге? Сначала мы вывели формулу n (n − 1) (n − 2) × … × (n − k + 1), потом сообразили, что в ней каждое множество позиций для единиц учтено k! раз. Это означает, что искомое количество кодовых слов равно

Заметим, что найденное выражение можно переписать в виде

Это так называемое число сочетаний из n по k, или биномиальный коэффициент. В настоящее время для него приняты два обозначения: