Verilog generator for multipliers based on recursive RNS arithmetic

Choose number of bits of multiplier inputs (from 5 to 64) : 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

Selected number of bits: 5 (Maximal output value: 1024)
Value of power n for basis 1: {2ⁿ-1, 2ⁿ, 2ⁿ+1}: 4 (Maximal value: 4080)
Value of power n1 for basis 2: {2ⁿ¹-1, 2ⁿ¹, 2ⁿ¹+1}: 3 (Maximal value: 504 > (2ⁿ+1)²)
Basis 1: {2⁴-1, 2⁴, 2⁴+1} or [15, 16, 17]
Basis 2: {2³-1, 2³, 2³+1} or [7, 8, 9]

module mul_binary_5 (A, B, out); input [4:0] A; input [4:0] B; output [9:0] out; wire [3:0] A_1; wire [3:0] A_2; wire [4:0] A_3; wire [2:0] A_1_LOW; wire [2:0] A_1_MID; wire [3:0] A_1_HIGH; wire [2:0] A_2_LOW; wire [2:0] A_2_MID; wire [3:0] A_2_HIGH; wire [2:0] A_3_LOW; wire [2:0] A_3_MID; wire [3:0] A_3_HIGH; wire [3:0] B_1; wire [3:0] B_2; wire [4:0] B_3; wire [2:0] B_1_LOW; wire [2:0] B_1_MID; wire [3:0] B_1_HIGH; wire [2:0] B_2_LOW; wire [2:0] B_2_MID; wire [3:0] B_2_HIGH; wire [2:0] B_3_LOW; wire [2:0] B_3_MID; wire [3:0] B_3_HIGH; wire [2:0] RES_1_LOW; wire [2:0] RES_1_MID; wire [3:0] RES_1_HIGH; wire [2:0] RES_2_LOW; wire [2:0] RES_2_MID; wire [3:0] RES_2_HIGH; wire [2:0] RES_3_LOW; wire [2:0] RES_3_MID; wire [3:0] RES_3_HIGH; wire [8:0] RES_1_BEFORE_MOD; wire [8:0] RES_2_BEFORE_MOD; wire [8:0] RES_3_BEFORE_MOD; wire [3:0] RES_1; wire [3:0] RES_2; wire [4:0] RES_3; wire [4:0] RES_1_SUM_MOD; wire [5:0] RES_3_SUM_MOD; forward_converter_4_32 fconvA(A, A_3, A_2, A_1); forward_converter_3_17 fconvA3(A_3, A_3_HIGH, A_3_MID, A_3_LOW); forward_converter_3_16 fconvA2(A_2, A_2_HIGH, A_2_MID, A_2_LOW); forward_converter_3_15 fconvA1(A_1, A_1_HIGH, A_1_MID, A_1_LOW); forward_converter_4_32 fconvB(B, B_3, B_2, B_1); forward_converter_3_17 fconvB3(B_3, B_3_HIGH, B_3_MID, B_3_LOW); forward_converter_3_16 fconvB2(B_2, B_2_HIGH, B_2_MID, B_2_LOW); forward_converter_3_15 fconvB1(B_1, B_1_HIGH, B_1_MID, B_1_LOW); mul_channel_2_pow_n_minus_1 mulchlow3(A_3_LOW, B_3_LOW, RES_3_LOW); mul_channel_2_pow_n_minus_1 mulchlow2(A_2_LOW, B_2_LOW, RES_2_LOW); mul_channel_2_pow_n_minus_1 mulchlow1(A_1_LOW, B_1_LOW, RES_1_LOW); mul_channel_2_pow_n mulchmid3(A_3_MID, B_3_MID, RES_3_MID); mul_channel_2_pow_n mulchmid2(A_2_MID, B_2_MID, RES_2_MID); mul_channel_2_pow_n mulchmid1(A_1_MID, B_1_MID, RES_1_MID); mul_channel_2_pow_n_plus_1 mulchhigh3(A_3_HIGH, B_3_HIGH, RES_3_HIGH); mul_channel_2_pow_n_plus_1 mulchhigh2(A_2_HIGH, B_2_HIGH, RES_2_HIGH); mul_channel_2_pow_n_plus_1 mulchhigh1(A_1_HIGH, B_1_HIGH, RES_1_HIGH); assign RES_2 = RES_2_BEFORE_MOD[3:0]; assign RES_1_SUM_MOD = RES_1_BEFORE_MOD[3:0] + RES_1_BEFORE_MOD[7:4] + RES_1_BEFORE_MOD[8:8]; assign RES_3_SUM_MOD = RES_3_BEFORE_MOD[3:0] + 17 - RES_3_BEFORE_MOD[7:4] + 17 - RES_3_BEFORE_MOD[8:8]; mod_15_31 before_rev_low(RES_1_SUM_MOD, RES_1); mod_17_49 before_rev_high(RES_3_SUM_MOD, RES_3); reverse_converter_3_9 revconv3(RES_3_HIGH, RES_3_MID, RES_3_LOW, RES_3_BEFORE_MOD); reverse_converter_3_9 revconv2(RES_2_HIGH, RES_2_MID, RES_2_LOW, RES_2_BEFORE_MOD); reverse_converter_3_9 revconv1(RES_1_HIGH, RES_1_MID, RES_1_LOW, RES_1_BEFORE_MOD); reverse_converter_4_10 revconv(RES_3, RES_2, RES_1, out); endmodule module forward_converter_4_32 (x, x_mod17, x_mod16, x_mod15); input [4:0] x; output [4:0] x_mod17; output [3:0] x_mod16; output [3:0] x_mod15; wire [3:0] x0; wire x1; assign x0 = x[3:0]; assign x1 = x[4]; wire [4:0] x_prom_15; assign x_prom_15 = x0 + x1 ; mod_15_16 mod1(x_prom_15, x_mod15); wire [5:0] x_prom_17; assign x_prom_17 = x0 + 5'd17 - x1 + 0; mod_17_33 mod2(x_prom_17, x_mod17); assign x_mod16 = x[3:0]; endmodule module mod_15_16 (in, out); input [4:0] in; output reg [3:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 7; 8: out = 8; 9: out = 9; 10: out = 10; 11: out = 11; 12: out = 12; 13: out = 13; 14: out = 14; 15: out = 0; 16: out = 1; default: out = 0; endcase end endmodule module mod_17_33 (in, out); input [5:0] in; output reg [4:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 7; 8: out = 8; 9: out = 9; 10: out = 10; 11: out = 11; 12: out = 12; 13: out = 13; 14: out = 14; 15: out = 15; 16: out = 16; 17: out = 0; 18: out = 1; 19: out = 2; 20: out = 3; 21: out = 4; 22: out = 5; 23: out = 6; 24: out = 7; 25: out = 8; 26: out = 9; 27: out = 10; 28: out = 11; 29: out = 12; 30: out = 13; 31: out = 14; 32: out = 15; 33: out = 16; default: out = 0; endcase end endmodule module forward_converter_3_17 (x, x_mod9, x_mod8, x_mod7); input [4:0] x; output [3:0] x_mod9; output [2:0] x_mod8; output [2:0] x_mod7; wire [2:0] x0; wire [1:0] x1; assign x0 = x[2:0]; assign x1 = x[4:3]; wire [3:0] x_prom_7; assign x_prom_7 = x0 + x1 ; mod_7_9 mod1(x_prom_7, x_mod7); wire [4:0] x_prom_9; assign x_prom_9 = x0 + 4'd9 - x1 + 0; mod_9_17 mod2(x_prom_9, x_mod9); assign x_mod8 = x[2:0]; endmodule module mod_7_9 (in, out); input [3:0] in; output reg [2:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 0; 8: out = 1; 9: out = 2; default: out = 0; endcase end endmodule module mod_9_17 (in, out); input [4:0] in; output reg [3:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 7; 8: out = 8; 9: out = 0; 10: out = 1; 11: out = 2; 12: out = 3; 13: out = 4; 14: out = 5; 15: out = 6; 16: out = 7; 17: out = 8; default: out = 0; endcase end endmodule module forward_converter_3_16 (x, x_mod9, x_mod8, x_mod7); input [3:0] x; output [3:0] x_mod9; output [2:0] x_mod8; output [2:0] x_mod7; wire [2:0] x0; wire x1; assign x0 = x[2:0]; assign x1 = x[3]; wire [3:0] x_prom_7; assign x_prom_7 = x0 + x1 ; mod_7_8 mod1(x_prom_7, x_mod7); wire [4:0] x_prom_9; assign x_prom_9 = x0 + 4'd9 - x1 + 0; mod_9_17 mod2(x_prom_9, x_mod9); assign x_mod8 = x[2:0]; endmodule module mod_7_8 (in, out); input [3:0] in; output reg [2:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 0; 8: out = 1; default: out = 0; endcase end endmodule module forward_converter_3_15 (x, x_mod9, x_mod8, x_mod7); input [3:0] x; output [3:0] x_mod9; output [2:0] x_mod8; output [2:0] x_mod7; wire [2:0] x0; wire x1; assign x0 = x[2:0]; assign x1 = x[3]; wire [3:0] x_prom_7; assign x_prom_7 = x0 + x1 ; mod_7_8 mod1(x_prom_7, x_mod7); wire [4:0] x_prom_9; assign x_prom_9 = x0 + 4'd9 - x1 + 0; mod_9_17 mod2(x_prom_9, x_mod9); assign x_mod8 = x[2:0]; endmodule module mod_15_31 (in, out); input [4:0] in; output reg [3:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 7; 8: out = 8; 9: out = 9; 10: out = 10; 11: out = 11; 12: out = 12; 13: out = 13; 14: out = 14; 15: out = 0; 16: out = 1; 17: out = 2; 18: out = 3; 19: out = 4; 20: out = 5; 21: out = 6; 22: out = 7; 23: out = 8; 24: out = 9; 25: out = 10; 26: out = 11; 27: out = 12; 28: out = 13; 29: out = 14; 30: out = 0; 31: out = 1; default: out = 0; endcase end endmodule module mod_17_49 (in, out); input [5:0] in; output reg [4:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 7; 8: out = 8; 9: out = 9; 10: out = 10; 11: out = 11; 12: out = 12; 13: out = 13; 14: out = 14; 15: out = 15; 16: out = 16; 17: out = 0; 18: out = 1; 19: out = 2; 20: out = 3; 21: out = 4; 22: out = 5; 23: out = 6; 24: out = 7; 25: out = 8; 26: out = 9; 27: out = 10; 28: out = 11; 29: out = 12; 30: out = 13; 31: out = 14; 32: out = 15; 33: out = 16; 34: out = 0; 35: out = 1; 36: out = 2; 37: out = 3; 38: out = 4; 39: out = 5; 40: out = 6; 41: out = 7; 42: out = 8; 43: out = 9; 44: out = 10; 45: out = 11; 46: out = 12; 47: out = 13; 48: out = 14; 49: out = 15; default: out = 0; endcase end endmodule // {17 16 15} module reverse_converter_4_10 (x1, x2, x3, out); input [4:0] x1; input [3:0] x2; input [3:0] x3; wire [7:0] a1; wire [7:0] a2; wire [7:0] a3; wire [7:0] sum1; wire [7:0] sum2; wire [7:0] sum3; output [9:0] out; coef_a1_4_10 ca1(x1,a1); coef_a2_4_10 ca2(x2,a2); coef_a3_4_10 ca3(x3,a3); sum_modulo_255_4_10 sm1(a2, a3, sum1); sub_a1_x1_4_10 sm2(a1, x1, sum2); sum_modulo_255_4_10 sm3(sum1, sum2, sum3); assign out[0] = x2[0]; assign out[1] = x2[1]; assign out[2] = x2[2]; assign out[3] = x2[3]; assign out[4] = sum3[0]; assign out[5] = sum3[1]; assign out[6] = sum3[2]; assign out[7] = sum3[3]; assign out[8] = sum3[4]; assign out[9] = sum3[5]; endmodule module coef_a3_4_10 (x3, a3); input [3:0] x3; output [7:0] a3; assign a3[7] = x3[0]; assign a3[6] = x3[3]; assign a3[5] = x3[2]; assign a3[4] = x3[1]; assign a3[3] = x3[0]; assign a3[2] = x3[3]; assign a3[1] = x3[2]; assign a3[0] = x3[1]; endmodule module coef_a2_4_10 (x2, a2); input [3:0] x2; output [7:0] a2; assign a2[7] = ~x2[3]; assign a2[6] = ~x2[2]; assign a2[5] = ~x2[1]; assign a2[4] = ~x2[0]; assign a2[3] = 1; assign a2[2] = 1; assign a2[1] = 1; assign a2[0] = 1; endmodule module coef_a1_4_10 (x1, a1); input [4:0] x1; output [7:0] a1; wire bx; assign bx = x1[4] ^ x1[0]; assign a1[7] = bx; assign a1[6] = x1[3]; assign a1[5] = x1[2]; assign a1[4] = x1[1]; assign a1[3] = bx; assign a1[2] = x1[3]; assign a1[1] = x1[2]; assign a1[0] = x1[1]; endmodule // Sum modulo (2^8 - 1) = 255 module sum_modulo_255_4_10 (in1, in2, out); input [7:0] in1; input [7:0] in2; output reg [7:0] out; wire [8:0] data; wire [8:0] data2; assign data = in1 + in2; assign data2 = in1 + in2 + 1; always @(*) begin if (data2[8] == 1) out <= data2[7:0]; else out <= data[7:0]; end endmodule module sub_a1_x1_4_10 (a1, x1, out); input [7:0] a1; input [4:0] x1; output [7:0] out; assign out = a1 - x1; endmodule // {9 8 7} module reverse_converter_3_9 (x1, x2, x3, out); input [3:0] x1; input [2:0] x2; input [2:0] x3; wire [5:0] a1; wire [5:0] a2; wire [5:0] a3; wire [5:0] sum1; wire [5:0] sum2; wire [5:0] sum3; output [8:0] out; coef_a1_3_9 ca1(x1,a1); coef_a2_3_9 ca2(x2,a2); coef_a3_3_9 ca3(x3,a3); sum_modulo_63_3_9 sm1(a2, a3, sum1); sub_a1_x1_3_9 sm2(a1, x1, sum2); sum_modulo_63_3_9 sm3(sum1, sum2, sum3); assign out[0] = x2[0]; assign out[1] = x2[1]; assign out[2] = x2[2]; assign out[3] = sum3[0]; assign out[4] = sum3[1]; assign out[5] = sum3[2]; assign out[6] = sum3[3]; assign out[7] = sum3[4]; assign out[8] = sum3[5]; endmodule module coef_a3_3_9 (x3, a3); input [2:0] x3; output [5:0] a3; assign a3[5] = x3[0]; assign a3[4] = x3[2]; assign a3[3] = x3[1]; assign a3[2] = x3[0]; assign a3[1] = x3[2]; assign a3[0] = x3[1]; endmodule module coef_a2_3_9 (x2, a2); input [2:0] x2; output [5:0] a2; assign a2[5] = ~x2[2]; assign a2[4] = ~x2[1]; assign a2[3] = ~x2[0]; assign a2[2] = 1; assign a2[1] = 1; assign a2[0] = 1; endmodule module coef_a1_3_9 (x1, a1); input [3:0] x1; output [5:0] a1; wire bx; assign bx = x1[3] ^ x1[0]; assign a1[5] = bx; assign a1[4] = x1[2]; assign a1[3] = x1[1]; assign a1[2] = bx; assign a1[1] = x1[2]; assign a1[0] = x1[1]; endmodule // Sum modulo (2^6 - 1) = 63 module sum_modulo_63_3_9 (in1, in2, out); input [5:0] in1; input [5:0] in2; output reg [5:0] out; wire [6:0] data; wire [6:0] data2; assign data = in1 + in2; assign data2 = in1 + in2 + 1; always @(*) begin if (data2[6] == 1) out <= data2[5:0]; else out <= data[5:0]; end endmodule module sub_a1_x1_3_9 (a1, x1, out); input [5:0] a1; input [3:0] x1; output [5:0] out; assign out = a1 - x1; endmodule module mul_channel_2_pow_n_plus_1 (A, B, out); input [3:0] A; input [3:0] B; output [3:0] out; wire [2:0] invA; wire [2:0] invB; wire [2:0] nA_0; wire [3:0] P_0; wire [2:0] nA_1; wire [3:0] P_1; wire [2:0] nA_2; wire [3:0] P_2; reg [4:0] P_ALL; assign invA[0] = ~A[0]; assign invA[1] = ~A[1]; assign invA[2] = ~A[2]; assign invB[0] = ~B[0]; assign invB[1] = ~B[1]; assign invB[2] = ~B[2]; assign nA_0[0] = A[0]; assign nA_0[1] = A[1]; assign nA_0[2] = A[2]; assign nA_1[0] = ~A[2]; assign nA_1[1] = A[0]; assign nA_1[2] = A[1]; assign nA_2[0] = ~A[1]; assign nA_2[1] = ~A[2]; assign nA_2[2] = A[0]; assign P_0 = (B[0]*nA_0); assign P_1 = (B[1]*nA_1) + !B[1]*1'b1; assign P_2 = (B[2]*nA_2) + !B[2]*2'b11; mod_9_26 mod(P_ALL, out); always @(*) begin if ((A == 4'd8) && (B == 4'd8)) P_ALL <= 1; else if (A == 4'd8) begin P_ALL <= invB + 2; end else if (B == 4'd8) begin P_ALL <= invA + 2; end else begin P_ALL <= P_0 + P_1 + P_2 + 5; end end endmodule module mod_9_26 (in, out); input [4:0] in; output reg [3:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 7; 8: out = 8; 9: out = 0; 10: out = 1; 11: out = 2; 12: out = 3; 13: out = 4; 14: out = 5; 15: out = 6; 16: out = 7; 17: out = 8; 18: out = 0; 19: out = 1; 20: out = 2; 21: out = 3; 22: out = 4; 23: out = 5; 24: out = 6; 25: out = 7; 26: out = 8; default: out = 0; endcase end endmodule module mul_channel_2_pow_n_minus_1 (a, b, out); // Умножитель input [2:0] a, b; wire [4:0] intermediate; output [2:0] out; wire [2:0] p0, p1, p2; // ФОРМИРОВАНИЕ ЧАСТИЧНЫХ ПРОИЗВЕДЕНИЙ assign p0 = a[2:0] * b[0]; assign p1 = {(a[1:0]*b[1]), a[2]*b[1]}; assign p2 = {(a[0]*b[2]), a[2:1]*b[2]}; assign intermediate = p0 + p1 + p2; mod_7_19 mod(intermediate, out); endmodule // Faster but more area module mod_7_19 (in, out); input [4:0] in; output reg [2:0] out; always @ (in) begin // we have small max value so we can use table here case (in) 0: out = 0; 1: out = 1; 2: out = 2; 3: out = 3; 4: out = 4; 5: out = 5; 6: out = 6; 7: out = 0; 8: out = 1; 9: out = 2; 10: out = 3; 11: out = 4; 12: out = 5; 13: out = 6; 14: out = 0; 15: out = 1; 16: out = 2; 17: out = 3; 18: out = 4; 19: out = 5; default: out = 0; endcase end endmodule module mul_channel_2_pow_n (A, B, out); input [2:0] A; input [2:0] B; output [2:0] out; wire [4:0] intermediate; wire [2:0] p0, p1, p2; assign p0 = A[2:0] * B[0]; assign p1 = (A[1:0] << 1) * B[1]; assign p2 = (A[0] << 2) * B[2]; assign intermediate = p0 + p1 + p2; assign out = intermediate[2:0]; endmodule module atest_bench(); wire [9:0] out; reg [4:0] in1; reg [4:0] in2; integer i, j, k, l, m, n; integer fori, forj, forz; reg dummy; mul_binary_5 r1(in1, in2, out); initial begin /* Full range */ for (fori = 0; fori < 32; fori = fori + 1) begin for (forj = 0; forj < 32; forj = forj + 1) begin in1 = fori; in2 = forj; #1 dummy = 1; l = fori*forj; $display ("!!! Input = (%d, %d) Res = (%d) Expect = (%d)", fori, forj, out, l); i = out; if (i != l) begin $display ("!!! Error (%d, %d, %d, %d)!!!", fori, forj, i, l); end #1 dummy = 1; end end end endmodule

Description: Generator of conventional binary multiplier, where input operands have n bit length and output has 2*n bit length. Multiplication is done based on RNS arithmetic and special moduli sets {2ⁿ-1, 2ⁿ, 2ⁿ+1}, which are used twice in hierarchy. As the result, nine parallel channels are formed. However, two stages of direct and inverse converters are needed.

Work scheme


First results (05.2013): For 32 bits this method is slower and takes more area than conventional RNS multiplication with basis {2ⁿ-1, 2ⁿ, 2ⁿ+1}. Delay is 6.87 compared to 4.30, area is 43401 compared to 31879. Possible variants of speed-up: merging of two levels of direct converters into one due to new mathematical tools, merging of reverse converters and intermediate module calculation. More research in this direction is needed.

---