Добавлен: 26.06.2023
Просмотров: 93
Скачиваний: 3
Введение
Актуальность темы обусловлена тем, что получение, передача, обработка и хранение информации - это одна из наиболее динамично развивающихся и перспективных областей человеческой деятельности.
Теория информации как наука существует с середины ХХ века, с момента появления основополагающей работы – Клод Шеннон: «Математическая теория связи» (1948) – прошло чуть более 60 лет. У Шеннона (1916 – 2001) были предшественники, например, Р. Хартли, впервые предложивший в 1928 году количественную меру информации, или В. А. Котельников, сформулировавший в 1933 году важнейшую теорему о возможности представления непрерывной функции совокупностью ее значений в отдельных точках отсчета. Были и современники, и последователи, например, А. Н. Колмогоров, внесший большой вклад в статистическую теорию колебаний, являющуюся математической основой теории информации. Работы по развитию теории информации продолжаются и в настоящее время.
Теория информации быстро разделилась на фундаментальную и прикладную.
Разработка конкретных методов и средств кодирования относятся к прикладной теории информации, которая занимается изучением любых процессов, связанных с получением, передачей, хранением, обработкой и использованием информации.
Фундаментальная теория информации – это:
– анализ сигналов как средства передачи сообщений и оценка переносимого «количества информации»;
– анализ информационных характеристик источников сообщений и каналов связи и обоснование принципиальной возможности кодирования и декодирования сообщений, обеспечивающих предельно допустимую скорость передачи сообщений по каналу связи, как при отсутствии, так и при наличии помех.
Существует множество определений понятия информация, от наиболее общего философского (информация есть отражение реального мира), до узкого практического (информация есть все сведения, являющиеся объектом хранения, передачи и преобразования).
Имеется множество точек зрения на суть информации, одна из которых рассматривает информацию как некоторую философскую категорию, такую же общую, как понятия материи или энергии (Н. Винер).
Существует ли информация независимо от того, воспринимается ли она, зависит ли ее восприятие от индивидуальных способностей воспринимающего?
Противоречие частично снимается, если рассматривать информацию как некое потенциальное свойство объекта (системы).
Информация существует только в форме материально-энергетических сигналов. Причем, с точки зрения теории, безразлично, в какой конкретной форме эта информация передается. Информацию, представленную в формализованном виде, позволяющем осуществить ее обработку с помощью технических средств, называют данными.
Кодирование данных как процесс: любому дискретному сообщению или знаку можно приписать какой-либо порядковый номер. Измерение аналоговой величины, выражающееся в сравнении ее с образцовыми мерами, также приводит к числовому представлению информации. Передача или хранение сообщений при этом сводится к передаче или хранению чисел.
Общепризнанным в настоящее время является позиционный принцип образования системы счисления. Значение каждого символа (цифры) зависит от его положения – позиции в ряду символов, представляющих число.
Чем больше основание системы счисления, тем меньшее число разрядов требуется для представления данного числа, а значит – меньшее время для его передачи. Однако с ростом основания аппаратура должна иметь большее число устойчивых состояний, соответственно возрастает и стоимость ее создания.
Учитывая статистические свойства источника сообщения, можно минимизировать количество символов, требующееся для выражения одного знака сообщения, что позволяет уменьшить время передачи или объем запоминающего устройства.
В настоящей работе будут рассмотрены следующие вопросы проблематики темы работы: из теории кодирования: основные понятия, задачи; приведена классификация способов кодирования; приведены и изучены кодирование при сжатии данных изображений: вейвлет-кодирование, и методы специального кодирования данных с ограничением длины поля записи.
1 Теория кодирования: основные понятия, задачи. Классификация способов кодирования
С глубокой древности люди искали эффективные способы передачи информации.
Толчок развитию теории кодирования дало создание в 1948 году Клодом Эльвудом Шенноном (1916 — 2001) теории информации. Идеи, изложенные Шенноном в статье «Математическая теория связи», легли в основу современных теорий и техник обработки, передачи и хранения информации.
Результаты его научных исследований способствовали развитию помехоустойчивого кодирования и простых методов декодирования сообщений.
На сегодняшний день основными целями теории кодирования являются:
· Разработка принципов наиболее экономного представления информации;
· Согласование параметров передаваемой информации с особенностями канала связи;
· Разработка приемов повышения надежности передачи информации.
Задача кодирования – это задача перевода дискретного сообщения из одного алфавита в другой. Причем такое преобразование не должно приводить к потере информации.
Алфавит, с помощью которого представляется информация до преобразования называется первичным, а алфавит конечного представления – вторичным.
При определении понятия «код» используют два подхода. С одной стороны, код — это правило, описывающее соответствие знаков или их сочетаний первичного (исходного) алфавита знакам или их сочетаниям вторичного алфавита. Также кодом называют набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита.
Кодирование – это перевод информации, представленной символами первичного алфавита в последовательность кодов.
Декодирование – операция обратная кодированию — перевод последовательности кодов в соответствующий набор символов первичного алфавита.
Кодер – устройство, обеспечивающее выполнение операции кодирования.
Декодер – устройство, производящее декодирование.
Рассмотрим несколько примеров кодирования:
· перевод письменного текста с одного естественного языка на другой (в этом случае первичный алфавит — алфавит языка, на котором написан текст, вторичный алфавит — алфавит языка перевода);
· ввод и сохранение текста на компьютере (первичный алфавит — алфавит используемого естественного языка, вторичный алфавит — набор двоичных цифр {0; 1});
· флажковый семафор (первичный алфавит — алфавит используемого естественного языка, вторичный алфавит — совокупность различных положений рук (флажков) по отношению к туловищу сигнальщика).
Операции кодирования и декодирования называются обратимыми, если их последовательное применение не приводит к потере информации.
Примером обратимого кодирования является телеграф. Также к обратимому кодированию относят сжатие информации без потерь, помехоустойчивое кодирование. Необратимое кодирование происходит при переводе с одного естественного языка на другой, при сжатии с потерями, при аналого-цифровом преобразовании.
Необратимое кодирование можно подвергнуть более детальной классификации. Различают принципиально необратимое, обратимое с помощью дополнительной информации и безусловно обратимое кодирование.
Принципиально необратимое кодирование (хэширование) используется, например, в операционных системах для хранения паролей. При первоначальном вводе пароль преобразуется с помощью так называемых односторонних функций (хэш-функций), подобранных таким образом, чтобы из полученной на их выходе строки принципиально нельзя было получить первоначальное значение пароля. При дальнейшем использовании пароль каждый раз преобразуется такой же функцией и сравнивается с первоначальным хэшем. При их совпадении делается вывод о правильности ввода пароля. Объем полученной в итоге информации равен ровно одному биту: пароль совпал либо не совпал. В некоторых случаях этого может оказаться недостаточно, поэтому, гораздо чаще используется кодирование, обратимое с помощью дополнительной информации (ключа шифрования). Входная информация преобразуется с помощью пароля таким образом, чтобы обратное преобразование также требовало знания пароля (простейший пример такого преобразования – операция исключающего ИЛИ между байтами исходного текста и байтами пароля). Именно этот способ обычно используется при шифровании архивов.
Наконец, последний случай - безусловно обратимое кодирование, в случае которого обратное преобразование не требует знания какой-то дополнительной информации. В подавляющем большинстве случаев для хранения паролей к внешним ресурсам используется именно этот способ. К примеру, почтовому клиенту для получения почты необходимо передать на РОР3-сервер логин и пароль пользователя, который решил доверить их хранение клиенту, поставив соответствующую галочку. Пароль уходит на сервер в открытом виде, какие-то дополнительные пароли при его сохранении взять неоткуда (бессмысленно требовать от пользователя какой-то дополнительный пароль, если он захотел избавиться от ввода основного пароля). В этом случае единственный вариант - использовать как можно более запутанные алгоритмы кодирования и декодирования, которые обеспечат относительную защиту данных.
Существует множество способов классификации способов кодирования.
По условию построения кодовых комбинаций коды делят на равномерные и неравномерные. В равномерных кодах все сообщения передаются кодовыми группами с одинаковым числом элементов (длина кода n = const). Примером такого кода может служить телеграфный код Бодо, который является равномерным пятибитным кодом (n=5). Первоначально код, разработанный Эмилем Бодо (1845 -1903) в 1870 году для своего телеграфа, вводился прямо клавиатурой, состоящей из пяти клавиш, нажатие или ненажатие клавиши соответствовало передаче или непередаче одного бита в пятибитном коде. В 1901 году Дональд Мюррей (1866 - 1945) переработал код, изменил порядок знаков и добавил некоторые дополнительные знаки, адаптировав код Бодо к раскладке современной клавиатуры
QWERTY. Однако общие принципы — пятибитная кодировка и использование буквенного и цифрового регистров — остались неизменными.
При использовании неравномерных кодов разные сообщения могут передаваться кодовыми группами, содержащими неодинаковое число элементов (n = var).
Типичным представителем неравномерного кода является код Морзе, созданный в 1838 году Самюэлем Морзе и подвергавшийся впоследствии неоднократным изменениям. В настоящее время кодом Морзе называют способ знакового кодирования, в котором для представления букв алфавита, цифр, знаков препинания и других символов используется последовательность троичных сигналов, например, длинных и коротких: «тире» и «точек». За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака — одна точка, между знаками в слове — три точки, между словами — семь точек.
Равномерный код обладает большими возможностями с точки зрения обеспечения помехозащищенности передачи, так как потеря элементов или возникновение новых элементов в кодовых комбинациях с n = const могут быть легко обнаружены.
Неравномерные коды могут обеспечить наибольшую экономичность построения кодов и наибольшее быстродействие передачи сообщений. Такие коды используются при так называемом статистическом кодировании. Вместе с тем неравномерные коды менее помехозащищенные, чем равномерные. Потеря или возникновение новых элементов в комбинации в результате действия помех могут привести к созданию новой ложной комбинации, воспринимаемой на приемной стороне как истинная. Неравномерные коды требуют при передаче либо специальных разделительных символов, указывающих конец одной и начало другой кодовой комбинации (например, код Морзе требует наличия разделительного символа), либо же должны строиться так, чтобы никакая кодовая комбинация не явилась началом другой.
По числу уникальных символов, используемых в кодовых комбинациях различают единичные, двоичные и многопозиционные коды. В единичном коде используются одинаковые символы. Кодовые комбинации отличаются друг от друга лишь количеством символов (импульсов). Такие коды называют еще числоимпульсными. Единичные коды используются в машине Поста (для кодирования целых положительных чисел), машине Тьюринга, в цифровых электронных счетчиках, в которых измеряемая величина преобразуется в пропорциональное ей число импульсов.
Единичный код отличается своей простотой. Однако вследствие того, что он неравномерен, помехозащищенность его низкая. Кроме того, при передаче большого количества сообщений происходит изменение в широких пределах длины кода, что вызывает определенные неудобства.
В связи с этим единичный код практически не используется для передачи информации по каналу связи, а используется лишь при промежуточных преобразованиях сигналов на передающей и приемной сторонах.
Наибольшее распространение получили двоичные коды. Это обусловлено следующим. Формирование кодовых сигналов и их дешифрация производятся с помощью релейных устройств, способных занимать ряд устойчивых состояний. Количество таких состояний определяется основанием кода. Очевидно, что простейшими релейными устройствами являются устройства с двумя состояниями. К такого типа устройствам принадлежит большинство электромагнитных, электронных, магнитных и других типов бесконтактных реле. Кроме того, следует также учитывать простоту хранения информации и выполнения арифметических и логических операций при двоичном кодировании.