The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z₄, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and “Preparata” codes are Z₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the “Preparata” code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

Quasi-cyclic codes over Z4 and some new binarycodes

Previously, (linear) codes over Z₄ and quasi-cyclic (QC) codes (over fields) have been shown to yield useful results in coding theory. Combining these two ideas we study Z ₄-QC codes and obtain new binary codes using the usual Gray map. Among the new codes, the lift of the famous Golay code to Z₄ produces a new binary code, a (92, 2²⁴, 28)-code, which is the best among all binary codes (linear or nonlinear). Moreover, we characterize cyclic codes corresponding to free modules in terms of their generator polynomials     

Focused codes for channels with skewed errors

Consider a channel with inputs and outputs in the field F _q(q>2). It is said that the channel is skewed on a set B⊂F_q* if the additive noise generated by the channel is likely to lie in B, i.e. B is a set of common errors. The concern is the construction of focused codes that are appropriate for such channels. It is said that a code is (t₁,t₂)-focused on B if it can correct up to t₁+t₂ errors provided at most t₁ of those errors lie outside of B; the strategy is to offer different levels of protection against common and uncommon errors and so provide novel tradeoffs between performance and rate. Techniques for constructing focused codes and bounds on their rates are described     

Thermal shifts of the spectral lines in the 4F3/2 to 4I11/2 manifold of anNd:YAG Laser

A report is presented of the thermal shifts of eleven of the twelve lines from the ⁴F_3/2 Stark energy levels to the ⁴I_11/2 energy levels in an Nd:YAG laser for a temperature change from 20-200°C. The thermal shift difference between the Stark sublevels R₁, R₂ in ⁴F_3/2 is found to be about -0.6±0.6 cm^-1/100°C. Within experimental uncertainty, all of the lasing lines either moved to longer wavelength or remained unchanged with increasing temperature     

Measurement of the characteristics of the optical-microwavedouble-resonance effect of the 87Rb D1line for application as an atomic frequency standard

The OMDR (optical-microwave double resonance) spectrum of ⁸⁷ Rb with the aim of using a frequency-stabilized GaAs semiconductor laser instead of an Rb lamp as a pumping source in a gas-cell-type Rb frequency standard. Natural isotope ⁸⁷Rb was sealed in a glass cell with buffer gases (Ar/N₂=1.2, total pressure=39 torr). The double resonance signal in the 5P_1/2(F=2)←5S_1/2( F=1) transition appearing at the resonance to the F=2←1 hyperfine transition of the 5S_1/2 state was detected. The optimum operational cell temperature was 56°C. The peak-to-peak frequency width of the atomic hyperfine resonance discriminator used to stabilize the microwave frequency shifts induced by detuning of the laser frequency, changes in the laser and microwave powers, and temperature drift of the cell were investigated     

A 2-adic approach to the analysis of cyclic codes

This paper describes how 2-adic numbers can be used to analyze the structure of binary cyclic codes and of cyclic codes defined over Z _2(a), a⩾2, the ring of integers modulo 2^a. It provides a 2-adic proof of a theorem of McEliece that characterizes the possible Hamming weights that can appear in a binary cyclic code. A generalization of this theorem is derived that applies to cyclic codes over Z_2(a) that are obtained from binary cyclic codes by a sequence of Hensel lifts. This generalization characterizes the number of times a residue modulo 2^a appears as a component of an arbitrary codeword in the cyclic code. The limit of the sequence of Hensel lifts is a universal code defined over the 2-adic integers. This code was first introduced by Calderbank and Sloane (1995), and is the main subject of this paper. Binary cyclic codes and cyclic codes over Z_2(a) are obtained from these universal codes by reduction modulo some power of 2. A special case of particular interest is cyclic codes over Z₄ that are obtained from binary cyclic codes by means of a single Hensel lift. The binary images of such codes under the Gray isometry include the Kerdock, Preparata, and Delsart-Goethals codes. These are nonlinear binary codes that contain more codewords than any linear code presently known. Fundamental understanding of the composition of codewords in cyclic codes over Z₄ is central to the search for more families of optimal codes. This paper also constructs even unimodular lattices from the Hensel lift of extended binary cyclic codes that are self-dual with all Hamming weights divisible by 4. The Leech lattice arises in this way as do extremal lattices in dimensions 32 through 48     

Dependence of the frequency shift of the optical-microwave doubleresonance signal in the Cs D2 line on the pumpingfrequency and power of a GaAs semiconductor laser

The OMDR (optical-microwave double resonance) effect in the Cs D₂ line was studied for realizing a gas-cell-type Cs atomic frequency standard. A glass cell containing Cs with buffer gases (Ar/N₂=1.26, total pressure=39 torr) was placed in a TE₀₁₂ mode microwave cavity at a temperature of 45°C and was pumped using a GaAs semiconductor laser frequency locked to an external interferometer tuned to the 6P_3/2 (F=2,3,4)←6 S_1/2(F=3) transition. The OMDR signal appearing at the resonance to the F=4←3 hyperfine transition of the 6S_1/2 state shifted with detuning of the laser frequency and with change of the laser and microwave powers. The dependence of the shift on these variables around an optimum operating condition was obtained as, Δν_MW[Hz]=-(0.31±0.02) {1+(0.44±0.15) (ΔP_L/P_L)} Δν_L [MHz]-10(ΔV_MW/V _MW)     

Determination of the merit factor of Legendre sequences

M.J.E. Golay (ibid., vol.IT-23, no.1, p.43-51, 1977) has used the ergodicity postulate to calculate that the merit factor F of a Legendre sequence offset by a fraction f of its length has an asymptotic value given by 1/F=(2/3)-4|f|+8f ², |f|⩽1/2, which gives F=6 for |f |=1/4. Here this is proved without using the ergodicity postulate     

Bandwidth efficient coding for fading channels: code constructionand performance analysis

The authors apply a general method of bounding the event error probability of TCM (trellis-coded modulation) schemes to fading channels and use the effective length and the minimum-squared-product distance to replace the minimum-free-squared-Euclidean distance as code design parameters for Rayleigh and Rician fading channels with a substantial multipath component. They present 8-PSK (phase-shift-keying) trellis codes specifically constructed for fading channels that outperform equivalent codes designed for the AWGN (additive white Gaussian noise) channel when v⩾5. For quasiregular trellis codes there exists an efficient algorithm for evaluating event error probability, and numerical results which demonstrate the importance of the effective length as a code design parameter for fading channels with or without side information have been obtained. This is consistent with the case for binary signaling, where the Hamming distance remains the best code design parameter for fading channels. The authors show that the use of Reed-Solomon block codes with expanded signal sets becomes interesting only for large value of E_s/N₀, where they begin to outperform trellis codes     

A single-hop F2 propagation model forfrequencies above 30 MHz and path distances greater than 4000 km

Standard textbook explanations of ionosphere propagation suggest that 30 MHz and 4000 km are the limiting frequency and distance for single-hop communications. During the peak of sunspot cycle 22, however, there have been hundreds of reports of F₂ communications exceeding great-circle distance of 4200 km at 50 MHz. It is shown that parabolic F₂ ionospheric models explain this propagation irregularity, although textbooks and reference books fail to show that such long distances at VHF are possible     

The Einstein relation for degenerate semiconductors with nonuniformband structures

Modification of the Einstein equation for semiconductors with nonparabolic energy bands and doped nonuniformly with impurity atoms is suggested. The suggestion is based on a new approximation of the Fermi-Dirac integral of order 1/2, namely, F_1/2(η_n), where η_n is the reduced Fermi level for electrons. The relation reduces to that for semiconductors with parabolic energy bands and doped uniformly with impurity atoms under appropriate boundary conditions. A comparison of the calculated and exact results for F_1/2(η) is found to be very encouraging     

A new method for on wafer noise measurement

A method for measuring the noise parameters of MESFETs and HEMTs is presented. It is based on the fact that three independent noise parameters are sufficient to fully describe the device noise performance. It is shown that two noise parameters, R_n and |Y_OPT|, can be directly obtained from the frequency variation of the noise figure F₅₀ corresponding to a 50 Ω generator impedance. By using a theoretical relation between the intrinsic noise sources as additional data, the F₅₀ measurement only can provide the four noise parameters. A good agreement with more conventional techniques is obtained     

Repeated convolutional codes for high-error-rate channels

An error-correction scheme for an M-ary symmetric channel (MSC) characterized by a large error probability p_e is considered. The value of p_e can be near, but smaller than, 1-1/M, for which the channel capacity is zero, such as may occur in a jamming environment. The coding scheme consists of an outer convolutional code and an inner repetition code of length m that is used for each convolutional code symbol. At the receiving end, the m inner code symbols are used to form a soft-decision metric, which is passed to a soft-decision decoder for the convolutional code. The effect of finite quantization and methods to generate binary metrics for M>2 are investigated. Monte Carlo simulation results are presented. For the binary symmetric channel (BSC), it is shown that the overall code rate is larger than 0.6R₀, where R₀ is the cutoff rate of the channel. New union bounds on the bit error probability for systems with a binary convolutional code on 4-ary and 8-ary orthogonal channels are presented. For a BSC and a large m, a method is presented for BER approximation based on the central limit theorem     

On algebraic decoding of the Z4-linearCalderbank-McGuire code

The quaternary Calderbank-McGuire (see Des., Codes Cryptogr., vol.10, no.2, 1997) code is a Z₄-linear code of length 32 which has 2³⁷ codewords and a minimum Lee distance of 12. The Gray map of this code is known to be a nonlinear binary (64, 2³⁷,12) code. The Z₄-linear Calderbank-McGuire code can correct all errors with Lee weight ⩽5. An algebraic decoding algorithm for the code is presented in this paper. Furthermore, we discuss an alternative decoding method which takes advantage of the efficient BCH decoding algorithm     

Optical absorption and stimulated emission of neodymium in yttriumorthosilicate

A spectroscopic investigation of the biaxial crystal yttrium orthosilicate doped with Nd³⁺(Nd³⁺:Y₂SiO₅) has been performed. Spectrally and orientationally resolved emission cross sections necessary for the evaluation of laser performance on the Nd^{3+ 4}F_3/2-⁴I _9/2 and ⁴F_3/2-⁴I_11/2 transitions have been determined. The Judd-Ofelt theory has been applied to measured values of optical absorption line strengths to obtain the orientation averaged intensity parameters: Ω₂-3.34×10^-20 cm², Ω ₄=4.35×10^-20 cm², and Ω₆=5.60×10^-20 cm². These Judd-Ofelt intensity parameter values are significantly different from those previously reported by A.M. Tkachuk et al. Using these intensity parameters, the Nd^{3+ 4}F₂ metastable state lifetime is predicted to be 225 μs. Measured low Nd concentration ⁴F_3/2 lifetimes of 214 μs indicate a high radiative quantum efficiency. Because of the Stark level splitting of the Nd^{3+ 4}F_3/2 and ⁴I_9/2 manifolds, laser operation at twice one of the Cs atomic resonance filter acceptance wavelengths is possible     

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     

The Zak transform and some counterexamples in time-frequencyanalysis

It is shown how the Zak transform can be used to find nontrivial examples of functions f, g∈L²(R) with f×g≡0≡F×G, where F, G are the Fourier transforms of f, g, respectively. This is then used to exhibit a nontrivial pair of functions h, k∈L²(R), h≠k, such that |h|=|k|, |H |=|K|. A similar construction is used to find an abundance of nontrivial pairs of functions h, k∈L² (R), h≠k, with |A_h |=|A_k| or with |W_h|=|W _k| where A_h, A_k and W_h, W_k are the ambiguity functions and Wigner distributions of h, k, respectively. One of the examples of a pair of h, k∈L²(R), h≠k , with |A_h|=|A_k| is F.A. Grunbaum's (1981) example. In addition, nontrivial examples of functions g and signals f₁≠f₂ such that f₁ and f₂ have the same spectrogram when using g as window have been found     

A strengthening of the Assmus-Mattson theorem

Let w₁=d,w₂,…,w _s be the weights of the nonzero codewords in a binary linear [n,k,d] code C, and let w' ₁, w'₂, …, w'₃, be the nonzero weights in the dual code C1. Let t be an integer in the range 0<t<d such that there are at most d-t weights w'_i with 0<w'_i ⩽n-t E. F. Assmus and H. F. Mattson, Jr. (1969) proved that the words of any weight w_i in C form a t-design. The authors show that if w₂⩾d+4 then either the words of any nonzero weight w_i form a (t+1)-design or else the codewords of minimal weight d form a {1,2,…,t,t+2}-design. If in addition C is self-dual with all weights divisible by 4 then the codewords of any given weight w_i form either a (t +1)-design or a {1,2,…,t,t+2}-design. The proof avoids the use of modular forms     

Two 16-state, rate R=2/4 trellis codes whose free distances meetthe Heller bound

For rate R=1/2 convolutional codes with 16 states there exists a gap between Heller's (1968) upper bound on the free distance and its optimal value. This article reports on the construction of 16-state, binary, rate R=2/4 nonlinear trellis and convolutional codes having d _free=8; a free distance that meets the Heller upper bound. The nonlinear trellis code is constructed from a 16-state, rate R=1/2 convolutional code over Z₄ using the Gray map to obtain a binary code. Both convolutional codes are obtained by computer search. Systematic feedback encoders for both codes are potential candidates for use in combination with iterative decoding. Regarded as modulation codes for 4-PSK, these codes have free squared Euclidean distance d_{E, free}²=16     

Tight bounds on the redundancy of Huffman codes

A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p₁ of the most likely source letter is presented. This method will be used to compute bounds for all p₁⩾1/127, which were previously known only for a few special cases. Furthermore, the known optimal lower bound for binary Huffman codes is generalized to arbitrary code alphabets and some upper bounds for D-ary Huffman codes, 2⩽D<∞, are given, which are the tightest possible for all p₁⩾1/2