The Fixed Sphere Decoder Homepage

Overview of Sphere Decoding and the Fixed Sphere Decoder

1. Introduction

This webpage describes research carried out by Dr Luis Barbero (now at Queen's University Belfast) and Dr John Thompson into the design and implementation of sphere decoding algorithms for multiple input multiple output (MIMO) wireless channels. This work was carried out as a CASE award PhD programme, sponsored by Alpha-Data.

As part of the research, a novel detection algorithm was discovered which is called the Fixed Sphere Decoder. This algorithm modifies the original sphere decoding concept for MIMO systems to make it more amenable to efficient, high speed hardware implementation, at the cost of a small loss in performance. The basic idea is to specify in advance the number of constellation points to be considered, when calculating Euclidean distance metrics for each transmit antenna. This makes the algorithm much more suited for pipelining than the original sequential tree-search technique used in the sphere decoder. When combined with a novel antenna ordering algorithm, it can be shown that this detector can provide almost Maximum Likelihood detection performance.

2. Tools Used For The Project

A key part of this project was to test the proposed algorithms in hardware to understand how efficiently they would run in real-time implementations. During the project, the researchers made use of the following software tools:

MATLAB(R) and Simulink(R) to develop sphere decoding algorithms
Xilinx System Generator(TM) and ISE(TM) to port the algorithms onto an FPGA board
Alpha-Data Software to run hardware-in-the-loop testing of the algorithms from MATLAB

We used two FPGA test boards provided by Alpha-Data containing the following Xilinx FPGAs:

ADM-XRC-II with a Xilinx Virtex-II (XC2V4000)
ADM-XP with a Xilinx Virtex-II-Pro (XC2VP70)

3. White Paper for the Project

You can download a copy of a brief white paper here that outlines the system used and some of the results obtained during the project.

A block diagram of how a MIMO system was implemented in MATLAB and in the FPGA is shown below in Figure 1. The most intensive part of the system, namely the sphere decoder receiver, was implemented on the FGPA. Other parts of the simulation, including modelling of the MIMO transmitter and radio channel, were simulated in MATLAB. A memory interface was set up to allow the two parts of the simulation to communicate.

Figure 1: Block diagram of the MIMO system simulation using MATLAB and the FPGA.

4. Overview of Sphere Decoding and the Fixed Sphere Decoder

This section provides a very brief overview of how the fixed sphere decoder differs from the standard sphere decoder. Much more detailed explanations can be found in the publications below.

The maximum likelihood decoder for a MIMO receiver operates by comparing the received signal vector with all possible noiseless received signals corresponding to all possible transmitted signals. Under certain assumptions, this receiver achieves optimal performance in the sense of maximising the probability of correct data detection. However, the complexity of this decoder increases exponentially with the number of transmit antennas, making it impossible to implement for large array sizes and high order digital modulation schemes.

The main idea of the Sphere Decoder is to reduce the computational complexity of the maximum likelihood detector by only searching over only the noiseless received signals that lie within a hypersphere of radius R around the received signal. Normally, this algorithm is implemented as a depth first tree search, where each level in the search represents one transmit antenna's signal. This is illustrated in Figure 2 below. If at a given level, a given branch exceeds the radius constraint, then that part of the tree can be removed from further consideration. Unfortunately, it is difficult to estimate how much of the tree needs to be searched in advance, since this depends on both the noise and the channel conditions. This means that the complexity of the sphere decoder is not fixed, but will typically vary with time.

Figure 2: The Tree Structure and Sphere Constraint for the Sphere Decoder.

The main idea behind the Fixed Sphere Decoder is to perform a search over only a fixed number of possible transmitted signals, generated by a small subset of all possible signals located around the received signal vector. This ensures that the detector complexity is fixed over time, a major advantage for hardward implementation. In order for such a search to operate efficiently, a key point is to order the antennas in such a way that most of the points considered relate to transmit antennas with the poorest signal-to-noise (SNR) conditions. Antennas with higher SNR conditions are much more likely to be detected correctly, based only on the received signal. Figure 3 below shows a hypothetical subset S in 4 transmit antenna, 4 recieve antenna system with 4-QAM constellations used at each transmit antenna. The number of points considered per level (i.e. transmit antenna) is (n1,n2,n3,n4) = (1,1,2,3). In each level, the ni closest points to the received signal are considered as components of the subset S. In this case, the Euclidean distance of only 6 transmitted vectors would be calculated, whereas the total number of possible vectors, 256, is much larger.

Figure 3: A Hypothetical Tree Structure for the Fixed Sphere Decoder.

5. Publications

This research project has led to a number of publications including joint work with researchers at the University of Mondragon, Spain, TU Munich, Germany and KTH Stockholm, Sweden. Copies of papers published during the project can be found here:

[1] J. Jalden, L.G. Barbero, B. Ottersten and J.S. Thompson, "The Error Probability of the Fixed-Complexity Sphere Decoder", Accepted for publication in IEEE Trans Signal Processing, 2009 - pdf preprint
[2] L. G. Barbero and J. S. Thompson, "Extending a Fixed-Complexity Sphere Decoder to Obtain Likelihood Information for Turbo-MIMO Systems", IEEE Transactions on Vehicular Technology, Vol 57, No 5, Sept 2008, pp 2804-2814 (Available from IEEE Xplore).
[3] L. G. Barbero and J. S. Thompson,"Fixing the Complexity of the Sphere Decoder for MIMO Detection", IEEE Transactions on Wireless Communications, Vol 7, No 6, June 2008, pp 2131 - 2142 (Available from IEEE Xplore).
[4] M. Joham, L. G. Barbero, T. Lang, W. Utschick, J. Thompson and T. Ratnarajah,"FPGA Implementation Of MMSE Metric Based Efficient Near-ML Detection", in proceedings of IEEE 2008 Workshop on Smart Antennas, Germany - pdf
[5] L. G. Barbero and J. S. Thompson, "Performance of the Complex Sphere Decoder in Spatially Correlated MIMO Channels", IET Communications, Vol 1, No 1, Feb 2007, pp 122-130. Also Erratum Vol 1, No 2, April 2007. (Available from IEEE Xplore).
[6] J. Jalden, L. G. Barbero, B. Ottersten and J. S. Thompson, "Full Diversity Detection in MIMO Systems with a Fixed-Complexity Sphere Decoder", accepted for publication in IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '07), Honolulu, Hawaii, USA, April 2007 - pdf
[7] M. Mendicute, L. G. Barbero, G. Landaburu, J. S. Thompson, J. Altuna and V. Atxa, "Real-Time Implementation of a Sphere Decoder-Based MIMO Wireless Systems", Invited Paper, in EURASIP European Signal Processing Conference (EUSIPCO '06), Florence, Italy, Sep. 2006 - pdf
[8] L. G. Barbero and J. S. Thompson, "FPGA Design Considerations in the Implementation of a Fixed-Throughput Sphere Decoder for MIMO Systems", in IEEE International Conference on Field Programmable Logic and Applications (FPL '06), Madrid, Spain, Aug. 2006 - pdf
[9] L. G. Barbero and J. S. Thompson, "A Fixed-Complexity MIMO Detector Based on the Complex Sphere Decoder", in IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC '06), Cannes, France, Jul. 2006 - pdf
[10] L. G. Barbero and J. S. Thompson, "Rapid Prototyping of a Fixed-Throughput Sphere Decoder for MIMO Systems", in IEEE International Conference on Communications (ICC '06), Istanbul, Turkey, Jun. 2006 - pdf
[11] L. G. Barbero and J. S. Thompson, "Performance Analysis of a Fixed-Complexity Sphere Decoder in High-Dimensional MIMO Systems", in IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '06), vol. 4, Toulouse, France, May 2006, p. 557-560 - pdf
[12] L. G. Barbero and J. S. Thompson, "List-Sphere Decoder with Channel Matrix Ordering for MIMO Systems", Invited Paper, in Proc. 15th Joint Conference on Communications and Coding (JCC '06), vol. 1, Solden, Austria, Mar. 2006, p. 10 - pdf
[13] L. G. Barbero and J. S. Thompson, "Rapid Prototyping System for the Evaluation of MIMO Receive Algorithms", in Proc. IEEE International Conference on Computer as a tool (EUROCON '05), vol. 2, Belgrade, Serbia, Nov. 2005, pp. 1779-1882 - pdf
[14] L. G. Barbero and J. S. Thompson, "Rapid Prototyping of the Sphere Decoder for MIMO systems", in Proc. IEE/EURASIP Conference on DSP Enabled Radio (DSPeR '05), vol. 1, Southampton, UK, Sept. 2005, pp. 41-47 - pdf
[15] L. G. Barbero and J. S. Thompson, "Rapid Prototyping of MIMO Algorithms for OFDM WLAN", in Proc. 5th PostGraduate Symposium on Telecommunications, Networking and Broadcasting (PGNET '04), vol. 1, Liverpool, UK, Jun. 2004, pp. 235-240 - pdf

Last Update: March 2009