Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
7 Если было задумано число 3, то ответами будут «да», «нет», «нет», т. е. числу 3 соответствует последовательность 011. По результатам ответов можно составить следующую таблицу:
Таблица 1
Задуманное число 0 1 2 3 4 5 6 ! 7
Otb еты ООО 001 OiO 01! 100 101 110 111
Читатель, знакомый с двоичной системой счисления, узнает в нижней строке двоичную запись соответствующих чисел верхней строки.
Заметим, что вместо множества чисел от 0 до 7 можно рассматривать любое множество из восьми сообщений, и каждое из них мы можем закодировать последовательностями из нулей и единиц длины 3. Если использовать более длинные двоичные последовательности, то ими в принципе можно закодировать любое конечное множество сообщений. Действительно, число двоичных последовательностей длины 3 равно 23=8 (все они приведены в таблице 1), двоичных последовательностей длины 4 вдвое больше — число их равно 24 ==16. Вообще, число двоичных последовательностей длины п равно 2". Поэтому, если требуется закодировать нулями и единицами, к примеру, 125 сообщений, то для этого с избытком хватит двоичных последовательностей длины 7 (их в нашем распоряжении имеется 27 = — 128). Из этого примера становится ясно, что M сообщений можно закодировать двоичными последовательностями длины п тогда и только тогда, когда выполняется условие z'CjsA/, т. е. когда n^log2A4.
Первый, кто понял, что для кодирования достаточно двух символов, был Фрэнсис, Бэкон. Двоичный код, который он использовал в криптографических целях, содержал пятиразрядные (как и в коде Б одо) слова, составленные из символов 0, L.
Сказанное здесь — это лишь первые подступы к проблеме кодирования, которой посвящена эта книга. Пока же отметим только, что наряду с двоичными кодами применяют коды, использующие не два, а большее число элементарных сигналов, или, как их еще называют, кодовых символов. Их число d называют основанием кода, а множество кодовых
8 символов — кодовым алфавитом. При этом общее число п-буквенных слов, использующих d символов, вычисляется аналогично прежнему и равно dn.
Задачи и дополнения
1. Часто по разным соображениям для кодирования сообщений используют те все последовательности в данном алфавите, а только некоторые из них, удовлетворяющие тем или иным ограничениям. Будем рассматривать, например, n-буквенные двоичные слова с фиксированным числом t единиц (или, как говорят, слова постоянного веса t). Сколько всего таких слов — нетрудно подсчитать. Каждое из них получится, если мы выберем некоторым образом t позиций из я, и запишем в них единицы, а в остальных n—t позициях — нули. Значит, число всех слов постоянного веса совпадает с числом сочетаний из п элементов по і, т. е. равно
Qi _ «'
2. Сложнее найти число всех двоичных слов длины п, к; содержащих несколько нулей подряд. Обозначим это число через s„. Очевидно, S1=2, а слова длины 2, удовлетворяющие нашему ограничению, таковы: І0, 01, 11, т. е. S2= 3. Пусть K1Ot2 . . . a„_ja„—такое слоро из п символов. Если символ et,,= 1, то G1 Ct2 . . . os„_j может быть произвольным {!I—1)-буКЕЄННЬІМ словом, не содержащим нескольких нулей подряд. Значит, число слов длины п с единицей на конце равно s„_x.
Если же символ а„=0, то обязательно а„_і=І, а первые п—2 символа Oidi2 ¦ ¦ ¦ °-п-г могут быть произвольными с учетом рассматриваемого ограничения. Следовательно, имеется s„_2 слов длины п с нулем на конце. Таким образом, общее число интересующих нас слоз равно
sn " sn~ 1 -Г sIl-lZ'
Из полученного соотношения (подобные соотношения называют рекуррентными) легко можно пайти числа Sn для любого п. Поскольку S1 и s2 кзкестны, то s3=S1-J-S2=-S; s4 = s2-|-s3—8, sa=s3-[-s^--- ІЗ и т.д. Полученная последовательность чисел
2, 3, 5, 8, 13, 21, 34, ... ,
б которой каждый последующий член равен сумме двух предыдущих,— это хорошо известный в математике ряд Фибоначчи. О многих интересных свойствах чисел Фибоначчи и их разнообразных приложениях можно прочесть в популярной брошюре [21], а также в недавно изданной книге [6]. В частности, можно убедиться (см. [21]), что п-ый член ряда Фибоначчи вычисляется по формуле:
3. Соединим оба предыдущих ограничения и найдем число двоичных слов постоянного веса і, не содержащих нескольких нулей подряд.
Рассуждать можно так. Пусть q—ti—і —- число нулей в рассматриваемых словах. В любом слове имеется q—1 промежутков между ближайшими нулями, в каждом из которых находится одна или несколько
9 единиц (см. рис. 1). Предполагается, конечно, чтс q<nf2. E прогшмом случае (при q>n/2) нет ни одного слова без рядом стоящих нулей.
Если из каждого промежутка удалить ровно по одной единица, то получим слово длины л—?+1, содержащее q нулей. Легко видеть, п п что любое такое слово может Сыть О— • - - - - ¦ .......... получено указанным образом из некоторого (и притом только одного) и-буквенного слова, содержащего q нулей, никакие два из которых не стоят рядом. Значит, искомое число совпадает с числом всех слов Промежутки длины п—<7+1, содержащих ровно сединицвт q нулей, т. е. равно (см. допол-
