Squaring algorithm and the corresponding architecture was implemented with the aid of “Yavadunam Sutra”. Mathematical formulation of Yavadunam Sutra
If a number X is between 2n-1 and 2n then the average of 2n-1 and 2n is . If X A then 2n is chosen as radix and if X A then 2n-1 is the selected radix.
In Binary mathematics, the number can be reformulated as,
, when Radix=2n-1 (7)
, when Radix=2n (8)
The square of the number X can be obtained from equation (1) as,
Similarly the expression of X2 that can be obtained from equation (2) is given as,
Equations (3) and (4) are the mathematical formulations of Yavadunam Sutra in Binary mathematics.
The architecture of radix selection unit is shown in Fig.-2. The input bits X (of length n) is fed to the left shift register. The clock signal to the shift register is controlled by mother clock generated from a clock generator and the shifted MSB of the input. Initially the MSB is set to ‘0’.After one left shift if the MSB is ‘1’ then the AND output
Fig. 2: Architecture of Radix Selection Unit
produces ‘0’ which stops further shifting. But if the MSB is ‘0’ then the AND output produces ‘1’ which allows further shifting operation. The first subtractor is initialized by the maximum power of input bit string (the exponent of the MSB). The output of the first subtractor is the exponent which is further decremented by one by the second subtractor. The second left shift register is initialized by the input “11” which is shifted to the left by by the number of times denoted by the exponent generated from the second subtractor. X is compared with the output of the second left shift register (A). If X>A then the exponent is not needed to be incremented by the incrementer. If X A then the exponent is incremented by one. At last the incremented exponent is fed to the converter to determine the selected radix. The converter is a Barrel shifter which can shift the input bits number of times assigned by the select inputs. It takes the input generated from the incrementer which is used for select inputs. ‘1’ is loaded to the shifter which is shifted to the left as per the select inputs.
The architecture of squaring algorithm using “Yavadunam Sutra” is shown in Fig.-3. The basic building blocks of the architecture are (i) RSU, (ii) Subtractor, (iii) Add-Sub unit and (iv) Duplex squaring architecture. The architecture of RSU is shown Fig.-2. The Subtrctor architecture using “Nikhilam” sutra has been elucidated in sub-section-(3) and the architecture has been shown in Fig.-4.
Fig. 3: Architecture of squaring algorithm using Yavadunam Sutra