автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка и исследование комбинированных методов сжатия данных и их реализация в структурах запоминающих устройств специализированных ЭВМ

ВВЕДЕНИЕ.

1. ОБЗОР И АНАЛИЗ МЕТОДОВ И СРЕДСТВ СЖАТИЯ ИНФОРМАЦИИ.

1.1. Информационные основы безызбыточного кодирова- Q ния данных. у

1.2. Зависимость эффективности вычислительной системы от организации памяти и принципов передачи информации между устройствами. «

1.2,1. Анализ эффективности организации иерархической памяти с использованием модели массового обслуживания. ™

1.3. Уравнение баланса системы

1.4. Классификация методов сжатия и краткая их характеристика

1.4.1. Статистические методы сжатия.

1.4.2. Корреляционные методы сжатия.

1.4.3. Комбинированные методы сжатия

1.5. Выводы.

2. МЕГОда СЖАТИЯ ИНФОРМАЦИИ.

2.1. Метод сжатия совмещенных последовательностей

2.1.1. Обоснование метода сжатия

2.1.2. Генерация совмещенных последовательностей с помощью сдвигового регистра. 4У

2.1.3. Операторная модель регистра сдвига

2.1.4. Матричная форма представления регистра p-R сдвига.

2.2. Синтез накопителей на сдвиговых регистрах

2.2.1. Основные определения

2.2.2. Методика синтеза накопителей на сдвиговых ftT регистрах.

2.3. Полиномиальный метод сжатия.

2.4. Выводы

3. РЕАЛИЗАЦИЯ МЕТОДОВ СЖАТИЯ. ?

3.1. Реализация принципа сжатия совмещенных последо- вательностей

3.1.1. Исследование методов организации ЗУ с последовательным доступом

3.1.2. Организация ЗУ с параллельной выборкой.

3.2. Реализация полиномиального метода сжатия. П

3.2.1. Применение полиномиального метода сжатия для ттт реализации управления.

3.3. Выводы.

4. АВТОМАТИЗИРОВАННЫЕ СРЕДСТВА ОЦЕНИВАНИЯ СЖАТИЯ КОДИРОВАНИЯ ИНФОРМАЦИИ.

4.1. Методика оценивания.

4.2. Применение и организация моделирования.

4.2.1. Исследование метода сжатия совмещенных после- тоо довательностей. мг

4.2.2. Оценка полиномиального метода сжатия.

4.2.3. Оценивание автоматного метода сжатия.Е

4.2.4. Оценивание сжатия методом Хаффтна.

4.3. Организация системы оценивания

4.4. Выводы.

данных. Можно считать, что сокращение объема и надежное кодирование не цротиворечиво, если применять последовательно, например, сжишнются и восстанавливаются данные с искусственно введенной избыточностью. При этом методы сжатия не должны быть коррелированы с методами увеличения надежности, что в большинстве случаев соблюдается.Вопросы помехоустойчивого кодирования в работе не рассматриваются.1.2. Зависимость эффективности вычислительной системы от организации памяти и принципов передачи информации между устройствами Эффективность сжатия может быть связана со снижением стоимости хранения инфорь/ации (сокращение объеьа ЗУ, использование дешевых и доступных средств хранения информации, сокращение числа уровней в иерархии памяти и т.д.). С другой стороны, целесообразно сохранить имеющиеся ресурсы памяти, при этом эффективность сжатия будет связана с повышением производительности системы (ускорение доступа, сокращение времени преобразования). Существует зависимость между производительностью П системы, объемом М и организацией ^ ЗУ, которая должна учитываться при физической организации данных: П= n(M,S]Структурную организацию можно считать преимущественно зависящей от требуемого объема М, так как при ограниченной номенклатуре ЗУ организация памяти - разделение её на уровни иерархии — связана преимущественно с требуемой емкостью [2l] .Таким образом, необходимо исследовать зависимость П = П(М).Сжатие информации приводит к относительному сокращению требуемого объеьв М - с одной стороны, и, с другой - к дополнительным затратам времени - прямому снижению производительности.Следовательно, если учитывать оба эти фактора, то зависимость П от сжатия М может иметь экстремальные значения, которые зависят от конкретных методов сжатия и характерных для них колебаний параметров. Найти эти экстремальные значения можно при рассмотрении существа методов сжатия.Вместе с тем,зависимость П(М) при выбранном методе представления информации существенно определяется статистическими характеристиками вычислительного процесса. Так, например, при относительно невысокой интенсивности обращения к данным (большие задержки при обработке информации) увеличение объела М будет слабо сказываться на производительность П. Следовательно, применение сжатия в этом случае будет только снижать производительность П, так как увеличивает время обработки.При высокой интенсивности обращения к ЗУ можно ожидать, что сжатие будет положительно влиять на повышение производительноети,- необходимо следить за тем, чтобы сложность декодирования не привела к существенным задержкам при обработке информации* Анализ производительности вычислительных систем (ВС) является предметом многочисленных исследований, учитывающих специфику организации вычислительного процесса, управляемого операционной системой [5,39,102]. Кроме ьакроуровня, учитывающего параметры мультипрограммной обработки нескольких задач, исследуется более низкий уровень - взаимодействие процессора и основной памяти, в котором учитываются усредненные параметры на множестве задач, проходивших через ВС и конкретизируемых в данный момент [ 5] . I.2.I. Анализ эффективности организации иерархической памяти с использованием модели массового обслуживания Традиционный инженерный подход к анализу основывается на выборе подходящей модели процесса и использовании её для расчета требуемых параметров. Наиболее привлекательшыи являются модели, построенные на базе систем в/ассового обслуживания, для которых может быть найдена аналитическая зависимость, сохханяюп^ основные тенденции моделируемого процесса. Применение таких моделей для точных расчетов, например, объемов буферной памяти, вряд ли может пользоваться доверием вследствие значительных условностей, ограничений, загрубления и не всегда обоснованной экстраполяции реальной статистики, если даже она будет получена.Из графиков (рис, 1.5,6) и выршкешш (1.3), (1,4), (1.5), (1.6) видно, что время обработки запросов (решение задачи ), а следовательно, ж производительность системы памяти существенно зависят от коэффициента сжатия, С зпвеличением /С время обработки заявок уменьшается ,\ соответственно эффективность памяти уъеличивается, Однако минимальное время решения задачи (рис, 1.5,6) в вычислительной системе возможно при некотором опттлальном значении коэффициента сжатия, значения которого зависят от быстродействия процессора и методов сжатия.ЕА л г\ 1,0 0,5 1, d Рис.1.6 Изменение относительной длины очереди в первой ступени памяти в зависхшости от коэффициента сжатия 1.3. Уравнение баланса системы В предыдр^ем параграфе рассматривалась зависимость производительности (для косвенной оценки использовался параметр JJ время пребывания заявки в системе памяти). Сжатие данных приводит к снижению паршлетра U ,т.е. к увеличению производительности вычислительной системы за счет повышения интенсивности обслуживания заявок в иерархической системе памяти.О другой стороны, резервы повышения производительности могут быть выявлены при анализе баланса в системе. Нарушение баланса снижает эффективное быстродействие, так как возникают простои потери времени быстродействующих элементов. Необходимо решать задачу создания сбалансированной системы путем ускорения передачи информации и увеличения интенсивности обработки запросов.Уокорение обмена данными в узких каналах связи вычислительной системы, а следовательно, и повышение ее производительности может быть обеспечено сжатием информации.Для передачи данных на вход АЛБ процессора последовательно выполняется: выборка из ЗУ (С^) ^ - разрядных слов, промежуточное декодирование (кодирование) в ЗУ с преобразованием в про-/ межуточную форму -у^ - разрядные слова, передача по магистрали окончательное декодирование в процессоре и преобразование в /Z. - разрядные слова; S - машинное слово.Задача проектирования структуры систеьш и организации связи включает выбор оптимального сбалансированного принципа хранения и передачи информации, Таким образом, производительность системы определяется не только быстродействием процессора и емкостью памяти ЗУ, но и оптимальным временным соотношением (1.9) между быстродействием устройств системы и временем передачи информации по каналам связи между устройствами. С целью сокращения времени передачи целесообразно применять сжатие передаваемых сообщений.Уравнение баланса (1.9) показывает, что необходимо тщательно оценивать качество сжатия информации, исследовать и оценивать возможности использования аппаратных средств декодирования для снижения отрицательного влияния сжатия на время доступа.Таким образом, сжатие может быть использовано не только для повышения эффективности быстродействия систем, но и для ускорения передачи информации в канале связи при условии сохранения баланса.1.4. Классификация методов сжатия и краткая их характеристика Сжатие рассматривается как преобразование кодирования информации, сокращение её избыточности.Избыточность может быть устранена применением более компактных способов кодирования инфор1(Шз;ии, заключающихся в том, что данное множество элементов информации ti (Aj), выраженное в алфавите Aj, ставится в соответствие некоторому множеству кодовых комбинаций N (Аз)» выраженновяу в алфавите Ag [45,55].Схема классификации известных методов сжатия приведена на рис.1,8. I.4.I. Статистические методы сжатия Статистические методы сжатия требуют знания статистики хранимых или передаваемых данных (управление). В эту группу входит £ Статистичесхше Метод укорочения допустимой дли^ш кодовой комбинации Оптшлальное неравномерное кодирование Сжатие часто повторяющихся элементов данных Устранение неэторых символов на естественном языке Сжатие конечного набора слов Сжатие упорядоченных данных переход от естественных обозначении к более коротким Автоматный метод Методы сжатия г I Корреляционные Сжатие на основе применения различных математичес1шх приемов и способов Сжатие на основе применения относительной адресаЦ1Ш Комбинированные Устранение пропусков и пробелов Свертка данных С^ катие команд (гжкрокоманд) Метод совмещеш-шх последовательностей Полиномиальный метод Рис, 1.8 Классификация методов слсатия большое количество разнообразных способов сжатия информации.Способ укорочения допустимой для данного алфавита длины кодовой комбинации символа fl2,37,44,45,54,62,63j, в котором сжатие производится путем деления исходного алфавита на группы из нескольких символов. Символы, входящие в одну группу.,кодируются одинаковой кодовой комбинацией, кодовых символов при этом требуется значительно меньше,и каждый из них может быть выражен в виде более короткого двоичного числа.Основной недостаток способа - неоднозначность кодирования слов, поскольку неоднозначно кодируются буквы, входящие в одну группу. Нашёл применение для кодирования буквенно-символьной информации в небольших и строго фиксированных словарях информации.Для больших алфавитов наиболее экономичным, по инфоргащонному объему является лингвистический метод описания символов [7, 8], для которого полное описание алфавита Ап складывается из множества относительных описаний всех символов Со и множества полных описаний фрагментов Фп : Ап = Со + Фп.Множество Фп разбивается на компоненты связностей ФJJJ, Фд2, ..., Фд5» где - количество компонент связностей.Фрагменты множества Фп, входящие в разные символы, но связанные с общим фрагментом, образуют подмножество фрагментов, называемых связными.Метод сложен в реализации, обладает низким быстродействием, так как требуется время для выделения и сортировки фрагментов символов массива. Нашел применение в основном в устройствах документирования и отображения информации.Широкое распространение (особенно в США.) получило оптшвльное неравномерное кодирование[54,55,85], использующее статистическую модель вероятностного появления символов алфавита, в результате которой юбеспечивается максимум количества информации на символ сообщения. Учёт реальных вероятностей появления символов приводит к необходимости более вероятные символы кодировать более коротким кодом и менее вероятные - более длинным. Полученный код является неравномерным, поэтому данный метод может быть использован в ЭВМ, работающей с кодами переменной длины,- это один из недостатков метода. Второй недостаток - большое время сжатия, обусловленное необходимостью "собирать" статистику по каждому конкретному гассиву.Поэтому его используют для файлов, чтение и запись которых происходят редко. Метод оптимального неравномерного кодирования символов весьма близок к своему возможному пределу (I.I). Он позволяет сократить до 55-75^ [54] первоначальный объем информационного ь/нссива, а в сочетании с методом подавления повторяющихся символов свыше 80^. Способ чрезвычайно прост и высокоэффективен - это одна из причин его широкого применения на практике по сравнению с другими способами посимвольного кодирования.Очень близок по принципу действия к оптимальному неравномерному кодированию метод сжатия часто повторяющихся элементов данных (символов, слов, чисел, грушш чисел, части текста, прикладных программ) [ю,51,54,87,104,105,100,ПО,III, 112]. Смысл сжатия состоит в попытке выделить часто повторяющиеся элементы данных, которые заменяются более короткими кодами или ссылкой. Алгоритм сжатия,как в [54].включает в себя четыре фазы: - фазу предварительной обработки; - фазу выработки словаря; - фазу сжатия; - фазу декодирования, Метод сжатия позволяет сжимать любые объемы исходной инфориации. Реализуется программно и аппаратно. При программной реализации - затраты миниьильны, но время сжатия велико. При аппаратной значительно сокращается время сжатия, но увеличивается стоимость реализации. Эффект сжатия зависит от характера информации. Объем файлов коммерческой, производственной, финансово-экономической , удается сократить в два раза [54].Метод содержит все недостатки оптимального кодирования, кроме того вспомогательные таблицы кодирования инохда имеют такие же размеры, что и сжимаегея инфор]уация.В работах [45,93,94,95,99] исследованы методы сжатия инфорьации путем устранения некоторых символов в слове, словосочетании на естественном языке и их модификации. Некоторые из модификаций [99] требуют выполнения простейших арифметических операций (+, - ) • В среднем удалось сократить объем исходного материала до 25-35^. Недостатки - невысокое быстродействие, неоднозначность кодирования. За исключением способа Купара, который не обладает неоднозначностью и дает 2-3-кратное сок1ащение исходного объема.Используются в основном для построения словарей.Метод сжатия конечного набора слов исследован в работах [l5, 41,44,54]. При известном количестве слов в ]шссиве, в памяти можно хранить их двоичные номера, состоящие из ]/<9^ /./v[ разрядов.Коэффициент сжатия способа равен 3-4.Недостаток метода - для получения действительного значения символа необходимо в памяти хранить таблицы соответствия, которые при небольших размерах могут храниться в ОЗУ, в противном случае - на более низком уровне.Способ сжатия упорядоченных данных [l4,44,47,54,60,ПО] и сжатия монотонно изменяющихся чисел [2,82,109] требует упорядочения буквенно-символьной инфоргпции и размещения цифровой в возрастающей (убыващей) последовательности с небольшими отличиями в соседних элементах.Идея сжатия упорядоченных данных заключается в замене повторяющихся частей (слова, фразы, группы чисел и т.д.) некоторым знаком (символом), который в памяти занимает небольшое число разрядов.Коэффициент сжатия К = 84-10.Исследования, проведенные в [82,1091,показали, что коэффициент сжатия монотонно-изменяющихся чисел линейно зависит от количества сжиувемых чисел; Таким образом, обе модификации метода имеют большие коэффициенты сжатия. Это выгодно отличает их от ранее рассмотренных.Программы сжатия могут обрабатывать массивы любой длины.Рассмотренные алгоритмы сжатия имеют особо важное значение для построения справочников и таблиц, являющихся существенной частью многих методов организации файлов. Однако,они не универсальны.Переход от естественных обозначений к более коротким [54,97] на уровне фраз позволяет сжимать биографические данные, даты и т.д. Способ сжатия широко используется в ЭВМ.

1.4.2. Корреляционные методы сжатия Учитывают существование корреляционной (функциональной) зависимости мевду элементами инфорв/шщи.Развитие этих методов сжатия информации связано непосредственно с дальнейшим совершенствованием структуры процессора и улучшением его качественных показателей. В частности, одним из важнейших путей повышения быстродействия и упрощения логической структуры ЭВМ состоит в применении табличных методов выполнения вычислительных операций, обеспечивающих существенное сокращение количества ковенд, а следовательно, и евжости ОЗУ [38,44,58,59]. S5 Однако,он требует для своей реализации больших аппаратурных затрат на организацию памяти для хранения табличных констант. Метод наиболее прост для функциональных зависимостей. Но успехи в микроэлектронике и создание новых, более эффективных методов сжатия позволяют уже сейчас внедрить табличные и матричные структуры как для выполнения арифметических операций,так и для реализации сложных функциональных зависимостей. Тем более, что за последние годы разработаны различные способы и приемы, которые позволяют более чем в десятки раз сократить объемы памяти, необходимые для хранения табличной информации.К ним относятся [ЗЗ,57,58,59,76,80]: 1) выбор метода вычислений элементарных функций; 2) использование конкретных особенностей функций; 3) удачный выбор кода аргумента; 4) разбиение интервала аргумента на некоторое количество подинтервалов; 5) введение переменного пага таблиц; 6) применение различных способов интерполяций межцу узловыми точками, хранящимися в ПЗУ, и ряд других.Так, например, для вычисления показательной и степенной функций, использовав разложение в ряц Тейлора только с линейными членами, удается сократить объем ПЗУ в несколько десятков раз [58].Интерполирование применяется практически во всех ш.теш.тических таблицах. Теория его достаточно хорошо разработана в работах советских и иностранных згчёных.Интерполирование сводится к подбору более простой апцроксимирущей функции, определяющей не менее двух соседних значений функции, составленной с большим шагом, так что для нахождения функции необходимо 2 точек, а не 2^ , где п. - разрядность аргумента; {п.-"г) - разрядность части аргумента, которая используется дзш непосредственного обращения к таблице; *Z - разрядность остатка.В работе f б7 число разлагается на простые множители и записывается в разбитый на несколько блоков накопитель. Записи любого другого числа, степень простого множителя которого после разложения совпадает со степенью простого множителя уже записанного числа, не происходит, а происходит обращение к соответствующему этому множителю входу блока-накопителя.Способы обладают высоким быстродействием, надежностью, легко реализуются аппаратно, особенно удобны для построения ПЗУ, могут быть использованы в реальном масштабе времени. Однако с увеличением объема сжилаемой инфоринции увеличивается объем необходимого оборудования Гб,48]. В работах [11,27,28] сокращение объеш памяти достигается за счет применения относительной адр:еоа1Щи( проотейшя форьа корреляции), когда вместо полноразрядного адреса в коде команды размещаются их приращенияД^, т.е. шлоразрядные относительные адреса. Исполнительный адрес Лисп формируется путем сложения относительных адресов с базовым адресом Лиса. = Лб + ЛЛ. (Более подробно сжатие команд и микрокоьанд рассмотрено в п.1.4.3).Следовательно, применяя вышеперечисленные ьатеиатические способы и приемы^можно существенно повысить эффективность специализированных процессоров. Вместе с тем,большинство данных не может быть представлено функциональной зависимостью от некоторого общего косвенного параметра; корреляционные связи не могут быть представлены явной функциональной зависимостью - приходится выявлять связи, используя некоторые фиксированные правила. Выявлению и исполь

Основные результаты диссертационной работы:

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

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

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

4, Исследованы способы организации ЗУ с последовательным и параллельным доступом. Получены оценки сложности ЗУ.

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

6, Разработали программы, реализующие предложенные методы сжатия совмещенных последовательностей и определения коэффициентов обратных связей для сдвиговых регистров. Программа сжатия прошла экспериментальную проверку и была использована для сжатия управляющих программ при разработке автоматизированного комплекса ЛТК-133.

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

ЗА1ШЛЕНИЕ

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

Разработаны и исследованы автоматизированные средства оценивания качества сжатия, включающие в себя математическое моделирование и приближенное вероятностно-статистическое оценивание.

1. АКСЕНОВ В.П., БОЧКОВ С .В., МОШКОВ Л.А. Структура и характеристики высокопроизводительных ЭВМ и систем (обзор). - Зарубежная радиоэлектроника, 1982, & 3, ч.1, с.35-53, №4, ч.П, с.33-57.

2. АКУШКСКИЙ И.Я., ЗАБОЛОЦКИЙ В.М. О комбинаторном подходе к идее сжатия информации. В сб.: Цифровая вычислительная техника и программирование. - М.: Сов.радио, 1976, вып.6, с.5-17.

3. АЛЬТМАН Л. В перспективе полупроводниковые ЗУПВ емкостью I6K бит - Электроника, 1975, т.48, $ 12, с.35-42.

4. АЛЬТМАН Л. Запоминающие устройства: Обзор. Электроника, 1977, т.50, & 2, с.23-46. *

5. АРТАМОНОВ Г.Т., БРЕХОВ О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978, - 368 с.

6. АТАНЕЛИШВЙЛИ И.Г., ЧКОНШ И.Г., ГОРАДЗЕ М.В. Сжатие информации в ПЗУ. В кн.: Развитие теории и практики средств хранения инфоршции. Тез.докл. Всесоюз. научно-техн. конф. Москва; Рига: 1980, с.30-32.

7. Об одном методе минимизации описаний символов "(в запоминающем устройстве /Арутюнов М.Г., Изотов Н.Н., Шагимарданов Н.Ш., Шифрин Е.И. Вопросы радиоэлектроники, серия ЭВТ, 1976, с.20-28.

8. АРУТЮНОВ М.Г., ИЗОТОВ Н.Н. Некоторые вопросы синтеза символов для устройств документирования и отображения инфоршции. -Вопросы радиоэлектроники, серия ЭВТ, 1975, с.33-41.

9. АСКЕТОВ Т.М. Алгоритмы сжатия и развертывания логических шкал, применяемых в информационно-поисковых систем. В кн.: Цифровая вычислительная техника и программирования. М.: 1974, вып.8, с.100-122.

10. БАЛАШОВ Е.П., ПЕТРОВ Г.А., ХВОЩ С.Т. Способ сжатия объе- (.лс Ома прикладных программ логических алгоритмов управляющих вычислительных машин. Управляющие системы и машины, 1976, & 4, с.78-83.

11. БЕДИЦКИИ Р.И., СЫРОВ В.В. Две задачи косвенного кодирования микрокоманд. Управляющие системы и машины, 1978, № 6,с.82-84.

12. БЕ10Н0ГСВ Г.Г., ГРИГОРЬЕВ В.И., КОТОВ Р.Г. Автоматическое лексическое кодирование. Вопросы языкознания, I960, J& 4, C.I07-III.

13. БЕРЖ К. Теория графов и её применение. М.: Изд. иностр. лит., 1962. - 320 с.

14. БОБКО И.М. Программа уплотнения инфоршции при её обработке на ЭВМ. Труды Новосиб. ун-та, Экономика, 1965, вып.5, с.72-79.

15. БОРЩЕВ В.Б., РАХЛИН Ф.З. Методы буквенного сжатия слов. -Научно-техническая информация, 1964, J& I, с.41-52.

16. БРАТАЛЬСКИЙ Е.А., БЕЯКОВ М.С., ЗЛАТНИКОВ В.М. Устройство уплотнения и расстановки информации. Вопросы радиоэлектроники, серия ЭВТ, 1975, с.60-64. -/''V,

17. БРИК Е.А., СЕШГЕЙ A.M. О сжатии инфоршции в ПЗУ. -Вопросы радиоэлектроники, серия ЭВТ, 1975, с.31-46.

18. БРИК Е.А. Уплотнение информации в ПЗУ. В сб.: Запоминающие устройства. /Йод ред. Л.П.Крайзмера. - Л.: Энергия, 1974, с. 43-45.

19. БРИТАВСКИЙ Г.М., ГЛЕИБЕРМАН В.Г. Об одном подходе к представлению информации. Управляющие системы и машины, 1979, JS 2, " с.34-36.

20. БЕБЕР Д.Р. Экономический аспект проблемы сжатия данных. -В кн.: Достижения в области телеметрии. М.: Мир, 1970.357 с.

21. ВОРОНИН Ю.М., КРУПСКИЙ А.А., ЛЕСНИКОВ А.А. Вопросы организации многоуровневой памяти ЦВМ. Вопросы радиоэлектроники, серия ЭВТ, 1970, № 5-6, с.20-25.

22. ГШШ А. Линейные последовательноетные машины. М.: Наука. - 288 с.

23. ГЛУШКОВ В.М. Два универсальных критерия эффективности вычислительных машин. Доклады АН УССР, I960, № I, с.25-31.

24. ДАВЫДОВСКИЙ А.И. Некоторые аспекты использования вычислительной техники в 1980-90-х годах. Зарубежная радиоэлектроника, 1982, J6 5, с.51-60.

25. ЕВРЕЙНШ Э.В., КОСАРЕВ Б.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966. - 308 с.

26. ЖУРАВЛЕВ Ю.П., АКИНШИН Ю.С. Системное проектирование памяти ЦВМ. М.: Сов.радио, 1976. - 344 с.

27. ЖУРАВЛЕВ Ю.П., ЗАБУБЕНОВ В.Н. Выбор системы формирования команд управляющей ЦВМ. Автоматика и вычислительная техника. Рига, "Зинатне", 1973, № 2, с.71-76.

28. ЗАКРЕВСКИИ А.Д. Алгоритмы синтеза дискретных автоматов. -М.: Наука, 1971. 812 с.

29. ИВАНОВ A.M., ПРОСКУРЯКОВ С.А., САВЕЛЬЕВ А.И. О сжатии информации. Тезисы докладов "Развитие теории и техники средств хранения информации. Всесоюзн.научно-технич.конф. Москва; Рига: 1980, с.41-44.

30. ИВЧЕНКО Г.И., КАШТАНОВ В.А., КОВАЛЕНКО И.Н. Теория массового обслуживания. М.: Высшая школа, 1982. - 256 с.

31. ИЛЬИН В.А., ПОЗДНЯК Э.Г. Линейная алгебра. М.: Наука, 1980. - 302 с.

32. ИЛЬИН В.А., ПСП0В Ю.А., ДРУЖИНИН И.И. Об использовании сокращенных таблиц при вычислении элементарных функций. Управляющие системы и машины, 1979, & I, с.58-62.

33. КЕЛЛЕР Ф,Э. Графы кодов, кодирующие и декодирующие устройства. Л.: Энергия, 1972. - 98 с.

34. КЕМЕНЙ Дж., СНЕЛЛ Дж., ТОМПСОН Дж. Введение в конечную математику. М.: Изд-во иностр.лит., 1963 - 486 с.

35. КЕМЕНИ Дж., СНЕЛЛ Дж. Конечные цепи Маркова. М.: Наука, 1970, - 272 с.

36. КНУТ М., J3E0HCEH 0. Блочное кодирование графических материалов: Обзор. ТИИЭР, 1980, т.68, № 7, с.21-40.

37. КСЛУБАЙ С.К., МУРАЖО А.Г. Принципы построения процессоров типа "память система поиска". - УСиМ, 1977, )£ 4, с.58-62.

38. КОЛИН К.К., ЛИПАЕВ В.В. Проектирование алгоритмов управляющих ЦВМ. М.: Сов.радио, 1970. - 344.

39. КОНОН Н.И., ПЛАТОНОВ П.И., СКОРУБСКИЙ В.И. Уплотнение ин- ч формации в памяти ЭВМ. Изв.вузов СССР - Приборостроение, 1979,т.22, № 7, с.61-65.

40. КОРОЛЕВ Л.Н. Кодирование и свертывание кодов. В кн.: ДАН СССР, 1957, т.113, В 4, с.738-741.

41. КРАВЦОВ Л.Я., ЧЕРШЩЗШЙ Г.И. Проектирование микропрограммных устройств управления. Л.: Энергия, 1976. - 152 с.

42. ШИН Б.И., ПЛАТОНОВ П.И. Об одном методе рациональнойорганизации информации в ЭВМ. Межвуз. сб.: Теория и методы управления производственными процессами. - Л.: 1979, с.14-18.

43. КУРБАКОВ К.И. Некоторые характеристики распределения символов русского алфавита. В кн.: Научно-техн. информация. -М.: 1965, В 9, с.41-46.

44. КУРБАКСВ К.И. Кодирование и поиск информации в автоматическом словаре. М.: 1968. - 248 с.

45. ЛИПАЕВ В.В., КШШН К.К. О составе операций и статистике их использования в программах управляющих ЦВМ. В сб.: Цифровая вычислительная техника и программирование. - М.: Сов.радио, 1972, с. 15-18.

46. ЛИНЧ Т. Временное кодирование последовательности для сжатия данных. ТИИЭР, 1966, № 10, с.292-294.

47. ЛИСИЩН Н.М., МАТУШКИН Н.Н. Способы рационального разме- щения информации в ПЗУ специализированной цифровой управляющей машине. В кн.: Автоматизированные системы и средства управления. Межвуз. сб. научн. трудов. - Пермь, 1976, 1 180, с.89-91.

48. МАЙОРОВ С.А., НОВИКОВ Г.И. Электронные вычислительные машины. М.: Высшая школа, 1982. - 176 с.

49. МАЙОРОВ С.А., НОВИКОВ Г.И. Структуры электронных вычислительных шшин. Л.: Машиностроение, 1979. - 384 с.

50. Малогабаритная специализированная ЦВМ высокой производительности. /Кляторный М.Ю., Пронин В.А., Смолов В.Б., Хвощ С.Т. -Управляющие системы и машины, 1980, № 2, с.29-35.

51. МАРКОВ А.А. Введение в теорию кодирования. М.: 1982. -432 с.

52. МАРК-ВШЕШМС Дж. Структуры и свойства бинарных циклических алфавитов. Кибернетический сборник. М.: Мир, 1967, вып.4, с.7-12.

53. МАРТИН Дж. Организация баз данных в вычислительных системах. М.: Мир, 1982. - 662 с.

54. Основы теории вычислитаяьных систем./Йод ред. С.А.Майорова. М.: Высшая школа, 1978. - 408.

55. ОРАНСКИЙ A.M. Аппаратные методы в цифровой вычислительной технике. Минск: БГУ, 1977. - 207 с.

56. ОРАНСКИЙ A.M., РЕЙХЕНБЕРГ АЛ. Повышение эффективности вычислений использованием табличных предпроцессоров. В сб.: Теория и применение математических машин. Шнек: БГУ, 1972, с.148-159.

57. ОСЕТРОВ С.И. Об одной модификации методов кодирования возрастающей и неубывающей последовательностей. Вопросы радиоэлектроники, серия ЭВТ, 1975, с.50-59.

58. ПАЛАШ А.В., ПИСАРСКИЙ А.В., ПОГОРЕЛЬШЙ С.Д. Об одной задаче оптимизации размещения данных. Управляющие системы и , машины, 1976, й 4, с.54-58.

59. ПАЛЬМ Р. Об одном методе "сжатого" побуквенного кодирования. Сообщения по МП. Институт языка и литературы АН Эстонской ССР. Таллин, 1962, вып.1, с.49-58.

60. ПИАТРОВСКАЯ А.А., ПИАТРОВСКИЙ Р.Г., РОЗЖИВИН К.А. Энтро-ния русского языка. Вопросы языкознания. 1962, № 2, с.115-130.

61. ПИТЕРСОН У., УЭЛДСОН Э. Коды, исправляющие ошибки. М.: Мир, 1976. - 600 с.

62. ПЛАТОНОВ П.И. Сокращение объема управляющих ЗУ. Изв. вузов СССР. - Приборостроение, 1982, т.25, )£ 7, с.43-47.

63. А.С. 698053 (СССР). Способ записи цифровой информации в полупостоянные и постоянные запоминающие устройтройства/Й.И.Платонов, И.Г.Буренков, Ю.А.Бузунов и др. Опубл. в Б. И. 1979,1. В 42.

64. А.С. 750561 (СССР). Постоянное запоминающее устройство. /П.И.Платонов, В.И.Скорубский и др. Опубл. в Б. И. 1980, № 27.

65. А.С. 780041 (СССР). Ассоциативное запоминающее устройство /П.И.Платонов, Ю.А.Бузунов, И.Г.Буренков. Опубл. в Б. И. 1980, В 42.

66. А.С. 744731 (СССР). Постоянное запоминающее устройство /П.И.Платонов, В.И.Скорубский, Н.И.Конон. Опубл. в Б. И. 1980, В 24.

67. А.С. 980163 (СССР). Постоянное запоминающее устройство /П.И.Платонов, В.С.Грама. Опубл. в Б. И. 1982, № 45.

68. А.С. 841052 (СССР). Запоминающее устройство на сдвиговых регистрах./П.И.Платонов, В.И.Скорубский, В.С.Грама и др. -Опубл. в Б. И. 1981, Л 23.

69. А.С. 847371 (СССР). Долговременное запоминающее устройство. /П. И.Платонов, В.К.Борщев и др. Опубл. в Б. И. 1981, № 26.

70. А.С. 842967 (СССР). Запоминающее устройство./П.И.Платонов, В.И.Скорубский, Н.И.Конон и др. Опубл. в Б. И. 1981, В 24.

71. А.С. 860139 (СССР). Запоминающее устройство на сдвиговых регистрах /П.И.Платонов, В.С.Грат и др. Опубл. в Б. И. 1981, Ш 32.

72. Полупроводниковые запоминающие устройства и их применение/Йод ред. Ю.Ю.Гордонова. М.: Радио и связь, 1981. - 344 с.

73. ПШОВ В.И., ФЛОРЕНСЕВ А.Н. Таблично-алгоритмический метод реализации в ЦВМ функций логарифма. УСиМ, 1978, № 4, с.90-94.

74. ПРИСЯЖНЮК О.А. Об одном способе кодирования командной информации. В сб.: Технические средства управляющих машин и систем. Киев: 1975, с.35-63.

75. СААТЙ Т.1. Элементы теории массового обслуживания и её применения. М.: Сов.радио, 1971. - 520 с.

76. СИГОРСКИЙ В.П. Штематический аппарат инженера. Киев: Техн ка, 1977. - 766 с.

77. Синтез вычислительных алгоритмов управления и контро-ля./Кузьмин И.В., Березюк Н.Т., Фурманов К.К., Шаранов В.Б.- Киев: Техн ка, 1975. 348 с.

78. СКОРУБСКИЙ В.И., ЭКАЛО Ю.В. Размещение микрокоманд в управляющей ЭВМ. Управляющие системы и машины, 1979, 1 3,с.73-78.

79. СОЛОВЬЕВ В.Ф. Рациональное кодирование при передаче coo- г V бщений. М.: Энергия, 1970. - 66 с.

80. СОУЧЖ Б. Мини-ЭВМ в системах обработки информации.- М.: Мир, 1976. 520 с.

81. ФИЛИППОВИЧ В.В. Задача размещения данных в памяти ; г ЦВМ. УСиМ, 1975, JS I, с.87-92.

82. ШЕННОН К. Работы по теории инфортции и кибернетике.- М.: Изд-во иностр.лит. 1963. 830 с.

83. ПИТИЯ А.Г., ДЕРЮГИН А.А. Цифровые вычислительные машины (Память ЦВМ). М.: Энергия, 1975. - 536 с.

84. ЖГАРЬКОВ Ю.М., БАБКИН В.Ф. Кодирование длин серий в устройствах априорной неизвестности. В кн.: Аппаратура для космических исследований. - М.: Наука, 1974, с.3-9.

85. ЯГЛОМ A.M., ЯЛОМ И.Н. Вероятность и информация. М.: Наука, 1973. - 512 с.

86. ХАССАН С. Микропрограммное управление. М.: Мир, 1973, вып. I, 240 с.

87. ХОЛЛ М. Комбинаторика. М.: Мнр, 1970. - 424 с.

88. Alsberg P.A. Spase and time sayings through lorge data base compression and dynamic re struct uriag. Procceedings of the LEEE., 1975, v.65, N8, p III4 - 1122.

89. Arora S.R., Gallo A. Optimization of static loading of multilevel memory susmes. I. Ass. Comput. Mach, 1973» April, v.20, p. 507 - 319.

90. Barret I.A. Greems M. Abbreviating words sustematically.-Comms. of the ACM, I960, v.3, p.323 327.

91. Bourne С .P., lord D.F. A study of methods for sustemati-cally abbreviating english words and names. I. of the ACM, 1961,v.8, m, p.538 552.

92. Bourne C.P., Ford D.F. A study of statistic of letters in english words. Information and Control, 1961, v.4, N1, p.48-6?.

93. Hahn B. A new technique for compression and storage of data. Communications the ACM., 1974, v.I7, N8, p.434-436.

94. Bunselmuser R. Mrtoden zur Daten komprimierung. - Versi-cherungs - betrieb, 1973, N11-12, S. 14-18.

95. Davis R.H., Rinaldi C., Trebilcock C.I. Data compressionin limited capcity microcomputer sustem. Inf. Process. Lett. I981, v.I3, N4-5, p. 138 - 141.

96. Davidson L. Retrievol of misspelled names in an airlines passanger record systems. Comms of the ACM, 1962, v. 5, N3, p. 169 - 171.

97. Denning P.I., Buzen I.P. The operational analusis of queueing network models. Commpat. Surveys., 1978, Sept., v.10,p. 225 261.

98. Fajman R., Borgelt I. WuLBUR: An interative text editingtand remonte jjob entru aystem.— Comm. ACM., 1973» v.I6, n5, p.314 322.

99. Geist R.M., Trivedi K.C. Optimal design of multilevel storage hierarchies. IEEE Trans. Comput., 1982, v.31, ^3, p. 249 - 260.

100. Hagamen W.D., Linden D.I., Land H.S., Weber I.C. Encoding verbal information as unigne numbers. IBM fiustems I., 1974, v.II, N4, p.278-315.

101. Ling H., Palermo P.P. Block oriented information compression. - IBM L. Res. and Develop., 1975, v.9, N2., p.I4I-I45.

102. Mayne A., Lames E.B. Information compression by factori-sing common strings. Commput. I., 1975» v.18, N2, p.I57-I6Q.

103. Parrat D. Development and trende in memory technology.-Microelectron. Reliab., 1981, v.2I, N3, p.467-470.

104. Rolame B.P. Data compression sistem /Ohne Bunher Romo

105. Corp./. Патент США, кл. 340-1725, (G06 f), H3438oo3, Заявл. 10.06.65, опубл. 8.04.69.

106. Sidhu P.S. Croup coded recording rebiably dubles diskette copacity.- Comput. Des., 1976, v.I5, N12, p. 84-86.

107. Sniwely I.W. A bit-eavingen coding sheme for a set of monotonic numbers. Proc. of the IEEE, 1965, v.55, N5, p.I05-109.

108. Susan J., Eggers A.S. Efficient access of compressed data.- 6 th Int. Conf, Veru Lorge Data Bases, 1980, v.51,p. 205-211.

109. Wolff J#G. Recoding of natural laugu age for economy of transmission or storage. Comput. J., 1978, v.21, N1, p.42-44.

110. Wolff J.G. The disccoury of segments in natural langvage.--British. Journal of Psychology, 1917, v.68, N5 , р.97-Ю6.115• Yitzhak D. Data compaction im computer systems. Computer desingn, April, 1917, p.85-90.