On optimum time-hopping patterns

Time-hopping patterns can be constructed from simple difference sets. By studying such constructions, it has been proven that whenever n-2, n-1, or n+1 is a prime power, then time-hopping patterns that have n terms can be constructed and are of length less than n². By computation it is shown that such patterns can have length less than n²-n^1.44 for all n⩽150. It is also shown that time-hopping patterns for n terms can have length less than n²+O(n^1.55) for all n     

Fast decoding of codes from algebraic plane curves

Improvement to an earlier decoding algorithm for codes from algebraic geometry is presented. For codes from an arbitrary regular plane curve the authors correct up to d*/2-m² /8+m/4-9/8 errors, where d* is the designed distance of the code and m is the degree of the curve. The complexity of finding the error locator is O(n^7/3 ), where n is the length of the code. For codes from Hermitian curves the complexity of finding the error values, given the error locator, is O(n²), and the same complexity can be obtained in the general case if only d*/2-m²/2 errors are corrected     

Reliability of consecutive-k-out-of-n:F systemswith nonidentical component reliabilities

A system with n components in sequence is a consecutive- k-out-of-n:F system if it fails whenever k consecutive components are failed. Under the supposition that component failures need not be independent and that component failure probabilities need not be equal, a topological formula is presented for the exact system reliability of linear and circular consecutive-k -out-of-n:F networks. The number of terms in the reliability formula is O(n⁴) in the linear case and O(n⁵) in the circular case     

Efficient algorithm for reliability of a circular consecutive-k-out-of-n:F system

The time complexities of previously published algorithms for circular consecutive-k-out-of-n:F systems are O (nk²) and O(nk). The authors propose a method to improve the original O(nk² ) algorithm, and hence derive an O(nk) algorithm     

Reliability of linear and circular consecutively-connected systems

J.G. Shanthikumar (IEEE Trans. Reliability, vol.R-36, p.546-50, Dec. 1987) proposed a new system structure called the consecutively connected system, which is a generalization of the well-studied consecutive-k-out-of-n:F system. An O(n ²) algorithm was developed for its reliability evaluation. This work studies the structure of the consecutively connected system and provides more efficient algorithms for its reliability evaluation. The complexities of the algorithms are of order O(kn) for linear systems and O(k³n) for circular systems (k <n). The concepts of transmitting capability and receiving capability are introduced     

Multistate consecutively-connected systems

G. Shanthikumar (ibid., vol.R-36, p.546-550, Dec. 1987) has proposed a system called the consecutively connected system, which is a generalization of the consecutive-k-out-of-n:F system. He gave an O(n²) algorithm for computing the reliability of the consecutively connected system. In the present work, the authors further generalize it by assuming that the components are multistate. They give an O(Kn) algorithm for computing the reliability of the multistate system where K(K<n) is the maximum number of states for a component. They discuss the difficulties of obtaining corresponding algorithms for circular systems and two-way communication, although for two-state components they are able to extend the Shanthikumar algorithm to circular systems     

A generalized recursive algorithm for wave-scattering solutions intwo dimensions

A generalized recursive algorithm valid for both the E _z and H_z wave scattering of densely packed scatterers in two dimensions is derived. This is unlike previously derived recursive algorithms which have been found to be valid only for E_z polarized waves. In this generalized recursive algorithm, a scatterer is first divided into N subscatterers. The n-subscatterer solution is then used to solve the (n+n')-subscatterer solution. The computational complexity of such an algorithm is found to be of O (N²) in two dimensions while providing a solution valid for all angles of incidence. This is better than the method of moments with Gaussian elimination, which has an O(N³) complexity     

A multiple scattering solution for the effective permittivity of asphere mixture

A recursive algorithm for calculating the exact solution of a random assortment of spheres is described. In this algorithm, the scattering from a single sphere is expressed in a one-sphere T matrix. The scattering from two spheres is expressed in terms of two-sphere T matrices, which are related to the one-sphere T matrix. A recursive algorithm to deduce the (n+1)-sphere T matrix from the n-sphere T matrix is derived. With this recursive algorithm, the multiple scattering from a random assortment of N spheres can be obtained. This results in an N² algorithm rather than the normal N³ algorithm. As an example, the algorithm is used to calculate the low-frequency effective permittivity of a random assortment of 18 dielectric spheres. The effective permittivity deviates from the Maxwell-Garnett result for high contrast and high packing fraction. With a high packing fraction, dielectric enhancement at low frequency is possible     

The fast multipole method (FMM) for electromagnetic scatteringproblems

The fast multipole method (FMM) developed by V. Rokhlin (1990) to efficiently solve acoustic scattering problems is modified and adapted to the second-kind-integral-equation formulation of electromagnetic scattering problems in two dimensions. The present implementation treats the exterior Dirichlet problem for two-dimensional, closed, conducting objects of arbitrary geometry. The FMM reduces the operation count for solving the second-kind integral equation from O(n³) for Gaussian elimination to O(n^4/3) per conjugate-gradient iteration, where n is the number of sample points on the boundary of the scatterer. A sample technique for accelerating convergence of the iterative method, termed complexifying k, the wavenumber, is also presented. This has the effect of bounding the condition number of the discrete system; consequently, the operation count of the entire FMM (all iterations) becomes O(n^4/3). Computational results for moderate values of ka, where a is the characteristic size of the scatterer, are given     

Fast algorithm and architecture for constrained adaptive side-lobecancellation

An efficient implementation of auxiliary constraints for a concurrent-block least-squares adaptive side-lobe canceler is described. A QR decomposition of the auxiliary data matrix is computed, and this information is sent to one or more main beam processors, where the constraints are applied using blocking matrices and the individual residuals are computed. Structured blocking matrices are used to derive a fast algorithm and architecture for constrained main beam processing. This approach reduces the operation count of this phase of the processing from O(n³) to O(n ²), where n is the number of auxiliary sensors     

Reliability polynomial for a ring network

A mathematical model is developed for the reliability of a system made up of m unreliable nodes arranged in a ring. The model can be used to calculate the reliability of single-ring networks in which the network recovery mechanism depends on bypassing failed stations, but link signal power margins are inadequate to overcome losses due to more than n bypass switches in series. Computational complexity is 0(n²m+nm²/2) in time, and 0(m²/2) in memory requirements     

Monte Carlo particle investigation of noise in shortn+-n-n+ GaAsdiodes

The noise current spectral density in n⁺-n -n⁺ GaAs diodes is computed by the Monte Carlo particle technique employing a three-valley model. The normalised spectral density is found to decrease with field for a short sample length     

On the number of points on shells for shiftedZ4n lattices

A conjecture is proven on the number of points on shells for the shifted Z⁴ and the shifted Z⁸ lattices. Furthermore, the results are extended to any shifted Z⁴ⁿ lattice (n=0, 1, . . .). These results provide an easy way to compute the number of points on shells for the type of lattices used in the design of multidimensional signal sets or in vector coding     

Optimal replacement policies for k-out-of-nsystems

The authors study a discrete-time, infinite-horizon, dynamic programming model for the replacement of components in a binary k -out-of-n:F system. The goal is to trade off the component replacement and system failure costs. Under the criterion of minimizing the long-run average cost per period, it is optimal to follow a critical component policy (CCP), viz., a policy specified by a critical component set and the rule: replace a component if and only if it is failed and is in the critical component set. Computing an optimal CCP is a binary nonlinear programming problem, which can be solved by searching through a set with O(n^k-1) points. This approach to finding an optimal CCP is practical when k is small. In particular, assuming s-independent components, it requires O(n^2k-1) calculations. The authors analyze in detail the two most important cases with small k: the series (1-out-of-n:F) system and the 2-out-of-n:F system     

pn+ junction in an implanted electroactive polymer:poly(paraphenylene)

The authors have recently shown that specific and stable n or p doping may be obtained on poly(paraphenylene), providing moderate implantation conditions with appropriate ions are used. Here they describe a pn⁺-junction made in intrinsic insulating poly(paraphenylene) (α<10^-12 Ω^-1 cm^-1) by implantation (E≃50 keV) of alkali metal ions (essentially caesium for n doping) and halogen (iodine for p doping)     

Systolic arrays for matrix I/O format conversion

New 1-slow and 2-slow systolic arrays for row-to-diagonal and diagonal-to-row input/output format conversion of matrices are given. For n×n matrices, the arrays consist of n ² cells. A 1-slow systolic array performs the conversion in 2n-1 periods. The arrays can be used also for column-to-diagonal, diagonal-to-column, row-to-column and column-to-row input/output format conversions. The 1-slow array performs these operations in 2 n-1, 2 n-1, and 3 n-1 periods, respectively     

On updating signal subspaces

The authors develop an algorithm for adaptively estimating the noise subspace of a data matrix, as is required in signal processing applications employing the `signal subspace' approach. The noise subspace is estimated using a rank-revealing QR factorization instead of the more expensive singular value or eigenvalue decompositions. Using incremental condition estimation to monitor the smallest singular values of triangular matrices, the authors can update the rank-revealing triangular factorization inexpensively when new rows are added and old rows are deleted. Experiments demonstrate that the new approach usually requires O(n²) work to update an n×n matrix, and that it accurately tracks the noise subspace     

Parallel testing of parametric faults in a three-dimensionaldynamic random-access memory

A testable design of dynamic random-access memory (DRAM) architecture which allows one to access multiple cells in a word line simultaneously is presented. The technique utilizes the two-dimensional (2-D) organization of the DRAM and the resulting speedup of the conventional algorithm is considerable. The failure mechanism in the three-dimensional (3-D) DRAM with trench-type capacitor is specifically investigated. As opposed to the earlier approaches for testing parametric faults that used sliding diagonal-type tests with O(n^3/2) complexity, the algorithms discussed here are different and have O(√n/p) complexity, where p is the number of subarrays within the DRAM chip. These algorithms can be applied externally from the chip and also they can be easily generated for built-in self-test applications     

On the number of memories that can be perfectly stored in a neuralnet with Hebb weights

Let {w_ij} be the weights of the connections of a neural network with n nodes, calculated from m data vectors v¹, ···, v^m in {1,-1}ⁿ, according to the Hebb rule. The author proves that if m is not too large relative to n and the v^k are random, then the w_ij constitute, with high probability, a perfect representation of the v^k in the sense that the v ^k are completely determined by the w_ij up to their sign. The conditions under which this is established turn out to be less restrictive than those under which it has been shown that the v^k can actually be recovered by letting the network evolve until equilibrium is attained. In the specific case where the entries of the v^k are independent and equal to 1 or -1 with probability 1/2, the condition on m is that m should not exceed n/0.7 log n     

A fast algorithm for the Fourier transform over finite fields andits VLSI implementation

The Fourier transform over finite fields is mainly required in the encoding and decoding of Reed-Solomon and BCH codes. An algorithm for computing the Fourier transform over any finite field GF(p^m) is introduced. It requires only O(n(log n)²/4) additions and the same number of multiplications for an n-point transform and allows in some fields a further reduction of the number of multiplications to O(n log n). Because of its highly regular structure, this algorithm can be easily implementation by VLSI technology