請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
+ A$ `0 J* R3 ?% i有辦法達到real time輸出嗎?
還起大大們提點

kevin

資料量少的話,用插入排序法則也不錯.
3 ^: P6 t" O6 A5 h
2 X2 q9 g, w/ Y. \假設有九個registers,每個register附帶1個comparator,
每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)
- b; P) M" l, W6 D- J% g# K9 l- |
       Reg(n) <= Reg(n);                   //保持原來的值

% F: H5 J& r, M  c4 S5 oelse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

       Reg(n)  <= Reg(n-1);             //shift in 前一級的值
# w) @+ |# e1 L: v" D2 O
: x' r- X5 H" }( @8 y$ Felse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
     
      Reg(n)  <=In_value;             //load input value
         
8 [5 h) J% o9 v$ w7 z每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

alita

我覺得 對於3x3的median filter
5 q$ P1 @( m8 V% y1 S! c2 I5 F22排序 看起來是不錯的做法, 1 clock 即可做完.

tommywgt

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

masonchung

桶米版大 真是太棒嚕

呆頭鴨

回復 8# kevin

# S1 \) H3 Q3 L
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

tommywgt

啪啪啪
! A, b" x) S2 }5 ?3 ^' _4 k其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
7 B& j5 k' ~5 s" a最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
9 q* a. D- m/ S" h8 E當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
. L& B3 z$ _2 f0 [; D5 z! R. [左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,

9 w9 N: E6 ?0 \8 v有人有更佳解嗎?

呆頭鴨

2 v5 m5 r" u3 y; D
8 R% k  \) N# }! n- ^" N2 C5 K5 i回復 5# tommywgt
5 {5 a4 m7 v/ T" Q: c

    謝謝大大熱心分享
4 Y: `/ A4 E+ T6 W  y* }我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
則想像成
4 z& ~! u: k' A7 f5 9 6
, p. v9 h; E! y7 8 2
4 s5 ?/ q1 s1 B- z) ~4 Q. h" I/ G9 l1 3 4
% C) v& r  v* ^5 [# K3 V3 ]! H2 n不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
5 6 9
- n! T7 @' \. b9 Q5 l+ T7 t5 }& L2 7 8
% a9 {* Y; y7 ]: }1 3 4
/ R* H+ C; i4 c  U* y: L5 U這時候再將 垂直列的3筆丟入R可得到
1 2 5
3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
8 [1 ]) z: s$ z1 Q' j; R. L8 A- w9 C
最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
3 5 7
6 8 9
, v9 S5 E' g* S( R8 O這時候可以發現
  w  b9 _1 a5 s6 i5 R中間的數值確實是9筆資料按大小排列後的中值(5)
9 k# N1 I6 W5 a% T: e( `雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

對於3x3的median filter你可以考慮22排序(這是我之前自己用的方法), 只要多排幾次就有答案
9 w) s9 \8 ]: ?% ~至於real time本來就不是問題, 除非你要在FPGA跑超過300MHz以上的clock rate (就算要跑更高速也是可以的, 只要從演算法著手修改就行了), 用ASIC的話速度就不是重點了.
- m: b4 V5 {) d' v) ~: l
舉個4進4出的例子:
input [word length] a[4];
( |4 \6 V8 p, f# v2 Z5 I4 Freg [word length] b[4], c[4];
第一次排序
b[0]=min(a[0], a[1]);
  `% Q" A0 i% Z3 Q. x3 _0 a: \# zb[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
b[3]=max(a[2], a[3]);
5 D, i; d* e; L1 r4 m. C/ L$ [第二次排序
0 ?& G$ K8 n- p) lc[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
第三次修正項
d[0]=c[0]; //real minmum
d[1]=min(c[1], c[2]);
' w# y5 `6 R5 }0 v7 i( sd[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
$ t2 R9 _4 z( @: h; u//d[0]~d[3]就是依序小到大的答案
' j3 U( J+ V, s, k3 V- r5 G( ~8 ~
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)

. R. a! r% j8 d2 u% G1 S4 F' o實做的考量
9 W) B3 U" `. m' S9 N: U; B9 x. |1. 實做上min()跟max()應該是一起做的
& o1 Z" c! K7 q! G+ z& K if(a>b)
     min = b;
     max = a;
  else
    min = a;
    max = b;
' y" S$ K" N  h4 ~' F' Y2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

masonchung

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

呆頭鴨

回復 2# kokonut
& D7 [" a/ B% k8 o8 G% J
7 t8 x) Z9 z. K8 z
    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
. x# f% K8 ?# t6 H/ i大概是這樣子...0.0

kokonut

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

3 s/ ]# j( r" q* V9 h至於你real time輸出~不太懂你要表達意思~
1 Z( e% U5 k- d) g* Z- K+ B
) [( D- n( H; y' ]你可以把你整個架構描述完整點
8 y! K( {2 Q( i; Q& e
$ ^  J) ^! R3 u: y! L1 q這樣比較好給意見~!!!