Intro to Computing (EE 306) Midterm #1 Review
Intro to Computing (EE 306) Midterm #1 Review EE 306
Popular in Introduction to Computing
verified elite notetaker
Popular in Electrical Engineering
verified elite notetaker
This 8 page Study Guide was uploaded by Luca Tomescu on Tuesday September 27, 2016. The Study Guide belongs to EE 306 at University of Texas at Austin taught by Dr. Yerraballi in Fall 2016. Since its upload, it has received 197 views. For similar materials see Introduction to Computing in Electrical Engineering at University of Texas at Austin.
Reviews for Intro to Computing (EE 306) Midterm #1 Review
Report this Material
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/27/16
Intro to Computing (EE 306): Exam #1 Study Guide Bottom-up Approach to Computing o 1. Mathematical foundation of computing Binary Logic with 0 or 1 0: 0-0.5V 1: 2.4-3.3V Algorithms Information: symbols (alphabet, numbers, special characters) Number system, ASCII, images/video, sound o 2. Boolean logic NOT, AND, OR Composed of physical gates o 3. Combinational/sequential logic Sequential has to do with time o 4. Computer Register, decoder, memory, automatic logic unit (ALU) o 5. Software Turing Machines o Contain input, output, and storage o Contains a read/write head with a set of rules to perform a specific task Algorithms o Must be precise (no ambiguity) o Characterized by finiteness (must terminate) o Must be effectively computable Universal Turing Machine o Takes other, individual turing machines as inputs o All computers are able to do “any” task given sufficient time and memory Binary System o Top-down design 1. Problem: Find the most frequently occurring score 2. Solution in the form of an algorithm 3. Program: language and data structures used 4. Choose architecture (ISA – instruction set architecture) interface X86, ARM, Sparc, PowerPC implementation 5. Choose microarchitecture Intel, AMD 6. Logic Gates Device material (NMOS, PMOS, CMOS) Mathematical Foundation o Base-10 Bases: 10^0, 10^1, 10^2 …. 10^(N-1) Coefficient (weights): [0,9] o Base-2 Bases: 2^0, 2^1, 2^2 …. 2^(N-1) Coefficients (weights): [0,1] o Can be generalized to Base-k Bases: k^0, k^1, k^2 …. k^(N-1) Coefficients (weights): [0, k-1] Decimal 2-bit binary 3-bit binary N-bit binary 0 00 000 1 01 001 2 10 010 3 11 011 4 100 5 101 6 110 7 111 [0, 3] [0, 7] [0, 2^N – 1] o Know methods for converting between decimal and binary For decimal binary: Divide decimal number by 2, and the remainder will tell you if that place is a 1 or 0, starting from the least significant bit If in doubt, write out: _ x 2^N + _ x 2^(N-1) + … etc. Fill in the blanks accordingly Signed representations of numbers o Binary: signed magnitude, one’s complement, two’s complement o Signed Magnitude The first bit represents the sign (0 = positive, 1 = negative) Problems: There is + and – 0 0000 and 1000 are both 0 Operations (addition, subtraction) don’t work o One’s complement To get the negative version of a signed magnitude number, flip all bits 13 (decimal) 01101 (13 in binary) 10010 (-13 in 1’s comp.) Problems: o There is still the option of +/- 0 o Two’s complement 1. Convert decimal # to binary in signed magnitude 2. Flips all bits 3. Add 1 Continuing from 1’s comp. example: 10010 (-13 in 1’s comp.) 10011 (-13 in 2’s comp.) Eliminates the problems from the previous two representations Also takes advantage of having the maximum number of representable numbers within its range (doesn’t double up on 0) Keep in mind that ONLY negative numbers must go through the 2’s Comp. process; positive numbers stay as they are Special cases in 2’s comp Leading 0s on positive numbers have no effect Leading 1s on negative numbers have no effect o Ranges with different representations Unsigned: [0, 2^N – 1] Signed magnitude: [-2^(N-1) + 1, 2^(N-1) – 1) 1’s comp.: Same as signed magnitude 2’s comp.: [-2^(N-1), 2^(N-1) – 1] Overflow o When the sum of 2 numbers exceeds what can be represented with the given number of bits o Detecting overflow: If 2 positive numbers are added and yield a negative result If 2 negative numbers are added and yield a positive result Think of the circular number like with positive numbers on the right hemisphere and negative numbers on the left hemisphere Base-16 and Base-8 o Hexadecimal and Octal are convenient ways of representing binary numbers Both of these notations are unsigned 1 hex digit represents 4 binary digits Hex ranges [0,F] where A=10 …. F=15 Prefixes: 0x for hex, 0c for octal, 0b for binary Logic: the fundamental data type o 0 = false, 1 = true o Basic logic operators are NOT, AND, OR o NOT can be represented by an apostrophe or a horizontal bar above a variable o AND can be represented as “&” or multiplication o OR can be represented as addition o Truth tables show all possible results of a logic operation Floating point o Representing decimal numbers in binary o Numbers must always be “normalized” i.e. move decimal over so there’s only 1 significant figure left of the decimal (think scientific notation) o When representing floating point numbers, the bits available are split into 3 boxes The most significant bit is the sign Some bits right of that are the exponent Determine exponent by adding the exponent on the two to the bias Bias is determined by the formula: 2^(k-1)-1 where k = # of bits in the exponent box The rest of the bits to the right are used for the fraction portion, which is everything to the right of the “1.” on the normalized binary floating point number NOTE: The “1.” is never explicitly stated; instead, it is always implied to be in front of the fraction since the only significant figure in binary is 1 o Formula: (-1)^s * 1.fraction * 2^(exponent – bias) o IEEE standard Single precision uses 32-bits for floating point numbers 1 sign, 8 exponent, 23 fraction Double precision uses 64-bits for floating point numbers 1 sign, 12 exponent, 51 fraction o Special cases (denormalized) When the exponent and fraction box contains all 0s, that means the number is 0 (even though doing the work for normalization would result in a nonzero number) When the exponent box contains all 1s and the number box contains all 0s, that means the number is infinity Works with +/- infinity based on sign bit When the exponent box contains all 1s and the fraction box is non-zero, that means “Not a number” We also use denormalized floating point numbers to represent fractions smaller than what we can with the given number of fraction bits When the exponent box contains all 1s and the fraction box is nonzero, the formula on the exponent changes from 2^(exponent – bias) to 2^(-bias + 1) o Transistors A transistor is a controlled switch It is essentially a gate connecting a drain and a source; the gate can be switched open or closed N-type 0 = open, 1 = closed Conventionally represented with drain at the top and source at the bottom P-type 0 = closed, 1 = open Conventionally represented with drain at the bottom and source at the top o Logic Gates Logic operations are composed of transistors that take inputs and open or close accordingly The resulting circuit either gives 0 volts or 3.3 volts to the output, representing a 0 or 1, respectively Checking for output of transistors can be done just as with any logic circuits built a truth table! Check lecture notes/slides to get familiar with the transistor arrangements of certain logical operators, especially NAND Every logical operation can be made through a combination of NAND gates Also, make sure you know the symbols for the various logic gates A circle at the output of a gate means the NOT version of that gate o DeMorgan’s Law (A & B)’ = A’ or B’ (A or B)’ = A’ & B’ o Combinational Logic Circuits (CLC) Basic form: Boolean expression logic circuit Extended: Problem Solution Truth table Boolean expression logic circuit A combinational logic circuit operates on the formula: Output = f(inputs) Common CLCs include decoders, multiplexers, and adders o Decoder Takes n inputs and can produce 2^n different outputs Every combination of inputs can have a different output option Think of it as taking a code and performing a certain task that is unique to that code Composed of many AND gates that all feed into an OR gates Any truth table can be converted into a decoder o Multiplexer (MUX) “Many-to-one” Has multiple inputs (let’s call that i), 1 output, and log2(inputs) select lines Composed of i and gates, which each takes 1 input and all the select lines as inputs Select line essentially pick which of the many inputs is outputted o Adder A full adder takes 2 number (A and B) and a “carry in” as inputs Outputs: sum (S) and “carry out” A full adder of 2 number is a 3x8 decoder The wires connecting the decoder outputs to OR gates are known as a programmable logic array (PLA) There’s an OR gate for S and another one for carry out A 4-bit adder is composed of 4 full adders in a row that carry out to each other Can also be used to subtract by putting a multiplexer before one of the inputs to each full adder o The MUX selects if the second input is NOTted, which represents the flipping all bits to make the second number negative o Memory R-S latch Composed of 2 NAND gates that feed into each other and maintain the same value over time Inputs are R and S o When both are 1, that’s the hold/quiet state where the value inside the latch is maintained o When S is 0 and R is 1, the latch is SET (S for set) to 1 o When S is 1 and R is 0, the latch is RESET (R for reset) to 0 o When both are 0, the latch becomes unstable because it constantly switches values D-latch Solves for the both 0s problem It adds 2 NAND gates ahead of R and S o 1 input is D, which is the value you want to save in the latch o The other input is “write enable” (WE), which allows you to change the value Must be 1 to change the value in the latch A WE of 0 means the latch will not change Fundamental storage element A register is multiple D-latches in a row with a common WE Large-scale memory Memory is described by 2 terms o Address space: No. of locations (rows) in memories o Addressability: No. of bits in each location (the width of each register) MAR stores the address for what register you want to access (read or write to) o # of bits = log2(address space) MDR holds the contents being read or written to memory o # of bits = addressability o Finite State Machines (FSM) Represents a sequential logic circuit Output = f(state and input) Defined by 5 parameters: 1. Has set of inputs 2. Has set of outputs 3. Has finite set of states 4. Has a corresponding state transition graph (TT) 5. Output determination Drawn as series of circles, each representing a state, connected by arrows with different outputs leading to different states Moore FSM: Produces output based on the current state Reads input Changes to next state based on current state and input Can make a truth table for current state and next state addresses As with all truth tables, this can be represented using a decoder and OR gates connected through a PLA The OR gates feed into memory boxes, which feed back into the new current state A simple D-latch won’t work because the value stored can change millions of times in a fraction of a second We use a D flip-flop, which is 2 D-latches in a row o When one latch is open, the other is closed o That way, a value can be stored for 1 clock cycle Generic FSM Has m inputs, n outputs, and up to k states represents by log2(k) bits (we’ll call that j) The decoder size is (m + j) x (2^(m + j)) No. of OR gates = n + j Storage elements o D flip-flops = j o D latches = 2j
Are you sure you want to buy this material for
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'