题解 | #4bit超前进位加法器电路#

简析

如果只是简单地将逻辑表达式转化为verilog语言，这道题算不上较难题。难点应该是借着这道题理解超前进位加法器。下面梳理一些常见的加法器。

半加器

半加器是最简单的加法器。它不考虑进位输入。其中A和B是两个加数，S是和，C_o是进位输出。

assign S     = A ^ B;
assign C_out = A & B;

全加器

全加器是多bit加法器的基础。 $C_{i}$ 是进位输入。

\left\{ \begin{array}{lr} S=A\oplus B\oplus C_{i}\\ C_{o}= AB+C_{i}(A\oplus B) \end{array} \right.

下图中红色路径是全加器的关键路径。

module full_adder(
    input  A,
    input  B,
    input  C_i,
    output S,
    output C_o
);
    assign S    = A ^ B ^ C_i;
    assign C_o  = A & B | C_i&(a^b);
    // assign C_o  = A & B | A & C_i | B & C_i; // 也可以
endmodule

行波进位加法器

Ripple-carry adder, RCA。将全加器串联起来。虽然RCA结构简单易于理解，但容易看出，每一位的运算结果 $S_{k}$ 都要依赖进位 $C_{k}$ 才能得出。如下图所示，这会使得RCA的关键路径变得很长，而长关键路径会让电路难以满足时序要求。

module rca #(
    parameter width = 4
)(
    input  [width-1:0] A,
    input  [width-1:0] B,
    output [width-1:0] S,
    
    input  C_i,
    output C_o
);
    wire [width:0] C;
    genvar i;
    generate
      	for (i=0; i<width; i=i+1)begin
            full_adder myadder(
                .A    (A[i]),
                .B    (B[i]),
                .C_i  (C[i]),
                .S    (S[i]),
                .C_o  (C[i+1]),
            );
        end
    endgenerate
  	assign C[0] = C_i;
    assign C_o  = C[width];
endmodule

超前进位加法器

Lookahead Carry Adder，LCA。超前进位加法器的思想是并行计算进位 $C_{k}$ ，以缩短关键路径。 $C_{k}$ 可以直接由加数得到。
首先，令：

\begin{cases} P_k=A_k\oplus B_k,& \text{k=0,...,N-1}\\ G_k=A_kB_k & \text{k=0,...,N-1} \end{cases}

然后有：

\begin{cases} S_k=P_{k}\oplus C_{k},& \text{k=1,...,N}\\ C_k=G_{k-1}+C_{k-1}P_{k-1}& \text{k=1,...,N}\\ C_{N}=C_{out}\\ C_0 = C_{in} \end{cases}

对于4bit LCA有：

\begin{cases} C_1=G_0+C_{0}P_0 \\ C_2=G_1+C_{1}P_1 = G_1+G_0P_1+C_0P_1P_0 \\ C_3=G_2+C_{2}P_2 = G_2+G_1P_2+G_0P_2P_1+C_0P_2P_1P_0 \\ C_4=G_3+C_{3}P_3 = G_3+G_2P_3+G_1P_3P_2+G_0P_3P_2P_1+C_0P_3P_2P_1P_0\\ \end{cases}

超前进位加法器是通过公式直接导出最终结果与每个输入的关系，是一种用面积换性能的方法。
对于4bit LCA，进位输出 $C_{4}$ 的计算路径如下：

只需要三级门电路就可以得到，并且同时还计算出了 $P_{0} . . . P_{3}$ 和 $G_{0} . . . G_{3}$ 等可以复用的结果。而根据之前的分析，RCA产生 $C_{4}$ 需要 $3 + 2 + 2 + 2 = 9$ 级路径。加法器宽度越大，性能优势越明显。但LCA的逻辑门扇入扇出比较大，面积和复杂度都比较高。
参考资料：超前进位加法器原理与设计。下面的代码来自于参考资料

module pg_gen(
    input A,
    input B,
    output G,
    output P
);
	assign G = A & B;
	assign P = A ^ B;
endmodule

module lca_4bit #( width=4 ) (
    input  [width-1:0] op1,
    input  [width-1:0] op2,
    input  C_i,
    output [width-1:0] S,
    output C_o
);
    wire [width-1:0] G;
    wire [width-1:0] P;
    wire [width:0] C;

	genvar i;
	for( i=0; i<width; i=i+1) begin
    	pg_gen u_pg_gen(
        	.A( op1[i]),
        	.B( op2[i]),
            .G( G[i]  ),
            .P( P[i]  )
    	);
	end

    assign C[0] = C_i;
    assign C[1] = G[0] || ( C[0] & P[0] );
    assign C[2] = G[1] || ( (G[0] || ( C[0] & P[0]) ) & P[1] );
    assign C[3] = G[2] || ( (G[1] || ( (G[0] || (C[0] & P[0]) ) & P[1])) & P[2] );
    assign C[4] = G[3] || ( (G[2] || ( (G[1] || ( (G[0] || (C[0] & P[0]) ) & P[1])) & P[2] )) & P[3]);
    assign C_o = C[width-1];

	genvar k;
	for( k=0; k<width; k=k+1) begin
        assign S[k] = P[k] ^ C[k];
	end
endmodule

代码

注意+的优先级高于&和^。

`timescale 1ns/1ns

module lca_4(
	input		[3:0]       A_in  ,
	input	    [3:0]		B_in  ,
    input                   C_1   ,
 
 	output	 wire			CO    ,
	output   wire [3:0]	    S
);
    wire [3:0] C;
    
    assign S[0] = A_in[0] ^ B_in[0] ^ C_1;
    assign S[1] = A_in[1] ^ B_in[1] ^ C[0];
    assign S[2] = A_in[2] ^ B_in[2] ^ C[1];
    assign S[3] = A_in[3] ^ B_in[3] ^ C[2];
    assign C[0] = (A_in[0] & B_in[0]) || ((A_in[0] ^ B_in[0]) & C_1);
    assign C[1] = (A_in[1] & B_in[1]) || ((A_in[1] ^ B_in[1]) & C[0]);
    assign C[2] = (A_in[2] & B_in[2]) || ((A_in[2] ^ B_in[2]) & C[1]);
    assign C[3] = (A_in[3] & B_in[3]) || ((A_in[3] ^ B_in[3]) & C[2]);
    assign CO = C[3];
endmodule