РАЗДЕЛ 2
МЕТОДЫ СТРУКТУРНОГО ПРЕДСТАВЛЕНИЯ ДАННЫХ
Разрабатываются методы двумерного однопризнакового структурного кодирования двоичных данных с целью повышения степени сжатия информационных потоков в АСУ. Определено, что дополнительный учет ограничений на количество серий единичных элементов в двоичных последовательностях чисел обеспечивает увеличение степени сжатия информационного потока. Проведена оценка степени сжатия двоичных данных в информационных сетях АСУ на основе разработанного кодирования.
2.1. Структурная избыточность при кодировании информационных потоков
Для обоснования того, что за счет выявленных закономерностей относительно количества серий единиц в структурном пространстве осуществляется дополнительное сокращение избыточности необходимо доказать неравенства:
; (2.1)
, (2.2)
где, , - множества двоичных последовательностей, удовлетворяющих соответственно ограничениям на позиции единиц, на количество серий единиц и на количество серий единиц в структурном пространстве [16, 127, 159, 166].
Для доказательства неравенства (2.1) необходимо показать, что выполняется соотношение:
, где ; , (2.3)
т.е. обосновать взаимонезависимость множеств двоичных последовательностей в структурном пространстве, полученных для разных значений признаков и (где , - количество серий единиц соответственно для -й и -й двоичных последовательностей, - максимальное количество серий единиц, которое может содержатся в двоичной последовательности длиной элементов, ).
Действительно, соотношение (2.3) выполняется, поскольку выполняется условие взаимонезависимости для различных однопризнаковых множеств без ограничений на возможные позиции единиц
, где ; . (2.4)
Поскольку условие (2.4) выполняется для произвольных ограничений на позиции единиц, то оно также будет выполняться в условиях наложения конкретных ограничений (соотношение (2.3)).
Из взаимонезависимости множеств следует, что они являются слагаемыми множества структурных чисел . Причем знак равенства в выражении (2.1) будет стоять тогда, когда наложены запреты на появления единиц для всех позиций. Неравенство (2.1) доказано.
Рассмотрим доказательство неравенства (2.2). Двоичная последовательность будет принадлежать множеству тогда, когда через заданную позицию с () не будет проходить серия единиц, т.е. структурные ограничения трактуются как запрет появления единиц на определенной позиции. Значит, на расположение серий единичных элементов накладываются дополнительные запреты, задаваемые структурными ограничениями . Отсюда следует, выполнение неравенства (2.2). Знак равенства в соотношении (2.2) будет тогда, когда для всех позиций разрешено появление единичных элементов [6, 13, 16]. Примеры запрещенных двоичных последовательностей показаны на рис. 2.1.
а) общая схема выделения двух рабочих зон, состоящих соответственно из трех и одного двоичного элемента и , ;
б) примеры запрещенных двоичных последовательностей с количеством серий равным ;
в) примеры запрещенных двоичных последовательностей с количеством серий равным .
000011100100001000000000010111Рис. 2.1. Пример запрещенных комбинаций для :
2.2. Кодирование двоичных чисел по ограниченному количеству серий единиц
Перед разработкой процесса кодирования дадим определение однопризнаковому двоичному структурному числу.
Определение 1. Множеством однопризнаковых двоичных последовательностей в структурном пространстве называется множество структурных чисел с двоичным алфавитом, для которых значение структурного признака принимает заранее заданное значение.
Определение 2. Однопризнаковым структурным кодированием двоичных данных в структурном пространстве называется система выражений, обеспечивающая формирование кода-номера двоичному структурному числу, элементы которого удовлетворяют заданному структурному признаку. (Система выражений, определяющая номер заданной двоичной последовательности в множестве однопризнаковых структурных чисел).
В нашем случае структурным признаком является количество серий единиц. Поэтому сформулируем следующее определение.
Определение 3. Множеством двоичных последовательностей в структурном пространстве по количеству серий единиц называется пронумерованное множество двоичных последовательностей, содержащих заданное количество серий единиц, не проходящих через позиции с запретом единиц.
Для определения объема множества докажем следующую теорему [16, 159, 161, 166].
Теорема об объеме множества двоичных структурных чисел по количеству серий единиц. Количество двоичных последовательностей, удовлетворяющих ограничениям (1.15) и (1.16) равно
; (2.5)
, (2.6)
где - значение числа серий для -й допустимой зоны двоичной последовательности (рис. 2.1.а);
- вектор, элементами которого является k-я комбинация количеств серий единиц в допустимых зонах , ;
Z - количество допустимых зон в двоичной последовательности;
- количество векторов (количество комбинаций длиной Z, составленных из элементов ;
- количество двоичных элементов в -й допустимой зоне;
- количество допустимых двоичных последовательностей, полученных для -й допустимой зоны по количеству серий единиц, равному для вектора ;
- количество допустимых двоичных последовательностей, полученное с учетом обработки всех Z допустимых зон для k-го вектора значений величин .
Доказательство. Система структурных ограничений делит исходную двоичную последовательность на допустимые и запрещенные зоны (рис. 2.1.а). Запрещенные зоны состоят из элементов, на позициях которых запрещено появление единицы, т.е. . Допустимые зоны располагаются между запрещенными зонами и на их позициях допустимо появление единиц. Обозначим число допустимых зон через Z, . Причем , когда все элементы двоичной последовательности равны 0. Пример множества двоичных структурных чисел по количеству серий единиц для ,