Digital Systems Flashcards
positional numbering system
- position of a digit in the number determines that digit’s contribution to the total value of the number
base, r
- also known as the radix
- determined by the position of the digit
radix point
separates the integer part of a number from the fractional part
expansion method
method of calculating an equivalent decimal value from a base-r number
binary number system
- base- 2 number system
- only 2 binary digits (bits)L 0 and 1
- number consist of string of bits
counting in base-r
each time:
- count up one
- increment the least significant digit
carry
if the least significant digit reaches the base, r, it is reset to zero and a carry is generated into the next LSD
Binary bit addition
bits can be added, subtracted, multiplied and divided
only digits 0 and 1 are allowed in the results
octal number system
base-8 number system
alternative to working with long binary numbers
uses digits 0 through 7
(2)^3 = 8 so three binary digits can be represented by a singe octal
hexadecimal number system
- shorter method of representing the value of four binary digits at a time, (2)^4 =16
- requires 16 unique characters
- generally uses capital letter A through F for digits 10 through 15
converting base 10 numbers to base-r
- remainder method used
- repeated division by base, r, until quotient is zero
- base-r number found by taking remainders in reverse order in which they were found
radix (base) complement, R(M)
- given M, an N-bit, base-r argument, R(M) is the number which when added to M results in a sum of r^N
- R(M) depends on the machine being used. N is the maximum number of digits used by the machine to store an integer
diminished radix complement
- also called r - 1 complement
- equal to R(M) - 1
for example, if working in base-10 R(M) is the ten’s complement and one less than this is the nine’s complement
computer representation of negative numbers
- the typical representation of a negative number ( a minus sign) is not possible in a machine
- one N digit, usually the MD is reserved for sign representation
- this reduces the machine’s capacity to represent numbers N -1 bits per number
- it is arbitrary whether the sign bit for negative numbers is 0 or 1, as long as the MSD is different for positive and negative numbers
1’s complement
- obtained by inverting each bit of the number, M
- ideal for forming a negative number,
21 = 0001 0101
-21 = 1110 1010
2’s complement
for an N-bit binary integer, M, the 2’s complement is
R(M) = 2^N - M
An alternative way to calculate this to take the 1’s complement and add 1.
21= 0001 0101 -21= 1110 1011
Boolean algebra
a system for representing and evaluating logical variables (Boolean variable) and their combinations
- logical variables are typically represented by uppercase letters (A, B, and so on)
- in a digital environment, Boolean variables are confined for two values representing true and false, typically 1 and 0, respectively
logic gate
- implements logic operators digitally
- has one or more inputs and a single output
- dot (“bubble”, or small circle) designates use of NOT operation
truth tables
represents results of Boolean function for all combinations of the input variables
order of operations
- defines order of precedence for which digital calculations are performed
- analogous to the order of operations for mathematical operations
binary digit
also known as bit, or scalar
binary scalar, B
- typically takes on value of either 0 or 1
- represents one bit of information
- Boolean states are associated with bit values
n-tuple
- grouping of n binary scalars
- represented by [ A1, A2, A3, .. An]
- value of n is called word length
- total number of values that can be represented is N =2^N
cell
- smallest information storage unit
- often referred to as a word or byte
register
- ordered collection of cells
- when ordering values of binary variables, leftmost is most significant bit ( MSB) , rightmost is least significant bit (LSB)
logical 1
- indicates a true condition
- typically associated with high voltage in an electronic circuit
logical 0
- indicates a false condition
- typically associated with a lower voltage
voltage range
- practical real logic devices provide a range of voltage levels which are interpreted as logical 1 or 0.
- for example, transistor-transistor logic (TTL) allows a voltage range 0 - 0.8 V for a logical 0, AND 2.0 - 5.0 V for a logical 1
fan-out
number of logic gates that can be driven from a single output
fundamental logic operations
set of simple boolean functions from which all other digital functions can be derived
combinational logic
logic of processing information by combining with and comparing to other information so the output depends only on the value of the inputs
unary operation
logic operator involving a single variable or operand
function set
- the set of all possible mappings from input to output
- for N binary inputs, there are 2^N possible input combinations and 2^2^N possible functions
miniterm, m
- term that consists of the product of every variable in the function without duplication of any variables
- associated with conditions where the output is true (logical 1)
maxterm, M
- term that consist of the sum of every variable in the function without duplication of any variables
- associated with conditions where the output is false (logical 0 )
canonical sum-of-product (SOP) forms
logical OR combinations (summation) of minterms
canonical product of sums (POS) forms
logical AND combinations (products) of maxterms
implementation
- any given truth table can be implemented with many different logical expressions
- each expression corresponds to a different digital circuit
minimization
process of reducing the logical equation in order to minimize hardware resources for the circuit
minimization method:
- Boolean algebra and Karnaugh maps
- removes redundancy, simplifies logic, and improves speed
De Morgan’s theorems
- give equivalent functional representation for NAND gates and NOR gates
- can be extended to any AND/OR gate
- rule is change the AND gate to an OR gate (or vice versa) and invert the bubbles on the gate
Karnaugh map (K-map)
- graphical representation of a Boolean function (truth table)
- each cell in the map represents a miniterm or maxterm
- adjacent rows or columns change by one variable only
- two cells next to each other eliminate one variable
grouping types
cells can be circled in the center, along any row or column, and across the edges