### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Digital Systems I EEC 180A

UCD

GPA 3.93

### View Full Document

## 60

## 0

## Popular in Course

## Popular in Engineering Electrical & Compu

This 113 page Class Notes was uploaded by Furman Breitenberg on Wednesday September 9, 2015. The Class Notes belongs to EEC 180A at University of California - Davis taught by Staff in Fall. Since its upload, it has received 60 views. For similar materials see /class/191949/eec-180a-university-of-california-davis in Engineering Electrical & Compu at University of California - Davis.

## Reviews for Digital Systems I

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/09/15

3 0m M We mil I 1 9 semem L e B a z 56 Hw S a 039 EVOFW Hcs 39 U aSMcf 4 e 39 a H t a B 2i B 239 V i 445 3 5 9 1 3 Alf1 c a quot gtquot Ac q I as a 24 y 63 513 a22 4reI 4 e L o 2 I 6 I s S Dis39ML wHN a u sin A a k f M weB a Z 93 9qu 4M 2390 i let 0 44 1 G a 4 tw 51 2amp1 4ampQ 114 Vq l 2 gm w u 23333 173 l w a o or tum lev 7 W0 594 w UaX U J al d 30 f B 2 km 384 3 3 57 th 181i m 1 MT 927 332 36 at Q3913 w GratinW 00 OOKW 4 rtan 3 may 99 95900 M H s o r a K o wv tm Va m 9K I p n b u vi u 94 90 P u n a saw u o lt atria prr v1550 swr toifmad n n I o I s ddfi 3va 9 our am A i 3 er ww 3 3 I a w n 9 A I a g x s but 9 M m 5 aatL 4J2 vb fat915 131 a 45 39 3939 L39 Dns39 quot Mus Q39 39Q r x 341quot 4 a 04 5 2 prquot Ltak algt 5 Lquot 3 5 4 quot quotCu g 5 a A Soc 3 39 45 Gareth4 D n a I P uvi ab Puf n Anos m 39 A u l waqu LOAVELS i F39F 3 g be D L x 1 Jr wit L mt JJN QM So k 4f K Qtr t 0quot V 0w 5 0 wk EA m IUU D II If t Poltbo Miny ufo 41 VI d Or I 0 Dotss lm 11 ll Qbee s f lt2 cm 2 D gt J 3 L N 39 N D j F lt3 39 i L o T gt39tcr dock uE rm 9 4LZ aFL J gba 019 m r rn tu v J 9 3 m II er as I 27 u DE 1 A 2 P 547 tamer VLSI Arithmetic Adders amp Multipliers Prof Vojin G Oklobdzija University of California httpwwweceucdaviseduacsel Prof VG Oklobdzija VLSI Arithmetic 1 Addition of Binary Numbers Full Adder The full adder is the fundamental building block of most arithmetic circuits ai b i ll C Full C out lt lt 1n Adder l S 1 The sum and carry outputs are described as Sl aiblCl aiblCl aiblCl aiblCl C 11 aibici aibici aibici aibici aibi aici 1716 Prof VG Oklobdzija VLSI Arithmetic 2 Addition of Binary Numbers Inputs Outputs a I 0 3 CH1 0 0 1 1 0 1 0 0 1 1 1 Prof VG Oklobdzija VLSI Arithmetic FullAdder Implementation Full Adder operations is de ned by equations SI 61195 67195 67196 aibicl 2 at 6 bl 6 cl 2 pl 6 Cl 111 111 Ill Ci1 C libici aibici aibi gi pici ai bi CarryPropagate pl 2 at 69 bl and CarryGenerate g1 gi ai bi Cout Onebit adder could be implemented as shown Prof VG Oklobdzija VLSI Arithmetic Si HighSpeed Addition Cil gi pici ai b giZaibigt pizai bi out Onebit adder could be implemented more ef ciently because MUX is faster Prof VG Oklobdzija VLSI Arithmetic The RippleCarry Adder Prof VG Oklobdzija VLSI Arithmetic The RippleCarry Adder Worst case delay linear with the number of bits td ON tadder z N 1tcarry tsum Goal Make the fastest possible carry path circuit From Rabaey Prof VG Oklobdzija VLSI Arithmetic Inversion Property S39ABCl SABE 0ltABCi C 21115 From Rabaey Prof VG Oklobdzija VLSI Arithmetic Minimize Critical Path by Reducing Inverting Stages Even Cell Odd Cell A0 BO l l A2 32 l l l l ll ll l l ll ll C C C IIIII FA l quotlllllnllxlll FA IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII nun FA IIIIIII Iquot FA Illv I quotquotquotquotquotquotquotquotquotquotquot ill ll quotquotquotquotquotquotquotquotquotquotquotquotquotquot J quotquotquotquotquotquotquotquotquotquotquotquot quotllllquot39li quotquotquotquotquotquotquotquotquotquotquotquot l0 2 l Exploit Inversion Property From Rabaey Note need 2 different types of cells Prof VG Oklobdzija VLSI Arithmetic 9 Manchester CarryChain Realization of the Carry Path Simple and very popular scheme for implementation of carry signal path Vdd Generate device Carry in Il Propagate device Predischarge amp kill device ii Prof VG Oklobdzija VL SI Arithmetic 10 Manchester Carry Chain olmplement P with passtransistors olmplement G with pullup kill delete with pulldown Use dynamic logic to reduce the complexity and speed up VDD ll lull lull will llllllll Poll lllllll Plll llllllll 1le llllll Pill llllllll Pill lllllll u inquot IIIIIIIIIII nnnnnnnnn quot39quotllllllzl u Gil l Gil all uuuuuuuuuu 39393939 ll l ll ll l llll I ll lquot Ill quotm Kilburn et al IEE Proc 1959 Prof VG Oklobdzija VLSI Arithmetic 11 Ripple Carry Adder CarryChain of an RCA implemented using multiplexer om the standard cell library Prof VG Oklobdzija VL SI Arithmetic 12 CarryLookahead Adder Weinberger and Smith Weinberger and J L Smith A Logic for HighSpeed Addition National Bureau of Standards Circ 591 p312 1958 Prof VG Oklobdzija VL SI Arithmetic 13 CarryLookahead Adder Weinberger and Smith Ci1 C lz39bz39cz39 aibicz39 aibi gt 1916 Ci2 gm 171416141 gi1 pi1 g1 picl gi1 pi1gi 1714117161 CH3 2 gi2 171426142 2 gi2 pi2gi1 pi1gi pi1pici gi2 pi2gi1 pi2pi1gi pi2pi1pici Prof VG Oklobdzija VL SI Arithmetic 14 CarryLockahead Adder G gi3 pi3gi2 pi3pi2gil pi3pi2pi1cj P pi3pi2pi1pi One gate delay A cm to p7 g g391p391 g391p391 g391pi1 l l l l l l One A to calculate C P G Group P and two for G 401 Three gate delays 3 J l J l To calculate C41 4i3 C4j2 C4j1 G P G Pi C4j1 239 23964 Compare that to 8 A in RCA 15 Prof VG Oklobdzija VLSI Arithmetic CarryLookahead Adder Weinberger and Smith gtXlt G j Gi3 Pi3Gi2 Pi3Pi2Gi1 Pi3Pi2Pi1Gi P j Pi3Pi2Pi1Pi Gj3 j3 G 2 142 Gj1111 C4j1 lt C4 i C4j1 G k P k C4 c4j3 Additional two gate delays C16 will take a total of 5A vs 32A for RCA Prof VG Oklobdzija VL SI Arithmetic 16 32bit Carry Lookahead Adder individual adders ai generating gi pi bi and sum Si xx Carrylookahead super blocks of Carrylookahead blocks of 4bits blocks generating 4bits generating Gi Pi and Cin for the 4bit Gi Pi and Cin for the blocks adders Group producing final carry Cout and C16 Critical path delay 1A for gipi2X2A for GP3X2A for Cin1XORA for Sum appx 12A of delay Prof VG Oklobdzija VLSI Arithmetic 17 CarryLookahead Adder Weinberger and Smith original derivation CI AIR AIBICI 3 123 A B 39n C39m 151 AriBali Prof VG Oklobdzija A33 439 A Bil l l a3 AIBJQ 43 AI 39939 3134443 I 1i39l393 39Mri39B i39il i AIRIJ39A5EA1EJGJ VL SI Arithmetic 1 8 CarryLookahead Adder Weinberger and Smith original derivation 039 A434 APB AiBl U fl1 Bail 313B x l Arl39 ai39h 1ri39EnHt 1 Bald1E AI 3 344313 3 3 44131339Uw a finBa 111BGJ ASBI iquot 31 AH H dri39 Bl raw 1 3 A at a m Prof VG Oklobdzija VL SI Arithmetic 19 CarryLookahead Adder Weinberger and Smith please notice the similarity with ParallelPre x Adders Fl rllggl IJqilr quot31 1 I tiilfl39lh in A L hhiflilljll I n In I quotll ll 1 I glljih 39IIIflI IIIII I I I n n In t 4 F it39ll MIA l m Iquot ELM it I w quot iiquot III I III11mlumnlu39 um Fm u 19 punam binary Prof VG Oklobdzija VLSI Arithmetic 20 CarryLookahead Adder Weinberger and Smith please notice the similarity with ParallelPrefix Adders mun 39MI II39 Mil Flattj LID mee mub pam d Binary aim Prof VG Oklobdzija VLSI Arithmetic 21 647 r oo 0 0 039 c dl 023 cube 8 Max pWLL 393 03 Iwkuku fa on cumquot 9 7 Zic known o joLZic 070 a g o q 9 1 l 3 o 0 b 0H 0 O o C 39 mo ll m a M21 O H 3 b H L Iquot i 9 L 44con Mic 7quot bu Lc ss RMS 4 ampLampa Mi 1404 4L 39 N 1 4 C I a HRH F39 F 3 ooo O 00 l I O I lo10 O 3 5 l Io R a 1 3 l a W 39 2 won x R 53 2quot m g g 31 81 45 W5 t ampolt c E to up u a SOUAIE S zOUAIE 3 OUAI p LJJKJquot P EEC 6904 1 4 l K 39 R 1 F 2 2m K 13452 m a K Mb I X smg j 1 E fi A Z 4 i 1 K FL o Ok 1L4P F Y1 1 A MD E 5 Y0 V1 PF v a pm A K 3 if Wst 5 omows F r W00 W z A b 4 i 3 21a 0 Ab o o A c O KY5 AZ 39 0 O 1 I F AC AC kc o 07 lt PCHrOKMCA Jul 9 ll ti W r7141 1 MKPrrva k 1 v n p m 4 a mm M b in J x Vj s f 20 n gt I x f Jf agtrn I3 p m 1 pzvgrsn 15 U V e n n rth 7 L l amm m V VT mxofAF P r 7 w n w AI a W lgtgtr D b D TN W in p x 9n V 7 I51 m 1 Ana N rupwo aw I l p hm a w T q mm mm IJ39l A zwzv MW 3 9 P MIG WQVNH Tm mn im No16 Nunmvl L GIP N wn K an mo 3 MXVHHT turph bo zm run gt 4f P fa 5 p QIII S T4 mb mv 0 man 5v 3 n v n Mwnwn Vtg EM cit m I Q n C 2 REAHZE 4 4L4 LL4 6LLC EQ 2 163 LcI aLc Lo T 35 Mr quotquot a i 5 R quotr 4f 5 39 1 39I S 2 7 3 i F LA Take A 4 3 a L c 4 2 L3 0 O l 0 l o o o o l o o l o o 1 o o 4ND OK no a 0 d 4 KL K m Kgquot 5 A 39 A b goo 0 0quot 1 KEQ39 0 Ad G Kt s 0 53 Qf 3 dquot 3 g o abNJ g r i d quot6 quot393 2 lt 0900000v Qooo J N 339 WOOOOO Oquotquot quot39O o oooozva 0 my g quot 0 039 quot9 2 1 0 3 300 3quot i 5 710000 dd 300005 jrr o 0000m a F395 9quot 238 UNIT 9 Figure 930 PAL Segment 394 Output a Unprogrammed 3 113 I I2 b Programmed Figure 9 32 Logic Diagram for PAL12H6 Courtesy of Monolithic Memories 240 UNIT 9 Figure 9 31 Logic Diagram for PAL14L4 Courtesy of Monolithic Memories LA Tque aLQ A 41 2L3 I D 00quot quot o o O O o o o 00 39 0 Rwekem Uo m A E quotK v Q A 1 A REA V161 4 LAFm gt lGL c EQ 2 C a b C A P4 mg Rs D r S P Ahl sis e We 7m Mf39wulg XX1 4 Tx39Tz Xi xz Tz T T drift 39 30xw 9 f xn39yz H Winz quot39 2 a cal 4 WMC s39Yz39 39gtzxagt 1 c a wax 13433 39Xw YI39H IA 4 xyyr Yr 4quot Yo H9 quot 5 I 4 0 sz 3392 o xv i375 H35 wyxhamnomuhoroln a 1 use 3 L E 5 93 fl n 3 Cc Pm quot II P 930Arv 01 uif l l R o 871 233 5 NSFNA I L Ed alRthIquot die 1 m f2 0P 2 tra m 7 nth jar 99V oh ram on 2 O has pf M kbfl 1 X e L quotquoto 0 1 L CS 3CH 6 4 CpCrCJCH39CI39CC39 C Cg hazy 22 lanaigag squot139 4 4ix 3 w Is COMM Mam ZWM 9 I M x 4752 32 H 2N S auws wmw amp W 5 new M M 35 I BunMAT PC39O Oi 53quot W 9 5 gt03 r70 K3iai X455 rapema 2 43226 sxa2 4 912043 39 0 quot TI 5 Z V Tm 0 Tauk z 4 4 6 quot m 70 0H 3 I M L 3 9 3 a quotT C EDP l7 Evil EEH39amp7 A r 39c xl xzno o I39 k KKX L 3 quotc 55quot Eu i h39 b E q 4 b 5quot b b b B 3 29 00 m a SOP M 4 20 N 439 quot39 m Wb WW3 C4 My 1 3 0 4Mm gt Agt gt39 23 quot Pr 3 mePio Fromv u m T mrKr new law 373 iewv u QC Tu Y xiCh v u mmwer 5 L1 3 uh I39 XON x1o 0 moh o 9r r9 m v ur0LPwltF t N30rv90 namranv 09V OV1Trnu PATO0VH m3 Extra 3 60 v1 uol Mara l 3 963 I 0 he 0 y lt0 n K r 00v u quot 80v w YOK r Qt quot Javaquot Xj 1x 00 Ta E K93 0 0 xyqpp 6739 06 4 DisH Luku any 4 xog Mam3quot 1 quot 35 04073m2 39 a n x3 x51 x 3543 39 Y 102 U P ff quot I d mlh Xxvov VVU n xxovtv rm my gh mnl0uv m NM N0V unlm 472 hn4 1012 Vim 3 VR J KQ l xtmvd uxd FL KIM m lynme u tn oM0VIpWP Afwv cn on N Nola Va IAbH v0 4 eggkc 01Ci ag 4D ADCl 4 09 4 1 E hi M1 mm at y W 1 3 3 a 44 4 M m 3 Mali926 OJ 2 yacht925 v09 gtc3n q we 50 99 XqYXei X a 39 go Ew Ci x 47 w3 i XI3 X2 32 x 23 31 xv32 3 It 211 g 47 39 V z iatz x 2393 quotORuquot A Q 4 t 3232quot gt 5 Irat okw5 W39XdX39P quot qu M was 39 6 f P D 1 5 L 42 r l p a W W J gsquot 4 Va O WV If i 4 Vega Vi V V630 l 3 vuv gut 39o t lt IL I 4clt 4 Vw Vuquot D I O IMI fSl Dn V quot 39v 39 V 0 JET 1L d gt 43 V I 3gt halya Lk Unit 5 Karnaugh Maps EEC18OA 51 Minimum Forms of Switching Functions Find a minimum sumof products expression for Fa b c Z m012567 Note Use XY XY X F a39b39c39a39b39c a39bc39ab39 c abc39abc F a b b c bc ab None of these terms can be eliminated However if we combine in a different way F a39b39c39a39b39c a39bc39ab39c abc39abc 52 Karnaugh Maps We can represent a 1 and 2input truth table as 1D and 2D cube X F u 1 0 o gto 1 v lrzuhe XY XY F 11 of 11 00 01 x 10 11 52 Karnaugh Maps Allows for easy application of XY XY X X YXY Y XY XY X X Y X Y X X Y XY Y 52 TwoVariable Karnaugh Maps l V 1IIB 0 quot739 AB I 52 TwoVariable Karnaugh Maps Two Variable Karnaugh Map Example l l B H ml 0 ldl Minterms in adjacent squares on the map can be combined since they differ in only one variable ie XY XY X 52 ThreeVariable Karnaugh Maps We can represent a 3input truth table as a 3D cube 3939z X Y Z on III U u o o n n I II 1 U mud O u 1 1 HU 1 0 u I n 3913 Z 001 1 3 7 o l 1 1 I l l 52 ThreeVariable Karnaugh Maps Location of Minterms on a Three Variable Karnaugh Map Il LU br 1 7 b V nu noo lno 1m 0 4 m 001 ml mm m 1 s t Mmcum 1 onTlll WI 11 7 v 7 m 010 no 1n 2 a i m mar nulzuiuu by Declmul HULHinu 52 ThreeVariable Karnaugh Maps Truth Table and resulting Karnaugh Map for ThreeVariable Function 4m um um 11 my Hm 52 ThreeVariable Karnaugh Maps Location of Minterms on a Three Variable Karnaugh Map Fa 1m Zm135 H 02467 52 ThreeVariable Karnaugh Maps Karnaugh Map for F abo b c a 52 ThreeVariable Karnaugh Maps Karnaugh Maps for Product Terms a 1 m bquot I m mhmm nn m rum mm mm v I l yr I m quothmum In 52 ThreeVariable Karnaugh Maps Simplification of a ThreeVariable Function F Z m135 7392 T It39h39L ub r min iim Iz r u Fa cb39c 52 ThreeVariable Karnaugh Maps Simplification of F F Zmltl3 5 F Zm02467 u Iw U i U I 52 ThreeVariable Karnaugh Maps Karnaugh Maps which illustrate the Consensus Theorem m I numemu m un H I J 52 ThreeVariable Karnaugh Maps Function with Two Minimum Forms 53 FourVariable Karnaugh Maps Adjacent squares should differ by only one variable 53 FourVariable Karnaugh Maps Location of Minterms on a FourVariable Karnaugh Map 53 FourVariable Karnaugh Maps Sample 4variable Karnaugh Map Facda bd 53 FourVariable Karnaugh Maps Simplification of FourVariable Functions F Zm1345101213 F bc a b d ab cd39 53 FourVariable Karnaugh Maps Simplification of Incompleter Specified Function uh m x F Zml3579 Zd61213 Fa dc d 53 FourVariable Karnaugh Maps Finding Minimum Product of Sums from Karnaugh Maps F x39z39wyz w y Z x39y WX WX wxz yz oo 01 11 1o yz oo 01 11 1o 00 1 1 0 1 00 0 01 o 0 0 0 01 Y Z 111011 110 1010 01 100 F w xy F F39 y39z wxz39w39xy Using DeMorgan s F y Z39Xw39x39zw x39y39 54 Determination of Minimum Expressions lmplicant any single 1 or any group of 1 s which can be combined together on a map of the function F wx wxy wx y yz 00 01 11 10 oo WY Z 01 wy z y 11 WY List of lmplicants wxy wx y wy z wy z wy w x y w yz and all single 1 s 54 Determination of Minimum Expressions Prime lmplicant an implicant which can not be combined with another term to eliminate a variable lmplicants Prime lmplicants WX WX yz oo 01 11 1o yz oo 01 11 1o 00 1 00 1 1 01 01 1 1 q 11 1 11 1 wxy wy 10 10 J J wyz List of Prime lmplicants w x y w yz wy 54 Determination of Minimum Expressions Find the prime implicants ab cd 00 01 11 10 00 1 1 01111 54 Determination of Minimum Expressions Find the prime implicants ab cd 00 01 11 10 00 1 1 01 1 1 1 q 11 1 1 1 10 1 1 All prime implicants a h39ii byquot up u39r ri uh h cd 54 Determination of Minimum Expressions Minimum Solution might not utilize all prime implicants ab ab cd oo 01 11 10 cd oo 01 11 1o 00 1 1 00 1 01 1 1 1 01 q 11 1 1 1 11 10 1 1 10 l39u Iinimum solution F u39h d bi it All prime implicants ci F i hr atquot u39r u uh b39m 54 Determination of Minimum Expressions Essential Prime lmplicant A prime implicant that contains a minterm that is covered by only one prime implicant ab bc cd oo 01 11 1o 00 1 minterm covered by more than 1 prime implicant 01 minterm covered by 11 only 1 prime implicant 10 ac List of Essential Prime lmplicants bc ac 54 Determination of Minimum Expressions To nd minimum expression Find all Prime lmplicants Determine Essential Prime lmplicants Find Simplest Expression for remaining uncovered 1 s ab bc cd oo 01 11 1o find simplest 00 1 expression for remaining 39 1 1 5 11 a b d 10 ac F a b d bc ac 54 Determination of Minimum Expressions Find Minimum SumofProducts Expression AB CD oo 01 11 10 oo 1 1 01 1 1 54 Determination of Minimum Expressions First find all Prime Implicants AB CD oo 01 11 1o 00 1 1 01 1 1 q 11 1 1 1 54 Determination of Minimum Expressions Next find all essential Prime lmplicants mintern covered by only 1 prime implicant AB AB AC 00 01 11 10 11 10 ACD A B D List of Essential Prime lmplicants A C ACD A B D Minimum Solution F A C ACD A B D ALED BCD 00 01 10 A8 00 01 11 10 c0 00 01 11 10 00 01 11 10 00 O1 11 10 48 oo 01 11 10 oo 01 11 1o oo 01 11 10 CD 00 pl 11 1o oo 01 11 10 J go oo 01 01 P p 11 nquot 11 10 1o FZDI cAs 439 339 00 01 11 10 oo 01 11 1o oo 01 11 1O 1 Minimum sum of products fabcd b c d bcd acd a b c a bc d fabcd Ema 2 3 5 7 8 10 14 15 fabcd 2m0 2 3 5 7 8 10 14 15 ab 0 00 0 4 12 8 01 1 5 13 9 11 13 I 15 11 10 2 6 I14 10 ab z d 2Minimum product of sums Ploting Karnaugh map for f fabcd 2m0 2 3 5 7 8 10 14 15 f abcd Ema 4 6 9 11 12 13 00 01 11 10 4339 at o a bc aa b353 agjizdoa 45

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.