Bertrand SelvaThis MATLAB/Octave script automatically computes look-up tables (LUTs) for a Residue Number System (RNS) with a given set of moduli. It generates:
- The total product
M = m1 * m2 * ... * mn - The reconstruction coefficients
Ai - An example table
Tjfor a modulusmj - Verilog-style outputs (
case / endcase) ready to integrate into your FPGA design
Method
The reconstruction follows the classical Chinese Remainder Theorem (CRT):
M = product of all moduli Mi = M / mi Ai = (Mi * inverse(Mi mod mi, mi)) mod M Tm(r) = (Ai * r) mod M for r = 0 .. mi-1
Each Tm table stores precomputed modular residues, allowing fast RNS operations on FPGA
without any division or modulo logic.
MATLAB/OCTAVE Script
close all;
clear all;
clc;
format long g;
%% RNS LUT generation
%% Moduli list
moduli = [7 11 13 15 17 19 23 29 31];
%% Compute M
M = 1;
for i = 1:length(moduli)
M = M * moduli(i);
end
disp(M); % 100280245065
%% Coefficients Ai
Ai = zeros(1, numel(moduli)); % preallocation
for i = 1:numel(moduli)
m = moduli(i);
Mi = M / m; % M_i
t = mod(Mi, m); % (M_i mod m)
[g, x, ~] = gcd(t, m); % t*x + m*y = g
if g ~= 1
error('No modular inverse for m=%d (gcd=%d).', m, g);
end
inv_t = mod(x, m); % inverse of t modulo m
Ai(i) = mod(inv_t * Mi, M); % A_i = (M_i * inv_t) mod M
end
%% Example LUT Tj (e.g., j=9 -> m = 31)
j = 9; % choose index in 'moduli'
mj = moduli(j);
Tj = zeros(1, mj); % Tj(r+1) = (Ai(j)*r) mod M
for r = 0 : mj-1
Tj(r+1) = mod(Ai(j) * r, M);
end
% Display
disp('Ai ='); disp(Ai);
disp(['T' num2str(mj) '(r) for r=0..' num2str(mj-1) ':']);
disp(Tj);
%% Verilog-like table generator
for j = 1:numel(moduli)
m = moduli(j);
fprintf('function [36:0] T%d;\n', m);
fprintf(' input [4:0] r;\n begin\n case (r)\n');
for r = 0:m-1
fprintf(' 5''d%-2d : T%d = 37''d%u;\n', r, m, mod(Ai(j)*r,M));
end
fprintf(' default: T%d = 37''d0;\n endcase\n end\nendfunction\n\n', m);
end
Notes
- Chosen moduli:
[7, 11, 13, 15, 17, 19, 23, 29, 31] - Total product: M = 100,280,245,065
- Because
2^37 = 137,438,953,472 > M, 37-bit wide signals are sufficient. - Each input
rfits in 5 bits (max modulus = 31). - In this configuration, M is large enough to prevent overflow when using Q15 coefficients in an RNS-based FIR filter (the goal project).
Conclusion
This log automates the generation of RNS LUTs and Verilog snippets.
Run the script, copy the output, and integrate it directly into your FPGA design without manual editing. Because Typing 300 Constants by Hand Is for Humans...
Results
function [36:0] T7;
input [4:0] r;
begin
case (r)
5'd0 : T7 = 37'd0;
5'd1 : T7 = 37'd28651498590;
5'd2 : T7 = 37'd57302997180;
5'd3 : T7 = 37'd85954495770;
5'd4 : T7 = 37'd14325749295;
5'd5 : T7 = 37'd42977247885;
5'd6 : T7 = 37'd71628746475;
default: T7 = 37'd0;
endcase
end
endfunction
function [36:0] T11;
input [4:0] r;
begin
case (r)
5'd0 : T11 = 37'd0;
5'd1 : T11 = 37'd91163859150;
5'd2 : T11 = 37'd82047473235;
5'd3 : T11 = 37'd72931087320;
5'd4 : T11 = 37'd63814701405;
5'd5 : T11 = 37'd54698315490;
5'd6 : T11 = 37'd45581929575;
5'd7 : T11 = 37'd36465543660;
5'd8 : T11 = 37'd27349157745;
5'd9 : T11 = 37'd18232771830;
5'd10 : T11 = 37'd9116385915;
default: T11 = 37'd0;
endcase
end
endfunction
function [36:0] T13;
input [4:0] r;
begin
case (r)
5'd0 : T13 = 37'd0;
5'd1 : T13 = 37'd53997055035;
5'd2 : T13 = 37'd7713865005;
5'd3 : T13 = 37'd61710920040;
5'd4 : T13 = 37'd15427730010;
5'd5 : T13 = 37'd69424785045;
5'd6 : T13 = 37'd23141595015;
5'd7 : T13 = 37'd77138650050;
5'd8 : T13 = 37'd30855460020;
5'd9 : T13 = 37'd84852515055;
5'd10 : T13 = 37'd38569325025;
5'd11 : T13 = 37'd92566380060;
5'd12 : T13 = 37'd46283190030;
default: T13 = 37'd0;
endcase
end
endfunction
function [36:0] T15;
input [4:0] r;
begin
case (r)
5'd0 : T15 = 37'd0;
5'd1 : T15 = 37'd6685349671;
5'd2 : T15 = 37'd13370699342;
5'd3 : T15 = 37'd20056049013;
5'd4 : T15 = 37'd26741398684;
5'd5 : T15 = 37'd33426748355;
5'd6 : T15 = 37'd40112098026;
5'd7 : T15 = 37'd46797447697;
5'd8 : T15 = 37'd53482797368;
5'd9 : T15 = 37'd60168147039;
5'd10 : T15 = 37'd66853496710;
5'd11 : T15 = 37'd73538846381;
5'd12 : T15 = 37'd80224196052;
5'd13 : T15 = 37'd86909545723;
5'd14 : T15 = 37'd93594895394;
default: T15 = 37'd0;
endcase
end
endfunction
function [36:0] T17;
input [4:0] r;
begin
case (r)
5'd0 : T17 = 37'd0;
5'd1 : T17 = 37'd17696513835;
5'd2 : T17 = 37'd35393027670;
5'd3 : T17 = 37'd53089541505;
5'd4 : T17 = 37'd70786055340;
5'd5 : T17 = 37'd88482569175;
5'd6 : T17 = 37'd5898837945;
5'd7 : T17 = 37'd23595351780;
5'd8 : T17 = 37'd41291865615;
5'd9 : T17 = 37'd58988379450;
5'd10 : T17 = 37'd76684893285;
5'd11 : T17 = 37'd94381407120;
5'd12 : T17 = 37'd11797675890;
5'd13 : T17 = 37'd29494189725;
5'd14 : T17 = 37'd47190703560;
5'd15 : T17 = 37'd64887217395;
5'd16 : T17 = 37'd82583731230;
default: T17 = 37'd0;
endcase
end
endfunction
function [36:0] T19;
input [4:0] r;
begin
case (r)
5'd0 : T19 = 37'd0;
5'd1 : T19 = 37'd58056983985;
5'd2 : T19 = 37'd15833722905;
5'd3 : T19 = 37'd73890706890;
5'd4 : T19 = 37'd31667445810;
5'd5 : T19 = 37'd89724429795;
5'd6 : T19 = 37'd47501168715;
5'd7 : T19 = 37'd5277907635;
5'd8 : T19 = 37'd63334891620;
5'd9 : T19 = 37'd21111630540;
5'd10 : T19 = 37'd79168614525;
5'd11 : T19 = 37'd36945353445;
5'd12 : T19 = 37'd95002337430;
5'd13 : T19 = 37'd52779076350;
5'd14 : T19 = 37'd10555815270;
5'd15 : T19 = 37'd68612799255;
5'd16 : T19 = 37'd26389538175;
5'd17 : T19 = 37'd84446522160;
5'd18 : T19 = 37'd42223261080;
default: T19 = 37'd0;
endcase
end
endfunction
function [36:0] T23;
input [4:0] r;
begin
case (r)
5'd0 : T23 = 37'd0;
5'd1 : T23 = 37'd87200213100;
5'd2 : T23 = 37'd74120181135;
5'd3 : T23 = 37'd61040149170;
5'd4 : T23 = 37'd47960117205;
5'd5 : T23 = 37'd34880085240;
5'd6 : T23 = 37'd21800053275;
5'd7 : T23 = 37'd8720021310;
5'd8 : T23 = 37'd95920234410;
5'd9 : T23 = 37'd82840202445;
5'd10 : T23 = 37'd69760170480;
5'd11 : T23 = 37'd56680138515;
5'd12 : T23 = 37'd43600106550;
5'd13 : T23 = 37'd30520074585;
5'd14 : T23 = 37'd17440042620;
5'd15 : T23 = 37'd4360010655;
5'd16 : T23 = 37'd91560223755;
5'd17 : T23 = 37'd78480191790;
5'd18 : T23 = 37'd65400159825;
5'd19 : T23 = 37'd52320127860;
5'd20 : T23 = 37'd39240095895;
5'd21 : T23 = 37'd26160063930;
5'd22 : T23 = 37'd13080031965;
default: T23 = 37'd0;
endcase
end
endfunction
function [36:0] T29;
input [4:0] r;
begin
case (r)
5'd0 : T29 = 37'd0;
5'd1 : T29 = 37'd41495273820;
5'd2 : T29 = 37'd82990547640;
5'd3 : T29 = 37'd24205576395;
5'd4 : T29 = 37'd65700850215;
5'd5 : T29 = 37'd6915878970;
5'd6 : T29 = 37'd48411152790;
5'd7 : T29 = 37'd89906426610;
5'd8 : T29 = 37'd31121455365;
5'd9 : T29 = 37'd72616729185;
5'd10 : T29 = 37'd13831757940;
5'd11 : T29 = 37'd55327031760;
5'd12 : T29 = 37'd96822305580;
5'd13 : T29 = 37'd38037334335;
5'd14 : T29 = 37'd79532608155;
5'd15 : T29 = 37'd20747636910;
5'd16 : T29 = 37'd62242910730;
5'd17 : T29 = 37'd3457939485;
5'd18 : T29 = 37'd44953213305;
5'd19 : T29 = 37'd86448487125;
5'd20 : T29 = 37'd27663515880;
5'd21 : T29 = 37'd69158789700;
5'd22 : T29 = 37'd10373818455;
5'd23 : T29 = 37'd51869092275;
5'd24 : T29 = 37'd93364366095;
5'd25 : T29 = 37'd34579394850;
5'd26 : T29 = 37'd76074668670;
5'd27 : T29 = 37'd17289697425;
5'd28 : T29 = 37'd58784971245;
default: T29 = 37'd0;
endcase
end
endfunction
function [36:0] T31;
input [4:0] r;
begin
case (r)
5'd0 : T31 = 37'd0;
5'd1 : T31 = 37'd16174233075;
5'd2 : T31 = 37'd32348466150;
5'd3 : T31 = 37'd48522699225;
5'd4 : T31 = 37'd64696932300;
5'd5 : T31 = 37'd80871165375;
5'd6 : T31 = 37'd97045398450;
5'd7 : T31 = 37'd12939386460;
5'd8 : T31 = 37'd29113619535;
5'd9 : T31 = 37'd45287852610;
5'd10 : T31 = 37'd61462085685;
5'd11 : T31 = 37'd77636318760;
5'd12 : T31 = 37'd93810551835;
5'd13 : T31 = 37'd9704539845;
5'd14 : T31 = 37'd25878772920;
5'd15 : T31 = 37'd42053005995;
5'd16 : T31 = 37'd58227239070;
5'd17 : T31 = 37'd74401472145;
5'd18 : T31 = 37'd90575705220;
5'd19 : T31 = 37'd6469693230;
5'd20 : T31 = 37'd22643926305;
5'd21 : T31 = 37'd38818159380;
5'd22 : T31 = 37'd54992392455;
5'd23 : T31 = 37'd71166625530;
5'd24 : T31 = 37'd87340858605;
5'd25 : T31 = 37'd3234846615;
5'd26 : T31 = 37'd19409079690;
5'd27 : T31 = 37'd35583312765;
5'd28 : T31 = 37'd51757545840;
5'd29 : T31 = 37'd67931778915;
5'd30 : T31 = 37'd84106011990;
default: T31 = 37'd0;
endcase
end
endfunction
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.