Процесор швидкого перетворення хартлі дійсних послідовностей

Процесор швидкого перетворення Хартлі дійсних послідовностей, що містить з першого по шостий комутатори, перший та другий блоки оперативної пам'яті, перший суматор, перший віднімач, комплексний помножувач, перший та другий регістри, блок постійної пам'яті, два лічильники та перший тригер, перший установочний вхід якого з'єднаний з входом початкового установлення першого лічильника і є входом початкового установлення процесора, а другий установочний вхід з'єднаний з лічильним входом першого лічильника та підключений до виходу переносу другого лічильника, інформаційні виходи першого та другого ЛІЧИЛЬНИКІВ підключені ВІДПОВІДНО ДО першого та другого адресних входів блока постійної пам'яті, вихід переносу першого лічильника є виходом ознаки завершення обробки масиву даних процесора, вихід першого тригера підключений до керуючих входів першого та другого комутаторів, до перших інформаційних входів яких підключені ВІДПОВІДНО перший та другий інформаційні входи процесора, вихід першого комутатора підключений до першого входу третього та другого входу четвертого комутаторів, вихід другого комутатора підключений до першого входу четвертого та другого входу третього комутаторів, до керуючих входів яких підключений перший вихід блока постійної пам'яті, другий та третій виходи якого підключені до адресних входів ВІДПОВІДНО першого та другого блоків оперативної пам'яті, до інформаційних входів яких підключені виходи ВІДПОВІДНО третього та четвертого комутаторів, вихід першого регістра підключений до перших входів першого суматора та першого віднімача, до других входів яких підключений вихід другого регістра, який відрізняється тим, що в пристрій введені з сьомого по чотирнадцятий комутатори, третій і четвертий блоки оперативної пам'яті, другий і третій суматори, другий і третій віднімачі та другий тригер, тактовий вхід якого підключений до виходу переносу другого лічильника, вхід скидання якого підключений до входу початкового установлення процесора, вихід першого тригера підключений до інформаційного входу другого тригера та керуючих входів сьомого та восьмого комутаторів, до перших інформаційних входів яких підключені ВІДПОВІДНО третій та четвертий інформаційні входи процесора, вихід сьомого комутатора підключений до першого входу дев'ятого та другого входу десятого комутаторів, вихід восьмого комутатора підключений до першого входу десятого та другого входу дев'ятого комутаторів, керуючі входи яких підключені до першого виходу блока постійної пам'яті, четвертий та п'ятий виходи якого підключені до адресних входів ВІДПОВІДНО третього та четвертого блоків оперативної пам'яті, інформаційні входи яких підключені до виходів ВІДПОВІДНО дев'ятого та десятого комутаторів, виходи з першого по четвертий блоків оперативної пам'яті підключені ВІДПОВІДНО ДО перших, других, третіх та четвертих інформаційних входів з одинадцятого по чотирнадцятий комутаторів, до керуючих входів яких підключені ВІДПОВІДНО з шостого по дев'ятий виходи блока постійної пам'яті, виходи одинадцятого та дванадцятого комутаторів підключені до входів ВІДПОВІДНО першого та другого регістрів, виходи яких підключені до других входів ВІДПОВІДНО п'ятого та шостого комутаторів, до перших входів яких підключені виходи ВІДПОВІДНО першого суматора та першого віднімача, керуючі входи п'ятого та шостого комутаторів підключені до виходу другого тригера, виходи тринадцятого та чотирнадцятого комутаторів підключені ВІДПОВІДНО до першого та другого входів комплексного помножувача, до третього та четвертого входів якого підключені ВІДПОВІДНО десятий та одинадцятий виходи блока постійної пам'яті, виходи п'ятого та шостого комутаторів підключені до перших входів ВІДПОВІДНО другого суматора і другого віднімача та третього суматора і третього віднімача, перший та другий виходи комплексного помножувача підключені до других входів ВІДПОВІДНО другого суматора і другого віднімача та третього суматора і третього віднімача, виходи другого та третього суматорів і другого та третього віднімачів підключені до других інформаційних входів ВІДПОВІДНО першого, другого, сьомого та восьмого комутаторів і є со Ю 53217 ВІДПОВІДНО першим, другим, третім та четвертим інформаційними виходами процесора, лічильний вхід другого лічильника з'єднаний з входами запису-читання з першого по четвертий блоків опера тивної памяті, тактовими входами першого, другого регістрів та комплексного помножувача і є тактовим входом процесора Винахід належить до галузі цифрової обчислювальної техніки і може бути застосований у пристроях обчислення спектрів, згорток та кореляційних функцій Відомий пристрій для швидкого дійсного перетворення Хартлі-Фур'є (ШПХФ) [А с СССР №1569847, кл G 06 F 15/332, 1990], що містить два лічильники, два регістри, три комутатори, блок оперативної пам'яті, блок постійної пам'яті, два помножувачі та суматор-віднімач Недоліком даного пристрою є низька швидкодія, оскільки час виконання кожної базової операції алгоритму ШПХФ складає від чотирьох до шести періодів тактової частоти Найбільш близьким за технічною сутністю до пропонованого є арифметичний пристрій для виконання ШПХФ [А с СССР, №1594562, кл G 06 F 15/332, Бюл №35, 1990], що містить з першого по шостий комутатори, перший та другий блоки оперативної пам'яті, перший суматор, перший ВІДНІмач, комплексний помножувач, перший та другий регістри, блок постійної пам'яті, два лічильники та перший тригер, перший установочний вхід якого з'єднаний з входом початкової установки першого лічильника і є входом початкової установки процесора, а другий установочний вхід з'єднаний з лічильним входом першого лічильника та підключений до виходу переносу другого лічильника, інформаційні виходи першого та другого ЛІЧИЛЬНИКІВ підключені ВІДПОВІДНО до першого та другого адресних входів блока постійної пам'яті, вихід переносу першого лічильника є виходом ознаки завершення обробки масиву даних процесора, вихід першого тригера підключений до керуючих входів першого та другого комутаторів, до перших інформаційних входів яких підключені ВІДПОВІДНО перший та другий інформаційні входи процесора, вихід першого комутатора підключений до першого входу третього та другого входу четвертого комутаторів, вихід другого комутатора підключений до першого входу четвертого та другого входу третього комутаторів, до керуючих входів яких підключений перший вихід блока постійної пам'яті, другий та третій виходи якого підключені до адресних входів ВІДПОВІДНО першого та другого блоків оперативної пам'яті, до інформаційних входів яких підключені виходи ВІДПОВІДНО третього та четвертого комутаторів, вихід першого регістра підключений до перших входів першого суматора та першого віднімача, до других входів яких підключений вихід другого регістра (ШПХ) дійсних послідовностей, який реалізує базову операцію алгоритму ШПХ, котра одночасно обробляє чотири операнди, в якому за рахунок введення нових блоків та зв'язків досягається зменшення КІЛЬКОСТІ базових операцій алгоритму, внаслідок чого скорочується загальний час виконання алгоритму ШПХ, що приводить до підвищення швидкодії процесора Поставлена задача досягається за рахунок того, що в процесор швидкого перетворення Хартлі дійсних послідовностей, що містить з першого по шостий комутатори, перший та другий блоки оперативної пам'яті, перший суматор, перший ВІДНІмач, комплексний помножувач, перший та другий регістри, блок постійної пам'яті, два лічильники та перший тригер, перший установочний вхід якого з'єднаний з входом початкової установки першого лічильника і є входом початкової установки процесора, а другий установочний вхід з'єднаний з лічильним входом першого лічильника та підключений до виходу переносу другого лічильника, інформаційні виходи першого та другого ЛІЧИЛЬНИКІВ підключені ВІДПОВІДНО до першого та другого адресних входів блока постійної пам'яті, вихід переносу першого лічильника є виходом ознаки завершення обробки масиву даних процесора, вихід першого тригера підключений до керуючих входів першого та другого комутаторів, до перших інформаційних входів яких підключені ВІДПОВІДНО перший та другий інформаційні входи процесора, вихід першого комутатора підключений до першого входу третього та другого входу четвертого комутаторів, вихід другого комутатора підключений до першого входу четвертого та другого входу третього комутаторів, до керуючих входів яких підключений перший вихід блока постійної пам'яті, другий та третій виходи якого підключені до адресних входів ВІДПОВІДНО першого та другого блоків оперативної пам'яті, до інформаційних входів яких підключені виходи ВІДПОВІДНО третього та четвертого комутаторів, вихід першого регістра підключений до перших входів першого суматора та першого віднімача, до других входів яких підключений вихід другого регістра, додатково введені з сьомого по чотирнадцятий комутатори, третій і четвертий блоки оперативної пам'яті, другий і третій суматори, другий і третій віднімачі та другий тригер, тактовий вхід якого підключений до виходу переносу другого лічильника, вхід скидання якого підключений до входу початкової установки процесора, вихід першого тригера підключений до інформаційного входу другого тригера та керуючих входів сьомого та восьмого комутаторів, до перших інформаційних входів яких підключені ВІДПОВІДНО третій та четвертий інформаційні входи процесора, вихід сьомого комутатора підключений до першого входу дев'ятого та другого входу десятого комутаторів, вихід восьмо Недоліком даного пристрою є низька швидкодія, оскільки, не зважаючи нате, що час виконання базових операцій алгоритму ШПХФ складає лише один період тактової частоти, кожна базова операція одночасно обробляє лише два операнди В основу винаходу поставлено задачу створення процесора швидкого перетворення Хартлі 53217 го комутатора підключений до першого входу десятого та другого входу дев'ятого комутаторів, керуючі входи яких підключені до першого виходу блока постійної пам'яті, четвертий та п'ятий виходи якого підключені до адресних входів ВІДПОВІДНО третього та четвертого блоків оперативної пам'яті, інформаційні входи яких підключені до виходів ВІДПОВІДНО дев'ятого та десятого комутаторів, виходи з першого по четвертий блоків оперативної пам'яті підключені ВІДПОВІДНО ДО перших, других, третіх та четвертих інформаційних входів з одинадцятого по чотирнадцятий комутаторів, до керуючих входів яких підключені ВІДПОВІДНО з шостого по дев'ятий виходи блока постійної пам'яті, виходи одинадцятого та дванадцятого комутаторів підключені до входів ВІДПОВІДНО першого та другого регістрів, виходи яких підключені до других входів ВІДПОВІДНО п'ятого та шостого комутаторів, до перших входів яких підключені виходи ВІДПОВІДНО першого суматора та першого віднімача, керуючі входи п'ятого та шостого комутаторів підключені до виходу другого тригера, виходи тринадцятого та чотирнадцятого комутаторів підключені ВІДПОВІДНО до першого та другого входів комплексного помножувача, до третього та четвертого входів якого підключені ВІДПОВІДНО десятий та одинадцятий виходи блока постійної пам'яті, виходи п'ятого та шостого комутаторів підключені до перших входів ВІДПОВІДНО другого суматора і другого віднімача та третього суматора і третього віднімача, перший та другий виходи комплексного помножувача підключені до других входів ВІДПОВІДНО другого суматора і другого віднімача та третього суматора і третього віднімача, виходи другого та третього суматорів і другого та третього віднімачів підключені до других інформаційних входів ВІДПОВІДНО першого, другого, сьомого та восьмого комутаторів і є ВІДПОВІДНО першим, другим, третім та четвертим інформаційними виходами процесора, лічильний вхід другого лічильника з'єднаний з входами запису-читання з першого по четвертий блоків оперативної пам'яті, тактовими входами першого, другого регістрів та комплексного помножувача і є тактовим входом процесора Введення в пристрій з сьомого по чотирнадцятий комутаторів, третього і четвертого блоків оперативної пам'яті, другого і третього суматорів, другого і третього віднімачів та другого тригера разом з їх зв'язками дозволило реалізувати базову операцію алгоритму ІППХ, в котрій одночасно обробляється чотири операнди, і тим самим зменшити КІЛЬКІСТЬ базових операцій алгоритму, внаслідок чого скоротився загальний час виконання алгоритму ШПХ, тобто, підвищилась швидкодія процесора Пропонований пристрій, як і прототип, виконує кожну базову операцію за один період тактової частоти, але КІЛЬКІСТЬ базових операцій зменшується більш, ніж ВДВІЧІ На фіг 1 представлена блок-схема процесора ШПХ дійсних послідовностей, на фіг 2 - графсхема алгоритму ШПХ для N=16, де N - КІЛЬКІСТЬ ВІДЛІКІВ оброблюваної ПОСЛІДОВНОСТІ, на фіг 3-4 граф-схеми базових операцій алгоритму ШПХ, що виконуються ВІДПОВІДНО на першому та інших етапах алгоритму Процесор (фіг 1) містить інформаційні входи 14, вхід 5 початкової установки, тактовий вхід 6, комутатори 7-20, блоки 21-24 оперативної пам'яті, суматори 25-27, віднімачі 28-30, комплексний помножувач 3 1 , лічильники 32-33, блок постійної пам'яті 34, тригери 35-36, регістри 37-38, інформаційні виходи 39-42, вихід 43 ознаки завершення обробки масиву даних Перший установочний вхід першого тригера 35 з'єднаний з входом початкової установки першого лічильника 33, входом скидання другого лічильника 32 і є входом 5 початкової установки процесора, а другий установочний вхід з'єднаний з лічильним входом першого лічильника 33 і тактовим входом другого тригера 36 та підключений до виходу переносу другого лічильника 32 Інформаційні виходи першого та другого ЛІЧИЛЬНИКІВ 32-33 підключені ВІДПОВІДНО до першого та другого адресних входів блока 34 постійної пам'яті, вихід переносу першого лічильника 33 є виходом 43 ознаки завершення обробки масиву даних процесора Вихід першого тригера 35 підключений до інформаційного входу другого тригера 36 та керуючих входів першого 7, другого 8, сьомого 9 та восьмого 10 комутаторів, до перших інформаційних входів яких підключені ВІДПОВІДНО з першого по четвертий інформаційні входи 1-4 процесора Вихід першого комутатора 7 підключений до першого входу третього 11 та другого входу четвертого 12 комутаторів, вихід другого комутатора 8 підключений до першого входу четвертого 12 та другого входу третього 11 комутаторів, вихід сьомого комутатора 9 підключений до першого входу дев'ятого 13 та другого входу десятого 14 комутаторів, вихід восьмого комутатора 10 підключений до першого входу десятого 14 та другого входу дев'ятого 13 комутаторів Керуючі входи третього 1 1 , четвертого 12, дев'ятого 13 та десятого 14 комутаторів підключені до першого виходу блока 34 постійної пам'яті, з другого по п'ятий виходи якого підключені до адресних входів ВІДПОВІДНО З першого по четвертий блоків 21-24 оперативної пам'яті, до інформаційних входів яких підключені виходи ВІДПОВІДНО третього 1 1 , четвертого 12, дев'ятого 13 та десятого 14 комутаторів Виходи з першого по четвертий блоків 21-24 оперативної пам'яті підключені ВІДПОВІДНО до перших, других, третіх та четвертих інформаційних входів з одинадцятого по чотирнадцятий комутаторів 15-18, до керуючих входів яких підключені ВІДПОВІДНО з шостого по дев'ятий виходи блока 34 постійної пам'яті Виходи одинадцятого та дванадцятого комутаторів 15-16 підключені до входів ВІДПОВІДНО першого та другого регістрів 37-38, виходи яких підключені ВІДПОВІДНО ДО перших та других входів першого суматора 25 та першого віднімача 28 і других входів ВІДПОВІДНО п'ятого 19 та шостого 20 комутаторів, до перших входів яких підключені ВІДПОВІДНО виходи першого суматора 25 та першого віднімача 28, а до керуючих входів підключений вихід другого тригера 36 Виходи тринадцятого та чотирнадцятого комутаторів 17-18 підключені ВІДПОВІДНО до першого та другого входів комплексного помножувача 3 1 , до третього та четвертого входів якого підключені ВІДПОВІДНО десятий та одинадцятий виходи блока 34 постійної пам'яті Виходи п'ятого та шостого 53217 8 другого регістрів 37-38 та комплексного помножувача 31 у ВІДПОВІДНОСТІ з граф-схемою алгоритму, зображеною на фіг 2 На суматорах 25-27, ВІДНІмачах 28-30 та комплексному помножувачі 31 виконуються базові операції алгоритму (фіг 3-4) Комутатори 19-20 визначають необхідність участі в виконанні базових операцій суматора 25 та віднімача 28 Процесор ШПХ працює наступним чином По входу 5 поступає сигнал початкової установки, котрий встановлює в нульовий стан тригер 35, обнулює лічильник 32 та записує в лічильник 33 значення, рівне КІЛЬКОСТІ етапів алгоритму ШПХ Перед початком виконання алгоритму ШПХ відбувається етап прийому оброблюваного масиву даних На цьому етапі на керуючих входах комутаторів 7-14 присутній нульовий сигнал, внаслідок чого в кожному такті під час дії високого рівня тактового імпульсу, що поступає по тактовому входу Алгоритм ШПХ, граф-схема якого зображена 6, четвірки даних з входів 1-4 записуються в блоки на фіг 2, складається з log2N-1 етапів, на кожному 21-24 оперативної пам'яті за адресами, що постуз яких виконується N/4 базових операцій На перпають з виходів блока 34 постійної пам'яті шому етапі (Мі) виконуються базові операції, зображені на фіг 3, на інших етапах (ІУЬ.Мз) - базові Після запису в блоки 21-24 оперативної пам'яті операції, зображені на фіг 4 На фіг 2-4 прийняті останньої N/4-oi четвірки даних лічильник 32 обнутакі позначення безперервна ЛІНІЯ позначає опелюеться, а по сигналу з його виходу переносу знарацію додавання, пунктирна ЛІНІЯ - операцію віднічення лічильника 33 зменшується на одиницю, та мання, ЛІНІЯ з стрілкою на КІНЦІ - операцію множенвиходи тригерів 35 і 36 встановлюються ВІДПОВІДНО ня на значення, розташоване біля неї, в одиничний і нульовий стан, внаслідок чого комуC COS(2TIK/N), 8К 8ІП(2ТІК/М), де К - ЦІЛІ числа татори 7-10 пропускають на свої виходи інформацію з виходів суматорів 26-27 та віднімачів 29-30, а Процесор виконує алгоритм ШПХ по ітераційкомутатори 19-20 пропускають на свої виходи інному принципу На кожній ітерації, час якої склаформацію з виходів першого суматора 25 та пердає один період тактової частоти,виконується шого віднімача 28 одна базова операція Після завершення прийому масиву даних поЛічильник 32 призначений для підрахунку КІЛЬчинають виконуватись базові операції алгоритму КОСТІ виконаних базових операцій на одному етапі ШПХ (фіг 2) Операнди базових операцій зчитуалгоритму ШПХ По спаду кожного тактового імпуються з блоків 21-24 оперативної пам'яті, на адрельсу він збільшує своє значення на одиницю Лісні входи яких поступають адреси з блока 34 почильник 33 призначений для підрахунку КІЛЬКОСТІ стійної пам'яті, під час дії низького рівня тактових етапів алгоритму, що залишилось виконати, і праімпульсів, проходять з певною комутацією на вицює в режимі віднімання При переповненні лічиходи комутаторів 15-18 і по фронту тактового імльника 32, що є ознакою завершення етапу алгопульсу записуються в перший та другий регістри ритму, сигнал з його виходу переносу поступає на 37-38 та комплексний помножувач 31 Разом з лічильний вхід лічильника 33 і віднімає від його операндами базових операцій в комплексний позначення одиницю При переповненні лічильника множувач записуються вагові коефіцієнти, що по33 на його виході переносу з'являється сигнал, що ступають з виходів блока 34 постійної пам'яті На є ознакою завершення обробки масиву даних Випершому етапі алгоритму ШПХ їх значення дорівходи ЛІЧИЛЬНИКІВ 32-33 визначають адреси комірок нюють одиниці, внаслідок чого на виходах комплеблока 34 постійної пам'яті, в кожній з яких зберігаксного помножувача з'являються результати суми ються чотири адреси операндів базової операції, та різниці операндов, що записані в нього На інпо яким відбувається їх читання та запис в блоки ших етапах алгоритму ШПХ їх значення дорівню21-24 оперативної пам'яті, два вагових коефіцієнти ють нулю і одиниці або тригонометричним коефіцібазової операції, однорозрядний код керування єнтам Ск і SK В першому випадку на виходи комкомутаторами 11-14 та чотири двохрозрядних коди плексного помножувача пропускаються операнди, керування комутаторами 15-18 Комутатори 7-10 записані в нього, в другому - на виходах комплекспризначені для пропуску значень оброблюваного ного помножувача з'являються результати суми та масиву даних або вихідних операндів базових різниці добутків операндів на тригонометричні кооперацій Комутатори 11-14 забезпечують такий ефіцієнти Базові операції першого етапу алгоритпорядок запису значень оброблюваного масиву му ШПХ реалізуються на суматорах 25-27, ВІДНІданих та вихідних операндів базових операцій в мачах 28-30 та комплексному помножувачі 31 При блоки 21-24 оперативної пам'яті, що ВХІДНІ операвиконанні базових операцій інших етапів алгоритнда кожної з базових операцій наступного етапу му ШПХ суматор 25 та віднімач 28 не приймають алгоритму містяться в різних блоках 21-24 операучасть, оскільки після завершення виконання пертивної пам'яті Комутатори 15-18 забезпечують шого етапу алгоритму по сигналу з виходу перенопорядок подачі операндів базових операцій з блосу лічильника 32 вихід тригера 36 встановлюється ків 21-24 оперативної пам'яті на входи першого, комутаторів 19-20 підключені до перших входів ВІДПОВІДНО другого суматора 26 і другого віднімача 29 та третього суматора 27 і третього віднімача ЗО Перший та другий виходи комплексного помножувача 31 підключені до других входів ВІДПОВІДНО другого суматора 26 і другого віднімача 29 та третього суматора 27 і третього віднімача ЗО Виходи другого та третього суматорів 26-27 і другого та третього віднімачів 29-30 підключені до других інформаційних входів ВІДПОВІДНО першого 7, другого 8, сьомого 9 та восьмого 10 комутаторів і є ВІДПОВІДНО першим, другим, третім та четвертим інформаційними виходами 39-42 процесора Лічильний вхід другого лічильника 32 з'єднаний з входами запису-читання з першого по четвертий блоків 21-24 оперативної пам'яті, тактовими входами першого, другого регістрів 37-38 та комплексного помножувача 31 і є тактовим входом 6 процесора = K = 53217 10 На останньому етапі алгоритму ШПХ результати обчислень поступають на виходи 39-42 процесора Після виконання останньої базової операції на виході переносу лічильника 33 з'являється сигнал завершення обробки масиву даних і готовності процесора до прийому наступного масиву даних в одиничний стан, внаслідок чого комутатори 1920 пропускають на свої виходи інформацію з виходів регістрів 37-38 ВИХІДНІ операнди базових операцій проходять через комутатори 7-10, комутатори 11-14, котрі забезпечують необхідну комутацію, і записуються в блоки 21-24 оперативної пам'яті під час дії високого рівня тактових імпульсів за тими ж адресами 21 22 23 24 43 ФІГ. 1 11 53217 Фіг. 2 Фіг. З Фіг. 4 ТОВ "Міжнародний науковий комітет" вул Артема, 77, м Київ, 04050, Україна (044)236-47-24 12