Пристрій для обчислення двоточкового зрізаного перетворення фур`є в полі gf(28)

Запропонована корисна модель відноситься до галузі автоматики й обчислювальної техніки і може бути використана в системах кодування даних. Відомий "П ристр ій для шви дко го дійсн ого пере твор ення Хар тлі -Фур'є " [1], який містить блок синхронізації, два лічильника адреси, блок постійно ї пам'я ті, вхі дни й ре гі стр , р егістр , ви хі дни й ре гі стр , блок пам 'я ті , два перемножувача, два комутатора, суматор-вичитач, ви хідний регістр, комутатор, інформаційний вхід, інформаційний вихід. Недоліком пристрою є те, що він не виконує обчислень векторів. Відомий також "Пристрій для обчислення усічено го перетворення Фур'є в остато чних класах" [2], який містить блок оперативної пам'яті, перший, др угий , тре тій та че твер тий блоки постійно ї пам'я ті, перший , др угий та третій блоки, які реалізують операцію складання по модулю два, перший, другий, третій та четвертий допоміжні блоки постійної пам'яті, перший, другий, третій та четвертий регістри, блок управління, до складу якого входять генератор тактових імпульсів, тригер, лічильник, дешифратор, перший, другий, третій та четвертий елементи І. Недоліком пристрою є те, що він обчислює усічене перетворення Фур'є в остаточних класах табличним способом. Найбільш близьким до запропонованого технічним рішенням, обраним як прототип, є "Пристрій для обчислення усіченого перетворення Фур'є в залишкових класах" [3], який містить блок оперативної пам'яті, перший, другий, третій та четвертий блоки постійної пам'яті, перший та другий мультиплексор и , бло к ск ла дан ня по м о дулю два , п ер ши й , др уги й , тр е ті й , че тве р тий та п'ятий регістри, блок керування, до складу якого входять генератор тактових імпульсів, перший, другий та третій тригери, перший, другий, третій та четвертий лічильники, деши фратор , пер ший , др угий, тре тій , че твер тий та п 'я тий елементи І, формувач фронтів, перший та другий елементи АБО, постійний запам'ятовуючий пристрій. Недоліком пристрою-прототипу є те, що він обчислює математичним способом чотирьохточкове усічене перетворення Фур'є в полі GF(28). В основу корисної моделі поставлена задача створити "Пристрій для обчислення двоточкового усіченого перетворення Фур'є в полі GF(28)", який реалізує знаходження вихідного вектора для двоточкового усіченого перетворення Фур'є в полі GF(2 8) математичним способом. Усічене перетворення Фур'є в залишкових класах визначено [4]: n -1 Vj = åW ij × Vi (1) i=1 å( n-1 ) æ ö 1 Vi = ç W -ij Å L × Vj ç n modp ÷ ÷ è ø j=1 (2) де w - елемент порядку n у полі GF(qm ); і - номер точки вхідного вектору (для дво точкового усіченого перетворення Фур'є в полі GF(28 ) і=1 , 2); j - номер точки вихідного вектору (для дво точкового усіченого перетворення Фур'є в полі GF(28) j=1, 2); Å - операція складання у полі; L=-1. Існує два способи знаходження вихідного вектора: 1. Математичний спосіб, який полягає у виконанні всіх математичних операцій згідно (1). 2. Табличний спосіб, який полягає в тому, що строя ть (n-1) таблиць, які складаються з 2m елементів, розміру m×(n-1) біт, а вихідний вектор отримують шля хом складання елементів таблиць, які відповідають точкам вхідного вектору. Поста влен а задача ви рі шується за р а хунок то го , що у при стро ї-прототипі усун уті третій та четвертий блоки постійної пам'яті, третій та четвер тий р е гі стри . У блоці кер ування усун уті тре ті й лі чиль ник , че твер тий та п'ятий елементи І та додатково введено D-тригер. Також додатково введені нові зв'язки у всьому пристрої. Технічний результат, який може бути отриманий при використанні корисної моделі, полягає в одержанні технічного засобу для знаходження вихідно го век тор а при реа лізації дво то чко во го усі чено го пере тво рення Фур 'є в полі GF(28) математичним способом. На Фіг.1 приведена блок-схема запропонованого пристрою. На Фіг.2 приведена блок-схема блока керування запропонованого пристрою. Запропонований пристрій для обчислення двоточкового усіченого перетворення Фур'є в полі GF(28) місти ть блок оперативної пам'яті 1, пер ший та другий блоки постійної пам'яті 2 і 3, блок керування 4, перший мультиплексор 5, блок складання по модулю два 6, перший та другий регістри 7 і 8, другий мультиплексор 9, третій регістр 10, вхід зап уску 11, ви хід 12, причому вхі д зап уск у 11 пристрою з'єднаний з вхо дом блока кер ування. Адресний вхід блока оперативної пам'яті 1 з'єднаний з ви хо дом 13 блока керування. Вхі д дозволу чи тання блока оперативної пам'яті 1 з'єднаний з ви ходом 14 блока керування. Вихід блока оперативної пам'яті 1 з'єднаний з адресними входами блоків постійної пам'яті 2 і 3. Входи дозволу читання блоків постійної пам'яті 2 і 3 з'єднані з виходом 14 блока керування. Вихід блока постійної пам'яті 2 з'єднаний з першим входом мультиплексора 5. Вихід блока постійної пам'я ті 3 з'єднаний з др угим входом мультиплексора 5 . Адресний вхід мультиплексора 5 з'єднаний з виходом 15 блока керування. Вихід мультиплексора 5 з'єднаний з другим входом блока 6, що реалізує операцію складання по модулю два. Вихід блока 6, що реалізує операцію складання по модулю два, з'єднаний з входами даних регістрів 7 і 8. Входи дозволу запису регістрі в 7 і 8 з'єднані з ви ходом 16 блока кер ування. Ви хід ре гістра 7 з 'єднани й з першим входом м уль тип лексора 9 . Ви хід регі стра 8 з 'єдна ний з др угим входом м ультиплексо ра 9 . Адре сний вхід м уль типлек сора 9 з 'єднаний з ви ходом 17 блока керування. Вихід м ультиплексора 9 з'єднаний з входом даних регістра 10. Вхід дозволу запису регістра 10 з'єднаний з вихо до м 17 блок а ке р ува н н я . Ви хі д ре гі стр а 10 є ви хо до м 1 2 п ри стр о ю та з 'єднан ий з пе р шим входом блока 6 , що ре алі з ує опе ра цію складання по модулю два. Блок керування 4 пристрою для обчи слення дво точко вого усічено го перетворення Фур'є в полі GF(28) містить: генератор тактових імпульсів 18, перший тригер 19, перший та другий лічильники 20 і 21, дешифратор 22, перший елемент І 23, формувач фронтів 24, перший та другий елементи АБО 25 і 26, D-тригер 27, третій лічильник 28, другий та третій тригери 29 і 30, постійний запам'ятовуючий пристрій 31, другий та третій елементи І 32 і 33, причому вхід 11 блока керування з'єднаний з входом переводу тригера 19 в одиницю, вихід три гера 19 з'єднаний з входом генератора тактови х імпульсів 18, вихід якого з'єднаний з рахунковим входом лічильника 21 та другими входами елементів І 32 і 33. Вхід скидання тригера 19 з'єднаний з виходом переповнення (переносу) лічильника 20. Перший вихід лічильника 21 (молодший розряд) з'єднаний з першим входом деши фратора 22 (молодший розряд) і першим входом елемента І 23. Другий вихід лічильника 21 з'єднаний з другим входом дешифра тора 22. Третій ви хід лічильника 21 (старший розряд) з'єднаний з третім входом дешифратора 22 (старший розряд) і другим входом елемента І 23. Вихід елемента І 23 з'єднаний з входом формува ча фронтів 24. Ви хід форм увача фронтів 24 з'єднаний з входом лічильника 20, входом обнуління лічильника 21, входами обнуління тригерів 29 і 30. Перший вихід дешифратора 22 з'єднаний з входом переводу тригера 29 в одиницю, др уги й ви хід деши фратора 22 з 'єднаний з входом перево ду тригер а 30 в одиницю, третій вихід дешифратора 22 з'єднаний з першим входом елемента АБО 25, четвер тий вихід де ши фратора 22 з'єднаний з першим входом елемента АБО 26 і першим входом елемента І 32, п'ятий вихі д деши фра тора 22 з'єднаний з другим входом елемента АБО 25, шостий вихід деши фратора 22 з'єднаний з другим входом елемента АБО 26 і першим входом елемента І 33. Вихід елемента АБО 25 з'єднаний з входом D-тригера 27. Вихід елемента АБО 26 з'єднаний з тактовим входом лічильника 28. Виходи лічильника 28 з'єднані з входами постійного запам'ятовуючого пристрою 31. Ви хід лічильника 20 по виходу 13 блока керування 4 з'єднаний з адресним входом блока оперативної пам'яті 1. Вихід тригера 29 по виходу 14 блока керування 4 з'єднаний з входом дозволу читання блока оперативної пам'яті 1. Вихід тригера 30 по виходу 14 блока керування 4 з'єднаний з входами дозволу читання блоків постійної пам'яті 2 і 3. Вихід постійного запам'ятовуючого пристрою 31 по виходу 15 блока керування 4 з'єднаний з адресним входом мультиплексора 5. Вихід елемента І 32 по виходу 16 блока керування 4 з'єднаний з входом дозволу запису регістра 7. Вихід елемента І 33 по виходу 16 блока керування 4 з'єднаний з входом дозволу запису регістра 8. Вихід елемента АБО 25 по виходу 17 блока керування 4 з'єднаний з входом дозволу запису регістра 10. Вихід Dтригера 27 по виходу 17 блока керування 4 з'єднаний з адресним входом мультиплексора 9. Робо та зап ропо но ван о го пр истрою здійснюєть ся за два цикли п о шість тактів у кожному та полягає в наступному. Перед початком роботи в блок оперативної пам'яті 1 записаний вхідний вектор v={v1 v2} в двійковому коді, причому Vi Î GF(28). В блоки постійної пам'яті 2 і 3 за адресою Vi=0 ¸ 255 записані результати множення в полі GF(28) у виді {P(viwIj)} де Р(Х) - перехід від десяткового предста влення елемента поля GF(28) до двійкового представлення; w - елемент порядку n у полі GF(qm); і - номер точки вхідного вектору; j - номер точки ви хідного вектору. Регістри 7, 8 і 10, тригер 19, лічильники 20 і 21, D-тригер 27, лічильник 28, тригери 29 і 30 у нульовому стані. На виході дешифратора 22 під час роботи пристрою формується унітарний код такту, причому рівень "1" буде тільки на одному з його виходів. Постійний запам'ятовуючий пристрій 31 містить для кожного з тактів 4 і 6 циклів 1 і 2 адреси, що використо вують для адресаці ї м ультиплексора 5 з метою здіснення математичного способу зна ходження ви хідного вектора при реалізації двоточкового усіченого перетворення Фур'є в полі GF(28). По сигналу "Запуск обробки", що надходи ть по входу 11 пристрою, тригер 19 встановлюється в одиничний стан, сигнал "1" з виходу тригера 19 надходить на вхід генератора тактових імпульсів 18, що починає формувати послідовність тактових імпульсів, що надходять на рахунковий вхід лічильника 21 та другі входи елементів І 32 і 33. Цикл 1. На першому такті формується рівень "1" на першому виході дешифратора 22, що встановлює тригер 29 в одиницю. Рівень "1" з виходу тригера 29 через вихід 14 блока керування 4 поступає на вхід дозволу читання блока оперативної пам'яті 1, на ви ході якого формується двійкове представлення числа v1. На другому такті формується рівень "1" на другому виході деши фратора 22, що встановлює тригер 30 в одиницю. Рівень "1" з виходу тригера 30 через вихід 14 блока керування 4 поступає на входи дозволу читання блоків постійної пам'яті 2 і 3. При цьому на виходах блоків постійної пам'яті 2 і 3 формується двійкове представлення результату множення vi wij у полі GF(28). Двійкове представлення результату множення з виходу відповідного блока постійної пам'яті (2 або 3) через мультиплексор 5 поступає на другий вхід блока 6. З виходу блока 6 результат складання по модулю два результату множення зі значенням, що міститься на виході регістра 10, поступає на входи даних регістрів 7 і 8. На третьому такті формується рівень "1" на третьому виході дешифратора 22 , що з ви хо ду елемен та АБО 25 через ви хід 17 блока ке р уван ня 4 по передньому фронту імпульсу в регістр 10 через мультиплексор 9 записує значення, що міститься у регістрі 7. По задньому фронту імпульсу з ви ходу елемента АБО 25 D-тригер 27 встановлюється в одиницю. Рівень "1" з виходу D-тригера 27 через вихід 17 блока керування 4 поступає на адресний вхід мультиплексора 9 та комутує на вхід даних регістра 10 ви хід регістра 8. На четвертому такті формується рівень "1" на четвертому виході дешифратора 22, що з виходу елемента І 32 через вихід 16 блока керування 4 записує до регістра 7 результат складання по модулю два результату множення v1 у полі GF (28) зі значенням, що міститься на виході регістра 10. Рівень "1" з четвертого ви ходу деши фратора 22 поступає на елемент АБО 26. По передньому фронту імпульсу з виходу елемента АБО 26 лічильник 28 збільшує своє значення на одиницю. При цьому з виходу постійного запам'ятовуючого пристрою 31 через вихід 15 блока керування 4 на адресному вході мультиплексора 5 встановлюється новий адрес і двійкове представлення результату множення v1 у полі GF(28) з ви ходу відповідного блока постійної пам'яті (2 або 3) через мультиплексор 5 поступає на другий вхід блока 6. З виходу блока 6 результат складання по модулю два результату множення зі значенням, що міститься на виході регістра 10, поступає на входи даних регістрів 7 і 8. На п'ятому такті формується рівень "1" на п'ятому виході деши фратора 22, що з ви ходу елемента АБО 25 через вихід 17 блока керування 4 по передньому фронту імпульсу в регістр 10 через мультиплексор 9 записує значення, що міститься у регістрі 8. По задньому фронту імпульсу з ви ходу елем ен та АБО 25 D -тр и гер 27 вста н о влюєть ся в 0 . Рі ве нь "0 " з ви хо ду D-тригера 27 через вихід 17 блока керування 4 поступає на адресний вхід мультиплексора 9 та комутує на вхід даних регістра 10 ви хід регістра 7. На шостому такті формується рівень "1" на шостому виході де шифратора 22, що з ви ходу елемента І 33 через вихід 16 блока керування 4 записує до ре гі стра 8 рез ульта т скла дання по модулю два рез уль та ту множення v1 у по лі GF (28 ) зі значенням , що місти ться на ви ході ре гістра 10 . Рі вень "1" з шосто го ви хо ду деши фратора 22 поступа є на е лемент АБО 26 . По передньому фронту імпульсу з ви ходу елемента АБО 26 лічильник 28 збільшує своє значення на одиницю. При цьому з виходу постійного запам'ятовуючого пристрою 31 через вихід 15 блока керування 4 на адресному вході мультиплексора 5 встановлюється новий адрес і двійкове представлення результату множення v1 у полі GF(28) з виходу відповідного блока постійної пам'яті (2 або 3) через мультиплексор 5 поступає на другий вхід блока 6. З ви ходу блока 6 результат складання по модулю два результату множення зі значенням, що міститься на виході регістра 10, поступає на входи дани х регістрів 7 і 8. По задньому фронту імпульсу з ви ходу елемента І 23 через формувач фронтів 24 здійснюється збільшення на одиницю лічильника 20, обнуління лічильника 21 та встановлення в "0" тригерів 29 і 30. Рівень "1" з виходу лічильника 20 через вихід 13 блока керування 4 встановлює на адресному вході блока оперативної пам'яті 1 адресу для зчитування двійкового представлення числа v2 . Цикл 2 здійснюється аналогічно циклу 1 за винятком того, що всі операції здійснюються з використанням двійкового представлення числа v2. Після завершення останнього такту др угого циклу на ви ході переповнення лічильника 20 формується рівень "1", що скидає тригер 19 у нульовий стан, а пристрій повертається у початковий стан, при цьому з виходу 12 пристрою через мультиплексор 9 і регістр 10 зчитують остаточний результат, що міститься на виходах регістрів 7 і 8. Джерела інформації 1. А.с. 1569847 СССР, МКИ G 06 F15/332 . Устройство для быстрого действительного преобразования Хартли-Фур'є / С.Н. Демиденко, Э.Б. Куно вский, О.В. Мала шонок, Е.М. Левин . - №4473106; Заяв. 10 .08.88, Опубл. 7.06.90, Бюл. №21. 2. Деклараційний патен т №4264 U України , 7 МПК G 06 F7/04 . Пристрій для обчислення усіче ного перетворення Фур'є в о ста точни х к ласа х /Дуденко С.В., Рубан І.В., Тре тяк В.Ф., С умцов Д.В. №20040323 21 ; Зая в. 30.03.2004, Опубл. 17.01.2005, Бюл. №1. - 4с. ил. 3. Деклараційний патент на корисну модель №14431 U України, МПК(2006) G06F 5/00 G06F 17/14. Пристрій для обчислення усіченого перетво рення Фур'є в за ли шко ви х кла сса х / Дуденко С В., Рубан І.В., Алексєєв С.В., Ко лмико в М.М., Ка лачова В.В. - №и 2005 1099 7; Зая в. 21 .11 .2005 , Оп убл. 15.05.2006, Бюл. №5 . - 6с іл. 4. Рубан И.В., Дуденко С.В. Оптимизация теоретико-числовых преобразо ван ий // Ін форма ційн о-кер уючи системи на залізни чном у тран спор ті . - 2002. - №6. – С .47-4 9.