Лекции - Теория информации. Лекция 1. Теория информации. Понятие видов информации
 Скачать 1.15 Mb.
|
|
1    1   0 . b a 1   2  .  b a
3    .   a b
2.  ,3.  В таком алгоритме в конце сообщения должен стоять некий маркер, обозначающий конец сообщения.  Код сообщения {aba}=10000. Декодирование арифметического кода производится по его значению и тем же интервалам до восстановления исходного сообщения. На практике часто используют адаптивный арифметический алгоритм, когда на начальном этапе относительные частоты появления символов задаются некоторыми отрезками, либо принимаются равновероятными. А в процессе кодирования значение этих частот уточняются.
Этот алгоритм относится к классу универсальных потому, что он не требует априорных знаний о статистике символов. Такой метод носит менее математически обоснованный характер, но более практический. Первый алгоритм разработан в 1971 году в Израиле Лемпелом и Зивом (LZ 77). Одной из причин популярности алгоритма LZ 77, а также семейства алгоритмов LZ 77, является их исключительная простота при высокой эффективности сжатия. LZ 77 использует уже просмотренную часть сообщения как словарь, а чтобы добиться сжатия он пытается заменить очередной фрагмент сообщения на соответствующий указатель в содержимое словаря, т.е. LZ 77 использует как бы скользящее окно по сообщению, разделенное на две части. Большая часть окна - словарь, включающий уже просмотренную часть сообщения, меньшая часть окна является буфером, содержащим еще не закодированные символы входного потока. Алгоритм пытается найти в словаре фрагмент сообщения, совпадающий с содержимым буфера. На практике размер словаря составляет несколько кбайт, а размер буфера - до 100 байт. В результате кодирования формируется совокупность групп по три элемента в каждой < a,l,z >, где a- относительный адрес в словаре, т.е. смещение в словаре относительно его начала до первого символа фрагмента, с которым совпадает содержимое буфера; l - число совпадений элементов буфера и словаря; z –первый несовпадающий со словарем символ в буфере. Пример. КРАСНАЯ КРАСКА
Для данного кода длину кодовой комбинации можно определить по следующей формуле:   - операция округления в большую сторону.Такой алгоритм еще часто называют словарным. Очевидно, что сжатие будет иметь место, если длина полученной кодовой комбинации будет меньше кода того же сообщения при непосредственном кодировании. Для словарного кодирования учтено: 1.Часто повторяющиеся цепочки кодируются очень эффективно. 2.Редко повторяющиеся символы и их последовательности с течением времени удаляются из словаря. 3.Можно доказать, что словарное кодирование асимптотически оптимально, т.е. что длина кодового слова стремится к энтропии этого текста. 4.Практически достижимая степень сжатия для этих кодов 50-60 %. В семейство алгоритмов LZ входит несколько моделей, которые модифицированы различными авторами в аспекте механизмов формирования кодовых групп, но во всех механизмах используется словарь. В настоящее время наибольшее распространение получил алгоритм LZW (1984 г.). В этом алгоритме длина кода уменьшается, так как не используется буфер. А кодирование проводится только по словарю, следовательно, кодовая группа определяется только длиной словаря. Декодирование словарного кода происходит в обратном порядке и упрощается тем, что не требует поиска совпадений в словаре.
Если коды алгоритмов типа LZ передать для кодирования алгоритму Хаффмана или арифметическому алгоритму, то полученный двухшаговый алгоритм дает результат сжатия, подобный случайным программам-архиваторам, таким, как GZ, AGZ, PK zip. Наибольшую степень сжатия дают двухпроходные алгоритмы, которые последовательно сжимают два раза исходные данные, но они соответственно и работают в два раза медленнее. Большинство программ- архиваторов сжимают каждый файл по отдельности, хотя некоторые способны это делать в потоке файлов, что дает соответствующее увеличение степени сжатия, но и одновременно усложняет способы работы с полученным архивом. Например, замена в таком архиве файла на более новую версию может потребовать перекодирования всего архива. В общем потоке с файлами способен работать архиватор RAR, а в ОС Unix практически все архиваторы, такие как Gzip, Bzip2 и т.д.
Сжатие с потерями используется в основном для трех видов данных: 1.Полноцветная графика. 2.Видеоинформация. 3.Звуковая информация. Сжатие с потерями обычно происходит в два этапа: 1.Исходная информация с потерями приводится к виду, в котором ее можно эффективно сжимать алгоритмами второго этапа сжатия без потерь. Основная идея сжатия графической информации с потерями состоит в следующем: каждая точка графической картинки характеризуется тремя равноценными атрибутами – яркость, цветность, насыщенность. Человек воспринимает их не как равные, т.е. полностью воспринимается информация о яркости, и гораздо меньшей степени о цветности и насыщенности, что позволяет отбрасывать часть информации о двух последних атрибутах без существенной потери качества изображения. Для сжатия графической информации с потерями в конце 80-х годов был установлен единый стандарт JPEG. В этом формате сложно регулировать степень сжатия, задавая степень потери качества. Сжатие видеоинформации основано на том, при переходе от одного кадра к другому на экране обычно ничего не меняется, поэтому сжатая видеоинформация представляет собой запись некоторых базовых кадров и последовательности изменения в них, при этом часть информации естественно может отображаться. А сжатую таким образом информацию можно и дальше сжимать другими методами, но уже без потерь. На сегодняшний день существует много форматов сжатия видеоинформации, но наиболее распространенным является MPEG. Этот стандарт был предложен в 1988 году и является практически единственным для спутникового телевидения и записи информации на DVD, CD и т.д. Сжатие звуковой информации с потерями осуществляется на основе ограничении спектра звукового сигнала диапазоном реальной слышимости человека. Используют для этого различные стандарты сжатия звуковых файлов и достаточно часто MPEG без видеоданных. ЛЕКЦИЯ № 5 ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ 5.1 Классификация помехоустойчивых кодов. Помехоустойчивое (канальное, избыточное, корректирующее) кодирование позволяет обнаруживать и исправлять ошибки, возникающие при передаче сообщения по каналу связи или в ходе других информационных процессов. Помехоустойчивое кодирование за счет введения в состав передаваемых кодовых слов достаточного большого объема избыточной информации, например, в форме проверочных символов. Операцию введения избыточности для повышения помехоустойчивости называют собственно помехоустойчивым кодированием. По способу кодирования помехоустойчивые коды можно разделить на: Помехоустойчивые коды   Блочные Непрерывные   Неразделимые Разделимые   Несистематические Систематические Блочное (блоковое) кодирование состоит в том, что каждой букве сообщения или последовательности из k символов, соответствующей этой букве сообщения, ставится в соответствие блок из n символов, причем n > k, а каждый символ блока формируется из k символов исходной последовательности по определенному правилу. На практике блок может достигать от 3 до нескольких сотен единиц. Непрерывные коды характеризуются тем, что кодирование и декодирование информационной последовательности символов осуществляется без разбиения на блоки. Каждый символ выходной последовательности как результат некоторой операции над символами входной последовательности. В таких кодах результат декодирования предыдущих и последующих символов может влиять на декодирование текущего символа. Наиболее широкое распространение среди непрерывных кодов получили сверточные коды. Блочные коды подразделяются на разделимые и неразделимые. К разделимым кодам относятся те, у которых кодовая комбинация состоит из двух частей, а именно информационной и проверочной частей. Обычно проверочные символы получаются посредством некоторых операций над информационными символами. Разделимые коды обозначают (n, k). К неразделимым относятся коды, у которых кодовую комбинацию нельзя разделить на эти две части - информационную и проверочную. Например, код с постоянным весом. Самый большой класс разделимых кодов составляют систематические, у которых значение проверочных символов определяется в результате проведения некоторых операций над информационными символами, поэтому эти коды часто называют линейными. Последовательность линейных операторов и число проверочных символов определяются тем, сколько ошибок может обнаружить и исправить данный код. Проверочные символы могут располагаться в любом месте кодовой комбинации, чаще их располагают справа, т.е. в младших разрядах. Пример формирования блокового разделимого системного кода.  1 0 0 1 Исходная комбинация k=4          1 0 0 1  0 Кодовая последовательность n=5 Код (5,4) В примере всего один проверочный символ, который формируется путем сложения по модулю 2 всех информационных символов. Такой код называется кодом с проверкой на четность. Причем, если новую так называемую разрешенную кодовую комбинацию систематического кода можно получить линейным преобразованием двух разрешенных комбинаций, то код называется линейным. К несистематическим кодам относятся те, в которых проверочные символы формируются за счет нелинейных операций над информационными символами (код Бергера). 5.2 Параметры (характеристики) помехоустойчивых кодов и их границы. Корректирующие свойства кодов. Основными характеристиками помехоустойчивых кодов являются:
Длина кода - число символов в кодовой комбинации n. Если кодовые комбинации содержат одинаковое число символов, то они называются равномерными. |
,
,
,
;