請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
0 n" d  W) }  ~  M4 v我有9筆資料 同時輸入 A1~A9
, C3 t4 D8 f: R/ j# [要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
! w, G# L: V- [' u$ I; Y! S& z/ l) ~還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
. n- t* {" G- L
- Z9 w0 S( P) V2 L1 G6 Y) z0 J假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)
$ d2 {% I' s" _, C7 H6 `: D
; |6 S7 c9 P) \$ L. ?3 a1 Y       Reg(n) <= Reg(n);                   //保持原來的值

+ s5 n/ I$ v$ O) R( S8 ]* lelse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

3 d; \1 t1 S5 [  t9 C       Reg(n)  <= Reg(n-1);             //shift in 前一級的值
, {. R' ?. M" R
else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
( l* Y* S3 Y' U* R% k     
; {( Y  _& T; q$ o      Reg(n)  <=In_value;             //load input value
- a, x1 B4 \; p4 O5 ?! j! c6 w         
0 {2 ?; _7 F( W, Y5 R, _% E每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
+ q/ [# E6 `  A/ `" ]
至於你real time輸出~不太懂你要表達意思~

你可以把你整個架構描述完整點
0 e! P) i" y& K, Z+ G; g/ L4 N$ R
這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut

) j+ E3 E0 {( |  T) s
4 S% K9 X2 {- B% p    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
' x0 T3 ?8 w9 Z& V# M   所以要將畫面中9個數值做排序後輸出中間的數值
/ }! }" @/ k, u因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
2 }; W! j( u7 j: g  C) z大概是這樣子...0.0

masonchung

首先看排序方法
1 o0 [8 r" W$ h! p' b再來看比較器有幾層,還有比較器的寬度

tommywgt

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

舉個4進4出的例子:
% T; d* e% g; A3 Minput [word length] a[4];
( @9 }+ N+ s3 g) M6 T$ v- Q1 ireg [word length] b[4], c[4];
) M, w' i( T+ T  U9 r: P第一次排序
7 \5 g! N7 u' M5 Cb[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
' y6 Y! N6 Z( Q1 |( `b[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
$ F1 f, X$ M1 a- Q第二次排序
! V1 F  ^% X& P6 Bc[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
/ }: I4 f6 x0 P+ |2 m7 M0 Ec[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
+ |1 @  R7 m- A' C: H& u第三次修正項
d[0]=c[0]; //real minmum
. j2 j+ R5 ]& P8 q! _  zd[1]=min(c[1], c[2]);
d[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
8 V0 ^+ ^' u' b9 s* Y5 u( Y
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

& P$ c6 J( y7 Q) D1 y! _# v# A實做的考量
+ L& U' o! K3 Q1. 實做上min()跟max()應該是一起做的
if(a>b)
, {7 c1 b! U. j- v# p2 ^3 o3 B     min = b;
     max = a;
  else
8 m) P3 D9 `1 A" |9 g9 j/ l    min = a;
( x7 j7 ~6 D4 E; s% l    max = b;
5 A  K( Z3 [+ r+ m2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
# l/ r) R& ?; U, t1 W; p8 WP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

( @, F" P- @( d3 a
' `$ D( X! O2 x$ c' }回復 5# tommywgt
! s/ t3 O) k" Y0 F* i
& o, Y  f1 Z( Y& t2 ]
    謝謝大大熱心分享
/ b1 H2 T/ Y% {5 {1 B我目前的做法是這樣的,提出來給大家研究討論一下.....
# }6 s1 X7 P5 y& U2 {" l我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
0 H( f: g7 e7 P8 ?則想像成
1 y5 K: c6 a4 G0 P, ^5 ^5 9 6
7 8 2
8 N& k4 I, \1 i+ L; J9 m0 h- S. a1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
8 s% {7 z' d5 l3 l! b將3段數值分別丟入R 得到
' e6 v: l6 a1 `+ V+ {0 z5 6 9
2 7 8
1 3 4
, Q4 e* s5 L; P" C0 p- f# |這時候再將 垂直列的3筆丟入R可得到
, X4 O( G8 D7 A& g1 2 5
3 M# N$ q; U4 t& C/ W1 y* X3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

4 {8 C* y9 k4 H, @' {* {- N! Y最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 ^+ E3 y" c% N% \5 ]1 2 4
3 5 7
6 8 9
& U7 v9 ~) i4 Q5 v( n這時候可以發現
: F  i$ |, N3 V& F' U8 T中間的數值確實是9筆資料按大小排列後的中值(5)
* K0 i: w) @4 K8 Y雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
# O4 W8 [( G/ u. T最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
$ P, Q2 R' L2 H* O0 M8 W左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,
! Z1 f0 R- o) k
有人有更佳解嗎?

呆頭鴨

回復 8# kevin

& _) v& K3 w* r& b& L
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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