請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
# n" M1 N- X1 e& B, b' E3 j  ]要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
5 q+ c6 ]0 `& q
假設有九個registers,每個register附帶1個comparator,
2 l# i6 l% Z. e: _3 b) p每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

) V* @, x4 q' B8 Y% W% R8 Q       Reg(n) <= Reg(n);                   //保持原來的值
4 P% e& e, L3 B" p
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

4 }% _+ W/ }* a1 {else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
! ]1 V9 u" U! a3 i; i2 z     
0 j# M. m, J6 }: w( f3 `: c' s      Reg(n)  <=In_value;             //load input value
         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
  c0 v' v7 c+ P
至於你real time輸出~不太懂你要表達意思~
+ D( ~; f+ N% y: T
你可以把你整個架構描述完整點

' o. k9 n; Q8 t& G5 S這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut

6 t. `! m7 O: e/ _7 V2 \* \
* Y) k4 j7 Q0 B# f/ U+ a    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
6 G1 _1 M8 z% a. H. {, s0 v   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

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

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.

( o) t: W" f$ q7 r- m1 N" D舉個4進4出的例子:
input [word length] a[4];
& }- P7 `: B- `% D9 ureg [word length] b[4], c[4];
. B2 u& T* E/ H8 ], i1 D第一次排序
b[0]=min(a[0], a[1]);
9 C& N% d; f  j' C4 q' N* ub[1]=max(a[0], a[1]);
* \5 F) t* d# X+ ]1 Hb[2]=min(a[2], a[3]);
' i+ O2 O; P( V- lb[3]=max(a[2], a[3]);
" W' {: ~4 x: Q8 ]/ s$ A  L8 x6 o第二次排序
, P8 u- f, r/ w. @c[0]=min(b[0], b[2]); //real minmum
$ N6 {" B9 A8 x) T% \c[1]=max(b[0], b[2]);
! r( K" O# Q4 b, c' |- m/ [6 X+ mc[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
第三次修正項
0 r8 }) ^% m7 B' r2 ?d[0]=c[0]; //real minmum
/ V5 f! X7 x& l7 }. J! bd[1]=min(c[1], c[2]);
3 O9 T' F; X6 U6 o' R( {d[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
+ @% G3 Y' q+ q3 \. }$ C- x  P* N//d[0]~d[3]就是依序小到大的答案
; I9 i2 v- x1 i
1 M1 {% m+ F9 F/ S7 ^8 z) _這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

5 M3 U3 L# p) }: t' t實做的考量
1. 實做上min()跟max()應該是一起做的
/ z# {* q8 s) B* W if(a>b)
     min = b;
! b5 w9 C! ]& p! ^; m: u6 `! W     max = a;
  else
    min = a;
    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

- d' }. P' j; ~5 H7 ]7 ^
0 t# f3 z- T4 f回復 5# tommywgt
: o6 U: W* `% Q1 B

: c5 F' W: I% \6 L" D" D* X    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
3 s- H6 R9 J  b2 _我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
1 S# U+ o; C+ |# B' \4 ~5 9 6
7 8 2
/ G7 z4 t' C* f2 X- `1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
+ B' i& a5 z' q2 y8 y將3段數值分別丟入R 得到
2 x' K) K9 n/ y  k  T+ J% |7 C5 6 9
2 7 8
' O, t. f; F  x2 J: }3 ?1 3 4
這時候再將 垂直列的3筆丟入R可得到
1 2 5
4 z6 u0 W5 L0 v: r" u3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
9 d+ C8 q5 z* w* d8 W6 8 9
  J8 d1 F- g* I5 T這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
6 O  y/ q  V2 f6 ]# p, e雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
: S4 Z1 s; B' q. s; k6 c最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
- X* G: O: @- y8 G2 M& F, D左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,

3 i+ E, `* A: ^' Q: v9 K有人有更佳解嗎?

呆頭鴨

回復 8# kevin

& i- C9 G& m  S# x3 w( Z9 J
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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