Luận án Tách sóng đa truy nhập dùng mạng Hopfield

tích phân có mức cao nên ngõ ra của bộ so sánh cũng ở mức cao. Công tắc S chuyển sang vị trí 1 hay 2 không làm dừng hoạt động của bộ tạo chuỗi giả ngẫu nhiên. 6.1.2. Tinh chỉnh đồng bộ (Tracking or Fine Synchronization) Tín hiệu sau khi được đồng bộ thô sẽ đưa vào mạch tinh chỉnh đồng bộ, sử dụng DLL (Delay Locked Loop) như sau: Hình 1.15: Mạch tinh chỉnh đồng bộ DS Tín hiệu ngõ vào DLL liên quan đến tốc độ chuỗi giả ngẫu nhiên g(t) và chuỗi dữ liệu d(t). Bộ tạo chuỗi giả ngẫu nhiên ở máy thu sẽ tạo ra chuỗi giống như chuỗi thu được nhưng sẽ lệch một khoảng thời gian, tức là g(t + τ) và sau đó sẽ tạo ra hai chuỗi sớm và trễ một lượng Tc/2: g(t + τ - Tc/2) và g(t + τ + Tc/2). g(t + τ - Tc/2) g(t + τ + Tc/2) y(t) VAF VA S(t) BPF Env. Det. PN Generator VCO LPF BPF Env. Det. ∑ VDF VD + – Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 17 vD = g(t) g(t + τ - Tc/2)d(t)cos(ω0t + θ) (1.28) vA = g(t) g(t + τ + Tc/2)d(t)cos(ω0t + θ) (1.29) Các tín hiệu này cho qua các bộ BPF giống nhau có BW = 2fb và tần số trung tâm f0. Băng thông của BPF nhỏ hơn nhiều so với băng thông của chuỗi giả ngẫu nhiên nên chỉ cho giá trị trung bình của g(t) g(t + τ ± Tc/2) đi qua. Do đó ngõ ra của mạch lọc là: vDF ≈ d(t)cos(ω0t + θ) (1.30) vAF ≈ d(t)cos(ω0t + θ) (1.31) Ta thấy rằng giá trị trung bình của tích g(t)g(t + τ ± Tc/2) là hàm tự tương quan của nó: Rg(τ ± Tc/2) = )/T g(t g(t) c 2±τ+ (1.32) Mạch tách sóng bao hình sẽ loại dữ liệu d(t) nên tín hiệu ngõ ra là: ( )2/TR cg −τ và ( )2/TR cg +τ Ngõ vào của VCO là: y(t) = ( )2/TR cg −τ - ( )2/TR cg +τ (1.33) Hình 1.16: VCO Input Tc/2 Tc Rg(τ - Tc) Rg(τ + Tc) -Tc -Tc/2 3Tc/2 -3Tc/2 Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 18 Nếu τ > 0 thì điện áp dương xuất hiện ở ngõ vào VCO làm tăng tần số của VCO và làm giảm τ. Tương tự, nếu τ < 0 thì điện áp âm xuất hiện ở ngõ vào VCO làm giảm tần số của VCO và làm tăng τ. 6.2. Đồng bộ cho hệ thống FH 6.2.1. Đồng bộ thô Như ta đã biết, hệ thống thông tin không kết hợp như FSK sẽ yêu cầu đồng bộ bit để cho phép phục hồi tín hiệu ở đầu thu. Hệ thống kết hợp yêu cầu thêm đồng bộ pha và sóng mang để cho phép giải điều chế tín hiệu. Trong hệ thống trải phổ, đồng bộ pha sử dụng để tạo lại dạng sóng chia (chipping waveform) giống với tín hiệu phát. Quá trình đồng bộ thô FH tương tự như kỹ thuật tìm nối tiếp trong hệ thống DS ngoại trừ bộ tạo chuỗi giả ngẫu nhiên điều khiển tần số nhảy. Sơ đồ khối của mạch đồng bộ thô FH như sau: Hình 1.17: Mạch đồng bộ thô FH Mạch bao gồm bộ trộn, bộ BPF có tần số trung tâm là f0 với băng thông gấp hai lần tốc độ nhảy (BW = 2fH), bộ tách sóng bao hình, bộ so sánh và VCO. VCO bao gồm xung clock, bộ tạo chuỗi giả ngẫu nhiên, bộ tổng hợp tần số. Xung clock được điều khiển bởi ngõ ra bộ so sánh và được truyền tới bộ tạo PN. Bộ tạo chuỗi PN và tổng hợp tần số của máy phát và máy thu giống nhau. Bộ tổng hợp tần số chỉ có một bộ dao động mà tần số của nó được điều khiển bởi chuỗi giả ngẫu nhiên. Do Điều khiển đóng / ngắt Áp ngưỡng Clock fh Toång hôïp taàn soá PN Generator BPF Env. Det. SS Toång hôïp taàn soá PN Generator Clock fh VCO Máy phát Acos(ωit + θ) cos(ωit +ω0t +φ) Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 19 đó, khi chuỗi giả ngẫu nhiên thay đổi trạng thái (mỗi trạng thái tồn tại trong khoảng thời gian TH = 1/fH) thì bộ tổng hợp tần số sẽ nhảy từ f1 tới f2, …, fN và quay trở lại f1. Mạch đồng bộ thô dùng để điều chỉnh sao cho bộ tạo chuỗi PN ở máy thu đồng bộ với máy phát. Giả sử tần số ban đầu tại bộ tổng hợp tần số ở máy thu là f0 + fj trong khi đó tần số thu được là fi với fi ≠ fj. Tại ngõ ra của bộ trộn tần sẽ có tần số f0 + (fj - fi) và không đi qua được BPF. Do đó ngõ ra của mạch tách sóng hình bao là 0 và được so sánh với điện áp ngưỡng nên ngõ ra mạch so sánh là 0 Æ không cho phép bộ dao động hoạt động. Ta thấy nếu tần số tín hiệu nhận được khác fi thì bộ tạo chuỗi PN sẽ không hoạt động và bộ tổng hợp tần số ở đầu thu giữ nguyên tần số. Khi tần số thu là fj thì sẽ có tín hiệu đi qua mạch BPF và ngõ ra bộ tách sóng sẽ lớn hơn điện áp ngưỡng nên ngõ ra của bộ so sánh là 1 Æ bộ dao động hoạt động và bộ tạo chuỗi PN ở máy thu sẽ có trạng thái sớm hơn so với ở máy phát. Dạng sóng của các ngõ ra có dạng như sau: Hình 1.18: Dạng sóng của mạch đồng bộ thô FH Ta thấy rằng cần một thời gian đáp ứng cho bộ tách sóng nên thời gian bộ tạo chuỗi PN ở máy thu thay đổi trạng thái chậm hơn thời gian thay đổi trạng thái của máy phát. Ngoài ra, do sự đáp ứng chậm này, ngõ ra của bộ tách sóng giữ nguyên ở trên mức điện áp ngưỡng và vẫn điều khiển bộ dao động hoạt động trong suốt thời gian khi hai chuỗi PN không cùng trạng thái. Tần số tín hiệu vào Ngõ ra bộ tổng hợp tần số Ngõ ra mạch tách sóng fi fj fk fl fk + f0 fl + f0 fj + f0 Điện áp ngưỡng Ngõ ra mạch SS Ngõ ra mạch điều khiển TH = 1/fH Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 20 6.2.2. Tinh chỉnh đồng bộ Để hiệu quả trong tinh chỉnh, chúng ta cần phải thay thế VCO của mạch đồng bộ thô bằng một VCO mà tần số của nó có thể hiệu chỉnh trên hoặc dưới tần số nhảy. Tần số của VCO được điều khiển bởi điện áp. Điện áp này được đo bởi sự khác biệt pha giữa hai chuỗi giả ngẫu nhiên, dùng để tăng hay giảm tần số VCO để giảm sự khác biệt pha. Thông thường sử dụng PLL (Phase Locked Loop). Sơ đồ khối của hệ thống cho như sau: Hình 1.19: Mạch tinh chỉnh đồng bộ FH (hay mạch tinh chỉnh cổng sớm trễ) Mạch BPF có băng thông đủ lớn để cho dữ liệu đi qua (BW = 2∆f). bộ điều khiển đóng/mở của mạch đồng bộ thô được thay thế bởi VCO hoạt động ở tần số fH. Tuy nhiên, có thể biến đổi trên hay dưới tần số fH nhờ tín hiệu điều khiển ở ngõ ra của mạch LPF làm cho xung clock ở bộ tạo chuỗi PN sẽ biến đổi giữa hai mức điện áp +1 và -1. Bộ tách sóng hình bao, không giống như trong mạch đồng bộ thô, có đáp ứng nhanh. Để đơn giản, ta giả sử rằng ngõ ra của mạch tách sóng hình bao đáp ứng ngay lập tức và không có thời gian trễ. Cổng giữa mạch tách sóng hình bao và mạch LPF gọi là cổng phát (transmission gate). Khi có tín hiệu ra của bộ tách sóng hình bao thì xung clock của VCO sẽ được truyền qua cổng và ngược lại. Nói chung, ta có thể thấy rằng đặc tính hoạt động của cổng như một quá trình nhân nếu xung clock của VCO biến đổi ở hai mức điện áp 1V và ngõ ra của mạch tách sóng là 0 khi không có tín hiệu ra và 1 khi có tín hiệu. Giả sử rằng đồng bộ thô đã được thiết lập, bộ tạo chuỗi PN giữa máy phát và máy thu sẽ trễ một lượng là τ. Trong suốt khoảng trễ này, hai chuỗi không cùng trạng thái nên ngõ ra mạch tách sóng sẽ có giá trị 0 và ngược lại. Do đó, dạng sóng vg = vνvd sẽ có ba mức và được đưa vào mạch LPF nên ngõ ra là vc (giá trị trung bình của vg) điều khiển VCO. Nếu ngõ ra VCO đối xứng và τ = 0 thì vc = 0. Tuy nhiên, trong thực tế thì τ ≠ 0 nên vc sẽ ở một trong hai mức để tăng hay giảm tần số VCO. Phương pháp đồng bộ này gọi là cổng sớm-trễ (early-late gate). Khi |τ| < TH BPF f0 Env. Det. LPF VCO PN Generator Frequency synthesizer Transmission Gate Vv Vd Vg Vccos(ω0t + ωjt +Φ) Acos(ωit + di(t)Ωt + θ) Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 21 thì hệ thống được đồng bộ, ngược lại, hệ thống mất đồng bộ và phải thực hiện lại toàn bộ quá trình. Các dạng sóng mô tả hoạt động của mạch như sau: Hình 1.20: Sóng của cổng sớm trễ 7. Chuỗi giả ngẫu nhiên Thông thường, số lượng chip trên bit N và dạng sóng chip giống nhau cho tất cả các user trong hệ thống CDMA. Để phân biệt được hai dạng sóng nhận dạng thì hai chuỗi nhị phân của chúng phải khác nhau, chuỗi nhị phân này được gọi là chuỗi giả ngẫu nhiên (pseudonoise). Chuỗi giả ngẫu nhiên phải có tính chất sau: 9 Tính cân bằng: tần suất xuất hiện của số bit 0 và bit 1 trong chuỗi là ½ (nghĩa là số lần xuất hiện của bit 0 và bit 1 chênh lệch tối đa là 1). 9 Tính Run: mỗi đường chạy (run length) của một chuỗi nhị phân được định nghĩa là một chuỗi con chỉ chứa giá trị 0 hay 1. Nếu xuất hiện 0 0 -1 -1 Toång hôïp taàn soá Tần số tín hiệu vào fi ± ∆f fj ± ∆f f0 + fi f0 + fj Ngõ ra của VCO vv Áp ra của cổng vg Ngoõ ra boä taùch soùng vd +1 +1 +1 0 t t t t τ Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 22 một số nhị phân khác thì sẽ bắt đầu đường chạy mới. Một chuỗi giả ngẫu nhiên phải có tính Run nghĩa là tổng số các đường chạy có chiều dài 1 bằng ½ tổng số các đường chạy, tổng số các đường chạy có chiều dài 2 bằng ¼ tổng số các đường chạy, tổng số các đường chạy có chiều dài 3 bằng 81 tổng số các đường chạy, … (số các đường chạy có chiều dài n bằng n21 tống số các đường chạy). Ví dụ như chuỗi 000100110101111 có 4 Run 0 (0,0,00,000) và 4 Run 1 (1,1,11,1111) (tổng cộng 8 Run, trong đó có 4 Run có chiều dài 1, 2 Run có chiều dài 2, 1 Run có chiều dài 3 và 1 Run có chiều dài 4) thoả mãn tính Run. 9 Tính tương quan: nếu so sánh một chuỗi giả ngẫu nhiên với chính nó dịch đi một số bit bất kỳ nào đó thì độ chênh lệch giữa số bit giống nhau và khác nhau tối đa là 1 (hàm tự tương quan bằng -1). Để xây dựng chuỗi giả ngẫu nhiên có các tính chất trên, ta dựa vào lý thuyết trường Galois. 7.1. Lý thuyết trường Galois 7.1.1. Nhóm, vành và trường 7.1.1.1. Nhóm (Group) Định nghĩa 1: Một nhóm là một tập hợp G cùng với một phép toán đại số kết hợp có phép toán ngược. Trong lý thuyết nhóm, thông thường phép toán này được gọi là phép nhân và quy ước dùng ký hiệu tương ứng. Các tính chất của nhóm: 9 Tính duy nhất: Trong mọi nhóm G tồn tại duy nhất phần tử e thỏa mãn a.e = e.a = a (a ∈ G). Phần tử e được gọi là phần tử đơn vị của nhóm. 9 Tính đảo: Trong mọi nhóm G, mỗi phần tử a có phần tử nghịch đảo duy nhất sao cho aa-1 = a-1a = e. 9 Tính đóng: nếu a ∈ G và b ∈ G thì ab ∈ G. 9 Tính kết hợp: Nếu a, b, c ∈ G thì (ab)c = a(bc). Số phần tử G của nhóm gọi là bậc của nhóm. Một nhóm được gọi là giao hoán (commutative) hay aben nếu phép toán trong nhóm là giao hoán. Như vậy, một nhóm giao hoán sẽ có thêm tính chất sau: 9 Tính giao hoán: Nếu a ∈ G và b ∈ G thì ab = ba. Định nghĩa 2: Tập hợp các phần tử trong một nhóm G tạo thành một nhóm G' thì G' gọi là nhóm con (subgroup) của G. Nếu G' ⊂ G thì G' gọi là nhóm con thích hợp (proper subgroup) của G. Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 23 Định nghĩa 3: Nếu tồn tại một số nguyên dương k nhỏ nhất sao cho ak = e trong đó a ∈ G và e là phần tử đơn vị của nhóm giao hoán thì k gọi là số mũ (exponent) của a. Tập hợp các phần tử định nghĩa như sau: Ga = {ai: 1 ≤ i ≤ k} (1.34) là một nhóm con của G và được gọi là nhóm tuần hoàn (cyclic group) tạo ra bởi G. Nếu tồn tại một phần tử a sao cho Ga = G thì G có tính tuần hoàn và a gọi là phần tử nguyên thuỷ (primitive element) của G. Số mũ của a là bậc của Ga. Một nhóm tuần hoàn G bậc k sẽ có tính đẳng cấu với tập hợp X = 0,1,…,k-1 dưới phép cộng modul k (tức là tồn tại một song ánh (bijective mapping) hay ánh xạ 1-1 trên (one-to-one onto) từ G vào X). 7.1.1.2. Vành (ring) và trường (field) Xét một tập hợp K với hai phép toán. Ta gọi một trong hai phép toán là phép cộng và phép toán kia là phép nhân. Giả thiết hai phép toán liên hệ với nhau bởi luật phân phối tức là với 3 phần tử a,b,c bất kỳ ∈ K thì ta có: (a + b)c = ac + bc a(b + c) = ab + ac (1.35) Định nghĩa 4: Một tập hợp K được gọi là một vành nếu trên đó đã xác định hai phép toán, cộng và nhân, sao cho cả hai đều có tính kết hợp, liên hệ với nhau bởi luật phân phối, phép cộng có tính giao hoán và có phép toán ngược. Một vành được gọi là giao hoán nếu phép nhân là giao hoán và không giao hoán trong trường hợp ngược lại. Chú ý rằng mỗi vành là một nhóm aben đối với phép cộng. Do đó, tồn tại phần tử 0 sao cho a + 0 = 0 + a = a ∀a ∈ K. Phần tử này cũng đóng vai trò đặc biệt trong phép nhân: tích của một phần tử với phần tử 0 là phần tử 0, nghĩa là a0=0a=0. Định nghĩa 5: Một vành giao hoán P chứa đơn vị và mỗi phần tử khác 0 đều có nghịch đảo gọi là một trường. Một trường bất kỳ có các tính chất sau: 9 Ứng với mỗi cặp phần tử a,b ta có phần tử a + b được gọi là tổng của a và b. 9 Phép cộng là phép giao hoán: a + b = b + a. 9 Phép cộng là kết hợp: a + (b + c) = (a + b) + c. 9 Tồn tại duy nhất phần tử 0 sao cho: a + 0 = 0 + a = a. 9 Với mỗi phần tử a tồn tại duy nhất phần tử đối -a sao cho: a + (-a) = 0. Ứng với mỗi cặp phần tử a,b ta có phần tử ab gọi là tích của a và b. 9 Phép nhân là giao hoán: ab = ba. 9 Phép nhân là kết hợp: a(bc) = (ab)c. 9 Tồn tại duy nhất phần tử đơn vị 1 sao cho: a1 = 1a = a. Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 24 9 Với mọi phần tử a≠0, tồn tại duy nhất phần tử nghịch đảo a-1 để aa-1=a-1a=1. 9 Phép nhân có tính phân phối đối với phép cộng: (a + b)c = ac + bc. Trong vành các số nguyên, ta có thể định nghĩa phép chia như là nghịch đảo của phép nhân. Lúc đó, ta định nghĩa ước số chung lớn nhất gcd (greatest common divisor) của m và n là số nguyên k sao cho k\n và k\m: k = gcd(m,n) (ký hiệu \ chỉ n chia hết cho k hay k chia hết n, tức là tồn tại số nguyên q sao cho n = kq). Nếu k = 1 thì m và n gọi là hai số nguyên tố cùng nhau (relatively prime). Thuật toán Euclide dùng để xác định gcd(m,n) như sau: Nếu m = qn + r và nếu tồn tại một số k sao cho nó là ước số chung của hai trong ba đại lượng m, n, r thì nó cũng là ước số của đại lượng còn lại. Do đó, ta có: gcd(m,n) = gcd(n,r) Giải thuật sau có thể sử dụng để tìm ước số chung lớn nhất của hai số m và n với m > n (giải thuật Euclide): c Đặt m1 = m, n1 = n. d Tính r = m1 mod n1. e If r ≠ 0 then   = = rn nm 1 11 và trở về bước 2. else gcd(m,n) = n1. Kết thúc. ™ Đặc số của trường: Nếu K là một trường, đặc số của K là cấp chung của các phần tử khác 0K của K, nói riêng là cấp của phần tử đơn vị 1K trong nhóm cộng của trường K, tức là số nguyên dương s bé nhất sao cho s1K = 0K. Trường K gọi là có đặc số 0 nếu không tồn tại số nguyên s > 0 sao cho s1K = 0K. Người ta đã chứng minh rằng: trường K có đặc số 0 hoặc có đặc số nguyên tố p. Thí dụ như trường Q các số hữu tỷ, trường R các số thực hay trường C các số phức có đặc số 0 còn mỗi trường Zp các số nguyên mod p (p là số nguyên tố) có đặc số p. Định nghĩa 6: Mở rộng của một trường K là một trường E chứa K như là một trường con. Giả sử K là một trường cho trước, tập hợp tất cả các trường con của K là một tập hợp khác rỗng (K cũng là trường con của K). Nếu P là giao của tất cả các trường con của K thì P là một trường con của K không chứa bất kỳ trường con nào của K khác P và mọi trường con của K đều chứa P. Khi đó, trường con P gọi là trường con nguyên tố của trường K. Nếu K = P thì K gọi là trường nguyên tố. Ta có tính chất: mọi trường là một mở rộng của trường con nguyên tố của nó. Cho K là một trường có trường con nguyên tố là P. Nếu K có đặc số 0 thì P đẳng cấu với trường Q các số hữu tỷ còn nếu K có đặc số nguyên tố p thì P đẳng cấu với trường Zp các số nguyên mod p. Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 25 7.1.2. Vành các đa thức Xét một trường P tuỳ ý. Một đa thức f(z) bậc n trên trường P được viết như sau: f(z) = a0 + a1z + … + anzn = ∑ = n i i iza 0 (1.36) trong đó ai ∈ P ∀i và an ≠ 0. Xét hai đa thức f(z) và g(z) có bậc tương ứng là n và s (giả sử n ≥ s) với các hệ số tương ứng là ai và bi thì: f(z) + g(z) = ∑ = n i i izc 0 (1.37) trong đó ci = ai + bi nếu i ≤ s và ci = ai nếu i > s (bậc của đa thức tổng có thể bằng hay nhỏ hơn n). f(z)g(z) = ∑+ = sn i i izd 0 (1.38) trong đó di = ∑ =+ ikj kjba (bậc của đa thức tích là n + s). Tập hợp các đa thức với hai phép toán nêu trên lập thành một vành giao hoán. Định lý 1: Với mọi đa thức f(z) và mọi đa thức khác không g(z) có thể tìm được các đa thức duy nhất q(z) và r(z) sao cho: f(z) = g(z)q(z) + r(z) (1.39) trong đó bậc của r(z) nhỏ hơn bậc của g(z) hay r(z) = 0. Nếu như r(z) = 0 thì ta nói đa thức f(z) chia hết cho đa thức g(z). Từ đó, ta định nghĩa ước số chung lớn nhất của hai đa thức f(z) và g(z) trên trường P là một đa thức có bậc cao nhất chia hết f(z) và g(z). Ta cũng có thể áp dụng giải thuật Euclide để tìm ước số chung lớn nhất của hai đa thức. Xét phép chia của một đa thức tuỳ ý khác 0 cho đa thức z - a. Ta có: f(z) = (z - a)q(z) + r(z) (1.40) Vì bậc của r(z) nhỏ hơn bậc của z - a nên r(z) là đa thức bậc 0. Từ đó suy ra: f(z) = (z - a)q(z) + f(a) (1.41) Định lý 2 (định lý Bézout): Số dư trong phép chia f(x) cho nhị thức g(x) = x-a là một hằng số bằng f(a). Nếu f(a) = 0 thì a gọi là nghiệm của đa thức f(z). Hệ quả: Nếu a là nghiệm của f(x) thì f(x) chia hết cho x - a. Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 26 Nếu f(a) = 0 thì ta có thể xác định f(z) chia hết cho (z - a)2 hay không bằng cách xác định xem q(z) có chia hết cho z - a hay không và quá trình tiếp tục cho đến khi xác định được số mũ của z - a. Định nghĩa 7: Một đa thức f(z) có bậc n gọi là đa thức monic nếu hệ số an=1. Ta có một số tính chất của vành các đa thức như sau: 9 Một đa thức trên một trường có thể viết dưới dạng một đa thức monic nhân với một hệ số là phần tử của trường. 9 Tích của hai đa thức monic là một đa thức monic. 9 Nếu f(z) và g(z) là hai đa thức có gcd bằng 1 thì g(z)\h(z) nếu g(z)\f(z)h(z). 9 Một đa thức monic có thể phân tích thành tích các đa thức monic tối giản (irreducible monic polynomial). Nếu một đa thức có thể viết dưới dạng tích của hai hay nhiều đa thức (mỗi đa thức có bậc lớn hơn 0) thì đa thức đó gọi là đa thức không tối giản. Ngược lại, ta nói đa thức đó tối giản. Gcd của một đa thức tối giản f(z) và một đa thức bất kỳ phải là 1 hay là f(z). 7.1.3. Cấu trúc trường Galois Vì mọi trường hữu hạn F đều có đặc số nguyên tố p và trường con nguyên tố P của nó đẳng cấu với trường Zp các số nguyên mod p nên ta có thể giả sử rằng F chứa trường Zp. Khi đó, F là một mở rộng hữu hạn của trường Zp và khi xem như không gian vector trên Zp thì F có một cơ sở gồm một số hữu hạn phần tử u1,…,un. Mọi phần tử w ∈ F có một dạng biểu diễn duy nhất thành một tổ hợp tuyến tính theo vector cơ sở: w = a1u1 + … + anun (1.42) Vì có p cách khác nhau để chọn hệ số ai thuộc Zp nên F có tất cả pn phần tử. Định lý 3: Số phần tử trong một trường hữu hạn bằng một lũy thừa của đặc số nguyên tố p của trường đó. Định lý 4: Hai trường hữu hạn có số phần tử bằng nhau thì đẳng cấu. Định lý 5: Với bất kỳ các số nguyên tố p và số nguyên dương n cho trước luôn tồn tại một trường hữu hạn có q = pn phần tử. Từ định lý 4 và 5, ta suy ra tồn tại trường duy nhất (sai khác đẳng cấu) có pn phần tử. Trường này được gọi là trường Galois và ký hiệu là GF(pn). Định lý 6: Nhóm nhân các phần tử khác 0 của một trường hữu hạn là nhóm tuần hoàn. Định lý 7: Với một trường hữu hạn có đặc số p thì ánh xạ a ap là một tự đẳng cấu của trường đó. Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 27 7.1.4. Đa thức tối giản và đa thức nguyên thuỷ 7.1.4.1. Đa thức tối giản Ta xem xét một số ý tưởng cơ bản sau: 9 Một trường hữu hạn có kích thước cho trước là duy nhất tức là các đa thức tối giản khác nhau có cùng bậc trên trường sẽ tạo ra các trường mở rộng có cùng cấu trúc. 9 GF(qn) ⊂ GF(qm) ⇔ nm # 9 Tất cả các nghiệm của các đa thức tối giản nằm trong cùng một trường. 9 Các phần tử của GF(qn) là các nghiệm của đa thức zz np − . Như vậy, đa thức zz np − có thể được phân tích như sau: ∏ ∏ ∈ =− n\m I)z(f p m n )z(fzz (1.43) trong đó Im là tập hợp tất cả các đa thức monic tối giản bậc m trên trường GF(q). Gọi f(z) là một đa thức bậc n trên trường GF(q). Định lý 8: (f(z))m = f(zm) Giải thuật xác định f(z) có phải là đa thức tối giản hay không: c m = 1. d Tính g(z) = gcd( zz np − ,f(z)). e If g(z) ≠ 1 then f(z) chia hết cho g(z). f(z) không tối giản. Đến bước 6. f If m < n/2 then m = m + 1. Trở về bước 2. g f(z) tối giản. h Kết thúc. Trong bước 2, để xác định g(z) ta sử dụng giải thuật Euclide đã đề cập để tính gcd của hai đa thức, nghĩa là phải tìm đa thức dư của hai đa thức, quá trình này có thể khó khăn do bậc của zz np − rất lớn. Giải thuật xác định r(z) = ( zz np − ) mod f(z): Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 28 c g(z) = z, m = 1. d h(z) = (g(z))p mod f(z). e If m < n then m = m+1. g(z) = h(z). Trở lại bước 2. f r(z) = [h(z) - z mod f(z)] mod f(z). g Kết thúc. Ta sử dụng định lý 8 và hai kết quả sau: (a x b) mod n = [ (a mod n) (b mod n) ] mod n (a + b) mod n = [ (a mod n) + (b mod n) ] mod n Số lượng các đa thức tối giản trên trường GF(pn) tính theo công thức sau: Ni = ( )∑ µn\m mnpmnn1 (1.44) Trong đó hàm µ được tính như sau: µ (i) = ( )    − = phöôngchính soámoät cuûa soá öôùclaø i 0 bieät phaântoá nguyeân soá j cuûa tích laø i 1 1i 1 j (1.45) 7.1.4.2. Đa thức nguyên thuỷ Một đa thức tối giản có phần tử nguyên thuỷ là nghiệm của nó gọi là đa thức nguyên thuỷ của trường. Người ta chứng minh được rằng một đa thức f(z) có bậc m là nguyên thuỷ nếu như số nguyên dương n nhỏ nhất để 1 - zn chia hết cho f(z) là n = 2m - 1. Sau khi xác định f(z) là đa thức tối giản, ta xác định f(z) có phải là một đa thức nguyên thuỷ hay không. Đầu tiên ta phải tìm các thừa số nguyên tố của pn - 1. pn - 1 = ∏ i e i ia (1.46) trong đó ai là các số nguyên tố. Số lượng các đa thức nguyên thuỷ có thể tính theo công thức sau: Np = ∏ = −− j i i i n a a n p 1 11 (1.47) Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 29 Trong đó j là số các thừa số nguyên tố của pn - 1. Bảng 2.1: Số lượng các đa thức nguyên thuỷ ứng với một số giá trị n n Np n Np n Np n Np 2 3 4 5 6 7 8 1 2 2 6 6 18 16 9 10 11 12 13 14 15 48 60 176 144 630 756 1800 16 17 18 19 20 21 22 2048 7710 8064 27594 24000 84672 120032 23 24 25 26 27 28 29 356960 276480 1296000 1719900 4202496 4741632 18407808 Giải thuật xác định đa thức tối giản f(z) có phải là đa thức nguyên thuỷ hay không: c i = 1, j = số thừa số nguyên tố. d g(z) =       − i n a p z 1 mod f(z). e If (g(z) ≠ 1) and (i < j) then i = i + 1. Trở lại bước 2. f If i = j then f(z) là đa thức nguyên thuỷ. Else f(z) không là đa thức nguyên thuỷ. g Kết thúc. 7.2. Đặc tính tương quan 7.2.1. Một số khái niệm cơ bản Gọi ℜn là tập hợp tất cả các vector có n chiều tức là phần tử của ℜn gồm các vector có dạng như sau: x = (x0,x1,…,xn-1) trong đó xi ∈ ℜ ∀i ∈ [0,n-1]. Tích của hai vector x và y được định nghĩa là: = ∑− = 1 0 n i iiyx (1.48) Tách sóng đa truy nhập dùng mạng Hopfield Giới thiệu chung GVHD: TS. Phạm Hồng Liên Trang 30 Gọi T là quá trình thực hiện dịch vòng một vector sang trái một thành phần, tức là Tx = (x1,x2,…,xn-1,x0). Nếu ta thực hiện dịch vòng k lần một vector thì kết quả dịch sẽ là Tkx = (xk,xk + 1,…,xn-1,x0,x1,…,xk-2,xk-1). Nếu k = n thì Tnx = x. Trong trường hợp k > n thì ta sẽ có: Tkx = Tk mod nx. Tương tự như vậy, ta định nghĩa quá trình dịch phải như trên và được ký hiệu là T-kx. Ta có thể thấy rằng T-kx = Tn-kx và T-nx = x. Chu kỳ của x định nghĩa là số nguyên dương m nhỏ nhất sao cho Tmx = x. Dễ thấy rằng m < n. Ta định nghĩa chuỗi tuần hoàn tổng quát dài vô hạn xây dựng bởi x bằng cách thay thế vector x liên tục, tức là chuỗi tuần hoàn tổng quát của x có dạng: x-2,x-1,x0,x1,…,xn-1,xn,xn+1,… trong đó xi = xn+i. Từ vector x, ta gọi w là vector ngược của x nếu: wi = xn-1-i tức là w có dạng: w = (xn-1,xn-2,…,x1,x0) 7.2.2. Tự tương quan và tương quan chéo của các chuỗi Trong hệ thống thông tin dùng kỹ thuật trải phổ CDMA, các chuỗi giả ngẫu nhiên sử dụng trong hệ thống đòi hỏi các tính chất sau nhằm đảm bảo tách được tín hiệu đã trải phổ: 9 Một chuỗi PN phải tách biệt với chính nó dịch chuyển đi một số chu kỳ bit. 9 Một chuỗi PN phải tách biệt với các chuỗi khác sử dụng trong hệ thống. Các chuỗi này thường là chuỗi tuần hoàn. Xét hai tín hiệu x(t) và y(t). Đại lượng dùng để đo khả năng phân biệt giữa hai tín hiệu x(t) và y(t) dựa trên h