QR decomposition algorithms for MIMO systems : impact on computational effort and hardware implementations

Abstract

Dentre as abordagens para se atingir altas taxas de transmissão em sistemas de comunicação sem fio, uma se destaca como muito promissora: sistemas de múltiplas antenas (ou Multiple Input Multiple Output – MIMO), nos quais a informação é transmitida e recebida por mais de uma antena. Tais sistemas podem atingir altas taxas de transmissão usando, entre outras possibilidades, algoritmos de sphere decoding para decodificar os símbolos MIMO recebidos. Para diversos algoritmos para detecção MIMO, tal como sphere decoding, uma variação do algoritmo de Fincke-Pohst (FINCKE, 1985), é necessário ter um hardware eficiente de decomposição QR, uma vez que esse é utilizado cada vez que a resposta impulsiva do canal modifica-se significativamente. E para obter-se uma implementação eficiente é necessário utilizar uma representação com ponto fixo para as matrizes, tanto por motivos de área quanto de latência. Evidentemente, a perda de precisão resultante do uso de ponto fixo introduz erros nas matrizes calculadas, e é provável que isso leve a um aumento na taxa de erros de quadros (FER). Um dos propósitos deste trabalho é determinar a quantidade mínima de bits necessária para manter esse aumento suficientemente baixo. Este trabalho também avalia a redução no esforço computacional para execução de detecção MIMO por algoritmos baseados em busca em árvore resultante do uso de versões melhoradas do algoritmo de decomposição QR. Mais especificamente, a sorted QR decomposition (SQRD) e a minimum mean-square error SQRD são avaliadas. O outro propósito deste trabalho é projetar arquiteturas de hardware capazes de computar a decomposição QR e suas variações para matrizes pequenas, tipicamente de 2ª e 4ª ordem. Também é importante obter uma descrição em VHDL desse hardware e comparar resultados de área e latência das diferentes versões.

Among the approaches to achieve high data rates in wireless systems, one rises as very promising: multiple-antenna systems (or Multiple Input Multiple Output – MIMO), in which the information is transmitted and received by multiple antennas. Such systems can achieve high data rates with using, among other possible choices, sphere decoding algorithms to decode the received MIMO symbols. For many algorithms used for MIMO detection, such as sphere decoding, a variation of the Fincke-Pohst Algorithm (FINCKE, 1985), it is required to have an efficient QR decomposition hardware, since it is used each time the channel impulse response changes significantly. And to achieve an efficient hardware implementation it is necessary to use a fixed point representation for the matrices, both for area and latency purposes. Evidently, the loss in precision resultant from fixed point precision introduces errors in the output matrices, and this is likely to lead to an increase in the frame error rate (FER). One of the purposes of this work is to determine the minimum amount of bits both for fractional and integer parts that are necessary to keep this increase sufficiently low. This work also evaluates the complexity reduction resultant from improved versions of the QR decomposition in tree-based search algorithms. More specifically, the sorted QR decomposition (SQRD) and the minimum mean-square error SQRD are evaluated. The other main purpose of this work is to come up with hardware architectures capable of computing the QR decomposition and its improved versions (SQRD and MMSE-SQRD) for small matrices, typically of 2nd and 4th order. It is also important to have a fully functional VHDL description of this hardware and compare the different versions regarding area and latency.