Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации (1974) (1186213), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

е. π ^ (xt) > 0;б) сумма элементов любой из ее строк равна единице, т. е.м/-ов) в матрице не имеется столбцов, состоящих из одних нулей, чтосоответствует отсутствию в автомате состояний, вероятность перехода в которые равна нулю, т. е.мТакие матрицы называются стохатическими.

Известно, что стохастическими матрицами описывается в теории вероятностей широкий классслучайных последовательностей, называемых простыми цепямиМаркова. Это позволяет анализировать автоматы со случайными переходами с помощью аппарата цепей Маркова [7, 91.Для более полной аналогии с марковскими цепями необходимо рассматривать не просто автоматы со случайными переходами, а так называемые случайные (стохастические) автоматы, у которых случайна нетолько функция переходов, но и выбор начального состояния.

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

Абстрактные схемь! алгоритмовДля реализации основных процессов переработки информации в радиолокационной системе используются программные автоматы,каковыми являются в частности цифровые вычислительные машины(ЦВМ). Особенностью ЦВМ является ее алгоритмическая универсальность, т. е. способность реализовать любые алгоритмы. Алгоритмическая универсальность ЦВМ обеспечивается необходимым наборомопераций и особым принципом организации управления в процессе ихвыполнения.Абстрагируясь от физической реализации, ЦВМ можно представитькак некоторый дискретный преобразователь информации, оперирующий с входными сигналами, которые представлены в виде слов в конечном алфавите, и выдающий информацию также в виде слов в некотором выходном алфавите, в общем случае, отличном от входного.Процесс преобразования информации сводится к установлению однозначного соответствия между словами входного и выходного алфавитов. Всякая функция, сопоставляющая слова выходного алфавитасловам входного алфавита, называется алфавитным оператором илиалфавитным отображением 14].Все конкретные алфавитные операторы могут быть заданы с помощью правил, позволяющих за конечное число шагов установить выходное слово, соответствующее любому наперед заданному входномуслову из области определения алфавитного оператора.

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

До сихпор мы пользовались понятием алгоритма именно в этом смысле.Определение установленное в абстрактной теории алгоритмов не противоречит общепринятому. Разница состоит только в том, что в абстрактной теории заведомо имеется в виду алгоритм переработки дискретной информации, представленной в некотором конечном алфавите.Этим подчеркивается принципиальная особенность реализации алгоритмов на ЦВМ.Алгоритмам присущи следующие общие свойства:1) детерминированность, состоящая в том, что метод действия(вычислений) задается настолько точно и общепринято, что не остаетсяместа произволу;2) массовость, состоящая в том, что алгоритм служит не для решения какой-либо одной конкретной задачи, а для решения целого класса задач;3) результативность, состоящая в том, что алгоритмическая процедура должна остановиться через конечное число шагов, после чегоможно получить результат.Способы представления и преобразования алгоритмов в самом общем виде рассматриваются в абстрактной теории алгоритмов.

Эта теорияполучила широкое развитие в трудах советских ученых, о чем свиде68тельствует большое число публикаций в периодической печати и монографиях [1, 4, 10, 11].В данном параграфе излагаются элементарные вопросы абстрактной теории алгоритмов, которые будут использоваться в дальнейшем.2.2.1 Способы задания алгоритмовВ абстрактной теории алгоритмов разрабатываются некоторые общие способы задания алгоритмов, обладающие свойством универсальности. При этом доказывается, что всякие общие способы задания алгоритмов включают в себя объекты двоякой природы, одни из которыхназываются операторами счета, а другие — логическими операторамиили распознавателями. Элементарные операторы счета обозначаютсяAlt А2, ....

Аи ••• и представляют собой достаточно простые алфавитные операторы, с помощью последовательного выполнения которых осуществляется переработка информации. Распознаватели, обозначаемыев дальнейшем через P l t P 2 , .... Рг> служат для распознавания тех илииных свойств перерабатываемой алгоритмом информации и для изменения, в зависимости от результатов распознавания, порядка следования элементарных операторов счета.Одним из наиболее известных способов задания алгоритмов являются блок-схемы или формульно-логические схемы алгоритмов. На блоксхеме алгоритма каждый элементарный оператор и распознавательпредставляются в виде геометрических фигур (прямоугольников,ромбов, кружков и т.

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

Например, из операторов А1( Аг, А3, А 4 и А6 и распознавателейPi» Рг» Рз и Р 4 можно составить следующую операторную схемуВ этой схеме знак f означает начало стрелки, а знак \ ее конец.Одинаковыми номерами отмечаются начало и конец одной и той жестрелки.

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

Работа алгоритма прекращается тогда, когда последнийиз сработавших блоков содержит указание о переходе к операторуостанова Ак.Для операторных схем сложных алгоритмов часто используется несколько отличный от описанного способ обозначения последовательности срабатывания блоков, или, как принято говорить, способ передачи управления от блока к блоку.Передача управления от операторов счета к оператору, не стоящемурядом, обозначается приписыванием к символу оператора справа вверху номера того оператора, которому передается управление. Например,запись At означает, что от оператора Aj управление передается оператору 3.

Факт передачи управления данному оператору обозначается номером того оператора, от которого передается управление,записываемым слева вверху от символа данного оператора. Например,6запись А 2 означает, что оператору А2 управление передается отоператора 5.Для изображения передачи управления от логических операторовиспользуются стрелки с номерами тех операторов, которым передаетсяуправление. Стрелка, поставленная справа вверху от символа логического оператора обозначает передачу управления в случае, когдаусловие, проверяемое данным логическим оператором выполнено,а управление должно быть передано не рядом стоящему блоку (оператору). Стрелка, поставленная справа внизу от символа логическогооператора, обозначает передачу управления в случае, когда условие,проверяемое данным логическим оператором, оказывается невыполненным.

Например, запись Р\1 означает, что от логического оператораР: управление следует передать оператору 3,' если условие проверяемое Р 1 ( выполнено, или оператору 4, если это условие не выполнено.В новых обозначениях операторная схема (1) записывается в видеАо6А1Р215А3Р4|72Р5цАе<А7Р8|кАе»АК.(2.2.2)Высокая степень абстракции достигается при задании алгоритмовс помощью матриц и направленных графов особого рода, которыеназываются граф-схемами алгоритмов.Матричная схема алгоритма имеет видАА2ctOnct0K(2.2.3)ηA,осαηατгде ai} = au (P 1 ( P 2 , ....

P,), ί = 0, 1, 2, .... л , } = 1, 2— логические функции, удовлетворяющие следующему70n, n + 1условию:если после выполнения оператора Af функция аи при некотором наборе логических переменных Р а , Р 2Р/, принимающих значенияР г — 1 или Р; = 0, равна единице, то следующим должен выполнятьсяоператор А ; . Возможно, что некоторые функции <хц ~ 1, тогда непосредственно за оператором А( должен выполняться оператор А;-. С другой стороны, некоторые из atJ могут быть тождественно равны нулю(сс;; = О).

Характеристики

Список файлов книги