Разработка и исследование универсального машинного алгоритма системы многократного сжатия/развертывания дискретных данных и её имитационное моделирование Сулейманов, Акиф Шамил оглы

Введение к работе

Актуальность работы. Информационные ресурсы становятся

основным национальным богатством, а эффективность их промкалешой эксплуатации одним из определяющих факторов уровня экономического развития страны. Несмотря на то. что емкость различного рода запоминающих устройств постоянно увеличивается, все равно с кг. остается узким местом в периферийном оборудовании, т.к. одновременно , и с еще большей скоростью увеличиваются обїеш информации, лодлеяетие фиксации, обработке, передачи и хранению. Если рассмотреть структуру расходов на периферийное оборудование компьютеров даже начала 80-х годов, то обнаружим, что более 50;; - ов всех расходов падают на долга различного рода еоломинактщх устройств и носителей информации сГрзг Пейстрик. Как удвоить, а то и утроить емкость

жесткого диска. PC Мазагіпе/Russion Edition, К Z_t 199Я. г. 15-26).

БольшінствоІ прогнозов сходятся ка том. что к началу следующего столетия в Технически развитых странах основная масса информации будет храниться в безбумажном зяде в системах памяти компьютерных сетей. Поэтому, эффективность системы обработки информации во многом зависит от организации структуры физического хранения данных и рационального использования ре.урсов вычислительной системы. Одним из существенных путей повышения эффективности функционирования таких систем (вообще систем хранения, обработки и передачи данных ) является разработка и применение современных методов и средств сжатия и однозначного развертывания дискретных данных. Вообще на современном этапе развития информационных технологий и рыночной экономики проблема сжатия данных является актуальной, т.к. путем разработки и применения ' соответствующих программно-аппаратных средств может быть успешно Грешен ряд важ- нейпмх задач, а именно:

-повышение эффективности использования ресурсов системы накопления, хранения к передачи данных <.памятей, коммуникационных каналов, сетевого оборудования и т.д.);

-увеличения надезиости и секретности хранения и передачи данных:

-поякгсение релевантности поиска дапшх.

Зет некоторые области возможно пирс ко го лрш-^-неклл сх./гия

дшшкх- сжтомы централизованной и ji-.слрєдоленшй со работки' данных: техника связи-, методы обнатруквнуя и исправления оос.оок в системах хранения а передачи данных; микропроцессорные системы-, книгохранилища; балі дан:шх . базы знаний и др.

Известии и* широко применяются р. персональных компьютерах сродства сжатия без пстерь : диалоговые - шгр., утилит ARS, ьчик.шд,

PKZIP И ДР; фОНОВЫе - НЛр. , Double DisJi, Superior, Stacker И

сопроцессор stacker аї/ig и др.), дтало.говые и автоматические метод}! сжатия данных с некоторыми потерями. Эти средства, в основном, чисто программные продукты хороши для применения в локальных диалоговых системах, но не совсем пригодны для универсального, применения в системах накопления, хранения и передачи данных общего (коллективного¹, использовашя. Они в некоторой степени удовлетворяют требованиям эффективности и обратимости, однако свойством массовости, даже в пределах сжатия файлов одного к того же типа, в определенной степени обладают только некоторые. Отмеченное является существенным недостатком и. в основном, по этой причине для глобального применения сжатия в системах накопления, хранения, обработки и передачи . данных недостаточно разрабатываются сколь-нибудь проблемно-ориентирошн_: ные аппаратно-программные средства, а тем более средства общего назначения. Наряду со средствами сжатия данных указанного тина необходимо иметь и такие, которые основывались бы на использовании или статистических,¹ или структурно-пространственных. или хе определенных комплексных характеристиках языка и (или; структуры первичного (или промежуточного) представления данных, т.к. они порождают универсальные методы.

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

Работа выполнялась согласно комплексно-целевой программе -Создание к внедрение микропроцессорной техники в народное хозяйство Азербайджанской Республики" по теме "Микропроцессорно-прог-рцм.мные средства, повышения эффективности использования ресурсов выделительных комплексов, систем и еот*Я" ( рогистряционннй И Є1дВЗС<031ййї на I'SUC-ladZ Г.Г. И 1УІ1-108Ї г.г.

Цель работы. Основная цель данной работы состоит в-синтезе угогеєреальних алгоритмов сжатия данных и соотштствущих программно - аппаратных ерздстз. позволящих применять их с достаточной эффективностью в более вироком спектро. Основными задачами, подлежащими решению для достижения указанной цели язля-

ЮТСЯ:

1. Исследование методов сжатия данных, основанных нз вероятностно-статистических характеристиках машинного, представления информации при виборе оптимального ее точки зрения минимизация среднего значения числа элементарных сигналов, приходящихся на ОГЯУ Сукву первичного сообщения) алфавита сжатия, определяемого в соэтштствии с локальными статистическими параметрами исходного двоичного кортежа.' Определение типовых процедур обработки при сиатки/развертывании данных, с целью синтеза типовых модулей обцого магзшного алгоритма преобразований, удоб:юго для аппаратно-программной реализации.

С. Нефедова!жз вопросов, связанных с неразновероятностями кодовых обозначений, получаемых при статюі и разработка машинных алгоритмов и технических приемов снятия этих вопросов при аппаратно-программной реализация сї-лїйД/ ;\з?г*ртнвзнйя данных.

3. Разработка быстрых маиинных алгоритмов определения и фиксации легальных статистических характеристик кортежей и анализ возможностей их аппаратно-программной реализации.

і.Машинное имитационное моделирование процессов функционирования типовых модулей основных блоков и узлов системы сжатия/раз-вертнвания данных при выполнении различных методов (алгоритмов^ пряного и обратного преобразований. Анализ результатов имитационного моделирования, синтез общего машинного алгоритма и системы зго реализации на базе типовых модулей,

1. 'Разработка технологии обработки данных с применением, аппаратно-программных средств сжатия/развертывания.

2. Разработка основ; нх аспектов построения и использования системы сяатия/развертнвания данных. _ч

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

денних искольсоЕзно имитационно* моделирование, для- чего рчзрйботан і'і&кьт программ имитационного моделирования с соотеот-ствукцей библиотекой имитационного моделирования типових фу!п:плналь"нх блоков на базе алгоритмического язика Турбо Си. Уни-вер сальный машинный алгоритм сиатия/развертнЕапия данных смоделирован программой, составленной на языке assembler івн рс/ат.

Научная новизна.

1. Мсследо"ваны"методн сжатия данных, основанные на применении
концепции логических шкал позиционного кодирования (ЛШПК) и про
анализированы полученные результаты, с точки зрения возможностей

синтеза относительно универсального алгоритма и соответствующих аппаратно-программных средств модульного типа для обработки данных, представленных в машинном коде с использованием, переменного щага квантования ( кванты сжатия переменной длины і. Основными характерными особенностями универсализации исследованных методов являются: использование вероятностно-статистических характеристик, алфавита саатия; варьирование длиной шага квантования.что открывает значительные возможности в расширении диапазона выбора эффективного алфавита сжатия; используя механизм ЛЩІК возможность выполнения декомпозиции исходного файла на эффективные, с точки зрения сжатия, подфайлы; адаптивность алгоритмов сжатия, которая достигается путем использования механизма ЛШПК, квантов переменной длины, паспортизации файлов и теговнх (самоопределяемых) структур организации сжатых образов, обеспечивающих их обратимость; применение .многократного сжатия данных в глубину.

2. .Предложена новая концепция динамического машинного опре
деления; локальных вероятностно-статистических характеристик
сегмэн?а сжатия параллельно с квантованием исследуемого- сегмента и
формированием булевой матрицы распределения букв алфавита снаеия
по длине сегмента, соответствующего текущему значению кванта. Раз
работаны параллельные алгоритмы функционирования соответствующих
блоков.

3.Синтезирован интегрированный универсальный алгоритм скатия/ развартквашм данных.и разработаны оригинальные машинные алгоритмы функционированияЧспециализироганньх модулей обработки данных, а именно: квантования двоичной стохастической последовательности переменным шагом квантования и получения статистических данных;

быстрого упорядочения статистических данных (многораэрадада двоичных чисел) путем оригинального преобразования идентификатора счетчика в соответствующий унитарный код его содержимого- і используя возможности совместного функционирования блоков "выделение старшей единицы", дешифратор", "шифратор" и "муяьтшшжсор"); формирования матриц ЛЕПК оригинальным применением счетчика " богатая единица" и тегов сжатих образов данных.

4. Разработаны модули параллельных алгоритмов преобразования
данных и произведено их имитационное моделирование.Составлен пакет
программ имитационного моделирования со своей библиотекой типовых
модулей.

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

Практическая ценность и внедрение результатов работы,
і ~ ~~

Разработанный универсальный машинний алгоритм в качестве программного средства может применяться в персональных компьютерах (автономно или в сетях) для сжатия/развертывания либкх типов данных с целью повышения емкостей дискет, винчестеров и узловых буферных устройств сете."!;, а так же скорости и надежности передачи данных.'

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

Программные средства применены в узловых сетях Азербайджан-, ской - Республики (отдел Автоматизированных систем управления Академии Наук Республики>: Европейская Академическая и Исследовательская сеть (EARN): ihterhet. В результате применения программ имитационного моделирования выбраны наиболее эффективные режимы сжатия данных в каналах указаннных сетей, а разработанные интегрированные средства многократного сжатия/развертывания дам-па для аппаратно-программной реализации (Акт внедрения приводится в дтгссрі.гагіиок.-.'с.і жбо^е).

Аііро&і!і«л работы. 0.":H0BifUi3 регулі тати диссертационной работы Лмлї~Д№ІжЗни и обсуждены на:

-научней конференции аспирантов Азербайджанской Республики (198G, 1ЭЗЗ гг.);

-республиканском совевднии-семинаре "Создание и внедрение в народное хозяйство республики микропроцессорных средств и систем"

(1984 Г.):

-всесоюзной научно-техшіческой конференции "Проблемы создания и использования мини- и микро-ЭБМ (Вильнюс. Москва, 1Э85 г.);

-научно-методических конференциях профоссорско- лрелодаватель-.сшго состава АзТУ (1988-1994 гг.);

-научном семинаре Института Кибернетики АН Азербайджанской Республіки.

Публикация. Основные результаты излокенн в 8 научных работах сиз нйТг~іЗоойі находятся в печати)

Структура и объем работы. Диссертационная работа состоит из