• Diese Seite als PDF öffnen.

Support-Constrained Generator Matrix

Description

The necessary and sufficient conditions for the existence of Reed-Solomon codes with support constrained generator matrices were conjecturen by Dau ei al. [1]. This is referred to as the GM-MDS conjecture, which was worked on by many researchers in [2-9] and finnally proved by Yildiz and Hassibi [10] and indenpendently by Lovett [11].

The objective of this work is to get an overview on the existing researches on GM-MDS conjecture and to summarize the methods used in the referenced papers for proving the GM-MDS conjecture.

References:

[1] S. H. Dau, W. Song, and C. Yuen, “On the existence of MDS codes over small fields with constrained generator matrices,” in 2014 IEEE International Symposium on Information Theory. IEEE, 2014, pp. 1787–1791.

[2] W. Halbawi, T. Ho, H. Yao, and I. Duursma, “Distributed Reed–Solomon codes for simple multiple access networks,” in 2014 IEEE International Symposium on Information Theory. IEEE, 2014, pp. 651–655.

[3] M. Yan, A. Sprintson, and I. Zelenko, “Weakly secure data exchange with generalized Reed–Solomon codes,” in 2014 IEEE International Symposium on Information Theory. IEEE, 2014, pp. 1366–1370.

[4] W. Halbawi, Z. Liu, and B. Hassibi, “Balanced Reed–Solomon codes,” in 2016 IEEE International Symposium on Information Theory (ISIT). IEEE, 2016, pp. 935–939.

[5] W. Halbawi, Z. Liu, and B. Hassibi, “Balanced Reed–Solomon codes for all parameters,” in 2016 IEEE Information Theory Workshop (ITW). IEEE, 2016, pp. 409–413.

[6] A. Heidarzadeh and A. Sprintson, “An algebraic-combinatorial proof technique for the GM-MDS conjecture,” in 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 11–15.

[7] W. Song and K. Cai, “Generalized Reed–Solomon codes with sparsest and balanced generator matrices,” in 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 2018, pp. 1–5.

[8] H. Yildiz and B. Hassibi, “Further progress on the GM-MDS conjecture for Reed–Solomon codes,” in 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 2018, pp. 16–20.

[9] G. Greaves and J. Syatriadi, “Reed–Solomon codes over small fields with constrained generator matrices,” IEEE Transactions on Information Theory, 2019.

[10] H. Yildiz and B. Hassibi, “Optimum linear codes with support constraints over small fields,” in 2018 IEEE Information Theory Workshop (ITW). IEEE, 2018, pp. 1–5.

[11] S. Lovett, “MDS matrices over small fields: A proof of the GM-MDS conjecture,” in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018, pp. 194–199.

Prerequisites

Supervisor: