Principal pivot transforms on radix-2 DFT-type matrices

Sian Jheng Lin, Amira Alloum, Tareq Y. Al-Naffouri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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.
Original languageEnglish (US)
Title of host publication2017 IEEE International Symposium on Information Theory (ISIT)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages5
ISBN (Print)9781509040964
StatePublished - Aug 29 2017

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01


Dive into the research topics of 'Principal pivot transforms on radix-2 DFT-type matrices'. Together they form a unique fingerprint.

Cite this