ИЗБЫТОЧНОСТЬ ПРЕДСТАВЛЕНИЙ БЕРНУЛЛИЕВСКИХ ИСТОЧНИКОВ

И.А. Косенков (студент гр. САПР-51)

Научный руководитель: д.ф-м.н.,профессор,

КФ МГТУ им.Н.Э.Баумана А.К. Горбунов

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

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

Формализация задачи.

Пусть - множество порождаемых источником n- мерных массивов, которые по каждой координате содержат N элементов двоичного алфавита {0,1}. Пусть - множество способов разбиения массивов на однородные фрагменты так, что при любом массив представлен совокупностью фрагментов , каждый из которых состоит из одинаковых элементов.

Введем среднюю сложность представления (на элемент массива) при способе разбиения

(1)

и минимальную среднюю сложность

(2)

 

которая достигается при оптимальном разбиение . Минимальные затраты на кодирование фрагментного представления определяются отношением энтропии ансамбля его фрагментов к среднему количеству элементов фрагмента. Эта величина равна

(3)

где суммирование производиться по множеству всех фрагментов, получаемых на разбиении

Оценка сложности и энтропии.

Для указанных представлений (1)-(3), при . В случае n=1 получены точные значения этих функций, в случае n>1- верхние и нижние оценки энтропии. Для средних сложностей минимального и древовидного представлений последовательностей найдены рекуррентные соотношения:

при .Учитывая, что в обоих случаях , из рекуррент имеем

(4)

для минимального представления

(5)

При n>1 верхние оценки сложностей равным n-ым степеням правых частей (4) и (5).

(6)

то имеет место оценка

(7)

Суммирование в (6) и (7) производится по всем значениям , получаемым на разбиении .

(8)

Вычисление энтропии (3) для распределения (6) с учетом соотношений (7) и (8) при приводят к оценкам следующего вида

(9)

где определенно в (8), а

и . Увеличение l приводит к уточнению оценок (9).

При n=1 и (9) выполняется со знаком равенства для минимального преставления и дает бита.

Таким образом, фрагментное представление с большей избыточностью сложности имеет меньшую избыточность энтропии. Так при n=1 и представление имеет наибольшую избыточность сложности, равную 1-0,5=0,5, и безизбыточно по энтропии; минимальное представление при тех же параметрах источника безизбыточно по сложности, но имеет максимальную избыточность энтропии 1-0,5=0,5 бита; древовидное представление занимает промежуточное положение.