November  2012, 6(4): 385-400. doi: 10.3934/amc.2012.6.385

Decoding affine reflection group codes with trellises

1. 

Communication Systems Group, Technische Universität Darmstadt, 64283 Darmstadt, Germany

2. 

Department of Computer Science, Ryerson University, Toronto, ON, Canada

3. 

Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON, Canada

Received  April 2011 Revised  June 2012 Published  November 2012

We present two decoding methods (called hybrid and lattice cosets) for affine reflection group codes (ARGC) of any dimension. The algorithms are based on viewing the affine reflection group as a semi-direct product of a crystallographic finite reflection group and its coroot lattice. The proposed lattice cosets method gives an explicit method for drawing a trellis diagram representation of ARGC. The complexities of these two decoding methods, as well as the trade-offs between them, are discussed.
Citation: Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
References:
[1]

A. H. Banihashemi, "Decoding Complexity and Trellis Structure of Lattices,'' Ph.D thesis,, Univerity of Waterloo, (1997). Google Scholar

[2]

A. H. Banihashemi and I. F. Blake, Trellis complexity and minimal trellis diagrams of lattices,, IEEE Trans. Inform. Theory, 44 (1998), 1829. doi: 10.1109/18.705562. Google Scholar

[3]

A. H. Banihashemi and I. F. Blake, On the trellis complexity of root lattices and their duals,, IEEE Trans. Inform. Theory, 45 (1999), 2168. doi: 10.1109/18.782169. Google Scholar

[4]

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups,'' 3rd edition,, Springer-Verlag, (1999). Google Scholar

[5]

J. G. D. Forney, Density/length profiles and trellis complexity of lattices,, IEEE Trans. Inform. Theory, 40 (1994), 1753. doi: 10.1109/18.340453. Google Scholar

[6]

S. Han, J. M. Cioffi and J. H. Lee, On the use of hexagonal constellation for peak-to-average power ratio reduction of an OFDM signal,, IEEE Trans. Wireless Comm., 7 (2008), 781. doi: 10.1109/TWC.2007.06104. Google Scholar

[7]

J. E. Humphreys, "Reflection Groups and Coxeter Groups,'', Cambridge University Press, (1990). doi: 10.1017/CBO9780511623646. Google Scholar

[8]

R. G. McKilliam, W. D. Smith, I. Vaughan and L. Clarkson, Linear-time nearest point algorithms for Coxeter lattices,, IEEE Trans. Inform. Theory, 56 (2010), 1015. doi: 10.1109/TIT.2009.2039090. Google Scholar

[9]

T. Mittelholzer, Construction and decoding of optimal group codes from finite reflection groups,, in, (1996). Google Scholar

[10]

T. Mittelholzer and J. Lahtonen, Group codes generated by finite reflection groups,, IEEE Trans. Inform. Theory, 42 (1996), 519. doi: 10.1109/18.485721. Google Scholar

[11]

T. Niyomsataya, A. Miri and M. Nevins, Affine reflection group codes,, IEEE Trans. Inform. Theory, 54 (2008), 441. doi: 10.1109/TIT.2007.911261. Google Scholar

[12]

T. Niyomsataya, A. Miri and M. Nevins, Efficient decoding algorithm for affine reflection group codes of rank 2,, in, (2008), 72. doi: 10.1109/BSC.2008.4563208. Google Scholar

[13]

T. Niyomsataya, A. Miri and M. Nevins, Improving PAPR reduction using tone injection on affine reflection group codes of rank 2,, preprint (based on Ph.D thesis work of the first author)., (). Google Scholar

[14]

D. J. Ryan, I. V. L. Clarkson, I. B. Collings, D. Guo and M. L. Honig, QAM and PSK codebooks for limited feedback MIMO beamforming,, IEEE Trans. Comm., 57 (2009), 1184. doi: 10.1109/TCOMM.2009.04.070178. Google Scholar

[15]

D. J. Ryan, I. B. Collins and J-M. Valin, Reflected simplex codebooks for limited feedback MIMO beamforming,, in, (2009), 1. doi: 10.1109/ICC.2009.5199405. Google Scholar

[16]

D. Slepian, Permutation modulation,, Proc. IEEE, 53 (1965), 228. doi: 10.1109/PROC.1965.3680. Google Scholar

[17]

D. Slepian, Group codes for the Gaussian channel,, Bell System Tech. J., 47 (1968), 575. Google Scholar

[18]

V. Tarokh and A. Vardy, Upper bounds on Trellis complexity of lattices,, IEEE Trans. Inform. Theory, 43 (1997). Google Scholar

show all references

References:
[1]

A. H. Banihashemi, "Decoding Complexity and Trellis Structure of Lattices,'' Ph.D thesis,, Univerity of Waterloo, (1997). Google Scholar

[2]

A. H. Banihashemi and I. F. Blake, Trellis complexity and minimal trellis diagrams of lattices,, IEEE Trans. Inform. Theory, 44 (1998), 1829. doi: 10.1109/18.705562. Google Scholar

[3]

A. H. Banihashemi and I. F. Blake, On the trellis complexity of root lattices and their duals,, IEEE Trans. Inform. Theory, 45 (1999), 2168. doi: 10.1109/18.782169. Google Scholar

[4]

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups,'' 3rd edition,, Springer-Verlag, (1999). Google Scholar

[5]

J. G. D. Forney, Density/length profiles and trellis complexity of lattices,, IEEE Trans. Inform. Theory, 40 (1994), 1753. doi: 10.1109/18.340453. Google Scholar

[6]

S. Han, J. M. Cioffi and J. H. Lee, On the use of hexagonal constellation for peak-to-average power ratio reduction of an OFDM signal,, IEEE Trans. Wireless Comm., 7 (2008), 781. doi: 10.1109/TWC.2007.06104. Google Scholar

[7]

J. E. Humphreys, "Reflection Groups and Coxeter Groups,'', Cambridge University Press, (1990). doi: 10.1017/CBO9780511623646. Google Scholar

[8]

R. G. McKilliam, W. D. Smith, I. Vaughan and L. Clarkson, Linear-time nearest point algorithms for Coxeter lattices,, IEEE Trans. Inform. Theory, 56 (2010), 1015. doi: 10.1109/TIT.2009.2039090. Google Scholar

[9]

T. Mittelholzer, Construction and decoding of optimal group codes from finite reflection groups,, in, (1996). Google Scholar

[10]

T. Mittelholzer and J. Lahtonen, Group codes generated by finite reflection groups,, IEEE Trans. Inform. Theory, 42 (1996), 519. doi: 10.1109/18.485721. Google Scholar

[11]

T. Niyomsataya, A. Miri and M. Nevins, Affine reflection group codes,, IEEE Trans. Inform. Theory, 54 (2008), 441. doi: 10.1109/TIT.2007.911261. Google Scholar

[12]

T. Niyomsataya, A. Miri and M. Nevins, Efficient decoding algorithm for affine reflection group codes of rank 2,, in, (2008), 72. doi: 10.1109/BSC.2008.4563208. Google Scholar

[13]

T. Niyomsataya, A. Miri and M. Nevins, Improving PAPR reduction using tone injection on affine reflection group codes of rank 2,, preprint (based on Ph.D thesis work of the first author)., (). Google Scholar

[14]

D. J. Ryan, I. V. L. Clarkson, I. B. Collings, D. Guo and M. L. Honig, QAM and PSK codebooks for limited feedback MIMO beamforming,, IEEE Trans. Comm., 57 (2009), 1184. doi: 10.1109/TCOMM.2009.04.070178. Google Scholar

[15]

D. J. Ryan, I. B. Collins and J-M. Valin, Reflected simplex codebooks for limited feedback MIMO beamforming,, in, (2009), 1. doi: 10.1109/ICC.2009.5199405. Google Scholar

[16]

D. Slepian, Permutation modulation,, Proc. IEEE, 53 (1965), 228. doi: 10.1109/PROC.1965.3680. Google Scholar

[17]

D. Slepian, Group codes for the Gaussian channel,, Bell System Tech. J., 47 (1968), 575. Google Scholar

[18]

V. Tarokh and A. Vardy, Upper bounds on Trellis complexity of lattices,, IEEE Trans. Inform. Theory, 43 (1997). Google Scholar

[1]

Kanat Abdukhalikov. On codes over rings invariant under affine groups. Advances in Mathematics of Communications, 2013, 7 (3) : 253-265. doi: 10.3934/amc.2013.7.253

[2]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[3]

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

[4]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[5]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

[6]

Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83

[7]

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

[8]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259

[9]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[10]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

[11]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419

[12]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1

[13]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49

[14]

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

[15]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007

[16]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[17]

Jamshid Moori, Amin Saeidi. Some designs and codes invariant under the Tits group. Advances in Mathematics of Communications, 2017, 11 (1) : 77-82. doi: 10.3934/amc.2017003

[18]

Cristina García Pillado, Santos González, Victor Markov, Consuelo Martínez, Alexandr Nechaev. New examples of non-abelian group codes. Advances in Mathematics of Communications, 2016, 10 (1) : 1-10. doi: 10.3934/amc.2016.10.1

[19]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295

[20]

Crnković Dean, Vedrana Mikulić Crnković, Bernardo G. Rodrigues. On self-orthogonal designs and codes related to Held's simple group. Advances in Mathematics of Communications, 2018, 12 (3) : 607-628. doi: 10.3934/amc.2018036

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]