Chapter 9 Arithmetic(5)

这一章是很难的，不过我打的就是精锐。😎

Contents of this lecture

English	中文
Manual Multiplication Algorithm	手动乘法算法
Array Multiplication	阵列乘法
Sequential Multiplication	顺序乘法

已知：

$
$
$
$
$
$
$
$

将所有部分积相加：
$ 1101 +11010 +00000 +1101000
= 10001111 ()
$

此算法直观且直接适用于手工计算，但在硬件实现中效率较低。

阵列乘法是一种基于硬件的并行乘法实现方法，将手动乘法算法转化为硬件逻辑电路，使用全加器（FA）和与门（AND gates）实现部分积的生成与累加。

输入：
- 被乘数 $ M = m_3 m_2 m_1 m_0 $
- 乘数 $ Q = q_3 q_2 q_1 q_0 $
- 结果积 $ P = p_7 p_6 p_5 p_4 p_3 p_2 p_1 p_0 $
生成部分积：
每一位 $ q_i $ 的值与被乘数 $ M $ 的每一位 $ m_j $ 相乘，生成部分积 $ PP_i $：$ PP_0 = m_3q_0, m_2q_0, m_1q_0, m_0q_0
$ $ PP_1 = m_3q_1, m_2q_1, m_1q_1, m_0q_1
$ $ PP_2, PP_3
$
累加部分积：
使用全加器（FA）对各部分积进行按位累加，考虑进位信号，最终得到完整的积：
$ PP_4 = P = p_7p_6p_5p_4p_3p_2p_1p_0
$

组成结构：
- 与门（AND gates）：生成部分积 $ m_j q_i $。
- 全加器（FA）：用于累加部分积并处理进位。
电路工作流程：
- 输入：被乘数 $ M $、乘数 $ Q $。
- 输出：最终积 $ P $。
- 逻辑结构：
  - 每个位的 $ q_i $ 和 $ m_j $ 通过与门生成部分积。
  - 使用全加器对部分积进行逐位累加，形成最终结果。

问题：在 $ n n $ 阵列乘法器中，计算 $ P = M Q $ （$ M, Q $ 均为 $ n $-位无符号二进制数）时需要多少全加器（FA）和与门（AND gates）？

解答：

$ n = 32 $：
- 全加器数量：
  $ FAs = 32 = 992 $
- 与门数量：
  $ AND gates = 32^2 = 1024 $
$ n = 64 $：
- 全加器数量：
  $ FAs = 64 = 4032 $
- 与门数量：
  $ AND gates = 64^2 = 4096 $

考试是很大概率靠这道题目的，一定要掌握。

输入与初始化：
- 被乘数（Multiplicand）：$ M $
- 乘数（Multiplier）：$ Q $
- 寄存器 C 和 A：初始值为 0
- 计数器 Count：初始值为 $ n $
核心硬件组成：
- $ n $-位加法器（Adder）
- 多路选择器（MUX）控制加法操作
- 移位寄存器实现部分积的移位操作
- 顺序控制器（Sequencer）管理各步骤
操作流程：
- 根据 $ Q_0 $ 判断是否加上 $ M $
- 每次将部分积（C, A, Q）右移
- 计数器 $ Count $ 减 1，重复操作直到计数器为 0。

起始条件：
- $ C, A = 0 $，$ Q $ 为乘数，$ M $ 为被乘数。
- $ Count = n $
循环步骤：
- 检查 $ Q_0 $：
  - 如果 $ Q_0 = 1 $，则执行 $ A = A + M $。
  - 如果 $ Q_0 = 0 $，跳过加法。
- 将 $ C, A, Q $ 整体右移一位。
- 计数器 $ Count - 1 $。
结束条件：
- 当 $ Count = 0 $ 时停止，寄存器中 $ C, A, Q $ 的值即为结果 $ P $。