Кому нужна математика? Понятная книга о том, как устроен цифровой мир

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

2 × 2 × 2 × 2 × 2 = 2⁵ = 32.

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

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.

3. Число сочетаний из n по k

Мы рассмотрим число сочетаний на примере, связанном с кодированием. Давайте попробуем сосчитать, сколько существует слов длины 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)

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