Hobby project ... FFT/IFFT

[jefflieu]

tôi thấy là phải chọn thuật toán trước.
Khi học môn Xử lý tín hiệu số 2, tôi có hỏi thầy về FFT, thì thầy tôi nói là phổ biến nhất vẫn là FFT radix 2 hoặc radix 4. vì các kiến trúc này đối xứng (cũng khá quan trọng), và tôi thấy là có thể dùng lại được butterfly của DFT 2 điểm. Tuy nhiên cấu trúc điền khiển sẽ phức tạp.

Nếu đã chọn được kiến trúc rồi, thì tôi nghĩ có thể biểu diễn thuật toán bằng C++, sau đó phân chia các khối chức năng và điều khiển sử dụng SystemC.

Thiết kế SystemC có thể coi như một reference design. Testbench của SystemC có thể dùng lại được, nhưng khi đó sẽ cần các công cụ hỗ trợ đồng mô phỏng có license như Modelsim SE, VCS v.v....

Thuật toán thì chắc sẽ thử trước với Radix-2, Jeff đang học lại lý thuyết FFT ... rồi sẽ nghiên cứu phần architecture. Không biết có cần viết trước trên C++ không nhỉ, hay nhảy luôn qua SystemC?

[tonyvandinh]

Ý Jeff là dùng lại cho mỗi stage:
Ví dụ 8-point FFT : mỗi stage có 4 phép tính butterfly, tổng cộng có 12 phép tính butterfly.
Nhưng có thể dùng 1 khối Butterfly cho mỗi stage --> mất 3 khối Butterfly tất cả.
--> cho N-point FFT thì cần log2(N) khối butterfly và một số RAM(theo tính toán của J thì mất 1.5xN-word RAM tất cả) để buffer giữa các stage.

Jeff làm thử với 8 điểm thì có vẻ làm được không bị resource conflict.
Source, phần systolic architecture:
http://www.ll.mit.edu/HPEC/agendas/p...ed/jackson.pdf

Vậy là khi Jeff nói dùng lại là ý dùng lại cách hoạt động (design reuse) chứ không phải sharing. Systolic là pipeline architecture không có sharing. Mình hiểu ý Jeff rồi. Còn in place achitecture thì dùng sharing cho nên đỡ tốn kém hơn nhưng chậm hơn pipeline. Những FFT lớn thường dùng achirecture này.

[tonyvandinh]

Thuật toán thì chắc sẽ thử trước với Radix-2, Jeff đang học lại lý thuyết FFT ... rồi sẽ nghiên cứu phần architecture. Không biết có cần viết trước trên C++ không nhỉ, hay nhảy luôn qua SystemC?

FFT achitecture thường phải xác định trước và code phải ám chỉ hardware achitecture. Không có cơ hội để làm exploration cho nên dùng systemc ngay từ đầu thì tiện hơn.

[cation_h]

Bạn có thể cho một ví dụ đơn giản về cách dùng lại butterfly mà vẫn cho vào 1 sample và cho ra 1 sample mỗi clock. Sample ở đây là toàn bộ mọi điểm của FFT. Cám ơn bạn trước

Nếu muốn dùng lại thì sẽ mất thêm clock. Tôi chưa thấy cách nào để giữ nguyên như thế cả.

chúc vui

[jefflieu]

Trong cái link về bài báo của jackson_preston thì họ đề nghị thiết kế như thế này:


Trong hình vẽ trên cùng, mỗi vòng tròn là một Operation, các số trong vòng tròn là chu kì clock mà tại đó operation được thực hiện. Ở mỗi stage, các operation được thực hiện bởi 1 khối (tạm gọi là khối Butterfly) duy nhất. Trong hình vẽ thì khối butterfly được vẽ ở dưới cùng.
Mỗi khối butterfly có 1 buffer ở đầu vào và 1 ở đầu ra. Độ sâu của các buffer này tùy thuộc vị trí của khối butterfly trong dãy tính toán FFT (stage).
Trong pipeline có các khối switch, ở một số cycle, cần phải switch các input. Một số cycle khác tín hiệu không bị switch.

Sau phép tính, các giá trị trong ô in đậm thể hiện giá trị tại đầu vào (A) của khối butterfly kế tiếp, các giá trị trong ô trắng thể hiện giá trị tại đầu B.
Ví dụ ô trắng chứa : x'[0],5 nghĩa là giá trị này valid tai clock 5 và valid tại đầu B của khối butterfly tiếp theo.

Đây là 1 cấu trúc mình mới biết được ... Hy vọng mình vẽ cái hình đó đúng và dễ hiểu
Đây là lý thuyết:

[tonyvandinh]

Trong pipeline có các khối switch, ở một số cycle, cần phải switch các input. Một số cycle khác tín hiệu không bị switch.

Sau phép tính, các giá trị trong ô in đậm thể hiện giá trị tại đầu vào (A) của khối butterfly kế tiếp, các giá trị trong ô trắng thể hiện giá trị tại đầu B.
Ví dụ ô trắng chứa : x'[0],5 nghĩa là giá trị này valid tai clock 5 và valid tại đầu B của khối butterfly tiếp theo.

Theo tôi thì nên tạm bỏ chi tiết thời gian qua một bên và chú trọng vào cách hoạt động trước rồi từ từ phân tích và phân chia ra cách hoạt động của khối nhỏ hơn, dễ làm việc hơn (design partition). Trong khi chia ra từng khối nhỏ nên chú trọng vô hoạt động giống nhau (trong trường hợp này là khối butterfly) và tìm cách dùng lại (reuse) càng nhiều càng tốt. Những khối chùng (giống nhau) cũng có thể nằm trong những khối chùng khác (trong trường hợp này, khối butterfly có thể nằm trong FFT stage). Nếu đường ra của mỗi stage được đổi hoán thì cấu trúc bên trong có thể thiết kế giống nhau và có thể dùng lại.



Trong hình ở trên, các bạn có thể chọn một stage nào đó trong 3 stages để dùng lại rồi vẽ lại sao đó để có cùng cách hoạt động như trước. Như vậy giữa mỗi stage sẽ có một khối để chuyển hoán (re-ordering)

Have fun! :-)

[jefflieu]

Sao project này ế thế nhỉ ... hức hức

Anyway, để tóm tắt:
1) Lý thuyết FFT: chia để trị (divide and conquer) thường sẽ nghe nói tới kiểu Decimation In Time (DIT) và decimation in frequency (DIF) ... và thông số Radix (tạm dịch là Gốc).
2) Về cấu trúc thực hiện FFT trên VLSI: cơ bản có 2 cấu trúc Single-Delay-Feedback (SDF) và Multiple-Delay-Commutator (MDC) ...
- Nghe loáng thoáng có kiểu thực hiện dựa trên fixed-point và kiểu thực hiện dựa trên Block Floating-point nữa ...


Source: http://ipdps.cc.gatech.edu/1996/PAPERS/S19/HE/HE.PDF

Từ 2 kiểu này đẻ ra nhiều kiểu khác gom cái mạnh cái yếu của mấy kiểu này.
Jeff mới chỉ giác ngộ được kiểu Radix-2 MDC, còn mấy kiểu khác sẽ nghiên cứu từ từ ...

You're welcome to join !!!

[jefflieu]

Sau khi đọc tới đọc lui các paper và các data-sheet IPCORE của Altera và Xilinx thì Jeff quyết định làm từng bước trước tiên là:
- R2SDF: Radix-2 Single-path delay feedback, kiểu này đơn giản nhất trong các loại.
- Sau đó sẽ mở rộng ra đến 256-point.
- Bước tiếp theo là dùng R2^2SDF, theo các paper thì kiểu này tiết kiệm được 1/2 tài nguyên DSP (Hard Multiplier), các IPCORE của Altera cũng sử dụng cấu trúc này.
- Từ đây mở rộng ra đến 16k-point.
- Sau đó có thời gian sẽ chuyển qua từ tính toán kiểu fixed-point sang tính toán kiểu block-floating-point (BFP).
---
Bắt đầu code bằng SystemC .

[nguyenchipon]

Anh jefflieu đã viết cái code C cho khối Butterfly chưa ạ ! Em cũng tập tành viết nhưng thấy nó ngô nghê thế nào ấy.
Code của e e cảm thấy kiểu như là ... nói chung dở tệ nhưng vẫn ra được cái kết quả ( mô hình của phần cứng). Chờ xem cái code của anh để học hỏi

[tonyvandinh]

Anh jefflieu đã viết cái code C cho khối Butterfly chưa ạ ! Em cũng tập tành viết nhưng thấy nó ngô nghê thế nào ấy.
Code của e e cảm thấy kiểu như là ... nói chung dở tệ nhưng vẫn ra được cái kết quả ( mô hình của phần cứng). Chờ xem cái code của anh để học hỏi

Chipon có thể bỏ code của mình lên cho mọi người tham khào kô?

[jefflieu]

Chipon có thể bỏ code của mình lên cho mọi người tham khào kô?

Uh đúng đó, post đi dể Jeff copy & paste haha ... được phần nào hay phần đó.

[jefflieu]

Cấu trúc Radix-2-Single-path-delay-feedback:



Hình trên mô tả khối BUF sẽ được sử dụng trong mỗi bước (stage) của FFT. Với N=2^s, cần s bước.
Trong hình bên, N là số lương điểm của thuật toán FFT, S là vị trí của BUF này trong các bước. Để đơn giản, dễ hiểu, lấy N=8, S=0. Giả sử rằng mỗi chu kì sẽ có 1 mẫu data đi vào block, và 1 mẫu data ra khỏi block.
Trong 4 chu kì đầu tiên (0->3), block không làm gì hết, chỉ shift input vào shift register (X0, X1, X2, X3), từ chu kì 4 đến chu kì 7, X0 sẽ ở đầu ra của shift-register, X4 sẽ ở input của block, block xuất ra X0+X4, X1+X5, X2+X6, X3 + X7, đồng thời shift register sẽ lấy input của bộ trừ (X0-X4, X1-X5 ... ) ...
Trong chu kì 8 tới 11, block sẽ shift X0 tới X3 của frame kế tiếp, và xuất ra output của bộ nhân, bộ nhân lúc này sẽ tính (X0-X4)*Wkn ... (X3-X7)*Wkn ...

Các bạn có thể đối chiếu ở:
http://www.cmlab.csie.ntu.edu.tw/cml...sform/fft.html
Giải thuật này sử dụng cách tách ở tần số (decimation in frequency).

[jefflieu]

Kêu gọi khan cổ mà không có bạn nào phụ code systemC, tự làm vậy.

Đây là code mô tả shift register bằng systemC, trước tiên mình làm với số kiểu float vì chưa quen với SystemC, và muốn thử nghiệm cách hoạt động của cấu trúc R2SDF trước. Cách hoạt động rất đơn giản, tại mỗi clock edge, nếu cổng vào shift = 1, thực hiện việc dịch data, còn không thì thôi, không làm gì. Phần template viết sẵn để có thể tạo được shift-register với độ sâu (depth) tùy ý.

template<int DEP=4>
SC_MODULE(shifter_f)
{
sc_in_clk clk;
sc_in<sc_logic> shift;
sc_in<float> din;
sc_out<float> dout;

int ibuff_depth;
float ibuff[DEP];
void shifting();

int _depth;

SC_CTOR(shifter_f){
_depth=DEP;
cout<<"Shifter (Float) Created "<<" "<<DEP<<endl;
for(int t=0;t<DEP;t++){ibuff[t]=0;}
SC_METHOD(shifting);
sensitive<<clk.pos();
}
};

template<int DEP>
void shifter_f<DEP>::shifting(void)
{
int t;
if(shift.read()==1)
{
for(t=DEP-1;t>0;t--)
{
ibuff[t]=ibuff[t-1];
}
ibuff[0]=din.read();
dout.write(ibuff[DEP-1]);
cout<<"Shift is called:";
for(t=0;t<DEP;t++)
{
cout<<ibuff[t]<<" ";
}
cout<<endl;
}
}

[jefflieu]

Done phần thử nghiệm mô phỏng = systemC cách hoạt động của R2SDF và mở rộng ra đến 8-point FFT.
Đã test với 1 test vector là 0-255. Kết quả khá giống với FFT của Matlab.

Các phần code quan trọng:

SC_MODULE(BUF_top_f)
{
sc_in<sc_logic> sof;
sc_in<sc_logic> dv;
sc_in<sc_logic> ce;
sc_in<float> real_in;//real part
sc_in<float> imag_in;//imaginary part
sc_in_clk clk;

sc_out<float> real_o; //real part
sc_out<float> imag_o; //imaginary part

sc_out<sc_logic> sofo;
sc_out<sc_logic> dvo;




shifter_f<(N>>S)>* shift_r, *shift_i;
//Internal signals
sc_signal<sc_logic> sof_i;
sc_signal<sc_logic> dv_i;
sc_signal<sc_logic> shift_en;
sc_signal<float> real_i;//real part
sc_signal<float> imag_i;//imaginary part
sc_signal<float> shifter_o_real;//real part
sc_signal<float> shifter_o_imag;//imaginary part

sc_signal<float> shifter_i_real;//real part
sc_signal<float> shifter_i_imag;//imaginary part

sc_signal<float> x_plus_x4_real;
sc_signal<float> x_minus_x4_real;
sc_signal<float> x_plus_x4_imag;
sc_signal<float> x_minus_x4_imag;

sc_signal<float> Wkn_real;
sc_signal<float> Wkn_imag;

sc_signal<float> P_real;
sc_signal<float> P_imag;

sc_signal<int> state;

int _total_state;

void execute(void);
void compute_BUF2(void);
void mult_Wkn(void);
void data_mux(void);
void Wkn_ROM(void);
void print_debug(void);

SC_CTOR(BUF_top_f)
{
state = 0;
_total_state=N>>(S-1);
sof_i = SC_LOGIC_0;
shift_en = SC_LOGIC_0;
PRINT_DBG(0)<<"Butterfly Stage "<<S<<" Created"<<endl;
shift_r = new shifter_f<(N>>S)>("ShiftReal");
shift_i = new shifter_f<(N>>S)>("ShiftImag");

(*shift_r)(clk,shift_en,shifter_i_real,shifter_o_r eal);
(*shift_i)(clk,shift_en,shifter_i_imag,shifter_o_i mag);

SC_METHOD(execute);
sensitive<<clk.pos();

SC_METHOD(compute_BUF2);
sensitive<<real_i<<imag_i<<shifter_o_real<<shifter _o_imag;

SC_METHOD(mult_Wkn);
sensitive<<state<<shifter_o_real<<shifter_o_imag<< Wkn_real<<Wkn_imag;

SC_METHOD(Wkn_ROM);
sensitive<<state;

SC_METHOD(data_mux);
sensitive<<state<<sof_i<<dv_i<<P_real<<P_imag<<x_p lus_x4_real<<x_plus_x4_imag<<real_i<<imag_i<<x_min us_x4_real<<x_minus_x4_imag;

SC_METHOD(print_debug);
sensitive<<clk.pos();
}

[jefflieu]

Codes

FFTIP.cpp là file chứa hàm main.
sysgen.h là file tạo các test vector và xuất output ra file.
Các file quan trong nằm trong thư mục FFTIP.