Файл: Крулькевич, М. И. Основы систем производственно-экономической информации учеб. пособие.pdf

§ 3. С татистическое к оди ров ан и е

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

Априори, зная статистические свойства источника сооб­ щения, можно минимизировать среднее число двоичных или* иных символов, требующихся для выражения одного элемен­ та сообщения, что в итоге позволяет уменьшить время пере­ дачи информации и объем запоминающих устройств ЭВМ.

В основу статистического кодирования положена теоре­ ма Шеннона о кодировании для дискретного капала без по­ мех. Согласно теореме, если источник информации имеет эн­ тропию Н единиц информации на символ сообщения, а ка­ нал связи обладает пропускной способностью С единиц ин­ формации в единицу времени, то сообщения источника всегда можно закодировать таким образом, чтобы скорость V' их передачи была сколь угодно близкой к величине, определяе­ мой соотношением

и не существует способа кодирования, позволяющего достичь таково положения, чтобы выполнить неравенство V>V z . При этом величину H'=VH называют потоком информации, созда­ ваемой источником.

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

Другими словами, по возможности каждый символ со­ общения должен принимать значения 0 и 1 с равными веро­ ятностями, 'и каждый выбор должен быть независим от. зна­ чений предыдущих символов.

Рассмотрим следующий пример. Пусть необходимо оп­ тимально закодировать наименование некоторых материа-

78

лов, отпускаемых со склада. Перечень материалов и вероят­ ность запроса на них представлены в табл. 5.

С учетом вероятности запроса на представление и пере­ дачу всех сообщений о материалах необходимо затратить в среднем двоичных символов

i= m

О = 2 Pi ni , i=i

где Pj — вероятность запроса на i-й материал;

n г — количество двоичных символов в коде i-ro мате­ риала.

В нашем случае; а) при традиционном кодировании

Q=0,15-1+0,10-1+0,05-2+0,3-2+0,18-2 + 0,22-3= 1,9'

дв. символов; б) при использовании теоремы Шеннона

<3 = 0,15-2 + 0,10-3+0,05-3+0,3-1+0,18-2+0,22-1 = 1,63 дв. сим­ волов.

Таким образом, использование принципов статистичес­ кого кодирования позволяет в данном случае сократить коли­ чество двоичных символов, необходимых для передачи сооб­ щений или ^отражения в соответствующих документах про­ цесса движения материалов, примерно на 20%.

79

Способы статистического кодирования различны и за­ висят они от статистики передаваемых сообщений. Обычно для сообщения со статистически независимыми элементами наиболее эффективным является либо поэлементное.описание оптимальными кодами, когда энтропия распределения эле­ ментов близка к единице, либо кодирование укрупненных блоков элементов исходного сообщения, когда энтропия рас­ пределения меньше единицы.

Известны две основные разновидности методов статисти­ ческого кодирования — пеадаптцвное и адаптивное.

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

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

Необходимость передачи разделительного знака между элементами сообщений снижает эффект неадаптивного ста­ тистического кодирования. В связи с этим применение извест­ ного способа классического кодирования по Шеннону-Фано к сообщениям с низкой энтропией и некоррелированными символами нецелесообразно.

Из адаптивных методов статистического кодирования можно отметить метод представления сообщений кодами пе­ ременной длительности. Данный метод позволяет устранить е кодовых посылках нули, не несущие никакой информации, п служащие лишь д^тя выделения границ элементов сообще­ ния.

Организация сжатия информации с использованием данного способа является весьма сложной.

• В какой-то мере аналогичные адаптивному статистичес­ кому кодированию принципы используются в так называе­ мом матричном кодировании, которое применяется, напри­ мер, для уплотнения кодов монотонно изменяющихся или периодически повторяющихся чисел.

80

§ 4. А п ер тур н ое сж а т и е

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

Основным критерием выделения избыточности в данном методе является полоса допустимого отклонения, или апер­ тура. Базируются способы либо на предсказании по преды­ дущим выборкам, либо на апостериорной интерполяции по­ следующих выборок. Размеры апертуры, исходя из требова­ ний потребителя информации, могут быть различными.

Сжатие информации при использовании апертурных ме­ тодов связано с частично допустимой потерей информации.

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

Относительная простота в реализации и высокая эффек­ тивность способствуют широкому распространению метода в настоящее время.

Практическое применение могул найти три следующих разновидности метода апертурного, сжатия:

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

При квантовании по уровню и по времени непрерывная величина как бы накладывается на сетку с координатами уровня и времени. Интервалы по времени т определяет шаг

квантования по контролируемой функции, величина которо­ го равна

А У, = у, — у,_1,

Значение уровня, удовлетворяющее неравенству

торых округляются значения у, определяет дискретную шка­ лу преобразования и называется уровнем квантования.

При одинаково выбранных Лул квантование называется равномерным. В практике такой вид квантования наиболее распространен.

Выбор числа уровней квантования зависит от разреша­ ющей способности датчика и от требуемой точности ввода соответствующего параметра в ЭВМ.

При выборе интервала т приходится учитывать нали­ чие автокорреляционной зависимости между соседними от­ счетами. Влияние медленных нестационарных изменений контролируемой переменной наблюдаться не должно.

В качестве примера неудачного использования метода

н исходная функция не анализировалась перед проектирова­ нием системыконтроля.

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

82

где j = 1,2, ..., n — количество существенных выборок; Ah (ti ) — величина отклонения от допустимой зоны.

Так как n < N и Л hcp( ti ) < Л h( ti ), то S' < 1.

Причем, чем меньше S', тем эффективнее способ апертурно­ го сжатия по сравнению с разностным кодированием.

Апертурное сжатие с предсказанием осуществляется сле­

что предсказание осуществляется правильно и выборка у (t) из дальнейшего рассмотрения устраняется как избыточная. В противном случае она передается потребителю инфор­ мации.

Наиболее удобно в практике использовать в качестве предсказателя полином Ньютона нулевого порядка. Этот предсказатель работает по принципу: каждая последующая выборка сообщения равна по величине последней передан­ ной неизбыточной выборке в пределах заданной полосы до­ пусков, то есть

У'« ( О - У . ( t - 1),

где Yi (t—1) — значение предыдущей неизбыгочной вы­ борки.

Вычисленное в момент появления неизбыточной выбор­ ки значение У'| (t) принимается за эталонное для всех в по­ следующем поступающих выборок до появления очередного

неизбыточного значения.

г

Если предсказание точное, то новая выборка обязатель­ но попадет в одну и ту же зону с эталонной величиной. Раз­ меры апертуры в каждом конкретном случае задаются заранее приемником информации, исходя из характера изменения контролируемого процесса и требуемой точности информационных данных. Для определения значения апер­ туры можно использовать выражение

h = ^ 1 0 0 % ,

84