Peter Allan Berlin
The addition of a feedback link to a discrete memoryless channel does not increase its capacity, but it does bring with it other benefits. One of these benefits is an increase to the best achievable error exponent. In the first part of this thesis we revisit a 1976 proof by Burnashev which determined the best achievable error exponent of variable length block codes. We develop a new derivation of the converse proof to the error exponent that parallels a simple and instructive achievability scheme developed by Yamamoto and Itoh. The proposed converse is more accessible than the original and yields some insight into the roles played by the quantities that appear in the exponent expression. This suggests that a communication and confirmation phase are implicit in any scheme which achieves the largest possible error exponent. When calculating error exponents the probability of error is studied in the limiting case of long coding delay. In the following part of the thesis, we construct codes that perform well when we are interested in finite coding delay. Starting from the Yamamoto-Itoh achievability scheme, a new scheme that makes use of a list decoder is proposed. This new scheme reduces the penalty associated with making communication longer when channel conditions require it, allowing the scheme to react better to unfavourable channel realisations. The scheme still achieves the same optimal error exponent as the Yamamoto-Itoh scheme. We show that the proposed scheme can be easily realised using Reed-Solomon codes, and can achieve the same probability of error with shorter delay than the comparable Yamaoto-Itoh scheme. Both feedback schemes are shown to perform significantly better than Reed-Solomon codes without feedback. Block coding techniques assume that the message to be mapped to the block is available at the time transmission starts. This is not the case for sequential codes where the information to be transmitted is revealed progressively to the transmitter. Delay is measured separately for each information symbol, starting from the instant it is passed to the transmitter. Consequently, sequential codes need a different definition of error exponents from block codes. In the third part of the thesis we divide sequential codes with feedback into four classes, according the way the information is revealed to the transmitter (at deterministic or random intervals), and the way delay is limited (peak value bounded or bounded in expectation). Sahai reapplied an argument developed by Viterbi to relate the exponent of sequential codes to the block coding exponent to the case of codes with deterministic interval and peak limited delay. We develop upper bounds to the error exponents for the remaining three cases by relating the sequential coding problems to Burnashev's variable length block coding problem studied earlier in the thesis. The setting with random information arrival time and expected delay bound is equivalent to the achievability schemes proposed by Horstein and Kudryashov, and our upper bound is found to meet the exponent of these schemes at zero rate. In the final part of the thesis we address a coding problem without feedback. We develop low-density parity-check (LDPC) codes to communicate over two-user fading broadcast channels with additive white Gaussian noise. Joint decoding of the codes is analysed and the message update rule at the mapping node linking the users' codes is derived. The update rule is found to exhibit an interesting soft interference cancellation property. High performance codes are found that have rates very close to the boundary of the achievable region for binary constrained input. Simulation results for moderate block length show that the codes operate within less than 1dB of the corresponding error correcting threshold.
EPFL2008
