La dernière contribution est liée à la proposition et la conception d'un processeur à jeu d'instructions dédié à l'application (Application-Specific Instruction-set Processor (ASIP)) pour un détecteur SISO LSD. L'ASIP proposé supporte différentes configurations MIMO (2 × 2, 3 × 3, 4 × 4) et différents ordres de modulation (QPSK, MAQ-16, MAQ-64) en plus d'une taille de liste flexible (1 à 64 éléments). Les résultats de synthèse sur une technologie CMOS 130 nm sont détaillés en termes de débit et surface de silicium occupée, et comparés avec d'autres implémentations dans ce domaine.

Résumé

Les systèmes multi-antennes (Multiple-Input Multiple-Output: MIMO) représentent incontestablement une technologie clé pour le déploiement de systèmes de communication sans fil de haute performance. Cependant, la complexité des détecteurs MIMO de haut débit pose un problème sérieux de mise en oeuvre. Parmi les détecteurs MIMO existants, l'algorithme nommé détecteur à sphère (Sphere Decoder Algorithm: SDA) a vu le jour pour réduire la complexité de traitement par rapport à la technique de détection originale basée sur le maximum de vraisemblance (ML). En outre, il a été démontré que SDA atteint des performances optimales pour les systèmes non codés. Toutefois, pour les systèmes codés, d'autres simplifications dans l'algorithme de détection peuvent être utilisées sans altérer les performances en taux d'erreur si un processus itératif de détection et de décodage canal est adopté dans le récepteur. Un tel traitement itératif avec un décodeur canal offre une amélioration significative de la performance en taux d'erreur pour des faibles rapports signal sur bruit. Dans ce contexte, le SDA peut être simplifié davantage et modifié afin de prévoir une détection basée sur des informations pondérées. LSD (List-Sphere Decoder) a été introduit comme une version à entrées/sorties pondérées de la version SDA originale.

En particulier, la première contribution est représentée par une amélioration de SDA, ce qui permet une augmentation significative du débit avec une complexité supplémentaire très limitée et sans dégradation en termes de performance en taux derreurs binaires. La méthode de détection proposée, appelée LASDA (Look-Ahead SDA), est basée sur des transformations formelles de l'algorithme, à savoir Look-Ahead, recalage et pipeline et sur une stratégie modifiée de recherche arborescente. Une conception efficace de type VLSI du détecteur LASDA supportant un system MIMO 4 × 4 avec une modulation MAQ-16 est proposée. Ciblant une technologie CMOS 130 nm, les résultats de synthèse montrent que la solution proposée atteint un débit moyen de 380 Mbps à un rapport signal sur bruit de 22 dB, avec une surface occupée de 0.18mm 2 de silicium. Des comparaisons avec un certain nombre de mises en oeuvre précédentes sont également fournies. La deuxième contribution concerne une étude détaillée sur la flexibilité et la convergence de la détection itérative avec un décodage canal. À cet égard, deux détecteurs à entrées/sorties pondérées (Soft-Input Soft-Output: SISO) sont considérés. Le premier est basé sur LSD et le deuxième est basé sur un filtrage linéaire de faible complexité (Linear Minimum-Mean-Square-Error-Interference-Canceller (MMSE-IC)). Pour les deux techniques, l'impact des différents paramètres de configuration du système en termes d'ordre de modulation et du nombre d'antennes est illustré et discuté. Des diagrammes de transfert d'information mutuelle (EXIT charts) sont développés afin d'analyser en détail le comportement et la convergence du processus itératif. Cette analyse est orientée pour obtenir les compromis possibles entre complexité et performance pour une implémentation matérielle flexible. algorithm can be used without altering the error rate performance if iterative detection and channel decoding is adopted in the receiver. Such an iterative processing with a channel decoder offers significant improvement in error-rate performance for a reduced signal-to-noise ratio. In this context, the SDA can be further simplified and modified in order to provide soft detection: "List Sphere Decoder" (LSD) has been introduced as a soft version of the original SDA. This research thesis focuses on algorithmic, architectural and implementation aspects of the " Sphere Decoder Algorithm" and the "List Sphere Decoder". The main objective of the conducted work is to propose area-efficient implementation solutions while considering throughput, flexibility, and error rate performance requirements of advanced digital communication systems. In particular, the first contribution is represented by an improved SDA, which enables significant throughput increase at a very limited additional complexity and with no degradation in terms of Bit Error Rate performance. The proposed detection method, called LASDA (Look-Ahead SDA) is based on formal algorithm transformations, namely look-ahead, retiming and pipelining, besides a modified tree search strategy. An efficient VLSI design of LASDA detector supporting a 4 × 4 MIMO channel with 16 QAM modulation is proposed. Targeting 130 nm CMOS standard cell technology, synthesis results

show that the proposed solution achieves an average throughput of 380 Mbps at a signal to noise ratio of 22 dB, with an occupied Silicon area of 0.18 mm 2 . Comparisons with a number of previous implementations are also provided. The second contribution concerns a detailed study on flexibility and convergence of iterative detection and channel decoding. In this regard, two Soft-Input Soft-Output detectors are considered. The first one is based on List Sphere Decoding and the second is based on a low complexity linear filtering (Linear Minimum-Mean-Square-Error-Interference-Canceller (MMSE-IC)). For both techniques, impact of the different system configuration parameters in terms of modulation order and number of antennas is illustrated and discussed. Extrinsic Information Transfer (EXIT) charts are developed in order to thoroughly analyze the behavior and the convergence of the iterative process. This analysis is oriented to obtain possible performancecomplexity trade-offs for a flexible hardware implementation.

The last contribution is related to the proposal and design of an Application-Specific-Instruction set-Processor (ASIP) for SISO List Sphere Decoding. The proposed ASIP supports different MIMO system configurations (2 × 2, 3 × 3, 4 × 4) and modulation orders (QPSK, 16QAM, 64QAM) besides a flexible list size (from 1 to 64 elements).

Synthesis results for a 130 nm technology are detailed in terms of throughput and occupied Silicon area, and compared with other related implementations. 3.16 Area-delay comparison between solutions in [1], [2], [3] [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] (4×4MIMO and 16QAM, R=1/2, Source frame=512bits). [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF], [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF], [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF], [4], [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF]. . . . . . . [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] (Hard-Ouput Sphere Decoder) and [4](Soft-Output Sphere Decoder) for SNR=18dB. .

To my parents

List of Figures

FER of

Comparisons between works in

Comparisons of architecture efficiency in

5.3

Comparisons of architecture efficiency in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] and [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] for a 2 × 2MIMO and 64-QAM. . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Comparisons of architecture efficiency in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] and [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF]

Introduction

MIMO technology improves performance of wireless links, at the cost of high computational complexity both at transmitter and receiver sides. In particular, at the receiver end, the detector has to recover from the received signal vector the original data stream corresponding to each transmitting antenna. The optimal receiver for uncoded MIMO systems is the Maximum Likelihood detector (ML). However the direct implementation of ML methods has exponential computational complexity, which makes this approach unattractive, except for low order MIMO systems [START_REF] Bolcskei | Space-time wireless systems : from array processing to MIMO communications[END_REF]. Sphere Decoder Algorithm (SDA) has been proposed as an alternative method, able to guarantee ML performance, with polynomial processing complexity [START_REF] Bolcskei | Space-time wireless systems : from array processing to MIMO communications[END_REF]. SDA reduces the average computational effort by only considering points that lie inside a hypersphere.

SDA can be formulated as a tree search algorithm, which adopts a depth-first search strategy and results in ML performance and variable throughput (see for example [1] [3]). Alternative search methods, such as breadth-first search strategies, normally achieve fixed throughput at the cost of sub-optimal detection performance (see for example K-best algorithms [START_REF] Guo | Algorithm and implementation of the k-best sphere decoding for MIMO detection[END_REF] [16] [START_REF] Guo | VLSI implementation issues of lattice decoders for MIMO systems[END_REF]).

All the works mentioned above have the common characteristic of showing a decline in performance with respect to the optimal receiver.

While most of these solutions achieve performance that is close to ML, this research work faces the problem of a high throughput full ML implementation.

The main contributions of this work are the following:

1. The traditional SDA has been modified at two levels. At the digital signal processing level, look-ahead, pipelining and retiming techniques have been exploited to enable higher clock frequency with respect to traditional SDA implementations. At the control level, a modified search strategy has been adopted. These modifications lead to a new SDA implementation scheme, called LASDA (Look-Ahead SDA).

2. To show the potential of the proposed solution and to estimate its area overhead, ASIC design has been completed for the above mentioned LASDA; compared to direct SDA implementations, the designed detector shows higher throughput with a small increase of occupied Silicon area. Moreover the faster detector maintains ML Bit Error Rate (BER) performance.

More recently, the interest of researchers has focused on MIMO detection algorithms providing soft-output information. Particularly, it has been shown that near-capacity can be achieved on a multiple-antenna channel by extending the maximum a posteriori (MAP) processing techniques developed for modern channel codes to the iterative detection and decoding of a linear space-time mapper combined with an outer channel code [START_REF] Hochwald | Achieving near-capacity on a multipleantenna channel[END_REF]. Proper extensions of the SDA have been proposed in this context [START_REF] Hochwald | Achieving near-capacity on a multipleantenna channel[END_REF] [19] [4] [20]: the List Sphere Decoder (LSD) was first introduced in [START_REF] Hochwald | Achieving near-capacity on a multipleantenna channel[END_REF] to enable joint detection and decoding; single tree search is exploited in [19] [4] as an alternative to repeated tree search technique to improve computational efficiency; a smart management of the tree search is proposed in [START_REF] Marsch | Smart candidate adding: A new low-complexity approach towards near-capacity MIMO detection[END_REF] to achieve low complexity. [START_REF] Witte | A scalable VLSI architecture for Soft-Input Soft-Output Single Tree-Search Sphere Decoding[END_REF] reports synthesis results for soft-in soft-out single tree search MIMO detectors implemented with a 90 nm technology. In [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] a soft-output detector is proposed for MIMO-OFDM systems like IEEE 802.11n WLANs; the work exploits Layered ORthogonal Lattice Detection (LORD) to simplify processing and achieves maxLogAPP performance. In [START_REF] Sun | High throughput VLSI architecture for softoutput MIMO detection based on a greedy graph algorithm[END_REF] near ML performance with fixed throughput is achieved for soft MIMO detection thanks to a graph based greedy algorithm.

The high throughput ML solution given in this work is also applicable for most soft-output detection schemes, since both hard and soft-output sphere decoders share several key processing units.

The LASDA solution represents the first contribution of this work. The second one is related to the List Sphere Decoder, first proposed in [23] as soft version of the original SD: it finds a list of possible candidates and computes soft information according to this list. The choice of the list size is critical as it affects both computational complexity and Bit-Error-Rate (BER) performance. This is particularly true in iterative Soft-Input Soft-Output (SISO) detection and channel decoding. In such systems, short lists tend to reduce the reliability of soft outputs and this can cause the problem of divergence [24][10]. This problem can, however, be limited by constraining the a priori information coming from the channel decoder [START_REF] Liu | Turbo processing for an OFDM-based MIMO system[END_REF]. The main contributions are the following: 1. To illustrate the problem of divergence, adopting the Extrinsic Information Transfer (EXIT) charts [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF].

2. To compare in terms of flexibility and performance the LSD with the Minimum-Mean-Squared-Error Interference-Canceller (MMSE-IC), which is an attractive alternative in MIMO detection mainly due to its reduced complexity [START_REF] Wang | List sphere decoding combined with linear detection-based iterative soft interference cancellation via exit chart[END_REF].

The ambitious aim of this analysis is to the design a multi-mode flexible MIMO detector supporting both MMSE-IC and LSD with variable list size, according to channel conditions and targeted performance.

The previous analysis on possible complexity-performance trade-offs is the preamble of the third contribution of this thesis. Concerning the flexibility, one of the most flexible kind of implementation, exploited in literature, is certainly the Application-Specific-Instruction set-Processor (ASIP): it is a programmable microprocessor, where hardware and instruction set are designed together for one special application. It currently represents the best performance-flexibility tradeoff, being more flexible than an Application-Specific-Integrated-Circuit (ASIC) and having better performance than a General-Purpose-Processor (GPP).

An ASIP implementation of the List Sphere Decoder is presented. In particular, the main contributions are the following:

1. To discuss which are the most critical parts, from an architectural point of view.

2. To propose at the best of our knowledge, the first ASIP of LSD,supporting multiple modulations, number of antennas and list sizes 3. To propose some modifications to the original design to increase the throughput, and to compare performance results with other existing implementations

This thesis is divided in two parts: the first part is dedicated to hard MIMO detection and the second part to the soft MIMO detection. In particular, the part I is composed of two chapters:

Chapter 2 is dedicated to present MIMO systems and MIMO functions. Some basic concepts and the mathematical model are introduced. Then, an overview of the most popular MIMO detection algorithms is reported and the Sphere Decoder Algorithm is detailed, with particular emphasis for the depth-first Schnorr-Euchner SDA, which is the starting point of this research thesis. For completeness, the chapter is concluded mentioning other versions of SDA, exploited in literature.

Chapter 3 presents a modified version of the SDA, which guarantees optimal performance and achieves an increase of throughput, with a limited additional complexity. All modifications applied to the SDA with the purpose of enabling a higher throughput implementation are detailed. In particular, some formal methods, such as look-ahead, pipelining and retiming are employed and described.

Performance of this solution, called Look-Ahead SDA (LASDA) is estimated in terms of both achieved BER and required average number of clock cycles, needed to detect one symbol vector. The VLSI architecture design and the obtained implementation results are presented and compared with other existing solutions.

The part II of this thesis is composed of four chapters: Chapter 4 represents a link between first and second parts. It explains the difference between hard and soft detection and the advantages achieved in a channel coded scheme, with respect to an uncoded one. Some hints on the most popular detection-decoding schemes are done. A particular emphasis is given to the List Sphere Decoder (LSD), which is one of the soft versions of SDA, and a linear detector, such as the Minimum-Mean-Squared-Error (MMSE). Finally, to complete the scenario, a complexity evaluation of a suboptimal soft-output MIMO detector implementation is reported.

Chapter 5 is dedicated to analyze the existing hard and soft MIMO detector implementations. Such an analysis has been conducted to explain and justify the idea of a flexible multi-algorithm MIMO detector, supporting both LSD and MMSE.

In Chapter 6, a detailed analysis of flexibility parameters and divergence issue of iterative LSD is reported. The Extrinsic-Information-Transfer (EXIT) Charts are employed to study the iterative behavior of LSD and, in particular, to have a more precise answer to the problem of divergence, taking into account also the effect of different parameters, such as the size of the list. Finally, LSD and MMSE-IC are compared in terms of performance and complexity, justifying again the idea of a flexible multi-mode detector.

Chapter 7 details a proposed ASIP implementation for LSD. The chapter starts with an introduction to the ASIP methodology, and continues with a discussion on the architectural choices and flexibility parameters. A first suboptimal release of the ASIP is presented, with synthesis results. Then an improved version in terms of clock frequency is proposed. Performance, synthesis results and comparison with state of the art implementations are also reported. In order to increase the throughput, a more efficient usage of the pipeline has been developed and detailed. The chapter ends with a discussion of the results, accompanied by further possible improvements.

Part I

Hard MIMO detection 2 MIMO systems

A continuous increase in required data rate, system capacity and quality of service characterizes wireless applications. Multiple-Input-Multiple-Output (MIMO) systems are recognized as a key enabling technology for increasing capacity and spectral efficiency, because with multiple antennas at both sides of the wireless link they are able to improve communication reliability [START_REF] Gesbert | From theory to practice: An overview of MIMO space-time coded wireless systems[END_REF]. MIMO technology has been proposed to be incorporated into the fourth generation (4G) mobile communication systems to enhance voice and data transmission. Moreover, several current and future wireless communication standards, such as IEEE 802.11n wireless LAN (Local Area Network), IEEE 802.16e WiMax and 3GPP-LTE [START_REF]Multiple-input multiple-output in UTRA (Release 7)[END_REF] already include MIMO techniques, often in combination with OFDM (Orthogonal Frequency-Division Multiplexing).

MIMO functions

MIMO systems are characterized by three main functions: precoding, spatial multiplexing and diversity coding, which are respectively associated with array gain, spatial gain and diversity gain.

1. Precoding: it is the multi-stream beamforming 1 technique, in the narrowest definition, and in a more general sense, the spatial processing done at the transmitter side. In the single layer beamforming, the same signal is emitted from each transmitting antennas, with a certain phase and gain , in order to maximize the signal power at the receiver side. The obtained advantages are:

MIMO functions

to increase the received signal gain, thanks to the constructive interference, and to reduce the multi-path fading 2 . But when the receiver has multiple antennas, the beamforming cannot simultaneously maximize the signal level for all of the receive antennas, so that the precoding is employed. It is important to underline that this technique requires knowledge of the channel state information (CSI) at the transmitter. Spatial multiplexing can be used with or without CSI knowledge.

3.

Diversity coding: it is employed when there is no channel knowledge at the transmitter. A single stream (unlike multiple streams in spatial multiplexing) is transmitted, but the signal is coded using techniques called space-time coding, which exploits full or near-full orthogonality. There are three main types of diversity: time diversity, frequency diversity and spatial diversity. The spatial diversity is related to the employ of spatially different links, affected by different fading. The time diversity ie related to total or partial retransmission of the information in different moments. The frequency diversity is due to frequency redundancy. The first one is very powerful, because it does not require an increase of time and bandwidth, and it is often employed together with the space-time coding.

The spatial multiplexing can be combined with the precoding, in presence of channel knowledge, or with diversity coding when a better decoding reliability is desired. Moreover, the spatial multiplexing makes the receiver very complex, and in general it is combined with the Orthogonal Frequency-Division Multiplexing (OFDM) 3 or with the Orthogonal Frequency-Division Multiple Access 2.2 MIMO system model (OFDMA) 4 , where the multi-path is is well managed. 1 2 3 4

MIMO system model

Considering a Rayleigh fading channel and a complex-valued MIMO system with M t transmit and M r receive antennas, the channel is represented by the M r × M t matrix H:

H =      h 1,1 h 1,2 • • • h 1,Mt h 2,1 h 2,2 • • • h 2,Mt . . . . . . . . . . . . h Mr,1 h Mr,2 • • • h Mr,Mt      (2.1)
where h ij ∼ N c (0, 1) is the fading coefficient between the j-th transmitter and the i-th receiver The M r -dimensional received signal y is given by:

y = Hs t + n (2.2)
where n ∼ N c (0, N 0 ) denotes the M r -dimensional additive i.i.d. (independent and identically distributed) white Gaussian noise vector, and s t stands for the M t -dimensional transmit signal vector, s t = [s 1 s 2 . . . s Mt ] T . Entries of s t are independently chosen from a complex constellation O, whose cardinality is |O| = 2 Q , with Q equal to the number of bits per symbol. The transmission rate is defined as R = M t Q bits per channel use (bpcu).

For QAM modulations, according to [3], the M t -dimensional complex signal model in (2.2) can be decomposed into an M = 2M t -dimensional real signal 1 It consists in controlling the direction and the sensitiveness of the signal, in presence of multiple transmitters and receivers. At the receiver side, the beamforming increases the sensitiveness in the direction of the signal and reduces that in the direction of the noise. At the transmitter side, instead, it increases the power of the signal to be emitted.

2 It indicates the effects of propagation of an electromagnetic wave, due to reflection, diffraction and scattering of signals, which reach the receiver as a sum of copies of the same.

3 It is a multi-carrier modulation scheme, which makes use of a great number of orthogonal sub-carriers. Each of these sub-carriers is modulated with a conventional modulation scheme, such as amplitude or quadrature amplitude modulation, at low symbol rate. The total transmission rate is comparable with that of a single-carrier modulation schemes, keeping the bandwidth constant. The signals are generated and detected with the Fast Fourier Transform. 4 It is a multi-user version of the OFDM. The multiple access is assured granting a subset of sub-carriers for each user.

MIMO detection algorithms

model: ℜ{y} ℑ{y} = ℜ{H} -ℑ{H} ℑ{H} ℜ{H} ℜ{s t } ℑ{s t } + ℜ{n} ℑ{n} (2.3)
where ℜ{ * } and ℑ{ * } respectively denote real and imaginary parts of * . In the real-valued model, the set of valid real-valued symbols is indicated as Ω, where

|Ω| = 2 Q/2 .
In the rest of the thesis, a real-valued model is assumed.

MIMO detection algorithms

Assuming perfect channel knowledge at the receiver and considering systems with space-time coding and spatial multiplexing, the algorithms to separate the data streams, exploited in literature, can be divided into four main categories:

1. Linear Detection Methods: they simply invert the channel matrix. In this family, there are:

• Zero Forcing (ZF): it multiplies the inverse of the channel matrix by the received signal vector. It does not take into account the noise, and for this reason, it has not good results in terms of performance.

• Minimum Mean Square Error (MMSE): it minimizes the square error between the received and the transmitted vectors, taking into account the noise and operating on each component, separately. This method is not able to reach the maximum diversity order M r M t , but it is limited to M r -M t + 1. This causes a low Bit Error Rate (BER) at high SNRs.

2. Interference Cancellation method (IC): it first detects the stronger stream, among all received signal vectors, by means of ZF or MMSE, and removes it before detecting the next stronger streams. Two main techniques are exploited:

• SUccessive Cancellation (SUC): it randomly chooses a component of the received vector and assumes the others as interference. It removes the contribution of it from the vector: this procedure is repeated for each symbol in the vector. This method reaches a diversity order, which is comparable with that of MMSE.

Sphere Decoder Algorithm

• Ordered SUccessive Cancellation (OSUC): similarly as SUC, it chooses the component with the highest Signal to Interference Noise Ratio (SINR). It achieves an higher diversity order than SUC, but it has limited performance, because ZF or MMSE is employed for the initial choice.

3. Maximum Likelihood (ML) detector: it minimizes the difference between the received signal vector and the vector of transmitted symbols distorted by the channel. The problem of deriving the ML estimation s for the transmitted signal vector is formally stated as s = arg min

s∈Ω M t y -Hs 2 (2.4)
where O Mt is the set of possible values for transmitted symbol vectors s.This method is optimal, since it minimizes the error probability and reaches the maximum diversity order, but a direct implementation of ML detection is the exhaustive search that explicitly computes (2.4) for all candidate symbols s ∈ O Mt . The detector has to examine 2 R hypothesis for each received symbol vector. If for low rates, such as R ≤ 8bpcu, this is feasible, for large M t and constellations it is practically unfeasible. As an example, for a 4 × 4 with a 16QAM modulation, corresponding to R ≤ 16bpcu, the number of candidates to be examined is 65536.

4. Sphere Decoder Algorithm (SDA): it has been introduced as a viable alternative to the ML detector, able to guarantee optimal performance, but only with a polynomial complexity [START_REF] Viterbo | A universal lattice code decoder for fading channels[END_REF]. It consists in limiting the search to only those points, which lie inside an hypersphere, with a certain radius, around the received vector. A detailed description of SDA is presented in the following paragraph.

Sphere Decoder Algorithm

SDA achieves ML performance, showing a polynomial average complexity [START_REF] Schnorr | Lattice basis reduction: improved practical algorithms and solving subset sum problems[END_REF].

It reduces the number of candidate symbols to be considered, without excluding the ML solution. The Sphere Decoder Algorithm is composed of three main steps: radius constraint, tree construction and tree exploration.

Sphere Decoder Algorithm

• Radius Constraint (RC)

The calculation of (2.4) is formulated as a tree visit problem, constrained to only those Hs points that lie inside a hypersphere with radius r, around the received point y. This means that:

y -Hs 2 ≤ C (2.5)
where C = r 2 .

• Tree construction

Before computing the distance between received and transmitted vectors, H can be triangularized using proper techniques, such as Cholesky decomposition: H = QR, where the M × M matrix Q has orthonormal columns (Q H Q = I M ) and the M × M matrix R is upper triangular. (2.4) can be written as:

s = arg min s∈Ω M y -QRs 2 = arg min s∈Ω M ỹ -Rs 2 (2.6)

Sphere Decoder Algorithm

where ỹ = Q T y is the Zero-Forcing (ZF) solution [1] 1 . Thus, (2.5) becomes:

ỹ -Rs 2 ≤ C (2.7)
A tree can be constructed [1], where each node has |Ω| sons and there are M = 2M t levels, in a real-valued model. As an example, a 4 × 4 MIMO system with 16 QAM modulation has M = 8 levels and |Ω| = 4 sons (Ω = {-3, -1, 1, 3} is a real-valued constellation). At the tree root, the possible values of entry s M of vector s are associated to |Ω| sons, while tree leaves correspond to all possible vectors s. A node placed at intermediate tree level l will corresponds to a partial symbol vector [s l s l+1 . . . s M ] T .

The square distance d 2 (s) = ỹ-Rs 2 can be iteratively computed following the tree from the root to a leaf:

T l = 0 l = M + 1 T l+1 + |ỹ l -M j=l R l,j s j | 2 l = M, . . . , 1 (2.8)
where l is the current level of the tree, T l is the (squared) Partial Euclidean Distance (PED), calculated as the squared distance between entries M to l of the received vector and partial symbol vector [s l s l+1 . . . s M ] T (distorted by the channel). Therefore d 2 (s) = T 1 is the (squared) Euclidean Distance (ED). As example, figure 2.2 shows the obtained tree for a 2 × 2-MIMO system and a QPSK modulation.

At each level, if obtained PED is larger than the specified radius, the corresponding node and the whole underlying sub-tree are excluded from the search (tree pruning). The amount e l = |ỹ l -M j=l R l,j s j | is called Distance Increment (DI) and can be written as:

e l = |ỹ l - M j=l+1 R l,j s j -R l,l s l | (2.9)
Symbol ψ[l] is introduced to indicate the first two terms in (2.9), which represents the l-th received signal reduced by the interference resulting from 2.4 Sphere Decoder Algorithm the already estimated symbols, s M to s l+1 :

ψ[l] = ỹl - M j=l+1 R l,j s j (2.10)
The expression above is unfolded as

ψ[l] = | (• • • ((ỹ l -R l,M s M ) -R l,M -1 s M -1 ) -• • • -R l,l+1 s l+1 ) | (2.11)
The computation in (2.11) can be arranged in M -l + 1 recursive steps:

1) ψ M +1 [l] = ỹl 2) ψ M [l] = ỹl -R l,M s M = ψ M +1 [l] -R l,M s M 3) ψ M -1 [l] = ỹl -R l,M s M -R l,M -1 s M -1 = ψ M [l] -R l,M -1 s M -1 • • • M -l + 1) ψ l+1 [l] = ψ l+2 [l] -R l,l+1 s l+1 = ψ[l]
(2.12) where the upper index of ψ ranges between M + 1 and l + 1. At the last recursion step, ψ l+1 [l] is used to compute DI:

e l = |ỹ l - M j=l+1 R l,j s j -R l,l s l | = |ψ l+1 [l] -R l,l s l | (2.13)

Sphere Decoder Algorithm

• Tree exploration The tree exploration in SDA is depth-first: when a tree node lies inside the hypersphere, the algorithm goes one level down (forward processing). When a tree leaf is reached and when part of the tree is pruned, an alternative node has to be selected going back to an upper level in the tree: this part of the algorithm is known as backward processing [1]. In SDA, forward processing

ψ l+1 (l) R l,l s (2) l s (4) l s
(3) l s l = s proceeds along tree levels: starting from the tree root (l = M), the nearest point to the received signal (Babai Point) [START_REF] Bolcskei | Space-time wireless systems : from array processing to MIMO communications[END_REF] can be calculated by means of a rounded division, as reported in [3] [1] [START_REF] Mennenga | Search sequence determination for tree search based detection algorithms[END_REF]:

s l = s (1) l = 0.5 ψ l+1 [l] R l,l + 1 (2.14)
where ⌊0.5x + 1⌋ rounds argument x to the nearest odd integer value (this is equivalent to select the nearest point in a PAM constellation). In the rest of the thesis, the Babai Point s

(1) l is indicated as s l for simplicity. Metric normalization with respect to R l,l elements along the diagonal of the channel matrix can significantly simplify this operation. However additional computational effort will be required in this case for normalization, especially in the presence of fast fading channel. Alternatively the Babai point can also be determined by calculating:

s l = s (1) l = arg min s |ψ l+1 [l] -R l,l s| (2.15)
In this work, (2.14) is adopted.

ψ and PED metrics are then updated according to (2.12) and (2.8). Forward processing continues at the lower tree level until either a tree leaf is reached 2.5 Other versions of Sphere Decoder Algorithm or the current PED metric goes outside the hypersphere (T l > C). In these cases, backward processing is started to return back to the closer tree level where not all sibling nodes have already been explored and to select a new symbol. In the Schnorr-Euchner (SE) enumeration, the first chosen symbol at each level is always the Babai Point, while following choices at the same tree level are made according to a zig-zag path around it; this enumeration technique follows the PED ascending order. Fig. 2.3 shows the points selected at tree level l, starting from the Babai Point s l and following the zig-zag sequence for subsequent choices, s

l , s

l , s

l . When a tree leaf is reached, radius may be updated if T 1 < C: if this is the case, T 1 becomes the new radius for the subsequent tree exploration. The tree leaf with the minimum T 1 represents the ML solution.

Other versions of Sphere Decoder Algorithm

The different versions of SDA can be classified, based on three aspects:

System model: complex-valued versus real-valued

The main difference between these two categories is the tree construction and the average number of visited nodes, directly related to the throughput. In fact, in a real-valued system, the tree has a double number of levels than in a complex-valued one, and a number of sons, which is equal to the root of the cardinality of the corresponding complex-valued constellation.

Considering the previous example, shown in the section 2.4, of a 4×4 MIMO system with 16QAM modulation, the tree has M t = 4 levels and |O| = 16 sons (O is a complex-valued constellation), in a complex-valued model. In a real-valued one, instead, it has 2M t = 8 levels and | √ O| = 4 sons. Clearly, the number of leaves is the same for both choices.

The actual number of tree nodes that are visited is directly related to the throughput, which may also be affected by the use of a real or complexvalued channel model. While several authors proved that complex-valued model results in a lower number of visited nodes with respect to real-valued one [1], it was shown in [START_REF] Lee | VLSI implementation of areaefficient list sphere decoder[END_REF] [START_REF] Myllyla | Implementation aspects of list sphere detector algorithms[END_REF] that the latter offers two advantages: (i) it involves a lower global number of elementary real-valued operations and 2.5 Other versions of Sphere Decoder Algorithm (ii) allows for simple enumeration techniques. For this reason real-valued model is more suitable for practical implementation.

2. Direction of the tree exploration: breath-first versus depth-first While the depth-first strategy (see the tree exploration in 2.4) first chooses one symbol at each level and goes down, coming back only later for examining the other alternative points at that same level, the breath-first concurrently selects more than one point at each level. The main exponent of this family is the K-best: it expands the K more promising points at each level. A big value of K avoids a great loss of BER, but it requires to expand an high number of paths in parallel, employing a huge amount of hardware resources. On the other hand, a small K causes a BER degradation. The algorithm finishes when it reaches the leaf level, and the ML solution is represented by the leaf with the minimum ED, among all K leaves. In this way, the K-best, and, more in general the breath-first strategy, is characterized by a fixed number of visited nodes, and therefore a fixed throughput [START_REF] Wong | A VLSI architecture of a Kbest lattice decoding algorithm for MIMO channels[END_REF]. In the depth-first, instead, the actual number of tree nodes that are visited in the detection of a received symbol vector is a stochastic value and its average depends on signal to noise ratio. This implies that detection throughput is not constant.

Enumeration: Fincke Pohst (FP) versus Schnorr-Euchner (SE)

The FP method is the fist introduced from an historical point of view [36]. It consists in considering the nodes of a level with the natural order. For example, in the case of a 4PAM, where sons are {-3, -1, 1, 3}, the nodes are visited exactly with that order. Only later, a more efficient method has been introduced, such as the SE strategy ((see the tree exploration in 2.4)).

Most algorithms are a combination of this three aspects. A short description of the main important follows:

Statistical pruning : it is a modified version of the SDA, in particular, the pruning is based on statistical criteria. It establishes a schedule of the radius r 1 ≤ r 2 ≤ . . . ≤ r Mt and solves

T 1 ≤ r 2 1 ,T 1 + T 2 ≤ r 2 2 , . . .,T 1 + T 2 + . . . + T Mt ≤ r 2
Mt . Since the radius is different at each level of the tree, the region D, which limits the search, is not an hypersphere. This means that the detection is 2.5 Other versions of Sphere Decoder Algorithm not exactly ML, but the performance can arbitrarily be close to ML, thanks to the choice of the probability ε that the transmitted vector does not belong to D , because the error probability upper bound is P e ≤ P M L e + ε. This solution achieves a complexity reduction of order M 2 t [START_REF] Gowaikar | Efficient near-ml decoding via statistical pruning[END_REF]. Automatic Sphere Decoder (ASD) : it is a very efficient algorithm for a software implementation. The nodes are stored into an ordered list, based on their PEDs. The expanded node is the first element in the list, i.e. the node with the smallest PED. The peculiarity of this method is that the above node can be at each level of the tree, but since it requires a sorting and a visiting of a list, it is not feasible for an hardware implementation.

Fixed-complexity Sphere Decoder (FSD) : it is a combination of K-best and SDA. Independently of the noise level and the initial radius, it only visits a fixed number of nodes for each level, based on the χ 2 distribution of the noise matrix. At the uppermost level many candidates are considered, because of the inter-level interference. At the lowest levels, instead, the number is reduced. This produces a performance-complexity trade-off: bigger the number of candidates, better the performance, but higher the computational complexity. This makes FSD suitable for reconfigurable architectures, able to adaptively change the number of candidates, according to channel conditions [START_REF] Barbero | A fixed-complexity MIMO detector based on the complex sphere decoder[END_REF].

Conditioned Ordered Successive Interference Cancellation (COSIC) : it is a particular case of FSD. The idea is to simplify the search thanks to successive interference cancellation for all nodes at the uppermost level. The throughput can be constant or not, depending on the implementation, and it has slightly worse performance with respect to SDA, but it reduces the computational complexity and occupied silicon area [START_REF] Hess | Reduced complexity MIMO detector with close-to ML error rate performance[END_REF].

Two techniques, which can be easily applied to all previous algorithms and all variants of SDA in order to reduce the processing complexity, are the Early Termination (ET) and the simplification of the mathematic norm in (2.4).

The Early Termination consists in constraining the maximum number of visited nodes. When this limit is reached, the detection ends, returning the best found 2.5 Other versions of Sphere Decoder Algorithm solution, which is not guaranteed to be ML. It can have a deep BER degradation. A variant of this method is to change the constraint, according to channel conditions [START_REF] Burg | Advanced receiver algorithms for mimo wireless communications[END_REF]. Another aspect of the SDA, which can be used in any methods, is the possibility of employing a simplified norm. This allows to reduce the complexity, from an implementation and algorithmic points of view, at a price of a degradation of BER. The radius constraint can be rewritten as:

d 2 (s) = T 2 1 + T 2 2 + . . . T 2 Mt ≤ r (2.16)
where T i represents the PED for the i-th level of the tree. It is possible to approximate the Euclidean-norm with one-norm:

d 2 (s) ≈ d 1 (s) = |T 1 | + |T 2 | + . . . + |T Mt | (2.17)
or with the infinity-norm:

d 2 (s) ≈ d ∞ (s) = max{|T 1 |, |T 2 |, . . . , |T Mt |} (2.18) 3
Look-ahead Sphere Decoder Algorithm

State of the Art

A relatively small number of SDA architectures have been implemented with real ML performance (e.g. the 1 st implementation in [1] and [3]), mainly because of three limitations associated with the ML approach: the high computational complexity, resulting in a large occupied area, the variable number of visited tree nodes, and the limited average throughput. Some works are focused on the reduction of the implementation area: in [1] the proposed ASIC (Application-Specific Integrated Circuit) adopts a approximated norm (see section 2.5), which allows for small area; in [START_REF] Hess | Reduced complexity MIMO detector with close-to ML error rate performance[END_REF] further techniques are explored to even reduce Silicon area; in [START_REF] Hsin-Lei | A high-speed SDM-MIMO decoder using efficient candidate searching for wireless communication[END_REF], area cost is limited resorting to efficient searching. The second problem, the variable number of visited nodes, has been widely investigated: in [START_REF] Barbero | Performance analysis of a fixed-complexity sphere decoder in high-dimensional MIMO systems[END_REF], a breath-first algorithm is implemented to achieve a fixed throughput, independently of noise level; the concept of layered orthogonal lattice detector is introduced in [START_REF] Siti | On layer ordering techniques for near-optimal MIMO detectors[END_REF] to guarantee constant throughput;

the parallel architecture proposed in [START_REF] Lee | Parallel architecture for sphere decoder with runtime constraint[END_REF] achieves a small variance in the number of visited nodes, resulting in matching run-time constraints; in [START_REF] Barbero | Fixing the complexity of the sphere decoder for MIMO detection[END_REF] the number of visited nodes is limited by means of a new search strategy. High throughput is also the aim of the ASIC II implementation in [1] that offers a throughput up to 169 Mbps at 20 dB on a 4×4 16QAM MIMO system, while the parallel and pipelined VLSI architecture in [START_REF] Guo | VLSI implementation issues of lattice decoders for MIMO systems[END_REF] also guarantees a fixed decoding throughput 3.2 Look-ahead methodology up to 53 Mbps for the same system. Some recent VLSI implementations for MIMO detectors with reduced complexity are also available in [START_REF] Mondal | Design and implementation of a Sort-Free K-Best Sphere Decoder[END_REF] and [START_REF] Ho Im | A new signal detection method for spatially multiplexed MIMO systems and its VLSI implementation[END_REF]. All the works mentioned above have the common characteristic of showing a decline in performance with respect to the optimal receiver.

While most of these solutions achieve performance that is close to ML, this research work faces the problem of a high throughput full ML implementation.

Some formal transformations can be applied to processing algorithms to enable high throughput implementation. In this work, look-ahead, pipelining and retiming transformations [START_REF] Parhi | VLSI Digital Signal Processing Systems[END_REF] are employed in order to shorten critical path delay and to increase throughput with respect to SDA. These techniques assume a graphical representation of the initial algorithm, in particular the well-known Data-Flow-Graph representation (DFG) is chosen [START_REF] Parhi | VLSI Digital Signal Processing Systems[END_REF].

Look-ahead methodology

This section gives an overview of formal transformation procedures that can be applied to processing algorithms to enable high throughput implementation. In order to clarify the employed methodology, a simple example is proposed: an IIR (Infinite Impulse Response) filter. Eq. (3.1) describes the filter and Fig. 3.1 gives the corresponding DFG representation:

y[k] = x[k] + ay[k -1] (3.1)
where node with symbol + represents the addition and the node with the symbol X the multiplication; a is a constant coefficient, x[n] and y[n] input and output samples at time n. The edge going from addition to multiplication is associated to a inter-iteration data dependency and for this reason it contains one unit-delay (register), labeled with D; on the contrary, the other edge going from multiplication to addition has no delay, as it represents an intra-iteration data dependency.

With the architecture of Fig. 3.1 the critical path delay is given by the following equation: The critical path delay determines the maximum clock frequency, achievable by that architecture. In fact, f max is exactly the inverse of t cp :

t cp = T add + T mul (3.2)
f max = 1 t cp (3.3)
Therefore also the processing throughput, which is directly proportional to the clock frequency, is superior bounded to:

th <= 1 T add + T mul (3.4)
In the Look-ahead transformation a linear recursion is iterated few times to create additional concurrency. Applying look-ahead to the iteration (3.1), the filter equation becomes:

y[k] = x[k] + ay[k -1] = x[k] + ax[k -1] + a 2 y[k -2] (3.5)
where two loop steps are concatenated. Fig. 3.2 shows the DFG, obtained after look-ahead transformation. Now, the number of resources is higher with respect to the original IIR and also the critical path is increased:

t look cp = 2T add + T mul (3.6)
But what is important is the presence of two registers in the recursive part of the graph, allowing to apply retiming technique. It consists in changing the location of delay elements in the datapath, without affecting the input/output behavior of the circuit. Moreover, it is also possible to apply pipelining to the delay is significantly reduced and the achievable throughput becomes:

th max = 1 max(T add , T mul ) (3.7)
In general, look-ahead transformation, accompanied by pipelining and retiming, provides an increment of throughput, and an increase of complexity. The most important limitation of look-ahead transformation is that it is feasible only for linear loops.

Look-ahead optimization of SDA

The presented methodology is applied to the SDA algorithm, described in section 2.4, as detailed in the following section.

3.3 Look-ahead optimization of SDA Operations performed within each block are detailed in dotted boxes.

On the left side of the DFG, computational blocks for the processing of previously defined ψ amounts are indicated. As shown in (2.12), the computation of ψ l+1 [l] (i.e. the received symbol reduced by interference resulting from the already estimated symbols) can be distributed along M -l + 1 steps: at step

k = 1, ψ M +1 [l] = ỹl is calculated, at step k = 2, ψ M [l] is obtained from ψ M +1 [l]
by subtracting the R l,M s M contribution, and at each subsequent step k a new ψ M +2-k [l] is generated. In particular, step k = 1 only needs the ZF term ỹl and can be performed for all l before starting tree exploration. Step k = 2 makes use of the first estimated symbol s M : as a consequence, all ψ M [l] can be calculated when exploration is at top of the tree (level M). Similarly, the following steps k = 3, . . . , M -l + 1 are executed at tree levels M -1, . . . , l + 1.

The DFG in Fig. 3.4 shows the forward processing at a specific tree level (l). ψ l+1 [l], calculated at the previous level l + 1, is used to compute e l according to (2.13). At the same time, ψ l+1 [l -1], also computed at level l + 1, is necessary to generate ψ l [l -1], which will be used at the lower level to obtain e l-1 : eq.(2.12) the ψ l [i] amounts that will be required at the lower tree levels, i < l-1. Therefore

ψ l [l -1] = ψ l+1 [l -1] -R l-1,l s l (3.8) A ψ-
D 1 [i] s l s l ψ l+1 [l] ψ l+1 [l] ψ l [i] ψ l+1 [i] ψ l+1 [l] R l,l ψ l+1 [i] R i,l s l ψ l [i] ⌊0.5 ψ l+1 [l] R l,l + 1⌋ ψ[i] s l R l,l e l ψ l+1 [l] e l e l T l+1 T l T l T l+1 D 2 ψ l+1 [l] R l,l R l,l R i,l i = l - 1 , . . . , 1

Look-ahead optimization of SDA

ψ[i] block 1.65
l -1 ψ-type blocks are indicated in the DFG (Fig. 3.4), each one performing the following update operation:

ψ l [i] = ψ l+1 [i] -R i,l s l i = l -1, . . . 1 (3.9) ψ[i] blocks also include l -1 registers, D 1 [i], with i = l -1, • • • , 1, used to accu- mulate ψ l [i]
amounts. These registers are initially loaded with the corresponding ỹi . In the adopted notation for ψ l [i], the l index corresponds to the current tree level and therefore during forward processing it decreases by one at each cycle.

As an example, input of register D 1 [i] is indicated as ψ l [i], while the output from the same register is

ψ l+1 [i].
Now, the next useful step in this analysis is to identify where the critical path is located, along the forward processing. In particular, it is interesting to find out the delay of each block, in order to understand which is the slowest. A VHDL description of each one has been developed and processing delays have been derived from synthesis using Synopsys Design Compiler version Z-2007.03-SP1. A 0.13 µm CMOS Standard Cell technology is adopted (Table 3.3, rows 2 to 5).

The first column of Table 3.3 shows the name of the block and the second column reports the minimum delay obtained with a 0.13 µm technology. According to synthesis results, the critical path delay in the DFG is approximately1 given by: eq.(2.12) in this case the insertion of pipeline registers along the loop is not allowed [START_REF] Parhi | VLSI Digital Signal Processing Systems[END_REF].

t SDA c.p. ∼ = t S
D 1 [i] D 3 D 4 ψ l+1 [l] ψ l [i] ψ[i] R l,l R i,l s l s l+1 R l+1,l+1 e l+1 D 2 ψ l+1 [i] ψ l+1 [l] D 5 e l+2 T l+3 T l+2 ψ l+2 [l + 1] I II III i = l - 1 , . . . , 1
The other loops in the DFG, namely loop 2 = P ED block → P ED block and

loop 3 = ψ[i] block → ψ[i] block,

Linear approximation and look-ahead transformation

One effective technique to improve processing throughput along a critical loop is look-ahead [START_REF] Parhi | VLSI Digital Signal Processing Systems[END_REF]. However the look-ahead technique can only be applied to linear processing, while loop 1 includes the non-linear operation (⌊0.5x + 1⌋). Thus a linear approximation is necessary. In the forward processing, according to (2.12) and (2.14), the calculation of ψ l+1

[l] at level l + 1 can be written as

ψ l+1 [l] = ψ l+2 [l] -R l,l+1 s l+1 = ψ l+2 [l] -R l,l+1 0.5 ψ l+2 [l+1] R l+1,l+1 + 1 (3.12)
Round operation in (3.12) is now replaced with a simple division:

ψ l+1 [l] ∼ = ψ l+1 [l] = ψ l+2 [l] -R l,l+1 ψ l+2 [l + 1] R l+1,l+1 (3.13)
The symbol ψ is used to represent the approximate version of ψ. Amounts ψ l+2 [l] and ψ l+2 [l + 1] in (3.12) are expressed according to (2.12) as:

ψ l+2 [l] = ψ l+3 [l] -R l,l+2 s l+2 ψ l+2 [l + 1] = ψ l+3 [l + 1] -R l+1,l+2 s l+2
Eq. (3.14) are substituted in (3.13), so obtaining:

ψ l+1 [l] = ψ l+3 [l] - R l,l+1 R l+1,l+1 ψ l+3 [l + 1] -s l+2 R l,l+2 - R l,l+1 R l+1,l+1 R l+1,l+2 (3.14)

Look-ahead optimization of SDA

With the following pre-calculated coefficients,

A l = R l,l+1 R l+1,l+1 B l = R l,l+2 - R l,l+1 R l+1,l+1 R l+1,l+2 (3.15)
(3.14) becomes:

ψ l+1 [l] = ψ l+3 [l] -A l ψ l+3 [l + 1] -B l s l+2 (3.16)
This is the key result that allows for breaking the SDA throughput bottleneck.

While in the first part of (3.12) the calculation of ψ l+1 [l] needs s l+1 , (3.16) clearly shows that the metric ψ l+1 [l] does not depend on s l+1 any more. Instead it requires s l+2 , which is available one cycle in advance with respect to s l+1 .

Since the computation of ψ l+1 [l] does not need to wait for s l+1 , we can think to recursively used it as an input of S block, in order to accelerate the processing in the loop 1 . This approach has the advantage of reducing the critical path. But, as a consequence, the generated output symbol might be different from the Babai Point and it must be indicated in a different way: s l . (3.16) has then to be written in the form

ψ l+1 [l] = ψ l+3 [l] -A l ψ l+3 [l + 1] -B l s l+2 (3.17)
The effects of the possible difference, due to the substitution of the Babai Point s l with s l , are discussed later.

Eq. (3.17 eq.(2.12) andψ), but the whole processing is distributed along three clock cycles, as indicated by bold dashed lines: this leads to a potentially large processing speed-up with respect to the SDA. In order to obtain an estimation for this speed-up, the ψ block has been described in VHDL and synthesized with the same approach adopted for the other main blocks (see

(3.10) D 1 [i] D 3 ψ l+1 [l] ψ l+1 [l] ψ l+3 [l] ψ l+3 [l + 1] ψ l+2 [l + 1] ψ ψ l+1 [l + 1] ψ l [i] ψ l+1 [i] ψ[i] D 4 D 7 s l s l+1 D 2 D 5 e l+1 T l+2 R l,l D 6 D 8 D 9 s l+2 R i,l R l+1,l+1 e l+2 T l+3 ψ l+1 [l] B l i = l - 1 , . . . , 1 ψ l+1 [l] s l+2 B l A l ψ l+3 [l] ψ l+3 [l + 1]

PED

eq.

Block

eq.

Block Block

(2.14)

(2.13) (2.8)
eq.(2.12) which is described as a cycle accurate model in C language. A random source of bits is directly mapped onto a complex-valued 16 QAM constellation, using Gray mapping. A 4 × 4 MIMO system is assumed, so that the bit stream is divided in blocks of 16 bits (4 bits per symbols per 4 transmitters). A flat i.i.d. Rayleigh block-fading channel is assumed: the channel coefficients remain constant over a block of 16 bits. Eq. (2.2) described the MIMO system. At the receiver side, perfect CSI is assumed and unsorted QR decomposition is performed. As detector, either SDA and LASDA are employed. For both the tree search is depth-first real-valued with SE enumeration. The 16QAM is transformed into a real-valued 4 PAM. As a consequence, the tree has M = 8 levels, with 4 sons per node. The detector makes an hard decision on symbols, which are at last directly demapped onto bits. In the detector, a fixed-point precision of 16 bits has been chosen, because it was adopted in most of the literature for the 16-QAM modulation, so it represents a good choice for comparisons. In particular, 8 bits are adopted both for integer and fractional part [START_REF] Cerato | Design of digital architectures for telecommunication systems with special emphasys in integrated circuits for MIMO-OFDM wireless channels[END_REF]. The signal-to-noise ratio(SNR) is defined as

(3.10) D 1 [i] ψ l+1 [l] ψ l+2 [l] e l+2 I II III ψ e l+1 ψ l+2 [l + 1] T l+2 ψ l+2 [i] ψ l+1 [i] ψ[i] ψ l+2 [l + 1] R l,l s l D 3 R l+1,l+1 D 5 D 2 s l+1 B l-1 s l+1 R i,l ψ l [l -1] i = l - 1 , . . . , 1 D 10
SNR = M T E s /N 0 , with E s = E[|s| 2 ], s ∈ O. The software model of LASDA
detector is detailed in Algorithm 2, which is derived modifying the SDA, reported in Algorithm 1.

Look-ahead optimization of SDA Algorithm 1 SDA

Require: |Ω| number of symbols in the real-valued constellation, M number of antennas, r initial radius, ỹi (i = 1, ..., M) ZF solution

1: l ← M, k max ← |Ω|, C ← r 2 = ∞ 2: Forward processing: 3: compute Babai Point, s (1) l , set k l = 1 and s l = s (1) l 4: update PD, ψ l (i) (i = l -1, . . . 1) 5: update PED, T l 6: if T l < C and l > 1 then 7: l ← l -1 8:
goto 2 9: end if 10: Backward processing: 11: if (l = 1) and (T l < C) then 12:

C ← T 1 13: end if 14: if (k l < k max ) and (T l < C) then 15: k l ← k l + 1 16: find s (k l ) l (next best symbol choice) and set s l = s (k l ) l 17: goto 4 18: end if 19: if l < M then 20: l ← l + 1 21: goto 14 22: end if 3.3 Look-ahead optimization of SDA Algorithm 2 LASDA Require: |Ω| number of symbols in the real-valued constellation, M number of antennas, r initial radius, ỹi (i = 1, ..., M) ZF solution 1: l ← M, k max ← |Ω|, C ← r 2 = ∞, ψ M +1 (M) ← ỹM 2:
Forward processing: 3: compute s l , first symbol choice from ψ l+1 (l), and set

k l = 1, s l = s l 4: update PD, ψ l (i) (i = l -1, ...1) 5: update PED, T l 6: compute ψ l (l -1) 7: if T l < C and l > 1 then 8: l ← l -1 9:
goto 2 10: end if 11: Backward processing: 12: if (l = 1) and (T l < C) then 13:

C ← T 1 14: end if 15: if (k l < k max ) and (T l < C) then 16: k l ← k l + 1 17: find s (k l ) l (next best symbol choice) and set s l = s (k l ) l 18: goto 12 19: end if 20: if l < M then 21: l ← l + 1 22:
goto 23 23: end if

Look-ahead optimization of SDA

In the reported simulations, the SNR (Signal-to-Noise-Ratio) ranges between 0 and 30 dB. Two measures are derived from the C model, BER and N C , average number of clock cycles needed to detect one symbol vector (four 16QAM signals for the considered case). In particular, N C is derived, considering a one-nodeper-cycle architecture, i.e. one clock is counted for each visited node. No error correction code is used in the simulated transmission scheme. Simulation results obtained for SDA and LASDA are reported in Fig. 3.9.

No degradation in terms of BER can be seen in Fig. 3.9(a): LASDA and SDA BER curves are exactly superimposed. ML performance of LASDA is explained by the fact that applied formal transformations do not modify the algorithm behaviour but simply its execution on a hardware architecture. Approximate ψ is only used by the S block in Fig. 3.7: although different from the Babai Point, the computed symbol always is a valid constellation point. Moreover, once a valid symbol is generated, it is used to evaluate PED metrics with no further approximations. Since the PED calculated at a certain node is always coherent with the selected symbol,no erroneous pruning can be decided and no decline in the BER performance is caused by LASDA. On the other hand, an huge increase in the number of clock cycles is shown in Fig. 3.9(b) for LASDA over SDA. This

Look-ahead optimization of SDA

increase is around 118% at SNR= 20 dB (BER 5.2 • 10 -4 ). This is due to the fact that, during forward processing, LASDA evaluates approximate ψ, which is used to make the first symbol choice at a tree level l, s l . This computation provides a processing speed-up over SDA. However the linear approximation introduced in LASDA might cause changes in the node enumeration. In particular, s l might be different from the true Babai Point, s l , and this cause the increase in the average number of visited nodes. Next subsection presents the solution to this problem.

A modified search strategy: Test & Restart

The key idea is to allocate resources to calculate Babai Point s l and to compare it against s l . The calculation of the Babai Point requires a separate S block and it is carried out one clock cycle later than calculation of s l , while LASDA is already processing the lower tree level: for this reason, this late Babai Point cannot be efficiently used to drive the tree search in the forward phase. However it can be used to detect and stop a wrong visit direction. Two symbols are then concurrently computed at each clock cycle: s l , which is rapidly derived from ψ metric in one single clock cycle, as illustrated in Fig. 3.7, and s l , the Babai Point, which is derived one cycle later from ψ l+1 [l], by means of a separate S block. The two symbols are exploited to control tree exploration with a strategy said Test &

Restart. This strategy involves the following three steps:

1. Symbol s l is compared to s l .

2. s l = s l means that the symbol chosen by LASDA is the Babai Point. In this case, the SE enumeration can be based on the computed s l and the tree visiting continues with the usual depth-first SE strategy.

3. s l = s l means that the symbol selected by LASDA is not the Babai Point.

This decision is not the best one and it is dropped: s l is substituted with s l and the forward processing is started again with one cycle of delay. Also SE enumeration will start from s l . LASDA choice is discarded and replaced by the Babai Point; the tree exploration is then continued accordingly. However the dropped search direction could be taken again in a later visit to the same tree level.

s l+1 = s l+1 l = l + 1 s l = s l ψ l+1 [l] = ψ l+1 [l]

Performance evaluation of LASDA with Test & Restart

Fig. 3.11 reports an example of tree search with the Test&Restar t strategy: at levels l and l -1, the LASDA is supposed to select symbols s l = 1 and s l = 3 in cycles 1 and 2 respectively: this search direction is indicated with a bold dotted line. In cycle 2, symbol s l = -1 is calculated: as this value is different from s l , the current search direction is stopped and postponed to a later time. The new direction corresponding to s l = -1 is taken and continued in cycle 3 with a new LASDA choice (bold solid line). The example shows that one additional clock cycle is necessary when the test on s l fails. Thanks to the Test & Restart search strategy, LASDA and SDA visit the same sequence of tree nodes; the only difference between the two algorithms is that LASDA tries to anticipate the next node in the forward processing and returns to the best choice when a wrong direction is taken. As a consequence, ML performance is already achieved, as without the Test & Restart, as shown in Fig. 3.12-(a). But in the new search strategy, some nodes might be visited twice as an effect of failed tests; as a consequence it is expected that the average number of clock cycles needed for the detection of a received symbol vector is increased with respect to SDA, but also reduced with respect to LASDA without Test & Restart. In fact, as shown in Fig. 3.12, the described approach results into a very small number of additional clock cycles: this increase is around 4% at SNR= 20 dB (BER 5.

3.3 Look-ahead optimization of SDA -3 -1 -1 3 1 3 3 1 1 3 -1 -3 : : : -3 -1 1 3 -3 -1 1 -3 2 1 3 2 1 : 2 3 " clock " l -1 l s l = 1 s l-1 = 3 s l = -1 = s l s l-1 = -3
: l ← M, k max ← |Ω|, C ← r 2 = ∞, ψ M +1 (M) ← ỹM 2:
Forward processing: 3: compute s l , first symbol choice from ψ l+1 (l), and set

k l = 1, s l = s l 4: if l < M then 5:
Test & Restart:

6:
compute Babai Point at previous tree level, s

l+1 , from ψ l+2 (l + 1)

7: if s l+1 = s (1) l+1 then 8: l ← l + 1 9: s l ← s (1) l 10: ψ l+1 (l) ← ψ l+1 (l) 11: end if 12: end if 13: update PD, ψ l (i) (i = l -1, ...
C ← T 1 23: end if 24: if (k l < k max ) and (T l < C) then 25: k l ← k l + 1 26: find s (k l ) l (next

Architecture design

The S block is a key component in the proposed LASDA architecture. The use of this processing block in an hardware sphere decoder was already introduced in [3]. The behaviour of the component is described in the following sub-section.

S block

Before seeing the overall high level architecture, a particular attention is given to S block, which is certainly the most critical block, in terms of time. Functions of remaining units are clearly defined and close to HW implementation: they process signals using adders, subtractors and multipliers. Less clear, instead, is the direct implementation of this unit.

It receives the approximate version of the PD metric and selects the Babai Point, according to eq. (2.14); additionally it derives the direction step l of the first successive element in the Schnorr-Euchner enumeration. The processing functions of S block unit is formally defined as:

   s l = 0.5 ψ l+1 [l] R l,l + 1 step l = sign (△) = sign s l -ψ l+1 [l] R l,l (3.19)
Fig. 2.3 shows the sequence of selected symbols at a given tree level around the first choice. At the first visit to a level, the Babai-Point corresponds to the first symbol to be chosen ( s l (1) ); the step l information is set to 0 if the algorithm will have to consider the left symbol ( s l (2) ) at the following visit of the node, and to 1 if the next choice is on the right ( s l (3) ). The S block simply choses the starting direction of the SE enumeration, in the forward processing. At each new visit of the node, i.e in the backward processing, the direction will be simply switched, so following the Schnorr-Euchner enumeration.

The general purpose hardware implementation of numerical division is not straightforward and it usually leads to expensive components. However in this specific case, a general hardware division can be avoided and an ad-hoc solution, customized on 16QAM case, can be adopted in order to limit hardware cost and achieve high throughput. The result returned by the S block is a signal point. 1. the Least Significant Bit (LSB) is equal to 1 for all points 2. the Most Significant Bit (MSB) is the sign.

Thus only the second bit must be determined [3]. Fig. 3.15 shows the implementation architecture for S block. It is composed of elementary units: left and right shifters, a 2-to-1 demultiplexer, comparators, xor and xnor gates, and blocks which generate the absolute value. • Forward Unit (FU), which is the core of the detector and performs the forward visit of the tree. This unit, detailed in Fig. 3 with k > 1) or Test & Restart (late Babai point s l ). It is clear that if s l is substituted with s l , also corresponding step l must be replaced by step l , computed by the additional S block in the Test & Restart Unit, and sent to the Backward Unit. The additional multiplexer, devoted to this aim, is not indicated only to not complicate Fig. 3.15. This is the same also for ψ l+1 [l]: the register at the output of the ψ block should be anticipated by another 2-to-1 multiplexer, where the alternative input is

High level architecture

ψ l+1 [l], stored into the Ψ Mem.
• Backward Unit (BU), which concurrently selects the subsequent node to be expanded, according to SE enumeration, and updates the corresponding ψ 3.4 Architecture design metrics:

ψ l [i] = ψ l+1 [i] -R i,l s k l i = l -1, . . . 1 k = 2, 3, . . . ( 3
ψ[i] ψ T l+2 s l s (k) l R ψ[i] i = 1 , . . . , M ψ BU R cmp s l R f/b restart R j,j s l ψ F U Ψ Figure 3
.15: High level implementation architectures for LASDA scheme.

continued in the opposite case. The second control operation makes use of the restart signal: signal cmp informs the CU about the comparison between the s l symbol, calculated by the FU, and the Babai point s l , and if the two symbols are different, the CU stops the current processing flow and starts it again from the Babai point.

Synthesis results

Synthesis results

To assess the achievable throughput and occupied area, the datapath of the proposed architecture (tailored to a 4×4 MIMO channel with 16 QAM constellation) has been synthesized on the same technology and with the same tool mentioned in Section 3.3. The internal precision has been set to 16 bits, which guarantees almost the same performance as the floating point model [START_REF] Cerato | Enabling VLSI processing blocks for MIMO-OFDM communications[END_REF].

Besides running the synthesis of the whole detector, key blocks have been also separately synthesized. Tables 3 Area complexity given in Table 3.3 was derived with a target clock period of 2.05 ns, corresponding to the delay of the S block. Given results reveal that most of area complexity in the detector is due to the ψ[i] blocks (M blocks need to be allocated in FU and BU), while the additional components needed in the LASDA, namely ψ block, the second S block and the CMP block in the TRU have a limited cost, lower than 25000 µm 2 . It is also worth noticing here that area cost for ψ[i] and DI blocks increases linearly with the number of levels in the tree, and so with the number of transmit antenna. On the contrary, the area complexity of the all other blocks reported does not depend on the assumed signal constellation: higher order modulations result into a larger number of sons to be considered at each tree level, but this does not affect the forward processing.

Comparisons with the state of the art

Comparisons with the state of the art

To facilitate comparisons, Table 3.4 reports the main features of a number of sphere decoder implementations: four different k-best SD implementations proposed in [START_REF] Mondal | Design and implementation of a Sort-Free K-Best Sphere Decoder[END_REF] [47] [START_REF] Jie | A threshold-based algorithm and VLSI architecture of a k-best lattice decoder for MIMO systems[END_REF] [15] (columns 2 to 5), the ASIC II in [1] (column 6), the solution in [2] (available for both 0.25 um and 0.13 um technologies), which resorts to "pipeline interleaving" to improve throughput (columns 7 and 8), and an ML serial detector implementation based on [3] (column 9). Column 10 reports the achieved results for the LASDA implementation. The "pipeline interleaving", described in [2], consists in cutting the combinational delay and processing multiple independent streams of incoming symbols. Look-ahead and pipeline interleaving provide the same kind of advantage, that is the achievement of higher clock frequency with respect to the original SDA. However, the two approaches achieve different cost -throughput trade-offs, as shown later in this discussion.

Technology and algorithm differences must be taken into account in the comparison: while architectures proposed in [3] 3.4 gives the Throughput to Area Ratio (TAR), derived as the ratio between average throughput expressed in Mbps and occupied area evaluated as KEG. Looking, in particular, at the achievable throughput, reported results show that pipelining [START_REF] Ho Im | A new signal detection method for spatially multiplexed MIMO systems and its VLSI implementation[END_REF], pipeline interleaving [2] and the proposed look-ahead method are effective techniques to break the throughput bottleneck in the forward processing of SDA and to achieve high throughput. However different penalties in terms of complexity are paid for this advantage. The TAR figure of merit can be used to compare these approaches:

pipelining in [START_REF] Ho Im | A new signal detection method for spatially multiplexed MIMO systems and its VLSI implementation[END_REF] requires a huge amount of area, which significantly affects the 3.6 Comparisons with the state of the art TAR; pipeline interleaving proposed in [2] also results into a very high throughput, but the corresponding increment in the implementation complexity is larger than that required by look-ahead. The larger area cost of the pipeline interleaving approach basically comes from the need of replicating internal memories, which retain data over multiple iterations. On the contrary, look-ahead only needs a few extra resources to implement Test & Restart strategy. Therefore the two approaches provide two different trade-offs between area and throughput. The area-delay plot in Fig. 3.16 shows how pipeline interleaving and lookahead span the design space. The global detector area is reported along the vertical axis, while the per unit time processed symbols are on the x axis (inverse of the throughput, 1/Th). Two points in the upper part of the plot indicate the 0.25 µm implementations in [1] and [2]: the slope of the arrow that links the two points shows that pipeline interleaving provides a huge throughput advantage at the cost of a significant area increase. Unfortunately the same comparisons

Discussion of the results

between the two mentioned implementations cannot be done for the 0.13 µm technology, as synthesis results are available only for the pipeline interleaved detector in [2], which is shown as an isolated point in the left part of the plot. Finally, in the lower part of the plot, two 0.13 µm architectures are reported:

a serial detector based on [3] and the look-ahead solution proposed in this work.

The arrow here proves the potential of the look-ahead method, which provides large throughput gain at the cost of an almost negligible additional area.

Discussion of the results

A modified Sphere Decoder Algorithm for high throughput implementation is proposed (LASDA Moreover, this high throughput ML solution is also applicable for most softoutput detection schemes. As shown in [START_REF] Hochwald | Achieving near-capacity on a multipleantenna channel[END_REF] [32], both hard and soft-output sphere decoders share several key processing units, particularly those necessary for tree search. As a consequence, not only hard-output, but also soft-output sphere decoding can take advantage of the proposed approach, which achieves a throughput gain in tree search.

Part II

Soft MIMO detection 4

Towards Soft Detection

In order to improve data rate and quality of service of wireless communications, the information is protected, thanks to the Forward Error Correction (FEC) (also called channel coding) at the transmitter side. It is a system of error control for data transmission, whereby the sender adds systematically generated redundant data to its messages, also known as an error-correcting code. The American In MIMO scenario, at the receiver side a MIMO detector is combined with a channel decoder: the so called Turbo principle [51] [52]. In fact, the success of iterative decoding for Turbo codes [53] [54] suggests that a new way to devise high-performance wireless communications could be found by considering a probabilistic approach where soft information, presenting the probabilities of different alternatives, is used in detection and decoding processes. Many detection, decoding and estimation problems can be reduced to the estimation of certain probabilities. There are two possible schemes of receiver:

• Scheme with no feedback: as shown in As MIMO detector, in literature many methods are exploited. There are linear detectors, such as Minimum-Mean-Square-Error-Interference-Canceller (MMSE-IC) and other more complex ones, such as the family of detectors, directly derived from the SDA, called Soft Sphere Decoders. In fact, the Sphere Decoding Algorithm (see section 2.4 in the part I) [START_REF] Damen | Lattice code decoder for spacetime codes[END_REF] achieves optimum error-rate performance for systems without error-correcting code, but for the more relevant case of channel coded systems, it can be used in a modified version in order to provide soft information.

Two main approaches are exploited, in order to modify the SDA:

1. Repeated (RTS) or Single Tree Search (STS): It restarts the SD after the ML solution has been found, forcing the SD onto paths for which the bit is the 4.1 Complexity evaluation of a soft-output MIMO detector opposite of the same bit in the ML solution, the so called counter-hypothesis.

In particular, the Repeated Tree Search first finds the ML solution, and restarts again the SDA in order to find the counter-hypothesis. In the Single Tree Search approach [START_REF] Studer | Soft-output MIMO detection algorithms: Performance and implemention aspects[END_REF] [4], instead, the ML solution and all other counterhypothesis are concurrently found.

2. List Sphere Decoder (LSD) [START_REF] Hochwald | Achieving near-capacity on a multipleantenna channel[END_REF]: it first reduces the number of candidate vector symbols to those points which are closer to the received vector.These points are kept into a list L with a certain cardinality and only candidate vector symbols in L are considered for the computation of soft information.

Next section shows a complexity evaluation, related to an hardware implementation of a suboptimal soft-output MIMO detector, which completes the scenario of soft MIMO detection algorithms.

Complexity evaluation of a soft-output MIMO detector

The aim of this work, which is based on [START_REF] Sorrenti | Architetture digitali per ricevitori multi-antenna[END_REF], is the study of feasibility of a

Description of the system

The considered detector includes an outer LDPC channel decoder and a softoutput inner detector for MIMO systems. Figure 4.4 shows the scheme of the transmitter and the iterative structure of the receiver of an Interleave Division Multiplexing-Space Time (IDSM-ST) system, with N T transmitters N R receivers.

Complexity evaluation of a soft-output MIMO detector

The role of the receiver is to estimate transmitted bits d, with respect to the received vector y. In particular, the receiver is composed by a sub-optimal iterative detector, called ESE, and an A Posteriori Probability Decoder (APP DEC) [START_REF] Ping | Interleave division multiple-access[END_REF], which exchange information, as shown in Fig. 4.4.

Ext x (n) j ≡ log   Pr x (n) j = d| -→ y , -→ L x Pr x (n) j = d 0 | -→ y , - → L x   (4.1)
The outputs of ESE are then used by APP DEC, in order to compute a posteriori LLRs with a standard APP decoding [START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF], so that the ESE can refine the estimations in the next iteration. This mechanism is repeated a predefined number of iterations, here chosen equal to 10. In the last iteration, the APP DEC produces hard decisions d on d.

The algorithm of the Elementary Signal Estimator

Assuming α

(n) m , n = 1, • • • , N T , m = 1, • • • , N R
are the fading coefficients between the n-th transmitter and the m-th receiver, modeled as random complex Gaussian variables with zero mean, the received vector at time j can be represented as:

        y (1) j . . . y (m) j . . . y (N R ) j         =         α (1) 1 • • • α (n) 1 • • • α (N T ) 1 . . . . . . . . . . . . . . . α (1) m • • • α (n) m • • • α (N T ) m . . . . . . . . . . . . . . . α (1)
N R • • • α (n) N R • • • α (N T ) N R                 x (1) j . . . x (1) j
. . .

x (N T ) j         +         n (1) j . . . n (m) j . . . n (N R ) j         (4.2)
where n (m) j denotes a sample of an N R -dimensional additive i.i.d. (independent and identically distributed) white Gaussian noise vector. Eq. (4.2) can be written in matricial notation, as:

-→ y j = [α] j -→ x j + -→ n j (4.3)
The a priori LLR of x Pr

(n) j is defined as: log   Pr x (n) j = d Pr x (n) j = d 0   = -→ L x d with d = d 1 ÷ d 2 ( m 2 -1)
x (n) j = d Pr x (n) j = d 0 = exp -→ L x d (4.5)
Keeping into account the contribution of each symbol of the constellation O to the sum of exponentials, it can be written:

d ′ ∈O exp -→ L x d ′ = d ′ ∈O Pr x (n) j = d ′ Pr x (n) j = d 0 = 1 Pr x (n) j = d 0 (4.6)
Now, substituting (4.6) in (4.5), the following equation is obtained:

Pr x (n) j = d = exp -→ L x d d ′ ∈O exp -→ L x d ′ (4.7) Let x
(n) j be a random variable, the mean E (•) and the variance Var (•) of x

(n) j can be computed starting from (4.7):

E x (n) j = d∈O dPr x (n) j = d = d∈O d exp -→ L x d d ′ ∈O exp -→ L x d ′ (4.8a) Var x (n) j = 1 -E x (n) j 2 (4.8b)
In order to avoid excessive growing of the exponential function, it is convenient to replace the exponent with the difference between the actual LLR value and the maximum LLR, as shown below:

E x (n) j = d d exp -→ L x d - -→ L max d ′ exp -→ L x d ′ - -→ L max (4.9)
The received signal at time j has mean

E ( -→ y ) = N T n ′ =1 -→ α (n) j E x (n) j (4.10)

Complexity evaluation of a soft-output MIMO detector

and covariance

[R] j ≡ Cov ( -→ y j ) = E -→ y j -→ y T j -E ( -→ y j ) E -→ y T j = N T n=1 Var x (n) j -→ α (n) j -→ α (n) j T +σ 2 [I]
(4.11) where T indicates the transposed vector.

For single-path channels, where each transmitted signal x

(n) j is considered only in one received signal, the soft estimation of x (n) j in (4.1) can be computed from (4.2), as in [START_REF] Liu | Simple iterative chip-by-chip multiuser detection for CDMA systems[END_REF]:

Ext x (n) j = (d n -d 0 ) -→ α T j [R] -1 j ( -→ y -E( -→ y ))+E x (n) j -→ α T j [R] -1 j -→ α j 1-Var x (n) j -→ α T j [R] -1 j -→ α j + -1 2 (d 2 n -d 2 0 ) -→ α T j [R] -1 j -→ α j 1-Var x (n) j -→ α T j [R] -1 j -→ α j (4.12)
Looking at (4.12), it is evident that the reverse matrix [R] -1 j for each j is the most complex computation. A simplification of (4.12) is possible applying Cholesky-decomposition [59]. Let [L] j be the inferior triangular matrix, obtained by Cholesky-decomposition [R] j = [L] j [L] T j , and let us define g

(n) j [L] -1 j -→ α (n) j
and f j [L] -1 j ( -→ y -E ( -→ y )), (4.12) can be written as:

Ext x (n) j = (d n -d 0 ) -→ g (n) j T -→ f j +E x (n) j -→ g (n) j T -→ g (n) j 1-Var x (n) j -→ g (n) j T -→ g (n) j + -1 2 (d 2 n -d 2 0 ) -→ g (n) j T -→ g (n) j 1-Var x (n) j -→ g (n) j T -→ g (n) j (4.13)
For clarity, a short description of the iterative decoding algorithm for singlepath channel with QAM modulation and multiple receivers is reported below:

Complexity evaluation of a soft-output MIMO detector

Algorithm for single-path channel with multiple receiver antennas (a) Initialization: Set -→ L (x

(n) j = 0) ∀n, j (b) Main iteration: E x (n) j , Var x (n) j = Apriori stat -→ L x (4.14a) E ( -→ y j ) = 2N T n=1 -→ α (n) j E x (n) j (4.14b) ----→ M40b1 (n) j = Var x (n) j -→ α (n) j (4.14c) [S40b] j = 2N T n=1 ----→ M40b1 (n) j -→ α (n) j T (4.14d) [Cov (y j )] = [S40b] j + σ 2 [I] (4.14e) [L] j = Cholesky factorization ([Cov (y j )]) (4.14f) L -1 j = [L] j -1 (4.14g) -→ g (n) j = L -1 j -→ α (n) j (4.14h) --→ S14 j = -→ y j -E ( -→ y j ) (4.14i) -→ f j = L -1 j --→ S14 j (4.14j) M11 (n) j = -→ g (n) j T -→ f j (4.14k) M12 (n) j = -→ g (n) j T -→ g (n) j (4.14l) M13 (n) j = E x (n) j M12 (n) j (4.14m) M14 (n) j = Var x (n) j M12 (n) j (4.14n) S15 (n) j = M11 (n) j + M13 (n) j (4.14o) S16 (n) j = 1 -M14 (n) j (4.14p) --→ Ext x (n) j = (s n -s 0 ) S15 (n) j S16 (n) j - 1 2 s 2 n -s 2 0 M12 (n) j S16 (n) j (4.14q)
More complex operations are detailed below.

var app1 = exp ( -→ L x) m -max apr f act var app2 = var app2 + Const[m + 1] • var app1 var app4 = var app4 + (Const[m + 1]) 2 • var app1 var app3 = var app3 + var app1 E x (n) j = var app2 var app3
Var x

(n) j = var app4 var app3 -E x (n) j 2
The parameters Const [i] with i = 0, . . . , 2 m 2 -1 are shown in Table 4.1 for a Q-PSK and a 16-QAM. -0.70710678118654757 -0.94868329805051377 Const [1] +0.70710678118654757 -0.31622776601683794 Const [2] +0.31622776601683794 Const [3] +0.94868329805051377

(Const[0]) 2 +0.5 +0.9 (Const[1]) 2 +0.5 +0.1 (Const[2]) 2 +0.1 (Const[3]) 2
+0.9

4.1 Complexity evaluation of a soft-output MIMO detector

4.14f: For m = 1, . . . , 2N R For i = m, . . . , 2N R x = ([Cov (y i )]) mi -i-1 r=1 l ir l mr If i = m l mi = √ x else l mi = x l ii 4.14g: For m = 1, . . . 2N R do [L -1 ] j mm = 1 lmm For m = 1, . . . 2N R -1 do For i = m + 1, . . . , 2N R do S13 = i-1 r=m l ir [L -1 ] j rm [L -1 ] j im = -[L -1 ] j ii S13 4.14h: For m = 1, . . . , 2N R -→ g (n) j m = 2N R r=1 [L -1 ] j mr -→ α (n) j r 4.14i: For m = 1, . . . , 2N R --→ S14 j m = ( -→ y j ) m -(E ( -→ y j )) m
4.14j:

Complexity evaluation of a soft-output MIMO detector

For m = 1, . . . , 2N R -→ f j m = 2N R r=1 [L -1 ] j mr --→ S14 j r 4.14k: M11 (n) j = 2N R r=1 -→ g (n) j r -→ f j r 4.14l: M12 (n) j = 2N R r=1 -→ g (n) j r -→ g (n) j r
It can be mathematically demonstrated that the decoding complexity grows linearly with the number of transmitters and with the cube of number of receivers [START_REF] Keing | Semi-random forward error correction codes and space-time codes[END_REF].

Hardware implementation

The high level block diagram of ESE is depicted in Fig. 4.5, where L0, L1 and L2 represent the a priori probabilities for the computation of mean E and variance V ar of transmitted signals. The covariance matrix is obtained by means of L0, L1 and L2 and CSI and stored into a Register File (RF). After Choleskydecomposition, the resulting upper triangular matrix replaces the original covariance matrix, then it is inverted and stored in the same locations, in order to save memory. The vector -→ f j (4.14j), which is common to each transmitter antenna, is used in the final computation of the a posteriori probabilities Ext0, Ext1 and Ext2.

The architecture is composed of six main macroblocks:

1. Apriori stat: computes a priori statistics, 2. cov : computes the covariance, 3. cholesky: applies the Cholesky-decomposition, ), which produces var app1 for one accumulator and two Multiply-Accumulate (MAC) units. This last block has the aim of computing mean and variance of signal coming from n-th antenna. It is important to underline that a division operation is avoided by means of a multiplication and a second memory MEMORIA 1/x, which stores the inverse (precomputed) of memory address. The Apriori stat block can be allocated 2N T times in a parallel architecture, or just once in a sequential one. In the following, the second case is assumed with the purpose of saving silicon area.

cov block

The most complex task of the algorithm is the computation of the covariance matrix, which is performed once per iteration. Moreover, the maximum dimension established for a MIMO system is 4 × 4, equivalent to a 8 × 8 real-valued system.

Thanks to the symmetric structure of the above matrix, it is necessary to store only 36 elements. For each column and for each row, one summation of N T elements is applied:

[Cov (y)] ij = 2N T n=1 Var x (n) -→ α (n) i -→ α (n) T j + σ 2 [I] (4.15)
The implementation of the above equation is characterized by three counters: the first, synchronized by the system clock, for index n, the second, synchronized by the terminal count of the first one, for the row index j and the last, synchronized by the terminal count of the second counter, for the column index i. The same indexes are also used as selection signals of multiplexers, whose inputs are variances and coefficients, α and α T , of channel. The circuit is simple. In order to avoid to lose the time (36 clock cycle) necessary to reset one MAC, two MACs

l ii = a ii - i-1 k=1 l 2 ik (4.16)
for diagonal elements and Since simulations demonstrate that x < 16, the significant bits of input data goes from s 3 to the desired precision, with respect to the chosen signal width. For example, if the architecture would initially implemented on FPGA, in particular a Xilinx Virtex 5, which has memories resources of 36Kbits, a 11 bits data width is necessary. So, input data goes from s -7 to s 3 . The representation of output data is, instead, variable, because it does nott contain initial zeros, as shown in Table . 4.2.

l ij = 1 l jj a ij - j-

Complexity evaluation of a soft-output MIMO detector

x 1/ √ x LUT notation 2 -7 2 3 • • • 2 -7 2 2 • • • 2 -8 2 -6 2 3 • • • 2 -7 2 2 • • • 2 -8 2 -6 + 2 -7 2 2 • • • 2 -8 2 1 • • • 2 -9 2 -5 2 2 • • • 2 -8 2 1 • • • 2 -9 2 -4 2 2 • • • 2 -8 2 1 • • • 2 -9 2 -3 2 1 • • • 2 -9 2 0 • • • 2 -10 2 -2 2 1 • • • 2 -9 2 0 • • • 2 -10 2 -1 2 0 • • • 2 -10 2 -1 • • • 2 -11 2 0 2 0 • • • 2 -10 2 -1 • • • 2 -11 2 1 2 -1 • • • 2 -11 2 -2 • • • 2 -12 2 2 2 -1 • • • 2 -11 2 -2 • • • 2 -12 2 3 2 -2 • • • 2 -12 2 -3 • • • 2 -13 2 4 -2 -7 2 -2 • • • 2 -12 2 -3 • • • 2 -13

invs block

In the computation of [B] = [L] -1 , diagonal elements are calculated, using Cholesky-decomposition, as:

b kk = l -1 kk = √ a kk -1 = 1 √ a kk (4.18)
which is exactly the value stored into the LUT. In this way, cholesky block can be modified as shown in Fig. 4.10. As for the not-diagonal elements, cholesky block can be reused just changing input data. Looking at Fig. 4.11, it is evident that, for the computation of b i,j , entire i-nth row and j-nth column are necessary at the same time. The solution is a smart Register File, composed of 36 registers, some control signals and concerning multiplexers, which choose between two possibilities: row j and row i for Cholesky decomposition or row i and column j for the matrix inversion. The equation for the auxiliary parameters -→ f j is the following:

-→ f j = L -1 j -→ y j - 2N T n=1 ) -→ α (n) j E x (n) j (4.19)
Fig. 4.12 shows the block digram of the f block: it is composed of 8 MAC units for the computation of the parallel summation of all elements of the vector -→ f j , 8 subtractors and a unit, called g and shown in detail in Fig. 4.13, for matrix-vector product -→ g

(n) j = [L -1 ] j -→ α (n) j .

antenna n block

As for Apriori stat block, also antenna n block, Fig. 4.14 , is allocated once and works sequentially for 2N T transmitters. This block computes the auxiliary parameter -→ g

(n)
j , by means of the g unit, as described before. Then last variables are calculated:

M11 (n) j = -→ g (n) j T -→ f j (4.20)
and M12

(n) j = -→ g (n) j T -→ g (n) j (4.21)
by means of 2 MAC units for M11

(n) j and other 2 MAC for M12

(n) j . For each MAC couple, the two units work alternatively: while the first MAC evaluates,

Complexity evaluation of a soft-output MIMO detector

the second one is reset to zero. Final outputs are:

--→ Ext x (n) j = Cost M11 (n) j + E x (n) j M12 (n) j 1 -Var x (n) j M12 (n) j + Cost2 M12 (n) j 1 -Var x (n) j

M12

(n) j (4.22) Thanks to the common denominator in (4.22), one memory, that as the same structure and functionality of rom div in Apriori stat block, can replace the divisions.

Synthesis results

In order to assess the achievable throughput and occupied area, the proposed architecture, tailored to a MIMO system {2 × 2, 3 × 3, 4 × 4} and modulations

th = N LLR N CK f CK (4.23)
where N LLR is the number of LLRs, depending on the topology of MIMO system and modulation, N CK the number of clock cycles to produce outputs and f CK the clock frequency. For the case of a 3 × 3-MIMO system and 16-QAM, the resulting throughput for a sequential and parallel architecture is respectevely: In the sequential architecture each block, shown in Tab. 4.3, is allocated once and work in a sequential way, so that Apriori stat and antenna n must be reused a number of times equal to the double of the number of transmitters.

th seq = 6.
The resulting throughput is low and silicon area is the minimum. In the parallel scheme, instead, Apriori stat and antenna n are allocated 2N T times, obtaining an increase of area and a further increase in term of throughput. Moreover, some blocks contain functional units that are the same used in other blocks: in order to optimize the area occupation, those resources could be shared, keeping into account that the throughput decreases.

5

Soft MIMO detection: the idea of a multi-algorithm detector

After a brief overview on the introduction of soft detection in MIMO communications presented in the previous chapter, here the idea of an multi-algorithm detector is introduced. Such an idea is detailed and supported by an analysis of existing hard and soft MIMO detector implementations.

State of the Art

In MIMO scenario, linear detectors are suboptimal, in terms of error rate performance, with respect to Soft Sphere Decoders, but they have also a reduced computational complexity. Therefore, it is fair to ask if it is possible to combine in some way the high BER performance, achieved by the family of Soft Sphere Decoders, and the low computational complexity, obtained with a linear detector, such as MMSE-IC. In order to have a precise answer, this chapter reports a detailed analysis of hard and soft detectors, exploited in literature. It points out the advantages of the soft detection with respect to the hard one, and represents a feasibility study, which justifies the previous idea.

Table 5.1 shows a comparison between different solutions, presented in literature, included [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF], which is the VLSI design of the Look-ahead SDA presented in chapter 3. The ASIP design in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] is related to a Minimum-Mean-Square-Error Interference Canceller Equalizer (Soft-Input Soft-Output). The throughput results are obtained for an iterative system, with MMSE-IC equalizer combined with Turbo

State of the Art

decoder, and the number of iterations is equal to 5. It is implemented as ASIC on a 90 nm technology. Then two VLSI designs of near-ML Soft-Output MIMO detectors are presented in [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] and [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF]. The QR-decomposition is not included in area results of the former, while it is comprised in the latter. In particular, solution in [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] is based he Layered ORthogonal Lattice. Already mentioned in chapter 1, the work in [4] proposes a near ML Soft-Output Single-Tree-Search Sphere Decoder, complex-valued and with Schnorr-Euchner enumeration. The error rate performance ranges from exact max-log soft-output to hard-output SIC. The MMSE-SQRD stage preprocessing is not included in the area results.

Finally, a Soft-Output MIMO Detector, dynamically reconfigurable for QPSK, 16-QAM and 64-QAM modulation schemes for 4 × 4 MIMO system, is presented in [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF]. The QR-decomposition is not included in the area results.

Before starting the analysis of the introduced implementations, some clarifications related to the parameters, shown in the Table 5.1 are also necessary:

• All papers, except [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], show area results in Equivalent Gate (EG) unit, as shown in the row 11 of the Table 5.1 . The correspondent values in mm 2 are obtained, according to A 1gate = 320f 2 , where f = f eature size, as reported in ITRS'10.

• The unit of measurement for the throughput (row 12) in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] is MSymbol/s. These values must be multiplied by the number of bits per symbol, according to the modulation (1 bit for a BPSK, 2 bits for QPSK, 4 bits for 16QAM and 6 for 64QAM), and divided by the number of iterations (5 in this case) in order to obtain the correspondent values in Mbps.

• Solutions in [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] and [4] are characterized by a variable throughput, depending on SNR value. [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF] reports the worst case (not defined in the paper). In order to have a direct comparison between [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] and [4] a value of SNR = 18dB has been chosen. The remaining papers have, instead, a fixed throughput and they cannot directly be compared to [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] and [4].

• In order to have a correct comparison, a reference technology of 90nm has been chosen, and area, frequency and throughput for different technologies are scaled, according to ITRS'10. In particular, the normalized throughput [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF], [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF], [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF], [4], [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF].

(

Analysis

a clock frequency increase of 2x per technology generation until 2007 (65nm) and of 1.25x per technology generation after the same year. The normalized throughput in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] and [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF] is given as a range, from the minimum to the maximum values (min to max). The normalized area (row 11) is computed according to A 90 = A( f 90 f ) 2 , where f = f eature size, f 90 = 90nm, A = area in the original technology and A 90 = normalized area in 90nm.

• Architecture efficiency metric has been measured through the Throughput to Area Ratio (TAR), computed as normalized throughput divided by normalized area, already defined in subsection 3.6.

Analysis

Analyzing Table 5.1, there are four points to be discussed:

1. Soft-Output vs Hard-Output: a Soft-Output Detector has a gain up to 3dB, with respect to an Hard-Output Detector, as already said. A Soft-Output detector presents an increase of area of about 60% [4], also pointed out comparing [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] and [4]. This is due to the higher number of symbols to be visited and to the additional computational complexity required to compute LLRs. The BER of solution in [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] cannot be directly compared to that in [START_REF] Wenk | VLSI implementation of the list sphere algorithm[END_REF], also shown in Fig. 5.1, because the former is related to the output of MIMO detector and the latter, instead, is related to the output of the decoder. Moreover no channel coding is assumed in the former, while a convolutional code is employed in the latter. Anyway the performance improvement, with a limited increase of occupied Silicon area, justifies the recent interest towards soft-output detection in MIMO systems.

2. Optimal Soft-Output vs Max-Log Soft-Output: as reported in [4], the Max-Log approximation produces only up to ∼ 0.3dB loss of SNR, with respect to Optimal Soft-Output (see Fig. 4.2), but achieves a great reduction of computational complexity.

Soft-Output MMSE vs Soft-Output and fixed-throughput MIMO

Decoder: this analysis concerns solutions in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF], [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] and [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF]. About FER

Analysis

Analysis

performance, [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] does not report any results, and it just states to achieve near-ML performance. So it is not comparable to the others, because of the absence of information. Instead, looking at Fig. 5.2 and Fig. 5.3, it is evident that the performance of MMSE with 3 iterations is comparable with that of LORD: in fact for a F ER = 5 * 10 -2 both have SNR ∼ 20dB. For more iterations MMSE has better performance. This improvement is due to iterations: the same equalizer can achieve a gain of some dBs if it iterates. In fact, paper [START_REF] Amis | Reduced complexity near-optimal iterative receiver for Wimax full-rate space-time code[END_REF] shows as an Iterative Full-Rate STBC equalizer gains 2dB of SNR for a BER = 6 * 10 -2 with 4 iterations with respect to the not-iterative one, as demonstrated in Fig. 5.4 and Fig. 5.5. This attests as a sub-optimal equalizer, like MMSE, can achieve better performances than an optimal one (optimal for not-iterative algorithms), if it becomes iterative. Analyzing the throughput over area ratio for all three papers, [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] shows the highest among all, as shown in Tables 5.3 and 5.4. This is due to the fact that both [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] and [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF] propose a K-best strategy, guaranteeing a fixed throughput. They focused on increase parallelism, visiting more points in the same time, and, clearly, requiring more area.

Analysis

Ref.

[13]

[4] Th/Area [ M bps mm 2 ] 6556 2173

Table 5.2: Comparisons of architecture efficiency in [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] (Hard-Ouput Sphere Decoder) and [4](Soft-Output Sphere Decoder) for SNR=18dB.

Ref. Baghdadi et al. [6]

[12]

Th/Area [ M bps mm 2 ] 1499 134

Table 5.3: Comparisons of architecture efficiency in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] and [START_REF] Cupaiuolo | Low-complexity and high throughput VLSI architecture of soft-output ML MIMO detector[END_REF] for a 2 × 2MIMO and 64-QAM.

Ref. [6]

[7] Th/Area [ M bps mm 2 ] 923 413

Table 5.4: Comparisons of architecture efficiency in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] and [START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF] for a 4 × 4MIMO and 64-QAM.

Soft-Output MMSE vs Soft-Output Sphere Decoder: a Soft-Output

Sphere Decoder gets a gain of ∼ 3.2dB with rate of 2/3 and ∼ 5.2dB with rate of 5/6 for a F ER = 10 -2 with respect to MMSE, as reported in [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF] (see Fig. 5.6). This is the further reason why to iterate is necessary, transforming a Soft-Output MMSE into a Soft-Input Soft-Output MMSE. A number of iterations from 5 to 7 is sufficient to have better performance [START_REF] Amis | Reduced complexity near-optimal iterative receiver for Wimax full-rate space-time code[END_REF]. In fact, comparing the curve of Soft-Output ML in Fig. 4.2 and MMSE (2 iterations) in Fig. 5.7, it can be seen that for a F ER = 2 * 10 -2 the latter as a gain of ∼ 2.3dB with respect to the former.

The reduction of area, achieved by the Soft-Output Sphere Decoder in [4] is about 32.6% with respect to MMSE-IC in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF], but the solution in [4] is related to a particular system and a particular constellation. The throughput and the TAR cannot be analyzed in this comparison, because [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] has a fixed throughput and [4] a variable one, based on channel conditions.

Also the [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF] does not specify which value of SNR or FER is associated to the reported worst case throughput, so that it is not possible to compare its results to [4] and, therefore to [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF].

Analysis

Analysis

Therefore, the comparison must be limited to [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] and [4], also because [START_REF] Gamba | Look-ahead Sphere Decoding: Algorithm and VLSI Architecture[END_REF] is related to Hard-Output MIMO detection. Therefore, it is necessary a detailed analysis between this above papers.

(a) Area: in order to have a more precise comparison in term of Silicon area, it is necessary to consider that results in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF] includes a matrix inversion, which is performed through an analytical method. But, in many works in literature, such as [START_REF] Echman | A scalable pipelined complex valued matrix inversion architecture[END_REF], [START_REF] Myllyla | Reduced complexity near-optimal iterative receiver for Wimax full-rate space-time code[END_REF], [START_REF] Karkooti | FPGA implementation of matrix inversion using QRD-RLS algorithm[END_REF] the matrix inversion includes a QRdecomposition and it consists of tree steps: 1) QR-decomposition, 2) a matrix inversion (R -1 ) and 3) a matrix multiplication (A -1 = R -1 Q) [START_REF] Echman | A scalable pipelined complex valued matrix inversion architecture[END_REF]. Also the Soft-Output Sphere Decoder needs a preprocessing stage to apply QR-decomposition to channel matrix, but area results in [4] does not include it. The table 5.5 shows some implementations of QRdecomposition in different technologies.

Ref.

[ It is reasonable taking into account results in [START_REF] Kuang-Hao | Implementation of QR decomposition for MIMO-OFDM detection systems[END_REF], since it is the more efficient and one of the most recent work among them. The normalized area in 90nm technology is A QR = 0.069984mm 2 , and by adding it to results in [4], a rough estimation of the total area required by QRdecomposition and Soft SD is obtained A QR+SSD = 0.2172mm 2 , i.e. ∼ 6% less than MMSE in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF]. This percentage seems to be low, but the Soft SD replaces the MMSE equalizer and the soft demapper, because its output are estimated symbols and LLRs, as Fig. 4.1 shows. So, an estimation of occupation of demapper is useful to have a more clear idea.

Analysis

Regarding this, paper [START_REF] Jafri | ASIP-Based Universal Demapper for Multiwireless Standards[END_REF] proposes an ASIP implementation of a universal demapper for multi-wireless standards and for one receiver. The area result must be multiplied by the number of receivers, which is 4, obtaining A demapper = 4 * 8KGE = 32KGE. Now, adding this value to that

shown in [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF], a rough estimation of the total area of MMSE+demapper is obtained, A M M SE+demapper = 116.3KGE = 0.3014mm 2 . The reduction achieved by the Soft Sphere Decoder is about 27.9% with respect to MMSE. Certainly, this is the case of a 4 × 4 system and 16-QAM.

For smaller systems and constellations, the area will be furthermore reduced. Anyway, the Soft SD has a very limited increase for higher number of antenna and higher order system, due to the more registers, necessary to store more visited points and related metrics. In fact, the search along the tree is depth-first, which means that the number of computational resources is the same, even if the number of levels and the number of sons per father node increase. So it can be expected that the area of the Soft SD is less or at most equal to MMSE with demapper for all cases (2 × 2, 3 × 3, 4 × 4, B-PSK, Q-PSK, 16-QAM, 64-QAM).

(b) Throughput: the throughput of Soft SD is variable with channel conditions, number of antennas and modulation. When channel conditions are good (high SNR), the number of visited nodes is low, and throughput high. Otherwise the algorithm needs to visit more nodes because of the presence of high level of noise. Moreover, usually the throughput decreases when number of antennas and order of constellation increase. It would seems that Soft SD is more suitable for smaller systems and modulations. In fact, for the case of (4 × 4 and 16-QAM) and F ER = 10 -2

Soft SD guarantees 320Mbps at SNR = 18dB, which is 5% less than that of MMSE (336Mbps). This last value is not reported in the Table 5.1, because in this case 2 iterations are sufficient to have better performance of FER: so it must be divided by 2 and not by 5. By the way, the throughput of [4] is related to SNR = 18dB and this means that the difference, between throughput of Soft SD and MMSE, reduces when SNR increases, since throughput of Soft SD becomes much more higher.

Analysis

(c) Architecture efficiency: the discussion can be similar to the previous. Soft SD obtains the best efficiency for high SNR. The architecture efficiency must be computed, taking into account the area of QR+Soft SD for [4] and MMSE+demapper for [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF]. About throughput of [START_REF] Jafri | A universal mmse-ic linear equalizer for multi wireless standards[END_REF], a 4 × 4 system, with 16-QAM modulation, F ER = 10 -2 is considered: the original throughput must be divided by 2, as in the previous case. Results are:

T AR M M SE+demapper = 336M bps 0.3014mm 2 = 1115 M bps mm 2
and T AR QR+SSD = 320M bps 0.2172mm 2 = 1473 M bps mm 2 . So, Soft SD has a value of throughput to area ratio, which is about ∼ 32% more with respect to MMSE.

Therefore, Soft SD could be a good candidate as substitute of MMSE, under certain conditions. Probably for low SNRs MMSE is better, because with some iterations it achieves better performance and higher throughput than Soft SD; instead for high SNRs Soft SD has a better architecture efficiency.

Anyway, this point can be furthermore investigated, also considering an iterative detection-decoding system. The key word in this research is the flexibility, not only in terms of trade-off between performance and complexity, but also meaning a detector able to fit in different numbers of antennas, modulation orders and wireless standards. As Soft-Input Soft-Output SD, the List Sphere Decoder has been chosen, since it is the easiest extension of a traditional depth-first hard SDA, and offers some parameters, such as the size of the list and the LLR clipping, which can be tuned, to obtain the desired performance-complexity trade-off.

6

Flexible Soft-Input Soft-Output detector: List Sphere Decoding and Linear MMSE Detection While chapter 5 justifies the idea of a multi-algorithm flexible detector, this chapter illustrates a detailed analysis of a Soft-Input Soft-Output LSD in terms of iterative behavior and flexibility parameters. BER performance and computational complexity of LSD have been also explored and compared to those of linear MMSE-IC.

Description of the system

In order to analyze the iterative behavior of the LSD algorithm, a traditional scheme for data transmission and reception has been adopted, as Fig. 6.1 shows. The system model is represented by eq. (2.2), in section 2.2. A stream of bits is encoded, randomly interleaved and mapped onto a constellation. In particular, a convolutional code (rate 1/2, generator polynomials [133 0 171 0 ] and constraint length 7) and an hard Gray mapper are assumed. Then the stream of symbols is mapped onto M t transmitters, through a serial-to-parallel block. The channel model is assumed to be flat, i.e. all frequency components of the signal experience the same magnitude of fading (Rayleigh). Moreover, it can be either stationary over a frame composed by several vectors of M t transmitted symbols (blockfading), or it can change from vector to vector (fast-fading). Since the channel 6.1 Description of the system model has a great impact on performance of the detector, in this work both models are considered. At the receiver side, a MIMO detector is combined with a channel decoder. They reciprocally exchange soft information. The detector takes as inputs channel observations y and the a priori information coming from the decoder. The soft outputs of the detector become the a priori information for the decoder. The channel decoding is performed by means of a BCJR decoder, with either MAP or Max-log-MAP approximation. As for MIMO detection, two algorithms are considered: LSD and MMSE-IC. In Fig. 6 the two following subsections.

List Sphere Detector (LSD)

The LSD algorithm was proposed in [23], as a straightforward extension of the sphere decoder [START_REF] Damen | Lattice code decoder for spacetime codes[END_REF]. It finds not only the ML solution, but a list of L candidates 6.1 Description of the system which have the smallest distance from the received vector. Considering a block of bits x, the a posteriori symbol probability can be expressed by means of LLR [23] as:

L D k = log P [x k = +1]|y, H P [x k = -1]|y, H (6.1)
with k = 1 . . . QM t . x k = -1 and x k = +1 represent respectively the logical zero and the logical one. Using Bayes theorem, the a posteriori L D k can be written as:

L D k = L A k + L E k (6.2)
where

L A k = log P [x k =+1] P [x k =-1]
represent the a priori LLR values coming from the decoder, and L E k are the extrinsic LLRs. According to (6.2) and with the Max-log approximation, the extrinsic LLRs can be directly computed by the detector as [23]:

L E k ≈ 1 2 max x∈L +1 k {- 1 σ 2 y -Hs 2 + x T [k] L A [k] } - 1 2 max x∈L -1 k {- 1 σ 2 y -Hs 2 + x T [k] L A [k] } (6.3)
where s = map(x), x [k] denotes the subvector of x obtained by omitting its k-th element x k , and L A [k] denotes the vector of all L A values omitting L A k . L +1 k and L -1 k denote respectively the subset of candidates in the whole list with the bit x k = +1 and the subset with x k = -1.

MMSE-IC Linear Equalizer

In the context of low-complexity suboptimal algorithms the Minimum-Mean-Square-Error Interference-Canceller (MMSE-IC) was developed [START_REF] Tuchler | Minimum mean squared error equalization using a priori information[END_REF] [START_REF] Wang | Iterative (turbo) soft interference cancellation and decoding for coded CDMA[END_REF]. The detector receives symbols corrupted by the noise of the channel and co-antenna interference. Then it partially cancels the interference and symbols are demapped into LLRs and deinterleaved. The decoder removes the noise and produces soft information values, which are interleaved and given as feedbacks to the detector. Since it is shown in [START_REF] Chen | An improved turbo-BLAST system for quasistatic channel[END_REF] that if the decoder and the detector exchange a posteriori information for the computation of symbol expectations, the receiver achieves faster convergence rate and better performance, we use a posteriori information 6.2 Flexibility and divergence analysis of iterative LSD as feedback. The detected symbols can be expressed using time invariant approximation [START_REF] Laot | Low-complexity MMSE turbo equalization: a possible solution for EDGE[END_REF] as: si = λ i p H i (y -Hŝ + ŝi h i ) (6.4) where i = 1 . . . M t , ŝ is the vector of decoded symbols, ŝi is the i-th element of this vector, h i is the i-th column of matrix H and (.) H represent the Hermitian operator. The parameters λ i and p k are given by:

λ i = σ 2 s 1 + σ 2 ŝ p H i h i (6.5
)

p i = E -1 h i (6.6)
In the previous equation the matrix E is:

E = ((σ 2 s -σ 2 ŝ )HH H + σ 2 n I) (6.7)
where σ 2 s , σ 2 ŝ and σ 2 n are variances respectively of transmitted symbols, received symbols and noise of the channel. I is the identity matrix.

Flexibility and divergence analysis of itera-

tive LSD

Flexibility parameters

The size of the list in LSD has an impact on both performance (BER) and computational complexity. If a detector has the capability to adaptively change the list size, this can be exploited to achieve a desired trade-off between BER performance and complexity.

In the context of iterative decoding, for a low number of antennas and low modulation order, a small list is enough in order to achieve good performance. In fact the list size is directly related to the system configuration. If a short list size is applied for high number of antennas and/or high modulation order rather than having an improvement of BER with iterations, a problem of divergence [START_REF] Dai | A list sphere decoder based turbo receiver for groupwise space time trellis coded (GSTTC) systems[END_REF][10] appears, so that a bigger list is necessary.

In literature two methods are mainly exploited to handle the list: the first method,

Flexibility and divergence analysis of iterative LSD

introduced in [23], consists in using the list obtained at the first iteration also for all subsequent iterations; the second method updates also the list at each iteration [START_REF] Jong | Iterative tree search detection for MIMO wireless systems[END_REF]. As showed in [START_REF] Dai | A list sphere decoder based turbo receiver for groupwise space time trellis coded (GSTTC) systems[END_REF], this last method, which implies much more computations, is equivalent to generate at the first iteration a larger list and to extract from the same list different sub-sets at each following iteration; this technique avoids the divergence and achieves further improvements in terms of performance. On the other hand, from the implementation point of view, the size of the list is a parameter with a great impact in term of latency and requirement of memory. Thus list size can be used to search a proper trade-off between performance and complexity.

The second key element of soft-output LSD is the "LLR clipping" level [23]:

when one of the two sets L +1 k , L -1 k is empty, the LLR value for the bit under consideration should be set to a certain value. This predefined value has an impact on performance and convergence of the iterative process. Different choices are proposed in literature: ±8 in [23], ±3 in [START_REF] Jong | Iterative tree search detection for MIMO wireless systems[END_REF], ±50 in [START_REF] Liu | Turbo processing for an OFDM-based MIMO system[END_REF], ±r 2 , where r is the radius of the hypersphere, in [START_REF] Wenk | VLSI implementation of the list sphere algorithm[END_REF] or ± ln 1-P b P b , where P b is the probability of a bit error at the detector output and it depends on the modulation, in [START_REF] Zimmermann | Optimal LLR clipping levels for mixed hard/soft output detection[END_REF]. The divergence is mainly caused by the unreliability of a smaller list [START_REF] Dai | A list sphere decoder based turbo receiver for groupwise space time trellis coded (GSTTC) systems[END_REF][10], but a better understanding of this phenomenon can be obtained via EXIT-chart, as explained in the next subsection.

Analysis of divergence using EXIT chart

First proposed in [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF] for parallel concatenated codes, and later extended to iterative demapping and decoding [START_REF] Brink | Designing iterative decoding schemes with the extrinsic information transfer chart[END_REF], the Extrinsic Information Transfer Chart is a powerful tool to analyze the iterative behavior of the system. The detector can be treated as a demapper. According to L A1 , L A2 , L E1 and L E2 in Fig. 6.1, I A1 and I A2 represent the a priori mutual input information respectively of the detector and of the decoder, and I E1 and I E2 the correspondent extrinsic mutual output information. The EXIT chart formulation is based on the fact that the extrinsic information L E1 (i.e. L A1 ) coming back from the decoder, are almost Gaussian distributed [START_REF] Brink | Designing iterative decoding schemes with the extrinsic information transfer chart[END_REF]. Additionally, large interleavers keep the a priori L A1 fairly uncorrelated over many iterations. Hence, the a priori input L A1 can be 6.2 Flexibility and divergence analysis of iterative LSD modeled, applying an independent Gaussian random variable n A1 , with variance σ 2 A1 and zero mean µ A1 , according to:

L A1 = µ A1 x + n A1 (6.8)
where x ∈ {±1} represent the known transmitted unmapped bits. Since L A1 is supposed to be Gaussian, µ A1 = σ 2 A1 /2 is fulfilled. The conditional probability density function belonging to L A1 value is:

p(L A1 /X = x) = 1 2πσ 2 A1 e -(L A1 -x σ 2 A1 2 ) 2 2σ 2 A1 (6.9)
It can be demonstrated that the Shannon's mutual information between the equally likely X and the respective LLRs L A1 , for symmetric and consistent L A1

values, is I A1 = I(L A1 ; X), 0 ≤ I A1 ≤ 1 [START_REF] Brink | Designing iterative decoding schemes with the extrinsic information transfer chart[END_REF]:

I A1 = 1 2 x=+1,x=-1 +∞ -∞ p(L A1 /X = x)log 2 2p(L A1 /X = x) p(L A1 /X = -1) + p(L A1 /X = +1) dL A1
(6.10) Then, with eq. (6.9), (6.10) becomes:

I A1 = 1 - +∞ -∞ 1 2πσ 2 A1 e -(L A1 -x σ 2 A1 2 ) 2 2σ 2 A1 log 2 1 + e -L A1 dL A1 (6.11)
Moreover, for a generic standard deviation σ, defining J(σ) := I A1 (σ A1 = σ):

lim σ→0 J(σ) = 0 lim σ→∞ J(σ) = 1 with σ > 0 (6.12)
The function J(σ) is directly connected to the capacity of the AWGN channel, it cannot be expressed in closed form. It is monotonically increasing and reversible [START_REF] Cover | Elements of Information Theory[END_REF].

σ A1 = J -1 (I A1 ) (6.13)
In the same way, also extrinsic mutual output information I E1 = I(L E1 ; X) can be expressed as:

I E1 = 1 2 x=+1,x=-1 +∞ -∞ p(L E1 /X = x)log 2 2p(L E1 /X = x) p(L E1 /X = -1) + p(L E1 /X = +1) dL E1
(6.14)

Flexibility and divergence analysis of iterative LSD

Viewing I E1 as a function of I A1 and E b /N 0 values, the extrinsic information transfer characteristics of the detector are defined as:

I E1 = T 1 (I A1 , E b /N 0 ) (6.15)
which can be computed for a desired (I A1 , E b /N 0 ) combination, by means of Monte Carlo simulations. The independent Gaussian random variable of eq. (6.8), where σ A1 is determined through eq. ( 6.13), is applied as a priori input to the detector. Similarly, the extrinsic transfer characteristic of the decoder is:

I E2 = T 2 (I A2 ) (6.16)
It describes the input/output relationship between the a priori input L A2 and the extrinsic output L E2 values. It is independent of the channel noise, and it can be computed assuming L A2 to be Gaussian distributed and applying same equations used for the characteristics of the detector T 1 .

The detector and the decoder characteristics are then plotted into a single diagram, called Extrinsic Information Transfer Chart. In the following graphics, the decoder characteristic is always represented by a solid red line, while other coloured lines are detector characteristics for different E b /N 0 values. On the yaxis, the extrinsic information produced by the detector I E1 becomes the a priori input for the decoder I A2 . On the x-axis, instead, the extrinsic output of the decoder I E2 becomes the a priori input of the detector I A1 . In this way, the so called ideal or snapshot trajectory , indicated with a solid black line, approximately describes the true behavior of the iterative system. While the ideal trajectory is obtained from a detection-decoding of a single block of bits, the average trajectory (dashed black line) traces the average behavior over a certain number of blocks. The considered system is a 4 × 4-MIMO, with a 16-QAM modulation, code rate 0.5, a MAP decoder and Gray mapping. The model of the channel is considered as block-fading for this analysis. Each EXIT chart is obtained for an interleaver size of 10 5 bits and finite list length. The numerical method to apply EXIT chart has been derived from [START_REF] Hagenauer | The exit chart -introduction to extrinsic information transfer[END_REF].

Since the divergence phenomenon has to be studied here, the first method of handling the list has been chosen, i.e. the list obtained at the first iteration is also used for all subsequent iterations. In particular, the original algorithm of LSD in [23], with LLR clipping value of ±8, has been adopted, in order to analyze the effect of a reduction of the size of the list. The Fig 6 .2(a) shows that for list size of 512 at E b /N 0 = 10dB the ideal trajectory gets stuck after 4 iterations. This means that the system is able to converge in 4 iterations. Fig. 6.2(b), instead, shows the BER for the same system, modulation and list size, but for an interleaver size of 480 bits (frame size of 240 bits), which is a more realistic case, applied by wireless communications standards, such as WiMax Standard.

Similarly to EXIT Chart, also BER curves show that performance is not improved with more than four iterations. The average trajectory in Fig. 6.2(a) is obtained from a "free-running" iterative detection-decoding of 1000 different blocks of 480 bits. The difference with respect to the ideal trajectory is evident [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF], due to the very smaller interleaver size (480 bits) with respect to the ideal case (10 5 bits), but this decoding also gets stuck after 4 iterations. The same conclusion can be drawn from BER curves. Then it can be concluded that a list of 512 candidates for a 16-QAM constellation is a reliable choice, which results into a decoder that Now, a reduction of the list size is applied: results obtained with a list size equal to 64 are shown in Fig. 6.3. With E b /N 0 = 10dB, the effect of a short list is to open the tunnel between detector and decoder, in particular increasing the mutual information for low BERs. The ideal trajectory has about 3 iterations, however Fig. 6.3(b) shows that, with an interleaver size of 480 bits, performance gets worse after the second iteration. This phenomenon is also visible in the average trajectory of Fig. 6.3(a): after the second iteration, even if the mutual information at the output of the LSD slightly increases, the decoder is not able to improve the results, and gets worse. The reason of this behavior is mainly the unreliability of the list: smaller the list, higher the probability that one of the two sets L -1 k , L +1 k is empty, higher the number of times you need to fix LLRs to the clipping value. When the detector sets the output LLRs to the fixed clipping level, it cannot take into account feedback soft inputs coming from the channel decoder and its behavior reduces to a hard-output detector [START_REF] Zimmermann | Optimal LLR clipping levels for mixed hard/soft output detection[END_REF]. Moreover, when the list size is reduced, the LLR distribution at the decoder output is no more 6.2 Flexibility and divergence analysis of iterative LSD Gaussian, as seen in Fig. 6.4. This explains why the EXIT Chart does not match with BER Chart, since the hypothesis of Gaussian distribution of soft information fails. After a wide research in literature, only [START_REF] Liu | Turbo processing for an OFDM-based MIMO system[END_REF] and [START_REF] Dai | A list sphere decoder based turbo receiver for groupwise space time trellis coded (GSTTC) systems[END_REF] has been found, which highlight the problem of divergence. In particular, only solution in [START_REF] Liu | Turbo processing for an OFDM-based MIMO system[END_REF] details the employed method in order to avoid the divergence: it is based on constraining the maximum allowable value of a priori information L A , coming from the decoder, to prevent the value of x T

[k] L A [k] from growing too large. The maximum value is chosen as:

L A max = r min(1, k O σ 2 ) (6.17)
where r is the radius of the LSD and k O = M t M r E avr . E avr is the average energy of the modulation (2 for Q-PSK, 10 for 16-QAM and 42 for 64-QAM). The rule for constraining the a priori information is the following:

L AC = L A max{L A } ≤ L A max L A max max{L A } L A max{L A } > L A max (6.18)
Moreover, an LLR clipping value of ±50 has been chosen [START_REF] Liu | Turbo processing for an OFDM-based MIMO system[END_REF]. Results obtained when this solution is applied to the case of 16-QAM and a list of 64 candidates,

Comparisons between LSD and MMSE-IC

are shown in Fig. 6.5. The effect of constraining a priori LLRs is, in general, a reduction and a modification of the original mutual information (see Fig. 6.5(a)), and since an empirical and conditional scaling is applied, the original transfer functions of the detector is modified (the curve corresponding to E b /N 0 = 12dB is below the one corresponding to E b /N 0 = 10dB for I A1 < 0.6). No divergence appears and at E b /N 0 = 10dB both average and ideal trajectories get stuck after 3 iterations, as furthermore pointed out by the BER chart in Fig. 6.5(b).

Comparisons between LSD and MMSE-IC

Adopting the solution in [START_REF] Liu | Turbo processing for an OFDM-based MIMO system[END_REF], it is interesting to explore the performance of LSD for different modulations and systems, also compared to a low-complexity suboptimal algorithm, such as the Minimum-Mean-Square-Error Interference-Canceller (MMSE-IC) equalizer [78][79]. As mentioned in section 6.1 both fast and block flat fading channel models are considered. The setup for the following simulations is shown in Table 6.1.

Comparisons between LSD and MMSE-IC

MIMO system 4 × 4, 2 × 2 Modulation Q-PSK,

Block Fading Channel

In the case of block-fading, the channel matrix is constant over a frame, here a coded frame of 480 bits is considered. As Fig. 6.6 shows, no significant improvement is achieved after two LSD iterations. Moreover LSD is able to outperform MMSE in two iterations, also with a moderate list size, such as 64 candidates.

Regarding MMSE a significant performance degradation appears for high SNRs, due to a matrix inversion issue in the eq. (6.7) [START_REF] Jafri | ASIP-based flexible MMSE-IC linear equalizer for MIMO turbo-equalization applications[END_REF]. This matrix has two contributes: one represented by the channel matrix and the other by the variance of the noise. For high SNRs the main contribution comes from the channel matrix H. Thus a bad realization of H causes the above matrix to be singular, which results in a wrong computation of equalization coefficients. This will impact the whole frame in case of block-fading scenario.

Fast Fading Channel

In the case of fast-fading channel, the matrix inversion issue in MMSE, described in the previous section, has much less impact (Fig. 6.7(a)(b)) because a bad channel matrix realization affects one symbol vector rather than the complete frame. Regarding LSD, simulations have shown that the proposed solution [START_REF] Liu | Turbo processing for an OFDM-based MIMO system[END_REF] is not able to eliminate definitively the unreliability of a small list. In the fast-fading, with a list of 64, a performance degradation, compared to MMSE, happens and the divergence appears early (since the third iteration). This forces to increase the size of the list, in order to improve BER performance and avoid the divergence with iterations. So, for the QPSK the size of the list has been increased to 256, and for 16QAM and 64QAM to 512. As before, also for this case, LSD has better performance for a block-fading channel. Although a list size of 64 is large enough for a 2 × 2 system, with a fast-fading channel, the achieved BER after two LSD iterations is comparable with that obtained with five MMSE iterations.

Comparisons between LSD and MMSE-IC

0 2 4 6 8 10 -8 -6 -4 -

Comparisons between LSD and MMSE-IC

0 2 4 6 8 -8 -6 -4 -
We can then say that LSD is more adaptable than a linear detector, such as MMSE-IC, since changing the size of the list and the "LLR clipping" value, different performance-complexity trade-offs can be achieved. For what concerns the channel model, in case of fast-fading, for small constellations and system configurations, MMSE has similar performance to LSD. On the other hand, LSD has better BER performance than MMSE when the estimation of the channel conditions remain constant over a frame, like in the block-fading case.

Comparisons between LSD and MMSE-IC

Complexity comparison

This section reports results on the number of operations required for the detection of a frame, in the block fading scenario. Table 6.2 shows the number of real additions/subtractions and multiplications for detecting an encoded frame of 480 bits, in the 4 × 4-MIMO case with 16-QAM. QR-decomposition for LSD and matrix inversion for MMSE-IC are not considered, so that these results are independent of the model of the channel. The complexity of MMSE-IC is fixed, with assigned antenna number and modulation, instead, for LSD it is variable with the SNR and Table 6.2 shows the average operation number, obtained after 1000 simulations for SNR=16dB (equivalent to a BER of 10 -6 ).

The LSD is mainly composed of two units: list generation, performed only in the first iteration, and LLRs computation, performed at each iteration. Similarly, MMSE-IC includes two main processing tasks: the computation of symbol expectations, which is performed according to eq. ( 6.4), and the evaluation at each iteration of soft mapper and demapper outputs. As shown in [START_REF] Hassibi | On the sphere-decoding algorithm i. expected complexity[END_REF], the average complexity for an hard SD is O(M 3 t ). Since the LSD not only finds the ML solution but a list of candidates, it is claimed that the complexity of list generation grows also linearly with the size of the list, as O(M 3 t L). Moreover the complexity of LLR computation is O(M 2 t Q 2 L) [START_REF] Wang | List sphere decoding combined with linear detection-based iterative soft interference cancellation via exit chart[END_REF] for one iteration. The average complexity for MMSE-IC is reported in [START_REF] Wang | List sphere decoding combined with linear detection-based iterative soft interference cancellation via exit chart[END_REF] as 2O(M t Q2 Q )+O(M 3 t ) for each iteration. These complexities are for a vector of M t symbols, so they must be multiplied for the total number of vectors in the frame (here 30 vectors). As already known [START_REF] Wang | List sphere decoding combined with linear detection-based iterative soft interference cancellation via exit chart[END_REF], LSD complexity is 10 times higher than MMSE. However LSD complexity can be reduced with a smaller list and adjusted clipping level. Considering, for example, the list generation for LSD with a list size of 64 and the symbol expectation for 5 iterations for MMSE-IC, the former has a number of additions/subtractions seven times higher than the latter. Even the difference between the LLR computation and soft mapper and demapper is of two orders of magnitude.

Discussion of the results

MMSE

Discussion of the results

The iterative behavior of LSD detector has been analyzed using EXIT charts. If the a priori LLRs are properly constrained, the divergence problem can be mitigated with a relatively small list size. This last solution has been compared with a linear detector, such as MMSE-IC, in terms of performance and complexity, both for block and fast-fading channel models. In case of fast-fading, for small constellations and system configurations, MMSE-IC has similar performance to LSD. On the other hand, LSD has better BER performance than MMSE-IC when the estimation of the channel conditions remain constant over a frame. Although complexity of LSD is significantly higher than that of MMSE-IC, LSD outperforms MMSE-IC in two iterations. Solution in [START_REF] Mennenga | Iterative soft-in soft-out sphere detection for MIMO systems[END_REF] shows how it is possible to reduce the complexity of the LSD to one half of a traditional LSD, thanks to Sorted QR-decomposition, MMSE preprocessing and Tuple Search. The performed analysis on possible complexity-performance trade-offs can be exploited to extend flexibility of current sphere decoders [3] and design a multi-mode flexible MIMO detector supporting both MMSE-IC and LSD with variable list size.

In such a flexible detector, selection between the executed algorithm and choice of the main parameters should be based on channel conditions and targeted performance.

ASIP implementation of LSD

In chapters 5 and 6, the idea of a multi-mode flexible MIMO detector supporting both MMSE-IC and LSD has been extensively presented and investigated. This chapter, instead, focuses on the implementation aspects of such a kind of detector, whose main feature is the flexibility. Nowadays, one of the most flexible kind of implementation is certainly the Application-Specific-Instruction set-Processor (ASIP) [START_REF] Hoffmann | A novel methodology for the design of application-specific instruction-set processors (ASIPs) using a machine description language[END_REF] [84] [START_REF] Hoffmann | A methodology for the design of application specific instruction set processors (ASIP) using the machine description language lisa[END_REF] [86] [START_REF] Jafri | Rapid Prototyping of ASIP-based Flexible MMSE-IC Linear Equalizer[END_REF].

An ASIP is a programmable microprocessor, where hardware and instruction set are designed together for one special application. It has the main characteristic of combining performance and energy efficiency of dedicated hardware solutions with the flexibility of a programmable solution. Anyway, other popular approaches for the implementation of specific functions in digital systems are exploited. The requirement of very high performance can be satisfied with an Application-Specific-Integrated-Circuits (ASICs) or even a physically optimized ICs, sacrificing completely the flexibility. On the contrary, programmable solutions, such as General-Purpose Processors (GPP), offer more flexibility and faster time-to-market. If some additional processing power is needed, there are specific processors, optimized for signal processing, such as Digital Signal Processors (DSPs), which offer some additional specialized instructions (e.g. Multiply-Accumulate, MAC). More flexibility is, instead, satisfied by programmable devices, like Field Programmable Gate Arrays (FPGAs), which are reconfigurable, at the price in terms of performance, power and cost, making them suitable in particular for prototyping. Among all these alternatives, ASIPs are the best

ASIP design flow

trade-off between performance and flexibility, and represent an intermediate solution between DSPs and FPGAs. Their instruction sets tailored to the application allow faster processing, while their programmability offers the flexibility needed to adapt to changing requirements. MIMO detection is one of the many domains, which can benefit from application-specific processors.

Several options are available to design an ASIP: it can be completely described through an Architecture Description Language (ADL), or obtained after a software programming of an existing processor, or using a so called transport triggered architecture (TTA). Next section provides a description of an ASIP design flow, accompanied by an overview of methodologies and tools.

ASIP design flow

The most popular ASIP design technologies can be divided in four main categories [START_REF] Leupers | From ASIP to MPSoC -Architectures and Design Tools for Communication and Multimedia systems[END_REF]:

ASIP design flow

• Architecture Description Language (ADL) based solutions: they are also known as ASIP-from-scratch, because of the accessibility to each detail of the architecture. Stages of pipeline, number and type of resources and memory structures are completely specified by the designer, through an high-level language. Some example of tools, which adopt this approach, are the CoWare Processor Designer [START_REF]CoWare Processor Designer Homepage[END_REF] and Target IP Designer [START_REF]Target IP Designer Homepage[END_REF]. This method has the highest flexibility and efficiency, but also requires a significant design effort.

• Configurable processor core based solutions: in this case, it is possible to add custom Instruction Set Extension (ISE) to a pre-defined and pre-verified core, so obtaining more efficiency. This approach has certainly less flexibility than ADL based solutions. Tensilica Xtensa [START_REF]Tensilica Xtensa 7 Homepage[END_REF] and ARC ARChitect [START_REF]ARC Configurable Cores Homepage[END_REF] are two examples of such a kind of technology. Moreover also transport triggered architectures (TTAs) are included in this category. TTA is a programmable architecture, where processor is a made of independent function units and register files, which are connected with transport buses and sockets [93]. In conventional processor architectures, data transports are consequences of operations . In this way, the data transmission may become the bottle-neck of implementations, where high amount of data is processed.

In TTAs, the situation is reversed and operations are consequences of data transports. In TTA design, the processor designer has free hands to built the optimal data transmission by adding enough buses between logic and memory. It is then programmed simply by defining the sources and destinations of these transports. The TTA-based Codesign Environment (TCE) [START_REF]TTA-based Codesign Environment (TCE) Homepage[END_REF] is an example of tool, employed to design TTAs.

• Software reconfigurable processors: like Stretch [START_REF]Stretch Software-Configurable Processors Homepage[END_REF] and ADRES [START_REF] Mei | Architecture exploration for a reconfigurable architecture template[END_REF]. They present a fixed hardware architecture with a reconfigurable ISE, which can be modified to customize instructions. This approach has the most restricting degree of freedom with respect to previous solutions.

Independently of the employed technology, the tipical ASIP design flow starts with the identication of the so called "hot spots" [97] of the application and with the definition of an initial architecture and a custom instruction set, both able to 7.1 ASIP design flow efficiently support those hot spots. Then the application is run on the processor and the designer verifies if the target requirements are met. If specifications are not satisfied, the flow is iterated.

Next subsection provides an overview of the ASIP design flow for ADL based solutions.

An ADL based tool: Coware Processor Designer

The ADL based method is the most powerful among all other above approaches, since the processor can be completely specified in all its parts, through an highlevel language. Such a language is more abstract than hardware description languages, such as VHDL of Verilog. This description is accepted by a specialized tool that automatically generates both synthesizable Register Transfer Level (RTL) and software descriptions. Many ADLs have been introduced through the years, like nML [START_REF] Fauth | Describing instruction set processors using nML[END_REF], based on a mixed structural and behavioral model, Sim-nML [START_REF] Rajesh | Processor modeling for hardware software codesign[END_REF], an extended version of the nML formalism, Instruction Set Description Language (ISDL) [START_REF] Hadjiyiannis | Isdl: An instruction set description language for retargetability[END_REF] and Language for Instruction-Set Architecture (LISA) [101] [102].

In this research thesis, a tool, namely CoWare Processor Designer [START_REF] Pees | LISA-machine description language for cycle-accurate models of programmable DSP architectures[END_REF], has been employed to design an ASIP for LSD. CoWare Processor Designer is a widespread commercial ASIP design environment, which is based on LISA [START_REF] Hoffmann | A methodology for the design of application specific instruction set processors (ASIP) using the machine description language lisa[END_REF].

Processor Designer is used to develop a wide range of processor architectures, including architectures with DSP-specific and RISC-specific features as well as SIMD and VLIW architectures. Moreover, processors with complex pipelines can be easily modeled. This includes the ability to describe architectures with complex execution schemes.

The main features of LISA are [START_REF] Hoffmann | A novel methodology for the design of application-specific instruction-set processors (ASIPs) using a machine description language[END_REF]:

1. to provide cycle-accurate processor models, specifying stages of pipeline and mechanisms, like stalls, flushes, reset and operation injection; The LISA machine description provides information consisting of the following model components [START_REF] Hoffmann | A novel methodology for the design of application-specific instruction-set processors (ASIPs) using a machine description language[END_REF]:

• Memory model : lists the registers and memories of the system with their respective bit widths, ranges, and aliasing. The compiler gets information on available registers and memory spaces. The memory configuration is provided to perform object code linking. During simulation, the entirety of storage elements represents the state of the processor, which can be displayed in the debugger. The HDL code generator derives the basic architecture structure.

• Resource model : describes the available hardware resources and the resource requirements of operations. Resources reflect properties of hardware structures that can be accessed exclusively by one operation at a time. The instruction scheduling of the compiler depends on this information. The HDL code generator uses this information for resource conflict resolution.

ASIP design flow

• Instruction-set model : identifies valid combinations of hardware operations and admissible operands. It is expressed by the assembly syntax, instructionword coding, and the specification of legal operands and addressing modes for each instruction. Compilers and assemblers can identify instructions based on this model. The same information is used at the reverse process of decoding and disassembling.

• Behavioral model : it abstracts the activities of hardware structures to operations changing the state of the processor for simulation purposes. The abstraction level of this model can range widely between the hardware implementation level and the level of high-level language (HLL) statements.

• Timing model : it specifies the activation sequence of hardware operations and units. The instruction latency information lets the compiler find an appropriate schedule and provides timing relations between operations for simulation and implementation.

• Microarchitecture model : it allows grouping of hardware operations to functional units and contains the exact micro-architecture implementation of structural components such as adders, multipliers, etc. This enables the HDL generator to generate the appropriate HDL code from a more abstract specification.

After describing the architecture, using these above models, the Processor Designer generates a synthesizable HDL representation and the complete software tool suite automatically. The design flow starts from a LISA 2.0 description, which allows to specify all components, such as stages of pipeline, memories, register files, instructions and pins. Then Processor Designer automatically generates both ISS, complete software tool suite (C-compiler, assembler and linker)

and the RTL implementation description (Verilog HDL, VHDL and System C). Through the simulator, the application can be run and debugged, verifying the processor model and evaluating the performance. If the specifications are not met, the flow comes back to the LISA description, since the design flow is a closed-loop, as shown in Fig. 7.2. When the design goals are completely satisfied, the HDL implementation can be synthesized, evaluating occupied Silicon area, clock frequency and power consumption. It is worth notifying that if if the number of transmitters and receivers is different, the square channel matrix can be obtained, using a mathematical trick [START_REF] Bolcskei | Space-time wireless systems : from array processing to MIMO communications[END_REF]. This is applied in the QR-decomposition, which is not included in the ASIP design.

• Type of modulation: indicated as PAM size. Since a real-valued system has been employed (see section 2.2), this parameter represents the number of PAM symbols, corresponding to a QPSK, 16QAM and 64QAM. So possible choices are 2, 4 and 8. In fact, QPSK has {-1,1}, as corresponding PAM symbols, the 16QAM has {-3,-1,1,3}, and the 64QAM {-7,-5,-3,-1,1,3,5,7}.

• List size: indicated as list size. Currently, the ASIP1 supports a number of candidates up to 64, which is an acceptable range, taking into account that the main problem of LSD is memory requirement due to list, and that a list of 64 is a reliable choice for all the previous constellations, in particular in the block fading scenario (see chapter 6).

Anyway, list and modulation sizes can be easily extended to other values, different from those above indicated, just with minimal modifications, mainly related to the size of memories. The resources of the processor are composed of one data memory and seven register files. The 2M × (2M + 1) Channel Data Mem stores R matrix coefficients and ZF solutions, ỹ, obtained after QR-decomposition. When the ASIP1 starts working, the content of the memory is load into the two corresponding register files (R RF and PSI RF ), in order to be directly read by the processor. During the detection, the PSI RF is also used to save intermediate results, together with The processor has to fulfill five main tasks:

• Babai point selection

• PED computation • ψ computation • SE enumeration • List management
Hardware architecture of each of these processing units is described in the following sections. As for the implementation of SDA and LASDA, the internal 7.2 First suboptimal ASIP of LSD precision has been set to 16 bits, half of them used for the integer part and the other half for the fractional part. Some data are represented with less than 16-bits, as specified in the next paragraphs, and in order to enable the reuse of hardware resources, they are sign extended to 16-bit format. Moreover, a 32 to 16-bit conversion is performed at the outputs of the multipliers and to avoid overflow or underflow problems, outputs are superior or inferior limited.

Babai Point selection

This unit has the role of selecting the Babai Point, in the forward processing, according to eq. (2.14). The complexity , in terms of number of resources, depends only on the cardinality of the modulation, not on the number of antennas. It is quite similar to S block, shown in Fig. 3.13, but extended to cover also the 64QAM modulation. This is a classical divisor, implemented with left shift operations and subtractions, as detailed in Fig. 7.4. It takes ψ l+1 [l] and R l,l , as inputs, and computes the Babai Point, indicated as res, and the initial direction of SE enumeration, indicated as step. If step is equal to 1, the next chosen point will be the closest symbol at right, otherwise the closest at left. Apart from inputs, represented on 16 bits, the Babai point can be set to 4 bits, with a two's complement representation, which is the maximum precision required for the worst case, i.e. 64QAM.

Alternatively the Babai Point selection can be implemented, according to eq. (2.15), as a network of subtractors, multipliers and comparators, as shown in Fig. 7.5. This architecture implies to consider all symbols of the constellation. In this way, the number of resources is directly proportional to the cardinality of the modulation. Cell technology is adopted. The occupied Silicon area is reported on y-axis, while the x-axis shows delays, from about 4.1 ns to the minimum critical path obtained, for each one. A quick look at those results, allow to state that the ad-hoc divisor has better performance than the alternative architecture, both in terms of area and in terms of clock frequency. same complexity, since the precision of their inputs is different. In particular, the multiplication at the bottom of Fig. 7.7(a) is more complex than that at the top, since it involves two 16-bits signals, obtaining a results on 32-bits, to be brought 7.2 First suboptimal ASIP of LSD back to 16 bits.

x x _ + ψ l+1 [l] T l+1 T l e l R l,l s l x - x - x - x - x - R 2,l ψ l [2] ψ l+1 [2] R l-2,l ψ l+1 [l -2] ψ l [l -2] R l-3,l ψ l+1 [l -3] ψ l [l -3] s l R l-1,l ψ l+1 [l -1] ψ l [l -1] R 1,l ψ l+1 [1] ψ l [1] (a) (b)

ψ computation

The aim of this block consists in computing ψ l [i] amounts that will be required at the lower tree levels, according to eq. (3.9). At each level l of the tree, it receives the current visited symbol s l , R i,l and ψ l+1 [i] elements for i = l -1, . . . , 1 and gives ψ l [i] as results. The basic unit is composed by a multiplier and an adder, which are allocated a number of times equal to l -1. The complexity of this block is therefore dependent on number of antennas, but not on the cardinality of the constellation. The necessary hardware to be allocated is specified by the 7.2 First suboptimal ASIP of LSD worst case: for a 4 × 4 system the root level of the tree is l = 7 and the maximum number of basic units, working in parallel, is equal to 6. For smaller systems, some units will not be employed. This unit has to compute the next alternative symbols, according to SE enumeration:

s k l = s k-1 l + 2step k-1 l step k l = -step k-1 l -sign(step k-1 l ) k > 1 (7.1)
As shown in Fig. 7.8, it is a quite simple unit, composed of a multiplexer, an adder, a subtractor, a comparator, a left shift and a two's complement operator.

The number of resources to be allocated is indipendent of number of antennas and cardinality of the constellation. Instead, the range of values that s k l and step k l can assume, clearly depends on the symbols, belonging to the modulation. One of the main issues of LSD is the management of the list, not only in terms of memory requirement, but also regarding how to handle it. If a large list size is preferred, the sorting and storing of symbol vectors quickly becomes the bottleneck of the algorithm. Two main approaches are exploited to maintain the list: memory-based [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF] and register-based. The former provides a more energyefficient but slower solution to the problem, while the latter guarantees an highly optimized and faster hardware, even if it tends to have an high energy consumption. Here the register-based approched has been adopted, since it will provide less energy-efficient, but certainly faster solution to the problem [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF].

The LSD is a generalization of the SD. Rather than finding only the best argument, if finds the best |L| ones. It stores each of these arguments u i and their corresponding value d2 i in a list L i = {u i , d2 i } for i = 1 . . . |L|. Each time a possible argument is found, the LSD checks whether it is better than all arguments in the list, and if so it exchanges them. This search requires an order of |L| comparisons, and is executed for every vector checked inside the sphere.

In particular, each visited leaf, which satisfies the radius constraint, has to be inserted. When the detection starts, the initial radius is set to infinity, i.e. the maximum representable value with the desired precision, and only when the list will be full it will be updated to the biggest ED stored into the list. For this reason, it is useful to maintain the list ordered. In fact, in the ascending order, the first candidate has the smallest ED, corresponding to the ML solution, and the last has the biggest, corresponding to the radius. Later on, if a new leaf has a smaller distance with respect to the radius, it must be inserted, the biggest candidate is eliminated and the radius updated to the new largest element in the list. Shortly, for each candidate found, three activities can be identified: As the latency of inserting a new symbol to the list is very crucial for the overall performance of the LSD algorithm, an efficient data structure is needed for sorting and storing of symbols. Heap data structure [START_REF] Rivest | Introduction to Algorifhnis[END_REF] has been suggested for LSD in [START_REF] Wiesel | Efficient implementation of sphere demodulation[END_REF] and [START_REF] Widdup | A highly-parallel VLSI architecture for a list sphere detector[END_REF] as an efficient algorithmic solution. The work in [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF],

shows an ASIP implementations of a K-best memory-based LSD, with detailed explanation of the heap utilization. Heap is an efficient choice for long lists: comparator networks for constructing binary heaps, presented in [START_REF] Brodal | Comparator networks for binary heap construction[END_REF], have a complexity of order O(|L|log 2 log 2 |L|), in terms of number of comparators, and O(log 2 |L|), in terms of delay.

The bubble sorting algorithm is more suitable for K-best approaches, since it is shown that the cost of sorting is linear with the value of K [START_REF] Wong | A VLSI architecture of a K-best lattice decoding algorithm for MIMO channels[END_REF] [110], and can be employed in a sequential fashion [START_REF] Guo | Algorithm and implementation of the k-best sphere decoding for MIMO detection[END_REF]. Since the K-best is a single-direction searching algorithm, the sorting can take more than one clock to be completed. This is not the case of depth-first LSD, which is double-direction, and the list must be ordered in one clock. A sorting network proposed in [START_REF] Leighton | On probabilistic networks for selection, merging, and sorting[END_REF] has a depth of O(log 2 |L|log 2 log 2 |L|): it makes use of an operation called (m, k)-sort-and-shuffle, which operates on an array of m elements, by first sorting elements in each block of size k, and then shuffling the m/k sorted blocks together. The shuffling simply consists in moving each element from a position to another position of the array, according to a specific rule. The quite complicate structure of this last solution, which also needs to apply a "random" permutation and the recursion [START_REF] Leighton | On probabilistic networks for selection, merging, and sorting[END_REF], makes it more suitable for software application. The heap-sort-based approach is, on the contrary, a good hardware solution, mainly addressed to low-area requirements. But if the main purpose is high data-rate, and, therefore, high clock frequency, a tree-based network of comparators, like for the heap-sort, is probably not the best answer. In this first version of the ASIP, the very basic and straight-forward implementation of the list management unit, whose pseudocode is illustrated in Algorithm 4, has been adopted, as shown in Fig. 7.9. This highly parallel and very easy to implement architecture is very fast, at a price of an increased occupied area, d2_list [2] d2_list [3] 16 d2_list [START_REF] Myllyla | Reduced complexity near-optimal iterative receiver for Wimax full-rate space-time code[END_REF] d2_list [START_REF] Karkooti | FPGA implementation of matrix inversion using QRD-RLS algorithm[END_REF] u_list [START_REF] Myllyla | Reduced complexity near-optimal iterative receiver for Wimax full-rate space-time code[END_REF] u_list [START_REF] Karkooti | FPGA implementation of matrix inversion using QRD-RLS algorithm[END_REF] u_list [1] with respect to above described methods. This is pointed out comparing [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF] and [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF]: the former solution employs heap structure for the list, while the latter make use of our same architecture to manage the list. The list unit in [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] occupies 5400 GE on a 130 nm technology and 100 MHz of clock frequency, while the same unit, implemented with heap structure, occupies 2300 GE, for same technology and frequency. This means about 134% increase of area. On the other hand, the maximum clock frequency obtained [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF] is 150 MHz, versus 280 MHz in [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] (86% more).

> > > < SEL SEL SEL d2_list[1]

Instruction Set Architecture

The ASIP has 5 pipeline stages: employed since the average number of clock cycles, needed to detect a symbol vector, is variable with SNR value: in these case the main loop, which handles forward and backward processing of the tree in the LSD algorithm, is repeated 123 7.2 First suboptimal ASIP of LSD a number of times which is not fixed and not a priori predictable. The JUMP format is represented in Fig. 7.13. As it will be explained later, until the detection is not finished, the program jumps to address1, otherwise to address2.

The specialized instructions, which implement the tree search and synchronize the units presented in subsection 7. This instruction is designed to initialize some internal registers of the ASIP. Through the fields pam size, numb ant and list size in Fig. 7.14, the user can choose the desired system configuration. pam size is the cardinality of the PAM constellation, and can assume values {2, 4, 8}, corresponding respectively to QPSK, 16QAM and 64QAM. The number of transmitters and receivers can be fixed with numb ant, choosing among {2, 3, 4}, corresponding respectively to 2 × 2, 3 × 3 and 4 × 4 MIMO. Finally, the list can have a number of candidates from 1 to 64, thanks to the list size field, which can assume integer values {0, 1, 2, . . . 63}. Since the only operation done by INIT is simply to set some global register to a certain value, this can be done only in one stage of pipeline, the OPF. In this way, this instruction effectively occupies only the first two stages, and is completed in two clocks.

BABAI instruction

This instruction has been initially thought to accomplish the forward processing, which implies to select the Babai Point, and to compute related ψ and PED metrics. For this reason, fields src1 and src2 of the instruction format in Fig. 7.15 are respectively ψ l+1 [l] and R l,l , which are inputs of the Babai selection unit (see Fig. 7.4).

The whole processing has been scheduled in the stages of pipeline, as shown in Fig. 7.16. In the OPF stage, the instruction is decode and operands are load from register files to pipeline registers: an entire row of R RF (R i,l with i = 1, . . . , l), one element T l+1 from P ED RF , and one element ψ l+1 [l] from P SI RF . In the EX1 stage, both Babai selection and ψ computation are performed, during the forward processing, while the PED computation is carried out in EX2. Finally, in the WB stage, results are written into RFs: T l in P ED RF , s l and related step l respectively in u RF and step RF , and all ψ l [i] with i = 1, . . . , l -1 in P SI RF . The forward and backward processings have the common task of calculating the PED and ψ metrics for a symbol, which is the Babai Point during the former and another alternative sibling, according to SE enumeration, during the latter. In order to enable the resource sharing, the BABAI instruction can be used also in the backward processing, disabling the BABAI selection unit. In this case, the input symbol to the ψ computation unit comes from a pipeline register and it is generated by the CHECK instruction, as explained in the following paragraph.

The choice of performing the Babai selection and the computation of the ψ metrics in the same stage comes from data dependency. In the forward visiting, the Babai Point needs the proper ψ element to be computed, according to (2.14). The idea is to design an ASIP, which is not so far from a one-node-per-cycle architecture, also because LSD has an high and variable latency, due to the sequential nature of the algorithm itself.

ψ l+1 [l] R l,l R l-1,l R l-2,l R 1,l ψ l [l -1] ψ l [1] step l s l T l ψ ψ l [l -2] R l,l ψ l+1 [l] s l T l+1
Figure 7.16: BABAI instruction and stages of pipeline. The CHECK instruction has the aim of managing the tree search: through the radius constraint verification, it can decide which will be next level of the tree to be visited. For these purpose, two global registers are allocated: level and up/down. As their names suggests, level contains the current level of the CHECK instruction works along the pipeline. In the OPF, operands are loaded: one element T l from P ED RF , the current symbol and related step respectively from u RF and step RF , and the current level of the tree from the level register. Then, all operations are concentrated in one clock. RC block verifies the radius constraint, according to (2.7) and, based on this, the up/down bit is set to 0 if the forward processing has to be accomplished, also enabling the BABAI selection in

CHECK instruction

Synthesis results

The Coware Processor Designer has been adopted to design the ASIP, describing the processor with LISA language. The tool provides software development suite (simulator, compiler, assembler, debugger and linker), so that, executing the application program, performance can be verified. Moreover, the VHDL code is automatically generated for hardware synthesis. The generated RTL description has been synthesized as ASIC, using Synopsys Design Compiler version Z-2007.03-SP1, on a 0.13 µm CMOS Standard Cell technology. In Table 7.1, the results of synthesis are summarized. The clock frequency is quite low. Before comparing

Improved ASIP: increased clock frequency

Analyzing the LSD in the Listing 7.1 (from line 14 to the end), it can be derived that the current application is able to visit one node per 6 clock cycles. This is due to the sequential nature of the algorithm, which implies data dependency between the results provided by the BABAI instruction and the radius verification of the CHECK. Therefore, the first modification that can be applied to the ASIP in order to increase clock frequency is to distribute the processing in a better way along the pipeline, just breaking each potential critical path. The main modifications involve BABAI and CHECK instructions, as Fig. In Table 7.1, the results of synthesis are summarized. Now, the clock frequency is more than doubled, with respect to the previous ASIP design, while the occupied area is almost the same. Then, Table 7.3 details the area for each block. The external data memory is not included in these results. The architecture can be partitioned in three main units: the pipeline, the register files and the interface for external memory. While interface for channel data memory, indicated as Area M emoryF ile is negligible, the area of register files (Area RF ) represents more than the half (59.5 %) of the whole architecture. In fact, the high memory requirement, mainly due to the list, is one of the major problem of LSD. The To facilitate comparisons, Table 7.7 reports the main features of a number of soft MIMO detector implementations: three different ASIC implementations proposed in [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], [START_REF] Witte | A scalable VLSI architecture for Soft-Input Soft-Output Single Tree-Search Sphere Decoding[END_REF] and [START_REF] Guo | Algorithm and implementation of the k-best sphere decoding for MIMO detection[END_REF] (columns 2 to 4), and two ASIPs of K-Best LSD in [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF] and [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] (columns 5 and 6). Column 7 reports the achieved results for the LSD ASIP implementation.

[l] R l,l step l s l ψ l [1] R 1,l R l-2,l R l-1,l s l R l,l ψ l+1 [l] T l+1 ψ l [l -2] T l ψ l [l -1]

Improved ASIP: increased clock frequency

The soft-output sphere decoder architecture, presented in [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], avoids the complexity related to PED calculation and sorting, employing a close-to Schnorr-Euchner order, with a simple look-up table. Work in [START_REF] Witte | A scalable VLSI architecture for Soft-Input Soft-Output Single Tree-Search Sphere Decoding[END_REF] proposes a VLSI architecture for Soft-In-Soft-Out Single-Tree-Search SD, following the one-nodeper-cycle (ONPC) paradigm, while a modified K-Best SE decoding algorithm is proposed in [START_REF] Guo | Algorithm and implementation of the k-best sphere decoding for MIMO detection[END_REF] to improve the performance of the soft-output KSE with low complexity and low-power features incorporated the VLSI architecture. The ASIP implementation of K-best list sphere detector in [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF] makes use of the transport triggered architecture (TTA): it is based on using memory and heap data structure for symbol vector sorting. This architecture has been improved and presented in [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF], showing low hardware and design complexities, together with various general-purpose properties. Table 7.7 gives for each implementation the corresponding technology, maximum clock frequency (f CK ), area complexity (Area), expressed in equivalent gate count (EG), and average throughput (Av. Throughput). For our work and [START_REF] Witte | A scalable VLSI architecture for Soft-Input Soft-Output Single Tree-Search Sphere Decoding[END_REF] the throughput depends on SNRs, as specified in the comments to the table, while all others presented a fixed one. To evaluate the efficiency of the compared solutions, row 11 gives the Throughput to Area Ratio (TAR).

In order to have a fair comparison, last two rows report respectively throughput and TAR for the processing of the considered system configuration on our ASIP. (6) 5.3 (6) 7.6 (6) @12-17dB L=7,N=5 (1) L=16,N=1 (1) TAR 1.43 0.1-0.9 1.1 0.03 0.3 [Mbps/KEG] @12-17dB Our Th. (4) 0.93-5.16 (8) 0.25-1.58 0.93-5.16 (7) 12.6-32.3 (2) (7) 3.75-4.86 (3)(7) Our TAR (4) 0.01-0.04 0.001-0.01 0.01-0.03 0.02-0.06 (5) 0.03-0.04 (1) N=number of symbol vectors, detected in parallel. (2) Worst case (0dB) and best case(30dB). Also a reduction in the number of clock cycles per node from 6 to about 2.2 has been considered since pipelining-interleaving (see subsection 7.3.3 ) has been applied. (3) Worst case (0dB) and best case(26dB). (4) Throughput and TAR evaluated for SE LSD on our ASIP are reported in the last two rows of each column. The system configurations change from column to column according to the references. (5) This TAR value has been computed considering an estimated area of 556KGE = A RF * 5 + A pipe + Area M emoryF ile (6) This work doesn not take into account the code rate in the computation of the throughput. (7) R has been eliminated in eq. (7.2) for the computation of this value. (8) Worst case (64QAM, L = 64 and 0dB) and best case (64QAM, L = 4 and 26dB). See Table 7.4.

Improved ASIP: increased clock frequency

Looking at Table 7.7, it is clear that having a precise comparison is not easy at all, due to differences especially in the algorithm and in the type of the implementation. In particular, the efficiency of ASIC is at least ten times higher than ASIP. [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF]- [START_REF] Witte | A scalable VLSI architecture for Soft-Input Soft-Output Single Tree-Search Sphere Decoding[END_REF]- [START_REF] Guo | Algorithm and implementation of the k-best sphere decoding for MIMO detection[END_REF] are better than our work by a factor 100, but, apart from [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF] which supports more than one modulation, they are not flexible in terms of number of antennas and constellations. Our work is, instead, comparable with that in [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF]: for low SNR (0dB) 7 of our ASIPs would be necessary to reach the same efficiency, while for high SNR (30dB) it is better by a factor 2. It is worth noticing that results in [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF] are for 5 processors working in parallel. Therefore, as clarified by notes (2) and (5) of the table, in the computation of our throughput, a reduction in the number of clock cycles per node has been considered, since the pipeline can be exploited in a better way, filling empty cycles. A reduction from 6 to 2.2 has been estimated, and clearly the throughput has been multiplied by a factor 5. The increase in terms of area has been considered, using A RF * 5 + A pipe + Area M emoryF ile . Finally, solution [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] is better than our ASIP by a factor between 7.5 and 10. They state to visit a fixed number of 328 nodes to detect one symbol vector, while our ASIP is able to visit an average number of nodes per SNR value that is smaller (less than the half (122@0dB-99@30dB)) for the same case (2 × 2, 64QAM and L = 16). Therefore, this factor is not due to the number of visited nodes, but to the fact that [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] is able to almost meet the one-node-per-cycle constraint (0.74 node per cycle), while our processor needs 6 clocks per node. Moreover, it is important to highlight that the implementation in [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] is targeted for 2 × 2 MIMO system, while our ASIP, when also works for a 2 × 2, is targeted for a 4 × 4, and this produce certainly an effect on complexity. If our ASIP would be designed to support only a 2 × 2 MIMO, the area should be reduced. In particular, it is possible to estimate a reduction of the area of register files by a factor 2. Also the Area pipe should have a reduction, in the ψ computation unit, but it is not easy to estimate it. Therefore, to have a comparison with [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] and also [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], an area value of 115KGE = Area pipe + 0.5Area RF + Area M emoryF ile has been adopted (see TAR values in column 2 and 6). It is worth noticing that, [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF], together with [START_REF] Guo | Algorithm and implementation of the k-best sphere decoding for MIMO detection[END_REF] and [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF], do not take into account the code rate in the computation of the throughput, so, also for our reported throughput, R has been eliminated in Anyway, it is evident that the current design has to be furthermore improved in order to be more competitive with other ASIP implementations of LSD. Next subsection explains a good idea to additionally refine the proposed architecture.

Efficient pipeline usage: the pipeline-interleaving

Another important observation, which can be derived looking at Listing 7.1 (from line 14 to the end), is that the pipeline is not exploited at 100 %, but only around the 40%. A good method to have a more efficient usage of the pipeline is the wellknown "pipeline interleaving" [2]. This solution consists in detecting two or more symbol vectors in parallel, and not allocating as many processors as necessary, but only with one ASIP, exploiting at maximum the pipeline.

The LISA description of the ASIP has been modified in order to support 5 symbol vectors to be detected. Each register file has been allocated 5 times, one for each vector, except for the R RF , since a block-fading scenario has been assumed. Also the interfaces between register files and the pipeline have been modified, so that each instruction can select the right resource at each time. In Table 7.8, the results of synthesis are summarized. Table 7.9 reports the area results of each block of the architecture. better of about 67 % with respect to [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF], showing that the estimation reported in Table 7.7 was quite good. The work in [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] is now better only by a factor between 1.87 and 2.5, with an improvement of 75 %, with respect to the ASIP without "pipeline interleaving". As in Table 7.7, to have a comparison with [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF] and also [START_REF] Paker | A low cost multi-standard near-optimal soft-output sphere decoder: Algorithm and architecture[END_REF], an area value of 323KGE = Area pipe +0.5Area RF +Area M emoryF ile has been adopted (see TAR values in column 2 and 6 of Table 7.10).

We can then state that the "pipeline-interleaving" provides a significant increase of throughput, since now our ASIP has the highest throughput among the other two ASIPs in [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF] and [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF]. The price for the flexibility is, in this case, represented by the area, which is already too much high. This aspect can be certainly improved: probably a better way to manage a such high memory requirement is to have external memories and use a stack to access to them. Moreover, it has to be noticing that 2.6 node per cycle is achieved when all vectors are processed in parallel, i.e. the best case. The detection of one vector can finish before than another one, this means a reduction of the throughput, which can be in part limited with an improved assembly program. (6) 5.3 (6) 7.6 (6) @12-17dB L=7,N=5 (1) L=16,N=1 (1) TAR 1.43 0.1-0.9 1.1 0.03 0.3 [Mbps/KEG] @12-17dB Our Th. (4) 9.8-54.6 (8) 2.6-16.7 9.8-54.6 (7) 9.8-25.1 (2)(7) 39.7-51.5 (3)(7) Our TAR (4) 0.03-0.17 0.005-0.03 0.02-0.10 0.02-0.05 (5) 0.12-0.16 (1) N=number of symbol vectors, detected in parallel. (2) Worst case (0dB) and best case(30dB). The actual reduction in the number of cycles per node is 6 to 2.6.

(3) Worst case (0dB) and best case(26dB). (4) Throughput and TAR evaluated for SE LSD on our ASIP are reported in the last two rows of each column. The system configurations change from column to column according to the references. (5) This TAR value has been computed considering an actual area of 520 KGE. (6) This work doesn not take into account the code rate in the computation of the throughput. (7) R has been eliminated in eq. ( 7.2) for the computation of this value. (8) Worst case (64QAM, L = 64 and 0dB) and best case (64QAM, L = 4 and 26dB). this flexibility is paid in terms of lower throughput and lower throughput to area ratio, than other implementations. In order to enable high throughput and to provide a more efficient usage of the pipeline, the "pipeline-interleaving" of 5 symbol vectors has been developed. Targeting 130 nm CMOS standard cell technology, synthesis results show that the proposed solution achieves the best throughput among other ASIPs of LSD. It is even better than other methods, with a comparable flexibility, such as the reconfigurable MIMO detector implemented using a Graphic Processor Unit (GPU) in [START_REF] Wu | Reconfigurable real-time MIMO detector on GPU[END_REF]. Moreover, throughput results are of the same order of magnitude of most ASIC solutions, able to satisfy many standard requirements. This demonstrates the feasibility of the ASIP approach, which has not been sufficiently exploited up to now. Certainly, further aspects could be investigated and improved, in particular some efforts could already be spent to manage the memory requirement in a more efficient way, with respect to a register-based implementation. This probably enables a reduction of area, improving the TAR.

Conclusions

This research thesis deals with the theme of MIMO detection, both hard and soft. It focuses on algorithmic, architectural and implementation aspects of the Sphere Decoder Algorithm and one of its soft versions, the List Sphere Decoder. From a detailed analysis on the state of the art, software models and architectural issues, some critical aspects become relevant: the throughput and the flexibility. This PhD thesis has the purpose to find solutions to this two problems.

In the hard detection scenario, a detailed study on state of the art MIMO detection algorithms has been conducted. The description of the depth-first Schnorr Euchner Sphere Decoder Algorithm, which represents the starting point of this research thesis, has been presented. Also, other versions of SDA, exploited in literature, are introduced. Then a modified Sphere Decoder Algorithm has been proposed. While most of state of the art solutions achieve performance that is close to ML, this research work faces the problem of a high throughput full ML implementation. The look-ahead, pipelining and retiming techniques, combined with a modified search strategy (Test & Restart), produce a significant increase of throughput, with no loss of error rate performance. The VHDL design of the presented solution, called LASDA (Look-ahead SDA), has been targeted for 4 ×4 MIMO system and 16QAM modulation. Synthesis results on a 130 nm technology show a throughput speedup of 92% at SNR = 20 dB , with respect to a serial unpipelined SDA solution, and a limited additional complexity of 24% in terms of occupied area.

It is important to underline that this high throughput ML solution can easily be applied for most soft-output detection schemes. The main advantage that can be obtained is an increase of about 50 % of the initial clock frequency.

In the soft detection scenario, the idea of a multi-mode flexible MIMO detector has been presented. This idea is supported by a detailed analysis of existing hard and soft MIMO detector implementations. The key word in this context is the flexibility, which can be seen in three different meanings: performancecomplexity trade-offs, the capability of supporting multiple antennas and modulation orders, and the adaptability to change the detection algorithm according to channel condition and targeted performance. In order to achieve the maximum degree of flexibility, among the soft versions of SDA, the List Sphere Decoder has been chosen. In fact, it is the easiest extension of a traditional depth-first hard SDA, and offers some parameters, such as the size of the list and the LLR clipping, which can be easily tuned, to obtain the desired performance-complexity trade-off. The idea is a multi-algorithm detector, able to combine performance of LSD and complexity of a linear detector, such as Minimum-Mean-Squared-Error-Interference-Canceller (MMSE-IC).

To exploit the previous idea, a detailed convergence and flexibility analysis on LSD has been conducted. In particular, the iterative behavior of LSD detector has been analyzed using EXIT charts, in order to deeply understand the problem of divergence. Moreover, the LSD has been compared with MMSE-IC, in terms of performance and complexity, both for block and fast-fading channel models. MMSE-IC has similar performance to LSD for small constellations and system configurations, in the fast-fading scenario. On the other hand, LSD has better BER performance than MMSE-IC when the estimation of the channel conditions remain constant over a frame. Although the complexity of LSD is at least ten times higher than that of MMSE-IC, LSD is able to outperform MMSE-IC in two iterations. There are solutions in literature, showing how it is possible to reduce the complexity of the LSD. Therefore, the performed analysis on possible complexity-performance trade-offs can be furthermore exploited to extend flexi-bility and to support again the idea of a multi-mode detector.

The implementation of LSD is the first step towards the achievement of the presented idea and the ASIP approach has been adopted, to obtain the required trade-off between flexibility and performance. After a first suboptimal ASIP architecture of the list generation unit of LSD, an improved version in terms of clock frequency has been presented. The ASIP flexibility allows its reuse for a 2 × 2, 3 × 3 and 4 × 4 MIMO systems, with QPSK, 16QAM, and 64QAM, and list size from 1 to 64. At the best of our knowledge, this is the first ASIP of LSD, supporting multiple antennas, modulation orders and list sizes. When targeting a 130 nm technology, the proposed architecture enables lower throughput and lower throughput to area ratio than other dedicated (ASIC based) state of the art implementations. The "pipeline interleaving" of 5 symbol vectors has been developed, obtaining an increase of throughput by a factor 10.6, by far exceeding other ASIPs, exploited in literature. Moreover, this results are also of the same order of magnitude of those of ASICs. This shows the effectiveness of the ASIP approach, combined with the "pipeline interleaving" method. It even allows to exceed ASICs performance, with many more symbols vector in parallel, but paying with an increased area. This is the price for the flexibility.

From short term perspectives, further aspects of the presented ASIP architecture could be investigated and improved. In particular some additional efforts should be spent to manage the memory requirement in a more efficient way, with respect to a register-based implementation. For example, the memory-based approach could be employed in combination with a data structure, like a FIFO. This methods probably allows a reduction of area, making the solution more competitive with the state of the art.

From the mean and long term work perspective, the LLR generation unit has to be designed, in order to complete the LSD detector. After that, the possibility that LSD and MMSE-IC share some resource has to be investigated, in order to modify the architecture, supporting both algorithms. This is, probably, another possible solution to increase the throughput.

2. 1

 1 Graphical example of an hypersphere . . . . . . . . . . . . . . . . 2.2 Tree for a 2 × 2-MIMO system and a QPSK modulation. . . . . . 2.3 Schnorr-Euchner enumeration around Babai Point. . . . . . . . .3.1 DFG representation of the computation y[k] = x[k] + ay[k -1]. . 3.2 The two steps look-ahead DFG of computation y[k] = x[k]+ay[k-1].3.3 The two steps look-ahead DFG with pipelining and retiming of computation y[k] = x[k] + ay[k -1]. . . . . . . . . . . . . . . . . . 3.4 The DFG representation of SDA (Forward processing). . . . . . . 3.5 The DFG representation of SDA (Forward processing) after pipelining. Registers D 3 , D 4 , D 5 have been inserted. . . . . . . . . . . . 3.6 DFG representation of LASDA (Forward processing) after lookahead. Retiming is applied on cut-sets CS 1 and CS 2 . . . . . . . . 3.7 DFG representation of LASDA (Forward processing) after lookahead, retiming and pipelining. . . . . . . . . . . . . . . . . . . . 3.8 Scheme of the transmitter and the receiver. . . . . . . . . . . . . . 3.9 BER (a) and iterations (IT)(b) of SDA and LASDA. . . . . . . . 3.10 Flux diagram of the LASDA with Test & Restart strategy. . . . . 3.11 Example of the tree search with the Test & Restart strategy. . . . 3.12 BER (a) and iterations (IT)(b) of SDA and LASDA with Test & Restart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 Scheme of the S block. . . . . . . . . . . . . . . . . . . . . . . . . 3.14 Points of a 4-PAM constellation. . . . . . . . . . . . . . . . . . . . 3.15 High level implementation architectures for LASDA scheme. . . . v LIST OF FIGURES

51 4. 1

 511 and this work, at SNR=22dB. 1/Th indicates the inverse of the average throughput. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . General scheme of a transmitter and a receiver with no feedback. 55 4.2 FER of a traditional Hard-Output ML Decoder and the Soft-Output Sphere Decoder, implemented in [4](MIMO-OFDM System,4×4MIMO, 16-QAM, 64 tones, R = 1/2 convolutional code (K = 7, [133o, 171o]), random interleaver, 1024 bits/codeblock, TGn Type C channel model, BCJR decoder). . . . . . . . . . . . . . . . . . . 56 4.3 General scheme of the receiver with feedback. . . . . . . . . . . . 56 4.4 Scheme of transmitter and receiver of an IDSM-ST system with B-PSK modulation . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.5 Block diagram of ESE . . . . . . . . . . . . . . . . . . . . . . . . 66 4.6 Block diagram of Apriori stat block . . . . . . . . . . . . . . . . . 68 4.7 Block diagram of cov block . . . . . . . . . . . . . . . . . . . . . . 69 4.8 Computation of diagonal elements in cholesky block. . . . . . . . 70 4.9 Computation of not-diagonal elements cholesky block. . . . . . . . 70 4.10 Computation of diagonal elements in invs block . . . . . . . . . . 72 4.11 Computation of non-diagonal elements in invs block . . . . . . . . 72 4.12 Block diagram of f block. . . . . . . . . . . . . . . . . . . . . . . 73 4.13 Block diagram of g block. . . . . . . . . . . . . . . . . . . . . . . 73 4.14 Block diagram of antenna n block. . . . . . . . . . . . . . . . . . 74 5.1 BER, shown in [5], of a traditional Hard-Output Sphere Decoder, the List Sphere Decoder and the Max-Log ML-APP. Coded 4 x 4 MIMO system, 16-QAM, Fast-fading channel, rate 1/2, length of the code-block is 1024 bits and the code has constraint length K = 7 with generator polynomials [133 0 ,171 0 ]. . . . . . . . . . . . . 80 5.2 FER of [6] (4 × 4MIMO, 64QAM, Frame source= 120bits, Channel matrix constant over 240bits (10 vectors of symbols), R=1/2 convolutional code). . . . . . . . . . . . . . . . . . . . . . . . . . . 80 vi LIST OF FIGURES 5.3 FER of different solution, reported in [7] (4 × 4 and 64-QAM, R = 1/2 [7 5] convolutional code, Channel matrix constant over a frame, frame size=10 vectors (24bits per symbol, 10 symbols), Viterbi decoder). . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 BER of a full-rate space-time block code (FR STBC) equalizer and decoder (red curves) without iterations, shown in [8]. . . . . . . . 5.5 BER of a full-rate space-time block code (FR STBC) equalizer and decoder (red curves) with 4 iterations, shown in [8]. . . . . . . . . 5.6 FER of different solution, reported in [9] (IEEE 802.11n 2×2MIMO and 64QAM, channel model D, 20 Mhz bandwidth and coding rates 5/6 and 2/3). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6. 1

 1 Fig. 3.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Synthesis results of computational blocks in the whole architecture: occupied area at the maximum clock frequency f ck = 487 MHz. Rows 2 to 8 refer to processing blocks required for SDA; rows 9 and 10 refer to the additional component needed to support LASDA 3.4 Comparisons with other works . . . . . . . . . . . . . . . . . . . .

for a 4 ×

 4 4MIMO and 64-QAM. . . . . . . . . . . . . . . . . . . . . . . . . ix LIST OF TABLES 5.5 Area results of different implementations of QR-decomposition for MIMO detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Setup of the conducted simulations . . . . . . . . . . . . . . . . . 6.2 Complexity estimation with a 4 × 4-MIMO and 16-QAM for LSD (list of 64, BER of 10

Figure 2 . 1 :

 21 Figure 2.1: Graphical example of an hypersphere

Figure 2 . 2 :

 22 Figure 2.2: Tree for a 2 × 2-MIMO system and a QPSK modulation.

Figure 2 . 3 :

 23 Figure 2.3: Schnorr-Euchner enumeration around Babai Point.

Figure 3 . 1 :

 31 Figure 3.1: DFG representation of the computation y[k] = x[k] + ay[k -1].

2 Figure 3 . 2 : 2 Figure 3 . 3 :

 232233 Figure 3.2: The two steps look-ahead DFG of computation y[k] = x[k]+ay[k -1].

Figure 3 . 4 :

 34 Figure 3.4: The DFG representation of SDA (Forward processing).

Figure 3 . 5 :

 35 Figure 3.5: The DFG representation of SDA (Forward processing) after pipelining. Registers D 3 , D 4 , D 5 have been inserted.

3. 3

 3 Look-ahead optimization of SDA reduced by inserting pipelining registers, because blocks S, DI and PED are not part of a loop: the pipelined DFG is shown in Fig. 3.5, where registers D 3 , D 4 , D 5 have been inserted. In the new DFG, the critical path is now placed along the loop including S block and ψ[i] blocks (loop 1 = S block → ψ[i] block → S block):

  ) represents now the recursion of the look-ahead SDA and a new DFG can be drawn for the modified SDA, as shown in Fig.3.6. It is obtained from Fig. 3.5 by simply inserting the additional operations resulting from the look-ahead transformation: the ψ block implements (3.17), while registers D 4 to D 9 introduce required delays. All other blocks perform the same operations as in Fig. 3.5. Three of the updated ψ are now directly used: ψ l+2 [l + 1] (output of register D 4 ) is still used by DI block, ψ l+3 [l] and ψ l+3 [l + 1], two cycles delayed versions of ψ l+1 [l] and ψ l+1 [l + 1] (through registers D 4 , D 6 , D 7 and D 8 ), feed the new ψ block, which computes ψ l+1 [l], according to eq. (3.17). Register D 9 is also required to generate s l+2 from s l+1 .As an effect of the applied look-ahead transformation, the outer feedback loop in Fig. 3.6 (S block → ψ[i] block → ψ block → S block) includes additional registers (D 4 , D 6 , D 7 and D 8 ) that can be properly shifted to cut the combinational 3.3 Look-ahead optimization of SDA x

Figure 3 . 6 :

 36 Figure 3.6: DFG representation of LASDA (Forward processing) after lookahead. Retiming is applied on cut-sets CS 1 and CS 2 .

3. 3

 3 Look-ahead optimization of SDA delay (retiming). The key requirement is to split the critical path formed by S and ψ[i] blocks in Fig.3.6. In order to increase the throughput, the cut-set retiming technique[START_REF] Parhi | VLSI Digital Signal Processing Systems[END_REF] can be exploited to move registers in suitable positions. The one cycle delay introduced by registers D 4 and D 6 can be moved from the outputs to the input of ψ[i] block by removing the two registers and feeding ψ[i] block with signal s l+1 , which is already available at register D 3 (cut-set indicated as CS 1 in Fig.3.6). Moreover delay introduced by registers D 7 , D 8 and D 9 can be moved from the inputs to the output of ψ block by removing D 7 , D 8 and D 9 and inserting the new register D 10 in Fig. 3.7. The ψ[i] blocks now receive symbol s l+1 (output of register D 3 ) instead of s l : as a consequence, all signals in ψ[i] blocks are shifted by one cycle (cut-set indicated as CS 2 in Fig. 3.6). Thus outputs ψ l+2 [l] and ψ l+2 [l+1] are directly applied to the input of ψ and DI blocks, with no need of registers. We call this modified algorithm LASDA (Look-ahead SDA). The loop 1 in the DFG of Fig. 3.5 includes S and ψ[i] blocks and it is distributed along two clock cycles. The path composed by S, DI and PED blocks, instead, is distributed along three clocks, as shown in Fig. 3.5. The outer loop in the LASDA DFG of Fig. 3.7 contains three blocks (S, ψ[i]

Figure 3 . 7 :

 37 Figure 3.7: DFG representation of LASDA (Forward processing) after lookahead, retiming and pipelining.

3. 3 Figure 3 . 8 :

 338 Figure 3.8: Scheme of the transmitter and the receiver.

Figure 3 . 9 :

 39 Figure 3.9: BER (a) and iterations (IT)(b) of SDA and LASDA.

Fig. 3 .

 3 Fig. 3.10 reports the flux diagram of LASDA with Test & Restart strategy. It is worth clarifying here that step 3 does not lead to any tree pruning, which only occurs after obtaining a PED greater than current C. When s l = s l , the

Figure 3 . 10 :

 310 Figure 3.10: Flux diagram of the LASDA with Test & Restart strategy.

Figure 3 . 11 :

 311 Figure 3.11: Example of the tree search with the Test & Restart strategy.

3. 3 Figure 3 . 12 :

 3312 Figure 3.12: BER (a) and iterations (IT)(b) of SDA and LASDA with Test & Restart.

Figure 3 . 13 :

 313 Figure 3.13: Scheme of the S block.

Figure 3 . 14 :

 314 Figure 3.14: Points of a 4-PAM constellation.

Fig. 3 .

 3 Fig. 3.15 shows the implementation architecture for the whole LASDA based detector. The datapath architecture includes three fundamental components:

  .3 reports the minimum combinational delay for additional blocks in the whole architecture of LASDA, providing results for the CMP block used to manage the Test & Restart search strategy, the ALT block in the TRU and R and Ψ memories. Memories are obtained by means of a RAM generator.

Figure 3 . 16 :

 316 Figure 3.16: Area-delay comparison between solutions in[1],[2],[3] and this work, at SNR=22dB. 1/Th indicates the inverse of the average throughput.

mathematician

  Richard Hamming pioneered this field in the 1940's and invented the first FEC code, the Hamming[START_REF] Bhagawat | Dynamically reconfigurable soft output mimo detector[END_REF]4) code, in 1950. The carefully designed redundancy allows the receiver to detect and correct a limited number of errors occurring anywhere in the message without the need to ask the sender for additional data. FEC is therefore applied in situations where retransmissions are relatively costly, or impossible such as broadcasting to multiple receivers. Errorcorrecting codes are usually distinguished between convolutional codes and block codes. The convolutional codes are processed on a bit-by-bit basis and they are particularly suitable for hardware implementation. The Viterbi decoder allows optimal decoding for such a king of codes. The block codes are processed on a block-by-block basis. Early examples of block codes are repetition codes, Hamming codes and multidimensional parity-check codes. They were followed by a number of efficient codes, like the Reed-Solomon codes, which were the most notable due to their current widespread use. Turbo codes and Low-Density Parity-Check codes (LDPC) are relatively new constructions that can provide almost optimal efficiency.

Figure 4 . 1 ,

 41 the MIMO detector receives the channel observations and the received signal vector and produces the soft information, which becomes input of the decoder. It is also called Soft-Output detection-decoding, and it is able to improve performance of coded systems up to 3 dB of SNR (see Figure4.2), with respect to the hard-output case.

Figure 4 . 1 :

 41 Figure 4.1: General scheme of a transmitter and a receiver with no feedback.

Figure 4 . 2 :

 42 Figure 4.2: FER of a traditional Hard-Output ML Decoder and the Soft-Output Sphere Decoder, implemented in [4](MIMO-OFDM System,4 × 4MIMO, 16-QAM, 64 tones, R = 1/2 convolutional code (K = 7, [133o, 171o]), random interleaver, 1024 bits/codeblock, TGn Type C channel model, BCJR decoder).

Figure 4 . 3 :

 43 Figure 4.3: General scheme of the receiver with feedback.

Figure 4 . 4 :) j are 4 . 1

 4441 Figure 4.4: Scheme of transmitter and receiver of an IDSM-ST system with B-PSK modulation

(4. 4 ) 4 . 1

 441 Complexity evaluation of a soft-output MIMO detector where m is the modulation efficiency and Pr x (n) j = d denotes the a priori probability that x (n) j is equal to d and it can be computed by inverting (4.4):

4. 1

 1 Complexity evaluation of a soft-output MIMO detector 4.14a: max apr = 0 For m = 0, . . . , M1exp -max apr f act var app2 = Const[0] • var app1 var app3 = var app1 var app4 = (Const[0]) 2 • var app1 For m = 0, . . . , M1 -2

Figure 4 . 5 : 4 . 1

 4541 Figure 4.5: Block diagram of ESE

4. 1

 1 Complexity evaluation of a soft-output MIMO detector

Figure 4 . 6 :

 46 Figure 4.6: Block diagram of Apriori stat block

Figure 4 . 7 :

 47 Figure 4.7: Block diagram of cov block

Fig. 4 .

 4 Fig. 4.8 and 4.9 show the block diagrams respectively for the computation of diagonal and not-diagonal elements.

Figure 4 . 8 :

 48 Figure 4.8: Computation of diagonal elements in cholesky block.

Figure 4 . 9 :

 49 Figure 4.9: Computation of notdiagonal elements cholesky block.

4. 1

 1 Complexity evaluation of a soft-output MIMO detector 4.1.2.5 f block

Figure 4 . 10 :

 410 Figure 4.10: Computation of diagonal elements in invs block

Figure 4 . 11 :

 411 Figure 4.11: Computation of nondiagonal elements in invs block

Figure 4 . 12 :

 412 Figure 4.12: Block diagram of f block.

Figure 4 . 13 :

 413 Figure 4.13: Block diagram of g block.

{QPSK

  and 16QAM}, has been synthesized on a 130 nm CMOS Standard Cell technology, using Synopsis Design Compiler version Z-2007.03-SP1. The internal precision has been set to 22 bits 1 , which guarantees almost the same performance as the floating point model. Tab. 4.3 shows the detailed silicon area results for each block of the architecture. The total area, reported in the last row, of 852194um 2 is related to a sequential architecture and the maximum clock frequency of it is f ck = 100MHz. As shown in Table 4.3, the most complex units are f and antenna n blocks, because of their strong parallelism. Memories are

Figure 4 . 14 :

 414 Figure 4.14: Block diagram of antenna n block.

Figure 5 . 1 :Figure 5 . 2 :

 5152 Figure 5.1: BER, shown in [5], of a traditional Hard-Output Sphere Decoder, the List Sphere Decoder and the Max-Log ML-APP. Coded 4 x 4 MIMO system, 16-QAM, Fast-fading channel, rate 1/2, length of the code-block is 1024 bits and the code has constraint length K = 7 with generator polynomials [133 0 ,171 0 ].

Figure 5 . 3 :

 53 Figure 5.3: FER of different solution, reported in [7] (4 × 4 and 64-QAM, R = 1/2 [7 5] convolutional code, Channel matrix constant over a frame, frame size=10 vectors (24bits per symbol, 10 symbols), Viterbi decoder).

Figure 5 . 4 :

 54 Figure 5.4: BER of a full-rate spacetime block code (FR STBC) equalizer and decoder (red curves) without iterations, shown in [8].

Figure 5 . 5 :

 55 Figure 5.5: BER of a full-rate spacetime block code (FR STBC) equalizer and decoder (red curves) with 4 iterations, shown in [8].

Figure 5 . 6 :

 56 Figure 5.6: FER of different solution, reported in [9] (IEEE 802.11n 2 × 2MIMO and 64QAM, channel model D, 20 Mhz bandwidth and coding rates 5/6 and 2/3).

Figure 5 . 7 :

 57 Figure 5.7: FER of [6] (4× 4MIMO and 16QAM, R=1/2, Source frame=512bits).

. 1 ,Figure 6 . 1 :

 161 Figure 6.1: Scheme of the MIMO transmitter and receiver.

Figure 6 . 2 :

 62 Figure 6.2: EXIT charts and BER performance for LSD and MAP decoder with different SNR values and a list size of 512 (a,b).

6. 2 Figure 6 . 3 :

 263 Figure 6.3: EXIT charts and BER performance for LSD and MAP decoder with different SNR values and a list size of 64 (a,b).

Figure 6 . 4 :

 64 Figure 6.4: Distribution of LLRs at the output of the LSD (16-QAM, 4×4-MIMO, list size of 64, block-fading channel model and E b /N 0 = 10dB).

Figure 6 . 5 :

 65 Figure 6.5: EXIT chart and BER performance for LSD and MAP decoder with different SNR values and a list size of 64 (a,b) with the proposed solution in [10].

Figure 6 . 6 :

 66 Figure 6.6: BER comparison between LSD (list size 64) and MMSE for different modulations and block-fading channel.

Figure 6 . 7 :

 67 Figure 6.7: BER comparison between LSD (list size 256 for QPSK and 512 for 16QAM and 64QAM) and MMSE for different modulations and fast-fading channel.

6. 3

 3 Comparisons between LSD and MMSE-IC 6.3.3 Block and Fast Fading Channel for a 2 × 2-MIMO system Considering flexibility requirements, it is important to see what happens also for a different number of antennas. Fig. 6.8(a)(b) shows results for 2 × 2-MIMO and 16-QAM, both for block and fast-fading.

Figure 6 . 8 :

 68 Figure 6.8: BER comparison between LSD (list size 64) and MMSE for 2 × 2-MIMO, 16-QAM, block (a) and fast-fading channel (b).

Figure 7 . 1 :

 71 Figure 7.1: A complexity-flexibility trade-offs for different approaches for implementation in digital systems [11].

2 .

 2 extension of the target class of processors including single instruction multiple data, VLIW, and super-scalar architectures of real-world processor architectures; 7.1 ASIP design flow 3. different levels of abstraction in the behavioral descriptions of parts of the process model: detailed bit-true description for simulation and implementation and assignment to arithmetical function for the instruction selection task of the compiler are distincted. 4. C/C++ based: LISA includes pure C/C++ behavioral operation description; 5. complex instruction coding schemes and instruction aliasing supported. LISA descriptions are composed of resources and operations. The resources are the storage objects: registers, memories and pipelines. The operations, instead, are the basic objects in LISA. They represent the designers view of the behavior, the structure, and the instruction set of the programmable architecture. Moreover, the high degree of automation of Processor Designer reduces the time for developing the software tool suite and hardware implementation of the processor: in this way, designers can mainly focus on architecture exploration and development. The usage of a centralized description of the processor architecture ensures the consistency of the Instruction-Set Simulator (ISS), software development tools (compiler, assembler, and linker) and RTL implementation, minimizing the verification and debug effort.

7. 2 Figure 7 . 2 :

 272 Figure 7.2: LISA design flow [11].

7. 2

 2 First suboptimal ASIP of LSDAs already described in chapter 6, the LSD is composed of two main blocks: list generation, performed only in the first iteration, and LLRs computation, performed at each iteration. Chosen the system and the list size, the former has the aim of finding the |L| candidates, which are nearest to the received signal vector. The number of clock cycles needed to fulfill this object is variable, depending on SNR value. The LLRs computation unit has to compute LLRs, based on the list: so this activity takes a constant number of clocks. Therefore, the complete architecture of LSD has to reflect this structure. It is composed of two ASIPs: the first devoted to list generation and the second to LLR computation. The rest of this thesis reports a detailed description of the ASIP1 (list generation), while the design of the ASIP2 (LLR computation) has been left to future works.

7. 2

 2 First suboptimal ASIP of LSD 7.2.1 Flexibility parameters and architectural choices

Fig. 7 .•

 7 Fig. 7.3 shows the high-level architecture of ASIP1, where memories, register files and input parameters are indicated. The considered flexibility parameters are three: • Number of antennas: indicated as M in Fig. 7.3. Through this parameter, the user can choose the number of transmitters and receivers. Here, the supported values are 2, 3 and 4, which are respectively for 2 × 2, 3 × 3 and 4 × 4 MIMO systems. It is worth notifying that if if the number of transmitters and receivers is

7. 2 Figure 7 . 3 :

 273 Figure 7.3: High level architecture of ASIP1.

Fig. 7 .

 7 6 reports synthesis results of both architectures using Synopsys Design Compiler version Z-2007.03-SP1. A 0.13 µm CMOS Standard

7. 2

 2 First suboptimal ASIP of LSD -

Figure 7 . 4 :

 74 Figure 7.4: Scheme of the Babai selection unit.

7. 2

 2 First suboptimal ASIP of LSD

Figure 7 . 5 :

 75 Figure 7.5: Alternative architecture for the Babai Point selection unit.

Figure 7 . 6 :

 76 Figure 7.6: Area-delay graph for two implementations of the Babai Point selection.

Figure 7 . 7 :

 77 Figure 7.7: Schemes of the PED computation (a) and ψ computation (b) units.

Figure 7 . 8 :

 78 Figure 7.8: Scheme of the SE enumeration unit.

7. 2

 2 First suboptimal ASIP of LSD 7.2.1.5 List management

1 .

 1 Position finder: it consists in finding the right position in the list; 2. Insertion: it implies to right shift all next candidates, with respect to the current position of the new argument, and to insert the new one. In this way, the last element is automatically eliminated; 7.2 First suboptimal ASIP of LSD 3. Radius update: the radius is updated to the PED of the last element in the list.

1 Figure 7 . 9 :

 179 Figure 7.9: Scheme of the list management unit.

Figure 7 . 13 :

 713 Figure 7.13: Instruction format of JUMP.

Figure 7 . 14 :

 714 Figure 7.14: Instruction format of INIT.

7. 2 Figure 7 . 15 :

 2715 Figure 7.15: Instruction format of BABAI.

7. 2

 2 First suboptimal ASIP of LSD

Figure 7 . 17 :

 717 Figure 7.17: Instruction format of CHECK.

7. 2 1 Figure 7 . 18 :

 21718 Figure 7.18: CHECK instruction and stages of pipeline.

Figure 7 . 19 :

 719 Figure 7.19: Modified BABAI instruction and stages of pipeline.

7. 3

 3 Improved ASIP: increased clock frequency eq. (7.2).

144 7 . 4

 74 Discussion of the results7.4 Discussion of the resultsA first suboptimal ASIP implementation of the list generation unit of LSD has been presented. A description of architectural choices and flexibility parameters is detailed. Results of synthesis are also provided. Then, an improved version of the ASIP in terms of clock frequency is given and compared with other state of the art implementations. At the best of our knowledge, this is the first ASIP of LSD, supporting multiple antennas, modulation orders and list sizes. But

  -6 ) and MMSE-IC . . . . . . . . . . . . . . 7.1 Synthesis results of LSD ASIP . . . . . . . . . . . . . . . . . . . . 7.2 Synthesis results of improved LSD ASIP . . . . . . . . . . . . . . 7.3 Detailed Area results of improved LSD ASIP . . . . . . . . . . . . 7.4 Throughput of the improved LSD ASIP for a 2 × 2 MIMO system. 7.5 Throughput of the improved LSD ASIP for a 3 × 3 MIMO system. 7.6 Throughput of the improved LSD ASIP for a 4 × 4 MIMO system.

	Quand je vous aimerai? Ma foi, je ne sais pas,
	Peut-être jamais, peut-être demain. Mais pas
	aujourd'hui, c'est certain.
	L'amour est un oiseau rebelle Que nul ne peut
	apprivoiser, Et c'est bien en vain qu'on
	l'appelle, S'il lui convient de refuser. Rien n'y
	fait, menace ou prière, L'un parle bien, l'autre
	se tait: Et c'est l'autre que je préfère, Il n'a
	xi

7.7 Comparisons with the State of the Art . . . . . . . . . . . . . . . 7.8 Synthesis results of improved LSD ASIP with "pipeline interleaving"140 7.9 Detailed Area results of LSD ASIP with "pipeline interleaving" . 7.10 Comparisons of the ASIP with "pipeline interleaving " with the State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . x Listings 7.1 LSD assembly code . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.2 LSD assembly code with "pipeline interleaving" . . . . . . . . . . 142 rien dit mais il me pla ît. L'amour! L'amour! L'amour! L'amour! L'amour est enfant de Bohème, Il n'a jamais, jamais connu de loi; Si tu ne m'aimes pas, je t'aime: Si je t'aime, prends garde à toi! Si tu ne m'aimes pas, Si tu ne m'aimes pas, je t'aime! Mais, si je t'aime, Si je t'aime, prends garde à toi! Si tu ne m'aimes pas, Si tu ne m'aimes pas, je t'aime! Mais, si je t'aime, Si je t'aime, prends garde à toi! L'oiseau que tu croyais surprendre Battit de l'aile et s'envola... L'amour est loin, tu peux l'attendre; Tu ne l'attends plus, il est là! Tout autour de toi, vite, vite, Il vient, s'en va, puis il revient... Tu crois le tenir, il t'évite, Tu crois l'éviter, il te tient. L'amour! L'amour! L'amour! L'amour! L'amour est enfant de

2 .

 2 Spatial multiplexing: an high rate signal is split into multiple lower rate streams and each stream is transmitted from a different transmit antenna in

the same frequency channel. If these signals reach the receiver antenna with sufficiently different spatial signatures, they are equivalent to almost parallel channels and it is possible to separate them. The spatial multiplexing is a very powerful technique, able to improve the channel capacity at high signalto-noise (SNR) ratio values. The maximum number of spatial streams is limited by the minimum between the number of transmitters and receivers.

  , obtaining the Babai Point s l from the received ψ l+1 [l]. DI block implements (2.13): the ED e l is generated from symbol s l and ψ l+1 [l]. Block PED in the DFG implements (2.8) to update PED metrics.

	3.3.1 DFG representation
	Starting from equations (2.8) to (2.14), the obtained DFG is represented in Fig.
	3.4 for the forward processing of SDA.
	To make more readable the DFG in Fig. 3.4, main operations are grouped
	in blocks: the S block implements (2.14)

Table 3 . 1 :

 31 Combinational delay (t pd min ) of computational blocks in forward processing. Rows 2 to 5 refer to processing blocks required for SDA; row 6 refers to the additional component needed to support LASDA

	Block S block	t pd min [ns] 2.05
	ψ[i] block	1.31
	DI block	1.31
	PED block	1.48

  block + t DI block + t P ED block = 4.84ns (3.10)3.3 Look-ahead optimization of SDAwhere t S block , t DI block and t P ED block are the delays associated respectively to blocks S, DI and PED. The delay along the identified critical path can be easily

		S Block eq. (2.14)
	Block	DI
		Block
		eq. (2.13)
		PED
		Block
		eq. (2.8)

  are not critical, as they include faster operations than loop 1 . Therefore loop 1 is the actual throughput bottleneck of the SDA.

	t pipe SDA c.p.

∼ = t S block + t ψ block = 3.36ns (3.11)

Table 3 .

 3

	t LASDA c.p.

3, last row): resulting delay is 1.65 ns. As in the new DFG, registers are present at the input and output of each processing block, the critical path corresponds to the longest block delay, which is equal to 2.05 ns (S block). The critical path delay of the LASDA DFG, t LASDA c.p. , is then shorter than t SDA c.p. . ∼ = t S block = 2.05ns < t SDA c.p. = 4.84ns (3.18) If compared with the worst case delay estimated for SDA, this result shows a 58% improvement in terms of clock frequency, as demonstrated in (3.18).

  best symbol choice) and set s l = s

		3.4 Architecture design
		(k l )
		l
	27:	goto 12
	28: end if
	29: if l < M then
	30: 31:	l ← l + 1 goto 23
	32: end if

CU Mem PED Block DI PED Block Block Block S Block Mem R FU Block D Block ALT BU TRU S Block D CMP Block Mem

  .[START_REF] Marsch | Smart candidate adding: A new low-complexity approach towards near-capacity MIMO detection[END_REF] In order to ensure that a new node is expanded at each clock cycle, a new, alternative metric must be available also after a pruning operation has taken place. Thus, when a given node p is reached, two candidate nodes are concurrently computed: the first one is a direct son of p and it is processed by the FU; the second one is the first sibling node of p according to the SE enumeration and it is concurrently computed by the BU. Both units generate ψ terms (indicated as ψ F U and ψ BU in Fig.3.15). ψ[i] blocks in FU and BU share the same architecture. S block in FU and Alt block in BU also have similar structures, however the latter does not need to perform the division included in the S block: the following best choices for s l (s

	(k) l , with k > 1)
	are generated according to the SE policy as shown in Fig. 2.3 and described
	in [3].
	A control unit (CU) properly synchronizes the processing components. It is
	implemented as a Finite State Machine (FSM). The processing flow is basically
	affected by two control operations. The first one is related to tree pruning and
	backward processing. PED metrics are sent to the control unit to verify radius
	constraint (2.7) and signal f/b is used to control the first multiplexer in FU:
	the alternative symbol s

• Test & Restart Unit (TRU), which implements the modified tree visit strategy described in Section 3.3. TRU computes the Babai Point s l by means of an additional S block and compares it (CMP block) with the symbol s l , provided by the FU unit. The CMP block is a simple comparator.

The architecture is completed by three memories for the storage of channel coefficients (R Mem), ψ amounts (Ψ Mem) and PED metrics (PED Mem). R memory stores the upper triangular matrix R, obtained after Cholesky decomposition (2.6). 1/2M × M locations are required in the Ψ memory, due to the triangular structure of the R matrix; however an M × M memory is allocated to simplify the generation of addresses. The PED memory only has M locations, so it can be implemented as a set of registers rather than using a RAM generator.

(k) l is selected if the test fails, while depth-first search is

3.4 Architecture design

Table 3 . 2 :

 32 Combinational delay (t pd min ) for additional architecture blocks in Fig.

	3.15
	Block	t pd min [ns]
	ALT block	1.39
	CMP block	0.34
	R Mem	2.05
	Ψ Mem	2.05

Table 3 . 3 :

 33 Synthesis results of computational blocks in the whole architecture: occupied area at the maximum clock frequency f ck = 487 MHz. Rows 2 to 8 refer to processing blocks required for SDA; rows 9 and 10 refer to the additional component needed to support LASDA

	Block	Area [µm 2 ]
		@ f ck = 487 MHz
	S block	3124
	ψ[i] block	39947
	DI block	6566
	PED block	12331
	ALT block	403
	R Mem	36269
	Ψ Mem	36269
	ψ[i] block	21493
	CMP block	38

  Comparisons with the state of the art

			3.6 Table 3.4: Comparisons with other works
	Reference	[46]	[47] [16]	[15] [1]		[2]	[3]	This
									work
	MIMO system Modulation	64 QAM		4 × 4 16 QAM
	BER Perf.			Close to ML				ML
	Technology	0.065	0.13 0.25	0.35 0.25	0.25	0.13	0.13 0.13
	[µm]
	Max.	f CK	158	150 100	100 71	180	333	250	488
	[MHz]
	Area [EG]	1760K	438K 669 (1) 91K 50K	73K	90K	30K 34K
	Area [mm 2 ]	2.38 (1)	2.23 13.4	5.76 1.0	1.46	0.49 (1) 0.16 0.18
					(1)	(1)
	Av. Through-	463	2,400 95	53.3 193	488	903	196	381
	put [Mbps]
	@SNR=22dB
	TAR	[Mbp-	0.26	5.48 0.14	0.58 3.86	6.68	10.03	6.53 11.21
	s/KEG]
					and in this work offer full ML per-
	formance, the other compared implementations give close to ML performance;
	moreover solutions in columns 4 to 7 are related to an older Silicon technol-
	ogy, and finally implementation in column 2 addresses a 64QAM modulation

(1) Estimated value, obtained assuming an area occupation, of a two input NAND gate, of 20 µm 2 , 5.4 µm 2 and 1.35 µm 2 respectively for 0.25 µm, 0.13 µm and 0.065 µm CMOS standard cell technologies and uses a 65 nm technology. Table

3

.4 gives for each implementation the corresponding technology, maximum clock frequency (Max. f CK ), area complexity (Area), expressed in both mm 2 and equivalent gate count (EG), and average throughput (Av. Throughput) at SNR=22 dB. To evaluate the VLSI efficiency of the compared solutions, the last row in Table

Table 4 . 1 :

 41 Constants used in the computation of a priori statistics

	Q-PSK	16-QAM
	Const[0]

Table 4 . 2 :

 42 Notation of 1/ √ x stored into the LUT

Table 4 . 4 :

 44 Area results of synthesis of memories generated using a RAM generator for a 130 nm technology, obtaining results in Tab. 4.4. An estimation of throughput can be done in term of LLRs per second, as in the following equation:

	4.1 Complexity evaluation of a soft-output MIMO detector
	Unit	Area um 2
	Apriori stat	26052
	cov cholesky	43676 134542	Memory n. Area um 2
	invs	94814	rom div 2	135605
	f	190059	rom exp 1	24412
	antenna n	224748	rom exp 1	99609
	Total	852194	Total	4	395231
	Table 4.3: Area results of synthesis of
	ESE (sequential architecture)

Table 5 . 1 :

 51 Comparisons between works in

	Ref.	Baghdadi et al.	[12]	[9]	My work	Burg et al.	[7]
		[6]			[13]	[4]
	Standard	IEEE 802.11n,	IEEE 802.11n
		802.16e, LTE
	Detection		Soft		Hard		Soft
	MIMO Modulation	2×2, 3×3, 4×4 BPSK ,QPSK,	2 × 2 64QAM	16QAM	4 × 4	QPSK, 16
		16 and 64QAM						and 64QAM
	Receiver	Turbo		Convolutional		Viterbi
	Algorithm	MMSE-IC	LORD	SSD	LASDA	STS-SESD	SO
		(ASIP)
	Implem.			ASIC
	Tech. [nm]	90	65	45	130	250		45
	BER Perf.		close to ML		ML		close to ML
	f max [MHz] 546	80	312	488	71		500
	Norm.90nm	546	40	124.8	976	568		200
	Area [KEG]	84.3	236	293	34	56.8		70
	Area[mm 2 ]	0.22	0.32	0.19	0.18	1.14		0.04
	Norm.90nm 0.22	0.61	0.76	0.09	0.15	0.18
	[mm 2 ]
	Th. [Mbps]	273MSps 2×2	164 2×2	307	295	40		1000 QP SK
		148MSps 3×3						500 16QAM
		168MSps 4×4						187.5 64QAM
	Norm.90nm 29.6to327.6	82	122.8	590	320		75to400
	Th/Area	135to1499	134	162	6556	2173	413to2205
	[Mbps/mm 2 ]

row 12)

and normalized clock frequency (row 10) are computed considering

Table 5 . 5

 55

		65]	[66]	[67]
	Matrix dimen-sions		4 × 4 complex-valued	8 × 8 real-valued
	Technology [nm] 250	180	130
	Frequency	125	162	not shown
	[MHz]
	Area [KGE]	54	61.8	27

: Area results of different implementations of QR-decomposition for MIMO detection.

Table 6 . 1 :

 61 Setup of the conducted simulations

		16-QAM, 64-QAM
	Mapping	Gray
	Channel model	Rayleigh fading, block and fast
	List size for block-fading	64
	List size for fast-fading	256, 512
	Channel encoder	Convolutional (rate 0.5)
	Channel decoder	Max-log MAP BCJR
	Number of iterations	5
	Coded frame	480 bits

Table 6 . 2 :

 62 Complexity estimation with a 4 × 4-MIMO and 16-QAM for LSD (list of 64, BER of 10 -6 ) and MMSE-IC

	-IC	ADD/SUB	MUL
	Symbol expectation 1 it	6.7e+03	2.9e+03
	Symbol expectation 5 it	3.4e+04	1.4e+04
	Soft Demapper+ Soft Mapper 1 it	1.3e+03	1.4e+03
	Soft Demapper+ Soft Mapper 5 it	6.6e+03	7.2e+03
	LSD	ADD/SUB	MUL
	List generation	2.5e+05	2.3e+05
	LLR comp. 1 it	3.7e+05	3.1e+04
	LLR comp. 2 it	7.4e+05	6.3e+04

  This unit has to compute the partial euclidean distance of the Babai Point, during the forward processing; during the backward processing, it computes the alternative points, based on SE enumeration, (eq. (2.8)). It receives s l , R l,l , ψ l+1 [l] and T l+1 , as inputs and produces the current partial euclidean distance T l . It is indipendent of both cardinality of constellation and number of antennas, making this block quite simple, composed only of two multipliers, one subtractor and one adder. It is worth clarifying here that the two multipliers do not have the

							7.2 First suboptimal ASIP of LSD
	7.2.1.2 PED computation
		9	x 10 4
							Babai Unit (Divisor)
		8					Babai Unit (mul-sub-comp network)
		7
		6
	Area[um 2 ]	5
		4
		3
		2
		1	2.6	2.8	3	3.2	3.4	3.6	3.8	4	4.2
						delay[ns]

  Stages of pipeline.least significant bit is used to select either R RF or P SI RF . The reg dest and reg adx fields represent the index for a general purpose register file, used as pointer to other RFs: the first is related to the index of R RF or P SI RF , the second, instead is the relative address, adjusted with an immediate value imm, of the data memory. The ADDI ("add immediate") adds a constant value to In particular, BNE is useful together with LW, in order to read the specified number of locations from the data memory. If reg1 = reg2 in Fig.7.12, the costant value number is added to the program counter. The JUMP is, instead,

						7.2 First suboptimal ASIP of LSD
	ISTRF	Pipeline Registers	OPF	Pipeline Registers	EX1	Pipeline Registers	MEM/EX2	Pipeline Registers	WB
	29 Figure 7.10: 31 22 15 1 1 1 reg_adx reg_dest		imm	1	0 R/zf
				Figure 7.11: Instruction format of LW.
	0 1	reg1	reg2			number
	31	30		23	16				0
	1. Instruction Fetch (ISTRF): it fetches the instruction from the program mem-Figure 7.12: Instruction format of BNE.
	ory and the fetch address register is prepared for the next instruction, check-
	ing if there is a jump or not;

a relative address, while NOP instruction is employed when empty cycles are required during the execution of the program. The jumps are managed by the BNE ("branch if not equal") for conditional ones, used to check a condition if there is a loop into the program, and JUMP for those which are unconditional.

Table 7 . 1 :

 71 Synthesis results of LSD ASIP

	Technology	ST 130nm
	Frequency	92 MHz
	Area	816113 um 2 (151 KGE)
	the proposed ASIP with the state of art implementations, next paragraph reports
	an improved design, faced to increase the clock frequency.

Table 7 . 4 :

 74 Throughput of the improved LSD ASIP for a 2 × 2 MIMO system.

			SNR [dB]			Th [Mbps]
			0	|L| = 4 |L| = 8 |L| = 16 |L| = 32 |L| = 64 3,07 2.51 2.27 2.27 2.27
		QPSK	6	3,21	2.57	2.30	2.30	2.30
			12	3,25	2.59	2.31	2.31	2.31
			18	3,29	2.60	2.31	2.32	2.31
			24	3,28	2.59	2.32	2.32	2.32
			30	3,27	2.59	2.32	2.32	2.32
			0	3.79	2.76	1.96	1.41	1.04
			6	4.46	2.96	2.09	1.47	1.07
	2 × 2	16QAM	12 18	4.60 4.63	3.08 3.14	2.12 2.18	1.50 1.49	1.08 1.08
			24	4.54	3.14	2.15	1.50	1.08
			30	4.59	3.11	2.12	1.50	1.08
			0	3.25	2.52	1.88	1.32	0.93
			6	4.15	3.06	2.19	1.50	1.01
			12	4.81	3.40	2.32	1.56	1.04
		64QAM	18	4.96	3.55	2.34	1.60	1.06
			24	5.12	3.46	2.36	1.58	1.06
			30	5.01	3.49	2.31	1.56	1.05
	his work. The LSD has the additional role of filling a list, whose size is fixed:
	this makes the throghput almost indipendent of the SNR.

Table 7 . 5 :

 75 Throughput of the improved LSD ASIP for a 3 × 3 MIMO system.

			SNR [dB]			Th [Mbps]
			0	|L| = 4 |L| = 8 |L| = 16 |L| = 32 |L| = 64 1.85 1.39 1.06 0.87 0.79
		QPSK	6	2.05	1.46	1.10	0.89	0.80
			12	2.14	1.51	1.12	0.89	0.80
			18	2.15	1.51	1.12	0.90	0.80
			24	2.17	1.53	1.13	0.90	0.80
			30	2.17	1.53	1.14	0.90	0.80
			0	1.50	1.12	0.81	0.57	0.39
			6	2.16	1.45	0.98	0.65	0.43
	3 × 3	16QAM	12 18	2.50 2.64	1.62 1.65	1.05 1.10	0.70 0.71	0.46 0.46
			24	2.64	1.73	1.10	0.73	0.47
			30	2.62	1.67	1.11	0.72	0.47
			0	0.62	0.51	0.41	0.35	0.25
			6	0.91	0.69	0.50	0.35	0.23
			12	1.38	0.90	0.62	0.42	0.27
		64QAM	18	1.53	1.04	0.68	0.44	0.29
			24	1.60	1.06	0.68	0.47	0.29
			30	1.56	1.02	0.69	0.45	0.30

Table 7 . 6 :

 76 Throughput of the improved LSD ASIP for a 4 × 4 MIMO system.

			SNR [dB]			Th [Mbps]
			0	|L| = 4 |L| = 8 |L| = 16 |L| = 32 |L| = 64 1.15 0.84 0.62 0.45 0.35
		QPSK	6	1.35	0.94	0.66	0.48	0.36
			12	1.35	0.94	0.66	0.48	0.36
			18	1.49	1.01	0.69	0.49	0.36
			24	1.56	1.04	0.71	0.50	0.37
			30	1.56	1.06	0.72	0.50	0.37
			0	0.56	0.41	0.33	0.25	0.17
			6	1.01	0.73	0.50	0.35	0.22
	4 × 4	16QAM	12 18	1.01 1.43	0.73 0.93	0.50 0.62	0.35 0.39	0.22 0.25
			24	1.58	1.03	0.68	0.43	0.27
			30	1.68	1.07	0.69	0.44	0.27
			0	0.09	0.08	0.07	0.06	0.05
			6	0.36	0.29	0.22	0.18	0.13
			12	0.36	0.29	0.22	0.18	0.13
		64QAM	18	0.74	0.52	0.39	0.29	0.19
			24	1.14	0.75	0.51	0.34	0.21
			30	1.32	0.86	0.57	0.36	0.23

Table 7 . 7 :

 77 Comparisons with the State of the Art

	Reference	[113]	[21]	[15]	[114]	[112]	This work
	Imp.		ASIC			ASIP
	Type of detec.	SO SD	SISO	SO MKSE	K-LSD	SO K-Best LSD	SE LSD
	MIMO system Modulation	2 × 2 B,Q,16,64-QAM		4 × 4 16 QAM		2 × 2 64-QAM	2 × 2-3 × 3-4 × 4 Q,16,64-QAM
	BER Perf.			Close to ML
	Tech [µm]	0.045	0.09	0.13	0.13	0.13	0.13
	f CK [MHz]	312	250	200	100	280	228
	Area [EG]	262K	96K	97K	170K	25K	164K
	Av. Th.[Mbps]	374	10-90	106.6

Table 7 . 8 :

 78 Synthesis results of improved LSD ASIP with "pipeline interleaving"The Listing 7.2 reports the assembly code for the ASIP with "pipeline interleaving". The INIT instruction initializes some configuration parameters: this sample code is for a 4 × 4 MIMO, 64QAM and |L| = 4. From line 4 to line 26, five loops are dedicated to load the first 5M locations of data memory, containing ZF solutions for each vector, into the corresponding register file (P SI RF 1, P SI RF 2, P SI RF 3, P SI RF 4 and P SI RF 5). The remaining 2M × 2M locations, containing channel coefficients, are, then, loaded into R RF (loop at 7.3 Improved ASIP: increased clock frequency

	Technology	ST 130nm
	Frequency	210 MHz
	Area	2809788 um 2 (520 KGE)

Table 7 .

 7 10: Comparisons of the ASIP with "pipeline interleaving " with the State of the Art

	Reference	[113]	[21]	[15]	[114]	[112]	This work
	Imp.		ASIC			ASIP
	Type of detec.	SO SD	SISO	SO MKSE	K-LSD	SO K-Best LSD	SE LSD
	MIMO system Modulation	2 × 2 B,Q,16,64-QAM		4 × 4 16 QAM		2 × 2 64-QAM	2 × 2-3 × 3-4 × 4 Q,16,64-QAM
	BER Perf.			Close to ML
	Tech [µm]	0.045	0.09	0.13	0.13	0.13	0.13
	f CK [MHz]	312	250	200	100	280	210
	Area [EG]	262K	96K	97K	170K	25K	520K
	Av. Th.[Mbps]	374	10-90	106.6

Ce travail de thèse traite les aspects algorithmique, architectural et de mise en oeuvre de la détection MIMO basée sur SDA et LSD. Le principal objectif des travaux menés est de proposer des solutions de mise en oeuvre de faible complexité, tout en considérant les exigences des systèmes avancés de communication numérique en termes de débit, de flexibilité et de taux d'erreurs.

Alternatively to this method, MMSE preprocessing[START_REF] Wubben | MMSE extension of V-BLAST based on sorted QR decomposition[END_REF] might be used on an extended channel matrix for the Cholesky decomposition.

With automated synthesis, when multiple components are integrated, the whole critical path delay may be different from the simple sum of component delays.

In some block of the architecture the data width is set less than

bits

The instruction set of the proposed ASIP is composed of two groups: the former includes some traditional instructions and the latter has specialized ones, which are properly designed for the LSD algorithm. The first group is composed of common instructions, such as LW, ADDI, NOP, BNE and JUMP. The LW ("load word") is used to load the content of Channel Data Mem into R RF and P SI RF . The instruction word is shown in Fig. 7.11. In particular, the 7.2 First suboptimal ASIP of LSD the BABAI instruction, or to 1, activating the SE enumeration block otherwise. When the algorithm reaches a leaf, the update list signal enables the list management unit, which directly reads and writes d2 list RF and u list RF . Finally, in the MEM/EX2 stage, proper elements of u RF and step RF are updated, and l new and up/down are written in the respective global registers. As shown in Fig. 7.17, only opcode bits are used in the instruction format. Nothing else is necessary, since the addresses for reading RFs are directly derived from the content of level register.

Sample program

In this subsection sample program to implement the LSD algorithm is described. The assembly code line starting with ";" denotes a comment line.

The user can choose the desired configuration through the INIT instruction:

this sample code is for a 4 × 4 MIMO, 64QAM and |L| = 64. After the initialization of the ASIP, the first M locations of data memory, containing ZF solutions, are loaded into P SI RF , using a loop (line 4). Then the program loads the remaining 2M × 2M locations, containing channel coefficients, into R RF (loop at line 9). After that the LSD can first start to process the highest level of the tree, and continues the tree search jumping back to "check up down", until the detection is not complete, and to "finish" otherwise. remaining 40.4 % is due to the pipeline (Area pipe ) and Table 7.3 also reports the area of all sub-blocks of it. At each pipeline stage corresponds one block, so it is quite easy to analyze these results. Most of the complexity is concentrated in the MEM stage (32.8 %). In fact, it is devoted to compute PED and ψ metrics, and to manage the list, besides loading the content of the external memory into proper registers.

Improved ASIP: increased clock frequency

Performance

The throughput of the ASIP is detailed for different system configurations in Tables 7.4, 7.5 and 7.6. The values, reported for each SNR, are average numbers, obtained after 10 6 simulations, according to [START_REF] Witte | A scalable VLSI architecture for Soft-Input Soft-Output Single Tree-Search Sphere Decoding[END_REF]:

with R being the code rate, Q the number of bits per symbol, M t the number of transmitters f clk the clock frequency and E(N en ) the average number of clock cycles N en , needed to detect one symbol vector . Here a convolutional code R = 0.5 has been adopted.

Chosen system and modulation, the throughput has not a big variation with SNRs, on the contrary it is almost constant. A traditional SDA, instead, has variation of about 80 % between low and high SNRs, as already shown in Fig. 3.12. This is due to the fact that, once the ML solution has been found, SDA stops the search, and if the noise level is high it requires more time to complete 5729 um 2 (0.2 %) line 28). After that the LSD can first start to process the highest level of each tree. The search continues jumping back to "check up down", until the detection of each symbol vector is not complete, and to "finish" otherwise. Now the ASIP is able to visit 2.6 node per cycle (5 nodes per 13 cycles). Moreover, the pipeline is exploited at about 85 %. A neglibile reduction of the clock frequency of about 0.7 % with respect to the ASIP without "pipeline-interleaving" has to be noticed. This is mainly due to the additional complexity as interface towards the register files. It can be estimated an increase in terms of throughput by a factor 5 6 2.6 0.92 = 10.6, and in terms of occupied area by a factor 3.2. Therefore, the TAR is improved by a factor 3.3. Table 7.10 reports the comparison of this new results with the state of the art. The advantage of throughput is quite evident. In fact, our ASIP is better than other ASIPs: by a factor from 2 and 5, with respect to [START_REF] Antikainen | Application-specific instruction set processor implementation of list sphere detector[END_REF], and between 5 and 7, with respect to [START_REF] Antikainen | Fine-grained application-specific instruction set processor design for the kbest list sphere detector algorithm[END_REF]. Moreover, the gap with ASIC implementations is not any more so large. The work in [START_REF] Witte | A scalable VLSI architecture for Soft-Input Soft-Output Single Tree-Search Sphere Decoding[END_REF], which is the most similar to our solution, since it adopts a depth-first Schnrorr Euchner policy, is now better than ours by a factor between 4 and 5, against 40 and 56 of the previous version. We claim that the "pipeline interleaving" is a good approach to be competitive also with ASIC implementations. For example, with 10 symbol vector detected in parallel, it is possible have comparable results. The main drawback is the increase of area, which makes the ASIP not yet competitive with ASICs in terms of TAR. For what concerns ASIPs solutions, our work is LW $0,0,$0 ,0,$1 BNE $0 , $1 , load_zf1 ; Load the successive M locations of Channel Data Memory into PSI RF 2 ADDI $0, $0 , -8 load_zf2 : ADDI $3 , $3 , 1 LW $3,8,$3 ,0,$2 BNE $3 , $1 , load_zf2 ; Load the successive M locations of Channel Data Memory into PSI RF 3 ADDI $3, $3 , -8 load_zf3 : ADDI $0 , $0 , 1 LW $0,16,$0 ,0,$3 BNE $0 , $1 , load_zf3 ; Load the successive M locations of Channel Data Memory into PSI RF 4 ADDI $0, $0 , -8 load_zf4 : ADDI $3 , $3 , 1 LW $3,24,$3 ,0,$4 BNE $3 , $1 , load_zf4 ; Load the successive M locations of Channel Data Memory into PSI RF 5 ADDI $3, $3 , -8 load_zf5 : ADDI $0 , $0 , 1 LW $0,32,$0 ,0,$5 BNE $0 , $1 , load_zf5 ; Load the successive 2M *2M locations of Channel Data Memory into R RF load_R : ADDI $0 , $0 , 1 ADDI $3 , $3 , 1 LW $3,32,$0 ,1,$

Improved ASIP: increased clock frequency