Design of Carry Lookahead Adders :
To reduce the computation time, there are faster ways to add two binary numbers by using carry lookahead adders. They work by creating two signals P and G known to be Carry Propagator and Carry Generator. The carry propagator is propagated to the next level whereas the carry generator is used to generate the output carry ,regardless of input carry. The block diagram of a 4-bit Carry Lookahead Adder is shown here below -
The number of gate levels for the carry propagation can be found from the circuit of full adder. The signal from input carry Cin to output carry Cout requires an AND gate and an OR gate, which constitutes two gate levels. So if there are four full adders in the parallel adder, the output carry C5 would have 2 X 4 = 8 gate levels from C1 to C5. For an n-bit parallel adder, there are 2n gate levels to propagate through.
Design Issues :
The corresponding boolean expressions are given here to construct a carry lookahead adder. In the carry-lookahead circuit we ned to generate the two signals carry propagator(P) and carry generator(G),
Pi = Ai ⊕ Bi
Gi = Ai · Bi
The output sum and carry can be expressed as
Sumi = Pi ⊕ Ci
Ci+1 = Gi + ( Pi · Ci)
Having these we could design the circuit. We can now write the Boolean function for the carry output of each stage and substitute for each Ci its value from the previous equations:
C1 = G0 + P0 · C0
C2 = G1 + P1 · C1 = G1 + P1 · G0 + P1 · P0 · C0
C3 = G2 + P2 · C2 = G2 P2 · G1 + P2 · P1 · G0 + P2 · P1 · P0 · C0
C4 = G3 + P3 · C3 = G3 P3 · G2 P3 · P2 · G1 + P3 · P2 · P1 · G0 + P3 · P2 · P1 · P0 · C0
Design of Carry Lookahead Adders :
Basic stage
Multiple choice questions:
- What is the main difference between half-adders and full-adders?
- Which one of the following will give the sum of full adders as output?
- The MOST commonly used system for representing signed binary numbers is the
- The time required for a pulse to decrease from 90 to 10 per cent of its maximum value is called
- Odd parity of word can be conveniently tested by
Nothing basically; full-adders are made up of two half-adders
Full-adders can handle double digit numbers
Full-adders have a carry input capability
Half-adders can only handle single digit numbers
Three bit parity checke
Three point majority circuit
Three bit counter
Three bit comparator
2's-complement system
1's-complement system
10's-complement system
Sign-magnitude system
Propagation delay
Rise time
Decay time
Binary level transition period
AND gate
OR gate
XOR gate
NOR gate
Subjective questions:
- What is the reason for using look ahead carry adder?
- What is the number of gate levels for output carry in a parrel adder composed of 4 full adders?
- What is the number of gate levels to propagate through for an n-bit parallel adder?
Advanced stage
Multiple choice questions:
- What distinguishes the look-ahead-carry adder?
- The time and space complexity of carry look ahead adder are respctively
- The number of full and half-adders required to add 16-bit numbers is
- The MOST commonly used system for representing signed binary numbers is the
- Ripple carry delay is increased in carry-look-ahead adder
- Carry of a full adder is a symmetric function
It requires advance knowledge of the final answer
It is faster than a ripple-carry adder
It is slower than the ripple-carry adder
It is easier to implement logically than a full-adder
O(n), O(nlogn)
O(n), O(1)
O(n), O(n)
O(logn), O(nlogn)
1 half-adder, 5 full-adders
4 half-adders, 12 full-adders
8 half-adders, 8 full-adders
16 half-adders, 0 full-adders
2's-complement system
1's-complement system
10's-complement system
Sign-magnitude system
True
False
True
False
Subjective questions:
- What is the worst case delay of an n-bit carry look ahead adder?
- What is the advantage of carry look head adder over ripple carry adder?
- What is the generate and propagate functions expression at level-2?
- What is the number of additions in carry look head adder for adding m numbers?
Design of Carry Lookahead Adders :
Procedure to perform the experiment:Design of Carry Lookahead Adders- Start the simulator as directed.This simulator supports 5-valued logic.
- To design the circuit we need 7 half adder, 3 OR gate, 1 V+(to give 1 as input), 3 Digital display(2 for seeing input and 1 for seeing output sum), 1 Bit display(to see the carry output), wires.
- The pin configuration of a component is shown whenever the mouse is hovered on any canned component of the palette or press the 'show pinconfig' button. Pin numbering starts from 1 and from the bottom left corner(indicating with the circle) and increases anticlockwise.
- For half adder input is in pin-5,8 output sum is in pin-4 and carry is pin-1
- Click on the half adder component(in the Adder drawer in the pallet) and then click on the position of the editor window where you want to add the component(no drag and drop, simple click will serve the purpose), likewise add 6 more full adders(from the Adder drawer in the pallet), 3 OR gates(from Logic Gates drawer in the pallete), 1 V+, 3 digital display and 1 bit Displays(from Display and Input drawer of the pallet,if it is not seen scroll down in the drawer)
- To connect any two components select the Connection menu of Palette, and then click on the Source terminal and click on the target terminal. According to the circuit diagram connect all the components, connect V+ to the upper input terminals of 2 digital displays according to you input. connect the OR gates according to the diagram shown in the screenshot connect the pin-1 of the half adder which will give the final carry output. connet the sum(pin-4) of those adders to the terminals of the third digital display which will give output sum. After the connection is over click the selection tool in the pallete.
- See the output, in the screenshot diagram we have given the value 0011(3) and 0111(7) so get 10 as sum and 0 as carry.you can also use many bit switches instead of V+ to give input and by double clicking those bit switches can give different values and check the result.
Components :
The components needed to create 4 bit carry lookahead adder is listed here -
- 7 half-adders: 4 to create the look adder circuit, and 3 to evaluate Si and Pi · Ci
- 3 OR gates to generate the next level carry Ci+1
- wires to connect
- LED display to obtain the output
Objective of 4 bit carry lookahead adder:
It computes the carries parallely thus greatly speeding up the computation.
- understanding behaviour of carry lookahead adder from module designed by the student as part of the experiment
- understanding the concept of reducing computation time with respect of ripple carry adder by using carry generate and propagate functions
- the adder wil add two 4 bit numbers
Examining behaviour of carry lookahead adder for the module designed by the student as part of the experiment (refer to the circuit diagram)
Loading data in the carry lookahead adder (refer to procedure tab for further detail and experiment manual for pin numbers)
- load the two input numbers in the adder units as:
- 1111 and 0001
Examining the carry generate and propagate function behaviour:
- check output sum 0000
- check final output carry 1
- check intermediate carry bit and sum bit of the unit adders and verify the values of carry generate and propagate function (refer to theory)
- probing the any port can be done by verifying the color of the wire coming out of the port
Recommended learning activities for the experiment: Leaning activities are designed in two stages, a basic stage and an advanced stage. Accomplishment of each stage can be self-evaluated through the given set of quiz questions consisting of multiple type and subjective type questions. In the basic stage, it is recommended to perform the experiment firstly, on the given encapsulated working module, secondly, on the module designed by the student, having gone through the theory, objective and procuder. By performing the experiment on the working module, students can only observe the input-output behavior. Where as, performing experiments on the designed module, students can do circuit analysis, error analysis in addition with the input-output behavior. It is recommended to perform the experiments following the given guideline to check behavior and test plans along with their own circuit analysis. Then students are recommended to move on to the advanced stage. The advanced stage includes the accomplishment of the given assignments which will provide deeper understanding of the topic with innovative circuit design experience. At any time, students can mature their knowledge base by further reading the references provided for the experiment.
- if value is UNKNOWN, wire color= maroon
- if value is TRUE, wire color= blue
- if value is FALSE, wire color= black
- if value is HI IMPEDENCE, wire color= green
- if value is INVALID, wire color= orange
Test plan:
- Set one input to zero(0) and check the output.
- Set one input to all one and another as 0001 in carry lookahead adder.
- Check the carry lookahead adder with two arbritrary input. Check the output and show the carry propagator and generator output for every bit.
Use Display units for checking output. Try to use minimum number of components to build. The pin configuration of the canned components are shown when mouse hovered over a component.
Assignment Statements :
- Design a 4-bit carry lookahead adder circuit using half adders and full adders and test it by giving proper input.
- Design a 16-bit carry lookahead adder circuit using half adders and full adders and test it by giving proper input.
Design of Carry Lookahead Adders :
General guideline to use the simulator for performing the experiment:- Start the simulator as directed. For more detail please refer to the manual for using the simulator
- The simulator supports 5-valued logic
- To add the logic components to the editor or canvas (where you build the circuit) select any component and click on the position of the canvas where you want to add the component
- The pin configuration is shown when you select the component and press the 'show pinconfig' button in the left toolbar or whenever the mouse is hovered on any canned component of palette
- To connect any two components select the connection tool of palette, and then click on the source terminal and then click on the the target terminal
- To move any component select the component using the selection tool and drag the component to the desired position
- To give a toggle input to the circuit, use 'Bit Switch' which will toggle its value with a double click
- Use 'Bit Display' component to see any single bit value. 'Digital Display' will show the output in digital format
- undo/redo, delete, zoom in/zoom out, and other functionalities have been given in the top toolbar for ease of circuit building
- Use start/stop clock pulse to start or stop the clock input of the circuit. Clock period can be set from the given 'set clock' button in the left toolbar
- Use 'plot graph' button to see input-output wave forms
- Users can save their circuits with .logic extension and reuse them
- After building the circuit press the simulate button in the top toolbar to get the output
- If the circuit contains a clock pulse input, then the 'start clock' button will start the simulation of the whole circuit. Then there is no need to again press the 'simulate' button
- If you are using linux platform then click on 'Linux(32 bit)' or if you are using then click on 'Windows(32 bit)'
- Start the simulator as directed.
- To design the circuit we need 7 half adder, 3 OR gate, 1 bit switch (to give 1 as input), 3 digital display (2 for seeing input and 1 for seeing output sum), 1 bit display (to see the carry output), wires.
- The pin configuration of a component is shown whenever the mouse is hovered on any canned component of the palette. Pin numbering starts from 1 and from the bottom left corner (indicated with the circle) and increases anticlockwise.
- For half adder input is in pin-5,8 output sum is in pin-4 and carry is pin-1
- Click on the half adder component (in the Adder drawer in the pallet) and then click on the position of the editor window where you want to add the component (no drag and drop, simple click will serve the purpose), likewise add 6 more full adders(from the Adder drawer in the pallet), 3 OR gates (from Logic Gates drawer in the pallete), 1 bit switch, 3 digital displays and 1 bit display (from Display and Input drawer of the pallet, if it is not seen scroll down in the drawer)
- To connect any two components select the Connection menu of Palette, and then click on the Source terminal and click on the target terminal. According to the circuit diagram connect all the components, connect V+ to the upper input terminals of 2 digital displays according to you input. connect the OR gates according to the diagram shown in the screenshot connect the pin-1 of the half adder which will give the final carry output. connet the sum (pin-4) of those adders to the terminals of the third digital display which will give output sum. after athe connection is over click the selection tool in the pallete.
- See the output, in the screenshot diagram we have given the value 0011 (3) and 0111 (7) so get 10 as sum and 0 as carry. Give different input and check the result.
Click here to download the older version of simulator
Click here to download the new version of simulator
OR
Launch the older version of Simulator
Launch the new version of Simulator
Once the simulator is downloaded, open the command prompt, then go to the directory where you have saved it using cd command and then give the following command to run the simulator:
java -jar coaSimulator.jar
- Start the simulator as directed.
- To design the circuit we need 7 half adder, 3 OR gate, 1 bit switch (to give 1 as input), 3 digital display (2 for seeing input and 1 for seeing output sum), 1 bit display (to see the carry output), wires.
- The pin configuration of a component is shown whenever the mouse is hovered on any canned component of the palette. Pin numbering starts from 1 and from the bottom left corner (indicated with the circle) and increases anticlockwise.
- For half adder input is in pin-5,8 output sum is in pin-4 and carry is pin-1
- Click on the half adder component (in the Adder drawer in the pallet) and then click on the position of the editor window where you want to add the component (no drag and drop, simple click will serve the purpose), likewise add 6 more full adders(from the Adder drawer in the pallet), 3 OR gates (from Logic Gates drawer in the pallete), 1 bit switch, 3 digital displays and 1 bit display (from Display and Input drawer of the pallet, if it is not seen scroll down in the drawer)
- To connect any two components select the Connection menu of Palette, and then click on the Source terminal and click on the target terminal. According to the circuit diagram connect all the components, connect V+ to the upper input terminals of 2 digital displays according to you input. connect the OR gates according to the diagram shown in the screenshot connect the pin-1 of the half adder which will give the final carry output. connet the sum (pin-4) of those adders to the terminals of the third digital display which will give output sum. after athe connection is over click the selection tool in the pallete.
- See the output, in the screenshot diagram we have given the value 0011 (3) and 0111 (7) so get 10 as sum and 0 as carry. Give different input and check the result.
Click here to download the older version of simulator
Click here to download the new version of simulator
OR
Launch the older version of Simulator
Launch the new version of Simulator
Once the simulator is downloaded, open the command prompt, then go to the directory where you have saved it using cd command and then give the following command to run the simulator:
java -jar Simulator.jar
Experiment-2 (Design of Carry Lookahead Adders) :
Screen shots of the experiment are presented here to help doing the actual experiment in the simulator. This is the screenshot of the graphical editor of the application where user can design and simulate their digital circuits.The cursor noted blank space in the image is the canvas or the editor portion,where the circuits can be drawn. And in the right hand side,there is palette which contains the list of the components that can be added like, different logic gates,LED,positive and negative logic input. There are also some canned compound components like half adder and full adder.
Design of Carry Lookahead Adders :
The steps of doing experiment are not shown here,just the complete design has been shown.
Design of Carry Lookahead Adders :
LED value has been given here in order to activate the circuit to have the output value.
Design of Carry Lookahead Adders :
References :
Books:
- Digital Logic and Computer Design - M. Morris Mano. Pearson Education - Prentice Hall.
- Digital Principles Foundation of Circuit Design and Application - Arun Kumar Singh. New Age Publishers.
- The Art of Electronics - Paul Horowitz and Winfield Hill (1989). Cambridge University Press
- Modern Dictionary of Electronics - Rudolf F. Graf (1999). Newnes
Web Sites:
About Us:
Virtual Lab is an initiative of Ministry of Human Resource and Development(MHRD) under National Mission of Education through ICT to provide an interactive environment over the internet for creating and conducting different laboratory experiments by sharing the costly equipments and the resources.
For more information about the Virtual Lab,please visit http://www.vlab.co.in/
Developers of Computer Organization and Architecture Virtual Lab
- Dr. Chittaranjan Mandal Professor, Computer Science & Engineering
- Gargi Roy Senior Project Assistant
- Devleena Ghosh
Professor, Information Technology
IIT Kharagpur
Target Audience:
Under graduate students.
Courses Aligned With:
Digital Logic and Computer organization.
Pre-requisite Softwares:
- 32 bit java runtime environment and java 1.6 or above
- Recommended browser: mozilla firefox, google chrome
Objectives:
The Objective is to Expose the students to the various key aspects of Computer Organisation & Architecture by enabling them to perform FPGA based prototyping of experiments with support of a virtual environment. The primary need for virtualisation here is multifold.
- Computer Organisation and Architecture are core courses in most of the Undergraduate Curricula of the entire Electrical Sciences Discipline(Computer Science / Engg., Electronics, Electrical) etc.
- Many colleges/institutes cannot procure sufficient number of FPGA boards for their students.
- Even when such FPGA boards are available, making them available round the clock is difficult.
- Expert help is required to effectively use these FPGA boards and such help can be easily channeled through a virtual environment.
- Helps to standardize the set of Experiments to a large extent.
Contact Information:
Mailing Address and Contact Information:Department of Computer Science & Engineering, IIT Kharagpur
Office : +91-3222-2882255
Postal Address:
Indian Institute of Technology Kharagpur, Kharagpur - 721302, INDIA Telephone Number +91-3222-255221 | FAX : +91-3222-255303
Tutorial on UI for lab:
Introduction:
- The simulator contains a pallete on the right hand side. This pallete contains all the components and tools . Tools are used to act up on the components. Different tools:
- Selection tool- used for selecting components
- Marquee tool- used for selecting many components at a time by draggiung the mouse in the design area(editor).
- Connection tool- used for connecting components
- Components have been catagorized according to their functionality and put into different drawers in the pallete. The area under every drawer is scrallable, if you are unable to see all the components in a particular drawer just click on the area and scroll. Different drawers:
- Circuits- contains 8 and 16 terminal circuits and flow container which can hold other circuit components.
- Logic gates- contains all kinds of basic logic gates.
- Display and inputs- contains all kinds of component needed to give input to the circuit and displaying outputs of the circuit.
- Adders- contains different types of adder circuits.
- Sequential ckt- contains basic flipflops for designing sequential circuits.
- Other Components- contains different kinds of components like decoders, multiplexers, arithmetic logic units(ALU), memory elements(RAM cell) required to design combinational circuits.
- To add the components to the editor select any component(first click on the selection tool then click on the desired compoent) then finally click on the position of the editor window where you want to add the component.
- The pin configuration of a component is shown whenever the mouse is hovered on any canned component of the palette. Pin numbering starts from 1 and from the bottom left corner(indicating with the circle) and increases anticlockwise.
- To connect any two components select the Connection tool in the palette, and then click on the Source terminal and click on the target terminal(no drag and drop, simple click will serve the purpose). After the connection is over click the selection tool in the pallete.
- To move any components select the Selection Mode and drag the component after selecting it.
- If needed select any component in the editor while designing your circuit and use Undo, Redo, Delete,Zoom in, Zoom out buttons to get corresponding functionalities. Open and Save options are under development.
- As the automated clock is under development and the simulator is under modification for sequencial circuits, for the time being please use individual clock (Bit switch which toggle its value with a double click) for each flipflop.
- The simulator is currently under modification for sequential circuits, now it is working properly for combinational circuits but may not give proper output for sequential circuits.
Description of Components:
General components:- Digital display: it can be used to give input and as well as to see the output in the decimal format, its right most terminal is the LSB (least significant bit) and the left most terminal is the MSB (most significant bit), in the editor after selecting a particular digital display you can use 'Increment LED' and 'Decrement LED' buttons in the top left corner of the simulator to increment and decrement its value respectively.
- Bit display: it displays a single bit value.
- V+: it gives 1 as input.
- Ground: it gives 0 as input.
- Bit switch: it gives 1/0 input, it toggels its value with a double click.
Specific components:
Pin numbering starts from 1 and from the bottom left corner(indicating with the circle) and increases anticlockwise. Pin configurations of all the components-
- Half adder: i/p: 5,8 o/p: sum=4, carry=1
- Full adder: i/p: 5,6,8 o/p: sum=4, carry=1
- RCA 4 bit: (4 bit ripple carry adder) i/p: A0=13,A1=14,A2=15,A3=16; B0=17,B1=18,B2=19,B3=20; C0=21 o/p: S0=12,S1=11,S2=10,S3=9,Cout=8
- Wallace tree adder: (adds 3 4-bit numbers) i/p: A0=13,A1=14,A2=15,A3=16; B0=17,B1=18,B2=19,B3=20; C0=21,C1=22,C2=23,C3=24 o/p: S0=12,S1=11,S2=10,S3=9,Cout=8
- RS flipflop: i/p: R=5, S=8, Clk=7 o/p: Q=4, Q'=1
- D flipflop: i/p: D=5, Clk=8 o/p: Q=4, Q'=1
- T flipflop: i/p: T=8, Clk=7 o/p: Q=4, Q'=1
- JK flipflop: i/p: J=5, K=8, Clk=7 o/p: Q=4, Q'=1
- 2:4 Decoder: i/p: A0=5,A1=7 o/p: D0=4,D1=3,D2=2,d3=1
- 2:4 Decoder with enable: i/p: A=6,B=5, Enable=8 o/p: D0=4,D1=3,D2=2,d3=1
- 4:1 Mux: i/p: I0=9,I1=10,I2=11,I3=12,S0=13,S1=14 o/p: F=8
- Combinational Multiplier: i/p: multiplicand: A0=13,A1=14,A2=15,A3=16 Multiplier: B0=9,B1=10,B2=11,B3=12 o/p: S0=8,S1=7,S2=6,S3=5,S4=4,S5=3,S6=2,S7=1
- ALU 1 bit: i/p: A0=9, B0=10, C0=21 S0=12,S1=13 o/p: F=8, Cout=7
- 4 bit ALU: i/p: A0=13,A1=14,A2=15,A3=16; B0=17,B1=18,B2=19,B3=20; C0=21;S0=22,S1=23 o/p: F0=12,F1=11,F2=10,F3=9,Cout=8
- 16 bit ALU: i/p: A1=13,A2=15; B1=14,B2=16; Cin=9,S0=12,S1=11,S2=10 o/p: Cout=6,F2=7,F1=8
- RAM Cell: i/p=5, select=8, R/W'=6, o/p=4, R/W'=1 for read operation, R/W'=0 for write operation
- IC Memory: R/W'=16 Memory Enable=15, Address i/p=14,13 Data i/p=12,11,10 Data o/p=6,7,8 R/W'=1 for read operation, R/W'=0 for write operation
- Direct Mapped Cache:
- pin-32= S (selects whether user wants to perform cache write or cache mapping)
- pin-31= R/W'A (selects whether user wants to input the address or cache mapping)
- pin-30=A3, pin-29=A2, pin-28=A1, pin-27=A0 (thise 4 pins are used to give address input). A3 is the most significant bit and A0 is the least significant bit. A3 and A2 will be compared with the tag. A1 and A0 will select the corrsponding set.
- pin-26= R/W'D (selects whether user wants to input in the set of cache or cache mapping)
- pin-25= M1, pin-24=M0 (M1 is the most significant bit and M0 is the least significant bit). thiese two bits are used for cache writhe purpose, it selects the particular set of which user wants to give inputs to the valid bit, tag bits and data bits.
- pin-23= Den (this is an enable input which has to set for any write purpose in the cache).
- pin-21= valid bit
- pin-20= T1, pin-19=T0 (T1 is the most significant bit and T0 is the least significant bit). These are tag bits.
- pin-18= D1, pin-17=D0 (D1 is the most significant bit and D0 is the least significant bit). These are data bits.
- pin-14= Hit/Miss bit(if it gives 1 then hit otherwise miss)
- pin-15= F1, pin-16=F0 (F1 is the most significant bit and F0 is the least significant bit). These are output data bits and will be given only when there is a hit.
- Essential pin configurations for writing in cache: S=1, R/W'A=0, R/W'D=0, Den= 1
- Essential pin configurations for cache mapping: S=0, R/W'A=1, R/W'D=1, Den= 0
Testing process:
- To test your circuit give some input (through Digital display or Bit switch or V+ or Ground), if you use the Digital display or Bit switch you can then give different input to you circuit through incrementing/decrementing the Digital display or double clicking the Bit switch, the other two gives constant inputs.
- to see the output, connect Digital display or Bit display to the output terminals of your circuit.
Go to the Top
Frequently Asked Questions:
What is virtual lab?
The Virtual Laboratory is an interactive environment for creating and conducting simulated experiments: a playground for experimentation. It consists of domain dependent simulation programs, experimental units called objects that encompass data files, tools that operate on these objects.
What are the advantages of virtual lab?
Virtual Logic Design and Computer Organisation lab enables students to perform FPGA based prototyping of experiments with support of a virtual environment. The primary need for virtualisation here is multifold.
- Digital Logic and Computer Organisation are core courses in most of the Undergraduate Curricula of the entire Electrical Sciences Discipline ( Computer Science / Engg., Electronics, Electrical ] etc.
- Many colleges/institutes cannot procure sufficient number of FPGA boards for their students.
- Even when such FPGA boards are available, making them available round the clock is difficult.
- Expert help is required to effectively use these FPGA boards and such help can be easily channeled through a virtual environment.
- Helps to standardize the set of Experiments to a large extent.
What is eclipse platform?
Eclipse is a Java-based, extensible open source development platform. By itself, it is simply a framework and a set of services for building a development environment from plug-in components. Eclipse comes with a standard set of plug-ins, including the Java Development Tools (JDT).
Which framework is used to develop the application?
We have used the eclipse gef framework. The Graphical Editing Framework (GEF) allows developers to take an existing application model and quickly create a rich graphical editor.
What is platform independent application?
Applications that run under particular operating systems and/or particular hardwares are called platform dependent application whereas platform independent applications can run in any operating environment.
What are the experiments which can be performed by the Virtual Logic Design and Computer Organization lab?
The experiments that will be supported by this lab are given below:
- Design of a ripple carry adder
- Design of a carry-look-ahead adder
- Design of registers and counters
- Design of a wallace tree adder
- Design of combinational multipliers
- Design of a Booth’s multiplier
- Design of an ALU
- Design of memory units
- Design of direct mapped cache
- Design of associative cache
- Design of combinational dividers
- CPU design