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

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Содержание

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

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

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

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

Вычислитель остатка от деления.png

Здесь:

  • 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
  20.  
  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) и.т.д.

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

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. 	// we have small max value so we can use table here
  7. 	case (in)
  8. 		0: out = 0;
  9. 		1: out = 1;
  10. 		2: out = 2;
  11. 		3: out = 3;
  12. 		4: out = 4;
  13. 		5: out = 0;
  14. 		6: out = 1;
  15. 		7: out = 2;
  16. 		8: out = 3;
  17. 		9: out = 4;
  18. 		10: out = 0;
  19. 		11: out = 1;
  20. 		12: out = 2;
  21. 		13: out = 3;
  22. 		14: out = 4;
  23. 		15: out = 0;
  24. 		16: out = 1;
  25. 		17: out = 2;
  26. 		18: out = 3;
  27. 		19: out = 4;
  28. 		20: out = 0;
  29. 		21: out = 1;
  30. 		22: out = 2;
  31. 		23: out = 3;
  32. 		default: out = 0;
  33. 	endcase
  34. 	end
  35. endmodule
  36.  
  37. module forward_conv_module_5 (in, out);
  38. 	input [9:0] in; // Max value: 1023
  39. 	output [2:0] out; // Max value: 4
  40. 	wire [4:0] inter1; // Max value: 23
  41. 	assign inter1 = in[2:0] + 3*in[3] + in[4] + 2*in[5] + 4*in[6] + 3*in[7] + in[8] + 2*in[9];
  42. 	mod_5_23 inst(inter1, out);
  43. endmodule

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация