Design and Digital Implementation of Fast and Recursive DCT II–IV Algorithms

Sirani M. Perera, Arjuna Madanayake, Nathan Dornback, Nilan Udayanga, Sirani K M. Perera

Research output: Contribution to journalArticlepeer-review

Abstract

Using the proposed factorizations of discrete cosine transform (DCT) matrices, fast and
recursive algorithms are stated. In this paper, signal flow graphs for the n-point DCT
II and DCT IV algorithms are introduced. The proposed algorithms yield exactly the
same results as with standardDCT algorithms but are faster. The arithmetic complexity
and stability of the algorithms are explored, and improvements of these algorithms
are compared with previously existing fast and stable DCT algorithms. A parallel
hardware computing architecture for theDCTII algorithm is proposed. The computing
architecture is first designed, simulated, and prototyped using a 40-nm Xilinx Virtex-6
FPGA and thereafter mapped to custom integrated circuit technology using 0.18-μm
CMOS standard cells from Austria Micro Systems. The performance trade-off exists
between computational precision, chip area, clock speed, and power consumption.
This trade-off is explored in both FPGA and custom CMOS implementation spaces.
An exampleFPGAimplementation operates at clock frequencies in excess of 230MHz
for several values of system word size leading to real-time throughput levels better
than 230 million 16-point DCTs per second. Custom CMOS-based results are subject
to synthesis and place-and-route steps of the design flow. Physical silicon fabrication
was not conducted due to prohibitive cost.
Original languageAmerican English
JournalCircuits Systems and Signal Processing
DOIs
StatePublished - Jul 6 2018

Keywords

  • Discrete cosine transforms
  • Fast algorithms
  • Recursive algorithms
  • Arithmetic complexity
  • Sparse and orthogonal factors
  • Signal flow graphs
  • Field-programmable gate array (FPGA)
  • Application-specific integrated circuits (ASIC)

Disciplines

  • Signal Processing
  • Control Theory
  • Numerical Analysis and Computation
  • Numerical Analysis and Scientific Computing
  • Theory and Algorithms

Cite this