Efficient implementation of n-point DCT, n-point IDCT, SA-DCT and SA-IDCT algorithms
View Patent ↗An efficient implementation of n-point discrete cosine transform, n-point inverse discrete cosine transform, shape adaptive discrete cosine transform and shape adaptive inverse discrete cosine transform algorithms for multimedia compression and decompression optimization. An n-point DCT function is represented by a first equation having an input matrix, an output matrix and a matrix of predetermined values. An n-point IDCT function is represented by a second equation having an input matrix, an output matrix and a matrix of predetermined values. The multiplication operations within the matrix of predetermined values are paired, thereby reducing processor instructions. SIMD operations, MMX operations, VLSI implementation, single processor implementation, and vector processing are used to perform the algorithms.
1. A machine-implemented method, comprising:
receiving a multimedia signal having data values;
forming the data values into a matrix of inputs X;
forming a matrix A of predetermined values and multiplication operations;
factoring the matrix A into a butterfly matrix B, a shuffle matrix S, and a multiplication matrix M, wherein the multiplication operations are selectively positioned into pairs within the matrix M, and wherein the values within the matrices B and S are integers selected from the group consisting of 1, 0, and −1;
executing a Single Instruction Multiple Data (SIMD) instruction that multiplies the matrices X, B, S, and M together to obtain a matrix of outputs; and
generating a compressed multimedia signal based on the obtained output matrix Y.
2. The machine-implemented method of claim 1 , wherein the SIMD instruction is a Packed Multiply and Add (PMADDWD) instruction.
3. The machine-implemented method of claim 1 , wherein the matrix A is a 4-point Discrete Cosine Transform (DCT) transformation matrix, the matrix X represents a time domain of a video signal, and the matrix A represents a frequency domain of the video signal.
4. The machine-implemented method of claim 3 , wherein the multiplication matrix M is
[
1
2
1
2
0
0
1
2
-
1
2
0
0
0
0
cos
(
3
π
8
)
cos
(
π
8
)
0
0
-
cos
(
π
8
)
cos
(
3
π
8
)
]
,
and wherein the positioned pairs are
1
2
1
2
and
1
2
-
1
2
.
5. The method of claim 1 , wherein the butterfly matrix B is of the form
[
1
0
0
1
0
1
1
0
0
1
-
1
0
1
0
0
-
1
]
.
6. A machine-readable medium having instructions to cause a machine to perform a machine-implemented method, comprising:
receiving a multimedia signal having data values;
forming the data values into a matrix of inputs X;
forming a matrix A of predetermined values and multiplication operations;
factoring the matrix A into a butterfly matrix B, a shuffle matrix S, and a multiplication matrix M, wherein the multiplication operations are selectively positioned into pairs within the matrix M, and wherein the values within the matrices B and S are integers selected from the group consisting of 1, 0, and −1;
executing a Single Instruction Multiple Data (SIMD) instruction that multiplies the matrices X, B, S, and M together to obtain a matrix of outputs; and
generating a compressed multimedia signal based on the obtained output matrix Y.
7. The machine-readable medium of claim 6 , wherein the SIMD instruction is a Packed Multiply and Add (PMADDWD) instruction.
8. The machine-readable medium of claim 6 , wherein the matrix A is a 4-point Discrete Cosine Transform (DCT) transformation matrix, the matrix X represents a time domain of a video signal, and the matrix A represents a frequency domain of the video signal.
9. The machine-readable medium of claim 8 , wherein the multiplication matrix M is
[
1
2
1
2
0
0
1
2
-
1
2
0
0
0
0
cos
(
3
π
8
)
cos
(
π
8
)
0
0
-
cos
(
π
8
)
cos
(
3
π
8
)
]
,
and wherein the positioned pairs are
1
2
1
2
and
1
2
-
1
2
.
10. The machine-readable medium of claim 6 , wherein the butterfly matrix B is of the form
[
1
0
0
1
0
1
1
0
0
1
-
1
0
1
0
0
-
1
]
.
11. A system comprising:
a processing unit coupled to a memory through a bus; and
a process executed from the memory by the processing unit to cause the processing unit to:
receive a multimedia signal having data values;
form the data values into a matrix of inputs X;
form a matrix A of predetermined values and multiplication operations;
factor the matrix A into a butterfly matrix B, a shuffle matrix S, and a multiplication matrix M, wherein the multiplication operations are selectively positioned into pairs within the matrix M, and wherein the values within the matrices B and S are integers selected from the group consisting of 1, 0, and −1;
execute a Single Instruction Multiple Data (SIMD) instruction that multiplies the matrices X, B, S, and M together to obtain a matrix of outputs; and
generate a compressed multimedia signal based on the obtained output matrix Y.
12. The system of claim 11 , wherein the SIMD instruction is a Packed Multiply and Add (PMADDWD) instruction.
13. The system of claim 11 , wherein the matrix A is a 4-point Discrete Cosine Transform (DCT) transformation matrix, the matrix X represents a time domain of a video signal, and the matrix A represents a frequency domain of the video signal.
14. The system of claim 13 , wherein the multiplication matrix M is
[
1
2
1
2
0
0
1
2
-
1
2
0
0
0
0
cos
(
3
π
8
)
cos
(
π
8
)
0
0
-
cos
(
π
8
)
cos
(
3
π
8
)
]
,
and wherein the positioned pairs are
1
2
1
2
and
1
2
-
1
2
.
15. The system of claim 11 , wherein the butterfly matrix B is of the form
[
1
0
0
1
0
1
1
0
0
1
-
1
0
1
0
0
-
1
]
.