Файл: Технологии программирования (Возникновение теории кодирования).pdf

ВВЕДЕНИЕ

Целью написания курсовой работы является изучение основных методов кодирования данных в информационных системах и определение связи с такими научными дисциплинами, как теория кодирования и теория информации.

Предметом является совокупность процессов преобразования данных в иную форму, предназначенную для хранения в памяти компьютера, а так же, передачи и защиты от несанкционированного доступа.

При написании курсовой были использованы различные учебники по теории информации, кибернетике, алгоритмам, сжатию информации и прочим, связанным с технологиями программирования, дисциплинам.

Помимо учебников были изучены переводы статей, написанных авторами исследуемых теорий.

1. Сущность кодирования данных в информационных системах.

1.1 Возникновение теории кодирования

Теория кодирования и теория информации возникли в начале XX века.

Теория информации это раздел прикладной математики, радиотехники (теория обработки сигналов) и информатики, относящийся к измерению количества информации, её свойств и устанавливающий предельные соотношения для систем передачи данных. Как и любая математическая теория, она оперирует математическими моделями, а не реальными физическими объектами (источниками и каналами связи). Использует, главным образом, математический аппарат теории вероятностей и математической статистики. [2]

Суть теории кодирования заключается в решении задачи выбора (отыскания) кода, оптимального по тому или иному критерию.[4]

Начало развитию этих теорий как научных дисциплин положило появление в 1948 г. Статей Клода Шеннона, которые заложили фундамент для дальнейших исследований в этой области.

Само понятие теории информации появилось задолго до публикации этой статьи. Множество авторов своими работами создавали базу для новой теории. К примеру, в 1924 году в журнале компании «Bell System» была публикация Найквиста, которая содержала в себе некоторые положения, послужившие основой для данной статьи.[12]

При публикации Шеннон не думал, что она станет важным открытием. Математик в значительной мере опирался на опыт предшественников. Выделяя это, он в самом начале статьи пишет: «Некоторые основные положения этой теории имеются в важных работах Найквиста и Хартли. В настоящей статье мы расширим теорию с тем, чтобы включить некоторое число новых факторов, в частности, влияние шума в канале»[5]

1.2 Модель передачи данных

По мнению Шеннона, теория информации — раздел математической теории связи. Теория информации определяет основные границы возможностей систем передачи информации, задает первичные принципы их разработки и практического применения. Задачи теории информации представляются с помощью структурной схемы, стандартной системы передачи или хранения информации. [9] Схема системы связи изображена на рисунке 1 в приложении.

Источником в схеме является любой объект, формирующий сообщения, передающиеся во времени и пространстве. Все подлежащие передаче сообщения, независимо от их изначальной физической природы, преобразовываются в форму электрических сигналов, которые являются - выходом источника.

Кодер источника представляет эти электрические сигналы в наиболее компактном виде.

Кодер канала обрабатывает полученную информацию для предохранения сообщений от помех при передаче по каналу связи или возможных искажений при хранении данных.

Модулятор перерабатывает информацию, созданную кодером канала, в сигналы, согласованные с физической природой канала связи или средой накопителя информации.

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

Блоки, на стороне приёмника действуют в обратном порядке по той же схеме, в итоге предоставляя получателю исходную информацию в удобном для понимания формате.

Сложность трансляции информации не зависит от его сути, так передавать сообщения, не имеющие смысловой нагрузки одинаково сложно, как и осмысленные.

Информацию можно выразить и как свойство объектов, и как результат их взаимодействия. Факт объективного существования информации независимо от нашего сознания для некоторых исследователей послужил поводом построения весьма неординарной точки зрения, что информация является третьей (наряду с материей и энергией) субстанцией материального мира. Но для информации пока не сформулировано фундаментальных законов сохранения и перехода в эквивалентное количество материи и/или энергии. На данный момент принято считать, что информация существует независимо от того, воспринимается она или нет, но проявляется только при взаимодействии.

1.3 Понятие кодирования информации

Другой вариант изображения «модели системы передачи сигналов» показан на рисунке 2.

Начальным звеном в приведенной модели является источник информации.

Рассмотрим дискретные источники без памяти, в которых выходом является последовательность символов некоторого фиксированного алфавита.

Множество всех различных символов, порождаемых некоторым источником, называется алфавитом источника, количество символов в этом множестве – размер алфавита источника.

Например, текст на русском языке порождается источником с алфавитом из 33 русских букв, пробела и знаков препинания.

Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам некоторого другого алфавита В.

Обычно символу исходного алфавита А ставится в соответствие не один, а группа символов алфавита В, которая называется кодовым словом.

Кодовый алфавит – множество различных символов, используемых для записи кодовых слов.

Кодом называется совокупность всех кодовых слов, применяемых для представления порождаемых источником символов. Например, азбука Морзе является известным кодом из символов телеграфного алфавита, в котором буквам русского языка соответствуют кодовые слова (последовательности) из «точек» и «тире».

Далее будем рассматривать двоичное кодирование, т.е. размер кодового алфавита равен 2.

Конечную последовательность битов (нулей или единиц) назовем кодовым словом, а количество битов в этой последовательности – длиной кодового слова.

Например код ASCII (американский стандартный код для обмена информацией) каждому символу ставит в однозначное соответствие кодовое слово длиной 8 бит. Пример таблицы ASCII можно посмотреть на рисунке 3.

Кодирование  — это процесс преобразования данных из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения, автоматической переработки и сохранения от несанкционированного доступа. [4] К основным проблемам теории кодирования относят вопросы взаимной однозначности кодирования и сложности реализации канала связи при заданных условиях  

В связи с развитием информационных технологий кодирование является центральным вопросом при решении самых разных задач программирования, таких как:

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

Дадим строгое определение кодирования.

Пусть даны алфавит источника A = {a1,a2,…an}, кодовый алфавит B = {b1,b2,…,bn}.

Обозначим через A* множество всевозможных последовательностей в алфавите А. Множество всех сообщений в алфавите А обозначим S. Тогда отображение F: S→B*, которое преобразует множество сообщений S в кодовые слова в алфавите В, называется кодированием. Обратное отображение F-1 (если оно существует) называется декодированием.

Задача кодирования сообщения ставится следующим образом:

требуется при заданных алфавитах А и В и множестве сообщений S найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле.

Свойства, которые требуются от кодирования, могут быть различными. Некоторые из них:

• существование декодирования;
• помехоустойчивость или исправление ошибок при кодировании;
• заданная трудоемкость (время, объем памяти).

Известны два класса методов кодирования дискретного источника информации: равномерное и неравномерное кодирование.

Под равномерным кодированием понимается использование кодов со словами постоянной длины. Для того чтобы декодирование равномерного кода было возможным, разным символам алфавита источника должны соответствовать разные кодовые слова. При этом длина кодового слова должна быть не меньше log_nm символов, где m – размер исходного алфавита, n – размер кодового алфавита.

Пример.

Для кодирования источника, порождающего 26 букв латинского алфавита, равномерным двоичным кодом требуется построить кодовые слова длиной не меньше log_nm=5 бит.

При неравномерном кодировании источника используются кодовые слова разной длины. Причем кодовые слова обычно строятся так, что часто встречающиеся символы кодируются более короткими кодовыми словами, а редко встречающиеся символы – более длинными кодовыми словами. За счет этого и достигается «сжатие» данных.

Под сжатием данных понимается компактное представление данных, достигаемое за счет избыточности информации, содержащейся в сообщениях.

Большое значение для практического использования имеет неискажающее сжатие, позволяющее полностью восстановить исходное сообщение.

При неискажающем сжатии происходит кодирование сообщения перед началом передачи или хранения, а после окончания процесса сообщение однозначно декодируется. Это соответствует модели канала без шума (помех).

Методы сжатия данных можно разделить на две группы:

• статические методы;
• адаптивные методы.

Статические методы сжатия данных предназначены для кодирования конкретных источников информации с известной статистической структурой, порождающих определенное множество сообщений.

Эти методы базируются на знании статистической структуры исходных данных.

К наиболее известным статическим методам сжатия относятся коды Хаффмана, Шеннона - Фано, Гилберта-Мура, арифметический код и другие методы, которые используют известные сведения о вероятностях порождения источником различных символов или их сочетаний.

Если статистика источника информации неизвестна или изменяется с течением времени, то для кодирования сообщений такого источника применяются адаптивные методы сжатия.

В адаптивных методах при кодировании очередного символа текста используются сведения о ранее закодированной части сообщения для оценки вероятности появления очередного символа.

В процессе кодирования адаптивные методы «настраиваются» на статистическую структуру кодируемых сообщений, т.е. коды символов меняются в зависимости от накопленной статистики данных.

Это позволяет адаптивным методам эффективно и быстро кодировать сообщение за один просмотр.

В данной главе мы рассмотрели понятия двух основополагающих теорий – теории информации и теории кодирования. Был определён ключевой момент в истории, положивший фундамент в развитии рассматриваемого направления информатики. Так же была описана основная модель системы передачи данных от отправителя до получающей стороны. И в итоге было выведено понятие кодирования информации: на каком этапе передачи данных оно происходит, какие решает задачи, на какие методы условно делится.

Описанное выше раскрывает сущность кодирования данных, его основные вопросы и процессы. В связи с этим глава и имеет соответствующее название.

Если формулировать основные причины, по которым кодирование информации необходимо и актуально в наше время, на мой взгляд, это будут передача информации по каналам связи и защита её от несанкционированного доступа. Примеры основных методов кодирования данных будут представлены в следующей главе.