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     

An efficient non-recursive algorithm for computing the reliabilityof k-out-of-n systems

An algorithm for computing the reliability of k-out-of- n systems is proposed. It is simple, easy to implement on a computer, time and memory efficient, and good for numerical computation. The memory complexity is O(n-k), and for a given value of n-k the computation time is proportional to n . Its FORTRAN implementation is presented     

Efficient algorithm for logic design using multiplexers

An algorithmic procedure has been developed for the realisation of any Boolean function F(n) of n variables with a single multiplexer of minimum size. This procedure gives the choice of control variables to be used for the realisation of the function. The algorithm is iterative in nature and very suitable for machine implementation     

Design of C-testable DCVS binary array dividers

Clocked differential cascode voltage switch (DCVS) circuits are dynamic CMOS circuits that have the advantage of being protected against test-set invalidation due to circuit delays and timing skews. The problem of testing nonrestoring and restoring DCVS binary array dividers is discussed. It is shown that a DCVS nonrestoring array divider can be made C-testable with only four or five vectors. These vectors detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The additional hardware required to achieve C-testability for an n×n nonrestoring array divider only consists of n-1 two-input XOR gates and one control input. It is also shown that a restoring DCVS binary array divider can be made C-testable with only six vectors, which also detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The hardware overhead required for the C-testable design of the n×n restoring array divider consists of n two-input XOR gates and one control input     

An efficient design of embedded memories and their testability analysis using Markov chains

This article presents a design strategy for efficient and comprehensive random testing of embedded random-access memory (RAM) where neither are the address, read/write and data input lines directly controllable nor are the data output lines externally observable. Unlike the conventional approaches, which frequently employ on-chip circuits such as linear feedback shift register (LFSR), data registers and multibit comparator for verifying the response of the memory-under-test (MUT) with the reference signature of a fault-free gold unit, the proposed technique uses an efficient testable design, which helps accelerate test algorithms by a factor of 0.5n, if the RAM is organized into an n×1 array and improve the test reliability by eliminating the LFSR that is known to have aliasing problems. Another serious problem in embedded memory testing by random test patterns is the problem of memory initialization, which has been tackled here by adding word-line flag registers. The paper has made indepth empirical studies of the functional faults such as stuck-at, coupling, and pattern-sensitive by suitably representing these faults by Markov chains and by simulating these chains to derive various test lengths required for detecting these faults. The simulation results conclusively show that, in order to test a IM-bit RAM for detecting the common functional faults, the proposed technique needs only one second as opposed to about an hour needed by the conventional random testing where memory cells are tested sequentially.An abridged version of this article was published in the IEEE International Conference on Wafer-Scale Integration, January 1989. This research was partially supported by the NSF under grant number MIP-9013092 and by ONR under grant number 85-K-0716.     

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     

Delay analysis of continuous bit rate traffic over an ATM network

A packet multiplexer is modeled for continuous bit rate (CBR) traffic in an asynchronous transfer mode (ATM) network as an nD/D/1 queue. The efficiencies of various algorithms for finding the delay distribution are compared. In particular, a new algorithm is proposed whose time complexity is O(n²), where n is the number of voice sources being multiplexed. The use of the central limit theorem can reduce the time complexity to O(n) for large n . An asymptotic formula is found whose time complexity is independent of n and it works well (for practical purposes) over a wide range of parameter values. The authors examine and comment on the use of the M/D/1 results as an approximation. In addition to comparing the performances of these algorithms, they show that the buffer requirements for such a queue are significantly less than the theoretical maximum (even when the requirement on the call disruption probability is very low). This result has important implications in the design of buffer size. The buffer requirement is relatively insensitive to the design criterion (call disruption probability)     

Maximum-rank array codes and their application to crisscross errorcorrection

A μ-[n×n,k] array code C over a field F is a k-dimensional linear space of n×n matrices over F such that every nonzero matrix in C has rank ⩾μ. It is first shown that the dimension of such array codes must satisfy the Singleton-like bound k⩽n(n-μ+1). A family of so-called maximum-rank μ-[n×n,k=n ( n-μ+1)] array codes is then constructed over every finite field F and for every n and μ, 1⩽μ⩽n . A decoding algorithm is presented for retrieving every Γ∈C, given a received array Γ+E, where rank (E)+1⩽(μ-1)/2. Maximum-rank array codes can be used for decoding crisscross errors in n×n bit arrays, where the erroneous bits are confined to a number t of rows or columns (or both). This construction proves to be optimal also for this model of errors. It is shown that the behavior of linear spaces of matrices is quite unique compared with the more general case of linear spaces of n×n. . .×n hyper-arrays     

How much information can one bit of memory retain about a Bernoullisequence?

The maximin problem of the maximization of the minimum amount of information that a single bit of memory retains about the entire past is investigated. The problem is to estimate the supremum over all possible sequences of update rules of the minimum information that the bit of memory at epoch (n+1) retains about the previous n inputs. Using only elementary techniques, it is shown that the maximin covariance between the memory at epoch (n+1) and past inputs is Θ(1/n), the maximum average covariance is Θ(1/n ), and the maximin mutual information is Ω(1/n² ). In a consideration of related issues, the authors also provide an exact count of the number of Boolean functions of n variables that can be obtained recursively from Boolean functions of two variables, discuss extensions and applications of the original problem, and indicate links with issues in neural computation     

A testable CMOS asynchronous counter

A testable design for an asynchronous n-bit CMOS counter is presented, with test inputs that provide full coverage for stuck-at and stuck-open faults. The test time is O(n) where the counter outputs are not observable, compared to O(n ²) for a synchronous counter. Three control signals are required for the testable counter as opposed to one reset signal for the base counter. The testable counter incorporates a scan path, utilizing the state storage in the counter cells, whereby the counter is converted into an n-bit master-slave asynchronous shift register with the counter's request input being used as the shift-register input. The only observable outputs are acknowledge and carry-out signals. The counter utilizes two-cycle (transition) signaling and guarantees that new output values are available before acknowledge is toggled. Two 16-b counters, one base design and one scan-based design, were fabricated on the same chip (2.0-μm n-well CMOS) through MOSIS. Four parts were received, all of which passed the test suites developed     

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     

Systolic array designs for Kalman filtering

Systolic Kalman filter (SKF) designs based on a triangular array (triarray) configuration are presented. A least squares formulation, which is an expanded matrix representation of the state space iteration, is adopted to develop an efficient iterative QR triangularization and consecutive data prewhitening formulations. This formulation has advantages in both numerical accuracy and processor utilization efficiency. Moreover, it leads naturally to pipelined architectures such as systolic or wavefront arrays. For an n state and m measurement dynamic system, the SKF triarray design uses n(n+3)/2 processors and requires only 4n+m timesteps to complete one iteration of prewhitened Kalman filtering system. This means a speedup factor of approximately n²/4 when compared with a sequential processor. Also proposed for the colored noise case are data prewhitening triarrays which offer compatible speedup performance for the preprocessing stage. Based on a comparison of several competing alternatives, the proposed array processor may be considered a most efficient systolic or wavefront design for Kalman filtering     

On the optimality and stability of exponential twisting in MonteCarlo estimation

Estimation of the large deviations probability p_n =P(S_n⩾γn) via importance sampling is considered, where S_n is a sum of n i.i.d. random variables. It has been previously shown that within the nonparametric candidate family of all i.i.d. (or, more generally, Markov) distributions, the optimized exponentially twisted distribution is the unique asymptotically optimal sampling distribution. As n→∞, the sampling cost required to stabilize the normalized variance grows with strictly positive exponential rate for any suboptimal sampling distribution, while this sampling cost for the optimal exponentially twisted distribution is only O(n ^1/2). Here, it is established that the optimality is actually much stronger. As n→∞, this solution simultaneously stabilizes all error moments of both the sample mean and the sample variance estimators with sampling cost O(n^1/2 ). In addition, it is shown that the embedded parametric family of exponentially twisted distributions has a certain uniform asymptotic stability property. The technique is stable even if the optimal twisting parameter(s) cannot be precisely determined     

New ternary line codes based on trellis structure

The trellis coding technique is applied to line-coded baseband digital transmission systems. For R=n/n+1(n=1,2,3) coding rates, a new codeword assignment model is proposed to accomplish basic requirements for line coding in which each length n binary data sequence is encoded into a length n+1 ternary (+,0,-) line codeword chosen among the code alphabet with 2ⁿ⁺² elements. Assuming Viterbi decoding, the system error performance is improved by increasing the free Euclidean distance between coded sequences. A new algorithm is given for the calculation of the free distance between line-coded sequences so obtained. For R=1/2 and R=3/4 rates, the analytical error performance upper bounds are derived. The power spectral densities of the new line codes are also calculated and compared with those of known line codes     

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     

The capacity of the Kanerva associative memory

Asymptotic expressions for the capacity of an associative memory proposed by P. Kanerva (1984) are derived. Capacity is defined as the maximum number of random binary words that can be stored at random addresses so that the probability that a word is in error is arbitrarily small when it is retrieved by an n-bit address containing fewer than δn errors, δ⩽1/2. Sphere-packing arguments show that the capacity of any associative memory can grow exponentially in n at a rate of at most 1-h₂(δ), where h₂(δ) is the binary entropy function in bits. It turns out that the Kanerva associative memory achieves this upper bound when its parameters are optimally set. Thus, the capacity of the Kanerva associative memory has an exponential growth rate equal to the rate of the best information-theoretic codes, that is 1-h ₂(δ). However, the Kanerva memory achieves its exponential growth in capacity at the expense of an exponential growth in hardware     

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     

A convolutional single-parity-check concatenated coding scheme forhigh-data-rate applications

The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n,n-1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n=12 and the set of short constraint length K=3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K=7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K=3, rate 1/2 as well as for the punctured K=3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K=7, rate 1/2 inner convolutional codes is given     

Robustness in neural computation: random graphs and sparsity

An attempt is made to mathematically codify the belief that fully interconnected neural networks continue to function efficiently in the presence of component damage. Component damage is introduced in a fully interconnected neural network model of n neurons by randomly deleting the links between neurons. An analysis of the outer-product algorithm for this random graph model of sparse interconnectivity yields the following result: If the probability of losing any given link between two neurons is 1- , then the outer-product algorithm can store on the order of pn/log pn² stable memories correcting a linear number of random errors. In particular, the average degree of the interconnectivity graph dictates the memory storage capability, and functional storage of memories as stable states is feasible abruptly when the average number of neural interconnections retained by a neuron exceeds the order of log n links (of a total of n possible links) with other neurons