Лекции. лекции оти. Лекция 1. Теория информации. Понятие видов информации
![]()
|
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 ![]() ![]() ![]() ![]() ![]() Кодовая последовательность n=5 ![]() Код (5,4) В примере всего один проверочный символ, который формируется путем сложения по модулю 2 всех информационных символов. Такой код называется кодом с проверкой на четность. Причем, если новую так называемую разрешенную кодовую комбинацию систематического кода можно получить линейным преобразованием двух разрешенных комбинаций, то код называется линейным. К несистематическим кодам относятся те, в которых проверочные символы формируются за счет нелинейных операций над информационными символами (код Бергера). 5.2 Параметры (характеристики) помехоустойчивых кодов и их границы. Корректирующие свойства кодов. Основными характеристиками помехоустойчивых кодов являются: Длина кода n; Основание кода m; Общее число кодовых комбинаций N; Число разрешенных кодовых комбинаций Nр; Избыточность кода |