M.Sc Thesis

M.Sc StudentAkirav Yaniv
SubjectTopics in Universal Coding and Decoding under Channel
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Neri Merhav


This work deals with designing and exploring universal encoders and decoding methods for information transferred over a channel whose parameters are unknown. In the first part, universally achievable error exponents pertaining to certain families of channels (most notably, discrete memoryless channels (DMC’s) and various ensembles of random codes, are studied by combining the competitive minimax approach, proposed by Feder and Merhav, with Chernoff bounds and Gallager’s techniques for the analysis of error exponents. In particular, we derive a single-letter expression for the largest, universally achievable fraction \xi of the optimum error exponent pertaining to the optimal ML decoding. Moreover, a simpler single-letter expression for a lower bound to \xi is presented. To demonstrate the tightness of this lower bound, we use it to show that \xi=1, for the binary symmetric channel (BSC), when the random coding distribution is uniform over: (i) all codes (of a given rate), and (ii) all linear codes, in agreement with well-known results. We also show tha \xi=1 for the uniform ensemble of systematic linear codes, and for that of time-varying convolutional codes in the bit-error-rate sense. For the latter case, we also show how the corresponding universal decoder can be efficiently implemented using a slightly modified version of the Viterbi algorithm which employs two trellises. In the second part, we study the special case of an additive white Gaussian noise channel (AWGN) with an unknown gain parameter, and with the above-mentioned minimax decoder. Our goal is to find the optimal modulator constellation (under channel uncertainty) to be used by the encoder, in the sense that the random coding error exponent associated with the minimax decoder will be maximized. One wishes that the optimal constellation will hold uniformly over all the parameter space, thus enable optimal design of the modulator independently of the unknown parameter. This constellation is sought for codes of two codewords, as well as for zero-rate codes.