Chip123 科技應用創新平台
標題:
請問~Verilog 設計資料排序~
[打印本頁]
作者:
呆頭鴨
時間:
2010-3-31 10:43 PM
標題:
請問~Verilog 設計資料排序~
請問大大們~
$ L, D' O6 m0 [6 p
我有9筆資料 同時輸入 A1~A9
" E( {' e# S% l$ L" n# l2 C
要如何設計才能達到按照數值大小排序輸出X1~X9
0 n# q3 z3 S+ h
有辦法達到real time輸出嗎?
* \+ a4 _4 I* @; W7 a R
還起大大們提點
作者:
kokonut
時間:
2010-4-5 04:30 PM
你把A1~A9吃進來後~要先排序處理吧~
0 Q- n9 _2 ^- W% \9 G' ?8 p
7 B. ` [. j( D0 n3 I7 C
至於你real time輸出~不太懂你要表達意思~
8 G @+ b; p7 F% ~$ X F
$ ?3 d ?' E8 i: P6 i" S+ Q1 @1 A3 ~. g }
你可以把你整個架構描述完整點
4 s' G& T$ s% r3 ?
2 x: m9 Z/ q- ^
這樣比較好給意見~!!!
作者:
呆頭鴨
時間:
2010-4-5 09:41 PM
回復
2#
kokonut
& K1 H. |; n* ]* q
: ^) f Q9 l& I, r
7 r: B* Z4 L# p9 d7 N4 D% y
是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
4 {! l& C0 A8 N
所以要將畫面中9個數值做排序後輸出中間的數值
g$ p$ f4 d( u; ]
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
$ v, `% Q# C! E, A" o: S
大概是這樣子...0.0
作者:
masonchung
時間:
2010-4-6 02:12 PM
首先看排序方法
1 j! ^! G; a* |8 k6 [$ E
再來看比較器有幾層,還有比較器的寬度
作者:
tommywgt
時間:
2010-4-11 03:41 PM
對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
( R) W7 }8 S( P- l
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
; B1 ?) A; v2 U( M; s1 O, y; |
, ^1 i$ z& \# V7 _# Z% c' U
舉個4進4出的例子:
! a# n& c; |6 X9 o- q" X
input [word length] a[4];
# c2 w! `( l, c `0 n
reg [word length] b[4], c[4];
; V. W6 m) R+ M5 y, r0 c" x; o z
第一次排序
% `& P" a, {2 i1 d
b[0]=min(a[0], a[1]);
6 z" p5 ]4 Z: F9 T1 d
b[1]=max(a[0], a[1]);
$ U) i! m) q0 `& m9 x$ H/ Z
b[2]=min(a[2], a[3]);
. j# l4 `- a- C9 L
b[3]=max(a[2], a[3]);
0 J, K% B0 L/ U
第二次排序
& A/ H+ s" Y: e- {7 A1 _
c[0]=min(b[0], b[2]); //real minmum
' S/ ]. @& S) o8 M0 n" N
c[1]=max(b[0], b[2]);
" v! E/ A! t @
c[2]=min(b[1], b[3]);
7 i7 W* V9 J {. Q4 d
c[3]=max(b[1], b[3]);//real maximum
0 G5 [& N& h% J1 b7 S: d* Z7 ^
第三次修正項
/ h2 I0 l+ e F% `0 ]
d[0]=c[0]; //real minmum
9 A+ p6 Z! a7 `2 F8 B
d[1]=min(c[1], c[2]);
. g$ ~# I! `, {7 _
d[2]=max(c[1], c[2]);
5 x% a% |' I1 i, g7 @; R# a5 ^* w8 i
d[3]=c[3];//real maximum
: E! _$ T9 Z' q3 [
//d[0]~d[3]就是依序小到大的答案
! o/ L, W5 ]: J% G% _1 ^7 t
& t: p3 ~' X9 b6 E* E1 `! r c
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
3 [, l, w4 p; i: q" s$ r
( Q4 l. A3 C) c+ F; E8 r
實做的考量
K. N- {8 Q* P" D7 e% v
1. 實做上min()跟max()應該是一起做的
7 h) [; U) F3 q* e4 x
if(a>b)
" d& J g7 _: n; h, o2 l
min = b;
0 {9 E* }, G. ^" J
max = a;
" I' I; y' D( w7 F: e; }
else
: @# v$ F) g) X& m; Q8 E) @
min = a;
( V2 `+ @- ?1 v) Y8 A4 u
max = b;
8 \6 O+ D' c1 W% z0 C
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
+ d" c6 d/ c8 i- D
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
3 z0 u+ m- g) W y1 w; b# ^& d- r! E! s
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD
作者:
呆頭鴨
時間:
2010-4-12 09:05 PM
本帖最後由 呆頭鴨 於 2010-4-12 09:06 PM 編輯
7 L7 w& l0 j5 y: r2 `, a
* b7 q8 `- f/ W
回復
5#
tommywgt
' J1 `' ^5 N1 _* X0 ?& j( E5 K) ]2 n
6 W, M! J$ l5 ~, j
F- }3 G' `. [' C( Q, }8 H0 |1 ^8 \
謝謝大大熱心分享
; [/ I8 o! ~4 D" @! r2 Q
我目前的做法是這樣的,提出來給大家研究討論一下.....
# O* b4 `) t8 C$ Y
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
/ u3 g+ l G9 n! k% P
則想像成
% J" }8 x( k( V- k% u2 s; e
5 9 6
: O" T: c4 X2 O! R, X
7 8 2
. H6 f6 F* T6 C
1 3 4
+ P% m; ?5 f+ K; b# | `$ e' x, K
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
% ]5 n p( e. v* ?% o2 v/ W
將3段數值分別丟入R 得到
* m8 S7 d% G& M. q/ u0 c, q1 ]
5 6 9
) v& c" J- P' W' n# A z& Y
2 7 8
/ q9 J. n9 \! R7 u% F! c: \3 [0 J
1 3 4
! E! {* t( b. c, N7 Q
這時候再將 垂直列的3筆丟入R可得到
% C+ S$ p$ `8 B1 [$ o) |1 }; V
1 2 5
) l9 z% T7 h! M& w! Z8 I; u
3 6 7
! f5 l1 X7 k% p, ~: s
4 8 9 (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
! B3 }7 W& `# c) N7 S, {. N
5 |3 Y- b" i9 v7 Y! G7 N0 ~9 V
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
/ ?& p# ^* ?$ |; s3 `7 F' {
1 2 4
* u1 c0 s9 m! Q- z6 h! L" s' l
3 5 7
- q, O6 I! K f
6 8 9
! \+ J; _. w2 r( a6 p+ y
這時候可以發現
' L; K9 o3 e( s: j: g' i9 ?
中間的數值確實是9筆資料按大小排列後的中值(5)
4 |- e) T: I4 g5 \8 ^ w7 E' |
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...
作者:
tommywgt
時間:
2010-4-12 10:31 PM
啪啪啪
, U" v d( a+ g w0 K: N9 Z! q
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
. H U+ r5 A' Y
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
) o# V1 K& n$ B5 N' [. m
當亂度能包含所有的項時, 答案一定是對的
+ V2 O3 t* a0 I a' E) J9 d
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
$ h5 W+ z6 ]& X( D
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
$ p- }8 k& e0 H$ [6 P
所以在最大的亂度中, 8-1=7次應是最多的運算了,
5 D" I+ v: w, X* J
4 T; z# V l% X* i
有人有更佳解嗎?
作者:
kevin
時間:
2010-4-15 07:48 PM
資料量少的話,用插入排序法則也不錯.
/ L* ?- R Z' S7 Q2 e- ?; L1 M/ u
[attach]9340[/attach]
5 Z' C0 p; g3 R0 ~- I
假設有九個registers,每個register附帶1個comparator,
: c B8 B+ N- y8 \0 X
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
) S6 T# H6 x t4 p
if (Reg(n) > Input_value)
0 S! V* W% o1 t! Y4 }
) y2 X( B% ~, `
Reg(n) <= Reg(n); //保持原來的值
" Z, f7 S8 j% W
5 n3 |& t" d! O% X; ^- r" l
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
Z& L6 X' L' R
2 [) D3 m, L6 N( t8 N
Reg(n) <= Reg(n-1); //shift in 前一級的值
% \- K% N: V! m( Z8 H% ~. C6 x5 n4 k
. w3 T. x& ~8 ?2 w5 F& N
else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
; l `" a5 o% ?5 j
% V! c% P+ b7 r3 Z, b5 u
Reg(n) <=In_value; //load input value
. e$ v8 X, t. R/ ^* V4 j
1 B8 n+ J) ]/ E" S2 J
每個clk 這些 registers array 都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.
作者:
呆頭鴨
時間:
2010-4-15 10:34 PM
回復
8#
kevin
+ v" D% @0 S1 F
7 `' x4 x( @; _6 C; H, h
9 z% w- V5 D8 Z1 w* y$ H
大大的方法真不錯~ 我怎麼沒有想到呢XD....
作者:
masonchung
時間:
2010-4-16 09:18 AM
桶米版大 真是太棒嚕
作者:
tommywgt
時間:
2010-4-19 08:39 PM
沒聲大大, 其實大家都很棒啊.
作者:
alita
時間:
2010-6-17 03:13 PM
我覺得 對於3x3的median filter
, M$ G: y* z( v, Z7 @, w
22排序 看起來是不錯的做法, 1 clock 即可做完.
歡迎光臨 Chip123 科技應用創新平台 (http://www.chip123.com.tw/)
Powered by Discuz! X3.2