請問~Verilog 設計資料排序~

呆頭鴨

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

kevin

資料量少的話,用插入排序法則也不錯.
7 o2 R7 P4 R- K" V6 E
$ J' R; N3 q( w; T/ s7 R# L假設有九個registers,每個register附帶1個comparator,
# x7 {- M4 m& M5 M: c: |每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

       Reg(n) <= Reg(n);                   //保持原來的值
( D& ~8 o5 a8 Z9 T2 z% t- f/ c
9 C& ^: h; a. I  oelse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
3 N3 x. n6 p8 \  ~3 C/ w- M. E
       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
      Reg(n)  <=In_value;             //load input value
         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

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

% j* l: ?6 `$ w/ B, B. l# b0 J' x4 M至於你real time輸出~不太懂你要表達意思~
! w. S% i( ^  R: O- o
你可以把你整個架構描述完整點
& L. k# d7 q! b4 U/ Y  h6 Z! I
2 V( J) }/ \2 N2 f# e這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
, [" H$ `( L# v- r4 r

    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
+ |# v& y" g7 C$ e- i因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

首先看排序方法
. |9 Y8 p$ T- E1 w9 [1 |" y/ r再來看比較器有幾層,還有比較器的寬度

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.

) S. v: i8 m+ U, T舉個4進4出的例子:
5 N& e$ H! R, V" ~input [word length] a[4];
$ R4 }/ |9 l# c* Wreg [word length] b[4], c[4];
第一次排序
+ E* M. t- M  Z3 t+ ~b[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
3 R7 N) ?+ q4 L  i: w5 Bb[3]=max(a[2], a[3]);
第二次排序
0 `/ m' B5 P2 L2 f' N9 o+ ]c[0]=min(b[0], b[2]); //real minmum
. B8 v( X6 Z# X7 M# Q( ~5 P+ n( Ac[1]=max(b[0], b[2]);
; @: u1 H' k3 U+ gc[2]=min(b[1], b[3]);
# W( O4 z# J. l% ]c[3]=max(b[1], b[3]);//real maximum
( L3 N; T) o5 o- Q第三次修正項
7 n, T: j' k3 C/ Gd[0]=c[0]; //real minmum
) S6 I, \% f, R, G5 R5 _, Qd[1]=min(c[1], c[2]);
0 `3 ?' `' }9 j% ud[2]=max(c[1], c[2]);
& ]& J: _- o$ Q. i7 J8 ud[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
) a; A8 o* i/ {  |3 Z
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

9 `, S2 ^/ L) W; a6 K實做的考量
1. 實做上min()跟max()應該是一起做的
if(a>b)
& \  L* y7 ^( F     min = b;
- r* e$ ]: m: `, L2 C& T     max = a;
! ~" y2 Q, n7 `) B2 m: p# ~  else
    min = a;
) Q# Z& \2 F7 G6 Q5 G  Q    max = b;
& i! [" I. k6 ~& g, l2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
9 M. u$ ]* E* Y; V$ _3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
, e% W2 I2 L: {0 h' WP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

  S* Q: g4 S4 L( U回復 5# tommywgt
$ Z+ L$ E' D6 X/ z4 I$ q1 b

    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
) o) Y4 V& m/ P3 E5 9 6
: L( ?$ d. {7 N) o8 B7 8 2
1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
& I9 l" S3 L5 P! H' i) d$ W5 6 9
  k, @4 j2 a4 g& t  q  n+ a$ v( @2 7 8
1 3 4
這時候再將 垂直列的3筆丟入R可得到
! a0 j: Y. k  X1 2 5
3 6 7
& o1 p0 S6 E5 p. I4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
3 P1 m8 r8 q6 z6 8 9
" L  a% Y# g; D) e: Y, \) w/ E這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
) L( I2 `/ o5 t* |! K* d雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
6 X) f# b& S. t+ ~& L1 |其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
; _; J9 _5 |0 T1 A1 j8 e1 e左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
  B% W: z2 t3 X! w9 Q, R- g" z' J. n所以在最大的亂度中, 8-1=7次應是最多的運算了,

; |' ^4 E( c2 W6 i2 ~  e有人有更佳解嗎?

呆頭鴨

回復 8# kevin

% x. K7 p+ r: a# G. ?8 P4 B6 T
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
8 r3 q* r6 Q+ q- s- [/ \5 a3 u22排序 看起來是不錯的做法, 1 clock 即可做完.