本文使用 Excel，Digital（lushprojects仿真器 可选），graphviz（可选），用数字电路课作为基础知识解释LRU算法的硬件实现。可以视为数字电路的一个综合实验。
几何原本和SICP教导我们，所有的定理都应该仅由公理直接或间接地逻辑推导而出，不应该在推导的过程中依靠没有证明过的观点。在工程和教学中，出于速度或成本的要求，或者单纯不够严谨，经常不能满足这一要求。虽然产品或同学们也都表示了满意，经常有不够完美的遗憾。
例如，计算机组成原理或系统结构中的Cache替换算法之一LRU，即 最近最少使用Least Recently Used。这个算法不仅有软件实现，也有硬件实现。讨论硬件实现在教学上有其利益，有利于学生理解 软件和硬件都可以实现算法，以及实现简单算法（猜测是乔姆斯基3型文法，使用时序逻辑电路）不一定要使用图灵机等价（例如C语言）的计算能力。但是，查了下教材，要么认为你已经会了，不必讨论，要么语焉不详，甚至不给参考文献。
在学习中，有的同学会担心，用文字和图示从内存访问领域知识解释、硬件、算法（经常被视为软件）是否一致呢。
1. Cache替换算法中的LRU，书上怎么说的
我只在李学干老师那里看到了解释，他在PPT里是如下面的截图中这样说的。
这个解释很清楚，所以后面可以用作依据计算 多少个内存块需要多少个哪种器件。不过这里的触发器（或者“对触发器”）是什么，与同学们见过的数字电路课上的长得略有差异。没有使用 状态方程、状态转换图、状态转换表，所以需要在当前领域（替换）中用文字解释。有的同学可能会误以为这是凭空建立的概念。并不是空中楼阁，这是严密地建立在我们已建立的知识体系之上的。只是为了生动，学习不那么痛苦，所以才有基于领域知识（替换）的讲解。
2. 如果以数字电路为基础，逻辑电路图应该怎么画
用数字电路的方法表达，逻辑电路图如下。
这个仿真的逻辑电路图是可以亲手操作的，在这里 https://tinyurl.com/2r32l3qw 。
通过按下左侧的某个开关，例如“访问A”，再抬起“访问A”，表示访问内存中的A块。如果按以下次序执行
关闭访问A
断开访问A
关闭访问B
断开访问B
关闭访问C
断开访问C
即以ABC的次序访问内存，右侧的A_LRU点亮，表示A是最近最少访问的块。
在上图中，用到的部件为3个JK触发器，时钟，电源，3个开关，3个与门。JK触发器也可以改用RS触发器，因为RS不会同时为1，所以RS触发器与JK触发器功能相同。
特别说明：从本文此处向下的电路与上面的电路连接略有不同，所以方程和状态转换表不同，但是功能相同。
3. 状态转换方程
接下来我走了点弯路，手推了状态转换方程。结果是对的，不过，可以借助工具，不必非得手推。
手推的过程如下。求功能，其中的一步即由逻辑电路图求状态转换方程，与数字电路课里学的一样，
(1)根据触发器 列出 特征方程，
(2)根据线路连接列出 驱动方程，
(3)把驱动方程代入特征方程，得到状态方程和输出方程。
右边删除那一块，也是对的，只是一会儿求状态转换表用Excel，不需要这一步。
4．状态转换表
由状态方程求状态转换表，我用了Excel。
Excel文件的一部分如下图所示。
共65行，除表头以外还有64行。这64行来自3个输入Ai,Bi,Ci和3个状态变量Q1,Q2,Q3，这6个量的穷举，2^6=64。
（1）穷举64行输入变量和状态变量的方法之一如下。
右侧权重最低的比特，每2行 上半部分是0，下半部分是1；
右数第2行， 每4行 上半部分是0，下半部分是1；
右数第2行， 每8行 上半部分是0，下半部分是1……
可以根据如上图的公式复制，也可以按这个规律复制粘贴，如下图所示。为方便观察，下图中的0涂成粉底色，1涂成绿底色。
（2）次态Q1*，Q2*, Q3*和输出Ao，Bo，Co
Q1*,根据手推的状态转换方程，如下图所示。
以第3行为例，
Q1* 的公式为 =OR(A3,AND(NOT(B3),D3))*1
Q2* 的公式为 =OR(A3,AND(NOT(C3),E3))*1
Q3* 的公式为 =OR(B3,AND(NOT(C3),F3))*1
公式中“*1”的目的是为了观察方便，显示为1或0，而不显示为 True 或 False。
输出，由次态求得，所以手推方程时最后一步没有必要。
以第3行为例，
Ao为 =AND(NOT(G3),NOT(H3))*1
Bo 为 =AND(G3,NOT(I3))*1
Co 为 =AND(H3,I3)*1
这样，就得到了12列*64行的状态转换表。
（3）自动生成电路图
把上述状态转换表导入到 digital （在https://github.com/hneemann/Digital/下载），可以自动生成电路图。步骤如下。
第一步 把EXCEL文件的 输入、现状 和 次态、输出 之间加一个空列；
现态命名为 Z_2^n, Z_1^n, Z_0^n, 次态命名为 Z_2^{n+1}, Z_1^{n+1}, Z_0^{n+1}。调整列的次序为 输入、现态、空列、次态、输出。
第二步 把上述EXCEL导出成CSV。
第三步 在Digital中，分析 | 综合，得到表，然后 文件 | 打开 | 类型选“逗号分开的值”，得到状态转换方程和输出方程，得到状态转换表。
第四步 创建|基于JK触发器的电路。也可以选择基于其他器件。
如下图所示，为基于JK触发器创建的电路，正在仿真运行，当前A是最近最少访问的块。
这个看起来更复杂的电路，与此前展示的电路，是等价的。这由状态转换表相同来保证。基于同样的原理，LRU算法的硬件实现 与 LRU算法是等价的。
5. 捷径，不必手推方程的方法
上文中提到，我走了一点弯路，不必手推方程。
不必手推方程的过程如下。
在 Digital 中，如果不使用异步RS触发器（例如用JK触发器）作为器件，手动画出电路。如下图，请注意从每个触发器的Q引出的三角标志，称为 隧道，以及它的名字。
在菜单中选择 分析|分析，即可得到方程和状态转换表。
附带说一句，上述电路图可以仿真运行。
穷举状态转换表，可以用以证明 上述电路能完成 LRU 算法的功能，因为状态转换表（以及输出），刻画了在所有 某个现态之下（在这里是历史上以何种次序访问过A,B,C哪些块）施加某个信号（在这里是访问A，B，C中的某个块），因此得到新的状态以及输出哪个块是最近最少访问的。
举个例子。在下图中，红框的部分 表明 在某些现态（历史有某些次序的按键）之下，访问了C块，则B块成为最近最少访问的块。
至此，基于数字电路的基础，我们解释了这个电路为什么可以实现LRU运算的功能——状态转换表（以及输出）所刻画的函数与LRU算法是一致的。
下图是使用RS触发器的版本，不能分析，可以仿真。
6. 状态转换图
我原本的目的，还包括用状态转换图表明3个触发器和3个与门的电路与LRU算法一致，这样观察可能更直观一些。
得到状态转换表和方程以后，我才发现 Digital并不支持生成状态转换图。我原以为它能，它能画状态转换图，但是需要用手拖动部件，画状态节点和状态迁移连线。可以估算出，3个触发器，共8个状态，每个状态向外迁移，有3个自变量作为消息，8个可能的消息，并有3个输出。工作量不小。
我搜索了一下画状态转换图的工具，看到了熟悉的 graphviz，自动布局的绘图工具，可以用源代码作为输入。
我做了两个版本。
其一，去除约束项。我们知道，A,B,C三个变量同一时刻只有1个可以是1，因为不允许同时访问内存的不同区域。并且，观察仿真器或状态转换表可知，访问某个块之后，例如访问A以后，A会由1再变为0，次态保持不变与现态相同。输出不全为0，我们暂不关心这种情况。
根据目标文件中的典型一行，
001->000[label="001/100"];
我调整Excel列的次序为 现态、次态、输入、输出。
把Excel文件导出，删除列间的空格。每一行类似下面这样。
001000001100
再使用Emacs的宏，插入箭头、方括号等字符，得到 每一行类似下面这样。
001->000[label="001/100"];
完整代码如下。
命令行
c:\tools\graphviz\bin\dot tran.dot -Tpng -otran.png
得到png图片。
如下图所示，是访问序列为A,B,C的实例之一，输出为A是最近最少访问的块。
另一个版本的状态转换图，方法完全相同。所不同者，我用了全部64行可能。看起来如下图所示，已经失去了帮助直观理解硬件与LRU算法等价的价值，适合炫技和作为熟悉工具的练习。
7. 总结
借助工具，我们可以直观展示和观察 通过数字电路这样的基础知识 理解 计算机组成原理或系统结构中的硬件实现LRU 算法，减少学生对领域知识、硬件、算法间是否同构的担心。