Digital Electronics Notes Flashcards
How would represent this equation from De Morgans theorem into a truth table?
What are the three specific types of logic systems ?
Combinational Logic System
Sequential Logic System
Storage Logic System
What is the property of a combinational logic system?
The output data is a logical function of the value of the input data at the instant the output is measured.
Property of a Sequential Logic System?
The outputs depend not only on the present inputs but also on all previous inputs over a specific operating time.
Function of a storage logic system ?
Storage of information (data is input and stored but nothing is output)
Access of information (data is output without data input)
The relationship between combinatorial, sequential and memory systems
- A simple sequential circuit has memory properties.
- A combinational logic circuit can be converted into a sequential system by applying feedback from some of the outputs to form additional internal inputs.
- A memory circuit can be organized as a combinational logic function.
What are truth tables?
A truth table l_ists the value of the output_ for each and every possible combination of inputs.
If the output is a function of two variables there are 22 or 4 possible input combinations.
For n variables, the truth table will have 2n input states.
What are the symbols and equations for each of the logic gates ?
ALSO Ex OR ! not in the table!
What is the truth table for each of these logic gates?
What are the logical operators on one variable for AND OR and NOT functions?
How does this work?
For AND, if one or more inputs are 0, then the output is 0.
For OR, if one or more inputs is 1, then the output is 1.
For AND, A.0 = 0, because in AND both inputs have to be 1 to output 1, in this case we know that one of the inputs is 0, and thus whatever value of A we get, the output is going to be 1.
For A.1, we always know the output is going to be A.
On the other hand, for OR, we know that A+0 = A because if A is 1, the output is one, if A is 0, the output is 0. So the input solely relies on the input.
Order of precedence for operations in Boolean Algebra ?
- Bracketed Functions and ‘barred’ or inverted functions
- AND operations
- OR operations
REMEMBER inversion is the same as NOT
What is De Morgans theorem?
Venn Diagram: Worked Example
De Morgan & Truth Table Question
Determining equality by means of truth tables
Positive and Negative Logic Coding
negative logic coding simply inverts all the bits used to the opposite, 1 becomes 0, 0 becomes 1.
How do you obtain the 1st canonical form?
To obtain the 1st canonical form from a truth table, create an AND minterm for every entry with an output of 1.
The variable is used if its value is 1, or its inverse if 0.
The shorthand notation of the canonical form
The variables in the minterms are replaced with their binary values.
Each minterm is now regarded as a number and the decimal value is obtained.
The function is now represented by decimal numbers.
1st Canonical Form Question
How is the 2nd canonical form obtained?
Is obtained from the truth table by defining the function by its F=0 terms.
First, write an equation in terms of minterms equal to F=0.
Invert both sides.
Apply De Morgans Theorem
How is the 2nd canonical form calculated directly from a truth table, without De Morgans?
for each entry into the truth table with an output of 0, create an OR of the outputs
Use the normal variable if 0
Use inverted if 1
Finally, the outputs of the OR gates are AND’d together.
Shorthand Notation of the 2nd canonical form
Just like the 1st canonical form, the 2nd canonical form can be represented by decimals that identify the terms.
Non-inverted variables are assigned 0 and inverted variables 1.
Π indicates the 2nd canonical form.
Conversion between the shorthand notations of the canonical form
Conversion between Canonical forms Question
Convert this into NAND form
NAND Logic Example
Circuit transformation with NOR Logic
To obtain a NOR logic gate it is first necessary to start with an implementation of the 2nd canonic form of a function (ie NOT/OR/AND implementation)
Function transformation to NOR logic
Apply De Morgans theorem to the 2nd canonic form.
Difference between negative-AND and NAND ?
negative-AND has the bar across the variables individually.
Like adding an inverter to the input
NAND has a bar across the whole term. This means that the inversion is at the output
Where are the NAND and NOR logic forms derived from ?
1st canonic and 2nd canonic form respectively
Obtain Karnaugh Map for Function - Example
Why are k-maps useful ?
by using the K-map alone, the variables that can be eliminated between a pair of minterms can be detected, without having to resort to algebra.
All that is necessary is to identify any minterms on the K-map that occupy adjacent cells and describe them by the simplest possible expression, which then replaces the original minterms.
What is the logic behind minimizing the 1st canonical form using this K-map?
It is based on finding the variables that are independent n each loop and removing them.
Minimisation of 2nd canonical form through K-maps
What are the rules for looping on a Karnaugh Map
- Loops must contain 2n adjacent cells set to 1 (or 0 for 2nd canonical form). A single cell cannot be simplified
- A loop of 21 is independent of 1 variable. A loop of 22 is independent of 2 variables. In general, a loop of 2n is independent of n variables.
- All cell set to 1 must be covered when expressing the minimal of the function using the 1st canonical form (or 0 if using the 2nd canonical form)
- Loops may overlap as long as one cell is unlooped.
- Any loop that has all its cells included in another loop is simply redundant.
- Loops must be square or rectangular
- Edges of K-map are considered to be adjacent. A loop can leave a side and enter on the other.
Why should you always aim to create the largest loops in k-map minimization?
It always you to obtain the simplest function.
BCD Example
Non-8421 BCD Example
What are ‘Don’t Care’conditions?
For some logic systems, certain combinations of inputs may/will never occur. (i.e. there are inputs for something, but you know it won’t happen)
As such, the creator of the circuit is open to set the output for these inputs to 0 or 1 to simplify the system. These input conditions are known as ‘don’t care’ conditions.
What is the hazard in combinational logic?
They are practical electronic logic circuits and thus not ideal devices. They have a finite time to operate.
This may introduce delays into the propagation of information. As a result, this may invalidate the rules of boolean algebra and cause errors in the logic state.
Hazard Elimination Example
Delays can be caused by the inverters (an extra step in the circuit).
You need to add a redundant loop, that outputs the value need for the final gate, while the other gate waits for correct output (?).
How do you determine the number of rows in a truth table for n number of variables?
2<strong>n</strong>
What is the problem with conventional logic systems?
As the number of variables increase, both the number of gates and the number of input terminals the gates have increased rapidly and quickly become unmanageable.
Also, any minor change in the system (such as adding another input variable) requires a major redesign of the circuit.
What is the general form of an adder cell ?
How do you make an N-bit adder ?
For an N-bit adder, we can simply interconnect N full adder cells as shown.
What composes a half adder cell?
To get the result S and the carry C, you need an EXOR gate as well as a AND gate.
If X and Y are two bits we’re adding, you can see that if both are 1, the value for S is 0 and the value of carry is 1. The carry will move to the next adder cell.
How does a full adder work? What are its components?
It is composed of two half adder cells.
There is also an incoming carry, Cin .
The output S goes through both HA.
The carry coming out of the first HA, goes to an OR gate.
The incoming carry goes to the 2nd HA, so it adds to the value of S. The resultant carry from the 2nd HA also goes to the OR gate.
The OR gate will result in an output of 1, if one of the carry inputs is equal to 1 or both are.
How does a 4-bit carry adder work?
The process is a follows.
The first full-adder calculates the first bit from A0 and B0 , with any incoming carry.
Then, the value of the resulting carry is moved to the next FA.
And so on, unitl the final 4th bit
What is parity?
It is way of detecting errors
A single bit error can be detected by it (not more…)
Alongside the bit stream, we send an EXTRA bit, the parity bit. It tells us the number of 1s.
There are two types of parity, even and odd.
If EVEN parity is used, the value of the extra bit needs to make the signal even. So if the number of 1s in the signal is odd, the parity bit will be 1, to make the transmitted signal EVEN.
Vice-versa, for ODD parity.
What is a parity generator?
A parity generator finds the parity value of a signal, which can later be used to check if the signal transmitted correctly.
Why is an EXOR gate used in a 4 bit parity generator?
Okay, so the EXOR gate is just to control the value of P output (Po). If the input bit is zero and the input value for P is zero , since the number of 1s has NOT changed, the value of P does not need to change. If the bit is zero and the previous P is 1, again, it does not need to change. If the value for x is 1, and the incoming parity is 0, it needs to adjust to the change, so now the NEW values of the parity is 1. If x is 1 and the incoming parity bit is also 1, again the value of the parity needs to change to accommodate the new number of 1s.
What is the significant difference between dedicated logic circuits and programmable logic systems?
Dedicated logic circuit (combinational circuits) will only perform the function it was designed to implement, it behaves according to its truth table.
A programmable logic system is electronically reconfigurable so that different logic operations can be performed, without having to change the circuit.
How does a NAND gate composed of n-switches work?
So the NAND works by having two switches which are connected to ground. When both the switches are closed, the current can short circuit and this is the reason the voltage through Vo is zero.
How does a NOR gate composed of n-switches work?
The switches are in parallel to each other.
As a result, all it takes is one switch to be closed for a short circuit to be complete leaving Vo with no votlage.
What is the difference between a n-switch and p-switch
With an n-switch if the applied voltage is above the threshold voltage, it closes to form a short circuit.
With a p-switch if the applied voltage is below the threshold it is closed forming a short circuit
In other words, the n-switch is open circuit with no voltage and p-switch is open circuit with the max applied voltage.
Two Input NAND gate for p-switch circuit diagram and truth table?
Why is there no voltage at Vo when both switches have +5V? For p-switches, the voltage needs to drop below a threshold to close it, otherwise, it stays open. So when +5V is applied both switches are open circuit, so no voltage at Vo.
When only one has voltage applied, the circuit isn’t open circuit because the current is flowing through the other switch.
Two input NOR gate for p-switch, what is the circuit diagram and truth table?
What sort of connections (series or parallel) do you need to create NAND and NOR gates for both N and P switches?
NAND: Series for n, parallel for p
NOR: parallel for n, seris for p
seems like the Vo is above the switches in n and below for p…
Analogue vs Digital
An analogue measurement is a continuous function
Digital is discrete and quantised
Convert Integer To Binary
1910 = 100112
Remember, the binary value you obtain by dividing needs to be
Convert Fraction to Binary
Unlike integers, you do NOT have to reverse the order.
What is the rule you need to remember when you’re converting from binary to an integer, and vice-versa?
When converting from a smaller to a larger base (binary to decimal) use a polynomial expansion.
When converting from a larger to a smaller base (decimal to binary) use successive division (for integer part) or successive multiplication (for non-integer part)
How do you convert binary to Hexadecimal?
Break binary into 4-bit pieces.
Add zeros in front if there is a remainder of dividing.
What is the 1s complement useful for?
What is its main downfall?
The main benefit of using the 1s complement is that the addition of a positive number and a negative number gives the correct answer (provided the answer is negative…)
The main issue is that there is a dual representation of zero.
What is the 2s complement?
Modification of the 1s complement that allows for a unique representation of zero.
By adding 12 to the 1s complement of the negative number we remove the value -0(negative zero).
You add 1 to the end, and remember to take into account any carry over.
2s complement is only for negative!!
What is the 2s complement of 2?
We can remove the negative sign as we are only looking at the magnitude, the sign bit 1 is in fact still there, just not shown…
What is the value of 6 - 2 using 2s complement negative numbers ?
What is the value of -2 - 6 using 2s complement negative numbers?
Sequential Logic: What is a clock?
Clocking times the circuit.
It decides the time of the input.
You can decide the speed of circuit by changing the clock frequency.
It is a signal that goes from low to high, then high to low.
What is the definition of duty cycle?
Ratio of the signal being high to the total time of the signal.
Triggering methods in Flip Flops / Latches
There is level triggering and edge triggering.
In level triggering whenever, the clock is in high, there will be a transition in the latch or flip flop.
There are two types of edge triggering. Positive and negative edge triggering.
With positive edge triggering, whenever the clock goes from low to high, the memory element will change state.
It’s the opposite with negative edge triggering. When the clock goes from high to low, the memory element will change state.
Whats the difference between a Latch and a Flip Flop?
The only thing that differentiates a latch and a flip-flop is the control input.
If the control input is an enabler, or in other words, the circuit is controlled by level triggering (enabled when the control input signal is high, i.e. by a clock).
A flip-flop is controlled by edge triggering through a clock.
A latch isn’t controlled by a clock.
How does the SR Latch work?
The SR Latch can be created using NOR or NAND.
The values or Q and Q-compliment are influenced by the inputs S and R.
Looking at the NOR gate, there are 3 different cases of the input values of S and R.
Case 1:
When S= 0, R=1, you can see from the truth table in the image that if any input for a gate is 1, the resulting value for that gate is going to be zero. So, in this case, R=1, so Q=0, and since we know that Q=0. Since the other NOR gate is connected to Q, both inputs are 0, and thus the output of the second NOR gate is 1. This makes sense as the output is Q-compliment, the opposite of Q.
Now… if R=0 is changed to zero, the input to the first NOR gate will be 0 and 1, the resulting value for the output is 0, the same as before. Similarly, the value of second NOR gate won’t change.
Since the values haven’t changed, this is condition is called MEMORY.
Case 2:
If S= 1 and R=0, the same principles as before are applied, except the values are reversed.
Case 3:
If S=1 and R=1, we can see from the truth table that the values of Q and Q-compliment are both going to be the same. This is a red flag, they do not compliment each other. However, the main issue arises, when the input values are changed to 0, the output values will become 0,1 or 1,0. Case 3 definitely does not store the value, and the value changes depending on the NOR gate you first apply the change to.
Case 3 is NOT USED.
For NAND gate it is also very similar, but the truth table is the opposite. For NAND, 00 is not used, 01 SR results in 10 for Q and Q-compliment, 10 for SR results in 01 for the outputs, and lastly 11 results in the MEMORY value (in other words same values as last input).
What is the schematic of the D Flip-Flop?
A D Flip-Flop can be built from two back to back D-latches, which are controlled by complementary clocks.
There is only one input with a D flip-flop, even though two inputs are necessary. The D flip-flop takes advantage of the fact that the inputs must be complementary to change the memory, and thus an inverter is used in a D flip-flop.
How does the D flip-flop work ?
When the CLK is 0, the master latch is transparent (because of the inverter) and the slave is opaque.
Since the master latch is transparent, D propagates through to N1.
When CLK = 1, the master is opaque and the slave is transparent. As a result, whatever value was at D before the change in CLK, gets copied to Q immediately after the CLK changes. This all happens during the change of CLK.
So essentially, the value of D changes the value of the output Q immediately when CLK=1.
A flip-flop copies D to Q on the rising edge of the clock, and it remembers its state at all other times.
What is a register?
An N-bit register is simply a bank of N number of flip-flops that share a common CLK input. so that all bits of the register are updated at once.
What does the D flip-flop do?
D flip flop copies the data input D into the output Q on the rising edge of the clock, it remembers its state all the other times.
What is the difference between Mealy and Moore State Machines?
Moore state machines output is the function of the present state only. This means that the outputs will NOT change until the state changes.
Mealy state machines output is the function of the present state and the input. Note that it may depend on the either of them, but doesn’t have to.
A key difference in how they are represented, in a Moore machine the state is placed inside the state bubble. In a Mealy machine the state is placed next to the input in the transition (implying that the state affects the output).
How do you make the state diagram?
You need to analyze the circuit and find the state equation.
From the equation you should the state table, defining the initial state, input, and then the new state and output based on the state equation.
Describe the input, state and output of a FSM.
Inputs: the incoming bits
State: Describe the current condition of the state machine. There are a limited number of states for a given FSM. The state of the FSM is determined by the history of the input.
Outputs: Are linked to the FSM’s state but are not the same thing. Outputs can depend either on the state only (Moore) or on the state and inputs (Mealy). Just like inputs, outputs are typically single bits.
How would you go about drawing a state diagram for a FSM ?
- You need to first identify the inputs and outputs
- Identify different states of operation
- Draw state diagram
Moore or Mealy circuit?
Y is independent of A, so its a moore model.
So in these sorts of questions, you need to look at the output, and see if it is in any way dependent on the state.
inputHow do state diagrams for Moore and Mealy state machines differ?
In Moore machines, the output is defined within the state bubble. This makes sense as the output is only dependent on the input.
Mealy machine state diagrams, the output is shown outside the state bubble.
What is the purpose of the state diagram?
The state diagram is similar to a flowchart that helps you visualize how ‘states’ transition between each other (or not) depending on the input. The output is also defined.
It is used in FSMs to show how the state’s transition.
When looking at the number of bits in the state column of state table, how can you determine the number of states?
It is dependent on the number of bits the states are represented by.
Why is a FSM considered a synchronous sequential circuit?
An FSM is a sequential circuit since the output is dependent on the current state and its associated input which itself was determined by the state and input before it, and so on.
When do you use don’t care in state diagrams?
When it doesn’t matter what value an input variable has on a state change.
When an input variable has no impact on state change from one state to another.
In the image k is considered a dont’t care bit twice. This because k had a value of 0 and 1 for the same state change, twice. This means that the value assigned to k is meaningless.
Knowing the number of states of an FSM how do you determine the k-bit register?
The number state and k-bit register are related by 2k .
So the value of k can be determined by taking the log in base 2 for the number of states.
How do you determine equations from a state table?
For the variable you’re looking at, identify all the moments it is equal to 1. For those instances identify the input (or state) combination (taking into account compliments) and create the equation. If possible simplify the equation.
One-hot encoding vs binary encoding?
More flip-flops are required with one-hot encoding, but the next-state and output logic is often simpler.
What does a truth table do?
It lists all possible combinations of inputs (e.g. input where one is 0 and the other 1, vice versa, etc.) and then the associated output of the inputs.
What is a thing that an exclusive NOR gate can check?
it can check for equality.
If both inputs are 0, it outputs 1, if both outputs are 1, it outputs 1.
How does a magnitude comparator work?
Magnitude comparison is done by computing A - B. If the result is negative, then B is greater than A, otherwise A is greater than or equal to B.
List out the typical functions a ALU can perform?
What is a multiplexor?
What can it simply defined as?
A multiplexor is a combinational circuit that selects binary information from one of many inputs lines and directs it the output line.
It is simply a data selector.
What does this represent?
It signifies that the line represents N number of bits.
If N was 4, the wire line would represent 4 bits.
What is the typical implementation of n-bit ALU?
Describe how the ALU functions.
The arithmetic and logical blocks in the ALU operate on A and BB. BB is either B or 𝐵(compliment), depending on the value of F2. If F1:0 = 00, the output multiplexer chooses A AND BB. If F1:0 = 01, the ALU computes A OR BB. If F1:0 = 10, the ALU performs addition or subtraction. Note that F2 is also the carry into the adder (recall that -B = 𝐵(comp) + 1 in 2’s complement arithmetic). If F2 = 0, the ALU computes A + B. If F2 = 1, the ALU computes 𝐴 + 𝐵(comp) + 1 = 𝐴 − 𝐵.
When F2:0 = 111, the ALU performs the set if less than (SLT) operation. With this operation, if A < B, Y = 1, else Y = 0. In other words, Y is set to 1 if A is less than B.
SLT is performed by computing S = A – B. If S is negative (i.e., the sign bit is set to 1), this shows that A is less than B. The zero extend unit produces an N-bit output by concatenating its 1-bit input with 0’s in the most significant bits. The sign bit (SN-1) of S is the input to the zero extend unit.
What is the output of this LSR
00110
What does the Arithmetic shifter do?
And what is the output of this ASR, arithmetic shift right.
Similar to logical shifters, but on right shifts, it fills the most significant bits (largest bits) with a copy of the old significant bit.
This is useful for multiplying for dividing signed numbers.
What is a rotator?
Also called a circular shift, shifts numbers around.
Empty spots are filled off the other end.
How can a logical shift left multiply and a logical shift right divide?
A left shift by N bits multiplies the number by 2N , (For example, 000000112 << 4 = 001100002 is equivalent to 310 × 24 = 48 in base 10)
A logical shift right by N bits divides the number by 2<strong>N</strong>.
What is the symbolic representation of a logical shift left?
With this implementation of a logical shift left, explain how it works.
By using the multiplexor you can decide the shift you want through shamt. A 00 input into shamt results in no shift, and this can be observed as all the inputs land in the same position in the output Y.
If shamt is 01, A2 is output at Y3, so it moved up one place, etc.
What does the symbol of a 4x4 binary multiplier look like?
What is the implementation of a binary counter?
What is a REGISTER?
A group of flips flops is known as a register. Compared to a normal flip-flop, this increases storage capacity.
The n-bit register consists of ‘n’ number of flips flops and is capable of storing an ‘n-bit’ word.
How do a synchronous and asynchronous counter differ?
With synchornous, the clock is connected to all the flip-flops at once.
What is the essence behind De Morgans theorem?
If there is a straight bar over n number of variables that are AND’d, it will be equivalent to the variables having individual bars and OR’d together.
Vice-versa.
If one bar across variables that are OR’d, the equivalent would be the variables AND’d but with individual bars.
Why do you sometimes have to double a function to apply De Morgans?
You can double bar something because it’s essentially the same as before.
However, now with the double bar, you can apply De Morgan’s and split one of the bars up, and it would still be equivalent.
What are these AND operations equal to ?
What are these OR operations equal to ?
What does the symbol representation of an arithmetic shift right (ASR) ?
When your simplifying a boolean expression and you see two of the same variables OR’d with eachother, what should you know?
That the value of a variable OR’d with itself is just equal to the variable itself.
When you see this what can you do?
You can factorize out the A_bar and you’ll be left with 1+B_bar which using the boolean algebra is equal to 1, which makes sense, 1 OR’d with a variable is always 1 since 1 is equal to TRUE.
How can you differentiate a n-switch from a p-switch?
n-switch has a negative next to the switch and hinges at the bottom.
p-switch is the exact opposite, it has a positive symbol and hinges at the top.
From n number of variables, how do you determine how many functions a multiplexor can perform?
A 2n to 1 multiplexer can be programmed to perform any function of n variables.
What would a 4 variable 4:1 multiplexor look like?
What is a multiplexor?
A MUX is a digital switch that has multiple inputs (sources) and a single output (destination).
The select lines determine which input is connected to the output.
“A multiplexor is a logic circuit which accepts many inputs, but selects only one input to be passed to the output.
What does an n-switch look like (exact symbol)?
What does a p-switch look like (exact symbol)?
Note the placement of Source(S) and Drain(D)
For N-switch circuits, are the switches performing pull down or pull up on the output voltage?
pull down
the resistor is providing the pull up
For P-switch circuits, are switches performing a pull down or pull up on the output voltage?
pull up function
resistor is providing pull down
What functions do CMOS circuits naturally yield?
Naturally yield NOR and NAND functions.
What is forward cross talk?
Cross talk is when signals running along adjacent tracks or wires are coupled together by mutual capacitance.
Forward cross-talk is when adjacent tracks of data signals run in the same direction. Problems usually occur when propagation distances exceed 1 metre.
What is back cross-talk?
Cross talk is when signals running along adjacent tracks or wires are coupled together by mutual capacitance.
Back cross-talk occurs when signals travel in opposite directions on adjacent tracks.
This can cause serious problems over coupled lengths of a few centimetres.
How can cross-talk be eliminated?
Crosstalk can only be eliminated by modifying the layout of the circuit board, increasing the spacing between tracks or separating cross-talking tracks with a third track at ground potential. In extreme cases, a ground plane may be needed.
rs flip flop is equivalent to…
SR flip flop
What is a group of flip-flops known as?
REGISTER
