請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
4 b/ X4 Q4 J) T- ^" X有辦法達到real time輸出嗎?
. ?0 Y' V) ]( J% H% p+ F還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
7 |' e9 e3 {4 B
" F" T. R" O2 ]  ~假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
# r9 r- y2 S( T/ [6 [+ p$ Uif (Reg(n) > Input_value)
. A; X. w3 p$ J* g* B) y3 R$ q
# N3 B7 h/ |# b' \       Reg(n) <= Reg(n);                   //保持原來的值
6 F5 U) f: V" j
( r8 e  Q& y8 T7 d+ j: Selse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

* |3 E( B( H/ E. R: ~1 T2 ?       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

0 g( D7 @' O7 L5 |2 qelse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
4 u& L" G2 `% X7 T' m     
; y) A+ H4 d0 i, C/ O5 G      Reg(n)  <=In_value;             //load input value
9 h( T2 e; s3 H$ b         
+ A- W2 ?8 i5 L; {& Q7 y0 o1 o每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

alita

我覺得 對於3x3的median filter
7 q+ m7 c7 N$ H6 f4 _22排序 看起來是不錯的做法, 1 clock 即可做完.

tommywgt

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

masonchung

桶米版大 真是太棒嚕

呆頭鴨

回復 8# kevin

# D& c+ w; F/ E* q8 a2 Z; j" {4 B3 D
$ T- `8 B: o( X) O2 v# c, T    大大的方法真不錯~ 我怎麼沒有想到呢XD....

tommywgt

啪啪啪
) t( m' L: }7 q0 O8 L' I其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
% E/ \  _. U' ?" E5 r3 b( F& O最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
, E' q6 {4 D8 \所以關鍵就在於如何用最少的運算次數達到最大的亂度.
8 A+ n; P9 ~2 b% h, k左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,

4 y$ H8 q0 x+ y9 d* \' Y: v有人有更佳解嗎?

呆頭鴨

* j; {- L. _! i* }' U+ b回復 5# tommywgt
7 m7 C+ ~- p  x( z
" F/ g$ h0 U6 F  F4 a4 I9 s7 h
    謝謝大大熱心分享
9 i% p9 V2 ~$ ~( W; X3 s我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
5 9 6
7 8 2
' F& n# b9 `1 G+ U/ t- B+ ~1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
5 6 9
2 7 8
1 3 4
( h+ w0 a7 e8 E這時候再將 垂直列的3筆丟入R可得到
1 2 5
3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
: f; q% v- Z; [2 q9 {) Q6 r
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
) w& m; V, v8 R  Q1 2 4
+ S6 {5 q* s* z- |1 ~% e3 5 7
6 8 9
這時候可以發現
% h6 N: R7 K1 F1 N$ G$ W3 V3 y' d) i中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
4 O" Q' K3 R" i- `( j至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
5 K/ F, g7 S6 U6 ?: ?3 t
舉個4進4出的例子:
input [word length] a[4];
' k, ?0 y1 L0 j* _" r- Dreg [word length] b[4], c[4];
" }, L8 n- [2 z) c+ V, B9 D第一次排序
- G7 Q& X  ?/ a  ib[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
9 H  Q1 L  n- ~% Z# y- R8 rb[2]=min(a[2], a[3]);
. p: g* d: L6 D, |1 I% Ob[3]=max(a[2], a[3]);
第二次排序
2 b7 w/ C6 a# Y3 x* [) ^4 w8 E1 bc[0]=min(b[0], b[2]); //real minmum
9 A) i& f8 P0 B: w9 R6 Z# rc[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
, T1 o# d" Z+ A4 h$ {) V' N& Dc[3]=max(b[1], b[3]);//real maximum
* S3 W$ s6 M& T4 A第三次修正項
% A5 D$ ~- H/ i1 G  Xd[0]=c[0]; //real minmum
. }/ Q- o& Z: J6 ~/ dd[1]=min(c[1], c[2]);
* b" n. u) N" L9 @/ P, {d[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案

這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

實做的考量
0 P. f0 d; ]7 ]7 ~& E6 E( h! T% S1. 實做上min()跟max()應該是一起做的
if(a>b)
5 o: x( f, U+ Q; a- Z     min = b;
9 V# I) z0 f7 Q/ r     max = a;
; M1 X) L- k7 u; r( ~% N  else
. n1 U4 W1 c- j, S0 O    min = a;
0 N9 d. A: X/ g" i! N    max = b;
* U* `4 Y6 _, ^/ `! k2 G" `) D2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
8 K$ |# o: Z2 K, o6 q& o3 l2 c& LP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

masonchung

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

呆頭鴨

回復 2# kokonut
& q. J2 _% D; R: o" p+ j

    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
) K0 u/ v% k- z   所以要將畫面中9個數值做排序後輸出中間的數值
/ U) o) @- [# \2 ^* J. F% H因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

kokonut

你把A1~A9吃進來後~要先排序處理吧~
6 W0 w* {1 L6 N8 p# ?9 q
至於你real time輸出~不太懂你要表達意思~

$ k' Z+ S* \1 G6 J0 U你可以把你整個架構描述完整點

% i% x4 f/ ?2 R2 ~7 a這樣比較好給意見~!!!