Take Home Exam Solutions

lOMoARcPSD|24554605
Take Home Exam - Solutions
Computer Arithmetic (Technische Universiteit Delft)
Studeersnel wordt niet gesponsord of ondersteund door een hogeschool of universiteit

Gedownload door Nishad Mandlik (mandliksg@gmail.com)
lOMoARcPSD|24554605
ET4170 Take Home Exam 2021

Pietro Pennestrì s2382660
April 2021
Contents
1 Solution of Problem 1 2
5.1 POINT A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.1 POINT A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.2 POINT B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.3 POINT C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.4 POINT D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7 Solution Problem 7 23
10 Appendix 34
10.1 Commonly used sub-circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
10.2 Step by Step computation of the non restoring square root: Python
Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
10.3 Modulo 9 adder & multiplier : test of correctness . . . . . . . . . . . . . 40
1
lOMoARcPSD|24554605
Take Home Exam 2021 ET4170 P. Pennestrì s2382660
1 Solution of Problem 1
r=5, α= 3 , β=4
α β
λ≥ , µ≥
r−1 r−1
λ=µ=1 =⇒ ti+1 ∈ {−1; 0; 1}
To compute the range of the comparison constants, the formula given in “Gen-
eralized Signed-Digit Number Systems” by B. Paharmi is used:
kr − (α − λ) ≤ Ck ≤ (k − 1)r + β − µ + 1
C1min = 5 − (3 − 1) = 3
=⇒ 3 ≤ C1 ≤ 4
C1max = 4 − 1 + 1 = 4
C0min = 3 − 4 = −1
=⇒ −2 ≤ C0 ≤ −1
C0max = −5 + 4 − 1 + 1 = −1
Finally, the comparison constants are within the following ranges:
C−1 = ∞ ; C0 = −1 ; 3 ≤ C1 ≤ 4 ; C2 = +∞
Whenever possible, it is convenient, to choose comparison constants as pow-

ers of 2:
C0 = −1 C1 = 4
The transfering rule is
ti+1 = 1 , if pi ≥ C1
ti+1 = −1 , if pi < C0
In the following, the logic equations which define the transfer ti+1 are reported.
Let pi be expressed as:
a b c d e
pi = ↑ ↑ (5 bit 2′ s complement)
MSB LSB
Point A
For the generate signals g1 , g−1 , the logic equations are:
g1 = ā(b ∨ c)
g−1 = ab̄ + ac̄ + ad¯ + aē

If g1 = 1 then ti+1 = 1 else if g−1 = 1 then ti+1 = −1.
2
lOMoARcPSD|24554605
Point B
The quantity si is computed as the sum of two 4 bits number and a 5 bit number
(pi ).
si = wi + ti = pi − 5ti+1 + ti (1)
Any 5 bit number can be expressed in the form:
(abcde)2 = (abcd)2 + (abcd)2 + (000e)2 (2)
The addition in equation (1) can be computed as the sum of only 4 bits numbers.
The dot reduction tree is depicted in Figure 1 (Dadda’s approach used).
pi
- 5 ti+1
4 HA ti
3 FA + 1 HA
3 FA + 1 HA
4 bits CPA
Adder
Figure 1: Dot notation of sum si
3
lOMoARcPSD|24554605
[a]
The system has the following dynamic range:
Smallest possible number : -16 x 15
2
x 13
= −1560
Largest possible numberr: 1559
The efficiency ϵ of the system is
RNS ( 16 | 15 | 13 )
4Bit 4Bit 4Bit
16 × 15 × 13
ε= ≈ 76.19%
212 − 1
[b]
x=60 -> (12 | 0 | 8)

RNS(16|15|13)
y=-35 -> (13 | 10 | 4)

RNS(16|15|13)
[c]
RNS ( 16 | 15 | 13 )
x 12 0 8
y 13 10 4
(x+y) 9 10 12
(x-y) 15 5 4
(x.y) 12 0 6
4
lOMoARcPSD|24554605
[d]
The structure of the described adder is the following:
MOD 16 MOD 15 MOD 13 MOD 16 MOD 15 MOD 13
4
4 4 4 4
4 4 4
MOD MOD MOD

16 15 13
UNIT UNIT UNIT
4 4 4
MOD 16 MOD 15 MOD 13
Inside the MOD16, MOD15 and MOD13 we have a 4 bit adder with the follow-
ing structure:
A3 B3 A2 B2 A1 B1 A0 B0
FA FA FA FA
Not
used
C3 C2 C1 C0
The RNS adder and a ripple carry adder (same dynamic range) will be now
compared.
AREA COMPARISON ( in terms of FA & HA):
F.A. N° H.A. N°
RNS 9 3
R.C. 12 0
AREA RNS< AREA RC
5
lOMoARcPSD|24554605
DELAY COMPARISON
A 11 B 11 A 10 B 10 A9 B9 A8 B8 A7 B7 A6 B6 A0 B0
FA FA FA FA FA FA FA C in
C out
S 11 S 10 S9 S8 S7 S6 S0
: critical path
FA FA FA FA
The RNS adder has a shorter critical path, thus is more effective than the ripple
carry adder.
[d]
To solve the inequality, the numbers are converted to base 10.
(1|0|0) =2145
RNS(16|15|13)
(0|1|0) =1456
RNS(16|15|13)
(0|0|1) =2640
RNS(16|15|13)
6
lOMoARcPSD|24554605
(3|4|5) =499
RNS(16|15|13)
(4|0|2) =992
RNS(16|15|13)
(4|0|2) > (3|4|5)

RNS(16|15|13) RNS(16|15|13)
7
lOMoARcPSD|24554605
According to the IEEE single precision floating point standard, 23 bits are ded-
icated to store the significant. This means that a significant adder has the
following number of bits:
23 bits + 1 hidden bit + 1 sign bit = 25 bits
In the following different implementation of the 25 bits adder will be discussed

and evaluated. The area of components is evaluated according to Table 1.
Table 1: Area evaluation

Component Area Units
OR 1
AND 1
XOR 2
NOT 1
2:1 MUX (MUXBIT ) 4
2:1 bus MUX (MUXBUS: n lines ) 4× bus lines
4 bitt carry network 29
4 bit carry-look ahead 49
Full Adder 7
For the evaluation of the delay, same assumptions as in the textbook are herein
adopted.
Carry Look - Ahead Adder

The structure of the required Carry Look - Ahead Adder is depicted in Figure
2. For completeness, its sub-circuits are reported in the Appendix (see Figures
19 , 20 )
8
lOMoARcPSD|24554605
A B
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
3..0 3..0 3..0 3..0 3..0 3..0 3..0 3..0 3..0 3..0 3..0 3..0
B A B A B A B A B A B A CIN
4 BIT LA ADDER C0 4 BIT LA ADDER C0 4 BIT LA ADDER C0 4 BIT LA ADDER C0 4 BIT LA ADDER C0 4 BIT LA ADDER C0
G P G P G P G P G P G P
0 0 S 0 0 S 0 0 S 0 0 S 0 0 S 0 0 S
3 3 3..0 3 3 3..0 3 3 3..0 3 3 3..0 3 3 3..0 3 3 3..0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
00..24
G P C G P C G P C G P
3 3 3 2 2 2 1 1 1 0 0
G P
Carry Generator C0
0 0
3 3
3 3 3 2 2 2 1 1 1 0 0
C0
G
0
P
0
Carry Generator
3 3
24
25 Bit Output
cout
4 BIT LA ADDER = 4 bits Carry-Lookahead Adder
Figure 2: 25 bits Carry look - ahead adder
For the analysis of the circuit we deduce that the area CCLA and TCLA delay of
the circuit can be expressed as:
CCLA = 6 × (4 BIT LA ADDER) + 2 × (4 BIT CARRY NET)

+ 2 × AND + 2 × XOR + 1 × OR = 359 Area units
TCLA = 4 log4 25 + 1 ≈ 10.28 Time units
Single-Level Carry Select

The general structure for a 25 bits single-level carry select adder is depicted in
Figure 3.
9
lOMoARcPSD|24554605
24 13 12 0
12 bit adder 0 cin
13 bit adder
12 bit adder 1
13 13 13
c13
cout
12
High 12 bits Low 13 bits
Figure 3: General structure for a 25 bit carry select adder
The 12 and 13 bit adders have been implemented with carry-lookahead tech-
nique. In particular, a 4 bit carry-lookahead adder and a 4 bit carry propagate
network have been used as building blocks. A more detailed schematics for the
25 bits single-level carry select adder is depicted in Figure 4.
The area of the implemented unit can be expressed as:
C(CARRY SELECT ADD) =9 × (4 BIT LA ADDER) + 3 × (4 BIT CARRY NET)

+ 2 × AND + 2 × XOR + 1 × OR + 1 × MUXBIT + 1 × MUXBUS: 12 lines
= 587 Area Units
The delay of a single BIT 2 to 1 MUX is assumed as 1 time unit.

Unit delay is expressed as:
T(CARRY SELECT ADD) =TADD (13 BIT) + 1

=4 log4 13 + 2 ≈ 9.4 Time units
10
lOMoARcPSD|24554605
25 bits input 25 bits input

12 bits Carry-Lookahead
Adder
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
3..0 3..0 3..0 3..0 3..0 3..0

3..0 3..0 3..0 3..0 3..0 3..0 B A B A B A Cin
B A B A B A
'1' 4 BIT LA ADDER C0 4 BIT LA ADDER C0 4 BIT LA ADDER C0
4 BIT LA ADDER C0 4 BIT LA ADDER C0 4 BIT LA ADDER C0
G P G P G P
G P G P G P 0 0 S 0 0 S 0 0 S
0 0 S 0 0 S 0 0 S 3 3 3..0 3 3 3..0 3 3 3..0
3 3 3..0 3 3 3..0 3 3 3..0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 3 2 1 0 3 2 1 0 3 2 1 0
3 2 1 0 3 2 1 0 3 2 1 0
1 1 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 0 9 8 7 6 5 4 3 2 1 0
1 0 9 8 7 6 5 4 3 2 1 0
00..11
'0'
G P C G P C G P C G P G P C G P C G P C G P
3 3 3 2 2 2 1 1 1 0 0 3 3 3 2 2 2 1 1 1 0 0
Carry Generator Carry Generator
C0 C0
G P G P
0 0 0 0
3 3 3 3
1
2
2 2 2 2 2 1 1 1 1 1 1 1
4 3 2 1 0 9 8 7 6 5 4 3
2 2 2 2 2 1 1 1 1 1 1 1
4 3 2 1 0 9 8 7 6 5 4 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
3..0 3..0 3..0 3..0 3..0 3..0

13 bits Carry-Lookahead Adder
B A B A B A
4 BIT LA ADDER C0 4 BIT LA ADDER C0 4 BIT LA ADDER C0
'0'
G P G P G P
0 0 S 0 0 S 0 0 S
3 3 3..0 3 3 3..0 3 3 3..0
0 0 0 0
3 2 1 0
0 0 0 0
3 2 1 0
0 0 0 0
3 2 1 0 25 bits output
1 1 0 0 0 0 0 0 0 0 0 0
1 0 9 8 7 6 5 4 3 2 1 0
00..11
'0'
3 3 3 2 2 2 1 1 1 0 0
Carry Generator
C0
G P 2
0 0 5
3 3
1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
1 0 9 8 7 6 5 4 3 2 1 0 1 0 9 8 7 6 5 4 3 2 1 0
12 bits Carry-Lookahead
1 1 0 0 0 0 0 0 0 0 0 0
1 0 9 8 7 6 5 4 3 2 1 0
1 1 0 0 0 0 0 0 0 0 0 0
1 0 9 8 7 6 5 4 3 2 1 0 Adder
15..00 15..00
I1 I0 I1 I0 2 2 2 2 2 1 1 1 1 1 1 1
S0 16 Mux 2-1 4 3 2 1 0 9 8 7 6 5 4 3
S0 Mux 2-1 Q
15..00
Q (Id1993)
1 1 0 0 0 0 0 0 0 0 0 0
1 0 9 8 7 6 5 4 3 2 1 0
Computer Arithmetic - Academic Year 2020 - 2021

T.H.E. Problem No. 3
Title 25 bits Carry Select Adder
Author P.Pennestri (s2382660) Date April 2021
Figure 4: 25 bits Single-Level Carry Select Adder
Two-Level Carry Select Adder

The general structure of a 25 bit two-level carry select adder is depicted in
Figure 5.
11
lOMoARcPSD|24554605
24 19 18 13 12 7 6 0
cin
6 Bits Adder 6 Bits Adder 6 Bits Adder 7 Bits Adder
7 7
6 6 7 7 7
c7
6
c13
13
cout, High 12 bits High 6 bits High 7 bits
Figure 5: General structure of 25 bit two level carry select adder
Different implementations of the adders of Figure 5 are possible. In particu-

lar, in this document two types of realization are considered and evaluated in
terms of area and delay:
• Sub-adders implemented as Carry look-ahead
C(2LEVEL SELECT ADD) =7 × (4 BIT LA ADDER) + 7 × (4 BIT CARRY NET)

+ (1 × AND) + 1 × OR + 15 × (LA CIRCUIT)
+ 1 × MUXBUS: 13 lines + 3 × MUXBUS: 7 lines
= 700 Area Units
where 1 LA CIRCUIT = 1 × AND + 2 × XOR.
T(2 LEVEL SELECT ADD) =TCarry look−ahead adder (7 BIT) + 2

=4 log4 7 + 3 ≈ 8.6 Time Units
A detailed schematic of this implementation is depicted in Figure 6.
• Sub-adders implemented as Ripple carry implementation
C(2LEVEL SELECT ADD) =6 × 6 BIT RIPPLE CARRY ADDER+

1 × 7 BIT RIPPLE CARRY ADDER+
+ 1 × MUXBUS: 13 lines + 3 × MUXBUS: 7 lines
= 437 Area Units
T(2 LEVEL SELECT ADD) =TCarry ripple adder (7 BIT) + 2

=7 + 2 = 9 Time Units
12
lOMoARcPSD|24554605
25 bits input 25 bits input
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
0 0 0 0 0 0 0 0
3..0 3..0 3..0 3..0 3..0 3..0 3 2 1 0 3 2 1 0
BA BA BA BA BA BA
B A B A B A
LA CIN LA CIN 4 BIT LA ADDER C0 '0' LA CIN LA CIN 4 BIT LA ADDER C0 '0' LA CIN LA CIN 4 BIT LA ADDER C0 '0' 3..0 3..0
BA BA BA
B A
G P G P G P
0 0 S 0 0 S 0 0 S LA CIN LA CIN LA CIN 4 BIT LA ADDER C0
G P S G P S 3 3 3..0 G P S G P S 3 3 3..0 G P S G P S 3 3 3..0
G P
0 0 S
G P S G P S G P S 3 3 3..0
0 0 0 0 0 0 0 0 0 0 0 0
5 4 3 2 1 0 5 4 3 2 1 0 0 0
5 4
0 0 0 0 0 0 0 0
3 2 1 0 0 0 0 3 2 1 0
'0' 6 5 4
0 0 0 0
'0' 0 0 0 0 3 2 1 0 '0' 0 0 0 0
3 2 1 0 3 2 1 0
0 0 0 0
3 2 1 0
G P C G P C G P C G P G P C G P C G P C G P G P C G P C G P C G P
3 3 3 2 2 2 1 1 1 0 0 3 3 3 2 2 2 1 1 1 0 0 3 3 3 2 2 2 1 1 1 0 0
Carry Generator Carry Generator Carry Generator G P C G P C G P C G P
C0 C0 C0 3 3 3 2 2 2 1 1 1 0 0
G P G P G P
0 0 0 0 0 0 Carry Generator
3 3 3 3 3 3 C0
G P
0 0
3 3
6 bits Carry-Lookahead Adder 6 bits Carry-Lookahead Adder 6 bits Carry-Lookahead Adder
2
4
2
3
2 2 2 1
2 1 0 9
1
8
1
7
1 1 1 1
6 5 4 3
1
2
1
1
1 0 0 0
0 9 8 7
cin
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
BA BA 3..0 3..0 BA BA 3..0 3..0 BA BA 3..0 3..0 7 bits Carry-Lookahead

B A B A B A
Adder

LA CIN LA CIN 4 BIT LA ADDER C0 LA CIN LA CIN 4 BIT LA ADDER C0 LA CIN LA CIN 4 BIT LA ADDER C0
G P G P G P
0 0 S 0 0 S 0 0 S
G P S G P S 3 3 3..0 G P S G P S 3 3 3..0 G P S G P S 3 3 3..0
0 0 0 0 0 0 0 0 0 0 0 0
6 bits Carry-
Lookahead Adder
0 0 3 2 1 0 0 0 3 2 1 0 0 0 3 2 1 0
5 4 5 4 5 4
00..05
0 0 0 0
3 2 1 0
'0' '0'
0 0 0 0 0 0 0 0 '0'
3 2 1 0 3 2 1 0
G P C G P C G P C G P G P C G P C G P C G P G P C G P C G P C G P
3 3 3 2 2 2 1 1 1 0 0 3 3 3 2 2 2 1 1 1 0 0 3 3 3 2 2 2 1 1 1 0 0
Carry Generator '1' Carry Generator '1' Carry Generator '1'
C0 C0 C0
G P G P G P
0 0 0 0 0 0
3 3 3 3 3 3
I1 I0 05..00 05..00
I1 I0
S0 Mux 2-1 S0 6 Mux 2-1
Q
05..00 05..00 05..00 05..00 Q 07..00
I1 I0 I1 I0
S0 6 Mux 2-1 S0 6 Mux 2-1
Q Q
05..00 05..00
0
0 0 0 0 0 0 0 0 0 0 0 0 0
: 5 4 3 2 1 0 5 4 3 2 1 0
0
7
1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 9 8 7 6 5 4 3 2 1 0
5 4 3 2 1 0 5 4 3 2 1 0
I1 I0 I1 I0
S0 Mux 2-1 S0 Mux 2-1
1 1 0 0 0 0 0 0 0 0 0 0 0
Q Q 1 0 9 8 7 6 5 4 3 2 1 0 0
:
0
7
I1 I0 11..00 11..00
I1 I0
S0 Mux 2-1 S0 12 Mux 2-1
Q
Q 12..00
00..15
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 9 8 7 6 5 4 3 2 1 0 5 4 3 2 1 0 6 5 4 3 2 1 0
cout 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
25 bits output
BA
B
LA CIN
A
G P S
G
CIN
P Computer Arithmetic - Academic Year 2020 - 2021
S
Title 25 bits 2 Level Carry Select Adder
Author P.Pennestri (s2382660) Date April 2021
Figure 6: 25 bits Two-Level Carry Select Adder with Sub-adders implemented

as Carry look-ahead
13
lOMoARcPSD|24554605
Optimal Variable-Block Carry Skip Adder

The optimal number of blocks topt is obtained as1 :
√
topt = 2 k = 10
b=1
where k is the adder bits number (25 in this case).

The block size distribution is
1234554321
However, it should be observed that with this distribution the adder would have
30 bits. Thus, the total number of blocks is pruned to 9 and the block size
distribution is:
123454321
The schematic of a 25 bits Optimal variable-block carry skip adder is depicted
in Figure 7. The sub-adders have been implemented as ripple carry adders. Ex-
tra circuitry was added to generate the propagate signals in each block. Using
the same mathematical notation as in the textbook, the propagate signal de-
fined for each k bit ripple carry adder block is
p[0,k] = p0 p1 . . . pk (3)
Thus, the hardware necessary to compute the propagate signal is estimated
as in Table 2:
Table 2: generate signal hardware evaluation
Sub block Hardware to compute the generate signal
2 bits adder 2× XOR + 1× AND

1
This procedure is taken from the course textbook (see section 7.1). In this document the
same mathematical notation is used.
14
lOMoARcPSD|24554605
25 bit input
25 bit input 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
7 6 5 4 3 2 1 0 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
7 6 5 4 3 2 1 0 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 2 1 0 2 1 0 3 2 1 0 3 2 1 0 4 3 2 1 0 4 3 2 1 0 3 2 1 0 3 2 1 0 2 1 0 2 1 0 1 0 1 0
1..0 1..0 2..0 2..0 3..0 3..0 5..0 5..0 3..0 3..0 3..0 3..0 3..0 3..0
B A B A B A B A B A B A B A
A B
2 BITS ADDER CI 3 BITS ADDER CI 4 BITS ADDER CI 5 BITS ADDER CI 4 BITS ADDER CI 3 BITS ADDER CI 2 BITS ADDER CI
Co FA Ci P01 RIPPLE CARRY P02 RIPPLE CARRY P03 RIPPLE CARRY P04 RIPPLE CARRY P03 RIPPLE CARRY P02 RIPPLE CARRY P01 RIPPLE CARRY A B
S CO S CO S CO S CO S CO S CO S CO S Co FA Ci
1..0 2..0 3..0 4..0 3..0 2..0 1..0
S
S0
Cout Mux 2-1 S0 S0 S0 S0 Cin
Mux 2-1 Mux 2-1 Mux 2-1 S0 S0 S0 S0 Mux 2-1
I1 Mux 2-1 Mux 2-1 Mux 2-1 Mux 2-1
Q I1 I1 I1 I1
I0 Q Q Q I1 I1 I1 I1 Q
I0 I0 I0 Q Q Q Q I0
I0 I0 I0 I0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 2 1 0 3 2 1 0 4 3 2 1 0 3 2 1 0 2 1 0 1 0
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
00..24
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
25 bit output
i BIT LA = i bits Carry-Lookahead Adder
Figure 7: 25 bits Optimal variable-block carry skip adder
COPT−VAR−BLOCK = 25 × FA + 9 MUX + 2 × XOR + circuitry for propagate signals

= 215 + 62 = 277 Area units
√
TOPT−VAR−BLOCK = 2 2 × 25 − 3 ≈ 11.14 Time units
Adder Selection
From our previous analysis, we conclude that the 25 bits Optimal variable-
block carry skip adder occupies the minimum area among the examined ar-
chitectures. Therefore, since our selection criteria is cost-effectiveness, this
architecture should be chosen for integration into the FFU.
15
lOMoARcPSD|24554605
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
L1
Brent
Kung
L2
L3
K.Stone
L4
L5
L6
Brent
Kung
L7
s24 s23 s22 s21 s20 s19 s18 s17 s16 s15 s14 s13 s12 s11 s10 s9 s8 s7 s6 s5 s4 s3 s2 s1 s0
Let us assume:
• 1 AND / OR : 1 unit
• 1 XOR : 2 units
Area = 25 × (p,g) + 46 ¢+ 25 xor (to compute si )= 25×(2+1)+3×46+2×25 = 213 units
Delay = 2 + 7 × 2 + 2 = 18 units
16
lOMoARcPSD|24554605
5.1 POINT A
Since it is requested to minimize the delay, the Wallace approach is used. The
dot reduction diagram is shown in Figure 8.
2FA+1HA
2HA+1FA
1HA+1FA
2BIT CPA
(carry out
not used)
Figure 8: Dot reduction diagram
17
lOMoARcPSD|24554605
0
1
2
3
4
5
6
7
8
9
10
18
lOMoARcPSD|24554605
6.1 POINT A
3 bits integers 2’s complement range: [−4; 3]
y max = 2 · 3 · 3 + 20 + 3 · 3 = 27 + 20 = 47
(a = 3, b = 3 , c = 3 , d = −4)
y min = −2 · 4 · 3 − 3 · 4 − 5 · 3 = −51
(a = 3, b = −4 , c = −4 , d = 3)
or (a = −4, b = 3 , c = −4 , d = 3)
The range y min ; y max
consists of 99 values. Thus,

#BITS = log2 99 + 1 = 7 BITS

j k
7 BITS are required to represent y.
6.2 POINT B
It is convenient to express y as follows:
y = 2(ab) + 2c − 4d − d
For the ab multiplication, the modified Baugh-Wooley method is used. In the
following, the method of operand addition matrix is shown.
6 5 4 3 2 1 0 COL
a 2 b0 a 1 b0 a 0 b0
a 2 b1 a 1 b1 a 0 b1
2ab
a 2 b2 a 1 b2 a 0 b2
1 1
c2 c2 c2 c2 c1 c0 2c
c2 c2 c2 c2 c2 c1 c0 c
d2 d2 d2 d1 d0 -4d
1
d2 d2 d2 d2 d2 d1 d0 -d
1
19
lOMoARcPSD|24554605
The above multi-operand addition matrix can be rewritten in a more compact

(simplified) form.
6 5 4 3 2 1 0
d2 d2 c2 a 2 b0 a 1 b0 a 0 b0 c0
c2 a 2 b2 a 2 b1 a 1 b1 a 0 b1 c0 d0
1 c2 a 1 b2 a 0 b2 c1 c1 1
1 d1 c2 d1
d2 d0
d2
MULTIOPERAND ADDITION MATRIX
All the carries generated in column 6 are ignored because from POINT A the
operation result can be represented with 7 bits.
6.3 POINT C
Since it is required to minimize both delay and area, Dadda’s reduction tree is
applied (see Figure 9).
20
lOMoARcPSD|24554605
6 5 4 3 2 1 0
1
2
=> n(h)= 6
3
4
Since the result of the operation
can be expressed as a 7 bit number, 5
carries generated in this column
are not taken into account. 6
7
1 HA
n(h)= 6 => n(h)= 4 3
3 FA + 1 HA 6
n(h)= 4 => n(h)= 3 2
4
4 FA + 2 HA
1
n(h)= 3 => n(h)= 2
2
3
7 FA
Parallel preﬁx adder
Figure 9: Dada Reduction tree
21
lOMoARcPSD|24554605
The hardware implementation of the reduction tree is depicted in Figure 10.
Input d Input c Input b Input a
d2 d1 d0 c2 c1 c0 b2 b1 b0 a2 a1 a0
DDD CCC BBB AAA

210 210 210 210
partial products
K6 K5 K4 K3 K2 K1 K0
2..0 2..0 3..0 4..0 6..0 3..0 2..0
K6 K5 K0
K4 K2 K1
3 bits
3 bits
3 bits
7 bits
4 bits
K3
4 bits
5 bits
00
01
A B
Co HA
00
01
S
LEVEL 1
00
01
02
02
03
A B A B A B
Co FA Ci Co FA Ci Co FA Ci
02
S S 03 S
LEVEL 2
03
A B
Co HA
S
00 00
01 01
00
01
04
05
A B A B A B A B A B A B LEVEL 3
Co HA Co FA Ci Co FA Ci Co FA Ci Co FA Ci Co HA
S S S S S S
02
02
00
04 06 01
02
02
03
A B A B A B A B A B A B A B
Co FA Ci Co FA Ci Co FA Ci Co FA Ci Co FA Ci Co FA Ci Co FA Ci LEVEL 4
S S S S S S S
A(5) B(5) A(4) B(4) A(3) B(3) A(2) B(2) A(1) B(1) A(0) B(0)
Parallel Prefix Adder
y0
y6 y5 y4 y3 y2 y1
K6 K5 K4 K3 K2 K1 K0
ADDR 0 d[2] d[2] c[2] a[2]b[0] a[1]b[0] a[0]b[0] c[0]

ADDR 1 c[2] a[2]b[2] a[2]b[1] a[1]b[1] a[0]b[1] c[0] d[0]
ADDR 2 ‘1’ c[2] a[1]b[2] a[0]b[2] c[1] c[1] ‘1’
ADDR 3 ‘1’ d[1] c[2] d[1]
ADDR 4 d[2] d[0]
ADDR 5 d[2]
ADDR 6 ‘1’
Computer Arithmetic - Academic Year 2020 - 2021

Title Circuit Block Diagram to compute y= 4ab + 3c - 5d
Author P.Pennestri (s2382660) Date March 2021
Figure 10: Hardware implementation of the required arithmetic circuit
22
lOMoARcPSD|24554605
6.4 POINT D
BRENT KUNG PARALLEL PREFIX ADDER
5 4 3 2 1 0
S5 S4 S3 S2 S1 S0
The delay of the FU can be expressed as:
3F A + 1HA + 1 CarryOperator
7 Solution Problem 7
Modulo 9 Adder design
A modulo 9 adder is implemented by means of a 4 bit carry propagate adder.
Its result is then corrected to be compliant with the modulo 9 arithmetic rules.
The schematic of the adder is depicted in Figure 11.
23
lOMoARcPSD|24554605
A B
00..03
0 0 0 0 0
0 3 2 1 0
:
0
3
0 0 0 0
3 2 1 0
A B A B A B A B
Co FA Ci Co FA Ci Co FA Ci Co HA
S S S S
0 0 0 0
3 2 1 0
00..03
Correction
circuit L2
3..0
IN
'0' '1'
L1
0 0 0 0 O
3 2 1 0 3..0
03..00 03..00
I1 I0
S0 4 Mux 2-1
Q
03..00
Correction
circuit L1
C
Figure 11: Modulo 9 RNS adder
In the following we will design circuits for L1 and L2.
• L1 c = 0
The behavior of the L1 circuit is described by the following K-MAPs
24
lOMoARcPSD|24554605
O[3] S1 S0 O[2] S1 S0
00 01 11 10 00 01 11 10
00 0 0 0 0 00 0 0 0 0
S3 S2
S3 S2
01 0 0 0 0 01 1 1 1 1
11 0 0 0 0 11 0 1 1 1
10 1 0 0 0 10 0 0 0 0
O[3]=S3S2S1S0 O[2]=S3S2 + S2S0+ S2S1
O[1] S1 S0 O[0] S1 S0
00 01 11 10 00 01 11 10
00 0 0 1 1 00 0 1 1 0
S3 S2
S3 S2
01 0 0 1 1 01 0 1 1 0
11 1 0 1 0 11 1 0 0 1
10 0 0 1 0 10 0 0 0 1
O[1]=S3S1 + S1S0+ S3S2S1S0 O[0]=S3S0 + S3S1S0+ S3S2S0
Figure 12: K-MAPs for the synthesis of L1 circuit
25
lOMoARcPSD|24554605
IN
03..00
0 0 0 0
0 1 2 3
0 0 0 0
3 2 1 0
00..03
03..00
Figure 13: Schematic of the L1 circuit
• L2 c = 1
This case is observed when both input are 10002 . Thus, L2 it is simply made
of a constant, namely 0111 (the result of the RNS addition).
Modulo 9 Multiplier Design

The partial product matrix of the mod (2m + 1) multiplier can be divided into
4 groups A, B, C and D. Only terms from one group can be simultaneously
different from 0.
The property is justified by observing that only two possible types of input are
feasible. The 4 possible cases are represented in Figure 14.
26
lOMoARcPSD|24554605
Case 1 Case 2
0 0
0 1
A 0 0 0 0 0
0 0 0 0 0
D 0 B 0 0 0 0
0 0 0 0 0
C
Case 3 Case 4
1 0 0 0 1 0 0 0
1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
Figure 14: Modulo 9 multiplication input classes
In our case m = 3. Thus, 4 bit are used to represent the numbers.

The initial partial product matrix is:
6 5 4 3 2 1 0
2 2 2 2 2 2 2
p p p p
30 20 10 00
p p p p
31 21 11 01
p p p p
32 22 12 02
p p p p
33 23 13 03
The above partial product matrix has been deduced by means of the follow-
27
lOMoARcPSD|24554605
ing equations:
m
X m
X
i i
R = |A × B|2m +1 = a2 bj 2 j
i=0 j=0 2m +1
m X
X m
= pij 2i+j
i=0 j=0 2m +1
Note: |X|Y denote the module Y residue of X.

The initial matrix product is simplified by applying the properties:
1. |22m |2m +1 = 1
2. |22m−1 |2m +1 = 2m−1 + 1
3. Only terms from one group can be simultaneously different from 0
The result is depicted in Figure 15.
4 3 2 1 0
2 2 2 2 2
p v q p q v p v p33
20 2 10 2 00
p v q p p
11 01
21 0
p v q p p
22 1 12 02
Figure 15: Modified Partial Product Matrix
where qi = pim ∧ pmi .

This modified partial product matrix can be further simplified. In particular, our
task is to find an equivalent one, such that terms at the left side of the dashed
line in 15 are rewritten in position at the right of the dashed line.
Such type of transformation is available after we consider the following prop-
erty:
s2i 2m +1
= −s|i|m 2m +1
= (2m + 1 − s) 2|i|m 2m +1
= s̄2 |i|m
+2 2 m |i|m
2m +1
, i ∈ [m; 2m − 2] (1)
According to equation (1), if a term in the ith position is inverted and rewritten
in position |i|m , the partial product matrix does not change when a correction
term ”2m 2|i|m ” is taken into account.
The partial product matrix is thus rewritten as:
28
lOMoARcPSD|24554605
2 1 0
2 2 2
p v q p q vp v p
20 2 10 2 00 33
p p p v q
11 01 21 0
p p v q p
02 22 1 12
The sum of all the required correction terms is given by:
COR1 = |2m (2m − m − 1)|2m +1 (4)
If in the reduced partial product matrix a carry ci is produced at column m − 1,

then
|2m ci |2m +1 = |2m + c̄i |2m +1 (5)
At column m − 1, m − 1 carries are generated. This means that a second correc-
tion term is taken into account
COR2 = |2m (m − 1)|2m +1 (6)
Thus, the total correction term is
COR = COR1 + COR2 = |2m (2m − 2)|2m +1 = 3
Finally,
m−1
(7)
X
R = |A × B|2m +1 = ppi + 3
i=0 2m +1
The proposed solution is a straightforward implementation of Equation 7.

The schematics for the mod 9 multiplier and its related sub-circuits are de-
picted in Figures 16 - 18.
29
lOMoARcPSD|24554605
B
A
0 0 0 0
3 2 1 0
0..3 B 0..3 B 0..3 B 0..3 B

A I A I A I A I
Partial Products Partial Products Partial Products Partial Products
pi3 pi2 pi1 pi0
O O O O O O O O O O O O O O O O
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
p30
p20
p10
p00
p31
p21
p11
p01
p32
p22
p12
p02
p33
p23
p13
p03
'1' '1'
A B A B A B
Co HA Co FA Ci Co FA Ci
S S S
A B A B A B
Co FA Ci Co FA Ci Co FA Ci
S S S
A B A B A B
2 2 1 1 0 0
3 bit mod 9 adder

S
0..3
Figure 16: Schematic of the Modulo 9 multiplier
30
lOMoARcPSD|24554605
B3 A2 B1 A1 B0 A0
A B A B A B
Co FA Ci Co FA Ci Co HA
S S S
L1 circuit developed
for the mod 9 adder
0 0 0 0
3 2 1 0
00..03
0 0 0 0
0 1 2 3
0 0 0 0
3 2 1 0
00..03
03..00
Figure 17: 3 bit Modulo 9 adder
A BI
03..00
0 0 0 0
0 1 2 3
O0 O1 O2 O3
Figure 18: Partial Product Block
31
lOMoARcPSD|24554605
Implemented Circuits Validation

The modulo 9 adder and multiplier have been implemented inside Digital Electronics
Deeds 2 . This software offers the possibility to export the schematic into VHDL,
suitable for simulation purposes. The validation procedure is divided into the
following steps:
• The generation of the VHDL code from the Deeds schematic.
• Generation of the all possible input patterns together with the expected
output result by means of a python script.
• Simulation of the unit (adder or multiplier) VHDL to check if the simulations

results match the expected ones.
Both multiplier and adder have successfully passed the validation process.
The VHDL code and the python script for io generation are available at section
10.3.
2
https://www.digitalelectronicsdeeds.com
32
lOMoARcPSD|24554605
To solve this class of problem I have developed the Python script3 reported in
section 10.2. The output is listed below:
==========================================
z = 01.011010110 NONRESTORING Algorithm
1 Guard digit(s) automatically added
==========================================
s[0] = z-1 0000.011010110 q_0= 1 q[0]= 0001.000000000
2s[0] 0000.110101100 q_-1= 1 q[1]= 0001.100000000
1101.100000000
-----------------------------------------
s[1] 1110.010101100 q_-2= -1 0001.010000000
2s[1] 1100.101011000
0010.110000000
-----------------------------------------
s[2] 1111.011011000 q_-3= -1 0001.001000000
2s[2] 1110.110110000
0010.011000000
-----------------------------------------
s[3] 0001.001110000 q_-4= 1 0001.001100000
2s[3] 0010.011100000
1101.101100000
-----------------------------------------
s[4] 0000.001000000 q_-5= 1 0001.001110000
2s[4] 0000.010000000
1101.100110000
-----------------------------------------
s[5] 1101.110110000 q_-6= -1 0001.001101000
2s[5] 1011.101100000
0010.011011000
-----------------------------------------
s[6] 1110.000111000 q_-7= -1 0001.001100100
2s[6] 1100.001110000
0010.011001100
-----------------------------------------
s[7] 1110.100111100 q_-8= -1 0001.001100010
2s[7] 1101.001111000
0010.011000110
-----------------------------------------
s[8] 1111.100111110 Negative 0001.001100001
0010.011000011
-----------------------------------------
Final Result 0001.00110000
============= Check Result ================

0001011010110
000100110000
3
The script, in case of negative reminder, does not correct it.
33
lOMoARcPSD|24554605
The input in decimal: 1.41796875

The result decimal: 1.1875
error: 0.003284930203603098
Point A
(a + b) = 0.39726 × 108 − 0.39724 × 108 = 0.00002 × 108

(a + b) + c = 0.2 × 104 + 0.14321 × 104 = 0.34321 × 104
(b + c) = −0.39724 × 108 + 0.00001 × 108 = −0.39723 × 108

(b + c) + a = −0.39723 × 108 + 0.39726 × 108 = 0.3 × 104
Point B
(a + b) + c = No Difference
a + (b + c) = a − (0.397226 × 108 ) = 0.34 × 104
Point C
a + (b + c) 2 G.B. → 0.343 × 104

a + (b + c) 3 G.B. → 0.3432 × 104
a + (b + c) 4 G.B. → 0.34321 × 104
10 Appendix
De minimis non curat praetor.
34
lOMoARcPSD|24554605
10.1 Commonly used sub-circuits
03
P3
03
03
03 00..03 : A
G3 00
03
P03 02
P2 03
02
00..03 :
00
B
02
G2
02
01
P1
G03 01
01
G1
01
00
P0
00
00
G0
00
C3
C0
C0
03 03
0 0 0 0
3 2 1 0
C2
02 02
03
S :
00
C1
01 01
0
0
:
0
3
00 00
Figure 19: Implementation of a 4 bit carry-look ahead adder
P3
G3
P03
P2
G2
G03 P1
G1
P0
G0
C3 C0
C2
C1
Figure 20: 4 bit carry network
35
lOMoARcPSD|24554605
10.2 Step by Step computation of the non restoring square root:

Python Script
1 # -*- coding : utf -8 -*-
2 """
3 Created on Wed Mar 31 11:39:56 2021
4 @author : Pietro Pennestri ( s2382660 )
5 @mail : p. pennestri@student . utwente .nl
6 @description : implementation of the non restoring square root
7 algorithm . The script produces step by step result .
8 """
9
10 import sys
11 class alu:
12 def __init__ (self ,bits ,point = None):
13 self.bits = bits
14 """
15 # self.point used to define the fixed point position .
16 Its position is expressed relative to the MSB bit
17 e.g. 101.11011 => self. point = 3
18 """
19 self.point = point
20
21
22 def unit(self):
23 unit="1"
24 while len(unit)!= self.bits:
25 unit= "0" + unit
26 return unit
27
28 def add(self ,a,b):
29 #a+b ( signed input)
30 if (( len(a) == self.bits) and ( len(b) == self.bits) ):
31 result = bin(int(a, 2) + int(b, 2))
32 result = result [2:] # remove 0b for the string
33
34 if(len( result ) < self.bits):
35 while len( result )!= self.bits:
36 result = "0"+ result
37
38 if(len( result ) > self.bits):
39 result = result [1:]
40
41 # check overflow
42 if(a[0]== b[0]):
43 if( result [0]!= a[0]):
44 print (" Overflow ")
45 return None
46 else:
47 return result
48 else:
49 return result
50 else:
51 print ("a,b, must agree with alu bit len.")
52 return None
53
54
55 def twosCompl (self ,a):
56 not_a = ""
57 for d in a:
36
lOMoARcPSD|24554605
58 if(d=="1"):
59 not_a = not_a + "0"
60 else:
61 not_a = not_a + "1"
62 one = self.unit ()
63 return self.add(not_a ,one)
64
65
66 def sub(self ,a,b):
67 # a - b
68 minus_b = self. twosCompl (b)
69 return self.add(a, minus_b )
70
71 def shiftLeft (self ,a,shift):
72 if(len(a)== self.bits):
73 return a[1:]+"0"
74 else:
75 print ("a=",a , "must have a len of ", self.bits)
76
77 def isPos(self ,a):
78 #check if a>0
79 if(a[0]== '1'):
80 return False
81 else:
82 return True
83
84
85 class binSQRT :
86 def __init__ (self , binValue ):
87 self.val = binValue
88
89 def trial2Subtract (self , prev_q , q_signed_digit , j , the_alu ):
90 temp1 = the_alu . shiftLeft (prev_q ,1)
91 # temp2 expresses 2^-j in binary
92 temp2 = the_alu .point * "0" + (j -1)*"0" + "1" + "0"*( the_alu .bits - (j
-1) - the_alu .point -1 )
93
94 if( q_signed_digit == '1'):
95 return the_alu . twosCompl ( the_alu .add(temp1 ,temp2))
96 else:
97 return the_alu .sub(temp1 ,temp2)
98
99
100 def computeQfromSignedDigit (self ,prev_q , q_signed_digit ,j, the_alu ):
101 #temp expresses 2^-j in binary
102 temp = the_alu .point * "0" + (j -1)*"0" + "1" + "0"*( the_alu .bits - (j -1)
- the_alu .point -1 )
103 if ( q_signed_digit == '1'):
104 return the_alu .add(prev_q ,temp)
105 else:
106 return the_alu .sub(prev_q ,temp)
107
108 def npb(self ,num , point):
109 # nice print binary numbers
110 if point == None:
111 return num
112 else:
113 return num [: point ]+"."+num[point :]
114 def testResult (self , z,result , precision , the_alu ):
115 print("\n ============= Check Result ================ ")
37
lOMoARcPSD|24554605
116
117 # compute decimal input
118
119 print(z)
120 print( result )
121 decimal_input = int("0b"+z, 2)
122 decimal_input = decimal_input * 2**( -( the_alu .bits - the_alu .point))
123
124 result_decimal = int("0b"+result , 2)
125 result_decimal = result_decimal * 2**( -( the_alu .bits - the_alu .point))
126 result_decimal = result_decimal * 2** precision
127 print("The input in decimal : ", decimal_input )
128 print("The result decimal : ", result_decimal )
129 print("error: ", abs (( decimal_input )**0.5 - result_decimal ) )
130
131 def nonRestoring (self , precision =1):

132 # check if input value is in the range [1 ,4)
133 if("." in self.val):
134 self.val = self.val + precision *"0"
135 integer_part = self.val.split(".")[0]
136 decimal_part = self.val.split(".")[1]
137 if (( len( integer_part ) >2) or ("1" not in integer_part )):
138 print("ERROR : The Algorithm require radicand in range [1 ,4)")
139 inputCheck = False
140 else:
141 inputCheck = True
142 iterations_steps = len( decimal_part )
143
144 else:
145 if (( len(self.val) >2) or ("1" not in self.val)):
146 print("ERROR : The Algorithm require radicand in range [1 ,4)")
147 inputCheck = False
148 else:
149 inputCheck = True
150 integer_part = self.val
151 decimal_part = "0"
152 iterations_steps =1
153
154 if( inputCheck ):
155
156 print (" ========================================== ")
157 print ("z = ", self.val , " NONRESTORING Algorithm ")
158 print (precision ," Guard digit(s) automatically added ")
159 print (" ========================================== ")
160
161 # ############# define an alu for the computations ######

162 alu_bits = len( integer_part ) + len( decimal_part ) + 2
163 point_position = len( integer_part ) + 2
164 the_alu = alu(alu_bits , point_position )
165
166 one = ( point_position -1)*"0"+"1"+( alu_bits - point_position )*"0"
167 # #######################################################
168 # rewrite z with the proper format (same number of bits as requested
by alu)
169 z = ( point_position -len( integer_part ))*"0" + integer_part +
decimal_part
170 # q history stores all the temporary values of q ( digit set in
[0 ,1])
171 q_history =[]
172 # for each iteration j the signed value of the digit q_j is stored
38
lOMoARcPSD|24554605
173 q_signed_digit =[]

174 s_history = []
175
176 # populate the previously defined vectors with init. data

177
178 # q is init as 1.
179 q_history . append (( len( integer_part )+1)*"0" + "1" + "0"*len(
decimal_part ))
180 # s(0) = z-1
181 s_history . append ( the_alu .sub(z,one))
182 q_signed_digit . append ('1')
183
184 for i in range( iterations_steps ):
185 prev_q = q_history [len( q_history ) -1]
186 s = s_history [len( s_history ) -1]
187 two_s = the_alu . shiftLeft (s ,1)
188
189 if(i==0 or ( the_alu .isPos(s)) ):
190 current_q_digit = '1'
191 else:
192 current_q_digit = '-1'
193
194 test = self. trial2Subtract ( prev_q , current_q_digit , i+1 ,
the_alu )
195 q_signed_digit . append ( current_q_digit )
196 current_q =self. computeQfromSignedDigit (prev_q , current_q_digit ,
i+1, the_alu )
197 q_history . append ( current_q )
198 next_s = the_alu .add(two_s ,test)
199 s_history . append ( next_s )
200
201 if(i==0):
202 print ("s[0] = z -1 ", self.npb(s, the_alu .point), " q_0=
","1", " q[0]=",self.npb( q_history [0], the_alu .point))
203 print ("2s["+str(i)+"] ",self.npb(two_s , the_alu .
point), " q_ -1=",current_q_digit , " q[1]=",self.npb( current_q , the_alu .
point) )
204 print (" ",self.npb(test , the_alu .point))
205 elif(i!= iterations_steps -1):
206 print ("s["+str(i)+"] ", self.npb(s, the_alu .point)
, " q_ -"+str(i+1)+"=", current_q_digit , " ",self.npb( current_q , the_alu .
point))
207 print ("2s["+str(i)+"] ",self.npb(two_s , the_alu .
point))
208

210 else:
211 if( current_q_digit == ' -1'):
212 tex2print = " Negative "
213 correctReminder = True
214 else:
215 tex2print = " Positive "
216 correctReminder = False
217 print ("s["+str(i)+"] ", self.npb(s, the_alu .point)
, " ",tex2print , " ",self.npb( current_q , the_alu .point))
219
220
221 # print (" one= ", one)
222 # print ("s= ", self.npb(prev_s , the_alu . point))
39
lOMoARcPSD|24554605
223 # print (" test: ", self.npb(test , the_alu . point ))

224
225 print(" -----------------------------------------")
226
227 final_result = q_history [len( q_history ) -1]
228 final_result = final_result [: len( final_result )-precision ] # truncate
229 print (" Final Result " , self.npb( final_result , the_alu .point) )
230 # print(len( s_history ) -2)
231 self. testResult (z, final_result ,precision , the_alu )
232
233
234 else:
235 return False
236
237
238
239 #sqrt1 = binSQRT ("10.00000000000000000000000000000")
240 sqrt1 = binSQRT (" 01.01101011 ")
241 sqrt1. nonRestoring ()
10.3 Modulo 9 adder & multiplier : test of correctness

1 # -*- coding : utf -8 -*-
2 """
3 Created on Sun Apr 4 15:47:48 2021
4 @author : Pietro Pennestri ( s2382660 )
5 @mail : p. pennestri@student . utwente .nl
6 @file name : io_gen .py
7 @description : This script generates :
8 1) a file with all the possible
9 input combination for the RNS adder and multiplier .
10
11 2) files with the expected output for both RNS multiplier
12 and adder
13
14 """
15
16 rns_base = 9
17 """
18 specify file name
19 """
20 input_file_name = " input.txt"
21 expected_adder_output_name = " given_output_adder .txt"
22 expected_mult_output_name = " given_output_mult .txt"
23
24 # open files
25 the_input = open( input_file_name , "w")
26 expected_adder_output = open( expected_adder_output_name , "w")
27 expected_mult_output = open( expected_mult_output_name , "w")
28
29 for i in range ( rns_base ):
30 input_1 = '{0:04b}'. format (i)
31 for k in range( rns_base ):
32 input_2 = '{0:04b}'. format (k)
33 """
34 compute the expexted output
35 """
36 mult_out = (i*k)% rns_base
37 mult_out_bin = '{0:04b}'. format ( mult_out )
38 add_out = (i + k)% rns_base
40
lOMoARcPSD|24554605
39 add_out_bin = '{0:04 b}'. format ( add_out )

40 """
41 write inputs + expected outputs into files
42 """
43 if(i== rns_base -1 and k== rns_base -1):
44 the_input .write( input_1 +" "+ input_2 )
45 expected_adder_output .write( add_out_bin )
46 expected_mult_output .write( mult_out_bin )
47 else:
48 the_input .write( input_1 +" "+ input_2 +"\n")
49 expected_adder_output .write( add_out_bin +"\n" )
50 expected_mult_output .write( mult_out_bin +"\n" )
51
52 # close files
53 the_input .close ()
54 expected_adder_output .close ()
55 expected_mult_output .close ()
1 -- File: mult.vhd
2 -- Description : Modulo 9 multiplier
3 -- Schematic Author : Pietro Pennestri ( s2382660 )
4 -- VHDL file generated from the schematic with Deeds software .
5 -- Date: 4/4/2021
6 -- This VHDL file should be used for simulation
7 -- purpose only and does not necessarily be feasible for synthesis .
8
9 LIBRARY ieee;
10 USE ieee. std_logic_1164 .ALL;
11 USE ieee. numeric_std .all;
12
13
14 ENTITY mult IS
15 PORT(
16 -- ------------------------------------> Inputs :
17 iA: IN std_logic_vector ( 3 downto 0 );
18 iB: IN std_logic_vector ( 3 downto 0 );
19 -- ------------------------------------> Outputs :
20 oC: OUT std_logic_vector ( 3 downto 0 )
21 -- ----------------------------------------------------
22 );
23 END mult;
24
25
26 ARCHITECTURE structural OF mult IS
27
28 -- --------------------------------------> Components :
29 COMPONENT NOT_gate IS
30 PORT( I: IN std_logic ;
31 O: OUT std_logic );
32 END COMPONENT ;
33 --
34 COMPONENT AND2_gate IS
35 PORT( I0 ,I1: IN std_logic ;
37 END COMPONENT ;
38 --
40 PORT( I0 ,I1 ,I2: IN std_logic ;
42 END COMPONENT ;
43 --
41
lOMoARcPSD|24554605
45 PORT( I0 ,I1 ,I2 ,I3: IN std_logic ;
47 END COMPONENT ;
48 --
49 COMPONENT OR3_gate IS
52 END COMPONENT ;
53 --
57 END COMPONENT ;
58 --
59 COMPONENT NOR3_gate IS
62 END COMPONENT ;
63 --
64 COMPONENT Adder_Half IS
65 PORT( COUT:OUT std_logic ;
66 A: IN std_logic ;
67 B: IN std_logic ;
68 S: OUT std_logic );
69 END COMPONENT ;
70 --
71 COMPONENT Adder_Full IS
72 PORT( CIN: IN std_logic ;
73 COUT:OUT std_logic ;
77 END COMPONENT ;
78
79 -- --------------------------------------> Signals :
80 SIGNAL S001: std_logic ;
42
lOMoARcPSD|24554605

154
155
156 BEGIN -- structural
157
158 -- --------------------------------------> Input:
159 S067 <= iA (0);
160 S068 <= iA (1);
161 S069 <= iA (2);
162 S070 <= iA (3);
163 S041 <= iB (0);
43
lOMoARcPSD|24554605
164 S040 <= iB (1);

165 S039 <= iB (2);
166 S038 <= iB (3);
167
168 -- --------------------------------------> Output :
169 oC (0) <= S071;
170 oC (1) <= S072;
171 oC (2) <= S073;
172 oC (3) <= S074;
173
174 -- --------------------------------------> Constants :
175 S001 <= '1';
176 S002 <= '1';
177
178 -- --------------------------------------> Component Mapping :
179 C065: Adder_Full PORT MAP ( S019 , S013 , S014 , S016 , S007 );
183 C076: Adder_Half PORT MAP ( S022 , S024 , S023 , S005 );
184 C082: NOT_gate PORT MAP ( S022 , S016 );
188 C148: NOR3_gate PORT MAP ( S028 , S029 , S027 , S020 );
189 C168: OR4_gate PORT MAP ( S033 , S032 , S034 , S031 , S018 );
190 C287: OR3_gate PORT MAP ( S031 , S032 , S025 , S023 );
191 C346: NOR3_gate PORT MAP ( S036 , S037 , S035 , S017 );
192 B1_C004 : AND2_gate PORT MAP ( S041 , S070 , S036 );
208 B5_C002 : Adder_Full PORT MAP ( S042 , S063 , S011 , S010 , S064 );
209 B5_C003 : Adder_Full PORT MAP ( S043 , S042 , S013 , S012 , S065 );
210 B5_C004 : Adder_Half PORT MAP ( S043 , S007 , S009 , S066 );
211 B5_C252 : NOT_gate PORT MAP ( S066 , S046 );
212 B5_C253 : AND3_gate PORT MAP ( S064 , S046 , S063 , S047 );
220 B5_C262 : AND4_gate PORT MAP ( S054 , S064 , S055 , S063 , S052 );
223 B5_C266 : OR3_gate PORT MAP ( S048 , S047 , S049 , S071 );
44
lOMoARcPSD|24554605

234 END structural ;
1 -- File: mult_components .vhd

2 -- Description : Components used in the modulo 9 multiplier
5 -- Date: 4/4/2021
8
9 -- ------------------------------------------------------------------
10 library ieee;
11 use ieee. std_logic_1164 .all;
12
13 ENTITY NOT_gate IS
16 END NOT_gate ;
17
18 -- ------------------------------------------------------------------
19 ARCHITECTURE behavioral OF NOT_gate IS
20 BEGIN
21 O <= (not I);
22 END behavioral ;
23
24
25
26 -- ------------------------------------------------------------------
27 library ieee;
29
30 ENTITY AND2_gate IS
33 END AND2_gate ;
34
35 -- ------------------------------------------------------------------
36 ARCHITECTURE behavioral OF AND2_gate IS
37 BEGIN
38 O <= (I0 and I1);
39 END behavioral ;
40
41
42 -- ------------------------------------------------------------------
43 library ieee;
45
49 END AND3_gate ;
45
lOMoARcPSD|24554605
50
51 -- ------------------------------------------------------------------
53 BEGIN
54 O <= (I0 and I1 and I2);
55 END behavioral ;
56
57
58 -- ------------------------------------------------------------------
59 library ieee;
61
65 END AND4_gate ;
66
67 -- ------------------------------------------------------------------
69 BEGIN
70 O <= (I0 and I1 and I2 and I3);
71 END behavioral ;
72
73
74 -- ------------------------------------------------------------------
75 library ieee;
77
78 ENTITY OR3_gate IS
81 END OR3_gate ;
82
83 -- ------------------------------------------------------------------
84 ARCHITECTURE behavioral OF OR3_gate IS
85 BEGIN
86 O <= (I0 or I1 or I2);
87 END behavioral ;
88
89
90 -- ------------------------------------------------------------------
91 library ieee;
93
97 END OR4_gate ;
98
99 -- ------------------------------------------------------------------
101 BEGIN
102 O <= (I0 or I1 or I2 or I3);
103 END behavioral ;
104
105
106 -- ------------------------------------------------------------------
107 library ieee;
109
46
lOMoARcPSD|24554605
110 ENTITY NOR3_gate IS

113 END NOR3_gate ;
114
115 -- ------------------------------------------------------------------
116 ARCHITECTURE behavioral OF NOR3_gate IS
117 BEGIN
118 O <= (not (I0 or I1 or I2));
120
121
122 -- ------------------------------------------------------------------
123 library ieee;
125
126 ENTITY Adder_Half IS
131 END Adder_Half ;
132
133 -- ------------------------------------------------------------------
134 ARCHITECTURE behavioral OF Adder_Half IS
135 SIGNAL AB: std_logic_vector ( 1 downto 0 );
136 BEGIN
137 AB <= A & B;
138 --
139 with AB select
140 S <= '0' when "00",
141 '1' when "01",
142 '1' when "10",
143 '0' when "11",
144 'X' when others ;
145 --
146 with AB select
147 COUT <= '0' when "00",
148 '0' when "01",
149 '0' when "10",
150 '1' when "11",
153
154 -- ------------------------------------------------------------------
155 library ieee;
157
158 ENTITY Adder_Full IS
164 END Adder_Full ;
165
166 -- ------------------------------------------------------------------
167 ARCHITECTURE behavioral OF Adder_Full IS
168 SIGNAL ABC: std_logic_vector ( 2 downto 0 );
169 BEGIN
47
lOMoARcPSD|24554605
170 ABC <= A & B & CIN;

171 --
172 with ABC select
173 S <= '0' when "000",
174 '1' when "001",
175 '1' when "010",
176 '0' when "011",
177 '1' when "100",
178 '0' when "101",
179 '0' when "110",
180 '1' when "111",
182 --
183 with ABC select
184 COUT <= '0' when "000",
185 '0' when "001",
186 '0' when "010",
187 '1' when "011",
188 '0' when "100",
189 '1' when "101",
190 '1' when "110",
191 '1' when "111",
1 -- File: tb_mult .vhd

2 -- Description : Modulo 9 multiplier testbench
3 -- Author : Pietro Pennestri ( s2382660 )
4 -- The structure of the test bench is inspired from the
5 -- tutorial freely available on nandland .com
6 -- Date: 4/4/2021
8 -- purpose only and is NOT feasible for synthesis .
9
10
11
12 library ieee;
14 use ieee. numeric_std .all;
15 use STD. textio .all;
16 use ieee. std_logic_textio .all;
17
18 entity tb_mult is
19
20 generic (
21 in_file_name : string := "data.in";
22 out_file_name : string := "data.out"
23 );
24
25 end tb_mult ;
26
27
28 architecture structure of tb_mult is

29
30 -- ---------------------------------------------------------------------------
31 -- Declare the Adder
32 -- ---------------------------------------------------------------------------
33 component mult is
34 port (
35 -- ------------------------------------> Inputs :
48
lOMoARcPSD|24554605

38 -- ------------------------------------> Outputs :
40 -- ----------------------------------------------------
41 );
42 end component mult;
43
44
45 -- ---------------------------------------------------------------------------
46 -- Testbench Internal Signals
47 -- ---------------------------------------------------------------------------
48 file file_VECTORS : text;
49 file file_RESULTS : text;
50
51 signal r_ADD_TERM1 : std_logic_vector (3 downto 0) := ( others => '0');
53 signal w_SUM : std_logic_vector (3 downto 0);
54
55 begin
56
57 -- ---------------------------------------------------------------------------
58 -- Instantiate and Map UUT
59 -- ---------------------------------------------------------------------------
60 duv : mult
61 port map (
62 iA => r_ADD_TERM1 ,
63 iB => r_ADD_TERM2 ,
64 oC => w_SUM
65 );
66
67
68 -- -------------------------------------------------------------------------
69 -- This procedure reads the file input_vectors .txt which is located in the
70 -- simulation project area.
71 -- It will read the data in and send it to the ripple - adder component
72 -- to perform the operations . The result is written to the
73 -- output_results .txt file , located in the same directory .
74 -- -------------------------------------------------------------------------
75 process
76 variable v_ILINE : line;
77 variable v_OLINE : line;
78 variable v_ADD_TERM1 : std_logic_vector (3 downto 0);
80 variable v_SPACE : character ;
81
82 begin
83
84 file_open ( file_VECTORS , in_file_name , read_mode );
85 file_open ( file_RESULTS , out_file_name , write_mode );
86
87 while not endfile ( file_VECTORS ) loop
88 readline ( file_VECTORS , v_ILINE );
89 read(v_ILINE , v_ADD_TERM1 );
90 read(v_ILINE , v_SPACE ); -- read in the space character
92
93 -- Pass the variable to a signal to allow the ripple - carry to use it
94 r_ADD_TERM1 <= v_ADD_TERM1 ;
96
49
lOMoARcPSD|24554605
97 wait for 60 ns;

98
99 write(v_OLINE , w_SUM , right , 4);
100 writeline ( file_RESULTS , v_OLINE );
101 end loop;
102
103 file_close ( file_VECTORS );
104 file_close ( file_RESULTS );
105
106 wait;
107 end process ;
108
109 end structure ;
110
111 -- -----------------------------------------------------------------------------
112 -- top level testbench (to bind generics )
113 -- -----------------------------------------------------------------------------
114
115 entity tb_mult_top is
116 end tb_mult_top ;
117
118 architecture top of tb_mult_top is

119 component tb_mult
120 generic (
123 );
124 end component ;
125 begin
126 tg: tb_mult ;
127 end top;
1 -- File: conf_tb_mult .vhd

2 -- Description : Configuration file for tb_mult
4 -- Date: 4/4/2021
5
6 configuration conf_tb_mult of tb_mult_top is

7 for top
8 for tg: tb_mult use entity work. tb_mult ( structure )
9 generic map (
10 in_file_name => " input.txt",
11 out_file_name => " mult_out .txt"
12 );
13 for structure
14 for duv: mult use entity work.mult( structural );
15 end for;
16 end for;
17 end for;
18 end for;
19 end conf_tb_mult ;
1 -- File: adder .vhd

2 -- Description : Modulo 9 adder
5 -- Date: 4/4/2021
8
9 LIBRARY ieee;
50
lOMoARcPSD|24554605
10 USE ieee. std_logic_1164 .ALL;

11 USE ieee. numeric_std .all;
12
13
14 ENTITY adder IS
15 PORT(
16 -- ------------------------------------> Inputs :
19 -- ------------------------------------> Outputs :
21 -- ----------------------------------------------------
22 );
23 END adder;
24
25
26 ARCHITECTURE structural OF adder IS
27
28 -- --------------------------------------> Components :
29 COMPONENT NOT_gate IS
32 END COMPONENT ;
33 --
37 END COMPONENT ;
38 --
42 END COMPONENT ;
43 --
47 END COMPONENT ;
48 --
52 END COMPONENT ;
53 --
54 COMPONENT BusMultiplexer21_4 IS
55
56 PORT( Q_03: OUT std_logic ;
57 Q_02: OUT std_logic ;
60 I0_03: IN std_logic ;
68 S0 : IN std_logic );
69 END COMPONENT ;
51
lOMoARcPSD|24554605
70 --
71 COMPONENT Adder_Half IS
76 END COMPONENT ;
77 --
78 COMPONENT Adder_Full IS
84 END COMPONENT ;
85
86 -- --------------------------------------> Signals :
52
lOMoARcPSD|24554605

132
133
134 BEGIN -- structural
135
136 -- --------------------------------------> Input:
137 S014 <= iA (0);
138 S013 <= iA (1);
139 S012 <= iA (2);
140 S011 <= iA (3);
141 S018 <= iB (0);
142 S016 <= iB (1);
143 S017 <= iB (2);
144 S015 <= iB (3);
145
146 -- --------------------------------------> Output :
147 oC (0) <= S042;
148 oC (1) <= S043;
149 oC (2) <= S044;
150 oC (3) <= S045;
151
152 -- --------------------------------------> Constants :
153 S009 <= '1';
154 S010 <= '0';
155
156 -- --------------------------------------> Component Mapping :
160 C005: Adder_Half PORT MAP ( S004 , S014 , S018 , S008 );
161 C011: BusMultiplexer21_4 PORT MAP ( S045 , S044 , S043 , S042 ,
162 S041 , S040 , S039 , S038 ,
163 S010 , S009 , S009 , S009 ,
164 S001 );
188 END structural ;
1 -- File: adder_components .vhd
53
lOMoARcPSD|24554605
2 -- Description : Components used in the modulo 9 adder

5 -- Date: 4/4/2021
8 -- ------------------------------------------------------------------
9 library ieee;
11
12 ENTITY NOT_gate IS
15 END NOT_gate ;
16
17 -- ------------------------------------------------------------------
18 ARCHITECTURE behavioral OF NOT_gate IS
19 BEGIN
20 O <= (not I);
21 END behavioral ;
22
23
24
25 -- ------------------------------------------------------------------
26 library ieee;
28
32 END AND2_gate ;
33
34 -- ------------------------------------------------------------------
36 BEGIN
37 O <= (I0 and I1);
38 END behavioral ;
39
40
41 -- ------------------------------------------------------------------
42 library ieee;
44
48 END AND3_gate ;
49
50 -- ------------------------------------------------------------------
52 BEGIN
53 O <= (I0 and I1 and I2);
54 END behavioral ;
55
56
57 -- ------------------------------------------------------------------
58 library ieee;
60
54
lOMoARcPSD|24554605

64 END AND4_gate ;
65
66 -- ------------------------------------------------------------------
68 BEGIN
69 O <= (I0 and I1 and I2 and I3);
70 END behavioral ;
71
72
73 -- ------------------------------------------------------------------
74 library ieee;
76
80 END OR3_gate ;
81
82 -- ------------------------------------------------------------------
84 BEGIN
85 O <= (I0 or I1 or I2);
86 END behavioral ;
87
88
89 -- ------------------------------------------------------------------
90 library ieee;
92
93 ENTITY BusMultiplexer21_4 IS
94
95 PORT( Q_03: OUT std_logic ;

107 S0 : IN std_logic );
108 END BusMultiplexer21_4 ;
109
110 -- ------------------------------------------------------------------
111 ARCHITECTURE behavioral OF BusMultiplexer21_4 IS
112 BEGIN
113 Q_03 <= I0_03 when (S0 = '0') else
114 I1_03 when (S0 = '1') else 'X ';
115 Q_02 <= I0_02 when (S0 = '0') else
116 I1_02 when (S0 = '1') else 'X ';
117 Q_01 <= I0_01 when (S0 = '0') else
118 I1_01 when (S0 = '1') else 'X ';
119 Q_00 <= I0_00 when (S0 = '0') else
120 I1_00 when (S0 = '1') else 'X ';
55
lOMoARcPSD|24554605
122
123 -- ------------------------------------------------------------------
124 library ieee;
126
127 ENTITY Adder_Half IS
132 END Adder_Half ;
133
134 -- ------------------------------------------------------------------
135 ARCHITECTURE behavioral OF Adder_Half IS
136 SIGNAL AB: std_logic_vector ( 1 downto 0 );
137 BEGIN
138 AB <= A & B;
139 --
140 with AB select
141 S <= '0' when "00",
142 '1' when "01",
143 '1' when "10",
144 '0' when "11",
146 --
147 with AB select
148 COUT <= '0' when "00",
149 '0' when "01",
150 '0' when "10",
151 '1' when "11",
154
155 -- ------------------------------------------------------------------
156 library ieee;
158
159 ENTITY Adder_Full IS
165 END Adder_Full ;
166
167 -- ------------------------------------------------------------------
168 ARCHITECTURE behavioral OF Adder_Full IS
169 SIGNAL ABC: std_logic_vector ( 2 downto 0 );
170 BEGIN
171 ABC <= A & B & CIN;
172 --
173 with ABC select
174 S <= '0' when "000",
175 '1' when "001",
176 '1' when "010",
177 '0' when "011",
178 '1' when "100",
179 '0' when "101",
180 '0' when "110",
181 '1' when "111",
56
lOMoARcPSD|24554605

183 --
184 with ABC select
185 COUT <= '0' when "000",
186 '0' when "001",
187 '0' when "010",
188 '1' when "011",
189 '0' when "100",
190 '1' when "101",
191 '1' when "110",
192 '1' when "111",
1 -- File: tb_adder .vhd

2 -- Description : Modulo 9 adder testbench
4 -- The structure of the test bench is inspired from the
5 -- tutorial freely available on nandland .com
6 -- Date: 4/4/2021
8 -- purpose only and is NOT feasible for synthesis .
9
10
11 library ieee;
13 use ieee. numeric_std .all;
14 use STD. textio .all;
15 use ieee. std_logic_textio .all;
16
17 entity tb_adder is
18
19 generic (
22 );
23
24 end tb_adder ;
25
26
27 architecture structure of tb_adder is
28
29 -- ---------------------------------------------------------------------------
30 -- Declare the Adder
31 -- ---------------------------------------------------------------------------
32 component adder is
33 port (
34 -- ------------------------------------> Inputs :
37 -- ------------------------------------> Outputs :
39 -- ----------------------------------------------------
40 );
41 end component adder;
42
43
44 -- ---------------------------------------------------------------------------
45 -- Testbench Internal Signals
46 -- ---------------------------------------------------------------------------
47 file file_VECTORS : text;
57
lOMoARcPSD|24554605
48 file file_RESULTS : text;

49
52 signal w_SUM : std_logic_vector (3 downto 0);
53
54 begin
55
56 -- ---------------------------------------------------------------------------
57 -- Instantiate and Map UUT
58 -- ---------------------------------------------------------------------------
59 duv : adder
60 port map (
61 iA => r_ADD_TERM1 ,
62 iB => r_ADD_TERM2 ,
63 oC => w_SUM
64 );
65
66
67 -- -------------------------------------------------------------------------
68 -- This procedure reads the file input_vectors .txt which is located in the
69 -- simulation project area.
70 -- It will read the data in and send it to the ripple - adder component
71 -- to perform the operations . The result is written to the
72 -- output_results .txt file , located in the same directory .
73 -- -------------------------------------------------------------------------
74 process
75 variable v_ILINE : line;
76 variable v_OLINE : line;
79 variable v_SPACE : character ;
80
81 begin
82
83 file_open ( file_VECTORS , in_file_name , read_mode );
84 file_open ( file_RESULTS , out_file_name , write_mode );
85
86 while not endfile ( file_VECTORS ) loop
87 readline ( file_VECTORS , v_ILINE );
89 read(v_ILINE , v_SPACE ); -- read in the space character
91
92 -- Pass the variable to a signal to allow the ripple - carry to use it
95
96 wait for 60 ns;
97
98 write(v_OLINE , w_SUM , right , 4);
99 writeline ( file_RESULTS , v_OLINE );
100 end loop;
101
102 file_close ( file_VECTORS );
103 file_close ( file_RESULTS );
104
105 wait;
106 end process ;
107
58
lOMoARcPSD|24554605
108 end structure ;

109
110 -- -----------------------------------------------------------------------------
111 -- top level testbench (to bind generics )
112 -- -----------------------------------------------------------------------------
113
114 entity tb_adder_top is
115 end tb_adder_top ;
116
117 architecture top of tb_adder_top is

118 component tb_adder
119 generic (
122 );
123 end component ;
124 begin
125 tg: tb_adder ;
126 end top;
1 -- File: conf_tb_adder .vhd

2 -- Description : configuration for tb_adder
4 -- Date: 4/4/2021
5
6 configuration conf_tb_adder of tb_adder_top is
7 for top
8 for tg: tb_adder use entity work. tb_adder ( structure )
9 generic map (
10 in_file_name => " input.txt",
11 out_file_name => " adder_out .txt"
12 );
13 for structure
14 for duv: adder use entity work.adder( structural );
15 end for;
16 end for;
17 end for;
18 end for;
19 end conf_tb_adder ;
Honor Pledge
I promise that I have not used unauthorised help from people or other sources
for completing my exam. I created the submitted answers all by myself during
the time slot that was allocated for that specific exam part.
Pietro Pennestrì
59

Take Home Exam Solutions

Uploaded by

Copyright:

Available Formats

Take Home Exam Solutions

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Take Home Exam Solutions

Uploaded by

Copyright:

Available Formats

lOMoARcPSD|24554605

Take Home Exam - Solutions

Computer Arithmetic (Technische Universiteit Delft)

Studeersnel wordt niet gesponsord of ondersteund door een hogeschool of universiteit

ET4170 Take Home Exam 2021

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

Whenever possible, it is convenient, to choose comparison constants as pow-

g−1 = ab̄ + ac̄ + ad¯ + aē

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

(abcde)2 = (abcd)2 + (abcd)2 + (000e)2 (2)

Figure 1: Dot notation of sum si

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

x=60 -> (12 | 0 | 8)

y=-35 -> (13 | 10 | 4)

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

MOD MOD MOD

MOD 16 MOD 15 MOD 13

AREA RNS< AREA RC

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

(4|0|2) > (3|4|5)

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

23 bits + 1 hidden bit + 1 sign bit = 25 bits

In the following different implementation of the 25 bits adder will be discussed

Table 1: Area evaluation

Carry Look - Ahead Adder

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

Figure 2: 25 bits Carry look - ahead adder

CCLA = 6 × (4 BIT LA ADDER) + 2 × (4 BIT CARRY NET)

Single-Level Carry Select

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

High 12 bits Low 13 bits

Figure 3: General structure for a 25 bit carry select adder

The area of the implemented unit can be expressed as:

C(CARRY SELECT ADD) =9 × (4 BIT LA ADDER) + 3 × (4 BIT CARRY NET)

The delay of a single BIT 2 to 1 MUX is assumed as 1 time unit.

T(CARRY SELECT ADD) =TADD (13 BIT) + 1

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

25 bits input 25 bits input

3..0 3..0 3..0 3..0 3..0 3..0

3..0 3..0 3..0 3..0 3..0 3..0

Computer Arithmetic - Academic Year 2020 - 2021

Title 25 bits Carry Select Adder

Author P.Pennestri (s2382660) Date April 2021

Figure 4: 25 bits Single-Level Carry Select Adder

Two-Level Carry Select Adder

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

cout, High 12 bits High 6 bits High 7 bits

Figure 5: General structure of 25 bit two level carry select adder

Different implementations of the adders of Figure 5 are possible. In particu-

• Sub-adders implemented as Carry look-ahead

C(2LEVEL SELECT ADD) =7 × (4 BIT LA ADDER) + 7 × (4 BIT CARRY NET)

where 1 LA CIRCUIT = 1 × AND + 2 × XOR.

T(2 LEVEL SELECT ADD) =TCarry look−ahead adder (7 BIT) + 2

A detailed schematic of this implementation is depicted in Figure 6.

• Sub-adders implemented as Ripple carry implementation

C(2LEVEL SELECT ADD) =6 × 6 BIT RIPPLE CARRY ADDER+

T(2 LEVEL SELECT ADD) =TCarry ripple adder (7 BIT) + 2

Take Home Exam 2021 ET4170 P. Pennestrì s2382660

25 bits input 25 bits input