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

Пристрій для обчислення усіченого перетворення Фур'є в остаточних класах, який містить блок оперативної пам'яті, перший, другий, третій та четвертий блоки постійної пам'яті, перший, другий та третій блоки, які реалізують операцію складання по модулю два, перший, другий, третій та четвертий допоміжні блоки постійної пам'яті, перший, другий, третій та четвертий регістри, блок управління, до складу якого входять генератор тактових імпульсів, тригер, лічильник, дешифратор, перший, другий, третій та четвертий елементи І, який відрізняється тим, що додатково введені другий, третій та четвертий блоки постійної пам'яті, перший, другий та третій блоки, які реалізують операцію складання по модулю два, перший, другий, третій та четвертий допоміжні блоки постійної пам'яті, перший, другий, третій та четвертий регістри, вхід запуску пристрою з'єднаний з входом блока управління, вхід дозволу читання блока оперативної пам'яті з'єднаний з першим виходом блока управління, вихід блока оперативної' пам'яті з'єднаний з адресними входами першого, другого, третього та четвертого блоків постійної пам'яті, входи дозволу читання першого, другого, третього та четвертого блоків постійної пам'яті з'єднані з другим виходом блока управління, вихід першого блока постійної пам'яті з'єднаний з першим входом першого блока, що реалізує операцію складання по модулю два, вихід другого блока постійної пам'яті з'єднаний з другим входом першого блока, що реалізує операцію складання по модулю два, вихід першого блока, що реалізує операцію складання по модулю два, з'єднаний з першим входом другого блока, що реалізує операцію складання по модулю два, вихід третього блока постійної пам'яті з'єднаний з другим входом другого блока, що реалізує операцію складання по модулю два, вихід другого блока, що реалізує операцію складання по модулю два, з'єднаний з першим входом третього блока, що реалізує операцію складання по модулю два, вихід четвертого блока постійної пам'яті з'єднаний з другим входом третього блока, що реалізує операцію складання по модулю два, вихід третього блока, що реалізує операцію складання по модулю два, з'єднаний з адресними входами першого, другого, третього та четвертого допоміжних блоків постійної пам'яті, входи дозволу читання котрих з'єднані з третім виходом блока управління, вихід першого допоміжного блока постійної пам'яті з'єднаний з входом запису першого регістра, вихід другого допоміжного блока постійної пам'яті з'єднаний з входом запису другого регістра, вихід третього допоміжного блока постійної пам'яті з'єднаний з входом запису третього регістра, вихід четвертого допоміжного блока постійної пам'яті з'єднаний з входом запису четвертого регістра, вхід дозволу запису першого, другого, третього та четвертого регістрів з'єднаний з четвертим виходом блока управління, вхід блока управління з'єднаний з входом переводу тригера в одиницю, вихід тригера з'єднаний з входом генератора тактових імпульсів, вихід якого з'єднаний з рахунковим входом лічильника та другим входом першого, другого, третього та четвертого елементів І, перший вихід лічильника з'єднаний з першим входом дешифратора, другий вихід лічильника з'єднаний з другим входом дешифратора, вихід переповнення лічильника з'єднаний з входом скидання тригера, перший вихід дешифратора з'єднаний з першим входом першого елемента І, другий вихід дешифратора з'єднаний з першим входом другого елемента І, третій вихід дешифратора з'єднаний з першим входом третього елемента І, четвертий вихід дешифратора з'єднаний з першим входом четвертого елемента І, вихід першого елемента І по першому виходу блока управління з'єднаний з входом дозволу читання блока оперативної пам'яті, вихід другого елемента І по другому виходу блока управління з'єднаний з входами управління читанням першого, другого, третього та четвертого блоків постійної пам'яті, вихід третього елемента І по третьому виходу блока управління з'єднаний з входом управління читанням першого, другого, третього та четвертого допоміжних CD CM З 4264 4 блоків постійної пам'яті, вихід четвертого елемез'єднаний з входами управління записом першонта І по четвертому виходу блока управління го, другого, третього та четвертого регістрів. Запропонована корисна модель відноситься до галузі автоматики й обчислювальної техніки І може бути використаний в системах обробки і відображення інформації. Відомий "Пристрій для обчислення дискретного перетворення Фур'е" [1], який містить інформаційний вхід, перемножувач, комутатор, N/2 обчислювальних модулей (де N - розмір перетворення), кожний з котрих містить k регістрів, тригер, два буферних регістра, два перемножувача, два регістри, два суматора. Крім цього, пристрій містить шину синхронізації, генератор тактових імпульсів, лічильник, дешифратор, елемент І-НІ, вхід завдання режиму, перемножувач, комутатор, два блоки постійної" пам'яті. Недоліком відомого пристрою є те, що він обчислює дискретне перетворення Фур'є комплексного вектору, кожна точка якого складається з дійсної та мнимої частини і тому потребує подвійних обчислень при знаходженні вихідного вектору. Відомий також "Пристрій для швидкого дійсного перетворення Хартлі-Фур'є" [2], який містить блок синхронізації', два лічильника адреси, блок постійної пам'яті, вхідний регістр, регістр, вихідний регістр, блок пам'яті, два перемножувача, два комутатора, суматор-вичитач, вихідний регістр, комутатор, інформаційний вхід, інформаційний вихід. Відомий пристрій перетворює коефіцієнти Хартлі в коефіцієнти Фур'є, що вказує на можливість використання пристроїв, які виконують перетворення Хартлі, для обчислення перетворення Фур'є при умові введення додаткових елементів та ВІДПОВІДНИХ зв'язків. Недоліком пристрою є те, що він не виконує обчислень векторів. Найбільш близьким до запропонованого технічним рішенням, обраним як прототип, є "Пристрій для реалізації швидкого перетворення Хартлі" [3], який містить: блок оперативної пам'яті, блок постійної пам'яті, блок управління, суматор, перемножувач, накопичуваючий суматор Блок управління містить генератор тактових імпульсів, тригер, два лічильники, дешифратор, одновібратор, чотири елементи І. Недоліком пристрою-прототипу є те, що він обчислює дискретне перетворення Хартлі, яке має аналітичні вирази (1), що відрізняються від виразів для усіченого перетворення Фур'є в остаточних класах (2, 3). В основу винаходу поставлена задача створити "Пристрій для обчислення усіченого перетворення Фур'є в остаточних класах", який реалізує табличний спосіб знаходження вихідного вектору при реалізації чотирьохточечного усіченого перетворення Фур'є в полі GF(28). Поставлена задача вирішується за рахунок то го, що у при строї-прототипі усунуті суматор, перемножувач, накопичуваючий суматор, та додатково введені другий, третій та четвертий блоки постійної пам'яті, перший, другий та третій блоки, що реалізують операцію складання по модулю два, перший, другий, третій та четвертий допоміжних блока постійної пам'яті, перший, другий, третій та четвертий регістри. В блоці управління усунуті: лічильник, одновібратор та додатково введені нові зв'язки у всьому пристрою. Технічний результат, який може бути отриманий при здійсненні винаходу, полягає в одержанні технічного засобу для табличного способу знаходження вихідного вектору при реалізації' чотирьохточечного усіченого перетворення Фур'є в полі GF(23) На Фіг.1 зображена блок-схема запропонованого пристрою. На ФІг.2 зображена блок-схема блоку управління запропонованого пристрою Запропонований пристрій для обчислення усіченого перетворення Фур'є в остаточних класах (Фіг.1) містить блок оперативної пам'яті 1, чотири блоки постійної пам'яті 2-5, блок управління 6, три блоки, що реалізують операцію складання по модулю два 7-9, чотири допоміжних блоки постійної пам'яті 10-13, чотири регістра 14-17, вхід запуску 18, вихід 19, причому вхід запуску пристрою 18 з'єднаний з входом блоку управління. Вхід дозволу читання блоку оперативної пам'яті 1 з'єднаний з виходом блоку управління 20. Вихід блоку оперативної пам'яті 1 з'єднаний з адресними входами блоків постійної пам'яті 2-5 Входи дозволу читання блоків постійної' пам'яті 2-5 з'єднані з виходом блоку управління 21. Вихід блоку постійної пам'яті 2 з'єднаний з першим входом блоку 7, що реалізує операцію складання по модулю два Вихід блоку постійної пам'яті 3 з'єднаний з другим входом блоку 7, що реалізує операцію складання по модулю два. Вихід блоку 7, що реалізує операцію складання по модулю два, з'єднаний з першим входом блоку 8, що реалізує операцію складання по модулю два. Вихід блоку постійної пам'яті 4 з'єднаний з другим входом блоку 8, що реалізує операцію складання по модулю два. Вихід блоку 8, що реалізує операцію складання по модулю два, з'єднаний з першим входом блоку 9, що реалізує операцію складання по модулю два. Вихід блоку постійної' пам'яті 5 з'єднаний з другим входом блоку 9, що реалізує операцію складання по модулю два. Вихід блоку 9, що реалізує операцію складання по модулю два, з'єднаний з адресними входами допоміжних блоків постійної1 пам'яті 10-13 Входи дозволу допоміжних блоків постійної пам'яті 10-13 з'єднані з виходом блоку управління 22. Вихід до 4264 поміжного блоку постійної пам'яті 10 з'єднаний з входом запису регістру 14. Вихід допоміжного блоку постійної пам'яті 11 з'єднаний з входом запису регістру 15. Вихід допоміжного блоку постійної пам'яті 12 з'єднаний з входом запису регістру 16 Вихід допоміжного блоку постійної пам'яті 13 з'єднаний з входом запису регістру 17. Входи дозволу запису регістрів 14-17 з'єднаний з виходом блоку управління 23. Блок управління 6 пристрою для обчислення усіченого перетворення Фур'є в остаточних класах (Фіг.2) містить тригер 24, генератор тактових імпульсів 25, лічильник 26, дешифратор 27, чотири елемента ! 28-31, причому вхід блоку управління 18 з'єднаний з входом переводу тригера 24 в одиницю, вихід тригеру з'єднаний з входом генератору тактових імпульсів 25, вихід якого з'єднаний з рахунковим входом лічильника 26 та другими входами елементів І 28-31. Перший вихід лічильника 26 (молодший розряд) з'єднаний з першим входом дешифратора 27 (молодший розряд). Другий вихід лічильника 26 (старший розряд) з'єднаний з другим входом дешифратора 27 (старший розряд). Вихід переповнення лічильника 26 (переносу) з'єднаний з входом скидання тригера 24. Перший вихід дешифратора 27 з'єднаний з першим входом елемента І 28, другий вихід дешифратора 27 з'єднаний з першим входом елемента І 29, третій вихід дешифратора 27 з'єднаний з першим входом елемента І ЗО, четвертий вихід дешифратора 27 з'єднаний з першим входом елемента 131. Вихід елемента І 28 по виходу 20 блоку управління 6 з'єднаний з входом дозволу читання блоку оперативної' пам'яті 1. Вихід елемента І 29 по виходу 21 блоку управління 6 з'єднаний з входами управління читанням блоків постійної пам'яті 2-5. Вихід елемента І ЗО по виходу 22 блоку управління 6 з'єднаний з входом управління читанням допоміжних блоків постійної пам'яті 10-13. Вихід елемента І 31 по виходу 23 блоку управління 6 з'єднаний з входами управління записом регістрів 14-17 Робота запропонованого пристрою полягає в наступному. Перед початком роботи в блок оперативної пам'яті 1 записаний вхідний вектор V={V1, V2, Vg, V4} В ДВІЙКОВОМУ КОДІ, ПрИЧОМу V, eGF(2 8 ). В блок постійної пам'яті 2 за адресою vi=0-255 6 записані результати множення в GF(2 ) у виді {Р(Ут • 52) ® P(v, -103)® Р(Ут •154)® P(v, • 205)} де Р(Х) - перехід від десяткового представлення елемента поля GF(28) до двійкового представлення; ® - знак конкатенації1 результатів множення. В блок постійної пам'яті 3 за адресою v2=0-255 записані результати {P(v 2 -103)®P(v 2 -205)®P(v 2 .52)®P(v 2 -154}j В блок постійної пам'яті 4 за адресою аз=0-255 записані результати {P(v 3 -154)®P(v 3 -52)®P(v3-205)®P(v3-103)}. В блок постійної" пам'яті 5 за адресою а4~0-^255 записані результати {P(v 4 -205)®P(v 4 -154)®P(v 4 -103)®P(v 4 -52)J. Регістри 14-17, тригер 24 і лічильник тактів 26 1 у нульовому стані. В блоки допоміжної постійної пам'яті 10-13 за адресою аі=0-^255 записані результати операції ОР (аі) - зворотного переходу від двійкового представлення елемента поля GF(2 ) до десяткового представлення. По сигналу "Запуск обробки", що надходить по входу пристрою 18, тригер 24 встановлюється в одиничний стан, сигнал " 1 " з виходу тригера 24 надходить на вхід генератора тактових імпульсів 25, що починає формувати ПОСЛІДОВНІСТЬ тактових імпульсів, що надходять на рахунковий вхід лічильника тактів 26 та другі входи елементів 128-131. На виході дешифратора 27 формується унітарний код такту, причому рівень " 1 " буде тільки на одному з чотирьох його виходів, з'єднаних з першими входами відповідних елементів І 28 -) 31. На першому такті формується рівень " 1 " на першому виході дешифратора 27, що дозволяє проходження тактового імпульсу з генератора 25 через вихід 20 блоку управління 6 на вхід дозволу читання блоку постійної пам'яті 1, на виході якого формується вектор v. На другому такті при надходженні через елемент І 29 виходу 21 блоку управління 6 тактового Імпульсу вектор v з виходу блоку оперативної пам'яті 1 подається на адресні входи блоків постійної' пам'яті у такому виді: vi (розряди 0-7) на адресний вхід блоку постійної пам'яті 2, v 2 (розряди 8-15) на адресний вхід блоку постійної пам'яті З, v 3 (розряди 16-23) на адресний вхід блоку постійної пам'яті 4, V4 (розряди 24-31) на адресний вхід блоку постійної пам'яті 5. На третьому такті результат складання в блоках 7-9, що реалізують операцію складання по модулю два, надходить на адресні входи допоміжних блоків постійної пам'яті 10-13, а при надходженні через елемент І ЗО виходу 22 блоку управління б тактового імпульсу на виходах допоміжних блоків постійної' пам'яті 10-13 формуються відповідні коди у такому виді: допоміжний блок постійної пам'яті 10 - розряди 0-7, допоміжний блок постійної пам'яті 11 - розряди 8-15, допоміжний блок постійної пам'яті 12 - розряди 16-23, допоміжний блок постійної пам'яті 13 - розряди 24-31. На четвертому такті при надходженні через елемент І 31 виходу 23 блоку управління 6 тактового імпульсу дозволяється запис у регістри 14-17. Після завершення останнього такту на виході переповнення лічильника тактів 26 формується рівень "1", що скидає тригер 24 у нульовий стан, а пристрій повертається у початковий стан, при цьому з виходу пристрою 19 повинний бути зчитаний остаточний результат - вихідний вектор V: Vi - розряди 0-7, Уг - розряди 8-15, V3 - розряди 16-23, V 4 -розряди 24-31. Перетворення Хартлі дійсної функції т(т),т = 0,1,. .,N-1 є сума косинусного та синусного перетворень 4264 N-1 H(v) = 1ST1 1 т=0 ), v = 0,N=1 (1) де cas(©)-cos(0) + sin(0). Усічене перетворення Фур'є в остаточних класах визначено [4]. Ч = 2>'Ч (2) (3) 8 в третьому блоці К 3 = {P(v3 -154) ® P(v 3 • 52) ® P(v 3 • 205) ® P(v 3 • 103)}, в четвертому блоці К 4 = {P(v4 -205)®P(v 4 -154)®P(v 4 -103)®P