Raptor codes on binary memoryless symmetric channels

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the stability condition to the class of Raptor codes. This generalization gives a lower bound on the fraction of output nodes of degree 2 of a Raptor code if the error probability of the belief-propagation decoder converges to zero. Using information-theoretic arguments, we will show that if a sequence of output degree distributions is to achieve the capacity of the underlying channel, then the fraction of nodes of degree 2 in these degree distributions has to converge to a certain quantity depending on the channel. For the class of erasure channels this quantity is independent of the erasure probability of the channel, but for many other classes of BIMSCs, this fraction depends on the particular channel chosen. This result has implications on the "universality" of Raptor codes for classes other than the class of erasure channels, in a sense that will be made more precise in the paper. We will also investigate the performance of specific Raptor codes which are optimized using a more exact version of the Gaussian approximation technique.     

List decoding from erasures: bounds and code constructions

We consider the problem of list decoding from erasures. We establish lower and upper bounds on the rate of a (binary linear) code that can be list decoded with list size L when up to a fraction p of its symbols are adversarially erased. Such bounds already exist in the literature, albeit under the label of generalized Hamming weights, and we make their connection to list decoding from erasures explicit. Our bounds show that in the limit of large L, the rate of such a code approaches the "capacity" (1 - p) of the erasure channel. Such nicely list decodable codes are then used as inner codes in a suitable concatenation scheme to give a uniformly constructive family of asymptotically good binary linear codes of rate /spl Omega/(/spl epsiv//sup 2//log(1//spl epsiv/)) that can be efficiently list-decoded using lists of size O(1//spl epsiv/) when an adversarially chosen (1 - /spl epsiv/) fraction of symbols are erased, for arbitrary /spl epsiv/ > 0. This improves previous results in this vein, which achieved a rate of /spl Omega/(/spl epsiv//sup 3/log(1//spl epsiv/)).     

无速率编码及其应用综述

纠错编码技术通过引入冗余增加可靠性,是现代通信的关键技术之一。无速率编码是一类新兴纠错编码,其速率可以根据信道状态自适应改变,编译码算法较为简单,且性能优异,可以适用于不同的应用场景,因此受到了国内外学者和工业界的关注。介绍了4种经典或新兴的无速率编码方案,包括卢比变换(Luby Transform,LT)码、Raptor码、在线喷泉码(OFC)和BATS(Batched Sparse)码。介绍无速率编码的基本原理,通过其发展过程比较不同无速率编码的特点。阐述了这些无速率编码的编译码方法,并简要介绍其最新的研究进展。最后,介绍无速率编码在广播通信及不等差保护、无线传感器网络、车联网、存储以及分布式计算等新老场景中的应用。无速率编码是一种复杂度低、灵活度高的编码,随着新型无速率编码的发展,在未来的分布式系统等场景中将会有更广泛的应用。     

The empirical distribution of good codes

Let the kth-order empirical distribution of a code be defined as the proportion of k-strings anywhere in the codebook equal to every given k-string. We show that for any fixed k, the kth-order empirical distribution of any good code (i.e., a code approaching capacity with vanishing probability of error) converges in the sense of divergence to the set of input distributions that maximize the input/output mutual information of k channel uses. This statement is proved for discrete memoryless channels as well as a large class of channels with memory. If k grows logarithmically (or faster) with blocklength, the result no longer holds for certain good codes, whereas for other good codes, the result can be shown for k growing as fast as a certain fraction of blocklength     

On the MDL principle for i.i.d. sources with large alphabets

Average case universal compression of independent and identically distributed (i.i.d.) sources is investigated, where the source alphabet is large, and may be sublinear in size or even larger than the compressed data sequence length n. In particular, the well-known results, including Rissanen's strongest sense lower bound, for fixed-size alphabets are extended to the case where the alphabet size k is allowed to grow with n. It is shown that as long as k=o(n), instead of the coding cost in the fixed-size alphabet case of 0.5logn extra code bits for each one of the k-1 unknown probability parameters, the cost is now 0.5log(n/k) code bits for each unknown parameter. This result is shown to be the lower bound in the minimax and maximin senses, as well as for almost every source in the class. Achievability of this bound is demonstrated with two-part codes based on quantization of the maximum-likelihood (ML) probability parameters, as well as by using the well-known Krichevsky-Trofimov (KT) low-complexity sequential probability estimates. For very large alphabets, kGtn, it is shown that an average minimax and maximin bound on the redundancy is essentially (to first order) log(k/n) bits per symbol. This bound is shown to be achievable both with two-part codes and with a sequential modification of the KT estimates. For k=Theta(n), the redundancy is Theta(1) bits per symbol. Finally, sequential codes are designed for coding sequences in which only m相似文献   

Fountain码编译码算法结构的改进

在LT码的基础上对Raptor码进行了分析。根据IRA码的结构及其线性时间的编译码特性,提出了Raptor码和IRA码相结合的改进Fountain码结构。研究结果表明,该结构既保持了线性的编译码特性又能有效增强信元的恢复能力。利用其它编码技术与Raptor码相结合是今后进一步的研究方向。     

Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels

A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity I(W) of any given binary-input discrete memoryless channel (B-DMC) W. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of N independent copies of a given B-DMC W, a second set of N binary-input channels {WN(i)1 les i les N} such that, as N becomes large, the fraction of indices i for which I(WN(i)) is near 1 approaches I(W) and the fraction for which I(WN(i)) is near 0 approaches 1-I(W). The polarized channels {WN(i)} are well-conditioned for channel coding: one need only send data at rate 1 through those with capacity near 1 and at rate 0 through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC W with I(W) > 0 and any target rate R< I(W) there exists a sequence of polar codes {Cfrn;nges1} such that Cfrn has block-length N=2n , rate ges R, and probability of block error under successive cancellation decoding bounded as Pe(N,R) les O(N-1/4) independently of the code rate. This performance is achievable by encoders and decoders with complexity O(N logN) for each.     

Bounds on mutual information for simple codes using information combining

For coded transmission over a memoryless channel, two kinds of mutual information are considered: the mutual information between a code symbol and its noisy observation and the overall mutual information between encoder input and decoder output. The overall mutual information is interpreted as a combination of the mutual informations associated with the individual code symbols. Thus, exploiting code constraints in the decoding procedure is interpreted as combining mutual informations. For single parity check codes and repetition codes, we present bounds on the overall mutual information, which are based only on the mutual informations associated with the individual code symbols. Using these mutual information bounds, we compute bounds on extrinsic information transfer (exit) functions and bounds on information processing characteristics (ipc) for these codes.     

Decoding of Expander Codes at Rates Close to Capacity

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding error probability. Specifically, it is assumed that there exists a family of codes of length N and rate R=(1-epsiv)C (C is a capacity of a binary-symmetric channel), whose decoding probability decreases inverse polynomially in N. It is shown that if the decoding probability decreases sufficiently fast, but still only inverse polynomially fast in N, then there exists another such family of codes whose decoding error probability decreases exponentially fast in N. Moreover, if the decoding time complexity of the assumed family of codes is polynomial in N and 1/epsiv, then the decoding time complexity of the presented family is linear in N and polynomial in 1/epsiv. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes", IEEE Transactions on Information Theory, 2002, and "Concatenated Codes: Serial and Parallel", IEEE Transactions on Information Theory, 2005. It is shown that the latter families cannot be tuned to have exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/epsiv     

Almost security of cryptographic Boolean functions

The propagation criterion, PC(/spl lscr/) of order k, is one of the most general cryptographic criteria of secure Boolean functions f. In this paper, we formalize its /spl epsiv/-almost version. The new definition requires that f(X)+f(X+/spl Delta/) is almost uniformly distributed while in the original definition, it must be strictly uniformly distributed. Better parameters are then obtained than the strict PC(/spl lscr/) of order k functions. To construct /spl epsiv/-almost PC(/spl lscr/) of order k functions, we introduce a notion of domain distance.     

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

In this paper, we present error-correcting codes that achieve the information-theoretically best possible tradeoff between the rate and error-correction radius. Specifically, for every 0 < R < 1 and epsiv < 0, we present an explicit construction of error-correcting codes of rate that can be list decoded in polynomial time up to a fraction (1- R - epsiv) of worst-case errors. At least theoretically, this meets one of the central challenges in algorithmic coding theory. Our codes are simple to describe: they are folded Reed-Solomon codes, which are in fact exactly Reed-Solomon (RS) codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, and in fact our methods directly yield better decoding algorithms for RS codes when errors occur in phased bursts. The alphabet size of these folded RS codes is polynomial in the block length. We are able to reduce this to a constant (depending on epsiv) using existing ideas concerning ldquolist recoveryrdquo and expander-based codes. Concatenating the folded RS codes with suitable inner codes, we get binary codes that can be efficiently decoded up to twice the radius achieved by the standard GMD decoding.     

Convolutional codes I: Algebraic structure

A convolutional encoder is defined as any constant linear sequential circuit. The associated code is the set of all output sequences resulting from any set of input sequences beginning at any time. Encoders are called equivalent if they generate the same code. The invariant factor theorem is used to determine when a convolutional encoder has a feedback-free inverse, and the minimum delay of any inverse. All encoders are shown to be equivalent to minimal encoders, which are feedback-free encoders with feedback-free delay-free inverses, and which can be realized in the conventional manner with as few memory elements as any equivalent encoder, Minimal encoders are shown to be immune to catastrophic error propagation and, in fact, to lead in a certain sense to the shortest decoded error sequences possible per error event. In two appendices, we introduce dual codes and syndromes, and show that a minimal encoder for a dual code has exactly the complexity of the original encoder; we show that systematic encoders with feedback form a canonical class, and compare this class to the minimal class.     

Limits to List Decoding Reed&#8211;Solomon Codes

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes. 1) Given n distinct elements alpha₁,...,alpha_n from a field F, and n subsets S₁,...,S_n of F, each of size at most l, the list decoding algorithm of Guruswami and Sudan can in polynomial time output all polynomials p of degree at most k that satisfy p(alpha_i)isinS_i for every i, as long as ldelta for small enough delta, we exhibit an explicit received word with a superpolynomial number of Reed-Solomon codewords that agree with it on (2-epsi)k locations, for any desired epsi>0 (agreement of k is trivial to achieve). Such a bound was known earlier only for a nonexplicit center. Finding explicit bad list decoding configurations is of significant interest-for example, the best known rate versus distance tradeoff, due to Xing, is based on a bad list decoding configuration for algebraic-geometric codes, which is unfortunately not explicitly known     

Universal denoising for the finite-input general-output channel

We consider the problem of reconstructing a finite-alphabet signal corrupted by a known memoryless channel with a general output alphabet. The goodness of the reconstruction is measured by a given loss function. We (constructively) establish the existence of a universal (sequence of) denoiser(s) attaining asymptotically the optimum distribution-dependent performance for any stationary source that may be generating the noiseless signal. We show, in fact, that there is a whole family of denoiser sequences with this property. These schemes are shown to be universal also in a semistochastic setting, where the only randomness assumed is that associated with the channel noise. The scheme is practical, requiring O(n/sup 1+/spl epsiv//) operations (for any /spl epsiv/>0) and working storage size sublinear in the input data length. This extends recent work that presented a discrete universal denoiser for recovering a discrete source corrupted by a discrete memoryless channel (DMC).     

Fault-tolerant analysis of TMR design with noise-aware logic

Due to the effect of thermal noise, ground bounce and process variations in nanometer process, the behavior of any logical circuit becomes increasingly probabilistic. In this paper, based on the noise model [5] on the input and output nodes of a probabilistic CMOS (PCMOS) gate, the correctness probabilities of four PCMOS primitive gates, NOT, NAND, NOR and XOR, can be firstly computed. Based on the concept of the probabilistic transfer matrices (PTMs) and the corresponding operations on PTMs for the serial and parallel compositions of the components in a well-formed circuit, the correctness probability of the output in a 3-input PCMOS majority circuit in a triple modular redundancy (TMR) design can be further computed. For a given circuit with smaller error, it is well known that a TMR design has good fault-tolerant characterization and the correctness probability of the original output is converged to 1. Under the use of noise-aware logic in a TMR design, it is obvious that the fault-tolerant characterization of a TMR design is degraded and the correctness probability of the original output is not converged to 1. The experimental results show that the improvement region of the correctness probability of the original output will be narrowed due to the noise effect on the gates in a 3-input PCMOS majority circuit.     

An Efficient Algorithm for Computing the Reliability of Consecutive-$k$-Out-Of-$n$:F Systems

Many algorithms for computing the reliability of linear or circular consecutive-k-out-of-n:F systems appeared in this Transactions. The best complexity estimate obtained for solving this problem is O(k³ log(n/k)) operations in the case of i.i.d. components. Using fast algorithms for computing a selected term of a linear recurrence with constant coefficients, we provide an algorithm having arithmetic complexity O(k log (k) log(log(k)) log(n)+k^omega) where 2相似文献   

Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the q-ary Random Deletion Channel for Large q

We demonstrate polynomial-time deletion codes based on the verification-based decoding paradigm that come arbitrarily close to capacity. The random deletion channel takes n symbols from a q-ary alphabet, and each symbol is deleted independently with probability p. Taking advantage of recent improvements on the results of Luby and Mitzenmacher for verification-based decoding by Shokrollahi and Wang, we show how to design for any epsi>0 and sufficiently large n and q deletion codes with the following properties: the rate is (1-p)(1-epsi), the failure probability is n^O(1/epsi2)/q, and the computational complexity for encoding and decoding is n^O(1/epsi2)log q. We also extend these schemes to obtain the same results even if the undeleted symbols are also transposed arbitrarily, and if a sufficiently small number of random symbols are inserted     

Asymptotic properties on codeword lengths of an optimal FV code for general sources

This correspondence is concerned with asymptotic properties on the codeword length of a fixed-to-variable length code (FV code) for a general source {X/sup n/}/sub n=1//sup /spl infin// with a finite or countably infinite alphabet. Suppose that for each n /spl ges/ 1 X/sup n/ is encoded to a binary codeword /spl phi//sub n/(X/sup n/) of length l(/spl phi//sub n/(X/sup n/)). Letting /spl epsiv//sub n/ denote the decoding error probability, we consider the following two criteria on FV codes: i) /spl epsiv//sub n/ = 0 for all n /spl ges/ 1 and ii) lim sup/sub n/spl rarr//spl infin///spl epsiv//sub n/ /spl les/ /spl epsiv/ for an arbitrarily given /spl epsiv/ /spl isin/ [0,1). Under criterion i), we show that, if X/sup n/ is encoded by an arbitrary prefix-free FV code asymptotically achieving the entropy, 1/nl(/spl phi//sub n/(X/sup n/)) - 1/nlog/sub 2/ 1/PX/sup n/(X/sup n/) /spl rarr/ 0 in probability as n /spl rarr/ /spl infin/ under a certain condition, where P/sub X//sup n/ denotes the probability distribution of X/sup n/. Under criterion ii), we first determine the minimum rate achieved by FV codes. Next, we show that 1/nl(/spl phi//sub n/(X/sup n/)) of an arbitrary FV code achieving the minimum rate in a certain sense has a property similar to the lossless case.     

Application layer forward error correction for multicast streaming over LTE networks

The next step beyond third generation mobile networks is the Third Generation Partnership Project standard, named Long Term Evolution. A key feature of Long Term Evolution is the enhancement of multimedia broadcast and multicast services (MBMS), where the same content is transmitted to multiple users located in a specific service area. To support efficient download and streaming delivery, the Third Generation Partnership Project included an application layer forward error correction (AL‐FEC) technique based on the systematic fountain Raptor code, in the MBMS standard. To achieve protection against packet losses, Raptor codes introduce redundant packets to the transmission, that is, the forward error correction overhead. In this work, we investigate the application of AL‐FEC over MBMS streaming services. We consider the benefits of AL‐FEC for a continuous multimedia stream transmission to multiple users and we examine how the amount of forward error correction redundancy can be adjusted under different packet loss conditions. For this purpose, we present a variety of realistic simulation scenarios for the application of AL‐FEC and furthermore we provide an in‐depth analysis of Raptor codes performance introducing valuable suggestions to achieve efficient use of Raptor codes. Copyright © 2012 John Wiley & Sons, Ltd.