Вопросы радиоэлектроники. 2019; : 50-56
Унифицированная реконфигурируемая схема коммутации быстрого преобразования Фурье
https://doi.org/10.21778/2218-5453-2019-8-50-56Аннотация
В традиционной схеме вычисления быстрого преобразования Фурье (БПФ) коммутация входных аргументов для вычислительного узла «бабочка» осуществляется в различном порядке в зависимости от стадии вычисления, что обуславливает дополнительные затраты ресурсов при аппаратной или программной реализации. В статье предложен способ вычисления БПФ с унифицированной схемой коммутации от стадии к стадии. Представлено итеративное выражение для аппаратной или программной реализации схемы вычисления. Итеративное выражение содержит циклы вычисления двойной вложенности, в отличие от традиционной схемы, где требуются циклы тройной вложенности. На основе итеративного выражения показаны унифицированные схемы коммутации для вычисления БПФ как с прореживанием по времени, так и с прореживанием по частоте. Для предложенных схем описана возможность реконфигурирования для вычисления БПФ различного числа отсчетов, при этом поворотные множители остаются прежними, и нет необходимости делать их переменными. Таким образом, возможность реконфигурирования не требует дополнительных вычислительных затрат.
Список литературы
1. Скляр Б. Цифровая связь. Теоретические основы практическое применение. М.: Вильямс, 1999. 1106 с.
2. Проксис Д. Цифровая связь. М.: Радио и связь, 2000. 800 с.
3. Морелос Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. 320 с.
4. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. 576 с.
5. Yu Ch. L., inventor; Ind Tech Res Inst., assignee. Memory based Fast Fourier Transform device. United States patent US20060253514. 09.11.2006.
6. Nag S. K, Verma H. K., inventors; Xilinx Inc., assignee. System and method for RAM partitioning to exploit parallelism of RADIX 2 elements in FPGAs. United States patent US6507860. 14.01.2003.
7. Hao J., Lin X., et al., inventors; Chinese Acad. Inst. Automation., assignee. Data access method and device for parallel FFT computation. United States patent US20140337401. 13.11.2014.
8. Du G., Hou N., et al, inventors; Hefei Gongda Xianxing Microelectronic Technology Co Ltd., Univ. Hefei Technology, assignee. Address mapping method and system of radix 2*K parallel FFT (fast Fourier transform) architecture. Patent of China CN000103034621. 10.04.2013.
9. Goel M., Kwong J. Y., inventors; Texas Instruments Inc., assignee. Constant geometry split radix FFT. Patent of China CN103106180. 15.05.2013.
10. Поперечный П. С., Поперечная И. Ю., Солохина Т. В., Петричкович Я. Я., авторы; АО НПЦ «ЭЛВИС», патентообладатель. Унифицированная реконфигурируемая схема коммутации быстрого преобразования Фурье. Патент РФ на полезную модель RU188978. 14.12.2018.
Issues of radio electronics. 2019; : 50-56
Unified reconfigurable commutation scheme of FFT
https://doi.org/10.21778/2218-5453-2019-8-50-56Abstract
In the traditional scheme for calculating the fast Fourier transform (FFT), the input arguments for the butterfly computation are switched in a different order depending on the computation stage, which leads to additional resource expenditures in hardware or software implementation. The article offers the method for FFT calculation by means of unified communication scheme stageby‑stage. There is an iterating equation for hardware and software implementation. The equation consists of two‑level loops rather than tree level loop for the traditional scheme. According to the iterating equation the unified communication scheme FFT is provided for both time scale and frequency scale. Also the reconfiguration of schemes by different samples number is provided too. The rotating multipliers are the same like in non‑reconfigurable (fixed) communication scheme. So the offered approach does not required additional hardware or software resources.
References
1. Sklyar B. Tsifrovaya svyaz'. Teoreticheskie osnovy prakticheskoe primenenie. M.: Vil'yams, 1999. 1106 s.
2. Proksis D. Tsifrovaya svyaz'. M.: Radio i svyaz', 2000. 800 s.
3. Morelos Saragosa R. Iskusstvo pomekhoustoichivogo kodirovaniya. Metody, algoritmy, primenenie. M.: Tekhnosfera, 2005. 320 s.
4. Bleikhut R. Teoriya i praktika kodov, kontroliruyushchikh oshibki. M.: Mir, 1986. 576 s.
5. Yu Ch. L., inventor; Ind Tech Res Inst., assignee. Memory based Fast Fourier Transform device. United States patent US20060253514. 09.11.2006.
6. Nag S. K, Verma H. K., inventors; Xilinx Inc., assignee. System and method for RAM partitioning to exploit parallelism of RADIX 2 elements in FPGAs. United States patent US6507860. 14.01.2003.
7. Hao J., Lin X., et al., inventors; Chinese Acad. Inst. Automation., assignee. Data access method and device for parallel FFT computation. United States patent US20140337401. 13.11.2014.
8. Du G., Hou N., et al, inventors; Hefei Gongda Xianxing Microelectronic Technology Co Ltd., Univ. Hefei Technology, assignee. Address mapping method and system of radix 2*K parallel FFT (fast Fourier transform) architecture. Patent of China CN000103034621. 10.04.2013.
9. Goel M., Kwong J. Y., inventors; Texas Instruments Inc., assignee. Constant geometry split radix FFT. Patent of China CN103106180. 15.05.2013.
10. Poperechnyi P. S., Poperechnaya I. Yu., Solokhina T. V., Petrichkovich Ya. Ya., avtory; AO NPTs «ELVIS», patentoobladatel'. Unifitsirovannaya rekonfiguriruemaya skhema kommutatsii bystrogo preobrazovaniya Fur'e. Patent RF na poleznuyu model' RU188978. 14.12.2018.
