Optimum number of errors corrected before releasing a softwaresystem

Software release problems based on Jelinski-Moranda and decreasing-failure-rate models are considered. The following software release policy is considered: after a preassigned number, n, of errors are removed, the test is terminated and the software system is released to the operational phase. The average gain is used as a criterion; there exists a unique optimal value of n. Numerical examples indicate that the software release policy based on the number of errors detected can be a good alternative to the existing policy     

Upper bounds on codes correcting asymmetric errors (Corresp.)

A Survey is given of known upper bounds on codes correcting asymmetric errors. The bounds are improved by introducing new Ideas. By solving a linear programming problem an upper bound is given that is easy to compute for all codelengths and all minimum asymmetric distances.     

Explicit evaluation of Viterbi's union bounds on convolutional code performance for the binary symmetric channel (Corresp.)

An explicit method is given to evaluate Viterbi's union bounds on both the first event error probability and the bit error probability of binary convolutional codes on a binary symmetric channel. These bounds are evaluated for the rate1/2code with generators1 + D + D^{2}and1 + D^{2}. Comparison is made with the bounds and experimental results of van de Meeberg.     

Serial concatenation of a block code and a 2D convolutional code

Multidimensional Systems and Signal Processing - In this paper we study two different concatenation schemes of twodimensional (2D) convolutional codes. We consider Fornasini–Marchesini state...     

An upper bound on the minimum distance of a convolutional code

An upper bound on the minimum distance of a linear convolutional code is given which reduces to the Plotkin bound for the block code case. It is shown that most linear convolutional codes have a minimum distance strictly less than their average distance. A table of the bound for several rates is given for binary codes as well as a comparison with the known optimum values for codes of block length2.     

Coded QAM using a binary convolutional code

As an alternative to trellis coding, a binary convolutional code is considered for use with such nonbinary modulation schemes as quadrature amplitude modulation (QAM). A Gray code is used to map the encoder output to the M-ary QAM constellation. The focus is on the design of 16-ary coded QAM with a rate 3/4 punctured convolutional code of a constraint length 7. A quantized binary metric generation method is proposed and shown to be suboptimum as compared to the direct use of a M-ary unquantized metric. Impressive coding gains and bandwidth efficiency are shown in comparison with uncoded systems     

Algebraic lower bounds on the free distance of convolutional codes

A new module structure for convolutional codes is introduced and used to establish further links with quasi-cyclic and cyclic codes. The set of finite weight codewords of an (n,k) convolutional code over F_q is shown to be isomorphic to an F_q[x]-submodule of F_q ⁿ[x], where F_q ⁿ[x] is the ring of polynomials in indeterminate x over F_q ⁿ, an extension field of F_q. Such a module can then be associated with a quasi-cyclic code of index n and block length nL viewed as an F_q[x]-submodule of F_q ⁿ[x]/langx^L-1rang, for any positive integer L. Using this new module approach algebraic lower bounds on the free distance of a convolutional code are derived which can be read directly from the choice of polynomial generators. Links between convolutional codes and cyclic codes over the field extension F_q ⁿ are also developed and Bose-Chaudhuri-Hocquenghem (BCH)-type results are easily established in this setting. Techniques to find the optimal choice of the parameter L are outlined     

New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities

With the Delsarte-MacWilliams inequalities as a starting point, an upper bound is obtained on the rate of a binary code as a function of its minimum distance. This upper bound is asymptotically less than Levenshtein's bound, and so also Elias's.     

A note on the free distance of a convolutional code (Corresp.)

A counterexample to a conjecture on the number of constraint lengths required to achieve the free distance of a rate1/nsystematic convolutional code is presented.     

Upper bounds on the size of quantum codes

This paper is concerned with bounds for quantum error-correcting codes. Using the quantum MacWilliams (1972, 1977) identities, we generalize the linear programming approach from classical coding theory to the quantum case. Using this approach, we obtain Singleton-type, Hamming-type, and the first linear-programming-type bounds for quantum codes. Using the special structure of linear quantum codes, we derive an upper bound that is better than both Hamming and the first linear programming bounds on some subinterval of rates     

Upper bounds on the rate of LDPC codes

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's (1963) bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes.     

Upper bounds on capacity for a constrained Gaussian channel

A low-pass and a bandpass additive white Gaussian noise channel with a peak-power constraint imposed on otherwise arbitrary input signals are considered. Upper bounds on the capacity of such channels are derived. They are strictly less than the capacity of the channel when the peak-power constrain is removed and replaced by the average-power constraint, for which the Gaussian inputs are optimum. This provides the answer to an often-posed question: peak-power limiting in the case of bandlimited channels does reduce capacity, whereas in infinite bandwidth channels it does not, as is well known. For an ideal low-pass filter of bandwidth B, the upper bound is Blog 0.934P/(N₀B) for P/( N₀B)≫1, where P is the peak power of the input signal and N₀/2 is the double-sided power spectral density of the additive white Gaussian noise     

Upper bounds on empirically optimal quantizers

In designing a vector quantizer using a training sequence (TS), the training algorithm tries to find an empirically optimal quantizer that minimizes the selected distortion criteria using the sequence. In order to evaluate the performance of the trained quantizer, we can use the empirically minimized distortion that we obtain when designing the quantizer. Several upper bounds on the empirically minimized distortions are proposed with numerical results. The bound holds pointwise, i.e., for each distribution with finite second moment in a class. From the pointwise bounds, it is possible to derive the worst case bound, which is better than the current bounds for practical training ratio /spl beta/, the ratio of the TS size to the codebook size. It is shown that the empirically minimized distortion underestimates the true minimum distortion by more than a factor of (1-1/m), where m is the sequence size. Furthermore, through an asymptotic analysis in the codebook size, a multiplication factor [1-(1-e/sup -/spl beta//)//spl beta/]/spl ap/(1-1//spl beta/) for an asymptotic bound is shown. Several asymptotic bounds in terms of the vector dimension and the type of source are also introduced.     

Two-channel multithreshold decoding of the systematic convolutional code

A variant of the two-channel sequential multithreshold decoding of the non-recursive systematic convolutional code of rate R = 0.5 has been considered. The main operations of two-channel sequential multithreshold processing and correction of errors detected in the receiving channel were determined on the basis of the joint comparative analysis of two functionally-related syndrome sequences generated.     

WiMax系统中卷积Turbo码技术的研究

卷积Turbo码是很灵活的码字，帧长和码率的变化范围很大，这也是选它做为WiMax（world Intemperability for Microwave Access）标准中的信道编码方案之一的主要原因，它采用递归系统卷积码作为子码，相对于经典Turbo码，它具有编码效率高，相同复杂度译码器下纠错性能好以及译码时延小等优点。详细介绍了卷积Turbo码的编译码器结构，提出译码方案，并且给出仿真性能曲线。     

Upper bounds on trellis complexity of lattices

Unlike block codes, n-dimensional lattices can have minimal trellis diagrams with an arbitrarily large number of states, branches, and paths. In particular, we show by a counterexample that there is no f(n), a function of n, such that all rational lattices of dimension n have a trellis with less than f(n) states. Nevertheless, using a theorem due to Hermite, we prove that every integral lattice Λ of dimension n has a trellis T, such that the total number of paths in T is upper-bounded by P(T)⩽n!(2/√3)^n2(n-1/2)V(Λ) ^n-1 where V(n) is the volume of Λ. Furthermore, the number of states at time i in T is upper-bounded by |S_i|⩽(2/√3)^i2(n-1)V(Λ)²ⁱ² n/. Although these bounds are seldom tight, these are the first known general upper bounds on trellis complexity of lattices     

Some properties of binary convolutional code generators

This paper formalizes the discussion of some structural properties of the generators for binary convolutional codes. The use of these properties may be helpful in the selection of generators which produce codes with desired error-correcting properties for sequential decoding. The approach taken is to decompose a generator sequence into subsequences called "subgenerators." The set of all such possible subsequences starting with a1is shown to form an Abelian group with respect to a binary convolution. The recurrence relation which permits the construction of the inverse of an encoding subgenerator is given. One application of these results is a simple proof of the reproducing property of the truncated convolutional message set noted by Wozencraft and Reiffen. The notion of "adjoint" canonical generators, all of which have the same error-correcting properties but different message sets, is also introduced. The distinction between encoding and decoding constraint lengths is pointed out and an estimate made of the achievable difference between the two. An efficient search procedure to select the generator of rate1/2which possesses the best error-correcting properties is also discussed. Selected generators of rates1/2and1/3are tabulated up to(32, 16)and(21, 7), respectively.     

Upper bounds on sequential decoding performance parameters

This paper presents the best obtainable random coding and expurgated upper bounds on the probabilities of undetectable error, oft-order failure (advance to depthtinto an incorrect subset), and of likelihood rise in the incorrect subset, applicable to sequential decoding when the metric biasGis arbitrary. Upper bounds on the Pareto exponent are also presented. TheG-values optimizing each of the parameters of interest are determined, and are shown to lie in intervals that in general have nonzero widths. TheG-optimal expurgated bound on undetectable error is shown to agree with that for maximum likelihood decoding of convolutional codes, and that on failure agrees with the block code expurgated bound. Included are curves evaluating the bounds for interesting choices ofGand SNR for a binary-input quantized-output Gaussian additive noise channel.     

Upper bounds on the free distance for a class of convolutionalcoded CPFSK signals

In this letter, we construct new encoder-independent upper bounds on the free distance for the rate (n-1)/n convolutional encoders that are formed by using rate 1/2 encoders and combined with 2ⁿ-level constant-envelope full-response CPFSK signals of single-h, by generalizing the bounding technique employed for the existing bounds. The new bounds coincide with the existing bounds for h⩽0.25, but are generally better for h>0.25. We also present actual encoder combinations achieving the constructed new bounds with short constraint lengths     

A construction of a space-time code based on number theory

We construct a full data rate space-time (ST) block code over M=2 transmit antennas and T=2 symbol periods, and we prove that it achieves a transmit diversity of 2 over all constellations carved from Z[i]⁴ . Further, we optimize the coding gain of the proposed code and then compare it to the Alamouti code. It is shown that the new code outperforms the Alamouti (see IEEE J Select. Areas Commun., vol.16, p.1451-58, 1998) code at low and high signal-to-noise ratio (SNR) when the number of receive antennas N>1. The performance improvement is further enhanced when N or the size of the constellation increases. We relate the problem of ST diversity gain to algebraic number theory, and the coding gain optimization to the theory of simultaneous Diophantine approximation in the geometry of numbers. We find that the coding gain optimization is equivalent to finding irrational numbers "the furthest," from any simultaneous rational approximations