Low-complexity near-maximum-likelihood multiuser detection and LDPC channel coding
MetadataShow full item record
In digital communication systems, maximum likelihood (ML) multiuser detection and decoding of linear block codes translate to similar basic combinatorial optimization problems with complexity exponential in the number of users or code size, respectively. Development of low-complexity high-performance sub-optimum solutions is of great practical interest. In this dissertation, we establish that the performance of the ML optimum multi-user detector can be approached efficiently and effectively as follows. First, we use a multiuser zero-forcing or minimum-mean-square-error (MMSE) linear filter as a pre-processor. The output magnitudes of the pre-processor, when properly scaled, provide a reliability measure for each user bit decision. Then, we produce and execute an ordered reliability-based error search sequence of length linear in the number of users which returns the most likely user bit vector among all visited options. Extensive simulation studies support these theoretical developments and indicate that the error performance of the optimum and the proposed detector are nearly indistinguishable over the whole pre-detection signal-to-noise ratio (SNR) range of practical interest. A low-complexity algorithm for the decoding of low-density parity-check (LDPC) codes is also developed. The algorithm is oriented specifically toward the low cost--yet effective--decoding of (high rate) finite geometry LDPC codes. The decoding procedure updates the hard-decision received vector iteratively in search of a valid codeword in the vector space. Only one bit is changed in each iteration and the bit selection criterion combines the number of failed checks and the reliability of the received bits. Prior knowledge of the signal amplitude and noise power is not required. An optional mechanism to avoid infinite loops in the search is also proposed. The algorithm achieves an appealing trade-off between performance and complexity for finite geometry LDPC codes. In addition, some new properties of generalized polygon LDPC codes are reported. We show formally that when the diameter is four or six or eight all codewords have even Hamming weight. When the generalized polygon has in addition equal number of points and lines, we see that the non-regular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum distance bound is presented for these codes. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and give the explicit size of circulant blocks in the parity check matrix.