A novel integration of a neural network and a mammographic database provides a promising means of amplifying the radiologist's power to screen mammograms. The principal novelty of this system is a neural network that produces both a classifier and a 2D relational map of the mammograms in a diagnostically proven database. We therefore refer to this as a neurodatabase system. Radiologists interacting with a neurodatabase system can achieve significant reductions in the number of benign biopsies and the number of missed cancers. The specificity of the computer-aided radiologist can exceed those of both the unaided radiologist and the computer system alone.

We demonstrate the ability of our recently devised "visual neural network" to display clusters in a database of multidimensional vectors, and to partition this display into decision regions. The multidimensional vectors may be feature vectors from an initial database of images, signals, or other data. The decision regions may be the classes into which the user assigns these data. The decision regions define classes that may only partially overlap some of the clusters. Thus the visual neural network classifies each vector in the database and at the same time maps the vector into a point in a two-dimensional display. When points in the display correspond to perceptually similar items in the initial data. When presented with a "query" from the initial data, a user call search for items similar to the query by examining the raw data represented by points in the same class as the query or by examining nearby points. In this way a user can efficiently browse a database and be assured of accessing related items. Information gained from browsing the database can be used to evaluate the network's classification decision. We show in an application to medical radiology that a visual neural network can learn a good compromise between perceptual grouping and classification.

A new neural classifier allows visualization of the training set and decision regions, providing benefits for both the designer and the user. We demonstrate the visualization capabilities of this visual neural classifier using synthetic data, and compare the visualization performance to Kohunen's self-organizing map. We show in applications to image segmentation and medical diagnosis that visualization enables a designer to refine the classifier to achieve low error rates and enhances a user's ability to make classifier-assisted decisions.

When a neural network makes a financial prediction, the user may benefit from knowing which previous time periods are illustrative of the current time period. The authors describe a high-performance neural network that in addition to predicting stock market direction, allows the user to visualize the relationship between current conditions and previous conditions that led to similar predictions. Visualization is accomplished by forming a gated multi-expert network using funnel-shaped multilayer dimensionality reduction networks. The neck of the funnel is a two-neuron layer that displays the training data and the decision boundaries in a two-dimensional space. This architecture facilitates a) interactive design of the decision functions and b) explanation of the relevance of past decisions from the training set to the current decision. They describe a stock market prediction system whose design incorporates a visual neural network for prediction, wavelet transforms and tapped delay lines for feature extraction, and a genetic algorithm for feature selection. This system shows that the visual neural network provides the low error rates (i.e., accurate predictions) of multi-expert networks along with the visual explanatory power of nonlinear dimensionality reduction.

A linear decision binary tree structure is proposed in constructing piecewise linear classifiers with the genetic algorithm (GA) being shaped and employed at each nonterminal node to search for a linear decision function optimal in the sense of maximum impurity reduction. The methodology works for both the two-class and multiclass cases. In comparison to several other well known methods, the proposed binary tree-genetic algorithm (BTGA) is demonstrated to produce a much lower cross validation misclassification rate. Finally, a modified BTGA is applied to the important pap smear cell classification. This results in a spectrum for the combination of the highest desirable sensitivity along with the lowest possible false alarm rate. The multiple choices offered by the spectrum for the sensitivity-false alarm rate combination will provide the flexibility needed for the pap smear slide classification.

We show that every piecewise linear classifier can be constructed as a three-layer network of linear decision functions. We define neural modeling as the replacement and subsequent training of each of these linear decision functions by a formal neuron with a differentiable activation function. We show that neural modeling of a piecewise linear classifier provides a means of combining the economy of design of piecewise linear classifiers with the good generalizing ability and low error rates of well designed neural classifiers. We show that globally optimized neural classifiers can be obtained from neural modeling of genetically designed piecewise linear classifiers. We describe applications of these techniques to an artificial data set and to a detector of lines and edges in a noisy aerial image.

Piecewise-linear mathematical structures form a convenient and important framework for implementing trainable and adaptive pattern classifiers. Neural networks and genetic algorithms offer additional approaches with important benefits for the design of such classifiers. In this paper we show how neural modeling and genetic selection can be applied to piecewise-linear structures to optimize both the topology and the parameter values of the network forming the classifier. Such a classifier will tend to have a low error rate and high robustness. We describe applications of these techniques to an adaptive detector of abnormal tissue in mammograms and a detector of straight lines and edges in noisy aerial images.

Window training, based on an extended form of stochastic approximation, offers a means of producing linear classifiers that minimize the probability of misclassification of statistically generated data. Associated with window training is a window criterion function. We show that minimizing the window criterion function yields a linear classifier that minimizes the probability of misclassification (i.e., the "error rate"). However window training may produce a local minimum that exceeds the global minimum error rate. We show that this defect does not occur in the error-correcting perceptron. The criterion minimized by that training procedure is "convex"; i.e., the perceptron criterion has only one local minimum. Consequently we recommend that window training be preceded by perceptron training, the perceptron training producing a decision surface which the window training process will move to a position that is likely to be globally optimum.>

Window training, based on an extended form of stochastic approximation, offers a means of producing linear classifiers that minimize the probability of misclassification of statistically generated data. However, window training may produce a local minimum that exceeds the global minimum error rate. To overcome this defect it is useful to precede window training by perceptron training. When a significantly large set of exemplars of the data is available at the beginning of the training process, the basic exchange algorithm offers a computationally convenient alternative to the window training algorithm to achieve a locally minimum error rate.

Describes a technique for reconstructing the skeletal structure of coronary arteries from a succession of frames of a single-view cineangiogram. The authors use local features in each frame to determine correspondences of arterial segments in successive frames. They define a similarity measure in 2D image space as the change in angular coordinates of corresponding pairs. They use a form of gradient descent to find those depth coordinates that minimize the average deviation of the 3D angular coordinates of all points on the skeleton from the coordinates produced by a 3D scaling transformation. In experiments with software models the reconstruction error was approximately two pixels when the initial guessed reconstruction was as large as 30 pixels.

A thinning method for binary images is proposed which converts digital binary images into line patterns. The proposed method suppresses shape distortion as well as false feature points, thereby producing more natural line patterns than existing methods. In addition, this method guarantees that the produced line patterns are one pixel in width everywhere. In this method, an input binary image is transformed into a graph in which 1-pixels correspond to nodes and neighboring nodes are connected by edges. Next, nodes unnecessary for preserving the topology of the input image and the edges connecting them are deleted symmetrically. Then, edges that do not contribute to the preservation of the topology of the input image are deleted. The advantages of this graph-based thinning method are confirmed by applying it to ideal line patterns and geographical maps.

The authors describe how to design color illumination to improve the discriminability of objects in color images. This procedure is useful in applications where the illumination can be controlled, such as inspection tasks. From the physics of color image formation, the optimal color illumination for discriminating materials is derived using a parametrically defined set of illuminants. The authors suggest how such an approach might be extended to sets of materials and more general classes of light sources. Experiments with painted color patches and live potato plantlets are used to illustrate the usefulness of actively controlling illumination color in machine vision.>

Presents a new algorithm for the estimation of optical flow from a monocular sequence of images using clustered trajectories in velocity-time. In the new algorithm, the objects in the scene may exhibit rotation and translation in all three dimensions. In addition, interframe displacement may be large-of the order of many pixels. It is assumed that there is a known upper bound on the magnitudes of the x and y components of interframe displacement. The authors conducted tests to compare the performance of the algorithm with that of two prior algorithms for optical flow estimation. They present the results of these tests. The results suggest that the algorithm is an improvement over prior algorithms in its ability to compute the optical flow field accurately under several commonly encountered scene conditions that have posed problems to earlier algorithms for optical flow estimation.>

Describes a method for extracting nonrigid moving objects. Every moving object may be approximated by a set of iso-intensity patches. The method finds the motions of these patches by integrating the locations and the intensities of temporal edges. Then, it finds the objects by finding clusters among the motions of the patches. The proposed method can extract many nonrigid objects on a complicated background. The performance of the proposed method was tested successfully on extracting pedestrians from a cinematic sequence viewing a street crossing.>

Describes a new algorithm for approximately reconstructing a 2D binary pattern from its two orthogonal 1D projections, under the constraint that the shape of the reconstructed binary pattern must represent a reasonable cross section of a coronary artery. In the hierarchical search process of this multiresolution algorithm, most of the branches are pruned to satisfy a shape constraint such as smoothness. Imposing adjacent-slice similarities on the reconstructions of a stack of consecutive transverse slices of the arterial lumen from two mutually orthogonal ('biplane') X-ray projections, and the constraint of smoothness, the 3D shape of the coronary artery can be estimated.>

Presents a new algorithm for interframe interpolation of cinematic sequences. The authors demonstrate its applicability to video data compression of pedestrian traffic and data compression for video conferencing. In both of these applications it is assumed that the background is nearly stationary and that there are no interobject occlusions. The interpolation algorithm makes use of estimates of optical flow to compensate for the motion of objects between two frames. We describe three major problems associated with motion compensated cinematic interpolation: interframe occlusion, interframe zooming and figure-ground ambiguity. Our algorithm suppresses artifacts caused by all three of these problems.>

An algorithm that reconstructs the cross sections of the lumens of coronary arteries from two mutually orthogonal X-ray projections is described. The algorithm accommodates the possibility of elliptical, crescent, or star shapes. It represents each biplane projection of a transverse slice of the arterial lumen as a binary-valued image. The single-coordinate moments of these two projection images are equal to those of the slice. Since the cross-coordinate moments of the slice are not available from the projections, an algorithm to estimate these moments based on assumptions of smoothness and connectivity is developed. Once all the missing moments are estimated, the image of the slice can be estimated by inverting these moments, using the uniqueness theorem governing the relation between an image and its moments. Preliminary tests of the algorithm on synthetic data, on hardware phantoms and on a segment of a barium-enhanced in vitro coronary artery are reported.

A flexible-mask algorithm that effectively provides correction for motion artifacts and gray-level variations in digital subtraction angiography (DSA) images is presented. The algorithm makes use of a flexible local registration of the mask with the live image to minimize the main distortions caused by the complex motion of the heart, namely spatial translation, rotation, and nonisotropic scaling. It also reduces the gray-level variations caused by the diffusion of the contrast medium into parts of the heart other than the arteries. It is concluded from experiments on X-ray coronary angiograms that when the background near the arteries is rugged or provides significant interference, flexible mask subtraction offers important improvements in quantitative estimates of the sizes of the arteries. In all the X-ray images used in the experiments, the precision of the method was at the 0.1-pixel level. The computation is extensive. However, some improvements can be achieved by doing the subtraction only at the coronary arteries and the immediate neighborhood instead of the whole image. The algorithm lends itself to implementation by parallel-structured hardware.

The production of robust classifiers by combining supervised training with unsupervised training is discussed. A supervised training phase exploits statistically scene invariant labeled data to produce an initial classifier. This is followed by an unsupervised training phase that exploits clustering properties of unlabeled data. This two-phase process is termed mixed adaptation. A probabilistic model supporting this technique is presented along with examples illustrating mixed adaptation. These examples include the detection of unspecified dotted curves in dotted noise and the detection and classification of vehicles in cinematic sequences of infrared imagery.>

The formation of temporal geodesics (i.e., fast routes) in a velocity field seems to offer a means of detecting curves by parallel hardware in a wide range of images with little prior design information. This hypothesis was tested by devising and constructing a dotted-curve detector based on it, and applying the detector to several synthetic dotted images covering a wide range of dotted curves and dotted partially coherent noise. The results are encouraging. The dotted-curve detector searches for fast routes in a velocity field determined locally by the approximate collinearity or cocircularity of clusters of dots, and globally by the tortuousness of the route and the uniformity of the spacing of dots along the route. The routes are found by a parallel adaptive classification of the dots into curve dots and noise dots, followed by a parallel merging and splitting of graphs spanning temporal close dots or subgraphs at successively higher levels of abstraction.>

An automated method is presented for the design of linear tree classifiers, i.e. tree classifiers in which a decision based on a linear sum of features is carried out at each node. The method exploits the discriminability of Tomek links joining opposed pairs of data points in multidimensional feature space to produce a hierarchically structured piecewise linear decision function. The corresponding decision surface is optimized by a gradient descent that maximizes the number of Tomek links cut by each linear segment of the decision surface, followed by training each node's linear decision segment on the data associated with that node. Experiments on real data obtained from character images suggest that the accuracy of the tree classifier designed by this scheme is comparable to those of the k-NN classifiers and the tree classifier of J.K. Mui and K.S. Fu (1980), while providing much greater decision speeds, and that the tradeoff between the speed and the accuracy in pattern classification can be controlled by bounding the number of features to be used at each node of the tree.>

A method for designing multiple-class piecewise-linear classifiers is described. It involves the cutting or arcs joining pairs of opposed points in d-dimensional space. Such arcs are referred to as links. It is shown how to nearly minimize the number of hyperplanes required to cut all of these links, thereby yielding a near-Bayes-optimal decision surface regardless of the number of classes. The underlying theory is described. This method does not require parameters to be specified by users. Experiments on multiple-class data obtained from ship images show that classifiers designed by this method yield approximately the same error rate as the best k-nearest-neighbor rule, while possessing greater computational efficiency of classification.>

We review recent research on methods for selecting features for multidimensional pattern classification. These methods include nonmonotonicity-tolerant branch-and-bound search and beam search. We describe the potential benefits of Monte Carlo approaches such as simulated annealing and genetic algorithms. We compare these methods to facilitate the planning of future research on feature selection.

The B-spline functions are used to develop recursive algorithms for the efficient implementation of two-dimensional linear digital image filters. These filters may be spatially varying. The B-splines are used in a representation of the desired point spread function. We show that this leads to recursive algorithms and hardware implementations which are more efficient than either direct spatial domain filter realizations or FFT implementations. The Z-transform is used to develop a discrete version of Duhamel's theorem. A computer architecture for B-spline image filters is proposed and a complexity analysis and comparison to other approaches is provided.

A computer-based technique for automatic selection of features for the classification of non-Gaussian data is presented. The selection technique exploits interactive cluster finding and a modified branch and bound optimization of piecewise linear classifiers. The technique first finds an efficient set of pairs of oppositely classified clusters to represent the data. Then a zero-one implicit enumeration implements a branch and bound search for a good subset of features. A test of the feature selection technique on multidimensional synthetic and real data yielded close-to-optimum, and in many cases optimum, subsets of features. The real data consisted of a) 1284 12-dimensional feature vectors representing normal and abnormal breast tissue, extracted from X-ray mammograms, and b) 1060 30-dimensional feature vectors representing tanks and clutter in infrared video images.

An optimal method for finding a minimum feature subset based on box classifiers is described. Feature selection is represented as a problem of zero-one integer programming. An implicit enumeration method is developed in order to solve this problem. Numerical examples are presented to illustrate the effectiveness of the approach.

A ``piecewise heuristic'' follower of the boundaries of difficult-to-notice nonoverlapping blobs in digitized images is described. The technique was tested on 324 X-ray images of candidate lung nodules from eight radiographs with good results. This technique is several times faster than earlier detectors of the boundaries of lung nodules, while maintaining good fidelity of the detected boundaries.

A computer procedure for detecting and finding the boundaries of blobs in noisy infrared images is described. Our evaluation of this procedure on a data base of 81 targets, 34 for design and 47 for test, resulted in only two false negatives (missed targets) and no false detections. Our procedure consists of an intensity normalizer, a dc notch filter, an edge detector, a spoke filter, a gradient-guided segmenter, an extractor of the standard deviation of the gray level in each blob, an extractor of the fraction of intense edge elements along the boundary of each blob, and a three-nearest-neighbor classifier. Among these processes, the spoke filter and the gradient-guided segmenter are new. Both of them contribute strongly to the effectiveness of our procedure. The spoke filter is sensitive to a wide variety of shapes of blobs within a specified range of sizes. The gradient-guided segmenter exploits the noise immunity of the direction of the digital gradient to find a best threshold for segmenting each detected blob.

We describe a versatile technique for designing computer algorithms for separating multiple-dimensional data (feature vectors) into two classes. We refer to these algorithms as classifiers. Our classifiers achieve nearly Bayes-minimum error rates while requiring relatively small amounts of memory. Our design procedure finds a set of close-opposed pairs of clusters of data. From these pairs the procedure generates a piecewise-linear approximation of the Bayes-optimum decision surface. A window training procedure on each linear segment of the approximation provides great flexibility of design over a wide range of class densities. The data consumed in the training of each segment are restricted to just those data lying near that segment, which makes possible the construction of efficient data bases for the training process. Interactive simplification of the classifier is facilitated by an adjacency matrix and an incidence matrix. The adjacency matrix describes the interrelationships of the linear segments {£i}. The incidence matrix describes the interrelationships among the polyhedrons formed by the hyperplanes containing {£i}. We exploit switching theory to minimize the decision logic.

The usual Hough procedure for detecting curves embedded in digitized images involves a transformation from image space I to parameter space P. In this note we suggest that insight into this transformation may be enhanced by mapping P back into I.

An overview of present computer techniques of partitioning continuous-tone images into meaningful segments and of characterizing these segments by sets of "features" is presented. Segmentation often consists of two methods:boundary detection and texture analysis. Both of these are discussed. The design of the segmenter and feature extractor are intimately related to the design of the rest of the image analysis system-particularly the preprocessor and the classifier. Toward aiding this design, a few guidelines and illustrative examples are included.

We describe a hierarchic computer procedure for the detection of nodular tumors in a chest radiograph. The radiograph is scanned and consolidated into several resolutions which are enhanced and analyzed by a hierarchic tumor recognition process. The hierarchic structure of the tumor recognition process has the form of a ladder-like decision tree. The major steps in the decision tree are: 1) find the lung regions within the chest radiograph, 2) find candidate nodule sites (potential tumor locations) within the lung regions, 3) find boundaries for most of these sites, 4) find nodules from among the candidate nodule boundaries, and 5) find tumors from among the nodules. The first three steps locate potential nodules in the radiograph. The last two steps classify the potential nodules into nonnodules, nodules which are not tumors, and nodules which are tumors.

This paper reports some results on the use of parallel-structured computers to detect and describe concavities in simply connected planar regions (``domains'' or ``blobs''). We show, in particular, how these concavities may be obtained by a parallel filling-in process-somewhat like pouring liquid into several cups simultaneously. It has been shown that the concavities and concavity tree of a regular cellular blob (i.e., a digitized simply connected planar region) can be obtained by the use of a sequential algorithm that finds the minimum-perimeter polygon (MPP) passing through the boundary cells of the cellular blob. In this paper we show how any such MPP may be computed by a sequence of simultaneous local operations in a parallel-structured computer. We also show that the ratio of computation times for sequential algorithms to those for parallel algorithms operating on the cellular image of a large circular blob is approximately proportional to the square root of the blob's perimeter, assuming the size of the vertex-detecting window is fixed and large enough to detect one or more vertices of the MPP. We also show that filling in the concavities by a sequence of parallel local operations terminates to an approximation of the cellular hull (i.e., the digitization of the convex hull of the original blob) in a finite time, and that this approximation is a subset of the cellular hull.

We develop a theory for the analysis of binary-valued digital pictures, particularly blobs and arcs, on a fairly large class of nonuniform as well as uniform mosaics. These so-called "acute mosaics" can represent a wide variety of schemes for digitizing images in machine vision systems. These mosaics can also represent a variety of retinas in human and animal visual systems. We prove the existence of minimum-perimeter-polygon (MPP) representations of digitized blobs on arbitrary mosaics and the uniqueness of MPP's in acute mosaics. We introduce the concept of "relative convexity," and show its relation to the MPP. We show that the MPP reflects the concavities of the digitized blob. We describe and prove the validity of simple tests for cellular convexity and cellular straightness. We present and prove the validity of an algorithm for computing the MPP of so-called "normal complexes" (a broad class of digitized blobs) on an acute mosaic.

We present a model of threshold learning that represents discrete one-dimensional learning processes by a continuous two-dimensional learning process. The model gives us an overall view of the learning dynamics of an expanded range of training procedures, and provides insight into the training of multidimensional linear pattern classifiers. In our model the expected performance is measured by learning curves, and the confidence in this expected performance is measured by variance curves. Previous work on the continuous approximation has been restricted to one-dimensional learning processes. The theory developed here promises to lead to improved training procedures and improved rules for determining when to stop training.

A theory for describing and measuring the concavities of cellular complexes (digitized silhouettes) is developed. This theory involves the use of the minimum-perimeter polygon and its convex hull.

The minimum-perimeter polygon of a silhouette has been shown to be a means for recognizing convex silhouettes and for smoothing the effects of digitization in silhouettes. We describe a new method of computing the minimum-perimeter polygon (MPP) of any digitized silhouette satisfying certain constraints of connectedness and smoothness, and establish the underlying theory. Such a digitized silhouette is called a ``regular complex,'' in accordance with the usage in piecewise linear topology. The method makes use of the concept of a stretched string constrained to lie in the cellular boundary of the digitized silhouette. We show that, by properly marking the virtual as well as the real vertices of an MPP, the MPP can serve as a precise representation of any regular complex, and that this representation is often an economical one.

We describe a parallel mechanism, based on an array of circularly nutating photodetectors, that computes an approximation of the density of slopes of the boundary of any piecewise regular silhouette. This density, when properly normalized, is invariant with respect to the size, translation, and orientation of the given silhouette.

Some of the results of a study of asymptotically optimum nonparametric training procedures for two-category pattern classifiers are reported. The decision surfaces yielded by earlier forms of nonparametric training procedures generally do not minimize the probability of error. We derive a modification of the Robbins-Monro method of stochastic approximation, and show how this modification leads to training procedures that minimize the probability of error of a one-dimensional two-category pattern classifier. The class of probability density functions admitted by these training procedures is quite broad. We show that the sequence of decision points generated by any of these training procedures converges with probability one to the minimum-probability-of-error decision point.

An approach to the analysis of threshold learning suggested by the classical theory of Brownian motion is presented. In particular, it is shown how a nonlinear Langevin equation represents the motion of the threshold of a trainable signal detector, and how a Fokker-Planck diffusion equation yields an estimate of the shape of the probability density of the threshold. Our results are applicable to all trainable signal detectors in which the training procedure 1) raises the threshold in response to a false alarm, lowers the threshold in response to a false rest, and keeps the threshold unchanged in response to a correct decision, and 2) adjusts the size of the threshold increment by an amount that depends only on the trial number, and such that the threshold can eventually reach any real number.

Thresholded convolution operations occur frequently in picture-processing algorithms and in special pict ure-processing hardware, such as image storage tubes.A number of theorems revealing some of the effects of combining the thresholding operation with tlle convolution operation are derived.In particular it is shown that a discrete convolution operation takes binary-valued functions into binary-valued functions if and only if it is a translation or identically zero.It is also shown that no thresholded nonzero convolution (i.e. a nonzero convolution followed by a thresholding) is equivalent to an unthresholded discrete convolution.

The technology of modern digital circuits displays the following trends.

A formalism for representing sequences or networks of program translations and compiler translations is described. The formalism is shown to be capable of (a) concisely and clearly representing the overall tasks of assemblers and preprocessors, (b) checking for similarities or equivalences among translation networks, and (c) reducing translation networks to smaller entities.

In certain systems of signal detection and pattern recognition, the process of training an observer to distinguish levels of sensory excitation or to recognize patterns, involves an adaptive threshold adjustment. These "threshold learning processes" (TLPs) can be modeled by finite-state Markov chains. When the output statistics of these TLPs move at random between two sets of parameters, we have a "two-mode" TLP. A probabilistic measure of the training and working performance of two-mode TLPs is proposed. A method of designing periodic train-work schedules for two-mode TLPs is described. For many two-mode TLPs the ratio of working time to retraining time yielding a desired performance level is maximized when the work-retrain period is made as small as possible. The final success probability in a working phase of any two-mode Markov chain cannot be less than one-half of the success probability at the beginning of that working phase. Train-work schedules can exploit the adaptive properties of trainable detectors to overcome not only the unpredictability of the mode, but also the designer's ignorance of the channel statistics.

A synthesis procedure is described which generates all tributary networks (TRIBs) realizing a given truth function when no a priori assignment of the variables to input terminals is specified. If the truth function is not known to be realizable by a TRIB structure, the synthesis procedure provides a convenient test for TRIB realizability. If the variables are preassigned to input terminals, the synthesis and test are still applicable and correspondingly shorter. A major tool of the procedure is the matrix of binary representations of the minterms of the truth function-the so called ``minterm matrix.'' The procedure is illustrated by a numerical example.

Five fairly representative members of the class of two-summand binary adders are described and evaluated. Hopefully, this will help the development of more general approaches to computer subsystems evaluation. The adders are evaluated on the basis of three quantities: the number of two-input AND gates and OR gates, G; the gate-normalized addition time, τ; and the number of bits, n, in each summand. Three plausible formulas for computational efficiency, η, are postulated, and plotted vs n for the five adders. Based on a comparison of the resulting curves, the following efficiency formula seems preferable: η = n/τlog2G. Of the five adders considered, the new ``conditional-sum adder'' is best by the above formula when n≥ 3. Other adders, however, are shown to be superior when the assumptions underlying the evaluation of G and τ are changed. The evaluation is found to have several limitations; these are discussed. Curves of G and τ vs n are given. It is suggested that these curves can serve as raw data for other evaluations, so that various evaluation methods may be compared.

Conditional-sum addition is a new mechanism for parallel, high-speed addition of digitally-represented numbers. Its design is based on the computation of ``conditional'' sums and carries that result from the assumption of all the possible distributions of carries for various groups of columns. A rapid-sequence mode of operation provides an addition rate that is invariant with the lengths of the summands. Another advantage is the possibility of realizing the adder with ``integrated devices'' or ``modules.'' The logic of conditional-sum addition is applicable to all positive radices, as well as to multisummand operation. In a companion paper, a comparison of several adders shows that, within a set of stated assumptions, conditional-sum addition is superior in certain respects, including processing speed.