  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. We also design a
low-complexity code for binary symmetric channels that we name the
instantaneous type set SED code with complexity $O(t^4)$. Simulation results
show that the gap in performance between the instantaneous SED code and the
instantaneous type-set SED code is negligible.
