РАЗДЕЛ 2
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ БИНОМИАЛЬНО-ПОЛИАДИЧЕСКОГО представления данных С
ПРОИЗВОЛЬНЫМ АЛФАВИТОМ
Разрабатываются теоретические основы биномиально-полиадического представления
видеоданных с произвольной мощностью алфавита, включающие в себя: вывод
аналитического выражения для определения объема допустимого множества, системы
правил нумерации и декодирования, а также доказательство того, что
разработанное представление не противоречит теориям биномиального и
полиадического представления данных. Доказывается взаимооднозначность
биномиально-полиадического представления видеоданных, что позволяет
восстанавливать изображения с нулевой погрешностью. Исследуется вид
избыточности, устраняемой в результате биномиально-полиадического кодирования.
2.1. Определение объема биномиально-полиадического множества
Разработка теоретических основ включает в себя [34, 35]:
· определение объема биномиально – полиадического множества;
· разработку системы правил, ставящую в соответствие биномиально–полиадическому
числу код-номер;
· оценку эффективности разработанного представления.
Построение базисного множества биномиально-полиадических чисел. Базисным
биномиально–полиадическим (БП) множеством называется множество комбинаций,
составленных из элементов , , удовле-
творяющих ограничениям:
, ; (2.1)
, (2.2)
где - ограничение на максимальное значение -го элемента изображения; - вектор,
составленный из элементов ; - сумма значений элементов обрабатываемой
последовательности; - длина обрабатываемой последовательности и размерность
биномиально-полиадического прямоугольника.
Последовательности , принадлежащие БП множеству, называются биномиально –
полиадическими числами. Пример биномиально-полиадических чисел, элементы
которых имеют ограничения на динамический диапазон, равные , , и , а сумма
элементов равна , представлен в приложении А табл. 1.
Для определения количества различных БП чисел сформулируем и докажем теорему.
Теорема об объеме биномиально-полиадического множества. Количество различных
биномиально-полиадических чисел, которое можно составить из последовательностей
, удовлетворяющих ограничениям (2.1) и (2.2), равно
или
(2.3)
где - объем биномиально-полиадического множества; - количество вложенных сумм,
; - количество величин в каждом слагаемом, ;
- число -сочетаний с повторениями из элементов
- параметр, значение которого зависит от величин и (табл. 2.1).
Доказательство. Доказательство теоремы будем проводить в два этапа [34, 35]. На
первом этапе найдем значение , когда величина суммы , соответствует
неравенствам
. (2.4)
На втором этапе получим значение объема БП множества без ограничений на сумму и
на значения динамического диапазона.
Первый этап. Рассмотрим последовательность полиадических чисел, удовлетворяющую
ограничению (2.1). Пример такой последовательности приведен в табл. А.2
приложения А. Зададим для них принцип нумерации, определяемый следующим
правилом.
Таблица 2.1
Значения параметра в зависимости от величин и
. . .
. . .
. . .
. . .
. . .
Принцип нумерации. Из двух полиадических чисел и меньшим, т.е. стоящим левее и
имеющим меньший порядковый номер, считается то число, у которого старший
элемент будет меньшим, т.е. , если выполняются условия
, , а .
Разобьем полученную последовательность полиадических чисел по равномерным
прямоугольникам в соответствии с правилом.
Правило построение биномиально-полиадического прямоугольника:
· построение БП прямоугольника начинается с младших значений обрабатываемых
последовательностей. В начале строится двумерный БП прямоугольник для элементов
и . При этом значения элементов и изменяются соответственно в интервалах и .
Остальные, более старшие элементы БП числа остаются без изменения и их значения
равны 0. Элементами БП прямоугольника являются значения сумм соответствующих
биномиально-полиадических чисел. В таком прямоугольнике будет строк и столбцов.
Размер двумерного БП прямоугольника равен ;
· после формирования БП прямоугольника формируется БП линейка, элементами
которой являются двумерные биномиально-полиадические прямоугольники. Начальным
прямоугольником является двумерный прямоугольник, построенный на предыдущем
этапе. Последующие БП прямоугольники в составе линейки формируются путем
увеличения значения элемента на 1 при фиксированных значениях младших
элементов. Биномиально-полиадическая линейка считается построенной тогда, когда
;
· после образования БП линейки осуществляется построение очередной линейки. Для
этого значение элемента увеличивается на 1 и повторяются два предыдущих этапа.
После формирования линейки с начальным индексом равным образуется четырехмерный
биномиально-полиадический прямоугольник. Он состоит из двумерных
биномиально-полиадических прямоугольников;
· процесс формирования биномиально-полиадического прямоугольника продолжается
до тех пор, пока для самого старшего элемента БП числа не будет достигнуто
условие .
Пример построения четырехмерного БП прямоугольника рассмотрен в табл. 3
приложения А. На основе правила построения БП прямоугольников можно
сформулировать следующие определения:
Определение 2.1. Биномиально-полиадическим прямоугольником -го порядка
называется прямоугольник, образованный основаниями полиадического множества, с
элементами равными значениям сумм :
; ; . (2.5)
Наименьшим неделимым элементом такого прямоугольника есть двумерный БП
прямоугол