Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Lower Bound on the Error Exponent of Linear Block Codes over the Erasure Channel
117
0
0.0
(
0
)
Added by
Enrico Paolini
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A lower bound on the maximum likelihood (ML) decoding error exponent of linear block code ensembles, on the erasure channel, is developed. The lower bound turns to be positive, over an ensemble specific interval of erasure probabilities, when the ensemble weight spectral shape function tends to a negative value as the fractional codeword weight tends to zero. For these ensembles we can therefore lower bound the block-wise ML decoding threshold. Two examples are presented, namely, linear random parity-check codes and fixed-rate Raptor codes with linear random precoders. While for the former a full analytical solution is possible, for the latter we can lower bound the ML decoding threshold on the erasure channel by simply solving a 2 x 2 system of nonlinear equations.
rate research
Read More
Applications where multiple users communicate with a common server and desire low latency are common and increasing. This paper studies a network with two source nodes, one relay node and a destination node, where each source nodes wishes to transmit a sequence of messages, through the relay, to the destination, who is required to decode the messages with a strict delay constraint $T$. The network with a single source node has been studied in cite{Silas2019}. We start by introducing two important tools: the delay spectrum, which generalizes delay-constrained point-to-point transmission, and concatenation, which, similar to time sharing, allows combinations of different codes in order to achieve a desired regime of operation. Using these tools, we are able to generalize the two schemes previously presented in cite{Silas2019}, and propose a novel scheme which allows us to achieve optimal rates under a set of well-defined conditions. Such novel scheme is further optimized in order to improve the achievable rates in the scenarios where the conditions for optimality are not met.
Using tools developed in a recent work by Shen and the second author, in this paper we carry out an in-depth study on the average decoding error probability of the random matrix ensemble over the erasure channel under three decoding principles, namely unambiguous decoding, maximum likelihood decoding and list decoding. We obtain explicit formulas for the average decoding error probabilities of the random matrix ensemble under these three decoding principles and compute the error exponents. Moreover, for unambiguous decoding, we compute the variance of the decoding error probability of the random matrix ensemble and the error exponent of the variance, which imply a strong concentration result, that is, roughly speaking, the ratio of the decoding error probability of a random code in the ensemble and the average decoding error probability of the ensemble converges to 1 with high probability when the code length goes to infinity.
The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashevs classic result is extended and a single letter characterization for the reliability function of finite-state Markov channels is presented, under the assumption that the channel state is causally observed both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference. In particular the convex analytical approach to Markov decision processes is adopted to handle problems with stopping time horizons arising from variable-length coding schemes.
We consider the classic joint source-channel coding problem of transmitting a memoryless source over a memoryless channel. The focus of this work is on the long-standing open problem of finding the rate of convergence of the smallest attainable expected distortion to its asymptotic value, as a function of blocklength $n$. Our main result is that in general the convergence rate is not faster than $n^{-1/2}$. In particular, we show that for the problem of transmitting i.i.d uniform bits over a binary symmetric channels with Hamming distortion, the smallest attainable distortion (bit error rate) is at least $Omega(n^{-1/2})$ above the asymptotic value, if the ``bandwidth expansion ratio is above $1$.
We show that Reed-Muller codes achieve capacity under maximum a posteriori bit decoding for transmission over the binary erasure channel for all rates $0 < R < 1$. The proof is generic and applies to other codes with sufficient amount of symmetry as well. The main idea is to combine the following observations: (i) monotone functions experience a sharp threshold behavior, (ii) the extrinsic information transfer (EXIT) functions are monotone, (iii) Reed--Muller codes are 2-transitive and thus the EXIT functions associated with their codeword bits are all equal, and (iv) therefore the Area Theorem for the average EXIT functions implies that RM codes threshold is at channel capacity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
