High-rate punctured convolutional codes for Viterbi and sequentialdecoding

An investigation is conducted of the high-rate punctured convolutional codes suitable for Viterbi and sequential decoding. Results on known short-memory codes M⩽8 discovered by others are extended. Weight spectra and upper bounds on the bit error probability of the best known punctured codes having memory 2⩽M ⩽8, and coding rates 2/3⩽R⩽7/8 are provided. Newly discovered rate-2/3 and -3/4 long-memory punctured convolutional codes with 9⩽M⩽23 are provided together with the leading terms of their weight spectra and their bit error performance bounds. Some results of simulation with sequential decoding are given     

A limit theorem for n-phase Barker sequences

It is proved that for 3⩽L⩽19, except for L =6, the total number of normalized n-phase Barker sequences of length L increases without limit as n goes to infinity     

Error detecting capabilities of the shortened Hamming codes adoptedfor error detection in IEEE Standard 802.3

Investigates the error detecting capabilities of the shortened hamming codes adopted for error detection in IEEE Standard 802.3. These codes are also used for error detection in the data link layer of the Ethernet, a local area network. The authors compute the weight distributions for various code lengths. From the results, they show the probability of undetectable error and that of detectable error for a binary symmetric channel with bit-error rate 10^-5⩽ϵ⩽ 1/2. They also find the minimum distance of the shortened code of length n for 33 ⩽n ⩽12144 and the double-burst detecting capabilities     

On the effect of gap width on the admittance of solid circularcylindrical dipoles

A center-fed, solid, circular cylindrical dipole of radius a with feed gap of width 2d radiating in a circular waveguide of radius b terminated in infinite ground planes is rigorously analyzed by applying both the conservation-of-complex-power technique and the multiple-reflections technique. The analysis begins by studying the dependence of the dipole admittance on its feed gap width and on its length, 2l, as well as on b, with ka (k=2π/λ is the number) as a parameter. From the decreasing amplitudes of the almost periodic oscillations of these input admittances as b/λ is increased, the input admittances of dipoles radiating in free space (b→∞) are estimated using a variable-bound approach. The effect of gap width (d/a⩽5) for different lengths of dipoles (0.2⩽2l/λ⩽1) in free space and for different thicknesses (ka⩽0.2) is then established. The feed gap dependence for a half-wave dipole is also examined in detail for d /a⩽10 and ka⩽0.14     

New minimum distance bounds for certain binary linear codes

Let an [n, k, d]-code denote a binary linear code of length n, dimension k, and minimum distance at least d. Define d(n, k) as the maximum value of d for which there exists a binary linear [n, k, d]-code. T. Verhoeff (1989) has provided an updated table of bounds on d(n, k) for 1⩽k⩽n⩽127. The authors improve on some of the upper bounds given in that table by proving the nonexistence of codes with certain parameters     

Trellis-coded multidimensional phase modulation

A 2L-dimensional multiple phase-shift keyed (L×MPSK) signal set is obtained by forming the Cartesian product of L two-dimensional MPSK signal sets. A systematic approach to partitioning L×MPSK signal sets that is based on block coding is used. An encoder system approach is developed. It incorporates the design of a differential precoder, a systematic convolutional encoder, and a signal set mapper. Trellis-coded L×4PSK, L×8PSK, and L×16PSK modulation schemes are found for 1⩽L⩽4 and a variety of code rates and decoder complexities, many of which are fully transparent to discrete phase rotations of the signal set. The new codes achieve asymptotic coding gains up to 5.85 dB     

A new table of constant weight codes

A table of binary constant weight codes of length n⩽28 is presented. Explicit constructions are given for most of the 600 codes in the table; the majority of these codes are new. The known techniques for constructing constant weight codes are surveyed, and a table of (unrestricted) binary codes of length n⩽28 is given     

Maximum-rank array codes and their application to crisscross errorcorrection

A μ-[n×n,k] array code C over a field F is a k-dimensional linear space of n×n matrices over F such that every nonzero matrix in C has rank ⩾μ. It is first shown that the dimension of such array codes must satisfy the Singleton-like bound k⩽n(n-μ+1). A family of so-called maximum-rank μ-[n×n,k=n ( n-μ+1)] array codes is then constructed over every finite field F and for every n and μ, 1⩽μ⩽n . A decoding algorithm is presented for retrieving every Γ∈C, given a received array Γ+E, where rank (E)+1⩽(μ-1)/2. Maximum-rank array codes can be used for decoding crisscross errors in n×n bit arrays, where the erroneous bits are confined to a number t of rows or columns (or both). This construction proves to be optimal also for this model of errors. It is shown that the behavior of linear spaces of matrices is quite unique compared with the more general case of linear spaces of n×n. . .×n hyper-arrays     

Linear spans of modified de Bruijn sequences

Order n modified de Bruijn sequences are created by removing a single zero from the longest run of zeros in period 2ⁿ de Bruijn sequences. The M sequences are then the natural undisguised linear subset of modified de Bruijn sequences. Theorems are given on the linear spans of modified de Bruijn sequences and data are presented for 4⩽n⩽6     

On linear structure and phase rotation invariant properties ofblock M-PSK modulation codes

Two important structural properties of block M(=2^' )-ary PSK modulation codes, linear structure and phase symmetry, are investigated. An M-ary modulation code is first represented as a code with symbols from the integer group S_M-PSK=(0,1,2,---,M-1) under modulo-M addition. Then the linear structure of block M-PSK modulation codes over S_M-PSK with respect to modulo- M vector addition is defined, and conditions are derived under which a block M-PSK modulation code is linear. Once the linear structure is developed, the phase symmetry of block M-PSK modulation codes is studied. In particular, a necessary and sufficient condition for a block M-PSK modulation code that is linear as a binary code to be invariant under 2^h/180°M phase rotation, for 1⩽h⩽l is derived. Finally, a list of short 8-PSK and 16-PSK modulation codes is given, together with their linear structure and the smallest phase rotation for which a code is invariant     

Binary [18,11]2 codes do not exist-Nor do [64,53]2 codes

A binary, linear block code C with block length n and dimension n is commonly denoted by [n, k] or, if its minimum distance is d, by [n, k,d]. The code's covering radius r(C) can be defined as the smallest number r such that any binary column vector of length (n-k) can be written as a sum of r or fewer columns of a parity-check matrix of C. An [n,k] code with covering radius r is denoted by [n,k]r. R.A. Brualdi et al., (1989) showed that l(m,r) is defined to be the smallest n such that an [n,n-m]r code exists. l(m,2) is known for m⩽6, while it is shown by Brualdi et al. that 17⩽l(7,2)⩽19. This lower bound is improved by A.R. Calderbank et al. (1988), where it is shown that [17,10]2 codes do not exist. The nonexistence of [18,11]2 codes is proved, so that l(7,2)=19. l[7.2)=19 is established by showing that [18,11]2 codes do not exist. It is also shown that [64,53]2 codes do not exist, implying that l(11,2)⩾65     

On the three-coefficient window family

The definition of the three-coefficient window family is extended to the form: w(t,b)=0.5(1-b)+0.5 cos(2πt/T)+0.5b cos(4πt/T ), |t|⩽T/2, -0.25⩽b⩽0.25, and its spectral behavior is investigated. It is found that with the parameter b adjusted to different values, this window family can attain a minimum main lobe width of 1.38, a maximum sidelobe attenuation of 64.19 dB, and a highest cutoff rate of 30 dB/oct     

Short codes with a given covering radius

The covering radius r of a code is the maximum distance from any vector in the space containing the code to the nearest codeword. The authors introduce a new function l(m,r), called the length function, which equals the smallest length of a binary code of codimension m and covering radius r. They investigate basic properties of the length function. Projective geometries over larger fields are used to construct families of codes which improve significantly the upper bound for l(m,2) obtained by amalgamation of Hamming codes. General methods are developed for ruling out the existence of codes of covering radius 2 with a given codimension and length resulting in lower bounds for l(m,2). A table is presented which gives the best results now known for l(m,r) with m⩽12 and r⩽12     

Some results on the covering radii of Reed-Muller codes

Let R(r,m) be the rth-order Reed-Muller code of length 2^m and let ρ(r,m ) be its covering radius. R(2,7), R(2,8), R (3,7), and R(4,8) are among those smallest Reed-Muller codes whose covering radii are not known. New bounds for the covering radii of these four codes are obtained. The results are ρ(2,7)⩾40, ρ(2,8)⩾84, 20⩽ρ(3,7)⩽23, and ρ(4,8)⩾22. Noncomputer proofs for the known results that ρ(2,6)=18 and that R(1,5) is normal are given     

On the minimum distance of ternary cyclic codes

There are many ways to find lower bounds for the minimum distance of a cyclic code, based on investigation of the defining set. Some new theorems are derived. These and earlier techniques are applied to find lower bounds for the minimum distance of ternary cyclic codes. Furthermore, the exact minimum distance of ternary cyclic codes of length less than 40 is computed numerically. A table is given containing all ternary cyclic codes of length less than 40 and having a minimum distance exceeding the BCH bound. It seems that almost all lower bounds are equal to the minimum distance. Especially shifting, which is also done by computer, seems to be very powerful. For length 40⩽n⩽50, only lower bounds are computed. In many cases (derived theoretically), however, these lower bounds are equal to the minimum distance     

Double series representation of bounded signals

Series representations of the form f(t)~Σ_n=-∞^∞Σ _k=-∞^∞a_n,kν(t-n)_e ^2πkts/ for bounded signals f(t) are studied, as are conditions on the unit function ν(t), such that coefficients a_n,k reveal the energy content of f(t) in the time interval n-(1/2)⩽t⩽n+(1/2) and frequency interval 2π(k-(1/2))⩽ω⩽2π(k+(1/2)). These conditions turn out to be orthogonality and integrability. Based on these conditions a number of properties of the expansion are derived, including summability of the double series and energy and power estimations. Some examples of the expansion are presented     

Combined equalization and coding for high-density saturationrecording channels

Combined equalization and coding approaches which significantly outperform previous techniques are presented for the binary Lorentzian channel with additive Gaussian noise. The authors develop a technique based on the concatenation of standard trellis codes with an equalization code and a block decision feedback equalizer (BDFE). Signal sets for the trellis code are generated by partitioning BDFE output vectors according to four- and eight-dimensional lattices. They also investigate the combination of a decision feedback equalizer (DFE) and a convolutional code (CC) and find that this system provides theoretical coding gains from 1 to 3 dB in the high linear recording density range of 2⩽pw₅₀/T⩽3. Although the BDFE with the trellis code system does not perform as well as the DFE with CC system at high densities, it does produce substantial coding gains at low linear recording densities     

A new upper bound on the minimal distance of self-dual codes

It is shown that the minimal distance d of a binary self-dual code of length n⩾74 is at most 2[(n+6)/10]. This bound is a consequence of some new conditions on the weight enumerator of a self-dual code obtained by considering a particular translate of the code, called its shadow. These conditions also enable one to find the highest possible minimal distance of a self-dual code for all n⩾60; to show that self-dual codes with d⩽6 exist precisely for n⩾22, with d ⩾8 exist precisely for n=24, 32 and n⩾26, and with d⩾10 exist precisely for n⩾46; and to show that there are exactly eight self-dual codes of length 32 with d=8. Several of the self-dual codes of length 34 have trivial group (this appears to be the smallest length where this can happen)     

Image coding by adaptive tree-structured segmentation

A new algorithmic approach to segmentation-based image coding is proposed. A good compromise is achieved between segmentation by quadtree-based decomposition and by free region-growing in terms of time complexity and scene adaptability. Encoding is to recursively partition an image into convex n-gons, 3⩽n⩽8, until the pixels in the current n-gon satisfy a uniformity criterion. The recursive partition generates a valid segmentation by aligning the polygon boundaries with image edges. This segmentation is embedded into a binary tree for compact encoding of its geometry. The compressed image is sent as a labeled pointerless binary tree, and decoding is simply polygon filling. High compression ratios are obtained by balancing the accuracy and geometric complexity of the image segmentation, a key issue for segmentation-driven image coding that was not addressed before. Due to its tree structure, the method is also suitable for progressive image coding     

Low-frequency intensity noise in semiconductor lasers

The observed 1/f noise in the light-output power S _p of four different types of heterostructure lasers is explained in terms of spatially uncorrelated gain fluctuations and spontaneous emission fluctuations. Two possible noise sources are suggested: fluctuations in the absorption coefficient and fluctuations in the number of free carriers. Both models are in agreement with the experimental results obtained from index-guided and gain-guided diodes at wavelengths of 1.3 and 0.8 μm. The dependence S_p ∝P^m has been observed with P the average light-output power and m=3/2 under spontaneous emission, a small transition region with m=5/2, m=4 in the superradiation region, and 0⩽m⩽1 in the laser region