Оценка эффективности сжатия равновесных кодов на основе биномиальных чисел

Сумский филиал Харьковского национального университета внутренних дел

ОЦЕНКА ЭФФЕКТИВНОСТИ СЖАТИЯ РАВНОВЕСНЫХ КОДОВ НА ОСНОВЕ БИНОМИАЛЬНЫХ ЧИСЕЛ

В. Б. Чередниченко, ст. преподаватель

Введение

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

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

При этом для оценки эффективности метода используется расчет быстродействия соответствующих алгоритмов и коэффициентов сжатия. Оценка быстродействия была проведена ранее в работах [2, 3]. В то же время оценка коэффициента сжатия алгоритмов, использующих данный метод, является актуальной. Поэтому целью настоящей работы является определение влияния параметров равновесных кодов на эффективность их сжатия методом последовательного биномиального счета. Задачей работы является оценка коэффициента и времени сжатия в зависимости от параметров кода.

Оценка коэффициента сжатия в зависимости от параметров кода

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

. (1)

Например, для равновесного кода с параметрами , величина = 15 и соответственно значение J согласно формуле (1) равно 3,9. При этом выполняется неравенство Jn, т.е. происходит уменьшение длины исходного кода, величину сжатия которого следует оценить с помощью коэффициента сжатия S:

. (2)

Для примера в таблице 1 приведены значения коэффициента сжатия S по формуле (2) при длине равновесных кодовых комбинаций n от 5 до 20 в зависимости от количества единиц k в них.

Из данных таблицы 1 видно, что коэффициент сжатия имеет максимальную величину при двух крайних значениях k = 1 и k = - 1.

На рис. 1 представлены графики, соответствующие данным таблицы 1.

Величины максимального коэффициента сжатия при различной длине кодовых комбинаций в диапазоне «n1» от 10 до 100 и диапазоне «n2» от 100 до 1000 приведены в таблице 2. Из нее видно, что чем длиннее код, тем больше максимальный коэффициент сжатия.

Таблица 1- Коэффициент сжатия S равновесных кодов в результате их нумерации (по формуле (2))

Рисунок 1 - Коэффициент сжатия равновесных кодов при их длине от 5 до 20 и при различном числе единиц k в них

Таблица 2 - Максимальный коэффициент сжатия для кодовых комбинаций длиной «n1» от 10 до 100 и «n2» от 100 до 1000

Минимальный коэффициент сжатия имеет место при

для четных значений n, а для нечетных n имеется минимум в двух точках

и

.

Величины при кодовых комбинациях длиной n от 10 до 100 (диапазон «n1») и от 100 до 1000 (диапазон «n2») представлены в таблице 3.

Таблица 3 - Минимальный коэффициент сжатия Smin для кодовых комбинаций длиной n от 10 до 1000

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

При практической реализации количество двоичных разрядов , необходимое для записи максимального номера биномиального числа в двоичной системе, может принимать только целые значения. Тогда при округлении J в большую сторону реальный коэффициент сжатия будет несколько меньше теоретически достижимого, за исключением величин n, кратных 2n. Проиллюстрируем это уменьшение на примере при длине кодов, равной (- 1), , (+ 1) для n от 4 до 20 (табл. 4).

Для удобства оценки уменьшения коэффициента сжатия вычислим величину его уменьшения как отношение Sокр/Sнеокр (табл.4). Эти величины сведем в отдельную таблицу 5 при длине кодов, равной (- 1) и (+1), и для значений n от 4 до 2048 (табл. 5).

Таблица 4 - Коэффициент сжатия при неокругленном J и округленном m количестве разрядов чисел

Таблица 5 - Уменьшение коэффициента сжатия Sокр/Sнеокр для значений n от 4 до 2048

Как видно из таблицы 5, отношение Sокр/Sнеокр приближается к единице, причем быстрее для значений n = (-1) и медленнее для значений

n = (+ 1).

Связь времени сжатия с коэффициентом сжатия

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

, (3)

где n,k соответственно длина равновесного кода и количество единиц в нем.

В работе (3) оценено количество тактов преобразования биномиального кода в его номер с использованием алгоритма последовательного счета при условии равной вероятности появления каждой из кодовых комбинаций, которое равно

. (4)

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

, (5)

где слагаемые берутся из формул (3) и (4).

По формуле (5) просчитано общее количество тактов , приводящих к сжатию равновесного кода в номер, при длине кодов от 4 до 20 результаты представлены в табл. 6.

Таблица 6 - Общее количество тактов преобразования равновесного кода в номер при длине кодов от 4 до 20

Данные таблиц 1 и 6 показывают, что коэффициент сжатия и общее количество тактов преобразования ведут себя противоположным образом при изменении количества единиц в кодах. Для иллюстрации этого построен общий график для и x0,01 при длине кода n=12 (см. рис.2).

Рисунок 2 - Коэффициент сжатия и общее количество тактов преобразования x 0,01 при длине кода n=12

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

Выводы

В работе установлено, что в результате нумерации равновесных кодов коэффициент сжатия достигает максимума при двух крайних значениях их параметров: k = 1 и k = n - 1, при этом сжатие возрастает с увеличением длины кодовых комбинаций. Минимальное значение коэффициента сжатия наблюдается при , с ростом длины кодов он асимптотически приближается к единице. Поскольку количество двоичных разрядов, необходимое для записи максимального номера биномиального числа в двоичной системе счисления, может принимать только целые значения, реальный коэффициент сжатия будет несколько меньше теоретически достижимого.

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

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

Summary

The paper estimates the coefficient of compression for transforming algorithm of equipond codes, in which uses methods of binary binоmial count. The results are confirmed by computations, tables and graphics.

Список литературы

1. А.А. Борисенко, В. Б. Чередниченко. Нумерация равновесных кодов на основе биномиальных чисел // Харьков: Право і безпека. - № 3 - 4. - 2004. - C.194 -197.

2. В.Б. Чередниченко. Оценка времени преобразования равновесных кодов в биномиальные // Вісник СумДУ. _ № 12(71). - 2004. - С. 113 - 117.

3. В.Б. Чередниченко. Оценка быстродействия нумерации биномиальных чисел методом последовательного счета //АСУ и устройства автоматики. - № 131.- 2005.

4. Борисенко А. А Биномиальный счет. Теория и практика: Монография. - Сумы: ИТД «Университетская книга», 2004. - 170 с.