請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
" {- r% |+ E# ~* R1 t
假設有九個registers,每個register附帶1個comparator,
; [% K# a% \- _4 x: o/ R, [每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

7 z& c3 J) c; h4 j1 ^# Z) J& G. J       Reg(n) <= Reg(n);                   //保持原來的值
1 i6 O& a; v$ o6 U7 ?
0 E- V! ?( t, R$ I4 }7 felse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

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

8 {. h& W" O2 k* a1 ielse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
. q9 v* p; u; Z2 z      Reg(n)  <=In_value;             //load input value
) i+ T$ t8 k7 y: ?         
6 Q/ m+ o6 l$ l7 ~' E- r+ |每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
: U9 W) \5 Z' U; v/ B
% ^: H7 C' C& P. q% U0 p至於你real time輸出~不太懂你要表達意思~

/ G  }# G7 k+ a! J你可以把你整個架構描述完整點
4 L7 H" [' |0 a; k
3 d0 n/ W7 I* O# t! m. h$ J這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut


3 p0 U$ D# J* G3 i    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
* v9 d- }# Q: `, Y0 f# J2 B( v1 V因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

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

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
7 t# L; E7 h& ~& [) q4 F$ P
- A$ ^7 y+ q5 f, p& z! ~- _舉個4進4出的例子:
+ ]. h7 k" }- [! T; o* [) \2 Pinput [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
, y& c$ ~" u% u6 v& _( r/ [  Qb[0]=min(a[0], a[1]);
5 M. M" w2 Q0 Ob[1]=max(a[0], a[1]);
: z! A( d& E/ S; n$ C. d' Zb[2]=min(a[2], a[3]);
3 b! |, d7 V& o5 Y4 @! ^9 pb[3]=max(a[2], a[3]);
5 f/ V. h3 p+ S- @第二次排序
8 F6 y0 f- p) e+ e2 lc[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
+ w; G3 a9 w7 w! P4 ], Ac[2]=min(b[1], b[3]);
6 i7 E8 C! q& Q/ w3 H$ Nc[3]=max(b[1], b[3]);//real maximum
" p& ^  \1 D- K1 U第三次修正項
, Q9 K# g9 Q" B: ~1 z1 S% h, Bd[0]=c[0]; //real minmum
4 f& q/ ?* @% p) ], b' bd[1]=min(c[1], c[2]);
  i/ h: k% K" ?: sd[2]=max(c[1], c[2]);
, U: q$ K. H, c& \' [. k! m$ Bd[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
: }9 M$ E5 ^. M% S2 ^' `. c
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
% g5 f  c2 u/ N( ]
+ e4 @7 `& b# {: V實做的考量
. ]9 |* n4 l+ c1. 實做上min()跟max()應該是一起做的
if(a>b)
     min = b;
     max = a;
  else
    min = a;
: M+ s, O8 q; n: x5 w  U8 R9 T! d    max = b;
& E7 D2 V+ K" ?' {4 I2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
+ d1 N. V5 R: ~% t5 VP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

回復 5# tommywgt

4 q, A  p& S, V# n
5 K# O1 b/ v8 ^    謝謝大大熱心分享
$ P7 o' Z) |5 [& @, h  W" D* T我目前的做法是這樣的,提出來給大家研究討論一下.....
- q% s& R  o+ b& D* a* d我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
; s' P) @. t, `3 |3 A3 ~則想像成
3 k/ I* Y6 }% Z+ N" y3 x5 9 6
, n8 i1 T$ Q9 O6 y7 }& l) [+ o( A7 8 2
1 3 4
+ z) h$ D/ Z* K不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
& R3 o0 E! y0 E. L將3段數值分別丟入R 得到
5 6 9
: o  k0 ~' \) M9 v/ m4 V, B7 q2 7 8
1 3 4
' R  G! P/ N# `這時候再將 垂直列的3筆丟入R可得到
6 {% _$ n% c( r5 P  a% \+ v7 W1 2 5
& L( @3 ^/ G( x7 m8 K/ g3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
9 i- p8 l4 Z: J. G
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
; T2 K2 w; }* _6 8 9
, @0 g" c  @$ ?" `: T$ s+ L這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
  [% V! [; {, u: r7 f9 d4 e9 E3 ^最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
9 Z' J; f+ m% k% c當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
3 t  E0 j+ h; K! ~; D% K所以在最大的亂度中, 8-1=7次應是最多的運算了,

有人有更佳解嗎?

呆頭鴨

回復 8# kevin

2 m% q( C- M/ u5 Q8 f$ I
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
  B7 Z1 e' u" B3 v: |9 l22排序 看起來是不錯的做法, 1 clock 即可做完.