American Institute of Mathematical Sciences

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

Higher genus universally decodable matrices (UDMG)

Steve Limburg 1, , David Grant 1, and  Mahesh K. Varanasi 2,

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.
Keywords: algebraic geometric codes., Universally decodable matrices.
Mathematics Subject Classification: Primary: 94B60, 94B05, 11T7.
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-97.  Google Scholar

[2]

A. Faldum and W. Willems, Codes of small defect, Des. Codes Crypt., 10 (1997), 341-350. 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-2575. doi: 10.1109/TIT.2007.899482.  Google Scholar

[5]

R. Nielsen, A class of Sudan-decodable codes, IEEE Trans. Inform. Theory, 46 (2002), 1564-1572. 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-63.  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-3258. 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-342. 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-97.  Google Scholar

[2]

A. Faldum and W. Willems, Codes of small defect, Des. Codes Crypt., 10 (1997), 341-350. 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-2575. doi: 10.1109/TIT.2007.899482.  Google Scholar

[5]

R. Nielsen, A class of Sudan-decodable codes, IEEE Trans. Inform. Theory, 46 (2002), 1564-1572. 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-63.  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-3258. 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-342. 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]

Gianira N. Alfarano, Martino Borello, Alessandro Neri. A geometric characterization of minimal codes and their asymptotic performance. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020104
[12]

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
[13]

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, 2020, 14 (4) : 591-602. doi: 10.3934/amc.2020032
[14]

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
[15]

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
[16]

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
[17]

Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, 2020, 14 (2) : 265-278. doi: 10.3934/amc.2020019
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy