Optimal Streaming Codes for Channels with Burst and Arbitrary Erasures
0
Citation
0
Reference
10
Related Paper
Abstract:
This paper considers transmitting a sequence of messages (a streaming source) over a packet erasure channel. In each time slot, the source constructs a packet based on the current and the previous messages and transmits the packet, which may be erased when the packet travels from the source to the destination. Every source message must be recovered perfectly at the destination subject to a fixed decoding delay. We assume that the channel loss model introduces either one burst erasure or multiple arbitrary erasures in any fixed-sized sliding window. Under this channel loss assumption, we fully characterize the maximum achievable rate by constructing streaming codes that achieve the optimal rate. In addition, our construction of optimal streaming codes implies the full characterization of the maximum achievable rate for convolutional codes with any given column distance, column span and decoding delay. Numerical results demonstrate that the optimal streaming codes outperform existing streaming codes of comparable complexity over some instances of the Gilbert-Elliott channel and the Fritchman channel.Keywords:
Erasure
Binary erasure channel
Erasure code
Convolutional code
Online codes
Luby transform code
In the paper an adaptive binary coding/decoding procedure of data transmission over the limited capacity packet erasure communication channel is numerically studied by example of unmanned aerial vehicles formation control over the communication network. Dependence of tracking accuracy on data erasure probability p is found based on the simulations.
Erasure
Binary erasure channel
Erasure code
Cite
Citations (7)
LT codes are a class of rateless codes designed for data dissemination on erasure channels. In this paper, we present a decoder for LT codes on partial erasure channels, which were recently introduced for multi-level read storage channel applications. We compare the efficiency of LT codes on these channels to those on the q-ary Erasure Channel (QEC).
Erasure
Erasure code
Online codes
Binary erasure channel
Luby transform code
Fountain code
Tornado code
Cite
Citations (1)
Motivated by applications of rateless coding, decision feedback, and automatic repeat request (ARQ), we study the problem of universal decoding for unknown channels in the presence of an erasure option. Specifically, we harness the competitive minimax methodology developed in earlier studies, in order to derive a universal version of Forney's classical erasure/list decoder, which in the erasure case, optimally trades off between the probability of erasure and the probability of undetected error. The proposed universal erasure decoder guarantees universal achievability of a certain fraction xi of the optimum error exponents of these probabilities. A single-letter expression for xi, which depends solely on the coding rate and the Neyman-Pearson threshold, is provided. The example of the binary symmetric channel is studied in full detail, and some conclusions are drawn.
Erasure
Erasure code
Binary erasure channel
Binary symmetric channel
Online codes
Probability of error
Cite
Citations (1)
We consider a real-time streaming system where messages are created sequentially at the source, and are encoded for transmission over a packet erasure channel. Each message must subsequently be decoded at the receiver within a given delay from its creation time. We consider code design and maximum message rates when all messages must be decodable by their respective deadlines under a specified set of erasure patterns (erasure model). Specifically, we provide a code construction that achieves the optimal rate for an asymptotic number of messages, under erasure models containing a limited number of erasures per coding window, per sliding window, and containing erasure bursts of a limited length.
Erasure
Erasure code
Binary erasure channel
Sliding window protocol
Online codes
Code (set theory)
Cite
Citations (69)
Streaming erasure codes guarantee that each source packet is recovered within a fixed delay at the receiver over a burst-erasure channel. This paper introduces a new class of streaming codes: Diversity Embedded Streaming Erasure Codes (DE-SCo), that provide a flexible tradeoff between the channel quality and receiver delay. When the channel conditions are good, the source stream is recovered with a low delay, whereas when the channel conditions are poor the source stream is still recovered, albeit with a larger delay. Information theoretic analysis of the underlying burst-erasure broadcast channel reveals that DE-SCo achieve the minimum possible delay for the weaker user, without sacrificing the single-user optimal performance of the stronger user. Our constructions are explicit, incur polynomial time encoding and decoding complexity and outperform random linear codes over burst-erasure channels.
Erasure
Binary erasure channel
Erasure code
Online codes
Luby transform code
Cite
Citations (0)
In this Letter, the authors introduce optimisation design technique of systematic Luby transform (SLT) codes over binary erasure channel (BEC). SLT codes are more efficient than Luby transform (LT) codes since the former ones can recover source symbols more quickly. There was some work about designing degree distribution in LT codes and it was shown that erasure probability barely impact performances of LT codes. Using degree distributions designed for LT codes directly in SLT codes does not provide satisfied performances. For the first time, they introduce erasure probability as a parameter to establish a linear programming model in SLT codes. By applying And–or Tree analysis, they propose the asymptotic analysis formulae of SLT codes over BEC. To achieve the goal of recovering source symbols as soon as possible, the authors' objective of optimisation is to minimise overhead. Simulations are offered to validate the performance of their optimisation result. Besides, their degree distribution outperforms other distributions with respect to bit error ratio.
Luby transform code
Online codes
Binary erasure channel
Fountain code
Tornado code
Erasure
Erasure code
Cite
Citations (2)
Multi-erasure locally recoverable codes play a very significant role in distributed data storage. The advantage of multi-erasure locally recoverable codes is that it has local and global erasure-correcting characteristics. Recently, based on classical algebraic geometry codes, Huang et al. constructed a family of explicit optimal multi-erasure locally recoverable codes over small finite fields F4. In this work, based on the work of Huang et al., we use cyclic codes to construct a family of new optimal multi-erasure locally recoverable codes over small finite fields F3. It turns out that our multi-erasure locally recoverable codes have smaller finite fields than the previously known results.
Erasure
Erasure code
Online codes
Tornado code
Storage efficiency
Distributed data store
Cite
Citations (0)
Rapid Tornado code is constructed from a Luby Transform code concatenated with a precode. This code is used to protect data sent over an erasure channel. An erasure channel will typically corrupt a number of transmitted data, causing the loss of several information symbols. Despite this loss, the transmitted data can still be reconstructed by the receiver if Rapid Tornado or Luby Transform code is used. In this paper, an encoding and decoding process using Rapid Tornado and Reed-Solomon precode is simulated with 9 information symbols sent over an erasure channel. The simulation result is compared to that of a Luby Transform code. It is shown that Rapid Tornado enables the reconstruction of data despite the loss of codewords transmitted over an erasure channel.
Kata kunci : Binary Erasure Channel, Rapid Tornado, Luby Transform, degree distribution
Binary erasure channel
Erasure code
Tornado code
Online codes
Code (set theory)
Luby transform code
Erasure
Reed–Solomon error correction
Cite
Citations (0)
We study windowed decoding of spatially coupled codes when the transmission occurs over the binary erasure channel. We characterize the performance of this scheme by defining thresholds on channel erasure rates that guarantee a target bit erasure rate. We give analytical lower bounds on these thresholds and show that the performance approaches that of belief propagation exponentially fast in the window size. We give numerical results including the thresholds computed using density evolution and the erasure rate curves for finite-length spatially coupled codes.
Erasure
Binary erasure channel
Erasure code
Luby transform code
Tornado code
Online codes
Cite
Citations (12)
We evaluate the performance of two types of erasure coding schemes for broadcasting small files over erasure channels with low bandwidth. One type is based on maximal distance separable (MDS) codes, while the other type uses low-density parity-check codes. The channel model is relevant to a variety of applications, such as the bootstrapping phase of a wireless sensor network. Our results show that erasure codes of the former type require a smaller total transmission time than codes of the latter type when the number of packets is not large. In addition to classical Reed-Solomon codes, we also consider a family of MDS codes defined by Cauchy matrices and analyze their decoding complexities for erasure codes.
Erasure code
Erasure
Tornado code
Binary erasure channel
Luby transform code
Online codes
Fountain code
Cite
Citations (0)