Low-complexity algorithms in digital receivers

Sammanfattning: This thesis addresses low-complexity algorithms in digital receivers. This includes algorithms for estimation, detection, and source coding. Low-complexity algorithms for estimation and detection, in this thesis concerns the approximation of optimal algorithms, so that a low complexity is obtained while most of the original performance is maintained. Two different problems are studied: Channel estimation in orthogonal frequency-division multiplexing (OFDM) systems and sequence detection in systems with inter-symbol interference (ISI). The work on channel estimation is focused on what can be viewed as transform-based estimators, where the estimation is transformed to a domain that allows the statistical properties of the channel to be used efficiently for complexity reduction. Estimators based both on the discrete Fourier transform (DFT) and on low-rank approximations are addressed. It is shown that these types of estimators, with proper design considerations, provide good low-complexity estimators, even though the DFT-based estimators have a tendency to suffer from approximation errors at high signal-to-noise ratios. The work on sequence detection in systems with ISI is a comparative study of designs in a class usually referred to as combined linear-Viterbi equalizers (CLVEs). The idea behind CLVEs is to shorten the impulse response of the channel by a linear prefiltering, before the Viterbi detector is applied. The comparison includes three previously known designs and a minimax design. A unified design-framework is also derived, which makes the comparison easier. The last two parts of the thesis are concerned with the design of robust variable-length codes and an analysis of the decoding speed for look-uptable based decoders for variable-length codes, respectively. By robust variable-length codes are meant fixed variable-length codes that have a low susceptibility to changes in the probability distribution of the source. Robustness measures are discussed in general and a measure called gradient robustness is introduced. It is shown that only a small loss in the degree of data compression can result in substantially increased robustness. As a side effect the proposed design methods also shorten the length of the longest code words, allowing efficient storage of code books. Finally, the design and the decoding speed of look-up table based decoders for variable-length codes are studied. These decoders are based on using the coded sequence for indexing a table, thereby providing an instantaneous decoding. Two types of decoders are studied. One allows a trade-off between decoding speed and memory requirement.