Процесор швидкого перетворення фур’є

1. Процесор швидкого перетворення Фур'є, що містить блок оперативної пам'яті, блок зберігання вагових коефіцієнтів, формувач адреси операндів, формувач адреси вагових коефіцієнтів, блок виконання базових операцій, блок підсумування операндів, блок керування зсувами, блок керування операціями та лічильник номера ітерації, входи якого з'єднані відповідно з першим і дев'ятим виходами, а вихід - з другим входом блоку керування операціями, перший вхід якого є входом запуску процесора, перший і другий входи блоку оперативної пам'яті з'єднані з виходами відповідно до блоку підсумування операндів і блоку виконання базових операцій, перший і другий входи якого з'єднані з першим виходом блоку оперативної пам'яті та виходом блоку зберігання вагових коефіцієнтів, виходи формувача адреси операндів з'єднані відповідно з другим і третім керуючими входами блоку оперативної пам'яті, шостий, сьомий, восьмий виходи блоку керування операціями з'єднані відповідно з другим, третім і четвертим входами формувачів адреси операндів і вагових коефіцієнтів, перші входи яких підключені до другого ви ходу блоку керування операціями, який із відрізняється тим, що додатково введений блок адресації вхідних операндів, вихід якого з'єднано з третім керуючим входом блоку оперативної пам'яті, третій інформаційний вхід якого є входом процесора, A (54) ПРОЦЕСОР ШВИДКОГО ПЕРЕТВОРЕННЯ ФУР'Є 36435 лення проводиться у форматі плаваючої коми з використанням лише одного множителя. Більш високу швидкодію має пристрій для обчислення коефіцієнтів Фур'є, що містить чотири блоки множення, шість підсумуючих блоків, шість вхідних регістрів, два проміжних регістри, чотири блоки зсуву та блок керування зсувами (Волошин Р.Д., Востриковець Н.С., Коротич Н.І. Пристрій для обчислення коефіцієнтів Фур'є. А. с. СРСР № 736112). Недоліком даного пристрою є мала точність під час використання його у процесорах швидкого перетворення Фур'є, обробляючих масиви двійкових чисел з фіксованою комою. Низька точність результату пов'язана з виникненням під час зсуву операндів і швидкому накопиченні систематичних помилок заокруглення, що порушують парність і непарність відповідно до дійсної та уявної частин спектрів. Даний недолік усуває пристрій для обчислення коефіцієнтів Фур'є, в якому на відміну від відомого введено блоки заокруглення, що виключають систематичні помилки після зсуву операндів (Миронов І.Л. Пристрій для обчислення коефіцієнтів Фур'є. Патент України № 23056А від 30.06.98 р). Відомий процесор швидкого перетворення Фур'є, що містить М/2 комутаторів, причому ви хід і-го (і=1,3,5…) арифметичного блоку поєднаний з виходом к-го (к=М +1/2) комутатора, вихід якого підключений до входу j-го арифметичного блоку, вихід m-го (m=2,4,6...) арифметичного блоку поєднаний з другим входом 1-го (1=m/2) множителя, вихід якого поєднаний з входом (m+1)-го арифметичного блоку, причому керуючі входи М/2 комутаторів поєднані з виходом лічильника, при цьому в і-ому (і=1,М) арифметичному блоці другий вихід вхідного комутатора підключений до входів суматора та віднімача (Бахтіаров Г.Д., Орлов Ю.Н. Процесор швидкого перетворення Фур'є. А. с. СРСР № 928362). Недоліком даного процесора є великі апаратурні витраті. Найближчим до винаходу є процесор швидкого перетворення Фур'є, що містить блок оперативної пам'яті, блок зберігання вагових коефіцієнтів, формувач адреси операндів, формувач адреси вагових коефіцієнтів, блок виконання базових операцій, блок підсумування операндів, блок керування зсувами, блок керування операціями, лічильник номера ітерації та лічильник із зворотним переносом, причому інформаційним входом і входом запуску процесора є відповідно інформаційний вхід блоку підсумування операндів і перший вхід блоку керування операціями, десятий вихід якого є виходом ознаки закінчення роботи процесора, другий інформаційний вхід і перший вихід блоку оперативної пам'яті з'єднані відповідно з виходом і першим входом блоку виконання базових операцій, другий вхід якого з'єднаний з виходом блоку зберігання вагових коефіцієнтів, керyючий вхід якого з'єднаний з виходом формувача адреси вагових коефіцієнтів, перший і другий виходи формувача адреси операндів з'єднаний відповідно з другим і третім керуючими входами блоку оперативної пам'яті, перший керуючий вхід якого поєднаний з виходом лічильника із зворотним переносом, перший і дев'ятий ви ходи блоку керування операціями з'єднані зі входами лічильника номера ітерації, вихід якого з'єднаний з другим входом блоку керування операціями, другий, третій і п'ятий виходи якого з'єднані відповідно з першим, другим і третім керуючими входами блоку підсумування операндів, другий і перший виходи якого з'єднані відповідно з першим керуючим входом блоку керування зсувами та першим інформаційним входом блоку оперативної пам'яті, перший і другий входи лічильника із зворотним переносом поєднані відповідно з другим і четвертим виходами блоку керування oпqэaцiями, шостий, сьомий і восьмий виходи якого з'єднані відповідно з другим, третім і четвертим входами формувачів адреси операндів і вагових коефіцієнтів, перші входи яких підключені до другого виходу блоку керyвaння операціями, восьмий вихід якого підключений до другого керуючого входу блоку керyвaння зсувами, вихід якого з'єднаний з третім входом блоку виконання базових операцій, вихід якого підключений до інформаційного входу блоку керування зсувами. Блок виконання базових операцій містить R=2r; r=1,2… арифметичних пристроїв, кожний з яких одночасно обробляє два операнди за формулою базової операції алгоритму ШПФ (Миронов І.Я. Пристрій для виконання швидкого перетворення Фур'є. Патент України № 22172А від 30.06.98) - прототип. Недоліком даного процесора є відсутність апаратурних засобів для обчислення двомірного перeтвopeння Фур'є. В основу винаходу поставлено задачу забезпечення умов обчислення двомірного газотворення Фур'є при високоточній цілочисельній обробці сигналів, для чого вводиться блок адресації вхідних операндів. Для вирішення цієї задачі у процесор швидкого перетвopeння Фур'є, що містить блок оперативної пам'яті, блок зберігання вагових коефіцієнтів, формувач адреси операндів, формувач адреси вагових коефіцієнтів, блок виконання базових операцій, блок підсумування операндів, блок керування зсувами, блок керування операціями і лічильник номера ітерації, входи та ви хід якого з'єднані з першим і дев'ятим виходами та з другим входом відповідно до блоку керування операціями, перший вхід якого є входом запуску процесора, перший і другий інформаційні входи блоку оперативної пам'яті з'єднані з виходами відповідно до блоку підсумування операндів і блоку виконання базових операцій, першій і другий входи якого з'єднані з першим виходом блоку оперативної пам'яті та виходом блоку зберігання вагових коефіцієнтів, керуючий вхід якого з'єднаний з виходом формувача адреси вагових коефіцієнтів, виходи формувача адреси операндів з'єднані з другим і третім керуючими входами блоку опертивної пам'яті, шостий, сьомий і восьмий виходи блоку керування операціями з'єднані відповідно з другими, третіми та четвертими входами формувачів адреси операндів і вагови х коефіцієнтів, перші входи яких підключені до другого виходу блоку керування операціями, додатково введено блок адресації вхідних операндів, вихід якого з'єднаний з третім керуючим входом блоку оперативної пам'яті, третій інформаційний вхід якого є інформаційним входом процесора, другий і третій виходи блоку керування 2 36435 операціями з'єднані з керуючими входами блоку адресації вхідних операндів і блоку керування зсувами, інформаційний вхід якого підключений до інформаційного входу процесора, вихід блоку адресації вхідних операндів з'єднаний з першим керуючим входом блоку оперативної пам'яті, другий вихід якого з'єднаний з першим інформаційним входом блоку підсумування операндів, другий інформаційний вхід якого з'єднаний з виходом блоку керування зсувами, керуючі входи блоку підсумування операндів з'єднані з четвертим і п'ятим виходами блоку керування операндів. Блок адресації вхідних операндів містить зсувач, регістр кількості зсувів, лічильник з прямим переносом, лічильник із зворотним переносом, комутатор і схему керування циклами, входи якої з'єднані з другим і третім виходами блоку керування операціями, вхід регістру кількості зсувів з'єднаний з першими входами скиду лічильників з прямим і зворотним переносом, керуючим входом комутатора та підключений до першого входу схеми керування циклами, другий вхід якої з'єднаний з керуючим входом зсувача, ви хід якого з'єднаний з першим керуючим входом блоку оперативної нам'я ти, а перший, другий і третій інформаційні входи з'єднані з виходами відповідно до регістра кількості зсувів, лічильника з прямим переносом і лічильника із зворотним переносом, другий вхід скиду якого з'єднаний з другим виходом комутатора, перший вихід якого з'єднаний з другим входом скиду лічильника з прямим переносом, перший, другий і третій виходи схеми керування циклами з'єднані з інформаційними входами відповідно до лічильника з прямим переносом, комутатора і лічильника із зворотним переносом. Відповідний аналіз з прототипом показує, що вказаний процесор швидкого перетворення Фур'є відрізняється тим, що блок адресації вхідних операндів забезпечує заданий порядок розміщення масивів цілочисельних даних оперативної пам'яті з виробленням умов масштабування даних, що сумуються, що забезпечує високу точність цілочисельних підрахувань із збереженням високої швидкодії процесора. Таким чином, вказаний процесор відповідає критерію винаходу "новизна". Порівняння вказаного рішення не тільки з прототипом, але й з іншими технічними рішеннями у даній галузі техніки, не дозволило виявити в них ознаки, що відрізняють вказане рішення від прототипу, що дозволяє зробити висновок про відповідність критерію ''суттєві відмінності''. Винахід пояснюється кресленнями фіг. 1, 2, на яких представлені функціональні схеми процесора швидкого перетворення Фур'є та його блоку адресації вхідних операндів. На фіг. 3 - гра фік значень вагових коефіцієнтів, фіг. 4 - часова діаграма роботи процесора, фіг. 5 - ілюстрація порядкової реалізації алгоритму двомірного перетворення Фур'є, фіг. 6 - функціональна схема блоку підсумування операндів. Процесор фіг. 1 містить: 1. Блок адресації вхідних операндів. 2. Блок керування зсувами. 3. Блок підсумування операндів. 4. Блок оперативної пам'яті. 5. Блок виконання базових операцій. 6. Блок зберігання вагових коефіцієнтів. 7. Формувач адреси операндів. 8. Формувач адреси вагових коефіцієнтів. 9. Блок керування операціями. 10. Лічильник номера ітерації. Блок 1 адресації вхідних операндів фіг. 2 містить: 11.Зсувач. 12. Регістр кількості зсувів. 13. Лічильник з прямим переносом. 14. Комутатор. 15. Лічильник із зворотним переносом. 16. Схема керування циклами. Вихід блоку 1 адресації вхідних операндів (фіг. 1) з'єднаний з першим керуючим входом блоку 4 оперативної пам'яті, перший інформаційний вхід якого є інформаційним входом процесора, входом запуску та виходом ознаки закінчення роботи процесора є відповідно перший вхід і десятий вихід блоку 9 керування операціями, другий і третій виходи якого з'єднані з керуючими входами блоку 1 адресації вхідних операндів і блоку 2 керування зсувами, інформаційний вхід якого підключений до першого інформаційного входу блоку 4 оперативної пам'яті, а вихід з'єднаний з першим інформаційним входом блоку 3 підсумування операндів, другий інформаційний вхід і вихід з'єднані відповідно з другим виходом і третім інформаційним входом блоку 4 оперативної пам'яті, а керуючі входи блоку 3 поєднані з четвертим і п'ятим виходами блоку 9 керування операціями, перший і дев'ятий виходи якого з'єднані зі входами лічильника 10 номера ітерації, вихід якого з'єднаний з другим входом блоку 9 керування операціями, виходи з шостого по восьмий якого з'єднані відповідно з другого по четвертий входами формувачів 7, 8 відповідно до адреси операндів і адреси вагових коефіцієнтів, перші входи яких підключені до другого виходу блоку 9 керування операціями. Виходи формувача 7 адреси операндів з'єднані відповідно з другим і третім керуючими входами блоку 4 оперативної пам'яті, третій і другий інформаційні входи якого з'єднані з виходами відповідно блоку 3 підсумування операндів і блоку 5 виконання базових операцій, другий вхід якого з'єднаний з виходом блоку 6 зберігання вагових коефіцієнтів, керуючий вхід якого з'єднаний з виходом формувача 8 адреси вагових коефіцієнтів. Керуючі входи блоку 1 адресації вхідних операндів (фіг. 2) з'єднані з другим і третім виходами блоку 9 керування операціями, є входами схеми 16 керування циклами, перший, другий і третій виходи якої з'єднані з інформаційними входами відповідно лічильника 13 з прямим переносом, комутатора 14, лічильника 15 із зворотним переносом, виходи лічильників 13, 15 з'єднані відповідно з першим і другим інформаційними входами зсувача 11, третій інформаційний вхід якого з'єднаній з виходом регістра 12 кількості зсувів, вхід якого з'єднаний з керуючими входами лічильників 13, 15 і комутатора 14, а також підключений до першого входу схеми 16 керування циклами, другий вхід якої підключений до керуючого входу зсувача 11, вихід якого підключений до першого керуючого входу блоку 4 оперативної пам'яті. Процесор швидкого перетворення Фур'є (ШПФ) вираховує дискретне перетворення Фур'є за N2 рядках довжиною N1 за алгоритмом з прорі 3 36435 джуванням за часом операндів і двоїчно-інверсним слідуванням відрахунків на вході. N1- 1 N2 - 1 X(k1, k2) = å å x(n1, n2) ×e Двомірне дискретне перетворення Фур'є знаходиться за відношенням: - j 2π ×k1×n1 - j 2π ×k2×n2 N1 × e N2 (1) n1 =0 n2 =0 x (n1, n2) - двомірний вхідний процес (матриця розміром N=N1*N2); к 1=0,N 1-1; к2=0,N2-1 - індекси частотних відрахунків. Співвідношення (1) можна представити у таких виглядах: é - j 2π ×k1×n1 ù - j 2π ×k2×n2 ê å x(n1,n2) × e N1 ú × e N2 X(k1, k2) = å ê ú n2 = 0 n1= 0 ê ú ë û 2π 2π é - j ×k2×n2 ù - j ×k1×n1 N1-1 N2-1 ú × e N1 X(k1, k2) = å ê å x(n1,n2) × e N2 ê ú n1 = 0 n2= 0 ê ú ë û N2-1 N1-1 Двомірне перетворення Фур'є зручно рахувати через одномірне перетворення спочатку за рядками довжиною N1 відрахунків, потім за стовпцями, як це рекомендується у монографіях і статтях з багатомірної обробки сигналів, наприклад, у книзі: Д. Даджион, Р.Мерсеро. Цифровая обработка многомерных сигналов. - М.: Мир, 1988. - С. 100. Алгоритм з векторної підстави 2*2 достатньо скла (2) дний (С. 102-105), тому практично не застосовується на практиці. Із співвідношень (2) видно, що двомірний спектр Х(к1, к2) процесу х(n1, n2) можна рахувати за схемами: рядки-стовпці або стовпці-рядки матриці. Запропонований процесор ШПФ виконує перетворення операндів x(n1, n2) за співвідношенням: N1-1 X(m1, m2) = å x(n1,n2) ×e - j 2π ×m1×n1 N1 (3) n1= 0 матрицю Х(m1, m 2) ® Х(m2, m1) і зробити вдруге перетворення за формулою (3) з параметрами N2, N1 при n1=m2; m1=0,N1-1; m2=0,N2-1. Алгоритм (З) вираховує проміжне перетворення Фур'є. Для знаходження перетворення Фур'є Х(к1, к2) за вираженням (1) слід транспонувати N2 - 1 X(k1, k2) = å x(m1,m2) ×e m2 =0 при m1=k1; m1=0,N1-1; m2=0,N2-1. З виражень (3), (4) видно, що для кожного рядка n2=0,N2-1, потім для кожного стовпця m1=0,N11 виконуються одномірні перетворення Фур'є довжиною відповідно N1 і N2 відрахунків. Для реалізації алгоритму (3) зручно використовувати алгоритм ШПФ за основанням два з проріжуванням операндів за часом і двоїчноінверсійним порядком на вході. Характерною особливістю даного алгоритму є об'єднання двох сусідніх перетворення Фур'є в єдиній подвоєній довжині. Виходячи з цієї особливості, обчислення робиться за загальним алгоритмом для масиву даних довжиною N=N1*N2 відрахунків з виконанням log2N1 етапів перетворення операндів за базовою операцією. Направлений граф алгоритму ШПФ, що реалізує співвідношення (3), наведений на фіг. 5. Двомірне перетворення Фур'є широко застосовується при обробці зображень, коли потрібна дуже висока швидкодія. Для його підрахування - j 2π ×k2×m2 N1 (4) зручно використовувати два запропонованих послідовно з'єднаних процесора швидкого перетворення Фур'є, яким відповідно обробляються рядки та стовпці вхідного масиву даних х(n1, n2). Масив х(n1,n2) поступає до першого процесора, з виходу якого проміжний спектр X(m1,m2), що підрахований за формулою (3), поступає до другого процесора з одночасним транспонуванням даних Х(m1, m2)®X(m2, m1). На виході другого процесора отримуємо двомірне перетворення Фур'є (1) X(k1, k2). Запропонований процесор швидкого перетворення Фур'є (фіг. 1) містить блок 5 виконання базових операцій. Для досягнення високої швидкодії доцільно у блоці 5 мати максимально можливу кількість арифметичних пристроїв, що реалізують базову операцію алгоритму ШПФ кожного рядка. 4 36435 p A i (k) = A i-1(k) + A i-1(l) × W N1 P A i (l) = A i - 1(k) - A i-1(l) × WN1 (5) A(k) = a(k) + j × b(k) ; A(l) = a(l) + j - b(l) 2π 2π W P = cos p - j × sin p = cosj (p) - j × sinj (p) N1 N1 N1 A(k), A(1) - операнди базової операції свавільноматриці, то рядки та стовпці міняються місцями. го рядка; Блок 1 адресації вхідних операндів має два режиN 1 - довжина рядка операнда A(k); ми функціонування: ввід матриці х(n1, n2) J = 1,2...n; без транспонування або з транспонуванням n= log 2N 1 - номер чергового етапу перетворення відповідно. операндів; Як видно із співвідношень (5), у базовій операN1 ції перетворюється два операнди A(l)=a(l)+jb(l), - номер вагового (що повертає) коефіp = 0; -1 2 або чотири дійсних числа а(l), b(l), a(k), b(k). Швидцієнта. кодія процесора фіг. 1 пропорційна кількості ариТаблиця вагових коефіцієнтів для максимальфметичних пристроїв блоку 5, однак їх кількість но оброблених рядків N1