請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
. f2 J1 d5 j  T5 F4 L' d7 I) X) S0 T$ W還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
% M1 `( S0 h1 V$ o4 z# G: S
假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
( F* d' _; t3 e5 hif (Reg(n) > Input_value)
+ [% U/ H$ L  Q
5 d) [* x0 l( G! W( o       Reg(n) <= Reg(n);                   //保持原來的值

+ S; u- L9 @2 B& C. p* v% ielse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

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

else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
( p; l! K/ r# H( D9 g$ e      Reg(n)  <=In_value;             //load input value
         
2 ?1 e! f8 P9 }: v& t- X" l$ }1 t+ P每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
( f* c9 z& f; G
; g' C* S* Y( f: g5 O) O至於你real time輸出~不太懂你要表達意思~

7 e" W* q7 v' o1 K# R你可以把你整個架構描述完整點

1 u, z9 E: s! T) X1 C這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
& S1 X) ~( b' _* d+ B

+ [( ^; k7 C' U6 S5 |8 [  E/ [8 |    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
' e6 y. A0 Y% X  ~1 L因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

首先看排序方法
4 ~7 X' o& f+ i" z+ R( d再來看比較器有幾層,還有比較器的寬度

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
( m! w9 c& C* }, a8 P7 d至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
/ y  g5 O1 p. o+ N0 m
5 u) i- [. C6 `- |舉個4進4出的例子:
+ J  ]5 p& [* ~* V* O  E2 y& rinput [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
b[0]=min(a[0], a[1]);
4 B3 q: N5 Q. a" db[1]=max(a[0], a[1]);
; Z; o3 o# g3 a) fb[2]=min(a[2], a[3]);
- {0 g" O& g( H, n$ Ab[3]=max(a[2], a[3]);
! w2 c. v$ Y( u9 ?第二次排序
c[0]=min(b[0], b[2]); //real minmum
; D" g) v& F, c7 {c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
5 t( h  W* ?7 k3 P6 E9 G0 D/ \c[3]=max(b[1], b[3]);//real maximum
第三次修正項
* S/ S6 I" Q3 Z" r- I8 wd[0]=c[0]; //real minmum
" Z: W% g- M& @9 ^" w! r9 X" k: j- ad[1]=min(c[1], c[2]);
d[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
# Z0 [0 l2 e& A8 m" k! Y5 h& D//d[0]~d[3]就是依序小到大的答案
) _9 L& s/ B( n: C% k# V) K2 }
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

實做的考量
1. 實做上min()跟max()應該是一起做的
: N( h5 W2 G* `' B if(a>b)
     min = b;
     max = a;
- D' L* Z$ v' ?8 G3 [3 r  else
    min = a;
' K8 \9 [0 u5 y" s% F, L% c. r    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
- c/ b3 g7 p7 S3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

回復 5# tommywgt


    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
- |0 U# j! ^# m我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
" y# A7 e, B' G/ C- `% O, V) q則想像成
: T% H+ O- H1 m* S- s" J5 9 6
1 k# P" j# u9 }7 8 2
4 m( Q  h! Z' d. }) U1 3 4
  d' f5 i& F6 `2 p不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
' [5 g: U8 t$ {6 ^8 s- M將3段數值分別丟入R 得到
. h, ]  @1 ^7 \4 d) e: t5 6 9
2 7 8
1 3 4
這時候再將 垂直列的3筆丟入R可得到
1 2 5
8 s& w( i1 _: U& D- |/ ~3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
: ]) H+ f+ H7 A7 }9 f/ j2 E  T9 ?
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
  F1 }# a7 T1 w8 }+ }# O3 5 7
( m0 u! u' Y1 K' z8 G$ z% k6 8 9
這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
9 }5 M: R5 u$ o: M2 w其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
8 |. C( m! U) l; D1 H8 y! f2 E最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
- r) n& V' P+ i0 R( a當亂度能包含所有的項時, 答案一定是對的
, \. j9 h6 F3 d' Q1 X$ j7 i5 f所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,
, e( f+ L' T$ D) D. A) V7 L
有人有更佳解嗎?

呆頭鴨

回復 8# kevin
5 \# g7 W8 y1 y6 Q2 @; q
& U1 p* B, U7 W8 C0 r5 d
: ?0 T( I( m7 d. B6 ]    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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