On Information-Debt-Optimal Streaming Codes With Small Memory

In the context of an (n,k,m) convolutional code where k is the number of message symbols, n the number of code symbols and m the memory, Martinian [1] introduced the concept of information debt whose value at time t is the number of additional coded symbols needed to decode all prior message symbols. The same paper shows the existence of (n,k,m) convolutional codes that can recover all prior message symbols whenever the symbol-erasure pattern is such that the maximum time interval τ between successive returns to zero of the information debt function is at most m. The parameter τ also represents the worst-case delay in decoding a message symbol. In the present paper, we study (n,k,m) convolutional codes that possess the analogous property for the case τ > m whenever it is possible to do so. We will refer to such codes as information-debt-optimal streaming (iDOS) codes. We prove the existence of periodically time-varying iDOS codes for all possible {n,k,m,τ} parameters. We also show that m-MDS codes and Maximum Distance Profile convolutional codes are iDOS codes for certain parameter ranges. As a by-product of our existence result, the minimum memory needed for a particular class of streaming codes studied earlier in the literature, is determined.