Streaming Codes for Low-Latency Communication over Various Sliding-Window Channel Models

Abstract

Streaming codes are packet-level codes that recover dropped (i.e., erased) packets within a decoding-delay deadline. A common model for packet erasures over a network is the Markov, two-state Gilbert-Elliott (GE) channel model. However, due to the intractability of the GE channel model, streaming code literature has instead focused on sliding-window (SW) approximations to the GE channel model. The primary focus of this thesis is the construction of streaming codes for various classes of SW channel models. A secondary focus of this thesis is a class of quantum error-correcting codes called Gottesman-Kitaev-Preskill (GKP) codes which have been demonstrated to be a hardware-efficient means for achieving quantum error-correction.

A SW channel model that has received considerable interest in the streaming code literature is one that admits in any SW either a single burst erasure or else a few random erasures. The optimal rate as well as rate-optimal code constructions of streaming codes for such a channel model are known in the literature. However, in general, these code constructions require a field size that is quadratic in the SW length. We provide a linear field size code construction that has either a near-optimal rate with optimal delay or near-optimal delay with optimal rate. When the delay constraint is less stringent, we also show how one can use binary cyclic codes to construct rate-optimal streaming codes. A popular technique to construct streaming codes is via diagonal embedding (DE) of a scalar block code in the packet stream. We characterize the existence of binary rate-optimal streaming codes constructed via DE when the delay requirement is stringent.

We next study streaming codes for a class of SW channels that allow both burst and random erasures to occur simultaneously within the same SW. By deriving upper bounds to the rate of a streaming code for such a channel model, we show that the optimal rate of a streaming code under this channel model is strictly less than that of a streaming code for a corresponding channel model that allows only either burst or random erasures in any given SW. We then characterize the optimal rate of a streaming code for the case when the number of random erasures that can simultaneously occur with the burst erasure is large. When this number is small, we characterize the optimal rate of a streaming code constructed via DE. We then show that if the channel allows more than a single random erasure to occur simultaneously with the burst erasure, then one needs a field size that is close to the SW length to achieve this rate. However, for the case when the SW channel produces only a single random erasure along with the burst, we provide a code construction that reduces this field size requirement under certain conditions. In a related context, we investigate the ability of a cyclic code to recover from simultaneous burst and random erasures.

We then introduce the notion of error-correcting streaming codes, i.e., streaming codes that recover erroneous packets, as opposed to erased packets, within a decoding-delay constraint. We determine the optimal rate and provide a rate-optimal code construction of error-correcting streaming codes for a class of SW channels that produce random packet errors within any SW, by establishing an equivalence with corresponding erasure-correcting streaming codes. We show a similar equivalence between burst error-correcting and burst erasure-correcting streaming codes and further show the necessity of a divisibility constraint in order to construct a rate-optimal burst error-correcting streaming code via DE.

In the presence of long burst erasures, which could arise, for example, from a deep fade, providing a decoding-delay guarantee becomes difficult when the source and destination are connected via a single link/path. In many 5G settings, such as dual connectivity and integrated access and backhaul, the source and destination are linked via multiple paths, which can provide link diversity to combat deep fades. Motivated by this, we study multi-path streaming codes, where we model each path as a SW erasure channel model which admits either a single burst erasure or else a few random erasures within any SW. We study such multi-path streaming codes under two settings, (a) the case when at most a fixed number of paths can have inadmissible erasure patterns, including the case of long bursts, and (b) the case when at most a fixed number of paths can simultaneously witness a burst at any time. For (a), we derive a rate upper-bound and provide matching code constructions. For (b), we show that it is possible to achieve a higher rate than the maximum possible in (a) for certain parameter sets.

We then study GKP codes, which are a class of continuous-variable quantum error-correcting codes that enable the encoding of qubits into the Hilbert space of a quantum harmonic oscillator. GKP codes are stabilizer codes whose stabilizer group is isomorphic to a lattice. A particular generator matrix of this lattice can be related to a canonical form via a symplectic matrix. An upper bound to the distance of a GKP code based on this symplectic matrix has been derived in the literature. We derive an upper-bound that is tighter than this bound. We then derive some necessary conditions for a class of GKP codes to achieve the improved upper bound. This also allows us to upper-bound the largest possible distance of a GKP code within this sub-class.