請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
5 u: P2 i6 u% W4 R: Y" k有辦法達到real time輸出嗎?
7 E: e& W, p2 {* J3 |2 d2 P還起大大們提點

kevin

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

0 m. f/ b2 n2 N+ U: q8 n% S/ P假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)
8 j9 `% c/ r0 e+ B
) I! z8 [" {: {5 R3 Z       Reg(n) <= Reg(n);                   //保持原來的值
/ \4 F* ]6 j6 d0 G8 A: @# I- o
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

( `/ x" [' g7 B" S/ ]) W       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
8 s) E' A8 g* A5 a9 d, w. I     
      Reg(n)  <=In_value;             //load input value
& d% @3 q& e- z( c% q0 R4 J4 K4 R% |         
# O, t0 @( {  @+ U* _& u; u7 t% A# g每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
9 s# }7 i, o7 D! a# r
; f9 W4 [5 U, m& m' ^& S至於你real time輸出~不太懂你要表達意思~

; Z0 W! N: x7 F& n/ E- b0 v你可以把你整個架構描述完整點

$ F1 m% v' p  f7 t! d8 s這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut

. Q6 i5 u3 z  w* V8 z' M3 S
    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
) p" z0 E5 G) x8 `   所以要將畫面中9個數值做排序後輸出中間的數值
6 M+ o& g% _- Z. Z因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

首先看排序方法
4 F% c) [+ v' w0 `) Z再來看比較器有幾層,還有比較器的寬度

tommywgt

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

舉個4進4出的例子:
input [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
/ n' \: I+ R( n8 _' S& [b[0]=min(a[0], a[1]);
8 I. J; J4 n" D& z& R7 y: Q5 e( |b[1]=max(a[0], a[1]);
, {, D+ P/ e! d3 M/ eb[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
1 a4 D3 L/ ?' k* e第二次排序
: h& D( i8 q: f8 e* y2 m5 U# Wc[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
% V& k, A) s- e' }' gc[3]=max(b[1], b[3]);//real maximum
. [, I3 H8 t" u" s! \, t6 A第三次修正項
5 t1 L5 e4 S9 P" U$ H3 Sd[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
; m& M, t$ i$ A* Q+ i+ Hd[2]=max(c[1], c[2]);
+ {) J# ]' H% ^( R/ w& y) Z! i' S/ td[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
6 W: u+ g  W+ z
7 U/ K# o" b7 j這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
/ G' L' }5 t" V7 `
3 S+ |$ N7 g8 T3 J實做的考量
1. 實做上min()跟max()應該是一起做的
" H- n/ E6 F! N' p1 } if(a>b)
     min = b;
     max = a;
  else
    min = a;
+ Z4 b2 S* @9 Z/ b" Y    max = b;
5 E( {$ W. R) F* G( k2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
8 ^, O8 g0 I6 Y! }+ {1 ]3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
. U" ^" I; G6 a" W) j1 u0 T1 eP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

回復 5# tommywgt
1 |1 k( p( F& v9 z9 Q" h) N6 b
6 p7 N1 G: w4 p3 v* U0 X
    謝謝大大熱心分享
8 s7 I6 m! B' p我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
3 z" e3 t- w& T. [5 9 6
7 8 2
1 3 4
0 E$ O& {  |2 p& v不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
3 [# i& X$ Q# X$ V' q9 |& T) y5 6 9
2 7 8
# b" M9 s/ e9 Y+ h# E* ~1 3 4
4 N2 h$ m" {- U! V; |: ?* R這時候再將 垂直列的3筆丟入R可得到
  K5 B. I+ K0 j' {: Y( O1 2 5
3 6 7
5 E% a, ?8 f- d: ~8 E) d% L- W4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
0 Q) n" `' e( Y& |5 Z$ i% m6 8 9
  y# O7 T- r' `8 k- u  R5 k這時候可以發現
: d% f+ F% M  R  k1 z中間的數值確實是9筆資料按大小排列後的中值(5)
9 S/ W, N! D. v5 O) z( Q: q: `2 `雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
" @; V) p( }: z其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
1 E1 N# S: X7 s' D( `  J$ |7 ~, ]0 E最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
0 i( O$ v3 Z7 u7 Z: |% R  a當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
% I6 j( y) l4 X% ]. p& s左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
/ @. z4 D- M5 n所以在最大的亂度中, 8-1=7次應是最多的運算了,
0 G. m( K3 r8 @: _
* g, k4 Y. g2 R: r- e3 K2 }/ V5 }有人有更佳解嗎?

呆頭鴨

回復 8# kevin


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

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
* ^3 u8 u$ w4 a- @- F5 Y2 r! B( u22排序 看起來是不錯的做法, 1 clock 即可做完.