Thomas Marconi
email: t.marconi@tudelft.nl

Christian Spagnol
email: c.spagnol@ue.ucc.ie

Emanuel Popovici
email: e.popovici@ucc.ie

Sorin Cotofana
email: s.d.cotofana@tudelft.nl

Transmission Channel Noise Aware Energy Effective LDPC Decoding

Keywords: LDPC Decoding, Low Energy, Dynamic Voltage Scaling, FPGAs, Communication Systems

In communication systems channel quality variation, mostly induced by interferences, mobility, and environmental factors, is an unhindered physical phenomenon, which is usually perceived as a threat in pursuing reliable communication. There is a direct relation between the channel condition and the amount of computational resources and energy that have to be spend in order to reconstruct the correct messages at the reception side. When the quality is good, the decoding requires less resources and energy to identify and correct channel condition induced message errors, while when the channel noise level is high more resources and energy are needed to correct the errors. To be able to properly handle high noise levels while keeping the QoS requirements satisfied, telecom platforms are built upon largely over-designed hardware, i.e., they rely on worse case designs, which results in a substantial energy waste during most of their operation. In this chapter we introduce a methodology to dynamically adapt the platform operation mode to the channel noise level. The main objective is to keep QoS requirements satisfied regardless of the actual channel conditions while minimizing the energy consumption footprint. In particular, we propose a technique to exploit channel noise variability towards energy effective LDPC decoding amenable to adaptable low-energy operation. Endowed with the instantaneous channel noise level knowledge, our technique dynamically adjusts the operating voltage on-the-fly, aiming to achieve the optimal tradeoff between decoder performance and energy consumption without ignoring the fulfillment of the QoS requirements expressed in terms of frame/bit error rate. To demonstrate the capabilities of our proposal we implemented it and other state of the art energy reduction methods in the framework of a fully parallel LDPC decoder mapped on a Virtex-6 FPGA. Our experiments indicate that the proposed technique outperforms state of the art counterparts, in terms of energy reduction, with 71% to 76% and 15% to 28%, w.r.t. early termination without and with DVS, respectively, while maintaining the targeted decoding robustness. Moreover, the measurements suggest that in certain conditions Degradation Stochastic Resonance occurs, i.e., timing faults caused by unpredictable underpowered components in the circuit unexpectedly become supporters rather than enemies of the decoding process.

Introduction

To communicate messages from senders to recipients channels are indispensable required. In one hand, we need channels to convey our messages. In the other hand, we want to avoid the channels from corrupting our messages. Channel quality variation is an unhindered physical phenomenon which is usually perceived as a threat in pursuing reliable communication. It is well known that channel quality variation may occur in communication systems as a result of, e.g., multi-path, interferences, mobility, and environmental conditions [START_REF] Tse | Fundamentals of wireless communication[END_REF] as illustrated in Figure 1. When the quality is low a large number of errors might occur during the transmission and high performance error correctors are required to recover the original message. However, if the quality is good, the system experiences less errors case in which decoders with lower decoding capabilities are enough to fulfill the Quality of Service (QoS) requirements. Since the systems are designed to meet a target acceptable error rate even in the worst-case scenario, e.g., the highest expected channel noise level, the decoders are over-designed. Thus decoders have excess performance during good channel conditions and as the worst-case, i.e., bad condition, rarely occurs, significant energy consumption is wasted during most of their operation.

In view of this observation, the main question that we are addressing in this work is "Can we adapt the decoder performance to the channel status to prevent energy over-consumption?" We positively answer this question by proposing a technique to trade off performance with energy while fulfilling error rates requirements by exploiting channel noise variability towards energy effective Low Density Parity Check (LDPC) decoding [START_REF] Gallager | Low-density parity-check codes[END_REF]. Decoding at the required performance is the key idea behind our method to diminish energy consumption and we determine the operation conditions resulting in the highest energy savings by actively monitoring the channel noise. More specifically, we diminish the supply voltage value when the channel is in a good condition to save energy and vice versa we increase it when the channel is getting worse for meeting the target error rate. To be able to properly adjust at run time the power supply voltage to the channel status we perform at design time a decoder pre-characterization, i.e., we measure decoder's Frame Error Rate (FER), Bit Error Rate (BER), and energy/bit under voltage scaling on a variety of noisy channels. The main objective is to minimize the energy consumption while preserving the decoder performance in terms of FER and BER. The operating voltage adaptation is done based on the estimated Signal-to-Noise Ratio (SNR) of an Additive White Gaussian Noise (AWGN) channel with Binary Phase Shift Keying (BPSK) modulation.

Although our technique is applicable to any electronic system for which the power supply vs performance relation can be pre-characterized, in this work, we experimentally evaluate it for an LDPC decoder implemented on Field-Programmable Gate Array (FPGA). We utilize as discussion vehicle an LDPC [START_REF] Gallager | Low-density parity-check codes[END_REF] for evaluating our proposed technique are (i) the superiority of its decoding performance, which is very close to the Shannon limit [START_REF] Mackay | Near shannon limit performance of low density parity check codes[END_REF], and (ii) its popularity, being adopted by many communication standards, e.g., WiFi

[4], WiMAX [5], DVB-S2 [6], 10GBase-T [7]. The decoder is automatically generated and the energy consumption is measured directly on the FPGA board by accessing the PMBus through the USB interface adapter. In contrast to [START_REF] Chow | Dynamic voltage scaling for commercial fpgas[END_REF], we adjust the supply voltage value by directly controlling the board internal power supply, thus we do not rely on an external power supply or need to operate board modifications for effective and efficient voltage scaling experiments. We note that we report measured data, gathered from experiments on a Virtex-6 FPGA, and not from theoretical analysis, e.g., density evolution, EXIT charts, or from, e.g., Monte-Carlo simulation.

For comparison purpose we mapped into the FPGA three versions of the considered LDPC decoder as follows: (i) equipped with our technique, (ii) with powering off capability/early termination (ET) technique, e.g., [START_REF] Darabiha | Power reduction techniques for ldpc decoders. Solid-State Circuits[END_REF], operated at nominal supply voltage value, and (iii) with a hybrid scheme combining ET and the Dynamic Voltage Scaling (DVS) techniques in [START_REF] Chow | Dynamic voltage scaling for commercial fpgas[END_REF]. Our experiments indicate that the proposed technique outperforms the other schemes, resulting in 71% to 76% and 15% to 28% energy reduction w.r.t. ET without and with DVS, respectively, while maintaining the required decoding performance. Moreover, we observe that in certain condition Degradation Stochastic Resonance (DSR) [START_REF] Gammaitoni | Stochastic resonance[END_REF][START_REF] Aymerich | Degradation stochastic resonance (dsr) in ad-avg architectures[END_REF] occurs, i.e., timing errors caused by voltage scaling improve the decoding performance, and by implication diminish the energy consumption, due to the fact that unpredictable underpowered components facilitate rather than impede the decoding process.

Many approaches have been proposed to reduce energy consumptions of LDPC decoders. Generally speaking voltage scaling has been frequently applied in Complementary Metal-Oxide-Semiconductor (CMOS) integrated circuits as by reducing the supply voltage we can gain energy efficiency at the expense of a longer circuit delay. However, as timing violation may occur if the circuit delay gets longer than the clock period, existing approaches either avoid this situation by tuning the operating frequency accordingly or correct potential errors by means of additional hardware.

To reduce LDPC decoders energy consumption, Dynamic Voltage Frequency Scaling (DVFS) based on the estimation of the maximum number of iterations was proposed in [START_REF] Wang | Low-power vlsi design of ldpc decoder using dvfs for awgn channels[END_REF] and [START_REF] Zhang | Low-power ldpc decoding based on iteration prediction[END_REF]. In [START_REF] Ahn | Dynamic voltage and frequency scaling scheme for an adaptive ldpc decoder using snr estimation[END_REF] a Signal to Noise Ratio (SNR) estimator is utilized to guide the operating frequency scaling based on the target throughput and channel conditions. Subsequently, assisted by an error detector and a critical path replica, the suitable voltage that ensures no timing violation is determined. In [START_REF] Kim | Energy-efficient ldpc decoders based on error-resiliency[END_REF] Reduced-Precision Replicas (RPR) of the bit and check nodes are utilised to detect and correct voltage scaling induced errors while in [START_REF] Cho | Low-power implementation of a high-throughput ldpc decoder for ieee 802.11n standard[END_REF], Voltage Over-Scaling (VOS) and RPR are combined.

In our proposal, the best operating voltage is chosen based on knowledge of the underpowered LDPC decoder behavior. The operation supply voltage is chosen such that the decoding performance of the decoder operated at the typical voltage, measured in terms of FER/BER, is maintained or a specific target decoding performance is achieved. Similar to [START_REF] Ahn | Dynamic voltage and frequency scaling scheme for an adaptive ldpc decoder using snr estimation[END_REF], we utilize the SNR estimator of existing communication systems but we do not modify the frequency in order to maintain the throughput and we allow for timing violation as long as the target performance is still achievable. We do not make use of additional hardware for error detection/correction or reduced precision replicas thus our approach results in smaller hardware overhead. In [START_REF] Kim | Energy-efficient ldpc decoders based on error-resiliency[END_REF] [START_REF] Cho | Low-power implementation of a high-throughput ldpc decoder for ieee 802.11n standard[END_REF], the supply voltage is fixed at runtime while our method adjusts the supply voltage according to the channel conditions at runtime. Last but not least our technique does not require any decoder modifications hence it can be easily combined with other techniques.

In summary, the main contributions of this work are: (i) A technique for exploiting channel noise variability, (ii) Measured results from FPGA based experiments demonstrating the energy savings capabilities of the proposed method, (iii) A new way to perform voltage scaling on commercial FPGAs without relying on an external power supply, and (iv) Evidence of DSR occurrence in LDPC decoder implementations. This chapter is an extended version of our previous conference paper in [START_REF] Marconi | Towards energy effective ldpc decoding by exploiting channel noise variability[END_REF].

The rest of the chapter is organized as follows. It starts with a short introduction of Sum-Product LDPC Decoding in Section 2. In Section 3, we present the proposed technique in the context of an LDPC decoder and evaluate it in Section 4. In Section 5, we close the discussion with some conclusions.

Sum-Product LDPC Decoding

Before we introduce Sum-Product (SP) LDPC decoding, we start with a brief introduction within the LDPC concept and decoding methodology. Generally speaking, adding parity bits to source information bits, i.e., creating a codeword, is a way to achieve reliable communication through unreliable channels between two parties located at the two channel ends. Each codeword should satisfy a set of pre-determined parity check equations and parties need to send only codewords on the channel. By doing so, the receiving party gets the means to check if the received message is right and if this is not the case to apply error corrective changes. For example, [BN 1 BN 2 BN 3 BN 4 BN 5 BN 6] = [101110] is a codeword that satisfies the following set of pre-determined parity check equations:

BN 1 ⊕ BN 2 ⊕ BN 4 = 0 (1) BN 2 ⊕ BN 3 ⊕ BN 5 = 0 (2) BN 1 ⊕ BN 5 ⊕ BN 6 = 0 (3)
BN 3 ⊕ BN 4 ⊕ BN 6 = 0 (4)
These parity check equations, taken from [START_REF] Johnson | Introducing low-density parity-check codes[END_REF], can be written as a parity check matrix H presented in Figure 2(a). Each row and each column of the H matrix represent a parity check equation and a codeword bit, respectively. This H matrix corresponds to a Tanner graph [START_REF] Tanner | A recursive approach to low complexity codes[END_REF] visualized in Figure 2(b), which describes an iterative decoding process. The Tanner graph in Figure 2(b) consists of two sets of vertices: 6 bottom vertices for visualizing 6 Bit Nodes (BNs) and 4 top vertices for visualizing 4 Check Nodes (CNs). Bit node n is connected to check node m if the element of column n row m of the parity-check matrix H is '1'. We use this figure to introduce general idea of decoding and SP LDPC decoding as a particular example. Now, we start with general idea of decoding. Let say we sent a message [BN 1 BN 2 BN 3 BN 4 BN 5 BN 6] = [101110] from the Moon to the Earth using the code in Figure 2. When it reaches the Earth, due to the noisy channel BN 4 flips from '1' to '0', the received message becomes

[BN 1 BN 2 BN 3 BN 4 BN 5 BN 6] = [101010].
Since the incoming message is not a codeword, the receiving decoder knows that this message is not the message transmitted by the sender. Subsequently the decoder tries to correct the error, e.g., comparing the received message with the closest valid codeword. In this case, the closest codeword is [101110] at a Hamming distance 1 away from the received message [101010]. The identification of the closest codeword is guided by the parity check equations which we can perceive as an agreement between two parties to conduct reliable communications. If the agreement is violated, it means that something went wrong during the transmission on the unreliable noisy channel and corrective actions are required. To get more insight into the decoding process we assume as a discussion vehicle the Sum-Product (SP) LDPC decoder which is a soft decision decoder based on the message-passing algorithm, as visualized in Figure 2(b). In soft decision decoding, each received bit x is represented as P (x = 1), i.e., the probability that x is logic '1'. The probability is expressed as a Log-Likelihood Ratio (LLR) in SP decoding to reduce the implementation complexity by turning multiplications into additions. LLR of x is defined as:

H= 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 CN 1 CN 2 CN 3 CN 4 BN 1 BN 2 BN 3 BN 4 BN 5 BN 6 (a) Parity Check Matrix H CN 1 CN 2 CN 3 CN 4 BN 1 BN 2 BN 3 BN 4 BN 5 BN 6 LLR CN 1 BN 1 LLR CN 3 BN 1 LLR BN 4 CN 1 LLR BN 2 CN 1 LLR BN 6 CN 3 LLR BN 5 CN 3 LLR BN 1 CN 1 LLR BN 1 CN 3 (b)
LLR x = log e P (x = 0) P (x = 1) (5)
LLR IN BNn stands for a message received from channel in form of the LLR of the bit node n. Messages are iteratively passing by between Bit Nodes (BNs) and Check Nodes (CNs) along the edges of the Tanner graph as illustrated in Figure 2(b). A message from a bit node n to a check node m in LLR form is written as LLR BNnCNm . In the opposite direction, a message from a check node m to a bit node n in LLR form is denoted as LLR CNmBNn . Each output decoding in LLR form for a bit node n, expressed as LLR OU T BNn , is utilized for (i) making hard decision at the end of each iteration for decoders with early termination and (ii) the determination of the final output at the end of the decoding process.

Let us focus our attention to CN 1 in Figure 2(b). Given that BN 2 CN 1 ⊕ BN 4 CN 1 = 0 is true if both BN 2 CN 1 and BN 4 CN 1 have the same value either '0' or '1', the probability of (BN 2 CN 1 ⊕ BN 4 CN 1 = 0) can be computed as:

P (BN 2 CN 1 ⊕ BN 4 CN 1 = 0) = P (BN 2 CN 1 = 0)P (BN 4 CN 1 = 0) + P (BN 2 CN 1 = 1)P (BN 4 CN 1 = 1) (6)
Since P (x = 0) = 1 -P (x = 1), Equation (6) becomes:

P (BN 2 CN 1 ⊕ BN 4 CN 1 = 0) = 1 2 + 1 2 {[1 -2P (BN 2 CN 1 = 1)][1 -2P (BN 4 CN 1 = 1)]} (7)
and:

P (BN 2 CN 1 ⊕ BN 4 CN 1 = 1) = 1 2 -1 2 {[1 -2P (BN 2 CN 1 = 1)][1 -2P (BN 4 CN 1 = 1)]} (8)
By dividing Equation (7) by Equation ( 8), we obtain:

P (BN 2 CN 1 ⊕BN 4 CN 1 =0) P (BN 2 CN 1 ⊕BN 4 CN 1 =1) = 1 2 + 1 2 {[1-2P (BN 2 CN 1 =1)][1-2P (BN 4 CN 1 =1)]} 1 2 -1 2 {[1-2P (BN 2 CN 1 =1)][1-2P (BN 4 CN 1 =1)]} (9)
and by multiplying the numerator and the denominator of Equation ( 9) by 2, we get:

P (BN 2 CN 1 ⊕BN 4 CN 1 =0) P (BN 2 CN 1 ⊕BN 4 CN 1 =1) = 1+{[1-2P (BN 2 CN 1 =1)][1-2P (BN 4 CN 1 =1)]} 1-{[1-2P (BN 2 CN 1 =1)][1-2P (BN 4 CN 1 =1)]} (10)
To satisfy check node 1, we need to submit to Equation (1):

LLR CN 1 BN 1 = log e P (BN 2 CN 1 ⊕BN 4 CN 1 =0) P (BN 2 CN 1 ⊕BN 4 CN 1 =1) (11)
By substituting Equation [START_REF] Gammaitoni | Stochastic resonance[END_REF] to Equation [START_REF] Aymerich | Degradation stochastic resonance (dsr) in ad-avg architectures[END_REF] we obtain:

LLR CN 1 BN 1 = log e 1+{[1-2P (BN 2 CN 1 =1)][1-2P (BN 4 CN 1 =1)]} 1-{[1-2P (BN 2 CN 1 =1)][1-2P (BN 4 CN 1 =1)]} (12)
and since log e 1+x 1-x = 2tanh -1 (x), Equation ( 12) becomes: 13) is transformed into:

LLR CN1BN1 = 2tanh -1 {[1 -2P (BN 2 CN 1 = 1)][1 -2P (BN 4 CN 1 = 1)]} (13) Since tanh 1 2 log e 1-x x = 1 -2x, thus Equation (
LLR CN1BN1 = 2tanh -1 tanh 1 2 log e 1-P (BN2CN1=1) P (BN2CN1=1) tanh 1 2 log e 1-P (BN4CN1=1) P (BN4CN1=1) (14)
Given the LLR definition in Equation (5), Equation ( 14) becomes:

LLR CN 1 BN 1 = 2tanh -1 tanh LLR BN 2 CN 1 2 tanh LLR BN 4 CN 1 2 (15)
By separating signs and magnitudes of LLR BN2CN1 and LLR BN4CN1 , Equation ( 15) can be written as:

LLR CN1BN1 = 2tanh -1 tanh sign(LLRBN 2 CN 1 )|LLRBN 2 CN 1 | 2 tanh sign(LLRBN 4 CN 1 )|LLRBN 4 CN 1 | 2 (16
) Separating sign and magnitude of LLR CN1BN1 in Equation ( 16) results: sign(LLR CN1BN1 ) = sign(LLR BN2CN1 )sign(LLR BN4CN1 ) [START_REF] Marconi | Towards energy effective ldpc decoding by exploiting channel noise variability[END_REF] and:

|LLR CN1BN1 | = 2tanh -1 tanh |(LLRBN 2 CN 1 )| 2 tanh |(LLRBN 4 CN 1 )| 2 (18)
Since log e (xy) = log e (x) + log e (y), therefore Equation ( 18) also can be restructured into:

|LLR CN1BN1 | = 2tanh -1 log -1 log tanh |(LLRBN 2 CN 1 )| 2 + log tanh |(LLRBN 4 CN 1 )| 2 (19) Let us define φ(x) as: φ(x) = -log[tanh(x/2)] = log e x + 1 e x -1 (20)
If we find the inverse of φ(x) through very simple mathematics, we get:

φ -1 (x) = log e x + 1 e x -1 = φ(x) (21)
Using the definition of φ(x), Equation ( 19) becomes:

|LLR CN1BN1 | = 2 tanh -1 log -1 {-[φ(|LLR BN2CN1 |) + φ(|LLR BN4CN1 |)]} (22)
If we find the inverse of Equation (20) through very simple mathematics, we obtain:

φ -1 (x) = 2 tan -1 log -1 (-x) (23)
Substitute Equation (23) to Equation (22):

|LLR CN 1 BN 1 | = φ -1 [φ(|LLR BN 2 CN 1 |) + φ(|LLR BN 4 CN 1 |)] (24)
Using φ -1 (x) = φ(x) in Equation ( 21), Equation ( 24) is transformed into:

|LLR CN 1 BN 1 | = φ[φ(|LLR BN 2 CN 1 |) + φ(|LLR BN 4 CN 1 |)] (25)
By doing the same computation for CN 3 , we get:

|LLR CN 3 BN 1 | = φ[φ(|LLR BN 5 CN 3 |) + φ(|LLR BN 6 CN 3 |)] (26)
and:

sign(LLR CN 3 BN 1 ) = sign(LLR BN 5 CN 3 )sign(LLR BN 6 CN 3 ) (27)
Using LLR CN1BN1 and LLR CN3BN1 , we can compute LLR BN1CN1 , LLR BN1CN3 , and LLR OU T BN1 as:

LLR BN1CN1 = LLR IN BN1 + LLR CN3BN1 (28)
,

LLR BN1CN3 = LLR IN BN1 + LLR CN1BN1 (29)
, and:

LLR OU T BN 1 = LLR IN BN 1 + LLR CN 1 BN 1 + LLR CN 3 BN 1 (30)
This LLR OU T BN1 is used for making a hard decision for bit 1 using this equation:

BN OU T 1 = 0, if LLR OU T BN1 is positive 1, if LLR OU T BN1 is negative (31)
This hard value BN OU T 1 is used with other bits for parity check to determine whether the vector [BN OU T

1 BN OU T 2 BN OU T 3 BN OU T 4 BN OU T 5 BN OU T 6
] is a codeword or not using Equation (1) to Equation (4). If the vector is a valid codeword, the decoder with early termination stops decoding and then sends this vector as the final output of decoding. LLR BN1CN1 and LLR BN1CN3 are used for next iteration using the same computation of bit 1. In the previous derivations we concentrated on the calculation of bit 1, computation of all the other bits can be done in the same way. The computation is stopped either when the decoder finds a codeword (for decoder with early termination) or the decoder gives up, i.e., the decoder could not find the codeword after a pre-defined maximum number of iterations.

Proposed Technique

The main concept behind the proposed technique is presented in Figure 3. Maintaining the decoding performance (in terms of FER/BER) to its required value by actively monitoring the channel noise is the key idea to prevent energy overconsumption. More precisely, we turn the supply voltage up when the channel is getting worse for meeting the target error rate and vice versa we turn it down when the channel is in a good condition to save energy. The question is "How far can we turn the supply voltage down in good channel conditions or up in bad channel conditions?" If we increase the voltage too much when the channel is getting worse, we may spill energy, while if the voltage is not big enough, the target error rate cannot be satisfied. Similar situations may also occur when turning down the voltage in good channel conditions. To determine the appropriate decoder operating voltage at a specific channel condition, we need to know the decoder behavior by means of a pre-characterization process as detailed in

Pre-characterization

It is clear that the decoder has to be aware of the channel condition for taking the best runtime decisions. Another important information the decoder needs to have is its own behavior when operating at different supply voltages and for various channel conditions in terms of performance/correction capability and energy efficiency. For this reason, in order to equip the decoder with the required knowledge, we need to make real measured data known to the decoder. Thus, during pre-characterization, we need to measure decoder FER, BER, and energy/bit on a variety of noisy channels and voltage conditions. There are 3 steps to do pre-characterization: (1) generation, (2) setup, and (3) run as depicted in Figures 4,5, and 6, respectively. Generation (see Figure 4) is the process of creating the decoder for precharacterization. The decoder VHDL code is produced by a tool designed for the automatic generation of LDPC decoder fully parallel IP cores starting from an H matrix, regular or irregular, and the number of bits to represent the channel message. The presented results are obtained using a MacKay A matrix [START_REF] Mackay | Near shannon limit performance of low density parity check codes[END_REF] with dimensions n=1000, k=500, and 4-bit 2's complement fixed point number representation of the message. Each fixed point number consists of 1 sign bit, 2 integer bits, and 1 fractional bit. The implemented decoder is based on Log Likelihood Ratio (LLR) Belief Propagation (BP) or the sum-product algorithm [START_REF] Gallager | Low-density parity-check codes[END_REF]. The parallel implementation consists in a one to one mapping of the bit and check nodes in the Tanner graph to the respective bit and check modules. The edges in the graph become physical buses of width equal to the chosen precision. In a fully parallel implementation the number and complexity of the interconnections may result in implementations where the area is dominated by the routing. However it is highly efficient from a power and speed point of view. For these reasons and given the high density and connection capability of modern FPGA chip, a fully parallel architecture has been chosen as the testcase for the research presented here. The maximum number of iterations is set at 100. Two clock cycles are needed for each iteration. LLRs represented by two's complement fixed point numbers are the inputs to the CN while its outputs are represented as Sign Magnitude (SM) numbers. The Check Node (CN) converts each 2's Complement (2C) number to a Sign Magnitude (SM) number using its 2C-SM converter. The absolute value of this SM number is then computed by ABS. This absolute value is further processed to obtain its φ(x) = -log(tanh(x/2)) = log( e x +1 e x -1 ) function.

The function φ is even and has the property that φ -1 (x) = φ(x) for x > 0.

In this work, each φ or φ -1 function is approximated by a 4-bit Look-Up Table (LUT) denoted as phiLUT or invphiLUT in the figure. This choice allows to take advantage of the structure of FPGA slices and the free availability of LUTs. To ease automatic hardware generation in a parametric way, all related φ(x) values are added (using ADD). The output of ADD is then subtracted (using SUB) by each specific φ(x) value. The subtraction result is then fed to φ -1 (x) function to obtain the magnitude bits as part of sign magnitude representation at the output of CN. In similar way like processing absolute value, each sign bit is processed separately using XOR. The input(output) of BN is represented as sign magnitude number(2's complement number). Each SM number at the input is converted to 2's complement number (denoted as SM-2C) and then sign extended (presented as SE) by N +2 2 before being processed further, where N is the number of connected CNs. The same reason like CN for making an easy automation of hardware generation, all related input values of each Bit Node (BN) are added (using ADD) and then subtracted (using SUB) by each specific output value of the SM-2C-SE. Since the result can be a number that cannot be represented by the number of bits of representation, we need to process it further by taking its saturated value using SAT operation.

Setup is the process of building the experimental platform in Figure 5. A PC is used for synthesizing the hardware platform targeting Xilinx Virtex-6 FPGA: XC6VLX240T-1FFG1156 using Xilinx CAD tools version 13.4. The PC is also used for downloading the bitstream file to the Xilinx ML605 board through the USB JTAG interface and for monitoring/capturing the number of iterations, FER, and BER through the USB UART. The energy/bit is obtained using the Fusion Digital Power Designer from Texas Instrument running on the Laptop through Texas Instrument USB Interface adapter by reading PMBus, accessing Power Supply Monitor and Controller inside the board. This technique allows for separately controlling and monitoring each on-board specific internal power supply. The measurements are done only for the internal circuits of the FPGA. The supply voltage is adjusted by directly controlling the internal power supply of the FPGA of the targeted board, keeping other supply voltages unchanged. In contrast to [START_REF] Chow | Dynamic voltage scaling for commercial fpgas[END_REF], no additional external power supply is needed. To simulate realistic scenarios we use an AWGN channel with BPSK modulation (with mapping 0 → 1 and 1 → -1) for our experiments. The generated input vectors are fed to the decoder by the MicroBlaze processor resident on the FPGA. BRAM is used to store software and data for Microblaze execution.

Run is the process of running the decoder on the experimental platform for pre-characterization purpose as depicted in Figure 6. This functionality is mainly operated by LDPC Monitoring and Controller (MC). The MC monitors the condition of decoding, feeds LLRs to the decoder, and computes BER. The Maximum Iteration Register (MIR) stores the maximum number of iterations allowed for decoding. This register is initialized by the MicroBlaze. If the decoder reaches the maximum number of iterations without reaching a valid code word, i.e., correcting the errors, MC goes to "Give Up" state. Soft messages in form LLRs are fed by MC to the LDPC decoder through the register Decoder Input (DI). This register can be accessed by the MicroBlaze through the PLB bus. The Decoder Golden Frame (DGF) is the original frame sent by the transmitter and conveyed by the MicroBlaze to the MC for evaluating purposes. By comparing this frame with the Decoder Output Frame (DOF), the controller determines the decoding success rate for computing FER and BER. The computed BER is stored in the BER Counter (BC) and can be accessed by the MicroBlaze. The Status Register (SR) indicates the decoder status and it is accessible by the MicroBlaze. The possible states are: (1) successful decoding denoted as "OK" state, (2) giving up decoding stored as "Give Up" state, or (3) wrong result decoding written as "Wrong Result" state means that the decoder can satisfy all check nodes but it is not the right frame as it was sent by the LDPC encoder. This can happen if the severity of noisy channel alters the frame to another valid codeword, which is considered as an error. The MC enters "Compute BER" state and starts to compute BER when errors occur.

Based on Post-PAR Static Timing Report of Xilinx tools, the minimum clock period is 19.992 ns (i.e., the maximum frequency is 50.020 MHz). The actual implementation is clocked at 50 MHz. Therefore, the throughput at its maximum iterations is 250 Mbps for all experiments. The complete experimental platform including the decoder requires 31433 FFs, 117231 LUTs, and 16 BRAMs whereas the decoder itself needs 29281 FFs and 114968 LUTs. The pre-characterization results of average number of iterations, FER, BER, and Energy/bit (nJ/bit) when varying the power supply value from 1V to 0.67V and the channel SNR from 10dB to 1dB are presented in Figures 7 to 10, respectively. Each SNR has its own minimum supply voltage after which the number of iterations starts to increase sharply as one can observe in Figure 7. In general, the increase starts earlier for lower SNR channels and this behavior can be related to the fact that the decoder can do self-correction easier for higher SNR channels where there is not much noise involved. Each SNR has its own specific minimum supply voltage after which its number of iterations goes to the maximum number of iterations which is 100. For the majority of the results it can be seen that when the supply voltage is lowered, the number of iterations stays constant for a while and then increases for the decoder to tackle timing errors. It is unexpected but interesting to note that sometimes, the average number of iterations decreases even if the supply voltage is reduced, which suggests that sometimes the timing errors can help the decoder converging to the correct codeword. This phenomenon is called Degradation Stochastic Resonance (DSR) [START_REF] Aymerich | Degradation stochastic resonance (dsr) in ad-avg architectures[END_REF] or Stochastic Resonance (SR) [START_REF] Gammaitoni | Stochastic resonance[END_REF] and it can be also observed in Figures 8 and9 where we present the measured results for FER and BER, respectively. This suggests that voltage reduction can sometimes help improving the decoder performance. Finally, in Figure 10, the measured energy/bit for various SNRs is presented. This figure shows the effect of the law of diminishing returns. The energy/bit decreases by scaling the voltage, however, after a certain point, an increase in energy/bit is visible. This is due to the effect of increasing of number of iterations that diminishes the energy gain we get from reducing the voltage.

Adaptation

The voltage scaling controller for the targeted LDPC decoder depicted in Figure 11 operates as follows. It gets SNR information from the SNR estimator and changes the operating supply voltage at runtime based on the knowledge it has from the measured information gathered during the pre-characterization stage. We note that given that in communication systems with adaptive coding and modulation, the SNR estimator is a standard system component. The basic principle of the adaptation is to trade off over-needed performance for energy saving through active channel quality monitoring. More precisely, we turn down the supply voltage when the channel is in good condition, hence allowing energy saving. However, for preserving target performance, it is required to turn the voltage up when the channel SNR is getting worse. The objective is to minimize the energy not the voltage while ensuring the decoder achieves its needed performance. Note that minimizing the voltage may not always improve the energy efficiency, because the number of iterations of the decoder may increase due to induced timing errors. Thus, this diminishing returns effect needs to be considered when choosing the operating voltage. We developed two different adaptation strategies as follows: (i) the conservative approach which guaranties that the original decoder performance is always preserved and (ii) the aggressive approach which only concentrates on achieving the required target performance. To maintain identical performance while ensuring higher energy efficiency for the channel condition characterized by SN R n , the operating voltage V n is moved towards the point where the energy/bit is minimized and at the same time the FER and BER remain identical to those of the decoder operated at the typical voltage V T ypical . By its conservative nature this approach may still sometimes result in energy waste as it tries to mimic the worse case designed decoder and not to just fulfill the target performance requirements. In view of this the aggressive strategy is designed to enable the decoder to adapt itself such that it delivers the required correction capability while minimizing the energy consumption.

To discuss how the Voltage Scaling Controller (VSC) determines the operating voltage of the decoder formally, some definitions are introduced as follows. Based on these definitions, the conservative approach required operating voltage at signal-to-noise ratio SN R n denoted as V c n (SN R n ) can be computed as For example, using the above equations, the conservative approach can operate the decoder at V c n = 0.75V preserving the performance (i.e., FER=0.498 and BER=0.041) of the original LDPC decoder operated at V T ypical = 1V. In this situation much less energy is consumed (i.e., 71% of energy saving) as illustrated in Figure 12. According to the aggressive scaling we adjust the power supply value to V a n = 0.71V while maintaining FER ≤ F ER T arget (i.e., FER=0.0166), reducing the energy by 74% as illustrated in Figure 13. Note that to minimize the adaptation process energy overhead all of these computations are performed at design time and their results are placed in an LUT mapping SN R n to V n .

V Energy/bit max V F ER T ypical min ,V BER
To sum up, although our conservative approach runs at lower supply voltage for saving energy, it insures of having an identical decoding quality like the one operated at standard voltage thanks to its endowed knowledge during design time and its smart adaptation at runtime. Awareness of its target performance is the added value of our aggressive approach to surpass the conservative one in terms of energy efficiency at the cost of performance degradation while still satisfying the required error rate.

Evaluation

To evaluate our technique, we utilize the platform and LDPC decoder as in the pre-characterization stage augmented with the following energy reduction schemes: (i) powering off capability using Early Termination (ET) technique operated at the original supply voltage as presented in [START_REF] Darabiha | Power reduction techniques for ldpc decoders. Solid-State Circuits[END_REF], (ii) a Hybrid Early Termination Scheme (HS) which includes the DVS technique in [START_REF] Chow | Dynamic voltage scaling for commercial fpgas[END_REF], (iii) our Conservative Approach (CON), (iv) our Aggressive Approach targeting FER (AGF), and (v) our Aggressive Approach targeting BER (AGB). We evaluated the energy consumption of all the approaches when changing the channel SNR from 2dB to 10dB and the results are plotted in Figure 14. The energy/bit is obtained by accessing Power Supply Monitor and Controller inside the ML605 board through PMBus. Because AGF and AGB result in identical energy consumptions their plots are overlapped in the figure .  One can observe in Figure 14 that: (i) Regardless of SNR value ET always consumes more energy than the other approaches and this can be explained by the fact that it has no capability to adapt to channel conditions. Energy consumed by ET decreases when the channel quality is getting better due to its early termination capability. At good channel quality, number of flipped bits decreases. Fewer flipped bits make decoding faster to converge and as a result, ET turns it power off earlier, reducing the consumed energy. (ii) Our technique always outperforms both ET and HS. However at low SNRs (2 to 3 dB) the energy reduction is limited (only 10-15% and 15-23% reductions over HS, for CON and AGF/AGB, respectively) by the fact that there is not that much excess performance to exploit. However, for less noisier channels, i.e., SNRs from 3 to 10 dB, more excess performance is available and CON achieves a 22-28% energy reduction over HS thanks to its adaptability to exploit channel noise variability; (iii) Because of its additional DVS technique, HS consumes 66% less energy than ET. CON (AGF/AGB) consumes around 71% (73%) and 76% (76%) less energy than ET, for bad and good channel quality, respectively; and (iv) At high SNR values CON, AGF, and AGB consume almost the same energy due to diminishing returns effect, while at low SNR values both AGF and AGB provide 15% energy reduction over CON.

We note that given that our technique does not alter the operating frequency it results in a better performance in terms of decoding throughput when compared to other decoders utilizing dynamic frequency scaling technique.

Conclusions

In this chapter, a technique towards energy effective LDPC decoding by exploiting channel noise variability to transform excess performance for energy saving was proposed. The proposed technique adaptively tunes the operating voltage on-the-fly based on the knowledge of the instantaneous channel noise level at runtime by utilizing its pre-characterization results, aiming to achieve the optimal tradeoff between decoder performance and power consumption, while fulfilling the QoS requirements. To demonstrate the capabilities of our proposal we implemented it and other state of the art energy reduction methods in the framework of a fully parallel LDPC decoder on a Virtex-6 FPGA. Based on the experimental results, when applied to a Sum-Product LDPC decoder our conservative approach improves energy efficiency by 71% to 76% and 15% to 28% compared to early termination without and with DVS, respectively, while preserving the decoder performance in terms of bit/frame error rate. With respect to the conservative version, our aggressive approach meets a given target error rate with up to 15% additional energy reduction thanks to its robustness-on-demand capability. In addition, since our technique maintains the operating frequency regardless of the utilized power supply voltage value, the frame throughput is preserved. Moreover, the FPGA-based experiments suggest that in certain conditions Degradation Stochastic Resonance occurs, i.e., the energy consumption is unexpectedly diminished due to the fact that unpredictable underpowered components facilitate rather than impede the decoding process.

Fig. 2 :

 2 Fig. 2: An Example of Parity Check Matrix (a) and its Tanner Graph Representation (b)

Subsection 3 . 1 .Fig. 3 :

 313 Fig. 3: Transmission Channel Noise Aware Energy Effective Decoding

Fig. 6 :

 6 Fig. 4: Step 1 of Pre-characterization: Generation

Fig. 9 :

 9 Fig. 7: Pre-characterization Results: Number of Iterations

Fig. 10 :

 10 Fig. 10: Pre-characterization Results: Energy/bit (nJ/bit)

Fig. 11 :

 11 Fig. 11: Hardware Design of Adaptation

Fig. 12 :Fig. 13 :

 1213 Fig. 12: An Example Result of Conservative Approach

Definition 1 :

 1 F ER T ypical (BER T ypical ) is the FER (BER) corresponding to the supply voltage V T ypical . Definition 2: V F ER T ypical min V BER T ypical min is the minimum supply voltage for which FER ≤ F ER T ypical (BER ≤ BER T ypical ) is satisfied. Definition 3: V F ERT arget min V BERT arget min is the minimum supply voltage for which FER ≤ F ER T arget (BER ≤ BER T arget ) holds true. Definition 4: V (Energy/bit(x,y)) best is the voltage corresponding to the minimum energy/bit value within the voltage range [x, y], x < y.

.

  Similarly the aggressive approach operating voltage targeting F ER T arget or BER T arget at signal-to-noise ratio SN R n denoted as V aF ER n (SN R n ) and V aBER n (SN R n ) can be calculated as V

  Fig. 14: Experimental Results

Acknowledgment

This work was supported by the Seventh Framework Programme of the European Union, under the Grant Agreement number 309129 (i-RISC project).


Salah Eddine Hajri

Student IEEE Mohamad Assaad
email: mohamad.assaad@centralesupelec.frcaire@tu-berlin.de

Senior IEEE Giuseppe Caire

Scheduling in Massive MIMO: User Clustering and Pilot Assignment

In this paper, we consider the problem of user scheduling and pilot assignment in TDD multicell multiuser Massive MIMO systems. While in TDD systems the channel is acquired using uplink pilots, we propose a scheme that utilizes additional downlink probing in order to improve the spectral efficiency. The idea is to dynamically assign mobile users to different clusters based on the directions of their channels through the use of downlink reference beams. This will result in forcing the interference to be centered in semiorthogonal subspaces without the need for important feedback and therefore enabling reduction of the pilot contamination effect. The scheduled users in each cluster employs orthogonal training sequences with a pilot reuse factor of 1 among the clusters. We then propose a graphical framework for pilot assignment. We show that this problem can be modeled as a max cut problem and we provide an approximation algorithm that optimizes the pilot allocation.

I. INTRODUCTION

Multiuser MIMO is one of the main technologies that has been adopted for wireless networks. It enables serving users in the same frequency band and time, exploiting the degrees of freedom in the spatial domain. Coupled with a large antenna array at the Base Station, this system enables a huge increase in the network spectral and energy efficiency. Massive MIMO was first proposed in [START_REF] Marzetta | Noncooperative cellular wireless with unlimited numbers of base station antennas[END_REF]. The idea was to mimics spreadspectrum used in 3G networks in which a large processing gain can be realized by massive use of radio spectrum. This gain is imitated through the use of a large number of antennas. Massive MIMO systems were intensively investigated and shown to have a huge potential in improving the spectral and energy efficiency of wireless networks. In [START_REF] Marzetta | Noncooperative cellular wireless with unlimited numbers of base station antennas[END_REF], the author showed that Massive MIMO systems require channel state information in order to enable simple linear beamforming. It was shown that the spectral efficiency of the massive MIMO system is limited by the CSI imperfection due to pilot contamination. With massive MIMO, the impact of uncorrelated receiver noise, fast fading and interference is decreasing as the number of antennas increases. Usually, when using pilot aided channel estimation, a limiting factor arises since we are required to reuse the same orthogonal pilot sequences in neighboring

The research of M. Assaad has been partially funded by Huawei, France and "Fondation Supelec" cells. This results in pilot contamination. This phenomenon was heavily investigated and many works proposed different methods to deal with it. In [START_REF] Yin | A Coordinated Approach to Channel Estimation in Large-Scale Multiple-Antenna Systems[END_REF], the authors proposed a Coordinated Approach to Channel Estimation, in which exploitation of covariance information under certain conditions on the covariance matrices can lead to a complete removal of pilot contamination effects in the large antenna limit. In [START_REF] Nam | Joint Spatial Division and Multiplexing: Opportunistic Beamforming, User Grouping and Simplified Downlink Scheduling[END_REF], Joint Spatial Division and Multiplexing (JSDM) for multiuser MIMO downlink was investigated. JSDM is a scheme that aims to serve users by clustering them into groups such that users within a group have approximately similar channel covariances, while users across groups have near orthogonal covariances. In [START_REF] Lee | A New Approach to User Scheduling in Massive Multi-user MIMO Broadcast Channels[END_REF], a two-stage beamforming method for massive MIMO broadcast channel in FDD mode was proposed.

The key ideas was to use a set of reference beams in order to select semi-orthogonal users and then apply zero-forcing beamforming using the CSI feedback from the selected users. In our paper, we revisit user scheduling for Massive MIMO, based on the channel covariance informations. We consider an a scheduling method where users are grouped according to their channel directions. We concentrate on time division duplexing (TDD) systems, in which channel reciprocity can be used to get estimates of the downlink channels through uplink training, thereby eliminating the need for feedback. This has the important advantage of enabling the usage of the full bandwidth efficiently for data transmission compared with the FDD case where a portion of the available bandwidth is reserved for feedback. We consider a multicell system and we aim at reducing the pilot contamination effect, resulting in an improved spectral efficiency. The proposed scheme consists of using random beamforming [START_REF] Sharif | On the capacity of MIMO broadcast channels with partial side information[END_REF] for downlink probing in TDD mode. This enables to schedule users in different clusters according to their channel directions. The proposed scheme allows to reduce the feedback to the index of the subspace on which users' channel is concentrated. The users in each cluster will then employ orthogonal training sequences in the uplink and the same set of pilots are reused in all clusters within a given cell. This allows more aggressive pilot reuse. While this scheme allows improvement in the spectral efficiency, it cannot remove completely the interference due to the semi orthogonality and limited dimensionality. In the second part of the paper, we propose a intelligent pilot assignment framework that reduces the remaining interference. We show that pilot assignment can be modeled as a max cut problem. We then propose an approximation algorithm, that optimizes the pilot allocation based only on the large scale fading coefficients. Notations: The notations A † , A and T r {A} are used for transpose, Euclidean norm and trace, respectively. We use CN 0, σ 2 for a circular symmetric complex Gaussian distribution a with zero mean and variance σ 2 .

II. SYSTEM MODEL AND PRELIMINARIES

We consider a two-dimensional cellular network composed of C hexagonal cells with one base station and K single omnidirectional antenna users in each cell. Each base station is equipped with M antennas . An example of the cells layout is given in FIGURE 1. We consider the case of frequency reuse factor of one where the same bandwidth is reused in all cells. The wireless channel from the i th user in the b th cell to the j th BS is given by: g

[j] ib = β [j] ib h [j]
ib . We assume that each channel coefficient can be decomposed as a product of the large-scale fading coefficient and the small-scale fading coefficient. The small-scale fading coefficients h

[jn] ib are modeled as Rayleigh fading, i.e., an i.i.d CN (0, 1) distributed random variables. The large-scale fading (LSF) coefficient β

[j]

ib ∈ R + depends on the distance between the user and BS and the shadowing. Typically, the distance between BS and a user is significantly larger than the distance between antennas, then the large-scale fading coefficient is the same for all the BS antennas. We suppose that the large-scale fading coefficient vary slower than small-scale fading coefficients which is particularly true when mobile users have low speed. We assume the block fading model for the small-scale fading coefficients, meaning they stay constant during small-scale coherent interval of T symbols. We consider Time-Division Duplexing (TDD) mode where the entire frequency band is used for downlink and uplink transmissions by all base stations and all users. In this paper we concentrate on the uplink. Channel state information estimation is performed using orthonormal training sequences where in each cell the same set of τ training sequences q i ∈ C τ ×1 (q † i q j = δ ij ) is used with reuse factor of 1.

Fig. 1: Network Model III. GROUP BASED USER SCHEDULING In this section, we propose a user scheduling method that exploits the directions of user's channel [START_REF] Lee | A New Approach to User Scheduling in Massive Multi-user MIMO Broadcast Channels[END_REF] [2] without the need for substantial feedback. We first provide a general introduction to the proposed scheduling scheme and then, in the next subsection, we describe the scheduling algorithm in more details. As in [3][7], the key idea is to partition users into multiple groups so that each group has a distinguishable linear subspace. While in [3][7], the subspaces are defined by the dominant eigenvectors of the groups channel covariance matrix, we concentrate in this work on multiuser diversity and the users are grouped according to their channel directions. The grouping method used in this paper has the advantage to not require the estimation of user channel covariance matrix which may be cumbersome and quite complex especially in massive MIMO systems The clusters will be computed in each cell such that the signal of users in different clusters are centered in orthogonal subspaces. This enable us to effectively mitigate the pilot contamination effect and even reusing the same pilot sequence more than once in a given cell. Scheduling users based on the dominant sub-spaces of their signal, can reduce the mutual interference. The Key idea is to limit pilot contamination which is responsible for the persistent interference in the large antenna array regime. This will be done by allocating the same pilot sequence only to users in different clusters [START_REF] Nam | On the Role of Transmit Correlation Diversity in Multiuser MIMO Systems[END_REF]. In order to exploit having multiple antennas at the BS without having full CSI, we propose a scheme in which the BS constructs random beams which will be used as downlink probes. The set of M random beams φ = {φ 1 , φ 2 , ...φ M } with φ i a random orthonormal vector ∈ C M ×1 is generated according to an isotropic distribution. Using this property we restrain the scheduled users to those having a predefined dominant subspace based on d vectors of the set of the reference beams, where d is the number of beams that are associated with each cluster. Using downlink probing simplifies the clustering procedure. While random beamforming has been already used in the literature [START_REF] Sharif | On the capacity of MIMO broadcast channels with partial side information[END_REF], [START_REF] Lee | A New Approach to User Scheduling in Massive Multi-user MIMO Broadcast Channels[END_REF] for FDD systems with CSI feedback, we apply it here for downlink probing in TDD mode with uplink training. This enables a more dynamic system and mitigates the need for substantial feedback. In fact, this is quite advantageous since the resources needed for CSI acquisition scale up with the number of BS antennas in FDD systems. The number of different beams sets that are associated with the clusters is G = M d . We will reuse the same reference beams in different cells. In the proposed setting, we consider a pilot reuse factor of 1 between the clusters in a given cell. Different pilot sequences will be used in neighboring cells which enables to reduce the pilot contamination effect thanks to pathloss. In fact, for a given user, copilot interference will be coming from distant or users with semi-orthogonal channels. Once the reference beams are allocated to the different cells, they will be transmitted so that the mobile users could determine if its channel is aligned enough with the reference beams corresponding to its serving cell. The detailed scheduling procedure is provided in the next subsection.

A. Training and Downlink Probing

As in [START_REF] Sharif | On the capacity of MIMO broadcast channels with partial side information[END_REF] [START_REF] Lee | A New Approach to User Scheduling in Massive Multi-user MIMO Broadcast Channels[END_REF], user selection will start by BSs sending their reference predefined beams which constitute a basis of the signal space. We suppose that user lr, ( l th user in cell r)

g [r] † lr Φ c g [r] lr < α , for, i = 1...d, for all but one c in [1...G]
meaning that user lr will be affected to the cluster for which the normalized projection is greater than α since the user channel is well aligned with the reference beams associated with this cluster. Since users associated with different clusters have their channels centered in different subspaces, the same pilot sequences will be used with a reuse factor of 1 between the clusters. After downlink probing, the mobile users will feed back the index of their cluster to the BS which will conduct pilot assignment and select the users scheduled for transmission. In each group, a maximum of τ users will be scheduled, each one having a different pilot sequence. The main upside of using the downlink probing through reference beams, is to reduce the complexity of the user grouping scheme. In fact, in our setting we do not need to estimate the user channel covariance matrix (e.g. as in [START_REF] Nam | Joint Spatial Division and Multiplexing: Opportunistic Beamforming, User Grouping and Simplified Downlink Scheduling[END_REF], [START_REF] Nam | On the Role of Transmit Correlation Diversity in Multiuser MIMO Systems[END_REF]) which may be cumbersome and quite complex especially in massive MIMO systems. We are able to group users according to their channel subspaces dynamically through the use of reference beams and very limited feedback. In fact the users will only feed back an index. Note that 0 < α < 1 and can be defined dynamically as a function of the user density in the network. The same pilot sequences will be reused in all clusters within a single cell. In this case, we will have an interesting impact on the training phase since we can shorten the pilot transmission time. Supposing that, for each cell, we are going to schedule K users and that we have G c clusters with N b direct neighboring cells. Then, in the classical MIMO setting with pilot aided channel estimation and universal pilot reuse, the training phase should at least have a duration of K channel uses. In our clustering setting on the other hand, only K(N b +1) Gc symbols are needed for training. By appropriately choosing G c and d, we are able to reduce the needed training resources for a given number of scheduled users. The copilot interference, in this case, is coming from users in different clusters or in distant cells. This will enable to reduce the impact of copilot interference.

B. Group based Channel Estimation

Once the users identify their serving cluster, the BS will select τ users per cluster to be scheduled for pilot transmission in order to estimate the effective CSI. In this section we introduce the index of the reference beams set to which, each user is assigned. The wireless channel from user l in cell r associated with cluster j to BS r is given by g i refers to the i th pilot sequence used in cell b. Then during the training phase, the received pilot signal at BS r taken here as a reference BS is given by:

Y p c = C b=1 j∈ν(b) τ i=1 g [rj] ib q b i † + N p Where N p ∈ C M × τ (N b +1)

Gc

is the additive white Gaussian noise matrix with i.i.d. CN (0, 1) entries. Conventionally, the Base Station correlates the training signal with the known pilot sequences of each user in order to obtain a channel estimate. Although we do not estimate the covariance matrix, we can use the information on the dominant subspace to further improve the estimation. Then the MMSE estimate of the l th user in cluster k and cell r is given by: ĝ

[rk] lr = Θ [rk] lr ĝ[rk] LS lr with ĝ[rk] LS lr
being the least square estimate of the channel given by: ĝ

[rk] LS lr = Y p c × q r l = C b∈χ(r) j∈ν(b) g [rj]
lb + N p q r l and Θ

M SE lr = E g [rk] lr - ĝ[rk] lr 2 = Tr      R [rk] lr -R [rk] 2 lr   I + C b∈χ(r) j∈ν(b) R [rj] lb   -1     
Then the channel estimate of user l, r can be written as:

ĝ[rk] lr = R [rk] lr   I + C b∈χ(r) j∈ν(b) R [rj] lb   -1 ĝ[rk] LS lr = ΦA [rk] lr Φ † ĝ[rk] LS lr
where A

[rk] lr is a diagonal matrix with A Therefore with α ≈ 0, g

[rk] lr ∈ Span φ (k-1)d+1 ...φ kd and the rest of copilot users is either confined in orthogonal subspace or coming from distant cells. The resulting channel estimate is given by:

lim α→0 Φ † k ĝ[rk] lr =Φ † k R [rk] lr (I + b∈χ(r) b =r j∈ν(b) R [rj] lb ) -1 ( b∈χ(r) b =r j∈ν(b) g [rj] lb + N p q r l )
Having a lower α enables us to have a better channel estimate reducing the interference and enhancing the spectral efficiency. Note that with α = 0, the only left copilot interference comes from distant cells in which the same set of pilots is reused.

In our setting, thanks to MMSE channel estimation, we are able to separate copilot users signals since each is centered in a different subspace. This enables us to reduce the pilot contamination problem. We propose that the pilot reuse factor would be 1 between the groups meaning that the same pilot sequence can be used G c times within one cell which enables us to reduce the training duration compared with a classical system for the same number of scheduled users. Since copilot signals are centered in different subspaces, increasing the reuse of a given training sequence will not degrade the achievable spectral efficiency of the system.

IV. SPECTRAL EFFICIENCY IMPROVEMENT

In this section we investigate the spectral efficiency of our system under direction based user scheduling. We derive SINR expressions for uplink when the number of antennas goes to infinity. Upon receiving the uplink signal the BS will use the MMSE estimate of the users channels. The decoding in MIMO systems can be done through, Zero ib are uncorrelated for all indexes r, l, j, i, b. and C

[rk] lr is a diagonal matrix with:

C [rk] lr ii = β [rk] 2 lr 1+ C b∈χ(r) j∈ν(b) β [rj] lb
We concentrate on cell r taken as a reference. After the training phase and upon receiving the uplink signal, the BS applies a matched filter using ĝ[rk] † lr in order to detect the data from user (k, l, r).

Then the expected value of d klr is given by:

dklr = C b=1 j∈ν(b) τ i=1 ĝ[rk] † lr g [rj] ib d jib + ĝ[rk] † lr N u
where d jib is the data symbol of user j, i, b with E(|d jib | 2 ) = 1. We see that with α ≈ 0 we completely remove the interference due to pilot contamination coming from different user clusters and the only remaining copilot contamination comes from distant cells in which the same training sequences are used. But another component of the interference becomes dominant. In fact, in classical Random Beam-forming settings, [START_REF] Sharif | On the capacity of MIMO broadcast channels with partial side information[END_REF] [4], only one user is scheduled according to a given criterion from the set of users associated with a given Beam. In our setting τ users from each cluster are scheduled. These users have channels that are to some degree correlated. Then even when using orthogonal pilot sequences, it is difficult to separate their signals. In order to reduce this effect we tend to have d -→ ∞ in the infinite antenna regime or at least a large number of beams d which reduces the correlation between the channels of users within the same group. When d is large, users in the same cluster will have channels distinct enough so that the detection of their signals is possible. When the number of antennas is large, interference not related to pilot contamination vanishes. Considering a constant number of clusters G and d very large we obtain the following result: Proof: The detailed proof can be found in [START_REF] Hajri | Scheduling in Massive MIMO: User clustering and pilot assignment[END_REF] The first term in the denominator represents the interference coming from users using the same pilot sequences in distant cells where the second term is the interference coming from clusters using different beams within cell r. Having a lower α will result in better spectral efficiency. When α -→ 0 the persistent interference will vanish, leaving only a weak component coming from distant cells. While it is very tempting to have a vanishing interference in the asymptotic regime, α can not be made low without having impact on the system. In fact in addition to spectral efficiency, α has an impact on the probability of having a user with the desired channel direction.

V. PILOT ASSIGNMENT USING MAX CUT

The proposed dynamic clustering scheme enables to improve the spectral efficiency but we are not able to completely remove copilot interference. In fact α is typically different from 0 and the limited training resources means that the same pilot sequences need to be reused in distant cells.

A. Problem Formulation

In order to further reduce copilot interference, we propose an intelligent pilot assignment method. In fact, the SINR in the large antenna regime can be enhanced if the users are associated with their pilot sequences such that copilot interference is minimized. After downlink probing, the users are separated into clusters (as explained in section III.A). The Base station selects then at most τ users per cluster (since the number of users in each cluster can be higher than τ ) to be active during one coherence time. This user selection can be done using any known scheduling policy. Then the network will assign efficiently the training sequences to the scheduled users in such a way to reduce the copilot interference. In this section, we focus on this pilot assignment problem. The basic idea is to infer the interference from the Large Scale Fading coefficients that depend on the mobile user geographical location. The aim is to maximize the sum rate by efficiently assigning the pilot sequences. We construct the following combinatorial optimization problem :

max X C b=1 j∈ν(b) τ i=1 τ p=1 log      1 + β ′[rj] 2 ib x [jp] ib C s∈χ(b) u∈ν(s) τ n=1 β ′[ru] 2 ns x [up] ns      s.t τ p=1 x [jp] ib ≤ 1 ∀b = [1..C] , ∀i = [1..τ ] , ∀j ∈ ν(b) τ i=1 x [jp] ib ≤ 1 ∀p = [1..τ ] , ∀b = [1..C] , ∀j ∈ ν(b) With x [jp] ib =
1 if user (i,b,j) uses pilot p 0 otherwise Here user (i, b, j) means user i in cell b and cluster j and p gives the index of the used pilot sequence. β

′[rj] 2 ib is equal to β [rj] 2 ib ξ or β [rj] 2 ib
depending on whether the interference is impacting users from the same cell or from distant ones with the same pilot sequences. The first constraint guarantees that a given user is allocated only one training sequences. The second constraints guarantees that a given pilot sequence is used only once in each cluster. Finding an optimal solution for the proposed optimization problem is computationally prohibitive. So in order to solve this problem we propose a graphical approach with an approximation algorithm that is guaranteed to achieve at least a constant relative performance guarantee. In order to optimize the pilot assignment we propose to construct a graph representing the mobile users and the mutual interference based on the large scale fading coefficients. To do this, we need first to proceed by simplifying the objective function of the optimization problem. Once the pilots are assigned the sum rate is given by:

C b=1 j∈ν(b) τ p=1 log      1 + β ′[rj] 2 ϕ(p)b C s∈χ(b) u∈ν(s) us =jb β ′[ru] 2 ϕ(p)s     
Here ϕ(p) gives the index of the user using pilot sequence p in each cell and cluster. Assuming high SINR, we obtain the following expression equivalent to the sum rate:

C b=1 j∈ν(b) τ p=1 log β ′[rj] 2 ϕ(p)b -log     C s∈χ(b) u∈ν(s) us =jb β ′[ru] 2 ϕ(p)s    
We can further simplify this expression by using the results from [START_REF] Tung | On lower and Upper Bounds of the Difference Between the Arithmetic and the Geometric Mean[END_REF], replacing the arithmetic mean with geometric mean. Then ∀i we can write:

C s∈χ(b) u∈ν(s) us =jb β ′[ru] 2 ϕ(p)s ≈ (|χ(b)| G c -1) |χ(b)|Gc    s∈χ(b) u∈ν(s) us =jb β ′[ru] 2 ϕ(p)s    1 (|χ(b)|Gc -1) + U .
Here U is due to the difference between the arithmetic and geometric means. U depends on the smallest and largest values in addition to the variance of the LSF coefficients. This approximation becomes accurate when the variance of the values of LSF coefficients is small. Since the persistent interference coming from co-pilot users in different neighboring clusters is attenuated by the semi orthogonality and the remaining interference is from distant cells, the variation of the LSF is small making the above approximation efficient. Then the aim of the pilot assignment optimization is to maximize the following expression:

C b=1 j∈ν(b) τ p=1 log β ′[rj] 2 ϕ(p)b -log     s∈χ(b) u∈ν(s) us =jb β ′[ru] 2 ϕ(p)s    
Since the users are already selected for pilot transmission, the first term of the sum does not play any role in the optimization.

Finally the original problem is equivalent to minimizing:

min X C b=1 s∈χ(b) j∈ν(b) u∈ν(s) τ i=1 n=1 τ p=1 log(β ′[ru] 2 is ) + log(β ′[rj] 2 nb ) x [up] is x [jp] nb s.t τ p=1 x [jp] ib ≤ 1 ∀b = [1..C] , ∀i = [1..τ ] , ∀j ∈ ν(b) τ i=1 x [jp] ib ≤ 1 ∀p = [1..τ ] , ∀b = [1..C] , ∀j ∈ ν(b)
Using the mentioned simplifications, we are now able to construct the graphical framework for the problem of pilot allocation.

B. Graphical Modeling and Pilot allocation

We construct corresponding undirected graph for the pilot allocation problem G = (V, E) where V represent the users and each edge from E will be associated with a weight that characterizes the mutual interference between the users in the uplink based on the large scale fading. Note that G = (V, E) will be given by N b + 1 disjoint graphs each one associated with a set of pilot sequences. Figure 2 shows the interference graph for a given set of τ pilot sequences. We specify the Fig. 2: Interference graph edge's weight so that we approach the effective interference between the users in the uplink. In order to make sure that a given pilot sequence is allocated only once in each cluster, the weight of the links between users in the same cluster will be given a large value ω. The weight of the link between two users k, l, r and j, i, b in different cells is given by: ω

[kj] lr,ib = log(β ′[rk] 2 lr ) + log(β ′[rj] 2 ib
). The optimization problem aims at putting users that interfere strongly in different pilot groups, resulting in the reduction of the copilot interference. Putting two users k, l, r and j, i, b in the same group p means that x a,b∈Pi ω ab is minimized. This means that edges where the interference is high are removed since the corresponding users will be allocated different pilot sequences. Recall that the weight of the edges between users in the same cluster will be given a large value ω. This will guarantee that each pilot sequence is used only once in each cluster. After building the Pilot association graph, we can notice that our optimization problem is equivalent to the MAX-τ -CUT problem for N b + 1 disjoint graphs. In graph theory the MAX-τ -CUT problem aims at partitioning the vertices's of the graph so that the weight of the edges crossing the cut is maximized. In our setting we partition the users into τ (N b + 1) groups, each one using one of the orthogonal pilot sequences. Solving the MAX-τ -CUT problem for each set of τ pilot sequences results in the minimization of the edges sum weight within each group, meaning a minimization of the mutual interference in each copilot users group. In this section we use an approximation algorithm to solve the pilot association problem. It is known that, MAX-τ -CUT problem is NP-hard. Which means that the optimal solution for this problem is computationally prohibitive. Then we apply the approximation algorithm proposed in [START_REF] Sahni | P-complete approximation problems[END_REF] which produces an approximate solution that attains, at least, 1 -1 τ of the optimal solution of the max-τ -cut problem. The proposed algorithm can produce a solution in which the inter-cluster weight is at least 1 -1 τ times the optimal sum weight for each set of cells using the same pilot sequences. Since the edge's weight represents the mutual interference that results from sharing a pilot sequence, then the max cut algorithm will assign different pilot sequences for users that interfere strongly.The algorithm proceeds by assigning users to the clusters such that, we minimize the intra-cluster interference at each step. The detailed description of the algorithm is given in the next table. The complexity of the proposed algorithm is proportional to the number of edges, nodes and clusters. The proposed method enables to efficiently allocate pilot sequences based only on large scale fading coefficient which are slowly varying and easily estimated compared with the instantaneous CSI.

Pilot assignment algorithm For each set of cells using the same pilot sequences: Initialize: intra-cluster interference W i = 0, ∀i = 1..τ 1. Assign the τ users in cell 1 to different clusters 2. Randomly Order the rest of the users 3. Take the next Node l and assign it to group i * for which the sum W l i is minimized where W l i = a∈Pi ω la 4. Update the intragroup interference of group i * such that W i * = W i * + W l i * 5. Repeat steps 3-4 until all nodes are assigned.

VI. NUMERICAL RESULTS

In this section we provide some numerical results demonstrating the performance of the proposed user clustering scheme and the pilot assignment approach. We consider an hexagonal cell network with 7 cells of 1 Km radius. The mobile users are located uniformly at random in each cell and we assume that no user is closer to its serving BS than r 0 = 10 m. For large scale fading coefficients we take into consideration only path-loss, where β

′[ru] ib = (R [r]
ib ) (-σ) , between the i th user in the b th cell and the j th BS, where the path-loss exponent σ = 3. We select the parameter α from the interval [0, 1]. We consider a coherence interval of T = 200 symbols split between training and data transmission. The spectral efficiency is measured in bits/second/Hz. Figure 3 shows a comparison in mean square error in channel estimation for a reference user. We can see that the MSE is an increasing function of α. We notice that for low values of α we have a considerably enhanced channel estimate, since low α yields almost orthogonal copilot signal. Figure 4 shows a comparison of the CDFs of achievable sum rates. We notice the considerable improvement due to user clustering. Here we considered the large antenna regime where d = 10. For 7 cells containing each one cluster of users, we achieve a total sum capacity (all users in the network) up to 289 bit/s/hz with probability 0.8 with the grouping scheme while a classical user scheduling achieves a sum capacity up to 140 bit/s/hz with the same probability. This improvement is due to the reduction of the persistent interference in massive MIMO systems due to pilot contamination since copilot signals are semi-orthogonal with user clustering. Figure 5 shows a comparison of the CDFs Fig. 4: CDF Sum Capacity comparison of achievable sum rates when applying the proposed pilot assignment algorithm. Although the curves seem to be close to each other, the improvement is not negligible. In fact, with the proposed pilot assignment method we achieve a sum capacity up to 291.6 bit/s/hz with probability 0.8 while a random pilot allocation achieves a sum capacity up to 289 bit/s/hz with the same probability. This means that the proposed approximation algorithm results in a gain of approximately 52 M bits/s for a bandwidth of 20 M hz. It is worth mentioning that by using our proposed direction based scheduling, we already reduced the interference considerably and the copilot interference comes from users in distant clusters. Therefore, one cannot expect a much larger gain from the pilot assignment framework.

VII. CONCLUSION

In this paper we studied the channel direction based user scheduling in order to mitigate pilot contamination in a massive MIMO system. We proposed a new scheduling approach for TDD systems. Downlink probing is used, reducing the complexity of the scheduling and the need for substantial feedback. The proposed scheme enables a more aggressive reuse of the pilot sequences without degrading the performance. Results show that this grouping improves the spectral efficiency and channel estimation accuracy. Since the proposed grouping approach cannot remove completely the interference, we also proposed a graphical framework for pilot assignment in order to further improve the performances of the system. We proved that pilot assignment can be approximated by a max cut problem in the high SINR regime. We then provide an approximation algorithm to optimize the pilot allocation.

  lr for i = 1, ..., M . This can be justified by measuring the strength of the signal on each beam given by g lr . Assuming that we have G different clusters, each one is associated with d predefined reference beams Φ c = [φ ic , i = 1...d] for c = 1...G. If the channel g [r] lr of user lr verifies:

  [rj] lr . Here ν(b), ∀b = 1..C gives the index of the beams groups allocated to cell b. Not that all the sets of beams can be used in each cell and the number of clusters G c can take values in [1, G]. χ(b) refers to the cells using the same set of pilot sequences as cell b. q b

1 .

 1 Since {φ 1 , φ 2 , ...φ M } is an orthonormal basis of the channel, lr covariance matrix of the channel of user l, r. The Mean square error of channel estimation is given in our case by:

[rk] 2 ilr 2 -→ 0

 20 j∈ν(b) β [rj] lbSince we enforce semi-orthogonality among users in different clusters before the training phase, copilot users within a given cell will have their signals confined in different subspaces each one with dimension d. We consider that Φ k = φ (k-1)d+1 ...φ kd are the reference beams vectors associated with cluster k. With α -→ 0, we reduce the interference between the groups since we confine more and more the channels to defined subspaces of rank d. With α -→ 0 we have a for ∀i > (k -1)d + 1 and i < (kd).

Lemma 1 .

 1 With a matched filter receiver Φ † k ĝ[rk] lr † and large d the uplink SINR of user l, r, k is lower bounded by:

= 1 .

 1 Then given the pilot allocation graph the aim is to partition the graph into τ disjoint Clusters [P 1 ...P τ ] such that ∪ τ i=1 P i = V and τ i=1

Fig. 3 :

 3 Fig. 3: Mean square Error in reference user channel estimation

Fig. 5 :

 5 Fig. 5: CDF Sum Capacity comparison Pilot Assignment