Random Linear Streaming Codes Analyses—Part II: Asymptotics

<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Streaming codes</i> take a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditional <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">block codes</i> and are thus especially appealing for delay sensitive applications. This work studies the asymptotics of random linear streaming codes (RLSCs) in the large finite-field-size regime under the i.i.d. symbol erasure channel models. Two important scenarios are analyzed: (i) tradeoff between decoding deadline Δ and probability of error <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p_e</i> assuming infinite memory α = ∞; and (ii) tradeoff between α and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p_e</i> assuming infinite Δ = ∞. For each scenario, this work derives the corresponding asymptotic constant ρ, power β and decay rate η that satisfy <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p_e</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i>) ∼ ρ<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">β</sup><italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−η<i>x</i></sup>. The results of (i) and (ii) are then used to study an important code design problem: Under a given target deadline Δ, what is the memory length α needed for the error probability <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p_e</i> to be within a factor of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</i> > 1 of the best possible <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i>∗ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>e</i></sub> over α. Further analysis also suggests that regardless the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</i> value being considered, the necessary memory length is approximately 3–7% of the target deadline Δ when Δ is large, the actual percentage depending on the channel model and the coding rate. Such a prediction is consistent with existing brute-force-based evaluations.