Browse Prior Art Database

Modulo 3 Residue Tree

IP.com Disclosure Number: IPCOM000094792D
Original Publication Date: 1965-Jun-01
Included in the Prior Art Database: 2005-Mar-06
Document File: 3 page(s) / 54K

Publishing Venue

IBM

Related People

Goldschmidt, RE: AUTHOR [+2]

Abstract

Residue generation, Modulo-3, is used in error detecting applications for both decimal and binary machines. In determining the residue of the value in a binary register, adjacent orders have relative values of 1 and 2 and are usually summed up, Modulo-3. Such generates a signal representing the residue of the two orders on the appropriate one of three output lines having values of 0, 1, and 2. Two such groups of three output lines each are then combined in each residue adder of a combining level of a residue tree. This reduces the number of output lines by one half. The combining levels are repeated until only one group of output lines remains. These lines carry the resultant residue signal.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Modulo 3 Residue Tree

Residue generation, Modulo-3, is used in error detecting applications for both decimal and binary machines. In determining the residue of the value in a binary register, adjacent orders have relative values of 1 and 2 and are usually summed up, Modulo-3. Such generates a signal representing the residue of the two orders on the appropriate one of three output lines having values of 0, 1, and
2. Two such groups of three output lines each are then combined in each residue adder of a combining level of a residue tree. This reduces the number of output lines by one half. The combining levels are repeated until only one group of output lines remains. These lines carry the resultant residue signal.

In large parallel machines, it is necessary to generate the residue of an answer at maximum speed. This is so that an error diagnosis can be made as early as possible. Therefore, only one logic delay due to the hardware can be permitted for each combining level of the residue tree. In the upper drawing, a 56-bit register 5 contains the value whose residue is to be generated. Each order provides a true + and a complement - output signal line. These true and complemental outputs are combined in a residue tree as indicated to generate an output residue signal. To meet the requirement of only one logic delay time for each combining level, two different residue Adders 1 and 2 are required.

Adder 1, as shown in a separate drawing, comprises three sets of three Nor's (Or-Invert's) 6. Each set has the outputs of its Nor's connected in a Dot OR connection as a single output line. This has a signal representing the residue outputs shown. When the voltages of inputs of Adder 1 are negative going i. e., complemental, to indicate the presence of a signal, one of the output line voltages goes positive, i. e., true to indicate the presence of a residue signal on that line. Adder 2 is the same as Adder 1 but receives one set of negative going, complemental, inputs and one set of positive going, true, inputs. With these inputs and the connection as shown, the voltages of its output lines are complemental to the residue output. By properly combining these Adders 1 and 2 as shown in the...