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.     

Some cross correlation properties for distorted signals

For a nondecreasing distortion characteristicphi(cdot)and a given signalx(cdot), the "cross correlation" function defined byR_{phi} (tau) triangleq int_{-infty}^{infty} phi[x(t)]x(t - tau) dtis shown to satisfy the inequalityR_{phi}(tau) leq R_{phi}(0), for alltau, generalizing an earlier result of Richardson that requiredphi(cdot)to be continuous and strictly increasing. The methods of the paper also show that, under weak conditions, begin{equation} R_{phi,psi}(tau) triangleq int_{-infty}^{infty} phi[x(t)]psi[x(t - tau)] dt leq R_{phi,psi}(0) end{equation} whenpsiis strictly increasing andphiis nondecreasing. In the case of hounded signals (e.g., periodic functions), the appropriate cross correlation function is begin{equation} mathcal{R}_{phi,psi}(tau} triangleq lim_{T rightarrow infty} (2T)^{-l} int_{-T}^T phi[x(t)]psi[x(t - tau)] dt. end{equation} For this case it is shown thatmathcal{R}_{phi,psi} (tau) leq mathcal{R}_{phi,psi}(0)for any nondecreasing (or nonincreasing) distortion functionsphiandpsi. The result is then applied to generalize an inequality on correlation functions for periodic signals due to Prosser. Noise signals are treated and inequalities of a similar nature are obtained for ensemble-average cross correlation functions under suitable hypotheses on the statistical properties of the noise. Inequalities of this type are the basis of a well-known method of estimating the unknown time delay of an observed signal. The extension to nondecreasing discontinuous distortion functions allows the use of hard limiting or quantization to facilitate the cross correlation calculation.     

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.     

Complexity-based induction systems: Comparisons and convergence theorems

In 1964 the author proposed as an explication of {em a priori} probability the probability measure induced on output strings by a universal Turing machine with unidirectional output tape and a randomly coded unidirectional input tape. Levin has shown that iftilde{P}'_{M}(x)is an unnormalized form of this measure, andP(x)is any computable probability measure on strings,x, thentilde{P}'_{M}geqCP(x)whereCis a constant independent ofx. The corresponding result for the normalized form of this measure,P'_{M}, is directly derivable from Willis' probability measures on nonuniversal machines. If the conditional probabilities ofP'_{M}are used to approximate those ofP, then the expected value of the total squared error in these conditional probabilities is bounded by-(1/2) ln C. With this error criterion, and when used as the basis of a universal gambling scheme,P'_{M}is superior to Cover's measurebast. WhenHastequiv -log_{2} P'_{M}is used to define the entropy of a rmite sequence, the equationHast(x,y)= Hast(x)+H^{ast}_{x}(y)holds exactly, in contrast to Chaitin's entropy definition, which has a nonvanishing error term in this equation.     

Maximum entropy and conditional probability

It is well-known that maximum entropy distributions, subject to appropriate moment constraints, arise in physics and mathematics. In an attempt to find a physical reason for the appearance of maximum entropy distributions, the following theorem is offered. The conditional distribution ofX_{l}given the empirical observation(1/n)sum^{n}_{i}=_{l}h(X_{i})=alpha, whereX_{1},X_{2}, cdotsare independent identically distributed random variables with common densitygconverges tof_{lambda}(x)=e^{lambda^{t}h(X)}g(x)(Suitably normalized), wherelambdais chosen to satisfyint f_{lambda}(x)h(x)dx= alpha. Thus the conditional distribution of a given random variableXis the (normalized) product of the maximum entropy distribution and the initial distribution. This distribution is the maximum entropy distribution whengis uniform. The proof of this and related results relies heavily on the work of Zabell and Lanford.     

Algorithms for the generation of full-length shift- register sequences

Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates2^{k cdot g(n,k)full cycles of length2^{n}, using3n + k cdot g(n, k)bits of storage, wherekis a free parameter in the range1 leq k leq 2^{((n-4)/2)}, andg(n, k)is of the order ofn - 2 log k. The second algorithm generates about2^{n^{2}/4}full cycles of length2^{n}, using aboutn^{2}/2bits of storage. In both algorithms, the time required to produce the next bit from the lastnbits is close ton. A possible application to the construction of stream ciphers is indicated.     

Characterization of stationary processes differentiable in mean square (Corresp.)

Recently Mazo and Salz proved that if{ Y(t), t in T }is a stationary random process with mean-square derivative{ dot{Y}(t), t in T }, then the conditional expectation ofdot{Y} (t)givenY(t)is zero almost everywhere with respect to the distribution ofY(t). We extend this property and obtain a characterization of stationary processes differentiable in mean square.     

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.     

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.     

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.     

A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)

A probabilistic polynomial-time algorithm for computing the square root of a numberx in {bf Z}/P{bf Z}, whereP = 2^{S}Q + 1(Qodd,s > 0)is a prime number, is described. In contrast to the Adleman, Manders, and Miller algorithm, this algorithm gets faster as s grows. As with the Berlekamp-Rabin algorithm, the expected running time of the algorithm is independent ofx. However, the algorithm presented here is considerably faster for values ofsgreater than2.     

Asymptotic performance and complexity of a coding scheme for memoryless channels

The purpose of this paper is to show that decoding complexity need not grow exponentially with the code block length at rates close to channel capacity and also to show the expediency of the approach of imbedding codes in each other. It is demonstrated that it is possible to communicate over a memoryless channel of capacityCat any rateR < Cwith a probability of error of less than2^{-E(R)nu}, E(R) > 0, per block of a length approximately proportional tonu^{2}and with a computational decoding complexity per digit which is asymptotically proportional tonu^{alpha}whennuis large,nu^{alpha}being finite forR < C.(alpha rightarrow mbox{as} R rightarrow C, alpha rightarrow 2 mbox{as} R rightarrow 0).     

On the accuracy of a numerical integration procedure for computing diffraction fields using table lookup

In this communication we have analyzed the errors introduced by table lookup when an electromagnetic diffraction integral is performed numerically. We have shown that in order to set the3sigmaerror of both the real and imaginary components equal tovarepsilon, the required table should have at leastKentries uniformly distributed within a2pirange, whereK geq 3.85/varepsilonsqrt{N}andNis the number of terms used for numerical integration. The maximum deviation of the amplitude (bar{R}) of this integral in this case is also less thanvarepsilonand the maximum phase deviation istan^{-1} (varepsilon/bar{R}). A numerical example is presented which confirms this prediction.     

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.     

On the quality factor of strip and line source antennas and its relationship to superdirectivity ratio

Exact formulas are derived for the quality factorQof strip and line source antennas. Contrary to popular opinion, none of them is equal to Taylor's superdirectivity ratiogammaor togamma - 1. But in the case ofE-plane strip sources (the complement of the type of strip source treated by Woodward and Lawson) the value ofQis precisely equal togamma_{alpha}^{-1/2}- 1, wheregamma_{alpha}^{beta}is a generalized superdirectivity ratio that reduces to Taylor'sgammawhen the edge exponentalphaand the pattern weighting exponentbetaare both zero. In the case ofH-plane strip sources the value ofQis approximately equal togamma_{alpha}^{1/2} - 1, and forH-plane line sources of vanishing widthait is approximately equal to[(2/pi) ln (2.516lambda/pi a)]gamma_{alpha}^{1}.     

Correlation of a signal with an amplitude-distorted form of itself

In comparing a signalf(t)with its amplitude-distorted formg(f(t)), whereg(cdot)is a monotonically increasing function of its argument, one is led to consider the correlation function begin{equation} R(s) triangleq int_{-infty}^{infty} dtg (f(t))f(t-s). end{equation} A rigorous proof is given of the inequalityR(s) leq R(O). Generalizations are presented for the cases of finite domains and of signals defined in two-dimensional space.     

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.     

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.     

On the distribution of de Bruijn sequences of given complexity

The distributiongamma (c, n)of de Bruijn sequences of ordernand linear complexitycis investigated. It is shown that forn geq 4, gamma (2^{n} - 1, n) equiv 0 pmod{8}, and fork geq 3, gamma (2^{2k} - 1,2k) equiv 0 pmod{l6}. It is also shown thatgamma (c, n) equiv 0 pmod{4}for allc, andn geq 3such thatcnis even.