請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
+ j/ F( `. R, p4 ~# @: Y我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
" x  c4 ^; r4 @8 D有辦法達到real time輸出嗎?
還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
2 l/ k" M1 Z; E  h/ `9 a# ~9 ^( m; ]
/ s8 S& b1 @+ O- [0 G3 w假設有九個registers,每個register附帶1個comparator,
/ U( w, a" F5 u( q每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

       Reg(n) <= Reg(n);                   //保持原來的值
/ S5 W$ R% S0 n' _
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
$ D1 j  z( W1 @  u% i
       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

6 J9 [) l- R8 A% \! A8 C) aelse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
0 o# r) }/ ^: W/ w     
  ^' l3 S4 `, F  {$ @$ E      Reg(n)  <=In_value;             //load input value
5 W( U$ H. k6 E- U         
) ?5 w1 ]2 S% I0 j2 F每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
; a0 x  u: l9 _8 t6 w% V1 H  i
至於你real time輸出~不太懂你要表達意思~

& i% D/ C8 r; B7 @你可以把你整個架構描述完整點

這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
# U6 A7 f5 {- g+ v

7 s+ U% c0 p! H- R4 j# ?8 `8 H  U# ?    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
, b$ u2 [8 T4 Q/ Y大概是這樣子...0.0

masonchung

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

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
# v4 }' z4 w5 a2 O) o8 ^1 w2 c至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
" t6 n; v( J) v: y
舉個4進4出的例子:
7 E- z! ?0 Q4 g$ h- b: ninput [word length] a[4];
/ F" i% i, q" b: s# l" t- Greg [word length] b[4], c[4];
第一次排序
% D! S& j  d1 P+ S9 F' A  {- d/ xb[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
第二次排序
! n1 X2 c$ r& ic[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
1 e- |& j. Y- Y5 y# H% m5 ?' ?第三次修正項
d[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
) B' D# F6 E1 _$ od[2]=max(c[1], c[2]);
% O0 J" z4 Z* L4 H3 jd[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
6 W) z/ t' ~, ~; B. q# Y$ c2 ?
( a1 d/ n: Y& n$ s這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

! E# _4 L- I9 }) `實做的考量
1. 實做上min()跟max()應該是一起做的
: Y0 C0 c  O: o! l6 \* K if(a>b)
( p- p" ]; s: W6 Q8 ^     min = b;
     max = a;
  else
    min = a;
    max = b;
+ x* c' G* N1 G; D: I: s* }0 a; n2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

( x  R6 J6 i: h9 J* a/ P回復 5# tommywgt


    謝謝大大熱心分享
2 m: F1 w# G9 _. u( ]1 h3 `" P$ f我目前的做法是這樣的,提出來給大家研究討論一下.....
9 L! T3 o& k7 z, e我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
! E, @5 B- I  d# S則想像成
+ T0 t# K3 q( x& h$ ^2 ~* m5 9 6
7 8 2
" o; n, e  }: n% p- ?$ q0 O& T1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
5 6 9
2 7 8
1 3 4
' f. l" U5 M, k: p( a: B4 i& K這時候再將 垂直列的3筆丟入R可得到
& r& G& u" O8 W3 [) Y% L1 2 5
3 6 7
4 q3 N: m, o$ M/ h$ _4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
6 8 9
9 c6 p. r2 Y3 Q. c" e& X這時候可以發現
7 {! `1 B) X0 q! c  H中間的數值確實是9筆資料按大小排列後的中值(5)
- b" B5 k! E7 w. B4 e# d, F雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
* o$ x: W3 o% e+ O* t. `9 v5 U5 }最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
6 h  _2 ~$ }7 x, U所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
0 f6 w! i, V+ d# P" x. U7 [所以在最大的亂度中, 8-1=7次應是最多的運算了,
6 i+ O3 m/ r- c5 t7 E3 z& x
有人有更佳解嗎?

呆頭鴨

回復 8# kevin
  G: w7 |+ W4 u, e6 m( ^: |
* j4 B+ e' L8 ~' \; g; `
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
" J1 }& m, m8 O2 u22排序 看起來是不錯的做法, 1 clock 即可做完.