Browse Prior Art Database

Digital Division by Small Integers

IP.com Disclosure Number: IPCOM000076354D
Original Publication Date: 1972-Feb-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 51K

Publishing Venue

IBM

Related People

Duke, KA: AUTHOR

Abstract

Disclosed is a digital network formed from commonly used, simpler networks (adders, gates, etc.,), which performs division by 5 of a binary number with remainder or round-off as required. The technique can be directly applied to division by certain integers of the form 2/n/ + 1, e.g., 3, 9 and extended to other integers such as 7. In all cases, a power of 2 must be found such that 2/n/ -1 is an exact multiple of the integer.

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

Page 1 of 3

Digital Division by Small Integers

Disclosed is a digital network formed from commonly used, simpler networks (adders, gates, etc.,), which performs division by 5 of a binary number with remainder or round-off as required. The technique can be directly applied to division by certain integers of the form 2/n/ + 1, e.g., 3, 9 and extended to other integers such as 7. In all cases, a power of 2 must be found such that 2/n/ -1 is an exact multiple of the integer.

A basic network for division by 5 would consist of a binary adder and a complementing shifter providing the function "-4x". The inputs to the adder are the binary number, x, and the output, y, of the shifter. The input to the shifter is the output, a, of the adder which is also the output of the network. When the network stabilizes, the following relationships apply. a = x + y ....(1) y = -4a ....(2)
Therefore: a = x -4a i.e.: 5a = x ...(3) and: x = a/5 ....(4).

Now equation (3) is true modulo 2/n/, where n is the number of bits in the adder and shifter. The step to equation (4) is valid only if a has no remainder when divided by 5. Since bits of higher significance have no effect on the bits of lower significance, it can be shown that the network will stabilize. Thus, a simple circuit can be devised for division by 5 of a binary number if that number is an exact multiple of 5. Furthermore, that circuit may operate in either a serial or parallel mode. To accommodate inputs which are not exact multiples of 5, the basic network can be preceded by a residue generator and the residue subtracted from x using the first two positions of the adder. However, residue circuits are fairly complex and completely nonstandard, i.e., have little general application. Post correction can be effected simply by using a binary adder.

If a number which is not an exact multiple of 5 is applied to the above- mentioned basic network, a binary pattern appears in the result which recurs every four bit positions and is indicative of the remainder which should have been subtracted. That pattern is the remainder divided by 5 modulo 2/n/. As shown in fig. 1, the value of the remainder, and thus of the correction pattern may be uniquely determined by inspection of the most significant two bits of the output of the first adder, unless they are...