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

Abstract

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)
Pages2358-2362
Number of pages5
ISBN (Print)9781509040964
DOIs
StatePublished - Aug 29 2017

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

Cite this