Two-dimensional transformation with minimum buffering
An apparatus having a first circuit and a second circuit is disclosed. The first circuit may be configured to (i) generate a sequence of intermediate matrices by multiplying a sequence of original matrices by a predetermined matrix and (ii) write the intermediate matrices into a memory in a first order that alternates between (a) a first of the intermediate matrices in a row order and (b) a second of the intermediate matrices in a column order. The second circuit may be configured to (i) read the sequence of the intermediate matrices from the memory in a second order that alternates between (a) the first intermediate matrix in the column order and (b) the second intermediate matrix in the row order and (ii) generate a sequence of transform matrices by multiplying the intermediate matrices as read from the memory by another predetermined matrix.
1. An apparatus comprising:
a first circuit configured to (i) generate a sequence of intermediate matrices by multiplying a sequence of original matrices by a predetermined matrix and (ii) write said intermediate matrices into a memory in a first order that alternates between (a) a first of said intermediate matrices in a row order and (b) a second of said intermediate matrices in a column order; and
a second circuit configured to (i) read said sequence of said intermediate matrices from said memory in a second order that alternates between (a) said first intermediate matrix in said column order and (b) said second intermediate matrix in said row order and (ii) generate a sequence of transform matrices by multiplying said intermediate matrices as read from said memory by another predetermined matrix.
2. The apparatus according to claim 1 , wherein said memory has a size that matches a plurality of elements in said intermediate matrices.
3. The apparatus according to claim 1 , wherein (i) each of a plurality of cycles used in said transforming creates a unit of said transform matrices and (ii) said unit is either a row or a column.
4. The apparatus according to claim 3 , wherein said memory is configured to (i) read one of said units and (ii) write another one of said units in a single one of said cycles.
5. The apparatus according to claim 3 , wherein a plurality of rows in at least two of said intermediate matrices are written into said memory in consecutive ones of said cycles.
6. The apparatus according to claim 1 , further comprising a third circuit configured to latch each column of said intermediate matrices prior to said write into said memory.
7. The apparatus according to claim 1 , wherein said predetermined matrix and said another predetermined matrix transform said original matrices either (i) from a spatial domain to a frequency domain or (ii) from said frequency domain to said spatial domain.
8. The apparatus according to claim 1 , wherein said transforming forms part of an H.265 decoding of encoded video.
9. The apparatus according to claim 1 , wherein said first circuit and said second circuit are hardware only.
10. A method for transform with minimum buffering, comprising the steps of:
(A) generating a sequence of intermediate matrices by multiplying a sequence of original matrices by a predetermined matrix;
(B) writing said intermediate matrices into a memory in a first order that alternates between (i) a first of said intermediate matrices in a row order and (ii) a second of said intermediate matrices in a column order;
(C) reading said sequence of said intermediate matrices from said memory in a second order that alternates between (i) said first intermediate matrix in said column order and (ii) said second intermediate matrix in said row order; and
(D) generating a sequence of transform matrices by multiplying said intermediate matrices as read from said memory by another predetermined matrix.
11. The method according to claim 10 , wherein said memory has a size that matches a plurality of elements in said intermediate matrices.
12. The method according to claim 10 , wherein (i) each of a plurality of cycles used in said transforming creates a unit of said transform matrices and (ii) said unit is either a row or a column.
13. The method according to claim 12 , wherein said memory is configured to (i) read one of said units and (ii) write another one of said units in a single one of said cycles.
14. The method according to claim 12 , wherein a plurality of rows in at least two of said intermediate matrices are written into said memory in consecutive ones of said cycles.
15. The method according to claim 10 , further comprising the step of:
latching each column of said intermediate matrices prior to said writing into said memory.
16. The method according to claim 10 , wherein said predetermined matrix and said another predetermined matrix transform said original matrices either (i) from a spatial domain to a frequency domain or (ii) from said frequency domain to said spatial domain.
17. The method according to claim 10 , wherein said transforming forms part of an H.265 decoding of encoded video.
18. An apparatus comprising:
means for generating a sequence of intermediate matrices by multiplying a sequence of original matrices by a predetermined matrix;
means for writing said intermediate matrices into a memory in a first order that alternates between (i) a first of said intermediate matrices in a row order and (ii) a second of said intermediate matrices in a column order;
means for reading said sequence of said intermediate matrices from said memory in a second order that alternates between (i) said first intermediate matrix in said column order and (ii) said second intermediate matrix in said row order; and
means for generating a sequence of transform matrices by multiplying said intermediate matrices as read from said memory by another predetermined matrix.