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]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065

[2]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[3]

Ivan Bailera, Joaquim Borges, Josep Rifà. On Hadamard full propelinear codes with associated group $ C_{2t}\times C_2 $. Advances in Mathematics of Communications, 2021, 15 (1) : 35-54. doi: 10.3934/amc.2020041

[4]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124

[5]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129

[6]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044

[7]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038

[8]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[9]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053

[10]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055

[11]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054

[12]

Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120

[13]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049

[14]

Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039

[15]

Tingting Wu, Li Liu, Lanqiang Li, Shixin Zhu. Repeated-root constacyclic codes of length $ 6lp^s $. Advances in Mathematics of Communications, 2021, 15 (1) : 167-189. doi: 10.3934/amc.2020051

[16]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122

[17]

Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127

[18]

Shin-Ichiro Ei, Masayasu Mimura, Tomoyuki Miyaji. Reflection of a self-propelling rigid disk from a boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 803-817. doi: 10.3934/dcdss.2020229

[19]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067

[20]

Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020123

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]