請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
+ U/ r6 Z- L  \' L# w) D我有9筆資料 同時輸入 A1~A9
/ I$ s3 X: H4 T/ H要如何設計才能達到按照數值大小排序輸出X1~X9
5 L0 {$ E+ E# z/ S4 n有辦法達到real time輸出嗎?
$ h9 H& D# J0 B4 @還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
# E6 R0 f( }3 h4 M; J& J. }9 h
- E6 u" V( n$ l3 r假設有九個registers,每個register附帶1個comparator,
) k) E6 S) m) L5 T2 m* J每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)
" y. |5 D3 H6 W* k. _: k
0 ?/ C& U& s! z5 l- T8 ^6 C4 X       Reg(n) <= Reg(n);                   //保持原來的值

6 q0 {% \7 t% ?& ^- Zelse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
9 Y) S, Q0 V7 X. c7 v
       Reg(n)  <= Reg(n-1);             //shift in 前一級的值
% }% k$ @& X3 J; C2 o
0 {. w5 L/ w2 U! u( V% nelse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
) Q1 G; H/ n( [  I, Q5 ^5 ?      Reg(n)  <=In_value;             //load input value
         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

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

0 ?/ A9 b8 F) \, A至於你real time輸出~不太懂你要表達意思~

/ u9 L9 f6 i( Z0 f' O3 }% y5 z" b你可以把你整個架構描述完整點
5 h3 r3 o! i+ H; m# T
, [  e( ]! N9 x0 y+ X# g$ ~這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
$ j' P/ D0 @- r5 N, K
, U! \8 J  z: y# K
9 |: m% F  k5 k8 a* i2 i% u    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
6 v' ~. i3 Q; Z$ R" T/ ]2 P! c/ @因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

首先看排序方法
+ t0 s) I8 T8 e/ U4 l* Y再來看比較器有幾層,還有比較器的寬度

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
& A! b0 {# P. S% y4 Q至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
( m" I7 H6 G, X) Y# Q
; h7 V0 q, x1 o/ X4 r& K1 G舉個4進4出的例子:
  f0 l7 ]1 i8 N6 pinput [word length] a[4];
reg [word length] b[4], c[4];
( M/ o  R8 H+ f* i0 S- \' X3 n# L第一次排序
b[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
, n& C; S' Q6 h6 ~$ A, H: [0 h. ub[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
第二次排序
c[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
# s2 ~( T/ X2 O9 W3 X# Z! g1 i; E第三次修正項
d[0]=c[0]; //real minmum
: U8 g; a7 z- P; l7 ~d[1]=min(c[1], c[2]);
d[2]=max(c[1], c[2]);
1 L( H1 f9 ~4 o- a# Fd[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案

9 m( R( a9 y5 B4 X這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
4 h- c  D7 c1 {% O) N; j$ b
實做的考量
1. 實做上min()跟max()應該是一起做的
( `9 {0 o* R7 O7 g! F if(a>b)
     min = b;
     max = a;
  else
    min = a;
    max = b;
# }" w; J9 p" M* h- [5 ^* x2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

2 \! I1 U1 C0 M0 z+ E
回復 5# tommywgt

8 ?& [0 g' J! w
    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
4 G4 L3 V- p4 ~0 O1 S5 9 6
9 D% C5 a2 l. A* [7 8 2
1 `2 r% T6 D' ~0 v! c1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
5 6 9
2 7 8
1 3 4
這時候再將 垂直列的3筆丟入R可得到
7 T- g* w3 m) \* b1 2 5
9 |/ C( D% w8 o3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
1 y5 ~4 F7 P; B- [
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
7 J) Z# q/ b% `, {6 }( ?& o" Y1 2 4
3 5 7
; ^6 _# i7 u5 e6 Z0 {/ g* N6 8 9
2 G' t5 f8 v+ e" X這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
" H! s# k3 ~" G4 ?雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
+ _' }, a* h) b, C/ h: w0 C& e* s' A最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
5 W5 J* X9 z" E8 y$ f所以在最大的亂度中, 8-1=7次應是最多的運算了,

有人有更佳解嗎?

呆頭鴨

回復 8# kevin
( r$ k6 D  p+ [/ y
0 @3 a# T; a) m  w' q: O
$ S+ {4 v& c% M    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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