Прокис Дж. - Цифровая связь (1266501), страница 22
Текст из файла (страница 22)
Это — алгоритм переменно-фиксированной длины, а кодирование выполняется так, как описано ниже. В алгоритме Лемпела — Зива последовательность с выхода дискретного источника делится на блоки переменной длины, которые называются фразами. Каждая новая фраза представляет собой последовательность символов источника, отличающуюся от некоторой предыдущей фразы в последнем символе. Фразы перечислены в словаре, который сохраняет расположение существующих фраз. При кодировании новой фразы мы просто определяем адрес существующей фразы в словаре и добавляем в конец новый символ. Как пример рассмотрим бинарную последовательность 1010110100100111010100001100111010110001!О!1.
Деление последовательности, как описано выше, производит следующие фразы: 1, О, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011. Мы видим, что каждая фраза в последователыюсти — соединение одной из предыдущих фраз с новым выходным символом источника. Для кодирования фразы мы конструируем словарь. как показано в табл. 3.3.4. Таблица 3.3.4. Словарь для алгоритма Лемпела-Зива Кодовое слово Содержимое слова я Расположение в слова е Ячейки словаря пронумерованы последовательно, начиная с 1 и далее. в данном случае ло 16.
что является числом фраз в последовательности, Различные фразы, соответствующие каждой ячейке, также перечислены, как показано в таблице. Кодовые слова конструируются путбм соединения двух частей, Первая часть представляет собой номер ячейки словаря 1в двоичной форме) предыдущей фразы, которая соответствует новой фразе, кроме последнего символа, Вторая часть — зто новый символ, выданный источником.
Он добавляется в конец к первой части, т.е. к номеру ячейки предыдущей фразы. Первоначальный номер ячейки 0000 используется„чтобы кодировать «пустую» фр у. , Декодер источника создает идентичную таблицу на приемном конце системы связи н соответственно декодирует полученную последовательность. Можно заметить„ что таблица закодировала 44 исходных бита в 16 кодовых слов по пять битов каждый, что привело к 80 кодированным битам.
Следовательно. алгоритм :-': .' вообще не обеспечил никакое сжатие данных. Однако неэффективность является следствием того, что последовательность, которую мы рассмотрели, очень коротка. По мере увеличения длины последовательности процедура кодирования становится более ! "-- эффективной и приводит к сжатию последовательности на выходе источника, Как мы выбираем полную длину таблицы? Вообще, независимо от размера таблицы, она в конечном счете переполнится.
Чтобы решить проблему переполнения, кодер ;. источника и декодер источника должны согласованно удалять фразы из соответствующих -';; ",:: словарей, которые больше ие используются и подставить новые фразы на их место Алгоритм Лемпела — Зива широко используется при сжатии компьютерных файлов. «Сжимающие» и «разжимающие» программы (утилиты) в операционной системе 1Л~ИХ~ и многочисленные алгоритмы в операционной системе МЗ ПОЗ являются воплощениями различных версий этого алгоритма. 1 2 5 6 7 з 9 10 11 1э 13 14 15 16 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 1 0 1О 11 01 ОО 100 111 010 1000 011 001 110 101 10001 1011 00001 00000 00010 00011 00101 00100 00110 01001 01010 01110 01011 01101 01000 00111 10101 11101 3.4. КОДИРОВАНИЕ ДЛЯ АНАЛОГОВЫХ ИСТОЧНИКОВ— ОПТИМАЛЬНОЕ КВАНТОВАНИЕ Как отмечено в разд.3.1, аналоговый источник выдает непрерывный сигнал х(/), который является выборочной функцией случайного процесса Х(г). Если Х(/) является стационарным случайным процессом с ограниченной полосой, теорема отсчетов позволяет нам представить Х(/) последовательностью отсчетов, выбираемых равномерно со скоростью Найквиста.
Применяя теорему отсчетов, выход аналогового источника преобразуется в эквивалентную дискретную во времени последовательность отсчетов. Затем отсчеты квантуются по уровням и кодируются. Один тип простого кодирования — представление каждого дискретного уровня амплитуды последовательностью двоичных символов. Следовательно. если мы имеем /.
уровней, нам необходимы Я = 1оя. /, бит/отсчет (если /. есть степень числа 2) или Я = ~ 1оя, ь'1+1 (в противном случае). Бели уровни не равновероятны, но вероятности уровней на выходе источника известны, мы можем использовать процедуру кодирования Хаффмена (называемую также энтропийным кодированием), чтобы улучшить эффективность процесса кодирования. Квантование амплитуд дискретизированного во времени сигнала обеспечивает сжатие данных, но это также приводит к некоторому искажению формы сигнала нли потере его точности. Минимизация этих искажений является предметом рассмотрения в данном разделе.
Многие результаты, данные в этом разделе, непосредственно применимы к дискретному во времени, непрерывному по амплитуде гауссовскому источнику без памяти. Такой источник служит хорошей моделью для нахождения остаточной ошибки в ряде методов кодирования источника, описанных в разд. 3.5. 3.4.1. Функция скорость-искажение Я(0) Начнем обсуждение квантования сигналов с рассмотрения погрешности представления отсчетов сигнала от информационного источника фиксированным числом символов (битов). Под термином «искажение» мы понимаем некоторую меру разности между фактическими выборками источника (х„) и соответствующими квантованными значениями х„, которую мы обозначаем И(х„,х,).
Например, обычно используемая мера искажения — квадрат ошибки, определенная как И(х„,х,) =(х„— х,)', (3.4.1) и используемое для определения ошибки квантования при ИКМ в разд. 3.5 1. Другие меры .!;-' искажения могут принимать более общую форму: Ы(х,, х' ) =1 х - х„1", (3.4.2) где р принимает значения из ряда положительных целых чисел. Случай р=2 имеет ': предпочтительную математическую трактовку.
, Если И(х„х„) — мера искажения на отсчйт, искажение между посчедовательностью п-::,':;:,,'-',, отсчетов Х„и соответствующими п квантованными значениями Х„является средним::,' я значением искажения по п отсчетам, т.е. И Ы(Х„,Х )=-~~~ И(х„,х,,).
(3.4.3) П~ ~ На выходе источника имеет место случайный процесс, и, следовательно, и отсчетов в ', Х„являются случайными величинами. Поэтому И(Х„,Х,) — случайная величина. Ей,: математическое ожидание определяет искажение О, т.е. 94 В = Е[г((ХгпХ„)1 =. — ~~8 Е[г1(х„,х,)1 = Е[г1(х,х)1, (3.4,4) 1" л„„, ,:-',::, где последнее равенство следует нз предположения, что исходный процесс является стационарным. Теперь предположим„ что мы имеем источник без памяти с непрерывно-амплитудным ';, выходом Х. который имеет ФПВ отсчета р(х), квантованный амплитудный алфавит Х и меру искажения на отсчет гг(х„,хя~, где хе Хи хе Х.
Тогда минимальная скорость в :,'-':::,- битах на отсчет, требуемая для представления выхода Хисточннка без памяти с искажением, меньшим или равным В, называется функцией скорость-искажение и определяется как Л(.Р) = шш У(Х, Х), жяр1яьд к Хуяяп (3.4.5) :::-:':-' где 1(Х,Х) — средняя взаимная информация между Х и Х, Вообще, скорость А(В) уменьшается при увеличении В или„наоборот, А(В) увеличивается при уменьшении В. Для гауссовской модели непрерывного по амплитуде информационного источника без памяти Шеннон доказал следующую фундаментальную теорему. Заметим, что (3.4.6) подразумевает, что, 2 если искажение В>о,, никакой информации передавать не нужно.
Конкретно при 2 В=а„для реконструкции сигнала доста- 2 точно воспроизвести нули. Прн В>а, для реконструкции сигнала мы можем использовать статистически независимые гауссовские шумовые выборки с дисперсией Р— а, . График функции К(Р) представлен на рис. 3.4.1. Функция скорость-искажение Я(В) источника связана со следующей основной теоремой кодирования источника в теории ':~': '"'.', информации. 0 1 0 0,2 0,4 0,6 0„8 В/02 Рис.
3.4.1. Функция скорость-искажение для .непрерывного по амплитуде гауссовского источиика без памяти 'Теорема: Кодирование источника с заданной мерой искажения (Шеннон, 1959а). Существует схема кодирования, которая отображает выход источника в кодовые слова так, '::,.:" что для любого данного искажения В минимальная скорость )г(В) бит на символ (на Теорема: Функция скорость-искажение для гауссовского источника без памяти ~;.:.- (Шеннон, 1959а).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
