Дискретная математика (998286), страница 28
Текст из файла (страница 28)
5.6. Пусть р„— число булевых функций, существенно зависящих от всех своих переменных. Очевидно, что ~'" ='> С(п,')рр 1=0 Получить явную формулу для р„, используя формулы обращения. 5.7. Чисаа Фибоааччи Е(п) определяются следующим образом: Е(0):=1, Е(1):=1, Р(п+2):=Р(п+1)+Р(п). Найти выражение для Е(п) через и (указание: рассмотреть производящую функцию 1/(1 — х — хз)). ГЛАВА 6 Кодирование Вопросы кодирования издавна играли заметную роль в математике. Пример 1. Десятичная позиционная система счисления — это способ кодирования натуральных чисел. Римские цифры — другой способ кодирования натуральных чисел, причем гораздо более наглядный и естественный: палец — 1, пятерня— У, две пятерни — Х. Однако при этом способе кодирования труднее выполнять арифметические операции над большими числами, поэтому он был вытеснен позиционной десятичной системой.
2. Декартовы координаты — способ кодирования геометрических объектов числам н. Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения, но с появлением компьютеров ситуация радикально изменилась. Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самых разных (практически всех) задач программирования: ° представление данных произвольной природы (например чисел, текста, графики) в памяти компьютера; м защита информации от несанкционированного доступы ~ обеспечение помехоустойчивости при передаче данных по каналам связи; гч сжатие информации в базах данных.
ЗАМЕЧАНИЕ Само составление текста программы часто и совершенно справедливо называют кодиро- ванием. Не ограничивая общности, задачу кодирования можно сформулировать следующим образом. Пусть заданы алфавиты А = (аы...,а„), гз = (Ьг,...,Ь,) и 160 Глава 6. Кодирование функция Р: Я -» В", где Я вЂ” некоторое множество слов в алфавите А, Я с А'. Тогда функция Р называется кодированием, элементы множества Я вЂ” сообщениямщ а элементы 3 = Р(а), а Е Я, 33 Е В' — кодами (соответствующих сообщений). Обратная функция Р ' (если она существует!) называется декодированием.
Если ~В~ = гп, то Р называется гл-ичиым кодированием. Наиболее распространенный случай В = (О, 1) — двоичное кодирование. Именно этот случай рассматривается в последующих разделах; слово «двоичное» опускается. Типичная задача теории кодирования формулируется следующим образом: при заданных алфавитах А, В и множестве сообщений Я найти такое кодирование Р, которое обладает определенными свойствами (то есть удовлетворяет заданным ограничениям) и оптимально в некотором смысле. Критерий оптимальности, как правило, связан с минимизацией длин кодов. Свойства, которые требуются от кодирования, бывают самой разнообразной природы: ь существование декодирования — это очень естественное свойство, однако даже оно требуется не всегда.
Например, трансляция программы на языке высокого уровня в машинные команды — зто кодирование, для которого не требуется однозначного декодирования; ь помехоустойчивость, или исправление ошибок: функция декодирования Р ' обладает таким свойством, что Р '(33) = Р '(33'), если 33' в определенном смысле близко к ~3 (см. раздел 6.3); ~ заданная сложность (или простота) кодирования и декодирования. Например, в криптографии изучаются такие способы кодирования, при которых имеется просто вычисляемая функция Р, но определение функции Р ' требует очень сложных вычислений (см. подраздел 6.5.5). Большое значение для задач кодирования имеет природа множества сообщений Я. При одних и тех же алфавитах А, В и требуемых свойствах кодирования Г оптимальные решения могут кардинально отличаться для разнмх Я.
Для описания множества Я (как правило, очень большого или бесконечного) применяются различные методы: м теоретико-множественное описание, например Я = (а ! а Е А» ог1а~ '= и); м вероятностное описание, например Я = А*, и заданы вероятности р; появления букв в сообщении, ~,"., р; = 1; м логико-комбинаторное описание, например, Я задано. порождающей формальной грамматикой. В этой главе рассматривается несколько наиболее важных задач теории кодирования и демонстрируется применение большей части упомянутых здесь приемов.
вл, Алфавитное кодирование 6.1. Алфавитное кодирование Кодирование Г может сопоставлять код всему сообщению из множества Я как единому целому или же строить код сообщения из кодов его частей. Элементарной частью сообщения является одна буква алфавита А. Этот простейший случай рассматривается в этом и следующих двух разделах.
6.1.1. Префикс и постфикс слова Пусть задано конечное множество А = (ам..., а„), которое называется алфавитом. Элементы алфавита называются буквами. Последовательность букв называется словом (в данном алфавите). Множество слов в алфавите А обозначается А'. Если слово а = а1.'.. аь 6 А*, то количество букв в слове называется длиной слова: )а~ = ~а1...
аь( = Й. Пустое слово обозначается Л: Л 6 А*, ~Л~ = О, Л к А. Если а = а1аз, то ад называется началам, или префиксам, слова а, а аз — окончанием, или постфиксвм, слова а. Если при этом а1 ф Л (соответственно, аз эе Л), то а1 (соответственно, аз) называется собственным началом (соотвественно, собственным окончанием) слова а.
6.1.2. Таблица кодов Алфавитное (или побуквенное) кодирование задается схемой (или таблицей кодов) сч а:=(аз -+ А,...,а » 4,), а; 6 А, Д 6 В*. Множество кодов букв У: =(~Ц называется множеством элементарных кодов. Алфавитное кодирование пригодно для любого множества сообщений Я: Р: А' » В', а;,... аи» - — а 6 А', Г(а): = 8п... Д». Пример Рассмотрим алфавиты А:=(0,1,2,3,4,5,6,7,8,9), В:=(О,Ц и схему 3: =(О -+ 0,1 -» 1,2 -+ 10,3 » 11,4 -» 100,5 -+ 101,6 -+ 110, 7 » 111, 8 -+ 1000, 9 -+ 1001).
Эта схема однозначна, но кодирование не является взаимно однозначным: Рл(ЗЗЗ) = 111111 = Гл(77), а значит„невозможно декодирование. С другой стороны, схема 5: =(О -+ 0000,1 » 0001,2 -+ 0010,3 -+ 0011,4 » 0100,5 -+ 0101,6 -» 0110, 7 -+ 0111,8 -+ 1000, 9 -+ 1001), известная под названием «двоична-десятичное кодирование», допускает одно- значное декодирование. 162 Вввв 6. Кодирование 6.1.3.
Разделимые схемы Рассмотрим схему алфавитного кодирования а и различные слова, составленные из элементарных кодов. Схема о- называется разделимой, если А, .А, =Агд Р1, =Ф(с=~й~~те ЕЬи=3о то есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды. Алфавитное кодирование' с разделимой схемой допускает декодирование.
Если таблица кодов содержит одинаковые элементарные коды, то есть если где А,333 6 Ъ', то схема заведомо не является разделимой. Такие схемы дзлее не рассматриваются, то есть 'т'3 ~ З А, 333 Е 1' =ь А Ф Я 6.1.4. Префиксные схемы Схема о- называется лрефиксной, если элементарный код одной буквы не является префиксом элементарного кода другой буквы: (т 3 3ь У А, Ц е Ъ ) ~ (т /3 е В А Р 33333). ТЕОРЕМА Лрефиксная схема является разделимой. Доклзлтвльство От противного.
Пусть кодирование со схемой а не является разделимым. Тогда сугцествует такое слово 33 6 Г (А'), что 33 = А,... А, = Д~, ... Д~, лс(дг У в (в с Г =~ А. = 333. 8с А, ть Я~)). Поскольку А,... А, = 333,... оп значит, 333' (А, = 33л33' ч 333, — — А,33'), но это противоречит тому, что схема префиксная. П ЗАМЕЧАНИЕ Свойство быть префикснон ввлнетсн достаточным, во не являетсв пеоохолимым для разделимости схемы.
Пример Разделимая, но не префнксная схема: А = (а,Ь), В = (О,Ц, а = (а -+ О Ь вЂ” ь ОЦ. 16З 6.1. Алфавитное кодирование 6.1.5. Неравенство Макмиллана Чтобы схема алфавитного кодирования была разделилюй, необходимо, чтобы длины элементарных кодов удовлетворяли определенному соотношению, известному как неравенство Макмиллана. ТЕОРЕМА Если схема с = (а1 -т 1У;),".
т разделима, тао 1 — < 1, гдв 11: = ~)11~. ;=1 ' Доказательство Обозначим 1: = шах 1о Рассмотрим п-ю степень левой части неравенства 1=1 (~2 1') . г=1 Раскрывая скобки, имеем сумму ~. (2"-"и-Г', (гт,...,э ) где тт,..., т„— различные наборы номеров элементарных кодов. Обозначим через и(п, 1) количество входящих в эту сумму слагаемых вида 1/21, где $ = Ц, + +1,„. Для некоторых 1 может быть, что и(п, ~) = О. Приводя подобные, имеем сумму и(п, 1) 2' 1=1 Каждому слагаемому вида (2" +"'+" ) ' можно однозначно сопоставить код (слово в алфавите В) вида Д,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
