Principal pivot transforms on radix-2 DFT-type matrices

摘要

In this paper, we discuss the principal pivot transforms (PPT) on a family of matrices, called the radix-2 DFT-type matrices. Given a transformation matrix, the PPT of the matrix is a transformation matrix with exchanging some entries between the input array and the output array. The radix-2 DFT-type matrices form a classification of matrices such that the transformations by the matrices can be calculated via radix-2 butterflies. A number of well-known matrices, such as radix-2 DFT matrices and Hadamard matrices, belong to this classification. In this paper, the sufficient conditions for the PPTs on radix-2 DFT-type matrices are given, such that their transformations can also be computed in O{n lg n). Then based on the results above, an encoding algorithm for systematic Reed-Solomon (RS) codes in O{n lg n) field operations is presented.