We describe an approach to parallel computation using particle propagation and collisions in a one-dimensional cellular automaton using a Particle model-a Particle Machine (PM). Such a machine has the parallelism, structural regularity, and local connectivity of systolic arrays, but is general and programmable. It contains no explicit multipliers, adders, or other fixed arithmetic operations; these are implemented using fine-grain interactions of logical particles which are injected into the medium of the cellular automaton, and which represent both data and processors. We give parallel, linear-time implementations of addition, subtraction, multiplication and division.

Given a discrete-time, linear, shift-invariant channel with finite impulse response, the problem of designing finite-length input signals with bounded amplitude (l/sub /spl infin// norm) such that the corresponding output signals are maximally separated in amplitude (l/sub /spl infin// sense) is considered. In general, this is a nonconvex optimization problem, and appears to be computationally difficult. An optimization algorithm that seems to perform well is described. Optimized signal sets and associated minimum distances (minimum l/sub /spl infin// separation between two distinct channel outputs) are presented for some example impulse responses. A conjectured upper bound on the minimum distance is given that is easily computed given the impulse response of the channel, the number of inputs, and the input length. This upper bound is shown to be valid for a limited class of impulse response functions.>

In personal communications applications, users communicate via wireless with a wireline network. The wireline network tracks the current location of the user, and can therefore route messages to a user regardless of the user's location. In addition to its impact on signaling within the wireline network, mobility tracking requires the expenditure of wireless resources as well, including the power consumption of the portable units carried by the users and the radio bandwidth used for registration and paging. Ideally, the mobility tracking scheme used for each user should depend on the user's call and mobility pattern, so the standard approach, in which all cells in a registration area are paged when a call arrives, may be wasteful of wireless resources. In order to conserve these resources, the network must have the capability to page selectively within a registration area, and the user must announce his or her location more frequently. We propose and analyze a simple model that captures this additional flexibility. Dynamic programming is used to determine an optimal announcing strategy for each user. Numerical results for a simple one-dimensional mobility model show that the optimal scheme may provide significant savings when compared to the standard approach even when the latter is optimized by suitably choosing the registration area size on a per-user basis. Ongoing research includes computing numerical results for more complicated mobility models and determining how existing system designs might be modified to incorporate our approach.

In personal communications applications, users communicate via wireless with a wireline network. The wireline network tracks the current location of the user, and can therefore route messages to a user regardless of the user's location. In addition to its impact on signaling within the wireline network, mobility tracking requires the expenditure of wireless resources as well, including the power consumption of the portable units carried by the users and the radio bandwidth used for registration and paging. Ideally, the mobility tracking scheme used for each user should depend on the user's call and mobility pattern, so that the current registration area approach (which ignores such information) may be wasteful of wireless resources under certain circumstances. In the paper, the authors provide a model and an optimization algorithm based on dynamic programming for choosing the mobility tracking scheme on a per-user basis. While illustrative results are provided for a simple one-dimensional mobility model, the approach is shown to be applicable to a very general class of problems.>

This paper considers the question of whether a mesh-connected machine is always better than a multi-pipelined machine for iterative 2-d mesh computations. Optimal throughput is determined as a function of a unified measure of resources (cost). The resulting performance curves for the two architectures show that there is a cost below which the pipelined architecture is an order of magnitude faster than the mesh, and above which this relationship is reversed. This methodology of comparing architectures using throughput-versus-cost modeling may prove useful in other contexts.

Abstract We present an on‐line distributed reconfiguration algorithm for finding a new maximum matching incrementally after some nodes have failed. Our algorithm is deadlock‐free and, withkfailures, maintains at leastM–kmatching pairs during the reconfiguration process, whereMis the size of the original maximum matching. The algorithm tolerates failures that occur during reconfiguration. The worst‐case reconfiguration time isO(kmin(|A|, |B|)) afterkfailures, whereAandBare the node sets, but simulations show that the average‐case reconfiguration time is much better. The algorithm is also simple enough to be implemented in hardware. ©1993 by John Wiley & Sons, Inc.

The authors study fault-tolerant redundant structures for maintaining reliable arrays. In particular, they assume that the desired array (application graph) is embedded in a certain class of regular, bounded-degree graphs called dynamic graphs. The degree of reconfigurability (DR) and DR with distance (DR/sup d/) of a redundant graph are defined. When DR and DR/sup d/ are independent of the size of the application graph, the graph is finitely reconfigurable (FR) and locally reconfigurable (LR), respectively. It is shown that DR provides a natural lower bound on the time complexity of any distributed reconfiguration algorithm and that there is no difference between being FR and LR on dynamic graphs. It is also shown that if both local reconfigurability and a fixed level of reliability are to be maintained, a dynamic graph must be of a dimension at least one greater than the application graph. Thus, for example, a one-dimensional systolic array cannot be embedded in a one-dimensional dynamic graph without sacrificing either reliability or locality of reconfiguration.>

ITRED (input-driven time-redundancy error detection), a methodology based on dependency graphs for doing concurrent run-time error detection in systolic arrays and wavefront processors, is described. It combines the projection method of deriving systolic arrays from dependency graphs with the idea of input-triggered testing. Tests are triggered by inserting special symbols in the input, and so the approach gives the user flexibility in trading off throughput for error coverage. Correctness of timing is proved at the dependency graph level. The method requires no extra processing elements and little extra hardware. The general approach is presented, and corresponding constraints on the modified dependency graphs that guarantee correctness are derived.>

Full-duplex data communication over a multi-input/multi-output linear time-invariant channel is considered. The minimum mean square error (MMSE) linear equalizer is derived in the presence of both near- and far-end crosstalk and independent additive noise. The MMSE equalizer is completely specified in terms of the channel and crosstalk transfer functions by using a generalization of previous work due to Salz (1985). Conditions are given under which the equalizer can completely eliminate both near- and far-end crosstalk and intersymbol interference. The MMSE transmitter filter, subject to a transmitted power constraint, is specified when the channel and crosstalk transfer functions are bandlimited to the Nyquist frequency. Also considered is the design of MMSE transmitter and receiver filters when the data signals are arbitrary wide-sense stationary continuous or discrete-time signals, corresponding to the situation where the crosstalk is not phase-synchronous with the desired signal.>

The problem of maximizing the output energy of a linear time-invariant channel, given that the input signal is time and amplitude limited, is considered. It is shown that a necessary condition for an input mu to be optimal, assuming a unity amplitude constraint is that it satisfy the fixed-point equation=sgn (F( mu )), where the functional F is the convolution of mu with the autocorrelation function of the channel impulse response. It is also shown that all solutions to this equation for which mod mu mod =1 almost everywhere correspond to local maxima of the output energy. Iteratively recomputing mu from the fixed-point equation leads to an algorithm for finding local optima. Numerical results are given for the cases where the transfer function is ideal low-pass and has two poles. These results support the conjecture that in the ideal low-pass case the optimal input signal is a single square pulse. A generalization of the preceding fixed-point condition is also derived for the problem of maximally separating N outputs of a discrete-time, linear, time-invariant channel.>

Achieving efficient and reliable synchronization is a critical problem in building long systolic arrays. This problem is addressed in the context of synchronous systems by introducing probabilistic models for two alternative clock distribution schemes: tree and straight-line clocking. Analytic bounds are presented for the probability of failure, and an examination is made of the tradeoffs between reliability and throughput in both schemes. The basic conclusion is that as the one-dimensional systolic array gets very long, tree clocking becomes preferable to straight-line clocking.>

Fault-tolerant redundant structures for maintaining reliable arrays are studied. It is assumed that the desired array (application graph) is embedded in a certain class of regular, bounded-degree graphs called dynamic graphs. The authors define the degree of reconfigurability (DR), and DR with distance DR/sup d/ of a redundant graph. When DR (respectively DR/sup d/) is independent of the size of the application graph, it is said that the graph is finitely reconfigurable, FR (resp. locally reconfigurable, LR). It is shown that DR provides a natural lower bound on the time complexity of any distributed reconfiguration algorithm, and that there is no difference between being FR and LR on dynamic graphs. It is then shown that if one wishes to maintain both local reconfigurability and a fixed level of reliability, a dynamic graph must be of dimension at least one greater than the application graph.>

Given a linear, time-invariant, discrete-time channel, the problem of constructing N input signals of finite length K that maximize minimum l/sub 2/ distance between pairs of outputs is considered. Two constraints on the input signals are considered: a power constraint on each of the N inputs (hard constraint) and an average power constraint over the entire set of inputs (soft constraint). The hard constraint, problem is equivalent to packing N points in an ellipsoid in min(K,N-1) dimensions to maximize the minimum Euclidean distance between pairs of points. Gradient-based numerical algorithms and a constructive technique based on dense lattices are used to find locally optimal solutions to the preceding signal design problems. Two numerical examples are shown for which the average spectrum of an optimized signal set resembles the water pouring spectrum that achieves Shannon capacity, assuming additive white Gaussian noise.>

The authors describe a test method for lattice-gas automata of the type introduced by U. Frisch et al. (1986). The test method consists of inserting test patterns into the initial state of the automaton and using a graphics display to detect errors. The test patterns are carefully constructed limit cycles that are disrupted by errors occurring at any level of the simulator system. The patterns can be run independently to test the system for debugging purposes, or they can be run as sub-simulations embedded in a larger lattice-gas simulation to detect faults at runtime. The authors describe the use of this method on a prototype parallel machine for lattice-gas simulations, and discuss the range of systems that can make use of this type of test method. The test patterns detect all significant one-bit errors. Included are experimental results indicating that multiple bit errors are unlikely to escape detection.>

The results of designing, training, and testing a neural network for the voiced/unvoiced (V/UV) speech classification problem are described. A feedforward multilayer backpropagation network was used with six input, ten internal, and two output nodes-for a binary decision. The six features are common and easily computed. Training was done with 72 frames from two speakers. Testing was done with 479 frames from four speakers and resulted in a total of two errors (0.4%). Thus, a small neural network performs well on the V/UV problem.>

A simple one-pass compiler that translates an intermediate filter language (IFL) into filter code is described. The main motivation is to provide an easy way to experiment with filters for digital sound synthesis. Any realizable, linear, constant-coefficient digital filter can be represented, using two primitive commands. The present version takes less than 250 lines of Pascal and produces Pascal. This compiler is completely portable, requires small computer resources, uses text input that can be generated by other programs, and is easy to modify. As an example of an application, an elaboration of the plucked-string filter is described that produces beat tones in a way similar to FM synthesis.>

Two natural operations on the set of convex polygons are shown to form a closed semiring; the two operations are vector summation and convex hull of the union. Various properties of these operations are investigated. Kleene’s algorithm applied to this closed semiring solves the problem of determining whether a directed graph with two-dimensional labels has a zero-sum cycle or not. This algorithm is shown to run in polynomial time in the special cases of graphs with one-dimensional labels, BTTSP (Backedged Two-Terminal Series-Parallel) graphs, and graphs with bounded labels. The undirected zero-sum cycle problem and the zero-sum simple cycle problem are also investigated.

A statistical model is considered for clock skew in which the propagation delays on every source-to-processor path are sums of independent contributions, and are identically distributed. Upper bounds are derived for expected skew, and its variance, in tree distribution systems with N synchronously clocked processing elements. The results are applied to two special cases of clock distribution. In the first, the metric-free model, the total delay in each buffer stage is Gaussian with a variance independent of stage number. In this case, the upper bound on skew grows as Theta (log N). The second, metric, model, is meant to reflect VLSI constraints. Here, the clock delay in a stage is Gaussian with a variance proportional to wire length, and the distribution tree is an H-tree embedded in the plane. In this case, the upper bound on expected skew is Theta (N/sup 1/4/ (log N)/sup 1/2/).>

Transceiver designs for multiple coupled channels typically treat the crosstalk between adjacent twisted pairs as random noise uncorrelated with the transmitted signal. The authors propose a transmitter/receiver pair that compensates for crosstalk by treating an entire bundle of twisted pairs as a single multi-input/multi-output channel with a (slowly varying) matrix transfer function. The proposed transceiver uses multichannel adaptive FIR filters to cancel near- and far-end crosstalk, and to pre- and postprocess the input/output of the channel. Linear pre- and postprocessors that minimize mean squared error between the received and transmitted signal in the presence of both near- and far-end crosstalk are derived. The performance of an adaptive near-end crosstalk canceller using the stochastic gradient (least-mean-square) transversal algorithm is illustrated by numerical simulation. Plots of mean squared error versus time and eye diagrams are presented, assuming a standard transmission line model for the channel. A signal design algorithm that maps a vector input bit stream to a stream of channel symbol vectors is also presented and illustrated explicitly for s simple model of two coupled channels.>

The problem of finding the maximum achievable data rate over a linear time-invariant channel is considered under constraints different from those typically assumed. The limiting factor is taken to be the accuracy with which the receiver can measure the channel output. More precisely, the following problem is considered. Given a channel with known impulse response h(t), a transmitter with an output amplitude constraint, and a receiver that can distinguish between two signals only if they are separated in amplitude at some time t/sub 0/ by at least some small positive constant d, what is the maximum number of messages, N/sub max/, that can be transmitted in a given time interval (0,T)? Lower bounds on N/sub max/ can be easily computed by constructing a particular set of inputs to the channel. The main result is an upper bound on N/sub max/ for arbitrary h(t). The upper bound depends on the spread of h(t), which is the maximum range of values the channel output may take at some time t/sub 0/>0 given that the output takes on a particular value alpha at time t=0. Numerical results are shown for different impulse responses, including two simulated telephone subscriber loop impulse responses.>

The following problem is discussed: given a channel with known impulse response h(t), a transmitter with an output amplitude constraint, and a receiver that can distinguish between two signals only if they are separated in amplitude at some time t/sub 0/ by at least some small positive constant d, then what is the maximum number of messages, N, that can be transmitted in a given time interval (0, T)? Upper bounds for arbitrary h(t) are computed by solving linear programs with bounded variables and one equality constraint. Solutions to linear programs in this class can be obtained very fast using, for example, a linear-time algorithm due to C. Witzgall (1980). Numerical results are shown for different impulse responses, including a simulated telephone subscriber loop impulse response. Assuming that the receiver resolution d is small, the upper bound is typically two to three times the lower bound for the cases examined.>

The authors consider transmission of data over multiple coupled channels, such as bundles of twisted-pair cables in the local subscriber loop, and between central offices in the public switched telephone network. Transceiver designs for such channels typically treat the crosstalk between adjacent cables as random noise uncorrelated with the transmitted signal. A transmitter/receiver pair is proposed which compensated for crosstalk by treating an entire bundle of cables as a single multi-input/multioutput channel with a (slowly varying) matrix transfer function. One attribute of the proposed transceiver is the use of a multichannel adaptive FIR (finite-impulse response) filter to cancel near-end crosstalk. Results of numerical simulations, including plots of mean squared error vs. time, and eye diagrams, are presented assuming a standard transmission line mode for the channel. These results indicate that data rates over coupled channels can be significantly increased by exploiting the multidimensional character of the channel.>

Abstract This paper describes an efficient way to test the VAP‐free (Vertex Accumulation Point free) planarity of one‐ and two‐dimensional dynamic graphs. Dynamic graphs are infinite graphs consisting of an infinite number of basic cells connected regularly according to labels in a finite graph called a static graph. Dynamic graphs arize in the design of highly regular VLSI circuits, such as systolic arrays and digital signal processing chips. We show that VAP‐free planarity testing of dynamic graphs can be done efficiently by making use of their regularity. First, we will establish necessary conditions for VAP‐free planarity of dynamic graphs. Then we show the existence of a small finite graph which is planar if and only if the original dynamic graph is VAP‐free planar. From this it follows that VAP‐free planarity testing of one‐ and two‐dimensional dynamic graphs is asymptomically no more difficult than planarity testing of finite graphs, and thus can be done in linear time.

It is shown that some kind of meaningful computation can be embedded in very simple, microscopically homogeneous, one-dimensional automata, and in particular filter automata with a parity next-state rule. A systematic procedure is given for generating moving, periodic structures (particles). These particles exhibit soliton-like properties; that is, they often pass through one another with phase shifts. Ways to encode information in the phase of these particles are discussed. The search for useful logical operations is reduced to a search for paths in certain graphs. As a demonstration of principle, the details of implementing a carry-ripple adder are given.>

Large errors may be produced by filtering finite-length records extracted from a discrete signal instead of filtering the signal itself. The knowledge that the signal is bandlimited in some particular way may be used to reduce these errors, particularly around the ends of the record. An optimal finite-record filtering technique that uses this information is presented here that performs the filtering operation by a single matrix multiplication. An improvement to the basic algorithm is also presented that permits the bandwidth of the signal to be estimated from knowledge of average-power characteristics of the original signal.

Article Free Access Share on Testing for cycles in infinite graphs with periodic structure Authors: K. Iwano Dept. of Computer Science, Rinceton University, Plrinceton, NJ Dept. of Computer Science, Rinceton University, Plrinceton, NJView Profile , K. Steiglitz Dept. of Computer Science, Rinceton University, Plrinceton, NJ Dept. of Computer Science, Rinceton University, Plrinceton, NJView Profile Authors Info & Claims STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingJanuary 1987 Pages 46–55https://doi.org/10.1145/28395.28401Published:01 January 1987Publication History 23citation426DownloadsMetricsTotal Citations23Total Downloads426Last 12 Months37Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Two sets of conditions are derived that make one- dimensional bilateral arrays of combinational cells testable for single faulty cells. The test sequences are preset and, in the worst case, grow quadratically with the size of the array. Conditions for testability in linear time are also derived. The basic cell can operate at the bit or at the word level. An implementation of FIR filters using (systolic) one-dimensional bilateral arrays of cells, which can be considered combinational at the word level, is presented as an example. A straightforward generalization for the two- dimensional case is made; a systolic array used for matrix multiplication is presented as an example for this case.

We study the problem of optimizing the pulldown diffusion widths in the one-bit full adder when it is embedded in a regular array, using the simplest possible array multiplier with a delay-time criterion as an example. A local optimization algorithm is used, which varies two parameters at a time along the critical path until a local optimum is found. The analysis routines include the Berkeley tools [10] and the Princeton procedural layout language ALLENDE [11- 12]. Two ways are suggested for optimizing large arrays in practical amounts of time. First, the full-adder cell optimized within a minimum-size array can be used in the large array. This is a good choice because the interior cells of the small prototype have the same boundary conditions as those in the larger array. A second, even faster, method is to approximate the delay time from some simple assumptions about the critical path. Numerical results show that both these methods are effective. We give typical local optima obtained when delay time is minimized, together with power-time tradeoff curves, for the 3×3 and 4×4 array multipliers, using 4µ (λ=2µ) nMOS fabrication parameters, and a 5- parameter random-logic full-adder cell.

We describe the design and testing of an 18- processor chip that implements the update rule for a fixed one-dimensional binary-valued cellular automaton. The VLSI design was done in the high level, procedural language ALLENDE [5,6]. The processors are bit-serial, completely pipelined, and cascaded, so that one chip performs 18 updates per major clock cycle. In principle, any number of chips can be cascaded, with a corresponding linear speedup. Sixteen chips were fabricated in 4 µ nMOS using the MOSIS facility, of which 10 were fully functional. When tested, 9 of the fully functional chips operated at maximum clock rates between 6 and 8 Mhz. This implies a maximum speed of about 108bit updates per second per chip, and opens the way for experimentation that is too time-consuming using general purpose devices.

We describe the design, layout, and simulation of a recursively defined VLSI chip, using a constraint-based, procedural layout language. We use as an example the problem of counting the number of 1's in a set of (B - 1) input bits, where B is a power of 2. A regular, recursive structure, called a unary-to-binary converter (UBC(B)), tally circuit, or parallel counter, is described, based on the original design of Swartzlander. Area from the CIF plots and worst-case delay from simulations are given for 5 instantiations of the circuit, for B = 4, 8, 16, 32, and 64. The results verify the expected asymptotic behavior of the implementation as a function of B. The high-level, procedural approach leads to a succinct and parameterized description of the circuit. Verification and simulation of different versions of the circuit is much easier than with the conventional, hand-layout approach.

This paper investigates the optimal tradeoff between the degree of intermediate latching and cost in special-purpose VLSI chips, using the measure AP, where A is the chip area and P is the period (the reciprocal of throughput). The results show that significant reductions in AP-product (reciprocal of throughput per unit area) can be achieved by-intermediate latching in many typical signal processing applications, for a wide range of circuit parameters.

We treat the problem of designing lowpass FIR digital filters that are very flat at zero frequency, smooth in the passband, and minimax in the stopband. The cases of lowpass and lowpass-differentiator are studied in particular. An effective design algorithm is described based on linear programming with a single equality constraint on the first derivative at the origin plus a concavity constraint in the passband. An empirical design equation for estimating model order in the odd-length lowpass-differentiator case is given.

Parallel counters (unary-to-binary converters) are the principal component of a Dadda multiplier.We specify a design first for a pipelined parallel counter, and then for a complete multiplier.As a result of its structural regularity, the layout is suitable for use in a VLSI implementation.We analyze the complexity of the resulting design using a VLSI model of computation, showing that it is optimal with respect to both its period and latency.In this sense the design compares favorably with other recent VLSI multiplier designs.

We consider the complexity of finding optimal fixed- or variable-length unambiguous address codes for the nodes of a packet radio network. For fixed-length codes this problem is proved to be NP-complete, and its complexity for variable-length codes is still unknown. Some suboptimal heuristic algorithms are proposed.

Over the past decade a large class of problems, called NP-complete[1], have been shown to be equivalent in the sense that if a fast algorithm can be found for one, fast algorithms can be found for all. At the same time, despite much effort, no fast algorithms have been found for any, and these problems are widely regarded as intractable. This class includes such notoriously difficult problems as the traveling salesman problem, graph coloring, and satisfiability of Boolean expressions. This paper describes some problems in digital signal processing which are NP-complete. These include: (1) Minimize the number of registers required to implement a signal flow graph; (2) Minimize the time to perform the additions (multiplications) of a signal flow graph using P adders (multipliers); (3) Minimize the computational cost for multiplication by a fixed matrix. Large-scale instances of such problems may become important with the use of VLSI technology to implement signal processing.

A central problem in the production of music by computer is how to generate sounds with similar but different timbres; that is, how to synthesize a "family" of instruments that are perceived as distinguishable but similar in timbre. This paper describes a method for synthesizing a family of string-like instruments that proceeds as follows: First, a few actual violin notes are analyzed using linear prediction. Second, a bilinear transformation is applied to the linear prediction model on synthesis, using a recently described algorithm. This yields a computationally efficient way to generate a virtual string orchestra, with violin-, viola-, violoncello-, and bass-like timbres. A realization of a 4.7-minute piece composed by P. Lansky will be played.

Deadlocks are very serious system failures and have been observed in existing packet switching networks (PSN’s). Several problems related to the design of deadlock-free PSN’s are investigated here. Polynomial-time algorithms are given for some of these problems, but most of them are shown to be NP-complete or NP-hard, and therefore polynomial-time algorithms are not likely to be found.

The star-star concentrator problem (SSCP) arises in computer network design. The complexity of this problem is studied, and polynomially solvable and (strongly) NP-complete cases are presented.

We study the problem of diagonalizing the DFT by finding eigenvectors through the use of commuting operators. An explicit form for the polar representation of the DFT is presented and powers of the DFT are studied. Possible applications to signal multiplexing and transform coding are suggested.

The problem of the minimax design of FIR digital filters with prescribed phase characteristics and unit magnitude is a nonlinear optimization problem. In this paper it is approximated by a linear programming problem which is optimal to first order. That is, if δ0and ε0are optimal deviations of magnitude and phase characteristics, then the actual deviations obtained from the linear program solution satisfy\delta \leq \delta_{0} + εmin{0}\max{2}andεleq ε_{0}(1+\delta_{0})/(1-\delta_{0}). Design results are given for full-band M-term chirp filters, which (like linear phase filters) can be implemented with (M+1)/2 multiplications per point.

A linear programming algorithm is described for designing FIR digital filters with the constraint that the magnitude response be concave over prescribed frequency bands. This is applied to odd-length Hilbert Transformers, and computational results are given. The concavity constraint avoids the ripple of the minimax design, and retains the advantage of maintaining half-band symmetry in the case of symmetric transition bands, so that alternate impulse response samples are zero. If N is the length of the impulse response, ΔF the (symmetric) transition width, and δ the maximum error, it is found thatN\DeltaF/\log_{10}^{/delta} \approx -1.1, as opposed to the value of -0.61 in the minimax case (with ripple) reported by Rabiner and Schafer. Thus, the price paid for the absence of ripples is about twice the number of multiplications per sample.

A quad tree for representing a picture is a tree in which successively deeper levels represent successively finer subdivisions of picture area. An algorithm is given for superposing N quad trees in time proportional to the total number of nodes in the trees. Warnock-type algorithms are then presented for building the quad tree for the picture of the boundary of a polygon, and for coloring the interior of such a polygon. These algorithms take O(v + p + q) time, where v is the number of polygon vertices, p is the polygon perimeter, and q is a resolution parameter. When the resolution q is fixed, these algorithms are asymptotically optimal.

A local search algorithm for the design of small-diameter networks is presented for both directed and undirected regular graphs. In all cases the resulting graphs are at least as good as any previously known, in the sense that they have at least as small a diameter and average shortest distance for a given number of nodes and degrees.

We describe the implementation of a practical system for pole-zero analysis-synthesis which produces synthesized speech that sounds qualitatively different from linear prediction at points of mouth closure. We also describe an apparently new synthesis method, windowed synthesis, which circumvents the problem of choosing initial conditions in synthesis using a filter model, and is also applicable to cepstral vocoding.

A method is described for automating the counting of asbestos fibers in air samples by computer processing of digitized pictures. Preliminary results show the method is feasible.

It is shown that, unless $P = NP$, local search algorithms for the traveling salesman problem having polynomial time complexity per iteration will generate solutions arbitrarily far from the optimal.

An algorithm for making the voiced/unvoiced decision in speech analysis is presented. Three features (LPC normalized minimum error, ratio of energy content at high to low frequencies, and input RMS) define a three-dimensional space in which the decision making process is viewed as a pattern classification problem. This is formulated as a linear program which runs on a training set to find a hyperplane dividing the V/UV regions if they are separable, or minimizing the distance by which misclassification occurs if they are not. A procedure is given for selecting the features and constructing the training set.

It is shown that, unless P=NP, local search algorithms for the Traveling Salesman Problem having polynomial time complexity per iteration will generate solutions arbitrarily far from the optimal. The Traveling Salesman Problem is also shown to be NP-Complete even if its instances are restricted to be realizable by a set of points on the Euclidean plane.

Improved exact and approximate algorithms for the n-job two-machine mean finishing time flow-shop problem, n/2JF/P, are presented While other researchers have used a variety of approximate methods to generate suboptimal solutions and branch-and-bound algorithms to generate exact solutmns to sequencing problems, thin work demonstrates the computatmnal effectiveness of couphng the two methods to generate solutmns with a guaranteed accuracy.The computational reqmrements of exact, approximate, and guaranteed accuracy algorithms are compared expemmentally on a set of test problems ranging in size from 10 to 50 jobs The approach is readily apphcable to other sequencing problems

We investigate the evaluation of an $(n - 1)$st degree polynomial at a sequence of n points. It is shown that such an evaluation reduces directly to a simple convolution if and only if the sequence of points is of the form $b, ba,ba^2 , \cdots ,ba^{n - 1} $ for complex numbers a and b (the so-called “chirp transform”). By more complex reductions we develop an $O(n\log n)$ evaluation algorithm for sequences of points of the form \[ b + c + d,\quad ba^2 + ca + d,\quad ba^4 + ca^2 + d, \cdots \] for complex numbers a, b, c and d. Finally we show that the evaluation of an $(n - 1)$st-degree polynomial and all its derivatives at a single point requires at most $O(n\log n)$ steps.

Branch-and-bound implicit enumeration algorithms for permutation problems (discrete optimization problems where the set of feasible solutions is the permutation group S n ) are characterized in terms of a sextuple ( B p S,E,D,L,U ), where (1) B p is the branching rule for permutation problems, (2) S is the next node selection rule, (3) E is the set of node elimination rules, (4) D is the node dominance function, (5) L is the node lower-bound cost function, and (6) U is an upper-bound solution cost. A general algorithm based on this characterization is presented and the dependence of the computational requirements on the choice of algorithm parameters, S, E, D, L, and U is investigated theoretically. The results verify some intuitive notions but disprove others.

This paper discusses the expression of algorithms by flowcharts, and in particular by flowcharts without explicit go-to's (D-charts).For this purpose we introduce a machine independent definition of algorithm which is broader than usual.Our conclusion is that Dcharts are in one technical sense more restrictive than general flowcharts, but not if one allows the introduction of additional variables which represent a history of control flow.

A random search technique for function minimization is proposed that incorporates the step-size and direction adaptivity of Hooke and Jeeves' [1] pattern search. Experimental results for a variety of functions indicate that the random pattern search is more effective than the corresponding deterministic method for a class of problems with hard constraints.

This paper presents a general approach to the derivation of series expansions of second-order wide-sense stationary mean-square continuous random process valid over an infinite-time interval. The coefficients of the expansion are orthogonal and convergence is in the mean-square sense. The method of derivation is based on the integral representation of such processes. It covers both the periodic and the aperiodic cases. A constructive procedure is presented to obtain an explicit expansion for a given spectral distribution.

Various encoding schemes are examined from the point of view of minimizing the mean magnitude error of a signal caused by transmission through a binary symmetric channel. A necessary property is developed for optimal codes for any binary symmetric channel and any set of quantization levels. The class of optimal codes is found for the case where the probability of error is small but realistic. This class of codes includes the natural numbering and some unit distance codes, among which are the Gray codes.

The transmission of a nonbandlimited analog signal over a digital channel with a fixed bit-rate is considered. The trade-off between the mean-square error due to quantizing and the mean-square error due to the process of sampling and reconstructing the signal is investigated. Simple approximations to these errors, which are valid in most practical situations, are derived, and simple expressions are obtained from which the optimum sampling interval and number of bits per sample can be calculated. Results for first-, second-, and third-order Butterworth and fiat bandlimited spectra, together with the zero-order hold and the linear point connector, are included. The resulting mean-square error goes to zero with large channel bit-rates in a slower manner than the Shannon limit, which assumes a strictly bandlimited signal and perfect reconstruction.