Chương 1. GIỚI THIEU ĐỀ TÀI 1. Tông quan đề tài Trong thế giới ngày nay, chúng ta đang tiếp xúc với một lượng lớn dữ liệu như là âm thanh, hình ảnh và đữ liệu từ các cảm biến, đặc biệt là dữ liệu lớn (big data). Khi làm việc với các tín hiệu thời gian như âm thanh, hình ảnh, hoặc dữ liệu từ các cảm biến thì việc hiểu và phân tích chúng là một phần không thé thiếu trong nhiều ứng dụng của nhiều lĩnh vực khác nhau.
Việc nắm bắt và phân tích sâu các tín hiệu thời gian này sẽ góp phần vào nhiều ứng dụng trong thực tiễn. Trước khi FFT phát triển thì trước đây đã có một phương pháp biến đối Fourier rời rac đó là DFT (Discrete Fourier Transform) đã ton tại va được sử dụng cho nhiều ứng dụng. Tuy nhiên việc sử dụng phép biến đổi Fourier rời rac (DFT) lại có một van dé, đó chính là việc tính toán tương đối phức tạp khi chiều dài dữ liệu can tính toán tăng lên. Dé tính DFT chiều dài N cần số phép nhân là N? và N (N - 1) phép cộng [2].
Chính vì vậy mà khi sỐ lượng mẫu N càng lớn thì việc tính toán DFT trở nên rất tốn kém về mặt tài nguyên máy tính. Điều này khiến việc ứng dụng DFT trong thực tế trở nên gặp nhiều hạn ché, đặc biệt là trong các ứng dụng yêu cầu xử lý các tín hiệu lớn hoặc thời gian thực. Từ khi James Cooley và John Tukey phát hiện ra thuật toán nhanh hơn vào khoảng năm 1965 gọi là FFT (viết tắt của Fast Fourier Tranform), là một phương pháp đo lường quan trọng trong lĩnh vực khoa học và kỹ thuật. Ý tưởng của thuật toán FFT là sử dụng kỹ thuật chia dé trị.
Thay vì việc tính DFT cho cả một đoạn tín hiệu có độ dài lớn chúng ta sé thực hiện DFT cho từng đoạn tín hiệu nhỏ hơn trong tín hiệu đó rồi từ kết quả thu được chúng ta tính ngược lại DFT của tín hiệu ban đầu. Yêu cầu của phương pháp này đó là day tín hiệu cần phải có độ dai N va N phải là lũy thừa của 2. Cách tính của phương pháp này là thực hiện chia day tín hiệu cần tính thành 2 nửa có độ dài N/2 rồi tính DFT của 2 dãy nhỏ này. Mỗi dãy nhỏ lại được tính bằng cách chia nhỏ chúng ra thành 2 day con nhỏ hơn,.
Công việc trên được lặp lại đến khi nào dãy con trở nên đơn giản hơn rồi và không cần phải chia nữa (thường dãy con chỉ còn là 2). Từ kết quả DFT của dãy con ta tính ngược lại DFT của dãy to hơn. Thuật toán FFT chiều dài N thì chỉ cần 5 (ogzN) phép nhân và NlogzN phép cộng [2]. Chính vì vật nó giúp giảm đáng kể thời gian và tài nguyên cần thiết dé thực hiện biến đôi Fourier đặc biệt khi số lượng mẫu N rất lớn.1: So sánh độ phức tạp của thuật toán DFT va FFT [2] DET FFT.
Số phép cộng | Số phép nhân | Số phép con N Sô phép nhân P peons P P š mạng , sô phức sô phức sô phức sô phức N? N(N - 1) (N/2)logoN NlogoN 8 64 56 12 24 16 256 240 32 64 32 1024 992 80 160 64 4096 4032 192 384 Từ FFT cơ số 2, giờ đây đã được phát trién và tinh toán được trên những cơ số khác như cơ số 4, cơ số 8, cơ số 2?, cơ số 23 cùng với nhiều cấu trúc tính toán FFT khác nhau như song song, SDF (Single Delay Feedback), MDC (Multipath Delay Commutator),. Sự ra đời của FFT đã mở ra nhiều cánh cửa mới cho các ứng dụng liên quan đến xử lý tín hiệu, truyền thông, xử lý ảnh và âm thanh kỹ thuật số,. Nó đã trở thành một công cụ không thé thiếu trong nhiều lĩnh vực khoa học và công nghệ hiện đại, góp phan đây nhanh tiến độ nghiên cứu và phát triển trong lĩnh vực này. Đối với các nghiên cứu trong nước Nghiên cứu FFT tại Việt Nam đã có những bước phát triển đáng kể trong những năm gần đây.
Hướng nghiên cứu này đã và đang được các kỹ sư, nhà nghiên cứu và sinh viên ở các trường đại học trong lĩnh vực công nghệ thông tin và viễn thông nghiên cứu và phát triển tập trung vào việc cải tiến thuật toán, tăng tốc độ xử lý và giảm tài nguyên hệ thống không cần thiết,. Đặc biệt là các công ty trong nước cũng đã nghiên cứu và phát triển cho IP này cho việc tích hợp được chúng vào các sản phẩm công nghệ của mình [3] [4] [5]. Đối với các nghiên cứu ngoài nước Nghiên cứu FFT là một lĩnh vực rất sôi động trên toàn thế giới, với sự tham gia của các nhóm nghiên cứu từ các trường đại học, viện nghiên cứu và các công ty công nghệ. Các hướng nghiên cứu chính bao gồm việc tối ưu thuật toán FFT trên các kiến trúc phần cứng như GPU, FPGA, ARM,.
phát triển các IP FFT tích hợp cao với hiệu suất và tính toán linh hoạt; triển khai FFT trên các ứng dụng như xử lý ảnh số, xử lý tín hiệu, radar, sonar,. [1] [6] Theo bài báo [1] hiện tại họ đã làm được mạch FFT trên N điểm và đạt được các thông số như Bảng 1.2: Kết quả từ bài báo [1] Parameters Reconfigurable Radix-22 FFT No. of Point 16 32 64 128 256 512 (N) No. of slice Flip Flop | 284 410 538 679 851 | 1028 used No.
of4 input LUTs 629 1031 1345 1397 2497 3335 used Max Frequency | 173.9 (MHz) Nhận thấy được sự cần thiết và tiềm năng của FFT. Do đó, nhóm đã quyết định quyết định nghiên cứu và thực hiện thiết kế một mạch FFT có khả năng nạp dữ liệu liên tục để làm khóa luận tốt nghiệp. Trong khóa luận này nhóm thực hiện thay đổi bộ tính toán từ Fix — Point sang bộ tính toán Floating — Point 32 — bit để có thé tăng độ chính xác hơn trong tính toán đồng thời đặt pipeline vào cho các bộ tính toán này dé van đảm bao toc độ. Mục tiêu đề tài - Hiéu được thuật toán và có xây dựng thuật toán bang Python.
- Thiết kế được bộ tính toán số Floating - Point 32 — bit trên các phép toán cộng trừ và nhân có pipeline. - _ Thiết kế bộ tính toán FFT tối ưu về tốc trên số Floating - Point 32 — bit. - _ Xây dựng môi trường dé kiểm tra tính đúng sai của thiết kế bằng UVM. - Tan số đạt được của thiết kế trên 100Mhz.
Giới hạn đề tài - Bộ tính toán trên số Floating — Point với sai số là 6 chữ số thập phân. - Dam bao được thiết kế FFT hoạt động đúng chức năng. - _ Xây dựng được môi trường kiểm tra tính đúng sai của thiết kế băng UVM. - _ Tần số đạt được của thiết kế trên 100 MHz.
Số dấu cham động (số Floating - Point) 2. Giới thiệu số dấu cham động Các số dấu chấm động cố định (Fixed — Point) bị hạn chế bởi việc chúng không thê đồng thời biểu diễn các số rất lớn và rất nhỏ băng một kích thước khoảng kích thước nhất định. Dé khắc phục điều này, người ta đã áp dung một dạng chuẩn mới đó là scientific notation. Với dang chuẩn này, ta có thể linh động đặt dấu cham nhị phân ở vi trí thuận tiện và sử dụng lũy thừa của hệ nhị phân dé xác định vị trí đó.
Nhờ vào điều này mà các số rất lớn và rất nhỏ có thể được biểu diễn chỉ bằng vài chữ số [7]. Chính vì vậy mà từ đó số dấu chấm động (Floating - Point) ra đời. Số dấu cham động được chuẩn hóa, cho phép biéu diễn gần đúng các số thập phân rất lớn hoặc rất nhỏ dưới dạng một số nhị phân trong dạng quy ước. Thành phan của số dau cham động bao gồm phan dau, phần mũ và phan thập phân [8].
Số dấu cham động được dùng để biểu diễn số thập phân trong hầu hết máy móc và tính toán kỹ thuật. Mỗi số dấu châm động nhị phân được biểu diễn dưới dạng f2°, trong đó f là phần thập phân (hay còn gọi là Mantissa), 2 là cơ số nhị phân và e là mũ của cơ số đó. Phần Mantissa và số mũ có thể là số dương hoặc âm, nhưng cơ số luôn là dương [7]. Khi thực hiện các phép toán số học trên số dấu chấm động, phần cứng phải xử lý sự kết hợp giữa dấu, số mũ và phần Mantissa, tất cả được mã hoá dưới dạng nhị phân.
Biéu diễn của số thực dấu cham động Số dấu cham động dạng nhị phan (binary Floating — Point) dang chuan [9]: 1.1) Số dấu chấm động dang thập phan (decimal Floating — Point) dạng chuẩn: 1.2) Trong đó: yyyy: Exponent (phần mũ) xxxxxxxx: Fraction (phần số lẻ) 1.xxxxxxxx: significand/Mantissa (phần định tri) 2. Dạng chuẩn IEEE 754 cho số dấu cham động Có nhiều cách biểu diễn số dấu chấm động, trong đó cách biểu diễn theo chuẩn IEEE — 754 được sử dụng rộng rãi trong khoa hoc máy tính hiện nay. Theo chuẩn IEEE — 754, số thực dấu cham động được biểu diễn ở hai dạng cơ bản: Số thực dấu chấm động với độ chính xác đơn (Single precision) va số thực dấu chấm động với độ chính xác kép (Double precision). Số thực dấu chấm động được chia thành các phần: Dấu (Sign bit), phần mũ (Exponent field) và phần thập phân (Mantissa Field) [7].
Phan bit dấu (Sign bit) theo chuẩn IEEE, bit dấu có giá tri 0 biểu diễn cho một số dương va bit dau có giá trị 1 biểu diễn cho một số âm. Phần thập phân (Mantissa Field) có thể thể biểu diễn theo nhiều cách khác nhau bằng cách dịch số sang trái hoặc sang phải của dấu nhị phân và tăng giảm mũ tương ứng. Phần mũ (Exponent field) xác định phạm vi biểu diễn của số dấu chấm động. Số thực dấu chấm động với độ chính xác đơn được định nghĩa có độ dài 32 — bit được chia thành các phần: Dấu (Sign) với độ dài 1 — bit, mũ (Exponent) với độ dài 8 — bit và phần lẻ sau dau cham (Mantissa/ Significand) với độ dài 23 bit.
Exponent (biased) Significand 1 bit 8 bits 23 bits Hình 2.1: Số dau cham động chính xác đơn Mối quan hệ giữa định dạng sỐ Floating - Point 32 — bits và số thực được cho bởi [7]: (—1)Ê(2°~127)(1. f) chuẩn hóa, 0 < e < 255, Giá trị = 4 (—1)°(2°~125)(0.3) Ngoại lệ, trường hợp khác.