Cheatsheet Digital Logic - RRB JE for Computer Science Engineering - Computer

2. Boolean Algebra

2.1 Basic Laws

2.2 Consensus Theorem

• A·B + A'·C + B·C = A·B + A'·C
• (A+B)·(A'+C)·(B+C) = (A+B)·(A'+C)

2.3 Standard Forms

2.4 Duality Principle

• Interchange AND ↔ OR, 0 ↔ 1. Variables and complements unchanged
• Dual of a theorem is also a theorem

3. Logic Gates

3.1 Basic Gates

3.2 Universal Gates

3.3 Exclusive Gates

3.4 Gate Fan-in and Fan-out

• Fan-in: Maximum number of inputs a gate can accept
• Fan-out: Maximum number of gates that can be driven by a single output

4. Combinational Circuits

4.1 Design Procedure

1. Problem statement and input/output variables
2. Truth table formulation
3. Boolean expression from truth table (SOP or POS)
4. Simplification using K-map or Boolean algebra
5. Logic diagram implementation

4.2 Karnaugh Map (K-Map)

4.2.1 K-Map Rules

• Cells arranged in Gray code order (one bit change between adjacent cells)
• Group 1s in powers of 2: 1, 2, 4, 8, 16 cells
• Groups can wrap around edges
• Larger groups preferred (fewer literals in product term)
• Essential prime implicants must be included

4.2.2 K-Map Sizes

4.2.3 Don't Care Conditions

• Represented by X or d in truth table/K-map
• Used for grouping to minimize expression, but not required to be covered
• Occur when input combinations never appear or output doesn't matter

4.3 Quine-McCluskey Method

• Tabular minimization method for Boolean functions
• Step 1: List minterms grouped by number of 1s
• Step 2: Combine minterms differing by 1 bit, mark with dash
• Step 3: Repeat until no more combinations possible
• Step 4: Identify prime implicants (unmarked terms)
• Step 5: Construct prime implicant chart and select minimum cover

5. Arithmetic Circuits

5.1 Half Adder

5.2 Full Adder

5.3 Half Subtractor

5.4 Full Subtractor

5.5 Multi-bit Adders

5.6 Magnitude Comparator

• Compares two n-bit numbers A and B
• Outputs: A>B, A=B, A<>
• 1-bit: (A=B) = A ⊙ B = A·B + A'·B'
• n-bit: Cascade 1-bit comparators from MSB to LSB

6. Multiplexers and Demultiplexers

6.1 Multiplexer (MUX)

6.1.1 MUX as Function Generator

• n-variable function with (n-1):1 MUX: Connect n-1 variables to select lines, function values to inputs
• n-variable function with n:1 MUX: Connect n variables to select, minterms to inputs
• Large MUX from smaller ones: Tree structure, cascading

6.2 Demultiplexer (DEMUX)

7. Encoders and Decoders

7.1 Encoder

7.1.1 Priority Encoder

• Multiple inputs can be active simultaneously
• Highest priority input encoded to output
• Includes valid output indicator (V) to show if any input is active
• 4:2 priority encoder: If D₃=1, output=11 regardless of other inputs

7.2 Decoder

7.2.1 Decoder as Function Generator

• Each decoder output = one minterm
• OR together outputs corresponding to minterms where function = 1
• Can implement any Boolean function
• With NAND gates: Directly connect outputs (active low) for POS form

7.2.2 Decoder Expansion

• Use enable inputs to combine smaller decoders into larger ones
• Example: Two 3:8 decoders with enable → 4:16 decoder

8. Sequential Circuits Basics

8.1 Sequential vs Combinational

8.2 Types of Sequential Circuits

8.3 Clock Signals

• Periodic signal controlling state transitions
• Clock period (T): Time for one complete cycle
• Clock frequency (f): f = 1/T
• Duty cycle: Percentage of time signal is high in one period
• Clock skew: Difference in arrival time at different flip-flops

9. Latches and Flip-Flops

9.1 SR Latch (NOR)

• Characteristic equation: Q_next = S + R'·Q_prev
• Active high inputs

9.2 SR Latch (NAND)

• Active low inputs (S' and R')
• S'=0, R'=0: Invalid state
• S'=0, R'=1: Set (Q=1)
• S'=1, R'=0: Reset (Q=0)
• S'=1, R'=1: Hold

9.3 Gated SR Latch

• SR latch with enable (E) input
• When E=0: Latch holds state regardless of S, R
• When E=1: Operates as normal SR latch
• Level-triggered

9.4 D Latch

• Characteristic equation: Q_next = D (when E=1)
• Eliminates invalid state of SR latch: D connects to S, D' connects to R
• Transparent latch: Output follows input when enabled

9.5 SR Flip-Flop

• Edge-triggered version of SR latch
• Changes state only on clock edge (positive or negative)
• Master-slave configuration eliminates race conditions

9.6 JK Flip-Flop

• Characteristic equation: Q_next = J·Q' + K'·Q
• Eliminates invalid state: J=K=1 causes toggle
• Most versatile flip-flop

9.7 D Flip-Flop

• Characteristic equation: Q_next = D
• Edge-triggered: Changes only on clock edge
• Most common in modern digital systems
• Delay flip-flop: Output follows input after one clock cycle

9.8 T Flip-Flop

• Characteristic equation: Q_next = T⊕Q = T·Q' + T'·Q
• Toggle flip-flop: Complements state when T=1
• Derived from JK flip-flop: Connect J and K together
• Used in counters and frequency dividers

9.9 Flip-Flop Conversions

9.10 Flip-Flop Timing Parameters

9.11 Preset and Clear

• Asynchronous inputs (override clock)
• Preset (PRE): Forces Q=1
• Clear (CLR): Forces Q=0
• Active low in most ICs
• PRE=0, CLR=0: Invalid state (avoid)

10. Registers

10.1 Register Types

10.2 Shift Registers

10.3 Shift Register Applications

• Serial-to-parallel and parallel-to-serial conversion
• Delay line: n-bit register provides n clock cycle delay
• Multiplication/division by 2: Left shift = ×2, right shift = ÷2
• Ring counter: Output of last flip-flop fed back to first
• Johnson counter (twisted ring): Q' of last flip-flop fed back to first. 2n states for n flip-flops
• Linear Feedback Shift Register (LFSR): Feedback through XOR gates. Pseudo-random sequence generation

10.4 Register Transfer Language (RTL)

• R1 ← R2: Transfer contents of R2 to R1
• R1 ← R1 + R2: Add R1 and R2, store in R1
• K: R1 ← R2: Conditional transfer when control signal K=1
• Used to describe data flow in digital systems

11. Counters

11.1 Counter Classifications

11.2 Asynchronous Binary Counter

• n flip-flops → 2ⁿ states (mod-2ⁿ counter)
• Each flip-flop divides frequency by 2
• MSB output frequency = Input frequency / 2ⁿ; each stage divides frequency by 2.
• Propagation delay = n × t_p (limits maximum frequency)
• T flip-flops or JK flip-flops with J=K=1
• LSB toggles every clock pulse. Each higher bit toggles when previous bit goes 1→0

11.3 Synchronous Binary Counter

• All flip-flops receive same clock
• JK or T flip-flops with control logic
• For T flip-flops: T₀=1, T_i = Q₀·Q₁·...·Q_i-1
• Uses AND gates for enable logic
• Faster than asynchronous: propagation delay independent of number of bits

11.4 BCD Counter (Decade Counter)

• Counts from 0000 (0) to 1001 (9), then resets
• Modulo-10 counter
• 4 flip-flops but only 10 states used
• Reset logic: Detect state 1010 (10) and force to 0000
• Cascading: Connect output of one to clock of next for multi-digit counting

11.5 Ring Counter

• n-bit shift register with feedback from output to input
• Requires n flip-flops for n states
• Only one flip-flop is 1 at any time
• Initial state: 1000...0, then circulates: 0100...0, 0010...0, etc.
• Self-starting requires additional logic
• Decoded outputs: Each flip-flop output represents one state

11.6 Johnson Counter

• Shift register with complemented feedback
• n flip-flops → 2n states
• Sequence: 000→100→110→111→011→001→000
• Self-starting with additional logic
• Decoded outputs require 2-input gates

11.7 Counter Design Steps

1. State diagram: Define all states and transitions
2. State table: List present state, next state for all states
3. Flip-flop excitation: Determine flip-flop inputs needed for each transition
4. Input equations: Minimize using K-maps. Derive expressions for J, K, D, or T inputs
5. Logic diagram: Implement using flip-flops and gates

11.8 Flip-Flop Excitation Tables

11.9 Counter with Parallel Load

• Can load external data or count
• Load control signal: Load=1 (load data), Load=0 (count)
• Uses multiplexers or logic gates to select between count and load operations
• Useful for programmable counters and frequency dividers

11.10 Frequency Division

• Mod-N counter divides input frequency by N
• Output frequency = f_in / N
• Non-binary divisions require custom counters with reset logic
• Example: Divide by 5 using 3 flip-flops, reset at state 101

12. Memory Elements

12.1 Memory Classifications

12.2 Memory Organization

• Memory capacity = 2ⁿ × m (n address bits, m data bits)
• Address lines (A): n lines address 2ⁿ locations
• Data lines (D): m lines for m-bit word
• Control signals: Read/Write (R/W̅), Chip Select (CS̅), Output Enable (OE̅)
• Word addressable: Each address refers to one word (typically 8, 16, 32 bits)
• Byte addressable: Each address refers to one byte (8 bits)

12.3 ROM Types

12.4 Memory Expansion

12.4.1 Word Length Expansion

• Connect chips in parallel
• Same address lines to all chips
• Same control signals to all chips
• Data lines combined: Chip1 provides lower bits, Chip2 provides upper bits
• Example: Two 2K×4 → One 2K×8

12.4.2 Word Capacity Expansion

• Connect chips using decoder for chip select
• Higher address bits → decoder → chip select lines
• Lower address bits common to all chips
• Data and control lines multiplexed
• Example: Four 1K×8 → One 4K×8 (2 address bits to 2:4 decoder)

12.5 Memory as Function Generator

• ROM can implement any combinational function
• Address lines = function inputs
• Data lines = function outputs
• Each address stores corresponding output value
• 2ⁿ×m ROM implements n-input, m-output function
• No minimization needed: Direct truth table implementation

13. Finite State Machines (FSM)

13.1 FSM Models

13.2 FSM Design Steps

1. Problem specification and state diagram
2. State table (present state, inputs, next state, outputs)
3. State assignment (binary codes to states)
4. Flip-flop selection and excitation table
5. Derive input equations using K-maps
6. Derive output equations using K-maps
7. Logic diagram implementation

13.3 State Assignment Methods

• Binary: Natural binary counting sequence
• Gray code: Minimize bit changes between adjacent states
• One-hot: One flip-flop per state (only one is 1)
• One-hot requires more flip-flops but simpler logic
• n states require ⌈log₂n⌉ flip-flops (binary/Gray), n flip-flops (one-hot)

13.4 State Reduction

• Minimize number of states without changing input-output behavior
• Two states equivalent if: Same outputs for all inputs, same next states (or equivalent next states) for all inputs
• Partition method: Group states with same output, refine based on next states
• Implication table method: Mark non-equivalent state pairs systematically

13.5 Moore vs Mealy Comparison

14. Programmable Logic Devices

14.1 PLD Types

14.2 Programmable Logic Array (PLA)

• Both AND and OR arrays programmable
• Can implement multiple functions with shared product terms
• Most flexible but most expensive
• n inputs, m outputs, k product terms
• Product terms (AND gates) can be shared among outputs

14.3 Programmable Array Logic (PAL)

• Programmable AND array, fixed OR array
• Each output has dedicated OR gate with fixed number of product terms
• Less flexible than PLA but simpler and faster
• Cannot share product terms between outputs
• Most common in practice

14.4 Complex PLD (CPLD)

• Multiple PAL-like blocks interconnected
• Contains macrocells: Programmable logic + flip-flop
• Non-volatile configuration memory
• Fast, predictable timing
• Typical sizes: 32 to 512 macrocells

14.5 Field Programmable Gate Array (FPGA)

• Array of configurable logic blocks (CLBs)
• Programmable interconnect network
• Look-up table (LUT) based logic implementation
• Contains flip-flops, RAM blocks, DSP blocks
• SRAM-based configuration (volatile, requires boot from external memory)
• Very high density: millions of logic cells
• More flexible than CPLD; modern FPGAs can achieve high clock speeds comparable to CPLDs.

15. Hazards and Timing

15.1 Hazard Types

15.2 Hazard Detection and Elimination

• Static hazards occur in SOP (static-1) or POS (static-0) implementations
• K-map detection: Adjacent 1s not covered by single prime implicant
• Elimination: Add redundant prime implicants to cover all adjacent 1-pairs
• Consensus term eliminates hazard by bridging gap between product terms

15.3 Timing Parameters

15.4 Critical Path and Maximum Frequency

• Critical path: Longest delay path from input to output
• Determines maximum operating frequency
• T_min = t_clk-Q + t_logic + t_setup + t_skew
• f_max = 1/T_min
• Clock skew and jitter reduce maximum frequency

16. Advanced Topics

16.1 Schmitt Trigger

• Exhibits hysteresis: Different thresholds for rising and falling edges
• V_TH+ (upper threshold), V_TH- (lower threshold)
• Eliminates noise and debounces mechanical switches
• Converts slowly varying input to clean digital output

16.2 Tri-State Logic

• Three output states: 0, 1, Hi-Z (high impedance)
• Hi-Z: Output disconnected (neither drives 0 nor 1)
• Enable signal controls output: Enable=0 → Hi-Z, Enable=1 → Normal operation
• Multiple tri-state outputs can share a bus (only one enabled at a time)
• Used in bus systems and memory interfaces

16.3 Race Conditions

• Race-around in JK flip-flop: When J=K=1 and pulse width > propagation delay, output toggles multiple times
• Solution: Master-slave flip-flop or edge-triggering
• Critical race in asynchronous circuits: Multiple state variables change, order affects final state
• Non-critical race: Multiple paths lead to same final state

16.4 Metastability

• Occurs when setup/hold time violated: Flip-flop output stuck between 0 and 1
• Output eventually settles to valid state, but time unpredictable
• Cannot be eliminated, only probability reduced
• Solutions: Synchronizer chains (multiple flip-flops), longer settling time, faster flip-flops
• MTBF = e^(t/τ) / (C · fclk · fdata)
  (τ and C are technology-dependent constants)

16.5 Clock Domain Crossing

• Signals crossing between different clock domains risk metastability
• Synchronizers: Two-flop synchronizer most common (reduces probability)
• FIFO buffers for multi-bit data transfer between clock domains
• Handshaking protocols: Request-acknowledge signaling

16.6 Power Consumption

• Static power: Leakage current when circuit idle. P_static = I_leak·V_DD
• Dynamic power: Charging/discharging capacitances. P_dynamic = α·C·V_DD²·f
• α = switching activity factor (0 to 1)
• Reduction: Lower V_DD, reduce f, minimize C, gate clocks, reduce switching activity