Re：从0开始的计算机科学（2）

emm，往后拖成常态了。

中间隔了一个星期，玩原神玩得有点狠，然后又出门玩了两天...

我有罪我有罪。

但是起床的时间可以慢慢前推了，也许是能慢慢进入状态。

做个与C语言比较的话，上一篇的时候是熟悉了基本语法，那么这一次就是初识了复杂度，同样的硬件资源，不同的排布方式，斜向进位阵列乘法器和横向阵列乘法器效率就是不一样；然后还在原码一位乘法这里见识到了怎么压榨寄存器的每一个字节，分析完直呼上瘾。

嘛，从改进海明码和CRC一点点开始说吧。

考虑总校验码

之前只是按着mook上老师的讲解进行实验，然后完成实验，自己做了初步的检查，觉得没啥问题。

然后了解到可以在EduCoder上提交测试，好家伙，有OJ那味了。

海明码

然后发现我之前绘制的海明码检错有点问题，检查一位错不能检查出总校验码出错。

这是因为增加了总校验位后已经不是纯粹的海明码了，相当于是两层检查，自然也要分情况讨论。

海明码检查一位错，总校验位显示错误，则有一位错；
海明码检查无错，总校验位显示错误，则总校验位错；
海明码无错，总校验码无错，那就是没有错误。

好家伙，检查的时候只要总校验位说有错就是有错，那么简化一下提交，竟然对了，震惊。

CRC冗余校验码

同样的道理也适用于CRC冗余校验，上次我使用了\(7\)位生成多项式\(100\ 0011\)，然后后续的流水线实验怎么做怎么出问题，然后逐步检查到底，发现了只用CRC校验是有问题的。

比如对于信息为\(0000\ 0000\ 0000\ 0000\)，进行模二除后余数为\(00\ 0000\)，那么加上校验位之后是\(0\ 0000\ 0000\ 0000\ 0000\ 0000\)，对于出了一位错的\(00\ 0000\ 0000\ 0001\ 0000\ 0000\)和两位错的\(00\ 0000\ 0000\ 0000\ 0001\ 1000\)进行模二除之后的余数都是\(1\ 1000\)。换言之，只是用CRC冗余校验时，可能出现两位错识别为一位错并进行改正的情形。

我以前一直以为CRC无敌了呢，在各种场合都能遇见。现在想想，可能这些用得到的场合要么是多种校验手段叠加buff，要么是对于出错信息只接受不纠错，或者出错概率不大，这些情形下CRC确实是非常受用。

那么拐回来，如果想要使用CRC进行检验并纠错的话应该怎么做呢？答案也是增加一位总校验位，这时的一位错就有两种情形：

CRC检验一位错，总校验位检验出错，这个时候是存在一位错；
CRC检验无错，总校验位检验出错，这个时候是总校验位出了错误。

无错误好说，其余情形都按照两位错处理。

然后修改后的编码电路与解码电路：

还有解码电路里的那个余数与出错位数转换的逻辑电路：

嘛，放在EduCoder里是都过了。

流水传输

这个实验其实差不多就是水到渠成了，理清楚各部分的逻辑，无错和一位错都直接放行，两位错的话就暂停接收新的信息进来，清空流水同时发信息的位置往前推\(3\)步，就没啥问题了。

海明码和CRC的大框架相同：

GB2312

之前嫌麻烦没有单独整理转换GB2312为十六进制的代码，但是提交的时候必须是修改后的字符，就写了个C++的程序吧。

#include <iostream>

using namespace std;

int main()
{
    printf("v2.0 raw\n");
    char ch, hex[9];
    bool flag = false;
    int cnt = 0;
    while (~scanf("%c", &ch))
    {
        sprintf(hex, "%x", ch);
        printf("%s", hex + 6);
        if (flag)
        {
            if (cnt == 7)
            {
                printf("\n");
                cnt = 0;
            }
            else
            {
                printf(" ");
                cnt++;
            }
        }
        flag = !flag;
    }
    return 0;
}

之后对于一个使用GB2312编码的文件使用重定向输入输出的方式得到可以导入logisim里的内容文件。

类似这样：

1 2	g++ main.cpp -o main.a ./main.a < in.txt > out.txt

\(8\)位可控加减法器

加法就没什么好说的，\(8\)个一位全加器串连在一起就好，不过减法就有点意思了。

众所周知计算机内部实际上只做补码加法运算，减法的话需要改写成加上一个负数，就像\([A]_补-[B]_补\Rightarrow[A]_补+[-B]_补\)，然后已知补码求相反数反的算法也好说“按位取反，末位加一”（和原码转补码有些类似），实现的思路就是对个位与\(1\)异或取反，然后再加个进位充当末位的\(1\)。

快速加法器

上面的实现是一种串行加法器，每一个全加器工作都需要上个全加器的进位输出，就导致运算存在延迟，且随着位数增加而递增。

\[ \begin{aligned} C_1=A_0B_0+(A_0+B_0)C_0\\ C_2=A_1B_1+(A_1+B_1)C_1\\ C_3=A_2B_2+(A_2+B_2)C_2\\ C_4=A_3B_3+(A_3+B_3)C_3\\ \end{aligned} \]

然后就根据运算公式得到了并行计算的方式：

\[ \begin{aligned} C_1=&A_0B_0+(A_0+B_0)C_0\\ C_2=&A_1B_1+(A_1+B_1)A_0B_0+(A_1+B_1)(A_0+B_0)C_0\\ C_3=&A_2B_2+(A_2+B_2)(A_1B_1+(A_1+B_1)A_0B_0)+(A_2+B_2)(A_1+B_1)(A_0+B_0)C_0\\ C_4=&A_3B_3+(A_3+B_3)(A_2B_2+(A_2+B_2)(A_1B_1+(A_1+B_1)A_0B_0)\\ &+(A_3+B_3)(A_2+B_2)(A_1+B_1)(A_0+B_0))C_3 \end{aligned} \]

\(4\)位先行进位\(74182\)

接着，设\(G_i=A_iB_i\)，\(P_i=A_i+B_i\)，上述的式子又可化为：

\[ \begin{aligned} C_1=&G_0+P_0C_0\\ C_2=&G_1+P_1G_0+P_1P_0C_0\\ C_3=&G_2+P_2G_1+P_2P_2G_0+P_2P_1P_0C_0\\ C_4=&G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_0\\ \end{aligned} \]

把这个进位关系单独拉出来，就成了现行进位电路：

快速加法器

进位电路已经有了，那么给定每一位的数据以及进位输入，就能轻松的完成 \(4\)位快速加法器：

套娃得到 \(16\)位快速加法器：

其实再套娃一层就能得到\(64\)位快速加法器的，不过按照要求完成串内并行，串间并行的 \(32\)位快速加法器：

乘法器

阵列乘法器

最简单的乘法器就是模拟手工运算，逐位相乘，然后相加，就是自然的横向进位无符号乘法器；而另外一种实现方式，斜向进位无符号乘法器的话，使用相同的硬件资源，关键路径更短，就效率更高些，然后实现结果， \(5\)位阵列乘法器：

再加上一位的符号位，然后根据符号位的情形确定运算结果的符号，就构成了 \(6\)位补码阵列乘法器：

单纯的把\(5\)位阵列乘法器分成几部分，一个时钟周期计算一部分，就构成了非常简易的 \(5\)位无符号乘法流水线：

一位乘法器

老实说我觉得叫移位乘法器更恰当些，也更容易理解，这个乘法器的设计，让我第一次觉得是在充分利用硬件资源，实现思路叹为观止。

原码一位乘法器

加法对乘法满足分配律，对二进制而言亦是如此，那么，二进制乘法就可以被拆分为多个加法。

设\(x=1001B\)，\(y=1011B\)，位数为\(n\)，对于\(x\times y\)，可以拆分成如下四个数的和：

\[\begin{aligned} 0:&1001\times&1&=&1001&\\ 1:&1001\times&10&=&10010&\\ 2:&1001\times&000&=&000000&\\ 3:&1001\times&1000&=&1001000&\\ \end{aligned}\]

从这之间又可以发现一些规律，从上往下看，算式结果的位数依次递增，同时末位\(0\)的数量也在递增；若将末位\(0\)去除，剩下的数认作有效数的话，可以看出这个有效数由乘数的最高位决定；若将它们从上往下依次相加，则加法的结果从最后一位起，每增加一次确定一位。

将上述三个规律整合在一起，可以得到这么一个结论：相加到第\(i\)个式子时，相加结果位数是\(n+i+1\)位，同时确定的位数为\(i+1\)，相加结束前，恒有\(n\)位是不确定的，且是高\(n\)位，由\(y\)的第\(i\)位决定不确定的\(n\)位需要加上\(a\)还是\(0\)，而此时\(b\)的低\(i-1\)位对后续的计算已经没有用处了。

那么如果将相加结果\(\sum\)与\(b\)中对后续计算有影响的位数列出来，会是这么一个样子：

\[ \begin{aligned} init:0000\quad1011\\ 0:01011\quad101\\ 1:011011\quad10\\ 2:0011011\quad1\\ 3:01100011\quad\\ \end{aligned} \]

两个数一共恒\(2n\)位，结合在一起考虑，将\(\sum\)每次确定的位数放到\(y\)中，可以变化成这样的格式：

\[ \begin{aligned} init:0000\quad1011\\ 0:0101\quad1101\\ 1:0110\quad1110\\ 2:0011\quad0111\\ 3:0110\quad0011\\ \end{aligned} \]

可以很自然的得到递推式：\(\{\sum,y\}=\{\sum+y_n|x|,y\}>>1\)，计算结束后，最终的计算结果为\(\{\sum,y\}\)，就很有意思。

按照这个结论画电路：

\(8\)位的话需要\(9\)个时钟周期，第\(1\)个周期初始化，然后\(8\)个周期做运算，可以用计数器精准操控。

就酱

尾声

emm，当沉下心来学习的时候，会很投入，但是一旦松懈一点点，就会一直不想提起劲来，然后时间会唰刷的流的很快，得加油啊。