Файл: Методы кодирования данных (Задача кодирования).pdf

Введение

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

Позднее, еще до нашей эры, появились криптограммы, что в переводе с греческого означает «тайнопись». Такими кодами пользовались для засекречивания сообщений. Уже в V в. до н. э. знаменитый греческий историк Геродот приводил примеры писем-криптограмм, понятных только одному адресату. Спартанцы имели специальный механический прибор, при помощи которого записывались сообщения–криптограммы, позволяющие сохранить тайну. Собственную секретную азбуку имел Юлий Цезарь (широко известный «шифр Цезаря»). В Средние века и эпоху Возрождения над изобретением тайных шифров работали многие выдающиеся умы, в том числе философ Фрэнсис Бэкон, математики Франсуа Виет, Джероламо Кардано. Криптографией занимались в монастырях, при дворах королей. Вместе с искусством шифрования сообщений развивалось и искусство их дешифрования. Многие оптимистично полагали, что вряд ли существует такая криптограмма, которую нельзя разгадать. И только в прошлом веке Клод Шеннон (1949 г.) показал, что существует совершенно секретный шифр – шифр Вернама, называемый также лентой однократного действия или шифром-блокнотом. В настоящее время теория кодирования имеет важное широкое практическое применение как средство экономной, удобной, быстрой, а также надежной передачи сообщений по линиям связи с различного вида шумами (телефон, телеграф, радио, телевидение, компьютерная и космическая связи, и т. д.). Подлинный взрыв развития теории связи начался в послевоенные годы, с 1948–1949 гг., с появлением классических работ Клода Шеннона и Норберта Винера. Труды Н. Винера были порождены исследованиями военного времени по автоматическому управлению огнем, труды К. Шеннона, знаменитые "Математическая теория связи" и "Связь при наличии шума" – исследованиями по шифрованию сообщений и их передачи по секретным каналам связи. Математические модели Н. Винера и К. Шеннона довольно сильно различались: сигнал по Н. Винеру может обрабатываться после воздействия шумом, по К. Шеннону сигнал можно обрабатывать как до, так и после передачи по каналу связи с шумами. В силу этого и других различий, Винеровские труды легли в основу теории автоматического управления, Шенноновские труды оказались основополагающими для задач эффективного использования каналов связи. Таким образом, с 1949 г., с фундаментальных работ К. Шеннона началось бурное развитие теории кодирования, как отдельной научной дисциплины, а также развитие таких тесно с нею связанных научных дисциплин, как сжатие информации и криптология в современном мире. С каждым днем в мире циркулирует все большее количество информации, как письменной, так и числовой, и звуковой.

Не все каналы связи являются совершенными, хоть и соответствуют основным стандартам и требованиям. Причиной всему служит наличие помех на каналах связи. Из за сбоев, при передаче информации между двумя объектами, может возникнуть искаженные дынных. Наиболее помехоустойчив русский язык, например: «По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолена бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы не чиатем кдаужю бкуву по отдльенотси, а все солво цликеом». В данной цитате изменена последовательность букв, но смысл остался понятен.

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

Объект: процессы кодирования данных.

Цель исследования: изучить методы кодирования.

Задачи:

1) рассмотреть основные понятия.

2) изучить методы сетевого кодирования.

3) изучить методы программного кодирования.

4) изучить методы энтропийного кодирования.

5) изучить методы дельта-кодирования.

Глава 1. Теоретические основы

1.1. Задача кодирования

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

Код – соответствие того или иного знака в одной системе символов равному знаку в другой.

Кодирование – это преобразование информации с одного языка на другой, говоря простыми словами - представление в другой системе символов.

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

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

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

Основными задачами кодирования являются:

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

Кодирование является предшественником таких процессов как сбор, передача и хранения информации. При этом хранение - это фиксация информации в некотором состоянии, а передача – изменение с течением времени.

В конце 40-х годов с появлением работ Голея, Хэмминга и Шеннона возникла и сама теория кодирования. Голей и Хэмминг заложили основу алгебраическим методам кодирования, которые используются и по сей день, а Шеннон предложил и исследовал понятие случайного кодирования. Стоит заметить, что в современных информационных системах обеспечение безопасности является важнейшей частью. Настоящий “бум” у ученых и инженеров вызвало появление работ Шеннона. Казалось, решение подобного рода задач на практике будет таким же простым и понятным, как Шеннон сделал это математически. Но весь ажиотаж спал достаточно быстро, так как прямого решения найти не удалось. В то же время, поставленные Шенноном задачи и доказательство фундаментальных теорем теории информации дали толчок для поиска решения задач с использованием детерминированных (неслучайных) сигналов и алгебраических методов помехоустойчивого кодирования (защиты от помех и шифрование для обеспечения секретности информации).

В 50-е,70-е годы было разработано большое количество алгебраических кодов с исправлением ошибок, среди которых наиболее востребованными стали коды Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Соломона (РС), Рида-Малера, Адамара, Юстенсена, Гоппы, циклические коды, сверточные коды с разными алгоритмами декодирования (последовательное декодирование, алгоритм Витерби), арифметические коды.

1.2. Сжатие данных

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

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

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

1.3. Принципы сжатия данных

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

Все методы сжатия данных делятся на два основных класса:

1.3.1Сжатие без потерь.

Сжатие данных без потерь (англ. lossless data compression) – метод сжатия данных (видео, аудио, графики, документов, представленных в цифровом виде), при использовании которого закодированные данные однозначно могут быть восстановлены с точностью до бита, пикселя, вокселя и т.д. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь. Сжатие данных без потерь используется во многих приложениях. Например, оно используется во всех файловых архиваторах. Оно также используется как компонент в сжатии с потерями. Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример – исполняемые файлы и исходный код. Некоторые графические файловые форматы (например PNG) используют только сжатие без потерь, тогда как другие (TIFF, FLIF или GIF) могут использовать сжатие как с потерями, так и без потерь.

1.3.2 Сжатие с потерями

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

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

1.4. Сжатие с потерями против сжатия без потерь

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

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

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

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