# Enhance DCT (discrete cosine transform) kernel function, RV32IM (w/ Fixed-point Arithmetic)
Contirbuted by < [Brian Cheng](https://github.com/BrianCheng-TheLegend) >
## Motivation
In this project I want to implement DCT into RV32IM.I chose the project [jpeg-encoder](https://github.com/BrianCheng-TheLegend/jpeg-encoder/blob/master/jpeg_encoder.c) from [Michael Schier](https://github.com/schiermike)'s github.

## Introduction
The Discrete Cosine Transform (DCT) stands as a fundamental mathematical transformation extensively employed in the realms of signal processing and data compression applications. Its pivotal application lies in the domain of [jpeg](https://en.wikipedia.org/wiki/JPEG) standard image compression, where it serves as a cornerstone for efficiently representing image data.

Given the limitations of the human visual system, particularly its reduced sensitivity to high-frequency signals, the DCT is instrumental in capturing and representing essential image features while minimizing the impact of components that might be less perceptible to the human eye. This attribute contributes significantly to the effectiveness of image compression algorithms, as it allows for the removal or quantization of high-frequency components without significantly compromising the perceived visual quality of the compressed image. Therefore, the integration of the DCT in JPEG compression plays a crucial role in achieving a balance between compression efficiency and perceptual quality.

This transform is applied to an 8x8 block of image data. The indices (x, y) in the formula represent the spatial frequencies, and (i, j) represent the pixel coordinates within the block.


The result of applying the 2D-DCT to an 8x8 block leads to coefficients that represent different frequency components. The position (i, j) in the resulting image corresponds to the spatial location of these coefficients. This is often visualized in a plot like the one you provided:


Each position (i, j) in the resulting image corresponds to a specific frequency component, and the brightness or color intensity at that position indicates the magnitude of the corresponding DCT coefficient.

## Attemptation
From [Discrete Cosine Transform (DCT) of Images and Image Compression](https://youtu.be/mUKPy3r0TTI?si=ovDpG677MyEAoJFF) we learn
$F(p, q) = T \cdot f(x, y) \cdot T'$
$f(x, y) = T' \cdot F(p, q) \cdot T$
when the block is $M*M$
$T(u, v) = \frac{1}{\sqrt{M}} \cos\left[\frac{(2x + 1)u\pi}{2M}\right] \cos\left[\frac{(2y + 1)v\pi}{2M}\right], \quad 0 \leq u, v \leq M-1$

At this time I want to implement formula above to complete my dct function.
I found that matlab have the function to generate $T$ Matrix.

B=zeros([8,8]);
D=dctmtx(size(B,1));

And the result is

$D = \begin{bmatrix}
0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 \\
0.4904 & 0.4157 & 0.2778 & 0.0975 & -0.0975 & -0.2778 & -0.4157 & -0.4904 \\
0.4619 & 0.1913 & -0.1913 & -0.4619 & -0.4619 & -0.1913 & 0.1913 & 0.4619 \\
0.4157 & -0.0975 & -0.4904 & -0.2778 & 0.2778 & 0.4904 & 0.0975 & -0.4157 \\
0.3536 & -0.3536 & -0.3536 & 0.3536 & 0.3536 & -0.3536 & -0.3536 & 0.3536 \\
0.2778 & -0.4904 & 0.0975 & 0.4157 & -0.4157 & -0.0975 & 0.4904 & -0.2778 \\
0.1913 & -0.4619 & 0.4619 & -0.1913 & -0.1913 & 0.4619 & -0.4619 & 0.1913 \\
0.0975 & -0.2778 & 0.4157 & -0.4904 & 0.4904 & -0.4157 & 0.2778 & -0.0975 \\
\end{bmatrix}$

But if I want to implement this function into my code I should write my own function, and as below:

T=zeros([8,8]);
for X=1:8
    x=X-1;
    for Y=1:8
        y=Y-1;
        if(x==0)
            T(X,Y)=1/(sqrt(8));
        else
            T(X,Y)=sqrt(2/8)*cos((pi*(2*y+1)*x)/(16));
        end
    end
end

And the result is

$T = \begin{bmatrix}
0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 & 0.3536 \\
0.4904 & 0.4157 & 0.2778 & 0.0975 & -0.0975 & -0.2778 & -0.4157 & -0.4904 \\
0.4619 & 0.1913 & -0.1913 & -0.4619 & -0.4619 & -0.1913 & 0.1913 & 0.4619 \\
0.4157 & -0.0975 & -0.4904 & -0.2778 & 0.2778 & 0.4904 & 0.0975 & -0.4157 \\
0.3536 & -0.3536 & -0.3536 & 0.3536 & 0.3536 & -0.3536 & -0.3536 & 0.3536 \\
0.2778 & -0.4904 & 0.0975 & 0.4157 & -0.4157 & -0.0975 & 0.4904 & -0.2778 \\
0.1913 & -0.4619 & 0.4619 & -0.1913 & -0.1913 & 0.4619 & -0.4619 & 0.1913 \\
0.0975 & -0.2778 & 0.4157 & -0.4904 & 0.4904 & -0.4157 & 0.2778 & -0.0975 \\
\end{bmatrix}$

We can see the $D = T$, so the logic for the function I wrote is correct.
:::success
Work
1. tranfer integer to fixed-point architecture
2. matrix transpose
3. matrix binary multiplier
:::

## Implement
* C code

The following C code is
The follow

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <sys/time.h>

double cos_lookup[8][8];
void init_dct_lookup()
{
	int i, j;
	for (i=0; i<8; i++)
		for (j=0; j<8; j++)
		{
			cos_lookup[i][j] = cos( (2*i+1)*j*M_PI/16 );
			assert( -1<=cos_lookup[i][j] && cos_lookup[i][j]<=1 );
		}
}

inline void dct_block(int gap, int in[], double out[])
{
	int x_f, y_f; // frequency domain coordinates
	int x_t, y_t; // time domain coordinates

	double inner_lookup[8][8];
	for (x_t=0; x_t<8; x_t++)
		for (y_f=0; y_f<8; y_f++)
		{
			inner_lookup[x_t][y_f] = 0;
			for (y_t=0; y_t<8; y_t++)
				inner_lookup[x_t][y_f] += ( in[y_t*gap+x_t] - 128 ) * cos_lookup[y_t][y_f];

		}

	// freq(x_f,y_f) = ...
	double freq;
	for (y_f=0; y_f<8; y_f++)
		for (x_f=0; x_f<8; x_f++)
		{
			freq = 0;
			for(x_t=0; x_t<8; x_t++)
				freq += inner_lookup[x_t][y_f] * cos_lookup[x_t][x_f];

			if (x_f == 0)
				freq *= M_SQRT1_2;
			if (y_f == 0)
				freq *= M_SQRT1_2;
			freq /= 4;

			out[y_f*8+x_f] = freq;
		}
}

* RISC-V