# signed multiplier & radix-4 signed multiplier
> 說例: 4bit x 4bit用2bit x 2bit(Radix-4)實現
### 4bit x 4bit
> (-5) x (7) = (-35)

    1011
x)  0111
========
11111011
1111011
111011
00000
======== 
11011101

### 2bit x 2bit算4次(radix-4)
> 解說

$數學式：A\times B=((A_1)2^1+(A_0)2^0))\times((B_1)2^1+(B_0)2^0)\\
=(A_1B_1)2^2+((A_1B_0)+(A_0B_1))2^1+(A_0B_0)2^0$

因此我們可以先算出所以2次冪前面的係數，最後再和起來
其中，$A_1和B_1$分別為A與B的高位元，運算時為有號乘法

> (-5) x (7) = (-35)
* 原本算法

        1011
    x)  0111
    ========
    11111011
    1111011
    111011
    00000
    ========
    11011101
    --------
        (-35)

- 分解成四組，按照空間位置可以分為(1)(2)(3)(4)

    (原本)

        10|11
    x)  01|11
    =========
    (分解)

    (1)      (2)        (3)        (4)
        10|      10|          |11        |11
    x)  01|  x)    |11  x)  01|    x)    |11
    =======  =========  =========  =========

- 整理一下，順便算出結果
<ps.>(1)(2)(3)為有號乘法，(4)為無號乘法

    (1)     (2)     (3)     (4)     |  (total sum)
        10      10      11      11  |   
    x)  01  x)  11  x)  01  x)  11  |  (4) 00001001
    ======  ======  ======  ======  |  (3) 000011
      1110    1110    0011    0011  |  (2) 111010
      000     110     000     011   |  (1) 1110
    ======  ======  ======  ======  |   ===========
      1110    1010    0011    1001  |      11011101
    ------  ------  ------  ------  |   -----------
       (-2)    (-6)    ( 3)    ( 9) |          (-35)

- 以數學式理解
- 數學式：$A\times B=(A_1B_1)2^2+((A_1B_0)+(A_0*B_1))2^1+(A_0B_0)2^0$
- 代數：$(-5)\times(7)=(-2)2^2+((-6)+(3))2^1+(9)2^0$
- 數學式可以另類拆解
- (前提)二補數回顧
- -5取2補數
- 法1：
- $(5)_10=(0101)_2$
- 取二補：$(1010)_1c=(1011)_2c$
- 法2：
- 用減的：$-(1)2^3+(0)2^2+(1)2^1+(1)2^0=-8+2+1=-5$
- 得二補：$(1011)_2c$
- 代數by法2：
- $-5=-(1)2^3+(0)2^2+(1)2^1+(1)2^0\\
=(-(1)2^1+(0))2^2+((1)2^1+(1))2^0\\
=(-2+0)2^2+(2+1)2^0\\
=(-2+0)4^1+(2+1)4^0
=(-2)4^1+(3)4^0$
- $7 = (-(0)2^1+(1)2^0)4^2+((1)2^1+(1)2^0)4^0\\
=(0+1)4^1+(2+1)4^0\\
=(1)4^1+(3)4^0$
- $(-5)\times(7)=((-2)4^1+(3)4^0)\times((1)4^1+(3)4^0)\\
(-2)4^2+((-6)+(3))4^1+(9)4^0$
- 因此證明一件事，我們可以切兩個bit一起看，來獲得上述數學式中的係數
- 然後我們將數學式做因式分解
- $(-5)\times(7)=(-2)4^2+((-6)+(3))4^1+(9)4^0\\
=((-2)4^1+(3)4^0)\times((1)4^1+(3)4^0)$
- 後來發現原來這個就是傳說中的radix-4表示法==
- 所以我們可以根據這四個係數直接使用"另類乘法"

(Radix-4的另類乘法)

    (-2)( 3)
x)  ( 1)( 3)
===========
     -6   9
  -2  3
===============================
(-2)*4^2+(-6+3)*4^1+(9)*4^0=(-35)