Chip123 科技應用創新平台
標題:
請問~Verilog 設計資料排序~
[打印本頁]
作者:
呆頭鴨
時間:
2010-3-31 10:43 PM
標題:
請問~Verilog 設計資料排序~
請問大大們~
1 D" [/ ^$ L" ~( H( P2 t9 d
我有9筆資料 同時輸入 A1~A9
" L8 Z1 Y; b6 ]' ~
要如何設計才能達到按照數值大小排序輸出X1~X9
5 _7 \2 B& ~) H- l
有辦法達到real time輸出嗎?
% r, x; [9 {: }- N- \ Q# b6 y
還起大大們提點
作者:
kokonut
時間:
2010-4-5 04:30 PM
你把A1~A9吃進來後~要先排序處理吧~
* U6 _( g9 N4 J! G6 A: V }2 N: ~% @
5 B+ A/ B, O* M; `( Q/ {" H
至於你real time輸出~不太懂你要表達意思~
* N5 d( C* O- F$ V; f
8 u# B/ |5 n6 L6 t: t* t4 ]" \
你可以把你整個架構描述完整點
( ^ j1 j9 [ s/ G9 i
* j& r1 {' ~" [- H$ B/ b
這樣比較好給意見~!!!
作者:
呆頭鴨
時間:
2010-4-5 09:41 PM
回復
2#
kokonut
. R% K; l: M9 O! }8 Z" P& ]. Z5 }
4 x7 r2 C' a) r8 f1 v- p
+ w! J+ Q* a" \6 d
是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
% W2 r0 I& q: y! _; ^9 ?
所以要將畫面中9個數值做排序後輸出中間的數值
. h& M2 y3 _0 a6 f
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
7 E. x/ U, J4 K/ S
大概是這樣子...0.0
作者:
masonchung
時間:
2010-4-6 02:12 PM
首先看排序方法
: Z" m1 i0 K0 o
再來看比較器有幾層,還有比較器的寬度
作者:
tommywgt
時間:
2010-4-11 03:41 PM
對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
0 K( z4 @9 Y# [9 G
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
, k( Z4 J% I1 p! Z5 k- U7 E" F
% b; g& G+ p) i+ g
舉個4進4出的例子:
( p8 O! @7 m5 I2 Z& q4 |* \( T
input [word length] a[4];
% r+ ^7 s' F2 R( e' u
reg [word length] b[4], c[4];
4 z. E5 P* o4 F; O- m
第一次排序
6 P: D3 T6 [/ u5 K. v
b[0]=min(a[0], a[1]);
4 W7 n7 L( B" U4 F) j
b[1]=max(a[0], a[1]);
9 D0 Z6 J4 y, {$ O
b[2]=min(a[2], a[3]);
( x! s. c& v' _7 [% \0 \: y, [
b[3]=max(a[2], a[3]);
q% i$ @3 d1 O- S
第二次排序
+ q! j _+ E7 A d' Q0 w. }
c[0]=min(b[0], b[2]); //real minmum
: ]( z' L1 Y: n: {1 Y
c[1]=max(b[0], b[2]);
9 x4 w R# D/ w% g" _1 J
c[2]=min(b[1], b[3]);
2 s, `+ d2 v$ L% |# e
c[3]=max(b[1], b[3]);//real maximum
) |: e8 o( S/ l. G$ B; V7 p
第三次修正項
4 h8 P B5 B. B- ]9 B L* W- m5 t, @& D
d[0]=c[0]; //real minmum
% A4 ~3 M; S/ r( f
d[1]=min(c[1], c[2]);
) M) C5 c6 u7 Q" u
d[2]=max(c[1], c[2]);
$ E; L/ ]5 e% J) g
d[3]=c[3];//real maximum
8 D( `) f3 V- M$ o# ~; S9 B/ b
//d[0]~d[3]就是依序小到大的答案
$ O$ s8 l6 B2 b5 ^' g3 j* G
/ @8 h r2 `4 N0 q
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
# u: ^. a" E) s
3 B$ @9 ~/ h' ^0 C
實做的考量
; o: D% _, x8 c# C
1. 實做上min()跟max()應該是一起做的
, D; y! ?( R$ K8 b. v K
if(a>b)
( E. R" e# d/ C7 `, \! Y# r; T# K
min = b;
+ w1 M( Y# \6 T- E
max = a;
6 q$ _2 d9 x$ Q1 k: M; r: T
else
3 S$ K4 G* C) A2 I$ P6 e( L
min = a;
0 O. Q) t) Z; P0 ~. H [7 E
max = b;
}9 y6 i0 S. K2 E
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
' S) L# v, M, D1 v3 ^$ e" y+ D
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
* ~0 A6 ]/ q" b" U% [
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD
作者:
呆頭鴨
時間:
2010-4-12 09:05 PM
本帖最後由 呆頭鴨 於 2010-4-12 09:06 PM 編輯
3 H" p s, M* Z$ T) q1 _. R6 k
- T6 V! @0 l9 ?& r( M5 e; U1 d
回復
5#
tommywgt
! J3 y) g$ X" h+ ~
: e0 D, q+ V$ ]& K* O
/ J. H) f7 V+ u6 o# X
謝謝大大熱心分享
0 V* g1 H( S0 b, l* z
我目前的做法是這樣的,提出來給大家研究討論一下.....
& y' Q5 a. P6 b
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
$ e/ @& M/ n# r4 x
則想像成
( d) \3 p; E. q- |6 X- _
5 9 6
* @3 ]/ v D! s$ J# v. `$ P
7 8 2
1 z$ M) O( K' r* u& ?
1 3 4
J2 y/ [' i' L$ U
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
: R/ n2 n/ \" |* }3 F( A
將3段數值分別丟入R 得到
: {' t, R1 o2 k9 P+ Y
5 6 9
- D3 ^7 ]: B. E& E# {) c+ y# d
2 7 8
6 }4 L. e4 \8 i4 R1 ]
1 3 4
z5 N9 z. a1 v; M7 Z. s3 V3 K
這時候再將 垂直列的3筆丟入R可得到
/ K6 D/ q K" B( t
1 2 5
: m. L& M0 e4 s" G2 I* ~7 w1 e( W. q( A
3 6 7
2 T6 x. u; \: T& [3 U5 u6 B
4 8 9 (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
! K, Y$ F' T+ \. Q
- h3 }* c9 K: M6 C
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
2 I% F) `9 ]# I, w2 K1 E( b. j* R6 k
1 2 4
6 r1 x/ ^" w; z2 f% `
3 5 7
( {( }7 f$ R7 D' ?2 l3 R6 t
6 8 9
" `% r1 w: V) O g0 N# G
這時候可以發現
1 {: o4 y4 U9 S6 X$ I
中間的數值確實是9筆資料按大小排列後的中值(5)
) `' s4 N$ M+ h3 n* U5 T, a
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...
作者:
tommywgt
時間:
2010-4-12 10:31 PM
啪啪啪
7 I6 d5 z% u0 m" _
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
. n& U- w8 W& ~# x
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
9 j* b) _0 Y: q& Q. `& S9 I; N
當亂度能包含所有的項時, 答案一定是對的
# B8 j- G. z; U0 b' @' L8 A" k r3 L
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
' R7 E$ g1 k9 E% }
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
: R2 m& ^" f, G4 q9 S9 s) o! ?
所以在最大的亂度中, 8-1=7次應是最多的運算了,
' \$ ^7 f1 \0 `3 Y
5 i4 B' m' `5 M9 w
有人有更佳解嗎?
作者:
kevin
時間:
2010-4-15 07:48 PM
資料量少的話,用插入排序法則也不錯.
7 t. u& `0 R7 K( `3 }% r+ d
[attach]9340[/attach]
W9 e+ O0 a: V7 j: ]/ M
假設有九個registers,每個register附帶1個comparator,
( ], ^5 z) ~/ [& n5 c
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
% y$ C: j3 N& y+ z- T/ _" M
if (Reg(n) > Input_value)
3 \6 h0 F( G- v
/ H% F$ i5 D! i( C- a9 p @, L
Reg(n) <= Reg(n); //保持原來的值
' _# J! R b9 z5 f. k+ O( R- W
0 f9 i) x9 w3 ~5 c4 ]3 N
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
$ o" v) A6 j% `2 ]; }- y% i
/ U, L* e8 m' P9 }) T% s
Reg(n) <= Reg(n-1); //shift in 前一級的值
: a" g8 s# X% K7 c
" N, U0 A4 f* O$ I+ T
else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
/ A# R+ k; y. j: |7 A/ `
_9 ?, c* G% J+ ? \ Y! L
Reg(n) <=In_value; //load input value
% Z0 A/ {1 H( e5 L8 v
2 m$ P( I# \3 I- a
每個clk 這些 registers array 都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.
作者:
呆頭鴨
時間:
2010-4-15 10:34 PM
回復
8#
kevin
+ S" f* R) t7 v) i9 B) b, X' z
" O" R5 p4 h$ X/ j) D
1 ]; z+ k( ~, r$ x. {5 z
大大的方法真不錯~ 我怎麼沒有想到呢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
8 P' M, c% t! A4 i* X- m3 m* A, s
22排序 看起來是不錯的做法, 1 clock 即可做完.
歡迎光臨 Chip123 科技應用創新平台 (http://free.vireal.world/chip123_website/innoingbbs/)
Powered by Discuz! X3.2