算法或代数表达式可以通过信号流图（Signal Flow Graph，简称 SFG）进行可视化表示。在本章中，我们将：

• 演示信号流图的外观。
• 详细定义信号流图及其组成部分。
• 为斐波那契数列构建一个信号流图。

信号流图长什么样？

假设有一个算法，它接受两个变量（例如 $a$ 和 $b$）作为输入，并输出它们的和（记为 $y$）：

这里，$y$ 是表示 $a$ 和 $b$ 之和的变量。

示例：

操作 $y=a+b$ 可以用以下方式直观地表示：

或者，如果从上下文中无法明确看出是何种操作，我们可以显式地标明它，如下所示：

这种表示方法被称为信号流图（SFG）。信号流图是算法的一种可视化表示形式，该算法接收多个输入（这里的 $a$ 和 $b$）并生成相应的输出（这里的 $y$）。现在我们将研究 SFG 的组成部分。

SFG 的组成部分

信号流图主要由**节点（nodes）和边（edges）**组成，其中节点代表变量并用圆点表示，而边是连接任意两个节点的线段。在下面的 SFG 中，有三个节点：$a$、$b$ 和 $y$。还有两条边：一条连接节点 $a$ 到节点 $y$，另一条连接节点 $b$ 到节点 $y$。

节点 $a$ 和节点 $b$ 称为输入节点（input nodes），$y$ 称为输出节点（output node）。

输入节点只有出边（outgoing edges）。输出节点只有入边（incoming edges）。混合节点（mixed node）可以同时具有入边和出边。我们很快就会看到涉及混合节点的例子。

边代表特定的操作。例如，在上面的图中，如果边代表加法，那么输出变量 $y$ 的值为：

如果操作是比较，那么 $y$ 的值为：

或

这取决于使用的是哪种比较操作。

边上的箭头指示了它的方向，这决定了相对于某个节点，它是一条入边还是一条出边。如果没有指定方向，我们默认它是从左到右的方向；也就是说，这条边是从左侧节点引出的出边，并作为入边指向右侧节点。

SFG 描述了变量之间如何通过节点和边相互作用。

混合节点是指同时具有入边和出边的节点，如下方图解中的节点 $p$ 和 $q$。

混合节点或输出节点始终表示其入边的结果，具体取决于与这些边相关联的操作。让我们看下面这个 SFG：

在这里，如果与边相关的操作是加法，那么：

节点 $p$ 是从节点 $a$ 和 $b$ 到达的值的和。节点 $q$ 是从节点 $c$ 和 $d$ 到达的值的和。最后，节点 $y$ 是从节点 $p$ 和 $q$ 到达的值的和。

带权重的边

边可以被赋予一个权重。权重是一个乘数因子，在应用与边相关的操作之前，它会乘以节点的值。让我们通过下面的例子来理解这一点。

在上面的图中，权重 $3$ 乘以 $a$，权重 $7$ 乘以 $b$。操作假设为加法。

随后，加法操作产生如下输出：

如果一条边没有分配权重，那么权重默认设为 $1$，这意味着节点的值乘以因子 $1$。例如，在下面操作定义为加法的 SFG 中：

$y$ 的值为：

减法可以通过在边上使用负权重来实现。例如，在下面的 SFG 中：

$y$ 的值是：

信号流图可用于表示和解释各种各样的算法和问题。接下来让我们看一个例子。

斐波那契数列的 SFG 表示

考虑著名的斐波那契数列：

数列中的每个元素都是前两个元素之和，其中第一个和第二个元素分别为 $0$ 和 $1$。

斐波那契数列可以表示为一个边执行加法操作的 SFG。让我们为一直到 $13$ 的元素构建斐波那契 SFG。令

这两个变量 $a$ 和 $b$ 是我们 SFG 的输入节点。下一个元素，

可以表示为：

对于下一个元素，

我们增加两条边和一个节点 $d$，得到：

类似地，节点 $e=c+d=1+2=3$ 表示为：

我们继续构建 SFG，直到到达输出节点

上面的 SFG 可以进一步扩展以达到任意第 $n$ 个斐波那契元素。因此，计算第 $n$ 个斐波那契元素的算法也可以表示为信号流图，其中我们将前两个元素作为输入节点，第 $n$ 个元素作为输出节点出现。其他节点则为混合节点。

对于已经熟悉斐波那契 SFG 的读者来说，为了简便起见，该图可以无方向地表示，如下所示：

一般而言，当我们了解 SFG 所表示的算法上下文时，通常会在绘制边时不使用箭头。

在下一章中，我们将了解如何使用信号流图来编写执行 NTT 的算法。

本文是我们在 ZK Book 中关于数论变换（Number Theoretic Transform）系列文章的一部分