Tài liệu Phương pháp mô phỏng nhanh và một vài áp dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thái Hà PHƯƠNG PHÁP MÔ PHỎNG NHANH VÀ MỘT VÀI ÁP DỤNG LUẬN VĂN THẠC SĨ Hà Nội – 2006 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thái Hà PHƯƠNG PHÁP MÔ PHỎNG NHANH VÀ MỘT VÀI ÁP DỤNG Ngành Chuyên ngành Mã số : Kỹ thuật điện tử - viễn thông : Kỹ thuật vô tuyến điện tử và thông tin liên lạc : 2.07.00 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. HUỲNH HỮU TUỆ Hà Nội – 2006 MỤC LỤC Trang phụ bìa Trang Mục lục Danh mục các ký hiệu, các chữ viết tắt Danh mục các bảng, hình vẽ, đồ thị MỞ ĐẦU .................................................................................................................. 1 Chương 1 – TỔNG QUAN .................................................................................... 2 1.1. Vai trò của việc đánh giá BER trong các hệ thống viễn thông ...................... 2 1.2. Vai trò mô phỏng Monte Carlo để ước lượng BER ...................................... 2 1.2.1. Vai trò mô phỏng Monte Carlo .............................................................. 2 1.2.2. Nhắc lại một số khái niệm cơ bản .......................................................... 3 1.2.2.1. Tần xuất tương đối .................................................................... 3 1.2.2.2. Các ước lượng cân bằng ............................................................ 4 1.2.2.3. Tích phân Monte Carlo .............................................................. 4 1.2.2.4. Áp dụng cho hệ thống truyền thông .......................................... 5 1.3. Nhu cầu mô phỏng nhanh .............................................................................. 7 1.3.1. Định nghĩa sự kiện hiếm .......................................................................... 7 1.3.2. Vai trò của mô phỏng Monte Carlo nhanh .............................................. 8 Chương 2 – MÔ PHỎNG MONTE CARLO NHANH ...................................... 10 2.1. Nguyên lý cơ bản của kỹ thuật lấy mẫu theo trọng số................................. 10 2.2. Mô hình hệ thống truyền thông số đơn giản ................................................ 11 2.3. Phương pháp lấy mẫu theo trọng số ............................................................ 13 2.3.1. Hệ thống tuyến tính không nhớ ........................................................... 14 2.3.2. 2.4. Hệ thống tuyến tính có nhớ .................................................................. 17 Sự thay đổi các quá trình ngẫu nhiên lối vào............................................... 22 2.4.1. Lấy mẫu theo trọng số thông thường ................................................... 22 2.4.2. Lấy mẫu theo trọng số cải tiến ............................................................. 29 Chương 3 – ỨNG DỤNG CỦA KỸ THUẬT IS ................................................. 32 3.1. Kênh fading ................................................................................................. 32 3.2. Áp dụng IS cho kênh fading ........................................................................ 33 3.2.1. Mô hình hệ thống ................................................................................. 33 3.2.2. Phương pháp IS cho kênh fading ......................................................... 34 3.2.3. Áp dụng IS trong kênh fading Rayleigh .............................................. 36 3.2.3.1. Phương pháp IS ....................................................................... 36 3.2.3.2. Tính ứng dụng của kỹ thuật IS ................................................ 39 Chương 4 – KẾT QUẢ MÔ PHỎNG ................................................................. 45 KẾT LUẬN ............................................................................................................ 52 TÀI LIỆU THAM KHẢO .................................................................................... 53 PHỤ LỤC ............................................................................................................... 55 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ATM Asynchronous Tranfer Mode AWGN Additive White Gauss Noise BER Bit Error Rate CIS Conventional Importance Sampling IID Identical Independent Distribution IIS Improved Importance Sampling IS Importance Sampling ISI InterSymbol Interference MC Monte Carlo PDF Probability Density Function SNR Signal to Noise Ratio STC System Threshold Characteristic DANH MỤC CÁC BẢNG, HÌNH VẼ, ĐỒ THỊ Hình 2.1. Mô hình hệ thống truyền thông số nhị phân băng gốc cơ sở Hình 2.2. Mô hình mô phỏng sử dụng kỹ thuật IS Hình 2.3. Phương pháp bias hàm mật độ xác suất Hình 2.4. Hàm mật độ xác suất f(x) gốc và f*(x) CIS theo x Hình 2.5. Hàm mật độ xác suất f(x) gốc và f**(x) mới của IIS theo x Hình 3.1. Mô hình hệ thống truyền thông số trong kênh fading Hình 3.2. Sơ đồ khối của một hệ thống tương đương băng gốc Hình 3.3. Đặc tính ngưỡng hệ thống (STC) Hình 3.4. STC và pdf fN(n) cho kênh AWGN Hình 3.5. STC và fN(n) cho kênh fading Rayleigh không chọn lọc tần số Hình 4.1. Mô phỏng BER của hệ thống sử dụng kỹ thuật CIS với N = 2000 mẫu Hình 4.2. Mô phỏng BER của hệ thống sử dụng kỹ thuật CIS với N = 5000 mẫu Hình 4.3. IIS là hàm của c với Eb/N0 khác nhau Hình 4.4. Pb là hàm của c với Eb/N0 khác nhau Bảng 1: Lợi thế của CIS so với MC và IIS so với CIS trong hệ thống không có tín hiệu. Bảng 2: Các thông số CIS σ*(j;opt) và IIS cj(opt) tối ưu đối với hệ thống có ISI và M = 3. Bảng 3 : Lợi thế của CIS so với MC và IIS so với CIS trong hệ thống có ISI với M = 3. Bảng 4: Các mẫu của BER theo mô phỏng CIS và IIS với ISI và M = 3 (N = N**). Bảng 5 : Kích cỡ mẫu NIS so với xác suất lỗi Pe trong hệ thống không tuyến tính có nhớ Bảng 6 : Thời gian mô phỏng giảm khi sử dụng kỹ thuật IS Bảng 7. So sánh kênh fading Rayleigh có chọn lọc và không chọn lọc theo thời gian Bảng 8. Hiệu suất IS cho kênh fading không chọn lọc theo thời gian 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 CHƢƠNG 1 TỔNG QUAN 1.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. 1.2. Vai trò mô phỏng Monte Carlo để ƣớc lƣợng BER 1.1.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 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. 1.1.2. Nhắc lại một số khái niệm cơ bản [1] 1.1.2.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 N N (1.1) 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 đ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. 1.1.2.2. 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  . 1.1.2.3. 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  Eg ( X )  g ( x) f X ( x)dx (1.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 )  Eg (U ) I N   N i 0  (1.5) 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ˆ N i 0 (1.6) đố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. 1.1.2.4. Á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 N N p N ( N e)    PEN e (1P E ) N e  Ne trong đó: N N!     k  k!( N  k )! (1.8) (1.9) 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.10)  2N e = NPE(1-PE) (1.11) Sử dụng các kết quả trong (1.7), trị trung bình của ước lượng MC cho xác suất lỗi là: EPˆ E EN e N (1.12) N PE  PE N (1.13) Thay thế (1.10) vào (1.12): EPˆ E Chứng tỏ ước lượng MC của xác suất lỗi là cân bằng. Phương sai của ước lượng MC cho xác suất lỗi:  Pˆ E  2  2N e (1.14) N2 Thay (1.11) vào (1.14):  2Pˆ E  PE (1 PE ) N (1.15) chứng tỏ ước lượng là nhất quán, do phương sai giảm khi N  . Trong việc sử dụng mô phỏng MC để ước lượng hiệu suất của hệ thống truyền thông, như xác suất lỗi ký hiệu, rõ ràng các ước lượng cân bằng và nhất quán là điều mong muốn. Nếu một ước lượng là cân bằng, thì tính giá trị trung bình, mô phỏng MC cho một kết quả đúng. Thêm vào đó, nếu một ước lượng là hữu ích, nó phải là phương sai nhỏ, để với xác suất cao, ước lượng nằm gần giá trị thực cần 6 được ước lượng. Nếu một ước lượng là cân bằng và nhất quán, thì việc mô phỏng quá trình truyền ký hiệu nhiều lần, để có nhiều lỗi được đếm trong một lần truyền, làm giảm phương sai của ước lượng. Phương trình (1.15) gợi cho ta biết số lỗi phải được đếm cho một ước lượng để có một phương sai cho trước và điều này ngược lại, cho chúng ta biết về thời gian cần thiết để thực hiện một mô phỏng. Tuy nhiên, (1.15) không thể dùng để xác định giá trị N cần thiết cho một phương sai cho trước do PE chưa được biết trước khi thực hiện mô phỏng. Trong nhiều vấn đề thực tế, chúng ta có thể xác định PE bằng cách áp dụng các giới hạn hoặc các công cụ phân tích khác. Các ước lượng bị lệch và nhất quán hội tụ tới một giá trị sai, rõ ràng là một tình huống không mong muốn trừ khi chúng ta biết cách loại bỏ độ lệch. Mặc dù với các đặc tính của bộ ước lượng, nhưng trong nhiều trường hợp, việc chứng tỏ rằng một ước lượng được cho là cân bằng và nhất quán là một nhiệm vụ khó. Các kết quả thu được trong phần này là hợp lý nếu các lỗi gây ra do nhiễu kênh là độc lập để phân bố lỗi cơ sở là nhị thức. Nếu các lỗi là tương quan, như trong kênh có băng tần giới hạn, các kết quả đưa ra ở đây không còn hợp lý nữa, và chúng ta phải đương đầu với một vấn đề khó hơn nhiều. 1.3. Nhu cầu mô phỏng nhanh 1.3.1. Định nghĩa sự kiện hiếm Các sự kiện hiếm thường được bắt gặp nhiều trong các công trình khoa học và kỹ thuật. Ví dụ như vật liệu bị gãy do sức nặng trong các công trình kiến trúc, sự vượt quá các cấp độ nguy hiểm trên dòng nước, tới những nhận định sai về mục tiêu trong các hệ thống radar, xác suất mất mát tế bào ở dải 10-6 tới 10-12 trong mạng ATM do tràn bộ đệm, v.v… [2]. Trong các hệ thống truyền thông số, đó là xác suất lỗi bit qua các tuyến vệ tinh sử dụng mã sửa lỗi được yêu cầu thấp tới 10-10, hay xác suất báo động giả của các bộ thu radar và sonar bắt buộc không vượt quá giá trị 106 . Các sự kiện này tuy có xác suất lỗi thấp, nhưng cũng đặc biệt quan trọng, do sự xuất hiện của chúng có thể gây ra những ảnh hưởng và biến đổi trong hệ thống. Vì vậy, đặc tính của các sự kiện hiếm cũng cần phải được nghiên cứu, và mô phỏng 7 trên máy tính là công cụ mạnh được dùng để đánh giá xác suất lỗi của những sự kiện đó. 1.3.2. Vai trò của mô phỏng Monte Carlo nhanh Phương pháp MC có thể áp dụng cho tất cả các hệ thống mà không cần quan tâm tới kiến trúc hay độ phức tạp, nhưng có một trở ngại quan trọng. Vấn đề cơ bản với phương pháp MC đó là 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. Đặc biệt, trong hầu hết các hệ thống truyền thông số phức tạp trong thực tế với nhiễu ngẫu nhiên và sự không tuyến tính, không thể tính được chính xác xác suất lỗi bằng cách phân tích. 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 MC cổ điển thường đòi hỏi số lần thực hiện rất lớn. Do một số lượng lớn các mẫu cần được đếm trong quá trình mô phỏng để quan sát lỗi tại lối ra hệ thống, đặc biệt khi các tỷ số SNR là cao. Trong các hệ thống truyền thông số thực tế, thời gian mô phỏng tỷ lệ nghịch với giá trị BER. Ví dụ, để ước lượng BER khoảng 10-6 hoặc thấp hơn, với độ chính xác là 10%, thì kích cỡ mẫu cần trong mô phỏng máy tính thường là 108 hoặc nhiều hơn để thu được giá trị ước lượng. Nhưng điều này là không thể chấp nhận được vì nó đòi hỏi thời gian chạy mô phỏng lên tới vài ngày. Từ những hạn chế của kỹ thuật MC cổ điển, cần tìm ra một phương pháp để có thể mô phỏng những hệ thống có xác suất lỗi thấp, đồng thời đảm bảo thời gian thực hiện ngắn. Một phương pháp dựa trên kỹ thuật MC đã chỉnh sửa, gọi là kỹ thuật lấy mẫu theo trọng số (IS) được nghiên cứu và sử dụng. 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. Kỹ thuật IS đã được áp dụng trong rất nhiều lĩnh vực, như truyền thông sợi quang, vệ tinh, các kênh không tuyến tính và không có dạng Gauss, ước lượng hiệu suất của các hệ thống tính toán có độ tin cậy cao, lý thuyết xếp hàng, thuật toán dò 8 ứng dụng trong các hệ thống radar và sonar, báo động giả, các kênh fading và các vấn đề khác trong truyền thông số. Nghiên cứu về phương pháp IS và các ứng dụng mới vẫn đang được tiếp tục, đặc biệt khi các hệ thống kỹ thuật trở nên phức tạp hơn và độ tin cậy ngày càng tăng. 9 CHƢƠNG 2 MÔ PHỎNG MONTE CARLO NHANH 2.1. Nguyên lý cơ bản của kỹ thuật lấy mẫu theo trọng số Xét một thí nghiệm ngẫu nhiên được thực hiện với số lần N lớn, NA là số lần xảy ra sự kiện A cần quan tâm. Có thể ước lượng xác suất của sự kiện A sử dụng phương trình [1]: Pr( A)  lim N A N N (2.1) Giả sử NA biểu diễn số lỗi trong quá trình truyền N ký hiệu, trong nhiều trường hợp, yêu cầu về NA lớn có thể dẫn tới số lần thực hiện mô phỏng dài. Điều này đặc biệt đúng khi BER của một hệ thống truyền thông là thấp. Nếu BER nhỏ, lỗi giải điều chế được mô phỏng là hiếm (xác suất xảy ra thấp) nhưng là sự kiện quan trọng. Các sự kiện hiếm cũng được xác định trên đuôi của hàm mật độ xác suất. Chúng có xác suất nhỏ và xảy ra không thường xuyên trong các ứng dụng thực tế hoặc trong mô phỏng. Mục đích của kỹ thuật lấy mẫu theo trọng số (IS) là thay đổi mô phỏng để tăng số sự kiện quan trọng hoặc hiếm này, trong khi vẫn có thể xác định đúng xác suất lỗi của hệ thống. Điều này đòi hỏi sự thay đổi trong (2.1). Lấy mẫu theo trọng số (IS) là kỹ thuật giảm phương sai, với mục đích phát triển một ước lượng cân bằng, thể hiện sự giảm phương sai hoặc giảm thời gian thực hiện mô phỏng khi so sánh với mô phỏng MC. Nguyên lý cơ bản của IS là làm cho các sự kiện có xác suất thấp xảy ra thường xuyên hơn bằng cách thay đổi (hay bias (làm lệch)) hàm mật độ xác suất (pdf) của quá trình ngẫu nhiên lối vào, để các lỗi này có thể được đếm nhanh hơn, và có thể thực hiện mô phỏng các sự kiện này mà không cần một số lượng lớn các mẫu. Mỗi sự kiện sau đó được lấy trọng số phù hợp, và tính tổng lại, để cung cấp một ước lượng cân bằng của xác suất sự kiện hiếm. Nói chung, hiệu suất của IS phụ thuộc vào việc chọn lựa hàm pdf và các tham số của hàm pdf. Phương pháp này được gọi là “lấy mẫu theo trọng số”, do các phân bố mô phỏng để cực tiểu hóa 10 phương sai ước lượng có xu hướng làm tăng tần xuất tương đối của các sự kiện “quan trọng”. 2.2. Mô hình hệ thống truyền thông số đơn giản Để nghiên cứu các kỹ thuật lấy mẫu theo trọng số trong việc mô phỏng MC thông số BER, xét một hệ thống truyền thông số nhị phân tương đương băng gốc đơn giản có nhớ như trên hình 2.1 [4]: n(t) g(.) s (t ) Sampler Yk Hình 2.1. Mô hình hệ thống truyền thông số nhị phân băng gốc cơ sở Giả sử lối vào s(t) của hệ thống có dạng: s(t )   ai p(t iT ) (2.2) i Dạng sóng x(t) được biểu diễn: x(t )  s(t)  n(t ) (2.3) trong đó: Dữ liệu thông tin ai có thể nhận các giá trị A hoặc –A với cùng một xác suất, tùy thuộc lối vào là bit 0 hoặc 1. T là thời khỏang bit. p(t) là hàm xung cửa có giá trị 1 trên đoạn [0, T] và giá trị 0 tại các điểm khác. n(t) là quá trình nhiễu Gauss trắng có trị trung bình bằng 0 và mật độ phổ công suất 2 phía là N0/2. Xác suất lỗi Pe trong hệ thống có thể được ước lượng thông qua mô phỏng MC như sau. Ta phát các giá trị lấy mẫu của các quá trình ngẫu nhiên S(t) và n(t) sử 11 dụng các bộ phát số ngẫu nhiên và tạo ra các giá trị lấy mẫu của X(t). Dãy các giá trị lấy mẫu của X(t), biểu diễn là Xk, dùng làm lối vào của hệ thống và lối ra là các giá trị lấy mẫu Yk của Y(t) đạt được qua các mô hình kênh không tuyến tính có nhớ và bộ lọc. Dãy {Yk} được lấy mẫu tại tốc độ bit 1/Tb của hệ thống, và đem so sánh Yk với một ngưỡng để xác định bit lối ra. Sau đó, so sánh dãy bit được phát (đã được biết) với lối ra bộ thu để biết tổng số lỗi trong hệ thống. Trong hình 2.1, tín hiệu y(t) được lấy mẫu trong mỗi chu kỳ T(s), do đó, lối ra của bộ lấy mẫu được biểu diễn là {Yk}: Y k  g ( X k , X k 1, ... , X k ( M 1)) trong đó: (2.4) g(.) là đáp ứng của hệ thống M là chiều dài nhớ {Xk} là một dãy ngẫu nhiên độc lập: Xk = A k + N k (2.5) với Ak nhận giá trị A (dưới H1) hoặc –A (dưới H0) với xác suất như nhau, Nk là một dãy Gauss iid (phân bố độc lập đồng nhất) có giá trị trung bình bằng 0 và phương sai  2  N0/ 2 . Xác suất lỗi của hệ thống là:  Pe   f ( y)dy (2.6) T0 trong đó T0 là ngưỡng quyết định, f(y) là pdf lối ra của bộ thu. Với giả thiết Ak nhận giá trị A hoặc –A với xác suất như nhau, tính đối xứng của mật độ nhiễu, và tính đối xứng của hàm g(.), ta có thể đặt T0 = 0, BER của hệ thống là:  Pe   h( y ) f ( y )dy (2.7)  trong đó, h(y) là hàm chỉ thị nhận giá trị 1 với y  0 và bằng 0 với y < 0. Ta đã biết các đặc tính thống kê của dãy lối vào và mô hình hệ thống chi tiết. Để ước lượng xác suất lỗi Pe, cần ước lượng hàm mật độ xác suất lỗi fˆ 12 Yk ( y) của dãy lối ra Yk tại thời điểm lấy mẫu tương ứng với lối vào đã biết trước ak = -A. Xác suất lỗi ước lượng được tính như sau :  Pˆ e   fˆ Y k ( y)dy T (2.8) 0 trong đó T0 là ngưỡng quyết định. Số mẫu cần thiết dùng để ước lượng Pe được tính trực tiếp là [3]: N 1 (2.9)  P 2 e trong đó  là lỗi chuẩn hóa của Pˆ e được ước lượng.  đô lêch chuân cua P̂e (2.10) Pe Việc giảm kích cỡ mẫu có thể thực hiện được bằng cách thay đổi (hoặc làm lệch) các đặc tính thống kê của dãy lối vào để tăng tốc độ lỗi xảy ra trong quá trình mô phỏng. Nói chung, lỗi bị gây ra do các mẫu nhiễu có biên độ lớn, nên việc sử dụng nhiều lỗi hơn trong quá trình mô phỏng cho ta một ước lượng tổng số lỗi tốt hơn. Tuy nhiên, phải chỉnh sửa thích hợp tổng số lỗi để thu được một ước lượng cân bằng của xác suất lỗi thực. 2.3. Phƣơng pháp lấy mẫu theo trọng số Trong nhiều vấn đề mô phỏng Monte Carlo, xuất hiện các sự kiện lỗi liên quan với xác suất xảy ra thấp. Ví dụ, với BER bằng 10-6, tính trung bình chỉ có một sự kiện lỗi trong 106 sự kiện được mô phỏng. Do vậy, trong phần lớn thời gian, các sự kiện được mô phỏng là ngoài tầm quan trọng. Trong phương pháp lấy mẫu theo trọng số cho mô phỏng Monte Carlo, các quá trình ngẫu nhiên lối vào được chỉnh sửa để cho các sự kiện đáng quan tâm xảy ra thường xuyên hơn. Tất nhiên, các giá trị kết hợp với các sự kiện ngẫu nhiên này cũng phải được thay đổi để các kết quả mô phỏng thu được qua phương pháp lấy mẫu theo trọng số giống với các kết quả trong mô phỏng gốc. 13 2.3.1. Hệ thống tuyến tính không nhớ Xét một hệ thống tuyến tính không nhớ, xác suất lỗi cần ước lượng Pe trong (2.7) có thể được viết lại như sau [4]:  Pe   h( y)  f ( y) * f ( y)  f *( y)dy   h*( y) f *( y)dy (2.11)  f*(y) là pdf mới của Y, được tạo ra bằng cách làm lệch các mẫu lối vào, và bây giờ Pe được ước lượng bởi: Pˆ e  1 N *  h ( yi ) N i 1 (2.12) trong đó {yi} là dãy lối ra tại các thời gian lấy mẫu bit được sinh ra từ dãy lối vào f *( y ) được làm lệch. Tỉ số được gọi là độ lệch của biến ngẫu nhiên lối ra Y tại Y f ( y) = y. Sau đây ta xét sự thay đổi của quá trình ngẫu nhiên lối vào. Mô hình mô phỏng IS được biểu diễn như trên hình vẽ sau: s yk n f 1 ( n) Kỹ thuật bias IS g(s,n) Ước lượng IS Pˆ e f 1*( n) Hình 2.2. Mô hình mô phỏng sử dụng kỹ thuật IS Trong mô phỏng MC chuẩn, một dãy các số ngẫu nhiên độc lập được phát đi, mỗi số được phân bố theo hàm pdf fX(x) của X. Lối ra của hệ thống là một dãy các mẫu độc lập của Y, từ đó ta có thể xây dựng được một ước lượng pdf của Y ở dạng histogram. Bây giờ, nếu pj là xác suất mà lối ra Y sẽ ở trong khỏang [yj-1, yj] thì ước lượng cân bằng của pj là [6]: Nj N  N pˆ j  lim trong đó: nj là số mẫu trong thời khỏang [yj-1, yj] 14 (2.13)