技术领域technical field
本发明涉及数字信号处理技术，尤其涉及一种快速傅里叶变换(FFT，FastFourier Transform)处理方法和装置。The present invention relates to digital signal processing technology, in particular to a fast Fourier transform (FFT, FastFourier Transform) processing method and device.
背景技术Background technique
FFT是数字信号处理中重要的单元，广泛应用于现代数字信号处理的各个领域，如有线通信、雷达、卫星通信和多媒体信号处理等。FFT根据实现结构可分为并行实现结构和串行实现结构。在对吞吐量和处理能力需求较高的应用中，通常会选择并行流水结构来实现FFT运算；但是，并行流水结构缺点在于硬件资源开销大。以N点FFT为例来讲，假定数据位宽为W，采用并行流水结构来实现，所需资源至少为：个寄存器，个复数乘法。所以，在对资源比较敏感的应用中，通常会选用串行实现结构。FFT is an important unit in digital signal processing and is widely used in various fields of modern digital signal processing, such as wired communication, radar, satellite communication and multimedia signal processing. According to the realization structure, FFT can be divided into parallel realization structure and serial realization structure. In applications that require high throughput and processing capabilities, the parallel pipeline structure is usually selected to implement FFT operations; however, the disadvantage of the parallel pipeline structure is that the hardware resource overhead is large. Taking N-point FFT as an example, assuming that the data bit width is W, and using a parallel pipeline structure to realize it, the required resources are at least: registers, complex multiplication. Therefore, in applications that are sensitive to resources, the serial implementation structure is usually selected.
串行实现结构的根本思想是对存储资源和蝶形运算单元进行复用，达到资源精简的目的。在现有技术中，要实现一个N点的FFT串行运算，通用做法是：采用两个深度为N的全功能双端口随机存取存储器(RAM，Random Access Memory)作为乒乓缓存进行蝶形运算；然而，在实际的电路设计中，采用全功能双端口RAM会消耗较多的资源，并且全功能双端口RAM的功耗也比较大。The basic idea of the serial implementation structure is to reuse storage resources and butterfly computing units to achieve the purpose of streamlining resources. In the prior art, to realize an N-point FFT serial operation, the general method is: two full-featured dual-port random access memories (RAM, Random Access Memory) with a depth of N are used as ping-pong buffers to perform butterfly operations However, in an actual circuit design, using a full-featured dual-port RAM will consume more resources, and the power consumption of the full-featured dual-port RAM is relatively large.
因此，如何在进行FFT处理中节省资源、降低功耗，提升芯片竞争力，是亟待解决的问题。Therefore, how to save resources, reduce power consumption, and improve chip competitiveness during FFT processing is an urgent problem to be solved.
发明内容Contents of the invention
有鉴于此，本发明实施例期望提供一种FFT处理方法和装置，能在进行FFT处理中节省资源、降低功耗，提升芯片竞争力。In view of this, the embodiments of the present invention expect to provide an FFT processing method and device, which can save resources, reduce power consumption, and improve chip competitiveness during FFT processing.
为达到上述目的，本发明的技术方案是这样实现的：In order to achieve the above object, technical solution of the present invention is achieved in that way:
本发明实施例提供了一种FFT处理方法，所述方法包括：An embodiment of the present invention provides an FFT processing method, the method comprising:
将离散数字信号序列中的各离散数字信号，按输入地址规则写入上部存储器和下部存储器中；Write each discrete digital signal in the discrete digital signal sequence into the upper memory and the lower memory according to the input address rules;
按照运算读取地址规则，依次从上部存储器和下部存储器中分别读取一组离散数字信号进行蝶形运算，将蝶形运算结果按运算写入地址规则写入上部存储器和下部存储器中，直至完成蝶形运算所有级数的运算；Read a set of discrete digital signals from the upper memory and the lower memory in turn according to the operation read address rules to perform butterfly operation, and write the results of the butterfly operation into the upper memory and the lower memory according to the operation write address rules until the completion Butterfly operation of all series operations;
按照输出地址规则，从上部存储器和下部存储器中读取完成蝶形运算的数据，将所述读取的数据确定为所述离散数字信号序列的FFT结果。According to the output address rule, read the data that has completed the butterfly operation from the upper memory and the lower memory, and determine the read data as the FFT result of the discrete digital signal sequence.
上述方案中，所述按输入地址规则写入上部存储器和下部存储器中，包括：In the above scheme, the writing into the upper memory and the lower memory according to the input address rules includes:
将位数等于蝶形运算级数的二进制数作为数据输入计数器，并从小到大计数；Input the binary number whose number of digits is equal to the number of butterfly operations into the counter as data, and count from small to large;
将所述数据输入计数器的最高位取反后的值和所述数据输入计数器的最高位分别作为上部存储器和下部存储器的写使能；Using the inverted value of the highest bit of the data input counter and the highest bit of the data input counter as the write enable of the upper memory and the lower memory respectively;
将所述数据输入计数器去除所述最高位后剩余各位的倒序二进制数作为写入地址；Taking the inverted binary numbers of the remaining bits after removing the highest bit from the data input counter as the write address;
按照所述数据输入计数器计数，依次将所述各离散数字信号按照所述数据输入计数器对应的写入地址写入所述上部存储器和下部存储器。According to the counting of the data input counter, the discrete digital signals are sequentially written into the upper memory and the lower memory according to the write address corresponding to the data input counter.
上述方案中，所述按照运算读取地址规则，依次从上部存储器和下部存储器中分别读取一组离散数字信号进行蝶形运算，包括：In the above solution, according to the operation read address rule, sequentially read a set of discrete digital signals from the upper memory and the lower memory respectively for butterfly operation, including:
将位数等于蝶形运算级数减1之差的二进制数作为运算计数器，并从小到大计数；Use the binary number whose number of digits is equal to the difference of the butterfly operation series minus 1 as the operation counter, and count from small to large;
第一级蝶形运算时，各次蝶形运算分别采用所述运算计数器相同二进制数作为读取地址，后续级数的蝶形运算分别以前级同次蝶形运算读取地址的循环左移作为读取地址；During the first-stage butterfly operation, each butterfly operation uses the same binary number of the operation counter as the read address, and the butterfly operation of the subsequent series is respectively the circular left shift of the read address of the same butterfly operation of the previous stage as the read address. read address;
按照所述运算计数器的计数，依次分别从上部存储器和下部存储器中，在运算计数器对应的读取地址读取离散数字信号并进行蝶形运算。According to the counting of the operation counter, the discrete digital signal is read from the upper memory and the lower memory respectively at the reading address corresponding to the operation counter in sequence, and the butterfly operation is performed.
上述方案中，所述将蝶形运算结果按运算写入地址规则写入上部存储器和下部存储器中，包括：In the above scheme, the butterfly operation result is written in the upper memory and the lower memory according to the operation write address rule, including:
按照蝶形运算数据读取地址以及所述读取地址先后顺序，将各次蝶形运算的结果间隔存入上部存储器和下部存储器；According to the read address of the butterfly operation data and the order of the read address, the results of each butterfly operation are stored in the upper memory and the lower memory at intervals;
同次蝶形运算的两组结果依次存入同一存储器。Two groups of results of the same butterfly operation are stored in the same memory in turn.
上述方案中，所述按照输出地址规则，从上部存储器和下部存储器中读取完成蝶形运算的数据，包括：In the above scheme, according to the output address rule, reading the data that completes the butterfly operation from the upper memory and the lower memory includes:
将位数等于蝶形运算级数的二进制数作为数据输出计数器，并从小到大计数；Use the binary number equal to the butterfly operation series as the data output counter, and count from small to large;
将去除最低位后的所述数据输出计数器的最高位移到最低位，并将完成移位的各二进制数作为排序的输出读取地址；Shift the highest bit of the data output counter after removing the lowest bit to the lowest bit, and use the binary numbers that have been shifted as the sorted output read address;
按所述输出读取地址排序，依次在各输出读取地址分别从上部存储器和下部存储器读取所述完成蝶形运算的数据。Sorting according to the output read addresses, reading the data that has completed the butterfly operation from the upper memory and the lower memory respectively at each output read address in sequence.
上述方案中，所述分别从上部存储器和下部存储器读取所述完成蝶形运算的数据，包括：In the above scheme, the reading of the data that has completed the butterfly operation from the upper memory and the lower memory respectively includes:
将所述数据输出计数器的最低位作为上部存储器和下部存储器的读使能，按照所述数据输出计数器计数，间隔使能所述上部存储器和下部存储器，并从同一输出读取地址读取所述完成蝶形运算的数据。Use the lowest bit of the data output counter as the read enable of the upper memory and the lower memory, count according to the data output counter, enable the upper memory and the lower memory at intervals, and read the data from the same output read address The data to complete the butterfly operation.
上述方案中，所述存储器为简单双端口RAM。In the above solution, the memory is a simple dual-port RAM.
上述方案中，所述存储器深度为所述FFT点数的一半。In the above solution, the memory depth is half of the number of FFT points.
本发明实施例还提供了一种FFT处理装置，所述装置包括：输入控制器、运算器、输出控制器、上部存储器和下部存储器；其中，An embodiment of the present invention also provides an FFT processing device, which includes: an input controller, an arithmetic unit, an output controller, an upper memory, and a lower memory; wherein,
所述输入控制器，用于将离散数字信号序列中的各离散数字信号，按输入地址规则写入上部存储器和下部存储器中；The input controller is used to write each discrete digital signal in the discrete digital signal sequence into the upper memory and the lower memory according to input address rules;
所述运算器，用于按照运算读取地址规则，依次从上部存储器和下部存储器中分别读取一组离散数字信号进行蝶形运算，将蝶形运算结果按运算写入地址规则写入上部存储器和下部存储器中，直至完成蝶形运算所有级数的运算；The arithmetic unit is used to sequentially read a group of discrete digital signals from the upper memory and the lower memory according to the operation read address rule to perform the butterfly operation, and write the result of the butterfly operation into the upper memory according to the operation write address rule And in the lower memory, until the operation of all stages of the butterfly operation is completed;
所述输出控制器，用于按照输出地址规则，从上部存储器和下部存储器中读取完成蝶形运算的数据，将所述读取的数据确定为所述离散数字信号序列的FFT结果。The output controller is used to read the data that has completed the butterfly operation from the upper memory and the lower memory according to the output address rule, and determine the read data as the FFT result of the discrete digital signal sequence.
上述方案中，所述输入控制器，具体用于：In the above solution, the input controller is specifically used for:
将位数等于蝶形运算级数的二进制数作为数据输入计数器，并从小到大计数；Input the binary number whose number of digits is equal to the number of butterfly operations into the counter as data, and count from small to large;
将所述数据输入计数器的最高位取反后的值和所述数据输入计数器的最高位分别作为上部存储器和下部存储器的写使能；Using the inverted value of the highest bit of the data input counter and the highest bit of the data input counter as the write enable of the upper memory and the lower memory respectively;
将所述数据输入计数器去除所述最高位后剩余各位的倒序二进制数作为写入地址；Taking the inverted binary numbers of the remaining bits after removing the highest bit from the data input counter as the write address;
按照所述数据输入计数器计数，依次将所述各离散数字信号按照所述数据输入计数器对应的写入地址写入所述上部存储器和下部存储器。According to the counting of the data input counter, the discrete digital signals are sequentially written into the upper memory and the lower memory according to the write address corresponding to the data input counter.
上述方案中，所述运算器，具体用于：In the above scheme, the calculator is specifically used for:
将位数等于蝶形运算级数减1之差的二进制数作为运算计数器，并从小到大计数；Use the binary number whose number of digits is equal to the difference of the butterfly operation series minus 1 as the operation counter, and count from small to large;
第一级蝶形运算时，各次蝶形运算分别采用所述运算计数器相同二进制数作为读取地址，后续级数的蝶形运算分别以前级同次蝶形运算读取地址的循环左移作为读取地址；During the first-stage butterfly operation, each butterfly operation uses the same binary number of the operation counter as the read address, and the butterfly operation of the subsequent series is respectively the circular left shift of the read address of the same butterfly operation of the previous stage as the read address. read address;
按照所述运算计数器的计数，依次分别从上部存储器和下部存储器中，在运算计数器对应的读取地址读取离散数字信号并进行蝶形运算。According to the counting of the operation counter, the discrete digital signal is read from the upper memory and the lower memory respectively at the reading address corresponding to the operation counter in sequence, and the butterfly operation is performed.
上述方案中，所述运算器，具体用于：In the above scheme, the calculator is specifically used for:
按照蝶形运算数据读取地址以及所述读取地址先后顺序，将各次蝶形运算的结果间隔存入上部存储器和下部存储器；According to the read address of the butterfly operation data and the order of the read address, the results of each butterfly operation are stored in the upper memory and the lower memory at intervals;
同次蝶形运算的两组结果依次存入同一存储器。Two groups of results of the same butterfly operation are stored in the same memory in sequence.
上述方案中，所输出控制器，具体用于：In the above scheme, the output controller is specifically used for:
将位数等于蝶形运算级数的二进制数作为数据输出计数器，并从小到大计数；Use the binary number equal to the butterfly operation series as the data output counter, and count from small to large;
将去除最低位后的所述数据输出计数器的最高位移到最低位，并将所述完成移位的各二进制数作为排序的输出读取地址；Shifting the highest bit of the data output counter after removing the lowest bit to the lowest bit, and using the binary numbers that have been shifted as sorted output read addresses;
按所述输出读取地址排序，依次在各输出读取地址分别从上部存储器和下部存储器读取所述完成蝶形运算的数据。Sorting according to the output read addresses, reading the data that has completed the butterfly operation from the upper memory and the lower memory respectively at each output read address in sequence.
上述方案中，所述输出控制器，具体用于：In the above solution, the output controller is specifically used for:
将所述数据输出计数器的最低位作为上部存储器和下部存储器的读使能，按照所述数据输出计数器计数，间隔使能所述上部存储器和下部存储器，并从同一输出读取地址读取所述完成蝶形运算的数据。Use the lowest bit of the data output counter as the read enable of the upper memory and the lower memory, count according to the data output counter, enable the upper memory and the lower memory at intervals, and read the data from the same output read address The data to complete the butterfly operation.
本发明实施例所提供的FFT处理方法和装置，将离散数字信号序列中的各离散数字信号，按输入地址规则写入上部存储器和下部存储器中；按照运算读取地址规则，依次从上部存储器和下部存储器中分别读取一组离散数字信号进行蝶形运算，将蝶形运算结果按运算写入地址规则写入上部存储器和下部存储器中，直至完成蝶形运算所有级数的运算；按照输出地址规则，从上部存储器和下部存储器中读取完成蝶形运算的数据，将所述读取的数据确定为所述离散数字信号序列的FFT结果；所述存储器可以是简单双端口RAM。如此，采用简单双端口RAM实现了FFT，相对于现有的全功能双端口RAM方案，节省芯片资源、降低芯片功耗，提升芯片竞争力。In the FFT processing method and device provided by the embodiments of the present invention, each discrete digital signal in the discrete digital signal sequence is written into the upper memory and the lower memory according to the input address rules; Read a set of discrete digital signals in the lower memory for butterfly operation, and write the results of the butterfly operation into the upper and lower memory according to the operation write address rules until the operation of all stages of the butterfly operation is completed; according to the output address The rule is to read the data that has completed the butterfly operation from the upper memory and the lower memory, and determine the read data as the FFT result of the discrete digital signal sequence; the memory can be a simple dual-port RAM. In this way, FFT is realized by using simple dual-port RAM, which saves chip resources, reduces chip power consumption, and improves chip competitiveness compared with the existing full-function dual-port RAM solution.
附图说明Description of drawings
图1为本发明实施例FFT处理方法的流程示意图；FIG. 1 is a schematic flow diagram of an FFT processing method according to an embodiment of the present invention;
图2为本发明实施例全功能双端口RAM的端口示意图；Fig. 2 is a port schematic diagram of a full-featured dual-port RAM according to an embodiment of the present invention;
图3为本发明实施例采用全功能双端口RAM进行FFT处理的技术方案框图；3 is a block diagram of a technical solution for FFT processing using a full-featured dual-port RAM according to an embodiment of the present invention;
图4为本发明实施例简单双端口RAM的端口示意图；Fig. 4 is a port schematic diagram of a simple dual-port RAM according to an embodiment of the present invention;
图5为本发明实施例采用简单双端口RAM进行FFT处理的技术方案框图；Fig. 5 is a block diagram of a technical solution for FFT processing using a simple dual-port RAM according to an embodiment of the present invention;
图6为本发明实施例16点FFT运算流示意图；6 is a schematic diagram of a 16-point FFT operation flow according to an embodiment of the present invention;
图7为本发明实施例在离散数字信号序列输入过程地址控制器的处理示意图；7 is a schematic diagram of the processing of the address controller in the discrete digital signal sequence input process according to an embodiment of the present invention;
图8为本发明实施例在离散数字信号序列输入过程写入地址取值示意图；FIG. 8 is a schematic diagram of writing address values during the discrete digital signal sequence input process according to an embodiment of the present invention;
图9为本发明实施例蝶形运算过程中地址控制器读写地址控制示意图；Fig. 9 is a schematic diagram of the address controller reading and writing address control during the butterfly operation process of the embodiment of the present invention;
图10为本发明实施例蝶形运算中读写地址取值示意图；Fig. 10 is a schematic diagram of reading and writing address values in the butterfly operation according to the embodiment of the present invention;
图11为本发明实施例间隔性数据交换示意图；FIG. 11 is a schematic diagram of interval data exchange according to an embodiment of the present invention;
图12为本发明实施例处理结果输出过程地址控制器的处理示意图；Fig. 12 is a schematic diagram of the processing of the address controller in the process of outputting the processing results according to the embodiment of the present invention;
图13为本发明实施例输出读取地址取值示意图；FIG. 13 is a schematic diagram of outputting and reading address values according to an embodiment of the present invention;
图14为本发明实施例FFT处理装置的组成结构示意图。FIG. 14 is a schematic diagram of the composition and structure of an FFT processing device according to an embodiment of the present invention.
具体实施方式Detailed ways
本发明实施例中，将离散数字信号序列中的各离散数字信号，按输入地址规则写入上部存储器和下部存储器中；按照运算读取地址规则，依次从上部存储器和下部存储器中分别读取一组离散数字信号进行蝶形运算，将蝶形运算结果按运算写入地址规则写入上部存储器和下部存储器中，直至完成蝶形运算所有级数的运算；按照输出地址规则，从上部存储器和下部存储器中读取完成蝶形运算的数据，将所述读取的数据确定为所述离散数字信号序列的FFT结果。In the embodiment of the present invention, each discrete digital signal in the discrete digital signal sequence is written into the upper memory and the lower memory according to the input address rules; A group of discrete digital signals is used for butterfly operation, and the results of the butterfly operation are written into the upper memory and the lower memory according to the operation write address rules, until the operation of all stages of the butterfly operation is completed; according to the output address rules, the upper memory and the lower memory The data that has completed the butterfly operation is read from the memory, and the read data is determined as the FFT result of the discrete digital signal sequence.
下面结合实施例对本发明再作进一步详细的说明。The present invention will be described in further detail below in conjunction with the examples.
本发明实施例提供的FFT处理方法，如图1所示，所述方法包括：The FFT processing method provided by the embodiment of the present invention, as shown in Figure 1, the method includes:
步骤101：将离散数字信号序列中的各离散数字信号，按输入地址规则写入上部存储器和下部存储器中；Step 101: Write each discrete digital signal in the discrete digital signal sequence into the upper memory and the lower memory according to the input address rules;
这里，所述存储器可以是简单双端口RAM，简单双端口RAM相对于全功能双端口RAM消耗较少的资源，并且功耗也比较小；图2为现有FFT处理技术方案采用的全功能双端口RAM的端口图；通常FFT的点数决定了全功能双端口RAM的深度；如图3所示的全功能双端口RAM进行FFT处理的技术方案框图中，在处理点数为N的FFT时，需要两个深度为N的全功能双端口RAM作为乒乓缓存；FFT处理的离散数字信号序列数据输入时，存储于乒缓存中；然后，同时读取全功能双端口RAM中对应的两个数据进行蝶形运算，将运算后得到的两个数据再同时写入乓缓存中，直至第一级所有数据蝶形运算结束；到第二级蝶形运算阶段，则是从乓缓存中读取对应的两个数据进行蝶形运算，将运算后得到的两个数据再同时写入乒缓存中，直至第二级蝶形运算结束；后续蝶形运算以此类推；而相同深度的简单双端口RAM比全功能双端口RAM更加节省电路资源，更有利于节省资源和功耗。Here, the memory can be a simple dual-port RAM, and the simple dual-port RAM consumes less resources than the full-featured dual-port RAM, and the power consumption is also relatively small; The port diagram of the port RAM; usually the number of FFT points determines the depth of the full-featured dual-port RAM; as shown in Fig. Two full-featured dual-port RAMs with a depth of N are used as ping-pong buffers; when the discrete digital signal sequence data processed by FFT is input, it is stored in the ping-pong buffers; In the shape operation, the two data obtained after the operation are written into the pong buffer at the same time until the butterfly operation of all the data in the first level is completed; in the second stage of the butterfly operation, the corresponding two data are read from the pong buffer. Butterfly operation is performed on two data, and the two data obtained after the operation are written into the ping buffer at the same time, until the end of the second-level butterfly operation; the subsequent butterfly operation is analogous; and the simple dual-port RAM with the same depth is more efficient than the full Functional dual-port RAM saves circuit resources more, and is more conducive to saving resources and power consumption.
本发明实施例提出的FFT处理方法，是基于简单双端口RAM来实现的，简单双端口RAM的端口图如图4所示；可以采用如图5所示的技术方案框图实现基于简单双端口RAM的FFT处理。进一步的，可以使用两个深度为N/2的简单双端口RAM上部存储器(RAM1)和下部存储器(RAM2)，替代上述设计中的两个深度为N的全功能双端口RAM，节省了至少一半的存储单元，为对资源敏感的电路设计提供更实用的解决方案。如图5所示技术方案可以实现离散数字信号序列数据的串行输入，运算后串行输出；可以采用芯片内部的硬件逻辑来进行写入和读取地址的控制器；The FFT processing method proposed in the embodiment of the present invention is realized based on a simple dual-port RAM, and the port diagram of the simple dual-port RAM is as shown in Figure 4; FFT processing. Further, two simple dual-port RAM upper memory (RAM1) and lower memory (RAM2) with a depth of N/2 can be used to replace the two full-featured dual-port RAMs with a depth of N in the above design, saving at least half memory cells, providing a more practical solution for resource-sensitive circuit designs. The technical solution shown in Figure 5 can realize the serial input of discrete digital signal sequence data, and the serial output after operation; the hardware logic inside the chip can be used to write and read the address controller;
如图5所示技术方案框图中，在进行离散数字信号序列输入时，可以将位数等于蝶形运算级数的二进制数作为数据输入计数器，并从小到大计数；将所述数据输入计数器的最高位取反后的值和所述数据输入计数器的最高位分别作为上部存储器和下部存储器的写使能；将所述数据输入计数器去除所述最高位后剩余各位的倒序二进制数作为写入地址；按照所述数据输入计数器计数，依次将所述各离散数字信号按照所述数据输入计数器对应的写入地址写入所述上部存储器和下部存储器；In the block diagram of the technical solution shown in Figure 5, when the discrete digital signal sequence is input, the binary number whose number of digits is equal to the butterfly operation series can be used as the data input counter, and count from small to large; the data input counter is The reversed value of the highest bit and the highest bit of the data input counter are respectively used as the write enable of the upper memory and the lower memory; the reverse binary number of the remaining bits after the data input counter is removed from the highest bit is used as the write address ; According to the counting of the data input counter, sequentially write the discrete digital signals into the upper memory and the lower memory according to the write address corresponding to the data input counter;
进行N点FFT运算的数据串行输入时，N通常为2的整数次方；可以使用地址计数器A[M-1：0]对输入数据进行计数，其中M为进行蝶形运算的级数，根据FFT蝶形运算常识可知，计数器的最高位取反(！A[M-1])作为上部存储器的写使能，计数器的最高位A[M-1]作为下部存储器的写使能。计数器的其他位进行倒序(A[0]，A[1]…A[M-2])则作为两块RAM的写入地址。两个简单双端口RAM深度均为N/2；When the data of N-point FFT operation is serially input, N is usually an integer power of 2; the address counter A[M-1:0] can be used to count the input data, where M is the number of stages for butterfly operation, According to the common sense of FFT butterfly operation, The highest bit of the counter is inverted (!A[M-1]) as the write enable of the upper memory, and the highest bit A[M-1] of the counter is used as the write enable of the lower memory. The reverse order of the other bits of the counter (A[0], A[1]...A[M-2]) is used as the write address of the two RAMs. Both simple dual-port RAMs are N/2 deep;
以16点FFT处理为例，16点FFT运算的流图如图6所示，由图可知，N＝16，蝶形运算级数M为4；在离散数字信号序列输入过程中，芯片中地址控制器的处理框图如图7所示，使用地址计数器A[3：0]对输入数据进行计数。计数器的最高位取反(！A[3])作为简单双端口RAM1的写使能，计数器的最高位A[3]作为简单双端口RAM2的写使能。计数器的其他位进行倒序(A[0]，A[1]，A[2])则作为两块RAM的写入地址。两个简单双端口RAM深度均为8；具体写入址表如图8所示；计数器A[3：0]每计一次数，可以往计数器对应的写入地址中写入一组离散数字信号，直至计数结束。Taking 16-point FFT processing as an example, the flow diagram of 16-point FFT operation is shown in Figure 6. It can be seen from the figure that N=16, and the number of butterfly operation stages M is 4; The processing block diagram of the controller is shown in Figure 7, using the address counter A[3:0] to count the input data. The highest bit inversion of the counter (!A[3]) is used as the write enable of the simple dual-port RAM1, and the highest bit A[3] of the counter is used as the write enable of the simple dual-port RAM2. The reverse order of the other bits of the counter (A[0], A[1], A[2]) is used as the write address of the two RAMs. The depth of two simple dual-port RAMs is 8; the specific write address table is shown in Figure 8; each time the counter A[3:0] counts a number, a set of discrete digital signals can be written to the write address corresponding to the counter , until the count ends.
实际应用中，可以由芯片中的地址控制器结合数据选择器(MUX)等实现对上部存储器和下部存储器的写入控制。In practical applications, the address controller in the chip can be combined with a data selector (MUX) to realize writing control to the upper memory and the lower memory.
步骤102：按照运算读取地址规则，依次从上部存储器和下部存储器中分别读取一组离散数字信号进行蝶形运算，将蝶形运算结果按运算写入地址规则写入两个存储器中，直至完成蝶形运算所有级数的运算；Step 102: Read a set of discrete digital signals from the upper memory and the lower memory in turn according to the operation read address rule to perform butterfly operation, and write the butterfly operation result into the two memory according to the operation write address rule until Complete the operation of all series of butterfly operations;
将离散数字信号序列中的各离散数字信号写入上部存储器和下部存储器中后，可以进行蝶形运算；进行可以采用运算读取地址规则读取存储在所述上部存储器和下部存储器中离散数字信号进行蝶形运算，以符合图6所示的运算流图。可以将位数等于蝶形运算级数减1之差的二进制数作为运算计数器，并从小到大计数；第一级蝶形运算时，各次蝶形运算分别采用所述运算计数器相同二进制数作为读取地址，后续级数的蝶形运算分别以前级同次蝶形运算读取地址的循环左移作为读取地址；按照所述运算计数器的计数，依次分别从上部存储器和下部存储器中，在运算计数器对应的读取地址读取离散数字信号并进行蝶形运算；After writing each discrete digital signal in the discrete digital signal sequence into the upper memory and the lower memory, the butterfly operation can be performed; the discrete digital signal stored in the upper memory and the lower memory can be read using the operation read address rule The butterfly operation is performed to conform to the operation flow diagram shown in FIG. 6 . The binary number whose number of digits is equal to the difference of the butterfly operation series minus 1 can be used as an operation counter, and counted from small to large; during the first stage of butterfly operation, each butterfly operation uses the same binary number of the operation counter as the operation counter. Read the address, the butterfly operation of the subsequent series is respectively the circular left shift of the read address of the same butterfly operation of the previous stage as the read address; The reading address corresponding to the operation counter reads the discrete digital signal and performs butterfly operation;
具体的，在FFT运算阶段，可以同时各从RAM1和RAM2中根据读地址依次取出数据进行蝶形运算。对图6所示的每级蝶形运算的各次蝶形运算使用次序进行从上至下计数，表示为I[M-2：0]；在第一级运算中，该计数器的值亦可看作读取数据的RAM读地址，读出数据依次进行蝶形运算。在第二级运算时，可以将第一级读取地址进行循环左移，读取数据的读地址则为{I[M-3：0]，I[M-2]}，依次类推，逐级变化；Specifically, in the FFT operation stage, data can be sequentially fetched from RAM1 and RAM2 at the same time according to the read address to perform butterfly operation. The order of use of each butterfly operation of each stage of butterfly operation shown in Figure 6 is counted from top to bottom, expressed as I[M-2:0]; in the first stage of operation, the value of the counter can also be It is regarded as the RAM read address of the read data, and the read data is sequentially subjected to butterfly operation. In the second-level operation, the first-level read address can be circularly shifted to the left, and the read address of the read data is {I[M-3:0], I[M-2]}, and so on, one by one level change;
以16点FFT处理为例，在FFT运算阶段，芯片中地址控制器的处理框图如图9所示，同时从RAM1和RAM2中根据读地址依次取出数据进行蝶形运算。对每级蝶形运算的蝶形运算单元使用次序进行从上至下计数，表示为I[2：0]。在第一级运算中，该计数器的值亦可看作读取数据的RAM读地址，读出数据依次进行蝶形运算。在第二级运算时，读取数据的读地址则为{I[1：0]，I[2]}。依次类推，逐级变化；其具体读地址取值如图10所示，如在第一级的第二次运算中，计数器为001，可以同时从RAM1和RAM2的地址001中取出数据进行蝶形运算；在在第二级的第二次运算中，计数器为001，读取地址为第一级的第二次读取地址循环左移一位，即为010，可以同时从RAM1和RAM2的地址010中取出数据进行蝶形运算。Taking 16-point FFT processing as an example, in the FFT operation stage, the processing block diagram of the address controller in the chip is shown in Figure 9. At the same time, the data is sequentially fetched from RAM1 and RAM2 according to the read address for butterfly operation. The usage order of the butterfly operation units of each stage of butterfly operation is counted from top to bottom, expressed as I[2:0]. In the first stage of operation, the value of the counter can also be regarded as the RAM read address of the read data, and the read data is sequentially subjected to butterfly operation. In the second stage of operation, the read address for reading data is {I[1:0], I[2]}. By analogy, it changes step by step; the specific read address value is shown in Figure 10. For example, in the second operation of the first level, the counter is 001, and the data can be taken out from the address 001 of RAM1 and RAM2 at the same time for butterfly Operation; in the second operation of the second stage, the counter is 001, and the read address is shifted left by one bit in the second read address of the first stage, which is 010, which can be read from the addresses of RAM1 and RAM2 at the same time 010 to take out the data for butterfly operation.
对于蝶形运算的结果，可以按照运算写入地址规则写入上部存储器和下部存储器中，直至完成所有级数的蝶形运算。可以按照蝶形运算数据读取地址以及所述读取地址先后顺序，将各次蝶形运算的结果间隔存入上部存储器和下部存储器；同次蝶形运算的两组结果依次存入同一存储器；The result of the butterfly operation can be written into the upper memory and the lower memory according to the operation write address rule until the butterfly operation of all stages is completed. The results of each butterfly operation can be stored in the upper memory and the lower memory at intervals according to the read address of the butterfly operation data and the sequence of the read addresses; the two groups of results of the same butterfly operation are stored in the same memory in sequence;
具体的，设第一级第一次蝶形运算时，分别从RAM1和RAM2中取出进行蝶形运算的两路数据分别为X路和Y路，读取地址为000。在进行蝶形运算后，X路数据和Y路数据同时从蝶形运算单元中输出。此时，将蝶形运算后的Y路数据延后一个周期。然后X，Y两路数据通过数据选择器进行间隔性数据交换，将蝶形运算的两组结果，按照X路数据读取地址依次写入RAM1，即写入RAM1的000和001地址；与第一级第一次蝶形运算类似，第一级第二次的运算结果写入RAM2的000和001地址，后续同理间隔写入，第一级蝶形运算具体间隔性数据交换操作结果如图11所示；以16点FFT处理为例，蝶形运算后的写入地址如图10所示；Specifically, it is assumed that during the first butterfly operation of the first stage, two channels of data for butterfly operation are taken out from RAM1 and RAM2 respectively as X channel and Y channel, and the read address is 000. After performing the butterfly operation, the X-channel data and the Y-channel data are simultaneously output from the butterfly operation unit. At this time, the Y channel data after the butterfly operation is delayed by one cycle. Then X and Y two-way data are exchanged at intervals through the data selector, and the two sets of results of the butterfly operation are written into RAM1 in sequence according to the X-way data read address, that is, the 000 and 001 addresses of RAM1; The first-level butterfly operation is similar. The first-level and second-time operation results are written to the 000 and 001 addresses of RAM2, and the follow-up is similarly written at intervals. The specific interval data exchange operation results of the first-level butterfly operation are shown in the figure As shown in Figure 11; taking 16-point FFT processing as an example, the write address after the butterfly operation is shown in Figure 10;
如此，同时把Y路数据对应的写地址延后于X路数据对应的写地址一个时钟周期，那么，第一次蝶形运算得出的两个数据均存入到了RAM1中，第二次蝶形运算得出的两个数据均存入到了RAM2中，依此类推。这样处理的目的在于将下一级同时参与蝶形运算的两个数据分别存储在两个不同RAM中，避免存在同一个RAM中，导致下次取数据出现问题。在接下来的M-1级运算中均采用这种处理方式将蝶形运算后的数据回写到RAM1和RAM2；In this way, at the same time, the write address corresponding to the Y channel data is delayed by one clock cycle from the write address corresponding to the X channel data. Then, the two data obtained by the first butterfly operation are stored in RAM1, and the second butterfly operation The two data obtained by the shape operation are stored in RAM2, and so on. The purpose of this processing is to store the two data that simultaneously participate in the butterfly operation at the next level in two different RAMs, so as to avoid being stored in the same RAM, which may cause problems in the next data fetch. In the following M-1 level operations, this processing method is used to write back the data after the butterfly operation to RAM1 and RAM2;
完成第一级蝶形运算后，按照运算读取地址规则读取第二级用于运算的数据进行蝶形运算，按运算写入地址规则写入上部存储器和下部存储器中，不断重复，直至完成所有级数的蝶形运算。After completing the first-level butterfly operation, read the second-level data for operation according to the operation read address rule to perform butterfly operation, and write it into the upper memory and lower memory according to the operation write address rule, and repeat until it is completed Butterfly operations for all series.
步骤103：按照输出地址规则，从上部存储器和下部存储器中读取完成蝶形运算的数据，将所述读取的数据确定为所述离散数字信号序列的FFT结果；Step 103: According to the output address rule, read the data that has completed the butterfly operation from the upper memory and the lower memory, and determine the read data as the FFT result of the discrete digital signal sequence;
这里，可以将位数等于蝶形运算级数的二进制数作为数据输出计数器，并从小到大计数；将去除最低位后的所述数据输出计数器的最高位移到最低位，并将完成移位的各二进制数作为排序的输出读取地址；按所述输出读取地址排序，依次在各输出读取地址分别从上部存储器和下部存储器读取所述完成蝶形运算的数据；可以将所述数据输出计数器的最低位作为上部存储器和下部存储器的读使能，按照所述数据输出计数器计数，间隔使能所述上部存储器和下部存储器，并从同一输出读取地址读取所述完成蝶形运算的数据Here, the binary number whose number of digits is equal to the number of butterfly operations can be used as a data output counter, and counted from small to large; the highest bit of the data output counter after removing the lowest bit is shifted to the lowest bit, and the shifted Each binary number is used as the output read address of sorting; According to the sorting of the output read address, the data of completing the butterfly operation are read from the upper memory and the lower memory respectively at each output read address successively; the data can be The lowest bit of the output counter acts as a read enable for the upper and lower memory, counts the output counter as per the data, enables the upper and lower memory at intervals, and reads the complete butterfly operation from the same output read address The data
具体的，可以使用计数器K[M-1：0]对持续N个周期的读使能信号进行计数；由于数据分别存储在RAM1和RAM2中，而输出时是由一路输出，于是，可以给RAM1和RAM2相同的输出读取地址进行读取，让每个输出读取地址持续两个周期，在这两个周期内分别使能RAM1和RAM2，并对输出数据进行选择输出；其中，输出读取地址可以是将去除最高位后的将计数器K[M-1：0]的最高位移到最低位后的二进制数，并可以将完成移位的各二进制数作为排序的输出读取地址；Specifically, the counter K[M-1:0] can be used to count the read enable signal that lasts for N cycles; since the data are stored in RAM1 and RAM2 respectively, and the output is output by one channel, therefore, it can be given to RAM1 Read the same output read address as RAM2, let each output read address last for two cycles, enable RAM1 and RAM2 respectively in these two cycles, and select and output the output data; among them, the output read The address can be the binary number after the highest bit of the counter K[M-1:0] is shifted to the lowest bit after the highest bit is removed, and each binary number that has been shifted can be used as the sorted output read address;
以16点FFT处理为例，芯片中地址控制器的处理框图如图12所示，使用计数器K[3：0]对持续16个周期的读使能信号进行计数；由于数据分别存储在RAM1和RAM2中，而输出时是由一路输出；于是，给RAM1和RAM2相同的读地址信号进行读取，让每个读地址信号持续两个周期；在这两个周期内分别使能RAM1和RAM2，并对输出数据进行选择输出；其中，输出读取地址可以是将去除最高位后的将计数器K[3：0]的最高位移到最低位后的二进制数，并可以将完成移位的各二进制数作为排序的输出读取地址；具体读地址取值如图13所示，由图13可以，两个周期中，分别在RAM1和RAM2中读取了同一输出读取地址的数据，并串行输出，直至计数器完成计数，即读取了所有蝶形运算结果；Taking 16-point FFT processing as an example, the processing block diagram of the address controller in the chip is shown in Figure 12, and the counter K[3:0] is used to count the read enable signals lasting 16 cycles; since the data are stored in RAM1 and In RAM2, the output is output by one way; therefore, read the same read address signal for RAM1 and RAM2, and let each read address signal last for two cycles; enable RAM1 and RAM2 respectively in these two cycles, And select and output the output data; wherein, the output read address can be the binary number after the highest bit of the counter K[3:0] is shifted to the lowest bit after the highest bit is removed, and each binary number that has been shifted can be The number is used as the sorted output read address; the specific read address value is shown in Figure 13, and it can be seen from Figure 13 that in the two cycles, the data of the same output read address is read in RAM1 and RAM2 respectively, and serially output until the counter finishes counting, that is, all butterfly operation results are read;
实际应用中，可以由芯片中的地址控制器结合MUX等实现对上部存储器和下部存储器的读取控制。In practical applications, the address controller in the chip can be combined with MUX to realize the read control of the upper memory and the lower memory.
如此，由简单双端口RAM组成的技术方案完成了对所述离散数字信号序列的FFT处理。In this way, the technical solution consisting of simple dual-port RAM completes the FFT processing of the discrete digital signal sequence.
本发明实施例提供的FFT处理装置，如图14所示，所述装置包括：所述装置包括：输入控制器1401、运算器1402、输出控制器1403、上部存储器1404和下部存储器1405；其中，The FFT processing device provided by the embodiment of the present invention, as shown in FIG. 14 , the device includes: the device includes: an input controller 1401, an arithmetic unit 1402, an output controller 1403, an upper memory 1404, and a lower memory 1405; wherein,
所述输入控制器1401，用于将离散数字信号序列中的各离散数字信号，按输入地址规则写入上部存储器1404和下部存储器1405中；The input controller 1401 is used to write each discrete digital signal in the discrete digital signal sequence into the upper memory 1404 and the lower memory 1405 according to input address rules;
这里，所述存储器可以是简单双端口RAM，简单双端口RAM相对于全功能双端口RAM消耗较少的资源，并且功耗也比较小；图2为现有FFT处理技术方案采用的全功能双端口RAM的端口图；通常FFT的点数决定了全功能双端口RAM的深度；如图3所示的全功能双端口RAM进行FFT处理的技术方案框图中，在处理点数为N的FFT时，需要两个深度为N的全功能双端口RAM作为乒乓缓存；FFT处理的离散数字信号序列数据输入时，存储于乒缓存中；然后，同时读取全功能双端口RAM中对应的两个数据进行蝶形运算，将运算后得到的两个数据再同时写入乓缓存中，直至第一级所有数据蝶形运算结束；到第二级蝶形运算阶段，则是从乓缓存中读取对应的两个数据进行蝶形运算，将运算后得到的两个数据再同时写入乒缓存中，直至第二级蝶形运算结束；后续蝶形运算以此类推；而相同深度的简单双端口RAM比全功能双端口RAM更加节省电路资源，更有利于节省资源和功耗。Here, the memory can be a simple dual-port RAM, and the simple dual-port RAM consumes less resources than the full-featured dual-port RAM, and the power consumption is also relatively small; The port diagram of the port RAM; usually the number of FFT points determines the depth of the full-featured dual-port RAM; as shown in Fig. Two full-featured dual-port RAMs with a depth of N are used as ping-pong buffers; when the discrete digital signal sequence data processed by FFT is input, it is stored in the ping-pong buffers; In the shape operation, the two data obtained after the operation are written into the pong buffer at the same time until the butterfly operation of all the data in the first level is completed; in the second stage of the butterfly operation, the corresponding two data are read from the pong buffer. Butterfly operation is performed on two data, and the two data obtained after the operation are written into the ping buffer at the same time, until the end of the second-level butterfly operation; the subsequent butterfly operation is analogous; and the simple dual-port RAM with the same depth is more efficient than the full Functional dual-port RAM saves circuit resources more, and is more conducive to saving resources and power consumption.
本发明实施例提出的FFT处理方法，是基于简单双端口RAM来实现的，简单双端口RAM的端口图如图4所示；可以采用如图5所示的技术方案框图实现基于简单双端口RAM的FFT处理。进一步的，可以使用两个深度为N/2的简单双端口RAM上部存储器1404(RAM1)和下部存储器1405(RAM2)，替代上述设计中的两个深度为N的全功能双端口RAM，节省了至少一半的存储单元，为对资源敏感的电路设计提供更实用的解决方案。如图5所示技术方案可以实现离散数字信号序列数据的串行输入，运算后串行输出；可以采用芯片内部的硬件逻辑来进行写入和读取地址的控制器；The FFT processing method proposed in the embodiment of the present invention is realized based on a simple dual-port RAM, and the port diagram of the simple dual-port RAM is as shown in Figure 4; FFT processing. Further, two simple dual-port RAM upper memory 1404 (RAM1) and lower memory 1405 (RAM2) with a depth of N/2 can be used to replace two full-featured dual-port RAMs with a depth of N in the above design, saving at least half of the memory cells, providing a more practical solution for resource-sensitive circuit designs. The technical solution shown in Figure 5 can realize the serial input of discrete digital signal sequence data, and the serial output after operation; the hardware logic inside the chip can be used to write and read the address controller;
如图5所示技术方案框图中，在进行离散数字信号序列输入时，可以将位数等于蝶形运算级数的二进制数作为数据输入计数器，并从小到大计数；将所述数据输入计数器的最高位取反后的值和所述数据输入计数器的最高位分别作为上部存储器1404和下部存储器1405的写使能；将所述数据输入计数器去除所述最高位后剩余各位的倒序二进制数作为写入地址；按照所述数据输入计数器计数，依次将所述各离散数字信号按照所述数据输入计数器对应的写入地址写入所述上部存储器1404和下部存储器1405；In the block diagram of the technical solution shown in Figure 5, when the discrete digital signal sequence is input, the binary number whose number of digits is equal to the butterfly operation series can be used as the data input counter, and count from small to large; the data input counter is The value after the highest bit inversion and the highest bit of the data input counter are used as the write enable of the upper memory 1404 and the lower memory 1405 respectively; input address; according to the counting of the data input counter, sequentially write the discrete digital signals into the upper memory 1404 and the lower memory 1405 according to the write address corresponding to the data input counter;
进行N点FFT运算的数据串行输入时，N通常为2的整数次方；可以使用地址计数器A[M-1：0]对输入数据进行计数，其中M为进行蝶形运算的级数，根据FFT蝶形运算常识可知，计数器的最高位取反(！A[M-1])作为上部存储器1404的写使能，计数器的最高位A[M-1]作为下部存储器1405的写使能。计数器的其他位进行倒序(A[0]，A[1]…A[M-2])则作为两块RAM的写入地址。两个简单双端口RAM深度均为N/2；When performing N-point FFT operation data serial input, N is usually an integer power of 2; the input data can be counted using the address counter A[M-1:0], where M is the number of stages for butterfly operation, According to the common sense of FFT butterfly operation, Inversion of the highest bit of the counter (!A[M-1]) is used as the write enable of the upper memory 1404 , and the highest bit A[M-1] of the counter is used as the write enable of the lower memory 1405 . The reverse order of the other bits of the counter (A[0], A[1]...A[M-2]) is used as the write address of the two RAMs. Both simple dual-port RAMs are N/2 deep;
以16点FFT处理为例，16点FFT运算的流图如图6所示，由图可知，N＝16，蝶形运算级数M为4；在离散数字信号序列输入过程中，芯片中地址控制器的处理框图如图7所示，使用地址计数器A[3：0]对输入数据进行计数。计数器的最高位取反(！A[3])作为简单双端口RAM1的写使能，计数器的最高位A[3]作为简单双端口RAM2的写使能。计数器的其他位进行倒序(A[0]，A[1]，A[2])则作为两块RAM的写入地址。两个简单双端口RAM深度均为8；具体写入址表如图8所示；计数器A[3：0]每计一次数，可以往计数器对应的写入地址中写入一组离散数字信号，直至计数结束。Taking 16-point FFT processing as an example, the flow diagram of 16-point FFT operation is shown in Figure 6. It can be seen from the figure that N=16, and the number of butterfly operation stages M is 4; The processing block diagram of the controller is shown in Figure 7, using the address counter A[3:0] to count the input data. The highest bit inversion of the counter (!A[3]) is used as the write enable of the simple dual-port RAM1, and the highest bit A[3] of the counter is used as the write enable of the simple dual-port RAM2. The reverse order of the other bits of the counter (A[0], A[1], A[2]) is used as the write address of the two RAMs. The depth of two simple dual-port RAMs is 8; the specific write address table is shown in Figure 8; each time the counter A[3:0] counts a number, a set of discrete digital signals can be written to the write address corresponding to the counter , until the count ends.
实际应用中，所述输入控制器1401可以由芯片中的地址控制器结合MUX等实现对上部存储器1404和下部存储器1405的写入控制。In practical applications, the input controller 1401 can control writing to the upper memory 1404 and the lower memory 1405 by combining the address controller in the chip with MUX and the like.
所述运算器1402，用于按照运算读取地址规则，依次从上部存储器1404和下部存储器1405中分别读取一组离散数字信号进行蝶形运算，将蝶形运算结果按运算写入地址规则写入上部存储器1404和下部存储器1405中，直至完成蝶形运算所有级数的运算；The arithmetic unit 1402 is used to sequentially read a set of discrete digital signals from the upper memory 1404 and the lower memory 1405 according to the operation read address rule to perform butterfly operation, and write the result of the butterfly operation according to the operation write address rule. into the upper memory 1404 and the lower memory 1405 until the operation of all stages of the butterfly operation is completed;
将离散数字信号序列中的各离散数字信号写入上部存储器1404和下部存储器1405中后，可以进行蝶形运算；进行可以采用运算读取地址规则读取存储在所述上部存储器1404和下部存储器1405中离散数字信号进行蝶形运算，以符合图6所示的运算流图。可以将位数等于蝶形运算级数减1之差的二进制数作为运算计数器，并从小到大计数；第一级蝶形运算时，各次蝶形运算分别采用所述运算计数器相同二进制数作为读取地址，后续级数的蝶形运算分别以前级同次蝶形运算读取地址的循环左移作为读取地址；按照所述运算计数器的计数，依次分别从上部存储器1404和下部存储器1405中，在运算计数器对应的读取地址读取离散数字信号并进行蝶形运算；After each discrete digital signal in the discrete digital signal sequence is written in the upper memory 1404 and the lower memory 1405, a butterfly operation can be performed; the algorithm can be used to read the address stored in the upper memory 1404 and the lower memory 1405 Butterfly operation is performed on discrete digital signals in order to conform to the operation flow diagram shown in Figure 6. The binary number whose number of digits is equal to the difference of the butterfly operation series minus 1 can be used as an operation counter, and counted from small to large; during the first stage of butterfly operation, each butterfly operation uses the same binary number of the operation counter as the operation counter. Read the address, the butterfly operation of the subsequent series is respectively the circular left shift of the read address of the same butterfly operation of the previous stage as the read address; , read the discrete digital signal at the read address corresponding to the operation counter and perform butterfly operation;
具体的，在FFT运算阶段，可以同时各从RAM1和RAM2中根据读地址依次取出数据进行蝶形运算。对图6所示的每级蝶形运算的各次蝶形运算使用次序进行从上至下计数，表示为I[M-2：0]；在第一级运算中，该计数器的值亦可看作读取数据的RAM读地址，读出数据依次进行蝶形运算。在第二级运算时，可以将第一级读取地址进行循环左移，读取数据的读地址则为{I[M-3：0]，I[M-2]}，依次类推，逐级变化；Specifically, in the FFT operation stage, data can be sequentially fetched from RAM1 and RAM2 at the same time according to the read address to perform butterfly operation. The order of use of each butterfly operation of each stage of butterfly operation shown in Figure 6 is counted from top to bottom, expressed as I[M-2:0]; in the first stage of operation, the value of the counter can also be It is regarded as the RAM read address of the read data, and the read data is sequentially subjected to butterfly operation. In the second-level operation, the first-level read address can be circularly shifted to the left, and the read address of the read data is {I[M-3:0], I[M-2]}, and so on, one by one level change;
以16点FFT处理为例，在FFT运算阶段，芯片中地址控制器的处理框图如图9所示，同时从RAM1和RAM2中根据读地址依次取出数据进行蝶形运算。对每级蝶形运算的蝶形运算单元使用次序进行从上至下计数，表示为I[2：0]。在第一级运算中，该计数器的值亦可看作读取数据的RAM读地址，读出数据依次进行蝶形运算。在第二级运算时，读取数据的读地址则为{I[1：0]，I[2]}。依次类推，逐级变化；其具体读地址取值如图10所示，如在第一级的第二次运算中，计数器为001，可以同时从RAM1和RAM2的地址001中取出数据进行蝶形运算；在在第二级的第二次运算中，计数器为001，读取地址为第一级的第二次读取地址循环左移一位，即为010，可以同时从RAM1和RAM2的地址010中取出数据进行蝶形运算。Taking 16-point FFT processing as an example, in the FFT operation stage, the processing block diagram of the address controller in the chip is shown in Figure 9. At the same time, the data is sequentially fetched from RAM1 and RAM2 according to the read address for butterfly operation. The usage order of the butterfly operation units of each stage of butterfly operation is counted from top to bottom, expressed as I[2:0]. In the first stage of operation, the value of the counter can also be regarded as the RAM read address of the read data, and the read data is sequentially subjected to butterfly operation. In the second stage of operation, the read address for reading data is {I[1:0], I[2]}. By analogy, it changes step by step; the specific read address value is shown in Figure 10. For example, in the second operation of the first level, the counter is 001, and the data can be taken out from the address 001 of RAM1 and RAM2 at the same time for butterfly Operation; in the second operation of the second stage, the counter is 001, and the read address is shifted left by one bit in the second read address of the first stage, which is 010, which can be read from the addresses of RAM1 and RAM2 at the same time 010 to take out the data for butterfly operation.
对于蝶形运算的结果，可以按照运算写入地址规则写入上部存储器1404和下部存储器1405中，直至完成所有级数的蝶形运算。可以按照蝶形运算数据读取地址以及所述读取地址先后顺序，将各次蝶形运算的结果间隔存入上部存储器1404和下部存储器1405；同次蝶形运算的两组结果依次存入同一存储器；The result of the butterfly operation can be written into the upper memory 1404 and the lower memory 1405 according to the operation writing address rules until all stages of butterfly operations are completed. The results of each butterfly operation can be stored in the upper memory 1404 and the lower memory 1405 at intervals according to the read address of the butterfly operation data and the sequence of the read addresses; the two sets of results of the same butterfly operation are stored in the same memory;
具体的，设第一级第一次蝶形运算时，分别从RAM1和RAM2中取出进行蝶形运算的两路数据分别为X路和Y路，读取地址为000。在进行蝶形运算后，X路数据和Y路数据同时从蝶形运算单元中输出。此时，将蝶形运算后的Y路数据延后一个周期。然后X，Y两路数据通过数据选择器进行间隔性数据交换，将蝶形运算的两组结果，按照X路数据读取地址依次写入RAM1，即写入RAM1的000和001地址；与第一级第一次蝶形运算类似，第一级第二次的运算结果写入RAM2的000和001地址，后续同理间隔写入，第一级蝶形运算具体间隔性数据交换操作结果如图11所示；以16点FFT处理为例，蝶形运算后的写入地址如图10所示；Specifically, it is assumed that during the first butterfly operation of the first stage, two channels of data for butterfly operation are taken out from RAM1 and RAM2 respectively as X channel and Y channel, and the read address is 000. After performing the butterfly operation, the X-channel data and the Y-channel data are simultaneously output from the butterfly operation unit. At this time, the Y channel data after the butterfly operation is delayed by one cycle. Then X and Y two-way data are exchanged at intervals through the data selector, and the two sets of results of the butterfly operation are written into RAM1 in sequence according to the X-way data read address, that is, the 000 and 001 addresses of RAM1; The first-level butterfly operation is similar. The first-level and second-time operation results are written to the 000 and 001 addresses of RAM2, and the follow-up is similarly written at intervals. The specific interval data exchange operation results of the first-level butterfly operation are shown in the figure As shown in Figure 11; taking 16-point FFT processing as an example, the write address after the butterfly operation is shown in Figure 10;
如此，同时把Y路数据对应的写地址延后于X路数据对应的写地址一个时钟周期，那么，第一次蝶形运算得出的两个数据均存入到了RAM1中，第二次蝶形运算得出的两个数据均存入到了RAM2中，依此类推。这样处理的目的在于将下一级同时参与蝶形运算的两个数据分别存储在两个不同RAM中，避免存在同一个RAM中，导致下次取数据出现问题。在接下来的M-1级运算中均采用这种处理方式将蝶形运算后的数据回写到RAM1和RAM2；In this way, at the same time, the write address corresponding to the Y channel data is delayed by one clock cycle from the write address corresponding to the X channel data. Then, the two data obtained by the first butterfly operation are stored in RAM1, and the second butterfly operation The two data obtained by the shape operation are stored in RAM2, and so on. The purpose of this processing is to store the two data that simultaneously participate in the butterfly operation at the next level in two different RAMs, so as to avoid being stored in the same RAM, which may cause problems in the next data fetch. In the following M-1 level operations, this processing method is used to write back the data after the butterfly operation to RAM1 and RAM2;
完成第一级蝶形运算后，按照运算读取地址规则读取第二级用于运算的数据进行蝶形运算，按运算写入地址规则写入上部存储器1404和下部存储器1405中，不断重复，直至完成所有级数的蝶形运算。After completing the first-level butterfly operation, read the second-level data for operation according to the operation read address rule to perform butterfly operation, and write it into the upper memory 1404 and the lower memory 1405 according to the operation write address rule, and repeat continuously. Until the butterfly operation of all series is completed.
所述输出控制器1403，用于按照输出地址规则，从上部存储器1404和下部存储器1405中读取完成蝶形运算的数据，将所述读取的数据确定为所述离散数字信号序列的FFT结果；The output controller 1403 is configured to read the data that has completed the butterfly operation from the upper memory 1404 and the lower memory 1405 according to the output address rule, and determine the read data as the FFT result of the discrete digital signal sequence ;
这里，可以将位数等于蝶形运算级数的二进制数作为数据输出计数器，并从小到大计数；将去除最低位后的所述数据输出计数器的最高位移到最低位，并将完成移位的各二进制数作为排序的输出读取地址；按所述输出读取地址排序，依次在各输出读取地址分别从上部存储器1404和下部存储器1405读取所述完成蝶形运算的数据；可以将所述数据输出计数器的最低位作为上部存储器1404和下部存储器1405的读使能，按照所述数据输出计数器计数，间隔使能所述上部存储器1404和下部存储器1405，并从同一输出读取地址读取所述完成蝶形运算的数据；Here, the binary number whose number of digits is equal to the number of butterfly operations can be used as a data output counter, and counted from small to large; the highest bit of the data output counter after removing the lowest bit is shifted to the lowest bit, and the shifted Each binary number is used as the output read address of sorting; According to the sorting of the output read address, read the data of completing the butterfly operation from the upper memory 1404 and the lower memory 1405 respectively at each output read address successively; The lowest bit of the data output counter is used as the read enable of the upper memory 1404 and the lower memory 1405, counting according to the data output counter, enabling the upper memory 1404 and the lower memory 1405 at intervals, and reading from the same output read address The data for completing the butterfly operation;
具体的，可以使用计数器K[M-1：0]对持续N个周期的读使能信号进行计数；由于数据分别存储在RAM1和RAM2中，而输出时是由一路输出，于是，可以给RAM1和RAM2相同的输出读取地址进行读取，让每个输出读取地址持续两个周期，在这两个周期内分别使能RAM1和RAM2，并对输出数据进行选择输出；其中，输出读取地址可以是将去除最高位后的将计数器K[M-1：0]的最高位移到最低位后的二进制数，并可以将完成移位的各二进制数作为排序的输出读取地址；Specifically, the counter K[M-1:0] can be used to count the read enable signal that lasts for N cycles; since the data are stored in RAM1 and RAM2 respectively, and the output is output by one channel, therefore, it can be given to RAM1 Read the same output read address as RAM2, let each output read address last for two cycles, enable RAM1 and RAM2 respectively in these two cycles, and select and output the output data; among them, the output read The address can be the binary number after the highest bit of the counter K[M-1:0] is shifted to the lowest bit after the highest bit is removed, and each binary number that has been shifted can be used as the sorted output read address;
以16点FFT处理为例，芯片中地址控制器的处理框图如图12所示，使用计数器K[3：0]对持续16个周期的读使能信号进行计数；由于数据分别存储在RAM1和RAM2中，而输出时是由一路输出；于是，给RAM1和RAM2相同的读地址信号进行读取，让每个读地址信号持续两个周期；在这两个周期内分别使能RAM1和RAM2，并对输出数据进行选择输出；其中，输出读取地址可以是将去除最高位后的将计数器K[3：0]的最高位移到最低位后的二进制数，并可以将完成移位的各二进制数作为排序的输出读取地址；具体读地址取值如图13所示，由图13可以，两个周期中，分别在RAM1和RAM2中读取了同一输出读取地址的数据，并串行输出，直至计数器完成计数，即读取了所有蝶形运算结果；Taking 16-point FFT processing as an example, the processing block diagram of the address controller in the chip is shown in Figure 12, and the counter K[3:0] is used to count the read enable signals lasting 16 cycles; since the data are stored in RAM1 and In RAM2, the output is output by one way; therefore, read the same read address signal for RAM1 and RAM2, and let each read address signal last for two cycles; enable RAM1 and RAM2 respectively in these two cycles, And select and output the output data; wherein, the output read address can be the binary number after the highest bit of the counter K[3:0] is shifted to the lowest bit after the highest bit is removed, and each binary number that has been shifted can be The number is used as the sorted output read address; the specific read address value is shown in Figure 13, and it can be seen from Figure 13 that in the two cycles, the data of the same output read address is read in RAM1 and RAM2 respectively, and serially output until the counter finishes counting, that is, all butterfly operation results are read;
实际应用中，所述输出控制器1403可以由芯片中的地址控制器结合MUX等实现对上部存储器1404和下部存储器1405的读取控制。In practical applications, the output controller 1403 can control the reading of the upper memory 1404 and the lower memory 1405 by combining the address controller in the chip with MUX and the like.
如此，由简单双端口RAM组成的技术方案完成了对所述离散数字信号序列的FFT处理。In this way, the technical solution consisting of simple dual-port RAM completes the FFT processing of the discrete digital signal sequence.
在实际应用中，所述输入控制器1401、运算器1402和输出控制器1403均可以由芯片内部的硬件逻辑、软件逻辑等实现。In practical applications, the input controller 1401, the arithmetic unit 1402 and the output controller 1403 can all be implemented by hardware logic, software logic, etc. inside the chip.
以上所述，仅为本发明的最佳实施例而已，并非用于限定本发明的保护范围，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。The above is only the best embodiment of the present invention, and is not used to limit the protection scope of the present invention. Any modification, equivalent replacement and improvement made within the spirit and principle of the present invention shall be included in the within the protection scope of the present invention.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710023363.0ACN108304347A (en) | 2017-01-12 | 2017-01-12 | A kind of Fast Fourier Transform (FFT) treating method and apparatus |
| PCT/CN2017/099342WO2018129930A1 (en) | 2017-01-12 | 2017-08-28 | Fast fourier transform processing method and device, and computer storage medium |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710023363.0ACN108304347A (en) | 2017-01-12 | 2017-01-12 | A kind of Fast Fourier Transform (FFT) treating method and apparatus |
| Publication Number | Publication Date |
|---|---|
| CN108304347Atrue CN108304347A (en) | 2018-07-20 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710023363.0APendingCN108304347A (en) | 2017-01-12 | 2017-01-12 | A kind of Fast Fourier Transform (FFT) treating method and apparatus |
| Country | Link |
|---|---|
| CN (1) | CN108304347A (en) |
| WO (1) | WO2018129930A1 (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111435383A (en)* | 2020-01-14 | 2020-07-21 | 珠海市杰理科技股份有限公司 | Data processing method, data processing chip and electronic equipment |
| CN111737638A (en)* | 2020-06-11 | 2020-10-02 | Oppo广东移动通信有限公司 | Data processing method and related device based on Fourier transform |
| CN114911828A (en)* | 2022-04-22 | 2022-08-16 | 哲库科技(北京)有限公司 | Data processing method for Fourier transform and related device |
| CN118626411A (en)* | 2024-08-13 | 2024-09-10 | 北京大有半导体有限责任公司 | Data reading and writing method, device, system and storage medium based on sliding FFT |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112487352B (en)* | 2020-12-18 | 2022-06-10 | 清华大学 | Fast Fourier transform operation method on reconfigurable processor and reconfigurable processor |
| CN113918875B (en)* | 2021-09-23 | 2024-05-03 | 同致电子科技（厦门）有限公司 | Fast processing method of two-dimensional FFT |
| CN114201725B (en)* | 2021-12-14 | 2023-04-07 | 电子科技大学 | Narrowband communication signal processing method based on multimode reconfigurable FFT |
| CN118069097B (en)* | 2022-12-20 | 2025-02-21 | 深圳市速腾聚创科技有限公司 | Data writing method, device, terminal equipment and storage medium |
| CN116136602B (en)* | 2023-04-14 | 2023-06-23 | 福建福大北斗通信科技有限公司 | Device and method for in-band spectrum amplitude and time delay consistency of Beidou anti-interference channel |
| CN117389946B (en)* | 2023-11-09 | 2024-05-28 | 合肥灿芯科技有限公司 | FFT (fast Fourier transform) implementation structure capable of dynamically expanding points |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020178195A1 (en)* | 2001-05-23 | 2002-11-28 | Lg Electronics Inc. | Memory address generating apparatus and method |
| CN1655143A (en)* | 2004-02-11 | 2005-08-17 | 三星电子株式会社 | Fast Fourier transform processor and method using half the size of memory |
| CN101650706A (en)* | 2009-06-30 | 2010-02-17 | 重庆重邮信科通信技术有限公司 | Method and device for calculating FFT branch |
| CN103176949A (en)* | 2011-12-20 | 2013-06-26 | 中国科学院深圳先进技术研究院 | Circuit and method for achieving fast Fourier transform (FFT) / inverse fast Fourier transform (IFFT) |
| CN103970718A (en)* | 2014-05-26 | 2014-08-06 | 苏州威士达信息科技有限公司 | Quick Fourier transformation implementation device and method |
| US9244886B1 (en)* | 2008-07-14 | 2016-01-26 | The Mathworks, Inc. | Minimum resource fast fourier transform |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020178195A1 (en)* | 2001-05-23 | 2002-11-28 | Lg Electronics Inc. | Memory address generating apparatus and method |
| CN1655143A (en)* | 2004-02-11 | 2005-08-17 | 三星电子株式会社 | Fast Fourier transform processor and method using half the size of memory |
| US9244886B1 (en)* | 2008-07-14 | 2016-01-26 | The Mathworks, Inc. | Minimum resource fast fourier transform |
| CN101650706A (en)* | 2009-06-30 | 2010-02-17 | 重庆重邮信科通信技术有限公司 | Method and device for calculating FFT branch |
| CN103176949A (en)* | 2011-12-20 | 2013-06-26 | 中国科学院深圳先进技术研究院 | Circuit and method for achieving fast Fourier transform (FFT) / inverse fast Fourier transform (IFFT) |
| CN103970718A (en)* | 2014-05-26 | 2014-08-06 | 苏州威士达信息科技有限公司 | Quick Fourier transformation implementation device and method |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111435383A (en)* | 2020-01-14 | 2020-07-21 | 珠海市杰理科技股份有限公司 | Data processing method, data processing chip and electronic equipment |
| CN111435383B (en)* | 2020-01-14 | 2023-06-20 | 珠海市杰理科技股份有限公司 | Data processing method, data processing chip and electronic equipment |
| CN111737638A (en)* | 2020-06-11 | 2020-10-02 | Oppo广东移动通信有限公司 | Data processing method and related device based on Fourier transform |
| CN114911828A (en)* | 2022-04-22 | 2022-08-16 | 哲库科技(北京)有限公司 | Data processing method for Fourier transform and related device |
| CN118626411A (en)* | 2024-08-13 | 2024-09-10 | 北京大有半导体有限责任公司 | Data reading and writing method, device, system and storage medium based on sliding FFT |
| CN118626411B (en)* | 2024-08-13 | 2024-12-06 | 北京大有半导体有限责任公司 | Data read-write method, device, system and storage medium based on sliding FFT |
| Publication number | Publication date |
|---|---|
| WO2018129930A1 (en) | 2018-07-19 |
| Publication | Publication Date | Title |
|---|---|---|
| CN108304347A (en) | A kind of Fast Fourier Transform (FFT) treating method and apparatus | |
| CN101729463A (en) | Hardware device and method for implementing Fourier transform and Fourier inverse transform | |
| CN110674927A (en) | A data reorganization method for systolic array structure | |
| CN112307421B (en) | Base 4 frequency extraction fast Fourier transform processor | |
| CN111562898A (en) | Multi-stage merging and sorting method based on FPGA | |
| Liu et al. | Towards high-bandwidth-utilization spmv on fpgas via partial vector duplication | |
| CN111258535A (en) | Ordering method for FPGA implementation | |
| CN114528111A (en) | FPGA chip for data recall and data recall method | |
| CN104504205B (en) | A kind of two-dimentional dividing method of the parallelization of symmetrical FIR algorithm and its hardware configuration | |
| WO2018027706A1 (en) | Fft processor and algorithm | |
| CN103034621B (en) | The address mapping method of base 2 × K parallel FFT framework and system | |
| CN111045727B (en) | Processing unit array based on nonvolatile memory calculation and calculation method thereof | |
| CN106383807B (en) | A kind of fft processor | |
| CN115495152A (en) | Memory computing circuit with variable length input | |
| CN106843803A (en) | A kind of full sequence accelerator and application based on merger tree | |
| CN118245431A (en) | A storage and calculation integrated circuit with configurable logic operation based on SRAM | |
| CN113222129A (en) | Convolution operation processing unit and system based on multi-level cache cyclic utilization | |
| CN107133194A (en) | Configurable FFT/IFFT coprocessors based on hybrid radix | |
| CN102129419B (en) | Based on the processor of fast fourier transform | |
| CN106021171A (en) | An SM4-128 secret key extension realization method and system based on a large-scale coarseness reconfigurable processor | |
| US20140089370A1 (en) | Parallel bit reversal devices and methods | |
| CN102929837A (en) | High-speed fixed point fast fourier transformation (FFT) processor based on field programmable gate array (FPGA) and processing method for high-speed fixed point FFT processor | |
| CN109343826B (en) | A reconfigurable processor computing unit for deep learning | |
| CN109117114A (en) | A kind of low complex degree approximation multiplier based on look-up table | |
| CN101236488A (en) | Cooperative distributed processing method and device |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | Application publication date:20180720 | |
| RJ01 | Rejection of invention patent application after publication |