High-speed division and square root calculation unit
AssigneeKabushiki Kaisha Toshiba
InventorGensoh Matsubara
Life of this patent
Estimating the term…
Abstract
A calculation unit speedily calculates a division or square root according to an iteration algorithm with a partial remainder expressed with the sum of a sum digit and carry digit. The calculation unit has a quotient selection logic circuit. The quotient selection logic circuit at least has an adder for adding higher three bits of the sum digit to higher three bits of the carry digit, an OR gate for providing the OR of the fourth bits of the sum and carry digits, and a quotient digit determination block for determining the next quotient digit according to the outputs of the adder and OR gate.
Claims16
A calculation unit having at least a quotient selection logic, for calculating a division or square root according to an iteration algorithm with a partial remainder expressed with the sum of a sum digit and carry digit, the quotient selection logic comprising:
- (a) an adder for adding higher three bits of the sum digit to higher three bits of the carry digit;
- (b) OR means for providing the OR of the fourth bits of the sum and carry digits;
- and
- (c) quotient digit determination means for determining a next quotient digit according to the outputs of said adder and OR means.
A calculation unit having at least square root arithmetic data generation means, for calculating a square root according to an iteration algorithm with a quotient digit of redundant form, the square root arithmetic data generation means comprising:
- (a) a bit position indicator for storing the position of a bit where a quotient digit is calculated;
- (b) a first quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is carry propagation from a lower position;
- (c) a second quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is no carry propagation from the lower position;
- (d) root multiple formation means for generating root multiples used for calculating the square root, according to the outputs of said bit position indicator and said first and second quotient digits memories;
- and
- (e) on-the-fly digit handling means for generating a quotient digit set with carry propagation and a quotient digit set without carry propagation according to the outputs of said bit position indicator and said first and second quotient digits memories as well as a next quotient digit to be obtained.
A calculation unit for calculating a square root according to an iteration algorithm with a partial remainder expressed with the sum of a sum digit and carry digit, comprising:
- (a) a partial remainder memory for storing the sum and carry digits;
- (b) a quotient selection logic having an adder for adding higher three bits of the sum digit to higher three bits of the carry digit, OR means for providing the OR of the fourth bits of the sum and carry digits, and quotient digit determination means for determining a next quotient digit according to the outputs of said adder and OR means;
- (c) square root arithmetic data generation means having a bit position indicator for storing the position of a bit where a quotient digit is calculated, a first quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is carry propagation from a lower position, a second quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is no carry propagation from the lower position, root multiple formation means for generating root multiples used for calculating the square root, according to the outputs of the bit position indicator and the first and second quotient digits memories, and on-the-fly digit handling means for generating a quotient digit set with carry propagation and a quotient digit set without carry propagation according to the outputs of the bit position indicator and the first and second quotient digits memories as well as the next quotient digit;
- (d) selection means for selecting one of the outputs of said square root arithmetic data generation means according to the quotient digit provided by said quotient selection logic, to provide data to be added to or subtracted from the partial remainder;
- and
- (e) a carry save adder for carrying out a calculation on the data provided by said selection means and the partial remainder stored in said partial remainder memory according to an addition/subtraction instruction from the quotient selection logic, and providing the output thereof to said partial remainder memory.
A calculation unit for calculating a square root and a division according to an iteration algorithm with a partial remainder expressed with the sum of a sum digit and carry digit, comprising:
- (a) a partial remainder memory for storing the sum and carry digits;
- (b) a quotient selection logic having an adder for adding higher three bits of the sum digit to higher three bits of the carry digit, OR means for providing the OR of the fourth bits of the sum and carry digits, and quotient digit determination means for determining a next quotient digit according to the outputs of the adder and OR means;
- (c) square root arithmetic data generation means having a bit position indicator for storing the position of a bit where a quotient digit is calculated, a first quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is carry propagation from a lower position, a second quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is no carry propagation from the lower position, root multiple formation means for generating root multiples used for calculating the square root, according to the outputs of the bit position indicator and the first and second quotient digits memories, and on-the-fly digit handling means for generating quotient digit sets according to the outputs of the bit position indicator and the first and second quotient digits memories;
- (d) a divisor digits memory for storing a divisor digit;
- (e) a division/square root selection means for selecting one of the outputs of the root multiple formation means and divisor digits memory;
- (f) summand selection means for selecting one of the outputs of said division/square root selection means according to the quotient digit provided by said quotient selection logic, to provide data to be added to or subtracted from the partial remainder;
- and
- (g) a carry save adder for carrying out a calculation on the data provided by said summand selection means and the partial remainder stored in said partial remainder memory according to an addition/subtraction instruction from the quotient selection logic, and providing the output hereof to said partial remainder memory.
A calculation unit for calculating a square root according to an iteration algorithm with a partial remainder expressed with the sum of a sum digit and carry digit, comprising:
- (a) square root arithmetic data generation means having a bit position indicator for storing the position of a bit where a quotient digit is calculated, a first quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is carry propagation from a lower position, a second quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is no carry propagation from the lower position, root multiple formation means for generating root multiples used for calculating the square root, according to the outputs of the bit position indicator and the first and second quotient digits memories, and on-the-fly digit handling means for generating quotient digit sets according to the outputs of the bit position indicator and quotient digits memories;
- (b) overlap execution means for estimating next partial remainders according to the output of said square root arithmetic data generation means and assumed quotient digits;
- (c) a selector for selecting one of the estimated partial remainders of said overlap execution means according to a determined quotient digit;
- (d) a quotient selection logic for selecting a quotient digit according to the selected partial remainder;
- and
- (e) partial remainder formation means for calculating a next partial remainder.
A calculation unit having at least a quotient selection logic, for calculating a division or square root according to a radix 2 iteration algorithm with a partial remainder expressed with the sum of a sum digit and carry digit, the quotient selection logic comprising:
- (a) an adder for adding higher three bits of the sum digit to higher three bits of the carry digit, to provide an output consisting of bits D0, D1, and D2;
- (b) OR means for providing the OR of the LSB (least significant bit) of the output of said adder and fourth bits of the sum and carry digits;
- and
- (c) quotient digit determination means for determining the next quotient digit according to the outputs of said adder and OR means.
A calculation unit having a predetermined number (at least two) of on-the-fly quotient digit decoders, for calculating a division or square root according to an iteration algorithm with a quotient digit being converted from redundant form into nonredundant form, each of the on-the-fly quotient digit decoders comprising:
- (a) a bit position indicator for storing the position of a bit where a quotient digit is calculated;
- (b) a first quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is carry propagation;
- (c) a second quotient digits memory for storing a quotient digit set of nonredundant form prepared on the assumption that there is no carry propagation;
- and
- (d) on-the-fly digit handling means for generating quotient digit sets to provide a next quotient digit,
- the calculation unit providing a quotient digit of at least two bits in one operation.
Dependencies are inferred from the claim text.