基于子集划分的素长度二维DCT快速算法
doi: 10.3724/SP.J.1146.2010.01220
A New Fast Prime-length 2-D DCT Algorithm Based on Subset Partition
-
摘要: 该文针对素长度类型的2维离散余弦变换(DCT)变换,提出一种子集划分准则,并根据该准则将2维DCT变换输出的频域数据集合划分为若干个互不相交子集;将对频域的计算转换为对2(N-1)个N点1维素数尺寸DCT的奇系数或偶系数的计算;最后给出了该算法的乘法复杂度和加法运算复杂度。相对于行列分解法,该算法节省了约一半的乘法次数,省略了数据的转置存储过程,而加法的运算复杂度基本维持不变。Abstract: A new fast algorithm based on subset partition for prime-length 2D Discrete Cosine Transform (DCT) is proposed. The rule of subset partition is put forward, and the frequency data of DCT output are separated into several irrelevant subsets according it. The calculation of frequency data is converted to 2(N-1) calculations of even- or odd-indexed N-length 1D-DCT coefficient. The computational complexity of the algorithm is presented. Compared to Roll and Column Method (RCM), this new fast algorithm reduces half of multiplication times, eliminates transposition of data, and retains computational complexity of addition.
计量
- 文章访问数: 3265
- HTML全文浏览量: 97
- PDF下载量: 514
- 被引次数: 0