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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
(Новая страница: «== Описание работы универсального прямого преобразователя из позиционного представлени…»)
 
 
(не показано 6 промежуточных версии этого же участника)
Строка 3: Строка 3:
 
== Постановка задачи ==
 
== Постановка задачи ==
  
−
Требуется реализовать микроэлектронное устройство выполняющее преобразование из позиционного представления в модулярный код. Разработку будем вести на языке Verilog. Пусть задано входное число <math>X</math> в позиционном виде разрядности <math>N</math>-бит. Требуется найти остаток от его деления на каждое число из набора, образующих модулярный базис <math>{p1, p2, ... pN}</math>. Так как алгоритм вычисления остатков будет одинаков для каждого из них, то рассмотрим произвольное число <math>p</math> размерности <math>k</math>-бит.
+
Требуется реализовать микроэлектронное устройство выполняющее преобразование из позиционного представления в модулярный код. Разработку будем вести на языке Verilog. Пусть задано входное число <math>X</math> в позиционном виде разрядности <math>N</math>-бит. Требуется найти остаток от его деления (вычет) на каждое число из набора, образующих модулярный базис <math>{p_1, p_2, ... p_m}</math>. Так как алгоритм вычисления остатков будет одинаков для каждого из них, то рассмотрим произвольное число из набора <math>p</math> размерности <math>k</math>-бит.
  
 
Схема этого блока с входами и выходами:
 
Схема этого блока с входами и выходами:
Строка 13: Строка 13:
 
* <math>0 \le OUT < p</math>
 
* <math>0 \le OUT < p</math>
 
* <math>p</math> - константа заданная на этапе проектирования
 
* <math>p</math> - константа заданная на этапе проектирования
 +
 +
== Специальные случаи ==
 +
 +
При некоторых соотношениях между входными данными и заданным p, модуль взятия остатка от деления можно реализовать простейшим образом. Рассмотрим такие случаи:
 +
 +
=== Модуль больше входных данных ===
 +
 +
<math>p > 2^N</math> - в этом случае выходные данные совпадают с входными, то есть <math>OUT = X</math>.
 +
 +
 +
<source lang="verilog" line>
 +
module forward_conv_module_23 (in, out);
 +
input [3:0] in; // Max value: 15
 +
output [4:0] out; // Max value: 22
 +
assign out = {1'd0,in[3:0]};
 +
endmodule
 +
</source>
 +
 +
=== Модуль равен степени двойки ===
 +
 +
<math>p = 2^t</math> - в этом случае выходные данные равны младшим t-бит входных данных, то есть <math>OUT = X[t:0]</math>.
 +
 +
 +
<source lang="verilog" line>
 +
module forward_conv_module_16 (out0, in);
 +
output [3:0] out0; // Max value: 15
 +
input [7:0] in; // Max value: 255
 +
assign out0 = in[3:0];
 +
endmodule
 +
</source>
 +
 +
=== N незначительно превосходит разрядность модуля ===
 +
 +
В этом случае достаточно проверить в какой из диапазонов вида <math>[0;p), [p;2 \cdot p), [2 \cdot p;3 \cdot p), ...</math> попадает <math>X</math> и вычесть из него поправочный коэффициент, соответствующий диапазону. <math>0</math> для <math>[0;p)</math>, <math>p</math> для <math>[p;2 \cdot p)</math>, <math>2 \cdot p</math> для <math>[2 \cdot p;3 \cdot p)</math> и.т.д.
 +
 +
 +
<source lang="verilog" line>
 +
module mod_253_511 (in, out);
 +
input [8:0] in;
 +
output reg [7:0] out;
 +
always @ (in)
 +
begin
 +
if (in < 8'd253)
 +
begin
 +
out = in;
 +
end
 +
else if (in < 9'd506)
 +
begin
 +
out = in - 8'd253;
 +
end
 +
else
 +
begin
 +
out = in - 9'd506;
 +
end
 +
end
 +
endmodule
 +
 +
module forward_conv_module_253 (in, out);
 +
input [8:0] in; // Max value: 511
 +
output [7:0] out; // Max value: 252
 +
mod_253_511 inst(in, out);
 +
endmodule
 +
</source>
 +
 +
== Общий случай ==
 +
 +
Представим входные данные <math>X</math> в следующем виде:
 +
* <math>X = 2^0 \cdot X[0] + 2^1 \cdot X[1] + 2^2 \cdot X[2] + ... + 2^{N-1} \cdot X[N-1]</math>
 +
и воспользуемся следующими свойствами вычетов:
 +
* <math>|A + B|_p = ||A|_p + |B|_p|_p</math> и <math>|A \cdot B|_p = ||A|_p \cdot |B|_p|_p</math>
 +
Тогда вычет X по модулю p можно записать следующим образом:
 +
: <math>|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 =</math>
 +
: <math>= ||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 =</math>
 +
: <math>= |A_0 \cdot X[0] + A_1 \cdot X[1] + A_2 \cdot X[2] + ... + A_{N-1} \cdot X[N-1]|_p</math>.
 +
 +
Константы вида <math>A_i = |2^i|_p</math> могут быть рассчитаны на этапе проектирования устройства и каждая константа не превосходит значение <math>p</math>. А общее значение выражения <math>SUM = (A_0 \cdot X[0] + ... + A_{N-1} \cdot X[N-1]) \le (p-1)*N</math>. Так как коэффициенты <math>A_i</math> известны, то оценку максимально возможного значения <math>SUM</math> можно сократить ещё больше.
 +
 +
Таким образом что бы посчитать значение вычета <math>|X|_p</math> требуется выполнить две операции:
 +
1) Найти сумму <math>SUM = (A_0 \cdot X[0] + ... + A_{N-1} \cdot X[N-1]) \le (p-1)*N</math>.
 +
2) Определить в какой интервал вида <math>[0;p), [p;2 \cdot p), [2 \cdot p;3 \cdot p), ... [(N-1) \cdot p;N \cdot p)</math> попадает значение <math>SUM</math> и вычесть из него соответствующее значение <math>0</math> для <math>[0;p)</math>, <math>p</math> для <math>[p;2 \cdot p)</math>, <math>2 \cdot p</math> для <math>[p;2 \cdot p)</math> и.т.д.
 +
 +
=== Численный пример ===
 +
 +
Пусть на входе у нас подается 10-битное число <math>X</math> и нам требуется найти его вычет (т.е. остаток от деления) на число 5. Запишем:
 +
: <math>X = 2^0 \cdot X[0] + 2^1 \cdot X[1] + 2^2 \cdot X[2] + ... + 2^{9} \cdot X[9]</math>
 +
: <math>X = X[0] + 2 \cdot X[1] + 4 \cdot X[2] + ... + 512 \cdot X[9]</math>
 +
: <math>|X|_5 = |X[0] + |2|_5 \cdot X[1] + |4|_5 \cdot X[2] + ... + |512|_5 \cdot X[9]|_p</math>
 +
Замечание: значение <math>X[i]</math> равно 0 или 1, т.е. меньше 5 поэтому <math>|X[i]|_p = X[i]</math>
 +
: <math>|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</math>.
 +
Что бы найти максимально возможное значение <math>SUM</math> достаточно сложить все коэффициенты <math>A_i</math>.
 +
: <math>SUM_{MAX} = 1+2+4+3+1+2+4+3+1+2 = 23</math>.
 +
 +
То есть что бы найти значение <math>|X|_5</math>, надо проверить в какой из следующих интервалов попадает значение <math>SUM</math>.
 +
: Если <math>0 <= SUM < 5</math>, то <math>|X|_5 = SUM</math>
 +
: Если <math>5 <= SUM < 10</math>, то <math>|X|_5 = SUM - 5</math>
 +
: Если <math>10 <= SUM < 15</math>, то <math>|X|_5 = SUM - 10</math>
 +
: Если <math>15 <= SUM < 20</math>, то <math>|X|_5 = SUM - 15</math>
 +
: Если <math>20 <= SUM < 25</math>, то <math>|X|_5 = SUM - 20</math>
 +
 +
=== Verilog-код для численного примера ===
 +
 +
<source lang="verilog" line>
 +
module mod_5_23 (in, out);
 +
input [4:0] in;
 +
output reg [2:0] out;
 +
always @ (in)
 +
begin
 +
if (in < 3'd5)
 +
begin
 +
out = in;
 +
end
 +
else if (in < 4'd10)
 +
begin
 +
out = in - 3'd5;
 +
end
 +
else if (in < 4'd15)
 +
begin
 +
out = in - 4'd10;
 +
end
 +
else if (in < 5'd20)
 +
begin
 +
out = in - 4'd15;
 +
end
 +
else
 +
begin
 +
out = in - 5'd20;
 +
end
 +
end
 +
endmodule
 +
 +
module forward_conv_module_5 (in, out);
 +
input [9:0] in; // Max value: 1023
 +
output [2:0] out; // Max value: 4
 +
wire [4:0] inter1; // Max value: 23
 +
assign inter1 = in[2:0] + 3*in[3] + in[4] + 2*in[5] + 4*in[6] + 3*in[7] + in[8] + 2*in[9];
 +
mod_5_23 inst(inter1, out);
 +
endmodule
 +
</source>
 +
 +
== Конвейеризация преобразователя ==
 +
 +
* Так как в преобразователе есть два четко выраженных этапа, то в синхронных устройствах можно увеличить частоту работы преобразователя, за счет увеличения тактов вычисления с 1 до 2. На первом такте вычисляется сумма <math>SUM</math>, на втором ищется интервал, куда она попадает и затем корректируется с помощью вычитания.
 +
* Если требуется дальнейшее увеличение тактовой частоты, то можно большой многовходовой сумматор из первого этапа сделать пирамидальным, с конвейеризацией каждой ступени пирамиды.
 +
 +
== Генератор Verilog ==
 +
 +
* [http://vscripts.ru/2013/forward-converter-universal.php Генератор Verilog универсального прямого преобразователя для произвольных модулей]
 +
 +
== Результаты моделирования ==
 +
 +
* [[Результаты синтеза универсальных прямых преобразователей для простых модулей в пределах 8 бит]]

Текущая версия на 11:29, 18 декабря 2013

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

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

Требуется реализовать микроэлектронное устройство выполняющее преобразование из позиционного представления в модулярный код. Разработку будем вести на языке Verilog. Пусть задано входное число X в позиционном виде разрядности N-бит. Требуется найти остаток от его деления (вычет) на каждое число из набора, образующих модулярный базис {p_1, p_2, ... p_m}. Так как алгоритм вычисления остатков будет одинаков для каждого из них, то рассмотрим произвольное число из набора 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 для [2 \cdot p;3 \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) и.т.д.

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

Пусть на входе у нас подается 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
  28.  
  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

Конвейеризация преобразователя

  • Так как в преобразователе есть два четко выраженных этапа, то в синхронных устройствах можно увеличить частоту работы преобразователя, за счет увеличения тактов вычисления с 1 до 2. На первом такте вычисляется сумма SUM, на втором ищется интервал, куда она попадает и затем корректируется с помощью вычитания.
  • Если требуется дальнейшее увеличение тактовой частоты, то можно большой многовходовой сумматор из первого этапа сделать пирамидальным, с конвейеризацией каждой ступени пирамиды.

Генератор Verilog

Результаты моделирования

Источник — «https://vscripts.ru/w/index.php?title=Описание_работы_универсального_прямого_преобразователя&oldid=802»