Кодирование инф. Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки
 Скачать 1.18 Mb.
|
|
КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ПОСОБИЕ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ «ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ» РАЗДЕЛ «КОДИРОВАНИЕ ИНФОРМАЦИИ» КАЗАНЬ 2012 УДК 519.72 Печатается по решению Редакционно-издательского совета ФГАОУВПО «Казанский (Приволжский) федеральный университет» методической комиссии института вычислительной математики и информационных технологий Протокол № 7 от 15 марта 2012 г. заседания кафедры информатики и вычислительных технологий Протокол № 6 от 16 февраля 2012 г. Рецензенты: канд. техн. наук, доц. КНИТУ Шлеймович М.И. канд. физ.-мат. наук, доц. КГУ Широкова О.А. Чепкунова Е.Г. Название: Пособие к подготовке к экзамену по дисциплине «Теоретические остновы информатики». Раздел «Кодирование информации»: Учеб.пособие / Е.Г.Чепкунова. – Казань: Казанский университет, 2012. – 92 с. Данное пособие предназначено студентам специальности «Информатика» для подготовки к экзамену по дисциплине «Теоретические основы информатики». Пособие содержит адаптированный курс лекций по темам раздела «Кодирование информации», методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки. © Казанский университет, 2012 © ЧЕПКУНОВА Е.Г., 2012 Оглавление Введение...........................................................................................5 Теория кодирования: история возникновения..............................6 Теория кодирования: цели, задачи и основные понятия............11 Код. Длина кода. Основание кода. Примеры...............................13 Обратимое и необратимое кодирование. Условие обратимости кодирования....................................................................................16 Код. Средняя длина кода. Относительная избыточность кода.. 19 Асимптотически оптимальный код. Первая теорема Шеннона. .........................................................................................................22 Классификация способов кодирования.......................................25 Неравномерный код с разделителем............................................31 Префиксные коды. Условие Фано. Примеры..............................35 Префиксный код Шеннона-Фано.................................................38 Префиксный код Хаффмана.........................................................43 Арифметическое кодирование......................................................49 Адаптивное арифметическое кодирование.................................54 Хранение чисел в памяти компьютера. Дополнительный код целого положительного числа......................................................57 Хранение чисел в памяти компьютера. Дополнительный код целого отрицательного числа.......................................................60 Хранение чисел в памяти компьютера. Дополнительный код вещественного числа.....................................................................62 Цифровые коды. Двоично-десятичное кодирование..................66 Цифровые коды. Код Грея.............................................................70 Помехоустойчивое кодирование: основная идея, используемые понятия...........................................................................................75 Шифрование. Основные понятия.................................................78 Основные криптографические алгоритмы. Алгоритм замены. 82 Основные криптографические алгоритмы. Алгоритм перестановки..................................................................................85 Основные криптографические алгоритмы. Алгоритм дробления.......................................................................................86 3 Литература......................................................................................89 Интернет-источники......................................................................90 Приложение 1. Оригинальный код Бодо..............................91 Приложение 2. Таблица частотности букв русского языка. ..................................................................................................92 4 Введение Данное пособие предназначено студентам специальности «Информатика» для подготовки к экзамену по дисциплине «Теоретические основы информатики». Пособие содержит теоретический материал раздела «Кодирование информации» соответствующий содержанию указанной дисциплины в Государственных образовательных стандартах. Формулировка каждого параграфа данного пособия совпадает в вопросом экзамена. Параграф включает в себя план ответа на один вопрос итогового экзамена по указанной дисциплине, краткий теоретический материал, который можно использовать при ответе, и вопросы для самопроверки. Представленная информация не является исчерпывающей при подготовке к экзамену по курсу «Теоретические основы информатики» — она содержит лишь методические указания для подготовки к ответу и основное содержание ответа. При необходимости, студент может воспользоваться дополнительной информацией источников, указанных в разделе «Литература». 5 Теория кодирования: история возникновения. При ответе на данный вопрос необходимо рассказать об истории возникновения различных способов кодирования и шифрования информации, сформулировать и пояснить на примерах требования к шифру Ф.Бекона. Теория кодирования — это раздел теории информации, изучающий способы отображения дискретных сообщений сигналами в виде определенных сочетаний символов. С глубокой древности люди искали эффективные способы передачи информации: • Движение факелов использовал древнегреческий историк Полибий (II в. до н.э.}; Рис.1 Схема кодирования букв греческого алфавита с помощью двух групп факелов. • Оптический телеграф – семафор – впервые использовал 6 Клод Шапп в 1791 г.; Рис.2 Оптический семафор К.Шаппа и его телеграфный алфавит. • Движение электромагнитной стрелки в электромагнитных телеграфных аппаратах впервые применили русский физик П.Л. Шиллинг (1832) и профессора Гёттингенского университета Вебер и Гаусс (1833); Рис.3 Схема электромагнитного телеграфа П.Л.Шиллинга (1 — источник тока, 2 — клавиатура, 3 — магнитные стрелки, 4 — провод обратной связи, 5 — вызывное устройство) 7 • Азбука и телеграфный аппарат Самюэла Морзе (1837); Рис. 4 Дерево кода Морзе - направо точка, налево тире. • Международный флажковый код для передачи информации оптическими сигналами впервые ввел капитан Фредерик Марьят в 1861 г. на основе свода корабельных сигналов; Рис.5 Морская азбука сигнальных флажков 8 • Беспроволочный телеграф (радиопередатчик) был изобретен А.С.Поповым в 1895 г. И Маркони в 1897 г. независимо друг от друга; Рис.6а Схема прибора Попова: Т — трубочка с железными опилками; К — колокол звонка; М — молоточек; А — аккумулятор, подающий ток в трубочку с опилками; Э1 и Э2 — электромагниты; П — железная пластинка. Рис. 6б Схема беспроволочного телеграфа Маркони. Слева 9 отправительная станция (передатчик): B — батарея аккумуляторов, I — индукционная катушка, S — вибратор, A — антенна с металлическим баком на конце, M — мачта, E — цинковыq лист, зарытый в землю. Справа — приемная станция: T — трубочка с никелевыми и серебряными опилками; G — батарея, подающая в трубочку ток; R -электрическийзвонок • Беспроволочный телефон, телевидение (1935), затем и ЭВМ – новые средства связи, появившиеся в XX в., с которыми связана новая эпоха в информатизации общества. Одновременно с потребностью передавать информацию люди искали способы скрыть смысл передаваемых сообщений от посторонних любопытных глаз. Императоры, торговцы, политики и шпионы искали способы шифрования своих посланий. Образцы тайнописи можно встретить еще у Геродота (V в. до н. э.). К тайнописи – криптографии прибегал Гай Юлий Цезарь, заменяя в своих тайных записях одни буквы другими. Использовали шифрование не только древнегреческие жрецы, но и ученые Средневековья: математики итальянец Джероламо Кардано и француз Франсуа Виет, нидерландский гуманист, историк, юрист Гроций, выдающийся английский философ Фрэнсис Бэкон. Отцом криптографии считается архитектор Леон Баттиста Альберти (1404-1472), который ввел шифрующие коды и многоалфавитные подстановки. Сэр Фрэнсис Бэкон (1561 – 1626), автор двухлитерного кода, доказал в 1580 г., что для передачи информации достаточно двух знаков. Также Ф.Бэкон сформулировал требования к шифру: 1. Шифр должен быть несложен, прост в работе; 2. Шифр должен быть надежен, труден для дешифровки 10 посторонним; 3. Шифр должен быть скрытен, по возможности не должен вызывать подозрений. Шифры Бэкона – сочетание шифрованного текста с дезинформацией в виде нулей. Таким образом, двузначные коды и шифры использовались задолго до появления ЭВМ. Новый толчок развитию теории кодирования дало создание в 1948 году Клодом Эльвудом Шенноном (1916 — 2001) теории информации. Идеи, изложенные Шенноном в статье «Математическая теория связи», легли в основу современных теорий и техник обработки, передачи и хранения информации. Результаты его научных исследований способствовали развитию помехоустойчивого кодирования и простых методов декодирования сообщений. Вопросы для самопроверки: 1. Перечислите основные способы передачи информации, расположив их в хронологическом порядке. 2. Расскажите об истории возникновения криптографии. 3. Сформулируйте основные требования к шифру Ф.Бекона. Теория кодирования: цели, задачи и основные понятия. При ответе на данный вопрос необходимо рассказать о целях теории кодирования, сформулировать основную задачу кодирования, определить понятия «код», «первичный алфавит», «вторичный алфавит», «кодирование», «декодирование». На сегодняшний день основными целями теории кодирования являются: 11 • Разработка принципов наиболее экономного представления информации; • Согласование параметров передаваемой информации с особенностями канала связи; • Разработка приемов повышения надежности передачи информации. Задача кодирования – это задача перевода дискретного сообщения из одного алфавита в другой. Причем такое преобразование не должно приводить к потере информации. Алфавит, с помощью которого представляется информация до преобразования называется первичным, а алфавит конечного представления – вторичным. При определении понятия «код» используют два подхода. С одной стороны, код — это правило, описывающее соответствие знаков или их сочетаний первичного (исходного) алфавита знакам или их сочетаниям вторичного алфавита. Также кодом называют набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита. Кодирование – это перевод информации, представленной символами первичного алфавита в последовательность кодов. Декодирование – операция обратная кодированию — перевод последовательности кодов в соответствующий набор символов первичного алфавита. Кодер – устройство, обеспечивающее выполнение операции кодирования. Декодер – устройство, производящее декодирование. Рассмотрим несколько примеров кодирования: 12 • перевод письменного текста с одного естественного языка на другой (в этом случае первичный алфавит — алфавит языка, на котором написан текст, вторичный алфавит — алфавит языка перевода); • ввод и сохранение текста на компьютере (первичный алфавит — алфавит используемого естественного языка, вторичный алфавит — набор двоичных цифр {0; 1}); • флажковый семафор (первичный алфавит — алфавит используемого естественного языка, вторичный алфавит — совокупность различных положений рук (флажков) по отношению к туловищу сигнальщика) Вопросы для самопроверки: 1. Подберите примеры для иллюстрации каждой из целей теории кодирования. 2. Поясните на конкретном примере двоиственность понятия «код». 3. Определите первичный и вторичный алфавит при кодировании сообщения, написанного на русском языке, посредством азбуки Морзе. Код. Длина кода. Основание кода. Примеры. При ответе на этот вопрос необходимо дать определение понятиям «код», «длина кода», «основание кода», привести примеры определения длины и основания кода для различных способов кодирования и различных кодовых признаков. Правило или совокупность правил, в соответствии с которыми производится отображение дискретных сообщений сигналами в виде определенных сочетаний символов вторичного 13 алфавита, называют кодом. Будем полагать, что источник выдает некоторое дискретное сообщение а, которое можно рассматривать как последовательность элементарных сообщений а i (i = 1, 2, ..., l). Эти элементарные сообщения будем называть символами сообщений, а их совокупность {а i } - алфавитом источника. Кодирование заключается в том, что последовательность символов источника а заменяется последовательностью кодовых символов - кодовой комбинацией (кодовым словом). Общее число символов, составляющих кодовую комбинацию, называется значностью, или длиной кода n. Количество значений кодовых признаков, используемых в кодовых комбинациях, называется основанием кода m. Рассмотрим примеры: На рисунке 7 приведен пример кодовой комбинации с длиной кода п = 5. В качестве импульсного признака здесь использована величина импульсов U i . Основание кода (число значений импульсного признака) т = 3. Рис.7 Пример кодовой комбинации с величиной импульсов U i (i = 1..5) На рисунке 8 приведена кодовая комбинация с n = 5 и m= 3, 14 в которой в качестве импульсного признака используется длительность импульсов t i Рис.8 Пример кодовой комбинации с длительностью импульсов t i На ленте машины Поста для обозначения целых положительных чисел используется правило: число n задается (кодируется) n+1 меткой. Тогда число 5, помещенное на ленте машины Поста, может быть интерпретировано как кодовая комбинация с длиной кода п = 6 и основанием кода т = 1 (число используемых меток — символов вторичного алфавита): Рис.9 Число 5 на ленте машины Поста Вопросы для самопроверки: 1. Что являлось символами сообщений при записи информации на магнитную ленту? 2. Определите значность и длину кода, если кодирование представляет собой перевод десятичного числа 20 в двоичную систему счисления. 3. Определите значность и длину кода, если сообщение а — монохромное изображение размером 240*320 пикселей . 15 Обратимое и необратимое кодирование. Условие обратимости кодирования. При ответе на этот вопрос необходимо дать определение понятиям «кодирование» и «декодирование», привести примеры обратимого и необратимого кодирования, сформулировать условие обратимости кодирования и записать его математический вид. Кодирование — перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов. Процесс обратного преобразования слова называется декодированием. Декодирование можно рассматривать как функцию F -1 – обратную функции F – кодированию. Декодирование — операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов. Операции кодирования и декодирования называются обратимыми, если их последовательное применение не приводит к потере информации. Примером обратимого кодирования является телеграф. Также к обратимому кодированию относят сжатие информации без потерь, помехоустойчивое кодирование. Необратимое кодирование происходит при переводе с одного естественного языка на другой, при сжатии с потерями, при аналого-цифровом преобразовании. Необратимое кодирование можно подвергнуть более детальной классификации. Различают принципиально необратимое, обратимое с помощью дополнительной информации и безусловно обратимое кодирование. 16 Принципиально необратимое кодирование (хэширование) используется, например, в операционных системах для хранения паролей. При первоначальном вводе пароль преобразуется с помощью так называемых односторонних функций (хэш- функций), подобранных таким образом, чтобы из полученной на их выходе строки принципиально нельзя было получить первоначальное значение пароля. При дальнейшем использовании пароль каждый раз преобразуется такой же функцией и сравнивается с первоначальным хэшем. При их совпадении делается вывод о правильности ввода пароля. Объем полученной в итоге информации равен ровно одному биту: пароль совпал либо не совпал. В некоторых случаях этого может оказаться недостаточно, поэтому гораздо чаще используется кодирование, обратимое с помощью дополнительной информации (ключа шифрования). Входная информация преобразуется с помощью пароля таким образом, чтобы обратное преобразование также требовало знания пароля (простейший пример такого преобразования - операция исключающего ИЛИ между байтами исходного текста и байтами пароля). Именно этот способ обычно используется при шифровании архивов. Наконец, последний случай - |