A New Fast Prime-length 2-D DCT Algorithm Based on Subset Partition

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.