Squaring of a binary number

Discussion in 'VHDL' started by lokesh kumar, Jul 19, 2013.

  1. lokesh kumar

    rickman Guest

    I think you didn't look at my example carefully enough. If a = 11111
    then c = 101010101 which is 9 bits. The IP is used once which removes
    the one in the msb and as you say, the next bit is a zero which is not
    changed. So we get two bits in the first step. But that still leaves
    us with a seven bit number and each further application of the IP only
    removes a single bit from the resulting value of c.

    Yes, I downloaded it and can open it, just not in Acrobat, I have an
    older copy which won't open this file, I have to use SumatraPDF reader.

    I think you mean figure 8.1 on page 132? That is what I am seeing.

    I assume you mean figure 8.2 on page 133.

    Sorry, I can follow your directions above, but I understand this less
    than you do. However, I think there is a lot not shown in Figure 8.2 on
    page 133. I guess most, if not each output bit has at least one XOR
    gate. I am guessing that they have manually "unrolled" the loop of the
    calculation and it distills to a series of XOR gates on each output. In
    fact, I seem to recall doing exactly that with a CRC computation once.
    We had to calculate CRC on some 32 bits of input at a time. I took the
    single bit calculation and applied it 32 times algebraically to produce
    a fairly messy, but accurate result. We can do that in VHDL without
    manually calculating the coefficients. We just apply the IP ANDed with
    the corresponding bit of the temp variable and the calculations will be
    implemented.

    So if you want a fully combinatorial circuit like they are describing in
    the squaring circuit of Figure 8.2 I will write a loop of combinatorial
    logic. I can only think the complication of the code you provided where
    they copy other higher order bits into the "zero" bits of c must be a
    way to simplify the circuit and save the logic of the zero bits.
    Although things like zero inputs are often optimized automatically in
    FPGA design tools making this unnecessary.
     
    rickman, Jul 21, 2013
    #21
    1. Advertisements

  2. lokesh kumar

    rickman Guest

    I almost forgot. To test the circuit will require that some examples be
    provided with solutions. Can you come up with enough examples that
    testing with those will give you confidence the circuit works correctly?
     
    rickman, Jul 21, 2013
    #22
    1. Advertisements

  3. lokesh kumar

    lokesh kumar Guest

    I think we can start with a small number like a 5-bit number. It would be easy to check.But for 163-bit, it is very difficult to check the result.So if we get an appropriate result for 5-bit then we can design 163-bit by using the same logic.As per your last message, if you can design a full combinatorial circuit for a 5-bit number by using the squaring circuit of figure 8..2, then we can check the results with several examples.If the circuit works fine then we can proceed for the implementation of 163-bit.

    We can take the reduction polynomial as F(x)= x^5 + x^2 + 1 for a 5-bit number.
     
    lokesh kumar, Jul 21, 2013
    #23
  4. lokesh kumar

    lokesh kumar Guest

    Hi Rick,

    Finally I got the logic properly. And as per your comment I am sending you some more examples. Please have a look on the logic.
    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    Example (Part-1)
    ----------------
    Suppose we consider a 5-bit number, A = 11010
    If we do the square of the number then,

    AxA = 11010
    11010
    ---------
    00000
    11010
    00000
    11010
    11010
    ---------------
    C= 101000100 (9-bit) (XOR operation is performed to add in this case, NOT the binary addition )

    But we can make it a 10-bit number by adding a zero as MSB.
    Hence we can write, C= 0101000100 (Now its a 10-bit number and the value is not changed)

    Now if we can obtain the same value of C, only by adding adding zeros between all the bits of A.
    In the example, A = 11010
    So after adding zeros between all the bits, then we will get

    1 0 1 0 0 0 1 0 0
    | | | |

    It is the value of C that we calculated earlier. Its of 9-bit.
    But we can add one extra zero at the MSB to make it 0101000100 ( Now it is of 10-bits)

    Or we can directly write

    0 1 0 1 0 0 0 1 0 0
    | | | | |
    Like this we do not need to multiply A, 2 times if we need to calculate thesquare.
    We can simply add zeros between all the bits of A to get the square.
    --------------------------------------------------------------------------------
    Step-1 (For design)

    So in general lets take

    A = a4a3a2a1a0 ( 5-bit number)

    If we take the square of the number, then we will get

    C = c9 c8 c7 c6 c5 c4 c3 c2 c1 c0 ( it is of 10 bit)

    C = 0 a4 0 a3 0 a2 0 a1 0 a0 ( This is how zeros are added and value of C is calculate)

    -----------------------------------------------------------------------------------------------
    Example (part-2)
    ----------------
    Now our main aim is to reduce the 10-bit result to 5-bit.
    For that purpose, we use reduction polynomial (it is a standard value)

    The reduction polynomial for a 5-bit number is : F(x) = x^5 + x^2 + 1

    We can write the reduction polynomial as 100101 in binary form.
    To reduce,

    0101000100 (10-bit number, that we obtained)
    10101 (reduction polynomial)
    ---------------
    0000010100 (XOR operation)

    Hence the first five MSB are zero, then if we do not consider these bits. Then it is a 5-bit number. It is our final result
    --------------------------------------------------------------------------------------------------------
    Step-2 (For design)

    The value of reduction polynomial is = 100101

    We have already got the 10-bit result.
    We have to do the XOR operation of the 10-bit result with the reduction polynomial in the same way (as shown is the example)

    For that purpose, we need to see if the MSB of the 10-bit result is "1" or not. If it is "1" then we will do the XOR operation with the reduction polynomial.
    If the MSB of 10-bit number is zero, then we need to check the second MSB of it. If the second MSB is "1" then we need to do the XOR operation there.

    We need to do this loop till we obtain the 5-bit result.

    Now this is the final result.
    --------------------------------------------------------------------------------
    I have explained you the logic with an example. I have started with an example. I have used example (1st part) to show the result after squaring. And in Step-1, I have described the general logic. In example (part-2) , I haveshown the reduction of the result to 5-bit. And in Step-2, I have providedthe general logic.
    So basically we need to follow both step-1 and step-2.


    Now I hope everything is clear. Please help me to design the code for it now. Hope this time we will be able to do it.

    Many Thanks!
    Lokesh
     
    lokesh kumar, Jul 22, 2013
    #24
  5. lokesh kumar

    lokesh kumar Guest

    Example (Part-1)
    ----------------
    Suppose we consider a 5-bit number, A = 11010
    If we do the square of the number then,

    AxA = 11010
    11010
    ---------
    00000
    11010
    00000
    11010
    11010
    ---------------
    C= 101000100 (9-bit) (XOR operation is performed to add in this case, NOT the binary addition )

    But we can make it a 10-bit number by adding a zero as MSB.
    Hence we can write, C= 0101000100 (Now its a 10-bit number and the value is not changed)

    Now if we can obtain the same value of C, only by adding adding zeros between all the bits of A.
    In the example, A = 11010
    So after adding zeros between all the bits, then we will get

    1 0 1 0 0 0 1 0 0
    | | | |

    It is the value of C that we calculated earlier. Its of 9-bit.
    But we can add one extra zero at the MSB to make it 0101000100 ( Now it is of 10-bits)

    Like this we do not need to multiply A, 2 times if we need to calculate the square.
    We can simply add zeros between all the bits of A to get the square.
    --------------------------------------------------------------------------------
    Step-1 (For design)

    So in general lets take

    A = a4a3a2a1a0 ( 5-bit number)

    If we take the square of the number, then we will get

    C = c9 c8 c7 c6 c5 c4 c3 c2 c1 c0 ( it is of 10 bit)

    C = 0 a4 0 a3 0 a2 0 a1 0 a0 ( This is how zeros are added and value of C is calculate)

    -----------------------------------------------------------------------------------------------
    Example (part-2)
    ----------------
    Now our main aim is to reduce the 10-bit result to 5-bit.
    For that purpose, we use reduction polynomial (it is a standard value)

    The reduction polynomial for a 5-bit number is : F(x) = x^5 + x^2 + 1

    We can write the reduction polynomial as 100101 in binary form.
    To reduce,

    0101000100 (10-bit number, that we obtained)
    10101 (reduction polynomial)
    ---------------
    0000010100 (XOR operation)

    Hence the first five MSB are zero, then if we do not consider these bits. Then it is a 5-bit number. It is our final result
    --------------------------------------------------------------------------------------------------------
    Step-2 (For design)

    The value of reduction polynomial is = 100101

    We have already got the 10-bit result.
    We have to do the XOR operation of the 10-bit result with the reduction polynomial in the same way (as shown is the example)

    For that purpose, we need to see if the MSB of the 10-bit result is "1" or not. If it is "1" then we will do the XOR operation with the reduction polynomial.
    If the MSB of 10-bit number is zero, then we need to check the second MSB of it. If the second MSB is "1" then we need to do the XOR operation there.

    We need to do this loop till we obtain the 5-bit result.

    Now this is the final result. How can I design the code? Please help me to implement.

    Many Thanks!
    Lokesh
     
    lokesh kumar, Jul 22, 2013
    #25
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.