Multiplier, especially a serial bit multiplier, free from internal overflow, and method for preventing internal overflow in a multiplier
AssigneeFrance Telecom
InventorsAlain Wittmann, Freddy Balestro
Life of this patent
Estimating the term…
Abstract
A multiplier for least significant bit first multiplication of a multiplicand coded on n bits by a multiplier coefficient includes a processor which, for each bit of the decimal part of the multiplier coefficient between the least significant bit and the most significant bit, calculates the sum of rank n+1 obtained from partial products of the bit in question with the n bits of the multiplicand and from corresponding sums calculated for the preceding bit or bits of the multiplier coefficient. This prevents internal overflow of the multiplier.
Claims17
Multiplier for least significant bit first multiplication of a multiplicand coded on n bits by a multiplier coefficient, said multiplier comprising processor means adapted for each bit of the decimal part of said multiplier coefficient between said least significant bit and a most significant bit to actually calculate the sum of rank n+1 obtained from partial products of said bit in question and the n bits of said multiplicand and from corresponding sums calculated for the preceding bit or bits of said multiplier coefficient, wherein said processor means comprises calculation means for calculating successive carries associated with sums of successive ranks, and wherein said processor means calculates, for each bit in question of the multiplier coefficient, the sum of rank n+1 from a complemented carry of rank n, in order to prevent internal overflow of said multiplier.
Multiplier according to claim 7 wherein a first section of said multiplier has a synchronization input for receiving a synchronization word in which each change of state of one bit corresponds to the arrival of the most significant bit of said multiplicand at the input of said first section of said multiplier, each multiplier section includes a synchronization time-delay circuit between an input and a corresponding synchronization output, the synchronization output of a multiplier section being connected to the synchronization input of a next multiplier section, the carry output and the first sum output of said adder are complemented, said elementary processor means of each multiplier section includes, in addition to said time-delay circuit connected to said complemented carry outputs:
- an exclusive-OR gate having one input connected to an output of said carry time-delay circuit and another input connected to the synchronization input of said multiplier section and one output connected to one input of an AND gate whose output is connected to said carry input of said adder;
- and
- a NOT-exclusive-OR gate having one input connected to the complemented first sum output of said adder, another input connected to the synchronization input of said multiplier section and an output connected to an input of said duplexer, the other input of said duplexer is connected to the output of said carry time-delay circuit, the output of said duplexer is connected to the output of said multiplier section by an invertor, and a control input of said duplexer and another input of said AND gate are connected to the output of said synchronization time-delay circuit.
Method for preventing internal overflow of a multiplier connected to a data transmission medium and adapted to carry out least significant bit first multiplication of a multiplicand coded on n bits with a multiplier coefficient, in which method, for each bit of the decimal part of the multiplier coefficient between the least significant bit and the most significant bit, there is calculated in said multiplier the sum of rank n+1 obtained from partial products of said bit in question with the n bits of said multiplicand and from corresponding sums calculated for the preceding bit or bits of said multiplier coefficient, and wherein the sum of rank n+1 is calculated for each bit in question of said multiplier coefficient from the complemented carry of rank n.
Dependencies are inferred from the claim text.