Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
 Скачать 0.89 Mb.
|
|
Большинство программ-архиваторов сжимает каждый файл по отдельности, но некоторые сжимают файлы в общем потоке, что дает увеличение степени сжатия, но одновременно усложняет способы работы с полученным архивом, например, замена в таком архиве файла на его более новую версию может потребовать перекодирования всего архива. Примером программы, имеющей возможность сжимать файлы в общем потоке, является RAR. Архиваторы ОС Unix (gzip, bzip2, ...) сжимают файлы в общем потоке практически всегда. В 1992 году фирма WEB Technologies объявила о выходе новой программы сжатия DataFiles/16, которая якобы может при неоднократном использовании сжать любое количество данных до 1024 байт. Информация об этом прошла из солидного издания, журнала Конечно же никакой алгоритм сжатия не может уплотнить произвольные данные. Для доказательства этого проделаем следующий мысленный эксперимент. Предположим, что на жестком диске компьютера хранятся всевозможные разные файлы длиной ровно 100 байт (таких файлов будет всего 2 800 ). И пусть существует идеальная программа сжатия данных, которая сожмет каждый из них хотя бы на один байт. Но тогда, так как всего разных файлов длиной меньшей 100 байт существует не более чем 1 + 2 8 + 2 16 + · · · + 2 792 = (2 800 − 1)/255 < 2 то неизбежно получится, что два разных файла упакуются в идентичные файлы. Следовательно, не может существовать программы сжатия данных, которая может сжать любые исходные данные. Формат файла, содержащего данные, которые перед использованием требуется распаковать соответствующей программой-архиватором, как правило, может быть идентифицирован расширением имени файла. В следующей таблице приводятся некоторые типичные расширения, соответствующие им программы-архиваторы и методы сжатия данных. Расширения Программы Тип кодирования arc, pkarc LZW, Хаффмена zip zip, unzip, pkzip, pkunzip LZW, LZ77, Хаффмена, Шеннона-Фэно gz gzip LZ77, Хаффмена bz2 bzip2 Берроуза-Уиллера, Хаффмена arj arj LZ77, Хаффмена ice, lzh lha, lharc LZSS, Хаффмена pak Практически все форматы файлов для хранения графической информации используют сжатие данных. Формат графического файла также, как правила, идентифицируется расширением имени файла. В следующей таблице приводятся некоторые типичные расширения графических файлов и соответствующие им методы сжатия данных Расширения Тип кодирования gif LZW jpeg, jpg сжатие с потерями, Хаффмена или арифметическое bmp, pcx RLE tiff, tif CCITT/3 для факсов, LZW или другие Сжатие RLE (Run Length Encoding — кодирование переменной длины) — это простейший метод сжатия, в общем случае очень неэффективный, но дающий неплохие результаты на типичной графической информации. Оно основано в основном на выделении специального кода-маркера, указывающего сколько раз повторить следующий байт. Сжатие и распаковка в реальном времени используется в програм- мах-драйверах для уплотнения носителей информации, позволяющих увеличить емкость носителя приблизительно в 2 раза. Наиболее известной программой такого рода является DriverSpace для MS-DOS и Mic- rosoft Windows. 18. Сжатие информации с потерями Все ранее рассмотренные алгоритмы сжатия информации обеспечивали возможность полного восстановления исходных данных. Но иногда для повышения степени сжатия можно отбрасывать часть исходной информации, те. производить сжатие с потерями. Естественно, что такое сжатие нельзя проводить, например, на финансовой базе данных банка. Нов тех случаях, когда сжимается информация, используемая лишь для качественной оценки (это, как правило, аналоговая информация, сжатие с потерями является очень подходящим. Сжатие с потерями используется в основном для трех видов данных полноцветная графика (2 24 ≈ 16 млн. цветов, звуки видеоинфор- мация. Сжатие с потерями обычно проходит в два этапа. На первом из них исходная информация приводится (с потерями) к виду, в котором ее можно эффективно сжимать алгоритмами го этапа сжатия без по- терь. Основная идея сжатия графической информации с потерями заключается в следующем. Каждая точка в картинке характеризуется тремя равноважными атрибутами яркостью, цветом и насыщенностью. Но глаз человека воспринимает эти атрибуты не как равные. Глаз воспринимает полностью только информацию о яркости ив гораздо меньшей степени о цвете и насыщенности, что позволяет отбрасывать часть информации о двух последних атрибутах без потери качества изображения. Это свойство зрения используется, в частности, в цветном телевизоре, в котором на базовое черно-белое изображение наносят цветовую раскраску Для сжатия графической информации с потерями в конце х установлен один стандарт — формат JPEG (Joint Photographic Experts Group — название объединения его разработчиков. В этом формате можно регулировать степень сжатия, задавая степень потери качества. Сжатие видеоинформации основано на том, что при переходе от одного кадра фильма к другому на экране обычно почти ничего не меняется. Таким образом, сжатая видеоинформация представляет собой запись некоторых базовых кадров и последовательности изменений в них. При этом часть информации может отбрасываться. Сжатую подобным образом информацию можно далее сжимать и другими методами. Хотя существует не один стандарт для сжатия видеоданных, наиболее распространенными являются стандарты MPEG (Motion Picture Ex- perts Group), первый из которых был опубликован в 1988 году. MPEG — практически единственный стандарт для записи видео и звуковой информации на CD-ROM, DVD-ROM ив цифровом спутниковом телевидении. Видеоинформацию можно сжать необыкновенно плотно, дои более раз, что позволяет, например, на одну видеокассету, записать более ста различных художественных фильмов. Но из-за очень сложных проблем, связанных с правами на интеллектуальную собственность, реально возможности сжатия информации таким образом используются сравнительно редко. Для сжатии звуковой информации с потерями существует несколько стандартов. Наиболее широко используемый из них — это без видеоданных. Стандарт LPC (Linear Predictive Coding) используется для сжатия речи. Алгоритм LPC пытается промоделировать речевой тракт человека и выдает на выходе буквально текущее состояние участвующих в формировании звуков органов. Информационный канал Канал информационный — это совокупность устройств, объединенных линиями связи, предназначенных для передачи информации от источника информации (начального устройства канала) до ее приемника (конечного устройства канала). Линии связи обеспечивают прохождение информационных сигналов между устройствами канала. Информация обычно передается при помощи электрического тока (по проводам, света (по оптоволокну), электромагнитных волн радиодиапазона (в пространстве) и, редко, звука (в плотной среде атмосфере, воде и т.п.) и прочих. Устройства канала — это, как правило, репитеры, просто передающие усиленным принятый сигнал (пример, радиорелейные линии). К устройствам канала иногда относят и кодеры/декодеры, нов только тех случаях, когда кодирование/декодирование происходит с высокой скоростью, не требующей ее специального учета, как замедляющего фактора обычно же кодеры/декодеры относят к источникам или приемникам информации. Технические характеристики канала определяются принципом действия входящих в него устройств, видом сигнала, свойствами и составом физической среды, в которой распространяются сигналы, свойствами применяемого кода. Эффективность канала характеризуется скоростью и достоверностью передачи информации, надежностью работы устройств и задержкой сигнала во времени. Задержка сигнала во времени — это интервал времени от отправки сигнала передатчиком до его приема приемником. Математически канал задается множеством допустимых сообщений на входе, множеством допустимых сообщений на выходе и набором условных вероятностей P (y/x) получения сигнала y на выходе при входном сигнале x. Условные вероятности описывают статистические свойства шумов (или помех, искажающих сигнал в процессе передачи. В случае, когда P (y/x) = 1 при y = x и P (y/x) = 0 при y = канал называется каналом без шумов. В соответствии со структурой входных и выходных сигналов выделяют дискретные и непрерывные каналы. В дискретных каналах сигналы на входе и выходе представляют собой последовательность символов одного или двух (по одному для входа и выхода) алфавитов. В непрерывных каналах входной и выходной сигналы представляют собой функции от непрерывного параметра- времени. Бывают также смешанные или гибридные каналы, но тогда обычно рассматривают их дискретные и непрерывные компоненты раздельно. Далее рассматриваются только дискретные каналы. Способность канала передавать информацию характеризуется числом пропускной способностью или емкостью канала (обозначение Для случая канала без шума формула расчета емкости канала имеет вид C = lim T →∞ log 2 N (T ) T , где N (T ) — число всех возможных сигналов за время T Пример. Пусть алфавит канала без шумов состоит из двух символов и 1, длительность τ секунд каждый. За время T успеет пройти n = T /τ сигналов, всего возможны 2 n различных сообщений длиной В этом случае C = lim T →∞ log 2 2 T /τ T = 1/τ бод. На рис. 8 приведена схема, на которой изображен процесс прохождения информации по каналу с описанными в примере характеристи- ками. Здесь для кодирования используется уровень сигнала низкий для и высокий для 1. Недостатки этого способа проявляются в случаях, когда нужно передавать много сплошных нулей или единиц. Малейшее рассогласование синхронизации между приемником и передатчиком приводит тогда к неисправимым ошибкам. Кроме того, многие носители информации, в частности, магнитные, не могут поддерживать длительный постоянный уровень сигнала 0 1 0 0 0 0 1 1 0 0 Рис. Для передачи информации используется обычно другой способ, когда для представления 0 и 1 используются две разные частоты, отличающиеся друг от друга ровно в два раза (см. рис. 9) — это так называемая частотная модуляция (ЧМ или FM). 1 0 0 0 1 Рис. Таким образом, при таком кодировании, если сигнал 1 имеет длительность, то 0 — 2τ Рассчитаем емкость этого канала. Нужно рассчитать N (T ). Пусть n = T /τ , тогда получается, что нужно рассчитать сколькими способами можно разбить отрезок длины n отрезками длины 2 и 1. Получаем, что N (T ) = S n = C n n + C n−2 n−1 + C n−4 n−2 + · · ·, где первое слагаемое это количество способов, которыми можно разбить отрезок длины n n отрезками длины 1, второе слагаемое — это количество способов, которыми можно разбить отрезок длины n (n − 2) отрезками длины 1 и одним отрезком длины 2, третье слагаемое — это количество способов, которыми можно разбить отрезок длины n (n − 4) отрезками длины и двумя отрезками длины 2 и т. д. Таким образом, S 1 = 1. Вследствие того, что C k m + C k+1 m = для любых k < m, получается, что · · S n = C n n + C n−2 n−1 + C n−4 n−2 + C n−6 n−3 + · · · S n+1 = C n+1 n+1 + C n−1 n + C n−3 n−1 + C n−5 n−2 + · · те+ при n > 1. Если положить, что S 0 = 1, то, S 1 , . . . — это последовательность 1, 1, 2, 3, 5, 8, 13, 21, 34, . . ., те. числа Фибоначчи. C XIX века для вычисления го члена последовательности Фибоначчи известна формула 1 + √ 5 2 n+1 − 1 − √ 5 2 n+1 47 Таким образом, C = lim T →∞ log 2 N (T ) T = lim n→∞ log 2 S n nτ = log 2 1+ √ 5 2 τ ≈ 0.69/τ бод. При использовании частотной модуляции на практике нули, как правило, кодируются в два раза плотнее. Это достигается тем, что учитываются не уровни сигнала, а смена уровня (полярности. Если частота ν соответствует 1, то с частотой 2ν производится проверка уровня сигнала. Если он меняется, то это сигнал 1, если нетто. На практике частота ν — это частота синхронизации, те. частота импульса, который независимо отданных меняет полярность сигнала не генерирует импульса смены полярности, а 1 генерирует (см. рис 0 0 0 0 0 0 Рис. Для записи информации на первые магнитные диски и ленты использовался метод FM. На гибкие диски 5.25” и 3.5” информация записывается методом MFM (Modified FM) — модификацией метода позволяющей в 2 раза повысить плотность записи. Это достигается тем, что частота синхронизации увеличивается вдвое. MFM можно использовать с теми же физическими каналами, что и FM, потому что импульсы синхронизации не передаются перед 1 и первым 0 в серии нулей (см. рис. 11). S D S D S D S D S D S D S D S D S D 1 0 0 0 0 0 0 Рис. Метод записи с групповым кодированием, RLL — Run Limited Length, не использует импульсы синхронизации, применяется, в частности, в жестких дисках винчестер и существует в нескольких разновидностях. Одна из них основана на замене тетрад байта на 5-битные группы. Эти группы подбираются таким образом, чтобы при передаче данных нули не встречались подряд более двух раз, что делает код са- мосинхронизирующимся. Например, тетрада 0000 заменяется группой бит 11001, тетрада 1000 — 11010, тетрада 0001 — 11011, тетрада 1111 — 01111 (см. рис. 12). Существуют разновидности RLL, в которых заменяются последовательности бит различной длины. Кодирование MFM 48 или FM можно представить как частный случай RLL. 1 1 0 1 0 1 1 0 1 Рис. При необходимости передачи записанных с помощью некоторого кода сообщений поданному каналу приходиться преобразовывать эти сообщения в допустимые сигналы канала, те. производить надлежащее кодирование, а при приеме данных — декодирование. Кодирование целесообразно производить так, чтобы среднее время, затрачиваемое на передачу, было как можно меньше. Получается, что исходному входному алфавиту нужно однозначно сопоставить новый алфавит, обеспечивающий большую скорость передачи. Следующий, основной факт теории передачи информации или основная теорема о кодировании при наличии помех позволяет признании емкости канала и энтропии передатчика вычислить максимальную скорость передачи данных в канале. Теорема Шеннона. Пусть источник характеризуется д.с.в. X. Рассматривается канал с шумом, те. для каждого передаваемого сообщения задана вероятность ε его искажения в процессе передачи (вероятность ошибки. Тогда существует такая скорость передачи u, зависящая только от X, что ∀ε > 0 ∃u < u сколь угодно близкая к u такая, что существует способ передавать значения X со скоростью u и с вероятностью ошибки меньшей ε, причем u = C/HX. Упомянутый способ образует помехоустойчивый код. Кроме того, Фэно доказана [20] следующая обратная теорема о кодировании при наличии помех . Для u > u можно найти такое положительное число ε, что в случае передачи информации по линии связи со скоростью u вероятность ошибки ε передачи каждого символа сообщения при любом методе кодирования и декодирования будет не меньше (ε очевидно растет вслед за ростом u Упражнение По каналу связи без шума могут передаваться четыре сигнала длительностью мс каждый. Вычислить емкость такого канала. Упражнение Три передатчика задаются случайными величинами со следующими законами распределениями вероятностей) P (X 1 = −1) = 1/4, P (X 1 = 0) = 1/2, P (X 1 = 1) = 1/4; 2) P (X 2 = −1) = 1/3, P (X 2 = 0) = 1/3, P (X 2 = 1) = 1/3; 3) P (X 3 = n) = 2 −n , n = 1, 2, . . . 49 Емкость канала связи с шумом равна 4000 бод. Вычислить максимальную скорость передачи данных поэтому каналу каждым из передатчиков, обеспечивающую сколь угодно высокую надежность передачи. Помехозащитное кодирование Простейший код для борьбы с шумом — это контроль четности, он, в частности, широко используется в модемах. Кодирование заключается в добавлении к каждому байту девятого бита таким образом, чтобы дополнить количество единиц в байте до заранее выбранного для кода четного (even) или нечетного (odd) значения. Используя этот код, можно лишь обнаруживать большинство ошибок. Простейший код, исправляющий ошибки, — это тройное повторение каждого бита. Если с ошибкой произойдет передача одного бита из трех, то ошибка будет исправлена, но если случится двойная или тройная ошибка, то будут получены неправильные данные. Часто коды для исправления ошибок используют совместно с кодами для обнаружения ошибок. При тройном повторении для повышения надежности три бита располагают не подряда на фиксированном расстоянии друг от друга. Использование тройного повторения значительно снижает скорость передачи данных r j r r Рис. Двоичный симметричный канал изображен на рис. 13, где p — это вероятность безошибочной передачи бита, а q — вероятность передачи бита с ошибкой. Предполагается, что в таком канале ошибки происходят независимо. Далее рассматриваются только такие каналы. Двоичный симметричный канал реализует схему Бернулли, поэтому вероятность передачи n бит по двоичному симметричному каналу с k ошибками равна P n (k) = C k n p n−k Пример. Вероятность передачи одного бита информации с ошибкой равна q = 0.01 и нас интересует вероятность безошибочной передачи бит (125 байт. Искомую вероятность можно подсчитать по формуле, те. она ничтожно мала. Добиться минимальности вероятности ошибки при передаче данных можно используя специальные коды. Обычно используют систематические помехозащитные коды. Идея систематических кодов состоит в добавлении к символам исходных кодов, предназначенных для передачи в канале, нескольких контрольных символов по определенной схеме кодирования. Принятая такая удлиненная последовательность кодов декодируется по схеме декодирования в первоначально переданную. Приемник способен распознавать и/или исправлять ошибки, вызванные шумом, анализируя дополнительную информацию, содержащуюся в удлиненных кодах. Двоичным (m, кодом называется пара, состоящая из схемы кодирования и схемы декодирования D: Z n 2 → Z m 2 , где множество всех двоичных последовательностей длины n, m < n (случай m = n рассматривается в криптографии). Функции D и E выбираются так, чтобы функция H = D ◦T ◦E, где — функция ошибок , с вероятностью, близкой к единице, была тождественной. Функции D и E считаются безошибочными, те. функция ◦ E — тождественная (см. рис. Исходное −→ Кодированное −→ Принятое −→ Декодирован- сообщение сообщение |