Modulatable orthogonal sequences and their application to SSMAsystems

A set of N-1 orthogonal sequences of period N ² is proposed, where N is a natural number. Each orthogonal sequence proposed can be modulated by N complex numbers of absolute value 1, so the modulated sequence is also orthogonal. When N is an odd prime number, the absolute value of the cross-correlation function between any two of the N-1 orthogonal sequences is constant and satisfies the mathematical lower bound. This property of the cross-correlation function is not changed when each of the two orthogonal sequences is modulated by N complex numbers of absolute value 1. Two spread-spectrum multiple-access (SSMA) systems using these sequences are proposed. One system is an asynchronous SSMA system, using the proposed sequences unmodulated. The cochannel interference peak between any two channels in this system realizes the mathematical lower bound for an asynchronous SSMA system using a set of orthogonal sequences. The other system is a synchronous SSMA system without cochannel interference which uses the modulated form of the proposed sequences     

Frequency-hopping code sequence designs having large linear span

In frequency-hopping spread-spectrum multiple-access communication systems, it is desirable to use sets of hopping patterns that, in addition to having good Hamming correlation properties and large period, are also derived from sequences having large linear span. Here, two such frequency hopping code sequence designs that are based on generalized bent functions and generalized bent sequences are presented. The Hamming correlation properties of the designs are optimal in the first case and close to optimal in the second. In terms of the alphabet size p (required to be prime in both cases), the period and family size of the two designs are given by (p², p) and (p ⁿ, p^n/2+1) (n an even integer), respectively. The finite field sequences underlying the patterns in the first design have linear span exceeding p, whereas still larger linear spans (when compared to the sequence period) can be obtained using the second design method     

Effective recursive algorithm for computing multiplicative inversesin GF(2m)

Presents an effective recursive algorithm for computing multiplicative inverses in GF(2^m), where m=2^k, employing normal bases. The proposed algorithm requires m-1 cyclic shifts and two multiplications in GF (2^m) and in each subfield of GF(2^m): GF(2^m/2), GF(2^m/4),. . ., GF (2⁸) and GF(2⁴)     

On the influence of coding on the mean time to failure fordegrading memories with defects

The application of a combined test-error-correcting procedure is studied to improve the mean time to failure (MTTF) for degrading memory systems with defects. The degradation is characterized by the probability p that within a unit of time a memory cell changes from the operational state to the permanent defect state. Bounds are given on the MTTF and it is shown that, for memories with N words of k information bits, coding gives an improvement in MTTF proportional to (k/n) N(d_min^-2)/(d_min ^-1), where d_min and (k/n) are the minimum distance and the efficiency of the code used, respectively. Thus the time gain for a simple minimum-distance-3 is proportional to N^-1. A memory word test is combined with a simple defect-matching code. This yields reliable operation with one defect in a word of length k+2 at a code efficiency k/(k+2)     

Perfect N-phase sequences and arrays [spread spectrumcommunication]

Perfect sequences and arrays have periodic autocorrelation functions whose out-of-phase values are zero. Time-discrete N-phase sequences and arrays have complex elements of magnitude one, and one of (2π/N)n, 0⩽n<N , different phase values. Existence conditions and construction methods for perfect N-phase sequences and arrays with a small alphabet of possible phase values are introduced. Combining the existence conditions with, methods of advanced computer search, new perfect N-phase arrays have been found. The resulting lowest number N of perfect N-phase sequences and arrays up to 40 elements are given in a table, after having applied the construction methods     

Message delay and queue-size analysis for circuit-switched TDMAsystems

A multiple-access communications channel which is shared among network stations using a circuit-switched time-division multiple-access (CS-TDMA) scheme is examined. Each station is allocated a fixed number of slots (N) during each frame. The authors carry out queue-size message delay analysis for CS-TDMA systems. They derive the generating function of the queue size and of the waiting time distribution for a discrete-time Geom^[x]/Geom/N queuing system. This result is used to obtain the generating function of the system size for the CS-TDMA scheme. The associated computation requires the solution of (N+1)2^N linear equations. To derive a more computationally effective procedure, tight lower and upper bounds are obtained, requiring the solution of at most 3N linear equations. The authors prove that a slot allocation scheme which distributes station slots uniformly over the frame yields a message delay lower bound. The application of the results to the analysis of demand-assigned CS-TDMA systems is also discussed     

The impedance matrix localization (IML) method for moment-methodcalculations

The impedance matrix localization (IML) method, a modification of the standard method of moments that can be implemented as a modification to existing computer programs, is examined. This modification greatly eases the excessive storage requirements and long computation times of moment-method approaches by using novel bases and testing function that localize the important interactions to only a small number of elements within the impedance matrix elements can be made so small (typically 10 ^-4 to 10^-6 in relative magnitude) that they may be approximated by zero. In the case of a two-dimensional body with unknowns on its surface, both analytical arguments and numerical calculations suggest that, for an N×N matrix, about 100N matrix elements will need to be kept, even for very large N. The resulting sparse matrix requires storage for only 100N complex numbers rather than for N² numbers. Similar results are expected in three dimensions. The structure of the resulting matrix problem allows the use of highly efficient solution methods. Results are given for one such possibility: iteration preconditioned by incomplete LU decomposition     

4-phase sequences with near-optimum correlation properties

Two families of four-phase sequences are constructed using irreducible polynomials over Z₄. Family A has period L =2^r-1. size L+2. and maximum nontrivial correlation magnitude C_max⩽1+√(L+1), where r is a positive integer. Family B has period L=2(2^r-1). size (L+2)/4. and C_max for complex-valued sequences. Of particular interest, family A has the same size and period as the family of binary Gold sequences. but its maximum nontrivial correlation is smaller by a factor of √2. Since the Gold family for r odd is optimal with respect to the Welch bound restricted to binary sequences, family A is thus superior to the best possible binary design of the same family size. Unlike the Gold design, families A and B are asymptotically optimal whether r is odd or even. Both families are suitable for achieving code-division multiple-access and are easily, implemented using shift registers. The exact distribution of correlation values is given for both families     

On a very tight truncation error bound for stationary stochasticprocesses

A very tight truncation error upper bound is established for bandlimited weakly stationary stochastic processes if the sampling interval is closed. In particular, the magnitude of the upper bound is O(N^-2q ln² N) for a symmetric sampling reconstruction from 2N+1 sampled values, where q is an arbitrary positive integer. The results are derived with the help of the Bernstein bound on the remainder of a symmetric complex Fourier series of the function exp (iλ t). Convergence rates are given for mean square and almost sure sampling reconstructions     

Asymptotically optimal classification for multiple tests withempirically observed statistics

The decision problem of testing M hypotheses when the source is Kth-order Markov and there are M (or fewer) training sequences of length N and a single test sequence of length n is considered. K, M, n, N are all given. It is shown what the requirements are on M , n, N to achieve vanishing (exponential) error probabilities and how to determine or bound the exponent. A likelihood ratio test that is allowed to produce a no-match decision is shown to provide asymptotically optimal error probabilities and minimum no-match decisions. As an important serial case, the binary hypotheses problem without rejection is discussed. It is shown that, for this configuration, only one training sequence is needed to achieve an asymptotically optimal test     

Estimating the information content of symbol sequences andefficient codes

Several variants of an algorithm for estimating Shannon entropies of symbol sequences are presented. They are all related to the Lempel-Ziv algorithm (1976, 1977) and to recent algorithms for estimating Hausdorff dimensions. The average storage and running times increase as N and Nlog N, respectively, with the sequence length N. These algorithms proceed basically by constructing efficient codes. They seem to be the optimal algorithms for sequences with strong long-range correlations, e.g. natural languages. An application to written English illustrates their use     

Phase-locked laser array far-field normalization

The normalization of the far-field distribution from phase-locked linear arrays of evanescently coupled semiconductor diode lasers is evaluated. As the element number N→∞, the peak irradiance of the fundamental array mode tends to 81% of the peak irradiance of an array of in-phase equal-intensity diodes. It is also found that for N⩾10, the peak irradiance is proportional to 0.81 (1+1/N)N², and the diffraction-limited beamwidth is approximately 1.19 λ(N+1)S where λ is the vacuum wavelength and S is the array period. The far-field array factor is the same for an N-element array and an (N+1) S-wide cosine source as long as N⩾10     

Cascaded GMW sequences

Pseudorandom binary sequences with high linear complexity and low correlation function values are sought in many applications of modern communication systems. A new family of pseudorandom binary sequences, cascaded GMW sequences, is constructed. These sequences are shown to share many desirable correlation properties with the GMW sequences of B. Gordon, W.A. Mills, and L.R. Welch (1962)-for example, high-shifted autocorrelation values and, in many cases, three-valued cross-correlation values with m-sequences. It is shown, moreover, that in many cases the linear complexities of cascaded GMW sequences are far greater than those of GMW sequences     

Modular VLSI architectures for computing the arithmetic Fouriertransform

Modular, area-efficient VLSI architectures for computing the arithmetic Fourier transform (AFT) are proposed. By suitable design of PEs and I/O sequencing, nonuniform data dependencies in the AFT computation which require nonequidistant inputs and assignment of Mobius function values are resolved. The proposed design employs 2N+1 PEs to compute 2N+1 Fourier coefficients. Each PE has an adder and a fixed amount of local storage, and one PE has a multiplier. I/O with the host is performed using a fixed number of channels. This results in simple PE organization, compared with those needed in known DFT/FFT architectures. The design achieves O(N) speedup. It uses significantly fewer PEs than designs in the literature and supports real-time applications by allowing continuous sequential input. It can be extended to achieve linear speedup in a fixed size array with 2p+1 PEs, 1⩽p⩽N     

Signature sequence selection in a CDMA system with orthogonalcoding

In code-division multiple-access (CDMA) systems, recent attention has focused on the use of orthogonal coding to provide spreading. Each signal is coded with the same orthogonal or biorthogonal code, followed by a modulo-2 addition of a unique signature sequence. The set of signature sequences used determines how much signals interfere with each other at a receiver, thus determining the performance of the system. An analysis is presented to determine the properties of an optimal set of signature sequences for such a system. Using a Kerdock code, a set of signature sequences is presented which optimizes performance in a direct sequence CDMA system with (a) synchronous transmission, (b) no multipath time dispersion, and (c) orthogonal or biorthogonal Walsh-Hadamard coding as a means of spreading the information signal. For a length-N-binary code (where N is an even power of two), the set contains N/2 signature sequences. Approaches are discussed for the cases when N is an odd power of two and when more sequences are needed     

An efficient communication structure for distributed commitprotocols

To maintain consistency in a distributed database environment, the transactions must be executed atomically. The standard algorithm for ensuring an atomic execution is called the distributed commit protocol. The two-phase commit protocol and its variations, the well-known protocols used for this purpose, are characterized by successive rounds of message exchange, among all the sites of the database, at the time a transaction enters into a completion phase. The performance of these protocols is given by a complexity measure that depends on the communication structure of the protocol. Given N sites, the worst-case complexity of a commit protocol is O(N²). A communication structure called maximal binomial structure (MBS) is presented, for which the complexity of the protocol is O(N×log³ N). A lower bound for this complexity is also given, which is O(N×log² N). Protocols using the MBS remain symmetric. A scheme for an arbitrary expansion of the MBS to allow communication among a large number of sites is proposed. For the expanded system, the protocol complexity is also shown to be O(N×log³ N ). These structures are shown to be superior to other known structures     

Recursive T-matrix algorithms for the solution ofelectromagnetic scattering from strip and patch geometries

Two recursive T-matrix algorithms are presented and their reduced computational complexities and reduced memory requirements are demonstrated. These algorithms are applied to the problem of electromagnetic scattering from conducting strips and patches with canonical geometries. The geometries are reminiscent of finite-sized frequency selective surfaces. Computational complexities of O( N²) and O(N^7/3) and memory requirements of O(N) and O(N ^4/3) are shown to be feasible for two-dimensional and three-dimensional geometries, respectively. The formulation uses only two components of the electric field. Therefore, the vector electromagnetic problem of scattering from three-dimensional patch geometries can be solved using scalar addition theorems for spherical harmonic wave functions. For a two-dimensional strip problem, both TM and TE polarizations can be solved simultaneously using this formulation. Numerical scattering results in the form of radar cross sections (RCS) are validated by comparison with the method of moments     

Maximum likelihood estimation of the parameters of discretefractionally differenced Gaussian noise process

A maximum-likelihood estimation procedure is constructed for estimating the parameters of discrete fractionally differenced Gaussian noise from an observation set of finite size N. The procedure does not involve the computation of any matrix inverse or determinant. It requires N²/2+O(N) operations. The expected value of the loglikelihood function for estimating the parameter d of fractionally differenced Gaussian noise (which corresponds to a parameter of the equivalent continuous-time fractional Brownian motion related to its fractal dimension) is shown to have a unique maximum that occurs at the true value of d. A Cramer-Rao bound on the variance of any unbiased estimate of d obtained from a finite-sized observation set is derived. It is shown experimentally that the maximum-likelihood estimate of d is unbiased and efficient when finite-size data sets are used in the estimation procedure. The proposed procedure is extended to deal with noisy observations of discrete fractionally differenced Gaussian noise     

Performance analysis of nonblocking packet switch with input andoutput buffers

The performance of nonblocking packet switches such as the knockout switch and Batcher banyan switch for high-speed communication networks can be improved as the switching capacity L per output increases; the switching capacity per output refers to the maximum number of packets transferred to an output during a slot. The N×N switch with L=N was shown to attain the best possible performance by M.J. Karol et al. (1987). Here a N×N nonblocking packet switch with input and output buffers is analyzed for an arbitrary number of L such that 1⩽L⩽N. The maximum throughput and packet loss probability at input are obtained when N=∞     

A linear lightwave Benes network

The authors consider linear lightwave networks with a single waveband that have N inputs, each with a transmitter, and N outputs, each with a receiver, interconnected by optical links, broadcast stars, and wavelength-independent 2×2 switches. The transmitters and receivers can tune to C different wavelengths. The authors describe a rearrangeably nonblocking network that is a modification of the Benes network and uses transmitters that are fixed tuned and switches with two states. The network uses [1+o(1)] N/log₂(N/C) switches, which is shown to be nearly the minimum number. It is also shown that, if C =o(log N), then a rearrangeably nonblocking network requires [1+o(1)]Nlog₂N switches even if the switches have more than two states