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     

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     

A note on D-ary Huffman codes

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p₁ of the most likely source letter is provided. For large values of p₁, the bound improves the one given by R.G. Gallager (1978). Additionally, some results known for the binary case (D=2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by J.D. Golic and M.M. Obradovic (1987) is derived     

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     

Phase noise effects on M-ary PSK trellis codes

The performance of M-ary phase-shift keying (PSK) coded systems in the presence of added white Gaussian noise (AWGN), with a noisy carrier reference in the receiver, is examined. The results are obtained by combining the Chernoff bound technique with the generating function approach. The bit error probability analysis is carried out for 8- and 16-PSK with code rates of 2/3 and 3/4, respectively. The numerical results obtained demonstrate the error performance degradation due to a Tikhonov phase noise process with parameter α     

Fully digital M-ary PSK and M-ary QAMdemodulators for land mobile satellite communications

A fully digital implementation of digital modems is the preferred option of system designers because high performance can be achieved at reasonable cost. The author explains the beneficial features inherent in fully digital demodulator implementations. Other features which are required for land mobile satellite communication systems are also discussed. Recently reported techniques for the synchronisation and detection of M-ary PSK and M-ary QAM modulation schemes are reviewed with emphasis placed on those which are well suited to digital implementation     

Lower bounds for binary covering codes

G.D. Chen et al. (ibid., vol.IT-32, p.680-94, 1986) presented two new lower bounds for K(n,R), where K(n,R) denotes the minimum cardinality of a binary code of length n and covering radius R. The author shows that a slight modification gives further improvements and some examples are given to confirm the argument. Codes that have a certain partitioning property are considered     

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 (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     

Constructions and bounds for systematic tEC/AUED codes

Several methods of constructing systematic t-error correcting/all unidirectional error-detecting codes are described. These codes can be constructed by adding a tail to a linear t-error correcting code, but other constructions presented are more of an ad hoc nature. These codes will often be found as suitably chosen subsets of nonsystematic tEC/AUED codes. Further bounds on the word length of systematic tEC/AUED codes are derived, and extensive tables are given     

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     

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     

On the existence of optimum cyclic burst correcting codes over GF(q)

A cyclic b-burst correcting code over GF(q) of redundancy r and length n=(q^r-b+1-1)/(q-1) is said to be optimum. It is proved that a necessary condition for the existence of such a code is the existence of a square-free polynomial in GF(q)[x] of degree b-1 which is not divisible by x such that its period and the degrees of its irreducible factors are relatively prime to q-1. Moreover, if such a polynomial exists, then there are an infinite number of optimum cyclic b-burst correcting codes over GF(q)     

M-ary orthogonal signaling in the presence of Doppler

The performance degradation of an M-ary orthogonal keying (MOK) system due to relative motion between its transmitter and receiver can be minimized by selecting good signaling sets. A formulation for evaluating good signaling sets, or code sets, is developed for Walsh function data modulations. A union bound performance measure which closely approximates the exact probability of a demodulation error, is devised to allow for convenient evaluation of Walsh function codesets. The best Walsh function codesets for codevectors up to length 10 and for M=2, 4, 8 and 16, found by exhaustive search, are presented, along with their performance. In addition, codesets based on error-correcting codes are presented, along with a performance bound expressed in terms of the code's minimum distance     

Spectral shaping and digital synthesis of an M-ary timeseries

The use of pulse shaping to control transmitted spectral density precisely is examined. A digital filter architecture is described that not only mitigates the traditional problems of lengthy development intervals and cost manufacturing methods, but offers the additional features of intrinsically coding high-speed binary (M=2) data into M-ary symbols while ensuring highly reproducible, baud-normalized, transmitter pulse shaping. A conceptual basis for the digital synthesis method is first described, including a functional circuit appropriate to the simplest filter realizations. Spectral effects internal to the filter are considered, and a simple method to obtain desired transmitted spectra is outlined. It is shown that even relatively short pulses used in high-level modulation systems lead to impractical memory storage demands; however, the simple expedient of segmenting the finite impulse function greatly reduced the individual memory requirements, though it necessitates intermediate adding operations. Experimental examples illustrate the design methodology for quaternary (M=4) data signals in a Nyquist communication channel and serve as points of reference for addressing performance and design flexibility     

Asymptotic performance of M-ary orthogonal modulation ingeneralized fading channels

The asymptotic (M→∞) probability of symbol error P_e,_m for M-ary orthogonal modulation in a Nakagami-m fading channel is given by the incomplete gamma function P(m, mx) where x=In 2/(E_b/N₀) and E_b is the average energy per bit. For large signal-to-noise ratio this leads to a channel where the probability of symbol error varies as the inverse mth power of E_b/N₀. These channels exist for all m⩾1/2. The special case of m=1 corresponds to Rayleigh fading, an inverse linear channel     

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     

Performance evaluation of M-ary QPRS schemes in severeimpulsive noise environments

The performance of multilevel quadrature partial-response systems (QPRS) in the presence of an additive combination of Gaussian and impulsive noise is analytically evaluated by means of the Fourier-Bessel series expansion method. The model of the impulsive noise used, which closely models atmospheric and/or man-made electromagnetic interference, consists of a stream of Poisson impulses with areas distributed according to a power Rayleigh probability density function. Analytical performance evaluation results are presented for 9, 49, and 225 QPR systems. The results indicate severe system performance degradation, especially for highly bandwidth-efficient systems (e.g. 225 QPRS), mostly due to the long error bursts caused by the impulsive noise tails. However, a qualitative comparison between these results and the corresponding performance results of equivalent QAM schemes demonstrates that 49 QPRS could be a suitable choice for microwave radio or HDTV satellite links operating in pure impulsive noise environments     

A coding scheme for m-out-of-n codes

A scheme for the construction of m-out-of-n codes based on the arithmetic coding technique is described. For appropriate values of n, k, and m, the scheme can be used to construct an (n,k) block code in which all the codewords are of weight m. Such codes are useful, for example, in providing perfect error detection capability in asymmetric channels such as optical communication links and laser disks. The encoding and decoding algorithms of the scheme perform simple arithmetic operations recursively, thereby facilitating the construction of codes with relatively long block sizes. The scheme also allows the construction of optimal or nearly optimal m-out-of-n codes for a wide range of block sizes limited only by the arithmetic precision used