Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStaggered Diagonal Embedding Based Linear Field Size Streaming Codes
213
0
0.0
(
0
)
Added by
Myna Vajha
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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}$.
rate research
Read More
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.
We obtain a characterization on self-orthogonality for a given binary linear code in terms of the number of column vectors in its generator matrix, which extends the result of Bouyukliev et al. (2006). As an application, we give an algorithmic method to embed a given binary $k$-dimensional linear code $mathcal{C}$ ($k = 2,3,4$) into a self-orthogonal code of the shortest length which has the same dimension $k$ and minimum distance $d ge d(mathcal{C})$. For $k > 4$, we suggest a recursive method to embed a $k$-dimensional linear code to a self-orthogonal code. We also give new explicit formulas for the minimum distances of optimal self-orthogonal codes for any length $n$ with dimension 4 and any length $n otequiv 6,13,14,21,22,28,29 pmod{31}$ with dimension 5. We determine the exact optimal minimum distances of $[n,4]$ self-orthogonal codes which were left open by Li-Xu-Zhao (2008) when $n equiv 0,3,4,5,10,11,12 pmod{15}$. Then, using MAGMA, we observe that our embedding sends an optimal linear code to an optimal self-orthogonal code.
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.
This paper considers the problem of simultaneously communicating two messages, a high-security message and a low-security message, to a legitimate receiver, referred to as the security embedding problem. An information-theoretic formulation of the problem is presented. A coding scheme that combines rate splitting, superposition coding, nested binning and channel prefixing is considered and is shown to achieve the secrecy capacity region of the channel in several scenarios. Specifying these results to both scalar and independent parallel Gaussian channels (under an average individual per-subchannel power constraint), it is shown that the high-security message can be embedded into the low-security message at full rate (as if the low-security message does not exist) without incurring any loss on the overall rate of communication (as if both messages are low-security messages). Extensions to the wiretap channel II setting of Ozarow and Wyner are also considered, where it is shown that perfect security embedding can be achieved by an encoder that uses a two-level coset code.
The conventional theory of linear network coding (LNC) is only over acyclic networks. Convolutional network coding (CNC) applies to all networks. It is also a form of LNC, but the linearity is w.r.t. the ring of rational power series rather than the field of data symbols. CNC has been generalized to LNC w.r.t. any discrete valuation ring (DVR) in order for flexibility in applications. For a causal DVR-based code, all possible source-generated messages form a free module, while incoming coding vectors to a receiver span the emph{received submodule}. An existing emph{time-invariant decoding} algorithm is at a delay equal to the largest valuation among all invariant factors of the received submodule. This intrinsic algebraic attribute is herein proved to be the optimal decoding delay. Meanwhile, emph{time-variant decoding} is formulated. The meaning of time-invariant decoding delay gets a new interpretation through being a special case of the time-variant counterpart. The optimal delay turns out to be the same for time-variant decoding, but the decoding algorithm is more flexible in terms of decodability check and decoding matrix design. All results apply, in particular, to CNC.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
