GSD 加法器

GSD 加法器

GSD (generalized signed-digit) 数制通常用来实现无进位加减法，这里以一种平衡冗余二进制数制为例。

平衡冗余二进制仍然使用 2 作为基底，使用 -1, 0, 1 三个数字，因此可以表示负数。

加法计算过程如下，将每一位的和拆成一位传递位，和一位中间位，中间位再和传递位相加，这里需要一个 E 位作为中和标志，以指示-1 和 1 的拆分方法，以用于中和传递位：

下图是该加法器的结构：

module CarryFreeAdder (input [1:0] A,input [1:0] B,input [1:0] TI, // 输入传递input EI, // 输入 Eoutput reg [1:0] S, // 本位和output reg [1:0] TO, // 输出传递output reg EO // 输出 E
);reg [1:0] I;always @(*) begincase ({A,B,EI})5'b00010, 5'b01000: beginI = 2'b10;TO = 2'b01;EO = 0;end5'b00011, 5'b01001: beginI = 2'b01;TO = 0;EO = 0;end5'b00100, 5'b10000: beginI = 2'b10;TO = 0;EO = 1;end5'b00101, 5'b10001: beginI = 2'b01;TO = 2'b10;EO = 1;end5'b01010, 5'b01011: beginI = 0;TO = 2'b01;EO = 0;end5'b10100, 5'b10101: beginI = 0;TO = 2'b10;EO = 1;end5'b10010, 5'b10011, 5'b01100, 5'b01101, 5'b00000, 5'b00001: beginI = 0;TO = 0;EO = 0;enddefault: begin // UnexpectedI = 0;TO = 0;EO = 0;endendcasecase({I, TI})4'b0001, 4'b0100: S = 2'b01;4'b0010, 4'b1000: S = 2'b10;4'b0110, 4'b1001, 4'b0000: S = 0;default: S = 0; // Unexpectedendcase
end
endmodule// GSD 加法器
module CarryFreeAdderChain #(parameter LEN = 8
) (input [1:0] A [LEN-1:0],input [1:0] B [LEN-1:0],output [1:0] S [LEN-1:0]
);wire [1:0] T [LEN:0];
wire [LEN:0] E;
assign T[0] = 0;
assign E[0] = 0;genvar i;
generatefor(i = 0;i < LEN;i++) beginCarryFreeAdder carryFreeAdder(.A(A[i]),.B(B[i]),.TI(T[i]),.EI(E[i]),.S(S[i]),.TO(T[i+1]),.EO(E[i+1]));end
endgenerate
endmodule// 二进制（补码）转GSD
module BinToCarryFree #(parameter LEN = 8
) (input [LEN-1:0] A,output [1:0] S [LEN-1:0]
);wire [LEN-1:0] P;
assign P = A[LEN-1] ? ~A + 1'b1 : A;genvar i;
generatefor(i = 0;i < LEN;i++) beginassign S[i] = P[i] ? (A[LEN-1] ? 2'b10 : 2'b01) : 0;end
endgenerate
endmodulemodule CarryFreeToBinUnit (input [1:0] A,input TI,output reg S,output reg TO
);
always @(*) begincase ({A,TI})3'b000, 3'b011: beginS = 0;TO = 0;end3'b001, 3'b100: beginS = 1'b1;TO = 1'b1;end3'b010: beginS = 1'b1;TO = 0;end3'b101: beginS = 0;TO = 1'b1;enddefault: begin // UnexpectedS = 0;TO = 0;endendcase
end
endmodule// GSD转二进制（补码）
module CarryFreeToBin #(parameter LEN = 8
) (input [1:0] A [LEN-1:0],output [LEN-1:0] S
);
wire [LEN:0] T;assign T[0] = 0;genvar i;
generatefor(i = 0;i < LEN;i++) beginCarryFreeToBinUnit carryFreeToBinUnit(.A(A[i]),.TI(T[i]),.S(S[i]),.TO(T[i+1]));end
endgenerate
endmodule

单次加法时间复杂度为 $O(1)$ 空间复杂度为 $O(n)$ ，适合多次累加计数。