символами, который удовлетворяет условию

Н(Х,...Х,,)<Т, <ЩX...XJ) + \. (3.3.27)

Деля обе части (3.3.27) на J, мы получаем границы для среднего числа R = Rj/j бит на исходный символ как

HjiX)<R<HAX) + j. (3.3.28)

Увеличивая размер блока J, мы можем приближаться к Hj (X) сколь угодно близко, и в пределе, когда J co,R удовлетворяет соотношению

HiX)<R<H„iX) + e, П.3.29)

где Е стремится к нулю как 1/J. Таким образом, эффективное кодирование стационарных источников может быть выполнено, если кодировать большие блоки символов в кодовые слова. Мы должны подчеркнуть, однако, что конструкция кода Хаффмена требует знания совместных ФПВ для 7-символьных блоков.

3.3.3. Алгоритм Лемпела-Зива

Из нашего предшествующего обсуждения следует, что алгоритм кодирования Хаффмена приводит к оптимальному кодированию источника в том смысле, что кодовые слова удовлетворяют префиксному условию и средняя длина кодового блока минимальна. Конструируя код Хаффмена для ДИБП, мы должны знать вероятности появления всех исходных символов. В случае дискретного источника с памятью мы должны знать совместные вероятности всех блоков длины и > 2. Однако на практике статистика выхода источника чаще всего неизвестна. В принципе возможно оценить вероятности выхода дискретного источника, наблюдая длинную информационную последовательность, выдаваемую источником, и получая требуемые вероятности опытным путем. Такой метод пригоден для оценки вероятностей отдельных символов {р.}. Однако вычислительная

сложность оценки совместных вероятностей чрезвычайно высока. Следовательно, использование метода кодирования Хаффмена для многих реальных источников с памятью вообще непрактично.

В отличие от алгоритма кодирования Хаффмена алгоритм кодирования Лемпела-Зива разработан так, чтобы быть независимым от статистики источника. Следовательно, алгоритм Лемпела-Зива принадлежит классу универсальных алгоритмов кодирования источника. Это - алгоритм переменно-фиксированной длины, а кодирование выполняется так, как описано ниже.

В алгоритме Лемпела-Зива последовательность с выхода дискретного источника делится на блоки переменной длины, которые называются фразами. Кал<дая новая фраза представляет собой последовательность символов источника, отличающуюся от некоторой предьщущей фразы в последнем символе. Фразы перечислены в словаре, который сохраняет расположение существующих фраз. При кодировании новой фразы мы просто определяем адрес существующей фразы в словаре и добавляем в конец новый символ.

Как пример рассмотрим бинарную последовательность

10101101001001110101000011001110101100011011.

Деление последовательности, как описано выше, производит следующие фразы: 1,0, 10, 11,01,00. 100, 111,010, 1000,011,001, 110, 101,10001, 1011.

Мы видим, что каждая фраза в последовательности - соединение одной из предыдущих фраз с новым выходным символом источника. Для кодирования фразы мы конструир>ем словарь, как показано в табл. 3.3.4.

Таблица 3.3.4. Словарь для алгоритма Лемпела-Зива

Ячейки словаря пронумерованы последовательно, начиная с 1 и далее, в данном случае до 16, что является числом фраз в последовательности. Различные фразы, соответствующие каждой ячейке, также перечислены, как показано в таблице. Кодовые слова конструируются путём соединения двух частей. Первая часть представляет собой номер ячейки словаря (в двоичной форме) предыдущей фразы, которая соответствует новой фразе, кроме последнего символа. Вторая часть - это новый символ, вьщанный источником. Он добавляется в конец к первой части, т.е. к номеру ячейки предыдущей фразы. Первоначальный номер ячейки 0000 используется, чтобы кодировать «пустую» фразу.

Декодер источника создает идентичную таблицу на приемном конце системы связи и соответственно декодирует полученную последовательность.

Можно заметить, что таблица закодировала 44 исходных бита в 16 кодовых слов по пять битов каждый, что привело к 80 кодированным битам. Следовательно, алгоритм вообще не обеспечил никакое сжатие данных. Однако неэффективность является следствием того, что последовательность, которую мы рассмотрели, очень коротка. По .мере увеличения длины последовательности процедура кодирования становится более эффективной и приводит к сжатию последовательности на выходе источника.

Как мы выбираем полную длину таблицы? Вообще, независимо от размера таблицы, она в конечном счёте переполнится. Чтобы решить проблему переполнения, кодер источника и декодер источника должны согласованно удалять фразы из соответствующих словарей, которые больше не используются и подставить новые фразы на их место.

Алгоритм Лемпела-Зива широко используется при сжатии компьютерных файлов «Сжимающие» и «разжимающие» программы (утилиты) в операционной системе UNIX® и многочисленные алгоритмы в операционной системе MS DOS яшхяются воплощениями р;1зличных версий этого алгоритма.

3.4. КОДИРОВАНИЕ ДЛЯ АНАЛОГОВЫХ ИСТОЧНИКОВ -ОПТИМАЛЬНОЕ КВАНТОВАНИЕ

Как отмечено в разд. 3.1, аналоговый источник вьщает непрерывный сигнал x{t). который является выборочной функцией случайного процесса X{t). Если X{i) является стационарным случайным процессом с ограниченной полосой, теорема отсчётов позволяет нам представить X{t) последовательностью отсчётов, выбираемых равномерно со скоростью Найквиста.

Применяя теорему отсчётов, выход аналогового источника преобразуется в эквивалентную дискретную во времени последовательность отсчётов. Затем отсчёты квантуются по уровням и кодируются. Один тип простого кодирования - представление каждого дискретного уровня амплитуды последовательностью двоичных символов. Следовательно, если мы имеем L уровней, нам необходимы Л = log, L бит/отсчёт (если L есть степень числа 2) или R = [log, Z +1 (в противном случае). Если уровни не

равновероятны, но вероятности уровней на выходе источника известны, мы можем использовать процедуру кодирования Хаффмена (называемую также энтропийным кодированием), чтобы улучшить эффективность процесса кодирования.

Квантование амплитуд дискретизированного во времени сигнала обеспечивает сжатие данных, но это также приводит к некоторому искажению формы сигнала или потере его точности. Минимизация этих искажений является предметом рассмотрения в данном разделе. Многие результаты, данные в этом разделе, непосредственно применимы к дискретному во времени, непрерывному по амплитуде гауссовскому источнику без памяти. Такой источник служит хорошей моделью для нахождения остаточной ошибки в ряде .методов кодирования источника, описанных в разд. 3.5.

3.4.1. Функция скорость-искажение R(D)

Начнём обсуждение квантования сигналов с рассмотрения погрешности представления отсчётов сигнала от информационного источника фиксированным числом симвоюв (битов). Под термином «искажение» мы понимаем некоторую меру разности между фактическими выборками источника {х} и соответствующими квантованными

значениями , которую мы обозначаем d{x,Xf}. Например, обычно используемая мера искажения - квадрат ошибки, определенная как

d(ix„x,) = (x,-x,)\ (3.4.1)

и используемое для определения ошибки квантования при ИКМ в разд. 3.5.1. Другие меры искажения могут принимать более общую форму:

d(x„x,)=\x-x,\, (3.4.2)

где р принимает значения из ряда положительных целых чисел. Случай р = 2 имеет предпочтительную математическую трактовку. , Если d{xi,Xi] - мера искажения на отсчёт, искажение между последовательностью п

отсчётов Х„ и соответствующими п квантованными значениями Х„ является средни.м значением искажения по п отсчётам, т.е.

(Х„.Х„) = -Х (3.4.3)

На выходе источника имеет место случайный процесс, и, следовательно, п отсчётов в Х„ являются случайными величинами. Поэтому d(X„,X) - случайная величина. Её математическое ожидание определяет искаженце D, т.е. 94