Method of determining a scaling factor

Details Method of determining a scaling factor Method of determining a scaling factor

1999-05-19

2002-01-29

Mai, Tan V. (Department: 2787)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06343303

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a method and circuit for determining a scaling factor of signed binary numbers.
BACKGROUND OF THE INVENTION
In digital signal processing applications, especially in fixed point operations, for example, in speech compression techniques, it is often necessary to determined how much a binary number can be scaled without causing a register overflow. It is convenient for the purposes of explanation to consider the decimal case. Consider a register capable of holding five decimal digits. The problem would be to determine how many times a number, say 275 could be scaled up without causing the register to overflow. In the decimal case, the answer would be 10 (10×250=2,500<10,000). In binary notation, since multiplication is equivalent to a shift to the left, for a positive number the problem essentially is one of determining the number of leading zeros. The problem is complicated by the fact that the binary numbers are assumed to be signed binary numbers, in which case the problem becomes how to determine the number of identical leading bits minus 1.
In signed binary numbers the most significant bit (MSB) indicates the sign of the number. A 1 indicates a negative number and a 0 indicates a positive number. In the case of a positive number, the magnitude is the same as the magnitude of the signed number. In the case of a negative number, the magnitude is the 1's complement of the number plus 1.
For example, the number 00001111 has a value of plus 15 in decimal notation. It can be scaled by three bits to 01111000 or decimal plus 240 without losing the sign information. If it were scaled one more place to the left, the sign information would changed and it would become a totally different number. Similarly, the number 11111110 is actually −2. It can be scaled 5 bits to the left without losing sign information to arrive at the number 11000000 or decimal −192.
It is desirable to incorporate this service into a digital signal processor. While the number of leading identical bits less one can be determined by cycling through the number, in the case of a 32 bit number this could involve up to 30 instruction cycles, which consumes substantial processor time.
An object of the invention is to provide a more efficient method of determining the scaling factor of a signed binary number.
SUMMARY OF THE INVENTION
According to the present invention there is provided a method of determining the scaling factor for a signed n bit binary number, where n=2
e
, comprising the steps of dividing the number into a plurality of subgroups of at least two bits each; providing a plurality of subunits holding said respective subgroups of bits; and arranging said subunits in a hierarchical tree structure of units, with each unit of a superior level receiving inputs from units of a lower level, each unit producing first, second and third output signals, said first output signal representing the most significant bit of said units in the associated hierarchy, said second signal indicating whether the bits in the associated hierarchy have the same value, and said third signal being an i-bit number representing the number of places less one that the bits in the associated hierarchy can be shifted, the index i being the same as the associated level in the hierarchy.
An analysis of this scheme shows that the exponent value, which is given by the value of the third signal at the top level of the hierarchy, can be arrive at in e +1 gate delays. In the case of a 32-bit number, the answer is arrived therefore in six gate delays, which represents a considerable improvement over the prior art.
The invention also provides a circuit for determining the scaling factor for a signed n bit binary number, where n=2
e
, comprising a register for storing said number, said register being divided into a plurality of subunits of at least two bits each; and a hierarchical tree structure of units with said subunits forming the lowest level thereof, and each unit of a superior level receiving inputs from units of a lower level, each unit producing first, second and third output signals, said first output signal representing the most significant bit of said units in the associated hierarchy, said second signal indicating whether the bits in the associated hierarchy have the same value, and said third signal being an i-bit number representing the number of places less one that the bits in the associated hierarchy can be shifted, the index i being the same as the associated level in the hierarchy.


REFERENCES:
patent: 4335372 (1982-06-01), Augderheide et al.
patent: 4983966 (1991-01-01), Grone et al.

Affiliated with

Also associated with

Rating

Method of determining a scaling factor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of determining a scaling factor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining a scaling factor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2873776