Содержание к диссертации
Введение
Глава I, Устранение избыточное ти сигналов и запись служебной информации в бортовых информаци онно-измерительных системах научных косми ческих исследований 9
1.1. Бортовые ИИС НКИ 9
1.2. Устранение избыточности аналоговых сигналов аппроксимацией 13
1,3. Первичная обработка, как метод сжатия 18
1.4. Устранение избыточности счетных сигналов 23
1.5. Запись служебной информации в бортовых ИИС НКИ 28
1.6. Некоторые системы записи служебной информации и оценка их эффективности 33
1.7. Результаты и выводы 37
Глава II. Лаконичное описание массивов служебной и измерительной информации 39
2.1. О классификации последовательностей 39
2.2. Массивы служебной и измерительной информации в бортовых ИИС НКИ с геофизическими КНА 43
2.3. Об алгоритмическом описании последовательностей в бортовой ИИС НКИ 4-8
2.4. Эффективность алгоритмического описания 53
2.5. Вычислениес помощью позиционной линейки 56
2.6. Достаточное условие эффективности 60
2.7. Результаты я выводы 61
Глава III Алгоритмы функционирования машин сжатия 64
3.1. Частотный алгоритм 64
3.2. Эффективность сжатия частотным алгоритмом с помощью ААС-алфавита 69
3.3. Анализ эффективности сжатия по заданным гистограммам 74
3.4. Алгоритм кодирования "расстояний" (АКР) 81
3.5. Формирование программы воспроизведения для АКР 86
3.6. Оценка эффективности сжатия с помощью АКР 90
3.7. Алгоритм АКР-ААС 95
3.8. Выполнение достаточного условия эффективности сжатия 97
3.9. Результаты и выводы 98
Глава IV. Реализация машин сжатия в виде специализиро ванных процессоров 100
4.1. Специализированный процессор, реализующий частот ный ААС-алгоритм 101
4.2. Процессор сжатия информации на базе оперативных запоминающих устройств 108
4.3. Процессор сжатия информации по алгоритму АКР 114
4.4. Универсальный процессор сжатия информации с обратной связью 118
4.5. Бортовые геофизические приборы и предикаты первичной обработки 121
4.6. Эффективность первичной обработки данных с геофизического КНА и условия физической реализуемостиалгоритмов 126
4.7. Результаты и выводы 134
Глава V. Моделирование информационно-измерительной стемы со сжатием данных
5.1. ИИС с однородным (спектрометрическим) КНА
5.2. ИИС с неоднородным составом КНА
Заключение
Литератора
Приложения
- Устранение избыточности аналоговых сигналов аппроксимацией
- Массивы служебной и измерительной информации в бортовых ИИС НКИ с геофизическими КНА
- Эффективность сжатия частотным алгоритмом с помощью ААС-алфавита
- Оценка эффективности сжатия с помощью АКР
Введение к работе
"Основные направления экономического и социального развития СССР на I98I-I985 годы и на период до 1990 г.", принятые ХХУІ съездом КПСС, предусматривают в качестве одной из важнейших задач развития науки и ускорения технического прогресса "дальнейшее изучение и освоение космического пространства в интересах развития науки, техники и народного хозяйства" _IJ . Интенсивность космических исследований все более возрастает, лавинообразно увеличивается количество научных и прикладных задач в исследовании космоса и соответственно увеличивается количество экспериментов, состав и качественные характеристики научной аппаратуры на борту космических аппаратов, предназначенной для исследования атмосферы.
Результаты прямых измерений физических величин в космосе, как правило, не могут быть непосредственно восприняты экспериментатором, что связано как с удаленностью и специфичностью объекта наблюдения, так и с большим количественным составом приборов, участвующих в эксперименте. Именно это обстоятельство и обусловило необходимость создания сложных многозвенных совокупностей бортовых и наземных технических средств и комплексов алгоритмов, обеспечивающих получение результатов научного космического эксперимента - информационно- измерительных систем научных космических исследований (ИИС НКИ).
Количество информации, поступающее с измерительных каналов бортовых научных приборов в единицу времени растет с ускорением научно-технического прогресса гораздо быстрее, нежели технические характеристики средств передачи данных с борта космического аппарата (КА) на Землю І 2І . Поэтому к бортовой части ИИС НКИ предъявляется два противоречивых требования: при безусловном сохранении всех необходимых экспериментатору сведения с заданной погрешностью, она
- З должна описать их так, чтобы существующие бортовые средства передачи данных донесли их до пользователя без потерь.
Разрешение этого противоречия состоит в разработке методов и устройств сжатия информации. Поэтому задача сжатия информации на борту КА является сейчас одной из важнейших задач, решаемых бортовыми ИИС НКИ [з] , что и определяет актуальность темы диссертации. Существуют два класса методов сжатия информации - класс методов необратимого сжатия, носящих в литературе название "устранение избыточности" и "сжатие с потерямиГ и класс методов обратимого, восстановимого преобразования исходной информации.
Методы необратимого сжатия основаны на работах по способам восстановления непрерывного сигнала по дискретным отсчетам и работах по вычислению -энтропии класса функций, связанных, в первую очередь, с исследованиями В.М.Котельникова, А.Н.Колмогорова, А.А.Харкевича, Р.Л.Добрушина, М.С.Пинскера, Ф.Е.Темникова и др.
Обратимое сжатие информации берет свое начало от работ К.Шеннона, Р.Хартли, Р.Файнстейна, Р.Фано и перечисленных выше исследователей. Методы обратимого описания случайных последовательностей с известным распределением вероятности получили название оптимального статистического кодирования. Важнейшие результаты получены здесь Д.Хаффменом, Р.Крафтом, Л.Д.Девиссоном. Б.М.Фитингоф, Р.Е.Кричевский, Р.Гилберт, Ю.М.Штарьков и другие рассмотрели случайные последовательности с неизвестным заранее распределением вероятностей и разработали оптимальные для бесконечных последовательностей методы описания на основе наблюдения статистики первых символов последовательности. Это направление получило в литературе название оптимального универсального кодирования.
Результаты наблюдения статистики первых символов случайной последовательности дают верное представление о распределении ве - 4 роятностей только тогда, когда не только относительные частоты символов сходятся к вероятностям, но эти символы и появляются "беспорядочно". Поэтому для определения границ применимости оптимального и универсального кодирований решающее значение имеет определение рамок применимости самой теории вероятностей,определение понятия "случайная последовательность". Впервые такую задачу поставил Р.Мизес; А.Н.Колмогоров в работе [4] предложил невероятностный, "алгоритмический" подход к описанию последовательностей с помощью вычислимых /частично-рекурсивных/ функций. Более того, на этой основе он поставил задачу обоснования теории вероятностей и, в частности, определения понятия "случайная последовательность", которое в дальнейшем и дал П.Мартин-Лёф.[99] После этих работ стало ясно, что не все последовательности, которые не являются детерминистическими, могут быть корректно описаны аксиоматическими вероятностными моделями, а алгоритмический подход к описанию последовательностей - наиболее универсальный и перспективный. Алгоритмические проблемы описания последовательностей рассматривали В.Н.Агафонов, И.М.Гельфанд, А.М.Яглом, А.К.Звбнкин, Л.А.Левин, Д.В.Ловеланд, Т.М.Ковер и др. Практическая разработка методов описания, основанных на этой теории, затруднялась сложностью нахождения причины "неслучайности" по Мартин-Лёфу конкретных последовательностей и впервые была начата И.Я.Акушским, А.И. Амербаевым, И.Т.Паком и др., причем машины /частично-рекурсивные процедуры/ сжатия представляли из себя достаточно сложные и объемные программы для больших наземных ЭВМ. В бортовой ИИС НКИ имеется несколько этапов переработки информации, и, как следует из предыдущего, задача сжатия должна решаться в зависимости от характера последовательностей, возникающих на каждом этапе. Различным будет и аппарат определения эффективности сжатия. Для алгоритмических методов описания эффект будет иметь место в том случае, когда сама процедура сжатия разрабатывается на основе характерных свойств, присущих сжимаемым последовательностям, и вытекающих из объективных обстоятельств космического эксперимента-алгоритма функционирования ИИС и наличия каких-либо событий на входах ИИС.
Итак, при сжатии информации на всех этапах ее переработки в бортовой ИИС НКИ необходимо последовательно решить ряд задач:
I. Устранить избыточность измерительных сигналов на входах ИИС можно двумя способами:
- применить методы необратимого сжатия исходя из требований пользователя к точности восстановления сигнала;
- выделить из сигнала непосредственно на борту КА. только те его характеристики, которые необходимы пользователю и, так или иначе, будут выделены на Земле, т.е. осуществить на бор ту первичную обработку данных.
Объемы получившихся последовательностей будут зависеть от характеристик сигналов и задач эксперимента. Поэтому выбор одного из способов с точки зрения сжатия представляет теоретический и практический интерес. В работе эта задача решена для ряда наиболее типичных геофизических приборов.
2.Выяснить, являются ли получившиеся последовательности с включенными в них служебными словами, случайными по Мартин-Лёфу и, в зависимости от результата, выбрать методику кодирования /известно, что алгоритмическое кодирование случайных по Мартин-Лёфу последовательностей по определению неэффективно с точки зрения сжатия/.
З.В случае неслучайности по Мартин-Лёфу последовательностей проанализировать возможные причины этого факта;на основе сведений об алгоритме функционирования ИИС формализовать детерминистические ограничения в виде условия принадлежности этих последователь - 6 ностей определенному множеству
4.Разработать процедуры описания,последовательностей,дающие (если это возможно) эффект сжатия на множестве и) и общерекурсивные на множестве Ji , оценить максимально возможный наJL проигрыш при такой процедуре.
5.В зависимости от сложности процедуры описания и максимального проигрыша, оценить приемлемость технической реализации метода сжатия на борту М.
6.Проверить эффективность на реальных сигналах.
Эти задачи и решены в работе.
Работа состоит из введения, пяти глав и заключения. В первой главе дается краткий обзор известных для бортовых ИИС НКИ методов сжатия сигналов и методов записи служебной информации. Выводится достаточное условие эффективности первичной обработки данных на борту по сравнению с известными методами аппроксимации. Во второй главе рассматриваются последовательности обработанных измерительных и служебных слов в бортовой ИИС НКИ и делается вывод о неслучайности их по Мартин-Лёфу. Выводятся необходимое и достаточное условия средней эффективности алгоритмического описания для бортовой ИИС НКИ. На основе алгоритмов записи служебной информации и влияния событий на входах ИИС НКИ на структуру последовательности формализуется характер этих последовательностей. В третьей главе описаны, алгоритмы сжатия для этих последовательностей и показано выполнение достаточного условия средней наЬс эффективности на материале реальных сигналов. В четвертой главе описана техническая реализация процедуры сжатия в виде специализированного процессора, а также алгоритмы и реализация устройств первичной обработки для геофизических бортовых приборов трех типичных классов. Показано, что технические характеристики разработанных устройств допускают их применение на борту уже при современном уровне микротехнологии. В пятой главе приводятся результаты, моделирования бортовой ИИС НКИ с первичной обработкой данных и алгоритмическим описанием массивов. Личный вклад автора в работу заключается в следующем:
I. Поставлена и доведена до практического применения задача • первичной обработки информации непосредственно на борту КА. и выведено достаточное условие ее эффективности.
2.Выведены необходимое и достаточное условия средней на JГ эффективности алгоритмического описания для бортовой ИИС НКИ.
3.Разработаны, алгоритмы сжатия для бортовой ИИС НКИ и разработан соответствующий процессор.
4.Разработаны алгоритмы, бортовой первичной обработки сигналов с геофизических приборов /за исключением известного алгоритма первичной обработки манометрических сигналов/ и соответствующие бортовые устройства.
Основные научные положения, выносимые на защиту:
І.Для основных бортовых геофизических приборов первичная обработка является наиболее эффективным в настоящее время методом сжатия сигналов.
2.Двоичные последовательности, возникающие в бортовых ИИС НКИ с устройствами обработки данных и состоящие из кодов величин существенных замеров, номеров каналов, меток времени и кадровых пауз, не являются случайными по Мартин-Лёфу и принадлежат определенным ограниченным множествам, нетривиально описываемым формально. Разработанные алгоритмы эффективно сжимают эти последовательности.
3.Технические характеристики спецпроцессоров сжатия и устройств первичной обработки данных геофизических приборов допускают их применение в бортовой ИИС НКИ.
Научная новизна работы заключается в том, что впервые показан факт принадлежности массивов измерительной и служебной информации, образующихся в бортовых ИИС НКИ определенным ограниченным множеством массивов с известными свойствами; разработаны, проверены на модели и экспериментально алгоритмы и специализированные процессоры сжатия этих массивов; новизна их подтверждана двумя авторскими свидетельствами на изобретение [9, idj. Показано достаточное условие эффективности первичной обработки, как метода сжатия по сравнению с аппроксимацией для ряда геофизических приборов, разработаны бортовые устройства первичной обработки, что также подтверждается двумя авторскими свидетельствами на изобретения ll, 12].
Практическая ценность работы состоит в том, что ее результаты позволяют проектировать бортовые ИИС для ряда геофизических экспериментов, как совокупность разработанных устройств модулей первичной обработки и сжатия; решать в каждом случае на основании требований пользователя вопрос о целесообразности первичной обработки на борту; в конечном счете это позволяет во многих случаях увеличивать количество участвующих в эксперименте приборов без увеличения количества и пропускной способности каналов связи.
Результаты работы использованы в эксперименте "Грузия-60", проведенном ИКИ АН СССР (тема "Плазма", Гос.per.№ 8187072). Акт прилагается к диссертации.
Устранение избыточности аналоговых сигналов аппроксимацией
Обработка информации в современных ИИС производится, как пра №вило, в цифровом виде; преимущества цифровой обработки общеизвестны [23] . Аналого-цифровое преобразование измерительного сигнала, по определению, включает в себя квантование /дискретизацию/ по уровню и по времени, что, естественно, породило проблему восстановления сигнала в интервале между дискретными отсчетами в соответствии с выбранным критерием точности восстановления [25,26,27], т.е. аппроксимации измеряемого сигнала х, как функции времени x(t) с помощью некоторой воспроизводящей /восстанавливающей/функции . Очевидна и обратная задача: выбор интервала квантования по времени в зависимости от заданных свойств сигнала, совокупность которых образует его модель, таким образом, чтобы незарегистрированные, но восстановленные значения сигнала имели бы ошибку восстановления, допускаемую заданным критерием точности.
Адаптивный выбор шага квантования по времени в литературе часто называют одним из способов устранения избыточности сигнала. Для анализа сигналов бортового КНА с целью выбора способа восстановления, способа квантования и критериев оценки эффективности дискретизации используются различные модели сигналов. В частности,/ в работе [з] отмечаетсяі что в качестве модели реальных сигналов научной аппаратуры, используемой в космических исследованиях можно принять следующую;
Реальный аналоговой сигнал представляет из себя нестационарный случайный процесс, который можно представить в виде суммы медленно меняющегося математического ожидания и случайного процесса, обладающего столь же медленно изменяющейся дисперсией. Т.о.реальный сигнал можно разбить по времени на участки, на которых он ведет себя близко к стационарному процессу с постоянным математическим ожиданием и дисперсией. Аппроксимация временной функции сигна \j ла с помощью полиномов, как метод сжатия аналоговых сигналов бортовых приборов широко применяется в космических исследованиях. Наиболее распространенными аппроксимирующими функциями являются полиномы первой и нулевой степеней, допускающие простую техническую реализацию. В настоящем параграфе приводятся результаты исследований их эффективности на некоторых моделях и на реальных сигналах.
В работах [3,18,22,30]исследована эффективность сжатия с помощью адаптивной временной дискретизации, осуществляемой с помощью предсказателя нулевого порядка (ПНП) и интерполятора первого порядка (ИПП) на моделях реальных сигналов. При этом в качестве моделей были использованы, в частности следующие:I.белый шум, пропущенный через одиночный низкочастотный фильтр,2.белый шум, пропущенный через гауссовский фильтр. Оценка эффективности проводилась по показателю, называемому "коэффициент сжатия по отсчетам".Л/ - число отсчетов сигнала (включая и избыточные отсчеты). Nan- число отсчетов сигнала после устранения избыточных отсчетов. Перед применением алгоритмов устанавливается величина порога 2 . Алгоритм работы ПНП состоит из следующих шагов: 1.Передается"опорный отсчет" X(ti) X и интервал времени д междуос и моментом регистрации предыдущего "опорного" отсчета. 2.Принимается отсчет х(/г), 3.Вычисляется разность X(n)-X i 4.Если \х{п)-х \- Ї , то Х(п) считается "избыточным", не передается,/г=/z i и следует переход к шагу 2. Если ж&\х(іг)-Х \ 2 , то ҐІ ҐІ+І и следует переход к шагу I. Алгоритм работы ИПП: I.Передается отсчет X (/г) и он же запоминается, как опорный: X (п.) = X 2.Принимается следующий отсчет (/г«/г+і) 3.Строятся лучи: ін(іг)через точки А (п =п(х ))} Б (АІ+І, X-Z) L6(tt0 через точки А и С {№+1} %2) 4.Принимается следующий отсчет (ti-n i) 5.Проверяется условие .Ln(n-) = зс(іг) Li (n.)t Если оно выполняется, то переходим к шагу 4. Если оно не выполняется, то переходим к шагу I. Графики, иллюстрирующие работу ПНП и ИПП, приведены на рис. 1.3. В таблице I.I. приведены результаты моделирования, позволяющие оценить эффективность сжатия в зависимости от выбранного порога Z- и количества точек опроса на интервале корреляции г:
Массивы служебной и измерительной информации в бортовых ИИС НКИ с геофизическими КНА
Неудовлетворенность определения случайных последовательснотой по Мизесу заключается в том, что это определение требует выполнения лишь некоторых, а не всех законов теории вероятностей [іб, 66,77,102] . Определение Д.Мартин-Лефа [99] требует выполнения всех возможных законов теории вероятностей, и в настоящее время является исчерпывающим определением случайной последовательности. В дальнейшем для нас будет существенно то обстоятельство, что последовательность, не случайная по Мизесу, тем более не случайна по Мартин-Лефу. Утверждение 2.2. Еоли последовательное тьіос(п) г случайна по Мизесу,то последовательность значений Ос или Осол частично рекурсивной функции, определенной определениями 1.3. и I.4-.(X/3c./является также случайной по Мизесу. Справедливость этого утверждения вытекает из того обстоятельства, что функции (г и R. являются сущности "правилами выбора-Ггы",упомянутыми в п."в" определения 2.2,а существенность условия %-ii X определяется тем, чтоІІОі и [/0Сопне должны ограничивать множества по отношению к множеству X. Утверждение 2.3. Последовательность] (п)К где =Осили У , у- код кадровой паузы (1.5., [У] ) не является случайной по Мизесу, но является недетерминистической. Доказательство. Пусть ІОс(пН- случайна по Мизесу с мерой г( ]= UР(ос) 1. Код -у кадровой паузы ставится в конце опроса I кана лов на позициях п=г Пу» независимо от того, сколько замеров ОС" появилось в данном цикле опроса каналов. Последовательность ідпД количеств ЛП существенных замеров в данном --овом цикле опро са, т.е. количество символов х между двумя соседними символами у является случайной по Мизесу с вероятностью (Р - вероятность того, что в данном канале отсчет "сущеетвенен"). Следовательно, в последовательности ]Пунельзя задать отображения , т.к. Пу ІДП . , т.е. область детерминистичности D последовательности / п)имеет собственную пустую область детер-министичности, т.е. следовательно, последовательность] п)явля-ется недетерминистической. (Ясно, что для любых позиций,где /сЗс согласно 2. Допустим, последовательность]f(ri)г является случайной по Мизесу и на алфавитеЬ5 Х1/у может быть задана вероятностная Очевидно, в бесконечной последовательности J (п)т будет бесконеч но много = , т.е. последовательность «Г Ч является бесконечной. Однако, для указанной последовательности всегда У =У , т.е. она является детерминистской и, следовательно, не случайной по Мизесу. Отсюда, согласно п. "в" определения 2.2. и последовательность-!?Мне является случайной по Мизесу. Следствие: Последовательности, состоящие из измерительных и служебных слов и кадровой паузы, не являются случайными по Мизесу, и, тем более, не случайны по Мартин-Лефу, но и не явля-ются.детерминистическими.
Обратим внимание на тот факт, что причина, по которой последовательности (массивы) служебной и измерительной информации, возникающие в бортовой ИИС НКИ не случайны по Мизесу, заключается в невыполнении п. "в" определения 2.2., в то время, как п."а" того же определения выполняется (2.3, 2.4), т.е. статистика у таких последовательностей сходится, (хотя задать ее в практических приложениях, как правило, не удается [3,4-5] ).
Пункт "в" определения 2.2. является попыткой определения понятия "беспорядочность" [іб] и несоответствие ему является признаком наличия некоторой неявной "упорядоченности", присущей рассматриваемым массивам. Можно показать, и это давно замечено исследователями Гз,Ю,17,21,42,45,4б] , что причиной возникновения неявной упорядоченности в этих массивах является не только разделение массива на кадры (т.е. временное разделение измерительных каналов) и не только нарушение синхронизации в результате работы УОД, но и включение в массив номеров каналов и меток времени, причем упорядоченность возникает при любом известном способе записи служебной информации (см. 1.5., 1.6.).
Пусть на измерительные каналы бортовой ИИС НКИ действует случайная по Мартин-Лефу, (т.е. подчиняющаяся всем законам теории вероятностей) физическая величина, распределение вероятностей которой задано (его вид несущественен для дальнейшего изложения). Поскольку алгоритм работы УОД является частично-рекурсивной, т.е. вычислимой функцией с известным пользователю предикатом (см.1.4), то на заданном распределении входной величины всегда вычислима вероятность pi появления безразлично какого существенного от счета XL по і -овому каналу , Если в одном кадре опрашивается I каналов, то относительная частота появления символа і в массиве будет стремиться к р.
Эффективность сжатия частотным алгоритмом с помощью ААС-алфавита
Там же показано, что коэффициент сжатия экспотенциально уменьшается с увеличением Е и исчезает примерно при Е = 0,4 М. Таким образом, для эффективного применения метода кодирования длин серий (единственного легко реализуемого существующего метода обратимого сжатия двоичных последовательностей) алфавит, предварительно кодирующий массив, принадлежащий множеству сОо( должен обеспечить превалирование нулей в битовой последовательности і b(dL) r. Эту задачу и решает ААС-алфавит, В следующем параграфе мы выведем выражение, позволяющее по последовательности 1 ( ) г вычислить величину Е в массиве, закодированным выше приведенным алгоритмом и ААС-алфавитом и, далее, определить KQ по формуле (3,8), в настоящем параграфе рассмотрим вопрос о выборе разрядности кодера длин серий Г , оптимальной в определенном, рассматриваемом ниже, смысле, В исходном массиве из М двоичных символов количество единиц ЕИСХж определится выражением: В массиве, закодированном алфавитом ААС, количество единиц определим, исходя из следующих соображений: 3. Гарантирование, принципиальной возможности достижения максимального при заданном " Е " коэффициента сжатия. Используем то обстоятельство, что Наилучшее при постоянном " Е " сжатие методом длин серий достигается тогда, когда все единицы в массиве расположены на "расстоянии" не более 2-І символов друг от друга. Действительно, если две единицы стоят на расстоянии друг от друга, не превосходящем 2 - I, то последняя единица заменяется одним "h" - разрядным словом; если расстояние до предыдущей единицы превышает 2 - I, то это расстояние заменяется более, чем одним "г" - разрядным словом. Т.о. наиболее эффективно сжимаемый массив - это тот, для которого выполняется соотношение? а максимально возможный коэффициент сжатия достигается при Сам коэффициент сжатия при этом равен В заключении отметим, что " р ", соответствующее выражениям (3,8 и 3.13) вычисляются численно Блок-схема приграммы вычисления " ", по (3.13) показана рис. 3.2; по (3,8)— Вопрос количественной оценки справедливости (3.20) и выбора соответствующего N мы рассматривать не будем (она достаточно известна), рассмотрим лишь задачу нахождения функции f(j)% минимизирующей величину " Е и. Формулу (З.П) по аналогии с (2.6) можно представить в виде: Функции (/(X), (Х) являются непрерывными и кусочно диф-еренцируемыми на отрезках: не определена при х=і Рис.3.5 Без ущерба для дальнейших рассуждений определим производные it (Рос и в точках, где они не определены: В общем случае задача минимизации функционала (3.25) есть задача внриационного исчисления. В нашем случав она легко решается, как задача нахождения минимума величины функций переменных iPj fa) при заданных начальных условиях . Тривиальное решение очевидно: ffiftj- j р(осфі)=0. При этом Е=0. Остальных решений, т.е. экстремалей fPj C ) функционала 1 , как легко убедиться, не существует. Однако две гистограммы с точки зрения применимости частотного алгоритма кодирования блоков все же можно сравнить из следующих соображений? внутри интервалов все слова К ( /) кодируются словами с & единицами, т.е. поведение №fa) внутри этих интервалов не имеет никакого зна чения - важна лишь их сумма. Обозначим эту сумму через Q% , Последнее выражение дает возможность оценить величину Е, не вычисляя Р(У) , а зная лишь интегральную величину Qt на определяемых выражением (3,30) участках упорядоченной гистрограм Для стохастического процесса с реализациями К , упомянутого в начале параграфа, выражение (3.22) дает возможность вычисления величины Е по участку из А/ реализаций исходного процесса. В этом случае вопрос о применимости алгоритма к сжатию массива, сформированного N реализациями исходного процесса решается уже не с помощью трудоемких вычислений суммы из I произведений (3.21), а вычислением по ({ --/) площадям и двум значениям ( Ю и срг ) величины Е по формуле (3.22) и затем нахождения оптимального г» по методике, изложенной в предыдущем параграфе. В заключение отметим, что идеальное сжатие при идеальном выборе разрядности " Г " достигается в случаях
Оценка эффективности сжатия с помощью АКР
Достаточным условием сжимаемости массива при формировании Рд в соответствии с вариантом I будет: Для массива, сжимаемого в соответствии с вариантами П, Ш, как нетрудно видеть, достаточным условием сжимаемости будет также (3.&9) При формировании Рд в соответствии с вариантом 17 достаточное условие сжимаемости ужесточается: Сравнивая формулы (3J39) и (З.І40), нетрудно видеть, что необходимым и достаточным условием преимущества организации массива варианту I по сравнению с вариантом Л, т.е. условием неравенства является Сравнивая (3.39) и (3.41) также легко получить условие преимущества Mg Mj : Аналогично M Mj при выполнении неравенства He вызывает никаких затруднений и сравнение других вариантов формирования Рд и вывод условий выбора способа формирования массива Рд. Из изложенного в настоящем параграфе следует, что для решения вопроса о применимости АКР, выбора наиболее оптимального для конкретного случая способа формирования массива достаточно знать: -число 1=\\{ і}[\ 3.6.3. Верхние границы коэффициентов сжатия с помощью АКР Достаточное условие сжимаемости массива с помощью алгоритма АКР может быть сформировано следующим образом: Для эффективного сжатия с помощью АКР одинаковые блоки в массиве должны группироваться на расстоянии, не большем, чем количество возможных блоков той же длины. В пре -дельном, наилучшем для сжатия случае, блоки одинакового вида стоят рядом друг с другом. В этом случае Q.- feconSi, При W- 00 все К Ц стремятся к величине "К". Это естественно, ведь, в сущности, сжатие АКР достигается за счет замены блоков разрядности "К" на блоки меньшей длины, которая не может стать меньше I. Т.о. для АКР ПриЛК-оо все Кож мах стремятся к величине "К". Это естественно, ведь, в сущности, сжатие АКР достигается за счет замены блоков разрядности "К" на блоки меньшей длины, которая не может стать меньше I. Т.О. для АКР В настоящем параграфе мы рассмотрим возможность последовательного применения алгоритма АКР и частотного алгоритма. 3.7,1. Применение АКР после применения частотного AAG-алгоритма. Такой вариант совместного применения алгоритмов менеее эффективен, чем каждый алгоритм, примененный к данному массиву в отдельности.
Действительно, применение частотного алгоритма не влияет на расположение блоков в массиве, поэтому эффективность сжатия по сравнению с АКР - алгоритмом не должна улучшиться. Другими словами, блоки исходного массива, замененные блоками из ААС-алфавита, или какого-либо другого, останутся на тех же расстояниях друг относительно друга, как и в исхожном. Величина объема алфавита между тем, увеличится по сравнению с объемом алфавита необходимой при сепаратном применении АКР за счет последовательности слов і h у , стоящих в том порядке, в котором они впервые встретились в исходном для АКР (т.е. конечном для ААС) массиве. Между тем порядок следования Г однозначно и прямо соответствует порядку следования Г , который не изменился после применения частного алгоритма. Объем самой последовательности[ feij останется одинаковым, как при сепаратном применении АКР, так и при применений АКР после ААС. Если вспомнить и о дополнительных аппаратурных либо временных затратах на выполнение предварительно операций частотного алгоритма, то из всего вышейзлоложенного можно сделать вывод:- применение совместно АКР и частотного алгоритма по схеме "частотный алгоритм, а после него АКР" нецелесообразно
