Ph.D Thesis

Ph.D StudentHof Eran
SubjectProblems in Coded Communications: Performance Bounds
and Polar Coding
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Igal Sason
Shlomo Shamai )Shitz(
Full Thesis textFull thesis text - English Version


Our study begins with the error performance analysis of non-binary codes. The performance of non-binary linear block codes is studied via the derivation of new upper bounds on the block error probability under maximum-likelihood decoding. The transmission of these codes is assumed to take place over a memoryless and symmetric channel. The new bounds, which are based on the Gallager bounding technique and their variations, are applied to regular ensembles of non-binary low-density parity-check codes. These upper bounds are also compared with sphere-packing lower bounds. Our study indicates that the new upper bounds are useful for the performance evaluation of coded communication systems which incorporate non-binary coding techniques.

Secondly, erasure and list decoding of linear block codes are concerned. A message independence property and some new upper bounds on the performance are derived for erasure, list and decision-feedback schemes with linear block codes transmitted over memoryless symmetric channels. Similar to the classical work of Forney, we focused on the derivation of some Gallager-type bounds on the achievable tradeoffs for these coding schemes, where the main novelty is the suitability of the bounds for both random and structured linear block codes (or ensembles). The bounds are applicable to finite-length codes and the asymptotic case of infinite block length, and they are applied to low-density parity-check code ensembles.

Next, a modified Viterbi algorithm with erasures and list-decoding is introduced. This algorithm is shown to yield the optimal decoding rule of Forney with erasures and variable list-size. For the case of decoding with erasures, the optimal algorithm is compared to the simple algorithm of Yamamoto and Itoh. The comparison shows a remarkable similarity in simulated performance, but with a considerably reduced decoding complexity.

Finally, two applications for the method of channel polarization are studied. Polar coding, recently introduced by Arikan, is a structured coding technique which is shown to approach capacity for every output-symmetric discrete memoryless channel. The theory of polar coding is still in its early days. Consequently, no known polar coding schemes have been shown to compete well with the state of the art of other modern coding schemes. Nevertheless, it has already been shown that channel polarization techniques may be applied for various multi-user information-theoretic problems. The application of channel polarization is investigated in our research for two different communication problems: signaling over parallel channels, and secure communication over the wire-tap channel.