Hobby project ... FFT/IFFT

[tonyvandinh]

Em chào bác Tony.
Em sẽ mở threat mới ra tiếu chuẩn, các bước thực hiện theo ý kiến chủ quan. Mong bác và các bác khác chỉnh sửa nếu cho gì chưa chính xác.
Em

Hoan hô cachep, tôi sẽ ủng hộ hết mình.

Tony

[jefflieu]

Okie. Hiện giờ Jeff cũng tịt về FFT. Mọi người cùng nghiên cứu.
Schedule của project như sau:
- Nghiên cứu (lại) FFT/IFFT - 4 tuần
- Nghiên cứu các cấu trúc để thực hiện FFT 4 tuần.
- Specifications + Thiết kế các khối 2 tuần.
- Thực hiện thiết kế + test:
+ 16 point : 2 tuần
+ 256 point: 2 tuần
+ 1k point: 3 tuần
+ 8k point : 3 tuần
+ 32k point: 4 tuần
- Nhìn sơ sơ, mất tổng cộng 6 tháng.

Mình dừng ở 32k Point vì nếu không lầm thì các công cụ Altera và Xilinx chưa support. Và sẽ cần FPGA khá bự để chứa cái core này.
Anh em, mình làm tà tà .
Bắt đầu bằng việc nghiên cứu lý thuyết FFT.

[jefflieu]

for Your Information

[jefflieu]

Bạn lick và các bạn khác có tìm kiếm được gì hay gặp rắc rối trong nghiên cứu gì thì post lên mọi người cùng nghiên cứu và thảo luận.
Mình có quen mấy bạn có account có thể download tài liệu trên các trang web khoa học.

[vannghia]

FFT có khá nhiều ứng dụng, hầu như những ai thuộc lĩnh vực điện tử đều từng nghiên cứu môn học xử lý tín hiệu số. Tham số quan trọng nhất khi chọn thiết kế FFT là số điểm FFT và tốc độ luồng dữ liệu.
Thực chất FFT là thực hiện nhiệm vụ quan sát phổ tín hiệu trong băng tần số, cho phép đánh giá cường độ tín hiệu (hay năng lượng) tại điểm quan sát.
FFT thực hiện phân dải tín hiệu thành các băng tần, do đó tiện lợi cho các bộ lọc phía sau. Khi kết hợp với các bộ lọc thì nó sẽ trở thành từng băng lọc rất hữu ích, giảm đi nhiệm vụ nặng nề cho các bộ lọc khi hệ thống chỉ sử dụng các bộ lọc đơn thuần.
Tài liệu kèm theo hy vọng hữu ích cho các bạn

[tonyvandinh]

Jeff định làm về "in place" hay pipeline?

[jefflieu]

Jeff định làm về "in place" hay pipeline?

Không chắc có hiểu đúng ý chữ " in place " của anh ko.
Em hiểu "in place" là làm FFT theo đúng như butterfly dataflow của nó. Nếu vậy thì làm cho mấy FFT lớn mất nhiều resource quá.
Do vậy chắc là phải làm pipeline mới scalable (=có thể mở rộng được).

[jefflieu]

Dự tính là sau khi nghiên cứu xong lý thuyết với mấy cấu trúc người ta đã làm, thì sẽ mô phỏng bằng SystemC và SystemVerilog thử.
Bạn nào hứng thú thì nghiên cứu phụ SystemC/SystemV nhé

[tonyvandinh]

Không chắc có hiểu đúng ý chữ " in place " của anh ko.
Em hiểu "in place" là làm FFT theo đúng như butterfly dataflow của nó. Nếu vậy thì làm cho mấy FFT lớn mất nhiều resource quá.
Do vậy chắc là phải làm pipeline mới scalable (=có thể mở rộng được).

Khi làm những FFT lớn, thường thì dùng lại những cấu trúc cho từng bước để giảm cost và vì vậy cần phải có chỗ chứa (storage) chẳng hạn như RAM. Những samples sẽ được chứa vô RAM trước rồi đọc ra, process và viết trở lại vô RAM. Kỹ thuật này gọi là "in place". Còn pipeline thì phải có chỗ chứa ở mỗi bước và không dùng lại butterfly (khối radix) để tăng tốc độ nhưng rất là tốn kém.

[tonyvandinh]

Dự tính là sau khi nghiên cứu xong lý thuyết với mấy cấu trúc người ta đã làm, thì sẽ mô phỏng bằng SystemC và SystemVerilog thử.
Bạn nào hứng thú thì nghiên cứu phụ SystemC/SystemV nhé

Bạn nào có hứng thú để dùng systemC thì nên theo cái tutorial ở dưới đây để làm quen nhe. Nếu cần tôi sẽ hướng dẫn thêm.

http://www.dientuvietnam.net/forums/showthread.php?t=34991

[jefflieu]

Khi làm những FFT lớn, thường thì dùng lại những cấu trúc cho từng bước để giảm cost và vì vậy cần phải có chỗ chứa (storage) chẳng hạn như RAM. Những samples sẽ được chứa vô RAM trước rồi đọc ra, process và viết trở lại vô RAM. Kỹ thuật này gọi là "in place". Còn pipeline thì phải có chỗ chứa ở mỗi bước và không dùng lại butterfly (khối radix) để tăng tốc độ nhưng rất là tốn kém.

Òh, vậy Jeff tính làm pipelined ... khá nhiều bài báo suggest pipeline để tăng tốc độ, nhưng cũng dùng lại khối Butterfly. Các khối butterfly ở mỗi bước của FFT được dùng lại.
Người ta lý luận là mỗi clock chỉ có 1 sample mới, cho nên mỗi clock chỉ cần produce 1 output, dẫn đến việc có thể schedule các operation ở mỗi stage vào 1 khối Butterfly phần cứng duy nhất.

Nhưng để schedule như vậy cũng tốn RAM để buffer output của stage trước và output của stage sau.
Để Jeff nghiên cứu thêm.

(bạn nào cần các bài báo để nghiên cứu thì email Jeff)

[tonyvandinh]

Òh, vậy Jeff tính làm pipelined ... khá nhiều bài báo suggest pipeline để tăng tốc độ, nhưng cũng dùng lại khối Butterfly. Các khối butterfly ở mỗi bước của FFT được dùng lại.
Người ta lý luận là mỗi clock chỉ có 1 sample mới, cho nên mỗi clock chỉ cần produce 1 output, dẫn đến việc có thể schedule các operation ở mỗi stage vào 1 khối Butterfly phần cứng duy nhất.

Nhưng để schedule như vậy cũng tốn RAM để buffer output của stage trước và output của stage sau.
Để Jeff nghiên cứu thêm.

(bạn nào cần các bài báo để nghiên cứu thì email Jeff)

Hm! Mình chưa hình dung ra được là họ dùng cách nào để dùng lại khối butterfly cho pipeline design, Ví dụ cái FFT cần 3 stages để hoàn tất. Cái hình đính kèm cho thấy là

* stage1 : nhận đường vào, làm butterfly
* stage2 : làm butterfly
* stage3 : làm butterfly rồi cho ra.

Cứ liên tục như vậy cho những clock (transaction) sau. Như vậy thì từ thời điểm C trở đi (C cũng còn được gọi là latency , mối ra đầu tiên), cần có tới 3 butterfly liền một lúc,

Jeff nghĩ sao? Nếu Jeff có thể cho cái link, mình sẽ nghiên cứu và cho Jeff biết là họ có thể thực hiện như nói ở trên.

Tony

[cation_h]

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....

[tonyvandinh]

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.

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

[jefflieu]

Hm! Mình chưa hình dung ra được là họ dùng cách nào để dùng lại khối butterfly cho pipeline design, Ví dụ cái FFT cần 3 stages để hoàn tất. Cái hình đính kèm cho thấy là

* stage1 : nhận đường vào, làm butterfly
* stage2 : làm butterfly
* stage3 : làm butterfly rồi cho ra.

Cứ liên tục như vậy cho những clock (transaction) sau. Như vậy thì từ thời điểm C trở đi (C cũng còn được gọi là latency , mối ra đầu tiên), cần có tới 3 butterfly liền một lúc,

Jeff nghĩ sao? Nếu Jeff có thể cho cái link, mình sẽ nghiên cứu và cho Jeff biết là họ có thể thực hiện như nói ở trên.

Tony

Ý 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/proc04/Talks/Wed/jackson.pdf