Chip123 科技應用創新平台
標題:
請問~Verilog 設計資料排序~
[打印本頁]
作者:
呆頭鴨
時間:
2010-3-31 10:43 PM
標題:
請問~Verilog 設計資料排序~
請問大大們~
" p6 P$ v; Y9 K6 P9 b, U
我有9筆資料 同時輸入 A1~A9
( V% O* X5 H v, U. c
要如何設計才能達到按照數值大小排序輸出X1~X9
2 M* o. u4 {9 J/ G+ a
有辦法達到real time輸出嗎?
2 _ |& p. V. [( C( P0 q4 |; B7 U
還起大大們提點
作者:
kokonut
時間:
2010-4-5 04:30 PM
你把A1~A9吃進來後~要先排序處理吧~
( o* } t% ~3 L9 p, P4 i
6 Y. p3 p; t5 h2 n
至於你real time輸出~不太懂你要表達意思~
. x1 g* K. t9 [' ~
3 r2 \% z H- [' K9 S
你可以把你整個架構描述完整點
5 O- {3 k( i* n7 v$ o
/ k. j4 w# x1 D( E! L
這樣比較好給意見~!!!
作者:
呆頭鴨
時間:
2010-4-5 09:41 PM
回復
2#
kokonut
3 O# N1 A7 _/ {0 J: T: M
5 h0 c5 a5 q3 S7 {
) H# v! P7 I0 @0 {
是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
+ r* f: c* E4 Z; ? R
所以要將畫面中9個數值做排序後輸出中間的數值
( @1 P( n* ?6 n$ v
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
: U0 T8 Z |! o) T2 @
大概是這樣子...0.0
作者:
masonchung
時間:
2010-4-6 02:12 PM
首先看排序方法
$ M( J, m! [* G( ?6 } t
再來看比較器有幾層,還有比較器的寬度
作者:
tommywgt
時間:
2010-4-11 03:41 PM
對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
/ Z1 Q$ M! A5 w" O8 I. |
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
' d* w1 @9 r0 V" w- Z
7 O0 G" V& Q4 _5 y: e; l) ^; q
舉個4進4出的例子:
; F% t" v& ~1 {# [$ ]$ n
input [word length] a[4];
$ V* P$ V2 T) }, S+ J2 j/ g
reg [word length] b[4], c[4];
3 M+ h8 e3 u5 P! C* y# C$ ^" a( }) o
第一次排序
* T5 B- ]% o2 K4 C' s
b[0]=min(a[0], a[1]);
4 Y. I" W: o" u$ |/ w n; s! n
b[1]=max(a[0], a[1]);
1 e& v& t) S: ^+ [$ M- x: b
b[2]=min(a[2], a[3]);
/ p7 p0 E! q0 u& M# H
b[3]=max(a[2], a[3]);
2 z% l) L' S8 m. ?
第二次排序
+ w) X. }: g9 v; s+ O& M3 b8 s
c[0]=min(b[0], b[2]); //real minmum
1 u/ B* J4 o2 U# L* R$ }
c[1]=max(b[0], b[2]);
/ g( y% o2 V: U! H9 _
c[2]=min(b[1], b[3]);
- B- D7 @) s" ~3 n0 p' O" D
c[3]=max(b[1], b[3]);//real maximum
( Y3 ?! ~2 z) R7 I0 B6 G5 _: {
第三次修正項
* Z6 Q# |) n! Y+ V
d[0]=c[0]; //real minmum
9 c q' s! l5 o1 ^ h3 p
d[1]=min(c[1], c[2]);
/ A5 a' u7 n) w# d, ^) d
d[2]=max(c[1], c[2]);
1 R( G0 ~4 V" Y, l$ ^
d[3]=c[3];//real maximum
# ~) E8 r- i' S. m; l
//d[0]~d[3]就是依序小到大的答案
- Y& U0 K) F/ M' i% |1 m
8 T- |2 O' P1 V& x5 |3 H
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
8 ]9 a( Z2 d3 K% e- `+ @# B% c
+ n. j; R( Q2 s; D
實做的考量
) F+ x! s, Y) l
1. 實做上min()跟max()應該是一起做的
7 L; s0 w s. L' z6 }
if(a>b)
/ y) q9 i! d# M( [& x) u
min = b;
5 u5 C5 @% S, o4 v9 K
max = a;
; _& y; a% Q- _' p! l
else
# n7 Y3 N/ e8 T
min = a;
+ V# V0 j" f0 j$ c$ a6 _
max = b;
9 t. G: A$ z. ~) o
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
7 ^9 a- ?" d9 l' t3 r
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
/ t v) L9 x7 d7 I9 Y
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD
作者:
呆頭鴨
時間:
2010-4-12 09:05 PM
本帖最後由 呆頭鴨 於 2010-4-12 09:06 PM 編輯
2 M7 l: j7 b( a( }0 e8 ?( N
/ L( O z0 Z* @3 L) D
回復
5#
tommywgt
4 m& [. n' D' U2 W; W, N6 X) J% c
* w) U6 }+ v" E2 _7 }8 y1 b
, u! R _3 ] z- d. O
謝謝大大熱心分享
2 i* y; p; X1 F2 ^$ n
我目前的做法是這樣的,提出來給大家研究討論一下.....
# x7 w4 h8 a: [+ V: {# i
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
G6 {. u; y! b1 |# y; w# K" L& p
則想像成
/ j; D1 Z, t# G. s7 c% |
5 9 6
2 H' ^5 s+ p3 b2 z
7 8 2
! |6 z: z7 Y4 B& F! A; i. ]3 f3 ^
1 3 4
9 u5 |) N! h0 {' @, H
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
. M+ L9 w" A8 i+ C2 n& J
將3段數值分別丟入R 得到
! I" o/ N( l. a( O* P* a M
5 6 9
& @/ F+ |7 L( D# ]1 z: F& {
2 7 8
% C2 i% p7 Q# s8 H" a& ]/ E {/ k
1 3 4
. l; P3 G h+ j9 O1 m" {& @
這時候再將 垂直列的3筆丟入R可得到
! `9 ~+ e* u) q* w
1 2 5
/ ]5 i# k) n( a
3 6 7
, Y. S/ H' `! n8 v) S8 G8 Y; A+ X
4 8 9 (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
s2 `2 H' ]6 \, T7 c( e
. y0 w5 O, `8 e- p! ~, V" k
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
& W: h% q+ s. s+ N" q/ D; y$ a
1 2 4
6 T' T7 T! Z2 Q2 r+ D
3 5 7
' w% a2 n3 l* l, g& G
6 8 9
' M7 [ `! v0 a: \9 ~7 F
這時候可以發現
! ~% ^5 n3 _5 a) i
中間的數值確實是9筆資料按大小排列後的中值(5)
, S7 D8 f, b4 x+ k4 S `$ ^9 c5 c
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...
作者:
tommywgt
時間:
2010-4-12 10:31 PM
啪啪啪
) y6 I# F3 Y. ]1 X$ ^% J% v
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
4 g# `5 J* L3 Z I( B
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
& P% @/ v# f# d( ]* Y& C
當亂度能包含所有的項時, 答案一定是對的
5 x" |) W" l7 `9 \# ?- Y. }* e/ C
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
n' F N- H. A9 P' p* x" {
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
; s% _# Q1 I' ?
所以在最大的亂度中, 8-1=7次應是最多的運算了,
: A' r7 `4 }' G: c& {2 O
! D+ h1 G& s2 p3 y: v( A; W
有人有更佳解嗎?
作者:
kevin
時間:
2010-4-15 07:48 PM
資料量少的話,用插入排序法則也不錯.
5 F0 J3 ~9 {4 B
[attach]9340[/attach]
' v1 h$ w$ B7 i9 K# Q6 L; }& T
假設有九個registers,每個register附帶1個comparator,
0 T3 m2 o$ {5 W5 [( z1 y
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
" b+ |$ b8 ~1 b" n5 @
if (Reg(n) > Input_value)
) |) W- K3 I" g4 Z Q
1 M- @7 h; h, D& ?
Reg(n) <= Reg(n); //保持原來的值
+ M. Z; ~/ ?! k
+ M- e* r7 o! ]
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
" `4 Y+ j, p# J6 z. `( y- Z+ z4 R' q
2 r, q: l2 [) l" b; Z
Reg(n) <= Reg(n-1); //shift in 前一級的值
4 x" @% ~% N5 l' M5 U
2 H3 |, D6 C. Z* h o6 T8 `) h
else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
/ d( g. N' I- `$ u
% ~4 X% p W* `
Reg(n) <=In_value; //load input value
! v& q& p! @; V' a& r7 [) D
. \4 y8 z3 x# a! p- p7 u
每個clk 這些 registers array 都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.
作者:
呆頭鴨
時間:
2010-4-15 10:34 PM
回復
8#
kevin
2 Y) H7 T J, Q& o* \% {) t
# Y1 }" w1 o7 G
2 h" g# |6 g/ @+ f0 w
大大的方法真不錯~ 我怎麼沒有想到呢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
+ ]: F V% ?; Q/ w/ a2 B
22排序 看起來是不錯的做法, 1 clock 即可做完.
歡迎光臨 Chip123 科技應用創新平台 (http://www.chip123.com/)
Powered by Discuz! X3.2