Исследование линейных дискретных систем, заданных интервальными характеристическими матрицами

В настоящее время теория автоматов успешно применяется в различных областях современной науки и техники. Это обусловлено тем, что автомат является адекватной математической моделью описания поведения сложных систем. Существуют две основных модели автоматов: автомат Мили и автомат Мура. Эти модели впервые были описаны в 1955 году Мили в работе [37] и в 1956 году Муром в работе [38], которая была переведена на русский и опубликована в 1956 году [21].

Теория экспериментов с автоматами является основой для некоторых разделов кибернетики, одним из которых является техническая диагностика. Эта теория является фундаментом многих современных методов и средств технической диагностики цифровой аппаратуры. Одной из существенных причин, порождающих сложности при решении проблемы диагностирования, является отсутствие информации о начальном, промежуточном или конечном состоянии устройства. Для снятия указанной неопределенности служат синхронизирующие, установочные и диагностические последовательности, подаваемые при проведении соответствующего эксперимента на входы устройства. В настоящее время теория экспериментов с автоматами достаточно хорошо развита и представлена в ряде работ: Гинзбурга С. [10], Глушкова В. М. [11], Гилла А. [8], Минского [20], Твер-дохлебова В.А. [30], Кудрявцева В. Б. [18], Сперанского Д. В. [6], Сытника А. А. 28], Богомолова A.M. [5, 6], Салия В. Н. [5] и других авторов. Полученные результаты позволяют сделать вывод о значительной трудоемкости методов синтеза упомянутых последовательностей, а также о сложности проверки факта существования этих последовательностей для конкретного автомата. Заметим, что в большинстве случаев проверка наличия у заданного автомата того или иного вида последовательности фактически была равносильна по трудоемкости ее построению.

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

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

Один из таких подклассов является классом линейных дискретных систем, так называемых линейных последовательностных машин или линейных автоматов. В дальнейшем мы будем использовать термин линейный автомат для обозначения представителя этого класса. Линейные автоматы сочетают в себе свойства линейных систем и конечных автоматов. Они имеют большое прикладное значение, так в монографии Гилла А. [9] отмечается, что такие автоматы: «. нашли широкое применение для решения многих характерных задач вычислительной техники, связи и автоматического управления, чем объясняется практический интерес к изучению этих машин. Среди наиболее важных областей их применения нужно отметить следующие: вычисления в кольцах многочленов и конечных полях, построение синхронизирующих устройств и счетчиков, воспроизведение линейных кодов, обнаружение и исправление ошибок, адресация в запоминающих устройствах, построение тестовых последовательностей с минимальным временем испытания, генерация последовательностей псевдослучайных чисел, которые применяются для повышения точности измерений в радиолокационных устройствах, при проведении вероятностных экспериментов, в задачах, требующих использования метода Монте-Карло, и т. д.» .

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

разделах математики очень велика и потому применительно к линейным автоматам аналитические методы открывают заманчивые перспективы.

Из работ, посвященных изучению свойств линейных автоматов, необходимо отметить следующие: монография Гилла А. [9], работа Фараджева Р. Г. [31], а также ряд работ Сперанского Д. В. [24, 25, 26].

В этих работах основное внимание уделялось диагностическим, установочным и синхронизирующим экспериментам. Эти эксперименты выясняют начальное и конечное состояния исследуемого автомата. Построение таких экспериментов основано на знании поведения линейного автомата, которое в свою очередь точно определяется его характеристическими матрицами. Однако не всегда эти матрицы известны перед началом проведения экспериментов по распознаванию состояний автомата. Поэтому и возникает задача определения этих матриц на основе эксперимента с экземпляром автомата, который перед началом эксперимента представляет собой «черный ящик». Эта задача является задачей распознавания автомата в классе линейных автоматов. Задача распознавания конечных детерминированных автоматов исследовалась в работах Гилла [8], Мура [21], Твердохлебова [30]. В них получены условия разрешимости задачи распознавания и оценки длин распознающих экспериментов. Эти оценки позволяют говорить о том, что такие эксперименты являются трудно реализуемыми из-за большой длины для автоматов, описывающих поведение реальных устройств с большим числом состояний.

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

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

В [2] отмечается, что интервальные методы являются наиболее перспективными при решении задач в условиях неопределенности.

Методы интервального анализа, используемые в настоящее время, базируются на использовании арифметических операций с вещественными и комплексными числами. В первой главе диссертации вводится интервальная арифметика над конечными полями GF (p), где р — простое число. Необходимость такой интервальной арифметики обусловлена потребностями развития методов теории дискретных систем.

С физической точки зрения уровни значений напряжений для входных и выходных значений сигналов, а также уровни значений состояний элементов памяти электронных устройств, описываемых математическими моделями линейных автоматов, можно измерять в «квантованных» единицах. Поскольку по техническим условиям значения напряжений имеют ограничения сверху, предельное значение этих напряжений, выраженное в «квантованных» единицах, и дает характеристику р поля GF (p). Отсюда же возникает и необходимость оперировать с квантованными значениями напряжений в арифметике по модулю р.

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

В связи с вышеизложенным, целью диссертационной работы является исследование линейных автоматов, заданных интервальными характеристическими матрицами, а также линейных автоматов с интервальным выходом.

В соответствии с целью исследования были поставлены следующие конкретные задачи:

1. Ввести интервальную арифметику над полем GF (p).

2. Исследовать свойства интервальных операций.

3. Найти метод решения системы линейных алгебраических уравнений с интервальной правой частью над полем GF (p).

4. Решить задачу распознавания линейного автомата, заданного интервальными характеристическими матрицами и получить оценку длины распознающего эксперимента.

5. Предложить метод синтеза линейных автоматов для упрощения решения задачи распознавания.

6. Найти способ построения диагностической последовательности для линейного автомата с интервальным выходом.

7. Предложить методы решения диагностической задачи для линейного автомата с интервальным выходом.

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

Работа состоит из введения, трех глав, содержащих 12 разделов, заключения и списка литературы, включающего в себя 49 наименований. Диссертация изложена на 101 странице.

Заключение

.

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

1. Введена интервальная арифметика над полем GF (p). Основным объектом в ней является мультиинтервал над полем GF (p). Исследованы свойства интервальных операций. Предложен метод решения системы линейных алгебраических уравнений с интервальной правой частью над полем GF (p).

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

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

4. Создан ряд программ: для реализации интервальной арифметики (в среде Maple), для решения диагностической задачи для линейных автоматов с интервальным выходом (построение диагностической последовательности реализовано на Delphi, решение на основе решения СЛАУв Maple, решение на основе генетических алгоритмов — на языке С).