M.Sc Thesis

M.Sc StudentTwitto Moshe
SubjectTightened Upper Bounds on the ML Decoding Error Probability
of Binary Linear Block Codes and Applications
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Igal Sason


Since the advent of information theory, the search for efficient coding systems has motivated the introduction of efficient bounding techniques tailored to specific codes or some carefully chosen ensembles of codes. The incentive for introducing and applying such bounds has strengthened with the introduction of various families of codes defined on graphs which closely approach the channel capacity with feasible complexity (e.g., turbo codes, repeat-accumulate codes, and low-density parity-check (LDPC) codes). Moreover, a lot of applications for turbo-like codes were suggested for a variety of digital communication systems, such as Digital Video Broadcasting (DVB-S2), deep space communications and the third generation of CDMA (WCDMA). Their broad applications and the existence of efficient algorithms implemented in custom VLSI circuits  enable to apply these iterative decoding schemes to a variety of digital communication systems. Clearly, the desired bounds must not be subject to the union bound limitation, since for long blocks these ensembles of turbo-like codes perform reliably at rates which considerably exceeds the cutoff rate $ (R_0) $ of the channel (recalling that for long codes, union bounds are not informative at the portion of the rate region exceeding the cut-off rate of the channel, where the performance of these capacity-approaching codes is most appealing). Although maximum-likelihood (ML) decoding is in general prohibitively complex for long codes, the derivation of bounds on the ML decoding error probability is of interest, providing an ultimate indication of the system performance. Further, the structure of efficient codes is usually not available, necessitating efficient bounds on performance to solely rely on basic features, such as the distance spectrum and input-output weight enumeration function (IOWEF) of the examined code (for the evaluation of the block and bit error probabilities,  respectively, of a specific code or ensemble).

In this thesis, we introduce improved upper bounds on the ML decoding error probability of binary linear block codes, which are tightened versions of the SFB. These bounds on the block and bit error probabilities depend on the distance spectrum of the code (or the average distance spectrum of the ensemble) and the input-output weight enumeration function, respectively. The effect of an expurgation of the distance spectrum on the tightness of the resulting bounds is also considered. By applying the new bounds to ensembles of turbo-like codes over the binary-input AWGN channel, we demonstrate the usefulness of these new bounds, especially for some coding structures of high rates.