i

MỤC LỤC
THUẬT NGỮ VÀ CÁC CHỮ VIẾT TẮT............................................................ii
DANH MỤC CÁC HÌNH VẼ................................................................................iii
DANH MỤC CÁC BẢNG BIỂU...........................................................................iv
Phụ lục..................................................................................................................115


ii

THUẬT NGỮ VÀ CÁC CHỮ VIẾT TẮT
A-CDMA
ACFs
CCFs
CLT
d
DS
DS-CDMA
ELS
FH/SS

Asynchronous-CDMA
Autocorrelation functions
Cross Correlation Functions
Central Limit Theorem
d-Transform
Direct Sequences
Direct Sequences-CDMA

Equivelent Linear Span


GF
GO
GQO
IGA
IFW
LAS
Lcz
LFSR
LS
MAI
PN
QS
QS - CDMA
SF
SGA
SIGA
TH/SS

Hệ thống CDMA không đồng bộ
Hàm tự tương quan
Hàm tương quan chéo
Định lý giới hạn trung tâm
Biến đổi d
Dãy trải phổ trực tiếp
CDMA trải phổ trực tiếp
Khoảng tuyến tính tương đương
Hệ thống trải phổ nhảy tần
Trường Galois
Trực giao suy rộng

Hình 1.3a: Hàm tự tương quan chuẩn hóa của dãy M độ dài N
Hình 1.3b: Hàm tự tương quan chuẩn hóa của dãy PN tạo từ dãy M
Hình 2.1: Mô tả sơ đồ của thanh ghi dịch phản hồi tuyến tính LFSR
Hình 2.2: Ví dụ dãy ghi dịch với g(d) =d5 + d4 + d2 + d +1
Hình 2.3: Bộ tạo dãy Gold đối với g1(d)=d3+d+a và g2(d)=d3+d2+1
Hình 2.4: Giản đồ véc tơ của cấu trúc đa cấp
Hình 2.5: Biểu đồ véc tơ mô tả phân hoạch dãy {bn} 4 cấp
Hình 2.6: Biểu đồ véc tơ mô tả phân hoạch dãy L=224-1 thành 4 cấp
Hình 2.7:Thủ tục tìm các dãy con của dãy L
Hình 2.8: Thủ tục tìm các cấu trúc cấp k theo giá trị n
Hình 2.9: Các giao diện của phần mềm tính cấu trúc đa cấp
Hình 3.1: Hai bộ trộn nối tiếp
Hình 3.2: Dãy phân chia thời gian
Hình 3.3: Ánh xạ GF(q) xuống GF(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
Hình 3.5: Mô phỏng tính K(d) cho đa thức bậc
Hình 3.6: Mô phỏng tính G(d), ITp cho da thức bậc 10.
Hình 4.1: Đồ thị Pe phụ thuộc vào B, K và N
Hình 4.2: Các đặc tính của dãy bít NRZ 10110010 tuần hoàn
Hình 4.3: Các đặc tính của dãy tín hiệu sau xáo trộn

14
14
31
32
36
39
48
51
52


38
43
49
50

Bảng 3.1: Biến đổi d của dãy M bậc 2 và bậc 3
Bảng 3.2: Biến đổi d của các dãy M có đa thức sinh 1+d2+d3

60
71

Bảng 3.3: Ma trận trùng để tính hàm tương quan

77

Bảng 4.1: Biến đổi trạng thái B của dãy phi tuyến với bậc n=8, B= 127
Bảng 4.2: Tính Pe của dãy phi tuyến với bậc n=8, B= 127
Bảng 4.3: Tính Pe của dãy phi tuyến với bậc n=6, B= 31
Bảng 4.4: Tính Pe của dãy phi tuyến với bậc n=9, B= 255
Bảng 4.5: Các giá trị của Q(x)
Bảng 4.6: Các đa thức đặc trưng của LFSR dùng trong mô phỏng
Bảng 4.7: Tín hiệu vào ở trường hợp 1 sau xáo trộn
Bảng 4.8: Tín hiệu vào ở trường hợp 2 sau xáo trộn
Bảng 4.9: Tín hiệu vào ở trường hợp 3 sau xáo trộn
Bảng 4.10: Tín hiệu vào ở trường hợp 4 sau xáo trộn

85
86
86

minh [13], [15], là có nhiều khả năng lựa chọn, khoảng tuyến tính tương đương lớn
(độ phức tạp lớn), hàm tự tương quan ACF nhọn và một số họ dãy có vùng tương
quan chéo thấp (Low cross correlation zone), thích hợp cho các hệ thống CDMA
tựa đồng bộ (Quasi Synchronized CDMA) và chống hiệu ứng đa đường, lệch đồng
bộ một cách hiệu quả, [7], [17], [24], [27], [34], [36], [37], [50], [54]. Dãy giả ngẫu
nhiên lồng ghép 2 chiều được đề xuất trong [21]. Đây là loại dãy trải phổ tốc độ
cao, hàm tương quan tốt và có cấu trúc lồng ghép.
Có thể nói kỹ thuật lồng ghép là một giải pháp công nghệ hữu hiệu để xây
dựng các dãy với các tính chất mong muốn và vì thế được nghiên cứu sâu rộng
trong thời gian gần đây. Về mặt toán học, có thể biểu diễn và phân tích dãy có cấu


2

trúc lồng ghép bằng hai công cụ trên trường hữu hạn là dùng hàm vết (Trace
Function) hoặc dùng biến đổi d (d-Transform). Các giải thuật biến đổi d và hàm vết
được sử dụng để biểu diễn và phân tích dãy lồng ghép. Giải thuật biến đổi d trong
khảo sát ACF, tính ELS, phân tích trạng thái của LFSR giúp chúng ta có thể mở
rộng các lớp dãy lồng ghép thành các dãy lồng ghép tổng quát (dãy con cân bằng
hay lồng ghép nhiều cấp). Do đó mở ra khả năng tìm kiếm thành công các họ mã có
cấu trúc lồng ghép nhiều cấp, nhiều chiều hơn nhằm ứng dụng cho thông tin thế hệ
mới. Tuy nhiên, đến nay việc tổng quát hóa cấu trúc lồng ghép (số cấp >2) 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
Về ý nghĩa 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 mới 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ổ ". Giới thiệu những khái niệm cơ bản
về công nghệ CDMA, các kỹ thuật trải phổ, các đặc tính yêu cầu đối với dãy trải
phổ trong CDMA. Đồng thời các dãy phi tuyến, dãy có tương quan đặc biệt, dãy có
cấu trúc lồng ghép hai cấp, biểu diễn dãy trên trường GF(2) cũng được giới thiệu.
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.


4

Chương 2: "Thuật toán tìm cấu trúc của mã lồng ghép đa cấp". Chương này
đề cập đến những kiến thức cơ bản về dãy M, đặc tính trải phổ và các ứng dụng của
dãy M. Từ các đặc tính phổ quát của dãy M và sử dụng công cụ toán học để xây
dựng cấu trúc lồng ghép đa cấp mới. Các định nghĩa mới dãy đa cấp lồng ghép được
đưa ra, các định lý về cấu trúc đa cấp của dãy được thành lập. Từ các cấu trúc của
dãy cấp 2, cấp k và cấu trúc tổng quát sẽ xây dựng thủ tục xác định cấu trúc cấp k,
cấu trúc đa cấp khi biết độ dài dãy lớn hoặc độ dài dãy con cơ sở. Vì vậy, có thể xây
dựng được các dãy có cấu trúc lồng ghép với độ dài và số cấp mong muốn.
Chương 3: "Phân tích và đánh giá dãy phi tuyến lồng ghép đa cấp". Hai
công cụ toán học trên trường hữu hạn là hàm vết và biến đổi d đã được sử dụng để
biểu diễn và phân tích dãy lồng ghép trên trường hữu hạn. Đây là tiền đề cho việc
thiết kế các dãy lồng ghép đa có vùng tương quan thấp Lcz. Mã lồng ghép đa cấp sẽ
được đánh giá theo các đặc tính khoảng tuyến tính tương đương (ELS) và đặc tính

“tạp âm". Tại phía máy thu, thực hiện giải trải phổ bằng cách nhân tín hiệu thu được
với cùng một dãy nhị phân được dùng để trải phổ ở phía máy phát. Quá trình giải
điều chế sẽ khôi phục lại được số liệu băng gốc nguyên thuỷ, cho phép máy thu lọc
bỏ phần lớn nhiễu băng rộng. Sau khi trải phổ, độ rộng băng của tín hiệu cần thu
giảm đến giá trị ban đầu B, trong khi độ rộng băng của nhiễu vẫn là W. Vì vậy, quá
trình lọc đối với độ rộng băng tần tín hiệu có thể được sử dụng để loại bỏ công suất
nhiễu trong SNR của số liệu băng gốc. Độ lợi xử lý N = W/B là tỷ số của tốc độ
chíp và tốc độ ký hiệu, còn được gọi là hệ số trải phổ (SF). Nó thể hiện mức độ
chống nhiễu băng rộng sẽ đạt được nhờ sử dụng quá trình trộn (nhân) và lọc (tương
quan). Như vậy, hệ thống trải phổ DS thu được một độ lợi xử lý chống nhiễu do
hiện tượng nhiều tia từ tín hiệu cần thu và có khả năng chống hiện tượng jamming
hoặc nhiễu từ những thuê bao khác. Hệ thống trải phổ trực tiếp có thể tách ra tín
hiệu cần thu và khử nhiễu do hiện tượng nhiều tia đã được khai thác bởi kỹ thuật


6

"rake", kỹ thuật này sẽ thu các tia sóng đến máy thu qua nhiều đường khác nhau
(multipath) sử dụng các mạch phát dãy PN có các thời gian trễ khác nhau, sắp xếp
lại các tia sóng này theo thời gian và sau đó kết hợp chúng để thu được một độ lợi
phân tập. Như vậy, mã trải phổ giả ngẫu nhiên PN có vai trò rất quan trọng trong kỹ
thuật trải phổ.
Đối với hệ thống CDMA không đồng bộ (A-CDMA, asynchronous CDMA),
không yêu cầu có sự đồng bộ giữa các dãy trải phổ được truyền, độ trễ giữa các dãy
trải phổ được truyền là bất kỳ. Do đó, để loại bỏ giao thoa đa truy nhập, cần thiết kế
một tập dãy trải phổ có hàm tự tương quan (ACFs-autocorrelation functions) dạng
đầu đinh và các mức tương quan chéo (CCFs-crosscorrelation functions) bằng 0.
Tuy nhiên, theo các định lý biên Welch và các lý thuyết giới hạn khác, về mặt lý
thuyết, không thể thiết kế các dãy có thuộc tính lý tưởng như vậy. Do đó, trong hệ
thống A-CDMA, dãy trải phổ thông thường được thiết kế sao cho có mức tự tương

Kỹ thuật trải phổ (SS), về lý thuyết bắt nguồn từ những ý tưởng của
C.Shannow, J.Pierce từ những năm 50 của thế kỷ trước [43], đã đi qua quãng
đường phát triển dài. Về thực tiễn, kỹ thuật SS được sử dụng từ thời trước
chiến tranh Thế giới II, đồng thời ở Mỹ và Đức. Vào thời gian đó nó là hoạt
động tối mật. Những cải tiến sau đó, đặc biệt là trong lĩnh vực CDMA, đều xảy ra
sau Thế chiến II. Gần đây SS/CDMA được xem xét lại và tỏ ra là phương tiện hấp
dẫn để xác định vị trí xe cộ, nhờ khả năng xác định cự li đồng thời của nó trong
khi đang sử dụng kênh. Ngoài ra nó còn cung cấp giải pháp cho vấn đề tắc
nghẽn phổ. Đến nay (năm 2011), công nghệ 3G dựa trên WCDMA và CDMA2000
đã và đang được triển khai ở nhiều nước trên thế giới, cung cấp các dịch vụ: thoại,
điện thoại thấy hình, video (phim), thư điện tử, truyền dữ liệu, truy cập internet.
Một hệ thống thông tin số được coi là hệ thống SS nếu tín hiệu phát chiếm dải
thông lớn hơn nhiều dải thông tối thiểu cần thiết để truyền tin tức và sự mở rộng
dải thông được thực hiện nhờ một mã không phụ thuộc vào dữ liệu. Khi mới đưa
vào ứng dụng, các kĩ thuật SS được dùng trong các hệ thống thông tin quân sự. Ý
tưởng là làm cho tín hiệu phát có dạng giống như tạp âm đối với máy thu không
chủ định, làm cho máy thu này khó phát hiện và lấy ra tin tức. Để biến đổi tin tức
thành tín hiệu giống như tạp âm, ta dùng mã được giả thiết là ngẫu nhiên để mã


8

hóa tin tức và mong muốn mã này càng ngẫu nhiên càng tốt. Tuy nhiên, máy thu
chủ định phải biết được đó là mã nào để tạo ra một mã y hệt và đồng bộ với mã
phát đi để giải mã tin tức. Tín hiệu giả ngẫu nhiên được thiết kế để có dải thông
rộng hơn nhiều dải thông của tin tức. Tin tức được biến đổi bởi mã sao cho tín
hiệu nhận được có dải thông xấp xỉ dải thông của tín hiệu ngẫu nhiên. Có thể
xem việc biến đổi như là quá trình mã hóa và được gọi là trải phổ. Ta nói rằng tin
tức được trải ra bởi mã giả ngẫu nhiên tại máy phát. Máy thu phải giải trải tín
hiệu tới để đưa dải thông về dải thông ban đầu của tin tức [57]. Kỹ thuật SS đã

sử dụng được gán một mã trải phổ, mã này là một tín hiệu được tạo ra bởi quá trình
điều chế tuyến tính một dãy tín hiệu giả ngẫu nhiên có tốc độ cao. Số liệu (tín hiệu
mang tin) được nhân với mã trải phổ này để tạo ra một dãy tín hiệu có tốc độ cao
hơn rất nhiều so với tốc độ ban đầu, và do đó phổ tín hiệu cũng rộng ra tương ứng.
Trong DS-CDMA, nhiều người sử dụng cùng dùng chung một băng tần và phát tín
hiệu của họ đồng thời. Máy thu sử dụng tín hiệu giả ngẫu nhiên chính xác để lấy ra
tín hiệu mong muốn bằng cách giải trải phổ. Các tín hiệu khác xuất hiện ở dạng
nhiễu phổ rộng công suất thấp tựa tạp âm. Tín hiệu trải phổ phản ứng tốt với kênh
đa đường. Trong kênh truyền đa đường, tín hiệu gốc bị phản xạ bởi những chướng
ngại như các công trình, đồi núi. Do đó, máy thu nhận được những bản sao của tín
hiệu gốc với độ trễ khác nhau. Nếu mức độ trễ các bản sao lớn hơn một chip, máy
thu có thể phân tách chúng (bằng máy thu Rake).


10

Trải phổ nhảy tần (Frequency hopping FH-CDMA), bản chất của công nghệ
này là tần số mang tín hiệu thay đổi một cách tuần hoàn. Kiểu thay đổi tần số được
xác định bởi dãy M, tập hợp dãy tần số mã sóng mang có thể chiếm được gọi là tập
hợp nhảy. Băng tần mà hệ thống nhảy tần chiếm khác với băng tần của hệ thống trải
phổ trực tiếp. Hệ thống trải phổ chiếm toàn bộ dải tần, còn hệ thống nhảy tần chỉ
chiếm một phần nhỏ băng tần nhưng vị trí của phần băng tần đó thay đổi theo thời
gian. So sánh với DS-CDMA, FH-CDMA có một số đặc điểm khác biệt. Đó là FHCDMA dễ đồng bộ hơn. Do tập hợp nhảy rất lớn, thời gian nhảy cũng sẽ dài hơn độ
rộng chip của DS-CDMA, nên sai số đồng bộ cho phép lớn hơn. Mặt khác, băng tần
FH-CDMA bị chiếm không liên tục nên có thể cho phép bộ tổng hợp tần số bỏ qua
nhiều đoạn của băng tần. Điều đó có nghĩa là hiệu suất sử dụng băng tần lớn hơn.
Xác suất nhiều người sử dụng phát cùng một tần số, cùng một thời gian là rất bé.
Nên tín hiệu của người sử dụng ở xa trạm gốc cũng có thể được trạm gốc thu tốt vì
người ở gần có thể phát ở tần số khác. Tác động của hiệu ứng xa-gần được hạn chế
bớt so với DS-CDMA. Tần số phát FH-CDMA thay đổi theo thời gian nên nhiễu đa

Mã PN trải phổ được xem là khả dụng nếu nó có được đặc tính quan trọng là
giống như dãy ngẫu nhiên, hàm tự tương quan phải nhọn, tương quan chéo ở mức
thấp, số lượng tổ hợp mã lớn đáp ứng yêu cầu, độ phức tạp của mã đủ đáp ứng cho
việc khó thám mã, giải mã với đối tượng không mong muốn. Đồng thời phải đảm
bảo các yếu tố của công nghệ thiết kế, tạo mã.
1.3.1. Các đặc tính ngẫu nhiên của dãy trải phổ
Theo các tài liệu đã mô tả, dãy giả ngẫu nhiên nhị phân tuần hoàn có 3 đặc
tính cơ bản. Đặc tính cân bằng, trong mỗi chu kỳ của dãy, xác suất xuất hiện của bit
1 và 0 là bằng nhau (mỗi loại bằng 1/2). Thực tế trong mỗi chu kỳ, số bit 1 và 0 sai
khác nhau là một đơn vị, sở dĩ như vậy là do bộ tạo dãy loại trừ trạng thái tất cả các
bit bằng zero, và sự sai khác nhau 1 bit này không có ý nghĩa gì khi dãy cực dài.
Đặc tính chạy (Run), sự kéo dài của bit 0 hoặc 1 liên tiếp trong dãy được định nghĩa
là bước chạy. Một bước chạy được định nghĩa là một nhóm bit cùng loại (1 hoặc 0)
liên tiếp tồn tại trong dãy. Trường hợp có một bit 0 hay bit 1 xen giữa các bit 1 hay
0 liên tiếp cũng được xem là kết thúc một bước chạy và bắt đầu một bước chạy mới.
Độ dài bước chạy là số bit trong bước chạy. Đặc tính chạy trong dãy giả ngẫu nhiên
phải thỏa mãn là trong một chu kỳ của dãy số và tổng quát có: 1/2 n số bước chạy có


12

độ dài là n. Đặc tính tương quan, từ một dãy giả ngẫu nhiên đã có, nếu ta dịch
chuyển theo cách dịch đi lần lượt từng vị trí bit sang phải hoặc sang trái, ta sẽ thu
được dãy M mới có số phần tử trùng hợp và không trùng hợp với dãy ban đầu. Tính
tương quan của dãy thỏa mãn nếu so sánh trong một chu kỳ các dãy tạo ra và các
dãy dịch chuyển, nếu các số hạng trùng hợp và các số hạng không trùng hợp sai
khác nhau không quá một đơn vị đếm. 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
Xét tín hiệu tất định x(t), hàm tự tương quan chuẩn hóa của nó được xác định

t ' +T p

0

x(t + τ ) x(t ) dt

(1.2)

Với t' là hằng số bất kì. Chú ý rằng Rx(τ ) trong (1.1) cũng tuần hoàn với chu
kì Tp. Mã ngẫu nhiên đóng vai trò rất quan trọng trong các hệ thống SS, vì chúng
không chỉ xác định mức nhiễu đa truy nhập, chẳng hạn nhiễu của nhiều người sử
dụng cùng kênh và tự nhiễu do đa đường mà còn phải đáp ứng các thuộc tính khác
về mã. Chúng phải đáp ứng được các thuộc tính tương quan chéo giữa các dãy khác
nhau trong cùng một tập hợp và đáp ứng thuộc tính tự tương quan giữa các dịch pha
của chính dãy đó. Tuy nhiên nếu mã này là ngẫu nhiên thực sự, thì ngay cả máy
thu mong muốn cũng không thể lấy được tin tức vì chưa có phương pháp nào để
đồng bộ với mã ngẫu nhiên thực sự, như vậy hệ thống trở nên vô dụng. Thay


13

vào đó ta phải dùng mã giả ngẫu nhiên, là mã tất định mà máy thu mong muốn
biết được, còn đối với máy thu không mong muốn thì nó giống như tạp âm.
Dãy trải phổ PN được tạo ra từ mạch tạo dãy nhị phân tuần hoàn với chu kỳ
nhất định và quy luật xác định. Các thuật toán và kỹ thuật tạo dãy được mô tả rất rõ
ràng trong [8], [9], [10]. Ta sử dụng ci , i=integer≡L, c-1, c0 , c1 , L để chỉ dãy PN.
Giả sử N là chu kì của nó tức là ci + N= ci . Ta cũng gọi N là độ dài của dãy PN, và
dãy tuần hoàn chỉ đơn thuần là phần mở rộng có chu kì của dãy dài N. Để dãy ai
là dãy giả ngẫu nhiên tốt, giá trị của ai phải độc lập với giá trị a j với bất kì i ≠ j.
Để điều này xảy ra thì dãy không được lặp lại tức chu kì phải là ∞. Vì dãy PN là

…...

Tc

N = 15; {ci , i = 0,……,14} = {1,1,1,-1,1,1,-1,-1,1,-1,1,-1,-1,-1,-1}

Hình 1.2: Một ví dụ của tín hiệu PN c(t), tạo nên từ dãy PN có chu kì N = 15
Như vậy, với 2 dãy số khác nhau c(t) và c'(t) hàm tương quan chéo liên tục được
định nghĩa:
T

1
Rcc' (τ ) = ∫ c'(t ).c (t + τ )dt , trong đó: T = NTc là chu kỳ dãy.
T 0

(1.4)

Nếu c = c', ta có hàm tự tương quan:
T

1
Rcc(τ ) = Rc(τ ) = ∫ c(t ).c(t + τ )dt
T 0

(1.5)


14

rc(k)

T n =1

(1.6)

Ngoài ra tương quan chuẩn hóa của dãy giả ngẫu nhiên còn được định nghĩa
khác (khi so sánh một chu kỳ của dãy đã có với dãy được tạo ra do dịch chuyển một
khoảng thời gian τ) là:

R=

A− D
A+ D

(1.7)

Với A là số phần tử giống nhau, D là số phần tử khác nhau. Hình 1.3a, 1.3b, biểu
diễn hàm tự tương quan chuẩn hóa của dãy M và của dãy PN tạo từ dãy M.
Trong quá trình thiết kế mã, yêu cầu về đặc tính tương quan và các yêu cầu
khác như đặc tính tương quan, độ phức tạp, độ dài từ mã, số lượng tổ hợp mã phải
được xem xét và được thỏa hiệp ở một giới hạn nhất định.
1.4. Các dãy trải phổ phi tuyến và dãy có tương quan đặc biệt
Các dãy tuyến tính được tạo ra bằng thuật toán cộng modulo 2 là thuật toán
tuyến tính trong trường nhị phân GF(2). Các dãy này có các đặc tính tương quan tốt,


15

trong đó dãy bé Kasami là tốt nhất. Các dãy khác như dãy Gold, dãy Kasami lớn
đều có kích thước tương đối lớn. Tuy nhiên, giá trị ELS của chúng thấp, khoảng
cùng bậc với ELS của dãy M trong khi các giá trị ACF và CCF kém hơn dãy M

≤ R(l ) ≤ 2 −( t +1) Π i
, ∀l ≠ 0 mod N1, N2, N3 ... Nt.
i =1
i =1
Ni
Ni
t

4 −t Π

(1.11)

Giới hạn trên này liên quan chặt chẽ tới tần suất của giá trị logic "1" trong
t

−t
dãy tích, được cho bởi: P (1) = 2 Π
i =1

Ni +1
Ni

(1.12)

Nói chung, giá trị trung bình của ACF chuẩn hoá của mọi dãy M nhị phân
đều liên quan chặt chẽ với bình phương của tần suất này, cho nên khi n>>1, giá trị


16


*

i

(1.14)

i =0

và dãy tích u.u*:
m −1 m −1

u n u n = ∑∑ Ai A j (α 2 + 2 ) n
*

*

i

j

(1.15)

i =0 j =0

Nếu không có hệ số ai nào bằng 0, dãy tích sẽ có ELS = (m+1) /2.
Nói chung, một số hệ số có thể bằng 0. Do đó giá trị này chỉ là giới hạn trên
của dãy tích nhận được bằng thuật toán phi tuyến bậc 2. Có thể mở rộng phương
pháp trên cho các dãy tích nhận được bằng thuật toán phi tuyến bậc cao hơn.
Dãy tích bậc r được mô tả :
m −1 m −1

 

N
số Ai nào bằng 0, giới hạn trên của ELS sẽ là: m = ∑  ÷
i
r

(1.17)

1.4.2. Các dãy hàm Bent
Các dãy hàm Bent là các dãy nhị phân có chu kỳ k=2m-1, m=0mod4 được tạo
nên bằng cách ánh xạ các phần tử của GF(2m) vào trong tập hợp nhị phân (-1,1) qua
một phép ánh xạ Γ(αt), trong đó αt, t= 0,1,..., 2m-1 biểu diễn các phần tử của GF(2m)
theo phần tử nguyên tố α, [36]. Phép ánh xạ Γ(.) được xây dựng trên cơ sở tập hợp
các 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 2 m/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)

Đây cũng chính là giới hạn trên của dãy Kasami bé, các dãy hàm Bent có độ
phức tạp được đo bởi ELS khá lớn. Đặt n=m/2, k=n/2 và gọi d là tham số về bậc
của hàm Bent được sử dụng để cấu trúc dãy, ta có:
Ε max

 m  n 
= ∑   +  2 d −

1 n  d
 2 + m  + n , với m ≥ 8, d =2.
2 d 
2

(1.21)

Ε min =

1 n  d
 2 + m = 8 , với m ≥4, d=2
2  d 

(1.22)

Nếu m đủ lớn, các giới hạn này đạt giá trị khá lớn làm cho các dãy hàm Bent
thích hợp cho thông tin vũ trụ dải rộng, đặc biệt là các hệ thống chống nghe trộm.
Trong [32], phương pháp thiết kế hàm Bent theo mô hình tiến hóa được đề xuất, đã
đem lại họ hàm Bent có độ phức tạp lớn, đặc tính tương quan tốt.


18

1.4.3. Các dãy có đặc tính tương quan đặc biệt
Nhằm xử lý nhiễu giao thoa và xác suất lỗi bit [16], [47], một số dãy có các tính
chất tương quan đặc biệt cũng được quan tâm nghiên cứu trong thời gian gần đây.
a) Mã trực giao và các dãy có vùng không tương quan ZCZ
Một trong những dãy sớm có ý nghĩa thực tiễn nhất là "Dãy trực giao N
nhịp" của N.Suehiro [36], từ cơ sở toán học của các công trình của Tyryn [56]vào
những năm 1960. Dãy trực giao N nhịp được định nghĩa :


L
ρ( S1 ; S 2 ; i ) ∆ j =L1
 1 ∑S1 , j S 2∗, j +i với i= -1,...,-L+1

 L j =1−i

và :

S1=(S1,1,...,S1,L), S2=(S2,1,...,S2,L)

(1.26)

(1.27)

Một dãy trực giao N-nhịp độ dài L được định nghĩa là dãy S (định nghĩa bởi
(1.23), (1.24) ) có hàm tự tương quan được định nghĩa như (1.25), lấy các giá trị 0
tại độ lệch một số nguyên lần N (i=nN) trừ độ lệch 0.
ρ(S,i) =0 với i = ± N, ± 2N, ...

(1.28)

Một cặp dãy trực giao có độ dài L (S1 và S2) được định nghĩa như (1.23),
(1.24) có hàm tương quan chéo được định nghĩa như (1.26) lấy giá trị 0 cho các độ
lệch một số nguyên lần N ( kể cả i=0) :
ρ(S1, S2;i) =0 với i = 0, ± N, ± 2N,...

(1.29)



Lp = [ TM/Tc ] + 1 = 21
Trong đó, chỉ có 3 tia nằm trong IFW, 18 tia còn lại ngoài IFW. Điều này dẫn đến
xuất hiện giao thoa. Về ý nghĩa vật lý, điều này là do độ trễ truyền sóng lớn hơn 20
lần khung cửa sổ đồng bộ.


20

Theo tính toán ở [17], [33], loại mã LAS trên ưu việt khi tốc độ số liệu là
1,2288Mchips/s đến 3,84Mchips/s. Nếu tốc độ là 30Mchips/s thì hiệu năng kém hơn
loại bình thường. Có 2 cách khắc phục nhược điểm đó:
- Chia ra nhiều băng sóng mang, mỗi sóng có tốc độ chips 3,84 Mbit/s.
- Mở rộng khoảng xê dịch đồng bộ cho phép - trả giá bằng hàm tương quan.
Lúc đó, không phải là ZCZ (zero correlation zone) mà là Lcz (low corelation zone).
c) Dãy có vùng tương quan thấp Lcz [15], [20], [49],[56], [58], [59].
Với một tập hợp các dãy a, b trên GF(p), mỗi dãy có độ dài n, cho a,b ∈ A, a
= (a0, a1, ... an-1), b = (b0, b1, ... bn-1) và δ là một số nguyên khá bé (1,3 ...). Vùng
tương quan thấp Lcz được định nghĩa là:
| τ |< L

Lcz = max | L | Ra ,b (τ ) ≤ δ 
0
21

Giả sử c(x) là đa thức sinh của LFSR và c(x) chia hết cho xj+x+1, j được gọi
là chỉ số nhảy của LFSR. Về mặt kỹ thuật, điều này được thực hiện bằng cách tăng
tốc độ xung nhịp lên j lần, hoặc sau mỗi nhịp thì XOR cả trạng thái LFSR.
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, dãy tuyến tính có độ
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 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, rất có khả năng ứng dụng
trong Cryptography.
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 2 m-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ã và độ phức tạp, 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.
Xét hai phương pháp đầu tiên. Hai phương pháp này có điểm khác biệt. Ở
phương pháp thứ nhất là sử dụng cấu trúc ghép tuyến tính đa cấp (thứ tự lồng ghép
ITp) và lồng dãy con có đặc tính ngẫu nhiên được tạo từ dãy M khác thay thế tạo mã
phi tuyến. Phương pháp thứ hai là trực tiếp tạo mã phi tuyến bằng cách tạo dãy tích