System and method for zero contention memory bank access in a reorder stage in mixed radix discrete fourier transform
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-012/00
G06F-003/06
G06F-017/14
출원번호
US-0612742
(2015-02-03)
등록번호
US-9459812
(2016-10-04)
발명자
/ 주소
Dvoretzki, Noam
Kaplan, Zeev
출원인 / 주소
Ceva D.S.P. Ltd.
대리인 / 주소
Pearl Cohen Zedek Latzer Baratz LLP
인용정보
피인용 횟수 :
0인용 특허 :
7
초록▼
Device and method for writing Discrete Fourier transform (DFT) samples in a memory in a reorder stage, the memory includes memory banks, each having a dedicated address generator. The method includes: dividing the DFT samples into R(reorder) equally sized segments, where R(reorder) is the radix valu
Device and method for writing Discrete Fourier transform (DFT) samples in a memory in a reorder stage, the memory includes memory banks, each having a dedicated address generator. The method includes: dividing the DFT samples into R(reorder) equally sized segments, where R(reorder) is the radix value of the reorder stage of the DFT; checking whether a number of butterfly computations per cycle of a reorder stage of the DFT operation times R(reorder), denoted as P, is not larger than the number of segments; if P is larger than the number of segments: further dividing the segments or sub-segments into X equally sized sub-segments, where X is a radix value of a next stage of the DFT operation until P is not larger than the number of sub-segments; and mapping the sub-segments to the memory, each in a separate row, with an offset that includes segment offset and sub-segment offset.
대표청구항▼
1. A method for writing Discrete Fourier transform (DFT) samples into a memory by a logic circuit in a reorder stage of a DFT operation, the memory being arranged as an array, wherein each column of the array is a memory bank, and wherein each memory bank has a dedicated address generator, the metho
1. A method for writing Discrete Fourier transform (DFT) samples into a memory by a logic circuit in a reorder stage of a DFT operation, the memory being arranged as an array, wherein each column of the array is a memory bank, and wherein each memory bank has a dedicated address generator, the method comprising: dividing the DFT samples into segments, based on R(reorder), where R(reorder) is a radix value of a reorder stage of the DFT operation;mapping the segments to the memory, wherein each segment is mapped with a segment offset with reference to first memory bank, to decrease bank contentions, wherein the segment offset is based on a number of butterfly computations per cycle of the reorder stage of the DFT operation; andwriting the DFT samples into the memory based on the mapping. 2. The method of claim 1, wherein dividing the DFT samples into segments comprises dividing the DFT samples into R(reorder) equally sized segments. 3. The method of claim 2, wherein the segment offset equals a segment number starting from 0, times the number of butterfly computations per cycle of the reorder stage of the DFT operation. 4. The method of claim 3, comprising: checking whether a number of butterfly computations per cycle of the reorder stage of the DFT operation times R(reorder), denoted as P, is not larger than the number of segments; andif P is larger than the number of segments then further dividing the segments into sub-segments and mapping the sub-segments to the memory with a sub-segment offset with reference to the segment offset, to further decrease bank contentions. 5. The method of claim 4, wherein further dividing comprises: dividing the segments into next-radix-value equally sized sub-segments until P is not larger than the number of segments. 6. The method of claim 5, wherein the sub-segment offset is incremental. 7. The method of claim 1, comprising providing the mapping to the dedicated address generators, wherein writing the DFT samples into the memory is performed using the dedicated address generators. 8. A method for writing Discrete Fourier transform (DFT) samples in a memory by a logic circuit in a reorder stage of a DFT operation, the memory being arranged as an array, wherein each column of the array is a memory bank, and wherein each memory bank has a dedicated address generator, the method comprising: dividing the DFT samples into R(reorder) equally sized segments, where R(reorder) is radix value of the reorder stage of the DFT;checking whether a number of butterfly computations per cycle of a reorder stage of the DFT operation times R(reorder), denoted as P, is not larger than number of segments;if P is not larger than the number of segments, then mapping the segments to the memory, with a segment offset with reference to first memory bank; andif P is larger than the number of segments then: further dividing the current segments or sub-segments into X equally sized sub-segments, where X is a radix value of a next stage of the DFT operation until P is not larger than the number of sub-segments; andmapping the sub-segments to the memory, with a sub-segment offset in addition to the segment offset of the corresponding segment. 9. The method of claim 8, wherein the segment offset equals a segment number starting from 0 times the number of butterfly computations per cycle of the reorder stage of the DFT operation and the sub-segment offset is incremental. 10. The method of claim 8, wherein each of the segments and sub-segments is mapped to a separate row. 11. The method of claim 8, comprising: writing the DFT samples into the memory based on the mapping. 12. The method of claim 8, wherein writing the DFT samples into the memory is performed using the dedicated address generators. 13. The method of claim 8, wherein the reorder stage is a first stage. 14. The method of claim 8, wherein each segment and sub-segment is mapped to a separate row. 15. An integrated circuit for calculating Discrete Fourier transform (DFT), the integrated circuit comprising: a memory arranged as an array, wherein each column of the array is a memory bank;dedicated address generators, each associated with one of the memory banks; anda logic circuit configured to:divide the DFT samples into R(reorder) equally sized segments, where R(reorder) is radix value of the reorder stage of the DFT;check whether a number of butterfly computations per cycle of a reorder stage of the DFT operation times R(reorder), denoted as P, is not larger than number of segments;if P is not larger than number of segments, then map the segments to the memory, with a segment offset with reference to first memory bank; andif P is larger than the number of segments then: further divide the current segments or sub-segments into X equally sized sub-segments, where X is a radix value of a next stage of the DFT operation until P is not larger than the number of sub-segments; andmap the sub-segments to the memory, with a sub-segment offset in addition to the segment offset of the corresponding segment. 16. The integrated circuit of claim 15, wherein the sub-segment offset is incremental. 17. The integrated circuit of claim 15, wherein the segment offset equals a segment number starting from 0, times the number of butterfly computations per cycle of the reorder stage of the DFT operation. 18. The integrated circuit of claim 15, wherein the logic circuit is configured to provide the mapping of the DFT samples to the dedicated address generators, and wherein the dedicated address generators are configured to write the DFT samples into the memory according to the mapping. 19. The integrated circuit of claim 15, wherein each segment and sub-segment is mapped to a separate row. 20. The integrated circuit of claim 15, wherein the reorder stage is a first stage.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (7)
Cope Stephen N. (Farnborough GB2), Discrete Fourier transform with non-tumbled output.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.