 Open Access
 Total Downloads : 12
 Authors : Maheshwari M, Joseph Gladwin S
 Paper ID : IJERTCONV3IS16017
 Volume & Issue : TITCON – 2015 (Volume 3 – Issue 16)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 multipleinput multipleoutput (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.

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 suboptimal detectors [9]. This is achieved by preprocessing followed in MIMO channel by an LR algorithm [3], which transforms the channel into a more orthogonal form. The lattice reduction

has been successfully used in signal processing applications for global positioning system (GPS), frequency estimation, particularly data detection and precoding 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 SchnoorEuchner 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 zeromean unitvariance complex Gaussian distribution [4]. The following were the steps involved in LLL algorithm

Gram Schmidt Orthogonalization (GSO)

Sizereduction

Swapping & updating GSO

Gram Schmidt Orthogonalization (GSO) :
The orthogonalization is done by using the following equation
V , V
transmitted withrespect to the number of operations and the
V V
i1 i j
V
(5)
reduced lattice points respectively [16].
i i j1
* 2 j


ALGORITHMS BASED ON LATTICE REDUCTION

Lenstra Lenstra Lovasz (LLL) algorithm
In a basisreduction algorithm, the so called LLL basis reduction [2] is introduced which results in relatively short basis vectors with a polynomialtime computational complexity. A multipleantenna system with M transmit
Vj
i 1,2,…..,m, m is number of column vectors.
V , V

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.

The algorithm checks if
Re
k,k1
0.5 or
The sizereduction 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 sizereduction.
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.


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 latticereduction decoding the CLLL achieve full diversity as that of RLLL. Whereas the biterrorrate (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

SchnoorEuchner (SE) algorithm
The SchnorrEuchner 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)


SchnoorEuchner 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 SchnoorEuchner Adaptive LAST (SEAL)
noise vector of NR dimensional.
H QR
(9)
sphere algorithm.


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 .

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.


Realization of SchnoorEuchner 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 withrespect to lattice points
Fig. 4.Weight withrespect 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.


CONCLUSION
In this paper analysis of various algorithm based on latticereduction 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 schnooreuchner 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

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

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.

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.

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

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

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

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

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

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

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

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

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

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.

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

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

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