Описание работы универсального прямого преобразователя

Постановка задачи

Требуется реализовать микроэлектронное устройство выполняющее преобразование из позиционного представления в модулярный код. Разработку будем вести на языке Verilog. Пусть задано входное число $X$ в позиционном виде разрядности $N$-бит. Требуется найти остаток от его деления (вычет) на каждое число из набора, образующих модулярный базис ${p1, p2, ... pN}$. Так как алгоритм вычисления остатков будет одинаков для каждого из них, то рассмотрим произвольное число из набора $p$ размерности $k$-бит.

Схема этого блока с входами и выходами:

Здесь:

• $0 \le X < 2^N$
• $0 \le OUT < p$
• $p$ - константа заданная на этапе проектирования

Специальные случаи

При некоторых соотношениях между входными данными и заданным p, модуль взятия остатка от деления можно реализовать простейшим образом. Рассмотрим такие случаи:

Модуль больше входных данных

$p > 2^N$ - в этом случае выходные данные совпадают с входными, то есть $OUT = X$.

1. module forward_conv_module_23 (in, out);

2. 	input [3:0] in; // Max value: 15

3. 	output [4:0] out; // Max value: 22

4. 	assign out = {1'd0,in[3:0]};

5. endmodule

Модуль равен степени двойки

$p = 2^t$ - в этом случае выходные данные равны младшим t-бит входных данных, то есть $OUT = X[t:0]$.

1. module forward_conv_module_16 (out0, in);

2. 	output [3:0] out0; // Max value: 15

3. 	input [7:0] in; // Max value: 255

4. 	assign out0 = in[3:0];

5. endmodule

N незначительно превосходит разрядность модуля

В этом случае достаточно проверить в какой из диапазонов вида $[0;p), [p;2 \cdot p), [2 \cdot p;3 \cdot p), ...$ попадает $X$ и вычесть из него поправочный коэффициент, соответствующий диапазону. $0$ для $[0;p)$, $p$ для $[p;2 \cdot p)$, $2 \cdot p$ для $[p;2 \cdot p)$ и.т.д.

1. module mod_253_511 (in, out);

2. 	input [8:0] in;

3. 	output reg [7:0] out;

4. 	always @ (in)

5. 	begin

6. 		if (in < 8'd253)

7. 		begin

8. 			out = in;

9. 		end

10. 		else if (in < 9'd506)

11. 		begin

12. 			out = in - 8'd253;

13. 		end

14. 		else

15. 		begin

16. 			out = in - 9'd506;

17. 		end

18. 	end

19. endmodule

21. module forward_conv_module_253 (in, out);

22. 	input [8:0] in; // Max value: 511

23. 	output [7:0] out; // Max value: 252

24. 	mod_253_511 inst(in, out);

25. endmodule

Общий случай

Представим входные данные $X$ в следующем виде:

• $X = 2^0 \cdot X[0] + 2^1 \cdot X[1] + 2^2 \cdot X[2] + ... + 2^{N-1} \cdot X[N-1]$

и воспользуемся следующими свойствами вычетов:

• $|A + B|_p = ||A|_p + |B|_p|_p$ и $|A \cdot B|_p = ||A|_p \cdot |B|_p|_p$

Тогда вычет X по модулю p можно записать следующим образом:

$|X|_p = |2^0 \cdot X[0] + 2^1 \cdot X[1] + 2^2 \cdot X[2] + ... + 2^{N-1} \cdot X[N-1]|_p =$

$= ||2^0|_p \cdot X[0] + |2^1|_p \cdot X[1] + |2^2|_p \cdot X[2] + ... + |2^{N-1}|_p \cdot X[N-1]|_p =$

$= |A_0 \cdot X[0] + A_1 \cdot X[1] + A_2 \cdot X[2] + ... + A_{N-1} \cdot X[N-1]|_p$.

Константы вида $A_i = |2^i|_p$ могут быть рассчитаны на этапе проектирования устройства и каждая константа не превосходит значение $p$. А общее значение выражения $SUM = (A_0 \cdot X[0] + ... + A_{N-1} \cdot X[N-1]) \le (p-1)*N$. Так как коэффициенты $A_i$ известны, то оценку максимально возможного значения $SUM$ можно сократить ещё больше.

Таким образом что бы посчитать значение вычета $|X|_p$ требуется выполнить две операции: 1) Найти сумму $SUM = (A_0 \cdot X[0] + ... + A_{N-1} \cdot X[N-1]) \le (p-1)*N$. 2) Определить в какой интервал вида $[0;p), [p;2 \cdot p), [2 \cdot p;3 \cdot p), ... [(N-1) \cdot p;N \cdot p)$ попадает значение $SUM$ и вычесть из него соответствующее значение $0$ для $[0;p)$, $p$ для $[p;2 \cdot p)$, $2 \cdot p$ для $[p;2 \cdot p)$ и.т.д.

Численный пример

Пусть на входе у нас подается 10-битное число $X$ и нам требуется найти его вычет (т.е. остаток от деления) на число 5. Запишем:

$X = 2^0 \cdot X[0] + 2^1 \cdot X[1] + 2^2 \cdot X[2] + ... + 2^{9} \cdot X[9]$

$X = X[0] + 2 \cdot X[1] + 4 \cdot X[2] + ... + 512 \cdot X[9]$

$|X|_5 = |X[0] + |2|_5 \cdot X[1] + |4|_5 \cdot X[2] + ... + |512|_5 \cdot X[9]|_p$

Замечание: значение $X[i]$ равно 0 или 1, т.е. меньше 5 поэтому $|X[i]|_p = X[i]$

$|X|_5 = |SUM|_5 = |X[0] + 2 \cdot X[1] + 4 \cdot X[2] + 3 \cdot X[3] + 1 \cdot X[4] + 2 \cdot X[5] + 4 \cdot X[6] + 3 \cdot X[7] + 1 \cdot X[8] + 2 \cdot X[9]|_5$.

Что бы найти максимально возможное значение $SUM$ достаточно сложить все коэффициенты $A_i$.

$SUM_{MAX} = 1+2+4+3+1+2+4+3+1+2 = 23$.

То есть что бы найти значение $|X|_5$, надо проверить в какой из следующих интервалов попадает значение $SUM$.

Если $0 <= SUM < 5$, то $|X|_5 = SUM$

Если $5 <= SUM < 10$, то $|X|_5 = SUM - 5$

Если $10 <= SUM < 15$, то $|X|_5 = SUM - 10$

Если $15 <= SUM < 20$, то $|X|_5 = SUM - 15$

Если $20 <= SUM < 25$, то $|X|_5 = SUM - 20$

Verilog-код для численного примера

1. module mod_5_23 (in, out);

2. 	input [4:0] in;

3. 	output reg [2:0] out;

4. 	always @ (in)

5. 	begin

6. 		if (in < 3'd5)

7. 		begin

8. 			out = in;

9. 		end

10. 		else if (in < 4'd10)

11. 		begin

12. 			out = in - 3'd5;

13. 		end

14. 		else if (in < 4'd15)

15. 		begin

16. 			out = in - 4'd10;

17. 		end

18. 		else if (in < 5'd20)

19. 		begin

20. 			out = in - 4'd15;

21. 		end

22. 		else

23. 		begin

24. 			out = in - 5'd20;

25. 		end

26. 	end

27. endmodule

29. module forward_conv_module_5 (in, out);

30. 	input [9:0] in; // Max value: 1023

31. 	output [2:0] out; // Max value: 4

32. 	wire [4:0] inter1; // Max value: 23

33. 	assign inter1 = in[2:0] + 3*in[3] + in[4] + 2*in[5] + 4*in[6] + 3*in[7] + in[8] + 2*in[9];

34. 	mod_5_23 inst(inter1, out);

35. endmodule