Оценка времени преобразования равновесных кодов в биномиальные

Оценка времени преобразования равновесных кодов в биномиальные

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

Филиал Национального университета внутренних дел в г. Сумах

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

Равновесные коды с параметрами n, k имеют одинаковую длину r_р = n, и равное количество единиц k в каждой комбинации, а также отвечают условиям

n > k, (1)

k ? 1. 2)

Биномиальные кодовые комбинации с теми же параметрами n и k имеют различную длину r_i ? n-1, а кодообразующие правила и ограничения для них описаны в [2].

Проанализируем время работы алгоритма получения биномиальных кодов из равновесных, при котором в каждой равновесной кодовой комбинации отбрасываются единицы справа до первого нуля или же отбрасываются нули справа до первой единицы. Разность между длиной каждой равновесной и соответствующей ей биномиальной кодовой комбинации будет составлять число тактов (или время) преобразования одной кодовой посылки. Для оценки усредненного времени преобразования, когда с равной вероятностью используются все кодовые комбинации, входящие в код с параметрами n и k, в данной работе исследуется средняя длина биномиальных кодовых комбинаций r_ср, которая определяется как сумма длин всех биномиальных кодовых комбинаций r_i (i = 1, 2,…i,...N), деленная на общее количество кодовых комбинаций N = :

= /N. (3)

Тогда искомое время работы алгоритма перехода от равновесного кода к биномиальному будет определяться средним количеством тактов такого преобразования r_рб:

/N. (4)

В работе [3] получена формула, позволяющая вычислить среднюю длину биномиальных кодовых комбинаций r_ср в зависимости от параметров кода:

r_ср = . (5)

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

k_min = 1, (6)

а из (1) следует:

n_min = 2, (7)

k_max = n - 1. (8)

Максимальная величина параметра n_max математических ограничений не имеет.

Средняя длина биномиальных кодовых комбинаций r_ср (5) является непрерывной функцией, так как при выполнении условий (1), (2) она определена при всех значениях n и k, ограниченных (6) - (8).

Проанализируем наличие экстремумов функции r_ср (5), для чего вычислим ее первую производную по k при фиксированном n, и приравняем ее к нулю

= = 0. (9)

Из (9) следует вывод, что первая производная обращается в нуль при

k = n/2. (10)

Следовательно, функция r_ср имеет экстремум в точке k = n/2.

Чтобы определить, является ли найденная экстремальная точка максимумом или минимумом, возьмем производную из (9). Если она в точке k = n/2 отрицательна, то здесь имеет место максимум, а если она положительна, значит это минимум.

= . (11)

Подставляем в (11) значение k = n/2. Тогда

¦_k=n/2 = -- 1/2(n² + 4n +4). (12)

Вторая производная при всех допустимых значениях n будет отрицательна, следовательно, в точке k = n/2 функция имеет один максимум.

Как было сказано выше, n и k являются целыми числами, следовательно, утверждение о максимуме функции (5) при k = n/2 справедливо для четных значений n, поскольку при нечетности n величина n/2 будет дробной, а не целочисленной. Например, при n =7,
k = n/2 = 3,5, тогда ближайшими целыми числами будут k_max1 = n/2 + +1/2, k_max2 = n/2 - 1/2. Очевидно, что при нечетном параметре n средняя длина биномиальных кодовых комбинаций r_ср (5) имеет две одинаковых точки максимальной величины при значениях k_max1 = n/2 + 1/2 и k_max2 = n/2 - 1/2. Действительно, при подстановке в (5) нечетных значений k_max1 и k_max2 получается одинаковый результат

¦_нечет = . (13)

Поскольку функция r_ср (5) непрерывна в заданной области определения и имеет один максимум при величине k = n/2, то своего минимума она достигает при крайних значениях k = 1 и k = n -1. Действительно, подставляя в (5) k = 1 и k = n -1, в обоих случаях получим

= = = . (14)

В качестве примера выполнены расчеты средней длины биномиальных чисел r_ср по формуле (5) для различных значений n и k внутри области их определения. Результаты приведены в таблице 1, а соответствующие им графики представлены на рис. 1. Полученные данные свидетельствуют о правильности сделанных выше утверждений.

Таблица 1 - Cредняя длина биномиальных чисел r_ср в зависимости от параметров n и k

Рисунок 1 - Средняя длина биномиальных чисел r_ср в зависимости от параметров n и k

Выполнены также расчеты среднего количества тактов преобразования равновесных чисел в биномиальные r_рб по формуле (4) для тех же, что и выше значений n и k, результаты приведены в таблице 2, а соответствующие графики представлены на рис. 2:

Таблица 2 - Среднее количество тактов преобразования r_рб из равновесных кодов в биномиальные в зависимости от n и k

Рисунок 2 - Среднее количество тактов преобразования равновесных кодов в биномиальные r_рб при различных параметрах кодов n и k

Минимальные значения среднего количества тактов преобразования будут наблюдаться при максимальной длине биномиальных чисел , т. е. при значении k = n/2. Тогда, подставляя эту величину в (5), получим

= n² /(n+2). (15)

Используя формулу (4), определим

= n - . (16)

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

= n - . (17)

Проведены расчеты по формулам (16) и (17), их результаты представлены в таблице 3.

Таблица 3 - Максимумы и минимумы среднего количество тактов преобразования r_рб из равновесных кодов в биномиальные при различной длине кода n

Выводы

Время преобразования равновесных кодов в биномиальные r_рб определяется средней длиной биномиальных кодовых комбинаций r_ср, которая является функцией длины равновесных кодов n и количества единиц в них k. В работе установлено, что средняя длина биномиальных кодовых комбинаций в случаях четного n имеет один максимум при k = n/2, а в случаях нечетного n - две одинаковых точки максимальной величины при k = n/2 + 1/2 и k = n/2 - 1/2. Два одинаковых минимума r_ср наблюдаются при k = 1 и k = n - 1.

Среднее время преобразования равновесных кодов в биномиальные r_рб минимально при максимальной средней длине биномиальных кодовых комбинаций, и оно максимально при их минимальной средней длине. Минимальное время преобразования стремится к двум тактам работы алгоритма преобразования, а максимальное - к n/2 тактам.

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

Summary

The paper estimates the functioning time 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. А. А. Борисенко, В. Б. Чередниченко. Нумерация равновесных кодов на основе биномиальных чисел // Право і безпека. - 2004. - №4.

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

3. И. А. Кулик. О средней длине двоичных биномиальных чисел // Вісник СумДУ. - 2004.

4. Андерсон Джеймс А. Дискретная математика и комбинаторика // Пер. с англ. - М.: Изд. дом «Вильямс», 2003. - 960 с.

5. Амелькин В. А. Методы нумерационного кодирования. - Новосибирск: Наука, 1986. - 155 с.

6. Борисенко А. А Введение в теорию биномиального счета: Монография. - Сумы: ИТД «Университетская книга», 2004. - 85 с.