International Business Machines Corporation

Arnold Weinberger

Samuel R Levine

Tin-Chee Lo

Chin-Long Chen

Lalit R Bahl

Shanker Singh

Benedicto U Messina

David T Shen

Raymond J Pedersen

Donald George Grice

Ronald Barthold Arps

Frederick T Blount

Leonard L Fogell

Canh Xuan Le

Louis R Bryant

David F Johnson

Robert C Letteney

A fault tolerant circuit having improved error correction and detection properties takes advantage of two distinct forms of information redundancy: modular redundancy and parity check bit redundancy, in a cooperative fashion. In particular, it is shown that simple majority voting logic circuits, when employed in the subject environment, provide an easily realized mechanism for error correction and error detection. This results in an extremely fault tolerant information system.

Fault tolerant system based on voting

A memory structure is described as comprised of a large number of fixed-size page frames. Each page frame in the memory is spread among all chips in the memory. The size of the memory structure may be extended or expanded by adding the same type of high-capacity chip originally used to construct the memory. (The chips may be constructed of semiconductor DRAM technology.) When the memory is extended/expanded, the fixed-size page frames have their lateral dimension decreased and their length increased, in accordance with the increase in the number of chips in the memory. A shift register on each chip accommodates the moving of pages within the memory structure as the page-frame shape and the redistribution of the page frame locations in the memory are changed when the number of chips in the memory structure is changed, without requiring any change in the internal structure of the chips. A page of data can be moved in two dimensions between any page frames within the memory structure without using any external bus, even though the size of the memory structure is changed. No bit in a page is moved off of its chip during a page move operation. All bits in a page are accessed and moved logically in parallel. Extremely fast page transfer rates are obtainable by the busless page move operations. Special addressing is provided that accommodates both the internal page move operations and data unit accesses in the memory structure for an external memory bus. Multiple logical memories can be accommodated in the memory structure.

Chip organization for an extendable memory structure providing busless

An (M plus K)-digit accessed address is checked to see if it may fall within a range of addresses g defined by the address at one end of the range plus a variable range of addresses (g). The checking is done in a single step in a comparison of the K lowest order address digits for both addresses. The K digits of the two addresses are checked against one another in two separate segments, a pointer segment and a range segment. The pointer segments of the two addresses are examined to see if any one of three relationships which would possibly place the accessed address within the range exists. The range segments of the two addresses are examined at the same time for an additional requirement to place the accessed address in the range.

Address range determination

Full adder stages in this adder are made up of two half adder stages that will produce either the true or complement of the sum as a bundle of subfunction signals that can be shared between the sum and carry outputs of the full adder stage. The half adder stages come in a variety of forms to accommodate both true, both complement or one true and one complement input combinations to the stage.

Sum and carry outputs with shared subfunctions

This error checker determines if more than one set of control signals F1 through FN are on and also flags invalid as opposed to valid situations where none of the control signals F1 to FN are on. To distinguish the invalid from valid situations where none of the control signals F1 to FN are on, an additional control signal X=F1.multidot.F2.multidot. . . . .multidot.FN is generated and then fed with the control signals F1 to FN through a prior art detector which detects when more than one or none of the control signals X and F1 through FN are on.

Error checking of mutually-exclusive control signals

This specification discloses a multi digit binary adder embodied in programmable logic arrays (PLAs). The particular programmable logic array used here has a separate two-bit decoder for receiving each like order pairs of digits A.sub.i, B.sub.i of two n digit binary numbers A.sub.0, A.sub.1 . . . A.sub.n-1 and B.sub.0, B.sub.1 . . . B.sub.n-1 plus a carry C.sub.in. The decoders generate an output signal called a minterm on a different line for each of the four possible combinations A.sub.i .multidot.B.sub.i, A.sub.i .multidot.B.sub.i, A.sub.i .multidot.B.sub.i and A.sub.i .multidot.B.sub.i of the true and complement of each pair. The minterms from the decoders are fed to an array called the product term generator or AND array which generates product terms

Programmable logic array adder

A high speed multiply apparatus minimizes latch requirements and I/O pin requirement between chips by a new configuration which iteratively adds four multiples of a multiplicand in a stage of 4-2 carry save adders which then feed four-bit parallel adders each having four sum outputs and a carry output from the highest order bit position. Only the sum outputs are latched and then fed to a carry propagate adder on each iteration for addition to the previous partial products. Only the single carry output from each of the 4-bit parallel adders needs to be latched and then fed to another 4-bit parallel adder.

High speed multiplier using carry-save/propagate pipeline with sparse

This specification discloses a multi digit binary adder embodied in programmable logic arrays (PLAs). The particular programmable logic array used here has a separate two bit decoder for receiving each like order pairs of digits A.sub.i, B.sub.i of two n digit binary numbers A.sub.0, A.sub.1....A.sub.n-1 and B.sub.0, B.sub.1....B.sub.n-1 plus a carry C.sub.in. The decoders generate an output signal called a min term on a different line for each of the four possible combinations A.sub.i B.sub.i, A.sub.i B.sub.i, A.sub.i B.sub.i and A.sub.i B.sub.i of the true and complement of each pair. The min terms from the decoders are fed to an array called the product term generator or AND array which generates product terms

An improved system for adding two numbers together. The numbers may be expressed either in binary form or in binary coded decimal form (wherein each decimal digit is represented by its equivalent four binary bits). By taking advantage of 'don't care' decimal input conditions, a minimal implementation of a carry look-ahead adder which can operate upon both types of numbers is obtained.

Integrated binary-BCD look-ahead adder

Disclosed is a decoder which receives a number of coded binary-weighted input signals and which provides, on a plurality of output signal lines, a threshold related to the coded value of the input signals. The threshold is defined at the output as a consecutive sequence of output signal lines having a binary 0 value on one side of the threshold, and a consecutive sequence of output signals on the other side of the threshold having a binary value of 1. In one embodiment, a single level of binary logic receives n input signals and produces a threshold on m = 2.sup.n -1 output signal lines. A second embodiment receives n input signals which are divided into groups of signals, each group of which is applied to an intermediate threshold generator, the outputs of which are combined in a final level to provide m output signals. A further embodiment of the threshold decoder receives two groups of input signals which are combined in a first level of intermediate threshold generators, the outputs of which are then combined in a final stage which may produce more than one threshold on the output signal lines. Another further embodiment of the threshold decoder discloses a plurality of groups of input signal lines, combined in a plurality of intermediate threshold generators, the outputs of which are combined in a final level of logic to produce, selectively, a like plurality of thresholds on the output signal lines.

Threshold decoder

An apparatus is disclosed for compressing a p .times. q image array of two-valued (black/white) sample points. The image array points are serially applied to the apparatus in consecutive raster scan lines. In response, the apparatus simultaneously forms two matrices respectively representing a high order p .times. q predictive error array and a p .times. q array of location events (such as the raster leading edges of all objects in the image). Improved compression is achieved by selecting between the more compression efficient of two methods for encoding the position of errors in the prediction error array. These alternative methods are conventional run-length coding and a novel form of reference encoding, used selectively but to significant advantage. Thus, a run-length compression codeword is formed from the count C of non-errors between consecutive errors (in response to the occurrence of each error in the jth bit position of the ith scan line of the predictive error array) upon either C.ltoreq.T, where T is a threshold, or C&gt;T and there being no occurrence of a line difference encoding for the error (where i, j, C and T have positive integers). A line difference codeword with difference value v is generated upon the joint event of C&gt;T and either the single or multiple occurrence of location events in the ith-1 scan line of the location event array within the bit position range of B.ltoreq.r.ltoreq.(j+n), where positive integer B is the greater of function D(T,v) and (j-n), and the number of intervening location events, s, within the bit position range of D(T,v).ltoreq.q&lt;(j-n) not exceeding some limit m (where m, n, q, r and s are positive integers).

Apparatus for compression coding using cross-array correlation between

A digital LRU network in which a use value in a chronology register always appears to be increasing; it is incremented for each access to a different data block currently represented in an active LRU array and this use value is copied into an index for that block in an active use-value array. Special circuits are provided to maintain the appearance of continuously increasing use values. At the start of each array search, the special circuits check the chronology register to determine if its use value is nearing its highest registerable value by testing its two high order bits for 1's. If so, the chronology register is set to 100...0, which is higher than any use value in the active array, after the use values in the active array are shifted one bit position to the right by writing them into corresponding positions in another array, which then becomes the active array. The right shift drops the low-order bit in the use values and sets the high-order bit to zero. The right shift increases the range of use values that can subsequently be set into the active array without affecting the stored relationships among the existing use values, and enables the incrementing of use values to continue. The second array is used to permit overlap of the read cycle of one array with the write cycle of the other array.

Circuit for implementing a modified LRU replacement algorithm for a cache

Logic circuits in an adder for use in data processing for the detection of a sum of all ZEROES together with the mathematics upon which the circuits are based. Circuits and mathematics are also disclosed for a detection of a sum of all digits equal to the radix less one. Each of these detected sum conditions are produced prior to or at least concurrently with the production of the sum itself.

Adder with fast detection of sum equal to zeroes or radix minus one

This specification describes a programmable logic array (PLA) in which the readout table or OR array for the PLA is broken into two segments and the segments placed on opposite sides of the search table or AND array for the PLA. The output lines for the AND array can then be split so that outputs on one segment of those lines are fed to the OR array on one side and outputs on the other portion of those lines are fed to the OR array on the opposite side. Likewise the output lines in the OR arrays can be broken so that different functions can be fed out to opposite sides of the OR arrays. It is also possible to break input lines in both the OR and AND arrays to isolate functions from one another.

Logic array with multiple readout tables

This specification describes an associative memory decoder for a memory system in which the units in the memory system are reconfigurable both in size and in number. The decoder is designed to take an address for that memory system and address memory space in the memory system irrespective of the amount of storage in the system so that the decoder has to change as memory capacity is added or subtracted from the memory system.

Growing community of inventors

Poughkeepsie, NY, United States of America

Arnold Weinberger