Browse Prior Art Database

Modulo-M Circuit

IP.com Disclosure Number: IPCOM000060052D
Original Publication Date: 1986-Feb-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 2 page(s) / 39K

Publishing Venue

IBM

Related People

Pasco, RC: AUTHOR

Abstract

This invention relates to an apparatus for converting a binary number C into a modulo-M residue by examining the status of predetermined bit positions of number C. A minimum number of circuits is required since table lookup is utilized. Let (Image Omitted) where ci e {0,1} is the value of the ith bit of C. Equality establishes the congruence (Image Omitted) from this, precompute the residue terms ri = 2i(mod M) and let the corresponding binary values ci establish whether the ri is to be included into the modulo-M sum (Image Omitted) A simple circuit may be constructed which performs this operation in parallel, as illustrated in the figure for the case M = 3. It is reminiscent of the tally circuit and barrel shifter examples from Mead and Conway, Introduction to VLSI Systems Design, Addison-Wesley, 1980, pp.

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 95% of the total text.

Page 1 of 2

Modulo-M Circuit

This invention relates to an apparatus for converting a binary number C into a modulo-M residue by examining the status of predetermined bit positions of number C. A minimum number of circuits is required since table lookup is utilized. Let

(Image Omitted)

where ci e {0,1} is the value of the ith bit of C. Equality establishes the congruence

(Image Omitted)

from this, precompute the residue terms ri = 2i(mod M) and let the corresponding binary values ci establish whether the ri is to be included into the modulo-M sum

(Image Omitted)

A simple circuit may be constructed which performs this operation in parallel, as illustrated in the figure for the case M = 3. It is reminiscent of the tally circuit and barrel shifter examples from Mead and Conway, Introduction to VLSI Systems Design, Addison-Wesley, 1980, pp. 78-79 and 157-163. There are N stages, each having one control input from the corresponding bit of C. Entering each stage from the left are M wires, one of which is at Logic True and the remainder are at Logic False. Each stage is capable of either passing this one-of-M signal directly to the M output wires on its right or rotating it by an amount fixed by the corresponding ri . (In the ternary example where

(Image Omitted)

the stages alternate between rotation clockwise one bit and counterclockwise one bit.) Whether or not the rotation is taken depends on the current value of ci . The modulo-M sum emerges as a 1-of-M signal from the rightmost...