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]

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

[2]

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

[3]

Susanne Pumplün, Thomas Unger. Space-time block codes from nonassociative division algebras. Advances in Mathematics of Communications, 2011, 5 (3) : 449-471. doi: 10.3934/amc.2011.5.449

[4]

Frédérique Oggier, B. A. Sethuraman. Quotients of orders in cyclic algebras and space-time codes. Advances in Mathematics of Communications, 2013, 7 (4) : 441-461. doi: 10.3934/amc.2013.7.441

[5]

David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35

[6]

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

[7]

David Grant, Mahesh K. Varanasi. The equivalence of space-time codes and codes defined over finite fields and Galois rings. Advances in Mathematics of Communications, 2008, 2 (2) : 131-145. doi: 10.3934/amc.2008.2.131

[8]

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

[9]

Hassan Khodaiemehr, Dariush Kiani. High-rate space-time block codes from twisted Laurent series rings. Advances in Mathematics of Communications, 2015, 9 (3) : 255-275. doi: 10.3934/amc.2015.9.255

[10]

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

[11]

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

[12]

Zbigniew Bartosiewicz, Ülle Kotta, Maris Tőnso, Małgorzata Wyrwas. Accessibility conditions of MIMO nonlinear control systems on homogeneous time scales. Mathematical Control & Related Fields, 2016, 6 (2) : 217-250. doi: 10.3934/mcrf.2016002

[13]

Xiongxiong Bao, Wenxian Shen, Zhongwei Shen. Spreading speeds and traveling waves for space-time periodic nonlocal dispersal cooperative systems. Communications on Pure & Applied Analysis, 2019, 18 (1) : 361-396. doi: 10.3934/cpaa.2019019

[14]

Yuming Zhang. On continuity equations in space-time domains. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 4837-4873. doi: 10.3934/dcds.2018212

[15]

Gerard A. Maugin, Martine Rousseau. Prolegomena to studies on dynamic materials and their space-time homogenization. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1599-1608. doi: 10.3934/dcdss.2013.6.1599

[16]

Dmitry Turaev, Sergey Zelik. Analytical proof of space-time chaos in Ginzburg-Landau equations. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1713-1751. doi: 10.3934/dcds.2010.28.1713

[17]

Montgomery Taylor. The diffusion phenomenon for damped wave equations with space-time dependent coefficients. Discrete & Continuous Dynamical Systems - A, 2018, 38 (11) : 5921-5941. doi: 10.3934/dcds.2018257

[18]

Chaoxu Pei, Mark Sussman, M. Yousuff Hussaini. A space-time discontinuous Galerkin spectral element method for the Stefan problem. Discrete & Continuous Dynamical Systems - B, 2018, 23 (9) : 3595-3622. doi: 10.3934/dcdsb.2017216

[19]

Vincent Astier, Thomas Unger. Galois extensions, positive involutions and an application to unitary space-time coding. Advances in Mathematics of Communications, 2019, 13 (3) : 513-516. doi: 10.3934/amc.2019032

[20]

Dong-Ho Tsai, Chia-Hsing Nien. On space-time periodic solutions of the one-dimensional heat equation. Discrete & Continuous Dynamical Systems - A, 2019, 0 (0) : 0-0. doi: 10.3934/dcds.2020037

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (2)

[Back to Top]