16th

要想理解 CLA（Carry-Lookahead Adder，超前进位加法器）的原理，首先要知道两个概念：生成（generate） 和 传播（propagate）。假设 A 和 B 是两个加数，$A_i$ 和 $B_i$ 分别代表 A 和 B 从右边数第 i 位上的数，i 从 0 开始计数，$C_i$ 代表第 i-1 位产生的进位，$C_0=0$ 。生成指的是无论右边有没有进位，当前位上都会产生进位，比如二进制的 10 + 10，个位上相加得 0，二位（类似于十进制的十位）上相加得 0，产生进位 1，于是我们说二位上是生成的，我们用 $G_i$ 表示第 i 位是否生成，其实可以看出来，只有当 $A_i$ 和 $B_i$ 同时为 1 时，第 i 位才生成，所以 $G_i = A_i \cdot B_i$（$A_i \cdot B_i$ 表示 $A_i$ 和 $B_i$ 做「与」操作）；传播指的是由于右边有进位，导致当前位相加时产生了进位，比如二进制的 101 + 111，本来二位上 0 + 1 没有产生进位，但是由于个位上两个 1 相加产生了进位，导致现在二位上其实是 0 + 1 + 1，由此产生了进位，这种情况我们称之为传播，用 $P_i$ 表示第 i 位是否传播，不难发现，$A_i$ 和 $B_i$ 只要有一个为 1，第 i 位就会传播，所以 $P_i=A_i + B_i$（$A_i + B_i$ 表示 $A_i$ 和 $B_i$ 做「或」操作）。

生成和传播决定了某一位相加时会不会产生进位，即 $C_{i+1}=G_i+P_i \cdot C_i$。例如，两个 4 bit 位的数相加时，我们可以得到以下等式：

$$C_{1}=G_{0}+P_{0}\cdot C_{0} \\ C_{2}=G_{1}+P_{1}\cdot C_{1} \\ C_{3}=G_{2}+P_{2}\cdot C_{2} \\ C_{4}=G_{3}+P_{3}\cdot C_{3} \\$$

把 $C_1$ 代入 $C_2$，$C_2$ 代入 $C_3$，$C_3$ 代入 $C_4$，可以得到下面这个展开的等式：

$$\begin{align*} &C_{1}=G_{0}+P_{0}\cdot C_{0} \\ &C_{2}=G_{1}+G_{0}\cdot P_{1}+C_{0}\cdot P_{0}\cdot P_{1} \\ &C_{3}=G_{2}+G_{1}\cdot P_{2}+G_{0}\cdot P_{1}\cdot P_{2}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2} \\ &C_{4}=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{2}\cdot P_{3}+G_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3} \\ \end{align*}$$

因为 $G_i$ 和 $P_i$ 都是由 $A_i$ 和 $B_i$ 计算出来的，并且 $C_0=0$，所以 $C_1\sim C_4$ 都可以直接通过电路算出来，无需等待前面的计算结果，得到 $C_i$ 之后，再拿 $C_i$ 与 $A_i$ 、 $B_i$ 做异或操作，即可得到每一位上的计算结果。与原始的全加器从右往左依次计算，CLA 效率要高很多。

由于 CLA 的电路实现比较复杂，且位数越多越复杂，所以一般以 4 个全加器为一组，组成一个 CLA，再将多个 CLA 组合起来，组成超级 CLA，实现多位二进制数的加法运算。

在 CLA 的基础上，又进一步演化出了曼彻斯特进位链，低位可以共享高位的逻辑电路，计算当前位的进位，节省了电路数量。

3011608125845_.pic_hd

package com.supermouse;

import java.util.Objects;

/**
 * 模拟超前进位加法器的计算过程
 * @author 王浩
 * @date 2020/12/16
 */
public class TestCLA {
    private static int p(int a, int b) {
        return a | b;
    }

    private static int g(int a, int b) {
        return a & b;
    }

    private static String arrayToString(int[] arr) {
        if (Objects.isNull(arr) || arr.length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int value : arr) {
            sb.append(value);
        }
        return sb.toString();
    }

    private static int binaryToDecimal(int[] arr) {
        if (Objects.isNull(arr) || arr.length == 0) {
            return 0;
        }
        int sum = 0;
        int digit = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            sum += (1 << digit++) * arr[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        final int bitLength = 4;
        int[] A = new int[bitLength];
        int[] B = new int[bitLength];
        int[] C = new int[bitLength + 1];
        int[] S = new int[bitLength + 1];
        // int a = 8, b = 6;
        out: for (int a = 0; a < (1 << bitLength); a++) {
            for (int b = 0; b < (1 << bitLength); b++) {
                int originA = a, originB = b;
                // 把十进制转成二进制
                for (int i = bitLength - 1; i >= 0; i--) {
                    A[i] = originA % 2;
                    B[i] = originB % 2;
                    originA /= 2;
                    originB /= 2;
                }
                System.out.println("A：" + a + "，二进制：" + arrayToString(A));
                System.out.println("B：" + b + "，二进制：" + arrayToString(B));
                // 以下4步在硬件层面可以通过电路同时计算
                C[3] = g(A[3], B[3]) | (p(A[3], B[3]) & C[4]);
                C[2] = g(A[2], B[2]) | (p(A[2], B[2]) & C[3]);
                C[1] = g(A[1], B[1]) | (p(A[1], B[1]) & C[2]);
                C[0] = g(A[0], B[0]) | (p(A[0], B[0]) & C[1]);
                // 这个循环在硬件层面可以通过电路同时计算
                for (int i = bitLength - 1; i >= 0; i--) {
                    S[i + 1] = A[i] ^ B[i] ^ C[i + 1];
                }
                S[0] = C[0];
                int calculateResult = binaryToDecimal(S);
                System.out.println("计算结果：" + calculateResult + "，二进制：" + arrayToString(S));
                if (calculateResult != a + b) {
                    System.out.println("计算错误！！！");
                    break out;
                }
                System.out.println();
            }
        }
    }
}

参考资料：https://en.wikipedia.org/wiki/Carry-lookahead_adder