17.Кодирование сообщений

Кодирование сообщений. Комбинаторика.

Что нужно знать:

• мощность алфавита M – это количество символов в этом алфавите

• если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно

• для двоичного кодирования (мощность алфавита M – 2 символа) получаем известную формулу:

• таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит:

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?

Решение:

1. согласно условию, алфавит содержит только два знака – точку и тире¹

2. «не менее четырёх и не более пяти сигналов» означает, что нужно определить количество всех 4- и 5-буквенных слов в двоичном алфавите

3. количество 4-буквенных слов равно 2⁴ = 16, а количество 5-буквенных 2⁵ = 32

4. поэтому общее количество 4- и 5-буквенных слов равно 16 + 32 = 48

5. ответ: 48.

1^ Не для ЕГЭ: здесь не учтено, что код Морзе – неравномерный, и для того, чтобы отделить одно кодовое слово от другого при передаче между ними делается пауза.