請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
6 \8 Y3 {! }3 v0 }7 K( U9 M還起大大們提點

kevin

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

假設有九個registers,每個register附帶1個comparator,
) N# L  c# O8 q' _; a2 ]每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)
/ \2 i9 [3 F) A  b* W: L, j6 f3 ?
4 z6 Y% _6 M+ f4 J7 W% s- K5 [       Reg(n) <= Reg(n);                   //保持原來的值
7 B4 w/ ]/ f' T# @
0 R- |% K+ j1 G& v# w8 Felse if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))
! @1 R9 n$ ~( ~" {1 F
# F0 p# F/ W: T       Reg(n)  <= Reg(n-1);             //shift in 前一級的值

6 Z& z$ `& s: Y. g& q+ I# n' |, Selse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
& I9 Y( o3 {$ d* Y     
& P) `4 e, w5 N" {2 x      Reg(n)  <=In_value;             //load input value
         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
6 d9 v5 U* f& f4 m2 n% B
& I5 s2 |9 y" O8 t! j至於你real time輸出~不太懂你要表達意思~

, E% C6 }  ?/ _# U你可以把你整個架構描述完整點

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

呆頭鴨

回復 2# kokonut
" Z# O  h! ~6 f5 r$ V; K4 C
) R9 u1 p  _5 P; B/ A2 o
    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
! x; J% I6 b. v( @' i   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
大概是這樣子...0.0

masonchung

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

tommywgt

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

0 W$ t: S7 B" E  r8 w0 n  |舉個4進4出的例子:
input [word length] a[4];
+ v$ F- ^! _& E; f) _6 F- o, O" l- |reg [word length] b[4], c[4];
2 f4 W* a5 ^0 D' u# v) a第一次排序
b[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]);
第二次排序
c[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
c[2]=min(b[1], b[3]);
9 C, |. V, U: r! ic[3]=max(b[1], b[3]);//real maximum
* S$ d& w/ |, i( u' u第三次修正項
& w0 B, J2 R' X5 i8 {" md[0]=c[0]; //real minmum
; |& ~: k) K" h* g" B5 cd[1]=min(c[1], c[2]);
d[2]=max(c[1], c[2]);
d[3]=c[3];//real maximum
//d[0]~d[3]就是依序小到大的答案

這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
9 E3 S( L# |  Z/ ^* d% ]4 Q8 N
實做的考量
2 K5 ?2 ^+ K( h( j. Z$ z- {6 Z1. 實做上min()跟max()應該是一起做的
if(a>b)
     min = b;
     max = a;
  else
    min = a;
% t2 y* [6 m7 o+ F+ Y7 J    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

' I% Q$ r7 _7 W7 v
; o5 K% |1 Z: _6 j回復 5# tommywgt
( s$ M( }( y1 a+ q, r( L

    謝謝大大熱心分享
5 j6 l6 c# y; r5 N9 v我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
. {: ]5 {) v7 d) t( G; K* \0 e則想像成
" w: n3 U3 u: Z' t9 H; C5 9 6
6 y( ~6 t4 ^" Y8 E- u7 8 2
1 3 4
) ~' l0 s3 M- L7 x不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
" \3 [% O/ I0 }" g% l, y+ O7 h5 f將3段數值分別丟入R 得到
- s3 J; ^8 v& }5 6 9
2 7 8
" v. `6 X( [! H' P2 Q8 \1 3 4
這時候再將 垂直列的3筆丟入R可得到
& u( M; S' N- y3 e; t4 k7 c1 2 5
$ B0 Y4 o" ?8 C8 H  F  _3 6 7
4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)

最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
1 2 4
9 y4 n3 z# w- E$ L' c- p3 5 7
5 E4 y. H/ W' _9 u6 8 9
# _4 q  c3 b" U這時候可以發現
% J: O3 ]3 a, x) r中間的數值確實是9筆資料按大小排列後的中值(5)
+ j! V% Z0 M* N9 o雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
: V) X7 E3 K8 n# |' S0 z其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
所以在最大的亂度中, 8-1=7次應是最多的運算了,
4 f2 v2 O  M3 D% R2 j7 g: o6 y
' \' w0 [5 A1 |6 a, r! ?0 }有人有更佳解嗎?

呆頭鴨

回復 8# kevin

$ S/ |0 x4 L! p4 a- e! o" X0 a
( |8 g/ T6 I4 [" i( h3 F$ L  D. ]% l    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

我覺得 對於3x3的median filter
, ?; a& D  a; q, W22排序 看起來是不錯的做法, 1 clock 即可做完.