Binary to modulo M translation
AssigneeBurroughs Corporation
InventorChandrakant R. Vora
Life of this patent
Estimating the term…
Abstract
Modulo M translation is performed on a large binary number of n bits by grouping the binary number in contiguous sets of approximately K bits each, storing the modulo M residues for each K bit set in an individually associated pre-stored ROM, reading the modulo M residues for a particular K bit segment of a binary number out of the ROMs, and performing modulo M addition on the read-out residues. Thus, modulo M translation of a positive number is accomplished in n/k modulo M additions and a table look-up, with the look-up table being stored in n/k ROMs. A subsequent modulo M subtraction is performed if the binary number is negative.
Claims11
An apparatus for translating to modulo M a binary number of value greater than a number M, said number M being relatively prime to said binary number, said apparatus comprising:
- means having two inputs for summing modulo M binary numerical data conveyed thereto;
- means for conveying to a first of said two inputs a first portion of said binary number, said first portion being binary numerical data of value less than said number M;
- means including a memory for translating to modulo M a second portion of said binary number, said second portion being said binary number minus said first portion;
- and
- means for conveying to a second of said two inputs said translated second portion.
An apparatus for translating to modulo M a positive-only binary number of value two times a number M, said M being relatively prime to said positive-only binary number, said apparatus comprising:
- a first modulo M translator for translating a first portion of said positive-only binary number, said first portion representing a binary number of value less than two times said number M, said first modulo M translator including
- adder means inputted by said first portion for summing said first portion minus said M and for indicating whether said summing produces a positive or negative sum, and
- multiplex means responsive to said indicating for outputting said adder means summing when said indicating is positive and for outputting said first portion when said indicating is negative;
- a second modulo M translator for translating the remaining portion of said positive-only binary number, said remaining portion being the binary number minus said first portion, said second modulo M translator including a memory system addressed by said remaining portion, said memory system including at least two memories, each of said at least two memories addressed by an individual segment of contiguous bits in said remaining portion and outputting a prestored modulo M translation for each memory address;
- a plurality of modulo M adders, one modulo M adder individually associated with each of said at least two memories;
- and
- means connecting each of said at least two memories with the individual modulo M adder associated therewith, said multiplexer means with one of said plurality of modulo M adders, and said plurality of modulo M adders with each other for providing at the output of one of said plurality of modulo M adders, a modulo M translation of said positive-only binary number.
A modulo M adder for use in a binary to modulo M translator comprising:
- a first binary input for conveying binary numerical representations less than a number M;
- a second binary input for conveying binary numerical representations less than said number M;
- first adder means for summing the binary representations conveyed on said first and second binary inputs;
- second adder means operating in parallel with said first adder means, said second adder means for summing binary representations conveyed on said first and second binary inputs minus a binary representating of said number M;
- and
- multiplexer means responsive to the summing of said second adder means for outputting the summing of said second adder means when the summing of said second adder means is positive and for outputting the summing of said first adder means when the summing of said second adder is negative.
Dependencies are inferred from the claim text.