Browse Prior Art Database

Algorithm for Negabinary Division

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

Publishing Venue

IBM

Related People

Knapp, JW: AUTHOR [+2]

Abstract

In the algorithm for performing division in a negabinary system, coaddition is used both for testing the polarity of a negabinary number and for converting a binary number to a negabinary number.

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

Page 1 of 4

Algorithm for Negabinary Division

Introduction.

In the algorithm for performing division in a negabinary system, coaddition is used both for testing the polarity of a negabinary number and for converting a binary number to a negabinary number.

Before explaining the mechanization of a negabinary divide method, some preliminary concepts are required. First is the operation of coaddition denoted by @. The cosum of numbers A and B is the negative of the sum of A and B. A @ B = - (A + B) (Eq. 1).

Table I below is a truth table for a single-stage negabinary coadder. Inputs A and B are the operand bits, C-IN is the incoming carry, C-OUT is the outgoing carry, and @ is the cosum. Table I. Coaddition Truth Table A B C-IN @ C-OUT 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1.

It has been shown that for negabinary coaddition, there is only one interstage carry signal, as opposed to two interstage carry signals for negabinary addition or subtraction. Studies of the complexity of negabinary coadders versus negabinary adders or subtractors show that negabinary coaddition can represent a cost savings. In this implementation, the use of coaddition for the basic arithmetic operation is assumed for reasons of economy.

A useful quantity in dealing with negaradix number systems is the inversion base, denoted I(n) for a word length of n. The inversion base for n-bit negabinary words is the value of the number consisting of all 1's: 11...1. Table II shows some values for I(n) for different values of even n, and it also shows the maximum number and minimum number representable in an n-bit negabinary number system. Table II. Key Values for n-bit Negabinary Numbers n(even) I(n) max. min. 2 -1 1 -2 4 -5 5 -10 6 -21 21 -42 8 -85 85 -170 10 -341 34 1 -682. It can be shown by induction that for even n; the value (-I(n)) is the largest positive number representable in an n-bit negabinary number. This fact leads to a polarity test for negabinary numbers. In @ X is a positive number larger than the largest representable in n-bits if and only if X is negative. Thus, if X is less than zero one obtains a high-order carry-out for the process I(n) @ X. In order to test for a number which is equal to or less than zero, a forced carry into the lowest order bit position is made. Thus the operation (I(n) + C-IN) @ X gives a high-order carry-out if X</-0. THE ALGORITHM. 1. Preliminary Operations.

It is convenient to always start with an R(o) the value of the dividend of the same sign as the divisor. In the case of an even number of bits in a word, we start with R(o) negative. The original sign of the divisor must be noted, and for each iteration, the changing sign of the aligned divisor must be accounted for.

In addition the divisor must be initially aligned by shifting left to the most significant bit of the dividend, which is defined above as the initial remainder, R(o) = Dividend. 2. Diminish Operation.

1

Page 2 of 4

The signed differe...