請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
- g7 |: m3 e! }: T$ f, k我有9筆資料 同時輸入 A1~A9
6 u  E% q9 d# s/ k2 B0 e* k要如何設計才能達到按照數值大小排序輸出X1~X9
8 Z' H- H9 n- A1 q* \/ F* m7 v2 s有辦法達到real time輸出嗎?
5 \% q* I: x% X5 Q0 N還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.

假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

+ r/ s2 ^& o& y& ^0 D. M7 {       Reg(n) <= Reg(n);                   //保持原來的值
( P2 W+ O$ D) M5 E( h2 y
3 V& o8 C8 M5 o. M9 L! N! s6 y/ uelse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
# E& Q$ C1 V& |
       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

& w2 P' G1 x. M8 }0 yelse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
' y* y' e2 F2 f     
      Reg(n)  <=In_value;             //load input value
" Y: k6 z6 K1 e  H# f8 r# L         
& J  s" e1 X1 L9 P; G( q# C每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~

7 G  p& X( H/ f) x: j至於你real time輸出~不太懂你要表達意思~
  t, j2 D+ ^% l/ s( {
你可以把你整個架構描述完整點

/ p8 @: `# m* J0 z% P" g' }. f/ \這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut
+ }0 Z/ y0 r3 J% P7 ?

    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
8 f% H6 N( q/ a- Y   所以要將畫面中9個數值做排序後輸出中間的數值
/ X  N8 ~7 j" O因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
0 @. S$ i8 z% S+ I$ a$ @大概是這樣子...0.0

masonchung

首先看排序方法
8 l9 S- x2 ~5 S- _, w6 I) E  l再來看比較器有幾層,還有比較器的寬度

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
2 S) K% H* r. x! Q& q至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
6 w$ \' ]) u$ x5 i! |4 D
& ^- N, y& {8 \! W% n! s% t舉個4進4出的例子:
9 x, O" l3 ]0 o5 [/ v' u) ?input [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
b[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
: m( @5 t2 J9 r- J1 ]$ ub[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
7 V0 |* X6 K8 a7 ?' O; g第二次排序
c[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
. Z6 O. |+ B% y5 S9 C$ Gc[3]=max(b[1], b[3]);//real maximum
4 \6 a0 ^0 \' [: A第三次修正項
; q4 b" x$ ^7 J  h! H+ qd[0]=c[0]; //real minmum
' s$ O% u2 p) ]# Y2 V5 {d[1]=min(c[1], c[2]);
9 |/ T% \( Z0 V9 Wd[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案

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

6 `: A% [% h/ g& H$ J4 M9 k實做的考量
1. 實做上min()跟max()應該是一起做的
if(a>b)
3 R' o+ V6 e7 ?& P9 `# s* f     min = b;
* |+ K$ c$ J/ [8 m1 V- i     max = a;
" b2 `- X) p% \$ Q" `& C  else
    min = a;
) k! R# y0 A3 Y- _* p& b6 _2 ?    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

回復 5# tommywgt
( K4 d7 ?+ ~; I
/ S! D; i9 h( N  b5 O
    謝謝大大熱心分享
$ v+ M3 }1 z  E7 I4 H我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
5 9 6
' i( T  n& O* q6 l3 `7 8 2
& u1 A: U5 W' f& C9 P/ c4 @* |1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
% ]% g- ]+ x) q( R將3段數值分別丟入R 得到
3 f* P) Y# V& S% n" v5 6 9
' I3 {5 z. j1 v2 7 8
5 O' `: S( H! O1 3 4
這時候再將 垂直列的3筆丟入R可得到
1 2 5
3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
# ^/ f5 A$ _, B, B( m3 N  b& f% ^
# g; e: s0 {; i9 M最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
' M7 h' ^* i5 t9 ~" K1 p1 z6 8 9
* `2 j6 [2 Y8 G: J這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
$ V8 s* U/ z6 D: ^& E8 K8 ^當亂度能包含所有的項時, 答案一定是對的
6 J, Q0 d  U* U7 I所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
5 e1 W2 t7 s. Y6 G1 ^8 D所以在最大的亂度中, 8-1=7次應是最多的運算了,
* z3 s0 x0 C1 ]' V& M& l, c
# O$ G2 o. z7 c$ w有人有更佳解嗎?

呆頭鴨

回復 8# kevin


' U7 D& z! x. o+ ^1 d    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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