請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
5 y9 t0 c7 g' O4 o$ N9 o7 b我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
/ L' L4 {# i; \) H% T' \還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
) x7 |3 y# v2 ?# I
假設有九個registers,每個register附帶1個comparator,
  w+ D* I; k/ o+ J每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

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

else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
5 I7 a/ V3 y" N! S
       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
/ x: h7 A/ k! o0 f     
      Reg(n)  <=In_value;             //load input value
         
& F5 I5 D/ X( |0 p' V6 P6 L% h' m每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

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

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

你可以把你整個架構描述完整點
4 u% u2 M- a1 o; N; b- K8 z
, S/ f2 z; n. m( l# K  X/ `這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
4 Q, |$ e  _) h2 ~  O  @
' S5 T  y3 D' k
    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
% e* [& @1 @' N% @   所以要將畫面中9個數值做排序後輸出中間的數值
, U' r2 }9 _: n; Y因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
' C, f  J5 f3 A! P# X! e- K; {大概是這樣子...0.0

masonchung

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

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
( b$ x2 g# J; d: i) V- P至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
1 c. u. R% y+ k5 Z
舉個4進4出的例子:
' v8 E* n$ r2 Y2 X7 dinput [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
/ q+ z& K  J* f$ t4 r' S. pb[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
  Z2 l" r1 W: u* P- Jb[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
3 E" [- u' g) {第二次排序
c[0]=min(b[0], b[2]); //real minmum
/ n9 I6 l; S/ H) z, {& ^; J* ec[1]=max(b[0], b[2]);
, d: M' i" t, ^* }& x6 qc[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
第三次修正項
/ ?& L8 v# _) O- X/ _6 T, b9 g3 dd[0]=c[0]; //real minmum
( t% T/ F; s/ o* }; ^5 @5 F* od[1]=min(c[1], c[2]);
d[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
' i! k7 A/ J6 W9 |4 o: k
% C. I; C& i; {% q( ~這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

實做的考量
1. 實做上min()跟max()應該是一起做的
1 u4 y1 \8 R, I" @2 g! E& g. v if(a>b)
     min = b;
6 P9 a: l4 T! B& W- r9 F     max = a;
  else
3 l/ S. T4 o4 M2 i    min = a;
3 v5 ?; Y8 J- Y0 I  i& ?# ?& C    max = b;
  @, [$ s' m$ u' Q2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
( x( ^+ l* O. Q5 T9 p8 y, ?1 g3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
$ Z2 n- q' A4 H3 J+ CP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

回復 5# tommywgt

0 F, e- R  Y( }9 @6 Y+ }/ X9 N  v
    謝謝大大熱心分享
# D+ k# t  q+ x2 i; L我目前的做法是這樣的,提出來給大家研究討論一下.....
# L$ }) `6 C4 i- X% M1 |8 ~我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
0 ?+ r3 i( l# g% y0 I5 9 6
6 H& s$ G/ ?2 N- o2 X' T4 S: c7 8 2
' J' b' v* F- T! d/ g* X$ o1 3 4
5 J1 @# L9 o/ J不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
7 V* f: ?. j& k* c( R# X9 I. U將3段數值分別丟入R 得到
6 J5 G4 t% F3 C" ?3 i) j5 6 9
2 7 8
1 3 4
) ~* U$ O1 F  x' n+ X9 Q. r這時候再將 垂直列的3筆丟入R可得到
1 2 5
3 6 7
/ C# @- Q: F* @) h& @4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
+ r) @( w1 y. J+ Q4 I! T6 Q
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
% a7 c( _* ]/ s2 }- R1 2 4
3 5 7
6 8 9
這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
. I! Z* j# {( _9 E- T最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
3 a5 E. [/ T: D2 p5 ]# r; f+ _當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
; D) ~" T0 v2 z2 ?所以在最大的亂度中, 8-1=7次應是最多的運算了,
! e7 X; f) j, p" V% r6 D, w1 M
: \3 q& P: p+ T- M有人有更佳解嗎?

呆頭鴨

回復 8# kevin


1 C% A) j  f& N" q  ?- S" L    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
9 w' a) z# v" @' O# X22排序 看起來是不錯的做法, 1 clock 即可做完.