MIT 6.004 - Computation Structures (Digital Logic & CPU Architecture) Flashcards

Question 1

What is Boolean Algebra?

Accepted Answer

A branch of algebra in which the values of the variables are the truth values `true` and `false`, usually denoted 1 and 0 respectively. It is fundamental for designing and analyzing digital circuits.

Question 2

List the three basic Boolean operations and their symbols.

Accepted Answer

1. AND (conjunction): $\cdot$ or no symbol (e.g., $A \cdot B$ or $AB$)
2. OR (disjunction): $+$ (e.g., $A + B$)
3. NOT (negation/complement): $'$ or $\bar{}$ (e.g., $A'$ or $\bar{A}$)

Question 3

Explain the difference between a combinational circuit and a sequential circuit.

Accepted Answer

*   **Combinational Circuit:** Its output depends *only* on the current inputs. It has no memory elements. Examples: Adders, Decoders, Multiplexers.
*   **Sequential Circuit:** Its output depends on both the current inputs *and* the past sequence of inputs (i.e., its current state). It includes memory elements like flip-flops. Examples: Registers, Counters, State Machines.

Question 4

What is a Karnaugh Map (K-map) used for?

Accepted Answer

A graphical method used to simplify Boolean expressions. It provides a systematic way to minimize the number of logic gates and inputs required for a digital circuit by grouping adjacent cells containing '1's (or '0's) in powers of two.

Question 5

Define a "minterm" in Boolean algebra.

Accepted Answer

A product term in which all variables appear exactly once, either in their true or complemented form. For $n$ variables, there are $2^n$ possible minterms. For example, for variables A and B, `A'B` is a minterm.

Question 6

What is a Multiplexer (Mux)?

Accepted Answer

A combinational circuit that selects one of several input data lines and routes it to a single output line. The selection is controlled by a set of select lines. An $N$-to-1 Mux has $N$ data inputs and $\log_2 N$ select lines.

Question 7

Describe the function of an Arithmetic Logic Unit (ALU).

Accepted Answer

A digital circuit within the CPU that performs arithmetic operations (like addition, subtraction, increment, decrement) and logical operations (like AND, OR, NOT, XOR) on integer binary numbers. It is a fundamental building block of the CPU's datapath.

Question 8

What is the primary difference between a latch and a flip-flop?

Accepted Answer

Both are basic memory elements.
*   **Latch:** Level-sensitive. Its output can change whenever its enable input is active.
*   **Flip-flop:** Edge-triggered. Its output changes only at a specific transition (rising or falling edge) of the clock signal. Flip-flops are preferred in synchronous sequential circuits.

Question 9

Explain the concept of a Finite State Machine (FSM).

Accepted Answer

A mathematical model of computation used to design sequential logic circuits. An FSM can be in one of a finite number of states, and its next state and outputs are determined by its current state and current inputs. It's often represented by state diagrams or state tables.

Question 10

Differentiate between Mealy and Moore FSM models.

Accepted Answer

*   **Mealy Machine:** Outputs depend on both the current state *and* the current inputs. Outputs are associated with the transitions between states.
*   **Moore Machine:** Outputs depend *only* on the current state. Outputs are associated with the states themselves.

Question 11

What is the Von Neumann architecture?

Accepted Answer

A computer architecture where program instructions and data are stored in the same memory space. This allows the CPU to fetch both instructions and data from the same memory unit, simplifying memory management but potentially creating a "Von Neumann bottleneck" due to shared access.

Question 12

Contrast RISC (Reduced Instruction Set Computer) and CISC (Complex Instruction Set Computer) architectures.

Accepted Answer

*   **RISC:** Emphasizes a small, highly optimized set of simple instructions, each taking roughly one clock cycle. Requires more instructions for complex tasks but allows for efficient pipelining. (e.g., MIPS, ARM)
*   **CISC:** Features a large, complex set of instructions, some of which perform multiple operations and can take many clock cycles. Aims to reduce the number of instructions per program. (e.g., x86)

Question 13

List the five stages of a classic CPU instruction pipeline.

Accepted Answer

1.  **IF** (Instruction Fetch): Fetch instruction from memory.
2.  **ID** (Instruction Decode): Decode instruction, read registers.
3.  **EX** (Execute): Perform ALU operation or calculate address.
4.  **MEM** (Memory Access): Access data memory (load/store).
5.  **WB** (Write Back): Write result back to a register.

Question 14

What is a data hazard in pipelining, and how can it be mitigated?

Accepted Answer

A data hazard occurs when an instruction tries to read a register before a preceding instruction has written to it.
*   **Mitigation:**
    *   **Forwarding (Bypassing):** Sending the result of an instruction directly from an internal pipeline stage to a subsequent instruction that needs it, without waiting for the write-back stage.
    *   **Stalling (Pipeline Bubble):** Inserting NOP (No Operation) instructions to delay the dependent instruction until the required data is available.

Question 15

Explain the purpose of the Program Counter (PC) in a CPU.

Accepted Answer

The `Program Counter` (PC) is a special-purpose register that holds the memory address of the next instruction to be fetched from memory. After an instruction is fetched, the PC is typically incremented to point to the subsequent instruction.

Question 16

What is the MIPS instruction format for R-type instructions?

Accepted Answer

R-type (Register-type) instructions are used for register-to-register operations.
```
opcode (6 bits) | rs (5 bits) | rt (5 bits) | rd (5 bits) | shamt (5 bits) | funct (6 bits)
```
*   `opcode`: Specifies the operation (0 for most R-type).
*   `rs`, `rt`: Source registers.
*   `rd`: Destination register.
*   `shamt`: Shift amount (for shift instructions).
*   `funct`: Function code, specifies the exact operation when `opcode` is 0.

Question 17

Provide an example of a MIPS `add` instruction and explain its operands.

Accepted Answer

`add $rd, $rs, $rt`
This instruction adds the contents of register `$rs` and register `$rt` and stores the result in register `$rd`.
Example: `add $t0, $s1, $s2` (Adds contents of `$s1` and `$s2`, stores in `$t0`).

Question 18

How does the MIPS `lw` (load word) instruction work?

Accepted Answer

`lw $rt, offset($base)`
This instruction loads a 32-bit word from memory into register `$rt`. The memory address is calculated by adding the `offset` (a signed 16-bit immediate value) to the contents of the `$base` register.
Example: `lw $t0, 8($sp)` (Loads word from address `$sp + 8` into `$t0`).

Question 19

What is the role of the `beq` (branch if equal) instruction in MIPS?

Accepted Answer

`beq $rs, $rt, Label`
This instruction is used for conditional branching. If the contents of register `$rs` are equal to the contents of register `$rt`, the program branches to the instruction at `Label`. Otherwise, execution continues with the next instruction in sequence.

Question 20

Describe the concept of a "control unit" in a CPU.

Accepted Answer

The `Control Unit` is a component of the CPU that directs the operation of the processor. It interprets instructions and generates control signals to coordinate the flow of data within the CPU's datapath, ensuring that the correct operations are performed at the correct time.

Question 21

What is the primary function of a register file in a CPU?

Accepted Answer

A `register file` is a small, fast storage unit within the CPU that consists of a set of general-purpose registers. It provides quick access to frequently used data and intermediate results, acting as the primary interface between the ALU and memory.

Question 22

How does a CPU execute a software instruction like `add $t0, $s1, $s2` at a high level?

Accepted Answer

1.  **Fetch:** The `Control Unit` uses the `Program Counter` to fetch the `add` instruction from memory.
2.  **Decode:** The `Control Unit` decodes the instruction, identifying it as an `add` operation and determining the source (`$s1`, `$s2`) and destination (`$t0`) registers.
3.  **Execute:** The `Control Unit` signals the `Register File` to read the values from `$s1` and `$s2`. These values are sent to the `ALU`, which performs the addition.
4.  **Write Back:** The `ALU`'s result is then written back to the `Register File` into register `$t0`, as directed by the `Control Unit`.

MIT 6.004 - Computation Structures (Digital Logic & CPU Architecture)

Cards in this deck

Related Flashcard Sets

Korean TOPIK I - Essential Vocabulary & Grammar (Levels 1-2)

TypeScript - Advanced Types, Interfaces & Generics

Organic Chemistry Mechanisms - SN1/SN2 & E1/E2 Reactions

Cisco CCNA (200-301) - Enterprise Networking & IP Services