Rate-Optimal Streaming Codes with Smaller Field Size Under Less-Stringent Decoding-Delay Requirements
Shobhit Bhatnagar, Vinayak Ramkumar, P. Vijay Kumar · 2022 IEEE Information Theory Workshop (ITW) · 2022
Streaming codes are packet-level erasure-recovery codes which offer reliability in the presence of burst or random packet erasures, while operating under a strict decoding-delay constraint. The Gilbert-Elliott channel model is a commonly-accepted channel model for such settings. Most recent designs of streaming codes are designed for a sliding-window (SW) channel model that may be viewed as a tractable approximation to the GE channel. An (a, b, w)-SW channel, admits only those erasure patterns having the property that within any sliding window of w packet durations, there is either a burst of b packets that is erased, or else a random set of a packets. A streaming code operating over an (a, b, w)-SW channel should be capable of recovering from any admissible erasure pattern and must do so under a decoding-delay constraint τ, meaning that packet t must be decoded upon arrival of packet (t + τ). The focus in the literature has been on the construction of streaming codes that achieve an upper bound on code rate for such a channel and there exist rate-optimal code constructions for any (a, b, w)-SW channel with τ = (w − 1), and for the general case, the field-size requirement is quadratic in w. While a code designed for the case τ = (w − 1) can also be employed in settings where τ > (w − 1), we show in the present paper that it is possible to construct rate-optimal codes specifically for the regime τ ≥ (w − 1 + b − a) that have smaller field-size requirement and are hence simpler to implement. The constructions presented here are based on MDS and binary cyclic codes, corresponding respectively to a linear and binary field-size requirement.