On efficient majority logic decodable codes

A particular shortening technique is applied to majority logic decodable codes of length2^{t}. The shortening technique yields new efficient codes of lengthsn = 2^{p}, wherepis a prime, e.g., a (128,70) code withd_{maj} = 16. For moderately long code lengths (e.g.,n = 2^{11} or 2^{13}), a 20-25 percent increase in efficiency can be achieved over the best previously known majority logic decodable codes. The new technique also yields some efficient codes for lengthsn = 2^{m}wheremis a composite number, for example, a (512,316) code withd_{maj} = 32code which has 42 more information bits than the previously most efficient majority logic decodable code.     

On the inequivalence of generalized Preparata codes

Ifmis odd andsigma /in Aut GF(2^{m})is such thatx rightarrow x^{sigma^{2}-1}is1-1, there is a[2^{m+1}-1,2^{m+l}-2m-2]nonlinear binary codeP(sigma)having minimum distance 5. All the codesP(sigma)have the same distance and weight enumerators as the usual Preparata codes (which rise asP(sigma)whenx^{sigma}=x^{2}). It is shown thatP(sigma)andP(tau)are equivalent if and only iftau=sigma^{pm 1}, andAut P(sigma)is determined.     

Complete decoding of triple-error-correcting binary BCH codes

An extensive study of binary triple-error-correcting codes of primitive lengthn = 2^{m} - 1is reported that results in a complete decoding algorithm whenever the maximum coset weightW_{max}is five. In this regard it is shown thatW_{max} = 5when four dividesm, and strong support is provided for the validity of the conjecture thatW_{max} = 5for allm. The coset weight distribution is determined exactly in some cases and bounded in others.     

The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)

It is shown thatsqrt[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Sincesqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, wheresqrt{2}is inGF(F_{2})=GF(17), is given.     

Characterization theorems for extending Goppa codes to cyclic codes (Corresp.)

Several theorems are presented which characterize Goppa codes having the property of becoming cyclic when an overall parity cheek is added. If such a Goppa code has location setL = GF (q^{m})and a Goppa polynomialg(z)that is irreducible overGF(q^{m}), theng(z)must be a quadratic. Goppa codes defined by(z- beta)^{a}and location setLwith cardinalitynsuch thatn+l|q^{m}-1are considered along with their subcodes. A sufficient condition onLis derived for the extended codes to become cyclic. This condition is also necessary whena= 1. The construction ofLfor differentnsatisfying the stated condition is investigated in some detail. Some irreversible Goppa codes have been shown to become cyclic when extended by an overall parity check.     

An approximation to the weight distribution of binary primitive BCH codes with designed distances 9 and 11 (Corresp.)

Recently Kasami {em et al.} presented a linear programming approach to the weight distribution of binary linear codes [2]. Their approach to compute upper and lower bounds on the weight distribution of binary primitive BCH codes of length2^{m} - 1withm geq 8and designed distance2t + 1with4 leq t leq 5is improved. From these results, the relative deviation of the number of codewords of weightjleq 2^{m-1}from the binomial distribution2^{-mt} left( stackrel{2^{m}-1}{j} right)is shown to be less than 1 percent for the following cases: (1)t = 4, j geq 2t + 1andm geq 16; (2)t = 4, j geq 2t + 3and10 leq m leq 15; (3)t=4, j geq 2t+5and8 leq m leq 9; (4)t=5,j geq 2t+ 1andm geq 20; (5)t=5, j geq 2t+ 3and12 leq m leq 19; (6)t=5, j geq 2t+ 5and10 leq m leq 11; (7)t=5, j geq 2t + 7andm=9; (8)t= 5, j geq 2t+ 9andm = 8.     

Mutual information of the white Gaussian channel with and without feedback

The following model for the white Gaussian channel with or without feedback is considered: begin{equation} Y(t) = int_o ^{t} phi (s, Y_o ^{s} ,m) ds + W(t) end{equation} wheremdenotes the message,Y(t)denotes the channel output at timet,Y_o ^ {t}denotes the sample pathY(theta), 0 leq theta leq t. W(t)is the Brownian motion representing noise, andphi(s, y_o ^ {s} ,m)is the channel input (modulator output). It is shown that, under some general assumptions, the amount of mutual informationI(Y_o ^{T} ,m)between the messagemand the output pathY_o ^ {T}is directly related to the mean-square causal filtering error of estimatingphi (t, Y_o ^{t} ,m)from the received dataY_o ^{T} , 0 leq t leq T. It follows, as a corollary to the result forI(Y_o ^ {T} ,m), that feedback can not increase the capacity of the nonband-limited additive white Gaussian noise channel.     

On the eigenfunction expansion of electromagnetic dyadic Green's functions

A relatively simple approach is described for developing the complete eigenfunction expansion of time-harmonic electric (bar{E}) and magnetic (bar{H}) fields within exterior or interior regions containing an arbitrarily oriented electric current point source. In particular, these results yield directly the complete eigenfunction expansion of the electric and magnetic dyadic Green's functionsbarbar{G}_{e}andbarbar{G}_{m}that are associated withbar{E}andbar{H}, respectively. This expansion ofbarbar{G}_{e}andbarbar{G}_{m}contains only the solenoidal type eigenfunctions. In addition, the expansion ofbarbar{G}_{e}also contains an explicit dyadic delta function term which is required for making that expansion complete at the source point. The explicit dyadic delta function term inbarbar{G}_{e}is found readily from a simple condition governing the behavior of the eigenfunction expansion at the source point, provided one views that condition in the light of distribution theory. These general expressions for the eigenfunction expansion ofbarbar{G}_{e}andbarbar{G}_{m}reduce properly to those obtained previously for special geometries by Tai.     

Dyadic Green's functions for a coaxial line

The eigenfunction expansions of the dyadic Green's functions for a coaxial line have been derived based on the method ofbarbar{G}_{m}, whereby the irrotational vector wave functionbar{L}is not needed. A dyadic boundary condition for the discontinuity of the tangential component ofbarbar{G}_{m}has been used to facilitate the derivation of the expression for the electric dyadic Green's function.     

High-radix transforms for Reed-Solomon codes over Fermat primes (Corresp.)

It is shown that a high-radix fast Fourier transform (FFT) with generatorgamma = 3over GF(F_{n}), whereF_{n} = 2^{2}^{n'} + 1is a Fermat prime, can be used for encoding and decoding of Reed-Solomon (RS) codes of length2^{2}^{n}. Such an RS decoder is considerably faster than a decoder using the usual radix 2 FFT. This technique applies most ideally to a 16-error-correcting, 256-symbol RS code of 8 bits being considered currently for space communication applications. This special code can be encoded and decoded rapidly using a high-radix FFT algorithm over GF(F_{3}).     

Bounds on the redundancy of Huffman codes (Corresp.)

New upper bounds on the redundancy of Huffman codes are provided. A bound that for2/9 leq P_{1} leq 0.4is sharper than the bound of Gallager, when the probability of the most likely source letterP_{1}is the only known probability is presented. The improved bound is the tightest possible for1/3 leq P_{1} leq 0.4. Upper bounds are presented on the redundancy of Huffman codes when the extreme probabilitiesP_{1}andP_{N}are known.     

On certain projective geometry codes (Corresp.)

LetVbe an(n, k, d)binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s}, andd geq [(q^{m-r}-1)/(q - 1)] + 1. This code isr-step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} }, the generator polynomialg(X), ofV, hasalpha^{nu}as a root if and only ifnuhas the formnu = i(q - 1)andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1), whereW_{q}(x)indicates the weight of the radix-qrepresentation of the numberx. LetSbe the set of nonzero numbersnu, such thatalpha^{nu}is a root ofg(X). LetC_{1}, C_{2}, cdots, C_{nu}be the cyclotomic cosets such thatSis the union of these cosets. It is clear that the process of findingg(X)becomes simpler if we can find a representative from eachC_{i}, since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2, withs = 2, 3, andm-r=3, withs=2.     

An algorithm for maximizing expected log investment return

Let the random (stock market) vectorX geq 0be drawn according to a known distribution functionF(x), x in R^{m}. A log-optimal portfoliob^{ast}is any portfoliobachieving maximal expectedlogreturnW^{ast}=sup_{b} E ln b^{t}X, where the supremum is over the simplexb geq 0, sum_{i=1}^{m} b_{i} = 1. An algorithm is presented for findingb^{ast}. The algorithm consists of replacing the portfoliobby the expected portfoliob^{'}, b_{i}^{'} = E(b_{i}X_{i}/b^{t}X), corresponding to the expected proportion of holdings in each stock after one market period. The improvement inW(b)after each iteration is lower-bounded by the Kullback-Leibler information numberD(b^{'}|b)between the current and updated portfolios. Thus the algorithm monotonically improves the returnW. An upper bound onW^{ast}is given in terms of the current portfolio and the gradient, and the convergence of the algorithm is established.     

Low-rate tree coding of autoregressive sources (Corresp.)

The performance of differential pulse-code modulation and random codes is evaluated experimentally for a range of autoregressive sources, including Gaussian and Laplacian sources of orders1, 2, and3encoded at rates1, 2, and7. Correlations are typical of those encountered in speech and images. Results show that the gain from a fixed moderate degree of code searching increases as the rate decreases, and increases consistently with1 /D_{o}, whereD_{o}is the Berger-Gray critical distortion. Laplacian and Gaussian sources behave similarly. Random codes perform better than DPCM codes for lightly correlated Laplacian sources but are otherwise worse.     

General theory of doubly periodic arrays over an arbitrary finite field and its applications

A general theory of doubly periodic (DP) arrays over an arbitrary finite field GF(q)is presented. First the basic properties of DP arrays are examined. Next modules of linear recurring (LR) arrays are defined and their algebraic properties discussed in connection with ideals in an extension ringtilde{R}of the ringRof bivariate polynomials with coefficients in GF(q). A finitetilde{R}-module of DP arrays is shown to coincide with thetilde{R}-module of LR arrays dermed by a zero-dimensional ideal intilde{R}. Equivalence relations between DP arrays are explored, i.e., rearrangements of arrays by means of unimodular transformations. Decimation and interleaving of arrays are defined in a two-dimensional sense. The general theory is followed by application to irreducible LR arrays. Among irreducible arrays,M-arrays are a two-dimensional analog ofM-sequences and may be constructed fromM-sequences by means of unimodular transformations. The results of this paper are also important in studying properties of Abelian codes.     

On the survival of sequence information in filters (Corresp.)

Given a binary data streamA = {a_i}_{i=o}^inftyand a filterFwhose output at timenisf_n = sum_{i=0}^{n} a_i beta^{n-i}for some complexbeta neq 0, there are at most2^{n +1)distinct values off_n. These values are the sums of the subsets of{1,beta,beta^2,cdots,beta^n}. It is shown that all2^{n+1}sums are distinct unlessbetais a unit in the ring of algebraic integers that satisfies a polynomial equation with coefficients restricted to +1, -1, and 0. Thus the size of the state space{f_n}is2^{n+1}ifbetais transcendental, ifbeta neq pm 1is rational, and ifbetais irrational algebraic but not a unit of the type mentioned. For the exceptional values ofbeta, it appears that the size of the state space{f_n}grows only as a polynomial innifmidbetamid = 1, but as an exponentialalpha^nwith1 < alpha < 2ifmidbetamid neq 1.     

Narrow-band systems and Gaussianity

The approach to Gaussianity of the outputy(t)of a narrow-band systemh(t)is investigated. It is assumed that the inputx(t)is ana-dependent process, in the sense that the random variablesx(t)andx(t + u)are independent foru > a. WithF(y)andG(y)the distribution functions ofy(t)and of a suitable normal process, a realistic boundBon the differenceF(y) -- G(y)is determined, and it is shown thatB rightarrow 0as the bandwidthomega_oof the system tends to zero. In the special case of the shot noise process begin{equation} y(t) = sum_i h(t - t_i) end{equation} it is shown that begin{equation} mid F(y) - G(y) mid < (omega_o/lambda) frac{1}{2} end{equation} wherelambda_iis the average density of the Poisson pointst_i.     

Equidistant binary arithmetic codes (Corresp.)

LetC(B)denote the binary cyclicANcode with generatorA, whereAB=2^{n} - 1. It is known thatC(B)is equidistant ifBis a prime powerp^{k}, where either2or-2is primitive moduloBprovidedpequiv 1 pmod{3}{rm if} k > 1. It is conjectured that these are the onlyBsuch thatC(B)is equidistant. We have verified this forB < 100 000. Several results are established that further limit the possibilities for counterexamples to the conjecture.     

Some periodic convolutional codes better than any fixed code (Corresp.)

Some(n_{o}=2; k_{o}=1)noncatastrophic periodic convolutional codes with memoryM=4are given that have the same free distance,d_{infty}, as the best fixed code but have both a smaller number of paths of weightd_{infty}per time instant and a smaller average number of information bit errors per such path for periodsT=2, 3, 4, and5. It is also shown that an(n_{0}, k_{0})code of periodTis equivalent to a fixed code with parameters(Tn_{0}, Tk_{0}).