Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExplicit Rate-Optimal Streaming Codes with Smaller Field Size
269
0
0.0
(
0
)
Added by
Vinayak Ramkumar
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size $b$ or $a$ random erasures within any window of size $(tau+1)$ time units, under a strict decoding-delay constraint $tau$. The field size over which streaming codes are constructed is an important factor determining the complexity of implementation. The best known explicit rate-optimal streaming code requires a field size of $q^2$ where $q ge tau+b-a$ is a prime power. In this work, we present an explicit rate-optimal streaming code, for all possible ${a,b,tau}$ parameters, over a field of size $q^2$ for prime power $q ge tau$. This is the smallest-known field size of a general explicit rate-optimal construction that covers all ${a,b,tau}$ parameter sets. We achieve this by modifying the non-explicit code construction due to Krishnan et al. to make it explicit, without change in field size.
rate research
Read More
This paper considers the transmission of an infinite sequence of messages (a streaming source) over a packet erasure channel, where every source message must be recovered perfectly at the destination subject to a fixed decoding delay. While the capacity of a channel that introduces only bursts of erasures is well known, only recently, the capacity of a channel with either one burst of erasures or multiple arbitrary erasures in any fixed-sized sliding window has been established. However, the codes shown to achieve this capacity are either non-explicit constructions (proven to exist) or explicit constructions that require large field size that scales exponentially with the delay. This work describes an explicit rate-optimal construction for admissible channel and delay parameters over a field size that scales only quadratically with the delay.
An $(a,b,tau)$ streaming code is a packet-level erasure code that can recover under a strict delay constraint of $tau$ time units, from either a burst of $b$ erasures or else of $a$ random erasures, occurring within a sliding window of time duration $w$. While rate-optimal constructions of such streaming codes are available for all parameters ${a,b,tau,w}$ in the literature, they require in most instances, a quadratic, $O(tau^2)$ field size. In this work, we make further progress towards field size reduction and present rate-optimal $O(tau)$ field size streaming codes for two regimes: (i) $gcd(b,tau+1-a)ge a$ (ii) $tau+1 ge a+b$ and $b mod a in {0,a-1}$.
This paper presents the construction of an explicit, optimal-access, high-rate MSR code for any $(n,k,d=k+1,k+2,k+3)$ parameters over the finite field $fQ$ having sub-packetization $alpha = q^{lceilfrac{n}{q}rceil}$, where $q=d-k+1$ and $Q = O(n)$. The sub-packetization of the current construction meets the lower bound proven in a recent work by Balaji et al. in cite{BalKum}. To our understanding the codes presented in this paper are the first explicit constructions of MSR codes with $d<(n-1)$ having optimal sub-packetization, optimal access and small field size.
We construct maximally recoverable codes (corresponding to partial MDS codes) which are based on linearized Reed-Solomon codes. The new codes have a smaller field size requirement compared with known constructions. For certain asymptotic regimes, the constructed codes have order-optimal alphabet size, asymptotically matching the known lower bound.
Streaming codes represent a packet-level FEC scheme for achieving reliable, low-latency communication. In the literature on streaming codes, the commonly-assumed Gilbert-Elliott channel model, is replaced by a more tractable, delay-constrained, sliding-window (DCSW) channel model that can introduce either random or burst erasures. The known streaming codes that are rate optimal over the DCSW channel model are constructed by diagonally embedding a scalar block code across successive packets. These code constructions have field size that is quadratic in the delay parameter $tau$ and have a somewhat complex structure with an involved decoding procedure. This led to the introduction of simple streaming (SS) codes in which diagonal embedding is replaced by staggered-diagonal embedding (SDE). The SDE approach reduces the impact of a burst of erasures and makes it possible to construct near-rate-optimal streaming codes using Maximum Distance Separable (MDS) code having linear field size. The present paper takes this development one step further, by retaining the staggered-diagonal feature, but permitting the placement of more than one code symbol from a given scalar codeword within each packet. These generalized, simple streaming codes allow us to improve upon the rate of SS codes, while retaining the simplicity of working with MDS codes. We characterize the maximum code rate of streaming codes under a constraint on the number of contiguous packets over which symbols of the underlying scalar code are dispersed. Such a constraint leads to simplified code construction and reduced-complexity decoding.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
