New multilevel codes over GF(q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GFⁿ¹(q) (n1⩽q ), and it is shown how to construct both multilevel block codes and multilevel trellis codes over GF(q). Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d_min⩾d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes     

Relationships between m-sequences over GF(q) andGF(qm)

It is shown that m-sequences over GF(q^m ) of length q^nm-1 corresponding to primitive polynomials in GF[q^m,x] of degree n can be generated from known m-sequences over GF(q) of length q^nm-1 obtained from primitive polynomials in GF[q,x] of degree mn. A procedure for generating the m-sequences over GF(q²) from m-sequences over GF(q) was given which enables the generation of m-sequences over GF( p²ⁿ). In addition it was shown that all of the primitive polynomials in GF[q,^m,x] can be obtained from a complete set of the primitive polynomials in GF[q ,x]     

On the linear complexity of functions of periodic GF(q)sequences

It is proved that the product of arbitrary periodic GF(q) sequences attains maximum linear complexity if their periods are pairwise coprime. The necessary and sufficient conditions are derived for maximum linear complexity of the product of two periodic GF(q ) sequences with irreducible minimal characteristic polynomials. For a linear combination of products of arbitrary periodic GF(q) sequences, it is shown that maximum linear complexity is achieved if their periods are pairwise coprime and the polynomial x -1 does not divide any of their minimal characteristic polynomials; assuming only that their periods are pairwise coprime, the author establishes a lower bound on the linear complexity which is of the same order of magnitude as maximum linear complexity. Boolean functions are derived that are optimal with respect to the maximum linear complexity. Possible applications of the results in the design of sequence generators are discussed     

Block-coded M-PSK modulation over GF(M)

Channel codes where the redundancy is obtained not from parity symbols, but from expanding the channel signal-set, are addressed. They were initially proposed by G. Ungerboeck (1982) using a convolutional code. Here, a block coding approach is given. Rate m/(m+1) coded 2^m+1-ary phase-shift keying (PSK) is considered. The expanded signal-set is given the structure of a finite field. The code is defined by a square nonsingular circulant generator matrix over the field. Binary data are mapped on a dataword, of the same length as the codewords, over an additive subgroup of the field. The codes using trellises are described, and then the Viterbi algorithm for decoding is applied. The asymptotic coding gain ranges from 1.8 to 6.0 dB for QPSK going from blocklength 3 to 12. For 8-PSK, the gain is from 0.7 to 3.0 dB with blocklength 4 to 8. With only four states in the trellis, codes of any length for QPSK and 8-PSK are constructed, each having an asymptotic coding gain of 3.0 dB. Simulation results are presented. It is found that the bit-error rate performance at moderate signal-to-noise ratios is sensitive to the number of nearest and next-nearest neighbors     

Two chi-square statistics for determining the orders p andq of an ARMA (p, q) process

The &thetas;, λ, and η functions have been previously proposed for use in choosing the autoregressive and moving-average orders of an ARMA (q, p) process visually. Two chi-square statistics associated with these three functions are presented and used here to determine the orders of an ARMA process statistically. It is shown that the two statistics are asymptotically equivalent to the Quenouille-Walker's goodness-of-fit test statistic, which is a Lagrange multiplier test statistic. Some numerical examples are presented to illustrate the usefulness of the two chi-square statistics as well as the three functions in ARMA modeling     

On the existence of optimum cyclic burst- correcting codes

It is shown that for each integerb geq 1infinitely many optimum cyclicb-burst-correcting codes exist, i.e., codes whose lengthn, redundancyr, and burst-correcting capabilityb, satisfyn = 2^{r-b+1} - 1. Some optimum codes forb = 3, 4, and5are also studied in detail.     

On normal and subnormal q-ary codes

The authors extend to the q-ary case the notions of a normal code, a subnormal code, and the amalgamated direct sum construction, in order to investigate problems related to the covering radius of codes. For example, the authors prove that every nonbinary nontrivial perfect code is absubnormal. They also include some linear-programming lower bounds on ternary codes with covering radius 2 or 3     

On (k, t)-subnormal covering codes

The concept of a (k, t)-subnormal covering code is defined. It is discussed how an amalgamated-direct-sumlike construction can be used to combine such codes. The existence of optimal (q, n, M) 1 codes C is discussed such that by puncturing the first coordinate of C one obtains a code with (q, 1)-subnorm 2     

Lower bounds for q-ary covering codes

The authors prove combinatorial lower bounds for K_q (n,R), the minimal cardinality of any q-ary code of length n and covering radius R. Tables of lower bounds for K_q(n,R) are presented for q=3, 4, 5     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

Identities and approximations for the weight distribution of q-ary codes

An explicit formula is derived that enumerates the complete weight distribution of an (n, k, d) linear code using a partially known weight distribution. An approximation formula for the weight distribution of q-ary linear (n, k , d) codes is also derived. It is shown that, for a given q-ary linear (n, k, d) code, the ratio of the number of codewords of weight u to the number of words of weight u approaches the constant Q=q ^-(n-k) as u becomes large. The error term is a decreasing function of the minimum weight of the dual. The results are also valid for nonlinear (n, M, d) codes with the minimum weight of the dual replaced by the dual distance     

Binary cyclic [n,k] codes used for simultaneoustEC and SBD

In a hybrid forward-error-correction-automatic-repeat-request system one may wish to use an [n,k] cyclic code because its decoding algorithm is well known. An analytic formula is given for determining the fraction of undetectable single bursts of different lengths when a cyclic code is used for simultaneous single-burst-error detection and t-random error correction     

The Nehari shuffle: FIR(q) filter design with guaranteederror bounds

An approach to the problem of designing a finite impulse response filter of specified length q which approximates in uniform frequency (L_∞) norm a given desired (possibly infinite impulse response) causal, stable filter transfer function is presented. An algorithm-independent lower bound on the achievable approximation error is derived, and an approximation method that involves the solution of a fixed number of all-pass (Nehari) extension problems (and is therefore called the Nehari shuffle) is presented. Upper and lower bounds on the approximation error are derived for the algorithm. Examples indicate that the method closely approaches the derived global lower bound. The method is compared with the Preuss (complex Remez exchange) algorithm in some examples     

Gain measurements on the KrF(B→X), XeF(B→X), and XeF(C→A) lasertransitions in an XeF(C→A) laser gas mixture

Optimum energy extraction from an electron-beam-pumped XeF(C →A) laser is achieved with a five-component rare gas halide mixture. The characterization and modeling of laser action in such a gas mixture requires a knowledge of small-signal gain and absorption coefficients not only on the blue-green XeF(C→ A) transition, but also in the ultraviolet (UV) region for the competing XeF(B→X) and KrF(B→X ) transitions. The authors report gain measurements on the XeF(C→A) transition and small-signal gain and absorption coefficients at or near both the XeF(B→X ) (351 and 353 nm) and KrF(B→X) (248 nm) transitions. A study of the gain for the UV and visible transitions as a function of Kr and Xe partial pressure is reported, and its impact on the XeF(C→A) kinetics is discussed     

Quantum codes from cyclic codes over GF(4m)

We provide a construction for quantum codes (Hermitian-self-orthogonal codes over GF(4)) starting from cyclic codes over GF(4^m). We also provide examples of these codes some of which meet the known bounds for quantum codes     

I/Q channel reversal correcting properties of anSQPSK Costas loop with integrated symbol synchronization

An integrated-carrier loop/symbol synchronizer, using a digital Costas loop with matched arm filters to demodulate staggered quaternary phase-shift keyed (QPSK) signals, is analyzed. An expression is derived for the S curve, parameterized by bit synchronization error. This result suggests that the demodulator structure offers an inherent I/Q channel reversal correcting capability. Computer simulation results are presented that support this conclusion, and suggest that ambiguity resolution performance depends on the ratio of carrier and synchronization loop bandwidths     

On the decoding of algebraic-geometric codes over Fq forq⩾16

It is proved that for algebraic-geometric codes on a curve over F _q for q⩾37 or on a curve of sufficiently large genus over F_q for q⩾16 there exists a polynomial decoding algorithm up to (d*-1)/2 errors, d* being the designed minimum distance     

Robustness of mean E{X} and R charts

The effect of nonnormality on E{X} and R charts is reported. The effect of departure from normality can be examined by comparing the probabilities that E{X} and R lie outside their three-standard-deviation and two-standard-deviation control limits. Tukey's λ-family of symmetric distributions is used because it contains a wide spectrum of distributions with a variety of tail areas. The constants required to construct E{X} and R charts for the λ-family are computed. Control charts based on the assumption of normality give inaccurate results when the tails of the underlying distribution are thin or thick. The validity of the normality assumption is examined by using a numerical example     

The (d,k) subcode of a linear block code

A simple technique employing linear block codes to construct (d,k) error-correcting block codes is considered. This scheme allows asymptotically reliable transmission at rate R over a BSC channel with capacity C_BSC provided R ⩽C_d,k-(1+C_BSC), where C_d,k is the maximum entropy of a (d,k ) source. For the same error-correcting capability, the loss in code rate incurred by a multiple-error correcting (d,k) code resulting from this scheme is no greater than that incurred by the parent linear block code. The single-error correcting code is asymptotically optimal. A modification allows the correction of single bit-shaft errors as well. Decoding can be accomplished using off-the-shelf decoders. A systematic (but suboptimal) encoding scheme and detailed case studies are provided