Sergey Tridenski


Tel-Aviv University

Natural Type Selection in Channels and Exponential Source/Channel Duality

and adaptive coding techniques, using a (preferably limited) feedback link from the receiver to the transmitter. This work focuses on several information-theoretic aspects of this problem. In the first part we consider a channel-independent decoder which is for i.i.d. random codes what the maximum mutual-information decoder is for constant composition codes. We show that this decoder results in exactly the same i.i.d. random coding error exponent and almost the same correct-decoding exponent for a given codebook distribution as the maximum-likelihood decoder. We propose an algorithm for computation of the optimal correct-decoding exponent which operates on the corresponding expression for the channel-independent decoder. The proposed algorithm comes in fixed-rate and fixed-slope versions. The fixed-slope version of the algorithm presents an alternative to the Arimoto algorithm for computation of the random coding exponent function in the correct-decoding regime. The fixed-rate version of the computation algorithm translates into a stochastic iterative algorithm for adaptation of the i.i.d. codebook distribution to a discrete memoryless channel in the limit of large block length. The adaptation scheme uses i.i.d. random codes with the channel-independent decoder and relies on one bit of feedback per transmitted block. The communication itself is assumed reliable at a constant rate. In the end of the iterations the resulting codebook distribution guarantees reliable communication for all rates below for some predetermined parameter of decoding confidence , provided that  is less than the channel capacity. In the second part, we propose a source/channel duality in the exponential regime, where success/failure in source coding parallels error/correctness in channel coding, and a distortion constraint becomes a log-likelihood ratio (LLR) threshold. We establish this duality by first deriving exact exponents for lossy coding of a memoryless source, at distortion, for a general i.i.d. codebook distribution, for both encoding success () and failure (). We then turn to maximum likelihood (ML) decoding over a memoryless channel with an i.i.d. input, and show that if we substitute, , and under the LLR distortion measure, then the exact exponents for decoding-error () and strict correct-decoding () follow as special cases of the exponents for source encoding success/failure, respectively. Moreover, by letting the threshold take general values, the exact random-coding exponents for erasure () and list decoding () under the simplified Forney decoder are obtained. Finally, we derive the exact random-coding exponent for Forney's optimum tradeoff erasure/list decoder, and show that at the erasure regime it coincides with Forney's lower bound and with the simplified decoder exponent, settling a long standing conjecture. Ph.D. student under the supervision of Prof. Ram Zamir.

Date: Thu 16 May 2019

Start Time: 14:30

End Time: 15:30

1061 | Electrical Eng. Building