Tài liệu Luận văn tiến sĩ kỹ thuật về một cấu trúc tổng quát của mã tựa ngẫu nhiên phi tuyến đa cấp-đa chiều theo kiểu lồng ghép

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG BÙI LAI AN Về một cấu trúc tổng quát của mã tựa ngẫu nhiên phi tuyến đa cấp-đa chiều theo kiểu lồng ghép Chuyên ngành: Kỹ thuật điện tử Mã số: 62.52.70.05 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI – 2012 Công trình được hoàn thành tại: Học viện Công nghệ Bưu chính Viễn thông Tập đoàn Bưu chính Viễn thông Việt Nam Người hướng dẫn khoa học: 1- GS.TSKH Nguyễn Xuân Quỳnh 2- TS. Lê Chí Quỳnh Phản biện 1: …………………………………………………… …………………………………………………… Phản biện 2: …………………………………………………… …………………………………………………… Phản biện 3: …………………………………………………… …………………………………………………… Luận văn sẽ được bảo vệ trước hội đồng chấm luận án tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận án tại: - Thư viện Học viện Công nghệ Bưu chính Viễn thông Danh mục các công trình đã công bố: [1] [2] [3] [4] [5] [6] Bùi Lai An, Nguyễn Thúy Anh, Ngô Minh Khải, Nguyễn Ngọc San, ”On internaly balanced and optimal projection methods to order- redution for models: a critical survery”, Tạp chí Nghiên cứu khoa học và kỹ thuật quân sự, 17/2006. Bùi Lai An, ”Xem xét mã nhiều chiều theo quan điểm lý thuyết hệ thống”, Tài liệu Hội nghị Khoa học lần thứ tám - Nhân dịp kỷ niệm 40 năm thành lập Viện Khoa học Kỹ thuật bưu điện - Tập đoàn bưu chính Viễn thông Việt Nam ; 2006/Số 00. 469-475 . Bùi Lai An, Nguyễn Xuân Quỳnh, “Về một cấu trúc tổng quát của mã PN phi tuyến đa chiều đa cấp theo kiểu lồng ghép”, Tạp chí Khoa học và công nghệ, số 3, 2009, pp 9-17. Bùi Lai An, “Thuật toán xác định cấu trúc của mã tựa nhiễu phi tuyến đa cấp theo kiểu lồng ghép”, Tạp chí Khoa học và Công nghệ 47(4) (2009), 27-35. Bùi Lai An, Nguyễn Hoàng Linh, “ Khảo sát giao thoa đa truy nhập với dãy trải phổ PN lồng ghép phi tuyến ”, Tạp chí Chuyên san các công trình nghiên cứu, phát triển và ứng dụng công nghệ thông tin, tập 1, số 1, 2010, 165-173. Bui Lai An, Nguyen Thuy Anh “Effect to handle of inter-leaving PN sequence”, Tạp chí Khoa học và Công nghệ số 4 , 2011), . MỞ ĐẦU Tính cấp thiết của đề tài: Nghiên cứu và phát triển các dãy trải phổ giả ngẫu nhiên PN có tính chất mong muốn là xu thế tất yếu của công nghệ viễn thông. Kỹ thuật lồng ghép là một giải pháp hữu hiệu để tạo dãy trải phổ có độ dài mong muốn, vì vậy được nhiều người quan tâm nghiên cứu. Tuy vậy, việc tổng quát hóa cấu trúc lồng ghép đa cấp-đa chiều chưa được mô tả một cách đầy đủ. Hơn nữa việc tìm kiếm và xây dựng các họ dãy lồng ghép đa chiều chưa được giới thiệu và khảo sát kỹ lưỡng (trong các tài liệu thường giới thiệu các minh họa có độ dài L<100). Trong thực tế thì chiều dài dãy lớn hơn rất nhiều, L=225-1 cho tới 232-1, thậm chí là 242-1. Tức là khoảng 33 triệu bít; 4,2 tỷ bít; 4.400 tỷ bít trong W-CDMA. Để xây dựng các dãy trải phổ phi tuyến lồng ghép có độ dài lớn như vậy thì cần thiết phải tổng quát hóa cấu trúc mã, đồng thời dãy đa cấp lồng ghép được xây dựng từ cấu trúc tổng quát trên sẽ được phân tích, đánh giá theo các đặc tính của dãy trải phổ để xác định khả năng ứng dụng. Đây chính là các yêu cầu bức thiết đặt ra cho những người thiết kế dãy trải phổ cho thông tin thế hệ mới. Mục đích nghiên cứu của luận án là đề xuất và xây dựng cấu trúc tổng quát của dãy trải phổ phi tuyến đa cấp-đa chiều theo kiểu lồng ghép, làm tiền đề cho việc thiết kế các dãy trải phổ phi tuyến mới. Thực hiện phân tích và đánh giá dãy trải phổ phi tuyến đa cấp-đa chiều theo kiểu lồng ghép về các đặc tính của dãy trải phổ. Từ đó đánh giá khả năng ứng dụng trong thông tin thế hệ mới. Đối tượng và phạm vi nghiên cứu là mã trải phổ phi tuyến đa cấp-đa chiều theo kiểu lồng ghép. Phạm vi nghiên cứu bao gồm xây dựng cấu trúc tổng quát của họ dãy PN phi tuyến có cấu trúc đa cấp-đa chiều theo kiểu lồng ghép. Đánh giá đặc tính của họ dãy mã tìm được theo các tiêu chí dãy trải phổ. Phương pháp nghiên cứu là dựa trên các công cụ toán học, lý thuyết đại số, lý thuyết trường hữu hạn như giải thuật như Hàm Vết (Trace Function) và biến đổi d (d-Transform). Các kết quả nghiên cứu được kiểm chứng bằng mô phỏng. 1 Ý nghĩa khoa học và thực tiễn: Về mặt lý thuyết, luận án đã đề xuất và xây dựng một cấu trúc tổng quát mới về dãy lồng ghép đa cấp và phân tích đánh giá các đặc tính cơ bản của dãy trải phổ đa cấp đa chiều theo kiểu lồng ghép. Các cấu trúc tổng quát, cấu trúc cấp 2, cấp k sẽ là tiền đề và công cụ hỗ trợ các nhà thiết kế mã xây dựng các dãy mã trải phổ có độ dài và độ phức tạp như mong muốn. Với giải thuật ghép đa cấp và lồng phi tuyến theo cấu trúc tổng quát, người thiết kế mã sẽ xây dựng được các mã phi tuyến đa cấp lồng ghép mới với các tiêu chí thiết kế khác nhau. Về mặt thực tiễn, luận án đã đưa ra một cấu trúc tổng quát, phương pháp biểu diễn và cách thức xây dựng, mô phỏng đánh giá các đặc tính họ dãy phi tuyến có cấu trúc lồng ghép đa cấp, tạo điều kiện thuận lợi cho người thiết kế mã tìm kiếm dãy mã trải phổ đa cấp lồng ghép có khả năng ứng dụng cho thông tin thế hệ mới. Nội dung của luận án bao gồm: Chương 1: "Tổng quan về dãy trải phổ". Chương 2: "Thuật toán tìm cấu trúc của dãy lồng ghép đa cấp" Chương 3: "Phân tích và đánh giá dãy phi tuyến lồng ghép đa cấp". Chương 4: "Mã trải phổ với dãy lồng ghép đa cấp". Kết luận: Phần này tổng kết các kết quả chính đã đạt được và hướng phát triển tiếp theo từ luận án này. 2 CHƯƠNG 1. TỔNG QUAN VỀ DÃY TRẢI PHỔ PHI TUYẾN 1.1. Mở đầu Chương này sẽ điểm qua các nội dung liên quan trong CDMA, kỹ thuật trải phổ, đặc tính của dãy trải phổ, các dãy trải phổ phi tuyến, dãy có tính chất tương quan đặc biệt và những phát hiện và công bố mới về mã lồng ghép hai chiều. Từ đó giúp cho việc định dạng bài toán xây dựng cấu trúc tổng quát cho mã lồng ghép đa cấp. Qua đây, những yêu cầu và thách thức đối với việc thiết kế dãy trải phổ phi tuyến đa cấp đa chiều đã được nêu rõ. Trên cơ sở đó các nhiệm vụ nghiên cứu cụ thể của luận án đã được đề ra. 1.2. Công nghệ CDMA và kỹ thuật trải phổ Công nghệ CDMA: Dựa trên nền tảng là kỹ thuật trải phổ, các công nghệ CDMA tương ứng là thuần CDMA và CDMA lai ghép. Kỹ thuật trải phổ: Các kỹ thuật DS, TH, FH và phối hợp các kỹ thuật DS, TH, FH sẽ tạo được dòng lai ghép CDMA. Hoặc phối hợp công nghệ CDMA và công nghệ khác như TDMA và CDMA tạo TDMA/CDMA, OFDM và CDMA tạo MC-CDMA hoặc đa tần tone và CDMA tạo MT-CDMA. 1.3. Các đặc tính của dãy trải phổ 1.3.1. Các đặc tính ngẫu nhiên của dãy trải phổ Dãy giả ngẫu nhiên nhị phân tuần hoàn có 3 đặc tính cơ bản là đặc tính cân bằng, đặc tính chạy, đặc tính tương quan. Các dãy số được tạo ra có các tính chất thỏa mãn được cả 3 đặc tính trên được gọi là dãy giả ngẫu nhiên. 1.3.2. Hàm tương quan Hàm tự tương quan chuẩn hóa của dãy giả ngẫu nhiên được xác định: R A D A D (1.7) Với A: số phần tử giống nhau, D: số phần tử khác nhau 3 1.4. Các dãy trải phổ phi tuyến và dãy có tương quan đặc biệt 1.4.1. Các dãy tích a) Dãy tích của các dãy M khác (dãy tích loại 1) Nếu u1. u2 . u3... ui. ... ut là những dãy M có chu kỳ N1, N2, N3 ... Nt với Ni, Nj nguyên tố cùng nhau cho mọi giá trị của i,j (1,2,...,t) thì chu kỳ của dãy tích sẽ là: N = N1. N2. N3 ... Nt (1.9) b) Dãy tích được tạo nên từ một dãy M (dãy tích loại 2) Dãy tích này được cấu tạo từ các pha khác nhau của một dãy M. Dãy ra u của bộ ghi dịch phản hồi tuyến tính (LFSR): m 1 i u n   Ai ( 2 ) n (1.13) i 0 Trong đó: un mô tả bit thứ n của dãy u.  là nghiệm nguyên tố của đa thức và các hệ số ai  {0,1}. Dãy tích u.u* có biểu diễn: * m 1 m1 * i j u n u n   Ai A j ( 2  2 ) n (1.15) i 0 j 0 với un* là một pha khác của u, lấy ra từ một tầng khác của LFSR. 1.4.2. Các dãy hàm Bent Một hàm số được gọi là hàm Bent nếu tất cả các hệ số biến đổi Fourier của nó đều có biên độ là 1. Mỗi tập hợp dãy hàm Bent chứa 2m/2 dãy, tất cả các dãy đều có các giá trị của ACF bé và CCF giữa các dãy cũng bé. Giới hạn trên của ACF và CCF được cho bởi: amax(l), l  0 =cmax = max = 2m/2-1. (1.18) 1.4.3. Các dãy có đặc tính tương quan đặc biệt Phần này giới thiệu về mã trực giao và các dãy có vùng không tương quan và các dãy có cửa sổ không giao thoa IWF 1.4.4. Các dãy được sử dụng trong Cryptography Các nghiên cứu về dãy sử dụng trong Crytography đều hướng tới mục tiêu tăng độ phức tạp của dãy. Hơn nữa phải là độ phức tạp khó tiên nghiệm. Các dãy tuyến tính khó đạt được tiêu chí này. Vì như chúng ta đã biết, với dãy tuyến tính thì độ phức tạp thấp, không đủ tin cậy để sử dụng cho bảo mật. Một điều khá chắc chắn là nếu sử dụng giải thuật tạo 4 mã phi tuyến, lồng ghép đa cấp sẽ hứa hẹn về khả năng xây dựng được họ mã có tốc độ cao, độ phức tạp rất lớn, có khả năng ứng dụng trong Crytography. 1.5. Dãy có cấu trúc lồng ghép 1.5.1. Phương pháp lồng ghép Ý tưởng cơ bản của kỹ thuật lồng ghép là dựa trên các dãy M có độ dài phân tích được thành tích và có ít nhất một nhân tử dạng 2m-1. Thứ tự lồng ghép và các dãy con sẽ được xác định và quyết định cấu trúc của mã. Sau đó, chuyển đổi cấu trúc đó thành phi tuyến để tăng tổ hợp mã, có thể theo các cách sau : - Giữ nguyên thứ tự lồng ghép nhưng thay dãy M con thành phần bằng dãy M khác cùng độ dài. - Giữ nguyên thứ tự lồng ghép nhưng thay dãy M con thành phần bằng dãy có phân bố tựa ngẫu nhiên cùng độ dài. - Dùng dãy tích của Ti dãy M con thành phần tạo dãy lớn (Dãy tích loại 2 bậc Ti ). - Dùng dãy tích của Ti dãy con thành phần là các dãy M khác nhau tạo dãy lớn. 1.5.2. Biểu diễn dãy lồng ghép Phần này mô tả biểu diễn dãy lồng ghép bằng hai công cụ quen thuộc là hàm Vết và biến đổi d (d-Transform) 1.6. Nhiệm vụ nghiên cứu của luận án Luận án này đề xuất xây dựng cấu trúc tổng quát của mã giả ngẫu nhiên phi tuyến đa cấp-đa chiều theo kiểu lồng ghép và đánh giá các đặc tính cơ bản theo mục đích trải phổ. Từ đó đánh giá khả năng ứng dụng của nó trong thông tin thế hệ mới. 5 CHƯƠNG 2: CẤU TRÚC TỔNG QUÁT CỦA DÃY LỒNG GHÉP ĐA CẤP 2.1. Mở đầu Trong chương này, tác giả sẽ đề xuất và chứng minh bốn định lý quan trọng về cấu trúc của dãy lồng ghép từ cấp 2 đến cấp k và cấu trúc tổng quát. Đề xuất các thủ tục để xác định cấu trúc đa cấp đa chiều của mã. Sử dụng cấu trúc tổng quát tìm được và áp dụng các thủ tục xác định cấu trúc đa cấp sẽ cho phép thiết kế xây dựng các cấc trúc mã đa cấp lồng ghép có số cấp và chiều dài mong muốn với hai bài toán tiêu chuẩn là tìm các dãy con theo chiều dài của dãy lớn và tìm các lớp dãy con theo bậc của dãy lớn. 2.2. M dãy, đặc tính trải phổ và ứng dụng 2.2.1. Thanh ghi dịch phản hồi tuyến tính LFSR Hình 2.1: Mô tả sơ đồ của thanh ghi dịch phản hồi tuyến tính Đa thức sinh: g(d) = cmdm + cm-1dm-1 + ... + c1d + c0 , với cm = c0 =1 (2.1) 2.2.2. Các thuộc tính của dãy M Các nghiên cứu trước đây đã chỉ ra rằng, dãy M có các đặc tính dịch vòng trái hoặc phải cũng là dãy M, tính chất hồi qui, tính chất cửa sổ, tính chất số lượng số ‘1’, số ‘0’ : số 1 nhiều hơn số số 0 một đơn vị, tính chất cộng, tính chất dịch và cộng, tính chất tự tương quan có dạng nhọn, tính chất hành trình, tính chất pha đặc trưng, tính chất phép chia (tức lấy mẫu c cứ mỗi n bít mã, kí hiệu là c[n]). 2.2.3. Các dãy tuyến tính tạo từ dãy M 6 Bảng 2.1: Các đặc tính của dãy tuyến tính có chu kỳ 2m-1 Họ m Kích cỡ Ruv.max Gold Lẻ 2 +1 1+2(m+1) /2 Gold 2(mod 4) 2m +1 1+2(m+2) /2 Kasami (small set) Chẵn 2m/2 1+2(m+2) /2 Kasame (large set) Chẵn 2m/2(2m+1) 1+2(m+2) /2 0(mod 4) 2m/2 1+2m/2` Bent m 2.3. Cấu trúc dãy lồng ghép đa cấp n Định nghĩa 2.1: Cấu trúc cấp 2 của dãy M có chiều dài L  2  1 được biểu diễn: L  2 n -1  T2i L2 i , với T2i, L2i nguyên dương, L2i cũng là một dãy M. Định lý 2.1: Điều kiện cần và đủ để L2i là dãy con cấp 2 của dãy L là : n  0(mod m2i ) , với m2i  [2, m/2]. (2.17) Hệ quả 2.1: Nếu tìm được các giá trị T2i nguyên dương theo (2.20), ta có quan hệ sau: L  0 mod L2 i (2.19) n Định lý 2.2: Số lượng cấu trúc cấp 2 khác nhau của dãy L  2 -1 , ký hiệu e1 e2 e p S n2 , với n nguyên dương, n  n1 n2 ...n p , được xác p 2 định : S n   (e j  1)  2 , với ej là bậc lũy thừa (2.28) j 1 2.3.2. Cấu trúc lồng ghép cấp k n Định nghĩa 2.2: Cấu trúc cấp k của dãy M có chiều dài L  2 -1 là cấu trúc cấp 2 của dãy M cấp k-1 và được biểu diễn: L( k -1)u  Tkv Lkv , trong đó Tk Lk v v nguyên dương, nhỏ hơn L/2 và Lkv cũng là một dãy M. Số cấp lớn nhất mà dãy L  2 n -1 có thể phân hoạch được: p S max n   e j  q , với q là tổng bậc lũy thừa j 1 Số lượng cấu trúc đa cấp của dãy L = 2 n - 1 , ký hiệu S k : 7 (2.32) q S k = S'n2 + S'n3 + ...+ S'nq =  S'nj (2.33) j=2 p với q =  ej là tổng bậc lũy thừa các thừa số của n, S'nj là tổng số j=1 lượng cấu trúc cấp j có thể có. 2.3.3. Cấu trúc tổng quát dãy lồng ghép đa cấp[1]. Định nghĩa 2.3. (cấu trúc tổng quát) k Cho {bn} là một m dãy, có độ dài: L  2n - 1   T L (2.34) i 1 i b j m k thỏa mãn điều kiện:  Ti Lb  2 j - 1 , i  1,2,3,...,k (2.35) i2 j   với n, mj là những số nguyên dương, Lb j là độ dài dãy M cơ sở được lựa chọn và k là số lần mà dãy L có thể phân hoạch liên tiếp được. Dãy {bn} được gọi là dãy có cấu trúc lồng ghép (k+1) cấp. Định lí 2.3. Dãy M có độ dài mj Lb  2 -1 là dãy cơ sở cho cấu trúc đa j n cấp của dãy lớn có độ dài L  2 -1 khi và chỉ khi mj |n. Định lí 2.4. : Cấu trúc tổng quát của mã PN phi tuyến đa chiều, đa cấp kiểu lồng ghép có dạng: (2.45) L  2 n -1  T1 * (T2 * (...(Tk * Lb )...)) k 2.4. THỦ TỤC XÁC ĐỊNH CẤU TRÚC ĐA CẤP 2.4.1. Thủ tục tìm các dãy con của dãy đầu vào Giá trị dãy L= 2n-1 L  2 n -1 Bắt đầu M2i ={m1,m2,...,mi} Gọi chương trình con tìm tập ƯS của n trong khoảng [2, n/2] i=i-1 i <1 S Lmi=2 mi-1 Tmi=L m / Lmi Đ Kết thúc Hình 2.6 Thủ tục tìm các dãy con của dãy L 8 2.4.2. Thủ tục tìm cấu trúc cấp k của dãy L  2 n -1 ban đầu Start Input: value n Input: value degree k Input Sc = 2 Input Flash = False Y Sc > k or Flash N Find sub-sequence degree Sc Sequence degree Sc have sub-sequence? N Y Sc = Sc + 1 Flash = true End Hình 2.7 Thủ tục tìm các cấu trúc cấp k theo giá trị n 2.5. TÍNH TOÁN TẬP HỢP DÃY LỒNG GHÉP PHI TUYẾN Khi biết bậc của dãy con là mj, sẽ xác định được số lượng đa thức nguyên thủy bậc mj: S nt (m j )  N 1 m (1  ); N  2 j  1  m j p| N p (2.48) Số tổ hợp phi tuyến có thể tạo được lồng ghép phi tuyến với bậc mj là S pt (m j ) , được xác định: S pt (m j )  2CS2nt ( m j )  Snt (m j )! (S nt (m j )  2)!  S nt (m j )[S nt (m j )  1] (2.49) 2.6. KẾT LUẬN Bốn định lý cơ bản đã được thành lập và chứng minh. Dựa trên các định lý này, có thể xác định kích thước tập hợp mã lồng ghép phi tuyến theo giá trị bậc mj của dãy con. Các thủ tục để xác định cấu trúc đa cấp đa chiều của mã đã được đề xuất. Phần cuối của chương trình bày về cách xác định kích thước tập hợp mã lồng ghép tuyến tính và phi tuyến theo giá trị bậc mj của dãy con. Nếu sử dụng cách ghép phi tuyến sẽ tạo nên tổ hợp mã phi tuyến rất lớn. 9 CHƯƠNG 3: PHÂN TÍCH VÀ ĐÁNH GIÁ DÃY PHI TUYẾN LỒNG GHÉP ĐA CẤP 3.1. Mở đầu Chương 3, sẽ biểu diễn dãy lồng ghép đa cấp trên trường hữu hạn bằng hàm Vết và biến đổi d. Các đặc tính tương quan, khoảng tuyến tính tương đương sẽ được khảo sát và đánh giá. 3.2. Biểu diễn dãy lồng ghép đa cấp phi tuyến theo biến đổi d 3.2.1. Mở rộng dãy con Cho {bn} là dãy M được tạo bởi đa thức sinh g(d) có bậc n. Nếu biểu diễn dãy {bn} bằng T2 dãy con cấp 2, ta có: T2  2n -1 2m2 -1 (3.4) Gọi b(d) là biến đổi d của {bn} được xác định bởi: b( d )  S (d ) g (d ) (3.5) Gọi {L2b} là dãy con cơ sở cấp 2 có độ dài L2  2 m2  1 và biến đổi d của nó là: L2 (d )  Si (d ) g s (d ) (3.6) Với Si (d) đặc trưng cho trạng thái ban đầu và gs(d) là đa thức sinh của dãy con cấp 2. Dựa trên cấu trúc lồng ghép của {bn}, ta có thể biểu diễn b(d) như sau: T2 1 b(d )   d i L2 i (d T2 ), i  0,1,...T2  1 (3.7) i 0 Với L2i là pha thứ i của dãy {L2b}. Viết lại (3.7) theo bậc của d như sau: b(d )  d 0e0  d T2   d 1e1  d T2   d 2 e2  d T2   ...  d T2 1eT2 1  d T2  (3.8) Các pha cụ thể của {L2b} trong cấu trúc lồng ghép đó được xác định qua 3 bước: Bước 1: Mở rộng dãy con L2(d) ra T2 lần. 10 Bước 2: Biểu diễn biến đổi d của {bn} dưới dạng lồng ghép của L2i (d). Bước 3: Đặt dT = D, tìm các pha tương ứng với: Si ( D)  L2i ( D ) g s ( D) (3.13) Như vậy có thể biểu diễn b(d) như sau: T2 1 G d  i 0 g s  d T2  b(d )   d i L2 i ( D)  (3.14) 3.2.2. Phân hoạch dãy lớn Nếu lấy mẫu {bn} với khoảng cách lấy mẫu T, ta có: a n   bnT   Tr1n ( Tn )  Tr0n (  n ) T T (3.15) m với β= α : vì α là phần tử nguyên tố trên GF(2 ), nên {an} cũng là một dãy M có độ dài N= (2n-1) /T. Nếu lấy mẫu từ bit đầu tiên ta sẽ có dãy con đầu tiên: {a0 , aT , a 2T ,..., a 2m  2 T } . (3.16) Tương tự, khi bắt đầu lấy mẫu từ bit thứ T chúng ta sẽ nhận được các dãy con: {a t 1 , aT  t 1 , a ( 2m  2 )T  t 1} (3.17) Như vậy trên trục thời gian, có thể coi như các dãy con này (các cột của M) được ghép theo thời gian {a nT }{a nT 1 }{a 2 nT 1 }...{a n ( 2 m  2 )T 1 } như hình dưới đây: a a M  a a a a a a  0 T 1 T  2m  2 T 2 m  2 T 1  T 1 2 T 1 (3.18)  2 T 1 2T a a   1 a a nT 11  a nT  1  2 m 1 T 1  a   n 2 m 1 T 1  T khe thời gian: {a nT } {a nT 1} {a n 2T 1 } {a n ( 2m 1)T 1} Hình 3.2: Dãy phân chia thời gian. Như vậy trình tự sắp xếp các cột {a n } chính là thứ tự lồng ghép ITp, ta có thể đối chiếu với bảng biến đổi d các đa thức sinh của dãy M để tìm thứ tự lồng ghép. 3.3. Phân tích dãy phi tuyến đa cấp đa chiều lồng ghép 3.3.1. Dùng hàm Vết (Trace Function) j Xác định thứ tự lồng ghép I n theo các bước sau: Bước 1: Định nghĩa một trình tự sắp xếp: i  I    Trmnj ( j )   Si ; j n n mj j Tr ( )  0; m i  0,1, 2,..., 2 j  2 (3.21) j  0,1, 2,..., S Với S là số lượng dãy con, được xác định: S 2n -1 2 mj (3.22) -1  là nghiệm của f(d) : f ( )  0 j Tiếp theo, thực hiện tính I n : Với n / m j 1 Trmnj ( x)   x2 m jk (3.23) k 0 Si Bước 2: Tính  (mod f(  )). Bước 3: Tính  j theo (2) bằng cách thay Tr ( j )  Tr ( x) của bước 1. Từ đây xác định được thứ tự lồng ghép. Ví dụ với q=10, p=5 ta có các đa thức sinh nguyên tố bậc 10 và các thứ trị lồng ghép như mô phỏng (POLYNO) trong phần phụ lục. 3.3.2. Dùng biến đổi d: Thứ tự lồng ghép được tính bằng phép mở rộng trường con lên trường lớn [1]. 12 Ví dụ 4: Phân hoạch của dãy độ dài 1023 bit, tương ứng n=10. Dãy trên phân hoạch thành 33 dãy con độ dài 31 bit. Theo cả hai phương pháp biến đổi d và hàm vết, ta có trình tự sắp xếp như sau: {12, 21, 01, 29, 06, 17, 00, 06, 06, 02, 04, 16, 21, 07, 22, 04, 29, 16, 13, 16, 15, 08, 24, 12, 04, 05, 25, 15, 10, 18, ∞,17, 08} 3.3.3. Biểu diễn Véc tơ mã đa chiều: Tính chất nhiều chiều của mã phi tuyến lồng ghép đa cấp theo các véc tơ cơ sở (độc lập tuyến tính) là các véc tơ biểu diễn pha (thứ tự lồng ghép). Hình 3.4: Biểu diễn các véc tơ thành phần của mã đa cấp đa chiều Véc tơ fn được tổng hợp từ các véc tơ thành phần en. Các véc tơ thành phần (sin, cosin hoặc en) là trực giao với nhau và có pha khác nhau (tức trên mặt phẳng pha có chiều khác nhau). Phần này giải thích rõ tính chất đa chiều của véc tơ mã lồng ghép như tên luận văn đã gọi. 3.4. ĐÁNH GIÁ DÃY LỒNG GHÉP ĐA CẤP PHI TUYẾN THEO ELS 3.4.1. §Þnh nghÜa Khoảng tuyến tính tương đương (ELS) của một dãy hữu hạn là độ dài của LFSR ngắn nhất tạo ra dãy. Từ các tính chất của biến đổi d, nếu biết chu kỳ L của dãy bn  , ta có thể tìm được đa thức cực tiểu sinh ra dãy đó: 1 d L m(d )  gcd(1  d L , b(d )) (3.25) Với gcd(.) là ước số chung lớn nhất của (.); b(d) là biến đổi d của dãy bn . Khi đó: 13 ELS  L   gcd(1  d L , b(d )) , với  (.) là bậc của đa thức (.) (3.34) T 3.4.2. Ph­¬ng ph¸p tÝnh ELS dùa trªn I p Để khôi phục dãy tuyến tính bậc n, ta cần xác định đúng 2n bit liên tiếp của dãy đó. Đối với dãy phi tuyến, người ta qui đổi ra khoảng tuyến tính tương đương. T Thuật toán tính ELS của dãy lồng ghép dựa trên I p : Bước 1: Tìm đa thức cực tiểu g(d) của dãy con  f n (đa thức sinh) Bước 2: Tìm biến đổi d của dãy lớn dưới dạng: T 1 C (d )   d i Z i (d T ) (3.27) i 0 T (với T=L/N (tỷ số độ dài dãy lớn/độ dài dãy con) và Z i ( d ) là biến đổi d tương ứng với pha thứ i của dãy con  f n  trong cấu trúc lồng ghép I Tp . Bước 3: Áp dụng thuật toán Euclid cho (3.27) để tìm ước số chung lớn nhất của mẫu và tử số. Sau khi giản ước ta có đa thức cực tiểu của C(d) và nhận được ELS. 3.4.3. Kết quả mô phỏng tìm ITp và ELS Ví dụ 6: Cho đa thức sinh: 10000001001 g(d) = d10+d7+1; Dùng chương tr×nh mô phỏng, cho ra các kết quả như sau: Chọn g1s(d) = 1+ d + d2 +d3 + d5 , ta có: IP= {17, 29, 13, 20, 21, 18, 21, 3, 9, 27, 12, 26, 21, 9, 7, 11, 11, 5, 22, 11, 4, 6, 27, 18, 14, 23, --, 24, 16, 21, 0, 11, 10} i) . Chọn: g2s(d) = 1+ d3 + d5 ta có: ELS = deg g2s(dT) – deg K(d) =165–125 =40 ii) . Chọn: g2s(d) =1 + d + d3 + d4 + d5 ELS = deg g2s(dT) – deg K(d) =165–145 =20 Tương tự ta tính với các trường hợp: iii) . Chọn g2s(d) = 1 + d + d2 + d4 + d5 ta có: ELS = deg g2s(dT) – deg K(d) = 165 – 125 =40 14 vi) . Chọn g2s(d) = 1 + d2 + d3 + d4 + d5 ta có: ELS = deg g2s(dT) – deg K(d) = 165 – 85 = 80 3.5. ĐÁNH GIÁ LỒNG GHÉP ĐA CẤP PHI TUYẾN THEO ĐẶC TÍNH TƯƠNG QUAN Hàm tự tương quan của dãy {bn}, ký hiệu là: L 1 Rc  k    bnbn  k (3.31) k 0 Trong trường hợp dãy nhị phân, ta có thể tính hàm tự tương quan R(k) theo công thức: R(k) = (A-D) /(A+D) (3.32) với: A: Số bit giống nhau giữa bn và bn+k; D: số bit khác nhau giữa bn và bn+k. Công thức trên có thể triển khai theo hàm vết như sau:   bn  Tr1n ( t )  (3.33)  bn k  Tr1n ( t  k ) (3.34) Bằng hàm vết, tính tổng {bn+ bn+k} ta tìm ra số bit giống nhau và khác nhau trong tổng đó. Tuy nhiên cách tính bằng hàm vết như trên không đơn giản và khó hình dung, cần có sự hỗ trợ của phần mềm trong ROM. Các dãy con không nhất thiết là dãy M mà chỉ cần thỏa mãn 2 điều kiện: cân bằng P(0) ≈P(1), ACF có 2 giá trị {-1/N và 1} (N: độ dài dãy con) thì dãy lớn vẫn cân bằng và có ACF tốt. Do đó không cần phải kiểm tra từng pha của các dãy con trong tổng {bn+ bn+k} và không thể dựa vào tính chất cộng và dịch để tính được. Điều này cho phép đơn giản hóa ma trận số nguyên và ta có ma trận trùng ITp để kiểm tra các điểm trùng nhau giữa các dãy con của {bn} và {bn+k}. Tại các điểm mà các dãy con không trùng nhau, vì Re = 1-2Pe(1) ≈ 0 ta có Pe(1) = 1/2. Tức là các dãy con trong {bn+ bn+k} cũng sẽ cân bằng. Ma trận trùng ITp được xây dựng để kiểm tra tính chất ACF của dãy lồng ghép được tạo ra (kiểm tra số các dãy con trùng nhau và các dãy con cân bằng). Nếu thỏa mãn điều kiện θ(k) = 1- 2P1(k) (dãy Vj= {bn+bn+k} cân bằng) thì dãy lớn {bn} sẽ cho ACF tốt. 15 3.6. KẾT LUẬN Chương 3 đã mô tả, biểu diễn dãy đa cấp lồng ghép được cấu tạo từ các dãy M con thành phần. Phần trình bày về biểu diễn các véc tơ thành phần của mã đa cấp đa chiều đã đề cập và mô tả tính đa chiều của mã PN phi tuyến lồng ghép trong không gian mã. Các nội dung về tính ELS cho mã lồng ghép đã khẳng định: dùng hai dãy con cơ sở bậc 5, lồng ghép cấp 2 thành bậc 10 (độ dài dãy lớn là 210-1), thì tùy thuộc đa thức sinh được lựa chọn sẽ có các giá trị ELS bằng 20, 40, 80. Trong khi ELS của dãy M bậc 10 bằng 10. Qua ví dụ đã được đề cập, ELS của dãy phi tuyến lồng ghép cấp 2 đã làm tăng ELS lên 2, 4, 8 lần. Như vậy, họ mã phi tuyến đa cấp lồng ghép được xây dựng theo cấu trúc được mô tả trong chương 2 có thể tạo dãy mã có khoảng tuyến tính tương đương lớn, tương quan chéo thấp, kích thước tập hợp mã lớn theo mục đích trải phổ. 16 CHƯƠNG 4: KHẢ NĂNG ỨNG DỤNG CỦA DÃY LỒNG GHÉP ĐA CẤP PHI TUYẾN 4.1. Mở đầu Để khẳng định khả năng ứng dụng của mã trải phổ, ngoài đánh giá về hàm tương quan, khoảng tuyến tính tương đương thì cần thiết phải tiếp tục phân tích đánh giá ảnh hưởng nhiễu đa truy nhập (MAI) của dãy mã trải phổ đa cấp lồng ghép. Nhằm chống chèn phá và không ảnh hưởng đến người dùng khác, mã trải phổ phải gần giống dãy ngẫu nhiên và có nhiễu MAI thấp. 4.2. Nhiễu đa truy nhập với dãy trải phổ lồng ghép phi tuyến 4.2.1 Nhiễu đa truy nhập trong thông tin CDMA Trong thực tế các mã PN không hoàn toàn trực giao với nhau, cụ thể là hàm tương quan chéo (cross-correlation function) giữa chúng có giá trị khác 0. Do đó, nhiễu MAI tồn tại. Thêm nữa, hiệu ứng đa đường tác động xấu tới hàm tự tương quan (auto correlation function) của từng từ mã và tương quan chéo giữa các từ mã (vì thời gian tới khác nhau). Điều đó không chỉ làm tăng MAI và sinh ra giao thoa giữa các ký tự ISI (Inter Symbol Interference). 4.2.2. Phương pháp tiếp cận nhiễu MAI trong CDMA Nhóm giải pháp thứ nhất sử dụng lý thuyết xác suất để tính gần đúng xác suất lỗi BER của kênh nhiễu trắng cộng với giả thuyết mã PN là dãy nhị phân hoàn toàn ngẫu nhiên. Nhóm giải pháp thứ 2 dựa trên các nghiên cứu và mô hình giao thoa giữa các ký hiệu (ISI) mà không quan tâm đến phân bố xác suất của MAI có thể kể tên các phương pháp như: hàm đặc trưng, FF tạo momenl, phương pháp gần đúng hoá chuỗi fourier. 4.2.3. Số lần biến đổi trạng thái B và tính chất thống kê của dãy trải phổ Số lần biến đổi trạng thái B là biến ngẫu nhiên quan trọng nhất và được coi như là thước đo trải phổ của tín hiệu và liên quan trực tiếp tới hàm tự tương quan phi chu kỳ của dãy CN theo công thức: 17