Last Revised: 7/2/2009 1 EE 101 Lab 5 – Fast Adders 1 Introduction In this lab you will compare the performance of a 16-bit ripple-carry adder (RCA) with a 16-bit carry-lookahead adder (CLA). The 16-bit CLA will be implemented hierarchically starting with a 4-bit CLA block and building up to a 16-bit CLA. You may work in groups of two for this lab, turning in one report for the group. 2 What you will learn This lab is intended to give you experience using the hierarchical design features of the Xilinx tools. Specifically, you will learn how to take a design, create a symbol for it and instantiate it in other designs. Also, this lab will illustrate the benefits of using a carry lookahead adder vs. a ripple carry adder. 3 Background Information and Notes Carry-Lookahead Adder Design: We have seen that ripple-carry adders are slow, especially for large bit-widths, because the carry generation delay is proportional to the length of the chain, n. Carry-lookahead adders seek to compute the carries for a group of columns all at once. By using this idea and implementing it hierarchically, we can create a carry chain that is proportional to the logarithm of the length of the chain (logm n). To implement a carry-lookahead adder, we rely on the generating all the carries for a set of columns at one time. To do this, we define the concept of carry propagation and generation for a single column. A column of bits (Ai, Bi) will propagate a carry-in in if either input is true. A column of bits will generate a carry (w/o having to wait for the carry coming in) if both inputs are true. pi = Ai + Bi gi = Ai • Bi For 4-columns of additions and the overall carry-input, C0, we can define each carry (C1, C2, C3, C4) using the following equation: ci+1 = gi + pici However, this does not make the design any faster because ci+1 still would need to wait for ci to be generated. However, by “unrolling” the recursion relation (substituting ci with its form of ci+1) we can reduce down to only two levels of logic. For example: c1 = g0 + p0c0 c2 = g1 + p1c1 = g1 + p1(g0+p0c0) = g1 + p1g0 + p1p0c0EE 101 Lab 5 - Fast Adders 2 Last Revised: 7/2/2009 Essentially, the equation for c2 can be understood by looking at each term. C2 can be 1 in three ways: g1 could be 1 indicating a carry was generated from that column (A1 and B1 were both 1 generating a carry), or p1 and g0 could be 1 (indicating the 0th column will generate a carry and at least 1 input in the 1st column is 1 allowing that carry-in to propagate to the carry-out of that column), or p1, p0, and c0 could be 1 (indicating the original carry-in was 1 and at least 1 input is 1 in each of the 1st and 0th columns allowing the original carry-in to propagate through). As an analogy consider a tube broken into segments with valves to control the flow between segments. Each segment also has an entrance where fluid can be inserted. Insertion of the fluids are the ‘generates’ and the control of the valves are equivalent to the ‘propagate’ inputs. The cases for the fluid reaching the output (i.e. c2 are shown below) Generateg1Valve (p1)Valve (p0)Generateg0Carry-inc0c2 Figure 1 - Analogy for propate (pi) and generate (gi) signals Using a similar recursive unrolling, 2-level SOP equations for c3 and c4 can be derived. In addition, to generating the carries for 4-columns of addition, we can also generate an overall propagate, P, and generate, G. We will eventually use this carry-lookahead logic to hierarchically create a 16-bit adder. These overall Propagate and Generate signals indicate whether for 4-columns of addition, a carry-input to the first column will propagate all the way through the 4 columns or whether the 4 columns will generate a carry-out independent of the carry-in to the 4 columns. These signals can be defined as: P = p3∙p2∙p1∙p0 G = g3 + p3g2 + p3p2g1 + p3p2p1g0EE 101 Lab 5 - Fast Adders Last Revised: 7/2/2009 3 We will decompose the design into several levels of hierarchy. You will design a block of logic to generate all the pi and gi signals called “PG”. You will design a block of logic to generate all the carries for 4 sets of p,g inputs, called “CLL” (Carry-Lookahead Logic). You will then design a 4-bit carry-look ahead adder, called “CLA4”, and then use 4 of these plus another CLL block to create a 16-bit CLA. A3 B3 A2 B2 A1 B1 A0 B0PGg0 p0g1 p1g2 p2g3 p3 C1C2C3C4C0Carry-Lookahead Logic (CLL)PGg0 p0g1 p1g2 p2g3 p3 Figure 2 - Implementation of PG and CLL block (you will need to derive the logic for the CLL block yourself) C1C2C3C4C0Carry-Lookahead Logic (CLL)A3 B3 A2 B2 A1 B1 A0 B0CLA4S1S2S3 S0B0A0B1A1B2A2B3A3C4PGA3 B3 A2 B2 A1 B1 A0 B0G PG PA[3:0] B[3:0] C0B[3:0]S[3:0]g0 C0p0g1 p1g2 p2g3 p3g0 p0g1 p1g2 p2g3 p3 Figure 3 - Implementation of a 4-bit Carry-Lookahead adder (CLA4) using the PG and CLL blocksEE 101 Lab 5 - Fast Adders 4 Last Revised: 7/2/2009 CLA4A[3:0] B[3:0] C0C4G P S[3:0]CLA4A[3:0] B[3:0] C0C4G P S[3:0]CLA4A[3:0] B[3:0] C0C4G P S[3:0]CLA4A[3:0] B[3:0] C0C4G P S[3:0]C1C2C3C4g0 C0p0g1 p1g2 p2g3 p3Carry-Lookahead Logic (CLL)PGA[15:12]B[15:12] A[11:8] B[11:8] A[7:4] B[7:4] A[3:0] B[3:0]S[15:12] S[11:8] S[7:4] S[3:0]C0C16? ? ????CLA16? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?N/C N/C N/C N/C Figure 4 - 16-bit CLA using CLA4 building blocks and 1 CLL block to AVOID carry chaining (?'s represent connections you need to figure out, N/C = Not Connected = Should not be connected to anything) Note: Many good web resources exist with discussions of carry-lookahead logic and carry-lookahead adders (Wikipedia offers a reasonably good explanation for “carry lookahead adder”). Feel free to reference these for your design. Xilinx Tools for Hierarchy and Timing: Before starting this lab you should either watch the advanced Xilinx design and simulation training video or the in-class demo covering the same topics by your instructor/TA. After this training you should be familiar with: a) Creating a symbol/component for a schematic and instantiating that component into other designs b) Naming instances c) Creating a multi-sheet design d) Synthesizing a design and finding the area and timing results e) Reading the critical path information In this design you will need to design the CLL component and instantiate it in your CLA4 design. You will design the CLA4 block and create a CLA4 symbol so you can instantiate it in your CLA16 design. Use the symbol wizard