Некоторые методы и устройства сжатия двоичных информационных массивов в бортовых информационно-измерительных системах научных космических исследований

Основные направления экономического и социального развития СССР на I98I-I985 годы и на период до 1990 г.", принятые ХХУ1 съездом КПСС, предусматривают в качестве одной из важнейших задач развития науки и ускорения технического прогресса «дальнейшее изучение и освоение космического пространства в интересах развития науки, техники и народного хозяйства» [Vj. Интенсивность космических исследований все более возрастает, лавинообразно увеличивается количество научных и прикладных задач в исследовании космоса и соответственно увеличивается количество экспериментов, состав и качественные характеристики научной аппаратуры на борту космических аппаратов, предназначенной для исследования атмосферы.

Результаты прямых измерений физических величин в космосе, как правило, не могут быть непосредственно восприняты экспериментатором, что связано как с удаленностью и специфичностью объекта наблюдения, так и с большим количественным составом приборов, участвующих в эксперименте. Именно это обстоятельство и обусловило необходимость создания сложных многозвенных совокупностей бортовых и наземных технических средств и комплексов алгоритмов, обеспечивающих получение результатов научного космического эксперимента — информационноизмерительных систем научных космических исследований (ИИС НКИ).

Количество информации, поступающее с измерительных каналов бортовых научных приборов в единицу времени растет с ускорением научно-технического прогресса гораздо быстрее, нежели технические характеристики средств передачи данных с борта космического аппарата (КА) на Земшо [^2 J. Поэтому к бортовой части ИИС НКИ предъявляется два противоречивых требования: при безусловном сохранении всех необходимых экспериментатору сведения с заданной погрешностью, она должна описать их так, чтобы существующие бортовые средства передачи данных донесли их до пользователя без потерь.

Разрешение этого противоречия состоит в разработке методов и устройств сжатия информации. Поэтому задача сжатия информации на борту КА является сейчас одной из важнейших задач, решаемых бортовыми ИИС НКИ [з], что и определяет актуальность темы диссертации. Существуют два класса методов сжатия информации — класс методов необратимого сжатия, носящих в литературе название «устранение избыточности» и «сжатие с потерямиГ и класс методов обратимого, восстановимого преобразования исходной информации.

Методы необратимого сжатия основаны на работах по способам восстановления непрерывного сигнала по дискретным отсчетам и работах по вычислению? -энтропии класса функций, связанных, в первую очередь, с исследованиями В. М. Котельникова, А. Н. Колмогорова, А. А. Харкевича, Р. Л. Добрушина, М. С. Пинскера, Ф. Е. Темникова и др.

Обратимое сжатие информации берет свое начало от работ К. Шеннона, Р. Хартли, Р. Файнстейна, Р. Фано и перечисленных вше исследователей. Методы обратимого описания случайных последовательностей с известным распределением вероятности получили название оптимального статистического кодирования. Важнейшие результаты получены здесь Д. Хаффменом, Р. Крафтом, Л. Д. Девиссоном. Б. М. Фитингоф, Р. Е. Кричевский, Р. Гилберт, Ю. М. Штарьков и другие рассмотрели случайные последовательности с неизвестным заранее распределением вероятностей и разработали оптимальные для бесконечных последовательностей методы описания на основе наблюдения статистики первых символов последовательности. Это направление получило в литературе название оптимального универсального кодирования.

Результаты наблюдения статистики первых символов случайной последовательности дают верное представление о распределении вероятностей только тогда, когда не только относительные частоты символов сходятся к вероятностям, но эти символы и появляются «беспорядочно». Поэтому для определения границ применимости оптимального и универсального кодирований решающее значение имеет определение рамок применимости самой теории вероятностей, определение понятия «случайная последовательность». Впервые такую задачу поставил Р.МизесА.Н.Колмогоров в работе [4] предложил невероятностный, «алгоритмический» подход к описанию последовательностей с помощью вычислимых /частично-рекурсивных/ функций. Более того, на этой основе он поставил задачу обоснования теории вероятностей и, в частности, определения понятия «случайная последовательность», которое в дальнейшем и дал П. Мартин-Лёф. [99] После этих работ стало ясно, что не все последовательности, которые не являются детерминистическими, могут быть корректно описаны аксиоматическими вероятностными моделями, а алгоритмический подход к описанию последовательностей — наиболее универсальный и перспективный. Алгоритмические проблемы описания последовательностей рассматривали В. Н. Агафонов, И. М. Гельфанд, А. М. Яглом, А. К. Звбнкин, Л. А. Левин, Д. В. Ловеланд, Т. М. Ковер и др. Практическая разработка методов описания, основанных на этой теории, затруднялась сложностью нахождения причины «неслучайности» по Мартин-Лёфу конкретных последовательностей и впервые была начата И. Я. Акушским, А. И. Амербаевым, И. Т. Паком и др., причем машины /частично-рекурсивные процедуры/ сжатия представляли из себя достаточно сложные и объемные программы для больших наземных ЭВМ. В бортовой ИИС НКИ имеется несколько этапов переработки информации, и, как следует из предыдущего, задача сжатия должна решаться в зависимости от характера последовательностей, возникающих на каждом этапе. Различным будет и аппарат определения эффективности сжатия. Для алгоритмических методов описания эффект будет иметь место в том случае, когда сама процедура сжатия разрабатывается на основе характерных свойств, присущих сжимаемым последовательностям, и вытекающих из объективных обстоятельств космического эксперимента-алгоритма функционирования ШО и наличия каких-либо событий на входах ИИС.

Итак, при сжатии информации на всех этапах ее переработки в бортовой ИИС НКИ необходимо последовательно решить ряд задач:

1.Устранить избыточность измерительных сигналов на входах ИИС можно двумя способами:

— применить методы необратимого сжатия исходя из требований пользователя к точности восстановления сигнала;

— выделить из сигнала непосредственно на борту КА только те его характеристики, которые необходимы пользователю и, так j или иначе, будут выделены на Земле, т. е. осуществить на борту первичную обработку данных.

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

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

3.В случае неслучайности по Мартин-Лёфу последовательностей проанализировать возможные причины этого факта-на основе сведений об алгоритме функционирования ИИС формализовать детерминистические ограничения в виде условия принадлежности этих последовательностей определенному множеству 60 (Uto = ¦Я).

4.Разработать процедуры описания, последовательностей, дающие (если это возможно) эффект сжатия на множестве СО и общерекурсивные на множестве S?, оценить максимально возможный наФ проигрыш при такой процедуре.

5.В зависимости от сложности процедуры описания и максимального проигрыша, оценить приемлемость технической реализации метода сжатия на борту КА.

6.Проверить эффективность на реальных сигналах.

Эти задачи и решены в работе.

Работа состоит из введения, пяти глав и заключения. В первой главе дается краткий обзор известных душ бортовых ИИС НКИ методов сжатия сигналов и методов записи служебной информации. Выводится достаточное условие эффективности первичной обработки данных на борту по сравнению с известными методами аппроксимации. Во второй главе рассматриваются последовательности обработанных измерительных и служебных слов в бортовой ИИС НКИ и делается вывод о неслучайности их по Мартин-Лёфу. Выводятся необходимое и достаточное условия средней эффективности алгоритмического описания для бортовой ИИС НКИ. На основе алгоритмов записи служебной информации и влияния событий на входах ИИС НКИ на структуру последовательности формализуется характер этих последовательностей. В третьей главе описаны, алгоритмы сжатия для этих последовательностей и показано выполнение достаточного условия средней на эффективности на материале реальных сигналов. В четвертой главе описана техническая реализация процедуры сжатия в виде специализированного процессора, а также алгоритмы и реализация устройств первичной обработки для геофизических бортовых приборов трех типичных классов. Показано, что технические характеристики разработанных устройств допускают их применение на борту.

КА уже при современном уровне микротехнологии. В пятой главе приводятся результаты, моделирования бортовой ИИС НКИ с первичной обработкой данных и алгоритмическим описанием массивов. Личный вклад автора в работу заключается в следующем:

1.Поставлена и доведена до практического применения задача ' первичной обработки информации непосредственно на борту КА. и выведено достаточное условие ее эффективности.

2.Выведены необходимое и достаточное условия средней на5″? эффективности алгоритмического описания для бортовой ИИС НКИ.

3.Разработаны алгоритмы сжатия для бортовой ИИС НКИ и разработан соответствующий процессор.

4.Разработаны алгоритмы, бортовой первичной обработки сигналов с геофизических приборов /за исключением известного алгоритма первичной обработки манометрических сигналов/ и соответствующие бортовые устройства.

Основные научные положения, выносимые на защиту:

1.ДЛЯ основных бортовых геофизических приборов первичная обработка является наиболее эффективным в настоящее время методом сжатия сигналов.

2.Двоичные последовательности, возникающие в бортовых ИИС НКИ с устройствами обработки данных и состоящие из кодов величин существенных замеров, номеров каналов, меток времени и кадровых пауз, не являются случайными по Мартин-Лёфу и принадлежат определенным ограниченным множествам, нетривиально описываемым формально. Разработанные алгоритмы эффективно сжимают эти последовательности.

3.Технические характеристики спецпроцессоров сжатия и устройств первичной обработки данных геофизических приборов допускают их применение в бортовой ИИС НКИ.

Научная новизна работы заключается в том, что впервые показан факт принадлежности массивов измерительной и служебной информации, образующихся в бортовых ИИС НКИ определенным ограниченным множеством массивов с известными свойствамиразработаны iiipoBepe-ны на модели и экспериментально алгоритмы и специализированные процессоры сжатия этих массивовновизна их подтверждана двумя авторскими свидетельствами на изобретение ioj. Показано достаточное условие эффективности первичной обработки, как метода сжатия по сравнению с аппроксимацией для ряда геофизических приборов, разработаны бортовые устройства первичной обработки, что также подтверждается двумя авторскими свидетельствами на изобретения [II, 12].

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

Результаты работы использованы в эксперименте «Грузия-бО», проведенном ШШ АН СССР (тема «Плазма», Гос.per.№ 8 187 072). Акт прилагается к диссертации.

3. Результаты работы могут быть применены не только для бортовых ИИС НКИ, но и для новых ИИС, у которых количество выходной информации является ограничивающим фактором их применения. В этом случае требуется провести анализ множества образуемых массивов и разработать специализированные алгоритмы и процессоры, аналогично тому, как это сделано в настоящей работе для бортовых ИИС НКИ.

ЗАКЛЮЧЕНИЕ

.

Результаты настоящей работы можно кратко сформулировать в следующем виде:

1. Решить актуальную научную задачу — лаконично описать массивы, подлежащие хранению и передаче в бортовых ИИС НКИ можно путем сжатия сигналов с выходов комплекта научной аппаратуры и сжатия массива служебной и измерительной информации .

2. Для сжатия сигналов КНА можно осуществить на борту часть первичной обработки (генерализацию) сигналов, которая до настоящего времени производилась на Земле. В работе выведено достаточное условие эффективности генерализации по сравнению с применившимися ранее аппроксимационными методами сжатия и показано, что это условие выполняется для широкого спектра геофизических бортовых приборов.

3. Показано, что двоичные последовательности, состоящие из кодов величин сигналов, выделенных устройствами обработки данных, и сопровождающих их кодов номеров каналов и меток времени, при любых известных способах нумерации каналов и временных интервалов, нельзя рассматривать, как случайные по Мартин-Лефу (общепринятое в настоящее время определение случайных последовательностей). По этой причине описание таких последовательностей с помощью методов, использующих законы теории вероятностей, некорректно — оно не дает нприорной гарантии эффективности. Описание последовательностей, возникающих в бортовой ИИС НКИ, может быть основано на подходе А. Н. Колмогорова — путем рассмотрения алгоритма описания аппаратом теории вычислимости.

Показано, что причиной «неслучайности» последовательностей в бортовых ИИС НКИ является упорядоченность в них некоторой части символов, возникающая вследствие включения в последовательность номеров каналов, деления последовательности на кадры и наличия событий на входах научной аппаратуры. В результате выделены три типичных множества последовательностей, возникающих в бортовых ИИС НКИ: со= uJaiJcoe^^c.

5. За описание массива принята, вслед за, программа его воспроизведения некоторой машиной (частично-рекурсивной функцией) А. На базе работ по теории алгоритмического описания выведены необходимое и достаточное условие эффективности такого описания, как метода сжатия. Выведено также достаточное условие эффективности описания для случаев, типичных для ИИС НКИ вследствие уникальности экспериментов — когда мера множества массивов не может быть точно определена количественно, и известны лишь ее ограничения.

6. Разработаны алгоритмы работы машин сжатия А" «*, сопоставляющей каждому массиву программу его воспроизведения машиной восстановления, причем:

— все разработанные алгоритмы общерекурсивны, -для каждого алгоритма показан метод формирования программы рА О), оптимальный для функции, характеризующей степень соответствия" массива ограничением, накладываемым необходимостью его отнесения к множеству аЛна материале реальных сигналов показано выполнение для ИИС НКИ достаточного условия эффективности разработанных машин сжатия.

7. Показана возможность реализации машин сжатия в виде специализированного процессора, по своим техническим характеристикам приемлемого для применения в бортовой ИИС НКИ. Показана также возможность реализации алгоритмов генерализации в виде. бортовых устройств и выведены условия физической реализуемости генерализации на борту КА.