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 DFTtype 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