Browse Prior Art Database

Apparatus and method for fast algorithm implementation of discrete cosine transform with variable size

IP.com Disclosure Number: IPCOM000125692D
Original Publication Date: 2005-Jun-13
Included in the Prior Art Database: 2005-Jun-13
Document File: 3 page(s) / 102K

Publishing Venue

IBM

Abstract

This invention is focused o the implementation of the algorithm II with inverse DCT e.g. IDCT as an example.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 62% of the total text.

Page 1 of 3

Apparatus and method for fast algorithm implementation of discrete cosine transform with variable size

[Background]:

The DCT (Discrete Cosine Transform) is a mathematic transformation for digital image processing applications and some other applications. It transforms the object from time domain to frequency domain. In the application of digital image processing, it helps separate the image from spatial domain into sub-band parts that have different importance with respect to the image's visual quality:

Figure 1. DCT Definition

The typical implementation of the DCT formula will be mostly DCT-II as defined:

DCT-II

Figure 2. DCT - II

with transpose and second pass way of the above defined 1-D, the 2-D DCT computation complexity is lowered from N2 to N*logN. The algorithm and complexity changes when implementations are changed, either in hardware or software or combination of both. The implementation has to be balanced between speed and number of hardware blocks or software multiplications being used.

This invention is focused o the implementation of the algorithm II with inverse DCT e.g. IDCT as an example.

[Solution Summary]:

An algorithm is created to approximate the IDCT coefficient computation. The key to the fast implementation is the usage of multiplier operations. The original definition would use 1K multiplier operations for an 8x8 computation block. The solution that used in this invention only uses 1/7 of the number of multiplier operations and half of the addition operations. The algorithms that implemented the 2-D DCT is as following:

1

[This page contains 2 pictures or other non-text objects]

Page 2 of 3

> Pipeline Register array

Multiplier array

> Pipeline Register array

Adder Array

> Pipeline Register Array

> Transpose memory array >

Figure 1. Implementation algorithm of fast DCT

The algorithms that being implemented can be write as the following equation:

   

   

f

 ) 0 (

  C C C C

F

 ) 0 (

  C C C C

F

 ) 1 (

   

  6 4 2 0

  C C C C

  C C C C

   

   

   

  7 5 3 1

  C C C C

   

f

 ) 1 (

  C C C C

  2 4 6 0

F

 ) 2 (

 C C C C

  5 1 7 3

F

 ) 3 (

f

 ) 2 (

  2 4 6 0

F

 ) 4 (

   

  C C C C

  3 7 1 5

   

F

 ) 5 (

   

=

*

f

 ) 3 (

  6 4 2 0

F

 ) 6 (

  1 3 5 7

F

 ) 7 (

+

*

   

f

 ) 7...