前言
逻辑门本质上操作的是单个二进制数,通过高低电压或者有无信号来表示,并且,因为二进制数的原因,一个数字,我们可以通过二进制数来表示,整数可以精确表示,浮点数可以近似表示
本篇文章使用逻辑门来构建加法器
git地址:https://gitlab.com/lingyanTools/comvirtual.git
加法器
先来看整数,一个二进制整数是怎么进行加法运算的呢?
看下面两个二进制数
A
=
101
(十进制)
=
01100101
(二进制)
A = 101(十进制) = 01100101(二进制)
A=101(十进制)=01100101(二进制)
B
=
201
(十进制)
=
11001001
(二进制)
B = 201(十进制) = 11001001(二进制)
B=201(十进制)=11001001(二进制)
我们从右边开始往左侧进行计算,计算相应的位,如果大于1,则进位,整个流程如下:
- 默认进位是0
- 1 + 1 + 进位0 =
0
,进位1 - 0 + 0 + 进位1 =
1
,进位0 - 1 + 0 + 进位0 =
1
,进位0 - 0 + 1 + 进位0 =
1
,进位0 - 0 + 0 + 进位0 =
0
,进位0 - 1 + 0 + 进位0 =
1
,进位0 - 1 + 1 + 进位0 =
0
,进位1 - 0 + 1 + 进位1 =
0
,进位1
因为最后有个进位,所以最终的结果位100101110 = 302 = 101 + 201
很容易发现,对于二进制的加法的每一位操作,有两个值需要我们确定,一个是当前的进位值
C
i
C_i
Ci,一个是当前的计算值
F
i
F_i
Fi,可以用下面的公式表示:
{
F
i
=
(
X
i
异或
Y
i
)
异或
C
i
−
1
,
C
i
=
(
X
i
与
C
i
−
1
)
或
(
Y
i
与
C
i
−
1
)
或
(
X
i
与
Y
i
)
\begin{cases} F_i = (X_i 异或 Y_i) 异或 C_{i-1},\\ C_i = (X_i 与 C_{i-1}) 或 (Y_i 与 C_{i-1}) 或 (X_i 与 Y_i ) \end{cases}
{Fi=(Xi异或Yi)异或Ci−1,Ci=(Xi与Ci−1)或(Yi与Ci−1)或(Xi与Yi)
用电路表示
F
i
F_i
Fi的值为:
用电路表示
C
i
C_i
Ci的值为:
我们把通过输入 X i X_i Xi、 Y i Y_i Yi和 C i − 1 C_{i-1} Ci−1获取输出$F_i 和 和 和C_i$用C语言表示如下:
/**
* 全加器
* 输入两个二进制位,其实就是两根电路
* 输入进位位:c
* param:
* f:输出值
* c1:输出进位值
* 返回加法位
*/
void full_add(long x,long y,long c,long* f, long* c1)
{
long a = xor_gate(x, y);
*f = xor_gate(a, c);
long b1 = and_gate(x, c);
long b2 = and_gate(y, c);
long b3 = and_gate(x, y);
*c1 = or_gate(or_gate(b1, b2),b3);
}
这个电路组合叫做全加器
串位进位加法器
上述的全加器可以计算一位的加法,我们把每位的运算连起来,就是我们上面计算过程列出的那样,从右向左依次计算,假设我们需要满足一个64位的加法器,我们可以用64个全加器串行连接起来,下图中n=64:
这种连接方式叫做串位进位加法器
这样我们的64位加法器就可以用C语言描述了
/**
* 逻辑运算器的加法
* param:
* in_1:输入1
* in_2:输入2
* bits:选择执行加法的位数
* 初始进位,并且返回执行后的进位
* return: 返回输出结果
*/
long alu_add(long in_1, long in_2, long bits,long* c)
{
long result = 0;
for(int i = 0;i<bits;i++)
{
long x = alu_bit(in_1, i); // 获取输入1的第i位
long y = alu_bit(in_2, i); // 获取输入2的第i位
long f = 0;
full_add(x, y, *c, &f, c);
result |= f<<i;
}
return result;
}
/**
* 获取二进制位
* param:
* in_1:输入的数据
* bits:获取哪一位的二进制位,0~sizeof(long)-1
* return
* 返回获取到的数据0或1
*/
unsigned long alu_bit(unsigned long in_1, long bits)
{
unsigned long a = 1;
return ((a<<bits)&in_1)>>bits;
}
进位选择加法器
串位进位加法器由于是串行的,这就导致每一步的运算必须等待前面一位计算完成。几乎所有的算术运算都要用到ALU, ALU的核心还是加法器,因此要提高运算速度, 加法器的速度非常关键。
在进行进位选择加法器讲解之前,先介绍一种选择器,2-1选择器
2-1选择器
2-1选择器是根据一位控制位控制2个输入输出哪一个的电路选择器,电路图如下:
我们可以用C语言实现一下
long select_2_1(long in_1,long in_2,long door)
{
long a1 = and_gate(in_1, door);
long a2 = and_gate(in_2, not_gate(door));
return or_gate(a1, a2);
}
并且该C函数可以不止实现单个位的选择,对于64位以内的可以通过该方法返回选择后的值。
进位选择加法器
进位选择加法器是这样一种算法,比如对于64位的加法,分成四部分
- A:0~15位
- B:16~31位
- C:32~47位
- D:48~63位
BCD部分都有两种计算逻辑,一种假设进位为0,一种假设进位为1
所以,A,B0,B1,C0,C1,D0,D1可以并行运算。运算完成后进行拼接,拼接逻辑如下:
- 根据A的进位选择B0或者B1
- 根据上一步选择的B0或者B1是否发生进位选择C0或者C1
- 根据上一步选择的C0或者C1是否发生进位选择D0或者D1
下面看一下C语言的实现
long alu_add_16(long in_1, long in_2)
{
long ac = 0;
long bc0 = 0;
long bc1 = 1;
long cc0 = 0;
long cc1 = 1;
long dc0 = 0;
long dc1 = 1;
// 下面这些并行运算
long a = alu_add(in_1, in_2, 16,&ac);
long b0 = alu_add(in_1>>16, in_2>>16, 16,&bc0);
long b1 = alu_add(in_1>>16, in_2>>16, 16,&bc1);
long c0 = alu_add(in_1>>32, in_2>>32, 16,&cc0);
long c1 = alu_add(in_1>>32, in_2>>32, 16,&cc1);
long d0 = alu_add(in_1>>48, in_2>>48, 16,&dc0);
long d1 = alu_add(in_1>>48, in_2>>48, 16,&dc1);
long b = select_2_1(b1, b0, ac);
long c = select_2_1(c1, c0, b==b1?bc1:bc0);
long d = select_2_1(d1, d0, c==c1?cc1:cc0);
return a | b<<16 | c<<32 | d<<48;
}
如何进行减法运算
使用逻辑门进行减法运算,涉及借位,运算比较麻烦,但是我们可以通过操作将减法运算变成加法运算,比如对下面的减法运算:
A
=
X
−
Y
A = X - Y
A=X−Y
我们可以写成加法的形式:
A
=
X
+
(
−
Y
)
A = X + (-Y)
A=X+(−Y)
而对于补码编码的数据来说,-Y等于Y取反然后加1
,取反操作之需要对Y执行反相器即可,而加1的操作正好可以通过设置加法的初始进位为1来进行处理,下面给出减法运算的C语言电路描述
long alu_not(long in_1, long bits)
{
long res = 0;
for(int i = 0;i<bits;i++)
{
long x = alu_bit(in_1, i); // 获取输入1的第i位
res |= (not_gate(x)<<i);
}
return res;
}
long alu_sub(long in_1, long in_2, long bits)
{
long a = alu_not(in_2,64);
int c = 1;
return alu_add(in_1, a, bits,&c);
}
这样,我们就使用C语言按照电路图的设计实现了加减的逻辑处理。