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

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

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

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

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

[[Изображение:Вычислитель остатка от деления.png]]

Здесь: 
* <math>0 \le X < 2^N</math>
* <math>0 \le OUT < 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>[p;2 \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> и.т.д.

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

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

<source lang="verilog" line>
module mod_5_23 (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 = 0;
		6: out = 1;
		7: out = 2;
		8: out = 3;
		9: out = 4;
		10: out = 0;
		11: out = 1;
		12: out = 2;
		13: out = 3;
		14: out = 4;
		15: out = 0;
		16: out = 1;
		17: out = 2;
		18: out = 3;
		19: out = 4;
		20: out = 0;
		21: out = 1;
		22: out = 2;
		23: out = 3;
		default: out = 0;
	endcase
	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>