Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации (1974) (1186213), страница 15
Текст из файла (страница 15)
Последнее означает, что при работе алгоритма, описываемогоданной матричной схемой, непосредственно после оператора А(невозможно выполнение оператора А; ни при каком наборе значенийлогических переменных.Для алгоритма, операторная схема которого записана выражением(1), матричная схема имеет вид1A20A30P PPiPiP 3PPAi"0A,T 1*3д P P232Δ —A3 0A4 0A60000000OiA, A5 AK0 0 0;000!p200!00!100(2.2.4)p4 p4j01jПусть запись At -*• Aj означает, что после выполнения оператораА( следует выполнять оператор А,-. В операторной схеме алгоритмаэтой записи соответствует непосредственное следование оператора А;за оператором А,-, т.
е. AfA^ а в матричной схеме ai} = 1. ЗаписьAfj -г a i 2 A 2 -j- ...(2.2.5)означает, что после выполнения оператора Af следует выполнять тотоператор, у которого функция аи, стоящая непосредственно слева отоператора А^ в выражении (5), равна единице. Другие функции оц,/ Ф j, будут при этом равны нулю.Выражение (5) называется формулой перехода для оператора А;.Такие формулы легко могут быть составлены для всех операторов счета алгоритма, заданного матричной схемой.. Для этого необходимо:а) каждый оператор А; {/ = 1, 2,..., л, п + I) умножить на логическую функцию, которой он подчинен после оператора Аг;б) все произведения а(;А^, полученные из элементов ί-й строки и соответствующих операторов, соединить знаком дизъюнкции.Так, из матричной схемы (4) получаем следующую систему формулперехода(2.2.6)AK.71Другим способом формального-описания алгоритмов является представление их в виде граф-схем.
Граф-схема алгоритма есть конечныйориентированный граф, удовлетворяющий следующим условиям:а) в каждом графе есть два отмеченных узла: входной (соответствующий оператору пуска), из которого выходит только одна стрелка,и выходной (соответствующий оператору останова), из которого не выходит ни одной стрелки;б) из каждого узла, отличного от входного или выходного, выходитлибо одна стрелка (А-узел), либо две (Р-узел); стрелки, выходящие изР-узлов, отмечаются знаками + и — или цифрами 1 и 0;в) каждому А-узлу однозначно сопоставлен оператор преобразования информации Af, а каждому Р-узлу — логический оператор Р г .В граф-схемах алгоритмов А-узлы, а также входной и выходной узлыусловно изображаются прямоугольниками, а Р-узлы — кружками.Построение граф-схемы алгоритма, равносильной (т.
е. с той жепоследовательностью операторов) заданной матричной схеме, призводится следующим образом:1) сначала строятся "частные графы' (подграфы), равносильные формулам перехода данной матричной схемы;2) затем производится операция объединения равносильных ветвейподграфов;3) наконец, производится операция объединения одинаковых операторов и окончательное оформление граф-схемы.Чтобы получить граф-схему с минимальным или близким к немучислом Р-узлов, необходимо по заданным формулам перехода построить подграфы также с минимальным или близким к нему числом такихузлов. Число Р-узлов можно уменьшить путем объединения однаковыхветвей составляющих подграфов.Методику построения и преобразования граф-схем алгоритмов проиллюстрируем на конкретном примере, взяв в качестве исходной матричную схему алгоритма (4).
Исходными для построения граф-схемыявляются формулы перехода (6). По этим формулам сначала должныбыть построены подграфы для каждого из операторов Ао, А 1( А 2 ,.... АБ.Построение подграфа начинается с приведения формулы переходак скобочной форме, содержащей разложение соответствующей логической функции по каждой из входящих в нее переменных. Например,формула переходапосле приведения записывается в видеАналогично формула перехода для А 2 после приведения имеет видДругие формулы перехода в выражении (6) приведения не требуют.Теперь уже легко построить подграфы каждой операции. Эти подграфыизображены на рис.
2.10.72Следующим этапом является поиск и объединение равносильныхветвей. В нашем случае равносильными являются ветви подграфов би в, начинающиеся с оператора Р 3 и обведенные пунктирной линией.После объединения равносильных ветвей получим подграф, изображенный на рис. 2.11. Других эквивалентных ветвей в рассматриваемом алгоритме нет.58гдРис.
2.10. Подграфы операций алгоритма.Наконец, производится объединение одинаковых операторов счетаи получение окончательной граф-схемы алгоритма эквивалентного заданной матричной схеме. В окончательном виде граф-схема рассматриваемого алгоритма приведена на рис. 2.12.Таким образом, рассмотренный способ построения граф-схем алгоритмов по заданной матричной схеме позволяет производить минимизацию числа логических операторов алгоритма и тем самым способствует егоупрощению. Этап минимизации числаоператоров является необходимым этапом подготовки алгоритма к машиннойреализации. В дальнейшем будем считать, что при синтезе алгоритмов обработки радиолокационной информацииприняты все меры к минимизации егоРис.
2.11. Объединенный подструктуры.граф равносильных ветвей б и в.При анализе свойств и качественных характеристик алгоритмов, предхтавленных граф-схемами, целесообразно дальнейшее преобразование последних с целью объединения операторов счета с логическимиоператорами (попарно или несколько операторов счета с одним логическим оператором) в узлы, которые предназначены для реализации более или менее крупных частей алгоритма. Из каждого такогообъединенного узла будет выходить две стрелки. Стрелка обозначается знаком «+» или «1», если в результате выполнения операции узлапроверяемое условие выполняется, и знаком «—» или «0», если этоусловие не выполняется.73Например, для алгоритма, граф-схема которого приведена нарис.
2.12, можно произвести следующее объединение операторов в блоки (входной и выходной узлы ни с чем не объединяются):*А2Р2, а3 ~ Р 3 ,А4Р4,А3А4Р4,А6.Получаемая при этом преобразованная граф-схема алгоритма изображена на рис. 2.13.Рис. 2.12. Граф-схема алгоритма.Сравнение преобразованной граф-схемы алгоритма с рассмотренными, ранее графами конечных автоматов показывает их полную аналогию. Эта аналогия Позволяет в дальнейшем подходить к исследованию, алгоритмов, реализуемых с помощью конечных автоматов и ал-Рис. 2.13. Преобразованная граф-схема алгоритма.горитмов, реализуемых на универсальных программных автоматах(ЦВМ) с единой точки зрения и с помощью одного и того же математического аппарата.2.2.2.
Композиция алгоритмовКак и ранее, под композицией алгоритмов понимаются различные спосо.бы соединения алгоритмов с целью обеспечения их совместной работы. При этом, естественно, решаются задачи минимизациичисла операторов объединенного алгоритма:Одним из наиболее распространенных видов композиции алгоритмов является их суперпозиция.
При суперпозиции двух алгоритмов Аи В выходное слово первого алгоритма А рассматривается как входноеслово второго алгоритма В, так что результат суперпозиции (алгоритмД) можно представить в виде Д — В (А). Это определение, естественно, распространяется на случай суперпозиции какого угодно конеч74ного числа алгоритмов.
Для получения граф-схемы., объединенногоалгоритма достаточно в этом случае выходной узел каждого предыдущего алгоритма совместить с входным узлом последующего алгоритма.Другими возможными методами композиции алгоритмов являютсяих объединение, разветвление, повторение (итерация) и т. д. Мы в дальнейшем рассмотрим простейший случай объединения двух алгоритмов,заданных матричными схемами.Итак, пусть решается задача объединения двух алгоритмов. В качестве первого составляющего алгоритма возьмем' алгоритм, рассматриваемый в предыдущем пункте и заданный матрицей (4). Матричнаясхема второго составляющего алгоритма имеет видAoA2A2 = A3A4A5AflA2 A 3 A4p5 P5 00000010Pi Px000000A50000Ae0001AK0000P 5 P 3 P5P3 p5Рз p 3 0(2.2.7)В каждом из объединяемых алгоритмов порядок следования операторов счета, после проверки одних и тех же логических условий, какправило, различный.
Например, в рассматриваемом случае при выполнении условий логического оператора Р! в первом алгоритме выполняется оператор А2, а во втором — оператор А4. Поэтому в объединенныйалгоритм должны быть введены дополнительные логические переменные, определяющие приндалежность оператора счета к тому или иномуалгоритму. Число к дополнительных переменных связано с числом Nобъединяемых алгоритмов соотношением 2к ^ N. В нашем случае достаточно ввести одну новую логическую переменную π и положить,что для операторов счета алгоритма Л\ эта переменная принимаетзначение 1(4-), а для операторов алгоритма Л2 — значение 0 (—).Итак положим:l liпП— для операторов алгоритма Лх — A o , Аг , А 3 , Л ^ ' А Б " — Дополнительная переменная — π = 1;— для операторов алгоритма Лг — AQS\ к{22\ Аза\ А!,21, А ^ 1 —дополнительная переменная π = 0:Для операторов Аг и А6, каждый из которых входит только в одиниз алгоритмов переменная л исключается.В процессе решения поставленной задачи прежде всего составляетсяматрица объединенного алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
