An algorithm is given for the base-extension (BE) computation in residue number systems that requires the standard four steps (for systems with three moduli) but which saves hardware. Furthermore, for the particular moduli m-1, m, and m+1 it is shown that fast-BE in only two steps is possible, for all combinations of the moduli.

Conditional-sum addition in a -2 base system and its comparison with normal binary conditional-sum addition is discussed. It is found that approximately 2.0 to 2.5 times as much hardware is required for this high-speed addition method in the negative binary system as compared to the positive binary system.

An algorithm for determining whether or not an arbitrary sequential machine can be synthesized using only shift registers or up-down counters as memory elements is presented. When realization is possible, a basis for state assignment is given. State-partitioning techniques are used to this end and it is concluded that by means of a single test, it is possible to simultaneously check for realizability using either of the two module types.

It is shown that in a residue system with only the two moduli m-1 and m+1, base extension to modulus m is possible with savings in time and sometimes in hardware over conventional techniques. It is also shown that the underlying theory generalizes to provide comparable savings when extending any system with two moduli nm-1 and nm+1 (where n may be any integer) to include the third modulus m. For systems with more than two moduli, the savings are obtained in sign detection and partial base-extension operations. Savings are also possible during other residue operations (e.g., scaling, magnitude comparison, and overflow determination) in which sign detection and base extension are used.