Синтез швидкодіючих пристроїв цифрової обробки сигналів на основі теоретико-числових перетворень
DOI:
https://doi.org/10.15587/1729-4061.2020.194342Ключові слова:
автокореляційна функція, кореляція, згортка, програмовані логічні інтегральні схеми, дискретне перетворення Фур'єАнотація
Запропоновано вибір модулів спеціального виду і відповідних їм первісних коренів, які допускають спрощену структуру арифметичних пристроїв, із застосуванням теоретико-числових перетворень. Розроблено метод визначення модулів, що забезпечує мінімальне число арифметичних операцій при виконанні операцій додавання і множення за модулем. Розроблено і промоделювано структури суматорів за модулями спеціального виду, що дозволяють максимально швидко виконувати операцію складання. Синтезовані і протестовані суматори за модулями чисел Ферма, Мерсенна і Голомба, які можна застосувати в арифметичних блоках швидкодіючих кореляторів і фільтрів.
Обчислення кореляцій і згорток в реальному часі стає досить трудомістким завданням у разі довгих вхідних послідовностей. Для вирішення цього завдання доцільно застосувати так звані швидкі алгоритми. Однак це вимагає високої продуктивності обчислювача згорток і кореляцій, які часто перевищують можливості сучасної обчислювальної техніки. Тому запропонована методика визначення модуля і розроблені структурні схеми суматорів за модулями спеціального виду, дозволяють прискорити обчислення кореляцій і згорток з використанням теоретико-числових перетворень.
Так як операція множення за модулем виконується за допомогою операцій додавання і зсуву, то трудомісткість розрахунку теоретико-числових перетворень в значній мірі залежить від кількості одиниць в двійковому поданні ступенів первісного кореня. Операція множення, як правило, зводиться до багаторазового складання чисел, то складність і швидкодія арифметичних пристроїв для теоретико-числових перетворень визначається характеристиками суматорів за модулем.
Запропонований метод проектування обчислювальних модулів для цифрових пристроїв обчислення кореляції і згортки на основі швидких теоретико-числових перетворень забезпечує спрощену апаратну і програмну реалізацію цих структур, що призводить до високошвидкісної обробки сигналів і зображень
Посилання
- Ortega Cisneros, S., Rivera D., J., Moreno Villalobos, P., Torres, C., C. A., Hernandez-Hector, H., Raygoza, P., J. J. (2015). An image processor for convolution and correlation of binary images implemented in FPGA. 2015 12th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE). doi: https://doi.org/10.1109/iceee.2015.7357987
- Ito, I. (2013). A Computing Method for Linear Convolution and Linear Correlation in the DCT Domain. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E96.A (7), 1518–1525. doi: https://doi.org/10.1587/transfun.e96.a.1518
- Valencia, F., Khalid, A., O’Sullivan, E., Regazzoni, F. (2017). The design space of the number theoretic transform: A survey. 2017 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS). doi: https://doi.org/10.1109/samos.2017.8344640
- Zhang, J., Li, S. (2009). Data-recovery algorithm and circuit for cyclic convolution based on FNT. IEICE Electronics Express, 6 (14), 1019–1024. doi: https://doi.org/10.1587/elex.6.1019
- Boussakta, S., Hamood, M. T., Rutter, N. (2012). Generalized New Mersenne Number Transforms. IEEE Transactions on Signal Processing, 60 (5), 2640–2647. doi: https://doi.org/10.1109/tsp.2012.2186131
- Campbell, K., Lin, C.-H., Chen, D. (2018). Low-cost hardware architectures for mersenne modulo functional units. 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC). doi: https://doi.org/10.1109/aspdac.2018.8297388
- Toivonen, T., Heikkila, J. (2006). Video filtering with Fermat number theoretic transforms using residue number system. IEEE Transactions on Circuits and Systems for Video Technology, 16 (1), 92–101. doi: https://doi.org/10.1109/tcsvt.2005.858612
- Zhang, J., Li, S. (2009). High Speed Parallel Architecture for Cyclic Convolution Based on FNT. 2009 IEEE Computer Society Annual Symposium on VLSI. doi: https://doi.org/10.1109/isvlsi.2009.10
- Kumar, S., Chang, C.-H. (2017). A Scaling-Assisted Signed Integer Comparator for the Balanced Five-Moduli Set RNS {2n - 1, 2n, 2n + 1, 2n+1 - 1, 2n-1 - 1}. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25 (12), 3521–3533. doi: https://doi.org/10.1109/tvlsi.2017.2748984
- Efstathiou, C., Vergos, H. T., Nikolos, D. (2003). Modulo 2n ±1 adder design using select-prefix blocks. IEEE Transactions on Computers, 52 (11), 1399–1406. doi: https://doi.org/10.1109/tc.2003.1244938
- Golomb, S. W., Reed, I. S., Truong, T. K. (1977). Integer Convolution over Finite Field GF(3‧2n + 1). SIAM Journal on Applied Mathematics, 32 (2), 356–365. doi: https://doi.org/10.1137/0132029
- Chernov, V. M., Korepanov, A. O. (2006). Teoretiko-chislovye preobrazovaniya v zadachah tsifrovoy obrabotki signalov. Samara, 112.
- Baozhou, Z., Ahmed, N., Peltenburg, J., Bertels, K., Al-Ars, Z. (2019). Diminished-1 Fermat Number Transform for Integer Convolutional Neural Networks. 2019 IEEE 4th International Conference on Big Data Analytics (ICBDA). doi: https://doi.org/10.1109/icbda.2019.8713250
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Andrey Ivashko, Igor Liberg, Denis Lunin
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
