MỞ ĐẦU Trong các hệ thống truyền thông, tốc độ lỗi bit (BER) là thông số quan trọng nhất trong việc đánh giá hiệu suất của hệ thống. Thuật toán Monte Carlo trở thành công cụ mô phỏng hiệu quả các thông số này. Tuy nhiên, với các hệ thống phức tạp trên thực tế, phương pháp Monte Carlo cổ điển trở nên bất lợi, do thời gian cần để thực hiện một mô phỏng và đạt được một ước lượng đáng tin cậy về hiệu suất của hệ thống thường rất dài. Việc ước lượng các sự kiện có xác suất lỗi thấp, hay các sự kiện hiếm bằng cách sử dụng trực tiếp các kỹ thuật mô phỏng Monte Carlo thường đòi hỏi số lần thực hiện rất lớn.
Một phương pháp mới dựa trên kỹ thuật Monte Carlo đã chỉnh sửa, gọi là kỹ thuật lấy mẫu theo trọng số (IS) đã được các nhà nghiên cứu đề xuất và đưa vào sử dụng trong nhiều năm qua. IS là kỹ thuật có khả năng cải thiện thời gian chạy mô phỏng trên máy tính, và cung cấp một ước lượng BER thu được có phương sai nhỏ hơn ước lượng theo kỹ thuật MC có thời gian mô phỏng tương đương. Nhận thức được những bất lợi của phương pháp mô phỏng Monte Carlo và hiệu quả của kỹ thuật lấy mẫu theo trọng số trong việc đánh giá hiệu suất của hệ thống truyền thông số, em chọn viết khóa luận tốt nghiệp với đề tài: "Phƣơng pháp mô phỏng nhanh và một vài áp dụng". Khóa luận gồm 4 chương với những nội dung sau: Chƣơng 1: Tổng quan Chƣơng 2: Mô phỏng Monte Carlo nhanh Chƣơng 3: Ứng dụng của kỹ thuật IS Chƣơng 4: Kết quả mô phỏng Đây là vấn đề tương đối khó và đang được nghiên cứu rộng rãi, do kiến thức còn hạn hẹp, khóa luận này không tránh khỏi những thiếu sót.
Em rất mong nhận được sự đánh giá, góp ý của các thầy cô giáo, các bạn sinh viên và những người quan tâm đến nội dung của bản khóa luận này. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1 TỔNG QUAN 1. Vai trò của việc đánh giá BER trong các hệ thống viễn thông Trong các hệ thống truyền thông số, tốc độ lỗi bit (BER) là thông số quan trọng nhất trong việc đánh giá chất lượng của đường truyền dữ liệu. Khi truyền qua hệ thống, tín hiệu có thể bị lỗi trong quá trình truyền, làm cho tín hiệu thu được bị sai lệch so với tín hiệu ban đầu.
BER của một hệ thống có thể được định nghĩa là xác suất ước lượng bit bị lỗi khi truyền qua hệ thống, nghĩa là nếu phát đi bit 1, nơi thu sẽ nhận được bit 0 và ngược lại. Trong các thử nghiệm thực tế, BER được đo bằng việc phát các bit qua hệ thống và đếm số bit lỗi thu được. Tỉ số của số bit lỗi thu được trên tổng số bit truyền đi được gọi là BER. Ví dụ, tốc độ lỗi bit của hệ thống là 10-6, nghĩa là khi truyền 106 bit dữ liệu qua kênh truyền, sẽ xuất hiện 1 bit lỗi tại nơi thu.
Chất lượng của ước lượng BER tăng khi tổng số bit được phát đi tăng. Tỷ số BER là phép đo cơ bản nhất về hiệu suất của hệ thống, do vậy chất lượng của hệ thống hầu hết được xác định bằng việc đánh giá BER. Đây là một trong những vấn đề chính trong việc nghiên cứu, thiết kế các đường truyền và mạng viễn thông. Việc áp dụng các kỹ thuật phân tích để đánh giá hiệu suất của các hệ thống truyền thông số phức tạp là rất khó và yêu cầu mô hình hệ thống phải được đơn giản hóa.
Mặt khác, việc xây dựng các cấu trúc phần cứng thường tốn rất nhiều thời gian, chi phí, và không có tính linh hoạt. Do vậy, các phương pháp mô phỏng trên máy tính, đặc biệt là phương pháp Monte Carlo trở thành công cụ hiệu quả trong việc ước lượng hiệu suất BER của hệ thống. Vai trò mô phỏng Monte Carlo để ƣớc lƣợng BER 1. Vai trò mô phỏng Monte Carlo Trong các hệ thống truyền thông số phức tạp, kỹ thuật mô phỏng Monte Carlo được dùng để đánh giá hiệu suất BER.
Các hệ thống ngày nay hoạt động 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com trong các môi trường được đặc trưng bởi nhiễu ISI, sự không tuyến tính, tính đa đường, fading, và hàng loạt ảnh hưởng khác. Do vậy, mô phỏng MC trở thành một phương pháp khả thi đối với các hệ thống thực tế. Tính linh hoạt và khả năng miêu tả các đặc tính của hệ thống không thể thực hiện bằng các kỹ thuật phân tích, trở thành hai lý do chính của việc áp dụng rộng rãi phương pháp MC. Nhắc lại một số khái niệm cơ bản [1] 1.
Tần xuất tƣơng đối Ước lượng MC là quá trình ước lượng giá trị của một thông số bằng cách thực hiện một thí nghiệm ngẫu nhiên và dựa trên khái niệm tần xuất tương đối của xác suất. Trong việc định nghĩa tần xuất tương đối, trước tiên phải xác định rõ thí nghiệm ngẫu nhiên và sự kiện đáng quan tâm. Theo lý thuyết xác suất, kết quả của thí nghiệm ngẫu nhiên không thể được dự đoán chính xác, nhưng có thể được xác định thống kê. Thí nghiệm ngẫu nhiên cơ bản nhất là tung một đồng xu, sẽ có 2 khả năng xảy ra {ngửa, sấp}.
Nếu đồng xu là cân bằng (unbias) hoặc nhất quán (consistent), thì mỗi sự kiện trong tập {ngửa, sấp} xảy ra với xác suất bằng nhau và các kết quả là độc lập. Xét ví dụ một hệ thống truyền thông số, thí nghiệm ngẫu nhiên là việc truyền một bit nhị phân 1, và sự kiện quan tâm là lỗi xảy ra trong quá trình truyền. Kết quả tại lối ra của bộ thu là một ước lượng của ký hiệu nhị phân được phát đi, sẽ là bit 0 hoặc 1. Việc xác định BER của hệ thống liên quan tới việc ước lượng xác suất có điều kiện của việc nhận được bit 0 khi bit 1 được phát đi.
Trong phương pháp MC, thí nghiệm ngẫu nhiên được thực hiện với số lần N rất lớn. Ta đếm số lần NA tương ứng với sự kiện A cần quan tâm. Xác suất của sự kiện A được xấp xỉ bằng tần xuất tương đối của sự kiện: Pr( A) lim N A (1.1) N N Trong việc ước lượng xác suất lỗi trong hệ thống truyền số, N là tổng số bit hoặc ký hiệu (được truyền qua hệ thống hoặc được mô phỏng) và NA là số lỗi (được 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com đo hoặc được mô phỏng). Với N < , NA/N là một ước lượng của Pr(A).
Ước lượng này được biểu diễn là P̂r( A). Do thí nghiệm là ngẫu nhiên, với N hữu hạn, NA sẽ là biến ngẫu nhiên, và do đó, P̂r( A) là một biến ngẫu nhiên. Thống kê của biến ngẫu nhiên này xác định độ chính xác của ước lượng và chất lượng của việc mô phỏng. Các ƣớc lƣợng cân bằng Để trở nên hữu dụng, các ước lượng MC phải thoả mãn đặc tính cân bằng.
Đó là, nếu  là ước lượng của A, thì E{  } = A. Nói cách khác, tính trung bình, ta thu được kết quả đúng. Giả sử rằng mô phỏng MC được thực hiện một số lần, tạo ra một tập các ước lượng của biến ngẫu nhiên cần quan tâm. Rõ ràng, chúng ta mong muốn các ước lượng này có một phương sai nhỏ.
Nếu các ước lượng là cân bằng và có phương sai nhỏ, việc ước lượng sẽ tạo ra các ước lượng mà hợp lại thành giá trị đúng của thông số cần được ước lượng, và khoảng cách giữa các ước lượng sẽ nhỏ. Việc xác định phương sai của ước lượng MC theo phân tích là một nhiệm vụ khó, trừ khi các sự kiện là độc lập thống kê. Tuy nhiên, phương sai của các giá trị được ước lượng giảm khi độ dài chạy mô phỏng (số lần lặp lại thí nghiệm ngẫu nhiên) tăng. Các ước lượng thỏa mãn đặc tính này là nhất quán.
Đối với các ước lượng nhất quán, 2Â 0 khi N , trong đó N là số lần lặp lại thí nghiệm ngẫu nhiên. Với các ước lượng cân bằng và nhất quán, lỗi e = A - Â có trị trung bình bằng 0, và phương sai lỗi e2 hội tụ tới 0 khi N . Tích phân Monte Carlo Giả sử ta muốn đánh giá tích phân: 1 I g ( x)dx (1.2) 0 trong đó g(x) là hàm bị giới hạn trên dải tích phân. Từ lý thuyết xác suất cơ bản, giá trị kỳ vọng (trung bình toàn bộ) của hàm g(x) là: 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3) trong đó fX(x) là hàm mật độ xác suất của biến ngẫu nhiên X.
Nếu hàm mật độ của X thỏa mãn fX(x) = 1 trong khoảng (0,1) và bằng 0 ở khoảng khác, thì E{g(X)} = I. Cho U là biến ngẫu nhiên có phân bố đồng nhất trong khoảng (0,1) thì: I = E{g(U)} (1.4) Sử dụng các argument tần xuất tương đối, có thể viết: 1 N lim g (U i ) Eg (U ) I (1.5) N N i 0 Do vậy, ta mô phỏng tích phân để lấy mẫu hàm số tại N điểm trong khỏang (0,1). Giá trị trung bình của các mẫu cung cấp một ước lượng cho giá trị của tích phân. Nếu việc lấy giới hạn trong (1.5) bị sai, việc xấp xỉ các kết quả luôn được thực hiện trong các ứng dụng thực tế.
Biểu diễn sự xấp xỉ này bởi Iˆ tạo ra: 1 N g (U i ) Iˆ (1.6) N i 0 đối với các ước lượng MC của tích phân. Nói tóm lại, ước lượng cho tích phân được thực hiện bằng việc đánh giá hàm g(x) tại N điểm ngẫu nhiên phân bố đồng nhất và lấy trung bình. Quá trình có thể được áp dụng cho bất kỳ tích phân nào. Áp dụng cho hệ thống truyền thông Để ước lượng hiệu suất của một hệ thống truyền thông số sử dụng mô phỏng MC, N ký hiệu được truyền qua hệ thống và đếm số lỗi truyền N e.
Ước lượng của xác suất lỗi là: Ne Pˆ E N (1.7) Giả sử môi trường kênh là AWGN (nhiễu Gauss trắng cộng tính). Các sự kiện lỗi xuất hiện do nhiễu kênh là độc lập và số lỗi Ne trong quá trình truyền N ký hiệu được miêu tả bằng phân bố nhị thức: 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.9) k k!( N k )! là hệ số nhị thức và PE là xác suất lỗi trong một lần truyền. Trị trung bình và phương sai của biến ngẫu nhiên có phân bố nhị thức là: E{Ne} = NPE (1.11) Sử dụng các kết quả trong (1.