Lower Bounds for Binary Codes of Covering Radius One

Let K(n, l) denote the minimal cardinality of a binary code of length n and covering radius one. Blass and Litsyn proved a lower bound K(n, l) for in the case n equiv 5 (mod6). We give a simplification of the proof, which yields a slightly better result.     

Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes

The performance of maximum-likelihood (ML) decoded binary linear block codes is addressed via the derivation of tightened upper bounds on their decoding error probability. The upper bounds on the block and bit error probabilities are valid for any memoryless, binary-input and output-symmetric communication channel, and their effectiveness is exemplified for various ensembles of turbo-like codes over the additive white Gaussian noise (AWGN) channel. An expurgation of the distance spectrum of binary linear block codes further tightens the resulting upper bounds     

Using Reed–Muller RM (1, m) Codes Over Channels With Synchronization and Substitution Errors

We analyze the performance of a Reed-Muller RM(1,m) code over a channel that, in addition to substitution errors, permits either the repetition of a single bit or the deletion of a single bit; the latter feature is used to model synchronization errors. We first analyze the run-length structure of this code. We enumerate all pairs of codewords that can result in the same sequence after the deletion of a single bit, and propose a simple way to prune the code by dropping one information bit such that the resulting linear subcode has good post-deletion and post-repetition minimum distance. A bounded distance decoding algorithm is provided for the use of this pruned code over the channel. This algorithm has the same order of complexity as the usual fast Hadamard transform based decoder for the RM(1,m) code     

Asymptotic Upper Bounds on the Minimum Distance of Trellis Codes

A trellis code is a "sliding window" method of encoding a binary data stream as a sequence of signal points in Rⁿ. When a trellis code is used to encode data at the rate ofkbits/channel symbol, each channel input depends not only on the most recent block ofkbits to enter the encoder, but will also depend on a set of ν bits preceding this block. The ν bits determine the state of the encoder and the most recent block ofkbits generates the channel symbol conditional on the encoder state. The performance of a trellis code depends on a suitably defined minimum distance property of that code. This paper obtains upper bounds on this minimum distance that are better than any previously known.     

Bounds on the Asymptotic Coding Gain of Long Binary Block Codes

For some time it has been known that, for fixed code lengthn, binary BCH codes appear to be most efficient when the number of information bitskis between1/4 nand3/4 n[1, p. 443], [2, p. 219]. In this correspondence the efficiency of block codes on an binary-quantized additive white Gaussian noise channel is analyzed as a function of the code rater = k/nfor hard decision decoding. A closed form analytical expression for the upper and lower bounds on block code performance is derived for large code lengthsn. They show that, for best codes, a relatively broad maximum occurs for rates of approximately 0.4. The performance of the BCH codes is also compared with the bounds.     

Bounds for Binary Codes With Narrow Distance Distributions

New lower bounds are presented on the second moment of the distance distribution of binary codes, in terms of the first moment of the distribution. These bounds are used to obtain upper bounds on the size of codes whose maximum distance is close to their minimum distance. It is then demonstrated how such bounds can be applied to bound from below the smallest attainable ratio between the maximum distance and the minimum distance of codes. Finally, counterparts of the bounds are derived for the special case of constant-weight codes.     

关于BCH码的广义Hamming重量上,下限

一个线性码的第ｒ广义Ｈａｍｍｉｎｇ重量是它任意ｒ维子码的最小支集大小。本文给出了一般（本原、狭义）ＢＣＨ码的广义Ｈａｍｍｉｎｇ重量下限和一类ＢＣＨ码的广义Ｈａｍｍｉｎｇ重量上限     

Improved Performance Upper Bounds for Terminated Convolutional Codes

In this letter, we propose tight performance upper bounds for convolutional codes terminated with an input sequence of finite length. To obtain the upper bounds, a weight enumerator is defined to represent the relation between the Hamming distance of the coded output and the Hamming distance of the input bits of the code. The upper bounds on frame error rate (FER) and average bit error rate (BER) are obtained from the weight enumerator. A simple method is presented to compute the weight enumerator of a terminated convolutional code based on a modified trellis diagram.     

关于等重码不可检错误概率的界

本文研究了二元等重码不可检错误概率(UEP)的界.首先,我们通过研究二元等重码的对偶距离分布及其性质,给出二元等重码UEP的一个新的下界,该下界改进了Fu-Kl  ve-Wei的最新结果;然后,我们指出2003年Fu-Kl  ve-Wei关于二元等重码UEP上界的某些结果有错误,我们随后给出更正后的结果,即二元等重码UEP的平均值和一个上界.     

High-Speed Interpolation Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Algebraic soft-decision decoding of Reed-Solomon (RS) codes delivers promising coding gains over conventional hard-decision decoding. The most computationally demanding step in soft-decision decoding of RS codes is bivariate polynomial interpolation. In this paper, we present a hybrid data format-based interpolation architecture that is well suited for high-speed implementation of the soft-decision decoders. It will be shown that this architecture is highly scalable and can be extensively pipelined. It also enables maximum overlap in time for computations at adjacent iterations. It is estimated that the proposed architecture can achieve significantly higher throughput than conventional designs with equivalent or lower hardware complexity     

Some Remarks on BCH Bounds and Minimum Weights of Binary Primitive BCH Codes

It is shown that ifm neq 8, 12andm > 6, there are some binary primitive BCH codes (BCH codes in a narrow sense) of length2^{m} - 1whose minimum weight is greater than the BCH bound. This gives a negative answer to the question posed by Peterson [1] of whether or not the BCH bound is always the actual minimum weight of a binary primitive BCH code. It is also shown that for any evenm geq 6, there are some binary cyclic codes of length2^{m} - 1that have more information digits than the primitive BCH codes of length2^{m} - 1with the same minimum weight.     

线性不等保护能力码的码长上界及应用

本文详细研究了线性不等保护能力码的码长上界,得到了一些优于文献[1]的结果,本文还讨论了新上界在线性不等保护能力码构造上的应用。     

Improving Embedding Efficiency of Covering Codes for Applications in Steganography

In image steganography, each pixel can carry a ternary message by choosing adding/subtracting one to/from the gray value. Although ternary covering functions can provide embedding efficiency higher than binary ones, it is necessary to convert the binary message into a ternary format. We propose a novel method that improves the embedding efficiency of binary covering functions by fully exploiting the information contained in the choice of addition or subtraction in the embedding. The improved scheme can perform equally well with, or even outperform, ternary covering functions without ternary conversion of the message.     

非线性等距码和等距等重码的上界

设Qq(n,d)代表码长为n、任意两个不同码字间的Hamming距离为d的q元等距码所能达到的最大可能码字数(不考虑码的重量);Eq(n,d,w)代表码长为n、任意两个不同码字间Ham-ming距离为d、每个码字重量为w的q元等距等重码所能达到的最大可能码字数量.设q,n,d,w∈N,获得当q＞2时,有①Eq(n,d,w)≤qn,②Qq(n,d)≤qn+1;当q=2时,则有③Eq(n,d,w)≤n,④Qq(n,d)≤n+1.     

On the Stopping Redundancy of Reed–Muller Codes

The stopping redundancy of the code is an important parameter which arises from analyzing the performance of a linear code under iterative decoding on a binary erasure channel. In this paper, we will consider the stopping redundancy of Reed-Muller codes and related codes. Let R(lscr,m) be the Reed-Muller code of length 2^m and order lscr. Schwartz and Vardy gave a recursive construction of parity-check matrices for the Reed-Muller codes, and asked whether the number of rows in those parity-check matrices is the stopping redundancy of the codes. We prove that the stopping redundancy of R(m-2,m), which is also the extended Hamming code of length 2^m, is 2m-1 and thus show that the recursive bound is tight in this case. We prove that the stopping redundancy of the simplex code equals its redundancy. Several constructions of codes for which the stopping redundancy equals the redundancy are discussed. We prove an upper bound on the stopping redundancy of R(1,m). This bound is better than the known recursive bound and thus gives a negative answer to the question of Schwartz and Vardy     

Upper Bounds on the Rate of LDPC Codes for a Class of Finite-State Markov Channels

In this correspondence, we consider the class of finite-state Markov channels (FSMCs) in which the channel behaves as a binary symmetric channel (BSC) in each state. Upper bounds on the rate of LDPC codes for reliable communication over this class of FSMCs are found. A simple upper bound for all noninverting FSMCs is first derived. Subsequently, tighter bounds are derived for the special case of Gilbert-Elliott (GE) channels. Tighter bounds are also derived over the class of FSMCs considered. The latter bounds hold almost-surely for any sequence of randomly constructed LDPC codes of given degree distributions. Since the bounds are derived for optimal maximum-likelihood decoding, they also hold for belief propagation decoding. Using the derivations of the bounds on the rate, some lower bounds on the density of parity check matrices for given performance over FSMCs are derived     

A Simplified Step-by-Step Decoding Algorithm for Parallel Decoding of Reed–Solomon Codes

A simplified parallel step-by-step decoding algorithm is proposed for decoding Reed-Solomon (RS) codes. It uses new method to calculate the determinants of the temporarily changed syndrome matrices, based on the property of these matrices determined in this paper. By using the proposed method, the calculations of the determinants of the temporarily changed syndrome matrices become much simpler and thus the computational complexity of the step-by-step decoding algorithm is significantly reduced.     

Amended Truncated Union Bounds on the ML Decoding Performance of Binary Linear Codes over AWGN Channels

In this paper＇s simple upper bounds are derived on the frame and bit error probabilities of binary linear codes over Additive white Gaussian noise （AWGN） channels. The conventional union bound is first truncated and then amended, which can be justified by invoking Gallager＇s first bounding technique （GFBT）. Different from most other works, the ＂good region＂ is specified by a suboptimal list decoding algorithm. The error probability caused by the good region can be upper-bounded by the union bounds using pair-wlse error probability and tripletwise error probability, which can be further tightened by exploiting the independence between the error events and certain components of the receiving signal vector. The proposed bounds are simple since they involve only the Q-function. The proposed bounds improve our recently proposed bounds. Numerical results are also presented to compare the proposed bounds with the Divsalar bound, which is a simple tight upper bound with closed-form, and the Tangential-sphere bound （TSB）, which is considered as one of the tightest upper bounds.     

Finite-Dimensional Bounds on Zm and Binary LDPC Codes With Belief Propagation Decoders

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zopf_m and binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For Zopf _m LDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for Zopf_m LDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with nonequiprobably distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional noniterative bound, the latter of which is the best known bound that is tight for binary-symmetric channels (BSCs), and is a strict improvement over the existing bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for nonsymmetric channels, which coincides with the existing bound for symmetric channels     

Krawtchouk多项式与纯的加性量子纠错码的上界

该文利用Krawtchouk多项式函数给出了纯的加性量子纠错码的两个不同的上界,并进一步证明了量子Singleton界和渐近量子Hamming界只是这两个上界的特例。