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

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

Содержание

1 Описание работы универсального прямого преобразователя из позиционного представления в модулярный код
2 Постановка задачи
3 Специальные случаи
4 Общий случай
- 4.1 Численный пример
- 4.2 Verilog-код для численного примера
5 Конвейеризация преобразователя
6 Генератор Verilog
7 Результаты моделирования

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

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

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

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

Здесь:

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

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

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

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

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

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
```

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

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

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
```

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

```
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
```

Общий случай

Представим входные данные $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-код для численного примера

```
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
```

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

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

Генератор Verilog

Генератор Verilog универсального прямого преобразователя для произвольных модулей

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

Результаты синтеза универсальных прямых преобразователей для простых модулей в пределах 8 бит

@@ Строка 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>-бит.
 Схема этого блока с входами и выходами:
@@ Строка 46: / Строка 46: @@
 === 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> и.т.д.
+В этом случае достаточно проверить в какой из диапазонов вида <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> и.т.д.
@@ Строка 76: / Строка 76: @@
 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> требуется выполнить две операции:
+) Найти сумму <math>SUM = (A_0 \cdot X[0] + ... + A_{N-1} \cdot X[N-1]) \le (p-1)*N</math>.
+) Определить в какой интервал вида <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

Содержание

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

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

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

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

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

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

Общий случай

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

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

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

Генератор Verilog

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

Навигация

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

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты