Project - Fast Adder Via Fast Increment-by-1
Problem: n-bit addition with a given initial carry-in (Cin)
Break up n-bit addition into MS (n/2)-bit adds with its Cin = 0 and a LS (n/2)-bit add (For LS (n/2)-bit addition, the Cin for root n-bit add should be used, and there is no waiting for that).
After the two (n/2)-bit adds done (design will use a similar D&C process that stops at, say, 2-bit add), quickly detect the LS 0 bit position j in the MS (n/2)-bit sum, and if Cout from LS (n/2)-bit addition is a 1, complement all bits from 0 to j in the MS (n/2)-bit sum, and retain its bits j+1 to (n/2)-1. Concatenate this modified (n/2)-bit sum of the MS (n/2)-bit add (now with correct Cin) with the LS (n/2)-bit sum, to form the n-bit sum of the root problem.
We will call this the "Add-carry-in-later" (ACL) adder.
The detection of the LS 0 bit position for a k-bit number, itself needs to be solved using D&C.
Your Tasks for the 1st part (design) of the project:
Determine a team of 2-3 members (preferably 3) and notify the TA of your team by Wed 10/10.
Determine the D&C with stitch-up of the root problem at 2 levels (given). Also, determine leaf function (stop D&C at 2-bit addition).
Determine the D&C with stitch-up of k-bit LS 0 bit detector at 2 levels. Also, determine leaf function.
Determine an efficient (delay and hardware cost using gate-input units) of the stitch-up function (Increment by 1) for k bits w/ inputs shown in the root problem's D&C tree.
Schematic for 16-bit adder with given carry-in.
Analysis for:
- Delay of n-bit adder which includes the delay of a k-bit LS 0-bit detector (note that k will be n/2, n/4, .. 2) using gate-input level delay model (m-input gate has a delay of m units).
- Cost (total number of inputs across all gates) of n-bit adder using gate-input level cost model (minput gate has a cost of m units).
- Note that you can do both delay and cost analysis hierarchically: determine delay and cost of each basic block, and then determine critical path through various (possibly different-type) basic blocks to determine delay. Similarly, determine number of basic blocks of each type in the design, multiply each number by its cost, and add them up
Submit a professional pdf report of the above using text and figure drawing s/w Fri 10/19
Heads up: Part 2 will include:
- Implementing a 64-bit ACL adder using Quartus, and also implementing a 64-bit RCA and a 64-bit DAC adder with x=8.
- Simulating these 3 adders for correctness using Quartus (input vwf will be provided by TA)
- Determining their area and delay reports using Synopsys Design Vision(DV), comparing them
- Submitting a comprehensive professional report of the above along with Quartus timing waveforms of relevant simulations, Quartus schematic, DV reports plus all design files (details will be provided by the TA).
- This will be due Wed 10/31 (note also that there will be HW 2 due in between and we may also have the midterm exam before 10/31 or just after).
Attachment:- Assignment File.rar