Explicit Information-Debt-Optimal Streaming Codes With Small Memory

Abstract

For a convolutional code in the presence of a symbol erasure channel, the information debt $I(t)$ at time $t$ provides a measure of the number of additional code symbols required to recover all message symbols up to time $t$. Information-debt-optimal streaming ($i$DOS) codes are convolutional codes which allow for the recovery of all message symbols up to $t$ whenever $I(t)$ turns zero under the following conditions; (i) information debt can be non-zero for at most $\tau$ consecutive time slots and (ii) information debt never increases beyond a particular threshold. The existence of periodically-time-varying $i$DOS codes are known for all parameters. In this paper, we address the problem of constructing explicit, time-invariant $i$DOS codes. We present an explicit time-invariant construction of $i$DOS codes for the unit memory ($m=1$) case. It is also shown that a construction method for convolutional codes due to Almeida et al. leads to explicit time-invariant $i$DOS codes for all parameters. However, this general construction requires a larger field size than the first construction for the $m=1$ case.

Accepted to 2023 IEEE International Symposium on Information Theory (ISIT)