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 -