請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
. r) [: f7 g3 ~4 B0 e( f0 ?有辦法達到real time輸出嗎?
還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
0 D& h, B# s9 S4 s
& b) |7 ?1 W% b* \: E$ ?, P; s假設有九個registers,每個register附帶1個comparator,
6 b, H2 {3 _4 H% I" W4 B每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
$ b4 A! F6 W/ ?% S) F+ F7 `if (Reg(n) > Input_value)

       Reg(n) <= Reg(n);                   //保持原來的值
) g: @0 I; [$ i% o/ U
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

& X" |: ]/ i  k: g% Y, u- ]       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

else if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
( P4 Q; c& Z) ]     
      Reg(n)  <=In_value;             //load input value
2 |& n: C8 G* \4 A" |) {0 s$ K         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
& M7 Z+ o/ c3 K0 L1 I1 Z; Z
: v: f- `- A5 k至於你real time輸出~不太懂你要表達意思~
  `0 g+ o* a" p3 t4 e1 N; i- j
0 b% K2 s/ q  R0 l0 S你可以把你整個架構描述完整點

這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut


$ ~' {) y( U' `4 G: o# X0 a; h  {8 Q    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
, Q# F7 p. d; B; [) ?$ l1 ~因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
6 m8 o" v* ^  E% E. l" H大概是這樣子...0.0

masonchung

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

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
* {: }. O* U+ X- ]6 R" S/ d1 I
舉個4進4出的例子:
) D1 y0 R; U) ^/ D) \0 ?input [word length] a[4];
reg [word length] b[4], c[4];
% d" O1 C0 h2 Y% @9 u; g" X9 \第一次排序
" P; h1 a* n0 q# y; P& w: e8 Qb[0]=min(a[0], a[1]);
b[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
/ [2 |$ V; J4 E第二次排序
c[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
) b4 D* d% r+ sc[3]=max(b[1], b[3]);//real maximum
第三次修正項
d[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
: ?3 B+ b# o+ _+ g7 c6 K: t: ud[2]=max(c[1], c[2]);
6 J1 j. @. a( F3 u; ~6 `d[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案
: X5 u9 k2 ^3 d7 q
- z0 D& t- u9 c. C* s這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

) t9 S9 V# ^  M5 K3 h實做的考量
1. 實做上min()跟max()應該是一起做的
# q! Q+ z' p) X9 M- ~$ a if(a>b)
0 C# q8 D7 M1 _2 K( |' W     min = b;
     max = a;
  else
  _* |2 g/ \0 V2 y+ p    min = a;
    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
# j: h5 `( S5 z' ^  `, [P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

+ T" U( w/ p$ Q& S. R+ H+ t: |4 j
8 v' V( j( P, `2 k* M回復 5# tommywgt
5 W) p4 h( V8 D3 U* T

    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
0 @# H8 Z# {% x( }8 U: s. b5 9 6
# R0 d) y2 a  w( H7 8 2
1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
: d/ P- H. k( V! a% k$ S5 6 9
; }! k0 b& W/ \2 7 8
1 3 4
這時候再將 垂直列的3筆丟入R可得到
% P% o* G! o/ A) H; h1 2 5
/ g( G  \( O) t1 x3 6 7
9 h2 Q: N4 W* ?) Z+ t0 O4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
: x7 w; _8 p3 n! u0 O. {1 t
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
& g7 d+ \4 G* i/ F' l% Q6 u1 2 4
: [4 h; A+ d" b4 S% k* W3 5 7
6 8 9
這時候可以發現
( b; K; B3 s; |% D中間的數值確實是9筆資料按大小排列後的中值(5)
, d3 K6 _0 H4 ?, h4 |, q雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
& R4 |. S8 y7 v, F) f當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
& y/ C) e! A$ U! {* }& J3 d0 F左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,
- g$ M7 K1 i* O+ g% b
, V3 L. ~1 Z9 N* Z9 {有人有更佳解嗎?

呆頭鴨

回復 8# kevin
# x: }; E- U2 j  o: T  L$ P

; k8 [1 w5 V* u$ a( ?    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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