請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
4 U! G6 c% d$ f  T/ ?" F% Y. G: u要如何設計才能達到按照數值大小排序輸出X1~X9
  g! q, ^0 @- u7 f' O& U5 o有辦法達到real time輸出嗎?
3 [1 d: Z1 I% q還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
# h# y+ H) b7 k. \! v
) T& {6 }6 F4 P8 o8 _. m3 n  {假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
$ U1 n& k" O9 jif (Reg(n) > Input_value)

& [* i6 o: E6 t* O: B+ @+ H       Reg(n) <= Reg(n);                   //保持原來的值
4 R- f" ]" }& C. L1 C- @
: A: z& P6 s- O4 k$ f5 g; }, gelse 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))
     
      Reg(n)  <=In_value;             //load input value
         
3 A3 @1 d( p7 y' h8 q; J每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

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

至於你real time輸出~不太懂你要表達意思~
) [$ I$ o( n) \0 q% ?/ S
; L# Z# X: A$ B& v你可以把你整個架構描述完整點

* h2 v! h6 F: ^. Z$ y& O/ e: g這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
0 H/ t7 s0 c! m6 i7 v) `: C* d1 h

! V& w8 X5 O: \    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
) T6 t$ x2 f5 O" _0 U" Z9 X( _' F   所以要將畫面中9個數值做排序後輸出中間的數值
3 ^6 O8 |/ S' b( {因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
( ^0 J$ E+ U4 T6 u: M1 X大概是這樣子...0.0

masonchung

首先看排序方法
" T5 D- L: y. L2 Q( i! r" ]再來看比較器有幾層,還有比較器的寬度

tommywgt

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

舉個4進4出的例子:
' H6 C9 p5 [7 M- L9 xinput [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
  ]- ?/ c7 g" L8 R' ]  Nb[0]=min(a[0], a[1]);
" E3 V0 F9 h. W4 Wb[1]=max(a[0], a[1]);
9 M- h# C- x& n1 l7 K# {, i$ Cb[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
; X/ e& C8 D1 E/ N5 ^第二次排序
; z) ]  v. k: n* @c[0]=min(b[0], b[2]); //real minmum
! w8 ^! b  i' ?% \9 xc[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
2 M6 }" ^4 w) x: j* ic[3]=max(b[1], b[3]);//real maximum
第三次修正項
0 [4 i9 d6 k& P/ |4 P8 S+ s4 Vd[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
d[2]=max(c[1], c[2]);
' ^; O- F# s. c- `" O5 Ad[3]=c[3];//real maximum
- m: ^/ R5 L: @3 z, l. s: J+ Z//d[0]~d[3]就是依序小到大的答案
( Z) ]" w+ M5 o2 U$ f
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
& g2 R6 |$ ]( f( Y! ?, J6 l* }' N
/ l" m' b7 b' A; S  p6 U5 g9 {實做的考量
1. 實做上min()跟max()應該是一起做的
if(a>b)
, i9 H8 Y% i- t  ~4 E. z     min = b;
     max = a;
  else
% c& e( d6 D0 Q    min = a;
- Q5 e/ x, n& W# Q8 h7 K    max = b;
" s" r$ w' G: A: a2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
' S' G3 A: |1 I8 O* d+ J/ rP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

. V& s! m+ l; `0 T3 @
0 H& b4 U) U/ ?3 Q3 F9 i- ]& H% L回復 5# tommywgt
3 R" d/ }" P) v2 R# j$ X
  H& r8 z& a! U1 z/ ?9 S0 g
    謝謝大大熱心分享
  q8 ^. c. w, e7 q1 }. X& k我目前的做法是這樣的,提出來給大家研究討論一下.....
) k# F7 Y0 c1 j  K我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
# R& m0 ?! z0 ^* |7 G, z* A* P9 M則想像成
* |& d  m' |$ q5 9 6
7 8 2
4 Z: @+ S+ e- l+ u9 u* p$ u1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
, V3 C% W: Q: W' h9 W; Z& _5 e, ?) O5 6 9
. c' w1 ~) X; q2 7 8
1 K9 S) y& d3 `& S1 3 4
) o3 r+ j# a# Y6 m& ^5 q這時候再將 垂直列的3筆丟入R可得到
1 2 5
+ V* a! u8 f# s& _% t4 h# A3 6 7
- ~8 D' q+ G5 P( W4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
% x: [' s! T  T$ a  M9 |
4 C% ~6 _; c6 D& [* o, p最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
6 8 9
這時候可以發現
- {* Y; Q4 ]# ]- q4 ~中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
/ P- B; F- W. j9 f/ S$ v其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
$ N- U5 `4 e/ j6 i最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,

2 n. D  r. Z9 r' A9 K' E有人有更佳解嗎?

呆頭鴨

回復 8# kevin

5 `% Z$ ?/ W9 K% M2 `# ^
/ d2 N5 K  f! X9 Z    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
1 H$ N# `7 A# X, D( a22排序 看起來是不錯的做法, 1 clock 即可做完.