다중 사용자 다중 입출력 시스템에서 Seysen 기법을 이용한 격자 감소 기반 전부호화 기법

송형준(Hyungjoon Song),홍대식(Daesik Hong) 대한전자공학회 2009 電子工學會論文誌-TC (Telecommunications) Vol.46 No.6

본 논문에서는 다중 사용자 다중 입출력 시스템을 위해 격자 감소 기법 기반 전부호화(precoding) 기법에 대해 연구하였다. 송신 단에서 완벽한 채널 상태 정보(CSI : channel state information)를 이용할 수 있을 때, 벡터 분산 기법(VP : vector perturbation)은 큰 채널 전송 용량(sum capacity)을 얻을 수 있으면서 간단한 수신기로 구현될 수 있다<SUP>[1~2]</SUP>. 그러나 VP 기법의 부호화는 비결정적 난해(NP-hard : nondeterministic polynomial time-hard) 문제이다. 이에 반해 격자 감소 기법 기반의 VP 기법은 부호화 복잡도를 크게 줄일 수 있다<SUP>[3]</SUP>. 본 논문에서는 기본 및 이중 베이시스의 동시 감소를 통한 Seysen 격자 감소 기반 VP 기법(VP-SLR : vector perturbation with Seysen's lattice reduction)을 제안한다. 모의실험 결과는 LLL 기반 VP기법(VP-LLL : vector perturbation with Lenstra-Lenstra-Lovasz lattice reduction)에 비해 제안된 VP-SLR 기법이 더 낮은 비트 오류율(BER : bit error rate)과 더 큰 전송 용량을 가짐을 보여준다. We investigate lattice-reduction-aided precoding techniques for multi-user multiple-input multiple-output (MIMO) channels. When assuming full knowledge of the channel state information only at the transmitter, a vector perturbation (VP) is a promising precoding scheme that approaches sum capacity<SUP>[1]</SUP> and has simple receiver<SUP>[2]</SUP>. However, its encoding is nondeterministic polynomial time (NP)-hard problem. Vector perturbation using lattice reduction algorithms can remarkably reduce its encoding complexity<SUP>[3]</SUP>. In this paper, we propose a vector perturbation scheme using Seysen's lattice reduction (VP-SLR) with simultaneously reducing primal basis and dual one. Simulation results show that the proposed VP-SLR has better bit error rate (BER) and larger capacity than vector perturbation with Lenstra-Lenstra-Lovasz lattice reduction (VP-LLL)<SUP>[3]</SUP> in addition to less encoding complexity.

Systolic Arrays for Lattice-Reduction-Aided MIMO Detection

Wang, Ni-Chun,Biglieri, Ezio,Yao, Kung The Korea Institute of Information and Commucation 2011 Journal of communications and networks Vol.13 No.5

Multiple-input multiple-output (MIMO) technology provides high data rate and enhanced quality of service for wireless communications. Since the benefits from MIMO result in a heavy computational load in detectors, the design of low-complexity suboptimum receivers is currently an active area of research. Lattice-reduction-aided detection (LRAD) has been shown to be an effective low-complexity method with near-maximum-likelihood performance. In this paper, we advocate the use of systolic array architectures for MIMO receivers, and in particular we exhibit one of them based on LRAD. The "Lenstra-Lenstra-Lov$\acute{a}$sz (LLL) lattice reduction algorithm" and the ensuing linear detections or successive spatial-interference cancellations can be located in the same array, which is considerably hardware-efficient. Since the conventional form of the LLL algorithm is not immediately suitable for parallel processing, two modified LLL algorithms are considered here for the systolic array. LLL algorithm with full-size reduction-LLL is one of the versions more suitable for parallel processing. Another variant is the all-swap lattice-reduction (ASLR) algorithm for complex-valued lattices, which processes all lattice basis vectors simultaneously within one iteration. Our novel systolic array can operate both algorithms with different external logic controls. In order to simplify the systolic array design, we replace the Lov$\acute{a}$sz condition in the definition of LLL-reduced lattice with the looser Siegel condition. Simulation results show that for LR-aided linear detections, the bit-error-rate performance is still maintained with this relaxation. Comparisons between the two algorithms in terms of bit-error-rate performance, and average field-programmable gate array processing time in the systolic array are made, which shows that ASLR is a better choice for a systolic architecture, especially for systems with a large number of antennas.

ON PAIRWISE GAUSSIAN BASES AND LLL ALGORITHM FOR THREE DIMENSIONAL LATTICES

Kim, Kitae,Lee, Hyang-Sook,Lim, Seongan,Park, Jeongeun,Yie, Ikkwon Korean Mathematical Society 2022 대한수학회지 Vol.59 No.6

For two dimensional lattices, a Gaussian basis achieves all two successive minima. For dimension larger than two, constructing a pairwise Gaussian basis is useful to compute short vectors of the lattice. For three dimensional lattices, Semaev showed that one can convert a pairwise Gaussian basis to a basis achieving all three successive minima by one simple reduction. A pairwise Gaussian basis can be obtained from a given basis by executing Gauss algorithm for each pair of basis vectors repeatedly until it returns a pairwise Gaussian basis. In this article, we prove a necessary and sufficient condition for a pairwise Gaussian basis to achieve the first k successive minima for three dimensional lattices for each k ∈ {1, 2, 3} by modifying Semaev's condition. Our condition directly checks whether a pairwise Gaussian basis contains the first k shortest independent vectors for three dimensional lattices. LLL is the most basic lattice basis reduction algorithm and we study how to use LLL to compute a pairwise Gaussian basis. For δ ≥ 0.9, we prove that LLL(δ) with an additional simple reduction turns any basis for a three dimensional lattice into a pairwise SV-reduced basis. By using this, we convert an LLL reduced basis to a pairwise Gaussian basis in a few simple reductions. Our result suggests that the LLL algorithm is quite effective to compute a basis with all three successive minima for three dimensional lattices.

Systolic Arrays for Lattice-Reduction-Aided MIMO Detection

Ni-Chun Wang,Ezio Biglieri,Kung Yao 한국통신학회 2011 Journal of communications and networks Vol.13 No.5

Multiple-inputmultiple-output (MIMO) technology provides high data rate and enhanced quality of service for wireless communications. Since the benefits from MIMO result in a heavy computational load in detectors, the design of low-complexity suboptimum receivers is currently an active area of research. Latticereduction-aided detection (LRAD) has been shown to be an effective low-complexity method with near-maximum-likelihood performance. In this paper, we advocate the use of systolic array architectures for MIMO receivers, and in particular we exhibit one of them based on LRAD. The “Lenstra-Lenstra-Lov´asz (LLL) lattice reduction algorithm” and the ensuing linear detections or successive spatial-interference cancellations can be located in the same array, which is considerably hardware-efficient. Since the conventional form of the LLL algorithm is not immediately suitable for parallel processing, two modified LLL algorithms are considered here for the systolic array. LLL algorithm with full-size reduction-LLL is one of the versions more suitable for parallel processing. Another variant is the all-swap lattice-reduction (ASLR) algorithm for complex-valued lattices, which processes all lattice basis vectors simultaneously within one iteration. Our novel systolic array can operate both algorithms with different external logic controls. In order to simplify the systolic array design, we replace the Lov´asz condition in the definition of LLL-reduced lattice with the looser Siegel condition. Simulation results show that for LR-aided linear detections, the bit-error-rate performance is still maintained with this relaxation. Comparisons between the two algorithms in terms of bit-error-rate performance, and average field-programmable gate array processing time in the systolic array are made, which shows that ASLR is a better choice for a systolic architecture, especially for systems with a large number of antennas.

SDR 시스템에서 GPU를 사용한 Lattice Reduction-aided 검출기 구현

김태현,이현석,최승원 (사)디지털산업정보학회 2011 디지털산업정보학회논문지 Vol.7 No.3

This paper presents an implementation of Lattice Reduction (LR)-aided detector for Multiple-Input Multiple-Output (MIMO) system using Graphics Processing Unit (GPU). GPU is a parallel processor which has a number of Arithmetic Logic Units (ALUs), thus, it can minimize the operation time of LR algorithm through the parallelization using multiple threads in the GPU. Through the implemented LR-aided detector, we verify that the LR-aided detector operates a lot faster than Maximum Likelihood (ML) detector. The implemented LR-aided detector has been applied to WiMAX system to show the feasibility of its real-time processing. In addition, we demonstrate that the processing time can be reduced at the cost of 3dB SNR loss by limiting the repeating loop in Lenstra-Lenstra-Lovasz (LLL)algorithm which is frequently used in LR-aided detector.

Joint Lattice-Reduction-Aided Precoder Design for Multiuser MIMO Relay System

( Hua Jiang ),( Hao Cheng ),( Lizhen Shen ),( Guoqing Liu ) 한국인터넷정보학회 2016 KSII Transactions on Internet and Information Syst Vol.10 No.7

Lattice reduction (LR) has been used widely in conventional multiple-input multiple-output (MIMO) systems to enhance the performance. However, LR is hard to be applied to the relay systems which are important but more complicated in the wireless communication theory. This paper introduces a new viewpoint for utilizing LR in multiuser MIMO relay systems. The vector precoding (VP) is designed along with zero force (ZF) criterion and minimum mean square error (MMSE) criterion and enhanced by LR algorithm. This implementable precoder design combines nonlinear processing at the base station (BS) and linear processing at the relay. This precoder is capable of avoiding multiuser interference (MUI) at the mobile stations (MSs) and achieving excellent performance. Moreover, it is shown that the amount of feedback information is much less than that of the singular value decomposition (SVD) design. Simulation results show that the proposed scheme using the complex version of the Lenstra--Lenstra--Lovasz (LLL) algorithm significantly improves system performance.

Block-Mode Lattice Reduction for Low-Complexity MIMO Detection

최권휴,Hannah Kim,김수영,Young-Il Kim 한국전자통신연구원 2012 ETRI Journal Vol.34 No.1

We propose a very-low-complexity lattice-reduction (LR) algorithm for multi-input multi-output detection in time-varying channels. The proposed scheme reduces the complexity by performing LR in a block-wise manner. The proposed scheme takes advantage of the temporal correlation of the channel matrices in a block and its impact on the lattice transformation matrices during the LR process. From this, the proposed scheme can skip a number of redundant LR processes for consecutive channel matrices and performs a single LR in a block. As the Doppler frequency decreases, the complexity reduction efficiency becomes more significant.

A New Approach to Proposition Set Reduction Based on the Minimal Transversal of Waned Values Hypergraph

Liang Yan,Wu Jie,Ma Yuan 보안공학연구지원센터 2016 International Journal of Hybrid Information Techno Vol.9 No.7

It is an important foundation for the in-depth application of the propositional logic to compute all reductions, and this is a hot subject at present. This paper defines the identity element concept and the zero element concept in concept lattice. It proves that the minimal transversal of waned values hypergraph of zero element concept is a reduction in inducible context, and it also proves that the minimal transversal set is a full reduction set. Furthermore, the paper presents a new method based on intent waned values and hypergraph minimal transversal of concept lattice. By this method, all reductions can be quickly computed all at once. It develops the reducing algorithm. Compared with the original algorithm, which compute a reduction every time in first and gradually aggregate all reductions, the operating number of the improved algorithm is remarkably reduced. The approach has the remarkable advantages and good results.

Attribute Reduction in Property Oriented Concept Lattices of Formal Contexts and Formal Decision Contexts

Junyu Li,Zeng Qiang,Xia Wang 보안공학연구지원센터 2016 International Journal of Database Theory and Appli Vol.9 No.9

This paper studies notions and approaches to attribute reduction in property oriented concept lattices of formal contexts and formal decision contexts based on congruence relations. Firstly, dependence space based on the property oriented concept lattice is researched to obtain the relationship among property oriented concept lattices and the corresponding congruence relations. Then notions of attribute reduction is defined for formal contexts and decision contexts to find minimal attribute subsets which can preserve all congruence classes determined by the original attribute set, and also keep all property oriented extents and their original hierarchy in the property oriented concept lattice. Finally, approaches of discernibility matrix are presented to calculate all attribute reducts.

Lattice Reduction-Aided Successive Interference Cancelation for MIMO Interference Channels

Jaehyun Park,Clerckx, Bruno,Joohwan Chun,Byung Jang Jeong IEEE 2014 IEEE Transactions on Vehicular Technology VT Vol.63 No.8

<P>In multiple-input-multiple-ouput (MIMO) interference channels (IFCs), interference alignment (IA) with zero-forcing (ZF) linear detection can be used to achieve the maximum degrees of freedom (DoFs). However, ZF linear detection usually degrades the performance due to the noise enhancement in practical systems. In this paper, we propose lattice reduction (LR)-aided successive interference cancelation (SIC) in conjunction with IA over lattice for three-user (and extendable to $K$-user) MIMO IFCs in which the interfering signals aligned over the lattices are detected and canceled rather than nulled out. To complete the proposed LR-aided SIC method, the detection ordering and the precoding matrix that minimize the mean square error are also determined.</P>