понедельник, 30 сентября 2013 г.

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

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

Exported from Notepad++
#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].
Exported from Notepad++
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) и перезаписываем. Тут ощутимо больше регистров задействовано и меньше логики.

Exported from Notepad++
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().

Комментариев нет:

Отправить комментарий