Пристрій для обчислення швидкого трансформування фур’є

1. Пристрій для обчислення швидкого трансформування Фур'є, що містить тактовий вхід, вхід величини розміру масиву, інформаційний вхід, інформаційний вихід, арифметичний вузол, два мультиплексори, який відрізняється тим, ідо додатково містить перший формувач адрес, другий формувач адрес, генератор коефіцієнтів, пам'ять коефіцієнтів, першу пам'ять, другу пам'ять, блок накопичувана добутків, третя пам'ять, причому тактовий вхід і вхід величини розміру масиву з'єднані з першим І другим формувачами адрес та генератором коефіцієнтів. вихід якого є входом даних пам'яті коефіцієнтів, адресним входом якої є другий вихід другого формувача адрес, перший вихід якого з'єднаний з входом першого формувала адрес, перший і другий адресні виходи якого з'єднані ВІДПОВІДНО З першою і другою пам'яттю, входом даних яких є інформаційний вхід, виходи даних першої і другої пам'яті з'єднані з входами першого і другого мультиплексора, вихід першого мультиплексора з'єднаний з входом арифметичного вузла, вихід якого подається до входів першої і другої пам'яті, третій вихід першого формувача з'єднаний з входами вибору першого і другого мультиплексорів, вихід другого мультиплексора з'єднаний з першим входом блока накопичувана добутків, другим входом якого є вихід даних пам'яті коефіцієнтів, вихід блоку накопичувача добутків з'єднаний з входами даних третьої' пам'яті, адресним входом яко) є другий вихід другого формувача адрес, виходом даних третьої пам'яті є Інформаційний вихід 2 Пристрій по п. 1, відрізняється тим, що перший формувач адрес містить схему керування, чотири лічильники, два мультиплексори, причому схема керування, виходи якої є входами керування ВІДПОВІДНО чотирьох лічильників, двох мультиплексорів та третім виходом першого формувача адрес, тактовий вхід з'єднаний з тактовими входами чотирьох ЛІЧИЛЬНИКІВ, ВИХОДИ яких з'єднані з входами двох мультиплексорів, третім входом яких є перший адресний вихід другого формувача адрес. виходи двох мультиплексорів є ВІДПОВІДНО першими і другими адресними виходами першого формувача адрес. З Пристрій по п. 1, відрізняється тим, що другий формувач адрес містить схему вибору, формувач непарних елементів, два формувачі парних елементів, причому тактовий вхід і вхід величини розміру масиву з'єднані з входами формувачів та входами схеми вибору, виходи якої з'єднані з входами керування формувачів, виходи якого є ВІДПОВІДНО першими і другими адресними виходами другого формувача адрес 4. Пристрій по п 3, відрізняється тим, що формувач парних елементів містить блок пам'яті, запам'ятовуючий пристрій, чотири лічильники, дві схеми порівняння, елемент &, причому вхід величини розміру масиву є першим адресним входом блоку пам'яті, другим адресним входом якого є вихід четвертого лічильника, який є також другим входом другої схеми порівняння, вихід якої з'єднаний з другим входом елемента &, вихід якого з'єднаний з другим входом четвертого лічильника, перший вхід якого з'єднаний з виходом схеми порівняння, ВИХІД якої є також першим входом елемента & та входом третього лічильника, вихід якого з'єднаний з другим адресним входом запам'ятовуючого пристрою та інформаційним входом першого лічильника, тактовим входом якого є тактовий вхід, вихід першого лічильника з'єднаний з другим адресним входом блоку пам'яті та інформаційним входом другого лічильника, вихід якого є першим адресним входом запам'ятовуючого пристрою та другим входом першої схеми порівняння, першим входом якої є третій вихід блоку пам'яті, другий вихід якої з'єднаний з першим входом другої схеми порівняння, третій вихід блоку пам'яті є першим адресним виходом, а вихід запам'ятовуючого пристрою є другим адресним виходом формувача парних елементів, вихід схеми вибору другого формувача адрес з'єднаний з входами керування блоку пам'яті і запам'ятовуючого пристрою. «5Г (О СО 34614 Винахід відноситься до обчислювальної техніки і може бути використаний для аналізаторів спектру І цифрових фільтрів, які обчислюють коефіцієнти Фур'є в реальному масштабі часу. Відомий пристрій для реалізації швидкого трансформування Фур'є, який містить блок пам'яті, з'єднаний з входом операндів арифметичного блоку, блок постійної пам'яті з'єднаний з входом коефіцієнтів арифметичного блоку, вихід якого з'єднаний з входом блоку пам'яті І є інформаційним виходом пристрою, блок керування, тактовий вхід пристрою ІА. с. №123Э166А1 (СССР), G06F15/332, • Устройство для реализации быстрого преобразования Фурье. / А.Н. Карташевич и МС. Курлйнд / Заявл. 04.01.84, опубл. 23.05 86 Бюп №191 Однак, даний пристрій для виконання швидкого трансформування Фур'є проводить обчислення однієї Ітерації при загальному числі операндів, що відповідають конкретному значенню N=2n, що потребує нарощення апаратних пристроїв для виконання всіх ітерацій та звужує функціональні можливості пристрою, виконуючи швидке трансформування Фур'є числа операндів тільки рівних ц ш т степені двійки. Найбільш близьким по технічній суті є . пристрій для обчислення швидкого трансформування Фур'є, який містить тактовий вхід, вхід величини розміру масиву, інформаційний вхід, арифметичний вузол, два мультиплексори [А.с. № 1697086А1 (СССР). G06F 15/332, Устройство для вычисления быстрого преобразования Фурье. / А С. Дыкун, Ю М. Захарко, А А. Мельник / Заявл. 23 10.89, опубл. 07 12.91 Бюл. № 45]. Однак, даний пристрій для виконання швидкого трансформування Фур'є проводить обчислення за допомогою л обчислювальних блоків, кожен з яких виконує певну ітерацію для конкретного значення, рівного цілій степені двійки N=2n (n=!og2N, N - максимальна розмірність перетворення), що потребує додаткових апаратних затрат для виконання всіх ітерацій та звужує функціональні можливості пристрою, виконуючи швидке трансформування Фур'є числа операндів тільки рівних ЦІЛІЙ степені двійки., В основу винаходу поставлене завдання створити пристрій для обчислення швидкого трансформування Фур'є, у якому внаслідок введення нових блоків та взаємозв'язків дозволили б на базі організації формувачами адрес показників степені експоненціального базису з доповненням матрицями знаків проводити обчислення трансформування Фур'є послідовностей довільного обсягу і тим самим забезпечити зв'язок на основі співвідношення невизначенності Af At г с між роздільними характеристиками по частоті і по часу та скоротити апаратні затрати. Поставлене завдання вирішується тим, що в пристрій для обчислення швидкого трансформування Фур'є, що містить тактовий вхід, вхід величини розміру масиву, інформаційний вхід, інформаційний вихід, арифметичний вузол, два мультиплексори, згідне винаходу, містить перший формувач адрес, другий формувач адрес, генератор коефіцієнтів, пам'ять коефіцієнтів, першу пам'ять, друг/ пам'ять, блок накопичу вача добутків, третя пам'ять, причому тактовий вхід і вхід величини розміру масиву з'єднані э першим і другим формувачами адрес та генератором коефіцієнтів, вихід якого с входом даних пам'яті коефіцієнтів, адресним входом якої є другий вихід другого формувача адрес, перший вихід якого з'єднаний з входом першого формувача адрес, перший і другий адресні виходи якого з'єднані відповідно з першою і другою пам'яттю, входом даних яких є інформаційний вхід, виходи даних першої і другої пам'яті з'єднані з входами першого І другого мультиплексора, вихід першого мультиплексора з'єднаний э входом арифметичного вузла, вихід якого подається до входів першої і другої пам'яті, третій вихід першого формувача з'єднаний з входами вибору першого і другого мультиплексорів, вихід другого мультиплексора з'єднаний з першим входом блока накопичувача добутків, другим входом якого є вихід даних пам'яті коефіцієнтів, вихід блоку накопичувача добутків з'єднаний з входами даних третьої пам'яті, адресним входом якої є другий вихід другого формувача адрес, виходом даних третьої пам'яті є інформаційний вихід. Введення в пристрій для обчислення швидкого трансформування Фур'с першого формувача адрес, другого формувача адрес, генератора коефіцієнтів, пам'яті коефіцієнтів, першої пам'яті, другої пам'яті, блоку накопичувача добутків, третьої пам'яті дозволило на базі організації формувачами адрес показників степені експоненціального базису з доповненням матрицями знаків проводити обчислення трансформування Фур'є послідовностей довільного обсягу і тим самим забезпечити зв'язок на основі співвідношення невизначенності АІ At > с між роздільчими характеристиками по частоті і по часу. Поставлене завдання досягається також тим, що перший формувач адрес містить схему керування, чотири лічильники, два мультиплексори, причому схема керування, виходи , якої є входами керування відповідно чотирьох лічильників, двох мультиплексорів та третім виходом першого формувача адрес, тактовий вхід з'єднаний з тактовими входами чотирьох лічильників, виходи яких з'єднані з входами двох мультиплексорів, третім входом яких є перший адресний вихід другого формувача адрес, виходи двох мультиплексорів с відповідно першими і другими адресними виходами першого формувача адрес. Введення в перший формувач адрес схеми керування, чотирьох лічильників, двох мультиплексорів дозволило провести формування адрес для зчитування і запису операндів при виконанні етапів об'єднань для обчислення швидкого трансформування Фур'є послідовностей довільного обсягу. Поставлене завдання вирішується тим, що другий формувач адрес містить схему вибору, формувач непарних елементів, два формувачі парних елементів, причому тактовий вхід і вхід величини розміру масиву з'єднані з входами формувачів та входами схеми вибору, виходи якої з'єднані з входами керування формувачів, виходи якого є відповідно першими і другими адресними виходами другого формувача адрес. 34614 Введення в другий формувач адрес схеми вибору, формувача непарних елементів, двох формувачів парних елементів дозволило провести формування адрес для зчитування і запису операндів при виконанні накопичення добутків для обчислення швидкого трансформування Фур'є послідовностей довільного обсягу. Поставлене завдання вирішується тим, що формувач парних елементів містить блок пам'яті, запам'ятовуючий пристрій, чотири лічильники, дві схеми порівняння, елемент &, причому вхід величини розміру масиву є першим адресним входом блоку пам'яті, другим адресним входом якого є вихід четвертого лічильника, який є також другим входом другої схеми порівняння, вихід якої з'єднаний з другим входом елемента &, вихід якого з'єднаний з другим входом четвертого лічильника, перший вхід якого з'єднаний з виходом схеми порівняння, вихід якої є також першим входом елемента & та входом третього лічильника, вихід якого з'єднаний з другим адресним входом запам'ятовуючого пристрою та інформаційним входом першого лічильника, тактовим входом якого є тактовий вхід, вихід першого лічильника з'єднаний з другим адресним входом блоку пам'яті та інформаційним входом другого лічильника, вихід якого є першим адресним входом запам'ятовуючого пристрою та другим входом першої схеми порівняння, першим входом якої є третій вихід блоку пам'яті, другий вихід якої з'єднаний з першим входом другої' схеми порівняння, третій вихід блоку пам'яті є першим адресним виходом, а вихід запам'ятовуючого пристрою є другим адресним виходом формувача парних елементів, вихід схеми вибору другого формувача адрес з'єднаний з входами керування блоку пам'яті і запам'ятовуючого пристрою. Введення в формувач парних елементів блоку пам'яті, запам'ятовуючого пристрою, чотирьох лічильників, двох схем порівняння, елементу & дозволило провести формування адрес для зчитування і запису операндів при виконанні накопичення добутків для обчислення швидкого трансформування Фур'є послідовностей, які містять парну кількість елементів. На фіг. 1 подано структурну схему пристрою для обчислення швидкого трансформування Фур'є; на фіг. 2 - структурна схема першого формувача адрес; на фіг 3 - структурну схему другого формувача адрес; на фіг 4 - структурну схему формувача адресів для парних елементів Пристрій містить тактовий вхід 1. вхід величини розміру масиву 2, інформаційний вхід З, перший формувач адрес 4, другий формувач адрес 5, генератор коефіцієнтів 6, пам'ять коефіцієнтів 7, першу пам'ять 8, перший мультиплексор 9, арифметичний вузол 10, другу пам'ять 11, другий мультиплексор 12, блок накопичувача добутків 13, третя пам'ять 14, інформаційний вихід 15. причому тактовий вхід 1 І вхід 2 з'єднані з першим і другим формувачами адрес 4, 5 та генератором коефіцієнтів б, вихід якого є входом даних пам'яті коефіцієнтів 7, адресним входом якої є другий вихід другого формувача адрес 5, перший вихід якого з'єднаний з входом першого формувача адрес 4, перший і другий адресні виходи якого з'єднані відповідно з першою і другою пам"яттю 8 11, входом даних яких є інформаційний вхід 3, виходи даних першої і другої пам'вті 8, 11 з'єднані з входами першого і другого мультиплексора 9, 12, вихід > першого мультиплексора 9 з'єднаний э іходом арифметичного вузла 10. вихід якого подається до входів першої і другої пам'яті 8. 11. третій вихід першого формувача 4 з'єднаний з входами вибору першого і другого мультиплексорів 9, 12, вихід другого мультиплексора 12 з'єднаний з першим входом блока накопичувача добутків 13. другим входом якого є вихід даних пам'яті коефіцієнтів 7. вихід блоку накопичувача добутків 13 з'єднаний з входами даних третьої пам'яті 14. адресним входом якої є другий вихід другого формувача адрес 5, виходом даних третьої пам'яті 14 є інформаційний вихід 15 Перший формувач адрес 4 містить схему керування 16; чотири лічильники 17, 18, 19, 20, два мультиплексори 21. 22. причому схему керуваннй 16. виходи якої є входами керування відповідно чотирьох лічильників 17, 18, 19, 20, двох мультиплексорів 21, 22 та третім виходом першого формувача адрес 4, тактовий вхід 1 з'єднаний з тактовими входами чотирьох лічильників 17, 18, 19, 20, виходи яких з'єднані з входами двох мультиплексорів 21. 22, третім входом яких є перший адресний вихід другого формувача адрес 5, виходи мультиплексорів 21, 22 є відповідно першими і другими адресними виходами першого формувача адрес 4. Другий формувач адрес 5 містить схему вибору 23, формувач непарних елементів 24, два формувачі парних елементів 25. 26, причому тактовий вхід 1 і вхід 2 з'єднані з входами формуаачів'24. 25. 26 та входами схеми вибору 23. виходи якої з'єднані з входами керування формувачів 24, 25, 26, виходи якого є відповідно першими і другими адресними виходами другого формувача адрес 5 Формувач парних елементів 25, 26 містить блок пам'яті 27, запам'ятовуючий пристрій 28, чотири лічильники - 29, ЗО, 33, 34. дві схеми порівняння 31, 32, елемент & 35, причому вхід 2 розмірності трансформування є першим адресним входом блоку пам'яті 27, другим адресним входом якого є вихід четвертого лічильника 34, який також є другим входом другої схеми порівняння 32, вихід якої з'єднаний з другим входом елемента & 35, вихід якого з'єднаний з другим входом четвертого лічильника 34, перший вхід якого з'єднаний з виходом схеми порівняння 31, вихід якої с також першим входом елемента & 35 та входом третього лічильника 33, вихід якого з'єднаний з другим адресним входом запам'ятовуючого пристрою 28 та інформаційним входом першого лічильника 29, тактовим входом якого є тактовий вхід 1, вихід першого лічильника 29 з'єднаний з другим адресним входом блоку пам'яті 27 та інформаційним входом другого лічильника ЗО. вихід якого є першим адресним входом запам'ятовуючого пристрою 28 та другим входом першої схеми порівняння 31, першим входом якої є третій вихід блоку пам'яті 27, другий вихід якої з'єднаний з першим входом другої схеми порівняння 32, третій вихід блоку пам'яті 27 є першим адресним виходом, а вихід запам'ятовуючого 34614 пристрою 29 с другим адресним виходом формувача парних елементів 25, 26, вихід схеми вибору 23 другого формувача адрес 5 з'єднаний з в*одами керування блоку пам'яті 27 і запам'ятовуючого присгрою 28 Пристрій працює наступним чином. Робота пристрою базується на організації формувачами адрес, які використовують показники степені експоненціального базису з доповненням матрицями знаків для обчислення трансформування Фур'є послідовностей довільного обсягу. На початку трансформування перший формувач адрес 4 виконує адресацію вводу з Інформаційного входу 3 вхідних значень х[і], і=0 (1) N-'1. і далі проводить формування адрес для зчитування І запису значень в процесі виконання етапів об'єднань в першу і другу пам'ять 8, 11. Проведення об'єднань виконується без заміщення за допомогою першої і другої пам'яті 8, 11, в яких зберігаються результати двох останніх етапів об'єднання. Так як при об'єднанні над одними і тими ж операндами виконується операція додавання та віднімання, то використовується парна кількість пристроїв додавання/віднімання в арифметичному вузлі 10 і рівномірно поділена на сегменти перша і друга пам'яті 8, 11 з одночасним доступом до них для зчитування операндів. Розмірність першої' та другої пам'яті визначається найбільшою величиною N розмірності ДТФ. Виконання етапів об'єднань проводиться за адресуванням кожного сегменту адресного простору першої і другої пам'яті 8, 11 з метою чіткого розміщення результатів об'єднань В першому формувачі адрес 4 фіг. 2 входить набір лічильників 17, 18, 19, 20 з інкрементним/декрементним режимом роботи та з попереднім встановленням за допомогою схем керування 16. Виходи лічильників 17, 18 через мультиплексори 21, 22 на першому адресному виході адресують для зчитування і запису значення об'єднань з першої і другої пам'яті 8, 11, відповідно. На початку роботи лічильник Л1 виконує адресування Адр1 запису вхідних значень xjil, i=0 (1) N-1. в першу пам'ять 8, де перша половина х[і] розміщена в частині пам'яті (0, N/2-1) і друга в (N/2, N-1). Проведення етапів об'єднань зобумовлює організацію адресування запису в кожний сегмент адресного простору пам'яті 8, 11 після виконання половини об'єднань, що створює можливість одночасного читання операндів для виконання наступного етапу об'єднань. В другий формувач адрес 5 структурної схеми обчислювача ШТФ входять за фіг. З формувач адресів для непарних елементів 24 розмірності трансформування, формувачі адресів для парних елементів 25, 26 розмірності трансформування, який організовано окремо для циклю підстановок э парними формувач 26 І непарними формувач 26 елементами,- схема . вибору 23 одного з формувачів адреси. Другий формувач адрес 5 приймає участь в формуванні послідовності адрес для зчитування об'єднаних значень з першої і другої пам'яті 8, 11 і значень тригонометричних функцій з пам'яті коефіцієнтів 7, Другий адресний вихід другого формувача адрес 5 через мультиплексор 21, 22 в першому формувачі адрес 4 служить для зчиту вання спеціально об'єднаних кратних значень першої або другої пам'яті 8, 11 в блок накопичувача добутків 13, який визначається першою лінійкою першого адресу І кожен раз синхронно відтворюється при зсуві циклічно вліво сформованої наступної лінійки першого адресу. Розглянем процес генерації адрес в залежності від N розмірності трансформування в структурній схемі другого формувача адрес 5 фіг. 3. до якого входять набір формувачів 24, 25, 26. Для парних N - розмірності трансформування ДТФ, формування адрес в другому формувачі адрес 5 для зчитування значень тригонометричних функцій з пам'яті коефіцієнтів 7 проводиться за структурною схемою формувача парних елементів 25, 26 фіг. 4 Аналіз циклового розкладу підстановки Р. побудований на основі матриці показників степені експоненціального базису, показує, що циклічний розклад підстановки Р містить окремі цикли з непарними, парними, кратними N елементами. Кількість циклів підстановок, як з непарними так і з парними елементами може бути різною. Тому в блоці пам'яті 27 циклічних розкладів підстановок Р необхідно записувати дані про кількість елементів в циклі підстановки к (третій вихід блоку пам'яті) і кількість циклів підстановки s (другий вихід блоку пам'яті) в цикловому розкладі Р. Доцільно блоки пам'яті циклічних розкладів підстановок Р з записаними даними про кількість елементів в циклі підстановки k і кількість циклів підстановки s організовувати окремо для циклів підстановок з парними (формувач 25) і непарними елементами {формувач 26). Враховується також, що для парних лінійок адрес, цикли підстановки тільки з парними елементами, використовується вищий етап об'єднань в порівнянні з непарними лінійками адрес. Використанням циклічності зліва на основі циклу підстановки формується лінійка адрес для зчитування значень тригонометричних функцій. В початковий момент, формування першої лінійки адресів для виконання добутків в блоці накопичувана добутків 13 проводиться за допомогою блоку пам'яті 27. Дані елементів циклу підстановки z\ послідовно виводяться з блоку пам'яті 27 на перший адресний вихід. Адресування блоку пам'яті 27 включає N розмірність трансформування (перший адресний вхід), s' кількість циклів підстановок (другий адресний вхід), вихід першого лічильника 29 (третій адресний вхід). Лічильник 29 послідовно виводить з 27 елементи циклу підстановки і проводить циклічний зсув прф формуванні наступної лінійки адрес. Величина циклічного зсуву визначається І встановлюється в 29 з виходу третього лічильника 33, який за допомогою другого лічильника ЗО І першої схеми порівняння 31 збільшує своє значення на одиницю при завершенні формування лінійки адрес з К елементів. Однак, встановлення величини циклічного зсуву в 29 відбувається, коли виконається формування вихідної адреси зі всією кількістю циклів підстановок s, які визначаються четвертим лічильником 34. Лічильник 34 після завершення формування і-го циклу підстановки змінює адресу s'=i+1 в 27 для зчитування наступного циклу підстановки. Після завершення формування всіх s циклів підстановок, аналіз проводиться за допо 34614 могою елементів 34, 32, 35 Елемент & 35 встановлює величину циклічного зсуву на виході лічильника 29 через вихід лічильника 33 на вхід 29. Починається виведення на адресному виході наступної зі зсувом на один елемент вліво лінійки адрес Другий адресний вихід формувача парних елементів 25, 26 є виходом запам'ятовуючого пристрою 28 і служить для зчитування об'єднаних значень з першої і другої пам'яті 8, 11 в блок накопичення добутків 13. в запам'ятовуючий пристрій 28 записується за допомогою виходів лічильників ЗО, 33, початкова лінійка адрес і кожен раз синхронно відтворюється при формуванні наступної зі зсувом на один елемент вліво лінійки адрес. Таким чином, в другий формувач адрес 5 входять фіг. З крім формувача адресів для непарних елементів 24 розмірності трансформування, формувач адресів для парних елементів розмірності трансформування, який організовано окремо для циклів підстановок з парними 25 і непарними 26 елементами, які за своєю структурною схемою аналогічні. В яких блок пам'яті 27 послідовно виводить, як парні так і непарні, записані кратні елементи циклу підстановки і проводить циклічний зсув при формуванні наступної лінійки адрес. Однак, встановлення величини циклічного зсуву відбудеться, коли виконається формування адрес Адр для кратних елементів зі всією кількістю циклів підстановок s, які складають половину періоду для даного кратного елемента. Після завершення формування і-го циклу підстановки змінюється адреса s'=i+1 в блоці пам'яті 27 для зчитування наступного циклу підстановки. Після завершення формування всіх s циклів підстановок, проводиться циклічний зсув. Починається виведення на першому адресному виході другого формувача адрес 5 наступної зі і 3 зсувом на один елемент вліво ЛІНІЙКИ адрес кратних елементів Пам'ять коефіцієнтів 7, в якій зберігаються значення синусу, косинусу та значення їхніх знаків. Визначення значень експоненціального базису для конкретного N розмірності трансформування виконується за допомогою генератора коефіцієнтів 6. Для заданого N визначаються знаки Zs, Zc за формулами + 1,якщо v(r,k)