請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
! |* Y$ q8 T& c  X) ?我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
: i. ]$ F7 Q0 {; a+ P* C6 D還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
' e, o6 w) m; B$ N9 L
假設有九個registers,每個register附帶1個comparator,
$ z  E1 [4 p4 v5 I每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
) B$ a- c$ ~1 X6 {# d3 c8 H/ kif (Reg(n) > Input_value)
2 r/ |9 U3 ]* b5 v4 _1 g$ \! e
* x$ M# A& W9 g. [- S7 P       Reg(n) <= Reg(n);                   //保持原來的值
7 ^* ~) k) v! n( ~6 {
1 G4 O) _' M4 J1 R2 Q" }else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

$ t- h" D5 c& e/ t' R; `0 k       Reg(n)  <= Reg(n-1);             //shift in 前一級的值
' ?  I/ _  B7 Z/ b7 j) e
1 L* H8 d! T3 B5 l, G0 Gelse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
% i1 a: X1 t2 j- q. t- c6 ^8 J     
7 D. ?) c6 ^5 H( }6 H8 w" s) F      Reg(n)  <=In_value;             //load input value
         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

alita

我覺得 對於3x3的median filter
1 H) F! S0 w& p) b3 ^  v22排序 看起來是不錯的做法, 1 clock 即可做完.

tommywgt

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

masonchung

桶米版大 真是太棒嚕

呆頭鴨

回復 8# kevin
$ G  m+ G; J( ~4 S$ P3 i% i5 t2 ?

& w. a! f2 _" v) g) A$ e: j    大大的方法真不錯~ 我怎麼沒有想到呢XD....

tommywgt

啪啪啪
& u' m7 g9 \. W3 a3 {3 D7 R$ t其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
! {1 X3 B( d3 N: z& l# o9 M9 u5 v; U當亂度能包含所有的項時, 答案一定是對的
8 z' ]5 h/ U6 c* r4 i5 ]所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,

有人有更佳解嗎?

呆頭鴨

回復 5# tommywgt


    謝謝大大熱心分享
4 v8 I# j) _, I& Y. K  I/ }0 l& q我目前的做法是這樣的,提出來給大家研究討論一下.....
9 V! z  l2 \$ U. R; f2 _  E. w2 j' }我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
7 P; e/ ^1 T2 _" `1 u$ g7 k& l' j+ Q則想像成
. {8 H* @; S- g, e+ b! x) t5 9 6
0 `  O2 [/ g% d3 T7 8 2
2 z4 ~' h& A" _7 J4 B  K+ q* D1 3 4
" I. p1 c! x( c不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
( @& T9 ~# V( ^: x5 6 9
8 h& U: Q, H, j" Y  T2 7 8
- r. j9 [$ |7 I1 3 4
- ?# U$ T8 }! J0 M. F; C9 ?: Y這時候再將 垂直列的3筆丟入R可得到
1 2 5
3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
* ~' k+ \1 j0 x  D+ }
2 X9 i( M8 h0 N* w- z' Z7 S, R最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
6 8 9
這時候可以發現
6 @  k4 `# Z5 z中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

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

舉個4進4出的例子:
input [word length] a[4];
6 u% E/ j; t. f+ G- a2 \5 _reg [word length] b[4], c[4];
第一次排序
' V- ]! n2 g+ Ab[0]=min(a[0], a[1]);
6 W9 _# }+ _5 w5 H& u9 Vb[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
& }7 i5 R6 @9 V% P* b& b第二次排序
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
第三次修正項
d[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
/ t( ~( H7 S/ \% v  c! `d[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
; z% C; J4 x. l//d[0]~d[3]就是依序小到大的答案

這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
& g& O1 L- J* R3 J+ g) t
實做的考量
  K8 ^' v1 b; k  o4 r1. 實做上min()跟max()應該是一起做的
/ d0 X; C8 F* z# K if(a>b)
     min = b;
     max = a;
( I: {/ x. }  I' R  else
    min = a;
" h1 B+ R4 q3 X5 z5 X5 u    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

masonchung

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

呆頭鴨

回復 2# kokonut
6 s, T0 r  O$ b3 p# m! j( p7 U
0 V2 p: ^9 w) U, ~5 i. h
    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
( i$ W8 i( y' P5 M% T5 i因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

kokonut

你把A1~A9吃進來後~要先排序處理吧~
: L# P+ H: O7 q0 f# P& l) I
( D' x9 F. i3 s至於你real time輸出~不太懂你要表達意思~
' z* Q0 P% }- T* o# i% _/ A
你可以把你整個架構描述完整點
4 O6 E6 a$ C3 K0 c$ Y0 b" q% y
這樣比較好給意見~!!!