# American Institute of Mathematical Sciences

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

2018 Impact Factor: 0.879