請問~Verilog 設計資料排序~

呆頭鴨

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

kevin

資料量少的話,用插入排序法則也不錯.

" b& L" z. y3 p+ a; h5 W假設有九個registers,每個register附帶1個comparator,
! D, P3 B" C. G' G每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
5 }/ Q- @- J* c4 ~& R/ Y+ kif (Reg(n) > Input_value)

       Reg(n) <= Reg(n);                   //保持原來的值

) Q" c8 U+ o. V) J0 v5 |5 W8 r" \else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

1 }' r( O% h& \, Q1 f  E       Reg(n)  <= Reg(n-1);             //shift in 前一級的值
" c3 c5 O$ s* S5 ~. \  R$ w5 V
8 {8 a8 {5 t9 i/ `- ~4 Felse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
3 K  v6 O  C) V5 |5 N      Reg(n)  <=In_value;             //load input value
         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

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

至於你real time輸出~不太懂你要表達意思~

+ _& z: u4 R; A$ A$ c# }/ G% ~+ x. z* O你可以把你整個架構描述完整點

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

呆頭鴨

回復 2# kokonut
1 q4 x2 [$ d. K

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

masonchung

首先看排序方法
9 J. ?% B; g6 R2 U2 o: ~8 e& g再來看比較器有幾層,還有比較器的寬度

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
& O0 v' a' {3 ~1 J
0 j: D' ?+ J7 `舉個4進4出的例子:
input [word length] a[4];
5 [1 c7 G! _5 ^# K2 yreg [word length] b[4], c[4];
5 O& z3 n+ `! e) |, K/ ~第一次排序
6 v* u! l* [5 eb[0]=min(a[0], a[1]);
& _9 n! u+ M$ Y5 f% m( [5 q5 Yb[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
' N7 X9 i# F+ X2 uc[1]=max(b[0], b[2]);
9 g" q/ d0 [6 Ac[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
第三次修正項
d[0]=c[0]; //real minmum
- @1 H" D$ T  Y$ Y: Sd[1]=min(c[1], c[2]);
) T$ ^9 o# }: S( wd[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
3 b, \* W% ~9 _0 h' P9 Z//d[0]~d[3]就是依序小到大的答案

這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
- H7 {7 s( }% b1 ^+ b
! H! r& v; b7 d. W: G  d( _0 X實做的考量
& _9 `% S! X- k/ b) D% T: B6 C1. 實做上min()跟max()應該是一起做的
4 c, ]- a9 ^, E& E if(a>b)
     min = b;
     max = a;
  else
1 T+ @8 Q( Z4 p0 R- f/ h/ X    min = a;
& o* o3 \  K( m1 A5 _6 `0 x1 w    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

回復 5# tommywgt
3 p, D1 U" n, c$ _4 D5 Z( `

, m# j0 p* w8 c$ t$ Z    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
2 y4 f2 b* t& Z6 a5 9 6
1 U2 a2 z% z, K+ P, z( I% s( \5 \7 8 2
7 y4 e9 q" G/ y$ n  \# T% p1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
5 6 9
/ J$ `; H5 u7 x! Q6 m2 7 8
1 3 4
1 C% s4 n- M4 @這時候再將 垂直列的3筆丟入R可得到
7 g+ m: B$ t/ o8 s/ m& O. h" f1 2 5
3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
9 C9 q) T$ a# p* }
+ P. T- D! a* }$ c最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
( B$ }0 T% j( q) Q1 2 4
; s8 T( h( x2 |1 A0 \4 h" a9 ^3 5 7
/ G$ T7 e" T% a2 y2 D6 8 9
這時候可以發現
, X0 _! ^1 H" @1 {/ S8 S中間的數值確實是9筆資料按大小排列後的中值(5)
( F+ J) b- ]/ ?/ }9 A" L& ^8 a* B雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
" s8 B. s7 g' v: ^& x其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
7 Q. t; e0 I$ E' }+ W, n7 H; v當亂度能包含所有的項時, 答案一定是對的
9 a& ~0 b" N' t+ S- N1 d* G* u所以關鍵就在於如何用最少的運算次數達到最大的亂度.
0 W; _2 j5 i/ N8 Z1 ]左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,

有人有更佳解嗎?

呆頭鴨

回復 8# kevin


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

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
22排序 看起來是不錯的做法, 1 clock 即可做完.