Computer Architecture and Digital Logic Vocabulary

Combinational Logic Circuits and Programmable Logic Devices

• Decoders:

  • Definition: A decoder is a combinational circuit that converts binary information from $n$ input lines to a maximum of $2^n$ unique output lines.

  • Structure: An $n$-input to $2^n$-output decoder expands an $n$-bit binary code into up to $2^n$ minterms.

  • 3-to-8 Decoder Example:

  • Inputs: $3$ lines ($A, B, C$ or $I_2, I_1, I_0$).

  • Outputs: $8$ lines ($D_0$ through $D_7$).

  • Operation: For each input combination, exactly one output line is set to $1$ (active high), corresponding to a unique minterm ($m_0$ to $m_7$).

  • Truth table mappings for active outputs:

    • $000 \rightarrow D_0$

    • $001 \rightarrow D_1$

    • $010 \rightarrow D_2$

    • $011 \rightarrow D_3$

    • $100 \rightarrow D_4$

    • $101 \rightarrow D_5$

    • $110 \rightarrow D_6$

    • $111 \rightarrow D_7$

  • Applications:

  • Binary-to-octal decoding

  • Code conversion

  • Memory address decoding

  • Seven-segment display driving

  • Generation of Boolean minterms for combinational functions

• Encoders:

  • Definition: An encoder performs the exact inverse operation of a decoder. It accepts one active input line among many and converts it into an $n$-bit output binary code.

  • 8-to-3 Encoder Example:

  • Inputs: $8$ lines ($D_0$ to $D_7$).

  • Outputs: $3$ lines ($x, y, z$).

  • Operation: Assumes only one input line is active at any given time. If input $D_5 = 1$, the output generates the binary value $101_2$.

• Priority Encoders:

  • Definition: A priority encoder resolves the limitation of standard encoders where multiple inputs may be asserted simultaneously. It guarantees that if two or more inputs are active concurrently, the input with the highest priority is selected.

  • Operation Rules:

  • Highest-numbered input line is typically assigned the highest priority.

  • An additional valid output flag ($V$) indicates whether at least one input line is active ($V = 1$) or no inputs are active ($V = 0$).

  • Boolean Equations for Priority Encoder Outputs:

  • Output $x = D_2 + D_3$

  • Output $y = D_3 + D_1 D_2'$

  • Valid output flag $V = D_0 + D_1 + D_2 + D_3$

• Multiplexers (MUX):

  • Definition: A multiplexer (or data selector) is a combinational circuit that receives binary information from $2^n$ input data lines and directs one selected input line to a single output line based on $n$ selection variables.

  • 4-to-1 Multiplexer:

  • Data inputs: $I_0, I_1, I_2, I_3$

  • Selection lines: $S_1, S_0$

  • Output: $Y$     

    

  • Boolean Logic Expression:       $Y = I_0 S_1' S_0' + I_1 S_1' S_0 + I_2 S_1 S_0' + I_3 S_1 S_0$

  • MUX as a Universal Function Generator:

  • Any Boolean function of $n$ variables can be implemented using a multiplexer with $n-1$ selection lines.

  • Boolean variables are assigned to the selection inputs, while data inputs are connected to $0$, $1$, a remaining variable, or its complement.

  • Applications of Multiplexers:

  • Data selection and routing

  • Communication channels and time-division multiplexing

  • Parallel-to-serial data conversion

  • Arbitrary Boolean function implementation

  • Processor bus and data path selection

• Read-Only Memory (ROM):

  • Definition: ROM is a non-volatile semiconductor memory device pre-programmed with permanent binary data. Information remains stored indefinitely even when power is removed.

  • ROM Architecture:

  • Inputs: $n$ address input lines.

  • Outputs: $m$ data output lines.

  • Size: Specified as $2^n \times m$, containing $2^n$ addressable words of $m$ bits each.

  • Internal Components: A decoder of size $n \times 2^n$ generating all $2^n$ minterms, connected to $m$ OR gates forming a programmable output array.

  • Combinational Function Implementation:

  • Since an $n \times 2^n$ decoder generates all minterms of $n$ input variables, connecting selected decoder outputs to OR gates realizes any set of $m$ Boolean functions.

  • Example: Implementing $F(A, B, C) = \Sigma(1, 3, 5, 6)$.

    • Use $A, B, C$ as 3 address lines ($n = 3 \rightarrow 2^3 = 8$ addresses).

    • Program the ROM memory array to output $F = 1$ at memory addresses $1, 3, 5, 6$ ($001_2, 011_2, 101_2, 110_2$) and $F = 0$ at all other addresses.

• Summary Formulas for Digital Logic Design:

  • Full Adder Sum equation: $S_i = A_i \oplus B_i \oplus C_i$

  • Carry Propagation equation: $C_{i+1} = G_i + P_i C_i$

  • Carry Generate: $G_i = A_i B_i$

  • Carry Propagate: $P_i = A_i \oplus B_i$

  • 2's Complement Subtraction: $A - B = A + \overline{B} + 1$

  • BCD Addition Correction factor: add binary $0110_2$ ($6$) when sum exceeds $9$ or generates a output carry.

  • Comparator Bit Equality: $x_i = A_i B_i + A_i' B_i'$

  • Decoder Outputs count: $2^n$

  • MUX Inputs count: $2^n$

  • ROM Addresses count: $2^n$

Basic Computer Organization and Design

• Instruction Codes:

  • Definition: An instruction code is a group of bits that instructs the computer to perform a specific operation, data transfer, or control action. Program instructions and data reside in common memory storage.

  • Execution Process: The CPU fetches an instruction from memory into the Instruction Register (IR), where the control unit decodes the operation code and issues the microoperations required for execution.

  • Instruction Code Fields:

  • Opcode (Operation Code): Group of bits defining the specific arithmetic, logical, or control operation (e.g., ADD, SUB, LOAD, STORE, AND, OR).

  • Address Field: Bits specifying the memory location or CPU register containing the operand.

  • Mode Bit ($I$): Direct/Indirect addressing mode bit.

  • Basic Computer 16-Bit Instruction Format:     

    

  • Bit $15$ ($1$ bit): Indirect address bit ($I$).

    • $I = 0$: Direct address (address field points directly to operand).

    • $I = 1$: Indirect address (address field points to a memory location holding the effective address of the operand).

  • Bits $12\text{--}14$ ($3$ bits): Opcode field (supports $2^3 = 8$ operations).

  • Bits $0\text{--}11$ ($12$ bits): Address field (addresses up to $2^{12} = 4096$ memory words).

  • Total bit length: $1 + 3 + 12 = 16\text{ bits}$.

  • Instruction Categories:

  • Memory-Reference Instructions ($Opcode = 000$ through $110$).

  • Register-Reference Instructions ($Opcode = 111$ with $I = 0$).

  • Input-Output Instructions ($Opcode = 111$ with $I = 1$).

• Computer Registers:

  • AR (Address Register): $12$\text{ bits}. Holds memory address for read/write operations.

  • PC (Program Counter): $12$\text{ bits}. Holds address of the next instruction to fetch from memory; automatically incremented after instruction fetch.

  • DR (Data Register): $16$\text{ bits}. Holds data read from or written to memory.

  • AC (Accumulator): $16$\text{ bits}. General-purpose processor register used for performing arithmetic and logical operations and storing intermediate results.

  • IR (Instruction Register): $16$\text{ bits}. Holds opcode and operand address of the current instruction during decoding and execution.

  • TR (Temporary Register): $16$\text{ bits}. Stores temporary internal data during complex execution cycles.

  • INPR (Input Register): $8$\text{ bits}. Holds an 8-bit input character transferred from an input device.

  • OUTR (Output Register): $8$\text{ bits}. Holds an 8-bit output character transferred to an output device.

  • SC (Sequence Counter): Controls execution timing by generating sequence timing signals ($T_0, T_1, T_2, \dots$).

• Computer Instruction Set Architecture:

  • Memory-Reference Instructions:

  • AND: $AC \leftarrow AC \land M[AR]$ (Bitwise Logical AND)

  • ADD: $AC \leftarrow AC + M[AR]$ (Binary Addition with Carry)

  • LDA: $AC \leftarrow M[AR]$ (Load Memory Word to Accumulator)

  • STA: $M[AR] \leftarrow AC$ (Store Accumulator to Memory)

  • BUN: $PC \leftarrow AR$ (Branch Unconditionally)

  • BSA: $M[AR] \leftarrow PC, PC \leftarrow AR + 1$ (Branch and Save Return Address)

  • ISZ: $M[AR] \leftarrow M[AR] + 1$; if $M[AR] = 0$ then $PC \leftarrow PC + 1$ (Increment and Skip if Zero)

  • Register-Reference Instructions (Executed when $I=0$ and $Opcode=111$):

  • CLA: $AC \leftarrow 0$ (Clear Accumulator)

  • CLE: $E \leftarrow 0$ (Clear Extended Bit E)

  • CMA: $AC \leftarrow \overline{AC}$ (Complement Accumulator / 1's Complement)

  • CME: $E \leftarrow \overline{E}$ (Complement Extended Bit E)

  • CIR: Circulate right $AC$ and $E$

  • CIL: Circulate left $AC$ and $E$

  • INC: $AC \leftarrow AC + 1$ (Increment Accumulator)

  • SPA: Skip next instruction if $AC > 0$

  • SNA: Skip next instruction if $AC < 0$

  • SZA: Skip next instruction if $AC = 0$

  • SZE: Skip next instruction if $E = 0$

  • HLT: $S \leftarrow 0$ (Halt Computer Processing)

  • Input-Output Instructions (Executed when $I=1$ and $Opcode=111$):

  • INP: $AC(0\text{--}7) \leftarrow INPR, FGI \leftarrow 0$ (Input Character)

  • OUT: $OUTR \leftarrow AC(0\text{--}7), FGO \leftarrow 0$ (Output Character)

  • SKI: Skip if Input Flag $FGI = 1$

  • SKO: Skip if Output Flag $FGO = 1$

  • ION: $IEN \leftarrow 1$ (Interrupt Enable On)

  • IOF: $IEN \leftarrow 0$ (Interrupt Enable Off / Disable)

• Input-Output Organization and Interrupts:

  • I/O Communication: Peripherals operate independently and asynchronously from CPU speeds. Communication requires I/O interface logic, temporary buffering registers (INPR, OUTR), and status flags (FGI, FGO).

  • Input Operation Sequence:

  1. External device places character data in INPR.

  2. Input flag $FGI$ is set to $1$

  3. CPU checks $FGI$ flag.

  4. CPU transfers character from INPR into $AC(0\text{--}7)$.

  5. Input flag $FGI$ is cleared to $0$

  • Output Operation Sequence:

  1. CPU transfers output character from $AC(0\text{--}7)$ into OUTR.

  2. Output flag $FGO$ is set to $0$

  3. External device receives character from OUTR.

  4. Output flag $FGO$ is set back to $1$ when device is ready for new data.

  • Interrupt Mechanisms:

  • Purpose: Eliminates programmed I/O status flag polling by allowing peripherals to signal the CPU only when service is needed, enabling continuous CPU instruction execution.

  • Interrupt Cycle Steps:

    1. CPU completes current instruction execution cycle.

    2. CPU inspects interrupt request line condition.

    3. If interrupt flag is enabled ($IEN = 1$) and flag is active ($FGI = 1$ or $FGO = 1$), interrupt sequence triggers.

    4. Current program context and Program Counter return address are saved (stored at memory location $0$).

    5. CPU branches to Interrupt Service Routine (ISR) by loading $PC \leftarrow 1$

    6. Interrupt Service Routine executes to process device request.

    7. CPU executes indirect branch to return to original program execution point.

Central Processing Unit Architecture

• CPU Structure:

  • Major Components:

  • Register Set: Stores operands, intermediate results, addresses, and status information.

  • Arithmetic Logic Unit (ALU): Performs execution of arithmetic, logic, and shift operations.

  • Control Unit: Decodes instructions, manages internal control pathways, and issues timing sequence signals.

  • Common CPU Organizations:

  • Single Accumulator Organization

  • General Register Organization

  • Stack-Based Organization

• General Register Organization:

  • Architecture: Registers are connected through internal buses multiplexed into the inputs of an ALU. Operations select two source registers, pass them through ALU logic, and route results back to a target register.

  • Operation Walkthrough ($R_1 \leftarrow R_2 + R_3$):

  1. Control logic selects register $R_2$ via Bus A multiplexer (MUX A).

  2. Control logic selects register $R_3$ via Bus B multiplexer (MUX B).

  3. Arithmetic Logic Unit performs ADD operation on inputs A and B.

  4. Destination decoder selects register $R_1$

  5. Calculated sum is loaded into register $R_1$

  • Control Word Format:     

    

  • SELA Field: $3$\text{ bits} (selects Bus A source register).

  • SELB Field: $3$\text{ bits} (selects Bus B source register).

  • SELD Field: $3$\text{ bits} (selects destination register).

  • OPR Field: $5$\text{ bits} (selects specific ALU operation).

  • Total Control Word Length: $3 + 3 + 3 + 5 = 14\text{ bits}$.

• Stack Organization:

  • Definition: A stack is a Last-In, First-Out (LIFO) memory structure where data elements are added and removed from a single top location.

  • Stack Pointer (SP): A register holding the memory or register address of the current top element of the stack.

  • Fundamental Operations:

  • PUSH: Inserts an item onto the stack.

    • Register Stack PUSH Microoperations:         $SP \leftarrow SP + 1$         $M[SP] \leftarrow DR$

  • POP: Removes an item from top of stack.

    • Register Stack POP Microoperations:         $DR \leftarrow M[SP]$         $SP \leftarrow SP - 1$

  • Stack Types:

  • Register Stack: Implemented using a dedicated set of internal CPU registers with fixed maximum capacity.

  • Memory Stack: Allocated as a dedicated region inside main memory; variable capacity controlled by Stack Pointer.

  • Reverse Polish Notation (RPN / Postfix):

  • Eliminates requirement for evaluation parentheses in algebraic expressions.

  • Infix: $(A + B) \times (C + D)$

  • Postfix / RPN: $A B + C D + \times$

  • Stack CPU execution: Operands are pushed onto stack sequentially; arithmetic operations pop top operands, compute result, and push output back to stack top.

• Instruction Formats:

  • Fields: Opcode field, Address field(s), and Addressing Mode field.

  • Three-Address Instructions:

  • Format: ADD R1, R2, R3

  • Operation: $R_1 \leftarrow R_2 + R_3$

  • Characteristic: Short program length, requiring more bits per instruction.

  • Two-Address Instructions:

  • Format: ADD R1, R2

  • Operation: $R_1 \leftarrow R_1 + R_2$

  • Characteristic: One register serves as both source operand and destination location.

  • One-Address Instructions:

  • Format: LOAD A, ADD B

  • Operation: $AC \leftarrow M[A]$, then $AC \leftarrow AC + M[B]$

  • Characteristic: Implicating a single Accumulator (AC) register for all arithmetic/logic operations.

  • Zero-Address Instructions:

  • Format: PUSH A, PUSH B, ADD

  • Operation: Operands implicitly popped from and pushed onto top of stack.

Memory Hierarchy and Organization

• Memory Hierarchy:

  • Rationale: Memory systems balance physical trade-offs where higher speed leads to increased cost per bit and smaller capacities, whereas low-cost, high-capacity memory suffers from slower access rates.

  • Levels of Hierarchy (Fastest/Smallest to Slowest/Largest):

  1. CPU Registers: Located inside the CPU core; sub-nanosecond access time; extremely limited capacity.

  2. Cache Memory: High-speed SRAM located close to CPU; holds active instructions and data to minimize CPU delay.

  3. Main Memory (RAM): Semiconductor memory communicating directly with CPU via system memory buses.

  4. Auxiliary Memory: Secondary non-volatile magnetic or optical storage devices (e.g., HDDs, SSDs, magnetic tapes) providing mass storage.

  • Principle of Locality of Reference:

  • Temporal Locality: Programs tend to execute recently accessed data or instruction memory locations repeatedly in short time spans.

  • Spatial Locality: Programs tend to access memory locations physically adjacent to recently referenced addresses.

• Main Memory:

  • Definition: Primary memory unit directly addressed by the CPU during instruction execution cycles.

  • Random Access Memory (RAM):

  • Operates read and write functions.

  • Volatile storage (loses stored content when system power turns off).

  • SRAM (Static RAM): Constructed using internal flip-flop latches; does not require refresh cycles; provides higher speed; higher cost and lower density; used in Cache memory.

  • DRAM (Dynamic RAM): Stores bits as electrical charges inside MOS capacitors; requires periodic refresh; high storage density; lower cost per bit; used for main memory.

  • Read-Only Memory (ROM):

  • Non-volatile (retains stored data when system power turns off).

  • Primarily read operations; used for pre-stored system software, firmware bootstrap loaders, and static tables.

  • RAM vs. ROM Comparison:     

    

  • Memory Capacity Calculation:

  • An $n$-bit address bus yields $2^n$ addressable memory locations.

  • Example: An address bus with $12$ address lines produces:       $2^{12} = 4096\text{ addressable memory locations}$