Analysis of Lattice based Algorithms in Wireless Communication

Analysis of Lattice based Algorithms in Wireless Communication

1Maheshwari M

PG Student, ECE Department SSN College of Engineering Chennai, India

2Joseph Gladwin S

Assistant Professor, ECE Department SSN College of Engineering Chennai, India

AbstractLattice reduction (LR) techniques are developed to

antennas and N receive antennas

M N were considered,

improve the performance of multiple-input multiple-output (MIMO) digital communication system. In cryptographic methods the lattice problems are high that is the problem of finding short basis is more. This type of reduction problem have a great impact on many areas of technology mainly in modern

where different transmit antennas is denoted as different users.

Considering the vectors,

cryptanalysis.

Y [Y , Y ,….,Y ]T

(1)

In this paper analysis of various LR technique were carried out based on its speed on the basis of number of operations

1 2 N

T

during the reduction process and also we analyze the path detection of information to be transmitted based on reduced lattice points.

Keywords Lattice reduction; size reduction; gram schmidt orthogonalization; babai point; lenstra lenstra lovasz; schnoor-

X [X1, X2,….,XM ]

W [W1, W2,, WN]T

(2)

(3)

euchner.

1. INTRODUCTION

   to be the transmitted, the noise vector and the channel matrix

   respectively. The channel model is described by the following equation

   Lattice reduction (LR) has been proposed in the context of multiple input multiple output (MIMO) systems as a

   Y HX W

   (4)

   means of improving the performance of sub-optimal detectors [9]. This is achieved by pre-processing followed in MIMO channel by an LR algorithm [3], which transforms the channel into a more orthogonal form. The lattice reduction

   1. has been successfully used in signal processing applications for global positioning system (GPS), frequency estimation, particularly data detection and pre-coding in wireless communication systems. Beyond mathematics , lattice have various diverse applications such as cryptography, coding theory and so on. It is also used to develop highly realistic source and channel codes for various communication applications, specifically in multiple terminals.

      This paper is on the basis of analyzing various lattice reduction algorithms Lenstra [15] and Schnoor-Euchner with its speed and path detection of the information to be

      The channel is considered to be Rayleigh and the noise is

      Gaussian that is the elements of H are independent and identically distributed with the zero-mean unit-variance complex Gaussian distribution [4]. The following were the steps involved in LLL algorithm

      • Gram Schmidt Orthogonalization (GSO)

      • Size-reduction

      • Swapping & updating GSO

   Gram Schmidt Orthogonalization (GSO) :

   The orthogonalization is done by using the following equation

   V , V

   transmitted with-respect to the number of operations and the

   V V

   i1 i j

   V

   (5)

   reduced lattice points respectively [16].

   i i j1

   * 2 j

2. ALGORITHMS BASED ON LATTICE REDUCTION

   1. Lenstra Lenstra Lovasz (LLL) algorithm

      In a basis-reduction algorithm, the so called LLL basis reduction [2] is introduced which results in relatively short basis vectors with a polynomial-time computational complexity. A multiple-antenna system with M transmit

      Vj

      i 1,2,…..,m, m is number of column vectors.

      V , V

      1. The condition of size reduction is stronger if

         Where ,

         i j

         ij 2

         V

         V

         *

         j

         (6)

         2

         ij 0.5

         resulting in fewer size reduction

         Size- reduction :

         computations.

      2. The algorithm checks if

      Re

      k,k1

      0.5 or

      The size-reduction that is in order to reduce the elements of the channel matrix the following equation were taken into account

      Im

      k,k1

      0.5 before doing size-reduction.

      Vi Vi

      • round

      V

      (7)

      The check will avoid unnecessary operations, thus the computational complexity is reduced with increase in speed of the algorithmic computations.

      ij

      ij

      j

      j

      Swapping & updating GSO:

      Swapping the current size reduced vectors and updating GSO using orthogonalization process.

   2. Complex Lenstra Lenstra Lovasz (CLLL) algorithm

      The average overall complexity of the complex LLL (CLLL) algorithm is almost half of the real LLL (RLLL) algorithm. In lattice-reduction decoding the CLLL achieve full diversity as that of RLLL. Whereas the bit-error-rate (BER) performance of both the reduced basis with the help of CLLL and RLLL in MIMO detection schemes contribute to be in similar manner. Compare to RLLL, the CLLL compute less complexity because of the avoidance of doubling the channel matrix dimension. Thus, it can reduce the complexity of other parts of the MIMO detector also. By considering the received Symbol vector Y , complex baseband equivalent model can be expressed as

   3. Schnoor-Euchner (SE) algorithm

      The Schnorr-Euchner algorithm [10] was used in cryptography applications and also mainly in sphere decoding [11]. This algorithm has the same principle as the Viterbo- Boutrous (VB), which is used for the closest point search [13]. It is based on the following two stages.

      • The first stage consists of finding the Babai point (BP), which is not similar to that of closest point. This point derive bounding error.

      • In the second stage, modification of the BP is repeated until the closest point [12] is found. If the BP is very far from the closest point, then the signal to noise ratio (SNR) is low which makes the algorithm to take more time to converge. However, if the BP is close to the closest point, then the SNR is high which makes the algorithm to converge in less time.

        Y HS V

        (8)

   4. Schnoor-Euchner Adaptive Search Radius Algorithm

   It is similar to that of SEA, where node without children

   H is a flat fading channel matrix, S is a complex transmit

   signal vector of NT dimensional, V is a Complex Gaussian

   were also applicable and the next siblings is analysed by boundary control. By stacking complex to real conversion is done before Schnoor-Euchner Adaptive LAST (SEAL)

   noise vector of NR dimensional.

   H QR

   (9)

   sphere algorithm.

3. ANALYSIS OF ALGORITHM IN MATLAB

   H, Q is NR NT dimensional

   R is NT NT dimensional.

   The following were the steps involved in CLLL algorithm

   • GSO: A modified orthogonalization is followed compare to LLL.

   Analysis of LLL and SE algorithm were carried out using matlab simulation tool. The following simulation results were done .

   1. Realization of Lenstra algorithm based on lattice reduction

      Considering a two dimensional square matrix,

      • Size reduction: Similar to the reduction method used in LLL .

        A 1

        3

        2

        4

      • Basis vector swapping: Initially as in LLL , here also the basis vectors were swapped. The idea is that, after swapping, size reduction can be repeated to make basis vectors shorter.

        The performance f CLLL is improved from that of LLL because of the use of following conditions.

        Fig. 1. shows the elements of the channel matrix row wise indicating,

        A:,1 1 the first column vector of A matrix and

        3

        A:,2 2 the second column vector of A matrix.

        4

        The number of vectors will vary according to the matrix dimension.

        Fig. 1. Elements of the channel matrix before lattice reduction.

        Fig. 2. Elements of the channel matrix after lattice reduction.

        Fig. 2. shows representation of less complexity based reduced form of channel matrix due to lattice reduction in Euclidian space. Thus as the elements value reduction will be directly proportional to the orthogonality too.

   2. Realization of Schnoor-Euchner algorithm for path detection of the information based on lattice points

   In Fig.3.

   • The closest lattice point is identified based on the weight of each point which is denoted as node.

   • If the weight of the node is less than the distance between the current and the nearest lattice point. This distance threshold is initially set to infinity.

   • If the weight of the node under is larger than the distance threshold, the current search path is terminated since it cannot lead to a closest lattice point.

   Fig. 3.Path with-respect to lattice points

   Fig. 4.Weight with-respect to each lattice points

   In Fig. 4.the weight of the lattice points is represented in such a way that the previous lattice point weight must be lesser the current lattice point weight.

4. CONCLUSION

In this paper analysis of various algorithm based on lattice-reduction were carried out. LLL algorithm makes more number of operations in complex channel rather than real channel because of the absence of complexity due to imaginary part. Whereas the number of operations is reduced for both complex and real channel in CLLL algorithm due to the conditions followed in size reduction based on the mean square value.

For path detection with respect to lattice points analysis of schnoor-euchner algorithm was carried out, where real channel can be applicable in SEAL and complex channel for SEA. Using Schnoor the path of the information where the effect of external disturbance is maintained to be less in impact is analysed with the help of the lattice points and the lattice points were considered to be identified such that their weight must be in descending order from its initial lattice point.

REFERENCES

1. Mahmoud Taherzadeh, Amin Mobasher and Amir K.Khandani, Communication Over MIMO Broadcast Channels Using Lattice-Basis Reduction, IEEE Trans. on Information theory, vol. 53, no. 12, Dec. 2007.

2. Taherzadeh, A.Mobasher and A.K.Khandani, LLL reduction achieves the receive diversity in MIMO decoding, IEEE Trans. on Information Theory, vol. 53, no. 12, Dec. 2007, pp. 48014805.

3. Wubben and D.Seethaler, On the performance of lattice reduction schemes for MIMO data detection, in Proc. IEEE Asilomar, Pacific Grove, CA, Nov. 2007, pp. 15341538.

4. Bruderer, C.Studer, D.Seethaler, M.Wenk, and A.Burg, VLSI implementation of a low-complexity LLL lattice reduction algorithm for MIMO detection, in Proc. IEEE ISCAS, Paris, France,May 2010,pp. 37453748.

5. P.Nguyen, J. Stern, The two faces of lattices in cryptology, in Proc CALC, Springer, LNCS, vol. 2146, 2001, pp.146180.

6. YAP. Fundamental problems in algorithmic algebra, Princeton University Press 1996.

7. H. W. Lenstra, Integer programming with a fixed number of variables, Mathematics of Operations Research, vol. 8, 4, 1983, pp.538548.

8. H. COHEN. A course in Computational Algebraic Number Theory, GTM 138, Springer Verlag, 4th Edition 2000.

9. Yao and G. W. Wornell, Lattice-reduction-aided detectors for MIMO communication systems, in Proc. IEEE GLOBECOM, vol. 1, Taipei, Taiwan, Nov. 2002, pp.424428.

10. Zhan Guo and Peter Nilsson. Reduced Complexity SchnorrEuchner Decoding Algorithms for MIMO systems, in Proc. IEEE Communications Letters, vol. 8, no. 5, May 2004.

11. J. Jald en and B. Ottersten, On the complexity of sphere decoding in digital communications,IEEE Trans. on Signal Process-ing,vol. 53, no. 4, pp. 14741484, 2005.

12. M. O. Damen, H. E. Gamal, and G. Caire, On maximum likeli-hood detection and the search for the closest lattice point,IEEE Trans. on Information Theory, vol. 49, no. 10, pp. 23892402, 2003.

13. E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, Closest point search in lattices,IEEE Trans. on Information Theory, vol. 48, no. 8, pp. 2201 2214, 2002.

14. C. Schnorr and M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems,Mathemat-ical Programming, vol. 66, pp. 181191, 1994.

15. L. Babai, On Lovasz lattice reduction and the nearest lattice point problem,Combinatorica, vol. 6, no. 1, pp. 113, 1986

16. B. A. LaMacchia, Basis reduction algorithms and subset sum problems, Masters thesis, Massachusetts Inst. Technol., May 1991