The problem of recovering from qubit erasures has recently gained attention as erasures occur in many physical systems such as photonic systems, trapped ions, superconducting qubits and circuit quantum electrodynamics. While several linear-time decoders for error correction are known, their errorcorrecting capability is limited to half the minimum distance of the code, whereas erasure correction allows one to go beyond this limit. As in the classical case, stopping sets pose a major challenge in designing efficient erasure decoders for quantum LDPC codes. In this paper, we show through simulation, that an attractive alternative here, is the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity. We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation, to improve decoding performance and their associated complexity.

Quantum low density parity-check (QLDPC) codes represent an attractive candidate for achieving fault-tolerant quantum computation. Erasure decoding of QLDPC codes has gained traction recently as many physical systems such as neutral-atom systems, photonic systems, trapped-ion systems etc. suffer from qubit erasures. Techniques for erasure decoding of QLDPC codes via belief propagation (BP) have been proposed in the literature, such as BP with guided decimation (BP-GD), where decimation refers to sequentially fixing hard values for the variable nodes. We provide an alternative decimation-based BP algorithm, which we term the BP with degree-based decimation (BP-DD) algorithm, that intelligently chooses a check node based on its degree and subsequently decimates a variable node in its neighborhood. We apply the BP-DD algorithm to two families of QLDPC codes, namely hypergraph product codes and lifted product codes, and show improved logical error performance over the BP-GD algorithm, without incurring additional complexity. Our simulations show that the BP-DD algorithm provides a versatile solution for erasure decoding of QLDPC codes, in contrast to some techniques in the literature that are applicable to only specific classes of QLDPC codes.

Streaming codes are codes designed to ensure erased packet recovery within a decoding-delay deadline. In streaming code literature, a sliding-window (SW) channel model is considered called the (a, b,w)-SW channel model. In the (a, b,w)-SW channel, within any window ofwtime slots, either a burst of ≤bconsecutive packets, or else ≤apackets at random can be erased. An (a, b,w,≤ ) streaming code is capable of recovering messages under a decoding-delay of τ time slots, from any erasure pattern produced by the (a, b,w)-SW channel. For any given (a, b,w)-SW channel, the minimum delay with which the maximum rate possible over this channel can be achieved is τ =w− 1. Rate-optimal constructions of streaming codes for parameters of the form (a, b,w, τ =w− 1) are known, and these constructions require a field size that is quadratic in w in general. In this paper, we show that is possible to construct linear field size streaming codes for all {a, b,w} parameters, by sacrificing a little on either delay or rate. Moreover, we characterize the existence of binary, rate-optimal (a, b,w, τ =w−1) streaming codes constructed via the popular technique of diagonal embedding. Further, under a less-stringent decoding-delay requirement of τ = (w+b−a−1), it is shown that binary, rate-optimal streaming codes can be constructed for certain parameters. Streaming codes for a more general class of SW channels that allow unerased packets within a burst erasure are also investigated.

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$\leq b$packets along with$\leq e$random packet erasures, or else,$\leq 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.

Streaming codes (SCs) are packet-level codes that recover erased packets within a strict decoding-delay deadline. SCs for various packet erasure channel models such as sliding-window (SW) channel models that admit random or burst erasures in any SW of a fixed length have been studied in the literature, and their optimal rate has been characterized. In this paper, we study error-correcting streaming codes (SCERRS), i.e., packet-level codes which recover erroneous packets within a delay constraint. We study SCERRSfor two classes of SW channel models, one that admits random packet errors, and another that admits multiple bursts of packet errors, in any SW of a fixed length. For the case of random packet errors, we establish the equivalence of an$SC_{ERR}$and a corresponding SC that recovers from random packet erasures, thus determining the optimal rate of an SCERRfor this setting. We then focus on SCs that recover from multiple erasure bursts and derive a rate-upper-bound for such SCS. We show the necessity of a divisibility constraint for the existence of an SC constructed by the popular diagonal embedding technique, that achieves this rate-bound under a stringent delay requirement. Sufficiency of this divisibility constraint follows from a construction known in prior literature. We further show the equivalence of the SCs considered and SCERRS for the setting of multiple error bursts, under a stringent delay requirement.

Gottesman-Kitaev-Preskill (GKP) codes are stabi-lizer codes that allow one to encode qubits into oscillators, and are known to be hardware efficient. The stabilizer group of a G KP code 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 G KP code based on the Euler decomposition of this symplectic matrix has been derived in the literature. We derive an upper-bound that is tighter than this bound whenever this symplectic matrix is not orthogonal. This enables us to show that the bound in the prior literature is tight only for the non-interesting case when the symplectic matrix is orthogonal. We then provide some necessary conditions for a class of G KP codes to achieve the improved upper bound. This allows us to upper-bound the largest possible distance of a G KP code in this class.

Streaming codes are codes designed to ensure erased packet recovery with a decoding-delay deadline. In streaming code literature, an (a, b, w) sliding-window (SW) channel model is considered, in which within any window of w time slots, either a burst of ≤ b packets, or else ≤ a random packets can be erased. An (a, b, w, τ) streaming code is a packet-level code capable of recovering messages under a decoding delay of τ time slots, from any erasure pattern produced by an (a, b, w)-SW channel. For any given (a, b, w)-SW channel, the minimum delay with which the maximum rate possible over this channel can be achieved is τ = w−1. Rate-optimal constructions of streaming codes for any parameter tuple of the form (a, b, w, τ = w−1) are known in the literature. However, these constructions require a field size that is quadratic in w in general, and linear field size constructions are known only for a subset of {a, b, w} parameters. The current paper shows that it is possible to construct linear field size streaming codes for all {a, b, w} parameters, by sacrificing a little on either delay or rate. When the allowed delay is one more than the minimum, i. e., when τ = w, we construct linear field size rate-optimal streaming codes for all possible {a, b, w} parameters. This construction also leads to an O(w) field size (a, b, w, τ = w − 1) streaming code whose rate is close to the optimal rate. Additionally, we show that our construction can be modified to get binary streaming codes without too much loss in rate.

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.

Streaming codes may be regarded as packet-level convolutional codes that guarantee recovery from packet erasures under a strict decoding-delay constraint and are hence relevant to the low-latency objective of many modern communication systems. Past study of these codes has focused on performance over a tractable approximation of the Gilbert-Elliott channel model, known as the delay-constrained sliding window (DCSW) channel model. Under the DCSW channel model, within any sliding window of length w there can either be (i) a burst of at most b packet erasures or (ii) at most a random packet erasures. We study here, an extended version of the first constraint which permits e random erasures in addition to a burst of b erasures. We show that the capacity of this extended DCSW channel is strictly less than that of the corresponding DCSW channel in which b is replaced by $b+e$. Cyclic codes are easy to implement and are inherently well-suited to burst-erasure recovery. We identify a necessary and sufficient condition on the parity polynomial of an $[n, k]$ cyclic code that allows the code to recover from any burst of $n-k-s$ erasures along with any $\rho$ random erasures, $1 \leq \rho \leq s \leq n-k$. We use this result to construct cyclic codes that provide reliable communication over the extended DCSW channel for certain parameters.