SLICAP图像分割C++实现

代码仓库

https://github.com/SingleZombie/SLICAP-image-segmentation-cpp

需求分析

输入一幅图像，输入图像中每个像素的分类。比如产生以下的效果：

由于我的软件工程天赋过于高超，加上用户、产品经理、程序员都是我自己，因此分析阶段的功能建模部分就略过了。

技能学习

算法原理

见上一篇博客

概要设计

学完算法，准备开始写程序后，我的脑中立刻就浮现了以下的程序结构图：

和以往一样，主函数分成预处理、执行操作、输出处理三个模块。执行操作可以分成生成超像素和利用超像素进行图像分割，在用超像素模块分割模块中会利用到AP聚类算法。

这次程序的两个主要模块非常清晰：用SLIC生成超像素的模块和用AP聚类的模块。两个模块独立性高，且具有先后关系。应该逐模块进行开发，每个模块开发完成后进行单元测试，确认模块工作正常后再进行后续的开发。同时，由于项目时间十分紧张，我还需要采用敏捷开发，不浪费一分一秒在无谓的写文档上。

详细设计

虽然划分模块用的是结构化设计的思想，但我还是喜欢设计类并进行面向对象编程。

超像素生成模块

时间紧张，不画UML图了，直接用文字表达思想，之后直接写代码。

首先要有一个SuperPixels类。该类用于在超像素生成和超像素图像分割模块间传递信息。该类存了一个图像矩阵、一个存储每个像素所述超像素类的数组、一个存储每个超像素信息（平均颜色向量）的数组。外部操作有根据图像矩阵创建新对象。由于算法对数据操作较多，该类可以被看成一个“结构”，标记数组、超像素信息是透明的。超像素信息用SuperPixel结构表示，该结构就是一个五维量（颜色和坐标）加一个像素数。

SuperPixelsGenerator提供生成超像素的算法，与一个SuperPixels关联，被处理模块调用。该类要存储一个图像矩阵，超像素期望的个数superPixelCount, 颜色距离参数colorDisM，最大迭代次数maxIterTime，计算一个期望距离expectedDis。我按算法流程顺序来设计每一个部分。设计时参考了这篇博客。

首先我需要一个RGB和LAB互相转换的函数，供SuperPixelsGenerator调用。这个函数应该单独写在一个模块中。上面那篇博客的作者还写了一篇RGB转LAB的博客。但由于自己实现比较复杂，我打算直接用OpenCV自带的方法转换。

std::vector SuperPixelsGenerator::computeGradient()，计算图像每一点的梯度。

void SuperPixelsGenerator::initSuperPixelsCenter()调用computeGradient()来计算初始的超像素中心。

void SuperPixelsGenerator::updateEachPixel()更新每个像素的标记（类别）。

void SuperPixelsGenerator::updateSuperPixelsCenter()更新超像素中心为平均值。

void SuperPixelsGenerator::enforceConnectivity()对最终的标记进行强制连续性的处理。

超像素聚类模块

我先完成AP算法模块的设计，再完成调用AP算法模块的设计。

AP算法应该可以对任何形式的数据进行。因此，AP算法应该写成一个模板函数。

AP算法接收一个数据间相似二元关系的矩阵，输出一个标记表，表示每一个数据的数据中心是哪个数据。唯一一个可调参数是更新率$\lambda$。我本来想写一个和STL风格类似的模板函数，结果发现我忘记了怎么声明一个参数的指针或迭代器参数。再进一步思考，不管什么类型的数据，都可以用一个整数索引来表示，相似度可以直接存在一个数组里。那么我就不需要使用模板函数了。最终，函数声明写成了这样：

1

std::vector<int> apClustering(const std::vector<int>& similarity, unsigned dataCount,double lambda = 0.5)

再思考一下程序设计细节。对于每对数据，要计算除某点之外的某值的最大值，这个可以通过记录每对点某值的最大值和次大值实现（打ACM做树形dp的时候实现了好多遍了）。另外，每对数据间还需要一个除了某两点以外的累计值，这个直接存一个累计值，用的时候减掉那两个不要的值就可以了。

这个算法直接写在一个函数里没什么问题。要让代码模块性更好的话，可以把$r,a$矩阵的更新分别写一个函数。

超像素聚类算法单独写一个类。该类初始化时接收算法权值参数。调用该类的clustering函数可以对一个超像素集合进行聚类，直接返回AP聚类的标记数组。该函数调用一个函数计算相似度，在调用AP算法返回结果。

1
2
3

SuperPixelClusteringAlgorithm::SuperPixelClusteringAlgorithm(int wl = 3, int wa = 10, int wb = 10);
std::vector<int> SuperPixelClusteringAlgorithm::clustering(const SuperPixel&);
std::vector<int> SuperPixelClusteringAlgorithm::getSimilarity(const SuperPixel&);

程序设计及性能优化

由于时间紧、算法对数据操作量复杂而软件流程复杂性低，本次程序我写得十分“暴力”，很多地方都没有进行模块化、封装。

超像素生成模块

我用四个半小时的实际工作时间完成了看似正确的超像素生成模块。在三种参数下的生成结果如下：（鼠标放到图片上可以看到参数信息）

但是，程序的性能非常差。明明我已经有意识地降低时间和空间使用程度，但程序依然要20多秒才能完成4次迭代的生成算法（生成上面的第三幅图）。

凭借着上次软件工程项目的经验，我使用VS的性能分析工具来改进程序，结果如下：

大部分时间都是画在迭代函数上。令我惊讶的是，几乎所有时间都浪费在了这个计算五维量距离的函数上。

仔细看了一遍网上实现代码和论文中的算法，发现我对算法的理解错了！每次是搜索超像素中心附近的$2S\times2S$个像素，不是对每个像素进行搜索。我立马修改了上一篇博客和代码。

这下算法的结果也正常了，性能也正常了。程序1.7秒可以完成4次迭代、500个超像素、图片大小510X385的超像素生成算法。哪怕不经过任何优化，这个性能也能满足一般的要求。调试的时候不会浪费太多时间，做为作业提交也十分足够。有机会的话，我还是会优化一下代码。

在算法正确的基础上，我又做了3次实验：

目前开发调试外加吹牛的时间共计五个半小时。

超像素聚类模块

这个模块实现起来并不复杂，但我还是浪费了很多时间在调试上。

一开始，我发现我没有正确理解AP算法，没有对相似度矩阵对角线上的值进行特殊处理。我把对角线的值设为平均值后，还是发现聚类算法只会把每一块的数据中心划成自己。由于图片不好调试，我构造了6个点相似度矩阵进行算法调试，其中每三个点有一个很明确的数据中心。算法迟迟得不到正确结果。我浪费了大量时间在代码比对上。突然，我一气之下修改了AP算法的循环停止条件，让它迭代进行100次，结果竟然正常了。我发现在AP算法迭代的过程中，每个点的数据中心可能会固定一段时间，但实际上两个矩阵的值还没有收敛。我把循环停止条件改成了数据中心连续5次迭代都不变才解决AP算法的收敛问题。可是，我把数据从6个点换成了原图像，算法还是进行失败。我又偶然间把计算相似度矩阵对角线的公式去掉了SLICAP论文中提到的比例系数，算法竟然正常工作了。不知道是不是我没有认真看那篇论文，我觉得那篇论文太坑人了，加上比例系数后算法完全工作不了，我还以为是自己写错了。

和设计的一样SuperPixelClusteringAlgorithm类只负责相似度计算和算法调用，AP算法的细节在APClustering中。

程序设计真的没什么可以说的。假设有$N$个数据，迭代$I$次，那么AP算法时间复杂度是$O(IN^2)$，空间复杂度$O(N^2)$。稍微优化一下求最大值和求和的过程就能把看似$O(N^3)$的单次迭代变成$O(N^2)$。

图片显示模块

我打算显示3幅图片：超像素分割结果、超像素聚类结果、图片分割处理结果。

理论上需要一个模块来专门处理输出图片的处理。由于时间不够，我也很懒，只把超像素聚类结果生成函数放到了单独的文件里。超像素分割结果图像放到了超像素类里，图像分割处理结果直接放到了main函数里。这样写程序是非常不好的，我会在之后的版本中修改。

命令行参数模块

理论上，所有的参数都是可以调整的，而且程序可以在不关闭的情况下保存之前的参数设定，循环处理图片。做为一个完整的软件来说，应该提供这些丰富的功能。但我暂时没有写，我写的东西暂时只能算一个程序。

最终结果

（我也忘了当时参数是什么了，但这绝对是程序生成出来的）

感想

我觉得自己很帅。在一天之内不仅实现了图像分割程序的功能，而且凭借着强大的心理抗挫折能力，没有被烦人的BUG击溃，最终站到了胜利的高点。当我回首过去，看着一条条充满荆棘的路，看着我踩的一个个坑，我感到一丝心酸；但当我俯视大地，看着程序能够产生较好的图像分割结果时，我又感到苦尽甘来，心旷神怡。

更新记录

20.2.1

• 上传博客

本文先对论文“SLIC Superpixels Compared to State-of-the-Art Superpixel Methods”做一个论文阅读报告，再稍微介绍一下其他论文，介绍算法原理。下一篇文章会按之前小作业的格式写技能学习、编程过程、代码结构介绍、实验结果分析与感想。

SLIC论文阅读报告

在搜索引擎中可以找到很多分析此论文的中文博客。比如这篇博客分析了代码实现原理。论文中的代码实现网页我怎么都打不开，只能从这篇博客里来获取代码实现的细节。另一篇博客分析了论文代码实现上的性能缺陷。直接看一些中文博客的分析就能对论文的方法理解个大概，再看论文的时候就会比较顺利。

内容梗概

本文对当时的5种超像素方法进行了比较，并提出了一种simple linear iterative clustering (SLIC)(简单线性迭代聚类)的生成超像素的算法。

超像素就是一些像素的集合。超像素的边缘要和图像中物体边缘大致符合。一般获取超像素是其他数字图像处理的预处理工作。图像分割就可以先进行超像素预处理，把每个超像素当成原来算法中的像素来处理，减少数据规模。

算法流程

算法整体上接受一个参数$k$，表示期望的超像素的个数。算法输出$k$个超像素中心以及每个像素属于哪个超像素。

每个像素被看成一个五维量$(l,a,b,x,y)$，前三维是LAB颜色空间信息，后两维是像素位置信息。算法均匀地初始化$k$个超像素中心，并计算超像素间距$S=\sqrt{N/k}$（$N$是像素个数）。之后遍历所有像素中心，找到每个像素周围$2S\times2S$范围内在一种距离度量下”最近“的超像素中心。每个像素”分类“完成后，把一类像素的五维平均值当成新的超像素中心，并以计算本轮分类方式和上一轮的残差。算法不断重复上述过程直到残差收敛至0。

以上只是一个算法的大致描述，算法的具体细节如下：

距离度量方式

如果单纯地把两个像素的距离定义成五维量的距离，就会出现一个问题：像素距离给整体距离的影响是不确定的。如果要求的$k$值较小，每个像素离超像素中心的距离较大，那么像素距离就会给整体的距离带来更大的影响。为了让像素距离和颜色距离对距离的影响权重更为平衡，文章提出了如下的距离度量方式：

其中$i,j$表示两个进行距离比较的像素，$N_c,N_s$是用于标准化颜色距离和像素距离的量。

文章取 $N_s = S=\sqrt{N/k} $，$N_c$直接定义为一个常数$m$。文章建议$m$取$[1,40]$。现在距离定义成了如下形式：

实际实现时出于方便，距离用以下公式计算：

另外，当图片的形式发生变化时，公式可以很方便地修改。如果图片是灰度图，那么颜色度量只需要考虑灰度之间的差就行了；如果不是图片而是三维体素，那么只需要把空间距离加上$z$分量。

保证超像素连续性

由于像素分类的时候除了位置的相似性外，还考虑了颜色的相似性，这样会出现一些问题：一个靠左的像素，可能属于右边像素中心；一个靠右的像素，可能属于左边像素中心。这样的话同类的像素可能被另一类的像素切成了两块，在图像上并不连续。

为了强制同一类超像素连通，算法在迭代结束后又对超像素进行了处理。算法从上到下，从左到右尝试搜索未标记的像素。对正在搜索的像素，把其四邻域中与它属于同一个旧超像素的像素加入搜索队列，并标记其和当前搜索像素属于同一个新超像素。当前这片新超像素搜索结束后，若新超像素总数少于期望超像素大小的一半，则把当前超像素的标记改成上一个新超像素的标记。上一个新超像素是当前新超像素搜索起点四邻域中的一个新超像素。

初始超像素中心优化

初始的超像素中心如果处于梯度比较大的点的话，可能会影响算法之后的表现。

该算法实现时，计算每个初步选择的超像素中心的$3\times3$邻域的梯度，把梯度最小的像素作为最终的初始超像素中心。

梯度的计算是$x,y$方向上梯度之和。$x$方向梯度是左右两个像素颜色向量的差平方和，$y$方向梯度是上下两个像素颜色向量的差平方和。

默认参数

由于残差收敛很快，算法默认迭代10次。这样残差可以不用计算了。

颜色距离参数$m$固定为10。

基于超像素的图像分割

仅获得了图像的超像素还不够，还需要一些其他的方法来做图像分割。我又去找了一些基于超像素的图像分割论文。

我浏览了以下论文：

[1] Li Z, Wu X M, Chang S F. Segmentation using superpixels: A bipartite graph partitioning approach[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2012: 789-796.

[2] Zhou B. Image segmentation using SLIC superpixels and affinity propagation clustering[J]. Int. J. Sci. Res, 2015, 4(4): 1525-1529.

[1]论文本身质量较高，且没有使用深度学习的方法。论文提出了一种基于超像素和二分图分割的图像分割方法，需要输入类别数$k$，输出图像分割结果。我一开始看到了标题中的二分图，以为图像分割会被转换成一个可以用我十分熟悉的二分图算法解决的问题。但是文章莫名其妙地把问题变成了一个我很陌生的二分图分割的问题。我既没有从文章不清晰的叙述中理解问题转换的原理，也不愿去学一个看起来比较复杂的二分图分割算法。所以最后放弃了实现这篇论文的方法。

在Google上搜索”superpixel based segemenataion”或”image segmentation using superpixel”，都能搜出这个网站。该网站的作者实现了一个基于超像素的图像分割算法，其算法来自论文[2]。论文[2]非常直接地把SLIC和AP聚类两个算法拼接起来，得到了一种基于超像素和聚类的图像分割算法，该算法不用指定类别数。正好，我觉得超像素这个预处理已经对图像分割帮助很大了，只需要一个简单的超像素分类算法即可。我最终决定学习论文[2]的方法。

学论文[2]不应该去看那篇论文，而应该去看AP聚类算法的论文Clustering by Passing Messages Between Data Points。这种聚类算法比较有名气，搜索引擎上可以找到不少分析此算法的中文内容。

AP算法需要提供数据间的相似度这一二元关系矩阵，输出每个数据点属于的数据中心。AP算法的思想我没有理解，但其流程十分简单：算法构建了两个关系矩阵$r，a$，用以描述某个点适合作为另一个但数据中心的程度。算法用两个公式来更新这两个关系矩阵直至矩阵收敛。特别地，为了防止数值上的问题，算法引入了一个更新系数$\lambda$，每次保留$\lambda$倍的上一轮值，加上$(1 - \lambda)$倍更新值。这个比例系数在数值算法中非常常见，有点像梯度下降中的学习率。

如果我把AP算法理解了，会写一篇博客来详细介绍这一算法。

把AP算法运用在图像分割中，只需要定义图像任意两个超像素间的相似度就行了。论文[2]的主要贡献也就是定义相似度。论文[2]比较了3种相似度定义方式，最终选择了效果最好，也最简单的一种定义方式：相似度定义为负带权颜色向量差平方和，即：

其中$s(i,j)$表示超像素$i,j$间相似度，$L,a,b$是超像素平均LAB颜色空间颜色向量分量。

论文中超像素数$K=600$，超像素颜色距离参数$m=20$，颜色权值$w_l=3,w_a=10,w_b=10$。理论上这些参数都是可以调的，甚至相似度的定义参数也是可以调的。

我总算找到了博客的正确用法：给自己增加做事情的动力。

寒假回家后，我整个人变得很懒，这个学期最后一门课程的大作业也迟迟没有做完。恰好我发现，自从我把博客链接放到了社交媒体上后，有同学看了我的博客。让别人看到自己“作品”的感觉还是很好的。我打算用写博客的方式来更好地完成作业。

本文按照作业的要求，分为论文概要、代码模块分析、实验结果（使用自己的数据）三个部分。当然，由于我在博客里写东西比较随意，我提交的作业报告肯定会在这篇博客的基础上有所修改。

论文概要

问题定义

本文解决的是一个非常经典的问题：如何恢复一张被模糊和添加噪声的图片。即假设模糊矩阵是$K$,原图像是$u$，噪声是$N$,模糊图像是$g$。那么$g = Ku+N$。现在我们只知道$g$，如何得到$u$。

更具体地，本文介绍的是盲去模糊，即不知道模糊卷积核的情况下，应该如何恢复模糊图像。我上次写的第二个小作业解决的是类似的去模糊问题，但那次问题是一个非盲去模糊，即卷积核已知。

文章贡献

求未知模糊卷积核的问题可以被转换成一个优化问题，即求解某一个损失函数的最小值。文章主要的贡献是提出了一种在损失函数中添加正则化的方法，并且围绕这种方法提供了一套完整的去模糊算法。

方法思想

求解模糊卷积核的优化问题有很多的局部最优解。为了获取一个更好的解，需要加入一些正则化项。正则化项似乎可以用在所有的优化问题里，来避免一些局部最优解。但正则化项的原理我一直都不是很理解，感觉这就是一个被人工设置出来的东西，没有比较清晰的理论依据。把一个参数的正则化项加入优化的损失函数，其直观意义就是让参数不能过大。

在去模糊问题中优化问题中，一般使用的是复原图像的高频图像（后面会详细介绍这个是什么东西）的第一范式（每个分量的和）做为正则化项，加入到需要最小化的损失函数中。该文章发现，噪声增加能让第一范式项也增加，但是模糊却能减少第一范式项。如果单纯地把这一项放进优化目标里，可能得不到好的去模糊效果。文章发现，如果把第一范式和第二范式（每个分量平方和的平方根）的比值做为正则化项的话，无论是模糊增加还是噪声增加，都会让这一项增加。那么，最小化这一项，就能达到同时减少模糊和噪声的效果了。

简而言之，这种新的正则化项较以往的方法，能更好地同时减少噪声和模糊。

算法流程

整体上来看，算法分两步：第一步使用新的优化函数估计出模糊卷积核，这样盲去模糊问题就变成了一个非盲去模糊问题；第二步使用以往的非盲去模糊方法得到去模糊结果。

模糊卷积核估计

卷积核估计是在图像的高频图像进行的。所谓高频图像，就是对图像求x方向的一阶导数和y方向的一阶导数得到的图像。用$y$来表示模糊图像的高频图像，$x$表示修复图像的高频图像，那么优化目标可以写成：

其中$k$是模糊卷积核，$\lambda,\phi$用来调节对应两项的权重。

解决这一优化问题的方法是对两个优化参数$x,k$进行轮流优化。即优化$x$时，假设$k$是一个常量；反之亦然。

更新$x$

此时，优化目标被简化成以下形式：

但这个函数依然是一个没有极点，比较难优化的一个函数。文章中发现，如果第二范式的值固定，即求解

$min_{x} \lambda||Kx-y||_2^2+{||x||_1}$这样一个优化目标的最小值的话，是有一个比较快的iterative shrinkage-thresholding algorithm(ISTA)算法的。

因此，更新$x$又可以分成两层：先在固定第二范式的分母的情况下，使用ISTA更新几次$x$；之后重新计算第二范式，这个大的过程又重复进行几次。

更新$k$

此时，优化目标被简化成以下形式：

这个问题也有现成的算法可以解决。文中用的是无约束的iterative re-weighted least squares (IRLS)算法。

文章中也指出，在实际运用的算法的时候，每次计算出卷积核后要把其中值较小的数直接设为0，以更好应对噪声。

多级卷积核更新优化

由于实际情况中，模糊卷积核可能很大。为了保证卷积核在较大时也能得到一个比较好的解，文章中使用了一种优化方法。该方法从粗到精地计算卷积核，即先假设卷积核很小，使用之前提到的算法计算出卷积核后，再把卷积核细分变大。

在实现时，文章把最开始的卷积核设为3X3，每次以$\sqrt{2}$ 的比例扩大卷积核。对每一层卷积核的更新，$x$和$k$都进行200次交替更新。新一层卷积核使用上一层卷积核的双线性插值得到。

图像恢复

图像恢复用的是Fast image deconvolution using hyper-laplacian priors这篇论文的非盲去模糊方法。该方法大致思想是最小化复原图像做模糊卷积的结果图像和退化图像之间的均方误差。由于非盲去模糊的非适定性较小，不需要再用这篇文章开始提到的第一范数和第二范数的比值做为正则化项。

方法拓展

之前的描述都假设模糊操作是通过一个卷积核来完成的。如果图像因为旋转而扭曲，也可以用类似的方法，只需要修改优化目标中的卷积那一项就行了，大致思想不变。

实验结果与评估

文章首先对Understanding and evaluating blind deconvolution algorithms中提出的4幅用8个大小不同的模糊卷积核得到的32个模糊图片进行去模糊操作，并且用这篇文章中提出的方式来评估去模糊的效果。具体来说，评估的方法是比较还原结果图像与真实图像的均方误差与以已知卷积核还原图像与真实图像的均方误差的比值。这个比值肯定是大于1的，反映的是模糊卷积核复原的效果。文章统计了错误比值的分布（图片错误比值为1、2、3…所占所有图片的百分比）。

文章把新提出的算法与之前的某两个算法进行了比较。

同时，文章还使用了一些现实中的模糊图片实例来进行去模糊。文章还对一些经过旋转扭曲的图像进行复原。这些复原的结果没有经过数据上的评估，但经肉眼观察，这些图像复原的效果还是很好的。

代码模块分析

整体层次

代码的模块调用层次如下：

• test_blind_deconv_params(执行算法的函数版本)
• test_blind_deconv（执行算法的脚本版本）
  • ms_blind_deconv（多级盲去模糊，主函数）
    • ss_blind_deconv（单级估计卷积核、原图像）
      • pcg_kernel_irls_conv（IRLS算法）
        • pcg_kernel_core_irls_conv（IRLS算法中计算一个公式中的值的函数）
    • fast_deconv_bregman（非盲去模糊算法）
      • solve_image_bregman（解决非盲去模糊中的优化问题的算法）
    • center_kernel_separate（把卷积核位置调整为居中）

算法接口test_blind_deconv

test_blind_deconv提供了一个对示例图片去模糊的脚本，而test_blind_deconv_params提供了一个接收文件名、模糊卷积核大小的去模糊函数。这两个文件里的内容相同。

算法接口仅仅调用了主去模糊函数ms_blind_deconv，并且默认了一些可调的参数（文件名或模糊图像矩阵，$\lambda$等参数，优化算法循环次数、非盲去模糊的参数等）。

多级盲去模糊主函数ms_blind_deconv

该函数接收文件名和参数结构，返回原图像、模糊图像、模糊卷积核、参数结构。

该函数描述整个算法的主要流程，在调用具体优化算法前对输入图像进行了繁琐的预处理，并最后把去模糊结果显示出来。

和论文中的描述算法流程一样，该函数先对数据预处理，再分级估计卷积核，每一级里先循环更新$x$，再调用IRLS算法更新$k$，求得最终估计模糊卷积核后使用非盲去模糊算法计算复原图像。

预处理部分大致干了以下事情：

• 从文件或参数中读取图像矩阵
• 更改图片的大小
• gamma校正
• RGB转灰度图
• 计算各级卷积核大小

在每一级估计卷积核前，函数还获取初始化卷积核、图像（从上一级插值得来）、计算高频图像。

之后函数调用单级卷积核估计函数ss_blind_deconv。每次卷积核被计算出来后使用center_kernel_separate函数居中卷积核。

最后一级的卷积核被估计出来后，这个卷积核会被存下来。该卷积核用于调用非盲去模糊算法fast_deconv_bregman，最终可以得到去模糊的图像。

单级估计卷积核、原图像ss_blind_deconv

该函数接受模糊图像、初始化复原图像、初始化卷积核、优化函数参数、循环次数，输出复原图像核估计卷积核。

该函数先初始化变量，之后按照论文中的方法，在固定第二范式项的情况下使用ISTA来更新几次$x$，之后更新第二范式项。更新$x$后调用IRLS算法更新$k$。

pcg_kernel_irls_conv函数是IRLS算法。算法中又调用了pcg_kernel_core_irls_conv来计算公式中的一个值。

非盲去模糊算法fast_deconv_bregman

该算法在Fast image deconvolution using hyper-laplacian priors中被提出。算法把最小化损失函数中的可变参数加入x方向的高频图像和y方向的高频图像，在每一轮迭代中使用solve_image_bregman来计算可变参数的更新值。

实验结果

现有数据

使用自带的fishes.jpg

新数据

我使用第二次小作业的模糊图像作为输入，用test_blind_deconv_params("I_n.jpg",9)命令来执行算法。

实际的模糊卷积核是一个高斯模糊卷积核。估计的卷积核与真实的卷积核十分接近。

我还剩软件工程这门课要考。这门课没留下真题，直接复习很难定下具体的目标。于是我决定还是用写复习笔记来复习，让复习的目的性更强，同时激发斗志，收获成就感。

软件工程这门课的性质十分特殊。这是一门几乎不涉及理论，却涉及工具的使用、大量的经验与人为设定的规则的一门课。讲得清楚一些，就是这门课几乎没有什么干货，应该更多地考察实践能力，而不是用靠着一张瞎记瞎理解就能回答的卷子来考察。但没办法，我纵使有着极为丰富的项目经验教训与软件工程方法实践心得，平时学这门课的时候也还算认真，考前还是不得不去做一下复习。

吐槽完了，来谈一下具体的复习策略。课本无效内容较多，每一章的有效内容量分布不均，最气人的是复习大纲和课本还对应不起来。没办法，我只能自己把这门课讲的内容分个类，针对每个类的内容集中复习。

从实际的编程方法来看，这门课讲了结构化编程和面向对象编程两种编程方式。这两种编程方式有着不一样的分析和设计方法、工具。因此，我会各用一篇文章来复习这两部分的方法和工具。此外，还有不少内容和具体的编程方法无关，比如软件测试、软件维护，这些内容我会用一篇文章来复习。还有一些比较细致的，略有理论性的东西，比如耦合的分类等内容，我单独用一篇文章来写这些理论知识。最后我对照复习大纲，扫干净剩下的知识点。

软件工程复习1：结构化编程

需求分析

结构化需求分析的核心的数据。围绕着数据，要建立三种模型：数据建模、功能建模、行为建模。三种模型有各自的建模工具，三种模型中涉及的概念会被统一写在数据字典中以方便查看。

数据建模

数据建模描述的是数据的静态信息。准确来说，是一个数据可以进一步被分解成哪些属性，以及一个数据和另一个数据的关系中出现的新属性。

数据建模使用的E-R图。矩形是实体，圆圈是实体的属性，菱形是实体间的关系。有关系的实体要写上是几对几关系。

E-R图在上学期学数据库的时候学了，我就不多加复习了。只要看了E-R图的一个例子，就能很快搞懂这个图的意义与使用方法。

功能建模

理论上来说，有了静态模型，剩下的应该是动态模型。我对剩下两种模型的理解是：功能模型是对数据整体处理方式的建模，行为建模是对数据局部具体处理方式的建模。

所有程序全部可以看成是一个输入转换成输出的过程。输入输出不仅是传统的数据，输入可能是鼠标的一次点击、键盘的一次输入；输出可能是屏幕窗口的一个变化。功能建模就是描述输入数据是怎么一步一步变成输出数据的。

数据流图（DFD）是常用的（考试考察的）功能建模工具。DFD按照自顶向下的思想，用多层图来逐步分解数据加工过程。顶层图只有一个数据加工过程，之后的1、2层图会把上一层的数据加工过程细分。

每一层中，圆圈表示数据加工；矩形表示外部的实体，也就是和数据交互的对象；封了半边口的矩形是数据库；箭头是数据流向，箭头上要有数据流名。

DFD有以下要求：

• 父图和子图要平衡。具体来说，父图和子图的输入输出要一致。子图可以把父图的输入分解。
• 数据变换部分要按次序编号

这种图看了一遍例子就能理解图的意思，但要自己画一画才能掌握画的方法。正常来说DFD至少要分解到第二层，但考试要求我们只画一层。为了复习，我来做一道例题。

</br>

例：银行活期现金存取款柜台业务软件系统。存款时，储户将存款金额及存折，交给银行柜台操作员；取款时，储户则直接将取款数额告知操作员，并递交存折。具体存取款过程如下：

(1) 存款处理

• 清点现金，确认存款金额；
• 输入帐号、存款金额；
• 根据存款金额记录分户账及总账，并登记存折及打印凭条。

（2）取款处理

• 输入帐号，取款金额；
• 储户输入密码，系统核对密码并查询余额；
• 若余额充足，根据取款金额记录分户账及总账，并由票据打印机打印登折数据和凭条数据。

</br>

要求：画出系统顶层和一层数据流图 。

老师给的参考答案：

我第一遍的答案：

看了答案后修改的答案：

先声明一下，这道题我们之前上课做了一遍，我不是第一次做。

首先先看一下顶层图，顶层图其实就是这个系统包含的范围，以及系统涉及的实体。把存折给操作员等行为并不是在软件中，因此不能放进软件系统里；打印机是一个独立的系统，不算在这个软件里面。所以最终顶层图画成了那个样子。我对顶层图答案没什么异议。

重点在一层图上。我这次第一遍画的时候，看到需求很明确地把软件的需求分成了存款和取款两个部分，所以我直接就分了两个数据变换模块，没有去管存取款的实现细节。讲道理，一层图不需要画那么细，这样画一样理论上就可以了。

但我看了答案之后，加入了一个信息记录模块。因为把修改分户账和总账在存款和取款中都出现了，单独拿出来也说得过去。

但是答案剩下的部分我就不能赞同了。首先是业务确认模块。需求只提到存款要确认，但没有提到取款要确认。虽然按常识来说存取款都是要确认操作的，但是这里需求没有给出，就不应该加进来。既然取款不需要确认，那么就不能写一个公共的业务确认模块。再来是查询余额模块。查询余额显然是属于取款的，这个应该属于实现细节，在一层图就写出来还早了一点。

老师上课的时候也跟我们说，由于只要求画一层图，这张图细节部分写得多了一些。按理来说，参考答案做的并不是很好。我觉得我第二遍的答案更好一些。甚至在实际实现的时候，我觉得第一遍的答案就够了，细节就应该在之后的图里显示出来。哪怕存取款有重合的部分，也可以在实现的时候进行模块复用。

我觉得这道题的最大启示不是一层图该如何分解，而是顶层图如何划分软件系统的边界的。我上课第一次画的时候就把递存折写进系统，而且没有画打印机，这些都是很明显的错误。当然我不知道考试的题会怎么出，应该把题目涉及的实体和数据变换模块找出来，把每一个重要的词都画进系统里应该就问题不大。

行为建模

前面也提到了，我觉得行为建模就是对更具体的数据变换过程进行建模。课本上介绍了两种建模方法：状态转换图（STD）和过程描述语言（PDL）或伪码语言（PL）。

状态转换图

正如其名，状态转换图描述了数据对象不同时刻的不同属性，以及在不同状态间的转换方式。

我先以个人经验讲一下状态转换图的必要性。我之前做游戏的时候，被一个逻辑搞得十分头疼：卡牌游戏中鼠标的控制逻辑。正常情况下，鼠标可以拖动卡牌，也可以放到敌人头上或者一个buff上查看具体信息。在拖一张卡的时候，卡移到我方头上或者对方头上就不能显示信息，而应该根据卡牌是否能对这个目标使用而高亮目标。拖手牌里的一张卡和拖场面上的一张卡的拖动状态还是不一样的。由于没有事先设计，这个逻辑写的我非常混乱。我一看到了状态转换图，就立刻知道了以后该怎么处理这种状态转换情况。课本上再栩栩如生的案例也不如一次个人的经历对我理解这个概念的帮助大。

状态转换图就类似自动机，是一个点和边构成的图。点是状态，边是转移条件。在STD中，黑点代表初态，带圈黑点表示终态，大圆角矩形框表示中间状态。中间状态要写上状态名、状态变量、状态此时的活动。

状态转移图我还没画过，虽然考试不一定会考怎么画，但我还是想练习一下。

我画的时候发现visio的状态图和课本上的不太一样，就不打算画了。

加工逻辑

加工逻辑就是描述流程或算法。工具就是我们非常熟悉的伪代码。

伪代码理论上没什么格式要求。我喜欢按C语言的风格写。当然有些人喜欢拿箭头表示赋值。

数据字典

数据字典就是对之前建模过程中的数据流、数据变换、数据做一个详细的定义，以方便沟通交流。

数据字典本身是一个概念性质的东西，其实现形式多种多样。课本上讲了三种定义数据字典的方法。

词条描述

非常死板非常麻烦的数据词典表示法，也许在实际运用中非常好用，因为它读起来的时候非常详细。但在学这门课的时候我是不愿这样写数据字典的。

直接拿一个例子来讲词条描述的表法吧：

1
2
3
4
5
6

数据元素名：词
类型：文字（char*)
长度：任意长度
取值范围：………………
相关数据元素：………………
相关数据结构：字符型（不能为空）

定义式

用一种类似上下文无关语言的方法来定义一种数据。还是直接上例子：

1
2
3
4

日期 = 年 ＋　月　＋日
年 = “1900”.."1999"
月 = "01".."12"
日 = "01".."31"

数据表

直接把数据库二维表当成数据字典。比如

结构化设计

设计分成概要设计和详细设计。这两个阶段的具体定义可能会在其他文章中讲。

在结构化设计中，概要设计就是根据数据流图设计出整体结构，详细设计则是在语句层面具体设计某一个算法、过程。概要设计用面向数据流的设计方法，详细设计会用到流程图、盒图、问题分析图（PAD）、判定树。

面向数据流的设计方法（画结构图）

面向数据流的设计方法就是根据需求分析时的数据流图，设计出程序的模块。和画DFD一样，这个过程也是自顶向下进行的。

结构图

这个过程用到的工具有层次图和结构图（SC）。但从课本上的介绍来看，结构图是层次图的一个拓展。也就是这两种图不是并列关系，而是递进关系。后续的分析也是基于结构图的。

层次图用方框表示模块，只是把模块一层一层地越分越细。结构图在层次图的基础行，要求在模块之间的线上加上数据流的描述

数据流图转结构图

数据流图经过很简单的转换就能变成结构图。课本介绍了两种转换方法。这两种方法输出的结构图的整体结构与大致算法大致相同，但分析数据流图的理解角度不同。

第一种方法是变换分析法。这种方法把整个程序看成输入处理、输出处理、变换控制三个大模块。在一层数据流图中，根据数据流与变换的形状关系，把变换分进这三种大模块里。每一个变换属于大模块里的一个小模块。

用这种方法画结构图要按以下步骤：首先，画一个主控模块（MC）、输入模块（MI）、输出模块（MO），变换控制模块（MT）。MC在最上面，MI、MT、MO分别画在下面，与MC连线。之后，再一层数据流图中画两条边界，把一层图分成三部分。最后，把数据流图“旋转”一下，把对应的数据流和变换模块都写到大模块下方。只要有了数据流图，划分了边界，就可以立刻把数据流图转换成结构图。看了书上的例子就能很快理解这个转换方法。

第二种方法是事物分析法。该方法是思想是找到一层数据流图中有多条路径的变换，把这个变换当成事务中心。所有的输入在经过预处理后经过事物中心进行变换，没有输出模块。

用这种方法画结构图有以下步骤：首先，在一层数据流图中找到事物中心，把事物中心的输入部分划分到一起。之后，画一个主控模块（MC）、输入模块（MI）、事物调度模块（该模块名就是选择的事务中心的变换名）。最后，用和变换分析法类似的方法把数据流图“旋转”一下，在大模块下补上小模块。

当然还有第三种方法，叫混合分析法，就是把两种方法综合一下，变换分析法的输出模块改成事物调度模块。

程序流程图

这是高中就学过的工具，用以描述程序设计的三种结构（顺序、分支、循环）。

圆矩形表示开始结束，方矩形表示是操作，菱形表示判断，箭头表示控制流方向。

盒图

盒图也是用来描述程序设计的。相比程序流程图，盒图没有随意的控制流，能够更好地划分数据的区域。

整个盒图画在一个方形中。具体形式看后面的示例。

问题分析图

问题分析图（PAD）也是用于程序设计的图。它也能规避控制流的任意性。

PAD从上到下是流程，从左到右是模块的细分。

例：

把代码转换成盒图和PAD。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

A;
B;
if (C1)
{
	while (C2)
	{
		if (C3)
		{
			D;
		}
		else
		{
			E;
		}
	}
}
else
{
	do
	{
		F;
		if (C4)
		{
			G;
		}
		else
		{
			H;
		}
	}
	while (C5);
}
if (C6)
{
	I;
}

（原题来自课本的一个流程图）

解：

判定树

判定树用来表述复杂的条件判断。由于if语句本身符合树结构，用一棵树来表示判断语句是非常自然的。

判定树画起来很简单，左边是条件，每个条件都可以分叉成多个子情况里的条件。最右边是该分支下的结构。

判定表

判定表和判定树作用一样，也是设计复杂条件判断的工具。

判定表的行分成两部分，一部分是条件，另一部分是动作。判定表的每一列表示一个条件和动作的组合情况（条件用T、F表示，执行的动作打个勾）。

一些后续的事情

由于我没有管理好精力，我没有对后面几章做系统的复习。还好，考试没有考很多死板的内容，考的东西偏向理解，我几乎都能答得上来。有一点要特别提一下：考前说好数据流图只画一层，考试的时候要求画两层。

计算机组成原理考试结果

和写论文一样，讲完了方法以后，要展示一下实验的结果。我在运用了带有周弈帆特色的费曼学习法进行计算机组成原理的复习后，也要讲一下考试的结果，以佐证方法的高效性。

考试前天结束，现在考试的分数还没出。我先从我自己的感觉谈一下考试的结果和收获。考试分数结果等出了分再更新。

个人感觉结果

考试考察的知识点果然全是复习PPT里的。复习PPT里用红字标出的内容全部出了题目。很不幸，我没有把复习PPT涉及的细琐知识点都过一遍，填空有3题左右完全没听过，选择有1题完全没听过。但我对剩下的题目涉及的知识点非常熟悉，解起题来十分顺畅。说实话，在这门课里我学到的东西并不多。但我也不搞硬件。我认为我在这门科目上的学习成果符合我对自己的要求，也符合学校对学生们的要求。

从复习时间安排上来评价我这次考试。学校所有课程结束后，我剩下了3天时间复习。虽然第一天我没有调整好生物钟，昏昏沉沉地过去了。但在接下来的两天半里（考试是下午考），我快马加鞭，聚精会神地进行复习。把对每章知识点的熟悉程度提升回写那一章作业时的程度。最终，虽然有些小赶，时间略显窘迫，但我还是比较完整地复习了所有内容。我在时间安排上虽有失误，却亡羊补牢，为时未晚。

从复习方法上了评价我这次考试。我和以前一样，用的是费曼学习的思想，也就是用自己的话去描述知识，从而找到理解的漏洞。其实我之前概率论和计算理论也是用了这种方法，但效果不佳。概率论那次应该是我对知识本来就比较熟悉，不应该重新理解知识，而应该做题巩固知识的理解；计算理论那次我只写了一章，实在太累了没有接着写下去。我坚信不是方法有问题，而是我之前做得不够好，所以这次依然采用了这种复习法。恰好，计算机组成原理考试强调知识的基本理解而不强调知识的熟练应用，这种复习法完美契合了考试的要求。我也坚持了下来，把主要章节都做了一次复习。可以说这次考试方法选择得非常恰当。不过话说回来，我似乎也没有发明出第二种复习方法，好像“选择”一词并不恰当。但是，用这个词更帅一些。

从复习策略上里评价我这次考试。我既没有像无头苍蝇一样，拿着课本乱翻乱看；又没有像复读机一样，逐字逐句地去从干巴巴的课本中背下每一句话。我去学校网站上下载了考试复习的PPT，非常精准地命中了大部分的会考到的知识点。与此同时，对于我上课的时候理解过一遍的知识点，以及每次课后作业所涉及的知识点，我又认真地复习了一遍。可谓是双管齐下，两手都抓，两手都硬。最终，虽然算有遗策，但大局难改，考试的大部分题目对我来说就像小学数学一般简单。在有限的时间里完成复习，复习策略的正确选择是成功的关键。

虽然考试结果没出，虽然我可能惨遭打脸，但我依然敢于给自己下断言：我这门学科成绩85起步，封顶95。

如果最终成绩有所偏差，那么我也不亏。在学这门课的时候，我学到了课本内的知识，培养了课本外的学习能力。分数不能代表一切。你若是只看分数，你就输了。要看到分数之外的东西。

希望二月出成绩后，我能看到一个比较好的结果。

考试结果

最后我考了88分。没考到90分满绩还是有点遗憾的。

考试的结果证明这次的整体复习效果确实还可以，但是由于时间不足的原因，我没有仔细去看每一个知识点，这些细琐的知识点应该是我失分的地方。

我不希望以后再出现这种考试，所以我就不写我以后应该怎么怎么做了。

去百度查课后答案的时候，发现这本教材至少11年没有发生改动。虽然这本书涉及都是一些原理性的东西，和时代无关，这门课对我们来说也不过是一门学过就忘的课，但我还是觉得这种“万年不变”的教学态度有问题，需要加以改正。

计算机组成原理复习：第六章 中央处理器

本章主要在讲CPU（中央处理器）。本章先整体介绍了CPU的组成结构、性能参数等内容，之后稍微介绍了CPU的硬件实现，再具体介绍了CPU的整个控制工作原理。由于CPU执行指令的时候涉及一些微操作，本章接着又进一步介绍了微操作的有关内容。介绍完了CPU的基本工作原理后，本章又介绍了一个简单CPU应支持的操作。最后本章介绍了CPU相关的新技术。

CPU实际上包括运算器和控制器。运算器主要涉及的计算方法在之前章节已经介绍过。这一章实际的重点是控制器的实现。

考试重点应该是放在对CPU执行指令的过程和微操作的原理上。要理解CPU指令的执行过程，对于一个给定的操作，要能够写出CPU每一步在做什么。

和上一章一样，我只对比较重点的地方进行复习。

CPU的基本组成

其实CPU的组成主要是讲CPU里有哪些寄存器。寄存器可以分成通用和专用。专用的寄存器是只有固定用途的寄存器，而通用寄存器可以根据实际需要使用。可以看成预定义常量和变量，或是操作系统中的系统内存和用户内存。

专用寄存器有：

• 程序计数器PC
• 指令寄存器IR
• 存储器数据寄存器MDR
• 存储器地址寄存器MAR
• 程序状态字寄存器PSWR

这里只是提一下这些寄存器的名字，后面讲CPU的控制原理的时候还会提到这些寄存器，到那个时候才能理解这些寄存器在干什么。这里提一下就当是在声明变量。

处理寄存器外，CPU中还有一个指令译码器IR，用于识别指令中的操作码。还有一个控制单元CU，大名叫微操作信号发生器。它是CPU控制功能的核心。

CU的实现方式在复习PPT中被列成了重点，我不得不看了一下。CU的实现大致分两种，组合逻辑控制器和微程序控制器。其实控制的微操作和程序设计一样，也是模块化的。组合逻辑控制器追求速度，却无法拓展，难以调试，难以实现自动化设计。微程序控制器的特点与之相反。（我没搞懂什么是自动化设计）

除了这些外，CPU中还有ALU，但这不是本章的重点。

时序系统

时序系统是CPU的工作基础。和游戏一样，CPU的工作也有基本的时间单位。这种和最小时间单位有关的系统就是时序系统。

这里自顶向下地介绍整个时序系统。指令周期是指从取指令、取数到完成指令整个过程需要的时间。各种指令所需的指令周期不同。指令周期会拆成机器周期（CPU）周期，每个机器周期干一个特定的活，比如取值周期、取数周期。机器周期又要完成若干微操作，每个微操作占用的时间叫做节拍。每个节拍最终由几个脉冲组成。脉冲是最小的时间单位。

指令执行过程

这一部分是CPU控制原理的核心。

指令执行过程分成三个阶段：取指令阶段、分析取数阶段和执行阶段。

取指令阶段

从宏观上来讲，这一阶段把指令从主存中取出来并存到指令寄存器中。具体来说分以下几步：

1. (PC)->MAR
2. CU向存储器发读命令 Read
3. 取出的指令存到MDR中 M(MAR)->MDR
4. 把MDR的内容送到IR中 (MDR)->IR
5. PC自增 (PC)+1->PC

分析取数阶段

根据指令，取操作数。由前几章的内容可知，指令中的操作数可能表达得十分“晦涩”，可能要通过多次间接寻址才能得到。

如果操作数不用寻址，那么就不用进行此阶段。

比如要取@R0，即以R0的值为地址，到主存中取数。那么操作有以下几步：

1. (R0)->MAR
2. Read
3. M(MAR)->MDR

执行阶段

现在我们有了函数，有了函数参数，接下来的任务就是执行指令并将结果保存。

比如把数相加的执行阶段指令有以下几步（MAR已经是目标存储寄存器的地址）：

1. (R1)+(Y)->Z
2. (Z)->MDR
3. Write

比如转移A步指令的执行阶段有以下几步：

1. (PC)->Y
2. Ad(IR) + (Y) -> Z
3. (Z)->PC

微程序原理

基本概念介绍

之前CPU执行的每一步操作，都叫做微操作。对于指令来说，这些微操作都是不可再分的操作。但是从微操作的角度来看，微操作还可以分成很多个更细致的操作，比如打开某个逻辑门等。这些更细致的操作叫微命令。不同的微操作之间可能会公用相同的微命令。引入程序设计的思想，微命令的重用和模块化非常关键。微程序控制的思想也因此被提出来了。

一个机器指令就对应一个微程序。一个微程序里可以分成多个微指令，微指令就是一个一个函数。和CPU的指令类似，微指令也分为操作码和地址码。但微指令的地址码只包括下一条要执行的微指令的地址，而不是存数据的地址。在微指令中，微命令就是原子操作，和程序中的语句相同。

微指令编码

微指令编码指对微指令的操作码编码。操作码译码的结果是得到一个01序列，表示执行哪些微命令。

最显然的两种编码法是直接编码法和最短编码法。前者令操作码每一位都表示一个微命令是否执行，后者进行完全编码，每次只能产生一个微命令的输出。由于微命令可以并行，但又不是每种操作都能并行，因此第一种方法编码长度过长，而第二种方法无法进行并行。

一种折衷二者的方案是：事先知道哪些操作不能并行，把这些操作分成一组，进行完全编码。整个操作码就被分成了一个一个完全编码的字段。

课后有一道这方面的题目。考试估计会考。

组成部件

• 控制存储器CM，存了一堆微程序
• μIR，微指令寄存器，和IR类似
• 微地址形成部件，用于形成初始微地址和后续微地址
• μMAR，微地址寄存器，和MAR类似，但不是从内存而是从CM中取指令

比较可惜的是，从这章开始，这门课的内容就讲得很不细致了。很多内容只能从一个很高的层次进行介绍，无法深入细节。一旦讲到了偏硬件的东西，由于难以进行实践，又和数学等理科知识关系不大，和电路等学科关系密切，课本就只能划水。

计算机组成原理复习：第五章 存储系统和结构

本章先从整体上介绍了计算机的存储结构，再着重介绍主存的存储思想以及具体的主存种类。之后讲了多个主存储器是如何构成一个系统的。最后稍微介绍了一些其他cache、虚拟内存等内容。

我只针对复习PPT提到的重点和我们课后习题涉及到的内容进行复习。

主存储器的组织

这一节围绕主存是如何存储数据的，介绍了主存储器整体的工作原理，和前面编码的内容有一些关联。主存储器本身的结构在后面的小节里介绍。

存储单元

数据的最小单位是位，被叫做存储位。按位存取效率太低，多个存储位在一起就成了存储字，这是访问的最小单元。存存储字的结构叫存储单元，地址和存储单元是一一对应的。大量存储单元构成了存储体。

主存部分技术指标

存取时间

执行一次读或写操作的时间。

存取周期

两次执行访问操作的间隔时间。因为除了完成存取操作外，主存内部还有一些其他的操作，存取周期一般略大于存取时间。

带宽

等于主存等效工作频率乘主存位宽。

数据在主存的存放

可能出现主存的存储字长比较大，而计算机传来的数据比较小的情况。比如主存的存储字长是64位，而计算机传来的数据可能是8~64位的。如何存这些数据是一个问题：

如果每个数据紧挨着存，那么主存空间没有浪费。但是万一一个存储字剩余容量较小，突然来了一个64位数据，那么这个数据就得拆成两半，存在两个存储字里了。

如果每个数据都存在一个存储字里，那就太浪费了。如果所有数据都是一个字节，那么大量的空间要被浪费。

因此，边界对齐的存取法被提出。这种方法综合了以上两种方法的优点。比如，在存储字为64位的主存储器里，64位数据只能从一个存储字开头从，32位数据只能从半个存储字开头存，16位位数据只能从四分之一个存储字开头存。

主存储器结构与工作原理

这一节前面讲了很多和电路的东西，我们缺乏基础知识，学不懂。我只复习DRAM的刷新以及RAM芯片的一些参数。

DRAM的刷新

由于DRAM电路的问题，需要经常刷新才能维护数据。

注意，刷新是指对每个芯片的刷新。芯片一般会排成正方向阵列，比如16K的芯片，就会排成128*128。之后谈到的按行刷新，这个“行”指的就是128。刷新就等于读了一遍，因此刷新周期等于读写周期。这个刷新周期是以行为单位的。

为了提高整体的工作效率，有几种不同的刷新策略：

集中刷新

在最大允许的刷新间隔内，把工作分成两个阶段：读写操作和刷新。在所有读写操作执行一段时间后，集中刷新所有的存储芯片，再继续读写。等于说每个刷新间隔构成了一个循环的工作周期。

分散刷新

每次读或写之后，立刻刷新。也就是读写操作和刷新绑定。这样可以保证内存正常，但是刷新过于频繁，读写周期变长，没有充分利用最大允许刷新间隔

异步刷新

异步刷新综合以上两种方法，把主存按行分组。先做一会儿读写操作，就停下来刷新第一行；再做一会儿读写操作，就刷新第二行……。在最大允许刷新间隔内，把所有行都刷新一遍。

课本上对以上三种方法都画了一个图，看了图就很好理解。

RAM芯片引脚

• 地址线
• 数据线
• 片选线 CS
• 读写控制线 WE
• Vcc 电源
• GND 地

其中片选线的意思可能不能通过字面来理解。片选线决定该芯片是否工作。

上述引脚的字母打的不是很准确。这篇文章我不打算渲染公式，所以就简单写一下。

先复习一下这些引脚是因为之后的内容会用到。

主存储器的连接与控制

本节讲的是多个主存储器是如何协作的。

主存储器扩展

存储芯片一般比较小。为了得到一个较大的主存储器，需要把存储芯片连接扩展。

先提一句，芯片用数据量和数据位数来表示。比如64K X 1就是地址64K，数据只有1位的芯片。

考试主要考察的就是画图。注意，一堆线要画成粗的线。箭头表示数据传输方向，数据线的箭头是双向的，其他线的箭头是单向的。

有以下三种扩展方法：

位扩展

用一堆地址一样的芯片扩展位数。

地址线、片选线并联进每一个芯片。

数据线每一根接一个芯片。

以64K X 1拓展到64K X 8为例：

地址扩展

假设一堆芯片位数相同，但存储量不够，可以把它们并在一起扩展地址

这种方法的思想是，地址线的高位用来片选，也就是选择使用那片芯片；低位直接输入芯片。

此处看书上的图很好理解。

字和位同时扩展

同时执行上面两种扩展。

看书上的图很好理解。

存储芯片的地址分配与片选

上一节地址扩展中，出现了如何分配地址这个问题。上一节是用一个译码器来分配地址高位，得到片选结果。本节具体介绍了分配地址时存储芯片片选的方式。

线选法

地址高位的每一位直接就代表是否选中某个芯片，而不经过移码。由于片选时0表示有效，因此用于片选的地址高位只能有一个0。

全译码法

就是上一节的方法，把高位输入译码器进行译码，输出选择哪一个芯片。有可能输入的地址组合量大于需要的量，比如输入9位，但只有4个芯片。这个时候译码结果只有4个是有效的，其他508个都是无效的。

　部分译码法

在全移码的基础上，只把部分位输入译码器。比如要选择4个芯片，只输入2位就行了。这样的话地址的高位完全用不到，会产生地址重叠。

和上一篇文章一样，这篇文章的很多内容是我学这门课的时候写的。

计算机组成原理复习：第四章 数值的机器运算

本章讲了计算机电路是如何实现运算。计算机中的运算可以整体分成数值计算和逻辑计算。无论多复杂的数值操作，都可以用加减乘除来实现，因此本章讲了加减乘除四则运算的实现；逻辑运算是计算机运算的基础，本章也介绍了与、或、取反等逻辑运算。最后本章讲了运算器的一些具体实现。

进一步来划分一下本章的结构。减法运算是靠加法实现的，因此本章先重点介绍了加法器的实现，之后讲了如何用加法器来实现加法和减法。由于乘除操作基于加法和移位，因此本章之后介绍了移位操作的实现，再介绍了定点乘除操作的实现。如第二章所述，浮点运算实际上基于的是定点小数和定点整数，浮点的所有运算也可以由定点的计算转换而来，因此再之后本章才介绍了浮点数间的计算。十进制做为数值计算的一种特例，和之前内容的关系并不是很紧密，在所有基本运算的实现介绍完之后才介绍。运算部分结束后，本章又稍微提了一下逻辑计算，因为它太简单了。最后是一些在本课中价值不大的运算器的实现。

本章各节间的逻辑关系是非常紧密的，当你整理出本章的依赖关系后，一张依赖图就能出现在你的脑海中。可惜这里位置太小，我画不下。

说实话，我觉得本书这一章的部分内容更应该放到数字逻辑中去讲。这一章有不少涉及电路的知识，很多知识都属于学科间的边缘交界地带。但这一章后面又多了很多和具体电路无关，介绍电路实现算法的知识，这些知识放进计算机组成原理倒也没错。我觉得本书这一章结构编的不是很好，前面全加器的电路实现应该放到其他学科去，整章就介绍抽象的电路实现，没必要讲到电路的优化上，保持知识的深入程度相似。

基本运算（加法）电路实现

由于所有其他运算可以用加法来表示，所以加法被叫做“基本算数运算”。

加法器简介

全加器

输入$A_i$，$B_i$，进位$C_{i - 1}$，输出当前结果$S_i$和进位$C_i$。

具体原理在数字逻辑中已经学过了，用两个半加器就能实现。

串行加法器

只有一个加法器，移位寄存器不断地把每一位放到全加器里计算。这种方法实在是太慢了

并行加法器进位的产生与传递

由于并行加法器比较复杂，这里单独开了好几个小节来讲。

并行加法器就是把一堆全加器放在一行，上一个的进位输出放到下一个的进位输入里。数字逻辑中也学过了并行加法器。

并行加法器的问题在于，当前位做运算时，需要等待上一位运算完成，获取进位输入。因此，并行加法器看似结构上并行，实际上运算速度还要受到产生和传递进位的速度的影响。

为了想办法提高运算速度，本节分析了并行加法器进位的产生与传递的本质。

进位的表达式为：

$C_i=A_iB_i+(A_i \bigoplus B_i)C_{i - 1}$

其意思是，如果要产生进位，要么两个当前位都是1，要么是两个当前位有一个是1，且上一位有进位。

说实话，后面那个异或运算增加了理解的难度。明明那个异或写成或的话，这个式子也是成立的，读起来也更加清晰。不知道是不是异或门比或门更快的原因。老师和课本都没有对这里进行讲解。

为了方便后面的分析，用更简单的形式来写上面的式子

$C_i = G_i + P_iC_{i - 1}$

这个式子暗示$A_i,B_i$对后面的分析毫无影响，我们只关系进位间的关系。

并行加法器进位的优化

并行进位法

根据之前的分析：

$C_1 = G_1 + P_1C_0$

$C_2 = G_2 + P_2C_1$

把第一个式子代入第二个式子得：

$C_2 = G_2 + P_2(G_1 + P_1C_0) = G_2 + P_2G_1 + P_2P_1G_0$

可以观察到，$C_1$消失了。只需要最初的$A_1,B_1,C_0$，就能直接得到第二位的进位，而不需要等待第一位的进位输入。

如果反复利用这种方式，那么无论是第几位的进位输出，都可以用初始的几个量算出来了。由于逻辑门是可以并行的，无论这个式子多长，只需要花费一次计算与的时间和一次计算或的时间就可以完成 进位输出的计算，时间复杂度是$O(1)$。设与门、或门的延迟时间位$ty$，那么这种方法耗费的时间是$2ty$。

顺带一提，之前要等待上一位进位输出的作为输入的并行加法器中，花费的时间是$2nty$，其中$n$是参加运算的数的位数。时间复杂度$O(n)$。

但是，时间复杂度是下降必然引起空间复杂度（电路中门的数量）的上升。据肉眼观察，之前的空间复杂度是$O(n)$，但新方法的空间复杂度是$O(n^2)$。如果所有位都用新的方法，那么电路的结构以及造价会飞快地上升。对于一个位数很长的数，直接使用这种并行进位法是不合适的。

分组并行进位

并行进位法在位数很大的时候就不合适了，但这种方法依然有利用的价值。4位数的并行进位电路是可以接受的。如果我们把一个很长的数每4位看成一组，分别放进4位的并行进位电路，那么电路的进速度还是得到了优化了的。准确来讲，应该是快了4倍。这种电路叫做4位先行进位电路（Carry Look Ahead，CLA）。其耗费时间是$\frac{n}{2}ty$。

可以发现，我们把每四位看成了一个组。这个组的概念，和原来每一位的概念是类似的。原来每一位的运算要输入$A_i,B_i,C_{i - 1}$，输出$C_i$；现在每一组输入$A_i \sim A_{i+3},B_i\sim B_{i+3},C_{i - 1}$，输出$C_{i+3}$。原来的位变成了现在的组。这实际上是一个递归的过程。

我们可以把4位当成一组，是不是也可以把几个组当成一个大组并行运算呢？

根据公式：

$C_4 = G_4 + P_4G_3 + P_4P_3G_2 + P_4P_3P_2G_1 + P_4P_3P_2P_1C_0$

和之前一样，把前面不含$C_0$的看成一个整体，含$C_0$的看成一个整体。可以得到：

$C_4 = G_1^+P_1^C_0$

因为我们每4位分成了一组，所以$C_8$也有类似的式子：

$C_8 = G_2^+P_2^C_4$

同样，如果把$C_4$代入，那么$C_8$也只含$C_0$这一个变量了。现在$C_4,C_8,C_{12}…$都可以并行计算出来了。为了产生$G^P^$，原来产生$C_4,C_8,C_{12}$的CLA电路要修改，把输出从$C_4…$改成$G^P^$。这种改过的电路叫做成组先行进位电路（Block Carry Look Ahead，BCLA）。

新的加法器原理和之前一样，但和之前不同的是，开始的进位输入只有$C_0$，而BCLA需要$C_4,C_8,C_{12}…$。在得到每一组的这些输入后，我们才能把每一组组内的结果算出来。

总结一下，新的电路分了三步：第一步，所有的$G^,P^$是从$G,P$中计算而来，需要额外花$2ty$有关计算所有的$G^,P^$；第二步，根据$G^,P^,C_0$，计算出$C_4,C_8,C_{12}…$，这种组内的运算用到的是开始的并行加法器，也要花费$2ty$时间；第三步，根据$C_4,C_8,C_{12}…$，计算每一组内部的进位，时间同样是$2ty$。总共花费了$6ty$的时间。特别地，由于$C_0$在一开始就已知，第一组组内的计算可以在第一个$2ty$里算出来。

这部分内容比较复杂，照着课本上电路的结构图能够更快地理解这些内容。

定点加减计算

原码

原码十分死板，因为只有原码的绝对值才有意义。而且在进行加减的时候，还要考虑两个数前面的正负号，才能决定绝对值是加还是减，非常麻烦。

首先需要一个逻辑电路，通过两个数的符号位和当前的运算得到绝对值进行的是加还是减运算。

对于绝对值加，直接加。对于绝对值减，减数要变补再加。

如果最终加的结果的负数，还要再求一次补，把负数转化成它的绝对值。结果的符号位也要取反。

补码

加法

由于补码中负数的表示是在模$2^n$意义下的,因此直接带上符号位计算就行了。

减法

把减数取负再做加法即可。问题是怎么把一个数取负。

口诀教的是：连同符号位一起取反，末尾+1，就得到了一个数的相反数。

我觉得按求负数补码的方式，倒着想也没错。正数就和上面一样取反+1，负数-1再全部取反。

符号扩展

符号扩展就是一个位短的数如何正确强制转换成一个位长的数。方法很简单：正数补0负数补1。

补码溢出

计算机运算都是在模意义下的。运算结果绝对值比模数/2大，就会发生溢出现象，运算结果因为无法表示而变得不正确。

只有同号加法才会溢出，因为异号加法绝对值一定变小。

比较简单的判溢出方法是：在当前符号位左边扩展一位，就是整数补0负数补1。之后用拓展过的数进行计算。如果两个符号位是10，表示负数溢出；符号位是01表示正数溢出。

补码运算的电路

这个章节划分得很没有条理。不过这一小节也不重要，课本写得不详细，老师也没讲几句。

移位

移位是乘除法的基础，所以在这一节先介绍一下。

移位规则

移位规则十分简单，用过C语言的移位运算的话很容易就能学会。

宏观上来看，不管符号位如何，左移要让数乘2，右移要让数除以2。

正数左右移补0，负数左移补0右移补1。

要用电路实现移位，要么用移位寄存器，要么用移位器进行计算后保存计算结果。移位操作就是一个多路选择器，等于是输入到输出的一个一对一映射。

舍入操作

右移时，有些数位会多出来，需要舍弃。舍入方法有：

1. 恒舍：什么都不管，直接全舍去。
2. 冯诺依曼舍入法：什么都不管，舍去，剩下的数最后一位置1.
3. 下舍上入：被舍的最后一位（保留的最右边的一位的右边一位）是1则前面保留的部分+1.
4. 查表舍入：把方法3放进一个表里，减少++成本。

定点乘法计算

方法中的“一位“、”两位“把乘除法计算步骤拆开后，每次做加法是逐位考虑还是每两位考虑。

原码一位乘法

和加法一样，原码做乘法的时候需要把符号位和绝对值分开处理。

符号位很好处理，做一个异或就行了。

绝对值相乘的步骤和我们列竖式手算乘法是一模一样的。由于二进制里只有0和1，因此每一步中要么加上被乘数，要么不加。这种是否关系刚好和逻辑电路相符合。

但是，我们列竖式的时候，每次新算出来的部分积都会往左一位，电路不方便做这样的操作。因此，电路每次把旧的部分积右移，以代替新部分积左移。

只要看一眼课本上的例题就能快速理解这个过程

补码一位乘法

补码中由于符号位参与运算，其计算过程更加复杂一点。

校正法

第一想法是把被乘数的符号位分开，即先对被乘数后面的部分进行计算，如果被乘数符号位是1（是负数），就再加上一个乘数的相反数乘上被乘数符号位。这种方法加入一个特判，电路实现很不方便。

Booth乘法

有人发现补码乘法有一个特殊的性质：

看完前几行后，就能发现这个性质了：补码乘法可以看成被乘数补码乘上乘数的相邻位比较结果码。注意最后一行，$Y_{n+1}$本来没有这个数，但在计算的时候为了统一，我们假设有这个数，并把它初始化为0。

有了这个公式，就可以直接进行补码乘法了。和之前一样，被乘数不断右移，但这次要看乘数最后一位和附加位的比较结果（附加位就是前一位，初始化为0）。如果当前位和附加位一样则不加；如果附加位是0这一位是1则减掉被乘数；如果附加位是1这一位是0则加上被乘数。

补码两位乘法

两位乘法就是每次考虑乘数的两位，加快乘法速度。

乘法还是用Booth法，但是这次比较位有些复杂。但只要记住公式会化简成$(Y_{i+1}+Y_i-2Y_{i-1})$就行了。记住这个公式就能记住每一位权是多少

定点除法计算

和乘法一样，除法的计算思路也由竖式中得来。同样，我们先从普通的原码除法，推广到补码除法。

原码除法

同样，考虑原码时我们只关心绝对值部分。

根据正常的列竖式除法，如果每次被除数比除数大，就商1，被除数减去除数，除数右移。在电路中，除数右移不方便，改成部分余数左移。这种比较法要用到比较电路，很麻烦。

一种想法是，每次不管被除数和除数，先减了再说。如果减成了一个非负数，就正常商1；否则，若减成了一个负数，就说明这次不够减，商0。如果这次把除数又加回来的话，下一步操作我们又无脑减一次除数。这次加回除数和下次再减一次除数可以合并成一个操作，就是忽略本次的负数，下次加一次除数。也就是说，若$r_i = 2r_{i - 1} - Y$小于0，则本次操作先不恢复这个数，而是令$r_{i+1}=2r_i+Y$，因为$2r_i+Y=2(r_i+Y)-Y$,其中$r_i+Y$是回复了余数的结果。

补码除法

补码中，要考虑到负数，算法复杂了一些。

仔细一想，算法中部分余数（包括被除数）一直在变，只有除数的值没有变化。所有的符号都应该是相对于除数而言的。

也就是说，原码除法可以看成补码除法的一种特殊情况，这是除数一直是正数。而当除数变成负数后，如果被除数是正数，说明”不够减“，商0；否则”够减“，商1。也就是说，我们要修正之前的加减交替法，把判断一个数是否不够减的一句擀成是否和除数异号。

规格化浮点计算

浮点加减

设：

浮点数加减前要对齐阶，阶小往阶大的移动。先计算$\Delta E = E_A - E_B$。$\Delta = 0$若等于0则不用管；若大于

0则B右移；否则A右移移。之后尾数加减。

由于尾数要满足规格化数（科学计数法）的要求，需要对尾数加减结果进行规格化。

假设尾数用双符号位表示。对于尾数计算结果的下列情况：

1. 00.1XXX | 11.0XXX 符号位和首位不同，满足规格化的要求
2. 00.0XXX | 11.1XXX 符号位和首位相同，绝对值小了，要把尾数放大（左移），阶码每次—。
3. 01.XXXX | 10.XXXX 双符号位仅在此处发挥作用。双符号位不同说明发生定点溢出，浮点超1。需要把尾数缩小，阶码++。

浮点相乘

阶码相加（有移码则要减掉），尾数相乘。

尾数大小一定落在$[\frac{1}{4}, 1)$,仅在尾数小于二分之一的时候需要进行左移，阶码—。

浮点相除

为了使尾数规格化，要保证被除数的尾数的绝对值比除数小，即$|M_A| < |M_B|$。由于二者本身就是规格化数，这个操作至多操作一次。

之后阶码相减，尾数相除。

十进制加减

没什么需要学的内容。十进制每一位都用4位二进制表示，每4位单独运算即可。

运算器实现

这一节内容又很偏硬件实现，应该不会去考。

反正我就记住了两种芯片，74182对应CLA电路，74181对应BCLA电路。

注意事项

本节有很多运算，动手把这些运算算一遍才能保证自己完全理解了这些概念。

我在做题的时候发现了一些坑点：

• 原码乘法最后还要再移位一次，补码乘法不需要。

这篇文章的内容主要是上课的时候写的，复习的时候我又修改了一些地方。

计算机组成原理复习：第三章 指令系统

指令对应机器语言，是计算机中最基本的命令。

本章先整体介绍了指令的结构，包括了操作码、地址码两个部分，并简要介绍两者所占长度的问题。之后，本章对地址码和操作分别进行了进一步介绍。先是介绍了地址码的具体知识，因为地址码可能不表示一个具体的地址，而是通过一些间接的方式来获取地址。特别地，有一部分存储区构成了栈结构，有一些操作专门是针对堆栈的。然后是一些具体的指令操作。最后，本着从普适性到具体性的思想，本章介绍了指令集中应该具有的操作，以及一些具体的指令集的发展过程。

指令格式

指令就是一段二进制代码。指令可以分成两部分，前一部分是操作码，后一部分是地址码。我觉得可以把操作码看成函数名，地址码看成函数参数。准确来讲，地址码是表示数据的代码，用地址码获取数据的方式再寻址技术部分会提到。

地址码结构

函数的参数可以有多有少。我们默认讨论双操作数系统。在指令这个“函数”中，最多支持4个参数。可惜的是，这个函数只支持默认参数来实现重载。也就是说，所有的指令实际上都会需要4个参数，但有些参数可能存在其它位置（可以看成一个全局变量），或者某些操作不需要所有4个参数。所以指令实际传入的操作数数量可能是0~4个。

指令传入的4个参数是：第一操作数地址，第二操作数地址，运算结果地址，下一条指令的地址。和C++的默认参数一样，每少输入一个参数，就代表最后的那个参数被设为了默认值。

3参数指令默认将下一条指令的地址设为当前指令地址+1。2参数指令把运算结果到第一操作数的地址。1参数指令把另一操作数存在某一个寄存器里。0参数指令一般是堆栈操作，把栈顶元素当成参数来进行操作。

操作码结构

操作码的长度可以固定，也可以不固定。后者可以节约空间，因为多地址的操作中地址码的长度较长，可以分配比较短的操作码。

显然，和哈夫曼编码一样，不能有一个操作码是另一个操作码的前缀。

寻址技术

寻址指获取操作数或指令的地址。实际上，这一节不仅讲了如何寻址，还先讲了如何编址。

编址

编址就是给寄存器、主存或IO设备中的存储单元编号，这样通过一个编号就能唯一地找到存在某处的一个数了。

编址最重要的是编址的最小单位。如果编址最小单位是字，那么在一个字长16位的系统里，你只能通过地址区分每16位数，而不能唯一确定数据某个字中的哪个地方；如果编址最小单位是字节，那么你就可以区分每8位的数字；如果编址最小单位是位，那么你可以精确地访问每一位了。

显然，编址最小单位是位的话，地址就会变得非常长了。还按字节编址比较好一些。在C语言中，我们可以得到每一个char的地址，这大概是字节编址的一个体现。

编址长度和主存的字长不是一个概念。

寻址

主要讲怎么寻找数据的地址。

最简单的是把数据直接放在指令里，这样不需要取通过地址来访问数据了。也就是往函数直接传了个值。但这样传进去的值的位数可能不够多。

还可以传数据的地址，也就是传指针。有时为了方便，还可以寻两次地址，也就是传指针的指针。数据可以在寄存器里找，也可以在主存里找，共$2\times 2 =4$种方法。这里还要多提一句，寄存器间接寻址指的是第一次在寄存器里找地址，第二次还是在主存里找。

此外，为了方便地获取一段连续的数据，还可以用基础地址加偏移量的方式获取数据。用C语言来写的话，就是

*(p + i)。p表示基础地址，i是偏移量。如果i在寄存器中，就叫做变址寻址；如果p在寄存器中，就叫做基址寻址。理论上这两种寻址方式表示的意思都是一样的，硬件实现方式也可能是相同的，但二者使用上有一些细微的差别。由于用户希望改变对于某个基址的偏移量i，因此变址寻址是一个面向用户的操作。

此外，在基址寻址的基础上，基址p可以来自程序计数器。这种寻址方式叫相对寻址。

指令类型

数据传输

数据是在寄存器和主存之间传输的，理论上存在4种不同起点和重点的传输指令。把寄存器看成0，主存看成1，有序对<0,0>,<0,1>,<1,0>,<1,1>就可以表示4种数据传输的指令了。

此外，还有对堆栈的PUSH和POP指令。但是，这两种指令本质上也是对于主存的操作，并不能称为最基本的操作。

除了单向传输，还可以交换两个位置的数据。

运算

包含C语言中的一些基本运算。比如加减乘除模、按位逻辑运算、移位运算。但书中没有具体讲这种指令的结构（比如有几个操作数）。

流程控制

　转移

转移有两种：有条件转移和无条件转移。有条件转移用于实现条件语句，而无条件转移让程序结构更加灵活，不必受到顺序存储的束缚。

转移都要定义转移到的地址这一参数。对于有条件转移，还要把比较条件作为参数。

子程序调用

一个程序通过一些指令，可以调用另一个程序。只是根据调用关系，把被调用的程序叫做子程序。

程序本身就是被调用的，这种调用其他程序的关系中体现了递归的思想。

子程序调用也可以让程序不按顺序执行，而是跑到另一个地方去执行。在这一点上，它和转移十分类似。为了搞清这两个概念，要知道这两个概念间的区别。

子程序调用与转移的区别

1. 子程序有“返回”这一操作。在调用了子程序后，一定要进行返回，返回到调用子程序的下一条指令。
2. 机器中应该有“程序”这个概念，也就是说不同程序之间是有明确的界限的。转移只能在当前程序中转移，而调用子程序会跳转到子程序的开头。

既然调用子程序的时候要返回，那么机器必须存储返回的地址。事实上，每调用一次子程序就会产生一条返回地址信息。有多种存储返回地址的方法。

返回地址的存储

1. 存到子程序的开头。我觉得这种方法很蠢，递归调用完全不可行了。但如果没有递归的话，这样设计节约了存储空间。
2. 先存到寄存器中，再让子程序把寄存器的内容存到内存中。这样不错。
3. 存到堆栈中。这种方法和2的本质是一样的。函数调用本身就类似栈的行为，用栈模拟的话更加自然，更加易于操作。但是，我觉得这种分类还是不够清楚。方法2里，你把东西存在内存里，在内存里也可以构成一个堆栈。方法3理论上是方法2的一个改进，而不是完全没有交集的两个方法。

返回指令

返回指令明明是和子程序调用配套出现的，不懂书上为什么要单独列出来。

输入输出指令

输入输出往往要用到除主存之外的存储区域。因此，IO指令可以分成两类。一种是IO地址单独编址，从0开始命名；另一种是把IO的地址接到主存后面。前者较独立编址，后者较统一编址。

我感觉这一小节涉及的内容还是比较少的，考试应该不会考。

指令集的发展

讲了一些很虚的东西，没什么价值。

计算机组成原理复习：第二章 数据表示

实际上，这章讲的是数据是怎么编码的。大部分时候，都是在讲二进制编码。本章编码不特别说明都是在指二进制下的编码。

数值

数值是运算中最常见的成分。

非得分类的话，数字可以分成整数和小数。但小数的表示方法中也是用到了整数的。因此本章先介绍整数怎么表示。

原码 补码 反码

无符号的数直接用二进制表示。

有符号的数因为有正负，所以编码的第一个任务就是把正数和负数区分开来。如果把最高位当成符号位，0表示正1表示负，后面当成无符号数表示，那么这种表述法就是原码表示。反码和补码都是对原码的负数表示进行更改。反码是把负数的每一位取反，补码是把原码的每一位取反加一。补码和反码的原理都是取模，把一个模意义下很大的正数视为一个负数。

其中，补码的特点是0只有一种表示方法，从而负数可以多表示一个数；原码和补码都有一个+0一个-0.

定点表示

定点可以表示小数和正数。

定点小数的第一位是符号位，小数点固定在第一位后面。也就是说，所有数是零点几。定点整数第一位也是符号位，小数点固定在最后一个数后面，和之前讲的整数表示完全相同。

定点小数根本不实用。但是它在后面会被利用到。

浮点表示

计算机中，小数都用浮点表示法，即小数点的位置可以移动。在这种表示法下，一个数的数位被拆成了两部分：一部分是指数，称为阶码；一部分是底数，称为尾数。

我写完了这篇文章，写完了忘了保存，直接上传到博客。我退出文章的时候提示是否要保存，由于文章上传到博客草稿文件消失，一定会提示是否保存，我就选择了丢弃。结果我辛辛苦苦写的内容全部消失了。复习时间太少，这篇文章今天晚上就不补了。以后有缘再补完这篇文章或者删掉这篇文章。气死我了！