Среднее значение в массиве

В этот раз я закончу с программой с нахождением минимума и максимума в массиве, а так же покажу как найти среднее значение. Будем отталкиваться от такой программы:

#include <iostream> #include <math.h> #include <limits.h> using namespace std; const short len = 4; short val[len] = {1,0,2,4}; short min_val(short *x, short len) { short min = *x; for(int i = 0; i < len; i++) { if(min > *(x+i)) min = *(x+i); } return min; } short max_val(short *x, short len) { short max = *x; for(int i = 0; i < len; i++) { if(max < *(x+i)) max = *(x+i); } return max; } short mean_val(short *x, short len) { short mean = 0; for(int i = 0; i < len; i++) mean += *(x+i); return (mean/len); } short sqrt(short x) { short ans = 0; short tmp1 = 0; short tmp2 = 0; short local_mask = 0b11; short mask = 0; for(int i = 3; i>=0; i--) { mask |= local_mask << (2*i); tmp1 = x & mask; ans ^= 1 << i; if(tmp1 < ans*ans) ans ^= 1 << i; } return ans; } int main () { short min = min_val(val, len); short max = max_val(val, len); short mean = mean_val(val, len); cout << min << "\t" << max << "\t" << mean; short sqrt_t = sqrt(max); return 0; }

Вывод: 0 4 1
Прелесть нахождения среднего в данном случае заключается в том, что (a+b)/c != (a/c) + (b/c). В этом можно убедиться, если массив заполнить {3,3,3,3}. Среднее должно быть равно 3, но в целочисленных 3/4 == 0, поэтому 3/4+3/4+3/4+3/4 == 0.
Здесь опять же можно заметить, что в расчете среднего значения в цикле не используются переменные из прошлой итерации. Значит можно посчитать за один такт сумму всех переменных и разделить ее на четыре. При этом мы помним, что длина суммы четырех переменных [3:0] будет равна [5:0].

module test( input wire clk, output wire signed [ 3 : 0 ] mean ); localparam len = 4; reg signed [ 3 : 0 ] val[ 0 : len-1 ]; initial begin val[0] = -3; val[1] = -3; val[2] = -3; val[3] = -3; end wire signed [ 3 : 0 ] tmp1 = val[0] > val[1] ? val[0] : val[1]; wire signed [ 3 : 0 ] tmp2 = val[2] > val[3] ? val[2] : val[3]; wire signed [ 3 : 0 ] max = tmp1 > tmp2 ? tmp1 : tmp2; wire signed [ 3 : 0 ] tmp3 = val[0] < val[1] ? val[0] : val[1]; wire signed [ 3 : 0 ] tmp4 = val[2] < val[3] ? val[2] : val[3]; wire signed [ 3 : 0 ] min = tmp3 < tmp4 ? tmp3 : tmp4; wire signed [ 5 : 0 ] mean_val = (val[0] + val[1] + val[2] + val[3]) >>> 2; assign mean = mean_val[3:0]; endmodule

В чем разница между >> и >>>. В случае использования знаковых переменных для сохранения знака при сдвиге нужно использовать >>>.

Теперь реализуем тоже самое на конвейере. Накапливаем результат за 4 такта (потому что len == 4) и перезаписываем. Тут ощутимо больше регистров задействовано и меньше логики.

module test( input wire clk, output wire signed [ 3 : 0 ] mean ); localparam len = 4; reg signed [ 3 : 0 ] val[ 0 : len-1 ]; initial begin val[0] = 1; val[1] = 0; val[2] = 2; val[3] = 4; end reg [ 1 : 0 ] cnt = 2'b0; reg signed [ 3 : 0 ] r_max = 4'b0; reg signed [ 3 : 0 ] r_min = 4'b0; reg signed [ 5 : 0 ] r_mean = 6'b0; reg signed [ 3 : 0 ] r_out = 4'b0; always@(posedge clk) begin cnt <= cnt + 1'b1; case(cnt) 2'b00: begin r_max <= val[cnt]; r_min <= val[cnt]; r_mean <= 5'b0; r_out <= r_mean >>> 2; end default: begin r_max <= r_max < val[cnt] ? val[cnt] : r_max; r_min <= r_min > val[cnt] ? val[cnt] : r_min; r_mean <= r_mean + val[cnt]; end endcase end assign mean = r_out; endmodule

В следующий раз расскажу про функцию sqrt().

Поиск MAX&MIN в массиве

Теперь пробуем решить простенькие задачки на Verilog. Начнем с того, где может понадобиться сравнение чисел: поиск максимального и минимального значения в массиве. Я предпочитаю сначала писать на C/C++, отлаживаться, а потом переносить код на Verilog. Так быстрее и надежнее, ведь в итоге должен получиться одинаковый результат в отладчике и в тестбенче.

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

#include <iostream> using namespace std; const short len = 4; short val[len] = {1,0,2,4}; short min_val(short *x, short len) { short min = *x; for(int i = 0; i < len; i++) { if(min > *(x+i)) min = *(x+i); } return min; } short max_val(short *x, short len) { short max = *x; for(int i = 0; i < len; i++) { cout << max << "\t" << *(x+i) << endl; if(max < *(x+i)) max = *(x+i); } return max; } int main () { short min = min_val(val, len); short max = max_val(val,len) cout << min << " " << max; return 0; }

Вывод: 0 4

На что тут можно обратить внимание? Результат находится за четыре прохода в цикле. Каждую итерация в цикле присутствует только одна переменная с текущим индексом, т.е. по сути можно пройтись с 0 индекса до 3, можно с 3 до 0, результат не измениться. Такой цикл можно разбить на два "как бы" параллельных с проходом 0..1 и 2..3. Или, если массив маленький, можно "как бы" за один проход сравнить все числа. Так максимальное значение за один такт можно найти:

localparam len = 4; reg signed [ 3 : 0 ] val[ 0 : len-1 ]; initial begin val[0] = 1; val[1] = 0; val[2] = 2; val[3] = 4; end wire signed [ 3 : 0 ] tmp1 = val[0] > val[1] ? val[0] : val[1]; wire signed [ 3 : 0 ] tmp2 = val[2] > val[3] ? val[2] : val[3]; wire signed [ 3 : 0 ] bigger = tmp1 > tmp2 ? tmp1 : tmp2;

Вывод: 4

Аналогично для минимального значения. Такой способ применим для относительно небольшой длины массива, потому что количество сравнений будет зависеть от длины и равно len-1.

Но ситуацию бывают разные. Предположим нам не нужно считать максимальное и минимальное значение за один такт, или стоит задача сэкономить ресурсы ПЛИС. Тогда тактика становится другой и в ход идет конвейер. Смысл такой: выполняем однотипные действия каждый такт, используя одни и те же ресурсы. Вместо 3 элементов сравнения в первом случае,  будет использоваться одно сравнение.

module test( input wire clk, output wire [ 3 : 0 ] big ); localparam len = 4; reg signed [ 3 : 0 ] val[ 0 : len-1 ]; initial begin val[0] = 1; val[1] = 0; val[2] = 2; val[3] = 4; end reg [ 1 : 0 ] cnt = 2'b0; reg signed [ 3 : 0 ] r_big = 4'b0; reg signed [ 3 : 0 ] r_out = 4'b0; always@(posedge clk) begin cnt <= cnt + 1'b1; case(cnt) 2'b00: begin r_big <= val[cnt]; r_out <= r_big; end default: if(r_big < val[cnt]) r_big <= val[cnt]; endcase end assign big = r_out; endmodule

Цена за конвейер: 4 такта считается максимальное значение и счетчик плюс триггера, хранящие промежуточные значения. Выигрыш в количестве логических элементов.

Числа в INT

В контексте данной записи под переменной будет иметься в виду reg[2:0].
По умолчанию все переменные в Verilog беззнаковые, а не наоборот. Поэтому объявленная переменная может принимать значения от 0 (3'b000) до 7(3'b111).
Чтобы сделать переменную знаковой, нужно добавить ключевое слово signed. Тогда переменная может принять значение в диапазоне:

011 //3
010 //2
001 //1
000 //0
111 //-1
110 //-2
101 //-3
100 //-4

Тут стоит обратить внимание на то, что для числа -4 не существует противоположного. Получить -1 из 1 можно проинвертировав все биты(~) и прибавив единицу:
1 = 001; ~1 = 110; -1 = ~1+1 = 110 + 001 = 111 == -1;
-4 = 100; ~(-4) = 011; ~(-4)+1 = 011 + 001 = 100 == -4;
Например, если нам понадобиться генерировать синус и косинус применительно к нашей переменной, то амплитуду нужно брать в диапазоне -3..3.
Для того, чтобы получить противоположное число на Verilog достаточно поставить "-" :
reg     [  2 :  0 ] a = 3'b001; //1
wire    [  2 :  0 ] na = -a; //111
и
reg     [  2 :  0 ] a = 3'b100; //-4
wire    [  2 :  0 ] na = -a; //100

Важно помнить, хоть na = -a, это число все равно остается беззнаковым. И если сравнить два числа, то большим окажется "отрицательное".
reg     [  2 :  0 ] a = 3'b001; //001
wire    [  2 :  0 ] na = -a; //111
wire    [  2 :  0 ] bigger = na > a ? na : a; //111

Поэтому, если будут проводиться какие-то операции над числами, лучше использовать знаковые числа. При этом результат так же должен быть знаковым.
reg     signed  [  2 :  0 ] a = 3'b001; //001
wire    signed  [  2 :  0 ] na = -a;    //111
wire    signed  [  2 :  0 ] bigger = na > a ? na : a;   //001