請問~Verilog 設計資料排序~

呆頭鴨

請問大大們~
我有9筆資料 同時輸入 A1~A9
% q8 C1 r- f- `) u要如何設計才能達到按照數值大小排序輸出X1~X9
有辦法達到real time輸出嗎?
4 }$ N+ R8 a: a" r+ T5 u! _還起大大們提點

kevin

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

假設有九個registers,每個register附帶1個comparator,
" ~  g: K4 o; H$ I每個clk有一筆data input,每個register會比較input data 與 自己register 的值. 假設第n個register 為 Reg_n
if (Reg(n) > Input_value)

       Reg(n) <= Reg(n);                   //保持原來的值
2 U0 Z& X# k! |. r+ b! ]/ n) x
else if ((Reg(n)<= In_value)&&( Reg(n-1)<= In_value))

       Reg(n)  <= Reg(n-1);             //shift in 前一級的值
9 q7 t+ \& Y( g7 d. ?
- b2 `3 a3 g( l, r1 velse if ((Reg(n)<=In_value)&&( Reg(n-1)> In_value))
  y- d% ^" r) h  f7 R# S     
      Reg(n)  <=In_value;             //load input value
         
每個clk 這些 registers array  都是排序好. 一直到最後的input結束,直接輸出第 Reg(5)即是 median value,再 reset all registers.

kokonut

你把A1~A9吃進來後~要先排序處理吧~
# ^+ A. [9 s/ ~: E1 D( Z
# }! Z" K4 m- n) b4 R+ I/ {0 w" s" \至於你real time輸出~不太懂你要表達意思~

( ^9 p4 k" T/ i% C你可以把你整個架構描述完整點
& D  `; q) Z" B
這樣比較好給意見~!!!

呆頭鴨

回復 2# kokonut

+ L, |( V6 T, E- ~
    是這樣的~我前面是影像讀進來的資料~我要做一個3*3遮罩的 中值濾波器
- ^: n1 z( P6 m% z. B9 b/ u   所以要將畫面中9個數值做排序後輸出中間的數值
因為資料是不斷的進來(暫不考慮使用RAM處理),所以輸出中值的時間只允許1個CLK內完成
- H: I  r6 W9 f) s) @4 n大概是這樣子...0.0

masonchung

首先看排序方法
- o) T7 i' c, Z0 k; m/ L3 }再來看比較器有幾層,還有比較器的寬度

tommywgt

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

1 T6 H- J# H' b( [/ J舉個4進4出的例子:
input [word length] a[4];
reg [word length] b[4], c[4];
第一次排序
2 N3 h3 \  j: }: f3 Tb[0]=min(a[0], a[1]);
/ {- V% H+ ^! Z' g) X$ v5 z+ c2 tb[1]=max(a[0], a[1]);
b[2]=min(a[2], a[3]);
' d/ W0 V8 X, X0 p* p1 q: i6 d" _b[3]=max(a[2], a[3]);
/ X5 }; Q  ?. h6 A5 V第二次排序
c[0]=min(b[0], b[2]); //real minmum
c[1]=max(b[0], b[2]);
. H+ Z2 H' e  xc[2]=min(b[1], b[3]);
c[3]=max(b[1], b[3]);//real maximum
1 u8 p2 e! c& z5 r' J; r& s: T第三次修正項
d[0]=c[0]; //real minmum
) B- J7 G; t7 y6 p4 u) |d[1]=min(c[1], c[2]);
+ K9 g4 P# P* t  C8 Ad[2]=max(c[1], c[2]);
1 H1 f6 g/ `4 d* Ed[3]=c[3];//real maximum
' Z6 K" O( j7 p  E$ s% W  I//d[0]~d[3]就是依序小到大的答案
7 @& z3 ~4 S. r( s
這個方法對你只有拋磚引玉的效果 (照做當然也會成功), 對於median filter, 建議你修改一下這個方法, 並且省略很多不需要的運算 (因為你只需要留下中間值, 其他的值並不需要)
! n. Y/ w1 m" W" U2 \/ s& e$ Z
實做的考量
' t7 i, u; K! Y" K& F3 |1. 實做上min()跟max()應該是一起做的
if(a>b)
8 N: s. K* V6 P2 ~4 R: x     min = b;
     max = a;
1 n$ y. u9 \8 t( n  [5 Y  else
5 |2 S/ j; W3 O$ o) S" R5 q5 p4 D# x    min = a;
4 r! s: o8 d6 v# M% X    max = b;
2. 另外實做時, 考慮硬體的複雜度及執行的速度, 適度的修改一定有其必要性.
: N5 e  R4 h0 ]# H3. 如果要做adaptive median filter的話, 除了中間值以外要多留下幾個項.
P.S. 用我的方法寫conference paper記得要掛我名字哦...XD

呆頭鴨

* b6 y+ E- k( e; A8 j2 V1 l回復 5# tommywgt
& \& s& o' d( c: D: e! S* |

    謝謝大大熱心分享
我目前的做法是這樣的,提出來給大家研究討論一下.....
我將輸入的9筆資料 拆成3段來做 假設輸入是1~9 順序是 5 9 6 7 8 2 1 3 4
! x0 ?7 N4 s4 }3 G; H+ p* P; \/ _4 l則想像成
5 9 6
7 8 2
6 a1 g- \4 s8 u- Y) c; a1 3 4
不過要先完成一個輸入 3筆資料 可以將之按大小排列輸出的小程式,這邊簡稱R
將3段數值分別丟入R 得到
5 6 9
2 7 8
1 3 4
這時候再將 垂直列的3筆丟入R可得到
* g* m. p' O6 Z% ^1 2 5
3 6 7
- s8 }5 [3 u1 t6 D2 R4 8 9  (這邊為了方便辨識 所以排橫的 值的橫的沒差@@)
. U8 V- j. ~, j$ d; y7 V: G4 F" I
! q  L" [3 k5 P# K8 Y3 Y9 t1 ^+ T4 s最後一步驟~將右上至左下的3筆資料丟入R 重新排列後再輸出~可得到
; z/ [& z; o. C# M$ {. p% {1 2 4
; h# t7 `9 b( R6 Z  S3 5 7
" W2 Z9 P1 h1 j3 R. T& b/ w7 j: l6 8 9
) U% ?' r" {6 B- D3 L" V* z% a" @這時候可以發現
中間的數值確實是9筆資料按大小排列後的中值(5)
雖然其於8筆資料未必有造大小排列,不過目前測 中值的部份還沒算到有問題的...

tommywgt

啪啪啪
- C& x* }/ c1 Z4 h其實你的想法已經跟我的想法是一樣的了, 我想已經你知道我一開始講的那個方法的最大問題了
最大問題在於, 第二次的結果只保証最大值及最小值是對的, 對於修正項, 需要更多的運算
- U; P( `9 B# a. @% ]4 `# T當亂度能包含所有的項時, 答案一定是對的
所以關鍵就在於如何用最少的運算次數達到最大的亂度.
左上到右下不用再算的理由是, 左上一定是最小值, 右下一定是最大值, 所以根本不用算
1 V* y0 M* [. o% ^8 B* o- B所以在最大的亂度中, 8-1=7次應是最多的運算了,

有人有更佳解嗎?

呆頭鴨

回復 8# kevin

9 D4 n; k* |9 C8 T" A
    大大的方法真不錯~ 我怎麼沒有想到呢XD....

masonchung

桶米版大 真是太棒嚕

tommywgt

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

alita

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