Please enable JavaScript.

Coggle requires JavaScript to display documents.

DL (Digital Logic) - Coggle Diagram

- - - - Operations
        
        Subtractions by 1’s Complement
        
        If there is no carry bit 1, then take 1’s complement of the result which will be negative
        
        If the result of above addition has carry bit 1, then add it to the least significant bit (LSB) of given result
        
        Take 1’s complement of the subtrahend
      - Number Systems
        
        Base Conversion
        
        Fraction Part
        
        Decimal to R
        
        Multiply by R till fraction becomes zero, which may or not happen(recurring decimal)
        
        Binary to Hex/Octal
        
        Group bits by 4/3
        
        Integer Part
        
        Decimal to R
        
        Divide by R till quotient becomes 0
        
        Binary to Hex/Octal
        
        Group bits by 4/3
        
        Combinations
        
        Decimal To Hex
        
        Decimal To Octal
        
        Decimal To Binary
        
        Hex To Octal
        
        Octal To Hex
        
        Base-r
        
        The coefficients a j range in value from 0 to r – 1
        
        Decimal
        
        Hexadecimal
        
        0-9, A-F
        
        Octal
        
        Binary
      - The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s)
      - Unlike two's complement, these numbers have not seen widespread use because of issues such as the offset of −1, that negating zero results in a distinct negative zero bit pattern, less simplicity with arithmetic borrowing, etc
      - The ones' complement of the number then behaves like the negative of the original number in some arithmetic operations
      - To within a constant (of −1), the ones' complement behaves like the negative of the original number with binary addition
    - - Types
        
        (r-1)'s Complement
        
        Given a positive number N in base r with an integer part of n digits and a fraction part of m digits
        
        r^n - r^–m – N
        
        r's Complement
        
        Given a positive number N in base r with an integer part of n digits
        
        r^n – N for N ≠ 0 and 0 for N = 0
      - Complements are used in digital computers for simplifying the subtraction operation and for
        logical manipulations
    - - Base
      - Format
        
        Sign
        
        1-bit
        
        Exponent
        
        Excess-127
        
        Subtract 127
        
        0 means very small number
        
        Makes circuitry simple
        
        Unsigned 8-bits
        
        True Exponent
        
        E - 127
        
        Mantissa
        
        23-bits
        
        Forms
        
        Normalized
        
        Avoids multiple representation
        
        In the normalized form, the actual fraction is normalized with an implicit leading 1 in the form of 1.F
        
        In normalized form, the actual exponent is E-127 (so-called excess-127 or bias-127)
        
        De-Normalized
        
        De-normalized form was devised to represent zero and other numbers
        
        For E=0, the numbers are in the de-normalized form
        
        An implicit leading 0 (instead of 1) is used for the fraction
        
        The actual exponent is always -126
        
        E = 0 and E = 1 lead to the same Exponent value = -126
        
        Smallest number is 0.00000001 * 2^-126 = 2^-134
  - - - Canonical Form
        
        Maxterms
        
        F(x,y,z) = ∏(0,2, 4, 5)
        
        Standard Sum
        
        Designated with M
        
        Product of maxterms
        
        Minterms
        
        Sum of minterms
        
        F(A,B,C) = ∑ (1,4, 5,6,7)
        
        Designated with m e.g. m0, m1, etc.
        
        Standard Product
        
        F(A, B, C) has MSB as A and LSB as C. e.g. ABC' will be m6
        
        Truth Table to Boolean Function
        
        A Boolean function may be expressed algebraically from a given truth table by forming a minterm for each combination of the variables which produces a 1 in the function, and then tak-
        ing the OR of all those terms.
        
        A Boolean function may be expressed algebraically from a given truth table by forming a maxterm for each combination of the variables which produces a 0 in the function, and then taking the AND of all those terms.
        
        Conversion between Canonical Forms
        
        the maxterm with subscript j is a complement of the minterm with the same subscript j
        
        Steps
        
        list those numbers missing from the original form
        
        interchange the symbols ∑ and ∏
      - Simplification of Boolean Functions
        
        Minimization
        
        Karnaugh map
        
        Representation
        
        Each square represents one minterm
        
        The map is a diagram made up of squares
        
        A Boolean function is recognized graphically in the map from the area enclosed by those squares whose minterms are included in the function.
        
        0 is X' and 1 is X
        
        Only 1 bit can change between subsequent blocks horizontally or vertically
        
        Don't Care
        
        For values that don't matter we can include them in both minterm and maxterm which are marked with X
        
        Don't draw additional boxes just to accommodate DC;s
        
        Implicants
        
        Prime Implicants
        
        A group of square or rectangle made up of bunch of adjacent minterms which is allowed by definition of K-Map are called prime implicants(PI)
        
        Maximum number of prime implicant = 2^(n-1)
        
        A PRIME IMPLICANT is a product term that cannot be combined with another term to eliminate a variable
        
        Essential Prime Implicants
        
        These are those subcubes(groups) which cover atleast one minterm that can’t be covered by any other prime implicant
        
        Essential prime implicants(EPI) are those prime implicants which always appear in final solution
        
        Maximum number of essential prime implicant = 2^(n-1)
        
        Selective Prime Implicants
        
        The prime implicants for which are neither essential nor redundant prime implicants are called selective prime implicants(SPI)
        
        These are also known as non-essential prime implicants
        
        They may appear in some solution or may not appear in some solution
        
        Redundant Prime Implicants
        
        The prime implicants for which each of its minterm is covered by some essential prime implicant are redundant prime implicants(RPI)
        
        This prime implicant never appears in final solution.
        
        Minimization
        
        Handle Don't Cares
        
        Combine across edges
        
        Top Bottom
        
        Left-Right
        
        Diagonal
        
        Remove the variables which are both 0 and 1 inside the group
        
        Group 1s by power of 2
        
        Maxterm Handling
        
        Same process as min-terms but use 0 instead of 1
        
        Use inverted variable when creating the maxterms. Example: is X'Y are in the maxterm, then the maxterm will be (X + Y')
        
        Quine-McCluskey Tabular Method
        
        Algo
        
        Group min-terms by the number of 1s
        
        Check group pairs n and n+1 for every pair of entries check if they vary by only on variable
        
        Group them and replace the varying variable by d
        
        Keep track of minterms which are used for grouping
        
        Keep track of terms which are not merged
        
        Repeat till not further reduction happens
        
        The minterms are the last table and all unchecked minterms
        
        Create new table with initial minterms for columns and the final terms as rows
        
        Put x in the columns for the final terms which are applicable for the minterm
        
        The solution are the rows which have a entries with a single x in a column
      - Standard Forms
        
        Types
        
        Product of Sums
        
        Canonical
        
        Each sum term contains all literals
        
        Sum of Products(SOP)
        
        Canonical
        
        Each product term contains all literals
        
        Product of SOPs
        
        When two SOP expressions are multiplied only the common terms remain
        
        Example: ∑m(4,5,6,7,8) * ∑m(1,6,8) = ∑m(6,8)
        
        Terms may not contain all the literals
        
        Function of Standard Forms
        
        Σ*Σ will only retain the common terms with Σ output
        
        ∏' = Σ of terms not included in ∏
        
        Σ+Σ has the union of the terms
        
        ∏*∏ has the union of the terms in ∏
        
        ∏+∏ will only retain the common terms with ∏ output
        
        Σ ' = ∏ of terms not included in Σ
        
        Find unknown function
        
        Reduce the function of standard forms
        
        At the last stage it will be apparent which should be the correct option in MCQ
      - A Boolean function is an expression formed with
        binary variables, the two binary operators OR and AND, the unary operator NOT, parentheses, and equal sign
      - Complete Function
        
        Tutorial
        
        Video 1
        
        Geeks
        
        A set of boolean functions is complete if all the boolean functions can be expressed with the help of functions of the set
        
        If (NOT, AND) or (NOT, OR) can be implemented with the set of boolean functions then all functions can be implemented with the functions
      - Cover
        
        A switching function f(x1, x2, ..., xn) is said to cover g(x1, x2, ..., xn) denoted by 'f is a superset of g' if f assumes true value whenever g does
        
        if f covers g and g covers f then both are equivalent
      - Hazards
        
        A hazard, if exists, in a digital circuit causes a temporary fluctuation in output of the circuit
        
        A hazard in a digital circuit is a temporary disturbance in ideal operation of the circuit which if given some time, gets resolved itself
        
        These disturbances or fluctuations occur when different paths from the input to output have different delays and due to this fact, changes in input variables do not change the output instantly but do appear at output after a small delay caused by the circuit building elements, i.e., logic gates
        
        Types
        
        Static hazard
        
        A static hazard takes place when change in an input causes the output to change momentarily before stabilizing to its correct value
        
        Types
        
        Static-1 Hazard
        
        If the output is currently at logic state 1 and after the input changes its state, the output momentarily changes to 0 before settling on 1, then it is a Static-1 hazard
        
        Detection of Static hazards using K-map
        
        4 more items...
        
        Removal of static-1 hazard
        
        2 more items...
        
        Static-0 Hazard
        
        If the output is currently at logic state 0 and after the input changes its state, the output momentarily changes to 1 before settling on 0, then it is a Static-0 hazard
        
        Similarly for Static-0 Hazards we need to consider 0’s instead of 1’s and if any adjacent 0’s in K-map are not grouped into same group that may cause a static-0 hazard
        
        The method to detect and resolve the static-0 hazard is completely same as the one we followed for static-1 hazard except that instead of SOP, POS will be used as we are dealing with 0’s in this case
        
        Dynamic hazard
        
        Functional hazard
    - - A set of elements
        
        {0, 1}
      - Theorems, Axioms, Postulates
        
        Theorems
        
        Theorem 2
        
        x • 0 = 0
        
        x + 1 = 1
        
        Theorem 5, Demorgan
        
        (xy)′ = x′ + y′
        
        (x + y)′ = x′ y′
        
        Theorem 4, Associative
        
        x + (y + z) = (x + y) + z
        
        x(yz) = (xy) z
        
        Theorem 3, Involution
        
        (x′)′ = x
        
        Theorem 1
        
        x • x = x
        
        x + x = x
        
        Theorem 6, Absorption
        
        x + xy = x
        
        x(x + y) = x
        
        Postulates(Huntington)
        
        Postulate 3
        
        x + y = y + x
        
        xy = yx
        
        Postulate 4
        
        x (y + z) = xy + xz
        
        x + yz = (x + y) (x + z)
        
        if y = x', then x + x'z = (x + x')(x + z) = x + z
        
        Postulate 2
        
        x + 0 = x
        
        x • 1 = x
        
        Consensus/Redundancy Theorem
        
        AB + A'C + BC = AB + A'C
      - Properties
        
        Duality Principle
      - A set of operators
        
        OR
        
        AND
        
        NOT
      - Operator Precedence
        
        OR
        
        NOT
        
        AND
        
        Parentheses
    - - F1 = xy
        
        AND
        
        x and y
      - F11 = x + y′
        
        If y then x
        
        x ⊂ y
      - F6 = xy′ + x′y
        
        x or y but not both
        
        Exclusive-OR
      - F2 = xy′
        
        x but not y
        
        x/y
      - F13 = x′ + y
        
        If x then y
        
        x ⊃ y
      - F7 = x +y
        
        OR
      - F5 = y
        
        Transfer
      - F14 = (xy)′
        
        NAND
        
        x↑y
      - F0 = 0
      - F4 = x′y
        
        y but not x
        
        y/x
      - F8 = (x + y)′
        
        NOR
        
        x ↓ y
      - F3 = x
      - F 12 = x′
      - F15 = 1
      - F10 = y′
      - F9 = xy + x′y′
    - - Combinational
        
        Types
        
        Encoder
        
        It has maximum of 2^n input lines and ‘n’ output lines
        
        The encoder encodes 2n input lines with ‘n’ bits
        
        Disadvantages
        
        There is an ambiguity, when all outputs of encoder are equal to zero. Because, it could be the code corresponding to the inputs, when only least significant input is one or when all inputs are zero
        
        If more than one input is active High, then the encoder produces an output, which may not be the correct code. For example, if both Y3 and Y6 are ‘1’, then the encoder produces 111 at the output. This is neither equivalent code corresponding to Y3, when it is ‘1’ nor the equivalent code corresponding to Y6, when it is ‘1’
        
        Priority Encoder
        
        Even if more than one input is ‘1’ at the same time, the output will be the binary code corresponding to the input, which is having higher priority
        
        The MSB has the highest priority
        
        LSB has the lowest priority
        
        Additional output to indicate if output is valid
        
        Code Converters
        
        Decoder
        
        Decoder is a combinational circuit that has ‘n’ input lines and maximum of 2n output lines
        
        One of these outputs will be active High based on the combination of inputs present, when the decoder is enabled
        
        Higher Order Decoders can be implemented using lower order
        decoders
        
        Think of the problem as output level to input level calculation
        
        To select the that many decoders in the last level we have to select the number of decoder in the previous level and so on
        
        Formula
        
        Or
        
        2 more items...
        
        Create log2(m) x m decoder using log2(n) x n decoders
        
        Demultiplexer
        
        De-Multiplexer is a combinational circuit that performs the reverse operation of Multiplexer
        
        It has single input, ‘n’ selection lines and maximum of 2n outputs
        
        The input will be connected to one of these outputs based on the values of selection lines
        
        Higher order de-multiplexers can be implemented using lower order de-multiplexers
        
        Implemented using decoder where each output line of the decoder is ANDed with the input signal and enabled line of the decoder receives the input signal
        
        Comparator
        
        Multiplexer
        
        Multiplexer is a combinational circuit that has maximum of 2^n data inputs, ‘n’ selection lines and single output line
        
        One of these data inputs will be connected to the output based on the values of selection lines
        
        Cascaded Multiplexer
        
        Higher order multiplexers can be implemented using lower order multiplexers
        
        8x1 from 4x1
        
        32x1 using 8x1
        
        Use enable line when the ratio is less than 1
        
        Mux Tree
        
        Find number of mux needed
        
        Implement mx1 using nx1
        
        3 more items...
        
        Expression simplification for MUX
        
        If enable signal is parameterized then multiply the MUX output with the enable variable
        
        Implemented using decoder where each output line of the decoder is ANDed with one input signal and all the ANDed signals are ORed, so the signal will be forwarded on the output line
        
        Arithmetic Circuits
        
        Adders
        
        Half Adder
        
        Half adder is a combinational circuit, which performs the addition of two binary numbers A and B of single bit
        
        Outputs
        
        2 more items...
        
        Inputs
        
        2 more items...
        
        Full Adder
        
        Full adder is a combinational circuit, which performs the addition of three bits A, B and Cin
        
        Inputs
        
        3 more items...
        
        Outputs
        
        2 more items...
        
        Full Adder from Half Adder
        
        1 more item...
        
        Full Adder From NAND gates
        
        Full Adder From NOR gates
        
        Delay Calculation
        
        4 more items...
        
        Parallel Adder
        
        Ripple Carry Adder
        
        5 more items...
        
        Carry Lookahead Adder
        
        6 more items...
        
        Serial Adder
        
        BCD Adder
        
        Each digit is 0-9
        
        Two 4-bit Adders needed
        
        Carry = C + S3*S2 + S3*S1 from first adder
        
        Add 6 to first adder output if carry is 1, discard carry of second adder
        
        Excess-3 Adder
        
        Excess-3 Code
        
        Subtractor
        
        A−B=A+(2′scomplimentofB)
        
        A−B=A+(1′scomplimentofB)+1
        
        1 more item...
        
        Binary Adder / Subtractor
        
        Produces either the addition or the subtraction based on the value of initial carry or borrow, 𝐶0
        
        The second input is XORed with initial carry
        
        Multiply
        
        Booths Algorithm
        
        Explanation
        
        Example
        
        Recoding
        
        5 more items...
        
        Implementation
        
        Universal Gates
        
        NOR
        
        NAND
        
        NOT Gate
        
        Feed same variable to both inputs of Nand gate, since a'+a' = a', the gate will behave as not gate
        
        AND Gate
        
        Use two nand gates
        
        Feed two variables to first nand gates which outputs (a.b)'
        
        Feed this as the input to both input pins of the second nand gate which will compute (a.b)'' = ab
        
        OR Gate
        
        Minimum Gates Implementation
        
        Logic
        
        Express function using K-map
        
        NAND
        
        7 more items...
        
        NOR
        
        7 more items...
        
        Special Case
        
        1 more item...
        
        Mixed with AND/OR
        
        After expressing with AND and OR check if some paths maybe kept intact to meet the criteria of mixing universal and specified gate types
      - Sequential
        
        This sequential circuit contains a set of inputs and outputs
        
        The outputs of sequential circuit depends not only on the combination of present inputs but also on the previous outputs
        
        Previous output is nothing but the present state
        
        Sequential circuits contain combinational circuits along with memory storage elements
        
        Some sequential circuits may not contain combinational circuits, but only memory elements
        
        Types
        
        Asynchronous sequential circuits
        
        Asynchronous sequential circuits do not use clock signals as synchronous circuits do
        
        Instead, the circuit is driven by the pulses of the inputs which means the state of the circuit changes when the inputs change
        
        The change of internal state occurs when there is a change in the input variable
        
        Their memory elements are either un-clocked flip-flops or time-delay elements
        
        They are similar to combinational circuits with feedback
        
        Synchronous sequential circuits
        
        In synchronous circuits the input are pulses (or levels and pulses) with certain restrictions on pulse width and circuit propagation delay
        
        Types
        
        Clocked
        
        In a clocked sequential circuit which has flip-flops or, in some instances, gated latches, for its memory elements there is a (synchronizing) periodic clock connected to the clock inputs of all the memory elements of the circuit, to synchronize all internal changes of state
        
        The operation of the entire circuit is controlled and synchronized by the periodic pulses of the clock
        
        Triggering
        
        2 more items...
        
        Clock signal
        
        5 more items...
        
        Unclocked/Pulsed
        
        Pulse mode circuits require two consecutive transitions between 0 and 1 - that is a 0-pulseor a 1 pulse to alter the circuit’s state
        
        A pulse -mode circuit is designed to respond to pulses of certain duration
        
        The constant signals between the pulses are “null” or “spacer” signals, which do not affect the circuit’s behavior
        
        Memory Elements
        
        Latches
        
        Latches operate with enable signal, which is level sensitive
        
        Types
        
        2 more items...
        
        Gated Latch
        
        3 more items...
        
        Flip-flops
        
        A flip flop is edge sensitive and its output changes only when the clock edge rises (positive edge triggered) or falls (negative edge triggered)
        
        Types
        
        4 more items...
        
        Flip-Flop Conversion
        
        2 more items...
        
        Timing
        
        3 more items...
        
        Tables
        
        2 more items...
        
        Clock Control
        
        3 more items...
        
        Bistable Element
        
        Made with two not gates with the output of one feeding the other
        
        Metastable state
        
        Counters
        
        Types
        
        Synchronous Counter
        
        3 more items...
        
        Asynchronous Counter
        
        3 more items...
        
        Value Change Types
        
        Ascending
        
        Descending
        
        Non-Linear
        
        Shift Register
        
        If the register is capable of shifting bits either towards right hand side or towards left hand side is known as shift register
        
        An ‘N’ bit shift register contains ‘N’ flip-flops
        
        Types
        
        Serial In − Serial Out shift register
        
        Serial In − Parallel Out shift register
        
        Parallel In − Serial Out shift register
        
        Parallel In − Parallel Out shift register
        
        Tables
        
        Characteristic Table
        
        Excitation Table
    - - Extension to Multiple Inputs
        
        NAND NOR multiple inputs
        
        x ↓ y ↓ z = (x + y + z)′
        
        x ↑ y ↑ z = (xyz)′
        
        A gate can be extended to have multiple inputs if the binary operation it represents is commutative and associative
      - AND, OR, NAND, NOR, exclusive-OR, and equivalence, are used as standard gates in digital design
      - XNOR Gate = NOT(XOR) = AB + A'B'
      - XOR = AB' + A'B
      - Open Collector
        
        Works like NOR gate
        
        OR everything and then apply not on the output
    - - Venn Diagram
      - Logic System
        
        Dual Functions
        
        Principle of Duality
        
        Any theorem or identity in Boolean algebra remains true if 0 and 1 are swapped and . and + are swapped throughout
        
        Self Dual
        
        A boolean function is called self dual if its dual is equal to itself
        
        Properties
        
        Function is neutral
        
        The given function is neutral i.e., (number of min terms is equal to the number of max terms)
        
        Neutral Function
        
        2 more items...
        
        Mutual Exclusive Minterms
        
        The function does not contain two mutually exclusive terms
        
        Two terms are mutually exclusive if they have no common variable e.g XY and X'Y' are mutually exclusive
        
        Contains one minterm from each mutually exclusive pair
        
        Number of Functions
        
        Total number of minterms = 2^n
        
        Total allowed minters = 2^n/2 = 2^(n-1)
        
        2 more items...
        
        Self duality is closed under compliment i.e, compliment of a Self dual function is also Self dual.
        
        The dual of a Boolean expression is the expression one obtains
        by interchanging addition and multiplication and interchanging 0’s and 1’s
        
        We take dual of an expression to convert positive logic system to negative logic system
        
        Positive Logic System
        
        Negative Logic System
      - Neutral Function
        
        Equal number of 0s and 1s
        
        Equal number of minterms and maxterms
        
        Number of Dual Functions
        
        2^nC2^(n-1)
      - Orthogonal Function
        
        A function is said to be orthogonal if both dual and complement of the function are equal
        
        Checking
        
        Function should be neutral
        
        It must have half number of mutually exclusive pairs(complete pair)
        
        Number of Orthogonal
        
        2^(n-1)C2^(n-2)
        
        Doubt
        
        Power of 2 is not needed in this case as combinations take care of all cases
  - - - Binary Coded Decimal or BCD is simply the 4-bit binary code representation of a decimal digit with each decimal digit replaced in the integer and fractional parts with its binary equivalent
  - - - Degenerative form
        
        If the output of two level logic realization can be obtained by using single Logic gate, then it is called as degenerative form
        
        The number of inputs of single Logic gate increases, the fan-in of Logic gate increases
        
        This is an advantage of degenerative form
        
        Types
        
        AND-AND
        
        AND-NAND
        
        OR-OR
        
        OR-NOR
        
        NAND-NOR
        
        NOR-NAND
      - Non-degenerative form
        
        If the output of two level logic realization can’t be obtained by using single logic gate, then it is called as non-degenerative form
        
        Types
        
        AND-OR
        
        AND-NOR
        
        OR-AND
        
        OR-NAND
        
        NAND-AND
        
        NAND-OR
        
        NAND-NAND
        
        NOR-AND
        
        NOR-OR
        
        NOR-NOR
    - - AND, OR, NAND & NOR
        
        AND-AND
        
        AND-OR
        
        AND-NAND
        
        AND-NOR
        
        OR-AND
        
        OR-OR
        
        OR-NAND
        
        OR-NOR
        
        NAND-AND
        
        NAND-OR
        
        NAND-NAND
        
        NAND-NOR
        
        NOR-AND
        
        NOR-OR
        
        NOR-NAND
        
        NOR-NOR
  - - - Parity Code
    - - Hamming Code
        
        Hamming Distance
        
        The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits
        
        We show the Hamming distance between two words x and y as d(x, y)
        
        The Hamming distance between the received codeword and
        the sent codeword is the number of bits that are corrupted during transmission
        
        The Hamming distance can easily be found if we apply the XOR operation (⊕) on the two words and count the number of 1s in the result
        
        Minimum Hamming
        Distance for Error
        Detection
        
        The minimum Hamming distance is the smallest Hamming distance between all possible pairs of codewords
        
        Linear Block Codes
        
        A linear block code is a code in which the exclusive OR (addition
        modulo-2) of two valid codewords creates another valid codeword
        
        Minimum Distance for
        Linear Block Codes
        
        The minimum Hamming distance is the number of 1s in the nonzero valid codeword with the smallest number of 1s
        
        Parity-Check Code
        
        A k-bit dataword is changed to an n-bit codeword
        where n = k + 1
        
        The minimum Hamming distance for this category is dmin = 2, which means that the code is a single-bit error-detecting code
        
        The extra bit, called the parity bit, is selected to make the total
        number of 1s in the codeword even
        
        Example
        
        4 more items...
        
        Cyclic Codes
        
        If a codeword is cyclically shifted (rotated), the result is another codeword
        
        Cyclic Redundancy Check
        
        3 more items...
        
        A code with minimum Hamming distance d between its codewords can correct ⌊(d-1)/2⌋ errors Link
        
        To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be dmin = s+1
  - - - Temporary
      - Permanent
        
        Path Sensitization