請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
+ k: b0 e5 g) ~% b' _' b5 P6 [我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
. h- i  Y1 m7 s有辦法達到real time輸出嗎?
還起大大們提點

kevin

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

假設有九個registers,每個register附帶1個comparator,
$ H* ]% g, `; _每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

* ?) X7 K% v2 q. c$ D. v       Reg(n) <= Reg(n);                   //保持原來的值

/ Y) x$ i3 A& {. M% Nelse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

+ Y# M- q9 X( J1 s# t8 Z1 pelse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
9 A' j9 {! [7 r- G  G  ~     
" k) c+ i4 F) W! M2 f      Reg(n)  <=In_value;             //load input value
         
' C3 u. c/ x; V5 o  `; ~% g$ U每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

alita

我覺得 對於3x3的median filter
# T& o) I6 ]! }" O. e22排序 看起來是不錯的做法, 1 clock 即可做完.

tommywgt

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

masonchung

桶米版大 真是太棒嚕

呆頭鴨

回復 8# kevin
+ E! z# T6 t3 z0 |, p2 P/ T
& t: F# J# L# F, l/ [
9 j5 b: L" z$ f/ Q+ P    大大的方法真不錯~ 我怎麼沒有想到呢XD....

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
. x6 O; J" B) j/ T3 I最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
0 X8 ?4 r1 d- u! O4 L所以在最大的亂度中, 8-1=7次應是最多的運算了,

! s* a5 x) Y! |8 D+ e. [9 Q有人有更佳解嗎?

呆頭鴨

回復 5# tommywgt
. g+ ]/ `1 M* n9 ^3 u) X* X( s
% f/ ^+ }: x# j4 c- [, {
1 X, V2 q( C. O1 c3 G% q4 _    謝謝大大熱心分享
1 d+ P, |7 F9 O- F我目前的做法是這樣的,提出來給大家研究討論一下.....
% a% |3 Y% Q5 q5 _1 K6 j7 W$ S4 Y我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
$ \$ b" ]% d( Q2 }+ b" p( C1 g則想像成
: r. K" p$ \  d8 G/ h0 ^% x5 9 6
7 8 2
: e) u# e8 d6 t+ v( F$ a1 3 4
# G! }, J) g) M: x& X1 G% N不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
) t) p0 X9 j( A' v8 K/ \2 ?3 C  X5 6 9
2 7 8
1 3 4
% s0 R7 @8 y" p這時候再將 垂直列的3筆丟入R可得到
1 2 5
' c+ K+ @; i* j3 6 7
9 r2 D- U0 _5 f4 b4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
# v- m6 I4 P  E  U3 5 7
( V3 V; D$ y( k  ?6 8 9
( p& Z: a" y' ?; W2 U這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

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

7 m! C: K# o8 j/ l) I: A  |舉個4進4出的例子:
input [word length] a[4];
# K" l2 x5 `, k: Breg [word length] b[4], c[4];
* O& p) [8 d) i  o9 l第一次排序
b[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
; ^* \6 K" i8 lb[2]=min(a[2], a[3]);
# C7 M) z3 d7 f3 E; A. R! F5 J+ hb[3]=max(a[2], a[3]);
第二次排序
* V$ k$ A% M, d* w4 S: U4 F+ uc[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
第三次修正項
/ v1 R4 e# E/ M+ @3 h+ F' X3 y: q$ hd[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
) @  S6 z/ w0 S! h3 M" Fd[2]=max(c[1], c[2]);
. I# {8 l5 g0 V7 V1 Z1 `d[3]=c[3];//real maximum
& i  n& r, E4 c/ m# V: [# X. l//d[0]~d[3]就是依序小到大的答案
/ C6 Y3 Y7 T8 S/ l
5 p6 X7 N- t$ ?這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
1 x: F9 m* j- V) J2 O; j
實做的考量
1 Y1 G- _9 E6 t  O; `% r1. 實做上min()跟max()應該是一起做的
* \! |  q$ W+ v if(a>b)
7 Z5 S; ?# @; Y     min = b;
/ H/ B& {3 @2 x+ S9 w# g     max = a;
  else
9 |, Y3 O8 g/ T! d6 P    min = a;
    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
' I$ p8 m! o3 {# oP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

masonchung

首先看排序方法
' a/ X# d% S* I' P/ X4 @再來看比較器有幾層,還有比較器的寬度

呆頭鴨

回復 2# kokonut


    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
% L( R: e, L: V8 l. d. c   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
7 z5 S2 e" Z. p2 j- G* U3 T; q大概是這樣子...0.0

kokonut

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

至於你real time輸出~不太懂你要表達意思~
1 u+ Y: u3 ]5 ~# d) _4 ]2 \
! B; |+ l  O: e  F1 F$ i你可以把你整個架構描述完整點
- Q# k+ H' z* Z4 P+ V7 o; c
這樣比較好給意見~!!!