Прокис Дж. Цифровая связь (2000) (1151856), страница 22
Текст из файла (страница 22)
источником. Он добавляется в конец к первой части, т.е. к номеру ячейки предыдущей фразы. Первоначальный номер ячейки 0000 используется, чтобы кодировать «пустую» фразу. Декодер источника создает идентичную таблицу на приемном конце системы связи и соответственно декодирует полученную последовательность.
Можно заметить, что таблица закодировала 44 исходных бита в 16 кодовых слов по 'пять битов каждый, что привело к 80 кодированным битам. Следовательно, алгоритм вообще не обеспечил никакое сжатие данных. Однако неэффективность является следствием того, что последовательность, которую мы рассмотрели, очень хоротха.
По мере увеличения длины последовательности процедура кодирования становится более эффективной и приводит к сжатию последовательности на выходе источника. Как мы выбираем полную длину таблицы? Вообще, независимо от размера таблицы, оиа в конечном счете переполнится. Чтобы решить проблему переполнения, кодер источника и декодер источника должны согласованно удалять фразы из соответствующих словареи, которые больше не используются и подставить новые фразы на их место. Алгоритм Лемпела — Зива широко используется при сжатии компьютерных файлов. ~ «Сжимающие» н «разжимающие» программы (утилиты) в операционной системе 1ЛЧ1Хи и 1многочисленные алгоритмы в операционной системе МЗ РОЗ являются воплощениями различных версий этого алгоритма.
1 2 3 5 б 7 8 9 10 11 12 13 14 15 1б 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 1 0 10 11 01 00 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, аналоговый источник выдает непрерывный сигнал х(г). который является выборочной функцией случайного процесса Х(г).
Если Х(г) является стационарным случайным процессом с ограниченной полосой, теорема отсчетов позволяет нам представить Х(г) последовательностью отсчетов, выбираемых равномерно со скоростью Найквиста. Применяя теорему отсчетов, выход аналогового источника преобразуется в эквивалентную дискретную во времени последовательность отсчетов. Затем отсчеты квантуются по уровням и кодируются.
Один тип простого кодирования †представлен каждого дискретного уровня амплитуды последовательностью двоичных символов. Следовательно, если мы имеем Х уровней, нам необходимы л =!оя. Х бит/отсчет (если Е есть степень числа 2) или 11 = ~ 1од, ь3+1 (в противном случае). Если уровни не равновероятны, но вероятности уровней на выходе источника известны, мы можем использовать процедуру кодирования Хаффмена (называемую также энтропийным кодированием), чтобы улучшить эффективность процесса кодирования. Квантование амплитуд дискретизированного во времени сигнала обеспечивает сжатие данных, но это также приводит к некоторому искажению формы сигнала или потере его точности. Минимизация этих искажений является предметом рассмотрения в данном разделе.
Многие результаты, данные в этом разделе, непосредственно применимы к дискретному во времени, непрерывному по амплитуде гауссовскому источнику без памяти. Такой источник служит хорошей моделью для нахождения остаточной ошибки в ряде методов кодирования источника, описанных в разд. 3.5. 3.4.1. Функция скорость-искажение )г(0) Начнем обсуждение квантования сигналов с рассмотрения погрешности представления отсчетов сигнала от информационного источника фиксированным числом символов (битов). Под термином «искажение» мы понимаем некоторую меру разности между фактическими выборками источника ~х„) и соответствующими к вантован ными значениями х„, которую мы обозначаем Ы(х„х„).
Например, обычно используемая мера искажения — квадрат ошибки, определенная как сК(х„,х,.) =(х„-х„)', (3.4.1) и используемое для определения ошибки квантования при ИКМ в разд. 35.1. Другие меры искажения могут принимать более общую форму: Ы(х,х„) =~ х — х„)», (3.4.2) где р принимает значения из ряда положительных целых чисел. Случай р=2 имеет предпочтительную математическую трактовку. , Если Ы(х„,х,) — мера искажения на отсчет, искажение между последовательностью и отсчетов Х„ и соответствующими и квантованнымн значениями Х. является средним значением искажения по п отсчетам, т.е. Н(Х„, Х„) = — ~~> Ы(х„, х„) .
1 (3.4.3) и ~., На выходе источника имеет место случайный процесс, и, следовательно, и отсчетов в Х„являются случайными величинами. Поэтому Н(Х„,Х„) — случайная величина. Ее математическое ожидание определяет искажение 23, т.е. )?(Р) = ш1п Е(Х, Х), Р(ЯИ)л(8(х,хЯяп (3.4.5) где Е(Х,Х) — средняя взаимная информация между Х и Х. Вообще, скорость Я(Р) уменьшается при увеличении Р или, наоборот, т?(Р) увеличивается при уменьшении Р. Для гауссовской модели непрерывного по амплитуде информационного источника без памяти Шеннон доказал следующую фундаментальную теорему.
Теорема: Функция скорость-искажение для гауссовского источника без памяти (Шеннон, 1959а). Минимальная скорость кодирования, необходимая для представления выхода дискретного во времени, непрерывного по амплитуде гауссовского источника без памяти, при использовании в качестве меры искажения среднеквадратнческой ошибки на символ (односимвольная мера искажения) ~?8(Р) = 2 1одт(а. /Р) (О ~ Р ~ а, ), (3.4.6) О (Р.,а), где а, — дисперсия выхода.
гауссовского источника. Заметим, что (3.4.6) подразумевает, что, если искажение Р>а„, никакой иифор- 2 мации передавать не нужно. Конкретно прн 2 Р = а, для реконструкции сигнала достаточно воспроизвести нули. При Р >а, для 2 2,0 Б Ф 3" реконструкции сигнала мы можем использовать статистически независимые гауссовские шумовые выборки с дисперсией Р-а, График функции Яя(Р) представлен на рис.
3.4.1. Функция скорость-искажение А(Р) источника связана со следующей основной теоремой кодирования источника в теории информации. 0 о 0,2 0,4 0,6 0,8 1 .0Епт Рис. 3.4.1. Функция скорость-искажение для непрерывного по амплитуде гауссовского источника без памяти 'Теорема: Кодирование источника с заданной мерой искажения (Шеннон, 1959а). Существует схема кодирования, которая отображает выход источника в кодовые слова так, что для любого данного искажения Р минимальная скорость Е?(Р) бит на символ (на 95 .Р = Е((Е(Х„, Х„)] = — ~~) Е((Е(х„, х„)] = Е((Е(х, х)], (3.4.4) 1 и„., где последнее равенство следует из предположения, что исходный процесс является стационарным. Теперь предположим, что мы имеем источник без памяти с непрерывно-амплитудным выходом Х, который имеет ФПВ отсчета р(х), квантованный амплитудный алфавит Х и меру искажения на отсчет ц((х„,хь~, где хе Хн х и Х.
Тогда минимальная скорость в битах на отсчет, требуемая для представления выхода Х источника без памяти с искажением, меньшим нли равным Р, называется функцией скорость-искажение и определяется как отсчет) источника является достаточной для восстановления исходного сигнала со средним искажением, которое является произвольно близким к Р. Это очевидно, потому что функция скорость-искажение Я(Р) для любого источника представляет нижнюю границу скорости источника, которая является возможной для данного уровня искажения.
Вернемся к результату в (3.4.6) для функции скорость-иска>кение гауссовского источника без памяти. Если мы поменяем функциональную зависимость между. Р и )г, мы можем выразить Ря через гг как Рк(К) =2 ~"о, (3.4.7) Эта функция называется функцией искажение-скорость для дискретного во времени гауссовского источника без памяти Если искажение в (3.4.7) выразить в децибелах, мы получаем 101оя о Ря(К) = — 6Я+10!ой~о о, . (3.4.8) Заметим, что среднеквадратическое искажение уменьшается со скоростью 6 дБ/бит.
Явных выражений для функции скорость-искажение для негауссовских источников без памяти не существует. Однако имеются полезные верхние и нижние границы функции скорость-искажение для произвольного дискретного по времени, непрерывного по амплитуде источника без памяти. Верхняя граница дается следующей теоремой. (3.4.13) Теорема: Верхняя граница дли Я(Р) . Функция скорость-искажение непрерывного по г амплитуде источника без памяти с нулевым средним и конечной дисперсией а„при использовании среднеквадратичной меры искажений ограничена сверху величиной г К(Р) <-г'1ояг — ' (0<Р<а,.
). (3.4.9) Р Доказательство этой теоремы дано Бергером (1971). Подразумевается, что гауссовский источник требует максимальную скорость кодирования среди всех других источников при заданном уровне среднеквадратической ошибки. Следовательно, функция скорость- искажение Я(Р) для произвольного непрерывного источника без памяти с нулевым средним и конечной дисперсией сг, удовлетворяет условию Л(Р)ь Я„(Р). Аналогично функция искажение-скорость того же источника удовлетворяет условию Р(11) <Р ф)=2-гао ' (3.4.10) Существует также нижняя граница функции скорость-искажение. Ее называют нижней границей Шеннона для среднеквадратической ошибки искажения, и она определяется так: г1 (Р) = Ь(Х)-ф1ояг 2пеР, (3.4.1 1) где Ь(Х) — дифференциальная энтропия источника без памяти с непрерывной амплитудой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
