verilog arithmetic module

synthesiseable verilog 32-bit integer arithmetic module design space

• Target Specs

Name	Spec	Description
Clock Freq	50MHz	Only Divider & Multiplier unit dependants clock
Reset Type	Asynchronous Active-Low	-
Input Size	32-bit	-
Output Size	32-bit or 64-bit	Only Multiplier Unit has 64-bit output
Support Type	Integer	-
Support Format	Signed or Unsigned	-

• Directory_Info.

Directory	Tag
Adder	Addition/Subtraction Hardware directory
Multiplier	Multiplication Hardware directory
Divider	Division Hardware directory

---

Multiplier Algorithm

(Multiplier) * (Multiplicand) == (Product)

• Signed Booth Algorithm SD code

Q	Q-	Action
0	0	Shift Right(Signed Extension)
1	1	Shift Right(Signed Extension)
1	0	SUB Multiplier from Accumulator and Shift Right
0	1	ADD Multiplier to Accumulator and Shift Right

Example

Ex) 1101 * 0011 = 1111_0111
(-3) * 3 = (-9)

N	Accumulator	Q	Q-	Description
Ready	0000	0011	0	Initialize with A = 0, Q = Multiplicand, Q- = 0
1	0011 0001	0011 1001	0 1	SUB 1101 from Accumulator Signed Shift Right
2	0000	1100	1	Shift Right (Signed Ext)
3	1101 1110	1100 1110	1 0	ADD Accumulator to 1101 Signed Shift Right
4	1111	0111	0	Shift Right (Signed Ext)

RESULT = Accumulator + Q = 1111_0111

• Unsigned Booth Algorithm SD code

LSB of Q	Action
0	Righ Shift (With Accumulator Carry)
1	ADD Multiplier to Accumulator and Shift Right (With Accumulation Carry)

Example

Ex) 1101 * 0011 = 0010_0111
13 * 3 = 39

N	Carry	Accumulator	Q	LSB of Q	Description
Ready	0	0000	0011	1	Initialize with A = 0, Q = Multiplicand, Q- = 0
1	0 0	1101 0110	0011 1001	1 1	ADD Accumulator to 1101 Shift Right
2	1 0	0011 1001	1001 1100	1 0	ADD Accumulator to 1101 Shift Right
3	0	0100	1110	0	Shift Right
4	0	0010	0111	1	Shift Right

RESULT = Accumulator + Q = 0010_0111

---

Divider Algorithm

(Dividend) / (Divisor) == (Quotient) ... (Remainder)

• Parameter Description

  Main Register: N, Q, M, A

    N: Number of bits of dividend
    Q: Quotient
    A: Accumulator, It has (N+1) bit
    M: Divisor
  

• Restoring Division Flow

1. Initialize with Q = Dividend, M = Divisor, A = 0

2. Shift Left A, Q

3. IF MSB of A == 1, Q[0] == 0 and Restore A
   ELSE, Q[0] == 1

4. Counter update as N = N - 1

5. IF N != 0, Goto Step 2.
   ELSE, Goto Step 6.

6. DONE! (Q: Quotient, A: Remainder)

Example

1111 / 1011 = 0001 ... 0100
(15) / (11) = 1 ... 4

N	M	A	Q	Description
Ready	1011	00000	1111	Initialize
4		00001 10110 00001	1110 1110 1110	Shift Left A, Q A = A - M Q[0] = 0 and Restore A
3		00011 11000 00011	1100 1100 1100	Shift Left A, Q A = A - M Q[0] = 0 and Restore A
2		00111 11100 00111	1000 1000 1000	Shift Left A, Q A = A - M Q[0] = 0 and Restore A
1		01111 00100 00100	0000 0000 0001	Shift Left A, Q A = A - M Q[0] = 1
RESULT		0_0100	0001	A[3:0] = Remainder Q = Quotient

RESULT: Q = 0001, R = 0100

• Non-Restoring Division Flow

1. Initialize with Q = Dividend, M = Divisor, A = 0

2. IF MSB of A == 1, Shift A,Q and update A = A + M
   ELSE, Shift A,Q and update A = A - M

3. IF MSB of A == 1, Q[0] = 0
   ELSE, Q[0] = 1

4. Counter update as N = N - 1

5. IF N != 0, Goto Step 2.
   ELSE, Goto Step 6.

6. IF MSB of A == 1, update A = A + M
   ELSE, Do Nothing.

7. DONE! (Q: Quotient, A: Remainder)

Example

1111 / 1011 = 0001 ... 0100
(15) / (11) = 1 ... 4

N	M	A	Q	Description
Ready	1011	00000	1111	Initialize
4		00001 10110 10110	1110 1110 1110	SHIFT LEFT {A,Q} A = A - M Q[0] = 0
3		01101 11000 11000	1100 1100 1100	SHIFT LEFT {A,Q} A = A + M Q[0] = 0
2		10001 11100 11100	1000 1000 1000	SHIFT LEFT {A,Q} A = A + M Q[0] = 0
1		11001 00100 00100	0000 0000 0001	SHIFT LEFT {A,Q} A = A + M Q[0] = 1
LAST		00100 00100	0001 0001	MSB_A is 0, Do Nothing
RESULT		0_0100	0001	A[3:0] = Remainder Q = Quotient

RESULT: Q = 0001, R = 0100