US 6,173,305 B2Granted

Division by iteration employing subtraction and conditional source selection of a prior difference or a left shifted remainder

AssigneeTexas Instruments Incorporated

InventorSydney W. Poland

Life of this patent

Estimating the term…

Loading patent…

Abstract

A data processing apparatus iteratively forms quotient, includes data registers (200) for storing various initial and intermediate quantities, a multiplexer (215) for selecting data from one of two data registers, a barrel rotator (235) and an arithmetic logic unit (230). A first register (200a) stores the numerator, which is left shifted each iteration. A second register (200c) stores the difference formed by the prior trial subtractions. A status register (210) set by the prior arithmetic logic unit (230) result controls the selection made by the multiplexer (215). A barrel rotator (235) rotates the data selected by multiplexer (215). The arithmetic logic unit (230) subtracts the divisor from the rotated quantity this result controls the iterative division process. If the difference is less than zero, then the rotated data is selected and the quotient bit is “0”. Otherwise, the prior difference is selected and the quotient bit is “1”. In the preferred embodiment, the numerator is split between two registers. The trial difference involves only the most significant bits of the numerator. In the preferred embodiment, the inverse of the divisor is stored and the difference is formed by adding the inverse of the divisor. The division processing repeats until the quotient is completely formed and loop logic controls the number of iterations. Also, the data processing apparatus is embodied as at least one digital image/graphics processor (71, 72, 73, 74) as a part of a multiprocessor (100) formed in a single integrated circuit.

Claims28

Dependent claims

A method for performing division of a numerator having a set of most significant bits and a set of least significant bits by a divisor in a data processing apparatus comprising the steps of:

forming an arithmetic inverse of said divisor;
storing said inverse of said divisor in said first data register;
storing said set of most significant bits of said numerator in a second data register;
storing said set of least significant bits of said numerator in a third data register;
storing a status bit in a status register;
selecting an intermediate data word as either data stored in said second data register or data stored in a fourth data register based upon said status bit stored in said status register;
left shifting said intermediate data word one bit position;
left shifting said third data register one bit position;
storing in said second data register said left shifted intermediate data word including a most significant bit shifted out of said third data register as a least significant bit stored thereby replacing data previously stored in said second data register;
subtracting said divisor from said left shifted intermediate data word thereby forming a difference by adding said inverse of said divisor stored in said first data register to said left shifted intermediate data word employing an arithmetic logic unit having a first input terminal connected to said first data register, a second input terminal receiving said left shifted intermediate data word, an output generating a sum of said inverse of said divisor and said left shifted intermediate data word and a carry input to a least significant bit of said sum receiving said most significant bit shifted out of said third data register;
storing said difference of said left shifted intermediate data word and said divisor in a fourth data register thereby replacing data previously stored in said fourth data register;
determining whether said difference is less than zero;
setting said status bit stored in said status register based upon whether said difference is less than zero;
and
setting a quotient bit based upon whether said difference is less than zero.

12 more elements

A data processing apparatus for iteratively forming the quotient of a numerator divided by a divisor, said numerator including a most significant half of bits and a least significant half of bits, said data processing apparatus comprising:

a first data register storing said divisor;
a second data register initially storing said most significant half of said bits of said numerator;
a third data register;
a multiplexer having first and second inputs connected respectively to said second and third data registers, an output and a control input, said multiplexer selecting at said output one of either said first input or said second input corresponding to a control signal received at said control input;
a barrel rotator having an input connected to said output of said multiplexer and an output, said barrel shifter generating at said output barrel shifted data received at said input left shifted one bit position, said barrel shifted data supplied for storage in said second data register;
a multiple flags register initially storing a least significant half of said bits of said numerator, said multiple flags register having a shift output of a most significant bit and an shift input of a least significant bit, said shift output supplied for storage as a least significant bit in said second data register;
an arithmetic logic unit having a first operand input connected to said first data register, a second operand input connected to said output of said barrel shifter, a carry input connected to said shift output of said multiple flags register, a carry output and an output connected to said third data register, said arithmetic logic unit forming a difference between said first operand input and said second operand input at said output, and said output supplied for storage in said third data register;
an OR gate having a first input connected to a most significant bit of said output of said multiplexer, a second input connected to said carry output of said arithmetic logic unit and an output, said OR gate generating at said output a logical OR of said most significant bit of said output of said multiplexer and said carry output of said arithmetic logic unit, said logical OR supplied to said shift input of said multiple flags register;
a status register having an input connected to said output of said OR gate and an output connected to said control input of said multiplexer, said status resister thereby causing said multiplexer to select at said output either said second or said third register corresponds to a logical OR of said most significant bit of said output of said multiplexer and said carry output of said arithmetic logic unit for an immediately prior operation.

6 more elements

A data processing system performing division of a numerator by a divisor, said numerator having a set of most significant bits and a set of least significant bits, comprising:

a data system bus transferring data and addresses;
a system memory connected to said data system bus, said system memory storing data and transferring data via said data system bus;
a data processor circuit connected to said data system bus, said data processor circuit including
a first data register storing said divisor,
a second data register initially storing a most significant half of said bits of said numerator,
a third data register,
a multiplexer having first and second inputs connected respectively to said second and third data registers, an output and a control input, said multiplexer selecting at said output one of either said first input or said second input corresponding to a control signal received at said control input,
a barrel shifter having an input connected to said output of said multiplexer and an output, said barrel shifter generating at said output barrel shifted data received at said input left shifted one bit position, said barrel shifted data supplied for storage in said second data register,
a multiple flags register initially storing a least significant half of said bits of said numerator, said multiple flags register having a shift output of a most significant bit and an shift input of a least significant bit, said shift output supplied for storage as a least significant bit in said second data register,
an arithmetic logic unit having a first operand input connected to said first data register, a second operand input connected to said output of said barrel shifter, a carry input connected to said shift output of said multiple flags register, a carry output and an output connected to said third data register, said arithmetic logic unit forming a difference between said first operand input and said second operand input at said output, and said output supplied for storage in said third data register,
an OR gate having a first input connected to a most significant bit of said output of said multiplexer, a second input connected to said carry output of said arithmetic logic unit and an output, said OR gate generating at said output a logical OR of said most significant bit of said output of said multiplexer and said carry output of said arithmetic logic unit, said logical OR supplied to said shift input of said multiple flags register, and
a status register having an input connected to said output of said OR gate and an output connected to said control input of said multiplexer, said status register thereby causing said multiplexer to select at said output either said second or said third data register corresponds to a logical OR of said most significant bit of said output of said multiplexer and said carry output of said arithmetic logic unit for an immediately prior operation.

9 more elements

Dependencies are inferred from the claim text.