Signed multiplication

Discussion in 'VHDL' started by knight, Sep 8, 2008.

  1. knight

    knight Guest

    hi

    Can anyone tell me how can i multiply two signed numbers in FPGA.
    How the logic is really implemented..
    ie., if i multiply two signed numbers are they multiplying the
    positive number and the 2's complement (if the number is negative)
    directly ..?
    Or are they really changing the negative number to positive and do
    normal multiplication and appends the sign accordingly..?
    And is the positive number, and its 2's complement form same always...?
     
    knight, Sep 8, 2008
    #1
    1. Advertising

  2. knight

    Tricky Guest

    On 8 Sep, 07:11, knight <> wrote:
    > hi
    >
    > Can anyone tell me how can i multiply two signed numbers in FPGA.
    > How the logic is really implemented..
    > ie., if i multiply two signed numbers are they multiplying the
    > positive number and the 2's complement (if the number is negative)
    > directly ..?
    > Or are they really changing the negative number to positive and do
    > normal multiplication and appends the sign accordingly..?
    > And is the positive number, and its 2's complement form same always...?


    Multiplication, at it's heart, is nothing more than a sum of all of
    the powers in any given number. The same holds for digital
    multiplication. Lets first look at unsigned multiplication:

    13 * 7 (1101 x 0111)

    All that happens is you add up all of the individual powers of two
    multiplication, which in binary is a simple bit shift to the left.

    0 1 1 1 0 0 0 (8x = 2^3) 1
    0 1 1 1 0 0 (4x = 2^2) 1
    0 0 0 0 0 (2x = 2^1) 0
    + 0 1 1 1 (1x = 2^0) 1
    ----------------
    0 1 0 1 1 0 1 1 = 91

    When multiplying two binary numbers, the number of bits required to
    represent the result is always length(a) + length(b).
    The rules above still carry through when using two's compliment. Lets
    have a look at the same two binary numbers in twos compliment.

    7 x -3 (0111 x 1101)
    In twos compliment though, you have to remember to extend the sign bit
    forward.

    0 0 0 0 0 0 0 0 (8x) 0
    1 1 1 1 0 1 0 0 (4x) 1
    1 1 1 1 1 0 1 0 (2x) 1
    + 1 1 1 1 1 1 0 1 (1x) 1
    ------------------
    1 1 1 1 0 1 0 1 1 = -21.
    |
    |
    -------- We only have an 8 bit result, so bits above bit 7 are
    removed.

    Fixed point multiplication works in exactly the same way, except that
    an m.n x a.b number has a result of length (m + a).(n + b) (the total
    number of bits is still the sum of the totals). This means some
    additions require a bit shift to the right rather than left (ie. 2^-n)

    FPGA's though, often have integrated multipliers and you dont have to
    worry about resourcing a large number of adders. The easiest form of
    multiplaction in VHDL is:

    library ieee.
    use ieee.numeric_std.all

    .....
    .....
    .....

    signal A, B : unsigned(7 downto 0); --or signed if you wish
    signal R : unsigned(15 downto 0); --or signed if you wish, if A
    and B are signed
    begin

    process(clk)
    begin
    if rising_edge(clk) then
    R <= A * B;
    end if;
    end process;

    ....
    ....

    Any good synthesiser should assign this to an onboard multiplier (if
    it fits - its common for internal multipliers to be 9/18/36 bits or
    less). Otherwise it should have knowledge of a multiplier it can build
    out of logic.

    Also remember though, that multiplying by 2^n is simply a bit shift,
    so you dont need to use any logic for that. You simply append 0's or
    remove bits.
     
    Tricky, Sep 8, 2008
    #2
    1. Advertising

  3. knight

    Tricky Guest

    On 8 Sep, 07:11, knight <> wrote:
    > hi
    >
    > Can anyone tell me how can i multiply two signed numbers in FPGA.
    > How the logic is really implemented..
    > ie., if i multiply two signed numbers are they multiplying the
    > positive number and the 2's complement (if the number is negative)
    > directly ..?
    > Or are they really changing the negative number to positive and do
    > normal multiplication and appends the sign accordingly..?
    > And is the positive number, and its 2's complement form same always...?


    Multiplication, at it's heart, is nothing more than a sum of all of
    the powers in any given number. The same holds for digital
    multiplication. Lets first look at unsigned multiplication:

    13 * 7 (1101 x 0111)

    All that happens is you add up all of the individual powers of two
    multiplication, which in binary is a simple bit shift to the left.

    0 1 1 1 0 0 0 (8x = 2^3) 1
    0 1 1 1 0 0 (4x = 2^2) 1
    0 0 0 0 0 (2x = 2^1) 0
    + 0 1 1 1 (1x = 2^0) 1
    ----------------
    0 1 0 1 1 0 1 1 = 91

    When multiplying two binary numbers, the number of bits required to
    represent the result is always length(a) + length(b).
    The rules above still carry through when using two's compliment. Lets
    have a look at the same two binary numbers in twos compliment.

    7 x -3 (0111 x 1101)
    In twos compliment though, you have to remember to extend the sign bit
    forward.

    0 0 0 0 0 0 0 0 (8x) 0
    1 1 1 1 0 1 0 0 (4x) 1
    1 1 1 1 1 0 1 0 (2x) 1
    + 1 1 1 1 1 1 0 1 (1x) 1
    ------------------
    1 1 1 1 0 1 0 1 1 = -21.
    |
    |
    -------- We only have an 8 bit result, so bits above bit 7 are
    removed.

    Fixed point multiplication works in exactly the same way, except that
    an m.n x a.b number has a result of length (m + a).(n + b) (the total
    number of bits is still the sum of the totals). This means some
    additions require a bit shift to the right rather than left (ie. 2^-n)

    FPGA's though, often have integrated multipliers and you dont have to
    worry about resourcing a large number of adders. The easiest form of
    multiplaction in VHDL is:

    library ieee.
    use ieee.numeric_std.all

    .....
    .....
    .....

    signal A, B : unsigned(7 downto 0); --or signed if you wish
    signal R : unsigned(15 downto 0); --or signed if you wish, if A
    and B are signed
    begin

    process(clk)
    begin
    if rising_edge(clk) then
    R <= A * B;
    end if;
    end process;

    ....
    ....

    Any good synthesiser should assign this to an onboard multiplier (if
    it fits - its common for internal multipliers to be 9/18/36 bits or
    less). Otherwise it should have knowledge of a multiplier it can build
    out of logic.

    Also remember though, that multiplying by 2^n is simply a bit shift,
    so you dont need to use any logic for that. You simply append 0's or
    remove bits.
     
    Tricky, Sep 8, 2008
    #3
  4. knight

    knight Guest

    >On Sep 8, 2:12 pm, Tricky <> wrote:

    Hi
    thanks for the insight
    it was very useful
    But i still have some doubts



    > 7 x -3 (0111 x 1101)
    > In twos compliment though, you have to remember to extend the sign bit
    > forward.
    >
    > 0 0 0 0 0 0 0 0 (8x) 0
    > 1 1 1 1 0 1 0 0 (4x) 1
    > 1 1 1 1 1 0 1 0 (2x) 1
    > + 1 1 1 1 1 1 0 1 (1x) 1
    > ------------------
    > 1 1 1 1 0 1 0 1 1 = -21.
    > |
    > |
    > -------- We only have an 8 bit result, so bits above bit 7 are
    > removed.




    In this case why did you append 4 bits to the left..?
    Why cant it be 1 or 2..?

    Suppose i am multiplying -3 and 3 (appending only 1 bit)
    that means 00011 * 11101
    So the result is 0001010111.
    In this case how can we determine which all bits we need to skip..?
    And i think if we change the number of bits appended, the result is
    likely to be changed.. and the 2's complement doesn't yield the
    expected result.
    Does that mean there is no direct way to realize signed multiplication
    in hardware..?,
    rather we should changed signed to unsigned and multiply and put back
    the sign for the result..?



    > Any good synthesiser should assign this to an onboard multiplier (if
    > it fits - its common for internal multipliers to be 9/18/36 bits or
    > less). Otherwise it should have knowledge of a multiplier it can build
    > out of logic.



    For me only 16 bits are required for signed representation..
    But why these multipliers start of multiples of 9..?


    Thanks for the reply
     
    knight, Sep 8, 2008
    #4
  5. knight

    knight Guest

    >On Sep 8, 2:12 pm, Tricky <> wrote:

    Hi
    thanks for the insight
    it was very useful
    But i still have some doubts



    > 7 x -3 (0111 x 1101)
    > In twos compliment though, you have to remember to extend the sign bit
    > forward.
    >
    > 0 0 0 0 0 0 0 0 (8x) 0
    > 1 1 1 1 0 1 0 0 (4x) 1
    > 1 1 1 1 1 0 1 0 (2x) 1
    > + 1 1 1 1 1 1 0 1 (1x) 1
    > ------------------
    > 1 1 1 1 0 1 0 1 1 = -21.
    > |
    > |
    > -------- We only have an 8 bit result, so bits above bit 7 are
    > removed.




    In this case why did you append 4 bits to the left..?
    Why cant it be 1 or 2..?

    Suppose i am multiplying -3 and 3 (appending only 1 bit)
    that means 00011 * 11101
    So the result is 0001010111.
    In this case how can we determine which all bits we need to skip..?
    And i think if we change the number of bits appended, the result is
    likely to be changed.. and the 2's complement doesn't yield the
    expected result.
    Does that mean there is no direct way to realize signed multiplication
    in hardware..?,
    rather we should changed signed to unsigned and multiply and put back
    the sign for the result..?



    > Any good synthesiser should assign this to an onboard multiplier (if
    > it fits - its common for internal multipliers to be 9/18/36 bits or
    > less). Otherwise it should have knowledge of a multiplier it can build
    > out of logic.



    For me only 16 bits are required for signed representation..
    But why these multipliers start of multiples of 9..?


    Thanks for the reply
     
    knight, Sep 8, 2008
    #5
  6. knight

    Muzaffer Kal Guest

    On Mon, 8 Sep 2008 04:10:55 -0700 (PDT), knight <>
    wrote:

    >>On Sep 8, 2:12 pm, Tricky <> wrote:

    >
    >Hi
    >thanks for the insight
    >it was very useful
    >But i still have some doubts
    >
    >
    >
    >> 7 x -3 (0111 x 1101)
    >> In twos compliment though, you have to remember to extend the sign bit
    >> forward.
    >>
    >> 0 0 0 0 0 0 0 0 (8x) 0
    >> 1 1 1 1 0 1 0 0 (4x) 1
    >> 1 1 1 1 1 0 1 0 (2x) 1
    >> + 1 1 1 1 1 1 0 1 (1x) 1
    >> ------------------
    >> 1 1 1 1 0 1 0 1 1 = -21.
    >> |
    >> |
    >> -------- We only have an 8 bit result, so bits above bit 7 are
    >> removed.

    >
    >
    >
    >In this case why did you append 4 bits to the left..?
    >Why cant it be 1 or 2..?
    >
    >Suppose i am multiplying -3 and 3 (appending only 1 bit)
    >that means 00011 * 11101
    >So the result is 0001010111.
    >In this case how can we determine which all bits we need to skip..?
    >And i think if we change the number of bits appended, the result is
    >likely to be changed.. and the 2's complement doesn't yield the
    >expected result.
    >Does that mean there is no direct way to realize signed multiplication
    >in hardware..?,


    You need to sign extend to the size of the result for two's complement
    multiplication work as expected for signed numbers. After the
    multiplication you need to use the lower 2N bits for the result. So
    011x101 (3x-3) should be treated as 000011x111101 which gives the
    result 110111 6 bit result which is the expected outcome ie -9 in 6
    bits.
     
    Muzaffer Kal, Sep 8, 2008
    #6
  7. knight

    rickman Guest

    On Sep 8, 12:58 pm, Muzaffer Kal <> wrote:
    > On Mon, 8 Sep 2008 04:10:55 -0700 (PDT), knight <>
    > wrote:
    >
    >
    >
    > >>On Sep 8, 2:12 pm, Tricky <> wrote:

    >
    > >Hi
    > >thanks for the insight
    > >it was very useful
    > >But i still have some doubts

    >
    > >> 7 x -3 (0111 x 1101)
    > >> In twos compliment though, you have to remember to extend the sign bit
    > >> forward.

    >
    > >>    0 0 0 0 0 0 0 0    (8x) 0
    > >>    1 1 1 1 0 1 0 0    (4x) 1
    > >>    1 1 1 1 1 0 1 0    (2x) 1
    > >> +  1 1 1 1 1 1 0 1    (1x) 1
    > >> ------------------
    > >> 1  1 1 1 0 1 0 1 1   = -21.
    > >> |
    > >> |
    > >> -------- We only have an 8 bit result, so bits above bit 7 are
    > >> removed.

    >
    > >In this case why did you append 4 bits to the left..?
    > >Why cant it be 1 or 2..?

    >
    > >Suppose i am  multiplying -3 and 3 (appending only 1 bit)
    > >that means 00011 * 11101
    > >So the result is 0001010111.
    > >In this case how can we determine which all bits we need to skip..?
    > >And i think if we change the number of bits appended, the result is
    > >likely to be changed.. and the 2's complement doesn't yield the
    > >expected result.
    > >Does that mean there is no direct way to realize signed multiplication
    > >in hardware..?,

    >
    > You need to sign extend to the size of the result for two's complement
    > multiplication work as expected for signed numbers. After the
    > multiplication you need to use the lower 2N bits for the result. So
    > 011x101 (3x-3) should be treated as 000011x111101 which gives the
    > result 110111 6 bit result which is the expected outcome ie -9 in 6
    > bits.


    If you are using signed numbers, you only need 2n-1 bits to hold the
    result.

    Rick
     
    rickman, Sep 8, 2008
    #7
  8. knight

    jeppe

    Joined:
    Mar 10, 2008
    Messages:
    348
    Location:
    Denmark
    jeppe, Sep 8, 2008
    #8
  9. knight

    Muzaffer Kal Guest

    On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <>
    wrote:

    >On Sep 8, 12:58 pm, Muzaffer Kal <> wrote:
    >> You need to sign extend to the size of the result for two's complement
    >> multiplication work as expected for signed numbers. After the
    >> multiplication you need to use the lower 2N bits for the result. So
    >> 011x101 (3x-3) should be treated as 000011x111101 which gives the
    >> result 110111 6 bit result which is the expected outcome ie -9 in 6
    >> bits.

    >
    >If you are using signed numbers, you only need 2n-1 bits to hold the
    >result.
    >
    >Rick


    Have you considered the most negative number multiplied by itself?
    Unless you saturate to most positive number that result doesn't fit to
    2n-1 bits.
     
    Muzaffer Kal, Sep 9, 2008
    #9
  10. knight

    Tricky Guest


    >
    > For me only 16 bits are required for signed representation..
    > But why these multipliers start of multiples of 9..?
    >
    > Thanks for the reply


    Im not 100% sure exactly why they chose 9/18/36, but I think it has
    something to do with the fact that many of them allow you to
    accumulate before multiplying (8bits + 8bits = 9 bit result).

    Dont worry about having exact multiples of 9. If you dont append 0s
    (for unsigned multiplication) or the sign bit (for signed
    multiplication) the synthesiser will.
     
    Tricky, Sep 9, 2008
    #10
  11. knight

    rickman Guest

    On Sep 9, 3:33 am, Muzaffer Kal <> wrote:
    > On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <>
    > wrote:
    >
    > >On Sep 8, 12:58 pm, Muzaffer Kal <> wrote:
    > >> You need to sign extend to the size of the result for two's complement
    > >> multiplication work as expected for signed numbers. After the
    > >> multiplication you need to use the lower 2N bits for the result. So
    > >> 011x101 (3x-3) should be treated as 000011x111101 which gives the
    > >> result 110111 6 bit result which is the expected outcome ie -9 in 6
    > >> bits.

    >
    > >If you are using signed numbers, you only need 2n-1 bits to hold the
    > >result.

    >
    > >Rick

    >
    > Have you considered the most negative number multiplied by itself?
    > Unless you saturate to most positive number that result doesn't fit to
    > 2n-1 bits.


    I think you are confused. Try the math. It fits...

    -8 x -8 = -64 === 1000 x 1000 = 1000000

    or even simpler

    -2 x -2 = -4 === 10 x 10 = 100

    The reason this fits is because in an n bit signed number there are
    n-1 significant bit plus a sign bit. Multiplied, this gives 2(n-1)
    significant bits plus a sign bit or 2n-1 rather than 2n bit to hold
    the full word.

    Rick
     
    rickman, Sep 9, 2008
    #11
  12. knight

    rickman Guest

    On Sep 9, 4:21 am, Tricky <> wrote:
    > > For me only 16 bits are required for signed representation..
    > > But why these multipliers start of multiples of 9..?

    >
    > > Thanks for the reply

    >
    > Im not 100% sure exactly why they chose 9/18/36, but I think it has
    > something to do with the fact that many of them allow you to
    > accumulate before multiplying (8bits + 8bits = 9 bit result).
    >
    > Dont worry about having exact multiples of 9. If you dont append 0s
    > (for unsigned multiplication) or the sign bit (for signed
    > multiplication) the synthesiser will.


    The fact that Xilinx matches multipliers to block RAMs (which come in
    multiples of 9 bits) would make you think it has more to do with some
    chip level efficiency improvements. It may just be that they are
    sharing the I/O routing, or it may be that they are sharing some of
    the logic. Can you use both the block rams and the multipliers?
    Maybe it just ends up being a packing convenience based on the
    symmetry of the routing for both.

    Rick
     
    rickman, Sep 9, 2008
    #12
  13. knight

    Muzaffer Kal Guest

    On Tue, 9 Sep 2008 07:47:08 -0700 (PDT), rickman <>
    wrote:

    >On Sep 9, 3:33 am, Muzaffer Kal <> wrote:
    >> On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <>
    >> wrote:
    >>
    >> >On Sep 8, 12:58 pm, Muzaffer Kal <> wrote:
    >> >> You need to sign extend to the size of the result for two's complement
    >> >> multiplication work as expected for signed numbers. After the
    >> >> multiplication you need to use the lower 2N bits for the result. So
    >> >> 011x101 (3x-3) should be treated as 000011x111101 which gives the
    >> >> result 110111 6 bit result which is the expected outcome ie -9 in 6
    >> >> bits.

    >>
    >> >If you are using signed numbers, you only need 2n-1 bits to hold the
    >> >result.

    >>
    >> >Rick

    >>
    >> Have you considered the most negative number multiplied by itself?
    >> Unless you saturate to most positive number that result doesn't fit to
    >> 2n-1 bits.

    >
    >I think you are confused. Try the math. It fits...
    >
    >-8 x -8 = -64 === 1000 x 1000 = 1000000
    >
    >or even simpler
    >
    >-2 x -2 = -4 === 10 x 10 = 100


    I know you're confused. When you square -8 you get +64 and when you
    multiply -2 by itself you get +4. Continuing with the simpler case if
    you have two bit two's complement numbers and you multiply the most
    negative number (ie -2) by itself the result has to be a positive
    number and one should be able to represent and interpret it thus. So
    -2 x -2 == 10 x 10 = +4 == 0100. If you drop the leading zero and
    claim that the result fits into 3 bits as opposed to 4 needed then you
    should interpret it as a 3 bit two's complement number which makes 100
    a negative number ie -4 which is the wrong result.

    The confusing issue is that two's complement numbers don't have a
    symmetrical distribution in the number line. The most negative two's
    complement number of any size doesn't have an equivalent in the
    positive domain so one can not describe it in the same size. And when
    one squares the most negative number the result doesn't fit into 2n-1
    but fits into 2n nicely.
     
    Muzaffer Kal, Sep 9, 2008
    #13
  14. knight

    KJ Guest

    On Sep 9, 10:47 am, rickman <> wrote:
    >
    > I think you are confused.  Try the math.  It fits...
    >
    > -8 x -8 = -64  ===  1000 x 1000 = 1000000
    >
    > or even simpler
    >
    > -2 x -2 = -4 === 10 x 10 = 100
    >


    I guess I'll have to get a new calculator. It tells me...
    -8 x -8 = 64 (not -64)
    -2 x -2 = 4 (not -4)

    But if my calculator is correct, then the signed representations would
    need 7 bits to represent +64 and 3 bits to represent +4 in a signed
    notation.

    KJ
     
    KJ, Sep 9, 2008
    #14
  15. knight

    KJ Guest

    On Sep 9, 11:09 am, KJ <> wrote:

    > then the signed representations would
    > need 7 bits to represent +64 and 3 bits to represent +4 in a signed
    > notation.
    >


    Make that 8 bits to represent +64 and 4 bits to represent +4 in signed
    notation...sigh...

    +64 = 01000000
    +4 = 0100

    KJ
     
    KJ, Sep 9, 2008
    #15
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Weng Tianxiang
    Replies:
    4
    Views:
    3,107
    Weng Tianxiang
    Apr 7, 2005
  2. Christopher Dyken

    32x32 and 64x64 signed integer multiplication

    Christopher Dyken, Feb 17, 2004, in forum: C Programming
    Replies:
    18
    Views:
    1,440
    glen herrmannsfeldt
    Feb 24, 2004
  3. priya

    signed multiplication

    priya, Nov 16, 2006, in forum: VHDL
    Replies:
    2
    Views:
    1,678
    priya
    Nov 17, 2006
  4. Andy
    Replies:
    1
    Views:
    496
    Mike Treseler
    Sep 29, 2008
  5. William Hughes
    Replies:
    13
    Views:
    1,237
    Ben Bacarisse
    Mar 15, 2010
Loading...

Share This Page