Near-optimal limited-search detection on ISI/CDMA channels and decoding oflong convolutional codes

We derive an upper bound on the bit-error probability (BEP) in limited-sear ch detection over a finite interference channel. A unified channel model is presented; this includes finite-length intersymbol interference channels a nd multiuser CDMA channels as two special cases. We show that the BEP of th e hi-algorithm (MA) is bounded from above by the sum of three terms: an upp er bound on the error probability of the Viterbi algorithm (VA) detection g iven in [10], and upper bounds on the error probabilities of two types of e rroneous decision caused by the correct path loss event. We prove that erro r propagation tin terms of the mean recovery step number) is finite for all finite interference channels. The convergence and asymptotic behavior of the upper bounds are studied, Th e results show that, if a channel satisfies certain mild conditions, all se ries in the bounds are convergent, One of the key results is that, for any finite interference channel satisfying certain mild conditions, the asympto tic BEP of the MA is bounded by the same upper and lower bounds (which have the same asymptotical behavior) as those for the VA if the correct path lo ss probability is smaller than that of the VA. Furthermore, we extend the above results to near optimally decode long conv olutional codes in a short packet format (about 200-300 bits), We present a nonsorting combined M/T algorithm and showed that the M/T algorithm with M > 2(dfree/n) and T > (d(free)E(b))ln can near-optimally decode the code. W e also propose a hierarchical decoding algorithm (HDA) to further cut down the average decoding complexity, Numerical results show that the bounds are reasonably tight. The HDA can ac hieve a performance within about 0.8 dB of the sphere-packing lower bound f or a packet error rate of 10(-4) and a packet length below 200 bits, which is the best reported decoding performance so far for block sizes from 100 t o 200 bits.