Tài liệu Bộ tách sóng đa người dùng sử dụng giải thuật mmse

ĐAI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ Đ in h C hí Hiếu B ộ TÁCH SÓNG ĐA NGƯỜI DÙNG SỬ DUNG GIẢI THUẬT MMSE Chuyên ngành : KỸ THUẬT v ỏ TUYẾN ĐIỆN TỬVÀ THÔNG TIN LIÊN LẠC Mã SỐ : 2.07.00 LUẬN VĂN THẠC s ĩ KHOA HỌC NGUỜI HUỔNG DẪN KHOA HỌC PGS.TS. Nguyễn Viết Kính p V- Lơ / ịỊ f Hà nội - 2002 MỤC LỰC Liệt kê các ký hiệu và chữ viết tắt....................................................................3 Phần giới thiệu.................................................................................................... 4 Chương 1 1.1 1.2 1.3 Giới thiệu tổng quan về công nghệ M Ư D ................................6 ư u điểm ................................................................................................6 Lịch sử phát triển..........................................................................6 Các nshiên cứu gần đây về MUD và các kết quả chính.......7 Chương 2 2.1 Mô hình thu cdma với một người dùng.............................. 13 Dạng sóng ký hiệu....................................................................... 14 2.1.1 Trải p h ổ chuỗi trực tiếp........................................................14 2.1.2 Chuỗi kỷ hiệu...........................................................................15 2.1.3 Chuỗi ngẫu nhiên................................................................... 17 2.2 Bộ lọc hoà hợp.............................................................................. 18 2.3 Bô thu một người dùng cổ điển.................................................... 20 Chương 3 3.1 3.2 3.3 Bộ tách sóng đa người dùng tối ưu..................................... 22 Tiêu chuẩn cực đại xác suất.......................................................... 22 Bộ tách sóng MMSE đa người dùng tổng quát......................... 23 Phương pháp hình chiếu gradient............................................. 24 3.3.1 Điều kiện Kuhn - Tucker................................................... 24 3.3.2 Hình chiếu gradient - di chuyển trên cạnh ràng buộc 25 3.3.3 Nẹoại lệ - ra nqoài biên.................................................... 27 3.3.4 Di chuyển bên tronq không ẹian ràno buộc................. 28 3.3.5 Điều kiện kết thúc.................................................................. 28 3.3.6 Độ phức tạp tính toán........................................................... 29 Chương 4 Bộ tách sóng đa người dùng tuyến tính M M SE..................30 Chương 5 Bộ tách sóng đa người dùng MMSE tuyến tính tương thích..................................................................................34 Biểu diễn bài toán............................................................................34 Phương pháp giảm theo độ dốc lớn nhất................................. 35 Độ lớn của bước lặp thay đổi theo thời gian..............................37 5.1 5.2 5.3 Chương 6 6.1 6.2 Kết quả Mô phỏng.................................................................... 38 Cấu trúc của chương trình mô phỏng..........................................38 Kết quả mô phỏng............................................. !.........................39 6.2.1 Trườnẹ hợp hai người dùng................................................. 39 6.2.2 Trường hợp 100 người dùnẹ................................................ 41 1 Kết luận................................................................................................................. 43 Phụ lục..................................................................................................................... 44 Tài liệu tham k h ảo ...............................................................................................48 2 LIỆT KÊ CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT 1. Ký hiệu Liên hợp phức (.)* ư Phép chuyển vị d(.) Khoảng cách Euclide Q(.) Hàm mục tiêu EC) Trung bình s(t) chuỗi ký hiệu trải phổ M V Sô người dùne o Toán tử Gradient K(n) Nhiễu Gauss trắng có PSD bằng 1. Ơ Phương sai của nhiễu của kênh truyền b Vector bit truyền R Ma trận tương quan chéo A Ma trận biên độ tín hiệu thu được V tín hiệu thu được d Hình chiếu của Gradient lẽn mặt phảng tiếp tuyến vv Vector trọng số 2. Chữ viết tăt MMSE Cực tiểu sai số toàn phương trung b'lnh (Minimum Mean Square Error) CDMA Đa truy cập phân chia theo mã (Code Division Multiple Access) AWGN Nhiễu Gauss trắng cộng được (Additive White Gaussian Noise) MAI Multiple Access Interference 3 P H Ẩ N GIỚ I T H I Ệ U Sự tăng trưởng của số thê bao truy cập cố định sẽ đạt tới điểm bão hoà vào khoảng năm 2004 cho dịch vụ thoại. Truy cập vô tuyến di động đang tãng trưởng rất nhanh và số thuê bao dự kiến sẽ vượt quá số thuê bao cố định vào khoảng năm 2004. Truy cập internet qua mạng cố định đang tăng trưởng cùng với truy cập qua mạng vô tuyến di động. Khoảng 80% số người sử dụng Internet kết nối qua mạng cố định có dùng thông tin di động. Do vậy những người dùns; này ngày càng mong đợi cũng có các dịch vụ như vậy qua mạng di động. Điều này dẫn tới một thị trường đầy tiềm năng: di động đa môi trường, mà điều này sẽ được khởi đầu với các hệ thống như GPRS, HSCSD, EDGE và IMT-2000 [13]. Hiện nay, các thiết bị vô tuyến được thiết kế để truyền thoại và các bản tin nsắn chứ chưa thể truyền tải được thông tin đa phương tiện và các thông tin Internet băng rộng [12]. Điều này đòi hỏi phải có những kỹ thuật mới để đáp ứng nhu cầu cung cấp dịch vụ. Dung lượne của Đa truy cập phân chia theo tần số (FDMA) hoặc Đa truy cập phân chia theo thời gian (TDMA), thường là hệ thống thông tin thế hệ thứ hai, như đã biết, khi hết các kênh vô tuyến hoặc các khe thời gian rỗi, không khách hàng nào có thể thêm vào được nữa. Còn Đa truy cập phân chia theo mã (CDMA) lại bị giới hạn bởi can nhiễu. Hệ thống có thể thêm nữa người dùng, mặc dù phải trả giá là tỷ số tín hiệu trên tạp âm của mọi người dùng đều giảm chút ít. Hệ thống thông tin vô tuyến di động thế hệ thứ ba sẽ dùng đa truy cập phân chia theo mã băng rộng, W-CDMA. Các kỹ thuật tách sóng dùng cho bộ thu đa người dùng (M UD - Multiuser Detection) là một trong những tiến bộ quan trọng nhất trong thời gian gần đây trong công nghệ viễn thông. MƯD giải quyết bộ thu tối ưu có can nhiễu lẫn nhau giữa các dòng bit thông tin số xảy ra trong rất nhiều hệ thống thông tin dựa trên công nghệ đa truy cập TDMA, FDMA, CDMA. [9] Tách sóng đa người dùng là kỹ thuật được dùng để tăng dung lượng và vùng phú sóng ở các hệ thống CDMA. v ề mặt lý thuyết, MƯD có thể tăng dung lượng lên khoảng 3 lần trong kênh Gauss trắng cộng được, nhưng trong thực tế, sự tăng này phụ thuộc nhiều vào kiểu tách sóng, ước lượng kênh truyền và trễ. Người ta đã chỉ ra rằng MUD có khả năng tận dụng được cấu trúc của can nhiễu đa truy cập và có thể hạn chế được hiệu ứng gần xa. Việc nghiên cứu trong lĩnh vực tách sóng đa người dùng được bắt đầu vào đầu những năm 80 và đã tạo ra rất nhiều kỹ thuật mới. Ban đầu, các lời giải 4 tối ưu cho hiệu năng tốt nhất trong kênh ồn Gauss đã được nghiên cứu và phát triển. Tuy nhiên, độ phức tạp tính toán của các phương pháp này tăng theo hàm mũ với số người dùng nên khó áp dụng trong thực tế. VI vậy nó đã được cải tiến liên tục và dẫn tới các giải thuật tách sóng đa người dùng cận tối ưu ít phức tạp hơn, ví dụ như: bộ tách sóng triệt tương quan, bộ tách sóng nhiều trạng thái, bộ tách sóng đa người dùng quyết định phản hồi ngược và các bộ tách sóng cận tối ưu khác. Bởi vì tách sóng đa người dùng mang lại rất nhiều lợi thế cho các hệ thống CDMA vô tuyến về mật tăng dung lượng và loại bỏ hiệu ứng gần xa, nên các kỹ thuật có nhiều triển vọng này được áp dụng cho các hệ thống thông tin vô tuyến thế hệ thứ ba, W-CDMA. Đó chính là vấn đề mà bản luận văn này đề cập đến. Trong bản luận vãn này, trường hợp cụ thể của CDMA dựa trên chuỗi ký hiệu giả ngẫu nhiên sẽ được xem xét. Đặc biệt, tiêu chuẩn tối ưu MMSE sẽ được nghiên cứu chi tiết và đặc tính hội tụ của các kỹ thuật lập sẽ được nghiên cứu. Bản luận văn này gồm những chương sau: Chương I Giới thiệu tổng quát về công nghệ tách sóng đa người dùng, tính ưu việt, lịch sử phát triển và các tiến bộ gần đây. Chương II Đưa ra mô hình hệ thống xem xét, chuỗi tín hiệu giả ngẫu nhiên và bộ thu CDMA cổ điển Chương III Giới thiệu bộ thu đa người dùng tối ưu và giải thuật Hình chiếu Gradient được giới thiệu chi tiết. Chương IV Bộ thu đa người dùng tuyến tính MMSE Chương V Bộ thu đa người dùng tuyến tính thích nghi MMSE Chương VI Kết quả mô phỏng và các nhận xét Chương VII Kết luận và hướng phát triển tiếp theo của đề tài. 5 Chương 1 1.1 GIỚI THIỆU TỔNG QUAN VỀ CÔNG NGHỆ MƯD ưu điểm Một số công nghệ viễn thông đang xuất hiện nhắm vào các kỹ thuật quan trọng để tới gần giới hạn về lý thuyết dung năng của các kênh vô tuyến đa truy cập. Các hệ thống đa người dùng vô tuyến chịu can nhiễu đa truy cập. Người dùng TDMA chịu nhiễu do các khe chồng lấn từ các ô khác, và từ những người dùng trong cùng ô do kênh truyền bị méo. Tương tự, truyền CDMA đổng bộ trực giao sẽ mất tính trực giao của nó khi truyền qua kênh fading. Can nhiễu đồng kênh trona; hệ thống CDMA không đổng bộ là không thể tránh được thậm chí cả khi kênh không méo và không có can nhiễu từ các ô khác. Can nhiễu đa truy cập là nhân tố chính tạo thành can nhiễu tổng cộng ở máy thu, của cả máy di dộng và trạm gốc. ớ các hệ thống thế hệ thứ hai, một số phương pháp đã được áp dụng để giảm bớt can nhiễu đa truy cập. Trong TDMA-GSM và IS-136 việc duy trì mẫu tái sử dụng tần số và khoảng thời gian bảo vệ giữa các khe liên tiếp thì lại chịu thiệt về hiệu suất phổ. Trong CDMA (IS-95), điều khiển công suất nghiêm ngặt hạn chế vấn đề gần-xa; dùng mã sửa lỗi mạnh cho các kênh có tỷ số tín hiệu trên tạp âm thấp để giải mã thông tin một cách tin cậy khi có can nhiễu đa truy cập. Tất cả các hệ thống thế hệ thứ hai coi can nhiễu đa truy cập như là một phần của nhiễu nền, và không có quá trình xử lý tín hiệu nào để chống lại nó. Tuy nhiên, nhiễu đa truy cập có cấu trúc đặc trưng của nó, và chắc chắn là ít nsẫu nhiên hơn nhiễu Gauss trắng nền. Bằng cách tận dụng cấu trúc này, tách sóng đa người dùng [7] có thể tăng hiệu suất phổ, độ nhạy máy thu, và số người dùng của hệ thống. Thêm vào đó, việc sử dụng bộ tách sóng đa người dùng làm giảm đáng kể sự phụ thuộc vào điều khiển công suất nghiêm ngặt và chính xác (mà điều này không thể thực hiện được trong một vài ứng dụng vô tuyến). 1.2 Lịch sử phát triển Các bộ tách sóng đa người dùng mới chỉ bắt đầu được phát triển vào đầu những năm 80. Thời gian qua đã chứng kiến một số lượng lớn các kỹ thuật xử lý tín hiệu để chống lại can nhiễu đa truy cập. Loại bỏ liên tiếp, được thúc đẩy bởi lý thuyết thông tin, giải điều chế liên tiếp bằng cách điều chế lại và trừ đi tín hiệu đã được điều chế. Các bộ tách sóng đa người dùng tuyến tính đã sửa đổi mạch lọc hoà hợp có tính tới cấu trúc của nhiễu đa 6 Với N là chiều dài của chuỗi ký hiệu, ở đây, dạng sóng của ký hiệu được chọn sao cho p t] = 1 (để chuẩn hoá tương quan chéo). Do vậy, ta có định nghĩa về ma trận tương quan chéo R như sau: R= P\\ p\2 P\M P l\ P ll P lM VP m I P 2 ••■ P mm m 02.3) Ma trận R có các tính chất sau: • Đối xứng • Các phần tử trên đường chéo bằng 1 ( chuẩn hoá ) => Nó là toeplitz • Nói chung, ma trận là xác dinh, không âm. 2.1 2.1.1 Dạng sóng ký hiệu Trải phổ chuỗi trực tiếp Chuỗi trực tiếp liên quan đến một hướng tiếp cận đặc biệt để cấu trúc nên dạng sónơ trải phổ, có tính chất như sau: 1. Dạng sóng của chip pTc, sao cho Ị p Ạ t ) p TS t ~ n T c)cit = ° ’ /í = 1,2,... (2.4) -co 2. Số chip trên một bit: /V •' 3. Chuỗi nhị phân có chiều dài N: (cy, c v) Nếu dạng sóng của chip là chuỗi nhị phàn đối cực thì ta có dạng sóng trải phổ trực tiếp với chu kỳ NT : s(t) = A ị i ( - i y p Tí( t - ự - \ ) T , ) (2.5) /=1 Chuỗi nhị phân (ch C N ) không chứa thông tin và được xem là biết trước ở đầu thu. Một ví dụ vể dạng sóng trải phổ trực tiếp cho trong hình 2.1. Trong trường hợp này, chip có dạng sóng là các xung hình chữ nhật: Ptc(0 ịì, 110, khi 0 .( ') - ' X + T.) (2-9) với {dkie {-1, +1 }, k= 1, K; i= 1, N ) độc lập và phân bố đều và giả sử dạng sóng chip p Tí có năng lượng đơn vị và hàm tự tương quan: 00 Rp(r ) = (2-10) -0 0 Chú ý rằng (2.4) có nghĩa là: Rp(nTt.)=0, n*0 (2.11) Hàm tương quan chéo không đồng bộ có thể được viết như sau: P Ả T)= p t C O í / ơ - r ) * (2 .12) 1 N = Ì ; Z ĩ . ‘l « W T + U - ì K ) N /=I j =I Rồ ràng, bởi vì { d kiE {-1, năne nên, + 1}, k = \ , K\ /=1, /VỊ độc lập và đồng khả E [ p kl(ĩ)]=0 (2.13) với kĩ4. Mômen bậc hai của hàm tương quan chéo là Í [ # Í W /V] 4 f‘. Í| jỈm\ Ẻm=| Ế W ,W .] n= l xR ,(T + U - i ) T r)Rp(T + ( n - m ) T c) (2.14) = - ề ĩ ị ị * > +U - 0 T ') IV i=\ 7=1 Tính đến (2.11), ta có thể chỉ ra (2.14) khi I = 0 để có được moment bậc hai của tương quan chéo đồng bộ p u - p kl(0): /V /= Ị (2.15) N Bộ lọc hoà họp Bộ lọc hoà hợp trong hệ thống thông tin số được dùng để tạo ra đủ về mặt thống kè cho bộ tách tín hiệu. Trong hệ thống đa truy câp, bộ thu chứa một dãy các bộ lọc hoà hợp, mỗi bộ tươns ứng với một dạnơ sóng tín hiệu của người dùng, như chỉ ra trong hình 2.4. Lối ra của bộ lọc hoà hợp thứ j là: y j = ỉ , y ( n)sA n) (2.16) /1=1 Khai triển ra, phương trình trên trở thành: y, = X k-\ Akbk Vn=ỉ ( * ) * ; ( « ) J + ơ £ n ( h ) s , ( « ) /1=1 = i AAPjk + nj (2-17) Jk = l Biểu thức trên có thể được viết gọn lại dưới dạng ký hiệu ma trận y ~ ryAb + n; • • • (2.18) r, = [p]X,Pp, p,MY , vector tương quan chéo của người dùng thứ j với tất cả các người dùng khác. A = diag(Aị, Am), ma trận biên độtín hiệu nhận được. b = [bị, bM], vector bit truyền. Nếu viết gộp cả lối ra của tất cả mọi người dùng, ta có: ' y\ N P\\ Pi\ A, 0 0 ... A, . . . 0 / 2. \ 0 / n. A (2.19) + U /, V \P.\4 P.v/11 Pmi ■■■ P\11A® ® KpM ) \ nM) 18 Dưới dạng ký hiệu ma trận rút gọn, phương trình trên được viết lại thành: y = RAb + n (2.20) Hình 2.4 M ạch lọc h oà hợp nhiễu ở lối ra của bộ lọc hoà hợp, n có thể được mô tả vể mặt thống kê như sau: E {n,nj} = ơ 2Ỳ i si(n)Sj(n) = ơ 2p tJ (2.21) /1=1 Và, ma trận hiệp phương sai của lối ra của bộ lọc hoà hợp được cho bcri: £{nnr}= n = cr2R (2'22) 19 2.3 Bộ thu một người dùng cổ điển ở bộ thu một người dùng cổ điển, bộ thu của mỗi người dùng chứa một bộ giải điều chế tương quan (hoặc mạch lọc hoà hợp) tín hiệu nhận được với chuỗi ký hiệu của người dùng và đưa qua bộ tách tương quan lối ra. Do vậy, bộ thu cổ điển loại bỏ sự hiện diện của những người dùng khác trên kênh truyền, hay, coi rằng ồn kết hợp với nhiễu là dạng Gauss trắng. Hình 2.5 Bộ thu m ột nguòi dùng c ổ điển Lối ra của bộ tương quan cho người dùng thứ k của tín hiệu trong khoảng 0 < t < T là: T yk = 0 K = Akbk + X Ajbjpjk + nk (2.23) và bk = sign(yk) (2.24) với thành phần ồn ^.được định nghĩa như sau: T nk = Ịn(t)sk(t)dt (2.25) 0 20 Vì n(t) là ồn Gauss trắng với mật độ phổ công suất 1/2N 0, phương sai của nk là: 4».!] = - ỳ ^ K ( ' ) * = V o 0 ^ (2-26) Rõ ràng, nếu các chuỗi ký hiệu là trực giao, thì can nhiễu từ các người dùng khác tạo ra bởi hệ số ở giữa ở phương trình (2.23) - MAI- bị triệt tiêu và bộ thu một người dùng cổ điển là tối ưu. Mặt khác, nếu một hay nhiều chuỗi ký hiệu khác không trực giao với chuỗi ký hiệu của người dùng, thì can nhiễu từ những người dùng khác có thể trờ thành rất lớn nếu mức công suất của các tín hiệu (hay năng lượng của tín hiệu nhận được) của một hav nhiều rì2ười dùns khác đủ lớn hơn mức công suất của người dùng thứ k. Trường hợp này nói chung được sọi là hiện tượng gần - xa (near-far problem) trong thông tin đa người dùng, và cần phải có điều khiển công suất cho bộ thu cổ điển. Một giải pháp khác là áp dụng các bộ thu đa người dùnẹ. Nhận xét: Chúng ta đã thấy rằng bộ thu cổ điển có hai nhược điểm chính: 1. Khả năng chống lại hiệu ứng gần - xa kém, do vậy đòi hỏi phải điều khiển công suất nghiêm ngặt. 2. Dung năng thông tin thấp, bị giới hạn chủ yếu bởi can nhiễu đa truy cập chứ không phải nhiễu AWGN. Tuy nhiên lợi thế chính của bộ thu này là độ phức tạp tính toán thấp - tăns tuyến tính theo số người d ù n g - và dễ cài đặt. [6J 21 Chương 3 BỘ TÁCH SÓNG ĐA NGƯỜI DỪNG T ối u u Sử dụng mô hình phát triển trong phần trước, bài toán thu đa người dùng tối ưu được phát biểu như sau: Cho thống kê (V/, . . yM) ở lối ra của hộ lọc hoà hợp, tìm ước lượng của bit truyền (b/, . . by) sao cho tối lãi (cực tiểu hoá) xác suất lỗi. Xác suất mắc lỗi được chọn là tiêu chuẩn tối ưu bời vì nó là tiêu chuẩn quan trọns nhất để đánh giá chất lượng của một hệ thống thông tin số. 3.1 Tiêu chuẩn cực đại xác suất Ta đã biết rằng, khi tách tín hiệu bị ảnh hưởng bởi nhiễu Gauss trấng cộng được (AWGN), bộ giải mã cực tiểu hoá xác suất mắc lỗi là bộ tách sóng cực đại xác suất. Tiêu chuẩn cực đại xác suất dựa trên việc lựa chọn các bit lối vào, để cực tiểu hoá khoảng cách Euclide giữa tín hiệu truyền (tức là các bit lối vào) và tín hiệu thu được. Trong trường hợp tách sóng đa người dùnơ, khoảng cách Euclide giữa vector tín hiệu truyền, tươns ứng với vector bit lối vào b, và vector tín hiệu nhận được là [1]: (3.1) n=1 k=1 Khai triển biểu thức trên, ta có: d(b) = Ý jy ( n ý - 2 Ỵ j Akbkị j y(n)sk{n) + 'ỵj Y,Akbksk(n) n =l k=\ n= I /t = l \ Ấ r = l (3.2) / Hẹ sô đầu tiên trong biểu thức là độc lập với b và do vậy có thể loại bỏ khỏi quá trình cực tiểu hoá (thay vào đó, chúng ta định nghĩa hàm xác suất Q(b) sai khác với d(b) một hằng số). Dùng định nghĩa yJ ở phương trình (2.4) và dùng định nghĩa của A và b, biểu thức trên được viết gọn lại thành: Q(b) = -2/VbrAy + ýVbrARAb (3.3) 22 Bỏ /V và dùng tính chất là cực đại âm của một hàm tương đương với cực tiểu của hàm đó, bài toán tách sóng đa người dùng tối ưu có thể được phát biểu như sau: Max: Q(b) = 2brAy - brARAb (3.4) b e{ + 1 ,-1 }" Bài toán cực đại phát biểu ở trên là bài toán tối ưu tổ hợp, bởi vì các biến của bài toán tối ưu về cơ bản được giới hạn trong một tập hữu hạn. Phương pháp trực tiếp để giải bài toán tổ hợp này là tìm kiếm mọi khả năng. Trong trường hợp trên, bởi vì b e{ +1, -1 )M , nên có 2M khả năng. (Khi điều chế Q-ary thì có Q‘l/ khả năng!). Do vậy không gian tìm kiếm tăng theo cấp số nhân theo số người dùng. Nói cách khác, độ phức tạp tính toán cần thiết để giải mã M bit dữ liệu là 0 ( 2'v/). Verdu [1] đã chỉ ra rằng không có giải thuật nào có độ phức tạp tính toán là đa thức theo số người dùng để giải bài toán tối ưu tổ hợp này. Bộ tách sóne; đa neười dùng tối U11 ưu việt hem nhiều so với bộ thu cổ điển, tuv nhiên nó có nhược điểm là tăng đáng kể độ phức tạp tính toán — tăng theo hàm mũ với số người dùng. [5] 3.2 Bộ tách sóng M M S E đa người dùng tổng quát Khống gian ràng buộc trong trường hợp bộ tách sóng đa người dùng cực đại xác suất là tập các cạnh của siêu cầu M chiều. Nếu không gian ràng buộc này được mở rộng để chứa hình cầu M chiều đi qua mọi cạnh, ta có bài toán tối ưu dưới đây: Max: Q(b) = 2brAy - brARAb brb < M (3.5) Vì là cực tiểu của một hàm lồi trên một tập lồi, cực tiểu duy nhất tồn tại và có thể tìm bằng phương pháp hình chiếu gradient. Bộ tách sóng này được gọi là bộ tách sóng MMSE tổng quát vì dạng lời giải của nó là tổng quát cho tất cả mọi bộ tách sóng MMSE khác (có các ràng buộc bổ xung), như đã chỉ ra trong [7]. Cần phải lưu ý rằng ở bộ tách sóng tối ưu và bộ tách sóng MMSE tổng quát, không có ràng buộc nào về loại phép toán được y M). Nếu các phép toán áp dụng lên lối phép thực hiện trên thống kê (yj, vào thống kê được hạn chế chỉ là tuyến tính, thì phép tối ưu hoá trở thành bộ tách sóng đa người dùng tuyến tính có cấu trúc đẹp (bậc ba). Phương pháp giảm theo độ dốc lớn nhất có thể được dùng để đi tới kết quả. 23 3.3 Phương pháp hình chiếu gradient Bài toán trên có thể được giải bằng phương pháp hình chiếu gradient với các hạn chế phi tuyến [8]. Để bắt đầu, ta đơn giản bài toán trên như sau: Min: fì(b) = brb < M 1/2 brARAb -brAy (3.6) Bài toán đã cho được chuyển đổi thành bài toán cực tiểu và định lại tỷ lệ (để thuận tiện cho tính toán). Hơn nữa, ta định nẹhĩa các hằng số sau: Q = ARA q = Ay (3.7) (3.8) Báy giờ, bài toán đã cho trở thành: Min: Q(b) = brb < M 1/2 brQb - brq (3.9) Chú ý rằng lời giải cho bài toán này, nói chung, là không thuộc {+ 1, - 1 ỊM. “Vết” của nghiệm là nghiệm thực sự của bài toán đã cho. 3.3.1 Điểu kiện Kuhn - Tucker Điều kiện Kuhn- Tucker cho lập trình phi tuyến hạn chế được phát biểu như sau [8]: VQ(b*) + juVh(b*) = 0 /Jh(b*) = 0 JU > 0 (3.10) (3.11) (3.12) Với bài toán đã cho, điều kiện Kuhn-Tucker được viết thành: (Qb - q) + 2/đ> = 0 /i(b b - M) = 0 /J> 0 (3.13) (3-14) (3.15) Lời giải cho điều kiện Kuhn - Tucker có thể thu được khi giả sử chỉ ràng buộc là cố định và khi đó nghiệm của phương trình trên là b 0p, = Q 'q (3.16) 24 Các phần dưới đây sẽ mô tả phương pháp Hình chiếu gradient áp dụng cho Bộ tách sóng đa người dùng MMSE. 3.3.2 Hỉnh chiếu gradient - di chuyên trên cạnh ràng buộc Giả sử rằng ta bắt đầu tại điểm trên cạnh ràng buộc (tức là trên bề mặt của siêu cầu). Tìm một điểm như vậy là đơn giản, điểm b mà các phần tử đều bằng 1 là một trong số các điểm đó. Bây giờ ta phải di chuyển theo hướng ngược với gradient để cực tiểu hoá hàm: -g* = -VQ(b,)r = - (Qbt - q) (3.17) với k là số bước lặp. Nhưng, vì phải thoả mãn ràng buộc, nên đầu tiên ta tìm hình chiếu của gradient lên mặt phẳng tiếp tuyến với tập ràng buộc. Ma trận hình chiếu của phép chiếu này là: p, = I - V/i(bk)r[VÃ(bk) /!(bk)r]-' h(bk) (3.18) VÌ h{b k)r = 2 b k, nên phương trình trên trở thành: p = b*r b4 (3.19) M Do vây, hướng di chuyển là: b, = -p,g, (3.20) Tiếp theo ta phải xác định sẽ di chuyển “xa bao nhiêu” theo hướng của hình chiếu để cho hàm được cực tiểu càng nhiều càng tốt theo hướng này. Do vậy, theo h ư ớ n g d ; , ta phải tìm a là n g h iệm c ủ a bài toán tối ưu phi tuyến không ràng buộc sau: Min,/(«;.) = Q(b, + a kdk) = i(b* + a kdk) TQ (h k + a kdk) - (b* + a kdk)Tq (3.21) Giá trị của a k để cực tiểu hàm này theo [8] là: ak = 4 ^ d[Qd, (3.22) 25 Do vậy, bước lặp cho phương pháp hình chiếu gradient là: x M = bk + a kdk (3.23) Nói chung, Xk+J có thể không rơi vào trong không gian ràng buộc. Cụ thể là trong trường hợp này, trừ khi d^. = 0, \ k+l luôn red ra ngoài siêu cầu. Do vậy ta phải tìm hình chiếu của điểm mới \ k+1 sao cho nó rơi trở lại vào bể mặt ràng buộc. Để làm được như vậy, ta phải giải hệ phương trình phi tuyến sau: x,+/ + V h ( b f a = b*+1 h(bM ) = 0 (3.24) (3.25) Hệ phương trình trên được biến đổi thành (x,+/ + a kb,)r (x,+/ + a kbk) = M (3.26) Đơn giản biểu thức trên, ta có phương trình theo a: (4b[bt )a 2 +(4bir x*+1)a + (4x[+1x*tl - M ) = 0 (3.27) Có hai giá trị của a thoả mãn phương trình trên: -c2±-Ịcị - 4 c,c3 a \a 2 = 2c, (3.28) với c, = 4 b fk b C-, = 4 b [ x cĩ = 4xL.x*+1 - M Chọn a là điểm gần nhất trên bề mặt của siêu cầu, tức là: a x, nếu N - Iữ2 «2, nếu \a2 ã VI (3.29) Khi đó, b*+1 trở thành b*+i = xt+1 + a p V h (b k)T (3.30) 26