請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
5 F1 p. B' E" ^2 u% G我有9筆資料 同時輸入 A1~A9
+ z* Z2 u, g6 P5 q* U3 c" D! m1 e! C要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
9 G" p5 n1 t- v! a7 ?
假設有九個registers,每個register附帶1個comparator,
, q$ q  C0 B+ Z/ c& C, S  g5 O8 u  a每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

       Reg(n) <= Reg(n);                   //保持原來的值
0 Q1 W5 P! O, D( q/ O* ~
" S3 ~2 C/ }( r! p+ g3 N& xelse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
* n- t  |6 a; F, g5 `) g
$ l  o0 C& P8 S2 j- t5 v       Reg(n)  <= Reg(n-1);             //shift in 前一級的值
' ]% s( n' x% L9 H, n
else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
1 w# J0 P3 S# x& J0 f  G3 v      Reg(n)  <=In_value;             //load input value
         
, ?4 o; I: ^( w/ e7 ~6 X& G7 h: m9 h  M每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

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

% s' O2 E/ F( D1 J至於你real time輸出~不太懂你要表達意思~

你可以把你整個架構描述完整點
9 d3 R' G2 h! s* I
這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
4 Y0 g: v+ ?) F, _, R: D% ~% U; B

    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
3 G0 v8 ]5 y9 f  j! K! b: a9 M- }   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

首先看排序方法
再來看比較器有幾層,還有比較器的寬度

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
% w# S# B& U% m% t5 b2 W8 H5 U/ N
; k) @$ p: e1 n) `" s舉個4進4出的例子:
: d1 B, I) t$ O; j  A9 ^input [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
' g& c% B$ v" ?) }& w1 Q6 A- k; Ob[0]=min(a[0], a[1]);
0 `5 ?  [# k" z. @b[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
第二次排序
c[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
6 C* t5 g; T: ~$ R' ec[3]=max(b[1], b[3]);//real maximum
7 j( A' Q  `9 o# p3 c5 F7 e. |; n第三次修正項
d[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
  {, g/ p. C7 X' o5 dd[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
# ]9 T9 C; P, Z
; q  V3 Z! R0 w* ?& S' O這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
# I+ Q5 N) y/ U; c- j# J
' e2 |6 E; [. _) j, u$ O實做的考量
1. 實做上min()跟max()應該是一起做的
if(a>b)
" v' v1 S! j4 {! G     min = b;
* c" f' V% i6 I! K6 P% s: o     max = a;
. ?, O! N0 ^7 d8 ], S; O  else
! U: O1 b8 B! E' w$ `    min = a;
" H) [. N: K: X    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
( x! d5 B) X- Y9 V  l! z, `+ s& vP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

  @# }+ E) F# G2 E0 P- [回復 5# tommywgt
: Y2 p7 P6 Z% ~' Z. R9 F
2 C* K9 F' @6 E& n
6 G$ _( r: K) B' t/ g    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
( k0 S! ~! l: [3 v+ j5 9 6
8 O& Z/ ?4 M5 G3 G! D. M. ^7 8 2
1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
5 6 9
2 7 8
- ]; q) Q9 @& {) k& s1 M1 3 4
這時候再將 垂直列的3筆丟入R可得到
. X: m7 V( X5 ?4 G* m6 Y+ [1 2 5
6 n1 _' i  f: ]* t; C8 W: {; Y1 e3 6 7
& D  K* E( t6 [+ Q( k( [4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 [8 F3 m$ t8 z" i% w/ n5 X1 2 4
" f' C. {  g5 v6 L1 k3 5 7
6 8 9
這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
0 E9 D) u$ t1 o& _9 p$ o5 F& f其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
) @7 S7 I$ |, p當亂度能包含所有的項時, 答案一定是對的
8 U/ q+ ~! P; A1 c) K所以關鍵就在於如何用最少的運算次數達到最大的亂度.
2 }8 Z/ H7 Q/ P0 ?0 I' F6 k左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
0 D3 H, g- j+ y# l所以在最大的亂度中, 8-1=7次應是最多的運算了,
3 i! p; E. A$ @- @: [
3 k& q. b# X& v- ^; J有人有更佳解嗎?

呆頭鴨

回復 8# kevin


    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
- g4 j( Y2 I6 a" m% V+ p  `22排序 看起來是不錯的做法, 1 clock 即可做完.