TY - GEN

T1 - Principal pivot transforms on radix-2 DFT-type matrices

AU - Lin, Sian Jheng

AU - Alloum, Amira

AU - Al-Naffouri, Tareq Y.

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2017/8/29

Y1 - 2017/8/29

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/630830

UR - http://ieeexplore.ieee.org/document/8006951/

UR - http://www.scopus.com/inward/record.url?scp=85034081305&partnerID=8YFLogxK

U2 - 10.1109/isit.2017.8006951

DO - 10.1109/isit.2017.8006951

M3 - Conference contribution

AN - SCOPUS:85034081305

SN - 9781509040964

SP - 2358

EP - 2362

BT - 2017 IEEE International Symposium on Information Theory (ISIT)

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -