# Feedback Overhead in the FDD Downlink Massive MIMO System

Authors: Papis Ndiaye; Moussa Diallo
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

One of the fundamental problems in massive multiple input multiple output (MMIMO) systems based on the frequency division duplexing (FDD) mode is the acquisition of the channel state information at the base station (BS). Indeed, in these systems, the reciprocity of the uplink (UL) and downlink (DL) channels is not applicable. Thus, the users are supposed, after having estimated their subchannels, to feedback them to the BS. Since the size of the information to be returned is proportional to the number of base station antennas that is very large, then we witness an excess of the number to be returned for each user. It is therefore essential to find a way to reduce this quantity, which affects the overall performance of the system. In this article, we propose two new MMIMO-OFDM-FDD-DL schemas based on the Givens rotation quantization used in the 802.11ac standard to reduce the amount of information to be returned for each user. The first is a fusion between the Givens rotation (GR) and the arithmetic coding (AC) technique, and the second is based on the combination of the GR method and the universal compression technique, Lempel Ziv Welch (LZW). The proposed schemes named GR & AC and GR & LZW (with an improvement of this proposal based on a modified version of LZW (LZWM) named GR & LZWM) for the first and second, respectively, are compared and both can achieve a compression ratio of up to 95% (or even 98%) and 83%, considerably exceeding recent advanced techniques.


---

## Body

## 1. Introduction

MMIMO systems can significantly increase the capacity and energy efficiency of communication systems by using an excessive number of antennas (more than 100 at the BS). It has been shown in [1] that increasing the number of antennas at the BS is always beneficial even with a very noisy channel estimate, because in this case, the BS can recover information even with a low signal-to-noise ratio (SNR). This strongly justifies the use of a very large number of transmit antennas compared to current cellular systems [2]. This is the reason this technology has been named as the most promising for 5G and 6G communications.Note that in the MMIMO technology, obtaining the channel state information (CSI) for transmission (BS) and reception (mobile station) is essential for beamforming, signal detection, and optimization of resources allocation. Moreover, the manner of obtaining this CSI differs generally with respect to the mode of duplexing used. There are two nowadays: the time domain duplexing (TDD) mode and the frequency domain duplexing (FDD) mode.In the TDD mode, the CSI can be easily obtained at BS. Indeed, in this mode, each user sends their pilot symbol to the BS and the BS estimates all subchannels. Since in the TDD mode there is reciprocity of the downlink and uplink channels, we only need one to deduce the other. Therefore, after estimating the channels in the uplink, the BS knows those in the downlink in an implicit way. Unlike the TDD mode, in the FDD mode, the downlink and uplink channels cannot be considered reciprocal: they are different. In this case, it is up to the BS to send the pilot symbols in a broadcast, and the estimation of the downlink subchannels will be done at the level of each user to obtain the CSI. After that, each CSI is sent back to the BS. Since the characteristic of MMIMO systems is the presence of several antennas at the BS, we witness not only an excess of pilot symbols to estimate the transmission channel but also the amount of feedback information becomes essential. Therefore, a fundamental question arises: in a FDD MMIMO system, how to significantly reduce the feedback overhead?The answer to this question is so unclear that early work on MMIMO systems [2, 3] chose the TDD mode which is more reasonable and easy to use in this context. Recall that in the TDD mode, even if the downlink and uplink channels are reciprocal, the front-end radios are not, and there are problems of calibration, synchronization, and pilot contamination. In addition, the most current wireless communication networks operate in FDD mode. Thus, the answer to this question becomes a capital necessity. In other words, it would be interesting to see how to use the FDD mode optimally in MMIMO systems. This is the reason this work will focus on this issue.All works that have attempted to address this problem can be categorized as follows.(i)
The codebook principle is widely used. This technique consists of building a codebook (using the Grassmann manifold theory, for example) available at the transmitter and the receiver. This dictionary contains a number of predefined precoding matrices with their associated indices. Once the receiver obtains the CSI after channel estimation, it chooses from the dictionary matrix the one that best approximates the channel conditions and feeds back its index on the return path. Sending the index only on the return path significantly reduces the feedback overhead. The disadvantage of this technique is that the selected matrix is an approximate version: there will be quantization errors, which reduces the beamforming gain. In addition, the accuracy of the selected matrix is strongly related to the size of the dictionary: the larger the size, the better the accuracy matrix, but the longer waiting time is important. The size of the codebook is also proportional to the number of transmission antennas. Therefore, the codebook principle is only appreciated for a reduced transmission antenna number (thus a small amount of feedback). In [4], the authors proposed a new technique to use the codebook approach in a MMIMO context in the FDD mode. The proposed technique, based on the construction of a dictionary by the Grassmann manifold method and the minimization of the choral distance, allows a considerable reduction in the amount of feedback. However, the solution becomes ineffective when the number of antennas exceeds 64(ii)
Antenna grouping beamforming (AGB) approach has also been proposed to solve this problem [5]. Here, the idea is to do the grouping of transmission antennas to have a very reduced representation of the number of excessive antennas by using the properties of the designed grouping patterns. This will allow a considerable reduction in the number of pilot symbols and the amount of feedback. However, this method is similar to that of the codebook but more complex to achieve. As a result, there are large quantization errors as the number of antennas becomes large(iii)
In addition in this register of reducing feedback overhead, Shen et al. [6] proposed an adaptive angle-departure (AoD) subspace codebook for channel feedback in FDD massive MIMO systems. Their key idea is based on the observation that path AoDs vary more slowly than path gains. In the angular coherence time, by using the constant AoD information, the proposed AoD adaptive subspace codebook is able to quantify the channel vector more accurately. The authors show that the feedback overhead of the proposed codebook scales only linearly with a small number of dominant AoDs (paths) instead of the large number of antennas at the BS. Moreover, their proposal makes it possible to obtain a good quality of channel feedback, while requiring a low overhead(iv)
In contrast to the previous techniques, other works have been based on the fact of making the compression of the CSI at the level of the users with specific compression techniques (arithmetic coding [7], Givens rotation [8], time domain quantization [8], and LZW compression [9])It should be noted that none of these works specify whether it is more optimal to return only the precoding matrix (partial CSI) or the channel matrix (full CSI). Indeed, in a classical MIMO system or MMIMO, the BS does not need the full channel matrix (full CSI) to beamform properly. Only the precoding matrix (partial CSI) is sufficient. Recall that the precoding matrix comes from the singular value decomposition of the full channel matrix. Therefore, in almost all works, to diagonalize the channel transmission and eliminate cochannel interference, users feedback only the precoding matrix after the estimated channel and singular value decomposition. However, it is quite possible for users to feed back the estimated channel matrix entirety, and in this case, it is up to the BS to do the singular value decomposition (SVD) of each subchannel to retrieve the precoding matrix relative to each subchannel.In this paper, we will first make a comparative study between the full channel matrix and the precoding matrix resulting from the latter to choose the right candidate to be feedback. After that, we will make a comparative study of the application of compression techniques (GR, AC, and LZW) in a MMIMO context to know which of its techniques gives better performance in terms of compression ratio. Finally, we will propose two new approaches to reduce the downlink feedback overhead (GR&AC and GR&LZW) based on the combination of GR used in 801.11 and methods AC and LZW, respectively. The proposed techniques can reach 83% and 97% compression ratios, respectively. The rest of the paper is organized as follows: In Section2, the system model is defined. Section 3 will present the comparison between the partial CSI and the full CSI. In Section 4, we will briefly describe the quantification of the Givens rotation, AC, and LZW compression in the MMIMO context. Section 5 will cover the proposals of improvement of the GR as well as the numerical results. Finally, Section 6 will serve as a conclusion.


## 2. The System Model

Consider a multiuser MIMO downlink channel operating in the FDD mode withNBS antennas at the base station (BS) and K mobile stations (MS); each K mobile station has NMSk antennas for k=1,2,⋯,K.NBS is assumed to be greater than or equal to ∑k=1KNMSk: sum of all MS’s antennas.In Figure1, the vector xk=x1,x2,⋯,xNMSkT represents the transmitted data of the BS to the kth MS, where k=1,⋯,K.Figure 1
Multiuser multiantenna downlink FDD with preprocessing and postprocessing.A preprocessing is done on the BS side for each streamxk, using the precoding matrices Pk∈ℂNBS×NMSk, where k=1,⋯,K. After DL transmitter preprocessing, the NBS-component signal broadcast by the BS to the K MSs can be expressed as
(1)w=∑k=1Kwk=P×x,where wk=Pk×xk.
(2)P=P1,P2,⋯,PK,x=x1,x2,⋯,xKT.As shown in Figure1, the frequency domain received signal yk of the kth MS for the considered OFDM subcarrier can then be expressed as
(3)yk=Hkw+nk=HkPx+nk,(4)yk=HkPkxk+∑i=1,i≠kKHkPixi+nk,where nk is a length-NBS additive white Gaussian noise with zero mean and a covariance matrix given by σ2INBS, whereas Hk is an (NMSk×NBS)-component channel transfer matrix connecting the NBS DL transmit antennas of the BS with the kth MS’s NMSk receive antennas, which can be expressed as
(5)Hk=H1,1kH1,2k⋯H1,NMSkkH2,1kH2,2k⋯H2,NMSkk⋮⋮⋱⋮HNBS,1kHNBS,2k⋯HNBS,NMSkk.A postprocessing on the postcoding matrixPsk∈ℂNBS×NBS is performed at each MS side to eliminate the multiuser interference (MUI). After that, the detected data on the considered OFDM subcarrier can be given by x∧k=x^1,x^2,⋯,x^NMSk.The procedure described in this section is the same for all orthogonal frequency division multiplex (OFDM) subcarriers. To facilitate paper reading, in the following, we will consider a single OFDM subcarrier.


### 2.1. The SVD-Based Beamforming

Consider the SVD of the channel transfer matrixHk: Now, let us perform the SVD of our matrix Hk assuming that its rank is Nk: RankHk=Nk and that NBS≥∑k=1KNk.
(6)Hk=UkDkl0VkH=UkDkl0VklHVkrH=UkDklVklH,where Dk∈ℂNk×Nk is diagonal and Uk∈ℂNk×Nk and Vk∈ℂNBS×NBS are unitary matrices. In SVD-based beamforming, the transmit signal is precoded using the matrix Pk=Vk†, where † stands for the transpose-conjugation.In this context, Equation (3) becomes
(7)yk=UkDklVklHPx+nk.Let us now collect theK received DL signal vectors yk into a vector y=y1T,y2T,⋯,ykTT. Then, according to Equation (7), it can be shown that the overall DL-received signal vector y of the K MSs can be expressed as
(8)y=UDVlHPx+n,where
(9)U=U1l,U2l,⋯,UKlD=diagD1l,D2l,⋯,DKlVl=V1l,V2l,⋯,VKln=n1T,n2T⋯,nKTT.For ease of reading, it is assumed in the following that all MSs have the same number of antennas:(10)NMSk=NMSfork=1,2,⋯,K.Based on Equation (8), it is not possible to perform separately the postprocessing which allows the transmitted data of each UE to be detected at the BS side. As shown in Figure 1, one postcoder matrix Ps∈ℂNBS×KNMS is used to separate to separate the desired sign and the interfering signal at the K different UEs.Therefore, the postprocessing at each MS side can be done using the ZF solution:(11)Psk=Uk†Uk−lUk†.Then, Equation (8) becomes
(12)x~=Dlx+n~.SinceDl is exactly diagonal, there is no MUI, and the MMIMO channel is reduced to NMS×K separate and independent SISO channels. However, the noise component n~ is colored by the postfilter and can be potentially enhanced.Finally, the transmitted data from all UEs can be detected by performing a simple equalization process:(13)x^=Dl−1Dlx+Dl−1n~=x+n^.


### 2.2. Discussion

The SVD beamforming and ZF MUI cancellation presented in the two previous subsections can only be implemented if the DL CSI is known at both the BS and each UE. In the considered FDD system, the BS sends pilot sequences which are known at the MSs side. Based on the reception of these pilot sequences, each MS estimates its CSI. After that, each MS has to feed back the CSI to the BS. There are two possibilities:(i)
Each MS can feed back its channel matrix. However, this is not optimal for SVD beamforming scheme. Because in this case, the BS will be forced to perform a SVD decomposition to get its precoder matrix(ii)
To avoid this previous drawback, only the precoding matrices can be sent directly to the BS instead of the channel matrixIt is important to note that, in downlink MMIMO-OFDM system, each MS has to feed back its precoding matrix for each subcarrier. This feedback overhead can be essential and its reduction is necessary.


### 2.3. Channel Models for Massive MIMO

Let us talk a bit about the massive MIMO channel model. Indeed, the channel model plays an important role in system analysis as well as performance evaluation. One factor that critically determines the channel pattern is the configuration of an antenna array. Each measurement is made based on a given grating, and there are several typical antenna configurations that can be placed into three different groups: one-dimensional (1D), 2D, and 3D gratings. Each of these configurations as well as their size affects the properties of the channel by attributing different massive MIMO performance. For example, the distance between antenna elements essentially dictates the mutual coupling and correlation matrix, affecting the performance of massive MIMO. We can list two types of channel models found in the literature, namely correlation-based channel models and geometry-based stochastic channel models [10].
(i)
Correlation-based models are mainly used for theoretical evaluations of system performance. This family of channel models can be sorted into three different types of channel models. These are, namely, the following:(1)
Rayleigh channel model: it assumes that there is no correlation between transmitting antennas or receiving antennas. Here, the elements of the fast fading matrix are i.i.d. complex Gaussian random variables. Moreover, the most important property of such a model is given by increasing the number of transmit antennas tends to infinity, which causes the rows of the transmit channel matrixH to become nearly orthogonal [2], which gives a property known as channel hardening and mitigates the impact of fast fading, which simplifies the complexity of scheduling schemes(2)
Correlation channel model: this model inserts antenna correlation due to antenna spacing and broadcast environments(3)
Mutual coupling channel model: as the number of antennas increases, the effect of mutual impedance also increases. Additionally, the load impedance and antenna impedance must also be characterized to reflect a more realistic channel(ii)
Geometry-based stochastic channel models are cluster-based models that define the propagation channel containing multiple clusters with different delays and power factors. In the case of a 3D channel model, the two strongest clusters are split into three subclusters with a fixed delay offset [10]. This model is used for practical evaluations of wireless communication systemsIn this work, we use a channel model based on the correlation, more particularly that of Rayleigh.


## 2.1. The SVD-Based Beamforming

Consider the SVD of the channel transfer matrixHk: Now, let us perform the SVD of our matrix Hk assuming that its rank is Nk: RankHk=Nk and that NBS≥∑k=1KNk.
(6)Hk=UkDkl0VkH=UkDkl0VklHVkrH=UkDklVklH,where Dk∈ℂNk×Nk is diagonal and Uk∈ℂNk×Nk and Vk∈ℂNBS×NBS are unitary matrices. In SVD-based beamforming, the transmit signal is precoded using the matrix Pk=Vk†, where † stands for the transpose-conjugation.In this context, Equation (3) becomes
(7)yk=UkDklVklHPx+nk.Let us now collect theK received DL signal vectors yk into a vector y=y1T,y2T,⋯,ykTT. Then, according to Equation (7), it can be shown that the overall DL-received signal vector y of the K MSs can be expressed as
(8)y=UDVlHPx+n,where
(9)U=U1l,U2l,⋯,UKlD=diagD1l,D2l,⋯,DKlVl=V1l,V2l,⋯,VKln=n1T,n2T⋯,nKTT.For ease of reading, it is assumed in the following that all MSs have the same number of antennas:(10)NMSk=NMSfork=1,2,⋯,K.Based on Equation (8), it is not possible to perform separately the postprocessing which allows the transmitted data of each UE to be detected at the BS side. As shown in Figure 1, one postcoder matrix Ps∈ℂNBS×KNMS is used to separate to separate the desired sign and the interfering signal at the K different UEs.Therefore, the postprocessing at each MS side can be done using the ZF solution:(11)Psk=Uk†Uk−lUk†.Then, Equation (8) becomes
(12)x~=Dlx+n~.SinceDl is exactly diagonal, there is no MUI, and the MMIMO channel is reduced to NMS×K separate and independent SISO channels. However, the noise component n~ is colored by the postfilter and can be potentially enhanced.Finally, the transmitted data from all UEs can be detected by performing a simple equalization process:(13)x^=Dl−1Dlx+Dl−1n~=x+n^.


## 2.2. Discussion

The SVD beamforming and ZF MUI cancellation presented in the two previous subsections can only be implemented if the DL CSI is known at both the BS and each UE. In the considered FDD system, the BS sends pilot sequences which are known at the MSs side. Based on the reception of these pilot sequences, each MS estimates its CSI. After that, each MS has to feed back the CSI to the BS. There are two possibilities:(i)
Each MS can feed back its channel matrix. However, this is not optimal for SVD beamforming scheme. Because in this case, the BS will be forced to perform a SVD decomposition to get its precoder matrix(ii)
To avoid this previous drawback, only the precoding matrices can be sent directly to the BS instead of the channel matrixIt is important to note that, in downlink MMIMO-OFDM system, each MS has to feed back its precoding matrix for each subcarrier. This feedback overhead can be essential and its reduction is necessary.


## 2.3. Channel Models for Massive MIMO

Let us talk a bit about the massive MIMO channel model. Indeed, the channel model plays an important role in system analysis as well as performance evaluation. One factor that critically determines the channel pattern is the configuration of an antenna array. Each measurement is made based on a given grating, and there are several typical antenna configurations that can be placed into three different groups: one-dimensional (1D), 2D, and 3D gratings. Each of these configurations as well as their size affects the properties of the channel by attributing different massive MIMO performance. For example, the distance between antenna elements essentially dictates the mutual coupling and correlation matrix, affecting the performance of massive MIMO. We can list two types of channel models found in the literature, namely correlation-based channel models and geometry-based stochastic channel models [10].
(i)
Correlation-based models are mainly used for theoretical evaluations of system performance. This family of channel models can be sorted into three different types of channel models. These are, namely, the following:(1)
Rayleigh channel model: it assumes that there is no correlation between transmitting antennas or receiving antennas. Here, the elements of the fast fading matrix are i.i.d. complex Gaussian random variables. Moreover, the most important property of such a model is given by increasing the number of transmit antennas tends to infinity, which causes the rows of the transmit channel matrixH to become nearly orthogonal [2], which gives a property known as channel hardening and mitigates the impact of fast fading, which simplifies the complexity of scheduling schemes(2)
Correlation channel model: this model inserts antenna correlation due to antenna spacing and broadcast environments(3)
Mutual coupling channel model: as the number of antennas increases, the effect of mutual impedance also increases. Additionally, the load impedance and antenna impedance must also be characterized to reflect a more realistic channel(ii)
Geometry-based stochastic channel models are cluster-based models that define the propagation channel containing multiple clusters with different delays and power factors. In the case of a 3D channel model, the two strongest clusters are split into three subclusters with a fixed delay offset [10]. This model is used for practical evaluations of wireless communication systemsIn this work, we use a channel model based on the correlation, more particularly that of Rayleigh.


## 3. Full CSI vs. Partial CSI

### 3.1. Simulation Settings

The considered simulation parameters are listed in Table1. We consider several values of No in order to make simulations that concern a large part of the telecommunications systems using OFDM as long-term evolution (LTE) where No can be =1024, IEEE802.11 where No is up to 512 or IEEE802.16 where No=256.Table 1
Simulation parameters.
Channel modelRayleigh flat fadingNo128, 256, 512, and 1024nb8Cyclic prefix1/4NBS64 and 128NMS4 and 8Modulation4-QAMFECConvolutionalCoding rate1/2


### 3.2. Comparison

Figure1 gives an overall view of the system with the feedback mechanism. In blue, it is the feedback of the precoding matrix (partial CSI) and in yellow that of the matrix of the estimated channel (full CSI). To determine which of these candidates is more beneficial to return, we have mapped the structures of the two matrices. Figures 2 and 3 show that the structures of the dies are almost similar to an MMIMO configuration but remain valid for all other configurations. This similarity is further proven with the application of the LZW compression algorithm. Thus, from Table 2, we can see that the compression ratios for the two matrices are slightly identical. Thus, instead of sending back the full CSI which requires the BS to do an SVD decomposition for each subchannel, it is better to send the partial CSI so that the BS will directly precode which will reduce the processing time.Figure 2
Full and partial CSI for64×4×128 MMIMO configuration.Figure 3
Full and partial CSI for128×4×128 MMIMO configuration.Table 2
Compression ratio between the precoding matrix (partial CSI) and the total channel matrix (full CSI) with LZW algorithms in different MMIMO-OFDM configurations.NBS, NMS, and No, respectively, stand for the number of antennas at the BS, the number of antennas at each MS, and the number of OFDM subcarriers.
MMIMO-OFDMNBS×NMS×NoFeedback amount without compression in bitsCompression rate of full CSICompression rate of partial CSI64×4×12852428880.4686%80.8355%64×4×256104857684.8101%85.2493%64×4×512209715289.3295%89.5338%64×4×1024419430491.8439%91.9494%128×4×128104857679.1023%80.8941%128×4×256209715283.8996%85.0597%128×4×512419430488.6253%89.5372%64×8×128104857679.2945%80.3640%64×8×256209715283.7158%84.6728%64×8×512419430488.6832%89.1703%64×8×1024838860891.4242%91.7698%128×8×128209715278.0467%81.0543%In the rest of the document, we will consider that the users will return on the return path only the precoding matrix after SVD decomposition; thus, the feedback is partial. Therefore, we will focus on improving the method of the Givens rotation. Indeed, this method requires that the matrix be unitary.Since the previous comparative study gives the reason to return only the precoding matrix (unitary) instead of the total matrix of the channel (nonunitary), it is then legitimate to look at how to improve the method of the Givens rotation which the method used in the IEEE802.11/ac WLAN standard.


## 3.1. Simulation Settings

The considered simulation parameters are listed in Table1. We consider several values of No in order to make simulations that concern a large part of the telecommunications systems using OFDM as long-term evolution (LTE) where No can be =1024, IEEE802.11 where No is up to 512 or IEEE802.16 where No=256.Table 1
Simulation parameters.
Channel modelRayleigh flat fadingNo128, 256, 512, and 1024nb8Cyclic prefix1/4NBS64 and 128NMS4 and 8Modulation4-QAMFECConvolutionalCoding rate1/2


## 3.2. Comparison

Figure1 gives an overall view of the system with the feedback mechanism. In blue, it is the feedback of the precoding matrix (partial CSI) and in yellow that of the matrix of the estimated channel (full CSI). To determine which of these candidates is more beneficial to return, we have mapped the structures of the two matrices. Figures 2 and 3 show that the structures of the dies are almost similar to an MMIMO configuration but remain valid for all other configurations. This similarity is further proven with the application of the LZW compression algorithm. Thus, from Table 2, we can see that the compression ratios for the two matrices are slightly identical. Thus, instead of sending back the full CSI which requires the BS to do an SVD decomposition for each subchannel, it is better to send the partial CSI so that the BS will directly precode which will reduce the processing time.Figure 2
Full and partial CSI for64×4×128 MMIMO configuration.Figure 3
Full and partial CSI for128×4×128 MMIMO configuration.Table 2
Compression ratio between the precoding matrix (partial CSI) and the total channel matrix (full CSI) with LZW algorithms in different MMIMO-OFDM configurations.NBS, NMS, and No, respectively, stand for the number of antennas at the BS, the number of antennas at each MS, and the number of OFDM subcarriers.
MMIMO-OFDMNBS×NMS×NoFeedback amount without compression in bitsCompression rate of full CSICompression rate of partial CSI64×4×12852428880.4686%80.8355%64×4×256104857684.8101%85.2493%64×4×512209715289.3295%89.5338%64×4×1024419430491.8439%91.9494%128×4×128104857679.1023%80.8941%128×4×256209715283.8996%85.0597%128×4×512419430488.6253%89.5372%64×8×128104857679.2945%80.3640%64×8×256209715283.7158%84.6728%64×8×512419430488.6832%89.1703%64×8×1024838860891.4242%91.7698%128×8×128209715278.0467%81.0543%In the rest of the document, we will consider that the users will return on the return path only the precoding matrix after SVD decomposition; thus, the feedback is partial. Therefore, we will focus on improving the method of the Givens rotation. Indeed, this method requires that the matrix be unitary.Since the previous comparative study gives the reason to return only the precoding matrix (unitary) instead of the total matrix of the channel (nonunitary), it is then legitimate to look at how to improve the method of the Givens rotation which the method used in the IEEE802.11/ac WLAN standard.


## 4. Givens Rotation, AC, and LZW

### 4.1. Givens Rotation Quantization

The Givens rotation (GR) is proposed by Kim and Aldana [11] to reduce the feedback overhead, exploiting the unitary property of the precoding matrix Pk. The GR feedback compression method is adopted in the IEEE 802.11/ac WLAN standard, and its principle is to represent a unitary matrix in a special form with complex diagonal matrices as follows:
(14)Pk†=∏i=1minNt−1,NrDk,i∏l=i+1NtGk,liTψk,li×INt×Nr,where
(15)Dk,i=Ii−100⋯00ejϕk,i,i0⋯000⋯00000ejϕk,N−1,i000001,(16)Gk,li=Ii−100⋯00cosψk,li0sinψk,li000Il−i−1000−sinψk,li0cosψk,li00000IN−l.The matrixDk,i is an Nt×Nt diagonal matrix, INt×Nr is an Nt×Nr identity matrix, and Gk,li is an Nt×Nt Givens rotation matrix.According to Equations (14) and (15), the parameters to be determined to identify the precoder matrix Pk† are
(17)ψk,lifori=1,2,⋯,minNt−1,Nrandi<l≤Ntϕk,j,ifori=1,2,⋯,minNt−1,Nrandi<j≤Nt−1.Consider a unitary matrixP of dimension 3×3. According to the GR method seen above (Equation (14)), P can be decomposed as follows:
(18)P†=D1ψ21G21†D2ψ32G32†I3∗3.The precoder matrixP can then be reconstructed through the six parameters: ψ21,ψ31,ψ32,ϕ1,1,ϕ1,2, and ϕ2,2.Therefore, in a general way, instead of all elements of the matrixPk, it is sufficient to consider the parameters ψk,li and ϕk,j,i. Note that these angle parameters can vary from 0 to 2π for ϕk,j,i and from 0 to π/2 for ψk,li.Now,ψk,li and ϕk,j,i can be quantized according to Equations (19) and (20); ψ^k,li and ϕ^k,j,i represent the quantized angles.
(19)ψ^k,li=Qψπ/22nb+π/22nb+1,where Qψ=0,1,⋯,2nb−1 and nb the number of bits per angle ψ.
(20)ϕ^k,j,i=Qϕ2π2nb+2π2nb+1,where Qϕk,j,i=0,1,⋯,2nb−1 and nb is the number of bits per angle ϕ. Finally, the receiver feeds back the quantized parameters Qψk,li and Qψ to the transmitter which can recover the quantized precoder matrix P^k by using
(21)P^k†=∏i=1minNt−1,NrD^k,i∏l=i+1NtG^k,liTψ^k,li×INt×Nr,where
(22)D^k,i=Ii−100⋯00ejϕ∧k,i,i0⋯000⋯00000ejϕ∧k,N−1,i000001,G^k,li=Ii−100⋯00cosψ^k,li0sinψ^k,li000Il−i−1000−sinψ^k,li0cosψ^k,li00000IN−l.When we assume thatNt=Nr=N, the total number of bits for each user NFGR can be calculated using the formula NFGR=No×nb×NN−1, where No represents the number of OFDM subcarriers. Based on the fact that the feedback overhead without compression is No×nb×2×N2, the feedback overhead compression rate can be expressed by N+1/2N. Unfortunately, this feedback overhead compression rate decreases with the growth of antenna ports. This last disadvantage limits the performance of GR in MMIMO.However, the GR remains an interesting method because, as mentioned previously, the SVD decomposition is only performed at each MS side. Therefore, to take advantage of this particularity of the GR approach, we propose its improvement in Section5.


### 4.2. Arithmetic Compression

Figure4 gives an overall view of the transmission model with arithmetic coding from the insertion of the pilot signs to the estimation of the channel to the preprocessing of precoding and feedback.Figure 4
The system model for arithmetic coding.


#### 4.2.1. Description of Encoding and Decoding Principles

Arithmetic coding is a statistical coding, that is to say that more than one character is represented, the less bits need to be encoded [12]. The principle of the algorithm is as follows: First, we begin by subdividing the interval 0,1 in M intervals:
(23)Fxi−1,Fxi,i=1,⋯,MandFx0=0.Then we must make a mapping of the symbols of the alphabet that make up the sequence to compress to the intervals:(24)ak⇔Fxi−1,Fxik=1,⋯,NandFx0=0.So any real in the intervalFxi−1,⋯,Fxi may represent the symbol ak.Algorithm 1:AC feedback overhead encoding.
1: Input:A=ai,i=1,⋯,N: sequence to compress; p1,p2,⋯,pM: the symbol probabilities are known .2: Output Val: a real value in the range0,1 which represents the sequence.3: (Cum= cumulative probability and coincides with the various terminals:Fx);4:fori=1:Mdo5:cumi≔cumi−1+pi;   ⊳M being the number of the symbol alphabet (the number of intervals).6:low=0;                        ⊳ the lower bound7:high=1;                       ⊳ the upper bound8:fori=1:Ndo9:Range=high−low;10:high=low+Range∗cumai−1;11:low=low+Range∗cumai;12:returnval=lower+high/2;  ⊳ Val is the code word but any value from [low and high) is good.Algorithm 2: AC feedback overhead decoding.
1: Input:val: bit stream (compressed version of the sequence); N: the number of symbols to be decoded; p1,p2,⋯,pM: the symbol probabilities are known.2: Output: the decoded sequenceA.3: Begin-decoding⊳ (Cum = cumulative probability and coincides with the various terminals: Fx);4:cum0=p1;5:fori=1:Ndo6:cumi≔cumi−1+pi;7:low=0;                        ⊳ the lower bound8:high≔1;                        ⊳ the upper bound9:fori=1:Ndo10:Range=high−low;11:z=val−low/Range;12:j=2;13:while (j<N) and (cumj−1>zorz>cumj) do ⊳ we find the index j such this condition is fulfilled14:ifcumj−1<z<cumjthen15:ai=j;;16:else17:j=j+1;18:19:20:high=low+Range∗cumj−1;21:low=low+Range∗cumj;22:23:returnA=a1,a1a2,⋯aN;To better understand arithmetic coding, we will use a simple example. Let us go back to our sequence to compress: “MIMOMISO.” The length of this sequence is 8. Table3 defines the probabilities of the characters in our sequence as well as the relative intervals, respectively.Table 3
Probability tables and interval definitions.
SymbolsOccurrencesProbabilitiesIntervalsI20.250;0.25M30.3750.25;0.625O20.250.625;0875S10.1250.875;1Once this is done, we can now apply the arithmetic coding algorithm defined previously and we get Table4.Table 4
The arithmetic encoding process.
SymbolsLower boundUpper boundInitially01M0.250.625I0.250.34375M0.27343750.30859375O0.295410160.30419922M0.297607420.30090332I0.297607420.298431400S0.29832840250.298431400O0.29839792581250.2984185253125Thus, 0.2983979258125 is the arithmetic representation of the “MIMOMISO” message. In practice, any number between 0.2983979258125 and 0.2984185253125 represents the correct message.Figure5 shows the coding process.Figure 5
The representation of the arithmetic coding process of the message “MIMOMISO.”Decoding is just as simple: knowing that the encoded message is in the interval0.25;0.625; thus, the first letter is indeed an M. We then subtract the lower bound (for M), and we divide by the probability (for M); we thus obtain 0.1290611355 which is included in the interval 0;0.25, and so, the next letter will be an I. We continue to subtract the lower bound (for I) and divide by the probability (for I); this gives 0.516244542 which is in the interval 0.25;0.625, and therefore. the next letter will be an M, etc.


#### 4.2.2. Solving the Arithmetic Coding Overflow Problem

The two preceding algorithms give the classical arithmetic encoding and decoding. However, one of the main problems with arithmetic coding is the phenomenon of overflow: overflow and underflow. These are issues related to the precision of machines (hardware). To overcome this, the most used technique is that of scaling. The principle of this can be described as follows:(i)
Resizing interval: we increase the size of the interval, but we must preserve the information(ii)
Incremental encoding: transmission of the code portion by portion as the encoding progresses(iii)
We start from the observation of 3 possibilities concerning the interval during encoding:(1)
Interval is included in the lower half:0,0.5(2)
Interval is included in the upper half:0.5,1(3)
The interval contains the center point 0.5(iv)
When the gap is in one of the halves, it will stay in that half throughout the encoding of the sequence(v)
The most significant bit (MSB) is 0 if the interval is in0,0.5(vi)
MSB is 1 if the interval is in0.5,1(vii)
So when the interval is in one of the halves, the most significant bit becomes known(viii)
Once the encoder and decoder know which part we are in, we can ignore the other half(ix)
To implement the algorithm on a finite precision system, which is our case, we can resize the half in question to regain the interval0,1 in full. This will result in the loss of information on MSB, but it does not matter because we have already sent the MSB. We continue the coding, and each time we are in one half, we send a bit. This is an incremental coding(1)
Ifhigh<0.5(i)
Transmit bit 0 and add a 0 to the p number of pending bits(ii)
Low=2low(iii)
High=2high(2)
Iflow>0.5(i)
Transmit bit 1 and add a 0 to the p number of pending bits(ii)
Low=2 (low-0.5)(iii)
High=2 (high-0.5)(3)
Iflow>0.25 and high<0.75(i)
Add a 1 to the p number of pending bits(ii)
Low=2 (low-0.25)(iii)
High=2 (high-0.25)Note that the interval is scaled (zoomed) for each output bit. This multiplication by 2 means moving the binary point one position to the right. Sometimes it is easier to work with integers than to work with comma numbers. To apply arithmetic coding to integers, just do the following:(i)
Use symbol frequencies instead of probability(ii)
Replace0,1 by 0,2k−1(iii)
Replace 0.5 by2k−1−1(iv)
Replace 0.25 by2k−2−1(v)
Replace 0.75 by3.2k−2−1Here is the formula to calculate the following interval:(25)high=low+rangecumsymbol/total_freq‐1,low=low+rangecumsymbol‐1/total_freq.Thus, Algorithms1 and 2 become Algorithms 3 and 4, respectively: First we ask: First_qtr=2k−1−1, half=2k−2−1, and Third_qtr=3.2k−2−1.Algorithm 3: AC feedback overhead encoding.
1: Input:A=ai,i=1,⋯,N: sequence to compress; p1,p2,⋯,pM: the symbol probabilities are known.2: Output Val: a binary number that represents sequenceA.3: (Cum = cumulative probability and coincides with the various terminals:Fx); cum0=04:for {i=1:M} do5:cumi≔cumi−1+pi;   ⊳M is the number of symbols in the alphabet (the number of intervals)6: low =0; high=2k−1      ⊳ the lower and upper bound; K the number of bits7: First_qtr=2k−1; half= 2k−2; Third_qtr= 3.2k−2;8: bits_To_follow:=0; ⊳ Number of bits to look at in order to know which part we are on9fori=1:Ndo10:Range=high−low+1;11:high=low+Range∗cumai−1/cum1−1;12:low=low+Range∗cumai/cum1;13:while 1 do14:    ifhigh<Half                  ⊳ the lower part15:    transmission of bit “0”;B=B0;16:    low =2 low; high =2 high;17:    else iflow>=Half                ⊳ the high part18:    transmission of bit “1”;B=B1;19:    low = low-Half; high = high-Half;20:    low =2 low; high =2 high;21:    else iflow>=First_qtrandhigh<Third_qtr    ⊳ n the middle22:    bits_To_follow =bits_To_follow + 1;23:    low = low-First_qtr; high = high-First_qtr;24:    low =2 low; high =2 high;25:    else26:    break;27:    End if;After that we encode the symbol EOF_symbol as before to allow the decoder to stop.28:returnC=bin2decB;  ⊳ bin2dec converts the binary vector to a decimal number=0Algorithm 4: AC feedback overhead decoding.
1: Input:val: Bit stream (compressed version of the sequence); N: the number of symbols to be decoded; p1,p2,⋯,pM: the symbol probabilities are known.2: Output: the decoded sequenceA.3: Cum = cumulative probability and coincides with the various terminals:Fx); cum0=p1;4:fori=1:Mdo5:cumi≔cumi−1+pi;  ⊳M is the number of symbols in the alphabet (the number of intervals)6: low =0; high=2k−17: First_qtr=2k−1; half=2k−2; Third_qtr= 3.2k−2;8:while 1 do9:Range=high−low+1;10:cumval=val−low+1∗cum1−1/range;11:symbol=2;12:whilecumsymbol>cumvaldo13:symbol=symbol+1;14:high=low+range∗cumsymbol−1/cum1−1;15:low=low+range∗cumsymbol/cum1;16:while 1 do17:   ifhigh<Half     ⊳ the lower part        ⊳ we do nothing18:   else iflow>=Half                  ⊳ the high part19:   val = val-Half; low = low-Half; high = high-Half;20:   else iflow>=First_qtrandhigh<Third_qtr      ⊳ In the middle21:   val = val-First_qtr; low = low-First_qtr; high = high-First_qtr;22:   else23:   break;24:   End if;25:   low =2 low; high =2 high; val =2 val + bit;⊳ Move to next input bit26:   ifsymbol=EOF_symbol                  ⊳ the end27:   break;28:   End if;29:   A=symbol;30:returnA


### 4.3. LZW Compression

Among the most powerful data compression techniques, we can mention the compression algorithms based on the use of a dictionary. These are lossless data compression techniques that uses a dictionary with a predetermined state, but its value may be changed during the encoding or decoding process. One of the best-known dynamic dictionary-based compression algorithms is the LZW algorithm, which was created as a modification of the LZ78 algorithm [13]. It is a general-purpose compression algorithm in the sense that it can work with almost any type of data. LZW is a dictionary-based compression method [9] that associates a variable number of symbols (subsequences) with a code of fixed length. The algorithm works by traversing the input sequence to search a subsequence that is not in the dictionary. When such a subsequence is found, the index of the subsequence without the last element (that is, the longest subsequence of the dictionary) is extracted from the dictionary and sent to the output; then the new subsequence (including the last element) is added to the dictionary with the next available code. The last element entered is then used as the next starting point for searching for subsequences [9]. Increasingly long subsequences are stored in the dictionary and made available for later encoding as single output values.Figure6 gives an overall view of the transmission model with LZW compressing from the insertion of the pilot signs to the estimation of the channel with the preprocessing of precoding and feedback.Figure 6
The system model for LZW coding.The algorithm works best on data with repeated models. Like any compression algorithm, the LZW is defined by compression: obtained by replacing the subsequences with the codes associated with them in the dictionary and by decompression: performed by replacing sets of code words with their associated subsequences in the dictionary.Thus, the coding and decoding algorithms are, respectively, presented in Algorithms1 and 2, where BDC and DBC stand for, respectively, binary to decimal conversion and decimal to binary conversion.Algorithm 5: LZW feedback overhead encoding.
1: Initialize the dictionary with all integer values from0 to 2nb−12: Consider for each input binary sequence of lengthnb his BDC as a code3:Vmax=2nb−14:W=first input binary sequence of length nb5:while not end of the input nb sequences do6:C=next input binary sequence of length nb7:if the code of W concatenated with C is in the dictionary then8:  ReplaceW by W concatenated with C9:else10:Vmax=Vmax+111:   Output code ofW12:   AddVmax as the code of W concatenated with C in the dictionary.13:   ReplaceW by C14: Output the code ofW=0Algorithm 6: LZW feedback overhead decoding.
1: Initialize the dictionary with all integer values from0 to 2nb−12:Vmax=2nb−13: OLD=first input code of the codes stream4: Output the DBC of OLD5:while not end of input codes stream do6:  CURRENT = next input code of the codes stream7:  Output the sequence ofnb or a multiple of nb bits corresponding to CURRENT in the dictionary8:Vmax=Vmax+19:  AddVmax in the dictionary as the code of the sequence of bits corresponding to OLD concatenated with the first nb bits of that corresponding to CURRENT10:  Replace OLD by CURRENTIn the LZW encoding and decoding, we can see the following:(i)
The LZW algorithm is very simple. In addition to this, the dictionary is designed at the same time as the encoding or decoding and does not need to be saved(ii)
The efficiency of the algorithm increases as the number of repetitive sequences in the input data increases(iii)
At each MS side, after the GR compression, allNo×NMSkNMSk−1 output sequences of length nb bits are concatenated to get the AC or LZW input binary sequence(iv)
At the BS side, the AC or LZW decoding algorithm is used before the GR one to retrieve the precoding matrixPk, for k=1,⋯,K


## 4.1. Givens Rotation Quantization

The Givens rotation (GR) is proposed by Kim and Aldana [11] to reduce the feedback overhead, exploiting the unitary property of the precoding matrix Pk. The GR feedback compression method is adopted in the IEEE 802.11/ac WLAN standard, and its principle is to represent a unitary matrix in a special form with complex diagonal matrices as follows:
(14)Pk†=∏i=1minNt−1,NrDk,i∏l=i+1NtGk,liTψk,li×INt×Nr,where
(15)Dk,i=Ii−100⋯00ejϕk,i,i0⋯000⋯00000ejϕk,N−1,i000001,(16)Gk,li=Ii−100⋯00cosψk,li0sinψk,li000Il−i−1000−sinψk,li0cosψk,li00000IN−l.The matrixDk,i is an Nt×Nt diagonal matrix, INt×Nr is an Nt×Nr identity matrix, and Gk,li is an Nt×Nt Givens rotation matrix.According to Equations (14) and (15), the parameters to be determined to identify the precoder matrix Pk† are
(17)ψk,lifori=1,2,⋯,minNt−1,Nrandi<l≤Ntϕk,j,ifori=1,2,⋯,minNt−1,Nrandi<j≤Nt−1.Consider a unitary matrixP of dimension 3×3. According to the GR method seen above (Equation (14)), P can be decomposed as follows:
(18)P†=D1ψ21G21†D2ψ32G32†I3∗3.The precoder matrixP can then be reconstructed through the six parameters: ψ21,ψ31,ψ32,ϕ1,1,ϕ1,2, and ϕ2,2.Therefore, in a general way, instead of all elements of the matrixPk, it is sufficient to consider the parameters ψk,li and ϕk,j,i. Note that these angle parameters can vary from 0 to 2π for ϕk,j,i and from 0 to π/2 for ψk,li.Now,ψk,li and ϕk,j,i can be quantized according to Equations (19) and (20); ψ^k,li and ϕ^k,j,i represent the quantized angles.
(19)ψ^k,li=Qψπ/22nb+π/22nb+1,where Qψ=0,1,⋯,2nb−1 and nb the number of bits per angle ψ.
(20)ϕ^k,j,i=Qϕ2π2nb+2π2nb+1,where Qϕk,j,i=0,1,⋯,2nb−1 and nb is the number of bits per angle ϕ. Finally, the receiver feeds back the quantized parameters Qψk,li and Qψ to the transmitter which can recover the quantized precoder matrix P^k by using
(21)P^k†=∏i=1minNt−1,NrD^k,i∏l=i+1NtG^k,liTψ^k,li×INt×Nr,where
(22)D^k,i=Ii−100⋯00ejϕ∧k,i,i0⋯000⋯00000ejϕ∧k,N−1,i000001,G^k,li=Ii−100⋯00cosψ^k,li0sinψ^k,li000Il−i−1000−sinψ^k,li0cosψ^k,li00000IN−l.When we assume thatNt=Nr=N, the total number of bits for each user NFGR can be calculated using the formula NFGR=No×nb×NN−1, where No represents the number of OFDM subcarriers. Based on the fact that the feedback overhead without compression is No×nb×2×N2, the feedback overhead compression rate can be expressed by N+1/2N. Unfortunately, this feedback overhead compression rate decreases with the growth of antenna ports. This last disadvantage limits the performance of GR in MMIMO.However, the GR remains an interesting method because, as mentioned previously, the SVD decomposition is only performed at each MS side. Therefore, to take advantage of this particularity of the GR approach, we propose its improvement in Section5.


## 4.2. Arithmetic Compression

Figure4 gives an overall view of the transmission model with arithmetic coding from the insertion of the pilot signs to the estimation of the channel to the preprocessing of precoding and feedback.Figure 4
The system model for arithmetic coding.


### 4.2.1. Description of Encoding and Decoding Principles

Arithmetic coding is a statistical coding, that is to say that more than one character is represented, the less bits need to be encoded [12]. The principle of the algorithm is as follows: First, we begin by subdividing the interval 0,1 in M intervals:
(23)Fxi−1,Fxi,i=1,⋯,MandFx0=0.Then we must make a mapping of the symbols of the alphabet that make up the sequence to compress to the intervals:(24)ak⇔Fxi−1,Fxik=1,⋯,NandFx0=0.So any real in the intervalFxi−1,⋯,Fxi may represent the symbol ak.Algorithm 1:AC feedback overhead encoding.
1: Input:A=ai,i=1,⋯,N: sequence to compress; p1,p2,⋯,pM: the symbol probabilities are known .2: Output Val: a real value in the range0,1 which represents the sequence.3: (Cum= cumulative probability and coincides with the various terminals:Fx);4:fori=1:Mdo5:cumi≔cumi−1+pi;   ⊳M being the number of the symbol alphabet (the number of intervals).6:low=0;                        ⊳ the lower bound7:high=1;                       ⊳ the upper bound8:fori=1:Ndo9:Range=high−low;10:high=low+Range∗cumai−1;11:low=low+Range∗cumai;12:returnval=lower+high/2;  ⊳ Val is the code word but any value from [low and high) is good.Algorithm 2: AC feedback overhead decoding.
1: Input:val: bit stream (compressed version of the sequence); N: the number of symbols to be decoded; p1,p2,⋯,pM: the symbol probabilities are known.2: Output: the decoded sequenceA.3: Begin-decoding⊳ (Cum = cumulative probability and coincides with the various terminals: Fx);4:cum0=p1;5:fori=1:Ndo6:cumi≔cumi−1+pi;7:low=0;                        ⊳ the lower bound8:high≔1;                        ⊳ the upper bound9:fori=1:Ndo10:Range=high−low;11:z=val−low/Range;12:j=2;13:while (j<N) and (cumj−1>zorz>cumj) do ⊳ we find the index j such this condition is fulfilled14:ifcumj−1<z<cumjthen15:ai=j;;16:else17:j=j+1;18:19:20:high=low+Range∗cumj−1;21:low=low+Range∗cumj;22:23:returnA=a1,a1a2,⋯aN;To better understand arithmetic coding, we will use a simple example. Let us go back to our sequence to compress: “MIMOMISO.” The length of this sequence is 8. Table3 defines the probabilities of the characters in our sequence as well as the relative intervals, respectively.Table 3
Probability tables and interval definitions.
SymbolsOccurrencesProbabilitiesIntervalsI20.250;0.25M30.3750.25;0.625O20.250.625;0875S10.1250.875;1Once this is done, we can now apply the arithmetic coding algorithm defined previously and we get Table4.Table 4
The arithmetic encoding process.
SymbolsLower boundUpper boundInitially01M0.250.625I0.250.34375M0.27343750.30859375O0.295410160.30419922M0.297607420.30090332I0.297607420.298431400S0.29832840250.298431400O0.29839792581250.2984185253125Thus, 0.2983979258125 is the arithmetic representation of the “MIMOMISO” message. In practice, any number between 0.2983979258125 and 0.2984185253125 represents the correct message.Figure5 shows the coding process.Figure 5
The representation of the arithmetic coding process of the message “MIMOMISO.”Decoding is just as simple: knowing that the encoded message is in the interval0.25;0.625; thus, the first letter is indeed an M. We then subtract the lower bound (for M), and we divide by the probability (for M); we thus obtain 0.1290611355 which is included in the interval 0;0.25, and so, the next letter will be an I. We continue to subtract the lower bound (for I) and divide by the probability (for I); this gives 0.516244542 which is in the interval 0.25;0.625, and therefore. the next letter will be an M, etc.


### 4.2.2. Solving the Arithmetic Coding Overflow Problem

The two preceding algorithms give the classical arithmetic encoding and decoding. However, one of the main problems with arithmetic coding is the phenomenon of overflow: overflow and underflow. These are issues related to the precision of machines (hardware). To overcome this, the most used technique is that of scaling. The principle of this can be described as follows:(i)
Resizing interval: we increase the size of the interval, but we must preserve the information(ii)
Incremental encoding: transmission of the code portion by portion as the encoding progresses(iii)
We start from the observation of 3 possibilities concerning the interval during encoding:(1)
Interval is included in the lower half:0,0.5(2)
Interval is included in the upper half:0.5,1(3)
The interval contains the center point 0.5(iv)
When the gap is in one of the halves, it will stay in that half throughout the encoding of the sequence(v)
The most significant bit (MSB) is 0 if the interval is in0,0.5(vi)
MSB is 1 if the interval is in0.5,1(vii)
So when the interval is in one of the halves, the most significant bit becomes known(viii)
Once the encoder and decoder know which part we are in, we can ignore the other half(ix)
To implement the algorithm on a finite precision system, which is our case, we can resize the half in question to regain the interval0,1 in full. This will result in the loss of information on MSB, but it does not matter because we have already sent the MSB. We continue the coding, and each time we are in one half, we send a bit. This is an incremental coding(1)
Ifhigh<0.5(i)
Transmit bit 0 and add a 0 to the p number of pending bits(ii)
Low=2low(iii)
High=2high(2)
Iflow>0.5(i)
Transmit bit 1 and add a 0 to the p number of pending bits(ii)
Low=2 (low-0.5)(iii)
High=2 (high-0.5)(3)
Iflow>0.25 and high<0.75(i)
Add a 1 to the p number of pending bits(ii)
Low=2 (low-0.25)(iii)
High=2 (high-0.25)Note that the interval is scaled (zoomed) for each output bit. This multiplication by 2 means moving the binary point one position to the right. Sometimes it is easier to work with integers than to work with comma numbers. To apply arithmetic coding to integers, just do the following:(i)
Use symbol frequencies instead of probability(ii)
Replace0,1 by 0,2k−1(iii)
Replace 0.5 by2k−1−1(iv)
Replace 0.25 by2k−2−1(v)
Replace 0.75 by3.2k−2−1Here is the formula to calculate the following interval:(25)high=low+rangecumsymbol/total_freq‐1,low=low+rangecumsymbol‐1/total_freq.Thus, Algorithms1 and 2 become Algorithms 3 and 4, respectively: First we ask: First_qtr=2k−1−1, half=2k−2−1, and Third_qtr=3.2k−2−1.Algorithm 3: AC feedback overhead encoding.
1: Input:A=ai,i=1,⋯,N: sequence to compress; p1,p2,⋯,pM: the symbol probabilities are known.2: Output Val: a binary number that represents sequenceA.3: (Cum = cumulative probability and coincides with the various terminals:Fx); cum0=04:for {i=1:M} do5:cumi≔cumi−1+pi;   ⊳M is the number of symbols in the alphabet (the number of intervals)6: low =0; high=2k−1      ⊳ the lower and upper bound; K the number of bits7: First_qtr=2k−1; half= 2k−2; Third_qtr= 3.2k−2;8: bits_To_follow:=0; ⊳ Number of bits to look at in order to know which part we are on9fori=1:Ndo10:Range=high−low+1;11:high=low+Range∗cumai−1/cum1−1;12:low=low+Range∗cumai/cum1;13:while 1 do14:    ifhigh<Half                  ⊳ the lower part15:    transmission of bit “0”;B=B0;16:    low =2 low; high =2 high;17:    else iflow>=Half                ⊳ the high part18:    transmission of bit “1”;B=B1;19:    low = low-Half; high = high-Half;20:    low =2 low; high =2 high;21:    else iflow>=First_qtrandhigh<Third_qtr    ⊳ n the middle22:    bits_To_follow =bits_To_follow + 1;23:    low = low-First_qtr; high = high-First_qtr;24:    low =2 low; high =2 high;25:    else26:    break;27:    End if;After that we encode the symbol EOF_symbol as before to allow the decoder to stop.28:returnC=bin2decB;  ⊳ bin2dec converts the binary vector to a decimal number=0Algorithm 4: AC feedback overhead decoding.
1: Input:val: Bit stream (compressed version of the sequence); N: the number of symbols to be decoded; p1,p2,⋯,pM: the symbol probabilities are known.2: Output: the decoded sequenceA.3: Cum = cumulative probability and coincides with the various terminals:Fx); cum0=p1;4:fori=1:Mdo5:cumi≔cumi−1+pi;  ⊳M is the number of symbols in the alphabet (the number of intervals)6: low =0; high=2k−17: First_qtr=2k−1; half=2k−2; Third_qtr= 3.2k−2;8:while 1 do9:Range=high−low+1;10:cumval=val−low+1∗cum1−1/range;11:symbol=2;12:whilecumsymbol>cumvaldo13:symbol=symbol+1;14:high=low+range∗cumsymbol−1/cum1−1;15:low=low+range∗cumsymbol/cum1;16:while 1 do17:   ifhigh<Half     ⊳ the lower part        ⊳ we do nothing18:   else iflow>=Half                  ⊳ the high part19:   val = val-Half; low = low-Half; high = high-Half;20:   else iflow>=First_qtrandhigh<Third_qtr      ⊳ In the middle21:   val = val-First_qtr; low = low-First_qtr; high = high-First_qtr;22:   else23:   break;24:   End if;25:   low =2 low; high =2 high; val =2 val + bit;⊳ Move to next input bit26:   ifsymbol=EOF_symbol                  ⊳ the end27:   break;28:   End if;29:   A=symbol;30:returnA


## 4.2.1. Description of Encoding and Decoding Principles

Arithmetic coding is a statistical coding, that is to say that more than one character is represented, the less bits need to be encoded [12]. The principle of the algorithm is as follows: First, we begin by subdividing the interval 0,1 in M intervals:
(23)Fxi−1,Fxi,i=1,⋯,MandFx0=0.Then we must make a mapping of the symbols of the alphabet that make up the sequence to compress to the intervals:(24)ak⇔Fxi−1,Fxik=1,⋯,NandFx0=0.So any real in the intervalFxi−1,⋯,Fxi may represent the symbol ak.Algorithm 1:AC feedback overhead encoding.
1: Input:A=ai,i=1,⋯,N: sequence to compress; p1,p2,⋯,pM: the symbol probabilities are known .2: Output Val: a real value in the range0,1 which represents the sequence.3: (Cum= cumulative probability and coincides with the various terminals:Fx);4:fori=1:Mdo5:cumi≔cumi−1+pi;   ⊳M being the number of the symbol alphabet (the number of intervals).6:low=0;                        ⊳ the lower bound7:high=1;                       ⊳ the upper bound8:fori=1:Ndo9:Range=high−low;10:high=low+Range∗cumai−1;11:low=low+Range∗cumai;12:returnval=lower+high/2;  ⊳ Val is the code word but any value from [low and high) is good.Algorithm 2: AC feedback overhead decoding.
1: Input:val: bit stream (compressed version of the sequence); N: the number of symbols to be decoded; p1,p2,⋯,pM: the symbol probabilities are known.2: Output: the decoded sequenceA.3: Begin-decoding⊳ (Cum = cumulative probability and coincides with the various terminals: Fx);4:cum0=p1;5:fori=1:Ndo6:cumi≔cumi−1+pi;7:low=0;                        ⊳ the lower bound8:high≔1;                        ⊳ the upper bound9:fori=1:Ndo10:Range=high−low;11:z=val−low/Range;12:j=2;13:while (j<N) and (cumj−1>zorz>cumj) do ⊳ we find the index j such this condition is fulfilled14:ifcumj−1<z<cumjthen15:ai=j;;16:else17:j=j+1;18:19:20:high=low+Range∗cumj−1;21:low=low+Range∗cumj;22:23:returnA=a1,a1a2,⋯aN;To better understand arithmetic coding, we will use a simple example. Let us go back to our sequence to compress: “MIMOMISO.” The length of this sequence is 8. Table3 defines the probabilities of the characters in our sequence as well as the relative intervals, respectively.Table 3
Probability tables and interval definitions.
SymbolsOccurrencesProbabilitiesIntervalsI20.250;0.25M30.3750.25;0.625O20.250.625;0875S10.1250.875;1Once this is done, we can now apply the arithmetic coding algorithm defined previously and we get Table4.Table 4
The arithmetic encoding process.
SymbolsLower boundUpper boundInitially01M0.250.625I0.250.34375M0.27343750.30859375O0.295410160.30419922M0.297607420.30090332I0.297607420.298431400S0.29832840250.298431400O0.29839792581250.2984185253125Thus, 0.2983979258125 is the arithmetic representation of the “MIMOMISO” message. In practice, any number between 0.2983979258125 and 0.2984185253125 represents the correct message.Figure5 shows the coding process.Figure 5
The representation of the arithmetic coding process of the message “MIMOMISO.”Decoding is just as simple: knowing that the encoded message is in the interval0.25;0.625; thus, the first letter is indeed an M. We then subtract the lower bound (for M), and we divide by the probability (for M); we thus obtain 0.1290611355 which is included in the interval 0;0.25, and so, the next letter will be an I. We continue to subtract the lower bound (for I) and divide by the probability (for I); this gives 0.516244542 which is in the interval 0.25;0.625, and therefore. the next letter will be an M, etc.


## 4.2.2. Solving the Arithmetic Coding Overflow Problem

The two preceding algorithms give the classical arithmetic encoding and decoding. However, one of the main problems with arithmetic coding is the phenomenon of overflow: overflow and underflow. These are issues related to the precision of machines (hardware). To overcome this, the most used technique is that of scaling. The principle of this can be described as follows:(i)
Resizing interval: we increase the size of the interval, but we must preserve the information(ii)
Incremental encoding: transmission of the code portion by portion as the encoding progresses(iii)
We start from the observation of 3 possibilities concerning the interval during encoding:(1)
Interval is included in the lower half:0,0.5(2)
Interval is included in the upper half:0.5,1(3)
The interval contains the center point 0.5(iv)
When the gap is in one of the halves, it will stay in that half throughout the encoding of the sequence(v)
The most significant bit (MSB) is 0 if the interval is in0,0.5(vi)
MSB is 1 if the interval is in0.5,1(vii)
So when the interval is in one of the halves, the most significant bit becomes known(viii)
Once the encoder and decoder know which part we are in, we can ignore the other half(ix)
To implement the algorithm on a finite precision system, which is our case, we can resize the half in question to regain the interval0,1 in full. This will result in the loss of information on MSB, but it does not matter because we have already sent the MSB. We continue the coding, and each time we are in one half, we send a bit. This is an incremental coding(1)
Ifhigh<0.5(i)
Transmit bit 0 and add a 0 to the p number of pending bits(ii)
Low=2low(iii)
High=2high(2)
Iflow>0.5(i)
Transmit bit 1 and add a 0 to the p number of pending bits(ii)
Low=2 (low-0.5)(iii)
High=2 (high-0.5)(3)
Iflow>0.25 and high<0.75(i)
Add a 1 to the p number of pending bits(ii)
Low=2 (low-0.25)(iii)
High=2 (high-0.25)Note that the interval is scaled (zoomed) for each output bit. This multiplication by 2 means moving the binary point one position to the right. Sometimes it is easier to work with integers than to work with comma numbers. To apply arithmetic coding to integers, just do the following:(i)
Use symbol frequencies instead of probability(ii)
Replace0,1 by 0,2k−1(iii)
Replace 0.5 by2k−1−1(iv)
Replace 0.25 by2k−2−1(v)
Replace 0.75 by3.2k−2−1Here is the formula to calculate the following interval:(25)high=low+rangecumsymbol/total_freq‐1,low=low+rangecumsymbol‐1/total_freq.Thus, Algorithms1 and 2 become Algorithms 3 and 4, respectively: First we ask: First_qtr=2k−1−1, half=2k−2−1, and Third_qtr=3.2k−2−1.Algorithm 3: AC feedback overhead encoding.
1: Input:A=ai,i=1,⋯,N: sequence to compress; p1,p2,⋯,pM: the symbol probabilities are known.2: Output Val: a binary number that represents sequenceA.3: (Cum = cumulative probability and coincides with the various terminals:Fx); cum0=04:for {i=1:M} do5:cumi≔cumi−1+pi;   ⊳M is the number of symbols in the alphabet (the number of intervals)6: low =0; high=2k−1      ⊳ the lower and upper bound; K the number of bits7: First_qtr=2k−1; half= 2k−2; Third_qtr= 3.2k−2;8: bits_To_follow:=0; ⊳ Number of bits to look at in order to know which part we are on9fori=1:Ndo10:Range=high−low+1;11:high=low+Range∗cumai−1/cum1−1;12:low=low+Range∗cumai/cum1;13:while 1 do14:    ifhigh<Half                  ⊳ the lower part15:    transmission of bit “0”;B=B0;16:    low =2 low; high =2 high;17:    else iflow>=Half                ⊳ the high part18:    transmission of bit “1”;B=B1;19:    low = low-Half; high = high-Half;20:    low =2 low; high =2 high;21:    else iflow>=First_qtrandhigh<Third_qtr    ⊳ n the middle22:    bits_To_follow =bits_To_follow + 1;23:    low = low-First_qtr; high = high-First_qtr;24:    low =2 low; high =2 high;25:    else26:    break;27:    End if;After that we encode the symbol EOF_symbol as before to allow the decoder to stop.28:returnC=bin2decB;  ⊳ bin2dec converts the binary vector to a decimal number=0Algorithm 4: AC feedback overhead decoding.
1: Input:val: Bit stream (compressed version of the sequence); N: the number of symbols to be decoded; p1,p2,⋯,pM: the symbol probabilities are known.2: Output: the decoded sequenceA.3: Cum = cumulative probability and coincides with the various terminals:Fx); cum0=p1;4:fori=1:Mdo5:cumi≔cumi−1+pi;  ⊳M is the number of symbols in the alphabet (the number of intervals)6: low =0; high=2k−17: First_qtr=2k−1; half=2k−2; Third_qtr= 3.2k−2;8:while 1 do9:Range=high−low+1;10:cumval=val−low+1∗cum1−1/range;11:symbol=2;12:whilecumsymbol>cumvaldo13:symbol=symbol+1;14:high=low+range∗cumsymbol−1/cum1−1;15:low=low+range∗cumsymbol/cum1;16:while 1 do17:   ifhigh<Half     ⊳ the lower part        ⊳ we do nothing18:   else iflow>=Half                  ⊳ the high part19:   val = val-Half; low = low-Half; high = high-Half;20:   else iflow>=First_qtrandhigh<Third_qtr      ⊳ In the middle21:   val = val-First_qtr; low = low-First_qtr; high = high-First_qtr;22:   else23:   break;24:   End if;25:   low =2 low; high =2 high; val =2 val + bit;⊳ Move to next input bit26:   ifsymbol=EOF_symbol                  ⊳ the end27:   break;28:   End if;29:   A=symbol;30:returnA


## 4.3. LZW Compression

Among the most powerful data compression techniques, we can mention the compression algorithms based on the use of a dictionary. These are lossless data compression techniques that uses a dictionary with a predetermined state, but its value may be changed during the encoding or decoding process. One of the best-known dynamic dictionary-based compression algorithms is the LZW algorithm, which was created as a modification of the LZ78 algorithm [13]. It is a general-purpose compression algorithm in the sense that it can work with almost any type of data. LZW is a dictionary-based compression method [9] that associates a variable number of symbols (subsequences) with a code of fixed length. The algorithm works by traversing the input sequence to search a subsequence that is not in the dictionary. When such a subsequence is found, the index of the subsequence without the last element (that is, the longest subsequence of the dictionary) is extracted from the dictionary and sent to the output; then the new subsequence (including the last element) is added to the dictionary with the next available code. The last element entered is then used as the next starting point for searching for subsequences [9]. Increasingly long subsequences are stored in the dictionary and made available for later encoding as single output values.Figure6 gives an overall view of the transmission model with LZW compressing from the insertion of the pilot signs to the estimation of the channel with the preprocessing of precoding and feedback.Figure 6
The system model for LZW coding.The algorithm works best on data with repeated models. Like any compression algorithm, the LZW is defined by compression: obtained by replacing the subsequences with the codes associated with them in the dictionary and by decompression: performed by replacing sets of code words with their associated subsequences in the dictionary.Thus, the coding and decoding algorithms are, respectively, presented in Algorithms1 and 2, where BDC and DBC stand for, respectively, binary to decimal conversion and decimal to binary conversion.Algorithm 5: LZW feedback overhead encoding.
1: Initialize the dictionary with all integer values from0 to 2nb−12: Consider for each input binary sequence of lengthnb his BDC as a code3:Vmax=2nb−14:W=first input binary sequence of length nb5:while not end of the input nb sequences do6:C=next input binary sequence of length nb7:if the code of W concatenated with C is in the dictionary then8:  ReplaceW by W concatenated with C9:else10:Vmax=Vmax+111:   Output code ofW12:   AddVmax as the code of W concatenated with C in the dictionary.13:   ReplaceW by C14: Output the code ofW=0Algorithm 6: LZW feedback overhead decoding.
1: Initialize the dictionary with all integer values from0 to 2nb−12:Vmax=2nb−13: OLD=first input code of the codes stream4: Output the DBC of OLD5:while not end of input codes stream do6:  CURRENT = next input code of the codes stream7:  Output the sequence ofnb or a multiple of nb bits corresponding to CURRENT in the dictionary8:Vmax=Vmax+19:  AddVmax in the dictionary as the code of the sequence of bits corresponding to OLD concatenated with the first nb bits of that corresponding to CURRENT10:  Replace OLD by CURRENTIn the LZW encoding and decoding, we can see the following:(i)
The LZW algorithm is very simple. In addition to this, the dictionary is designed at the same time as the encoding or decoding and does not need to be saved(ii)
The efficiency of the algorithm increases as the number of repetitive sequences in the input data increases(iii)
At each MS side, after the GR compression, allNo×NMSkNMSk−1 output sequences of length nb bits are concatenated to get the AC or LZW input binary sequence(iv)
At the BS side, the AC or LZW decoding algorithm is used before the GR one to retrieve the precoding matrixPk, for k=1,⋯,K


## 5. Improved GR

To improve the GR feedback compression, we have proposed two methods in which the AC or LZW algorithm is applied to the output quantized anglesψ^ and ϕ^ which are sequences of length nb bits.


### 5.1. Validation of the Number of Quantizer Bits per Angle

Figures7–10 show the bit error rate (BER) as a function of signal-to-noise ratio (SNR) in the multiuser UL FDD MMIMO-OFDM context. The modulations are, respectively, 4-QAM and 16-QAM. Two schemes are considered, one with quantized feedback overhead compression by considering several values of nb and one without compression. Several values of the parameters M, N, and K are also considered.Figure 7
BER performance in the DL FDD MMIMO-OFDM contextM=64, N=4, K=16, and 256-QAM.Figure 8
BER performance in the DL FDD MMIMO-OFDM contextM=64, N=4, K=16, and 64-QAM.Figure 9
BER performance in the DL FDD MMIMO-OFDM contextM=16, N=4, K=16, and 4-QAM.Figure 10
BER performance in the DL FDD MMIMO-OFDM contextM=64, N=4, K=16, and 16-QAM.As we can see, the quatization error is negligible whennb reaches 8bit. The performances with or without quantization are the same in all considered configurations. Therefore, nb=8 is enough for the elimination of the quantization noise affect in the system performance. It is this number of quantizer bit nb=8 that has been adopted in the IEEE 802.11ac standard [14].


### 5.2. Compression Rate

The compression rates of conventional GR and the proposed GR with AC- (GR & AC) and LZW- (GR & LZW) based feedback overhead compression for different MMIMO configurations and number of OFDM subcarriers (No) are listed in Table 5. Note that the number of quantizer bits is fixed to nb=8 as previously validated.Table 5
Compression rate of the conventional Givens rotation and the proposed Givens rotation with AC and LZW algorithms in different MMIMO-OFDM configurations.NBS, NMSk, and No, respectively, stand for the number of antennas at the BS, the number of antennas at each UE, the number of UEs, and the number of OFDM subcarriers.
MMIMOOFDMM×N×NoFeedback amount in bitsAmount with GR in bitsCompression rateAmount with amount with GR & LZW in bitsCompression rateAmount with amount with GR & AC in bitsCompression rate64×4×12852428819660862.5%2678494.89%8050483.18%64×4×256104857639321662.5%3830496.35%17910483.15%64×4×512209715278643262.5%6048097.12%34047283.37%64×4×10244194304157286462.5%8608097.95%67957683.17%128×4×128104857639321662.5%5356894.89%17092083.38%128×4×256209715278643262.5%7660896.35%35684883.29%128×4×5124194304157286262.5%12096097.12%67958483.25%128×4×10248388608314572862.5%25773096.93%142330483.26%64×8×128104857645875256.25%7629692.72%31755270.25%64×8×256209715291750456.25%10912094.80%62417670.31%64×8×5124194304183500856.25%15514096.30%124404070.50%64×8×10248388608367001656.25%20397097.57%251956870.36%128×8×1282097152117964856.25%19642090.63%62672069.99%128×8×2564194304183500856.25%21824094.80%124912870.68%128×8×5128388608367001656.25%31047096.30%250938470.56%128×8×102416777216743003256.25%48705097.10%482907270.56%.As demonstrated in Section4, the compression rate of conventional GR is NMSk+1/2NMSk. That is why, in Table 5, for any MMIMO configuration and any number of OFDM subcarriers No, the compression rates are 56.25.5% and 62.5% when the numbers of antennas at each UE are, respectively, NMSk=4 and NMSk=8.Unlike the conventional GR compression rate which only depends on the number of antennas per UE, the GR & LZW one takes advantage on the evolution of others parameters, especially the number of OFDM subcarriers. Because, the moreNo increases, the more there is repetitive binary sequences of length nb. Accordingly, the compression rate increases considerably as the structure of LZW algorithm enables improvement of compression capacity when the repetitive sequences become large.Then, observing the behavior of the GR & LZW compression rate in Table5, we can note that, for the same MMIMO configuration (when NBS and NMSk are fixed), the compression rate of the proposed GR & LZW increases with the number of OFDM subcarriers No.In order to always push the compression rate, we have tried to improve the LZW algorithm that we have just applied on the GR method. To fully explain the new method proposed, GR & LZWM, we will be based on a simple example of compression with LZW.Let us take the sequence “MIMOMISO” to compress with LZW. In this case, the incoming stream will correspond to the ASCII codes of the letters contained in the sequence. For example, the ASCII code ofB is 98. So, the ASCII version of our sequence is as follows:To better understand LZW compression as well as the proposed modification, let us apply it to the text “MIMOMOSI” (see Tables6 and 7 where the ASCII decimal codes of M, I, O, and S are 77, 73, 79, and 83). This example shows
(i)
The LZW algorithm is very simple. In addition to this, the dictionary is designed at the same time as the encoding or the decoding and does not need to be saved(ii)
The efficiency of the algorithm increases as the number of repetitive sequences in the input data increasesTable 6
LZW encoding of “MIMOMOSI.”
StepsCWCodeDictionary1MM is known2II77MI is encoded to 2573MM73IM is encoded to 2584OO77MO is encoded to 2595MM79OM is encoded to 2606OMOMO is known7SS259MOS is encoded to 2618II83SI is encoded to 2629I73I is knownThe output is 77, 73, 77, 79, 259, 83, and 73Table 7
LZW decoding of the code “77, 73, 77, 79, 259, 83, and 73.”
StepsOLDCURRENTDecoding char or stringDictionary177M27373IMI is encoded to 25737777MIM is encoded to 25847979OMO is encoded to 2595259259MOOM is encoded to 26068383SMOS is encoded to 26177373ISI is encoded to 262The output is “MIMOMOSI”


### 5.3. LZW Modified

It is important to note that all outputs of the LZW encoder must be with the same number of bits which depends on the largest value in the dictionary. In the previous example, each output must be encoded with9 bits. Indeed, it is the length of the number 259 which will be that of the other numbers of the output. However, apart from this number, the others can be coded with 8 bits because they do not exceed 256=28.So, it will be interesting to see how to make the outputs of the LZW encoder individually coded with the minimum number of bits required. To do this, we have adopted another demarcation from the LZW algorithm name LZWM.(i)
First, we have defined a word from the dictionary as a reserved word: for the initial dictionary (0 to 255), the number 255 is reserved. This number will serve as a flag to warn the decoder about the number of bits encoded. So our initial dictionary becomes 0 to 254.(ii)
The first word of the output is 255: to signal to the decoder that the number of coded bits is9(iii)
Each time we encode a word, before putting it in the output sequence, we check whether it is greater than29−1:
(1)
If so, we place in the output sequence 29-1 to indicate that now the number of bits is 10(2)
And so on, until the end of the sequence is encoded(iv)
Otherwise, we place the latter code in the output sequence


#### 5.3.1. Comparison between LZW and LZWM

Table8 gives the LZWM encoding of our previous sequence. So in this example, the gain from the modification is not very visible (we even lose; Table 9). Indeed, the length of the sequence is very reduced; suddenly, there is no jump, i.e., going to 10 bits, 11 bits, and so on.Table 8
Encoding of “MIMOMOSI” by LZWM.
StepsCWCodeDictionaryNumber of coded bits125582MM is known3II77MI is not in the dictionary: we test if 257<29−1 (if this is true, we keep 257; otherwise, we send 29−1=511),and MI is encoded by 51394MM73IM is encoded to 25895OO77MO is encoded to 25996MM79OM is encoded to 26097OMOMO is known98SS259MOS is encoded to 26199II83SI is encoded to 262910II73I is known9The output is 77, 73, 77, 79, 259, 83, and 73Table 9
Number of bits for LZW and LZWM of the code “77, 73, 77, 79, 259, 83, and 73.”
LZWLZWMOutput sequence77, 73, 77, 79, 259, 83,and 7377, 73, 77, 79, 259, 83, and 73Number of bits9+9+9+9+9+9+9=63bits8+9+9+9+9+9+9+9=71bitsHowever, this article is part of a MMIMO context, which means that the sequences that we will be called upon to compress will take very large dimensions. Thus, this gain could become interesting. Moreover, the study allowed us to define the minimum and maximum gains of this method compared to the classical one.To generalize, let us setNd the number of starting bits and Nf the final number of bits. For Nd=8 and Nf=12, we have the following:
(i)
At a minimum, we have29−1−112−9−8 before going to 10 bits. 8 is the number of bits inserted so the flag(ii)
At a minimum, we have210−9−112−10−9 before going to 11 bits(iii)
At least we have211−10−112−11−10 before going to 12 bitsIn general, we will have a gain:(i)
At least we have(26)2Nd−1Nf−Nd−1∑n=Nd+1Nf−12n+1−2n−1−1Nf−n+1−n,which gives
(27)Gmin=∑n=Nd+1Nf−Nd−12n−1Nf−n−1−n(ii)
Likewise, at most(28)Gmax=∑n=Nd+1Nf−Nd−12n+1−1Nf−n−1−nTherefore, let us keep the same previous simulation parameters 1, and we consider the case where we have a single user and a multipath MMIMO channel; the comparison of the two algorithms gives Table10.Table 10
Comparisons between LZW and LZWM.
Number of subcarriers16×161282565121024LZW80.5752%84.7580%89.3175%91.8718%LZWM81.8413%86.1474%90.0122%92.6036%Though Table10 confirms that the modified version of the LZW algorithm has a gain of about 2% compared to the classic version, this percentage gain may seem small, but let us just remember that we are in a MMIMO context, so 2% of the data handled is necessarily significant. In addition, we will see later that if we apply these two algorithms to the GR method, the difference in favor of LZWM becomes more important.Thus, Table11 gives the comparison of the application of the new method proposed for some MMIMO-OFDM configurations.Table 11
Compression rate of LZW and LZWM algorithms in different MMIMO-OFDM configurations.NBS, NMSk, and No, respectively, stand for the number of antennas at the BS, the number of antennas at each UE, the number of UEs, and the number of OFDM subcarriers.
MMIMO-OFDMM×N×NoFeedback amount without compression in bitsFeedback amount with GR & LZW in bitsCompression rateFeedback amount with GR & LZWM in bitsCompression rate64×4×1285242883566493.20%7373 98.59%64×4×25610485765522494.73%1087898.96%64×4×51220971527861196.25%1581799.24%64×8×12810485769005191.42%2728297.39%64×8×256209715213862893.38%3987098.09%64×8×512419430419728895.29%5889598.59%128×8×256419430429680592.92%5889598.59%128×8×512838860842247594.96%8618298.97%128×8×10241677721664070496.18%12695799.24%In summary, we can say that excessive feedback overload is a major handicap in FDD MMIMO systems. Therefore, this excess downlink feedback must be compressed by sophisticated algorithms. Significant efforts are being made in this direction, and several solutions are proposed. We have proposed two lossless compression solutions based on the GR & LZW compression algorithm and a derivative of the latter: GR & LZWM. These algorithms can be considered evolutions of the Givens rotation method which is adopted in the WLAN standard IEEE 802.11/c. The results of the simulations show that the proposed methods can achieve more than 95% and 98% compression ratios, respectively.


## 5.1. Validation of the Number of Quantizer Bits per Angle

Figures7–10 show the bit error rate (BER) as a function of signal-to-noise ratio (SNR) in the multiuser UL FDD MMIMO-OFDM context. The modulations are, respectively, 4-QAM and 16-QAM. Two schemes are considered, one with quantized feedback overhead compression by considering several values of nb and one without compression. Several values of the parameters M, N, and K are also considered.Figure 7
BER performance in the DL FDD MMIMO-OFDM contextM=64, N=4, K=16, and 256-QAM.Figure 8
BER performance in the DL FDD MMIMO-OFDM contextM=64, N=4, K=16, and 64-QAM.Figure 9
BER performance in the DL FDD MMIMO-OFDM contextM=16, N=4, K=16, and 4-QAM.Figure 10
BER performance in the DL FDD MMIMO-OFDM contextM=64, N=4, K=16, and 16-QAM.As we can see, the quatization error is negligible whennb reaches 8bit. The performances with or without quantization are the same in all considered configurations. Therefore, nb=8 is enough for the elimination of the quantization noise affect in the system performance. It is this number of quantizer bit nb=8 that has been adopted in the IEEE 802.11ac standard [14].


## 5.2. Compression Rate

The compression rates of conventional GR and the proposed GR with AC- (GR & AC) and LZW- (GR & LZW) based feedback overhead compression for different MMIMO configurations and number of OFDM subcarriers (No) are listed in Table 5. Note that the number of quantizer bits is fixed to nb=8 as previously validated.Table 5
Compression rate of the conventional Givens rotation and the proposed Givens rotation with AC and LZW algorithms in different MMIMO-OFDM configurations.NBS, NMSk, and No, respectively, stand for the number of antennas at the BS, the number of antennas at each UE, the number of UEs, and the number of OFDM subcarriers.
MMIMOOFDMM×N×NoFeedback amount in bitsAmount with GR in bitsCompression rateAmount with amount with GR & LZW in bitsCompression rateAmount with amount with GR & AC in bitsCompression rate64×4×12852428819660862.5%2678494.89%8050483.18%64×4×256104857639321662.5%3830496.35%17910483.15%64×4×512209715278643262.5%6048097.12%34047283.37%64×4×10244194304157286462.5%8608097.95%67957683.17%128×4×128104857639321662.5%5356894.89%17092083.38%128×4×256209715278643262.5%7660896.35%35684883.29%128×4×5124194304157286262.5%12096097.12%67958483.25%128×4×10248388608314572862.5%25773096.93%142330483.26%64×8×128104857645875256.25%7629692.72%31755270.25%64×8×256209715291750456.25%10912094.80%62417670.31%64×8×5124194304183500856.25%15514096.30%124404070.50%64×8×10248388608367001656.25%20397097.57%251956870.36%128×8×1282097152117964856.25%19642090.63%62672069.99%128×8×2564194304183500856.25%21824094.80%124912870.68%128×8×5128388608367001656.25%31047096.30%250938470.56%128×8×102416777216743003256.25%48705097.10%482907270.56%.As demonstrated in Section4, the compression rate of conventional GR is NMSk+1/2NMSk. That is why, in Table 5, for any MMIMO configuration and any number of OFDM subcarriers No, the compression rates are 56.25.5% and 62.5% when the numbers of antennas at each UE are, respectively, NMSk=4 and NMSk=8.Unlike the conventional GR compression rate which only depends on the number of antennas per UE, the GR & LZW one takes advantage on the evolution of others parameters, especially the number of OFDM subcarriers. Because, the moreNo increases, the more there is repetitive binary sequences of length nb. Accordingly, the compression rate increases considerably as the structure of LZW algorithm enables improvement of compression capacity when the repetitive sequences become large.Then, observing the behavior of the GR & LZW compression rate in Table5, we can note that, for the same MMIMO configuration (when NBS and NMSk are fixed), the compression rate of the proposed GR & LZW increases with the number of OFDM subcarriers No.In order to always push the compression rate, we have tried to improve the LZW algorithm that we have just applied on the GR method. To fully explain the new method proposed, GR & LZWM, we will be based on a simple example of compression with LZW.Let us take the sequence “MIMOMISO” to compress with LZW. In this case, the incoming stream will correspond to the ASCII codes of the letters contained in the sequence. For example, the ASCII code ofB is 98. So, the ASCII version of our sequence is as follows:To better understand LZW compression as well as the proposed modification, let us apply it to the text “MIMOMOSI” (see Tables6 and 7 where the ASCII decimal codes of M, I, O, and S are 77, 73, 79, and 83). This example shows
(i)
The LZW algorithm is very simple. In addition to this, the dictionary is designed at the same time as the encoding or the decoding and does not need to be saved(ii)
The efficiency of the algorithm increases as the number of repetitive sequences in the input data increasesTable 6
LZW encoding of “MIMOMOSI.”
StepsCWCodeDictionary1MM is known2II77MI is encoded to 2573MM73IM is encoded to 2584OO77MO is encoded to 2595MM79OM is encoded to 2606OMOMO is known7SS259MOS is encoded to 2618II83SI is encoded to 2629I73I is knownThe output is 77, 73, 77, 79, 259, 83, and 73Table 7
LZW decoding of the code “77, 73, 77, 79, 259, 83, and 73.”
StepsOLDCURRENTDecoding char or stringDictionary177M27373IMI is encoded to 25737777MIM is encoded to 25847979OMO is encoded to 2595259259MOOM is encoded to 26068383SMOS is encoded to 26177373ISI is encoded to 262The output is “MIMOMOSI”


## 5.3. LZW Modified

It is important to note that all outputs of the LZW encoder must be with the same number of bits which depends on the largest value in the dictionary. In the previous example, each output must be encoded with9 bits. Indeed, it is the length of the number 259 which will be that of the other numbers of the output. However, apart from this number, the others can be coded with 8 bits because they do not exceed 256=28.So, it will be interesting to see how to make the outputs of the LZW encoder individually coded with the minimum number of bits required. To do this, we have adopted another demarcation from the LZW algorithm name LZWM.(i)
First, we have defined a word from the dictionary as a reserved word: for the initial dictionary (0 to 255), the number 255 is reserved. This number will serve as a flag to warn the decoder about the number of bits encoded. So our initial dictionary becomes 0 to 254.(ii)
The first word of the output is 255: to signal to the decoder that the number of coded bits is9(iii)
Each time we encode a word, before putting it in the output sequence, we check whether it is greater than29−1:
(1)
If so, we place in the output sequence 29-1 to indicate that now the number of bits is 10(2)
And so on, until the end of the sequence is encoded(iv)
Otherwise, we place the latter code in the output sequence


### 5.3.1. Comparison between LZW and LZWM

Table8 gives the LZWM encoding of our previous sequence. So in this example, the gain from the modification is not very visible (we even lose; Table 9). Indeed, the length of the sequence is very reduced; suddenly, there is no jump, i.e., going to 10 bits, 11 bits, and so on.Table 8
Encoding of “MIMOMOSI” by LZWM.
StepsCWCodeDictionaryNumber of coded bits125582MM is known3II77MI is not in the dictionary: we test if 257<29−1 (if this is true, we keep 257; otherwise, we send 29−1=511),and MI is encoded by 51394MM73IM is encoded to 25895OO77MO is encoded to 25996MM79OM is encoded to 26097OMOMO is known98SS259MOS is encoded to 26199II83SI is encoded to 262910II73I is known9The output is 77, 73, 77, 79, 259, 83, and 73Table 9
Number of bits for LZW and LZWM of the code “77, 73, 77, 79, 259, 83, and 73.”
LZWLZWMOutput sequence77, 73, 77, 79, 259, 83,and 7377, 73, 77, 79, 259, 83, and 73Number of bits9+9+9+9+9+9+9=63bits8+9+9+9+9+9+9+9=71bitsHowever, this article is part of a MMIMO context, which means that the sequences that we will be called upon to compress will take very large dimensions. Thus, this gain could become interesting. Moreover, the study allowed us to define the minimum and maximum gains of this method compared to the classical one.To generalize, let us setNd the number of starting bits and Nf the final number of bits. For Nd=8 and Nf=12, we have the following:
(i)
At a minimum, we have29−1−112−9−8 before going to 10 bits. 8 is the number of bits inserted so the flag(ii)
At a minimum, we have210−9−112−10−9 before going to 11 bits(iii)
At least we have211−10−112−11−10 before going to 12 bitsIn general, we will have a gain:(i)
At least we have(26)2Nd−1Nf−Nd−1∑n=Nd+1Nf−12n+1−2n−1−1Nf−n+1−n,which gives
(27)Gmin=∑n=Nd+1Nf−Nd−12n−1Nf−n−1−n(ii)
Likewise, at most(28)Gmax=∑n=Nd+1Nf−Nd−12n+1−1Nf−n−1−nTherefore, let us keep the same previous simulation parameters 1, and we consider the case where we have a single user and a multipath MMIMO channel; the comparison of the two algorithms gives Table10.Table 10
Comparisons between LZW and LZWM.
Number of subcarriers16×161282565121024LZW80.5752%84.7580%89.3175%91.8718%LZWM81.8413%86.1474%90.0122%92.6036%Though Table10 confirms that the modified version of the LZW algorithm has a gain of about 2% compared to the classic version, this percentage gain may seem small, but let us just remember that we are in a MMIMO context, so 2% of the data handled is necessarily significant. In addition, we will see later that if we apply these two algorithms to the GR method, the difference in favor of LZWM becomes more important.Thus, Table11 gives the comparison of the application of the new method proposed for some MMIMO-OFDM configurations.Table 11
Compression rate of LZW and LZWM algorithms in different MMIMO-OFDM configurations.NBS, NMSk, and No, respectively, stand for the number of antennas at the BS, the number of antennas at each UE, the number of UEs, and the number of OFDM subcarriers.
MMIMO-OFDMM×N×NoFeedback amount without compression in bitsFeedback amount with GR & LZW in bitsCompression rateFeedback amount with GR & LZWM in bitsCompression rate64×4×1285242883566493.20%7373 98.59%64×4×25610485765522494.73%1087898.96%64×4×51220971527861196.25%1581799.24%64×8×12810485769005191.42%2728297.39%64×8×256209715213862893.38%3987098.09%64×8×512419430419728895.29%5889598.59%128×8×256419430429680592.92%5889598.59%128×8×512838860842247594.96%8618298.97%128×8×10241677721664070496.18%12695799.24%In summary, we can say that excessive feedback overload is a major handicap in FDD MMIMO systems. Therefore, this excess downlink feedback must be compressed by sophisticated algorithms. Significant efforts are being made in this direction, and several solutions are proposed. We have proposed two lossless compression solutions based on the GR & LZW compression algorithm and a derivative of the latter: GR & LZWM. These algorithms can be considered evolutions of the Givens rotation method which is adopted in the WLAN standard IEEE 802.11/c. The results of the simulations show that the proposed methods can achieve more than 95% and 98% compression ratios, respectively.


## 5.3.1. Comparison between LZW and LZWM

Table8 gives the LZWM encoding of our previous sequence. So in this example, the gain from the modification is not very visible (we even lose; Table 9). Indeed, the length of the sequence is very reduced; suddenly, there is no jump, i.e., going to 10 bits, 11 bits, and so on.Table 8
Encoding of “MIMOMOSI” by LZWM.
StepsCWCodeDictionaryNumber of coded bits125582MM is known3II77MI is not in the dictionary: we test if 257<29−1 (if this is true, we keep 257; otherwise, we send 29−1=511),and MI is encoded by 51394MM73IM is encoded to 25895OO77MO is encoded to 25996MM79OM is encoded to 26097OMOMO is known98SS259MOS is encoded to 26199II83SI is encoded to 262910II73I is known9The output is 77, 73, 77, 79, 259, 83, and 73Table 9
Number of bits for LZW and LZWM of the code “77, 73, 77, 79, 259, 83, and 73.”
LZWLZWMOutput sequence77, 73, 77, 79, 259, 83,and 7377, 73, 77, 79, 259, 83, and 73Number of bits9+9+9+9+9+9+9=63bits8+9+9+9+9+9+9+9=71bitsHowever, this article is part of a MMIMO context, which means that the sequences that we will be called upon to compress will take very large dimensions. Thus, this gain could become interesting. Moreover, the study allowed us to define the minimum and maximum gains of this method compared to the classical one.To generalize, let us setNd the number of starting bits and Nf the final number of bits. For Nd=8 and Nf=12, we have the following:
(i)
At a minimum, we have29−1−112−9−8 before going to 10 bits. 8 is the number of bits inserted so the flag(ii)
At a minimum, we have210−9−112−10−9 before going to 11 bits(iii)
At least we have211−10−112−11−10 before going to 12 bitsIn general, we will have a gain:(i)
At least we have(26)2Nd−1Nf−Nd−1∑n=Nd+1Nf−12n+1−2n−1−1Nf−n+1−n,which gives
(27)Gmin=∑n=Nd+1Nf−Nd−12n−1Nf−n−1−n(ii)
Likewise, at most(28)Gmax=∑n=Nd+1Nf−Nd−12n+1−1Nf−n−1−nTherefore, let us keep the same previous simulation parameters 1, and we consider the case where we have a single user and a multipath MMIMO channel; the comparison of the two algorithms gives Table10.Table 10
Comparisons between LZW and LZWM.
Number of subcarriers16×161282565121024LZW80.5752%84.7580%89.3175%91.8718%LZWM81.8413%86.1474%90.0122%92.6036%Though Table10 confirms that the modified version of the LZW algorithm has a gain of about 2% compared to the classic version, this percentage gain may seem small, but let us just remember that we are in a MMIMO context, so 2% of the data handled is necessarily significant. In addition, we will see later that if we apply these two algorithms to the GR method, the difference in favor of LZWM becomes more important.Thus, Table11 gives the comparison of the application of the new method proposed for some MMIMO-OFDM configurations.Table 11
Compression rate of LZW and LZWM algorithms in different MMIMO-OFDM configurations.NBS, NMSk, and No, respectively, stand for the number of antennas at the BS, the number of antennas at each UE, the number of UEs, and the number of OFDM subcarriers.
MMIMO-OFDMM×N×NoFeedback amount without compression in bitsFeedback amount with GR & LZW in bitsCompression rateFeedback amount with GR & LZWM in bitsCompression rate64×4×1285242883566493.20%7373 98.59%64×4×25610485765522494.73%1087898.96%64×4×51220971527861196.25%1581799.24%64×8×12810485769005191.42%2728297.39%64×8×256209715213862893.38%3987098.09%64×8×512419430419728895.29%5889598.59%128×8×256419430429680592.92%5889598.59%128×8×512838860842247594.96%8618298.97%128×8×10241677721664070496.18%12695799.24%In summary, we can say that excessive feedback overload is a major handicap in FDD MMIMO systems. Therefore, this excess downlink feedback must be compressed by sophisticated algorithms. Significant efforts are being made in this direction, and several solutions are proposed. We have proposed two lossless compression solutions based on the GR & LZW compression algorithm and a derivative of the latter: GR & LZWM. These algorithms can be considered evolutions of the Givens rotation method which is adopted in the WLAN standard IEEE 802.11/c. The results of the simulations show that the proposed methods can achieve more than 95% and 98% compression ratios, respectively.


## 6. Conclusion

Multiuser MMIMO-OFDM systems operating in the FDD mode are a promising solution to deliver unprecedented spectral efficiency in future wireless communication systems. Several powerful preprocessing and postprocessing techniques are proposed in the literature to both diffuse and eliminate potential multiuser interference.However, since UL and DL CSI are mandatory on each side of the transceiver, MMIMO-OFDM systems in FDD mode require a large amount of feedback from the CSI. Therefore, limited feedback is now an important research topic.In this work, we have proposed three improvements to the conventional Givens rotation feedback compression which is adopted in the IEEE 802.11 standard.The first GR & AC proposal is based on a lossless compression technique, the arithmetic coding. By opting for arithmetic coding with resizing to avoid the overflow problem and to be able to transmit as the compression principle unfolds, the proposed GR & AC algorithm has achieved a compression rate of up to 83%.The second GR & LZW method is based on the LZW compression technique which is also a lossless compression method. With the LZW-based solution, the simulation results show that up to 95% compression ratio can be achieved. Finally, this second proposition has in turn been improved by modifying the coding principle of the LZW algorithm: GR & LZWM (modified). And this proposal brings improvements over the second in terms of compression rates which can reach 98%.All the proposed algorithms brought a feedback reduction gain compared to that of GR used in the IEEE 802.ac standard and presented the same performance in terms of BER if the number of quantization bits became greater than or equal to 8.



---

*Source: 5914855-2022-07-27.xml*