請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
% e8 K5 G! v% D# }- ^: R有辦法達到real time輸出嗎?
0 \3 q8 X2 G( G% x還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.

, f7 ]2 E4 |; Q假設有九個registers,每個register附帶1個comparator,
( Y* h0 E% ~$ [3 t3 T) C每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

, Z7 B6 y$ M- o) e; m% U       Reg(n) <= Reg(n);                   //保持原來的值
& n2 j! U  t# H0 H, z5 @* S+ t
- B+ E+ i7 s, N7 d" Relse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
+ K( O1 O0 X  w  A+ S     
! [) C9 {5 X( b- A$ Q# j( u      Reg(n)  <=In_value;             //load input value
& B4 i' [# ^- ?. k4 _. k1 c         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

alita

我覺得 對於3x3的median filter
22排序 看起來是不錯的做法, 1 clock 即可做完.

tommywgt

沒聲大大, 其實大家都很棒啊.

masonchung

桶米版大 真是太棒嚕

呆頭鴨

回復 8# kevin


; y( f6 ]4 j& t$ n    大大的方法真不錯~ 我怎麼沒有想到呢XD....

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
- f2 ?) E! ^3 |9 B2 g當亂度能包含所有的項時, 答案一定是對的
1 R; Z; m; k: O# l/ `所以關鍵就在於如何用最少的運算次數達到最大的亂度.
% O) v4 S/ L- X/ ?左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
& m+ I$ X$ U9 M所以在最大的亂度中, 8-1=7次應是最多的運算了,
* W7 J5 P/ {) n( f# j+ j
. t' I/ J1 r2 D( C" o有人有更佳解嗎?

呆頭鴨

# \0 F6 T. _6 z' z. t回復 5# tommywgt

2 V" ?, p9 l2 y; j7 ?4 ~3 ^
    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
# f1 G3 c& x5 ?8 w9 S- M/ [則想像成
5 9 6
7 8 2
1 3 4
8 Y  }1 ~: Y3 p# i; L不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
  }' V2 c; L: Q- P; t& D4 @& {5 6 9
2 7 8
' e3 y+ Y2 a8 L& W2 Q1 3 4
0 w9 C) I' V) u& I# |( N; }這時候再將 垂直列的3筆丟入R可得到
1 2 5
3 6 7
. |* E1 R# y: I( h! x4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
$ |* l6 v' [% ?8 P
) {1 D8 Y) ?: {4 v最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
1 |# {4 Z8 R/ ^/ G7 H# T( B3 5 7
6 8 9
% G) k( A: `) H3 U這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
5 ]7 z, z0 ]0 T7 s# ~
舉個4進4出的例子:
input [word length] a[4];
4 Y* _$ e1 g5 A  yreg [word length] b[4], c[4];
0 I# u6 m( q# a8 M$ }1 d9 ~第一次排序
b[0]=min(a[0], a[1]);
- x! Q$ F; o8 a& N6 Y4 O6 ~6 xb[1]=max(a[0], a[1]);
3 s& N: O, v7 @( b" pb[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
2 ~# h0 z. h4 y. K; L4 A第二次排序
c[0]=min(b[0], b[2]); //real minmum
* s& {4 F4 n* z7 N3 K, o) Hc[1]=max(b[0], b[2]);
' w* ^' f* Z0 v9 H2 mc[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
9 B2 u. F7 _3 L7 M& l& E: O第三次修正項
d[0]=c[0]; //real minmum
- j, f: }$ ~! S4 o: o. Bd[1]=min(c[1], c[2]);
1 E% V& a6 a+ z& ~( M8 ud[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
$ O$ I% ^* d! L/ N//d[0]~d[3]就是依序小到大的答案

0 h" d" Z0 o% Z/ Y8 S; i% D這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
; [  E7 i% a  ]9 H
實做的考量
+ d5 r3 }5 x  {- ?0 J1 e+ `1. 實做上min()跟max()應該是一起做的
- S' v& X: T4 b1 A0 ^# U if(a>b)
     min = b;
) `( o$ W! C5 u: g. E) L9 u5 _     max = a;
  else
    min = a;
    max = b;
8 Y" Z2 c$ R; d2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

masonchung

首先看排序方法
) R: w! s, j$ W- t. X" k& q( o再來看比較器有幾層,還有比較器的寬度

呆頭鴨

回復 2# kokonut


" \6 l, G+ p& b8 D: H7 t& U" d    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

kokonut

你把A1~A9吃進來後~要先排序處理吧~

至於你real time輸出~不太懂你要表達意思~
- m* e3 v. F% A
2 ]  F$ h! S8 G你可以把你整個架構描述完整點
" u0 A, V) n4 g# Q6 @
這樣比較好給意見~!!!