US4996527A — Pipelined residue to mixed base converter and bas…

Claim 1

Independent Claim 80 words

An information processor receiving a residue number as an input, said information processor comprising: a plurality of arithmetic units arranged in a plurality of sequentially arranged stages, odd stages of said plurality of stages performing first arithmetic operations in parallel, even stages of said plurality of stages performing second arithmetic operations in parallel; said odd and even stages alternately performing said first operations and said second operations to generate at least one mixed base digit corresponding to said residue number.

Claim 2

Dependent Claim 80 words

An information processor receiving a residue number as an input, said information processor comprising: a plurality of arithmetic units arranged in a plurality of sequentially arranged stages, odd stages of said plurality of stages performing first arithmetic operations in parallel, even stages of said plurality of stages performing second arithmetic operations in parallel; said odd and even stages alternately performing said first operations and said second operations to generate at least one mixed base digit corresponding to said residue number.

Claim 3

Dependent Claim 28 words

An information processor as set forth in claim 1, wherein said first operations are one of modular additions and modular subtractions, and said second operations are modular multiplications.

Claim 4

Dependent Claim 40 words

An information processor as set forth in claim 2, wherein said first and second operations are performed such that an equation in a general form of; ##EQU19## is solved for at least one a k , where k=1, ... N.

Claim 5

Dependent Claim 29 words

An information processor as set forth in claim 3, further comprising at least one delay circuit arranged such that said information processor processes information in a synchronous pipelined manner.

Claim 6

Dependent Claim 48 words

An information processor as set forth in claim 4, wherein said plurality of arithmetic units and said at least one delay circuit are arranged in a plurality of non-redundant residue channels such that one channel is associated with each digit of said at least one mixed base digit.

Claim 7

Dependent Claim 17 words

An information processor as set forth in claim 5, wherein said arithmetic units are optical arithmetic units.

Claim 8

Dependent Claim 43 words

An information processor as set forth in claim 5, further comprising a first redundant residue channel arranged parallel to said nonredundant residue channels; said first redundant residue channel including arithmetic units which calculate a first redundant residue digit based on said residue number.

Claim 9

Dependent Claim 17 words

An information processor as set forth in claim 7, wherein said arithmetic units are optical arithmetic units.

Claim 10

Dependent Claim 62 words

An information processor as set forth in claim 7, wherein an N-th arithmetic unit performing first operations in said first redundant residue channel adds a N to a sum S', said sum S' generated from stages prior to said N-th arithmetic unit performing first operations, where a N is a highest order non-redundant mixed base digit and N is a positive integer.

Claim 11

Dependent Claim 115 words

An information processor as set forth in claim 7, wherein: a first arithmetic unit of said first redundant residue channel utilizes an input of zero; and wherein said information processor further comprises; a second redundant residue channel arranged parallel to said first redundant residue channel, said second redundant residue channel including arithmetic units to calculate a second redundant residue digit based on said residue number, said second redundant residue channel utilizing an input of |M|m r , where M is a product of non-redundant moduli and m r is a redundant modulus; and a selector selecting said first or second redundant residue digits based on a value of a highest order non-redundant mixed base digit.

Claim 12

Dependent Claim 53 words

An information processor as set forth in claim 7, further comprising a final stage arithmetic unit adding M·a N to a value received from a last arithmetic unit of said first redundant residue channel, where M is a product of non-redundant moduli and a N is a highest order non-redundant mixed base digit.

Claim 13

Independent Claim 131 words

A method of processing a residue input number signal to generate a mixed base digits signal corresponding to said residue input number signal, comprising the steps of: (a) receiving said residue input number signal; (b) subtracting a first digit signal of said residue input number signal from other digit signals of said residue input number signal to generate first stage signals, said first digit signal indicative of a first mixed base digit; (c) in parallel with step (b), time delaying a signal identical to said first digit signal; (d) multiplying each of said first stage signals by multiplicative inverse signals to produce a second mixed base digit signal indicative of a second mixed base digit; (e) in parallel with step (d), time delaying said signal identical to said first digit signal.

Claim 14

Independent Claim 131 words

A method of processing a residue input number signal to generate a mixed base digits signal corresponding to said residue input number signal, comprising the steps of: (a) receiving said residue input number signal; (b) subtracting a first digit signal of said residue input number signal from other digit signals of said residue input number signal to generate first stage signals, said first digit signal indicative of a first mixed base digit; (c) in parallel with step (b), time delaying a signal identical to said first digit signal; (d) multiplying each of said first stage signals by multiplicative inverse signals to produce a second mixed base digit signal indicative of a second mixed base digit; (e) in parallel with step (d), time delaying said signal identical to said first digit signal.

Claim 15

Dependent Claim 38 words

A method according to claim 12, further comprising the steps of: (f) repeatedly subtracting mixed base digit signals and multiplying by multiplicative inverse signals in a synchronous pipelined fashion such that additional mixed base digit signals are generated.

Claim 16

Dependent Claim 127 words

A method according to claim 13, further comprising these steps performed in synchronism with steps (a) through (f): (g) subtracting said first digit signal of said residue input number signal from a zero signal; (h) repeatedly subtracting mixed base digit signals and multiplying by multiplicative inverse signals in a synchronous pipelined fashion such that a first sum signal, is generated; (i) subtracting a highest order mixed base digit signal from said first sum signal to produce a second signal; and (j) multiplying said second signal by a first multiplier signal to produce a first redundant residue digit signal associated with said residue input number signal, said first redundant residue digit signal representing a correct redundant residue digit when said residue input number signal represents a non-negative number.

Claim 17

Dependent Claim 137 words

A method according to claim 13 further comprising these steps performed in synchronism with steps (a) through (f): (k) subtracting said first digit signal of said residue input number signal from a zero signal; (1) repeatedly subtracting mixed base digit signals and multiplying by multiplicative inverse signals in a synchronous pipelined fashion such that a first sum signal is generated; (m) adding a highest order mixed base digit signal to said first sum signal to produce a second signal; and (n) multiplying said second signal by a multiplier signal to produce a first redundant residue digit signal associated with said residue input number signal, said first redundant residue digit signal representing a correct redundant residue digit when said residue input number signal represents a negative number and when said residue input number signal represents a non-negative number.

Claim 18

Dependent Claim 188 words

A method according to claim 14, further comprising these steps (o) thorough (r) performed in synchronism with steps (a) through (f) and steps (g) through (j): (o) subtracting said first digit signal of said residue input number signal from a signal representing a number based on a non-redundant ring circumference; (p) repeatedly subtracting mixed base digit signals and multiplying by multiplicative inverse signals in a synchronous pipelined fashion such that a third sum signal is generated; (q) subtracting a highest order mixed base digit signal from said third sum signal to produce a fourth signal; (r) multiplying said fourth signal by a second multiplier signal to produce a second redundant residue digit signal associated with said residue input number signal; (s) after completion of steps (a) through (r), selecting one of said first redundant residue digit signal and said second redundant residue digit signal based on a highest order mixed base digit signal to produce a fifth signal, said fifth signal representing a correct redundant residue digit when said residue input number signal represents a negative number and when said residue input number signal represents a non-negative number.

Claim 19

Dependent Claim 83 words

A method according to claim 14, further comprising the step of: (t) after steps (a) through (j), adding a signal representing M·a N to said first redundant residue digit signal, where M is a product of nonredundant moduli and a N is a highest order mixed base digit, to produce a sixth signal, said sixth signal representing a correct redundant residue digit when said residue input number signal represents a negative number and when said residue input number signal represents a non-negative number.

Claim 20

Dependent Claim 100 words

An information processor receiving a residue number as an input, said information processor comprising: a plurality of optical arithmetic and logic units (OALUs) arranged in channels and stages, each digit of said residue number corresponding to a channel which produces a mixed base digit associated with said residue number; said stages serially arranged to successively generate mixed base digits corresponding to said residue number by performing modular multiplication and modular subtraction; and delay circuits arranged parallel to said plurality of OALUs such that all of said mixed base digits are transmitted from said information processor at essentially the same time.

Claim 21

Dependent Claim 100 words

An information processor receiving a residue number as an input, said information processor comprising: a plurality of optical arithmetic and logic units (OALUs) arranged in channels and stages, each digit of said residue number corresponding to a channel which produces a mixed base digit associated with said residue number; said stages serially arranged to successively generate mixed base digits corresponding to said residue number by performing modular multiplication and modular subtraction; and delay circuits arranged parallel to said plurality of OALUs such that all of said mixed base digits are transmitted from said information processor at essentially the same time.

Claim 22

Dependent Claim 59 words

An information processor as set forth in claim 18, wherein said modular multiplication and modular subtraction is performed to solve an equation in the general form of; ##EQU20## for each a j , J=1, ... N, where a j is a mixed base digit corresponding to said residue number, and m i are moduli of a residue number system.

Claim 23

Dependent Claim 36 words

An information processor as set forth in claim 19, further comprising at least one additional channel of OALUs for calculating a redundant residue digit, which corresponds to said residue number, based on said mixed base digits.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1994-02-25	1994-08-27	1995-02-26	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1998-02-25	1998-08-27	1999-02-26	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2002-02-25	2002-08-27	2003-02-26	$7700.00	Window Closed / Lapsed

Pipelined residue to mixed base converter and base extension processor

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag