Алгоритм методу розкриття визначників без дублікацій

В заключение применим полученные результаты к расчету оценок сверху значений сумм (9) для каскадного и параллельного соединения N звеньев в схеме ЦФ. Импульсную характеристику тракта каскадного соединения Л/-звеньев вычислим как дискретную свертку импульсных характеристик отдельных звеньев

< П <2* (О*.

Из выражения (10) следует справедливость рекомендаций И, 21 объединения соседних нулей и полюсов при разбиении передаточной функции всего фильтра на передаточные функции отдельных звеньев, поскольку при этом обеспечивается минимальное значение коэффициентов (8) и сумм абсолютных значений отсчетов импульсных характеристик (9).

Подобный прием нельзя использовать в схеме с параллельным соединением звеньев, где импульсная характеристика сквозного тракта ЦФ равна сумме импульсных характеристик отдельных звеньев. Оценка значения (9) для тракта с параллельным соединением звеньев

..Л = 2

п*=0

2 1Ш)п

/=»1

Поскольку рекурсивные части передаточных функций звеньев в схемах с каскадным и параллельным соединением звеньев одинаковы, то различия в значениях оценок (9) и в разрядности операндов в этих вариантах можно выявить путем сравнения значений (8) и учета (10) и (11). Однако выполнение этого сравнения выходит за рамки данной статьи.

1. Брунченко А. В., Бутыльский Л. М., Гольденберг Л. М. и др. Цифровые фильтры в электросвязи и радиотехнике. М.: Радио и связь, 1982. 220 с. 2. Зааль Р. Справочник по расчету фильтров. М: Радио и связь, 1983. 752 с.

Поступила в редколлегию 25.09.84

УДК 621.372.061

В. К. ЛОВКИЙ, канд. техн. наук АЛГОРИТМ МЕТОДА РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЕЙ БЕЗ ДУБЛИКАЦИЯ

Анализ радиоэлектронных схем в буквенном виде приводит к. задаче раскрытия определителя и алгебраических дополнений матрицы схемы. Одним из наиболее распространенных методов, используемых при этом, является метод обобщенных чисел [1, 5].

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

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

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

Каждый обратимый элемент, включенный между узлами а и Ь, записывается в две строки а и Ъ древесного матричного числа. Если один из узлов базисный, то элемент записывается только в одну строку-

Необратимый элемент (например, зависимый источник тока, управляемый напряжением в случае анализа методом узловых потенциалов), включенный между узлами а и Ь, управляемый напряжением между узлами cub, записывается в две строки с номерами а и Ь. Если один из этих узлов базисный, то запись производится только в одну строку с номером небазисного узла. Перебор всевозможных сочетаний производится так же, как описано в работе [3]. Определение наличия контуров (циклов) производится с использованием массива топологии [4].

При определении наличия контура из обратимых элементов столбец отбрасывается как дубликация. Значительно сложнее определить дубликации с ветвями необратимых элементов.

Граф необратимого элемента содержит ветви, которые мы условно назовем ветвями четырех типов. Ветвь первого типа направлена от узла с к узлу а; ветвь второго типа — от узла b к а, третьего — от с к Ь; ветвь четвертого типа является собственной ветью узла Ь. Если в выбранный столбец входит одна ветвь второго или третьего типов, то этот столбец отбрасывается как дубликация.

Аналогично поступаем и в случае, когда в столбец входят ветви необратимых элементов (различных), при этом каждая из них второго либо третьего типов.

Если в выбранный столбец входит хотя бы одна ветвь первого или четвертого типов, необходимо вначале определить, нет ли в этом столбце (его графе) контура из обратимых элементов и ветвей необратимых элементов только второго и третьего типов. Если такой контур имеется, то столбец отбрасывается как дубликация.

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

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

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

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

Для построения алгебраического дополнения вида Дгг для всех кодов обратимых элементов, включающих код I, он заменяется на О зсли суммарный код получается нулевым, то элемент исключается из массива кодов соединений). Аналогично поступают и для кодов необратимых элементов.

В случае построения алгебраического дополнения вида Д^ также претерпевают изменения только коды, содержащие узлы I и/или /. Ниже приведены правила замены таких кодов.

И ОН ¡1 ¡01 ///->-//» И -> ОН Щ-+1

/7 ->- 0//' 121г1 у^' 1/7 -->- ¡01

// -у о// 12иг — /¿/ ->- но ч /о; 1/2/1->-о/2/1 ¡и ->- /17/

(I — производный узел схемы, не совпадающий с I или /).

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

1. Каширский И. С., Ловкий В. К., Трохименко Я К. Проектирование радиотехнических схем на инженерных ЭЦВМ. Киев: Техшка, 1976. 272 с. 2. Ловкий В. К. Анализ радиоэлектронных схем на инженерных ЭВМ: Автореф. ... канд. техн. наук. Кие^ 1973. 20 с. 3. Ловкий В. К. К реализации метода обобщенных чисел на малых ЭВМ//Вестн. Киев, политехи, ии-та. Радиотехника и электроакустика. 1973. Вып. 10. С. 202—204. 4. Ловкий В. К Использование массива топологии для нахождения путей и циклов графа // Изв. вузов СССР. Радиоэлектроника. 1973. Т. XVI, № 6. С. 146—147. 5. Трохименко Я• К. Метод обобщенных чисел и анализ линейных цепей. М.: Сов. радио, 1972. 310 с.

Поступила в редколлегию 25.04.84

УДК 621.317.757

О. П. ЛЫСЕНКО, канд. техн. наук

ШУМЫ ОКРУГЛЕНИЯ ПРИ ЭКОНОМИЧНОМ ДВУМЕРНОМ БЫСТРОМ ПРЕОБРАЗОВАНИИ ФУРЬЕ

Экономичный алгоритм двумерного быстрого преобразования Фурье (БПФ-2) [1] позволяет уменьшить вдвое количество нетривиальных умножений по сравнению с последовательным (стандартным) преобразованием. По количеству алгебраических сложений оба алгоритма равноценны. Оценим шумы округления результатов при БПФ-2, пользуясь методом анализа шумов при представлении чисел с плавающей запятой, примененным в 121 для одномерного БПФ-1 .

Вначале оценим шумы округления для последовательного БПФ-2, суть которого состоит е последовательном выполнении БПФ-1 строк двумерного массива размерностью N X N, а затем столбцов преобразованного массива. Дисперсия (а2£1) шума, возникающего в результате первого преобразования (строк), определяется |2] как =

= 2vNoc\ol, 0е = 2-2í,/3. Здесь v = log2 N; b — количество двоичных разрядов, представляющих мантиссу; о^ — дисперсия входного сигнала. Второе преобразование (столбцов) обусловливает шум с дисперсией (о|2), равной о2Е2 = 2xNa'2c2a2o, где а2с2 — дисперсия сигнала после первого преобразования. Поскольку о22 — Na7c{, последнее выражение принимает вид о^2 = 2vN2o¿1ajj. Помимо возникновения шума £2 второе преобразование обусловливает увеличение шума Е\ в N раз, т. е. его выходная составляющая равна Поскольку шумы ок-

ругления аддитивны и некоррелированны, дисперсия полного выходного шума при последовательном БПФ-2 определится как а| = a2ElN + + — Отношение С/Ш на выходе с учетом, что дис-

персия выходного сигнала о2 = N2o\v равно

С/Ш = Ос/а| =

Оценим шум округления для экономичного БПФ-2, который сводится к выполнению БПФ-1 одномерного массива размерностью N2. При таком алгоритме для v/2 нетривиальных этапов элементар-