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.     

Bent-function sequences

In this paper we construct a new family of nonlinear binary signal sets which achieve Welch's lower bound on simultaneous cross correlation and autocorrelation magnitudes. Given a parameternwithn=0 pmod{4}, the period of the sequences is2^{n}-1, the number of sequences in the set is2^{n/2}, and the cross/auto correlation function has three values with magnitudesleq 2^{n/2}+1. The equivalent linear span of the codes is bound above bysum_{i=1}^{n/4}left(stackrel{n}{i} right). These new signal sets have the same size and correlation properties as the small set of Kasami codes, but they have important advantages for use in spread spectrum multiple access communications systems. First, the sequences are "balances," which represents only a slight advantage. Second, the sequence generators are easy to randomly initialize into any assigned code and hence can be rapidly "hopped" from sequence to sequence for code division multiple access operation. Most importantly, the codes are nonlinear in that the order of the linear difference equation satisfied by the sequence can be orders of magnitude larger than the number of memory elements in the generator that produced it. This high equivalent linear span assures that the code sequence cannot be readily analyzed by a sophisticated enemy and then used to neutralize the advantages of the spread spectrum processing.     

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.     

Recursive computations for the optimal tracking of time-varying parameters (Corresp.)

Recursive relations are given for updating the conditional densityp(theta_{k} | X_{k-1}, cdots X_{1})(also forp(theta_{k} | X_{k}, cdots, X_{1})), wheretheta_{k}is a parameter of the density ofX_{k}. The observationsX_{1}, X_{2}, cdotsare assumed to be conditionally independent (i.e., for known parameters), and the sequence of time-varying parameterstheta_{1}, theta_{2}, cdotsconstitutes a Markov-M sequence. The result requires the storage of an intermediate function of(theta_{k-1}, cdots , theta_{k-M}).     

Repeated use of codes which detect deception (Corresp.)

A senderAwants to sendNmessagesx_{i} = 1 , ldots ,N, chosen from a set containingMdifferent possible messages,M > N, to a receiverB. Everyx_{i}has to pass through the hands of a dishonest messengerC. ThereforeAandBagree on a mathematical transformationfand a secret parameter, or keyk, that will be used to produce the authenticatory_{i} = f(x_{i} , k ), which is sent together withx. The key is chosen at random from a set ofLelements.Cknowsfand can find all elements in the setG(x_{i},y_{i}) = {k|f(x_{i}, k) = y_{i}}given enough time and computer resources.Cwants to changex_{i} into x^{prime}withoutBsuspecting. This means thatCmust find the new anthenticatory^{prime} = f(x^{prime} , k). SinceG(x_{i},y_{i})can be found for any(x_{i},y_{i}), it is obvious thatCwill always succeed unlessG(x_{i},y_{i})contains more than one element. Here it is proved that the average probability of success forCis minimized if (a)G(x_{i}, y_{i})containsL^{(N-1)/N}elements and (b) each new known pair(x_{j}, y_{j})will diminish this set of solutions by a factor ofL^{-l/N}. The minimum average probability will then beL^{-l/N}.     

Multiple detection of a slowly fluctuating target (Corresp.)

A "slowly" fluctuating target is assumed to keep its radar cross section constant for the duration of several(M)dwells on target. To resolve multiple range and/or Doppler ambiguities, the received signal, which is presumably coherently processed (i.e., predetection integrated or matched filtered) over each dwell, must often be tested against a threshold, {em independently} of those on other dwells. Such a procedure is referred to as {em multiple detection}. A technique for the evaluation of a tight lower bound on the multiple-detection probabilityP_{M}, under Swerling case I statistics for the cross section, is presented in term of an infinite series and worked out in detail forP_{2}andP_{3}. Estimates on the computation error due to the truncation of the series are derived. Numerical results indicate thatP_{3}comes much closer toP_{1}than top_{1}^{3}or even toP_{1}P_{2}; at an expected signal-to-noise ratio of13dB and atP_{1} = 0.51, it obtains thatP_{3} geq 0.40, whereasP_{1}P_{2} = 0.23andp_{1}^{3} = 0.17.     

Hybrid low autocorrelation sequences (Corresp.)

Skew-symmetric sequences of(2n + 1)terms,a_0,a_1,cdots,a_{2n}, are described for which the "merit factor" begin{equation} F_h = frac{biggl[sum_{i=0}^{2n} mid a_i mid biggr] ^2}{ 2 sum_{k=1}^{2n} biggl[ sum_{i=0}^{2n-k} text{sign} (a_i) cdot a_{i+k} biggl] ^2} end{equation} is unusually high.     

A class of composite codes (Corresp.)

Certain useful properties of the cyclic codeVare discussed with wordsV(x)=V_{1}(x)(l+x^{n})/(l+x^{n_{1}})+V_{2}(x)(l+x^{n})/(l+x^{n_{2}}), where fori=1,2,V_{i}(x)belongs to a binary codeV_{i}of lengthn_{i}.     

Further classifications of codes meeting the Griesmer bound (Corresp.)

For any(n, k, d)binary linear code, the Griesmer bound says thatn geq sum_{i=0}^{k-1} lceil d/2^{i} rceil, wherelceil x rceildenotes the smallest integergeq x. We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - sum_{i=1}^{p} 2^{u_{i} -1} right), wherek > u_{1} > cdots > u_{p} geq 1. We characterize all such codes whenp = 2oru_{i-1}-u_{i} geq 2for2 leq i leq p.     

On the weight distribution of binary linear codes (Corresp.)

LetVbe a binary linear(n,k)-code defined by a check matrixHwith columnsh_{1}, cdots ,h_{n}, and leth(x) = 1ifx in {h_{1}, cdots , h_{n}, andh(x) = 0ifx in neq {h_{1}, cdots ,h_{n}}. A combinatorial argument relates the Walsh transform ofh(x)with the weight distributionA(i)of the codeVfor smalli(i< 7). This leads to another proof of the Plessith power moment identities fori < 7. This relation also provides a simple method for computing the weight distributionA(i)for smalli. The implementation of this method requires at most(n-k+ 1)2^{n-k}additions and subtractions,5.2^{n-k}multiplications, and2^{n-k}memory cells. The method may be very effective if there is an analytic expression for the characteristic Boolean functionh(x). This situation will be illustrated by several examples.     

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.     

Estimating a probability using finite memory

Let{X_{i}}_{i=1}^{infty}be a sequence of independent Bernoulli random variables with probabilitypthatX_{i} = 1and probabilityq=1-pthatX_{i} = 0for alli geq 1. Time-invariant finite-memory (i.e., finite-state) estimation procedures for the parameter p are considered which takeX_{1}, cdotsas an input sequence. In particular, an n-state deterministic estimation procedure is described which can estimate p with mean-square errorO(log n/n)and ann-state probabilistic estimation procedure which can estimatepwith mean-square errorO(1/n). It is proved that theO(1/n)bound is optimal to within a constant factor. In addition, it is shown that linear estimation procedures are just as powerful (up to the measure of mean-square error) as arbitrary estimation procedures. The proofs are based on an analog of the well-known matrix tree theorem that is called the Markov chain tree theorem.     

On source coding with side information at the decoder

Let{(X_k, Y_k, V_k)}_{k=1}^{infty}be a sequence of independent copies of the triple(X,Y,V)of discrete random variables. We consider the following source coding problem with a side information network. This network has three encoders numbered 0, 1, and 2, the inputs of which are the sequences{ V_k}, {X_k}, and{Y_k}, respectively. The output of encoder i is a binary sequence of rateR_i, i = 0,1,2. There are two decoders, numbered 1 and 2, whose task is to deliver essentially perfect reproductions of the sequences{X_k}and{Y_k}, respectively, to two distinct destinations. Decoder 1 observes the output of encoders 0 and 1, and decoder 2 observes the output of encoders 0 and 2. The sequence{V_k}and its binary encoding (by encoder 0) play the role of side information, which is available to the decoders only. We study the characterization of the family of rate triples(R_0,R_1,R_2)for which this system can deliver essentially perfect reproductions (in the usual Shannon sense) of{X_k}and{Y_k}. The principal result is a characterization of this family via an information-theoretic minimization. Two special cases are of interest. In the first,V = (X, Y)so that the encoding of{V_k }contains common information. In the second,Y equiv 0so that our problem becomes a generalization of the source coding problem with side information studied by Slepian and Wo1f [3].     

Successive encoding of correlated sources

The encoding of a discrete memoryless multiple source{( X_{i}, Y_{i})}_{i=1}^{infty}for reconstruction of a sequence{Z_{i}}_{i=1}^{infty}}, withZ_{i} = F( X_{i}, Y_{i}); i = 1,2, cdotsis considered. We require that the encoding should be such that{X_{i}}_{i=1}^{infty}is encoded first without any consideration of{Y_{i}}_{i=1}^{infty}, while in a second part of the encoding, this latter sequence is encoded based on knowledge of the outcome of the first encoding. The resulting scheme is called successive encoding. We find general outer and inner bounds for the corresponding set of achievable rates along with a complete single letter characterization for the special caseH( X_{i}|Z_{i}, Y_{i}) = 0. Comparisons with the Slepian-Wolf problem and the Ahlswede-Korner-Wyner side information problem are carried out.     

Higher dimensional orthogonal designs and applications

The concept of orthogonal design is extended to higher dimensions. A properg-dimensional design[d_{ijk cdots upsilon}]is defined as one in which all parallel(g-1)-dimensional layers, in any orientation parallel to a hyper plane, are uncorrelated. This is equivalent to the requirement thatd_{ijk cdots upsilon} in {0, pm x_{1}, cdots , pm x_{t} }, wherex_{1}, cdots , x_{t}are commuting variables, and thatsum_{p} sum_{q} sum_{r} cdots sum_{y} d_{pqr cdots ya} d_{pqr cdots yb} = left( sum_{t} s_{i}x_{i}^{2} right)^{g-1} delta ab,where(s{1}, cdots , s{t})are integers giving the occurrences ofpm x_{1}, cdots , pm x_{t}in each row and column (this is called the type(s_{1}, cdot ,s_{t})^{g-1})and(pqr cdots yz)represents all permutations of(ijk cdots upsilon). This extends an idea of Paul J. Shlichta, whose higher dimensional Hadamard matrices are special cases withx_{1}, cdots , x_{t} in {1,- 1}, (s_{1}, cdots, s_{t})=(g), and(sum_{t}s_{i}x_{i}^{2})=g. Another special case is higher dimensional weighing matrices of type(k)^{g}, which havex_{1}, cdots , x_{t} in {0,1,- 1}, (s_{1}, cdots, s_{t})=(k), and(sum_{t}s_{i}x_{i}^{2})=k. Shlichta found properg-dimensional Hadamard matrices of size(2^{t})^{g}. Proper orthogonal designs of type     

Asymptotic properties of delay-time-weighted probability of error (Corresp.)

Asymptotic properties of expected distortion are studied for the delay-time-weighted probability of error distortion measured_n(x,tilde{x}) = n^{-1} sum_{t=0}^{n-1} f(t + n)[l - delta(x_t,tilde{x}_t)],, wherex = (x_0,x_1,cdots,x_{n-1})andtilde{x} = (tilde{x}_0,tilde{x}_1,cdots,tilde{x}_{n-1})are source and reproducing vectors, respectively, anddelta (cdot, cdot)is the Kronecker delta. With reasonable block coding and transmission constraintsx_tis reproduced astilde{x}_twith a delay oft + ntime units. It is shown that if the channel capacity is greater than the source entropyC > H(X), then there exists a sequence of block lengthncodes such thatE[d_n(X,tilde{X})] rigjhtarrow 0asn rightarrow inftyeven iff(t) rightarrow inftyat an exponential rate. However, iff(t)grows at too fast an exponential rate, thenE[d_n(X,tilde{X})] rightarrow inftyasn rightarrow infty. Also, ifC < H(X)andf(t) rightarrow inftythenE[d_n(X,tilde{X})] rightarrow inftyasn rightarrow inftyno matter how slowlyf(t)grows.     

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.     

A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers (Corresp.)

A new source coding problem is considered for a one-way communication system with correlated source outputs{XY}. One of the source outputs, i.e.,{X}, must be transmitted to the receiver within a prescribed distortion tolerance as in ordinary source coding. On the other hand, the other source output, i.e.,{Y}, has to be kept as secret as possible from the receiver or wiretappers. For this case the equivocation-distortion functionGamma ast(d)and the rate-distortion-equivocation functionRast (d,e)are defined and evaluated. The former is the maximum achievable equivocation of{Y}under the distortion tolerancedfor{X}, and the latter is the minimum rate necessary to attain both the equivocation toleranceefor{Y}and the distortion tolerancedfor{X}. Some examples are included.     

Performance of the biased square-law sequential detector in the absence of signal

G. E. Albert's general sequential test for making one of r distinct decisions about a distribution functionF(x_{i}|x_{i-1})by observing a sequence ofx_{i}'s is presented, and his results, which give the performance of this test as the solutions of integral equations, are stated. This test is more general than the usual sequential probability ratio test of Wald, and includes nonoptimum, as well as Wald's optimum, sequential tests. Albert's equations are used to treat the incoherent detection of a sine wave in Gaussian noise by a biased square-law detector. This is the detector which uses samplesy_{i}of the envelope of the received waveform to calculate the sumsx_{i} = k sum_{j=1}^{i} (yj^{2} -bias), i = 1, 2, cdots, and sequentially compares thex_{i}to two thresholds until anx_{i}is found which is less than the lower thresholdB, or greater than the upper thresholdA. Then ifx_{i} leq B, it is decided that the signal is not present (dismissal), and ifA leq x_{i}it is decided that the signal is present (alarm). Though this is not the optimum detector for a sine wave in Gaussian noise (unless the SNR is very small), it is a convenient test to implement and is of considerable interest in its own right. Fory_{i}having the Rayleigh probability distributionf(y) = y exp{-y^{2}/2}, i.e., for the received waveform consisting of Gaussian noise alone, {em exact} solutions are obtained for the probability of (false) alarm and for the average test duration. These results are unique in that they are valid without restrictions on either the design input SNR or on the thresholds A and B. Curves of the probability of false alarm vs. the upper threshold A, and of the average test duration vs. the expected input SNR are presented, and are compared to similar results of Wald.