Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

On the design of VLSI arrays for discrete Fourier transform

On the design of VLSI arrays for discrete Fourier transform

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings G (Circuits, Devices and Systems) — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In this paper the design of VLSI arrays for discrete Fourier transform (DFT) is investigated through three topics: (i) algorithm exploitation, derivation and analysis, (ii) array realisation, and (iii) schemes to calculate arbitrarily long length DFT using a reasonable sized array. Four DFT systolic algorithms are examined and compared in terms of computing parallelism and computational complexity. Among the four algorithms, one is newly proposed. The new one exhibits much higher computing parallelism and lower computational complexity than the other three, but is applicable when the DFT length is prime. Based on the four algorithms, seven systolic arrays and seven two-level pipelined systolic arrays are devised. The outstanding features of these arrays are that the number of I/O channels is independent of the DFT length and the time overhead in manipulating consecutive data bundles are eliminated. Two schemes are presented to calculate long-length DFT using arrays with a reasonable number of processing elements. Performance of different algorithms, arrays and schemes is compared and summarised in six tables to serve as the selection criteria for different applications.

References

    1. 1)
      • H.V. Jagadish , S.K. Rao , T. Kailath . Array architecture for iterative algorithms. IEEE Proc. , 9 , 1304 - 1321
    2. 2)
      • S.K. Rao , T. Kailath . Regular iterative algorithms and their implementation on processor arrays. Proc. IEEE , 3 , 256 - 269
    3. 3)
      • C. Mead , L. Conway . , Introduction to VLSI systems.
    4. 4)
      • H.T. Kung . Why systolic architectures ?. Comput. Mag. , 1 , 37 - 45
    5. 5)
      • Jen, C.-W., Hsu, H.Y.: `The design of a systolic array with tags input', International Symposium on Circuits and Systems, 1988, Finland, p. 2263–2266.
    6. 6)
      • L.H. Thomas . (1963) Using a computer to solve problems in physics, Applications of Digital Computers.
    7. 7)
      • G.L. Li , B.W. Wah . The design of optimal systolic arrays. IEEE Trans. Comput. , 66 - 77
    8. 8)
      • I.J. Good . The interaction algorithm and practical Fourier analysis. J. Royal Statist. Soc. , 361 - 375
    9. 9)
      • S.Y. Kung , S.C. Lo , P.S. Lewis . Optimum systolic design for transitive closure and shortest path problems. IEEE Trans. Comput. , 5 , 603 - 614
    10. 10)
      • T.E. Curtis , J.T. Wickenden . Hardware-based Fourier transforms: algorithms and architectures. IEE Proc. , 5 , 423 - 432
    11. 11)
      • M.C. Chen . A design methodology for synthesizing parallel algorithms and architectures. J. Parallel & Distrib. Comput. , 461 - 491
    12. 12)
      • C.-M. Liu , C.-W. Jen . On the design of algorithm-based fault-tolerant VLSI array processor. IEE Proc. , 6 , 539 - 547
    13. 13)
      • Delosome, J.M., Ipsen, I.C.F.: `An illustration of a methodology for the construction of efficient systolic architectures in VLSI', Proceedings of the 2nd International Symposium on VLSI Technology, Systems and Applications, 1985, Taipei, p. 268–273.
    14. 14)
      • Winograd, S.: `On computing the discrete Fourier transform', Proceedings of the National Academy of Science, 1976, USA, 73, p. 1005–1006.
    15. 15)
      • J.A. Beraldin , T. Aboulnasr , W. Steenaart . Efficient one-dimensional systolic array realization of discrete Fourier transform. IEEE Trans. , 1 , 95 - 100
    16. 16)
      • L.W. Chang , M.Y. Chen . A new systolic array for discrete Fourier transform. IEEE Trans. ASSP , 10 , 1665 - 1667
    17. 17)
      • H.T. Kung , M.S. Lam . Wafer scale integration and two-level pipelined implementations of systolic arrays. J. Parallel and Distrib. Comput. , 32 - 64
    18. 18)
      • C.-M. Liu , C.-W. Jen . , Hierarchic al synthesis of two-level pipelined systolic arrays.
    19. 19)
      • C.D. Thompson . Fourier transforms in VLSI. IEEE Trans. Comput. , 1 , 1047 - 1057
    20. 20)
      • Quinton, P.: `Automatic synthesis of systolic arrays from recurrence equations', Proceedings of the 11th Annual Symposium on Computer Architecture, p. 208–214.
    21. 21)
      • N.I. Cho , S.U. Lee . DCT algorithms for VLSI parallel implementations. IEEE Trans. ASSP , 1 , 121 - 127
    22. 22)
      • S. Winograd . On computing the discrete Fourier transform. Math. Comput. , 175 - 199
    23. 23)
      • Bayoumi, M.A., Jullien, G.A., Miller, W.C.: `A VLSI array for computing the DFT based on RNS', Proceedings of ICASSP 86, Tokyo, p. 2147–2150.
    24. 24)
      • M.H. Lee , Y. Yasuda . New 2D systolic array algorithm for DCT/DST. Electron. Lett. , 1702 - 1703
    25. 25)
      • Jen, C.-W., Liu, C.-M.: `Two-level pipeline design for image resampling', International Conference on ASSP, 1989, Glasgow, Scotland, p. 2441–2444.
    26. 26)
      • Kung, H.T.: `Special purpose devices for signal and image processing: An opportunity in very large scale integration (VLSI)', Proceedings of SPIE, 1980, 241, p. 76–84, (Real Time Signal Processing III).
    27. 27)
      • J.A.B. Fortes , D.I. Moldovan . Parallelism detection and algorithm transformation techniques useful for VLSI architecture design. J. Parallel Distrib. Comput. , 277 - 301
    28. 28)
      • Rader, C.M.: `Discrete Fourier transforms when the number of data samples is prime', Proc. IEEE, 1968, p. 1107–1108.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-g-2.1992.0084
Loading

Related content

content/journals/10.1049/ip-g-2.1992.0084
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address