M.Sc Thesis

M.Sc StudentGinzach Shai
SubjectSequential Hypothesis Testing and Channel Coding
with Feedback
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Igal Sason
Full Thesis textFull thesis text - English Version


In this thesis, we review concepts and methods of both sequential hypothesis testing and communication systems with feedback, where variable length coding is used. We begin with a concise review of many aspects of sequential hypothesis testing problems, starting with the problem of sequentially inferring between two simple hypotheses, through problems of composite and multiple hypotheses, and ending with problems in which there exists some feedback mechanism that enables the receiver to control future observations, using the knowledge gathered thus far. The discussion regarding hypothesis testing is concentrated around tests with the property that, as the expected number of observation grows, the average error probability tends to zero, and most of the results stated therein hold under the assumption of this asymptotic regime. Nevertheless, some non-asymptotic results will also be presented, along with very basic and simple sequential tests that have been proposed in the literature. One of the main goals of the work is to illuminate the interplay between sequential hypothesis testing and variable length coding problem in communication. This connection is established in the second part of the thesis, along with a review of some important and relevant results regarding communication systems with feedback. In addition to a review of existing work, we provide some novel results. Specifically, a new communication scheme for variable length coding is proposed and is proven optimal in the error-exponent sense. The novelty here is that it is purely sequential. In addition, for the "stop-feedback" constraint, in which only one feedback bit per message is allowed, bounds on the error exponent function are obtained in the random coding regime. Using these bounds, the exact expression for the random coding error exponent function is found for the binary-symmetric forward channel. This expression is shown to be equal to a well-known lower bound for the same setting.