# A Novel ASIC Implementation of Two-Dimensional Image Compression Using Improved B.G. Lee Algorithm
## 2 Methodology  
### B.G. Lee DCT Algorithm  
DCT converts signals into elementary frequency components operating on real numbers with even symmetry. The DCT also expresses an image as a sum of cosine functions in exponentials. One of the fundamental elements of the compression algorithm is DCT. The distinct property of DCT for images that makes the visually vital information concentrated in a few coefficients of DCT makes it useful for image compression applications.  
The DCT takes a set of correlated or similar data points as input and returns the same decorrelated or dissimilar data points, compacting the energy in just a few coefficients.  
The 1D DCT for a given sequence is defined as  
\[X_{c}(k)=c(k)\sum_{n=0}^{N-1}x(n)\cos\frac{\pi k(2n+1)}{2N},\ 0\ \leq k\ \leq N-1 \tag{1}\]  
\(x(n)\) can be obtained from \(X_{c}(k)\) by taking the inverse and is given by  
\[x(n)=\sum_{k=0}^{N-1}c(k)X_{c}(k)\cos\frac{\pi k(2n+1)}{2N},\ 0\leq n\leq N-1 \tag{2}\]  
where \(c(k)=\left\{\begin{array}{cc}\frac{1}{\sqrt{N}},&if\ k=0\\ \frac{\sqrt{2}}{\sqrt{N}}\,&if\ 1\ \leq k\ \leq N-1\end{array}\right.\).  
One-dimensional signals, such as audio, can be handled using 1D DCT, unlike video signals and images that require 2D DCT. The requisite for applications demanding 2D DCT computations is on the rise with technological advancements. The 2D DCT can be computed by obtaining the product of 1D DCT along the rows and columns, known as the row-column algorithm.  
There has been extensive use of 1D and 2D DCT in many signal and image processing applications. The application of the row-column technique using the separability property of 2D DCT permits the DCT implementation in 1D. This involves the 1D DCT computation on each row, taking the transpose of the resultant matrix, and then the computation of 1D DCT on each column of the transformed result. The total number of computations needed when N = 8 for the 1D eight-point DCT/IDCT calculations would be 56 addition operations and 64 multiplication operations. When carried out for 2D DCT/IDCT, usingthe separability property of the columns and rows, the number of computations would increase to 896 additions and 1024 multiplications.  
The row/column 1D DCT/IDCT technique typically takes roughly half as many computations as the 2D DCT/IDCT direct approach, but at the trade-off of more complicated control circuitry and inconsistent data paths. The exclusion of the transposition memory that reduces the delay is an added advantage of the 2D DCT/IDCT direct approach. The data flowgraph structure of DCT and IDCT using the [PERSON] algorithm [22] is given in Figure 1 and Figure 2, respectively.  
The multiplications involved in an N-point DCT proposed by [PERSON] are computed using the following equation.  
\[\frac{N}{2}\ log_{2}N \tag{3}\]  
The number of multiplications obtained was around 12--half the multiplication operations of the prevailing efficient algorithms. The additions involved when calculated using the equation came up to around 29.  
\[3\ \frac{N}{2}\ log_{2}N-N+1 \tag{4}\]  
Figure 1: Data flowgraph structure of eight-point DCT using [PERSON] algorithm.  
Figure 2: Data flowgraph structure of eight-point IDCT using [PERSON] algorithm.