English
!

Доклады

Windows-приложение для построения кодов Шеннона-Фано с разбиением множеств методом целочисленного программирования

Мещеряков В.В.

ГБПОУ Колледж «Царицыно», Россия, 115563, Москва, ул. Генерала Белова 6, Тел.: 8(495)393-89-58, E-mail: meshcheryakov.valery@gmail.com

Разработано Windows-приложение с графическим интерфейсом пользователя для кодирования данных по алгоритму Шеннона-Фано [1], включающему решение задачи целочисленного программирования [2] о разбиении множества на подмножества по заданному отношению объёмов подмножеств.

Приложение позволяет сформировать одномерный массив вероятностей вручную, вводя элементы массива в строку ввода, или с помощью генератора случайных чисел, вводя в строку ввода число букв первичного алфавита. Сумма элементов массива вероятностей должна быть равна 1 с ошибкой менее $10^{-5}$. Предусмотрена сортировка вектора вероятностей по убыванию величин его элементов и восстановление первичного порядка его элементов.

Приложение допускает изменение числа рекурсий для создания узлов сетки по которой идёт построение дерева вероятностей. Предусмотрены разные варианты графического отображения сетки и дерева вероятностей. Имеется возможность вывода в текстовый файл числа букв первичного алфавита, максимального числа разбиений на подмножества, абсолютной разности 1 и суммы вероятностей букв алфавита, отношения объёмов подмножеств, величин вероятностей корня и узлов дерева вероятностей и таблицы кодовых слов. Кроме того, кодовые слова алфавита с числом букв $N\le 32$ выводятся в графическое окно.

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

Проектирование графического интерфейса пользователя осуществлено средствами разработки математического обеспечения в среде MATLAB [3].

Литература.

1. Чисар И., Кёрнер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти. М.: Мир, 1985.

2. Wolsey L. A. Integer Programming, John Wiley \& Sons, 1998.

3. Кетков Ю., Кетков А., Шульц М., MATLAB 7. Программирование, численные методы. СПб.: БХВ-Петербург, 2005.

© 2004 Дизайн Лицея Информационных технологий №1533