February  2012, 6(1): 1-26. doi: 10.3934/amc.2012.6.1

Algebraic reduction for the Golden Code

1. 

Department of Electrical and Electronic Engineering, Imperial College London, London SW7 2AZ, United Kingdom

2. 

Département COMELEC, Télécom-ParisTech, 46, rue Barrault, 75013 Paris, France, France

Received  February 2010 Revised  October 2011 Published  January 2012

We introduce a new right preprocessing approach, called algebraic reduction, for the decoding of algebraic space-time block codes which are designed using maximal orders in division algebras. Unlike existing lattice-reduction aided decoding techniques, algebraic reduction exploits the multiplicative structure of the code. Its principle is to absorb part of the channel into the code, by approximating the channel matrix with a unit of the maximal order of the corresponding algebra.
    In the case of $2 \times 2$ space-time codes, we propose a low-complexity algorithm to approximate a channel with a unit, and apply it to the Golden Code. Simulation results for the Golden Code evidence that algebraic reduction has the same performance of LLL reduction but significantly lower complexity.
    We also show that for MIMO systems with $n$ receive and $n$ transmit antennas, algebraic reduction attains the receive diversity when followed by a simple ZF detection. However, establishing the approximation algorithm for higher dimensional codes remains an open problem.
Citation: Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
References:
[1]

J.-C. Belfiore, G. Rekaya and E. Viterbo, The golden code: a $2 \times 2$ full-rate space-time code with non-vanishing determinants,, IEEE Trans. Inform. Theory, 51 (2005), 1432.  doi: 10.1109/TIT.2005.844069.  Google Scholar

[2]

J. W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups,, Geometriae Dedicata, 16 (1984), 123.  doi: 10.1007/BF00146825.  Google Scholar

[3]

C. Corrales, E. Jespers, G. Leal and A. del Rio, Presentations of the unit group of an order in a non-split quaternion algebra,, Adv. Math., 186 (2004), 498.  doi: 10.1016/j.aim.2003.07.015.  Google Scholar

[4]

M. O. Damen, H. El Gamal and G. Caire, MMSE-GDFE lattice decoding for solving under-determined linear systems with integer unknowns,, in, (2004).   Google Scholar

[5]

A. Edelman, "Eigenvalues and Condition Numbers of Random Matrices,'', Ph.D thesis, (1989).   Google Scholar

[6]

J. Elstrodt, F. Grunewald and J. Mennicke, "Groups Acting on Hyperbolic Space,'', Springer, (1998).   Google Scholar

[7]

D. Epstein and C. Petronio, An exposition of Poincaré's polyhedron theorem,, L'Enseignement Mathématique, 40 (1994), 113.   Google Scholar

[8]

Y. H. Gan, C. Ling and W. H. Mow, Complex lattice reduction algorithm for low-complexity MIMO detection,, IEEE Trans. Signal Process., 57 (2009), 2701.  doi: 10.1109/TSP.2009.2016267.  Google Scholar

[9]

N. R. Goodman, The distribution of the determinant of a complex Wishart distributed matrix,, Ann. Math. Statist., 34 (1963), 178.  doi: 10.1214/aoms/1177704251.  Google Scholar

[10]

J. Jaldén and P. Elia, DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models,, IEEE Trans. Inform. Theory, 56 (2010), 4765.  doi: 10.1109/TIT.2010.2059493.  Google Scholar

[11]

J. Jaldén and B. Ottersten, On the Complexity of Sphere Decoding In Digital Communications,, IEEE Trans. Signal Process., 53 (2005), 1474.  doi: 10.1109/TSP.2005.843746.  Google Scholar

[12]

E. Kleinert, "Units of Classical Orders: A Survey,'', L'Enseignement Mathématique, 40 (1994), 205.   Google Scholar

[13]

E. Kleinert, "Units in Skew-Fields,'', Birkäuser, (2000).   Google Scholar

[14]

L. Luzzi, G. Rekaya-Ben Othman, J.-C. Belfiore and E. Viterbo, Golden space-time block coded modulation,, IEEE Trans. Inform. Theory, 55 (2009), 584.  doi: 10.1109/TIT.2008.2009846.  Google Scholar

[15]

C. Maclachlan and A. W. Reid, "The Arithmetic of Hyperbolic 3-Manifolds,'', Springer, (2003).   Google Scholar

[16]

A. D. Murugan, H. El Gamal, M. O. Damen and G. Caire, A unified framework for tree search decoding: rediscovering the sequential decoder,, IEEE Trans. Inform. Theory, 52 (2006), 933.  doi: 10.1109/TIT.2005.864418.  Google Scholar

[17]

F. Oggier, G. Rekaya, J.-C. Belfiore and E. Viterbo, Perfect space-time block codes,, IEEE Trans. Inform. Theory, 52 (2006), 3885.  doi: 10.1109/TIT.2006.880010.  Google Scholar

[18]

A. Page, "Computing Fundamental Domains for Arithmetic Kleinian Groups,'', Master thesis, (2010).   Google Scholar

[19]

J. Proakis, "Digital Communications,'', McGraw-Hill, (2001).   Google Scholar

[20]

K. Raj Kumar, G. Caire and A. L. Moustakas, Asymptotic performance of linear receivers in MIMO fading channels,, IEEE Trans. Inform. Theory, 55 (2009), 4398.  doi: 10.1109/TIT.2009.2027544.  Google Scholar

[21]

G. Rekaya, J.-C. Belfiore and E. Viterbo, A very efficient lattice reduction tool on fast fading channels,, in, (2004).   Google Scholar

[22]

B. A. Sethuraman, B. Sundar Rajan and V. Shashidar, Full-diversity, high-rate space-time block codes from division algebras,, IEEE Trans. Inform. Theory, 49 (2003), 2596.  doi: 10.1109/TIT.2003.817831.  Google Scholar

[23]

R. G. Swan, Generators and relations for certain special linear groups,, Adv. Math., 6 (1971), 1.  doi: 10.1016/0001-8708(71)90027-2.  Google Scholar

[24]

M. Taherzadeh, A. Mobasher and A. K. Khandani, LLL reduction achieves the receive diversity in MIMO decoding,, IEEE Trans. Inform. Theory, 53 (2007), 4801.  doi: 10.1109/TIT.2007.909169.  Google Scholar

[25]

R. Vehkalahti, C. Hollanti, J. Lahtonen and K. Ranto, On the densest MIMO lattices from cyclic division algebras,, IEEE Trans. Inform. Theory, 55 (2009), 3751.  doi: 10.1109/TIT.2009.2023713.  Google Scholar

[26]

M.-F. Vignéras, "Arithmétique des Algèbres de Quaternions,'', Springer-Verlag, (1980).   Google Scholar

[27]

E. W. Weisstein, Circle-Circle Intersection,, from MathWorld-A Wolfram Web Resource, ().   Google Scholar

show all references

References:
[1]

J.-C. Belfiore, G. Rekaya and E. Viterbo, The golden code: a $2 \times 2$ full-rate space-time code with non-vanishing determinants,, IEEE Trans. Inform. Theory, 51 (2005), 1432.  doi: 10.1109/TIT.2005.844069.  Google Scholar

[2]

J. W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups,, Geometriae Dedicata, 16 (1984), 123.  doi: 10.1007/BF00146825.  Google Scholar

[3]

C. Corrales, E. Jespers, G. Leal and A. del Rio, Presentations of the unit group of an order in a non-split quaternion algebra,, Adv. Math., 186 (2004), 498.  doi: 10.1016/j.aim.2003.07.015.  Google Scholar

[4]

M. O. Damen, H. El Gamal and G. Caire, MMSE-GDFE lattice decoding for solving under-determined linear systems with integer unknowns,, in, (2004).   Google Scholar

[5]

A. Edelman, "Eigenvalues and Condition Numbers of Random Matrices,'', Ph.D thesis, (1989).   Google Scholar

[6]

J. Elstrodt, F. Grunewald and J. Mennicke, "Groups Acting on Hyperbolic Space,'', Springer, (1998).   Google Scholar

[7]

D. Epstein and C. Petronio, An exposition of Poincaré's polyhedron theorem,, L'Enseignement Mathématique, 40 (1994), 113.   Google Scholar

[8]

Y. H. Gan, C. Ling and W. H. Mow, Complex lattice reduction algorithm for low-complexity MIMO detection,, IEEE Trans. Signal Process., 57 (2009), 2701.  doi: 10.1109/TSP.2009.2016267.  Google Scholar

[9]

N. R. Goodman, The distribution of the determinant of a complex Wishart distributed matrix,, Ann. Math. Statist., 34 (1963), 178.  doi: 10.1214/aoms/1177704251.  Google Scholar

[10]

J. Jaldén and P. Elia, DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models,, IEEE Trans. Inform. Theory, 56 (2010), 4765.  doi: 10.1109/TIT.2010.2059493.  Google Scholar

[11]

J. Jaldén and B. Ottersten, On the Complexity of Sphere Decoding In Digital Communications,, IEEE Trans. Signal Process., 53 (2005), 1474.  doi: 10.1109/TSP.2005.843746.  Google Scholar

[12]

E. Kleinert, "Units of Classical Orders: A Survey,'', L'Enseignement Mathématique, 40 (1994), 205.   Google Scholar

[13]

E. Kleinert, "Units in Skew-Fields,'', Birkäuser, (2000).   Google Scholar

[14]

L. Luzzi, G. Rekaya-Ben Othman, J.-C. Belfiore and E. Viterbo, Golden space-time block coded modulation,, IEEE Trans. Inform. Theory, 55 (2009), 584.  doi: 10.1109/TIT.2008.2009846.  Google Scholar

[15]

C. Maclachlan and A. W. Reid, "The Arithmetic of Hyperbolic 3-Manifolds,'', Springer, (2003).   Google Scholar

[16]

A. D. Murugan, H. El Gamal, M. O. Damen and G. Caire, A unified framework for tree search decoding: rediscovering the sequential decoder,, IEEE Trans. Inform. Theory, 52 (2006), 933.  doi: 10.1109/TIT.2005.864418.  Google Scholar

[17]

F. Oggier, G. Rekaya, J.-C. Belfiore and E. Viterbo, Perfect space-time block codes,, IEEE Trans. Inform. Theory, 52 (2006), 3885.  doi: 10.1109/TIT.2006.880010.  Google Scholar

[18]

A. Page, "Computing Fundamental Domains for Arithmetic Kleinian Groups,'', Master thesis, (2010).   Google Scholar

[19]

J. Proakis, "Digital Communications,'', McGraw-Hill, (2001).   Google Scholar

[20]

K. Raj Kumar, G. Caire and A. L. Moustakas, Asymptotic performance of linear receivers in MIMO fading channels,, IEEE Trans. Inform. Theory, 55 (2009), 4398.  doi: 10.1109/TIT.2009.2027544.  Google Scholar

[21]

G. Rekaya, J.-C. Belfiore and E. Viterbo, A very efficient lattice reduction tool on fast fading channels,, in, (2004).   Google Scholar

[22]

B. A. Sethuraman, B. Sundar Rajan and V. Shashidar, Full-diversity, high-rate space-time block codes from division algebras,, IEEE Trans. Inform. Theory, 49 (2003), 2596.  doi: 10.1109/TIT.2003.817831.  Google Scholar

[23]

R. G. Swan, Generators and relations for certain special linear groups,, Adv. Math., 6 (1971), 1.  doi: 10.1016/0001-8708(71)90027-2.  Google Scholar

[24]

M. Taherzadeh, A. Mobasher and A. K. Khandani, LLL reduction achieves the receive diversity in MIMO decoding,, IEEE Trans. Inform. Theory, 53 (2007), 4801.  doi: 10.1109/TIT.2007.909169.  Google Scholar

[25]

R. Vehkalahti, C. Hollanti, J. Lahtonen and K. Ranto, On the densest MIMO lattices from cyclic division algebras,, IEEE Trans. Inform. Theory, 55 (2009), 3751.  doi: 10.1109/TIT.2009.2023713.  Google Scholar

[26]

M.-F. Vignéras, "Arithmétique des Algèbres de Quaternions,'', Springer-Verlag, (1980).   Google Scholar

[27]

E. W. Weisstein, Circle-Circle Intersection,, from MathWorld-A Wolfram Web Resource, ().   Google Scholar

[1]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

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

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[4]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364

[5]

Shuang Chen, Jinqiao Duan, Ji Li. Effective reduction of a three-dimensional circadian oscillator model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020349

[6]

Annegret Glitzky, Matthias Liero, Grigor Nika. Dimension reduction of thermistor models for large-area organic light-emitting diodes. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020460

[7]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[8]

Ilyasse Lamrani, Imad El Harraki, Ali Boutoulout, Fatima-Zahrae El Alaoui. Feedback stabilization of bilinear coupled hyperbolic systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020434

[9]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[10]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461

[11]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[12]

Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137

[13]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336

[14]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[15]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[16]

João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138

[17]

Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

[18]

Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318

[19]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[20]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (44)
  • HTML views (0)
  • Cited by (3)

[Back to Top]