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
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.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)
      • I.J. Good . The interaction algorithm and practical Fourier analysis. J. R. Statist. Soc. , 361 - 372
    2. 2)
      • L.H. Thomas . (1963) Using computers to solve problems in physics, Applications of digital computers.
    3. 3)
      • C.M. Rader . Discrete Fourier transforms when the number of data samples is prime. Proc. IEEE , 6 , 1107 - 1108
    4. 4)
      • S. Boussakta , A.G.J. Holt . Proposed prime number Hartley transform implementation using transversal filter type structures. Electron. Lett. , 15 , 926 - 928
    5. 5)
      • P. Denyer , D. Renshaw . (1985) , VLSI signal processing: a bit-serial approach.
    6. 6)
      • R.N. Bracewell . Discrete Hartley transform. J. Opt. Soc. Am. , 12 , 1832 - 1835
    7. 7)
      • R. Bracewell . (1986) , The Hartley transform.
    8. 8)
      • D.C. Perkins . A separable Hartley-like transform in two or more dimensions. Proc. IEEE , 8 , 1127 - 1129
    9. 9)
      • B. Arambepola . Discrete Fourier transform processor based on the prime-factor algorithm. IEE Proc. G. Circuits, Devices and Systems , 4 , 138 - 144
    10. 10)
      • S. Warner . (1965) , Modern algebra.
    11. 11)
      • R.C. Osborn . (1961) , Tables of all primitive roots of odd primes less than 1000.
    12. 12)
      • S. Chu , C.S. Burrus . A prime factor FFT algorithm using distributed arithmetic. IEEE Trans. , 2 , 217 - 226
    13. 13)
      • R. Stasinski . Easy generation of small-N discrete Fourier transform algorithms. IEE Proc. G, Circuits, Devices and Systems , 3 , 133 - 139
    14. 14)
      • S. Winograd . On computing the discrete Fourier transform. Math. Comput. , 141 , 175 - 199
    15. 15)
      • J.H. McClellan , H. Nawab . (1979) Complex general-N Winograd Fourier transform algorithm (WFTA), Programs for digital signal processing.
    16. 16)
      • Johnson, H.W., Burrus, C.S.: `Large DFT modules: 11, 13, 17, 19, and 25', 8105, Report, 13 December 1981.
    17. 17)
      • 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
    18. 18)
      • R.F. Lyon . Two's complement pipeline multipliers. IEEE Trans. , 418 - 425
    19. 19)
      • O. Ersoy . Semisystolic array implementation of circular, skew circular, and linear convolutions. IEEE Trans. , 2 , 190 - 196
    20. 20)
      • 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.
    21. 21)
      • 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.
    22. 22)
      • 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
    23. 23)
      • L.B. Jackson , J.F. Kaiser , H.S. McDonald . An approach to the implementation of digital filters. IEEE Trans. , 3 , 413 - 421
    24. 24)
      • D.J. Myers , P.A. Ivey . Circuit elements for VLSI signal processing. Br. Telecom. Technol. J. , 3 , 67 - 78
    25. 25)
      • S.G. Smith , P.B. Denyer . Radix-4 modules for high-performance bit-serial computation. IEE Proc. E, Comput. & Digital Tech. , 6 , 271 - 276
    26. 26)
      • J. Hekrdla . Index transforms for N-dimensional DFT's. Numer. Math. , 469 - 480
    27. 27)
      • C.S. Burrus , T.W. Parks . (1985) , DFT/FFT and convolution algorithms, theory and implementation.
    28. 28)
      • 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
    29. 29)
      • P. Duhamel , B. Piron , J.M. Etcheto . On computing the inverse DFT. IEEE Trans. , 2 , 285 - 286
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