Sanders Associates Limited

Lockheed Sanders, Inc.

United States of America as Represented by the Secretary of the Air Force

James L Burrows

Paul D Zemany

Stephen B Butler

A finite-state machine (30), which receives its input on INPUT lines (32) and generates its output on OUTPUT lines (34), is implemented with a content-addressable memory (46), whose output is the address of the location containing the data word presented to the content-addressable memory as its input. The content-addressable memory's input data word is the concatenation of the finite-state-machine input and the content-addressable-memory output, while the content-addressable-memory output is the output of the finite-state machine.

Finite state-machine employing a content-addressable memory

A masked compare circuit for comparing a first N-bit dataword to a second N-bit dataword, the circuit including a decoder for receiving an M-bit mask code and generating an output signal identifying a bit position, K, derived from the M-bit mask code, M and K being positive integers; and a comparator module responsive to the decoder output signal for comparing the N-K+1 most significant bits of the first dataword to corresponding bits of the second dataword, the comparator module generating an output signal having a first value when all of the compared bits are the same and having a second value when any of the compared bits are different.

Bit masking compare circuit

A data processing system, for processing programs in the form of networks of connected processing elements each relating to an arithmetic or logical operation, includes a memory for storing code representations of the processing elements and process data, processing apparatus including address computation circuitry for generating addresses for the memory and arithmetic and logic circuitry for processing the process data. A finite state machine receives the code representations of the processing elements and generates control signals for controlling the address computation circuitry, arithmetic and logic circuitry and memory in response to the nature of the processing element.

Network simulation system

Each word location (18-0, 18-1, 18-255) in a content-addressable memory has a tally circuit (24-0, 24-1, 24-255) associated with it. A data word on data lines (12) is compared simultaneously with the words in all of the word locations, and the tally circuit associated with each location counts the number of matches between the key word in that location and the data word represented by the signals on the data line. The tally circuits apply tally signals representing the number of matching bits in their respective word locations to comparison circuits (28-1, 28-255), each of which compares the tally output from its associated tally circuit with the output from a previous comparison circuit and forwards the higher of the two to the next comparison circuit. Each comparison circuit also applies to a priority encoder (32) an output that indicates whether the associated tally circuit has generated a tally signal representing a tally greater than that from all previious locations. The encoder circuit (32) encodes the address of the location having the highest tally, and the output of the last comparison represents the highest tally is. In this manner, the content-addressable memory (10) can be addressed by the closest match, not only by an exact match.

Content-addressable memory with soft-match capability

A comparison circuit which is both window addressable and content addressable, the circuit including comparison elements which include a pair of match transistors which isolate outputs indicating whether an input is not greater than stored data and whether an input is not less than stored data from an output indicating whether an input is equal to stored data.

Comparison circuit

A simulator for simulating the response of a network of predefined processing elements to a set of input stimuli. The network processing elements are arrayed in a plurality of rows and columns and a representation of each element is stored in a storage location in a symbol memory, the storage locations of which have row and column addresses corresponding to the rows and columns in the network array. A control circuit iteratively receives representations from the symbol memory identifying a processing element at a location in the network and controls an arithmetic and logic unit to generate an output signal representative of the output of the corresponding processing element in response to input stimuli which are represented by data signals from a data memory and an intermediate storage register. The control circuit then controls the storage of the output signal from the arithmetic and logic unit in the data memory and the intermediate storage register. The simulator iteratively processes each processing element by stepping across each row in the network and down from one row to the next until all of the elements are processed.

Simulation device

A method and apparatus for simulating a network comprising a plurality of processing elements useful in simulating, for example, complex digital combinatorial electronic logic circuits. Each type of digital logic element is assigned a symbol, and the symbols are stored in an array pattern in a memory, with the row and column addresses of the symbols in memory corresponding to their position in the network. The simulator sequentially retrieves each element in the network starting from an input and determines the element response to an input signal based on the type of element and the signals input to it. After all of the elements in the network have been processed, the simulated output of the network is available at the network output elements.

Simulation apparatus and method

A data stack for storing data at sequential locations in a memory and for transmitting the data in modes defined by commands from a host data processing system. A random access memory stores the data in sequential locations at addresses selected by a state signal generator comprising read only memory. The state generator generates the addresses and read/write control signals for the random access memory in response to the commands from the host system and a previous address provided by the generator.

Programmable push-pop memory stack

A tally cell circuit for counting the number of logical ones in an input signal utilizing a parallel-series combination of four CMOS field-effect transistors. The number of input ones in the input are expressed in a binary code at the output of the tally cell circuit.

Tally cell circuit

A bit-slice adder circuit for adding a plurality of input numbers in binary form. A tally circuit receives all of the bits from a bit position of all of the numbers and identifies the number of 'ones' in that bit position. This information is coupled as address signals to a memory, which also receives, as address signals, carry signals. Each storage location at each address in the memory stores the sum of the carry portion of the location's address and the 'ones' portion of the address signals from the tally circuit. The least significant bit of the addressed storage location is coupled to a shift register, and the remaining bits comprise the carry signals that are coupled to the memory's address input for the next signal from the tally circuit. After all of the bit positions in the input numbers have been coupled through the tally circuit, the sum is generated which comprises the last carry signal concatenated with the bits stored in the shift register.

Bit-slice adder circuit

Universal logic circuit cells for use in designing and laying out electronic circuits. The cells provide AND and OR on other logical functions on input signals, and include a conventional AND or OR gate, or other logic gate, and associated input and output connections and circuitry that enables them to be used in many applications. The cells simplify laying out a combinatorial logic circuit after it has been designed.

Universal logic circuit modules

Apparatus for sorting two input numbers including a memory that iteratively receives a digit from both of the numbers and transmits output signals corresponding to the input digits, the digits of the larger number being transmitted on one output line and the digits of the smaller number being transmitted onto another output line. The apparatus includes a memory that receives, as address signals, the state signal and signals corresponding to the input digits. The state signal determines the output lines onto which the next pair of input digits are to be transmitted.

Sorting apparatus

A universal logic circuit that performs a selected one of several logic operations on a pair of input signals in response to the receipt of a control signal and the terminals to which the input signals and control signal are coupled.

Universal logic circuit

A variable radix processor is constructed on 1.25 micrometer CMOS/SOS. The processor, based upon a predetermined algorithm, is constructed to process radix 2 to 7 data wherein the data is input in a parallel-by-word, parallel-by-bit format. A format selection switch has the data input whereafter a plurality of switches outputs an address format to a bit-slice multiply-adder. The bit slice multiply-adder has ROMs addressed by the format selection switch. Based upon the predetermined algorithm, each unique address format causes the ROMs to output a unique word in parallel bits to a tally cascade circuit and then to a fast-carry adder. The processor can operate on a transfer function such as Z.sub.A =.+-.(A.+-.C), Z.sub.B =B where A=.SIGMA.a.sub.i X.sub.i, B=b.sub.i X.sub.i with very high throughput rates such as 380 million operations per second.

Variable radix processor

A data driven processor for searching data stored in memory to identify messages or other data containing operator selected keywords containing alpha-numeric or other characters and for performing arithmetic and other functions performed by processors. The processor comprises a plurality of commercially available integrated circuit random access memories (RAMs). The binary words read out of the RAMs are applied to the higher order addressing inputs of the same RAMs. Messages being searched for keywords are applied to the lower order addressing inputs of the same RAMs. A binary word applied to the higher order addressing inputs of the RAM memory selects a block of memory bits with each bit being associated with a different character. Only the memory bit within a selected block of memory bits corresponding to the keyword character being searched for contains a binary word indicating the block of bits for the subsequent keyword character to be searched for. When a character being searched for is detected, the binary word in the corresponding memory location is read out and applied to the higher order memory inputs. This causes the next block of memory bits to be addressed to await receipt and detection of the next keyword character. After detecting all the characters of a keyword or keywords an output from the RAM memory is used to transfer the stored message containing the selected keyword or words to the output device for operator review.

Growing community of inventors

Merrimack, NH, United States of America

James L Burrows