Relative two-weight codes have been studied due to their applications to wiretap channel and secret sharing. It has been shown that these codes form a large family, which includes dual Hamming codes and subcodes of pu...
详细信息
Relative two-weight codes have been studied due to their applications to wiretap channel and secret sharing. It has been shown that these codes form a large family, which includes dual Hamming codes and subcodes of punctured Reed-Muller codes as special instances. This work studies the properties of relative two-weight codes with regard to efficient decoding. More specifically, the trellis complexity, which determines the complexity of Viterbi algorithm based decoding and pseudoredundancy that measures the performance and complexity of linear programming decoding are studied for relative two-weight codes. Separating properties of these codes have been identified and proved first. Based on the results of separating properties, the trellis complexity of binary relative two-weight codes is fully determined. An upper bound on the pseudoredundancy of binary relative two-weight codes is derived.
The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths....
详细信息
The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a deterministic method of predicting error floors, based on high signal-to-noise ratio (SNR) asymptotics, applied to absorbing sets within structured LDPC codes. The approach is illustrated using a class of array-based LDPC codes, taken as exemplars of high-performance structured LDPC codes. The results are in very good agreement with a stochastic method based on importance sampling which, in turn, matches the hardware-based experimental results. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. Our deterministic estimates are guaranteed to be a lower bound to the error probability in the high SNR regime, and extend the prediction of the error probability to as low as 10(-30). By adopting a channel-independent viewpoint, the usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with mixture noise.
In this paper, we consider the pairwise error probability (PEP) of a linear programming (LP) decoder for a general binary linear code as formulated by Feldman et al. (IEEE Traits. Inf. Theory, Mar. 2005) on an indepen...
详细信息
In this paper, we consider the pairwise error probability (PEP) of a linear programming (LP) decoder for a general binary linear code as formulated by Feldman et al. (IEEE Traits. Inf. Theory, Mar. 2005) on an independent (or memoryless) Rayleigh flat-fading channel with coherent detection and perfect channel state information (CSI) at the receiver. Let H be a parity- check matrix of a binary linear code and consider LP decoding based on H. The output of the LP decoder is always a pseuocodeword. We will show that the PEP of decoding to a pseudocodeword omega when the all-zero codeword is transmitted on the above-mentioned channel, behaves asymptotically as K(w) . (E-s/N-0) -(vertical bar chi(omega)vertical bar), where chi(omega) is the support set of omega, i.e., the set of nonzero coordinates, E-s/N-0 is the average signal-to-noise ratio (SNR), and K (omega) is a constant independent of the SNR. Note that the support set chi(omega) of w is a stopping set. Thus, the asymptotic decay rate of the error probability with the average SNR is determined by the size of the smallest nonempty stopping set in the Tanner graph of H. As an example, we analyze the well-known (155, 64) Tanner code and present performance curves on the independent Rayleigh flat-fading channel.
In this letter, we study the minimum pseudo-codewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. We show that a lower bound of Chaichanavong and Siegel on the pseudo-weight of a p...
详细信息
In this letter, we study the minimum pseudo-codewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. We show that a lower bound of Chaichanavong and Siegel on the pseudo-weight of a pseudo-codeword is tight if and only if this pseudo-codeword is a real multiple of a codeword. Using this result we further show that for some LDPC codes, e.g., Euclidean plane and projective plane LDPC codes, there are no other minimum pseudo-codewords except the real multiples of minimum codewords.
We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, channel coding linear programming decoding (CC-LPD), which is a well-known relaxation of max...
详细信息
We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, channel coding linear programming decoding (CC-LPD), which is a well-known relaxation of maximum-likelihood channel decoding for binary linear codes, and, on the other hand, compressed sensing linear programming decoding (CS-LPD), also known as basis pursuit, which is a widely used linear programming relaxation for the problem of finding the sparsest solution of an underdetermined system of linear equations. More specifically, we establish a tight connection between CS-LPD based on a zero-one measurement matrix over the reals and CC-LPD of the binary linear channel code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows the translation of performance guarantees from one setup to the other. The main message of this paper is that parity-check matrices of "good" channel codes can be used as provably "good" measurement matrices under basis pursuit. In particular, we provide the first deterministic construction of compressed sensing measurement matrices with an order-optimal number of rows using high-girth low-density parity-check codes constructed by Gallager.
暂无评论