請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
' {8 q$ e, I8 ~- y  K7 p還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
( B  R, @5 g* I
+ ^5 C' [) M. o" G2 ~. E7 D  b假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
; E! Q7 r/ g  k4 t8 dif (Reg(n) > Input_value)

       Reg(n) <= Reg(n);                   //保持原來的值

else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

# b- l& K1 h* i, q$ P+ _. N  Y       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

: M& z# m% I+ [9 R( O6 l( E! xelse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
      Reg(n)  <=In_value;             //load input value
7 x3 `% n) |1 p         
* s+ H- V8 ^# A# `3 ^" O! ?- x每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
8 t3 Y' T; c+ w, J. s0 X  z
  X: h7 t* ^1 |5 [3 I至於你real time輸出~不太懂你要表達意思~

4 ]; l2 i& ]2 x2 T: n你可以把你整個架構描述完整點
/ h* C, O3 b$ O9 V5 N% T
) L1 U; f+ M& `* J) n, `這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
# @  a- r% g- I
! k" p/ s( W2 u5 K, `# i2 L: w$ e! a
/ ^/ [% ]/ Y+ Q4 E* f    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
; X$ a4 P+ M& O+ t. c   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

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

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
$ Y4 W3 c& C; E% J* U1 A至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
; v/ ]% c# N8 o% B+ P
' V1 x8 F  f1 k' f, J舉個4進4出的例子:
input [word length] a[4];
+ B! s) W0 L9 v% r4 i6 o8 B$ Ereg [word length] b[4], c[4];
第一次排序
b[0]=min(a[0], a[1]);
# C$ N! ~8 U0 Ub[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
5 P6 [9 ?" F- X: e0 y第二次排序
c[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
* B* q: Z6 l* R/ k8 U, J1 Dc[2]=min(b[1], b[3]);
1 o8 z0 k9 a1 o: X3 l6 G, t7 Ic[3]=max(b[1], b[3]);//real maximum
/ Q. C/ a4 e) K1 Z0 n第三次修正項
d[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
7 t/ j9 e- }4 Yd[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
+ Z1 L1 v0 Y! U* ]//d[0]~d[3]就是依序小到大的答案
( \. \8 Y' o9 T# L* T* Y
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
+ e# C4 t/ S# U. V
0 i. V/ y1 N& m, r3 s實做的考量
) d0 E: f/ ~, I. U3 u+ ^1. 實做上min()跟max()應該是一起做的
, B  W. N  N' z if(a>b)
     min = b;
# P5 q0 w4 {/ M8 q  b0 J- t, X     max = a;
* e: ?8 b0 r& Z- |  else
    min = a;
    max = b;
+ X3 b$ M7 T4 B9 L2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
  s$ ^, @2 n" n3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
8 {+ L; Y% S! ?0 i; @. eP.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

回復 5# tommywgt
5 m6 f" t/ [. r" B- F
& K4 P3 u/ r: c# ^
* B+ M( V; A8 [) @    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
% y+ i4 T/ }+ t- A) ]則想像成
  l1 a' N' l  Z; X: H% b! r& u. E5 9 6
" B' W% l  l) q( j/ K: y7 8 2
- q  W% m# n4 y; B9 l& S1 3 4
  p, E! e4 m! P, V8 F, D不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
! _' {' J8 T( a& ~+ Q5 6 9
2 7 8
1 3 4
: x+ e. S9 V1 @這時候再將 垂直列的3筆丟入R可得到
, \1 p8 P7 R7 d1 R- ~4 n1 2 5
  n& ~( d- j% j, o5 _' N3 6 7
' _* o2 K, e. T, Z4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
4 g2 ?$ X6 m" f0 _3 n9 B
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
2 w2 K8 t# U" {$ y& @( ~) A- k1 2 4
3 5 7
( ?) Z2 D* s, W4 |: Y6 8 9
( k8 `6 J# y( S7 V6 D" S6 F這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
+ L- U$ p1 ~* ?' k0 }0 ?4 P+ p雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
+ a1 v( h' j% i% }+ l( Q最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
1 C( b2 U, x' P+ `左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,

$ D, D0 z( z: W" z( w) R" u有人有更佳解嗎?

呆頭鴨

回復 8# kevin

+ k1 o/ u1 u& k; ~3 I+ W; H
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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