4bit/16bit Carry Lookahead Adder 설계

컴퓨터의 가산기(Adder)는 여러 종류가 있다. 기초적인 Ripple Carry Adder라던가, Carry Select Adder 등등...

 

Ripple Carry Adder는 예전에 다룬 적이 있었다.

https://verilog-hdl-design.tistory.com/entry/Adder-And-Subtractor

덧셈과 뺄셈, 그리고 sign extension

 

이번에 다룰 가산기는 Carry Lookahead Adder(CLA)다. Ripple Carry Adder에서는 각 Full Adder(FA)의 Sum을 계산하기 위해 이전 비트의 Carry Out을 기다려야 한다. 이게 가장 하위 비트부터 상위 비트까지 전달되어서 propagation이라고 하고, 가산기 연산에서 가장 긴 딜레이를 차지한다. 가장 긴 딜레이를 가진 Carry propagation을 줄이기 위해 Lookahead Carry Unit을 사용하여 Carry를 예측한다. 

 

4비트 CLA는 4개의 FA에서의 출력인 S, P, G 중 P, G 각각 4비트를 Lookahead Unit에 전달하여 Carry를 예측한다.

왼쪽 그림은 4비트 CLA의 입출력 구조를 나타냈다. P 4비트, G 4비트, C0를 입력으로 받고, PG(Group Propagation), GG(Group Generate) 및 C(Carry) 4비트를 출력한다.

 

S, P, G는 A, B에 대해 다음과 같은 연산을 취한다.

S = A xor B xor Cin

P = A or B

G = A and B

기존 FA에서는 Carry를 썼지만 CLA에서는 Carry를 예측하기 때문에 CLA FA에서는 Carry 대신 P(Propagate)와 G(Generate)를 출력한다.

 

Lookahead Unit은 P, G, Cin 입력 및 C 출력에 대해 아래와 같은 논리식을 따른다.

 

 

 

 

 

 

이 식을 풀어쓰면 아래와 같다.

 

 

 

 

 

 

 

이 논리식을 게이트로 나타내면 아래와 같은 구조를 가진다.

4비트 CLA 구조

해당 그림에서 나오지 않은 출력인 PG(Group Propagate)와 GG(Group Generate)는 아래와 같은 논리식을 따른다.

위의 PG와 GG는 4비트 CLA의 대표 P와 G라고 보면 된다. 16비트 CLA에 쓰이는데, 16비트 CLA 설계에서 설명하겠다.

이제 Verilog로 4비트 CLA를 구현해보자.

module FA_CLA_1b(
    output S, P, G,
    input A, B, Cin
);

assign P = A | B;
assign G = A & B;
assign S = (A ^ B) ^ Cin;

endmodule

FA를 CLA에 맞게 고쳤다.

module LookAhead_unit_4b(
    output [3:0] C,
    output PG, GG, 
    input Cin, 
    input [3:0] P, G
);

wire [2:0] P0_comb;
wire [1:0] P1_comb;
wire P2_comb;

assign P0_comb[0] = P[1] & P[0];
assign P0_comb[1] = P[2] & P0_comb[0];
assign P0_comb[2] = P[3] & P0_comb[1];

assign P1_comb[0] = P[1] & P[2];
assign P1_comb[1] = P1_comb[0] & P[3];

assign P2_comb    = P[2] & P[3];

assign PG = P0_comb[2];
assign GG = G[3] | (G[2] & P[3]) | (P2_comb & G[1]) | (P1_comb[1] & G[0]);

assign C[0] = G[0] | (P[0] & Cin);
assign C[1] = G[1] | (G[0] & P[1]) | (P0_comb[0] & Cin);
assign C[2] = G[2] | (G[1] & P[2]) | (P1_comb[0] & G[0]) | (P0_comb[1] & Cin);
assign C[3] = GG   | (PG   & Cin);

endmodule

Lookahead Unit 코드다. 중복 사용되는 부분을 wire(P0/1/2_comb)로 재활용했다. C2를 C1에 대한 식으로 나타내지 않는 이유는 C0~3은 동시에 연산이 시작되어야 하기 때문이다. P, G 4비트는 동시에 들어오는데 C2를 C1에 대한 식으로 나타내면 Ripple과 다를게 없기 때문이다.

module CLA_4b(
    output [3:0] Sum, 
    output CarryOut, PG, GG,
    input Cin,
    input [3:0] A, B
);

wire [3:0] P, G;
wire [3:0] C;

FA_CLA_1b FA0(.S(Sum[0]), .P(P[0]), .G(G[0]), .A(A[0]), .B(B[0]), .Cin(Cin));
FA_CLA_1b FA1(.S(Sum[1]), .P(P[1]), .G(G[1]), .A(A[1]), .B(B[1]), .Cin(C[0]));
FA_CLA_1b FA2(.S(Sum[2]), .P(P[2]), .G(G[2]), .A(A[2]), .B(B[2]), .Cin(C[1]));
FA_CLA_1b FA3(.S(Sum[3]), .P(P[3]), .G(G[3]), .A(A[3]), .B(B[3]), .Cin(C[2]));

LookAhead_unit_4b LCU4b(.C(C), .Cin(Cin), .P(P), .G(G), .PG(PG), .GG(GG));

assign CarryOut = C[3];

endmodule

탑 모듈인 CLA_4b다. 

 

CLA는 Lookahead Unit을 이용해 확장이 가능하다. PG와 GG를 Unit의 P와 G 포트에 연결하면 똑같이 동작한다. 아래 그림을 보면 이해가 쉬울 것이다.

4비트 CLA와 같은 구조인데, 여기서 알아야 할 것은 4개의 보라색 4비트 CLA 블록이 첫번째 사진인 4bit CLA를 나타낸다는 것(Lookahead Unit 포함)이다. 또한 아래의 16비트 Unit은 말만 16비트지 4비트에서의 Unit과 완전히 똑같은 것이다. 다른 점은 C16, 12, 8, 4를 출력한다는 것 뿐이다. 즉 16비트 CLA와 4비트 Lookahead Unit이 있으면 64비트 CLA도 만들 수 있다는 말이다.

 

Lookahead Unit의 종류에 따라 여러 가지 종류의 Adder를 만들 수 있다는 것인데, 예를 들어 8비트 Unit을 만든다 치면 8비트 CLA 8개와 8비트 Unit을 이용해 64비트 CLA를 만들 수 있다는 것이다.

 

수학적인 증명은 이 포스팅에서 다룰 것이 아니기 때문에 출처에서 따로 알아보길 바란다.

 

이제 16비트 CLA 코드를 만들어보자.

module CLA_16b(
    output [15:0] Sum, 
    output CarryOut, PG, GG,
    input Cin, 
    input [15:0] A, B
);

wire [3:0] P, G;    // P4, 8, 12, 16
wire [3:0] C;       // C4, 8, 12, 16
wire [3:0] Cout_CLA;

CLA_4b CLA4b_0(.Sum(Sum[0 +: 4]),  .CarryOut(Cout_CLA[0]), .PG(P[0]), .GG(G[0]), .Cin(Cin),  .A(A[0 +: 4]),  .B(B[0 +: 4]));
CLA_4b CLA4b_1(.Sum(Sum[4 +: 4]),  .CarryOut(Cout_CLA[1]), .PG(P[1]), .GG(G[1]), .Cin(C[0]), .A(A[4 +: 4]),  .B(B[4 +: 4]));
CLA_4b CLA4b_2(.Sum(Sum[8 +: 4]),  .CarryOut(Cout_CLA[2]), .PG(P[2]), .GG(G[2]), .Cin(C[1]), .A(A[8 +: 4]),  .B(B[8 +: 4]));
CLA_4b CLA4b_3(.Sum(Sum[12 +: 4]), .CarryOut(Cout_CLA[3]), .PG(P[3]), .GG(G[3]), .Cin(C[2]), .A(A[12 +: 4]), .B(B[12 +: 4]));

LookAhead_unit_4b LCU16b(.C(C), .Cin(Cin), .P(P), .G(G), .PG(PG), .GG(GG));

assign CarryOut = C[3];

endmodule

4비트 CLA와 다른 것이 딱히 없다.

 

이제 테스트벤치로 동작이 제대로 되는지 확인해보자.

`timescale 1ns/1ps

module tb_CLA_4b();

reg [3:0] A, B;
reg Cin;

wire [3:0] Sum;
wire CarryOut, PG, GG;

CLA_4b TEST(Sum, CarryOut, PG, GG, Cin, A, B);

initial begin
    A <= 4'd3;
    B <= 4'd6;
    Cin <= 1'b0;
    #10
    B <= 4'd8;
    #10
    B <= 4'd7;
    #10
    A <= 4'd11;
    #10
    B <= 4'd15;
    #10
    A <= 4'd3;
    Cin <= 1'b1;
    B <= 4'd8;
    #10
    B <= 4'd7;
    #10
    A <= 4'd11;
    #10
    B <= 4'd15;
    #10
    $finish;
end

endmodule
//------------------
module tb_CLA_16b();

reg [15:0] A, B;
reg Cin;

wire [15:0] Sum;
wire CarryOut, PG, GG;

CLA_16b TEST(Sum, CarryOut, PG, GG, Cin, A, B);

initial begin
    A <= 16'd3;
    B <= 16'd6;
    Cin <= 1'b0;
    #10
    B <= 16'd8;
    #10
    B <= 16'd7;
    #10
    A <= 16'd22;
    #10
    B <= 16'd30;
    #10
    A <= 16'd3;
    Cin <= 1'b1;
    B <= 16'd8;
    #10
    B <= 16'd7;
    #10
    A <= 16'd22;
    #10
    B <= 16'd30;
    #10
    $finish;
end


endmodule

시뮬레이션 결과는 아래와 같다.

https://en.wikipedia.org/wiki/Carry-lookahead_adder
https://en.wikipedia.org/wiki/Lookahead_carry_unit