ddca_recap

Introduction

• How we handle complexity
• Why we use abstraction and how it helps us
• How Hierarchy层次结构, Modularity模块, and Regularity规律 are related, and how they help us handle complexity
• That we have a lecture book available online

The Art of Managing Complexity

• Abstraction

  

Discipline约束

• The Three -Y’s

  • Hierarchy

    A system is divided into modules of smaller complexity

  • Modularity

    Having well defined functions and interfaces

  • Regularity

    Encouraging uniformity, so modules can be easily re-used

Binary Numbers

• How to convert between binary, decimal, and hexadecimal numbers

• Be able to work with numbers that are in powers of 2

• Be able to interpret numbers as unsigned, sign-magnitude, one’s, or two’s complement

• Compare the ranges these interpretations can represent

• Q

  If the hexadecimal number (82)_16 is expressing a number in sign-magnitude format, which number does it describe in decimal system?

Unsigned binary numbers

are as easy as pie. Assuming n bits, all n bits are used to represent binary numbers from 0 to $2^n − 1$, where the most significant bit represents $2^n−1$

Signed-Bit Magnitude

$123_10 = 1111011$

0 +, 1-

123 = 0 1111011

-123 = 1 1111011

wasteful

breaks arithmetic. −3 + 3 = 0 but get -6

Two’s Complement

5 = 0101

reverse 1010+1

-5 =1011

Range

Electrical Engineering Perspective

• What a transistor is, its basic function for digital functions, basic materials and components of it

• That they can be combined to realize basic logic functions

• What pMOS, nMOS, and CMOS stand for and what their roles are for realizing the functions

• Basic logic gates: AND, OR, XOR, NAND, NOR, XNOR, inverter and their truth tables

• Q

  True or false, “pMOS transistors are used in CMOS gates to drive the output of a logic gate to logic low”

Transistor

晶体管

nMOS + pMOS = CMOS

Transistor Basics

Transistor: A transistor is a semiconductor device used to amplify or switch electronic signals and electrical power. It consists of three layers of semiconductor material, each capable of carrying a current. The main function of a transistor in digital circuits is to act as a switch, turning on and off to control the flow of electrical current.

Basic Function: In digital circuits, transistors are used to create logic gates, which are the building blocks of digital circuits. They can be combined to realize basic logic functions such as AND, OR, and NOT gates.

Materials and Components:

• Basic Materials: Silicon, Germanium, Gallium Arsenide
• Components: Source, Drain, Gate (in MOSFETs)

Types of Transistors and Their Roles

pMOS, nMOS, CMOS:

• pMOS (P-type Metal-Oxide-Semiconductor): Transistors that use p-type carriers (holes). They are turned on by applying a low voltage to the gate.
• nMOS (N-type Metal-Oxide-Semiconductor): Transistors that use n-type carriers (electrons). They are turned on by applying a high voltage to the gate.
• CMOS (Complementary Metal-Oxide-Semiconductor): A technology for constructing integrated circuits using both pMOS and nMOS transistors. CMOS technology is used for constructing digital logic circuits and is known for its low power consumption.

Basic Logic Gates and Their Truth Tables

1. AND Gate:

   • Function: Output is true if both inputs are true.

   • Truth Table:

     A	B	Output
     0	0	0
     0	1	0
     1	0	0
     1	1	1

2. OR Gate:

   • Function: Output is true if at least one input is true.

   • Truth Table:

     A	B	Output
     0	0	0
     0	1	1
     1	0	1
     1	1	1

3. XOR Gate:

   • Function: Output is true if inputs are different.

   • Truth Table:

     A	B	Output
     0	0	0
     0	1	1
     1	0	1
     1	1	0

4. NAND Gate:

   • Function: Output is false if both inputs are true.

   • Truth Table:

     A	B	Output
     0	0	1
     0	1	1
     1	0	1
     1	1	0

5. NOR Gate:

   • Function: Output is true if both inputs are false.

   • Truth Table:

     A	B	Output
     0	0	1
     0	1	0
     1	0	0
     1	1	0

6. XNOR Gate:

   • Function: Output is true if inputs are the same.

   • Truth Table:

     A	B	Output
     0	0	1
     0	1	0
     1	0	0
     1	1	1

7. Inverter (NOT Gate):

   • Function: Output is the opposite of the input.

   • Truth Table:

     A	Output
     0	1
     1	0

True or False Statement

Statement: “pMOS transistors are used in CMOS gates to drive the output of a logic gate to logic low.”

Answer: False. Explanation: In CMOS technology, nMOS transistors are typically used to pull the output to logic low (0), while pMOS transistors are used to pull the output to logic high (1). The combination of nMOS and pMOS transistors ensures low power consumption and high noise immunity in digital circuits.

---

• c

  晶体管基础

  晶体管： 晶体管是一种用于放大或开关电子信号和电力的半导体器件。它由三层半导体材料组成，每层都可以承载电流。在数字电路中，晶体管的主要功能是充当开关，通过控制电流的流动来打开和关闭电路。

  基本功能： 在数字电路中，晶体管用于创建逻辑门，逻辑门是数字电路的基本构建块。它们可以组合起来实现基本的逻辑功能，例如与门、或门和非门。

  材料和组件：

  • 基本材料： 硅、锗、砷化镓
  • 组件： 源极、漏极、栅极（在MOSFET中）

  晶体管类型及其作用

  pMOS、nMOS、CMOS：

  • pMOS（P型金属氧化物半导体）： 使用P型载流子（空穴）的晶体管。通过对栅极施加低电压来打开它们。
  • nMOS（N型金属氧化物半导体）： 使用N型载流子（电子）的晶体管。通过对栅极施加高电压来打开它们。
  • CMOS（互补金属氧化物半导体）： 使用pMOS和nMOS晶体管构建集成电路的技术。CMOS技术用于构建数字逻辑电路，以其低功耗而著称。

  基本逻辑门及其真值表

  1. 与门（AND Gate）：

     • 功能： 只有当两个输入都为真时，输出才为真。

     • 真值表：

       A	B	输出
       0	0	0
       0	1	0
       1	0	0
       1	1	1

  2. 或门（OR Gate）：

     • 功能： 只要有一个输入为真，输出就为真。

     • 真值表：

       A	B	输出
       0	0	0
       0	1	1
       1	0	1
       1	1	1

  3. 异或门（XOR Gate）：

     • 功能： 当输入不同，输出为真。

     • 真值表：

       A	B	输出
       0	0	0
       0	1	1
       1	0	1
       1	1	0

  4. 与非门（NAND Gate）：

     • 功能： 只有当两个输入都为真时，输出才为假。

     • 真值表：

       A	B	输出
       0	0	1
       0	1	1
       1	0	1
       1	1	0

  5. 或非门（NOR Gate）：

     • 功能： 只有当两个输入都为假时，输出才为真。

     • 真值表：

       A	B	输出
       0	0	1
       0	1	0
       1	0	0
       1	1	0

  6. 同或门（XNOR Gate）：

     • 功能： 当输入相同时，输出为真。

     • 真值表：

       A	B	输出
       0	0	1
       0	1	0
       1	0	0

       | 1 | 1 | 1 |

  7. 反相器（NOT Gate）：

     • 功能： 输出是输入的相反。

     • 真值表：

       A	输出
       0	1
       1	0

  真或假声明

  声明： “在CMOS门中，pMOS晶体管用于将逻辑门的输出驱动到逻辑低。”

  回答： 错误。 解释： 在CMOS技术中，nMOS晶体管通常用于将输出拉低到逻辑低（0），而pMOS晶体管用于将输出拉高到逻辑高（1）。nMOS和pMOS晶体管的组合确保了数字电路中的低功耗和高抗噪性【6†source】【7†source】。

Combinational Circuits: Theory

• Boolean Algebra, Axioms, Theorems

• How gates map to basic Boolean operations AND/OR/Negate

• Rules of combinational circuits

• Simplifying Boolean logic equations

• Q

  Which one of the following circuits is NOT a combinational circuit, why

De Morgan’s Theorems:

• $\overline{A \cdot B} = \overline{A} + \overline{B}$
• $\overline{A + B} = \overline{A} \cdot \overline{B}$

Boolean Algebra, Axioms, and Theorems

Boolean Algebra: Boolean algebra is a branch of algebra that deals with variables that have two distinct values: true (1) and false (0). It is fundamental to the operation of digital circuits and logic gates.

Axioms: Axioms are the basic assumptions in Boolean algebra from which theorems can be derived. Some key axioms include:

1. Identity Law: $A + 0 = A$ and $A \cdot 1 = A$
2. Null Law: $A + 1 = 1$ and $A \cdot 0 = 0$
3. Idempotent Law: $A + A = A$ and $A \cdot A = A$
4. Complement Law: $A + \overline{A} = 1$ and $A \cdot \overline{A} = 0$

Theorems: Theorems are derived from the axioms of Boolean algebra. Some important theorems include:

1. De Morgan’s Theorems:
   • $\overline{A \cdot B} = \overline{A} + \overline{B}$
   • $\overline{A + B} = \overline{A} \cdot \overline{B}$
2. Distributive Law:
   • $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
   • $A + (B \cdot C) = (A + B) \cdot (A + C)$

Mapping Gates to Basic Boolean Operations

AND Gate:

• Boolean Operation: $A \cdot B$
• Symbol: $\cdot$

OR Gate:

• Boolean Operation: A + B
• Symbol: +

NOT Gate (Inverter):

• Boolean Operation: $\overline{A}$
• Symbol: \overline{}

Rules of Combinational Circuits

1. Outputs determined by current values of inputs: The output of a combinational circuit is determined solely by the current inputs.
2. Memoryless: Combinational circuits do not have any memory elements; they do not store past inputs.

Unique Output for Each Input Combination: Each unique combination of inputs produces a unique output.

Sequential Logic

1. Has memory
2. Outputs determined by previous and current values of inputs

Simplifying Boolean Logic Equations

Using Boolean Algebra:

1. Combine like terms using the distributive law.
2. Eliminate redundant terms using the idempotent and complement laws.
3. Apply De Morgan’s theorems to simplify expressions involving negations.

Example: Simplify the expression $A \cdot \overline{A} + A \cdot B :$ $A \cdot \overline{A} + A \cdot B = 0 + A \cdot B = A \cdot B$

Non-Combinational Circuits

A circuit that is NOT a combinational circuit is a sequential circuit. This is because sequential circuits have memory elements and their output depends not only on the current inputs but also on the past inputs.

Example of a Sequential Circuit:

• Flip-Flop: A flip-flop is a basic memory element that can store one bit of data. Its output depends on the current input and the previously stored value.

Reason Why Sequential Circuits are Not Combinational:

• Sequential circuits have feedback loops or memory elements, meaning they can store information about past inputs, making their output dependent on both current and past inputs. This violates the rule that a combinational circuit’s output is determined solely by the current inputs.

• c

  布尔代数、公理和定理

  布尔代数： 布尔代数是处理只有两个不同值的变量（真（1）和假（0））的代数分支。它是数字电路和逻辑门操作的基础。

  公理： 公理是布尔代数中的基本假设，从中可以推导出定理。一些关键公理包括：

  1. 恒等律： ( A + 0 = A ) 和 ( A \cdot 1 = A )
  2. 零律： ( A + 1 = 1 ) 和 ( A \cdot 0 = 0 )
  3. 幂等律： ( A + A = A ) 和 ( A \cdot A = A )
  4. 互补律： ( A + \overline{A} = 1 ) 和 ( A \cdot \overline{A} = 0 )

  定理： 定理是从布尔代数的公理推导出来的。一些重要的定理包括：

  1. 德摩根定理：
     • ( \overline{A \cdot B} = \overline{A} + \overline{B} )
     • ( \overline{A + B} = \overline{A} \cdot \overline{B} )
  2. 分配律：
     • ( A \cdot (B + C) = (A \cdot B) + (A \cdot C) )
     • ( A + (B \cdot C) = (A + B) \cdot (A + C) )

  映射门到基本布尔运算

  与门（AND Gate）：

  • 布尔运算： ( A \cdot B )
  • 符号： ( \cdot )

  或门（OR Gate）：

  • 布尔运算： ( A + B )
  • 符号： ( + )

  非门（NOT Gate，反相器）：

  • 布尔运算： ( \overline{A} )
  • 符号： ( \overline{} )

  组合电路的规则

  1. 确定性输出： 组合电路的输出完全由当前输入决定。
  2. 无记忆： 组合电路没有任何记忆元件；它们不存储过去的输入。
  3. 每个输入组合的唯一输出： 每个唯一的输入组合产生唯一的输出。

  简化布尔逻辑方程

  使用布尔代数：

  1. 使用分配律结合类似项。
  2. 使用幂等律和互补律消除冗余项。
  3. 应用德摩根定理简化涉及否定的表达式。

  示例： 简化表达式 ( A \cdot \overline{A} + A \cdot B )： [ A \cdot \overline{A} + A \cdot B = 0 + A \cdot B = A \cdot B ]

  非组合电路

  不属于组合电路的是 顺序电路。这是因为顺序电路具有记忆元件，它们的输出不仅取决于当前输入，还取决于过去的输入。

  顺序电路示例：

  • 触发器（Flip-Flop）： 触发器是一种基本的记忆元件，可以存储一位数据。它的输出取决于当前输入和之前存储的值。

  顺序电路不是组合电路的原因：

  • 顺序电路具有反馈回路或记忆元件，这意味着它们可以存储有关过去输入的信息，使其输出依赖于当前和过去的输入。这违反了组合电路输出完全由当前输入决定的规则。

Combinational Circuits: Design

• SOP and POS formulations, definitions

• How to read/construct truth tables, shortcuts with don’t cares

• Karnaugh maps, how to simplify Boolean Logic

• Contamination and propagation delay

• Q

  Implement the Boolean logic equation Z=ABC+!A!B+!C!B using ONLY two input AND/OR gates and inverters. On the circuit you have drawn show the critical path, the shortest path by using the delay values for these gates. Simplify this logic function, how much ere you abel to reduce the critical path

SOP and POS Formulations, Definitions

Sum of Products (SOP):

• Definition: SOP is a canonical form of expressing Boolean functions. It is a form where the function is written as a sum (OR) of products (AND) of literals.
• Example: For a given truth table, the SOP expression is obtained by OR-ing all the minterms (product terms) that produce an output of 1.
• Formulation: If the output is TRUE for rows (0,1), (1,0), and (1,1), the SOP form would be: $Y = F(A,B)=\overline{A}\cdot B + A\cdot B$

Product of Sums (POS):

• Definition: POS is another canonical form of expressing Boolean functions. It is a form where the function is written as a product (AND) of sums (OR) of literals.
• Example: For a given truth table, the POS expression is obtained by AND-ing all the maxterms (sum terms) that produce an output of 0.
• Formulation: If the output is FALSE for rows (0,0), (0,1), and (1,0), the POS form would be: [ f(X, Y) = (X + Y)(X + \overline{Y})(\overline{X} + Y) ]

Reading/Constructing Truth Tables, Shortcuts with Don’t Cares

Truth Tables:

• Reading: A truth table lists all possible input combinations to a Boolean function and the corresponding output for each combination.
• Construction: To construct a truth table, list all binary combinations of inputs and determine the output for each combination.

Don’t Cares (X):

• Definition: In certain cases, some input combinations may never occur or the output for some input combinations is irrelevant. These are marked as “don’t cares” (X).
• Shortcut: In a Karnaugh map, don’t cares can be used to simplify the Boolean function by grouping them with either 1s or 0s to create larger groups, thereby minimizing the logic expression【7:3†source】【7:6†source】.

Karnaugh Maps and Simplifying Boolean Logic

Karnaugh Maps (K-Maps):

• Definition: K-Maps are a visual method of simplifying Boolean expressions by organizing truth table values into a grid where adjacent cells differ by only one variable.
• Simplification: Group adjacent 1s (or 0s) into the largest possible power-of-two groups to simplify the Boolean expression【7:6†source】【7:16†source】.

Contamination and Propagation Delay

Propagation Delay (t_pd): max delay from input to output

• Definition: The maximum time it takes for a signal to propagate through a circuit from input to output.
• Importance: Determines the maximum speed at which a circuit can operate.

Contamination Delay (t_cd): min delay from input to output

• Definition: The minimum time it takes for an initial change at the input to start affecting the output.
• Importance: Ensures stability and correct operation by defining the minimum delay before an output starts to change【7:1†source】【7:5†source】.

Delay is caused by § Capacitance and resistance in a circuit § Speed of light limitation (not as fast as you think!) Reasons why tpd and tcd may be different: § Different rising and falling delays § Multiple inputs and outputs, some of which are faster than others § Circuits slow down when hot and speed up when cold

Implementing Boolean Logic Equation with Two-input Gates and Inverters

Given Equation: ( Z = ABC + \overline{A}\overline{B} + \overline{C}\overline{B} )

Steps:

1. Break Down the Equation: [ Z = ABC + \overline{A}\overline{B} + \overline{C}\overline{B} ]
2. Simplify Using Boolean Algebra: [ Z = (A \cdot B \cdot C) + (\overline{A} \cdot \overline{B}) + (\overline{C} \cdot \overline{B}) ] Combine terms involving (\overline{B}): [ Z = ABC + \overline{B}(\overline{A} + \overline{C}) ]
3. Implement Using Two-input AND/OR Gates and Inverters:
   • Use AND gates for (A \cdot B \cdot C) and (\overline{A} \cdot \overline{B}), (\overline{C} \cdot \overline{B}).
   • Use OR gates to combine the outputs.
4. Draw the Circuit:
   • Draw the AND gates for (A \cdot B \cdot C), (\overline{A} \cdot \overline{B}), and (\overline{C} \cdot \overline{B}).
   • Connect the outputs of the first two AND gates to an OR gate.
   • Connect the result and the third AND gate to another OR gate to get Z.
5. Identify Critical and Shortest Paths:
   • Critical Path: The path with the longest delay.
   • Shortest Path: The path with the shortest delay.

Simplified Circuit:

• Critical Path: Analyze the delays through AND and OR gates to identify the longest path and the overall propagation delay.
• Reduction: Use Boolean algebra and K-Map simplification to reduce the number of gates and the depth of the logic circuit, thus reducing the critical path delay【7:4†source】【7:19†source】.

---

SOP 和 POS 公式及定义

积之和（SOP）:

• 定义：SOP 是表达布尔函数的一种规范形式，它以文字的积（与运算）的和（或运算）的形式写出函数。
• 示例：对于给定的真值表，SOP 表达式是通过或运算所有产生输出为 1 的最小项（积项）获得的。
• 公式：如果输出在（0,1）、（1,0）和（1,1）行是 TRUE，则 SOP 形式为：

$Y = F(A,B)=\overline{A}\cdot B + A\cdot B$

和之积（POS）:

• 定义：POS 是表达布尔函数的另一种规范形式，它以文字的和（或运算）的积（与运算）的形式写出函数。
• 示例：对于给定的真值表，POS 表达式是通过与运算所有产生输出为 0 的极大项（和项）获得的。
• 公式：如果输出在（0,0）、（0,1）和（1,0）行是 FALSE，则 POS 形式为： [ f(X, Y) = (X + Y)(X + \overline{Y})(\overline{X} + Y) ]

读取/构建真值表，使用不关心项的快捷方式

真值表：

• 读取：真值表列出了布尔函数的所有可能输入组合及每种组合的相应输出。
• 构建：要构建真值表，列出输入的所有二进制组合，并确定每种组合的输出。

不关心项（X）：

• 定义：在某些情况下，某些输入组合可能永远不会出现，或者某些输入组合的输出无关紧要。这些项用“不关心”（X）标记。
• 快捷方式：在卡诺图中，不关心项可以用来简化布尔函数，通过将它们与 1 或 0 分组以创建更大的组，从而最小化逻辑表达式【7:3†source】【7:6†source】。

卡诺图和简化布尔逻辑

卡诺图（K-Maps）：

• 定义：卡诺图是一种通过将真值表值组织成相邻单元格仅有一个变量不同的网格来简化布尔表达式的可视化方法。
• 简化：将相邻的 1（或 0）分组成尽可能大的 2 的幂组，以简化布尔表达式【7:6†source】【7:16†source】。

污染延迟和传播延迟

传播延迟（tpd）：

• 定义：从输入信号变化到输出达到最终值的最大时间。
• 重要性：确定电路运行的最大速度。

污染延迟（tcd）：

• 定义：从输入信号变化到任何输出开始改变其值的最小时间。
• 重要性：通过定义输出开始改变之前的最小延迟来确保稳定性和正确操作【7:1†source】【7:5†source】。

使用双输入与/或门和反相器实现布尔逻辑方程

给定方程： ( Z = ABC + \overline{A}\overline{B} + \overline{C}\overline{B} )

步骤：

1. 分解方程： [ Z = ABC + \overline{A}\overline{B} + \over

line{C}\overline{B} ]

1. 使用布尔代数简化： [ Z = (A \cdot B \cdot C) + (\overline{A} \cdot \overline{B}) + (\overline{C} \cdot \overline{B}) ] 结合涉及 (\overline{B}) 的项： [ Z = ABC + \overline{B}(\overline{A} + \overline{C}) ]
2. 使用双输入与/或门和反相器实现：
   • 使用与门实现 (A \cdot B \cdot C) 和 (\overline{A} \cdot \overline{B})、(\overline{C} \cdot \overline{B})。
   • 使用或门组合输出。
3. 绘制电路图：
   • 为 (A \cdot B \cdot C)、(\overline{A} \cdot \overline{B}) 和 (\overline{C} \cdot \overline{B}) 绘制与门。
   • 将前两个与门的输出连接到或门。
   • 将结果和第三个与门连接到另一个或门以获得 Z。
4. 识别关键路径和最短路径：
   • 关键路径：最长延迟的路径。
   • 最短路径：最短延迟的路径。

简化电路：

• 关键路径：通过分析与门和或门的延迟识别最长路径和总体传播延迟。
• 减少：使用布尔代数和卡诺图简化减少门的数量和逻辑电路的深度，从而减少关键路径延迟【7:4†source】【7:19†source】。

Verilog for Combinational Circuits

• How to write a Verilog module, instantiate modules

• Implement basic functions

• Make assignments between busses of different sizes and types

• Be able to read/understand and write Verilog code for combinational circuits

• Draw a circuit diagram from a Verilog code or vice-versa

• Q

  Which one of the following Verilog statements have an ERROR, explain the issue, and correct the line

To address your queries about Verilog for combinational circuits, here’s a detailed guide based on the provided documents:

1. Writing a Verilog Module and Instantiating Modules

To write a Verilog module, you need to define the module with its inputs and outputs, describe the logic, and then end the module. Here’s a basic example:

module and_gate (
    input wire a, b,
    output wire y
);
    assign y = a & b;
endmodule

To instantiate this module within another module:

module top_module (
    input wire a, b,
    output wire y
);
    and_gate my_and_gate (
        .a(a),
        .b(b),
        .y(y)
    );
endmodule

2. Implementing Basic Functions

Basic combinational logic functions such as AND, OR, NOT, etc., can be implemented using assign statements:

module basic_gates (
    input wire a, b,
    output wire and_out, or_out, not_out
);
    assign and_out = a & b;
    assign or_out = a | b;
    assign not_out = ~a;
endmodule

3. Making Assignments Between Busses of Different Sizes and Types

When assigning between buses of different sizes, you must be cautious about the bit-width mismatches. Here’s an example:

module bus_assignment (
    input wire [3:0] small_bus,
    output wire [7:0] large_bus
);
    assign large_bus = {4'b0000, small_bus}; // Zero-padding small bus to fit the large bus
endmodule

4. Reading/Understanding and Writing Verilog Code for Combinational Circuits

Reading and understanding Verilog requires familiarity with syntax and constructs such as module, assign, and various operators. Writing involves clearly defining the module’s interface and describing the logic using continuous assignments or always blocks for sequential logic.

5. Drawing a Circuit Diagram from Verilog Code or Vice-Versa

Drawing circuit diagrams from Verilog code involves identifying the components (gates, multiplexers, etc.) and their connections as described in the code. For example, from the basic_gates module above, you would draw AND, OR, and NOT gates with inputs a, b and corresponding outputs.

6. Identifying Errors in Verilog Statements

Consider the following Verilog statements, which one has an error:

assign y = a && b;   // Statement 1
assign x = a || b;   // Statement 2
assign z = a & b;    // Statement 3

Explanation:

• Statement 1 (assign y = a && b;): This is incorrect because && is a logical operator, not a bitwise operator. In Verilog, && is used in conditions within always blocks or procedural statements, not for bitwise assignments. The correct operator should be &.
• Corrected Line: assign y = a & b;

Summary in Chinese

为了回答关于组合电路的Verilog问题，这里是基于提供的文档的详细指南：

1. 编写一个Verilog模块并实例化模块

编写一个Verilog模块需要定义该模块的输入和输出，描述逻辑，然后结束模块。以下是一个基本示例：

module and_gate (
    input wire a, b,
    output wire y
);
    assign y = a & b;
endmodule

在另一个模块中实例化此模块：

module top_module (
    input wire a, b,
    output wire y
);
    and_gate my_and_gate (
        .a(a),
        .b(b),
        .y(y)
    );
endmodule

2. 实现基本功能

使用assign语句实现基本的组合逻辑功能如AND，OR，NOT等：

module basic_gates (
    input wire a, b,
    output wire and_out, or_out, not_out
);
    assign and_out = a & b;
    assign or_out = a | b;
    assign not_out = ~a;
endmodule

3. 在不同大小和类型的总线之间进行赋值

在不同大小的总线之间进行赋值时，必须注意位宽的不匹配。以下是一个示例：

module bus_assignment (
    input wire [3:0] small_bus,
    output wire [7:0] large_bus
);
    assign large_bus = {4'b0000, small_bus}; // 用零填充small_bus以适应large_bus
endmodule

4. 读取/理解和编写组合电路的Verilog代码

阅读和理解Verilog需要熟悉语法和结构如module，assign以及各种运算符。编写时需要清晰地定义模块的接口并使用连续赋值或always块描述逻辑。

5. 从Verilog代码绘制电路图或反之亦然

从Verilog代码绘制电路图需要识别代码中描述的组件（如门电路，多路复用器等）及其连接。例如，从上述basic_gates模块，你需要绘制AND，OR和NOT门，其输入为a，b，对应的输出为and_out，or_out，not_out。

6. 识别Verilog语句中的错误

考虑以下Verilog语句，哪一个有错误：

assign y = a && b;   // 语句 1
assign x = a || b;   // 语句 2
assign z = a & b;    // 语句 3

解释:

• 语句 1 (assign y = a && b;): 这是不正确的，因为&&是逻辑运算符，而不是按位运算符。在Verilog中，&&用于always块或过程语句中的条件，而不是用于按位赋值。正确的运算符应为&。
• 正确的行: assign y = a & b;

这样可以更好地理解如何使用Verilog编写组合电路代码以及识别代码中的错误。

Combinational Circuits in Processors

• Basic building blocks of adders, half-adders, full-adders

• Ripple carry adder, how it works, the issue with carry propagation

• Carry-save and carry propagate adders

• Multipliers and other circuits built from adders

• Shifters and other circuits

• ALU and how it operates

• Q

  Calculate the propagation/contamination delay of a 16-bit Ripple Carry Adder, what is the maximum operating frequency of a processor that uses this adder in its critical path

Basic Building Blocks: Adders, Half-Adders, Full-Adders

• Half-Adder: Adds two single-bit binary numbers (A and B). It has two outputs: Sum (S) and Carry (C).

  module half_adder (
      input wire A, B,
      output wire Sum, Carry
  );
      assign Sum = A ^ B;   // XOR for sum
      assign Carry = A & B; // AND for carry
  endmodule

• Full-Adder: Adds three single-bit binary numbers (A, B, and Carry-in). It has two outputs: Sum and Carry-out.

  module full_adder (
      input wire A, B, Cin,
      output wire Sum, Cout
  );
      assign Sum = A ^ B ^ Cin;        // XOR for sum
      assign Cout = (A & B) | (Cin & (A ^ B)); // Carry logic
  endmodule

Ripple Carry Adder

• A Ripple Carry Adder (RCA) is constructed by connecting multiple full adders in series. The carry-out from each full adder is connected to the carry-in of the next higher-order full adder.
• Issue with Carry Propagation: The main issue with RCAs is the delay caused by the carry propagation. The carry has to ripple through all the full adders, which results in a linear delay based on the number of bits.

Carry-Save and Carry Propagate Adders

• Carry-Save Adder (CSA): Used in multi-operand addition. Instead of propagating carries immediately, it saves them and adds them in a subsequent stage.
• Carry Propagate Adder (CPA): Similar to RCA but includes optimization techniques like carry-lookahead to reduce delay.

Multipliers and Other Circuits Built from Adders

• Multipliers use a combination of adders to perform multiplication. For example, a basic binary multiplier uses adders to sum partial products.
• Shifters (like barrel shifters) can also be built using combinational logic to perform bit shifting operations efficiently.

Arithmetic Logic Unit (ALU)

• An ALU performs arithmetic and logical operations. It can include adders, subtractors, shifters, and logic gates to perform operations like addition, subtraction, bitwise AND, OR, XOR, and shifts.

Calculating Propagation/Contamination Delay and Maximum Operating Frequency

To calculate the propagation delay of a 16-bit Ripple Carry Adder:

1. Propagation Delay of a Full-Adder:
   • Assume the propagation delay for the Sum ((t_{sum})) is (t_{XOR}).
   • Assume the propagation delay for the Carry-out ((t_{carry})) is (t_{AND/OR}).
2. Ripple Carry Adder Propagation Delay:
   • The delay for each bit’s carry to propagate through the entire adder is approximately (16 \times t_{carry}).
3. Contamination Delay:
   • The contamination delay for the Sum ((t_{cont_sum})) and Carry ((t_{cont_carry})) can be similarly considered.

Example Calculation:

• Suppose (t_{XOR} = 1 , ns) and (t_{AND/OR} = 2 , ns).
• Total propagation delay for the 16-bit RCA: [ t_{prop_RCA} = 16 \times t_{AND/OR} = 16 \times 2 , ns = 32 , ns ]

Maximum Operating Frequency

The maximum operating frequency is the reciprocal of the total propagation delay: [ f_{max} = \frac{1}{t_{prop_RCA}} = \frac{1}{32 , ns} \approx 31.25 , MHz ]

Summary in Chinese

基本构建模块：加法器，半加法器，全加法器

• 半加法器: 加两个单比特二进制数（A 和 B）。它有两个输出：和（Sum）和进位（Carry）。

  module half_adder (
      input wire A, B,
      output wire Sum, Carry
  );
      assign Sum = A ^ B;   // 异或运算得到和
      assign Carry = A & B; // 与运算得到进位
  endmodule

• 全加法器: 加三个单比特二进制数（A、B 和进位输入）。它有两个输出：和和进位输出。

  module full_adder (
      input wire A, B, Cin,
      output wire Sum, Cout
  );
      assign Sum = A ^ B ^ Cin;        // 异或运算得到和
      assign Cout = (A & B) | (Cin & (A ^ B)); // 进位逻辑
  endmodule

串行进位加法器

• 串行进位加法器（RCA） 是通过将多个全加法器串联连接构成的。每个全加法器的进位输出连接到下一个高位全加法器的进位输入。
• 进位传播问题: RCA 的主要问题是进位传播引起的延迟。进位必须通过所有的全加法器传播，这导致了基于位数的线性延迟。

进位保存和进位传播加法器

• 进位保存加法器（CSA）: 用于多操作数加法。它不会立即传播进位，而是保存它们并在后续阶段进行加法。
• 进位传播加法器（CPA）: 类似于 RCA，但包括如进位预测等优化技术以减少延迟。

由加法器构建的乘法器和其他电路

• 乘法器使用加法器组合来执行乘法。例如，一个基本的二进制乘法器使用加法器来求和部分积。
• 移位器（如桶形移位器）也可以使用组合逻辑来高效执行位移操作。

算术逻辑单元（ALU）

• ALU 执行算术和逻辑操作。它可以包括加法器、减法器、移位器和逻辑门以执行如加法、减法、按位与、或、异或和移位操作。

计算16位串行进位加法器的传播/污染延迟和处理器的最大工作频率

计算 16 位串行进位加法器的传播延迟：

1. 全加法器的传播延迟:
   • 假设和的传播延迟（(t_{sum})）为 (t_{XOR})。
   • 假设进位输出的传播延迟（(t_{carry})）为 (t_{AND/OR})。
2. 串行进位加法器的传播延迟:
   • 每个位的进位通过整个加法器传播的延迟大约为 (16 \times t_{carry})。
3. 污染延迟:
   • 和的污染延迟（(t_{cont_sum})）和进位（(t_{cont_carry})）可以类似地考虑。

示例计算:

• 假设 (t_{XOR} = 1 , ns) 和 (t_{AND/OR} = 2 , ns)。
• 16 位 RCA 的总传播延迟: [ t_{prop_RCA} = 16 \times t_{AND/OR} = 16 \times 2 , ns = 32 , ns ]

最大工作频率

最大工作频率是总传播延迟的倒数: [ f_{max} = \frac{1}{t_{prop_RCA}} = \frac{1}{32 , ns} \approx 31.25 , MHz ]

这样就可以计算出16位串行进位加法器的传播/污染延迟以及使用该加法器的处理器的最大工作频率。

Sequential Logic Design

• Mealy and Moore (Guaranteed question)

• Basic state holding elements, latches, FFs, how they work

• Finite State Machines, how they are constructed

• Design, simplify, optimize, understand FSMs

• Q

  Design the FSM that implements “….” derive the logic equations for next state calculation, minimize them

Verilog for Sequential Circuits

• always statements in Verilog. How they are used

• How to define/read/understand FSMs, FFs, latches in Verilog

• If a Verilog description is a combinational or sequential circuit

• Basic logic gates: AND, OR, XOR, NAND, NOR, XNOR, inverter and their truth tables

• Q

  Which of the following Verilog descriptions will result in a combinational circuit, and which ones will be a sequential circuit

Sequential Circuits: Timing

• Setup and hold time calculations (with and without skew)

• You need to be up to date on propagation and contamination delays as well

• Q

  Given a circuit diagram (or Verilog code) calculate if the circuit has a setup or hold violation, if there is a violation explain how it can be fixed.

Need for Verification

• Why functional verification is difficult

• How are faults detected (control, activate, propagate, observe)

• What is a testbench

• The need for golden models

• Q

  If you can test 1’000’000’000 input combinations per second, how long would it take you to exhaustively test a 32bit adder.

Using Verilog for Testbenches

• initial statements in Verilog. How/why they are used

• Defining time in testbenches. #20

• Identify/understand parts of a testbench written in Verilog

• Helper functions $display, $readmemb

• The advantages of file-based testbenches

• Q

  Take a look at the following Verilog testbench. Explain what each section does. Two of the sections has a mistake in the code, identify these, and write the corrected version

Number Systems

• Difference between, integer, fixed-floating point numbers

• Be able to express simple fractional numbers in fixed-point format

• Explain the idea behind floating point encoding (sign, mantissa, exponent)

• Understand different rounding modes

• The need for special cases (for example NaN)

• Q

  What is the difference between round-down and round-to-nearest, give an example where the rounding would result in different numbers.

MIPS Assembly

• Essentially MIPS assembly, operands, memory addressing, registers

• Different types of instructions (R, I, J)

• Be able to interpret instructions, know what the basic instructions we covered in slides in class do (lw, sw, add, addi, bne, j, jal, and, xor..)

• Q

  Explain what the instruction lw $t0, 24 ($s1) will do. Where is the data coming from and where will it be written to after this instruction.

Memories

• The array structure of memories

• Types of memories SRAM, DRAM, Register files

• How larger memories can be constructed out of individual memory blocks

• Q

  You have an SRAM block that has 8 address bits and can store 32 bits at a time. How many bytes can be stored in this memory. For your 32 bit MIPS processor you need a 4 kByte memory, show a block diagram how this can be constructed using this memory block, connect the address bits and add necessary components.

MIPS Programming

• How to write/read assembly programs for MIPS

• Understand how function calls are made

• How stack works and how registers are copied

• How memory is organized (text, code, data segments)

• Given the appendix of your textbook, be able to understand all MIPS instructions

• Q

  What is the difference between round-down and rount-to-nearest, give an example where the rounding would result in different numbers.

Microarchitecture (Single Cycle)

• How instructions are executed, and components of the processor

• Calculate the performance of the processor and compare two processors with different parameters

• How instructions are decoded and control signals for the processor are generated

• Be able to interpret block diagrams of processors, find/add missing pieces

• Q

  What is the difference between round-down and rount-to-nearest, give an example where the rounding would result in different numbers.

Pipelined MIPS Architecture

• Pipelining basics, relationship between throughput and latency

• Issues of pipelining, data/control hazards, mitigation mechanisms

• Performance of pipelined processors

• Q

  We have a single cycle processor that works at 1GHz. The idea is to have a 10-stage pipeline pipelining to improve performance. What is the theoretical max frequency? We use pipeline registers with a 20ps setup time, 0ps hold time and a 30 ps propagation/contamination delay. If everything else needed for pipelining can be done without ill effects, what is the max frequency we can achieve. What other effects do you expect would reduce this theoretical performance, name three different aspects, describe one of them.