Úng dụng của FPGA tại Việt Nam
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
MỤC LỤC
BẢNG KÝ HIỆU VIẾT TẮT
Ký Hiệu
Diễn Giải
ASIC
Application Specific Integrated Circuit
ADC
Analog to Digital Converter
ALU
Arithmetic Logic Unit
ASM
Auto Senquencing Memory
CPLD
Complex Programmable Logic Device
CPU
Central Processing Unit
DSP
Digital Signal Processing
DAC
Digital to Analog Converter
DPU
Data Processing Unit
FIR
Finite Impulse Response
FPGA
Field Programmable Gate Array
HDL
Hardware Description Language
IC
Integrated Circuit
IEEE
Institute of Electrical and Electronics Engineers
JTAG
Joint Test Action Group
LED
Light Emitting Diode
LUT
Look Up Table
LMS
Least Mean Square
PAL
Programmable Array Logic
PLA
Programmable Logic Array
1
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
PCI
Peripheral Component Interconnect
PE
Process Element
RAM
Random Access Memory
ROM
Read Only Memory
RS232
Recommended Standard 232
SoC
System on chip
SRAM
Static Random Access Memory
SPLD
Simple Programable Logic Device
USB
Universal Serial Bus
VHDL
Very High Speed Itergrated Circuit
Hardware Description Language
VHSIC
Very High Speed Itergrated Circuit
2
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
LỜI MỞ ĐẦU
Ngày nay, xử lý tín hiệu và lọc số là một ngành phát triển hết sức mạnh mẽ, các
công nghệ, thuật toán ngày càng được đổi mới và tối ưu hoá nhằm nâng cao tính hiệu
quả của nó. Tuy nhiên, công nghệ phát triển càng cao thì đòi hỏi phần cứng phải đủ
nhanh để xử lý. Các mạch lọc tương tự trước đây không còn đủ khả năng để đáp ứng
yêu cầu đó nữa. Vì vậy, FPGA đã ra đời như một giải pháp cung cấp môi trường làm
việc hiệu quả cho các ứng dụng thực tế. Tính linh động cao trong quá trình thiết kế cho
phép FPGA giải quyết những bài toán phức tạp mà trước kia chỉ thực hiện nhờ phần
mềm máy tính. Ngoài ra, nhờ mật độ cổng logic cao, FPGA được ứng dụng cho những
bài toán đòi hỏi khối lượng tính toán lớn và dùng trong các hệ thống làm việc theo thời
gian thực. Những ứng dụng trong thực tế của FPGA rất rộng rãi, bao gồm: các hệ
thống hàng không, vũ trụ, quốc phòng, tiền thiết kế mẫu ASIC(ASIC prototyping), các
hệ thống điều khiển trực quan, phân tích nhận dạng ảnh, nhận dạng tiếng nói, mật mã
học, mô hình phần cứng máy tính...Đặc biệt, với khả năng tái lập trình, người sử dụng
có thể thay đổi lại thiết kế của mình chỉ trong vài giờ.
Chính vì tính thiết thực mà FPGA đã mang lại, em quyết định chọn FPGA làm
hướng nghiên cứu của mình. Trong bài khoá luận này, em xin trình bày một ứng dụng
cụ thể của FPGA trong xử lý tín hiệu số đó là “Thực hiện bộ lọc FIR thích nghi
dùng thuật toán LMS”. Đề tài được thực hiện tại phòng thí nghiệm mục tiêu “Các hệ
tích hợp thông minh ( SIS LAB)” trực thuộc trường Đại học Công nghệ - ĐHQG
HN.
Em xin chân thành cảm ơn các thầy cô giáo đặc biệt là PGS.TS Trần Quang Vinh
và Th.S Nguyễn Kiêm Hùng đã tận tình hướng dẫn và giúp đỡ em để hoàn thành bản
luận văn này một cách tốt đẹp.
Do thời gian và kiến thức có hạn nên công trình này không thể tránh khỏi sai sót,
vì vậy em rất mong nhận được các ý kiến đóng góp của các thầy cô và các bạn.
Em xin chân thành cảm ơn !
Hà Nội, Ngày 27 Tháng 3 Năm 2008
Nguyễn Anh Cường
3
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Chương 1
TỔNG QUAN VỀ FPGA VÀ NGÔN NGỮ VHDL
1.1. TỔNG QUAN VỀ FPGA
1.1.1. Lịch sử ra đời của FPGA
FPGA được thiết kế đầu tiên bởi Ross Freeman, người sáng lập công ty Xilinx
vào năm 1984, kiến trúc mới của FPGA cho phép tích hợp số lượng tương đối lớn các
phần tử bán dẫn vào 1 vi mạch so với kiến trúc trước đó là CPLD. FPGA có khả năng
chứa tới từ 100.000 đến hàng vài tỷ cổng logic, trong khi CPLD chỉ chứa từ 10.000
đến 100.000 cổng logic; con số này đối với PAL, PLA còn thấp hơn nữa chỉ đạt vài
nghìn đến 10.000.
CPLD được cấu trúc từ số lượng nhất định các khối SPLD (Simple programable
logic device) thuật ngữ chung chỉ PAL, PLA. SPLD thường là một mảng logic
AND/OR lập trình được có kích thước xác định và chứa một số lượng hạn chế các
phần tử nhớ đồng bộ (clocked register). Cấu trúc này hạn chế khả năng thực hiện
những hàm phức tạp và thông thường hiệu suất làm việc của vi mạch phụ thuộc vào
cấu trúc cụ thể của vi mạch hơn là vào yêu cầu bài toán.
Kiến trúc của FPGA là kiến trúc mảng các khối logic, mỗi khối này nhỏ hơn
nhiều nếu đem so sánh với một khối SPLD, ưu điểm này giúp FPGA có thể chứa nhiều
hơn các phần tử logic và phát huy tối đa khả năng lập trình của các phần tử logic và hệ
thống mạch kết nối, để đạt được mục đích này thì kiến trúc của FPGA phức tạp hơn
nhiều so với CPLD.
Một điểm khác biệt nữa với CPLD là trong những FPGA hiện đại được tích hợp
nhiều bộ logic số học đã được tối ưu hóa, hỗ trợ RAM, ROM, tốc độ cao, hay các bộ
nhân, cộng dùng cho những ứng dụng xử lý tín hiệu số.
Ngoài khả năng cấu trúc lại vi mạch ở mức toàn cục, một số FPGA hiện đại còn
hỗ trợ cấu trúc lại ở mức cục bộ, tức là khả năng cấu trúc lại một bộ phận riêng lẻ
trong khi vẫn đảm bảo hoạt động bình thường cho các bộ phận khác
4
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
1.1.2. Khái niệm cơ bản và cấu trúc của FPGA
FPGA (Field-programmable gate array) là vi mạch dùng cấu trúc mảng phần tử
logic mà người dùng có thể lập trình được. Chữ field ở đây muốn chỉ đến khả năng tái
lập trình “bên ngoài” tuỳ theo mục đích ứng dụng của người sử dụng, không phụ thuộc
vào dây chuyền sản xuất phức tạp của nhà máy bán dẫn. Kiến trúc tổng quan về FPGA
được mô tả như hình 1:
Hình 1: Kiến trúc tổng quan của FPGA
5
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Vi mạch FPGA được cấu thành từ các bộ phận:
• Các khối logic cơ bản lập trình được (logic block)
Phần tử chính của FPGA là các khối logic (logic block). Khối logic được cấu
thành từ LUT và một phần tử nhớ đồng bộ flip-flop. LUT (Look up table) là
khối logic có thể thực hiện bất kì hàm logic nào từ 4 đầu vào, kết quả của hàm
này tùy vào mục đích mà gửi ra ngoài khối logic trực tiếp hay thông qua phần
tử nhớ flip-flop.
Khối logic được mô tả như hình 2:
Hình 2: Khối logic lập trình được của FPGA
Trong tài liệu hướng dẫn của các dòng FPGA của Xilinx còn sử dụng khái niệm
SLICE, 1 Slice gồm 4 khối logic tạo thành, số lượng các Slices thay đổi từ vài
nghìn đến vài chục nghìn tùy theo loại FPGA.
• Hệ thống mạch liên kết lập trình được
Mạng liên kết trong FPGA được cấu thành từ các đường kết nối theo hai
phương ngang và đứng, tùy theo từng loại FPGA mà các đường kết nối được
chia thành các nhóm khác nhau, ví dụ trong XC4000 của Xilinx có 3 loại kết
nối: ngắn, dài và rất dài. Các đường kết nối được nối với nhau thông qua các
khối chuyển mạch lập trình được (programable switch), trong một khối chuyển
mạch chứa một số lượng nút chuyển lập trình được, đảm bảo cho các dạng liên
kết phức tạp khác nhau.
• Khối vào/ra (IO Pads)
Khối vào/ra nhiều hay ít là tuỳ thuộc vào từng loại FPGA. Chúng có thể được
kết nối với các thiết bị bên ngoài như LED, USB, RS232, RAM....tuỳ theo mục
đích sử dụng
• Các phần tử tích hợp sẵn
6
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Ngoài các khối logic, tùy theo các loại FPGA khác nhau mà có các phần tử tích
hợp thêm khác nhau, ví dụ để thiết kế những ứng dụng SoC, trong dòng Virtex
4, 5 của Xilinx có chứa nhân xử lý PowerPC, hay cho những ứng dụng xử lý tín
hiệu số trong FPGA được tích hợp các DSP Slice là bộ nhân, cộng tốc độ cao,
thực hiện hàm A*B+C, ví dụ dòng Virtex của Xilinx chứa từ vài chục đến hàng
trăm DSP slices với A, B, C 18-bit.
1.1.3. Các ứng dụng của FPGA
Ứng dụng của FPGA bao gồm: xử lý tín hiệu số, các hệ thống hàng không, vũ
trụ, quốc phòng, tiền thiết kế mẫu ASIC(ASIC prototyping), các hệ thống điều khiển
trực quan, phân tích nhận dạng ảnh, nhận dạng tiếng nói, mật mã học, mô hình phần
cứng máy tính...
Do tính linh động cao trong quá trình thiết kế cho phép FPGA giải quyết lớp
những bài toán phức tạp mà trước kia chỉ thực hiện nhờ phần mềm máy tính, ngoài ra
nhờ mật độ cổng logic lớn FPGA được ứng dụng cho những bài toán đòi hỏi khối
lượng tính toán lớn và dùng trong các hệ thống làm việc theo thời gian thực.
1.2. TỔNG QUAN VỀ NGÔN NGỮ VHDL
Thiết kế hay lập trình cho FPGA được thực hiện chủ yếu bằng các ngôn ngữ mô
tả phần cứng HDL như VHDL, Verilog ...các hãng sản xuất FPGA lớn như Xilinx,
Altera thường cung cấp các gói phần mềm và thiết bị phụ trợ cho quá trình thiết kế,
cũng có một số các hãng thứ ba cung cấp các gói phần mềm kiểu này như Synopsys,
Synplify... Các gói phần mềm này có khả năng thực hiện tất cả các bước của toàn bộ
quy trình thiết kế IC chuẩn với đầu vào là mã thiết kế trên HDL (còn gọi là mã RTL).
Trong bài Luận văn này, có sử dụng ngôn ngữ mô tả phần cứng VHDL, do đó ta
chỉ tập chung tìm hiểu về ngôn ngữ VHDL.
1.2.1. Giới thiệu về ngôn ngữ mô tả phần cứng VHDL
VHDL là ngôn ngữ mô tả phần cứng cho các mạch tích hợp tốc độ rất cao, là một
loại ngôn ngữ mô tả phần cứng được phát triển dùng cho trương trình VHSIC( Very
High Speed Itergrated Circuit) của bộ quốc phòng Mỹ. Mục tiêu của việc phát triển
VHDL là có được một ngôn ngữ mô phỏng phần cứng tiêu chuẩn và thống nhất cho
phép thử nghiệm các hệ thống số nhanh hơn cũng như cho phép dễ dàng đưa các hệ
thống đó vào ứng dụng trong thực tế. Ngôn ngữ VHDL được ba công ty Intermetics,
7
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
IBM và Texas Instruments bắt đầu nghiên cứu phát triển vào tháng 7 năm 1983. Phiên
bản đầu tiên được công bố vào tháng 8-1985. Sau đó VHDL được đề xuất để tổ chức
IEEE xem xét thành một tiêu chuẩn chung. Năm 1987 đã đưa ra tiêu chuẩn về
VHDL( tiêu chuẩn IEEE-1076-1987).
VHDL được phát triển để giải quyết các khó khăn trong việc phát triển, thay đổi
và lập tài liệu cho các hệ thống số. Như ta đã biết, một hệ thống số có rất nhiều tài liệu
mô tả. Để có thể vận hành bảo trì sửa chữa một hệ thống ta cần tìm hiểu kỹ lưỡng tài
liệu đó. Với một ngôn ngữ mô phỏng phần cứng tốt việc xem xét các tài liệu mô tả trở
nên dễ dàng hơn vì bộ tài liệu đó có thể được thực thi để mô phỏng hoạt động của hệ
thống. Như thế ta có thể xem xét toàn bộ các phần tử của hệ thống hoạt động trong
một mô hình thống nhất.
VHDL được phát triển như một ngôn ngữ độc lập không gắn với bất kỳ một
phương pháp thiết kế, một bộ mô tả hay công nghệ phần cứng nào. Người thiết kế có
thể tự do lựa chọn công nghệ, phương pháp thiết kế trong khi chỉ sử dụng một ngôn
ngữ duy nhất. Và khi đem so sánh với các ngôn ngữ mô phỏng phần cứng khác đã kể
ra ở trên ta thấy VHDL có một số ưu điểm hơn hẳn các ngôn ngữ khác:
- Thứ nhất là tính công cộng: VHDL được phát triển dưới sự bảo trợ của chính
phủ Mỹ và hiện nay là một tiêu chuẩn của IEEE. VHDL được sự hỗ trợ của
nhiều nhà sản xuất thiết bị cũng như nhiều nhà cung cấp công cụ thiết kế mô
phỏng hệ thống.
- Thứ hai là khả năng hỗ trợ nhiều công nghệ và phương pháp thiết kế. VHDL
cho phép thiết kế bằng nhiều phương pháp, ví dụ phương pháp thiết kế từ trên
xuống, hay từ dưới lên dựa vào các thư viện sẵn có. VHDL cũng hỗ trợ cho
nhiều loại công cụ xây dựng mạch như sử dụng công nghệ đồng bộ hay không
đồng bộ, sử dụng ma trận lập trình được hay sử dụng mảng ngẫu nhiên.
- Thứ ba là tính độc lập với công nghệ: VHDL hoàn toàn độc lập với công nghệ
chế tạo phần cứng. Một mô tả hệ thống dùng VHDL thiết kế ở mức cổng có thể
được chuyển thành các bản tổng hợp mạch khác nhau tuỳ thuộc công nghệ chế
tạo phần cứng mới ra đời nó có thể được áp dụng ngay cho các hệ thống đã thiết
kế .
- Thứ tư là khả năng mô tả mở rộng: VHDL cho phép mô tả hoạt động của phần
cứng từ mức hệ thống số cho đến mức cổng. VHDL có khả năng mô tả hoạt
động của hệ thống trên nhiều mức nhưng chỉ sử dụng một cú pháp chặt chẽ
8
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
thống nhất cho mọi mức. Như thế ta có thể mô phỏng một bản thiết kế bao gồm
cả các hệ con được mô tả chi tiết.
- Thứ năm là khả năng trao đổi kết quả: Vì VHDL là một tiêu chuẩn được chấp
nhận, nên một mô hình VHDL có thể chạy trên mọi bộ mô tả đáp ứng được tiêu
chuẩn VHDL. Các kết quả mô tả hệ thống có thể được trao đổi giữa các nhà
thiết kế sử dụng công cụ thiết kế khác nhau nhưng cùng tuân theo tiêu chuẩn
VHDL. Cũng như một nhóm thiết kế có thể trao đổi mô tả mức cao của các hệ
thống con trong một hệ thống lớn (trong đó các hệ con đó được thiết kế độc
lập).
- Thứ sáu là khả năng hỗ trợ thiết kế mức lớn và khả năng sử dụng lại các thiết
kế: VHDL được phát triển như một ngôn ngữ lập trình bậc cao, vì vậy nó có thể
được sử dụng để thiết kế một hệ thống lớn với sự tham gia của một nhóm nhiều
người. Bên trong ngôn ngữ VHDL có nhiều tính năng hỗ trợ việc quản lý, thử
nghiệm và chia sẻ thiết kế. Và nó cũng cho phép dùng lại các phần đã có sẵn.
1.2.2. Cấu trúc một mô hình hệ thống mô tả bằng ngôn ngữ VHDL
Mục đích của phần này sẽ nhằm giới thiệu sơ qua về cấu trúc khung cơ bản của
VHDL khi mô tả cho một mô hình thiết kế thực.
Thông thường một mô hình VHDL bao gồm ba phần: thực thể, kiến trúc và các
cấu hình. Đôi khi ta xử dụng các gói (packages) và mô hình kiểm tra hoạt động của hệ
thống (testbench).
+ Thực thể (entity): Khai báo thực thể trong VHDL là phần định nghĩa các chỉ
tiêu phía ngoài của một phần tử hay một hệ thống. Thực chất của việc khai báo thực
thể chính là khai báo giao diện của hệ thống với bên ngoài. Ta có thể có tất cả các
thông tin để kết nối mạch vào mạch khác hoạc thiết kế tác nhân đầu vào phục vụ cho
mục đích thử nghiệm. Tuy nhiên hoạt động thật sự của mạch không nằm ở phần khai
báo này
+ Kiến trúc (Architecture): Phần thứ 2 trong mô hình VHDL là khai báo kiến
trúc. Mỗi một khai báo thực thể đều phải đi kèm với ít nhất một kiến trúc tương ứng.
VHDL cho phép tạo ra hơn một kiến trúc cho một thực thể. Phần khai báo kiến trúc có
thể bao gồm các khai báo về các tín hiệu bên trong, các phần tử bên trong hệ thống,
hay các hàm và thủ tục mô tả hoạt động của hệ thống. Tên của kiến trúc là nhãn được
đặt tuỳ theo người sử dụng. Có hai cách mô tả kiến trúc của một phần tử ( hoặc hệ
thống) đó là mô hình hoạt động (Behaviour) hay mô tả theo mô hình cấu trúc
9
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
(Structure). Tuy nhiên một hệ thống có thể bao gồm cả mô tả theo mô hình hoạt động
và mô tả theo mô hình cấu trúc.
+ Mô tả kiến trúc theo mô hình hoạt động: Mô hình hoạt động mô tả các hoạt
động của hệ thống ( hệ thống đáp ứng với các tín hiệu vào như thế nào và đưa ra kết
quả gì ra đầu ra) dưới dạng các cấu trúc ngôn ngữ lập trình bậc cao. Cấu trúc đó có thể
là PROCESS, WAIT, IF, CASE, FOR-LOOP…
+ Mô tả kiến trúc theo mô hình cấu trúc: Mô hình cấu trúc của một phần tử
(hoặc hệ thống) có thể bao gồm nhiều cấp cấu trúc bắt đầu từ một cổng logic đơn giản
đến xây dựng mô tả cho một hệ thống hoàn thiện. Thực chất của việc mô tả theo mô
hình cấu trúc là mô tả các phần tử con bên trong hệ thống và sự kết nối của các phần tử
con đó. Như với ví dụ mô tả mô hình cấu trúc một flip-flop RS gồm hai cổng NAND
có thể mô tả cổng NAND được định nghĩa tương tự như ví dụ với cổng NOT, sau đó
mô tả sơ đồ móc nối các phần tử NAND tạo thành trigơ RS
+ Cấu trúc Process: Process là khối cơ bản của việc mô tả theo hoạt động.
Process được xét đến như là một chuỗi các hành động đơn trong suốt quá trình dịch.
Cấu trúc tổng quát:
[tên nhãn]:
process
[(danh sách các yếu tố kích thích hoạt động)]
[khai báo các biến]
begin
[các câu lệnh]
end process;
+ Môi trường kiểm tra (testbench): Một trong các nhiệm vụ rất quan trọng là
kiểm tra bản mô tả thiết kế. Kiểm tra một mô hình VHDL được thực hiện bằng cách
quan sát hoạt động của nó trong khi mô phỏng và các giá trị thu được có thể đem so
sánh với yêu cầu thiết kế.
Môi trường kiểm tra có thể hiểu như một mạch kiểm tra ảo. Môi trường kiểm
tra sinh ra các tác động lên bản thiết kế và cho phép quan sát hoặc so sánh kết quả hoạt
động của bản mô tả thiết kế. Thông thường thì các bản mô tả đều cung cấp chương
trình thử. Nhưng ta cũng có thể tự xây dựng chương trình thử (testbench). Mạch thử
thực chất là sự kết hợp của tổng hợp nhiều thành phần. Nó gồm ba thành phần: mô
hình VHDL đã qua kiểm tra, nguồn dữ liệu và bộ quan sát. Hoạt động của mô hình
10
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
VHDL được kích thích bởi các nguồn dữ liệu và kiểm tra tính đúng đắn thông qua bộ
quan sát.
Chương 2
BỘ LỌC FIR
2.1. BỘ LỌC FIR TRUYỀN THỐNG
Bộ lọc FIR là bộ lọc có đáp ứng xung chiều dài hữu hạn, tức là đáp ứng xung chỉ
khác không trong một khoảng có chiều dài hữu hạn N (từ 0 đến N-1). Bộ lọc FIR với
bậc của bộ lọc là N được biểu diễn như hình 3:
Hình 3: Cấu trúc của bộ lọc FIR truyền thống
Trong đó:
x[n]: là tín hiệu lối vào của mạch
y[n]: là tín hiệu lối ra của mạch
h[n]: là đáp ứng xung của mạch
Lối ra y[n] và lối vào x[n] liên hệ với nhau bởi công thức:
N −1
y[n] = ∑ h[k ]x[n − k ]
k=0
Để tính được các giá trị y[k] từ các mẫu lối vào x[k] thì các mẫu lần lượt qua các
bộ trễ, bộ nhân và bộ cộng. Với bộ lọc FIR có bậc là N thì phải sau N phép nhân và N1 phép cộng thì mới tính được giá trị của lối ra.
11
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Như vậy, bộ lọc FIR có cấu trúc như trên có nhược điểm là khả năng đáp ứng
chậm, các mẫu lối ra không được liên tục mà sau một khoảng thời gian tính toán xong
các phép nhân và phép cộng mới được xuất ra.
Để khắc phục nhược điểm đó, ta sử dụng kiến trúc systolic array để nâng cao khả
năng đáp ứng của mạch
2.2. BỘ LỌC FIR SỬ DỤNG KIẾN TRÚC SYSTOLIC ARRAY
2.2.1. Tổng quan về systolic array
Systolic array là cấu trúc xử lý song song đặc biệt chứa các khối xử lý dữ liệu
(data processing unit gọi tắt là DPU), các khối xử lý này được sắp xếp thành một
mạng. DPU tương tự như CPU nhưng nó không có bộ đếm chương trình. Từng khối
DPU như là một trigger truyền thông bởi sự luân chuyển dữ liệu từ DPU này đến các
DPU lân cận. Thông thường, những dữ liệu khác nhau thì sẽ luân chuyển theo các
hướng khác nhau. Các luồng dữ liệu tới và rời khỏi các cổng DPU được phát từ ASM
(Auto senquencing memory là thành phần không thể thiếu của cấu trúc Non-VonNeumann. Trong cấu trúc này, cơ chế senquencing đóng vai trò là bộ đếm chương
trình). Mỗi ASM đóng vai trò là bộ đếm dữ liệu. Trong hệ thống này, luồng dữ liệu
vào có thể vào từ đầu ra của thiết bị ngoại vi và ngược lại.
Các bộ xử lý (DPU) tính toán dữ liệu, lưu trữ dữ liệu theo những cách độc lập với
nhau. Các bộ xử lý này có thể có một vài thanh ghi và khối ALU. Các DPU có khả
năng lưư trữ và xử lý dữ liệu độc lập với nhau. Mỗi DPU sau khi xử lý dữ liệu xong sẽ
chia sẻ dữ liệu cho các Cell lân cận.
Trong hình 4, mô tả kiến trúc Systolic array một chiều, dữ liệu chuyển động theo
một hướng
PE
PE
PE
PE
PE
Hình 4: Cấu trúc systolic array một chiều
Hình 5 mô tả kiến trúc systolic array hai chiều, dữ liệu chuyển động hai hướng
theo chiều của mũi tên qua các bộ DPU. Dữ liệu ra cũng theo hai hướng
12
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Hình 5: Kiến trúc systolic array hai chiều
2.2.2. Bộ lọc FIR thực hiện theo kiến trúc systolic array một chiều
Để cho việc xử lý dữ liệu được nhanh hơn, bộ lọc FIR theo kiến trúc Systolic
array sẽ bao gồm một dãy các phần tử xử lý hay còn gọi là PE (Process Element).
Trong cùng một thời điểm, các PE sẽ thực hiện đồng thời các nhiệm vụ riêng, và do
đó, tín hiệu ở lối ra sẽ được đưa ra một cách liên tục mà không phải mất một khoảng
thời gian để tính toán do nó đã được tính từ trước đó.
Cấu trúc của một PE của bộ lọc FIR SYSTOLIC được trình bày như trong hình 6
Hình 6: Cấu trúc của một PE
Như vậy, cấu trúc của bộ lọc FIR Systolic với bậc bộ lọc là N, gồm N+1 PE
được trình bày như hình 7
13
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Yin
xin
Khoá luận tốt nghiệp
+
+
…..
x
aN
yout
x
ao
xout
…..
Hình 7: Cấu trúc bộ lọc FIR systolic bậc N
Khác với bộ lọc FIR thông thường, đầu ra của bộ cộng lại được đưa qua 2 bộ
chốt để làm trễ, nó có tác dụng chia đường truyền tín hiệu của mạch thành những đoạn
nhỏ, do đó làm tăng tần số hoạt động của mạch, đồng thời làm cho tín hiệu xin và yin
vào bộ cộng cùng một lúc, do đó, tín hiệu ra sẽ được liên tục, đáp ứng nhanh, bởi việc
tính toán đã được thực hiện trước đó.
Với việc chia đường truyền dài nhất của mạch thành những đoạn nhỏ nhờ các
thanh ghi chốt, ta còn có thể tối ưu bộ lọc FIR systolic hơn nữa. Hình 8 mô tả cấu trúc
tối ưu của bộ lọc FIR systolic.
Yin
xin
+
…..
x
aN
+
yout
x
ao
…..
xout
Hình 8: Cấu trúc tối ưu của bộ lọc FIR systolic bậc N
Mô hình này về ý tưởng vẫn giống mô hình trước, bao gồm các thanh ghi chốt,
bộ cộng, bộ nhân của mô hình trước, tuy nhiên, có sự thay đổi vị trí của các thanh ghi
chốt, trước bộ nhân và bộ cộng ta chèn thêm một thanh ghi chốt vào để chia nhỏ
đường truyền tín hiệu. Do đó, làm cho tần số hoạt động của mạch tăng lên.
14
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Chương 3
BỘ LỌC FIR THÍCH NGHI DÙNG THUẬT TOÁN LMS
3.1. ĐẶT VẤN ĐỀ
Thuật ngữ lọc dùng để chỉ tất cả các hệ thống có khả năng khôi phục lại dạng của
các thành phần tần số của tín hiệu lối vào để tạo ra tín hiệu lối ra thỏa mãn các yêu cầu
mong muốn. Với bộ lọc FIR trình bày ở trên, thì hệ số của bộ lọc luôn không đổi. Do
đó, nếu có sự thay đổi đột ngột của một hoặc một vài yếu tố đầu vào(như tín hiệu
nhiễu chẳng hạn) thì bộ lọc sẽ không còn được tối ưu nữa. Hay nói cách khác, ta
không thu được tín hiệu mong muốn.
Để khắc phục nhược điểm trên, người ta đưa ra một bộ lọc FIR có cấu trúc mới,
mà trong đó, các hệ số của bộ lọc có thể thay đổi được để có thể thích ứng với sự thay
đổi bất ngờ của các yếu tố lối vào. Mạch lọc FIR có các hệ số thay đổi như vậy được
gọi là mạch lọc FIR thích nghi. Giản đồ khối của mạch lọc như vậy được trình bày
trong hình 9.
Tín hiệu mong muốn
d(n)
+
Tín hiệu vào x[n]
__
h[n]=h0,h1...
+
y[n]
Tín hiệu sai số
e[n]
Hình 9: Giản đồ khối của mạch lọc thích nghi
Trong sơ đồ này, tín hiệu lối vào là một dãy thời gian rời rạc x[n], mạch lọc được
đặc trưng bởi đáp ứng xung h[n], còn tín hiệu lối ra ở thời điểm n là một dãy y[n].
15
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Lối ra này được sử dụng để xác định một đáp ứng mong muốn d[n]. Các hệ số
của mạch lọc phải được chọn lựa sao cho dãy tín hiệu mong muốn có dạng phù hợp
nhất với tín hiệu lối vào. Điều này có thể được thực hiện nếu dãy tín hiệu sai số e[n]
hội tụ về không nhanh nhất. Để làm được điều này, ta phải tối ưu hoá một hàm sai số
được xác định theo phương pháp thống kê hoặc phương pháp quyết định. Đối với
phương pháp thống kê, thì hàm sai số được sử dụng là giá trị toàn phưong trung bình
của tín hiệu sai số e[n]. Nếu tín hiệu vào và tín hiệu mong muốn là những tín hiệu
dừng, thì việc cực tiểu hoá sai số toàn phương trung bình đưa đến một mạch lọc rất nổi
tiếng đó là mạch lọc Wiener, được gọi là tối ưu theo nghĩa toàn phương trung bình.
Hầu hết các thuật toán thích nghi là áp dụng cho các loại mạch lọc Wiener. Trong
phương pháp quyết định, cách chọn hàm sai số là một tổng trọng số của tín hiệu sai số
toàn phương. Việc cực tiểu hoá hàm này dẫn đến một mạch lọc tối ưu đối với dãy dữ
liệu đã cho.
Như vậy, mạch lọc được thiết kế hoặc bằng các công thức thống kê hoặc bằng
các công thức xác định. Trong các thiết kế xác định, cần phải tính toán một số đại
lượng trung bình khi sử dụng dãy dữ liệu đã cho mà mạch lọc cần xử lý. Nói cách
khác, để thiết kế được mạch lọc Wiener cần phải biết trước các tính chất thống kê của
các tín hiệu cơ sở. Trong trường hợp này, các dãy tín hiệu cơ sở thường được cho là tín
hiệu dừng và trung bình theo thời gian bằng trung bình thống kê.
Mặc dù phép đo trực tiếp các giá trị trung bình của tín hiệu có thể được thực hiện
để thu được những thông tin cần thiết cho việc thiết kế mạch lọc Wiener hoặc các
mạch lọc tối ưu, nhưng trong nhiều ứng dụng thực tế, các giá trị trung bình của tín hiệu
lại được sử dụng theo cách gián tiếp, trong đó sai số lối ra của mạch lọc tương quan
với các mẫu của tín hiệu vào của mạch lọc theo một số cách và sử dụng kết quả của
phương trình đệ quy để điều chỉnh các hệ số của mạch theo kiểu lặp.
Sử dụng phương pháp lặp có thể đưa đến các lời giải thích nghi có khả năng tự
hiệu chỉnh. Có nghĩa là nếu các tính chất thống kê của tín hiệu thay đổi đối với thời
gian, thì nhờ nghiệm lặp, các hệ số của mạch lọc có thể tự điều chỉnh để thích nghi
với các tính chất thống kê mới.
Nghiệm lặp, nói chung rất được ưa chuộng vì nó dễ mã hoá trong phần mềm và
dễ thực thi trong phần cứng hơn các nghiệm không lặp.
16
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
3.2. CẤU TRÚC CỦA MẠCH LỌC THÍCH NGHI
Cấu trúc thường được sử dụng trong mạch lọc thích nghi được mô tả như hình
10:
x[n]
z-1
x
wo[n]]
x[n-N+1]
x[n-1]
z-1
z-1
wN-1[n]
w1[n]
x
x
+
x
y[n] -
Thuật toán thích nghi
e[n]
+
+
Hình 10: Cấu trúc của mạch lọc FIR thích nghi
Trong đó:
x[n] : Vector tín hiệu đầu vào của mạch lọc.
x[n] = [xn xn-1
xn-2… xn-N+1]T
w: Là vector trọng số của bộ lọc thích nghi
w = [w0 w1…wN-1]T
y[n] : là lối ra của mạch lọc
N −1
y[n] =
∑w[k ]x[n − k ] wT x[n]
k =0
(3.1)
d[n] : là lối ra mong muốn
e[n] : là sai số giữa tín hiệu mong muốn d[n] và tín hiệu đầu ra y[n]
e[n]=d[n]-y[n]
(3.2)
17
Nguyễn Anh Cường
d[n]
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Bài toán thích nghi sẽ tự điều chỉnh ma trận các trọng số w sao cho sai số e[n] là
nhỏ nhất.
3.3. MẠCH LỌC WIENER FIR
Vì wTx[n] là một vô hướng nên bằng chuyển vị của nó, tức là:wTx[n]=xT[n]w.
Do đó, từ (3.1) và (3.2) ta có:
e[n]=d[n]-y[n]=d[n]-wTx[n]=d[n]-xT[n]w
(3.3)
Đối với mạch lọc Wiener, hàm hiệu năng được chọn là sai số toàn phương trung
bình:
J= E[|e[n]|2]
(3.4)
Trong đó ký hiệu E[.] là kỳ vọng thống kê. Thay (3.3) vào (3.4) ta được:
J= E[(d[n]-wTx[n])(d[n]-xT[n]w)]
(3.5)
Khai triển (3.5) và chú ý w có thể đưa ra ngoài toán tử E[.] vì nó không phải là
biến số thống kê, ta thu được:
J=E[d2[n]]–wTE[x[n]d[n]]– E[d[n]xT[n]]w + wTE[x[n]xT[n]]w
(3.6)
Ta định nghĩa vector tương quan chéo bậc Nx1:
P = E[x[n]d[n]] = [P0 P1 … PN-1 ] T
(3.7)
Và ma trận tương quan:
T
R=E[x[n]x [n]] =
R00
R01
R02
……
R0 N-1
R10
R11
R12
……
R1 N-1
..
……
….
..
….
….
.....
….
…
..
..
..
..
..
..
RN-1 0 RN-1 1 RN-1 2
18
……
(3.8)
RN-1 N-1
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Chú ý là: E[d[n]xT[n]] = PT; wTP = PTw, ta thu được:
J = E[d2[n]] – 2wTP + wTRw
(3.9)
Để thu được táp trọng số ứng với hàm phí tổn J có giá trị cực tiểu, ta cần phải
giải hệ phương trình được tạo thành từ đạo hàm bậc nhất của J đối với mỗi táp trọng số
wi bằng không, tức là:
∂J
=0
∂wi
, với i = 0,1,2…N-1
(3.10)
Các phương trình trên có thể viết dưới dạng ma trận:
∇J = 0
(3.11)
ở đây ∇ là toán tử vi phân được xác định như một vectơ cột:
∇=
∂
∂ w[0]
∂
∂ w[1]
.
.
.
∂
∂ w[ N − 1]
(3.12)
Để tìm các đạo hàm riêng của J đối với các táp trọng số w i của mạch lọc, trước
hết phải khai triển hệ thức (3.9) thành dạng tường minh:
N −1
J = E[d [n]] – 2 ∑P[ k ]w[ k ]
2
k =0
N −1 N −1
+ ∑∑w[k ]w[ m]R[k , m]
k =0 m =0
(3.13) Tổng kép trong (3.13) có thể khai triển dưới dạng:
N −1 N −1
N −1 N − 1
N −1
k =0 m =0
k = 0 m− 0
k #i m #i
k =0
k #i
∑∑w[k ]w[m]R[k , m] = ∑ ∑ w[k ]w[m]R[k , m] +wi ∑w[k ]R[k , i] +wi
N −1
∑w[m]R[k , m] +wi2R[k,i]
m =0
m #k
(3.14)
19
Nguyễn Anh Cường
ĐH Công Nghệ- ĐHQG Hà Nội
Khoá luận tốt nghiệp
Thay (3.14) vao` (3.13), sau đó lấy đạo hàm riêng phần của J theo w i và thay
thế m cho k ta được:
∂J
∂w[i ]
N −1
= -2Pi +
∑w[k ]( R[k , i] + R[i, k ] )
, với i=0,1,2,…,N-1
k =0
(3.15)
Trong trường hợp này ta thấy:
Rki = E[x[n-k]x[n-i]] = Φxx[i-k]
(3.16)
ở đây Φxx[i-k] là hàm tự tương quan của x[n]
Tương tự:
Rik = Φxx[k-i]
(3.17)
Do tính chất đối xứng của hàm tự tương quan nên Φxx[k] =Φxx[-k], ta thu được:
Rki = Rik
(3.18)
Thay (3.18) vào phương trình (3.15) ta được:
∂J
∂w[i ]
N −1
= -2Pi + 2
∑R[i, k ]w[k ] , với i = 0,1,2…,N-1
k =0
(3.19)
Phương trình trên có thể biểu diễn dưới dạng ma trận:
∇J = 2Rw – 2P
(3.20)
Đặt ∇J=0 ta sẽ thu được phương trình tối ưu hoá táp trọng số của mạch lọc
Wiener
Rwo = P
(3.21)
Đây là phương trình Wiener-Hopf đối với vetor trọng số tối ưu wo:
wo = R-1P
(3.22)
Thay giá trị wo vừa tìm được từ phương trình Wiener-Hopf và Rw o=P vào
phương trình (3.9) ta sẽ tìm được giá trị cực tiểu của hàm phí tổn J:
20
Nguyễn Anh Cường
- Xem thêm -