Спирина, М.С. Дискретная математика

видов графики и др. Так как для любого кодирования должна вы­ полняться операция декодирования, то отображение должно быть обратимым (биекция). Если все кодовые слова имеют одинаковую длину, то код на­ зывается равномерным, или блочным. Под абстрактным алфавитом будем понимать упорядоченное дискретное множество символов. Например: • алфавит букв русского языка А, Б, В, ..., Я, мощность кото­ рого Л] = 33; • алфавит арабских цифр 0, 1 , 2 , ..., 9, п2 = 10; • алфавит знаков шестигранной кости (кубика) • , ;, ; ;, X , :::> «з = 6; • двоичный алфавит В = { 0, 1}, л4 = 2; • двоичный алфавит {«точка», «тире»}, п5= 2; • алфавит римской системы счисления I, V, X, L, С, D, М...; • алфавит языка блок-схем для изображения алгоритмов: D O O O Особенно важное значение имеют алфавиты, содержащие два элемента — двоичный, или бинарный, набор символов. Это такие пары символов, как цифры {0, 1}, семантические значения «ис­ тина» и «ложь» {и, л), пара ответов {да, нет}, пара состояний «включено» и «выключено», знаки азбуки Морзе {•, —} («точка», «тире»). Алфавитное кодирование. Пус^ь* заданы конечный алфавит А - = {аь ..., а„} и множество слов над алфавитом А — А*. Напомним, что для слова а = (aia2...a„) е А* количество используемых букв называется длиной слова и обозначается / (а ) = Iа | = | ах... ап | = п. Назовем элементарной частью сообщения ту его минимальную часть, которой ставится в соответствие символ из множества В. Будем рассматривать простейший случай, когда элементарной частью сообщения является одна буква алфавита А. Алфавитное, т.е. побуквенное, кодирование можно задать таб­ лицей кодов. Фактически кодом, кодирующей функцией, будет служить некоторая подстановка о. Тогда а: (а, -> о ( а , ) , ..., а„ -» а ( а я)> = ф,■...£/„> или а = где а , е А, р, е В*. Такое ocj ... а„ ft - Р„ , побуквенное кодирование обозначается К ^ . Множество кодов букв {Р,} называется множеством элементарных кодов. Алфавитное ко­ дирование можно использовать для любого множества сообщений. Таким образом, алфавитное кодирование является самым про­ стым, и его всегда можно ввести на непустых алфавитах. Пусть, например, заданы алфавиты А и В, состоящие соответ­ ственно из {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} и {0, 1}. Тогда таблица кодирования может быть подстановкой: 310