WE2.R8.3

On Streaming Codes for Simultaneously Correcting Burst and Random Erasures

Shobhit Bhatnagar, Indian Institute of Science, India; Biswadip Chakraborty, Qualcomm, India; P Vijay Kumar, Indian Institute of Science, India

Session:
Convolutional and Streaming Codes 2

Track:
2: Modern Coding Theory

Location:
Omega

Presentation Time:
Wed, 10 Jul, 12:10 - 12:30

Session Chair:
Wenhui Sui, UCLA
Abstract
Streaming codes are packet-level codes that recover dropped packets within a strict decoding-delay constraint. We study streaming codes over a sliding-window (SW) channel model which admits only those erasure patterns which allow either a single burst erasure of \(\le b\) packets along with \(\le e\) random packet erasures, or else, \(\le a\) random packet erasures, in any sliding-window of \(w\) time slots. We determine the optimal rate of a streaming code constructed via the popular diagonal embedding (DE) technique over such a SW channel under delay constraint \(\tau=(w-1)\) and provide an \(O(w)\) field size code construction. For the case \(e>1\), we show that it is not possible to significantly reduce this field size requirement, assuming the well-known MDS conjecture. We then provide a block code construction whose DE yields a streaming code achieving the rate derived above, over a field of size sub-linear in \(w,\) for a family of parameters having \(e=1.\) We show the field size optimality of this construction for some parameters, and near-optimality for others under a sparsity constraint. Additionally, we derive an upper-bound on the minimum distance of a cyclic code and characterize cyclic codes which achieve this bound via their ability to simultaneously recover from burst and random erasures.
Resources