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

Computation of prime factor DFT and DHT/DCCT algorithms using cyclic and skew-cyclic bit-serial semisystolic IC convolvers

Computation of prime factor DFT and DHT/DCCT algorithms using cyclic and skew-cyclic bit-serial semisystolic IC convolvers

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.

The paper presents the results of a study of the use of cyclic and skew-cyclic convolvers for the evaluation of the subspace discrete Fourier transforms (DFT) and discrete Hartley transform (DHT) modules resulting from a prime factor decomposition of the DFT and the DHT/discrete cas-cas transform (DCCT), respectively. The method of Rader is employed to convert the subspace DFT/DHT modules into cyclic convolutions (CCs). These are further dissected into CCs and skew-cyclic convolutions (SCCs), respectively, of length ½(Ni − 1), where Ni is the DFT/DHT module length in the ith stage. That allows both real and complex DFT modules, as well as DHT modules, to be computed with the same convolver structure, by a simple reconfiguration of a recombination stage.This has important consequences for hardware implementations as only one type of convolver needs to be fabricated. A family of VLSI building block processors (BBPs) with pipelined bit-serial arithmetic is proposed. All inner products are computed in parallel within each BBP, resulting in a throughput rate inversely proportional to ½(Ni + 1). This leads to easy load balancing, which is discussed first in the context of a array machine and then in that of a multiplexed pipelined machine.

References

    1. 1)
      • D.C. Perkins . A separable Hartley-like transform in two or more dimensions. Proc. IEEE , 8 , 1127 - 1129
    2. 2)
      • J.H. McClellan , H. Nawab . (1979) Complex general-N Winograd Fourier transform algorithm (WFTA), Programs for digital signal processing.
    3. 3)
      • J. Hekrdla . Index transforms for N-dimensional DFT's. Numer. Math. , 469 - 480
    4. 4)
      • Johnson, H.W., Burrus, C.S.: `Large DFT modules: 11, 13, 17, 19, and 25', 8105, Report, 13 December 1981.
    5. 5)
      • I.J. Good . The interaction algorithm and practical Fourier analysis. J. R. Statist. Soc. , 361 - 372
    6. 6)
      • L.H. Thomas . (1963) Using computers to solve problems in physics, Applications of digital computers.
    7. 7)
      • Y. Chikada , M. Ishiguro , H. Hirabayashi , M. Morimoto , K. Morita , T. Kanzavwa , H. Iwashita , K. Nakazima , S. Ishikawa , T. Takahashi , K. Handa , T. Kasuga , S. Okumura , T. Miyazawa , T. Nakazuru , K. Miura , S. Nagasawa . A 6×320-MHz 1024-channel FFT cross-spectrum analyzer for radio astronomy. Proc. IEEE , 9 , 1203 - 1210
    8. 8)
      • D.J. Myers , P.A. Ivey . Circuit elements for VLSI signal processing. Br. Telecom. Technol. J. , 3 , 67 - 78
    9. 9)
      • S. Winograd . On computing the discrete Fourier transform. Math. Comput. , 141 , 175 - 199
    10. 10)
      • P. Denyer , D. Renshaw . (1985) , VLSI signal processing: a bit-serial approach.
    11. 11)
      • T. Willey , R. Chapman , H. Yoho , T.S. Durrani , D. Preis . Systolic implementations for deconvolution, DFT and FFT. IEE Proc. F, Commun., Radar & Signal Process. , 6 , 466 - 472
    12. 12)
      • O. Ersoy . Semisystolic array implementation of circular, skew circular, and linear convolutions. IEEE Trans. , 2 , 190 - 196
    13. 13)
      • B. Arambepola . Discrete Fourier transform processor based on the prime-factor algorithm. IEE Proc. G. Circuits, Devices and Systems , 4 , 138 - 144
    14. 14)
      • P. Duhamel , B. Piron , J.M. Etcheto . On computing the inverse DFT. IEEE Trans. , 2 , 285 - 286
    15. 15)
      • S.G. Smith , P.B. Denyer . Radix-4 modules for high-performance bit-serial computation. IEE Proc. E, Comput. & Digital Tech. , 6 , 271 - 276
    16. 16)
      • Thompson, C.D.: `Area-time complexity for VLSI', Proceedings of the 11th Annual ACM Symposium on the Theory Computing, 1979, Atlanta, GA, USA, p. 81–88.
    17. 17)
      • R.F. Lyon . Two's complement pipeline multipliers. IEEE Trans. , 418 - 425
    18. 18)
      • R. Bracewell . (1986) , The Hartley transform.
    19. 19)
      • S. Warner . (1965) , Modern algebra.
    20. 20)
      • S. Chu , C.S. Burrus . A prime factor FFT algorithm using distributed arithmetic. IEEE Trans. , 2 , 217 - 226
    21. 21)
      • R. Stasinski . Easy generation of small-N discrete Fourier transform algorithms. IEE Proc. G, Circuits, Devices and Systems , 3 , 133 - 139
    22. 22)
      • S. Boussakta , A.G.J. Holt . Proposed prime number Hartley transform implementation using transversal filter type structures. Electron. Lett. , 15 , 926 - 928
    23. 23)
      • Smith, S.G., Denyer, P.B.: `Efficient bit-serial complex multiplication and sum-of-products computation using distributed arithmetic', Proceedings of ICASSP 86, 1986, Tokyo, Japan, p. 2203–2206.
    24. 24)
      • R.N. Bracewell . Discrete Hartley transform. J. Opt. Soc. Am. , 12 , 1832 - 1835
    25. 25)
      • L.B. Jackson , J.F. Kaiser , H.S. McDonald . An approach to the implementation of digital filters. IEEE Trans. , 3 , 413 - 421
    26. 26)
      • J.S. Ward , V. McCanny , J.G. McWhirter . Bit-level systolic array implementation of the Winograd Fourier transform algorithm. IEE Proc. F, Commun., Radar & Signal Process. , 6 , 473 - 479
    27. 27)
      • C.M. Rader . Discrete Fourier transforms when the number of data samples is prime. Proc. IEEE , 6 , 1107 - 1108
    28. 28)
      • R.C. Osborn . (1961) , Tables of all primitive roots of odd primes less than 1000.
    29. 29)
      • C.S. Burrus , T.W. Parks . (1985) , DFT/FFT and convolution algorithms, theory and implementation.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-g-2.1990.0059
Loading

Related content

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