автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Машинно-ориентированный метод синтеза систолических структур для устройств цифровой фильтрации

министерство связи российской федерации Московский технический университет связи и информатики

5 Г Б О Я На правах рукописи

I 2 АПР 1УЬо

Черноусова Татьяна Геннадьевна

удк 681.322.05

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

Специальность: 05.13.13 - Вычислительные машины,комплексы,

системы и сети

автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 1ЭЭ6

Работа выполнена в Московском техническом университете связи и информатики.

Научный руководитель - кандидат технических наук, доцент

Жидаков Владимир.Петрович.

Научный консультант - кандидат технических наук, доцент

Удадов Алексой Иосафович.

Официальные оппоненты - доктор технических наук

Корнеев Виктор Владимирович, кандидат технических наук Кочетов Евгений Леонидович.

Ведущее предприятие - Акционерное Общество открытого типа

Институт Точной Технологии и Про -оптирования. '

Защита состоится "!' " 1996 года, в. ча-

сов на заседании диссертационного совета К 118.06.02 по присуждению ученой степени кандидата технических наук в Московском ордена Трудового Красного знамени техническом университете связи и информатики по адресу: 111024, г. Москва, ул. Авиамоторная, д.-8а.

С диссертацией можно ознакомиться^ библиотеке университета.

Автореферат разослан "¿7 "СреМ~рС\_,_1&. <996 года.

Ученый секретарь , диссертационного совета К 118.06.02, к.т.н., доц. ■/ Е.В. Демина

Кйиу^

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Широкие возможности вычислительной техники нашли эффективное примякяни.е в практике обработки больших, массивов информации в реальном масштабе времени, в связи с э1ш возникают потребности в разработке вычислительных систем оптимально отвечающих требованиям цифровой обработки информации и сигналов.Одной из ключевых проблем, стоящих при решении задач цифровой обработки сигналов (ЦОС), в том числе цифровой фильтрации (Ш). является создание высокопроизводительных проблемно -ориентированных вычислительных систем реального времени. Повышение производительности может быть достигнуто в основном за счет совершенствования элементной базы и схемотехнических решений, принимаемых при построении вычислительных систем, или за счет создания новых архитектур вычислительных систем и способов организации вычислительного процесса .В настоящее время наиболее перспективным направлением повышения производительности вычислительных систем реального времени, ориентированных на определенный класс решаемых задач, является архитектурный. Исследование и разработка новых архитектурных решений ведутся уже более тридцати лет. Еще в 60-е годы Э.В. Евреиновым была предложена концепция однородных вычислительных систем, структур и сред, которая получила наибольшее развитие в работах научных коллективов под руководством И.В. Прангишвили, К.Г.Самофалова, Г.М.Луцкого, В.Г. Хорошевского, Ю.Г. Косарева и других. В рамках архитектурного направления важным классом однородных вычислительных структур являются систолические, представляющие собой пленарную сеть ячеек, основными свойствами которой являются : - однородность ячеек. Любая ячейка выполняет одну и ту же элементарную операцию, например, умножение/ сложение, при этом допускается, что входные и выходные ячейки, называемые граничными или периферийными, могут выполнять другие операции; -регулярность и локальность связей между ячейками, причем каждая ячейка имеет связи только со своими непосредственными соседями:

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

ше ритмично поступают в ячейку, обрабатываются и передаются в соседнюю.

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

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

11@лью_диссертационной работы является разработка метода проектирования систолических структур для устройств 'цифровой фильтрации, работающих в реальном масштабе времени.

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

-исследование существующих методов проектирования систолических

структур для задач цифровой обработки сигналов;

-разработка формализованной процедуры и библиотеки алгоритмов оп-

редэления эквивалентных графов потоков сигналов канонических биквадратных звеньев рекурсивных цифровых фильтров с целью построения из них эквивалентных графов потоков тгявппа ^»»¡рсЕых ф«лът-ров N - го порядка;

-разработка формализованной процедуры и библиотеки алгоритмов определения СИСТОЛИЧвСКИХ СТРУКТУР ЦИфрОЕИХ фильтров по соответ-ствущим т графам потоков сигналов;

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

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

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

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

горитыов) цифрового фильтра N - го порядка определить соответствуйте им систолические структуры по точности выполнения вычислений при ограничениях величины конвейерного такта приема / выдачи элементов входного / выходного потоков данных, а также найти оптимальные из шп по заданным критериям оптимальности.

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

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

Практическая ценность работы.

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

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

при ограничениях: величины конвейерного такта приема / еыдячи элементов входного / выходного потоков данных.

3. Предложен9 структура системы автоматизированного проп^тиронэ-Ш1Я систолических структур цифровых фильтров, целесообразная для практического применения, которая обеспечизаэт выполнение алгоритмического и структурного синтеза цифровых фильтров. Реализация и внедрение. Результаты, полученные автором при выполнении диссертационной работы, были использованы в ОКР 224 / 91, проводимой в специальном конструкторском технологическом бюро с опытном производством Белорусского государственного университета информатики и радиоэлектроники (СКТБ с 011 БГУ ИР), НИР "Исследование путей создания ультра - БИС с программно - перестраиваемой структурой " (шифр "Дума"), выполненной в конструкторском технологическом бюро "Еалмикросистемы" научно - производственного объединения "Интеграл" (КТБ "Бэлмикросистемы" НПО "Интеграл"), о чем подтверждают акта внедрения и использования. Апробация работы. Основные положения диссертации сбсуздоны на VI - й Всесоюзной школе - семинаре по распараллеливанию обработки информации (Льеов, 1987), V - й Всесоюзной научно - технической конференции по однородным вычислительным системам, структурам и средам (Москва, 1991), конференции по телекоммуникационным и вычислительным системам связи (Москва, 1993).

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

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения и содержит 150 страниц основного текста, 95 рисунков и 12 таблиц, перечень использованной научно - технической литературы из 142 наименований,,-ляти приложений. Основные положения, выносимые на защиту:

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

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

3.Граф потоков сигналов, е котором выходные сеязи (v.,,v2),

6S

(у1,у3)........ , вершины у., с соответствую-

щими им передачами ^2=^3= ••• ='с1 к- ... являются вход-

»V П/ Г*» IV

ними для верная у2, у^, ... ,ук, ... , тк, может Сыть преобразован в эквивалентный граф, исток которого т1 соединен с последовательностью вераин у2, г3> ... ,ук, ... ,ук, причем количество таких графов потоков сигналов, отличавшихся друг от друга последовательностью соединений вершин у2, у^.....ук, ... ,ук, равно (К-1 )!.

4.Преобразованный граф потоков сигналов канонического рекурсивного цифрового фильтра N - го порядка, каждой вершине которого соответствует опрерация умножение / сложение, при представлении его в ярусно - параллельной форме может быть раскрашен следующим образом: если вершины графа принадлежат ярусу й, то им присватается цвет Ь, при этом число цветов, присваиваемых Еершинам, равно глубине Н ярусно - параллельной формы этого графа. Б.Пусть задан прообразованный воршинно-раскрашенный граф потоков сигналов канонического рекурсивного цифрового фильтра N - го порядка, любой вершине которого соответствует операция умножение /

сложение. Если входными связями вершины у^ этого графа с цветом 1+1 являются связи (7^, 7^), (7^, 7^), причем вершинам И присвоены соответствующие им цвета I и ® так, что I > в (в * 11 ), тогда связь (7", у^) помечается меткой т.'^, где ;) = X -СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена исследованию методов синтеза систолических структур. Показано, что систолическая структура может быть представлена ориентированным графом У/=(У,Е), множеству вершин У= {Т00' уо1> ■••' ук1> 7кь:> К0Т0Р°Г0 ставится в соответствие множество автоматов, а множеству связей между вершинами Е=1е1, е0, ..., е^, ..., вд} - мнокество связей между автоматами. Граф У¥ является однородным, ациклическим и взвешенным. Каждой вершине графа назначается некоторое целое число (вес) из Р натуральных чисел, определяющее номер цикла, за который срабатывает данная .

вершина, причем, если мовду вершиной ч^, срабатываемой за цикл 1р,и вершиной vkl> срабатываемой за цикл 1п, существует связь, направления« от v^ :: rkl, тогда ip< 1п. Любая связь графа может -з

быть помечена метой Z , где j - число задержек.

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

Предложено методы проектирования систолических структур по виду представления вычислительного алгоритма разделить на два класса: алгебраический, представленный в работах Н.Т. Kung'a, Н. S. bail's,D. Cohen's, Т. P. Barnwell's III, C.J.M. Hodges', D.A. Schwartz's; а также пространственно - временной, представленный в работах А.D.I. Iioldovan и J.A. iortea', G.J. LI и B.W. Wah's, P. H„ Cappello и К. Stetglltz's, W.L. Minmker's, П.Н. Kuhn's, P. Quinton's, I.V.Ramakriatoan's, D.S.Fusaell'a, B.C. Каневского, О.Г. Седухина, B.B. Воеводина и других.Методы проектирования первого классе, позволяющие генерировать множество систолических структур, реализующих одну и ту же вычислительную задачу, путем различных алгебраических преобразований математического выражения, описывающего эту задачу, являются достаточно сложными для их реализации по сравнении с методами проектирования второго класса, которые позволяют генерировать множество систолических структур, реализующих одну и ту же вычислительную задачу, путем нахождения различных проекций графа зависимости.- Исследование методов проектирования систолических структур алгебраического и пространственно - временного классов показало, что при синтезе структур необходимо осуществлять проверку на точность выполнения вычислений, иначе отсутствие учета елияния этого параметра может привести к получении систолических структур со значительной погрешностью вычислений.

Сформулирована постановка задачи маишшо - ориентированного синтеза систолических структур для устройств цифровой фильтрации и предложен новый метод ее решения, который позволяет за счет нахождения множества структур {алгоритмов) ЦФ, эквивалентных в

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

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

Для нахождения множества эквивалентных структур (алгоритмов) канонического рекурсивного цифрового фильтра (РЦФ) еысокого порядка предложено от заданной структуры по схемам замещения перейти к соответствующему ей ГШ. Показано, что определение аквива-дентшх ШС канонического РЩ> высокого порядка, представляющего собой каскадное соединение однотипных канонических биквадратных звеньев, состоит из следующих этапов:

- генерация эквивалентных графов канонических биквадратных звеньев фильтра;

- последовательное соединение эквивалентных графов однотипных канонических биквадратных звеньев согласно заданной передаточной функции РЦФ Ы-го порядка.

Разработана формализованная процедура, а также библиотека алгоритмов определения эквивалентных ГПО канонических биквадратных звеньев Pits, базирующиеся на ряде доказанных утверждений по эквивалентным преобразованиям ГНС. На первом ваге разработанной процедуры любую Евршину ГПС канонического биквадратного звена заданного фильтра с полустепвнью захода больше двух по соответствующей ей комлозицш! продетавляте в виде последовательности вершин, каждая из которых имеет полустедань захода, равную двум. На следующем шаге в последовательности вершин графа, концевыми воршина-ш которой являютя х(п) и у(п), производится перенос вершины ветвления как но направлению прохождения сигнала, так и против. Вершина v. ГПС с полустепеныо захода z(v. )=1 и полустеиеньв исхода

> 2 называется вершиной ветвления. Перенос вершины ветвления ГПС канонических биквадратных звеньев РЦФ осуществляется cor-лвсно преобразованиям графов, доказанных в утверждениях 1,2.

Утядтлуггдп::о ;. Пусх-ь вершина ветвления vk ГПС имеет входную связь

(Y Vk) с передачей т^, являющейся выходной связью Еершины vp,

и еыходныв связи с передачей iki, (\»Y1) с передачей

тк1, являюидаеся входными связями соответственно вершин у^, v^. Положим,что входной связью вершины Vj^ кроме (vk,v1) является также связь (Vj.Vj) с передачей т^, а еыходной - (^Лщ) с передв-чей т1т. Тогда при переносе вершины ветвления vk в последовательности у , vk, vm ГПС по направлению прохождения сигнала для получения последовательности v^, у.^, v^, vn производится замена связей (Vg.Vjj), ) связью (vg, ух) с передачей tgl=Tgic

добавление вершины Yk в связь (v1Pvm), в результате чего находятся связи (virvfc) с передачей т1к = 1, (vk,ym) с передачей = т1га; а также добавление вершины у^ в связь входные связи (у^), ) которой имеют соответственно передачи т^ = 1,

= -x-lt а Еыходаая связь - передачу

Tki

Утверждение 2. Пусть Еершина ветвления Ук ГПС имеет входную связь

Ук) с передачей т1к, являющейся выходной связью вершины и выходные связи (т^.^) с передачей т^, С1^«7^) с передачей тк1> являющиеся входными связшя! соответственно верпзш у , у^. Положим также, что Берлина 71 имеет две входные связи (^Л^) с передачей т 1 и (у^- ,у1 ) с передачей т.д. Тогда при переносе вер-

ГУ /V (V »V «V

шиш ветвления ук в последовательности у , у1р ук, уш ГПС против направления прохождения сигнала для получения последовательности

7 ? V., производится замена связей (т.д. ), (у,,,у )

^ К -1. Гп J-.it 1С П1

сеязью (У7,Ут) с передачей т1т = т1к добавление Еериины

v. в связь (V , v.), в результате чего связь (v , v.) заменяется к „ ~ s ~ х

связь» (vg,vk) с передачей tgk = и связь» (v^.,^) с передачей Ъа = '' а такж9 Добавление вершины v^ е связь (vk,vi), входные связи (v^.v-j^) которой имеют соответственно передачи ■tj^ = btj! = tjx» а выходная связь (v1,vi) - передачу

^li^ki"

На основании преобразования ГПС, доказанного в утверждении 3 .предложен алгоритм определения эквивалентных ГПС канонического биквадратного звена РЦФ из графов,полученных при переносе вершины ветвления по направлению прохождения сигнала либо против. Утверждение 3. Пусть задан ГПС, в котором вершина ветвления vk

имеет входную связь (v^.v^) с передачей = р и выходные связи

(vk, v,), (vk, ч-) с соответствующими им передачами тк1 = р,

= а, а вернина - Еыходнуез связь (v., v.) с передачей т. . = 1.

Л*

Значение выходного сигнала вершины графа не изменится, если связи (v., v ■), (v.,y,J будут иметь соответственно передачи - =

X J J Л X J

р, 1, а связь <vlt, vL) с передачей чк1 = а заменить на

сеязь (vlf т^) с передачей = а .

В соответствии с разработанной процедурой и библиотекой алгоритмов построено множество ГПС {®m=(\»Em)} (m = 1,34), эквивалентных ГПС ¡¡0=(V0, Е0) канонического биквадратного звена рекурсивного цифрового фильтра.При перехода от ГПС к структурам по схемам замещения построено 2А,ЗА,...,15А структур, эквивалентных структуре 1А канонического биквадратного звена РЦФ, каждая из которых имеет две задержки, четыре умножителя, а число входов сумматоров - более двух. Для структур 2А, ЗА, ..., 15А получены передаточные функции.

На основа статистического подхода к ошибкам квантования в цифровых фильтрах с фиксированной запятой построены шумовые модели для всех эквивалентных структур канонического биквадратного звена РЦФ. ПроЕеден расчет дисперсии выходного шума для канонических биквадратных звеньев полосового цифрового фильтра и цифрового фильтра нижних частот, в соответствии с которым определены оптимальные структуры с минимальным собственным шумом при отсут-

ствии переполнений. Получены формулы расчета оур для Р - каскадной структуры из однотшшых биквадратных звеньев, а также разрядности 11 регистров арифметичоского устройство (¡лейка; сис-ю-ллчоской структуры) по заданному максимально допустимому уровню выходного шума. :

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

На основе доказанных утверзвдений представлена процедура и библиотека алгоритмов определения множества систолических структур РЦФ по соответствующим им графам потоков, сигналов, которая Еключаот следующие основные шаги: нахождение из эквивалентных графов штоков сигналов Щ& N - го порядка графов, вершинам которого соответствуют операции умножение / сложоние; выполнение раскраски вершин преобразованных графов; разметка связей преобразованных вершинно - раскрашенных графов; определение конвейерного такта приема / выдачи элементов входного / выходного потоков данных; определение полного времени формирования выходного потока данных.

В соответствии со свойствами систолических структур преобразование эквивалентных ГПС РЦФ К - го порядка на первом шаге разработанной процедуры осуществляется согласно доказанным утверждениям 4-6.

Утверждение 4. Г1Ю, в котором выходные связи (т.,,т2), (у.,,у3), ... , (у^у^), ... , (71 ,ук) Еершины с соответствующими гол передачами т12=г13= """ =т1к" ■■" =т1к=1 яелявтся входными для вершин у2, у3> ... ... ,ук, может быть преобразован в эквивалентный граф, исток которого у1 соединен с последовательностью вераин у2, у3", ... ,ук, ... ,ук. Число таких ГПС, отличающихся друг от друга последовательностью соединений вершин гг, уэ.....

.....равно (К-1)!.

Утверждение 5. ГПС, в котором вершина ветвления Ук имеет входную

п IV »V /V »V «V

связь (^,ук) с передачей т1к=1 и выходные сеязи (^»^щь (у^,^) с соответствующими км передачами и, в результате исключе-

ния вершины Ук может быть прообразован в эквивалентный граф, в котором входной связью вершины Ут является связь с пере-

дачей 1^=1. а выходной - связь (у[п,у1) с передачей , либо в граф, в котором вершина у^ имеет две выходные связи ,

(у1,у1) с соответствуй^ им передачами .

Утверждение 6. ГПО, в котором вершина ветвления Ук имеет входную связь (Ут,Ук) с передачей т^ и выходные связи (у1.,у1), (\,уш) с соответствующими им передачами т^, т^, а Еершина имеет еы-

ходную связь (у1,ут) с передачей результате выполнения опе-

рации замыкания может быть преобразован в граф, содержащий только

две вершины (у1,у1) и (\»ут)- Вершша (т1,у1) имеет петлю цу-.у^, (т^)) с передачей а такет входную связь

((ук,угп), (У-^у,)) с передачей = т^. Вершина <*кЛт) имеет петлю с передачей а также две входные свя-

зи ((у±,т1), (ук,уи)), передача одной из которых т1к=1, другой -

ЦП ^ -V ~

Для раскраски преобразованного ГЛС РЦФ N - го по-

рядка необходимо представить этот граф в ярусно - параллельной форме, которое осуществляется на основании утверждения 7.

Утверждение 7.Если выходной связью вершины Ук, принадлежащей ярусу 1 преобразованного ГЛС РЦФ N - го порядка, любой вершине которого соответствует опреация умножение / сложение, является связь (^¿1^), а выходной связью вершины у^, принадлежащей ярусу 8 этого графа, является связь , причем I ? 8 ,то вершина у^ принадлежит ярусу 1+1.

Если входной сеязью вершины т^ ГПО является связь

(х(п),у^), то считают, что у^ принадлежит первому ярусу графа.

Согласно определению вершинная раскраска графа является правильной, если никакие две смежные в ней вершины не имеют одного цвета.

Утверждение 8. Пусть задан прообразованный ГЛС РЦФ

И-го порядка с глубиной Н при представлении его в ярусно - параллельной форме. Если вершины графа принадлежат ярусу h, то им присваивается цвет h. Число цветов, присваиваемых пярагина;.*., равно глубине II spyuiiu - параллельной форм/ атого графа.

Для разметки вершинно - раскрашенного ГПС, любой вершине которого соответствует операция умножений/сложение, предложен алгоритм, основанный на следующем утвержден™. Утверждение 9. Пусть задан преобразованный вершинно-раскряшешшй

ГПС РЦФ N - го порядка, любой вершине которого соот-

ветствует операция умножение / сложение. Входными связями вершины этого графа с цветом Í+1 являются связи (v£, v^), причем вершинам и присвоены соответствущиа им цвета I и g так, что Г > g (g ?! f-1). Тогда связь помечается

меткой , где J = f - g.

Показано, что для преобразованного вершинно - раскрашенного

ГОС РЦФ Н - го порядка конвейерный такт 7d поступления элементов входного потока данных и выдачи элементов выходного потока данных'равен цвету h предшественника вершины, цевт которой равен единице. Преобразованный вершинно - раскрашенный ГПС РЦФ N - го порядка с размеченными связями, каждой вершине которого соответствует операция умножение / сложение, на вход которого поступает входной поток донных Сх(0), х(1),..., х(п),___ ,

x(N2)}, а на выхода формируется выходной поток данных { У(0), у(1}, ... , у(п).....У(NZ)> по определению является систолической структурой W¿=<Vd,Ed).

Найдены формулы определения полного времени формирования значений элементов выходного потока данных систолической структуры, реализующей РЦФ N - го порядка, а также Бремени поступлошя элементов входного потока данных.

Под СЕерткой систолической структуры N-ro по-

рядка будем понимать получение структуры Wi=(Vi,£i) путем последовательного замыкания смежных или несмежных ячеек Wd=(Vd,Ed) до тех пор, пока это возможно. В результате замыкания пары ячеек и у^ систолической структуры "^(Y^E^) с соответствующими т

метками 1, ш эти ячейки заменяются такой новой ячейкой с метками í и ю, что все связи, инцидентные vM, становятся инцидентны-

ми новой ячейке. Присвоение меток Гит новой ячейке означает,

что при вычислении у(п) (п=0, N2) данная ячейка выполняет операцию умножение / сложение в цикле, а также в цикле. Так как ячейка не может одновременно выполнять дав операции умножение / сложение, то метки Г,т должны быть различны:; Г * т. Отметим,что при выполнении свертки число меток,а также порядок вы-

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

Четвертая глава посвящена разработке структуры системы автоматизированного проектирования систолических структур ЦФ, а также машишю - ориентированных инженерных методик алгоритмического и структурного синтеза ЦБ.

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

Разработанная машинно - ориентированная инженерная методика структурного синтеза ВД> позволяет определить множество систолических структур, реализующих РЦФ N - го порядка, проверить правильность найденных структур и найти оптимальные из них согласно заданным критериям оптимальности при ограничениях на величину конвейерного такта приема / выдачи элементов входного / выходного потоков данных.

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

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

фильтра, вмплитудно - частотные характеристики эквивавалентных структур рассматриваемого в качестве примера канонического РЦ1 N - го порядка, акты внедрения и использования результлтпо диссертационной ргбсты.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Разработана формализованная процедура, а также библиотека алгоритмов определения эквивалентных графов потоков сигналов канонических биквадратных звеньев рекурсивных цифровых фильтров,из которых строятся эквивалентные гра^ы потоков сигналов цифровых фильтров N - го порядка. При переходе от графов потоков сигналов

Шт =(^т,Ет)} к структурам по схемам замещения построено 2А,...,15А структур, эквивалентных структуре 1А канонического биквадратного звена рекурсивного цифрового фильтра,каадая из ко-

торых имеет две задержки, четыре умножителя, а число входов сумматоров - более двух.Для структур 2А,...,15А получены передаточные функции.

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

найдены оптимальные структуры с минимальным собственным шумом

2

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

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

6. Разработана целесообразная для практического применения структура системы автоматизированного проектирования систолических структур цифровых фильтров, которая обеспечивает выполнение алгоритмического и структурного синтеза цифровых фильтров.

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

8. Разработана машшно - ориентированная инженерная методика структурного синтеза цифровых фильтров. Применение этой метода/л позволяет определить множество систолических структур капсппчзс-ких рекурсивных цифровых фильтров N - го порядка на системотехническом уровне по точности выполнения еычйслошШ и найти оптимальные из них по заданным времени выполнения вычислений, размеру структуры при ограничениях величины конвейерного такта приема / выдачи элементов входного / выходного потоков данных.

ПУБЛИКАЦИИ

По теме диссертации опубликованы сдвдухщие научные работы:

1.Петровский A.A., Черноусова Т.Г.Исследование методов синтеза систолических архитектур // Тезисы докладов VI Всесоюзной школы-семинара по распараллеливанию обработки информации. - Львов, 1987. - С.234.

2.Удалов А.И., Черноусова Т.Г. Синтез структур систолических процессоров // Тезисы докладов конференции по телекоммуникационным и вычислительным системам связи. - МоскЕа,,1993. - С. 81-82. 3.Черноусова Т.Г. К вопросу о структурах цифровых фильтров // Автоматика и вычислительная техника. - Вып.20, 1991, 0.110-117. 4.Черноусова Т.Г. Систематический подход к структурному синтезу систолических процессоров // Автоматика и вычислительная техника. - Минск, 1993. - Вып.21. - С.120-126.

Ь.ЧерноусоЕа Т.Г. Пакет прикладных программ к проектированию вычислительных структур на базе сверхбольших интегральных схем для устройств цифровой фильтрации // Тезисы докладов конференции но телекоммуникационным и вычислительным системам связи. - Москва, 1993. - С.83-84.

6.Черноусова Т.Г.Даткевич H.H. Структурный синтез свмотастиру-емых процессоров цифровой фильтрации // Тезисы докладов V Всесоюзной научно-технической конференции по однородным вычислительным системам, структурам и средам . - Москва,1991. - С.105-106.

7. Свиридович B.C., Черноусова Т.Г., Чернуха Б.Н., Бобков В.А. Контроллер прерываний К588ВН1 // Микропроцессорные средства и системы. - 1987. - N05. - С. 3-5.

8. Банников П.Д., Брибыльский A.B., Сякерсккй B.C., Черноусова Т.Г., ¡IiyxH.lt. Устройство последовательного обмена на основе универсального асинхронного приемопередатчика // Микропроцессорные средства и системы. - 1990. - N03. - С.7 - 11.

Подписано к печати 12.02.96. Формат 60 х 84/16. Печать офсетная. Объем 1,0 усл. п. л. Тираж 100 экз. Заказ 65.

ОПП МИ "ИнформсЕязьиздат", Москва, ул. Авиамоторная, 8.