1. Sequential Logic Circuits, Memory Elements, and Finite State Machines

Combinational versus Sequential Logic Circuits

• Combinational Logic Circuits Overview:

  • Logic circuits that possess no memory capacity.

  • The output at any given instant is strictly a mathematical function of the current input applied at that exact point in time ($\text{Output} = f(\text{Input}_{current})$).

  • As the input changes, the output immediately changes to reflect the new input.

  • Standard examples include adders, multiplexers, and decoders.

• Sequential Logic Circuits Overview:

  • Logic circuits that incorporate memory elements, acting as an extension of combinational logic.

  • Consist of combinational logic combined with memory storage elements.

  • The output at any point in time depends on both the current input and the past history of inputs and outputs.

  • Encapsulation of History: The past history of the circuit is encapsulated into a discrete representation known as the state.

• State Storage and Dual-Function Inputs:

  • The current state of a sequential logic circuit is continuously stored in memory.

  • When a sequential circuit receives an input signal, the input serves two distinct functions simultaneously:

  1. Computes an output as a function of the current input and the current stored state.

  2. Triggers a state transition to update the memory to the next state ($\text{State}_{t+1}$).

  • Writing new values into memory alters the state of the circuit, updating its recorded history for subsequent clock cycles.

Classification and Timing Assumptions of Sequential Circuits

• Synchronous Sequential Circuits:

  • The primary and most common class of sequential logic circuits.

  • State changes are strictly synchronized with respect to a central system clock signal.

  • State transitions occur exclusively during specific clock events: either on the rising edge ($0 \rightarrow 1$ transition) or on the falling edge ($1 \rightarrow 0$ transition) of the clock pulse.

• Asynchronous Sequential Circuits:

  • Sequential circuits that operate without a central internal timing clock.

  • State transitions occur dynamically in direct response to external events acting as triggers.

  • Real-World Elevator Example:

  • An elevator system operates asynchronously.

  • It remains in a stationary state on a given floor until an external trigger occurs (e.g., a person pressing a call button).

  • The external button press triggers an immediate state transition, causing the elevator to travel from its current story to the floor from which it was called.

• Timing Assumptions for State Transitions:

  • Instantaneous Transition Assumption: In theoretical analysis and basic design models, state transitions are assumed to occur instantaneously upon encountering a clock edge.

  • Physical Transition Constraints: Real-world hardware transitions require a finite duration of time. The instantaneous transition model is a simplifying assumption valid when the transition time is much smaller than the overall clock cycle period.

  • Impact of High-Speed Clocks: As processor clock cycle times decrease in modern systems, the state transition time becomes significant relative to the clock cycle time and must be explicitly analyzed to avoid timing failures.

The SR Flip-Flop as a Basic Memory Element

• Structural Configuration:

  • The Set-Reset (SR) flip-flop serves as the basic building block for sequential logic and solid-state memory.

  • Constructed using two cross-coupled NOR gates.

  • Cross-Coupling Logic: The output of the first NOR gate is fed directly as an input into the second NOR gate, and the output of the second NOR gate is fed back as an input into the first NOR gate.

• Operation and Truth Table Dynamics:

  • Let $Q_c$ (or $Q_t$) denote the current state, and $Q_n$ (or $Q_{t+1}$) denote the next state. Inputs are Set ($S$) and Reset ($R$).

  • No-Change Condition ($S = 0, R = 0$):

  • When both $S$ and $R$ are $0$, the circuit maintains its current state indefinitely ($Q_{t+1} = Q_t$).

  • If $Q_c = 0$, then $Q_n = 0$. If $Q_c = 1$, then $Q_n = 1$.

  • The flip-flop persists in its current state as long as external power is applied across the logic gates.

  • Reset Condition ($S = 0, R = 1$):

  • Forces the flip-flop state to binary $0$ ($Q_{t+1} = 0, \overline{Q}_{t+1} = 1$) regardless of the prior current state.

  • Corresponds to writing a binary $0$ into memory.

  • Set Condition ($S = 1, R = 0$):

  • Forces the flip-flop state to binary $1$ ($Q_{t+1} = 1, \overline{Q}_{t+1} = 0$) regardless of the prior current state.

  • Corresponds to writing a binary $1$ into memory.

  • Illegal / Invalid Condition ($S = 1, R = 1$):

  • Setting both $S = 1$ and $R = 1$ simultaneously is an invalid or forbidden input state, as it produces inconsistent output states violating the fundamental complementary relationship between $Q$ and $\overline{Q}$.

• 1-Bit Solid-State Storage Functionality:

  • The SR flip-flop operates as a single-bit memory cell.

  • Writing data: Assert $S = 1, R = 0$ to write a $1$; assert $S = 0, R = 1$ to write a $0$.

  • Retaining data: Return inputs to $S = 0, R = 0$. Stored data remains persistent as long as power is maintained.

• Historical Development of Solid-State Memory:

  • Prior to solid-state logic, digital memory relied on magnetic storage devices where physical magnetic polarities (North/South) stored binary bits.

  • William Shockley and researchers at Dell Labs developed the first solid-state semiconductor memory devices in the early 1960s (specifically around $1960$–$1962$), earning a Nobel Prize.

  • Modern computer systems built upon this fundamental SR flip-flop architecture to construct high-density RAM and integrated silicon memory.

Clocked SR Flip-Flops and Master-Slave Architecture

• Clocked SR Flip-Flop Circuitry:

  • Modifies the basic cross-coupled NOR flip-flop by placing two-input AND gates at the $S$ and $R$ input terminals, with one input of each AND gate connected to a central clock signal ($CLK$).

  • The clock signal acts as an explicit enable/disable control line for the memory cell.

  • When $CLK = 1$: The AND gates propagate the external $S$ and $R$ input signals to the internal NOR flip-flop, allowing state updates.

  • When $CLK = 0$: The outputs of both input AND gates are forced to $0$, isolating the cross-coupled NOR flip-flop and preventing any change in state regardless of changes on external $S$ and $R$ lines.

• Race Conditions in Sequential Logic:

  • A race condition occurs when an output signal passes through feedback loops and combinational logic to trigger multiple unintended state transitions within a single clock cycle.

  • Correct operation of sequential circuits requires strictly one state transition per clock cycle.

• Master-Slave Flip-Flop Architecture:

  • Designed explicitly to prevent race conditions and enforce a single state change per clock cycle.

  • Structural Configuration: Cascades two flip-flops in series—a Master flip-flop followed by a Slave flip-flop.

  • Clock Control Scheme: The Master flip-flop is gated by the direct clock signal ($CLK$), while the Slave flip-flop is gated by the inverted clock signal ($\overline{CLK}$).

  • Execution Cycle:

  1. On the rising edge of the clock ($CLK = 1$), the Master flip-flop becomes active and accepts inputs to change state, while the Slave flip-flop is disabled ($\overline{CLK} = 0$).

  2. On the falling edge of the clock ($CLK = 0$), the Master flip-flop disables, holding its state constant. Simultaneously, the inverted clock signal ($\overline{CLK} = 1$) enables the Slave flip-flop, passing the Master's state to the output Q$.\n - Result: State updates are completely isolated across clock phases, ensuring that the circuit state persists continuously over an entire clock cycle period.\n\n\n# The D Flip-Flop and Latch Architectures\n\n- **Structural Derivation from SR Flip-Flop**:\n - The D (Data or Delay) flip-flop is created by connecting a single primary input line D$directly to the Set ($S$) input and its inverted value$\overline{D}$(or$D'$) to the Reset ($R) input.\n - Because R$is always the logical complement of$S$, the illegal condition ($S = 1, R = 1) is structurally eliminated.\n\n- **Clocked D Latch Mechanics**:\n - Consists of a data line D$and an enable clock line$CLK.\n - When CLK = 1$: The latch is transparent; the value present on input$D directly determines the state written into the cell.\n - When CLK = 0$: The latch is locked/disabled; it retains its previously written bit value regardless of subsequent signal fluctuations on line$D$.

• Truth Table and Characteristic Equation:

  • If $D = 0$ when enabled: Next state $Q_{t+1} = 0$, regardless of current state Q_t$.\n - If D = 1$when enabled: Next state$Q_{t+1} = 1$, regardless of current state$Q_t$.

  • Characteristic Equation: $Q_{t+1} = D_t$

• Primary Role in Hardware Memory:

  • The D flip-flop serves as the standard single-bit storage cell and foundational building block across modern digital hardware, registers, and computer logic.

• Master-Slave D Flip-Flop Mechanics:

  • Built by connecting two D latches in series with complementary clocking inputs ($CLK$ and $\overline{CLK}$).

  • The Master accepts input $D$ on the clock rising edge. The Slave updates the output state on the clock falling edge.

  • Guarantees that the output state of the flip-flop remains fully stable and persistent across one complete clock cycle.

Formalism and Structure of Synchronous Finite State Machines (FSM)

• Mathematical Formalism:

  • A synchronous Finite State Machine (FSM) is modeled using state variables, inputs, outputs, and logical transformation functions evaluated at discrete integer clock steps $t \in \{1, 2, 3, \dots\}$.

  • Discrete Time $t$: Measures discrete clock cycles (e.g., cycle 21, 22, 23) corresponding to clock edges rather than continuous physical time.

  • State Variables: $n$ binary state variables $S_0^t, S_1^t, \dots, S_{n-1}^t$ representing the current state at time step t$.\n - **Inputs**: m$binary input lines$x_0^t, x_1^t, \dots, x_{m-1}^t$at time step$t$.

  • Outputs: $k$ binary output lines $y_0^t, y_1^t, \dots, y_{k-1}^t$ at time step t$.\n\n- **Output Functions**:\n - Each binary output variable y_i^t$is determined by a Boolean output function$f_i evaluated on current state variables and inputs:\n    y_i^t = f_i(S_0^t, S_1^t, \dots, S_{n-1}^t, x_0^t, x_1^t, \dots, x_{m-1}^t)\n\n- **Next-State Functions (State Transition Functions)**:\n - The future value of each state variable S_i^{t+1}$for the next clock cycle is determined by a next-state logic function$h_i:\n    S_i^{t+1} = h_i(S_0^t, S_1^t, \dots, S_{n-1}^t, x_0^t, x_1^t, \dots, x_{m-1}^t)\n\n- **State Capacity and Variable Rules**:\n - An FSM configured with n$binary state variables can represent up to$2^n distinct unique states.\n - Given N$desired distinct states, the required number of state variables$n is the smallest integer satisfying:\n    2^n \ge N\n - **Calculation Examples**:\n - For N = 4$states ($A, B, C, D$): Requires$n = 2$state variables ($2^2 = 4$distinct variable combinations:$00, 01, 10, 11).\n - For N = 6$states: Requires$n = 3$state variables, because$2^2 = 4 < 6 \le 2^3 = 8.\n\n\n# Design Example: 1011 Sequence Detector Finite State Machine\n\n- **Functional Requirement**:\n - Design a synchronous finite state machine sequence detector to identify the binary sequence 1011 within a continuous input bit stream.\n - Rule: Overlapping instances of the sequence must be detected (e.g., in input sequence 1011011, two target sequences are identified).\n\n- **State Diagram and Transition Logic**:\n - **State A$**: Reset/Initial state (no bits of matching sequence accumulated). Output$y = 0$.

  • Input $x = 0$: Remain in State $A$ ($y = 0$).

  • Input $x = 1$: Transition to State $B$ ($y = 0$) [First matching bit '1' detected].

  • State $B$: Accumulated sequence prefix '1'. Output y = 0$.\n - Input x = 1$: Remain in State$B$($y = 0) [Retains '1' prefix].\n - Input x = 0$: Transition to State$C$($y = 0) [Accumulated '10'].\n - **State C$**: Accumulated sequence prefix '10'. Output$y = 0$.

  • Input $x = 0$: Transition to State $A$ ($y = 0$) [Sequence '100' breaks match; reset].

  • Input $x = 1$: Transition to State $D$ ($y = 0$) [Accumulated '101'].

  • State $D$: Accumulated sequence prefix '101'. Output y = 0$.\n - Input x = 0$: Transition to State$C$($y = 0) [Sequence '1010' received; '10' suffix can serve as prefix for next sequence].\n - Input x = 1$: Sequence$1011$fully matched! Assert output$y = 1$. Transition to State$B$($y = 1) to capture potential overlapping sequence starts.\n\n- **Boolean State Assignment**:\n - Total state count N = 4$($A, B, C, D$) requires$n = 2$binary state variables ($S_1, S_0).\n - Unique state variable mapping:\n - State A \rightarrow S_1 S_0 = 00\n - State B \rightarrow S_1 S_0 = 01\n - State C \rightarrow S_1 S_0 = 10\n - State D \rightarrow S_1 S_0 = 11\n - State assignment choices are arbitrary as long as every individual state is uniquely identified by binary variable values.\n\n\n# Classroom Logistics and Discussion\n\n- **Questions & Discussion on State Variable Calculations**:\n - Student Query / Calculation: How many state variables are needed for 4 distinct states?\n - Answer: 2 state variables (2^2 = 4).\n - Student Query / Calculation: How many state variables are needed if a machine has 6 distinct states?\n - Answer: 3 state variables (2^3 = 8$$ covers 6 states).

• Examination Schedule:

  • Test Number 1 is scheduled for two weeks from today (Thursday, the 24th).

  • A detailed announcement containing responsible study materials and scope will be published on ELC.

• Roll Call Verification:

  • Attendance check conducted at conclusion for students including John and Luis.