CLA以及bit乘法

tags: IT铁人

例题答案

就简单把答案打出来罗~
小心转换成二位元不要粗心。

Full Adder

在介绍Carry Lookahead Adder(CLA)之前，先跟各位介绍甚麽是Full Adder。

简单来说长这样	复杂一点长这样	Logic Gate的表

与Full Adder相对的是Half Adder，後者没有Carry-in，也就是说没办法接收前一个位元结果进位与否，因为晚点会用到的是Full Adder，在这边就不介绍另一个了。

Full Adder接收两个bit以及一个Carry-in，然後能够输出加法的结果以及进位。

CLA

CLA要达成的做法是避免每个Full Adder都要等前面一个把结果输出才能开始做加法，如果我们能提前知道前面是否会进位，就能够提前让後面的Full Adder开始运作了，为了加速，我们就需要来一点逻辑游戏了。

G & P

我们先定义两个新东西，称为Generate ( G ) & Propagate ( P )，概念上代表我是否产生进位以及我是否传递我收到的进位。

假设有四个Full Adder，F0的G为1，代表F0产生了进位，所以F1会收到进位，当F1的P=1，代表F1会继续传递这个F0产生的进位到F2，以此类推，直到有人不传递也不产生，就会留在那边，否则会继续传下去。

如此一来G和P的逻辑可以定义成：

g~i~ = a~i~ * b~i~
p~i~ = a~i~ + b~i~ (也可以用 a~i~ {xor} b~i~)

Combine

根据刚刚提到的传递方式，我们可以将每个Full Adder的进位写成：

c~i~ = g~i-1~ + p~i-1~ * c~i-1~ , 1<=i<=4
其中Ci代表第i个Full Adder收到的Carry-in。
因为基本上都是以4位元的CLA实作，所以C~4~代表最後输出给下一组的Carry-in

而每一组都可以把c展开来，化简过程以及c的结果如下：

化简过程及结果	CLA示意图

如此一来我们就能在Full Adder算完之前拿到p,g，并且让後面的Full Adder提早动作。

位元乘法

做直式乘法的时候，我们需要一个一个用九九乘法表计算，把进位加进去，并且把每个位数做完後加起来，不过因为电脑使用二进位制，0和1的意思分别代表填0或是把被乘数照抄，这就是电脑的运算方式。

电脑运算的时候，是将被乘数每次往左边shift一格，代表乘法一次比一次还要大一个位元，类似平常直式乘法每次都会比上一个从更前面的地方开始运算。

而乘数会每次往右边shift一格，代表做完之後丢掉，把下一个要计算的位元移动到准备计算的位置。

如下：

不过因为数字都是32bit，而结果最大是64bit，并且在前面几次的乘法并不会压满64bit，所以为了节省空间，我们可以先将Product以及Multiplier写在一起，把不会改变的被乘数固定32bit，每次决定乘法结果时，和Product的最大32bit加起来填回去并且向右shift一位。

如下：

如此一来就能够同时缩小成本及空间，少了乘数的空间、被乘数又缩短成32bit，并且只要32bit的ALU，可以说是一石多鸟阿！！

这次的内容比较难出题目，那我们就地解散ㄅ，88~