Full Adder Implementation using FPGA

Field Programmable Gate Array

9rogram

This chapter introduces the principles, implementation and programming of configurable logic circuits, from the point of view of cell design and interconnection strategy.

1. Introduction
Field programmable gate arrays FPGA! are specific integrated circuits that can be user" programmed easily. The FPGA contains versatile functions, configurable interconnects and an input#output interface to adapt to the user specification. FPGAs allow rapid prototyping using custom logic structures, and are very popular for limited production products. $odern FPGA are e%tremely dense, with a comple%ity of several millions of gates which enable the emulation of very comple% hardware such as parallel microprocessors, mi%ture of processor and signal processing, etc& 'ne (ey advantage of FPGA is their ability to be reprogrammed, in order to create a completely different hardware by modifying the logic gate array. The usual structure of FPGA is given in figure )"1.

1|Page +,,$,+"-assan

*ept of

,onfigured I#' pads

Programm abl e log ic blo c(s

P ro gr a m m a bl e in te rc o n n e ct p oi nt s

Figure"1. /asic structure of a field programmable gate array

'ne e%ample of a very simple function 0"input 1'2! implemented in a FPGA is given in figure )"3. Three pads on the left are configured as inputs, one logic bloc( is used to create the 0"input 1'2 and one pad on the right is used as output. The propagation of signals is handled by interconnect lines, connected together at specific programmable interconnect points.

Pads configured as inputs

Programmable l o g ic bloc( A configured as Programmable 1'2 interconnect points / Pad configured , as output f4A5/5,

Interconnect lines

Figure"3. 6sing a field programmable gate array to build a 0"input 1'2 gate

Figure"0. +7uivalent circuit for the FPGA configured in 1'20 gate Three pads are configured as inputs and represent the logical information A, / and , Figure )"0!. An internal routing path is created to establish an electrical lin( between the I#' region and the logic bloc. Internally, the logic bloc may be configured in any combination of se7uential basic function. +ach logic bloc usually supports 0 to 8 logic inputs. In our e%ample, the bloc is configured as a 0"input 1'2. Then, other internal routing wires are configured in order to carry

out the signal to an I#' pad configured as an output. The global propagation delay of such architecture is evidently very high, if compared to a 0"input 1'2 gate that may be found in the cell library. This is usually the price to pay for configurable logic circuits. 9otice that FPGA not only e%ist as simple components, but also as macro"blocs in system"on"chip designs Figure )":!. In the case of communication systems, the configurable logic may be dynamically changed to adapt to improved communication protocol. In the case of very low power systems, the configurable logic may handle several different tas(s in series, rather than embedding all corresponding hardware that never wor(s in parallel.

,P6 FPGA

$+$'2<

FPGA

I9T+2FA,+

a! ;tand"alone FPGA

b! FPGA internal bloc(

Figure":. FPGA e%ist as stand"alone Ics or blocs within a system"on"chip

3. Configurable Logic Circuits

The programmable logic bloc( must be able to implement all basic logic functions, that is I9=, A9*, 9A9*, '2, 9'2, 1'2, 19'2, etc... ;everal approaches are used in FPGA industry to achieve this goal. The

first approach consists in the use of multiple%or, the second one in the use of loo("up tables.

MULTIPLEXORS
;urprisingly, a two"input multiple%or can be used as a programmable function generator, as illustrated in table )"1. 2emember that the multiple%or output f is e7ual to i> if en4>, and i1 if en41. For e%ample, the inverter is created if the multiple%or input i> is e7ual to 1, i1 is e7ual to >, and enable is connected to A. In that case, the output f is the ?A. The figure )"@ describes the use of multiple%or to produce the '2, A9*, 9'T and /6F functions. Boolea expressi n on for output f f=A f=~(A) f=A&B f=A!B

Function BUF(A) NOT(A) AND(A,B) O (A,B)

i0 0 1 0 B

i1 A 0 B 1

en 1 A A A

Table "1. use of multiple%or to build logic functions

Figure "@. use of multiple%or to build logic functions

Although 9'T, A9* and '2 are directly available, other functions such as 9A9*, 9'2 and 1'2 cannot be built directly using a single 3"input multiple%or, but need at least two multiple%or circuits.

Figure "A. The 1'2 gate built from 3 multiple%or circuits

The 1'2 function is shown in figure )"A. The :"input 1'2 gate would re7uire A multiple%or cells. 2emember that each multiple%or cell consists of a minimum of A transistors for a buffered output, and has 0 delay stages The two inverters and the pass transistor!. The 1'2: implementation would comprise a total of 18 delay stages, which is far too important. Therefore, the multiple%or approach is not very efficient for many logical functions

.Look Up Table
The loo("up table B6T! is by far the most versatile circuit to create a configurable logic function. The loo("up table shown in table )"3 has 0 main inputs F>,F1 and F3. The main output is Fout, which is a logical function of F>, F1 and F3. The output Fout is defined by the values given to =alueC>D&..=alueCED.

The three values F>,F1, F3 create a 0"bit address i between > and E, so that Fout gets the value of =alueCiD. In the e%ample of table )"3, the input creates the number @, so =alueC@D is routed to Fout. The table below gives =alueCiD for the most common logical functions of F>,F1 and F3.
i4@ =alueC>D > F> 1 F1 =alueC0D F o u t =alueC1D =alueC3D

1 F3 =alueC:D =alueC@ =alueCAD =alueCED Boo("up"table

Function ~F0 ~F1 ~F% F0&F1 F0!F1!F% F0+F1+F%

"alu e #0$ 0 0 0 0 0 0

"alu e #1$ 1 0 0 0 1 1

"alu e #%$ 0 1 0 0 1 1

"alu e #&$ 1 1 0 1 1 0

"alu e #'$ 0 0 1 0 1 1

"alu e #($ 1 0 1 0 1 0

"alu e #)$ 0 1 1 0 1 0

"alu e #*$ 1 1 1 1 1 1

Table )"3. Bin( between basic logic functions and the information stored in =alueC>D..CED
In the case of the 0"input 1'2, the set of values of Fout given in the truth"table of table )"0, must be assigned to =alueC>D..=alueCED. In the schematic diagram shown in figure )"E, we must assign manually the Fout truth"table to each of the 8 buttons. Then Fout produces the 1'2 function of inputs F>, F1 and

F3. F% 0 0 F1 0 0 F0 0 1 Fout= F0+F1+F% 0 1 Assi,ne- to "alue#0$ "alue#1$

0 0 1 1 1 1

1 1 0 0 1 1

0 1 0 1 0 1

1 0 1 0 0 1

"alue#%$ "alue#&$ "alue#'$ "alue#($ "alue#)$ "alue#*$

Table "3. Truth"table of the 0"input 1'2 gate for its implementation in a loo("up"table

Bogic inputs F>,F1 and F3

+lementar y cell for the 0"to"8 demultiple %or

+ach value is assigne d the 1'20 truth" table data

?F>F?F1F?F3

F>F?F1F?F3

?F>FF1F?F3

Fout4F>5F15F3
F>FF1F?F3

?F>F?F1FF3

F>F?F1FF3

?F>FF1FF3

F>FF1FF3

Figure )"E. The output f produces a logical function Fout according to a loo("up"table stored in memory points =alueCiD

Memor Points
$emory points are essential components of the configurable logic bloc(s. The memory point is used to store one logical value, corresponding to the logic truth table. For a 0"input function F>,F1,F3 in the previous B6T!, we need an array of 8 memory points to store e%ist the here information There several also =alueC>D..=alueCED.

approaches to store one single bit of information. The one that is illustrated in figure )"8 consists of *"reg cells. +ach register stores one logical information =alueCiD. The *reg cells are chained in order to limit the control signals ,loc(Prog to and one one cloc( data

signal *ataProg. The logical data =alueCiD is fully programmed by a word of 8 bits sent in series to the signal *ataPro

Figure "8. The loo("up information is given by a shift register based on *"reg cells!.

The configuration of the 0"input B6T into a 0"input 1'2 gate obeys to a strict protocol described in figure )"). A series of 8 active edges is generated by the ,loc(Prog signal *reg is active on fall edges!. This is done by configuring a pulse generator with series of >"1 as shown below.

Figure "). Programming the ,loc(Prog pulse to generate 8 active edge At each active edge, the shift register is fed by a new value presented se7uentially at input *ataProg. As the *"reg is active on fall edge, data may be changed on each rise edge. 9otice that the last *reg corresponds to =alueCED. Therefore, =alueCED must be inserted first, and =alueC>D last. This means that the *ataProg pulse must describe the truth table in reverse order, as shown below.
,loc( disabled, 1'20 wor(ing Active edge

1 *ata changed when ,loc( is =alueCED inactive

>

>

>

>

=alueC >D

Figure "1>. At the end of the 8"th cloc( period, the B6T is configured as a 0"input 1'2

$ost FPGA designs use *reg to store the B6T configuration. 9otice that the configuration is lost when the power supply is down.

Implementation in !SC"
In *;,-, a loo("up"table symbol is proposed in the symbol menu Figure )"1:!. It is e7uivalent to the schematic diagram of figure )"8. An important property of the B6T symbol is its ability to retain the internal programming as a non"volatile memory would do. The userGs interface of the B6T symbol is given in figure )"1:. There are three ways of filling the loo("up"table. one consists in defining each array element with a > or a 1. The number corresponds to the logic combination of inputs F3,F1,F>. For e%ample nH: is coded 1>> in binary, corresponding to F341,F14> and F>4>. A second solution consists in choosing the function description in the list. The logic information Fout assigned to each combination of the inputs updates the loo("up"table. A third

solution is also proposed. enter a description based on inputs F>,F1 and F3, and the logic operators I?I 9ot!, IFG And!, IJI 'r! and I5I 1or!. Then clic( the button

Fill LUT to transfer the result of the e%pression to the table.

Figure "1:. The loo("up"table symbol

0. Programmable Logic #lock

The programmable logic bloc( consists of a loo("up table, a *"register and some multiple%ors. There e%ist numerous possible structures for logic bloc(s. Ke present in figure )"1@ a simple structure which has some similarities with the 1ilin% 1,@3>> series ;ee C;mithD for detailed information on its internal structure!. The configurable bloc( contains two active structures, the But and the *"reg, that may wor( independently or be mi%ed together. The output of the loo("up"table is directly connected to the bloc( output Fout. The output can also serve as the input data for the *"register, than(s to the multiple%or controlled by *ataInLFout. The *ata'ut net can

simply pass the signal *ataIn, in that case the cell is transparent. The *ata'ut signal can also pass the signal nM, depending on the multiple%or status controlled by *ataInLnM

A#?A#?Fout on A cloc( edge

?A#?Fout

A#Fout A#Fout on cloc( edge Fout directly

Figure "1@. ;imple configurable logic bloc( including the Boo( 6p Table and a *"register

The bloc( now consists of the B6T and the *"register. Ke chain the information *ataInLFout and *ataInLnM on the path of the shift register by adding 3 supplementary *reg cells. +ach *reg still uses the same cloc( ,loc(Prog and chained input data *ataProg. The complete circuit is shown in figure "1A.

Figure "1A. The Boo( 6p Table, the *"register and the shift register including the 3 multiple%or cells

. The
configuring of the bloc( is achieved than(s to 1> active cloc( edges on ,loc(Prog, and 1> serial data on *ataProg. The chain of *reg starts at *reg> 6pper *reg in figure )"1A, which produced =alueC>D! and stops at *reg) 2ight side of figure )"1A which produced *ataIn#nM!. The information that flows at the far end of the register chain is defined at the first cycle, while the closest register is configured by the data present at the last active cloc( edge.,

*ata enters in serial here

9earest *reg info used for =alC>D

Farthest *reg info used for *ataIn#97

*ataPro g ,loc(Prog

*re g>

*re g1

*re g3

*re g)

.loc/ c2cle Data3ro,

% Datai n 5 Fou t

& "a l #* $

' " a l # ) $

( "a l #( $

) "a l #' $

* "a l # & $

0 " a l # % $

1 "a l #1 $

10 "a l #0 $

Data4n5 N6

Table "0. ;erial data information used to program the B6T memory points

:. Interconnection bet$een blocks

The interconnection strategy between logic bloc(s is detailed in this paragraph. Ke shall focus on the programmable interconnect point and the programmable switching matri%. Then, we will discuss the global implementation of the structure.

Programmable Interconnect Point

The elementary programmable interconnect point PIP NGlossO!may be found in the Advanced set of Switches symbols Figure )"1E!. It consists of a configurable bridge between two
interconnects.

The PIP may have two states. I'nI and I'ffI. <ou may switch from I'nI to I'ffI by a double clic( on the symbol ;creen shown in figure )"18! and a clic( on the button On o!!.

Programmable interconnect point Boo("up"table ;witching matri%

+lementary switch

Figure "1E. The programmable interconnect point PIP! in the palette of symbols

, l i c (

h e r e t o c h a n g e t h e s t a t e

Figure "18. ,hanging the state of the PIP

The bridge can be built from a transmission gate, controlled once again by a *"reg cell Figure )"1)!. Khen the register information contains a >, the transmission gate is off and no lin( e%ists between

Interco1 and Interco3. Khen the information held by the register is 1, the transmission gate establishes a resistive lin( between Interco1 and Interco3. The resistance value is around 1>> .

a! ;witch off

b! ;wicth on

Figure "1). Internal structure of the PIP and illustration of its behavior when 'ff a! and 'n b! The regrouping of programmable interconnect points into matri% is of (ey importance to ensure the largest routing fle%ibility. +%amples of 0%0 and 0%3 PIP matri% are shown in figure )"3>. The lin( between In1 and 'ut1, In3 and 'ut3, In0 and 'ut0 is achieved by turning some PIP on. A specific routing tool usually handles this tas(, but the manual re" arrangement is not rare in some comple% situations. In *;,-, Pust press the (ey I'I to switch the PIP 'n and off.

Figure "3>. $atri% of programmable interconnects points

S$itc%ing Matri&
The switching matri% is a sophisticated programmable interconnect point, which enables a wide range of routing combinations within a single interconnect crossing. The aspect of the switching matri% is given in figure )"31. The matri% includes A configurable bridges between the two main interconnects.

The switching matri% symbol may be found in Advanced set of Switches symbols. /y a double clic( on the matri% symbol, you get access to the A On O!! switches.

, l i c ( o n o n e o f t h e s e A s w i t c h e s t o c o n f i g u r e t h e r o u

t i n g Figure "31. ,hanging the state of the matri% Fpga$atri%.;,-! To ease the programming of the matri%, short cuts e%ist in *;,-. <ou can change the state of the matri% by placing the cursor on the desired symbol and pressing the following (eys.

Q Q Q Q

To switch off the matri%, press the (ey IoI. To switch on the matri%, press the (ey I'I. To enable an horiRontal lin(, press the (ey I"I. To enable a vertical lin(, press the (ey IJI.

+%amples of 0%3 and 0%0 switching matri% are given in figure )"33. The routing possibilities are numerous, which improves the configurability of the logic blocs.

Figure "33. 0%3 switching matri% and e%ample of routing strategy between A inputs and outputs 1@

Implementation of t%e S$itc%ing Matri&

From a practical point of view, the switching matri% can be built from a regrouping of A transmission gates Figure )"30!. +ach transmission gate is controlled by an associated *reg cell, which memoriRes the desired configuration. The *reg cells are chained so that one single input *ataIn and one cloc( Boad,loc( are enough to configure the matri%.

Figure "30. The transmission gates placed on the routing lines to build the matri% Fpga$atri%0.;,-!

'rra of #locs
The configurable blocs are associated with programmable interconnect points and switching matri% to create a complete configurable core. An e%ample of double configurable bloc( and its associated configurable routing is proposed in figure "3:.

,onfigurable I#'s

/loc( configuration data

Global cloc(

;witching matri%

PIP

Global reset

Figure "3:. ,onfigurable bloc(s, switching matri%, configurable I#'s and arrays of PIP

(ull)'dder E&ample

The truth table and logical e%pression for the full"adder are recalled in Table )"0. The implementation of the ,A22< and ;6$ function is achived by programming two loo("up tables according to the truth"tables reported in table )"0. FU77 ADD8 A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 9U
:

. 0 1 0 1 0 1 0 1

.A
;

89 U7T

0 1 1 0 1 0 0 1

0 0 0 1 0 1 1 1

0 1 1 % 1 % % &

Table )"0. The full"adder truth"table

A, /, ,

;u m

,arr y

/loc( 1 /loc( 3 ;6$! ,A22<!

Figure "3@. The ;6$ and ,A22< functions to realiRe the full"adder in FPGA

The general diagram of the Full adder implementation is given in figure )"3@. 'ne

programmable logic bloc( /loc(1 supports the generation of the sum for given logic values of the inputs A,/ and ,. The information needed to configure /loc(1 as a ;um function 0" input 1'2! is given in table )":. 9otice that we only use the B6T in this programmable logic bloc(. The *reg is not active, and we only e%ploit the output of the B6T Fout, which is configured as the ;um. The signal ;um propagates outside the bloc( to the output interface region by e%ploiting the interconnect resources and switching matri%. The other programmable logic bloc( /loc(3 supports the generation of the signal ,arry, from the same inputs A,/ and ,. The programming of /loc(3 is also given in table )":. The result ,arry is e%ported to the output interface region as for the ;um signal. Again, in this bloc(, only the B6T is active.

Bloc/ 1 (9u< of F0,F1 an- F%) .2cle 1 % & ' Datai "al#* "al#) Data4n n $ $ N6 Fout 0 0 1 0 Bloc/ % (.arr2 of F0,F1 F%) .2cle 1 % & Datai "al#* Data4n n $ N6 Fout 0 0 1 an' "al#) $ 1

( "al#( $ 0

) "al#' $ 1

* "al#& $ 0

0 "al#% $ 1

1 "al#1 $ 1

10 "al#0 $ 0

( "al#( $ 1

) "al#' $ 0

* "al#& $ 1

0 "al#% $ 1

1 "al#1 $ 0

10 "al#0 $ 0

Table ":. ;erial data used to configure the logic bloc(s 1F3 as ;6$ and ,A22<

Figure "3A. ;imulation of the full"adder implemented in 3 configurable bloc(s

The programming se7uence is contained in the piece"wise"linear symbols Prog/loc(1 and Prog/lco(3. As seen in the chronograms of figure )"3E, the program cloc( ,loc(Pgm is only active at the initialiRation phase, to shift the logic information to the memory points inside the bloc(s which configure each multiple%or. The routing of the signals A,/ and , as well as ;um and ,arry has been done manually in the circuit shown in figure )"3A. In reality, specific placement#routing tools are provided to generate the electrical structure automatically from the initial schematic diagram, which avoids manual errors and limits conflicts or omissions.
InitialiRation phase 'perationnal phase

Figure "3E. ,hronograms of the full"adder FPGA

Conclusion
In this chapter, we have given a brief introduction to field programmable gate arrays, from the point of view of cell design. Firstly, the use of multiple%or and loo("up" tables for building configurable logic circuits has been illustrated. ;econdly, the programming of memory points using chained *"registers and fuse has been described. Thirdly, we have described the programmable interconnect points and switching matri%, with their implementation in *;,-. Finally, the implementation of a full adder and a cloc( divider have been performed using two configurable logic bloc(s, programmable interconnect points and switching matri%.

References
C;mithD $ichael. S. ;. ;mith IApplication ;pecific Integrated ,ircuitsI, Addison Kesley, I;/9 >"3>1"@>>33"
C ; h a r m a D

N a d d O

C 6 y e m u

r a D

N a d d O