August  2014, 8(3): 257-270. doi: 10.3934/amc.2014.8.257

Higher genus universally decodable matrices (UDMG)

1. 

Department of Mathematics, University of Colorado at Boulder, Boulder, CO 80309-0395, United States

2. 

Department of Electrical and Computer Engineering, University of Colorado at Boulder, Boulder, CO 80309-0425, United States

Received  November 2012 Published  August 2014

We introduce the notion of Universally Decodable Matrices of Genus $g$ (UDMG), which for $g=0$ reduces to the notion of Universally Decodable Matrices (UDM) introduced in [8]. Fix positive $K,N,L$. A UDMG is a set $\{M_i|1\leq i\leq L\}$ of matrices of size $K \times N$ over a finite field such that the rows of any matrix of $K+g$ columns formed from the initial segments of the $M_i$ are linearly independent. We show that UDMG can be used to build approximately universal codes. We then provide a dictionary between UDMG and linear codes under the $m$-metric, which quickly provides constructions of UDMG and places bounds on the size of UDMG.
Citation: Steve Limburg, David Grant, Mahesh K. Varanasi. Higher genus universally decodable matrices (UDMG). Advances in Mathematics of Communications, 2014, 8 (3) : 257-270. doi: 10.3934/amc.2014.8.257
References:
[1]

S. T. Dougherty and M. M Skriganov, acWilliams duality and the Rosenbloom-Tsfasman metric,, Mosc. Math. J., 2 (2002), 81.   Google Scholar

[2]

A. Faldum and W. Willems, Codes of small defect,, Des. Codes Crypt., 10 (1997), 341.  doi: 10.1023/A:1008247720662.  Google Scholar

[3]

A. Ganesan and N. Boston, Universally decodable matrices,, in Proc. 43rd Allerton Conf. Commun. Control Computing, (): 28.   Google Scholar

[4]

A. Ganesan and P. O. Vontobel, On the existence of universally decodable matrices,, IEEE Trans. Inform. Theory, 53 (2007), 2572.  doi: 10.1109/TIT.2007.899482.  Google Scholar

[5]

R. Nielsen, A class of Sudan-decodable codes,, IEEE Trans. Inform. Theory, 46 (2002), 1564.  doi: 10.1109/18.850696.  Google Scholar

[6]

M. Y. Rosenbloom and M. A. Tsfasman, Codes for the m-metric,, Probl. Peredachi Inform., 33 (1997), 55.   Google Scholar

[7]

J. H. Silverman, The Arithmetic of Elliptic Curves,, Springer Verlag, (2009).  doi: 10.1007/978-0-387-09494-6.  Google Scholar

[8]

S. Tavildar and P. Viswanath, Approximately universal codes over slow-fading channels,, IEEE Trans. Inform. Theory, 52 (2006), 3233.  doi: 10.1109/TIT.2006.876226.  Google Scholar

[9]

D. Tse and P. Viswanath, Fundamentals of Wireless Communication,, Cambridge University Press, (2005).  doi: 10.1017/CBO9780511807213.  Google Scholar

[10]

P. O. Vontobel and A. Ganesan, On universally decodable matrices for space-time coding,, Des. Codes Crypt., 41 (2006), 325.  doi: 10.1007/s10623-006-9019-4.  Google Scholar

[11]

J. L. Walker, Codes and Curves,, Amer. Math. Soc., (2000).   Google Scholar

show all references

References:
[1]

S. T. Dougherty and M. M Skriganov, acWilliams duality and the Rosenbloom-Tsfasman metric,, Mosc. Math. J., 2 (2002), 81.   Google Scholar

[2]

A. Faldum and W. Willems, Codes of small defect,, Des. Codes Crypt., 10 (1997), 341.  doi: 10.1023/A:1008247720662.  Google Scholar

[3]

A. Ganesan and N. Boston, Universally decodable matrices,, in Proc. 43rd Allerton Conf. Commun. Control Computing, (): 28.   Google Scholar

[4]

A. Ganesan and P. O. Vontobel, On the existence of universally decodable matrices,, IEEE Trans. Inform. Theory, 53 (2007), 2572.  doi: 10.1109/TIT.2007.899482.  Google Scholar

[5]

R. Nielsen, A class of Sudan-decodable codes,, IEEE Trans. Inform. Theory, 46 (2002), 1564.  doi: 10.1109/18.850696.  Google Scholar

[6]

M. Y. Rosenbloom and M. A. Tsfasman, Codes for the m-metric,, Probl. Peredachi Inform., 33 (1997), 55.   Google Scholar

[7]

J. H. Silverman, The Arithmetic of Elliptic Curves,, Springer Verlag, (2009).  doi: 10.1007/978-0-387-09494-6.  Google Scholar

[8]

S. Tavildar and P. Viswanath, Approximately universal codes over slow-fading channels,, IEEE Trans. Inform. Theory, 52 (2006), 3233.  doi: 10.1109/TIT.2006.876226.  Google Scholar

[9]

D. Tse and P. Viswanath, Fundamentals of Wireless Communication,, Cambridge University Press, (2005).  doi: 10.1017/CBO9780511807213.  Google Scholar

[10]

P. O. Vontobel and A. Ganesan, On universally decodable matrices for space-time coding,, Des. Codes Crypt., 41 (2006), 325.  doi: 10.1007/s10623-006-9019-4.  Google Scholar

[11]

J. L. Walker, Codes and Curves,, Amer. Math. Soc., (2000).   Google Scholar

[1]

Seungkook Park. Coherence of sensing matrices coming from algebraic-geometric codes. Advances in Mathematics of Communications, 2016, 10 (2) : 429-436. doi: 10.3934/amc.2016016

[2]

Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543

[3]

Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021

[4]

Jop Briët, Assaf Naor, Oded Regev. Locally decodable codes and the failure of cotype for projective tensor products. Electronic Research Announcements, 2012, 19: 120-130. doi: 10.3934/era.2012.19.120

[5]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[6]

David Clark, Vladimir D. Tonchev. A new class of majority-logic decodable codes derived from polarity designs. Advances in Mathematics of Communications, 2013, 7 (2) : 175-186. doi: 10.3934/amc.2013.7.175

[7]

Susanne Pumplün, Andrew Steele. The nonassociative algebras used to build fast-decodable space-time block codes. Advances in Mathematics of Communications, 2015, 9 (4) : 449-469. doi: 10.3934/amc.2015.9.449

[8]

Susanne Pumplün. How to obtain division algebras used for fast-decodable space-time block codes. Advances in Mathematics of Communications, 2014, 8 (3) : 323-342. doi: 10.3934/amc.2014.8.323

[9]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[10]

Zihui Liu, Xiangyong Zeng. The geometric structure of relative one-weight codes. Advances in Mathematics of Communications, 2016, 10 (2) : 367-377. doi: 10.3934/amc.2016011

[11]

T. L. Alderson, K. E. Mellinger. Geometric constructions of optimal optical orthogonal codes. Advances in Mathematics of Communications, 2008, 2 (4) : 451-467. doi: 10.3934/amc.2008.2.451

[12]

Dean Crnković, Ronan Egan, Andrea Švob. Self-orthogonal codes from orbit matrices of Seidel and Laplacian matrices of strongly regular graphs. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020032

[13]

Dean Crnković, Bernardo Gabriel Rodrigues, Sanja Rukavina, Loredana Simčić. Self-orthogonal codes from orbit matrices of 2-designs. Advances in Mathematics of Communications, 2013, 7 (2) : 161-174. doi: 10.3934/amc.2013.7.161

[14]

Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93

[15]

Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233

[16]

Grégory Berhuy. Algebraic space-time codes based on division algebras with a unitary involution. Advances in Mathematics of Communications, 2014, 8 (2) : 167-189. doi: 10.3934/amc.2014.8.167

[17]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[18]

Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020019

[19]

Bernard Bonnard, Monique Chyba, Alain Jacquemard, John Marriott. Algebraic geometric classification of the singular flow in the contrast imaging problem in nuclear magnetic resonance. Mathematical Control & Related Fields, 2013, 3 (4) : 397-432. doi: 10.3934/mcrf.2013.3.397

[20]

Christos Koukouvinos, Dimitris E. Simos. Construction of new self-dual codes over $GF(5)$ using skew-Hadamard matrices. Advances in Mathematics of Communications, 2009, 3 (3) : 251-263. doi: 10.3934/amc.2009.3.251

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]