Principal pivot transforms on radix-2 DFT-type matrices

Sian Jheng Lin; Amira Alloum; Tareq Al-Naffouri

doi:10.1109/ISIT.2017.8006951

Principal pivot transforms on radix-2 DFT-type matrices

Sian Jheng Lin, Amira Alloum, Tareq Al-Naffouri

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 language	English (US)
Title of host publication	2017 IEEE International Symposium on Information Theory, ISIT 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2358-2362
Number of pages	5
ISBN (Electronic)	9781509040964
DOIs	https://doi.org/10.1109/ISIT.2017.8006951
State	Published - Aug 9 2017
Event	2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany Duration: Jun 25 2017 → Jun 30 2017

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095

Conference

Conference	2017 IEEE International Symposium on Information Theory, ISIT 2017
Country/Territory	Germany
City	Aachen
Period	06/25/17 → 06/30/17

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Applied Mathematics
Modeling and Simulation

Access to Document

10.1109/ISIT.2017.8006951

Cite this

Lin, S. J., Alloum, A., & Al-Naffouri, T. (2017). Principal pivot transforms on radix-2 DFT-type matrices. In 2017 IEEE International Symposium on Information Theory, ISIT 2017 (pp. 2358-2362). Article 8006951 (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8006951

@inproceedings{c7b9d818beef40f9842b953460201f28,

title = "Principal pivot transforms on radix-2 DFT-type matrices",

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.",

author = "Lin, {Sian Jheng} and Amira Alloum and Tareq Al-Naffouri",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE International Symposium on Information Theory, ISIT 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

year = "2017",

month = aug,

day = "9",

doi = "10.1109/ISIT.2017.8006951",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2358--2362",

booktitle = "2017 IEEE International Symposium on Information Theory, ISIT 2017",

address = "United States",

}

Lin, SJ, Alloum, A & Al-Naffouri, T 2017, Principal pivot transforms on radix-2 DFT-type matrices. in 2017 IEEE International Symposium on Information Theory, ISIT 2017., 8006951, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 2358-2362, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 06/25/17. https://doi.org/10.1109/ISIT.2017.8006951

Principal pivot transforms on radix-2 DFT-type matrices. / Lin, Sian Jheng; Alloum, Amira; Al-Naffouri, Tareq.
2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 2358-2362 8006951 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Lin, Sian Jheng

AU - Alloum, Amira

AU - Al-Naffouri, Tareq

PY - 2017/8/9

Y1 - 2017/8/9

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://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

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2358

EP - 2362

BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017

Y2 - 25 June 2017 through 30 June 2017

ER -

Principal pivot transforms on radix-2 DFT-type matrices

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this