A Caltech Library Service

Instantaneous SED coding over a DMC

Guo, Nian and Kostina, Victoria (2021) Instantaneous SED coding over a DMC. In: 2021 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, pp. 148-153. ISBN 9781538682098.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


In this paper, we propose a novel code for transmitting a sequence of n message bits in real time over a discrete-memoryless channel (DMC) with noiseless feedback, where the message bits stream into the encoder one by one at random time instants. Similar to existing posterior matching schemes with block encoding, the encoder in our work takes advantage of the channel feedback to form channel inputs that contain the information the decoder does not yet have, and that are distributed close to the capacity-achieving input distribution, but dissimilar to the existing posterior matching schemes, the encoder performs instantaneous encoding - it immediately weaves the new message bits into a continuing transmission. A posterior matching scheme by Naghshvar et al. partitions the source messages into groups so that the group posteriors have a small-enough difference (SED) to the capacity-achieving distribution, and transmits the group index that contains the actual message. Our code adopts the SED rule to apply to the evolving message alphabet that contains all the possible variable-length strings that the source could have emitted up to that time. Our instantaneous SED code achieves better delay-reliability tradeoffs than existing feedback codes over 2-input DMCs: we establish this dominance both by simulations and via an analysis comparing the performance of the instantaneous SED code to Burnashev’s reliability function. Due to the message alphabet that grows exponentially with time t, the complexity of the instantaneous SED code is double-exponential in t. To overcome this complexity barrier to practical implementation, we design a low-complexity code for binary symmetric channels that we name the instantaneous type set SED code. It groups the message strings into sets we call type sets and tracks their prior and posterior probabilities jointly, resulting in the reduction of complexity from double-exponential to O(t⁴). Simulation results show that the gap in performance between the instantaneous SED code and the instantaneous type-set SED code is negligible.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Guo, Nian0000-0003-4490-328X
Kostina, Victoria0000-0002-2406-7440
Additional Information:© 2021 IEEE. This work was supported in part by the National Science Foundation (NSF) under grants CCF-1751356 and CCF-1956386. Stimulating discussions with Prof. Richard Wesel, Amaael Antonini, and Prof. Aaron Wagner are gratefully acknowledged.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20210323-145545445
Persistent URL:
Official Citation:N. Guo and V. Kostina, "Instantaneous SED coding over a DMC," 2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 148-153, doi: 10.1109/ISIT45174.2021.9518087
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108537
Deposited By: Tony Diaz
Deposited On:24 Mar 2021 21:31
Last Modified:24 Oct 2022 22:43

Repository Staff Only: item control page