Multi-level error correcting codes

Abstract

This dissertation investigates algebraic block codes with multiple levels of error protection on the information messages, also known as unequal-error-protection (UEP) codes. New constructions of multi-level error correcting linear block codes specified by their generator matrices and by their parity-check matrices are presented and discussed. A family of nonbinary optimal LUEP codes, capable of correcting any t or less random errors affecting the most significant information symbols, while correcting any single random error in the least significant information symbols, is constructed and analyzed. This class of codes is constructed by specifying their parity check matrices, which are combinations of parity check matrices of Reed-Solomon codes and shortened nonbinary Hamming codes. Near optimal binary LUEP codes, constructed by appending (also known as time-sharing) cosets of sub-codes of shorter linear Hamming codes, are proposed and analyzed. This class of LUEP codes is specified by their generator matrices. By computing the Hamming bound on binary LUEP codes with the same dimension and error correcting capabilities as the optimal binary LUEP codes, it is shown that this family of LUEP codes requires at most one additional redundant bit. Furthermore, constructions of LUEP codes by specifying their generator matrices allow the use of multi-stage decoding methods, with reduced decoding complexity, as shown in this work. Certain families of known linear block codes are analyzed to determine their UEP capabilities. We derive conditions for which some shortened Hamming codes, some non-primitive BCH codes and some cyclic codes of composite length are LUEP codes. Bounds on the multi-level error correcting capabilities of these families of linear codes are derived. The error performance of some binary multi-level error-correcting codes over binary symmetric channels and over additive white Gaussian noise channels with BPSK modulation is considered. Some new block coded modulation (BCM) systems using LUEP codes as component codes are presented. It is shown that these schemes offer multiple values of minimum squared Euclidean distances, one for each message part to be protected. In addition, the error performance of a BCM system using LUEP codes and QPSK modulation with Gray mapping between 2-bit symbols and signals, is analyzed. In this dissertation, we also present a new multi-stage soft-decision decoding, based on the trellis structure of LUEP codes.