Tóm tắt Luận án Tiến sĩ: Nghiên cứu các mã đối ngẫu của mã xyclic cục bộ

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

43
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án nghiên cứu khảo sát đặc điểm của mã xyclic cục bộ xây dựng từ một lớp kề xyclic trên phân hoạch vành đa thức, làm cơ sở đề xuất phương án, cách tiếp cận để xây dựng mã đối ngẫu của lớp mã xyclic cục bộ xây dựng trên nhóm nhân xyclic.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ: Nghiên cứu các mã đối ngẫu của mã xyclic cục bộ

BỘ GIÁO DỤC ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ NGUYỄN VĂN TRUNG NGHIÊN CỨU CÁC MÃ ĐỐI NGẪU CỦA MÃ XYCLIC CỤC BỘ Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2016
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ - BỘ QUỐC PHÒNG Người hướng dẫn khoa học: GS. TS. Nguyễn Bình TS. Phạm Việt Trung Phản biện 1: PGS. TS. Lê Mỹ Tú Phản biện 2: PGS. TS. Đỗ Trung Tuấn Phản biện 3: TS. Nguyễn Mạnh Linh Luận án được bảo vệ tại Hội đồng bảo vệ cấp Viện theo quyết định số 489/QĐ-VKHCNQS ngày 25 tháng 4 năm 2016 của Giám đốc Viện Khoa học và Công nghệ quân sự, họp tại Viện Khoa học và Công nghệ quân sự vào hồi … giờ … ngày ... tháng … năm … Có thể tìm hiểu luận án tại - Thư viện Viện KH-CNQS - Thư viện Quốc gia
1 PHẦN MỞ ĐẦU Tính cấp thiết của đề tài Thông tin và vấn đề mã hóa thông tin hiện nay vẫn luôn là một trong những lĩnh vực được nhiều chuyên gia hàng đầu trên thế giới tiếp tục nghiên cứu và phát triển dựa trên nền tảng của lý thuyết mã hóa (được bắt đầu nghiên cứu từ những năm 40 của thế kỉ trước). Các nghiên cứu trong lĩnh vực này thường là các nghiên cứu về độ tin cậy của truyền tin trên các kênh truyền có nhiễu, xây dựng các bộ mã tốt và các phương pháp giải mã hiệu quả. Một trong những kết quả nổi bật nhất về lý thuyết mã hóa ứng dụng trong truyền tin là các lớp mã tuyến tính, đặc biệt là lớp mã xyclic. Tiếp tục kế thừa và phát triển theo hướng phát triển mã khối tuyến tính và mã xyclic, mã xyclic cục bộ bắt đầu được nghiên cứu và phát triển. Đây là một loại mã không những bao hàm mọi tính chất của mã xyclic truyền thống mà nó còn có nhiều ưu điểm nổi trội và thiết thực như: khả năng lựa chọn mã đa dạng, tốc độ lập mã và giải mã nhanh hơn. Xuất phát từ thực tế nghiên cứu về mã xyclic cục bộ từ khi ra đời đến nay, nghiên cứu sinh quyết định lựa chọn đề tài “Nghiên cứu các mã đối ngẫu của mã xyclic cục bộ” làm đề tài nghiên cứu cho luận án của mình. Việc nghiên cứu các mã đối ngẫu của mã xyclic cục bộ ngoài mục đích bổ sung, hoàn thiện và làm phong phú thêm về mặt lý thuyết của mã xyclic cục bộ, còn có thể giúp cho việc xây dựng, đánh giá và lựa chọn trên đó các bộ mã tốt trong việc mã hóa và giải mã thông tin một cách chính xác, hạn chế sai sót trong quá trình truyền tin. Mục tiêu nghiên cứu của luận án - Nghiên cứu sâu về mã xyclic cục bộ, tập trung vào các mã xyclic cục bộ xây dựng từ một lớp kề xyclic.
2 - Nghiên cứu khảo sát đặc điểm của mã xyclic cục bộ xây dựng từ một lớp kề xyclic trên phân hoạch vành đa thức, làm cơ sở đề xuất phương án, cách tiếp cận để xây dựng mã đối ngẫu của lớp mã xyclic cục bộ xây dựng trên nhóm nhân xyclic. Đối tượng và phạm vi nghiên cứu Luận án thuộc phạm vi lý thuyết cơ sở, tập trung nghiên cứu khảo sát và chứng minh chặt chẽ về mặt toán học các tính chất của nhóm nhân xyclic, cấp số nhân xyclic và các lớp mã xyclic cục bộ xây dựng từ một lớp kề xyclic trên phân hoạch vành đa thức, đề xuất cách xây dựng mã đối ngẫu của mã xyclic cục bộ xây dựng theo nhóm nhân xyclic. Phương pháp nghiên cứu Phương pháp nghiên cứu tổng hợp, phân tích kết hợp với xây dựng chương trình khảo sát trên ngôn ngữ lập trình Matlab để tìm ra những tính chất mới của mã xyclic cục bộ xây dựng theo nhóm nhân xyclic trên phân hoạch vành đa thức, sử dụng kiến thức toán học để chứng minh tính đúng đắn của các tính chất trên, từ đó đề xuất phương án xây dựng các lớp mã đối ngẫu của mã xyclic cục bộ xây dựng theo nhóm nhân xyclic trên phân hoạch vành đa thức. Luận án sử dụng các kết quả nghiên cứu về các cấu trúc đại số trong lý thuyết đại số tuyến tính, các kết quả nghiên cứu về mã xyclic cục bộ và lý thuyết mã kết hợp với kết quả khảo sát để chứng minh cho tính đúng đắn về những tính chất của mã xyclic cục bộ. Ý nghĩa khoa học và thực tiễn của luận án Luận án là một công trình nghiên cứu tương đối hoàn chỉnh về các lớp mã xyclic cục bộ xây dựng theo nhóm nhân xyclic trên phân hoạch vành đa thức. Những đóng góp mới của luận án: xác định được tính chất của nhóm nhân xyclic: cấp của nhị thức trên phân hoạch vành đa thức; xây dựng và xác định cấp của nhóm nhân xyclic tích bằng cách kiến thiết
3 thông qua các nhóm nhân xyclic thành phần; chứng minh các mã xyclic cục bộ xây dựng từ một lớp kề xyclic trên phân hoạch vành đa thức là mã xyclic ; xác định tính chất của mã xyclic trên một lớp vành đa thức đặc biệt: Vành Mersenne. Với các tính chất đã được xây dựng để thiết lập và tìm kiếm mã đối ngẫu của mã xyclic cục bộ trên các phân hoạch vành đa thức. Cấu trúc của luận án Luận án bao gồm phần mở đầu, kết luận và 3 chương nội dung. Chương 1 trình bày tổng quan về mã khống chế sai, các quan điểm và xu hướng xây dựng mã khống chế sai, các tiêu chuẩn đánh giá về một bộ mã tốt, tập trung chủ yếu vào mã xyclic cục bộ và các kiểu phân hoạch vành đa thức để xây dựng mã xyclic cục bộ. Chương 2 trình bày về các tính chất của nhóm nhân xyclic, vành đa thức và mã xyclic, khảo sát và chứng minh những tính chất mới của nhóm nhân xyclic và cấp số nhân xyclic trên phân hoạch vành đa thức. Chương 3 trình bày chứng minh các mã xyclic cục bộ xây dựng từ một lớp kề xyclic là mã xyclic, tính chất của các mã xyclic xây dựng trên vành Mersenne và các kiến thức cơ sở, nền tảng về mã đối ngẫu của mã tuyến tính nói chung và mã xyclic nói riêng, từ đó đề xuất phương án và thuật toán xây dựng mã đối ngẫu của mã xyclic cục bộ trên vành đa thức. CHƯƠNG 1 TỔNG QUAN VỀ MÃ KHỐNG CHẾ SAI 1.1 Những vấn đề cơ bản và các hướng nghiên cứu về mã khống chế sai 1.2 Các quan điểm xây dựng mã có kiểm tra sai 1.3 Các tiêu chuẩn đánh giá mã khống chế sai 1.4 Các loại mã khống chế sai điển hình
4 1.5 Mã xyclic cục bộ Trong phần này tác giả trình bày về định nghĩa của mã xyclic cục bộ, cách biểu diễn mã xyclic cục bộ, các cách phân hoạch vành đa thức để xây dựng và biểu diễn mã xyclic cục bộ cũng như mối liên hệ giữa mã xyclic cục bộ với các bộ mã tuyến tính được xây dựng trên các cấu trúc đại số cũng như các kết quả đạt được và các hướng nghiên cứu mở đối với mã xyclic cục bộ. Các dạng phân hoạch vành đa thức được sử dụng để xây dựng mã xyclic cục bộ: - Phân hoạch chuẩn. - Phân hoạch cực đại. - Phân hoạch cực tiểu. - Phân hoạch vành thành các cấp số nhân có cùng trọng số. - Phân hoạch vành thành các phần tử có cùng tính chẵn lẻ của trọng số. - Phân hoạch vành thành các cấp số nhân theo modulo… Đối với mã xyclic cục bộ và các mã tuyến tính xây dựng trên các cấu trúc đại số, có thể khái quát và phân loại các dạng mã thuyến tính theo hình 1.6 Qua một thời gian dài nghiên cứu, thành tựu về mã xyclic cục bộ đã có được những kết quả nhất định góp phàn không nhỏ vào lĩnh vực nghiên cứu một dạng mã khống chế sai được ứng dụng và đưa vào thực tiễn, có thể kể đến những thành tựu trong quá trình nghiên cứu về mã xyclic cục bộ như: - Xây dựng được các dạng phân hoạch khác nhau và các kiểu phân hoạch khác nhau của vành đa thức làm cơ sở để xây dựng mã xyclic cục bộ. - Xây dựng một số mã xyclic cục bộ tự trực giao và mã xyclic cục bộ có khả năng tự trực giao.
5 - Xây dựng một số mã xyclic cục bộ đối xứng và tự đối xứng trên các lớp kề (cấp số nhân) đối xứng và tự đối xứng. - Xây dựng được một số lớp mã xyclic cục bộ và mã xyclic trên n 1 các phần tử liên hợp của lũy đẳng nuốt e  x    xi trên các i 0 phần tử liên hợp của zero trên vành chẵn. - Xây dựng một số mã xyclic cục bộ trên các phân hoạch hỗn hợp - Xây dựng được hệ mật đa biểu và trường hợp riêng của nó là hệ mật luân hoàn trên một số loại vành đặc biệt (vành đa thức có n  2k và vành đa thức có hai lớp kề xyclic). Mã tuyến tính Không có cấu trúc Có cấu trúc Vành số Mã AN cylic Mã tuyến tính Vành Vành đa thức n chẵn Vành các lớp ngẫu nhiên ma trận Z2[x]/xn+1 liên hợp n lẻ Phân hoạch Ma trận Ma trận Vành Mã cyclic vành theo các Cauchy Vandermon đồng dư cục bộ nhóm nhân cyclic Mã Gopa Mã BCH Trên 1 Trên 2 vành vành Mã cyclic theo Ideal I= Phân hoạch Phân hoạch Phân hoạch Vành và Hai cực tiểu chuẩn cực đại vành ước vành của vành bất kì Mã cyclic Mã cyclic Mã tựa cục bộ đa cục bộ cyclic tốc độ liên hợp cục bộ Mã cyclic đơn nhịp Mã cyclic với nhịp Mã cyclic với x: I={ximod h(x)} nhịp đa thức Hình 1.6: Phân hoạch các loại mã tuyến tính
6 Với các kết quả đạt được ở trên có thể nói, mã xyclic cục bộ cũng đã được nghiên cứu khá khoàn chỉnh về mặt lý thuyết, tuy nhiên vẫn còn có các hướng nghiên cứu mở để hoàn thiện về mặt lý thuyết mã xyclic cục bộ như: - Nghiên cứu phổ trọng số của các mã xyclic cục bộ - Khảo sát kỹ các cấu trúc các nhóm nhân xyclic và cấp số nhân xyclic trong vành. Tìm tiêu chuẩn nhận biết cho các đa thức có cấp cực đại trong vành. - Xây dựng các ma trận kiểm tra của các mã xyclic cục bộ - Nghiên cứu các mã xyclic cục bộ theo quan điểm lý thuyết hệ thống. - Nghiên cứu các mã xyclic cục bộ trên trường mở rộng GF 2 n   - Nghiên cứu lý thuyết phổ cho các mã xyclic cục bộ. - Nghiên cứu các mã đối ngẫu của mã xyclic cục bộ. - Nghiên cứu trên vành chẵn và các mã được xây dựng trên vành này. KẾT LUẬN CHƯƠNG 1 Chương này đề cấp đến các xu hướng và quan điểm xây dựng mã không chế sai hiện nay trên thế giới, các bộ mã khống chế sai điển hình xây dựng trên cấu trúc đại số và mối quan hệ của những bộ mã này đối với mã xyclic cục bộ, các cách xây dựng và biểu biễn mã xyclic cục bộ trên phân hoạch vành đa thức, các phương pháp phân hoạch vành đa thức để xây dựng mã xyclic cục bộ cùng với những thành tựu quan trọng trong quá trình nghiên cứu về mã xyclic cục bộ cũng như các hướng nghiên cứu tiếp theo cho mã xyclic cục bộ, hướng nghiên cứu của tác giả đối với mã xyclic cục bộ. Nội dung của chương cũng đề cấp đến mối liên hệ của mã xyclic cục bộ và các bộ mã tuyến tính trong bảng phân loại các bộ mã tuyến tính.
7 CHƯƠNG 2 NHÓM NHÂN XYCLIC TRÊN PHÂN HOẠCH VÀNH ĐA THỨC 2.1 Cơ sở đại số Phần này đề cập đến các định nghĩa và tính chất của các cấu trúc đại số liên quan đến luận án: nhóm vành trường. 2.2 Vành đa thức và trường Galois Phần này đề cập đến khái niệm, các định nghĩa cơ bản và tính chất của vành đa thức trên trường Galois, đa thức bất khả quy. 2.3 Lũy đẳng trên vành đa thức theo modulo  x n  1 2.3.1 Khái niệm và các tính chất Định nghĩa 2.16: Trong vành đa thức, R  x  nếu tồn tại một đa thức mà bình phương của nó lại bằng chính nó thì đa thức đó được gọi là lũy đẳng của vành 2  x  /  x n  1 , ký hiệu: e  x  . e  x   e2  x   e  x 2  (2.11) Tính chất của lũy đẳng trên vành đa thức: (i) Tập các lũy đẳng của vành đa thức 2  x  /  x n  1 lập thành một vành con. (ii) e  x  là một lũy đẳng trên vành đa thức, khi đó gcd  e  x  ,1 là ước không tầm thường của  x n  1 Trong mỗi vành đa thức 2  x  /  x n  1 đều tồn tại một lũy đẳng n 1 e0  x    x i , lũy đẳng này được gọi là lũy đẳng nuốt (Swallowing i 0 Idempotent). Trong một vành đa thức  x  /  x n  1 bất kì, với 2 n lẻ luôn tồn tại một lớp kề chỉ chứa một lũy đẳng nuốt e0  x  . Tính chất của lũy đẳng nuốt: - Nếu a  x   2  x  /  x n  1 và W  a  x   là một số lẻ thì a  x  e0  x   e0  x  .
8 - Nếu a  x   2  x  /  x n  1 và W  a  x   là một số chẵn thì a  x  e0  x   0 2.3.2 Các lũy đẳng nguyên thủy và cách xác định. 2.3.2.1 Các chu trình trên n Các chu trình C s (cyclotomic coset) theo modulo n trên trường GF  2  được xác định theo công thức sau:  Cs  s, 2 s, 22 s,..2ms 1  (2.12) Trong đó 2ms 1  s mod n . Khi đó, tập các số nguyên theo modulo n được phân hoạch thành các chu trình. Ta có: 1, 2,.., n  Cs . s Số các phần tử của chu trình C s được gọi là lực lượng của chu trình, ký hiệu: # Cs Tính chất của chu trình Nếu n lẻ, tập các quỹ đạo C  Cs : s  n  tạo thành một phân hoạch trên vành n # C0  1 , s  n , ta có: # Cs | # C1 . Nói một cách khác, chu trình C1 có lực lượng lớn nhất. 2.3.2.2 Sự tồn tại của lũy đẳng nguyên thủy trên vành đa thức Bổ đề 2.1: Đa thức e  x  là một lũy đẳng khi và chỉ khi tập các chỉ số với các hệ số khác không của nó trùng với một hợp nào đó của các chu trình. Ví dụ 2.5: Xét vành 2  x  /  x7  1 , theo định nghĩa về chu trình, ta có: C0  0  e0  x   1 C1  1, 2, 4  e1  x   x  x 2  x 4
9 C3  3,6,5  e3  x   x3  x5  x 6 C0  C1  0,1, 2, 4  e01  x   1  x  x 2  x 4 C0  C3  0,3,6,5  e03  1  x3  x5  x 6 C1  C3  1, 2,3, 4,5,6  e23  x   x  x 2  x 3  x 4  x 5  x 6 C0  C1  C 3  0,1, 2,3, 4,5,6  e013  x   1  x  x 2  x3  x 4  x5  x 6 Đây chính là lũy đẳng nuốt của vành. Như vậy, dựa vào việc phân tích các chu trình, ta có thể nhận thấy, ý nghĩa của các chu trình như sau: - Số các chu trình cho biết số các đa thức bất khả quy trong vành 2  x  /  x n  1 . - Lực lượng của các chu trình cho biết bậc của đa thức bất khả quy tương ứng trong phân tích của nhị thức x n  1 .   - Các số trong chu trình cho biết số mũ tương ứng của các đa thức lũy đẳng e  x  . 2.4 Nhóm nhân xyclic trên vành đa thức 2.4.1 Định nghĩa Nhóm nhân xyclic (CMG: Cyclic Multiplicative Group) là một tập hợp các phần tử đều bằng lũy thừa của một phần tử, gọi là phần tử sinh. A   , 2 ,.. m  (2.13) Trong đó: - A là nhóm nhân xyclic. -  là phần tử sinh - m là cấp của nhóm nhân xyclic, cũng chính là cấp của phần tử sinh  . Cấp của nhóm nhân cylic là tổng số các phần tử của nhóm. Ví dụ 2.6: Xét đa thức a  x   1  x  x 2  x 4 ~  0 1 2 4  trên vành 2  x  /  x9  1 Ta có:
10  0 1 2 4  0 2 4 8  4 5  0 4 7 8  0 3 5 6 7 8 1 8  0 2 5 8      0 5 7 8  3 4 5 6  0 1 3 5 6 7  0 1 2 5  2 7  0 3 4 6 7 8   A   0 1 4 7 2 3 6 7  0 1 5 7  0 2 3 4 6 8 1 3 6 8   0   1 2 3 4 6  0 1 2 3 5 6 1 2 3 4 5 6 7 8   Nhóm nhân A có cấp 21. 2.4.2 Cấp của phần tử trên vành đa thức Rq , n  q  x  /  x n  1 Định nghĩa 2.18: Đa thức   a  x  được gọi là có cấp hữu hạn nếu tồn tại một số nguyên dương m nhỏ nhất sao cho a m  x   e  x  mod  x n  1 (2.14) Trong đó - e  x  là một lũy đẳng nào đó của vành - m được gọi là cấp của đa thức kí hiệu m  ord a  x  . Tính chất về cấp của phần tử trong vành: Bổ đề 2.2: Cho R là một vành hữu hạn, khi đó mọi phần tử a  R đều có cấp hữu hạn Chứng minh: Thật vậy, a  R , ta có dãy a i  , i  1, 2, gồm vô hạn các phần tử thuộc R , mà tập R là một tập hữu hạn các phần tử, do đó sẽ tồn tại các giá trị j, k  1 sao cho a j  a j k (2.15) Từ (2.14) dễ dàng suy ra với mọi giá trị t , ta có: a j  a j  t k (2.16) Với (2.15), thế t  j , ta được: a j  a j1 k  (2.17) Như vậy, từ (2.17), thu được: a  j k 2  a j k 1 a j k 1  a jk Như vậy a jk là một lũy đẳng, do đó a có cấp hữu hạn, kết quả được chứng minh
11 Bổ đề 2.4. Với mọi đa thức   Fq  x  /  x n  1 và mọi số tự nhiên m , ta có: gcd  m , x n  1  gcd  , x n  1 (2.19) Bổ đề 2.5: Mọi ước  của  x n  1 luôn tồn tại lũy đẳng  của Rn sao cho    *|  * Rn* (2.20) Với R là tập các đa thức nguyên tố cùng nhau với  x  1 . * n n Bổ đề 2.6:   Rn , ta có    * trong đó  là một lũy đẳng nào đó của Rn và  * thỏa mãn tính chất gcd  * , x n  1  1 . Nói cách khác, ta có thể viết Rn  E  Rn  Rn* Bổ đề 2.7:   E  Rn  ta có  .Rq*, n     . * |  *  Rq*,n  là nhóm nhân với phần tử đơn vị  . Định lý 2.4.  ,   Rq ,n  Fq  x  /  x n  1 với Fq là trường đặc số p hữu hạn và n không là bội của p . Nếu    Rq*, n , trong đó  là một lũy đẳng nào đó thì #       #  (2.23) 2.4.3 Cấp cực đại của một đa thức trên vành Định lý 2.5: Trong vành đa thức 2  x  /  x n  1 , cấp cực đại của đa thức  được xác định như sau: Nếu n lẻ và xn  1   fi  x  , trong đó fi  x  là các đa thức bất khả quy. Khi đó ord    2m  1 . Trong đó m  max deg fi  x  Nếu n chẵn, n  2 s  2k  1 và x2k 1  1   fi  x  . Khi đó max ord    2 s  2m  1 . Trong đó m  max deg fi  x 
12 2.4.4 Cấp của nhị thức Định lý 2.6: Cấp của nhị thức 1  x j được xác định như sau: ord 1  x j | 2mi  1 ví i j  Ci (2.26) Chứng minh: Xét chu trình Ci  i, i.21 , i.22 ,.., i.2mi 1 Với j  Ci , ta có: 1  x j   1  x 2 j . Rõ ràng 2 j  Ci . 2 Xét nhóm nhân xyclic sinh bởi 1  x j  , nhóm này chứa tất cả các nhị thức 1  x j  với j  Ci . Như vậy mọi phần tử đều có cùng cấp và chúng có cùng cấp và chúng có cấp là ước của 2mi 1 với mi là số nguyên dương nhỏ nhất thỏa mãn i.2mi  i mod n, mi  Ci . Nhận xét: - Các nhị thức 1  x j  với j  Ci là các nhị thức có cấp lớn nhất mi  max mi i Ví dụ 2.9: n  9; m0  1; m1  6; m3  2 ord 1  x   26  1  63 Ta có: ord 1  x3   22  1  3 - Với mọi n ta luôn có nhị thức 1  x  là phần tử có cấp cực đại trong số tất cả các nhị thức. Ví dụ 2.10: Với n  5 ta có: C1  1, 2, 4,3  m1  4  ord 1  x j   24  1  15 Bổ đề 2.11: Với n lẻ, xét nhóm nhân xyclic sinh bởi   a  x  : A  a i  x  ; i  1, 2,.. A  ord    m Khi đó nhóm nhân cylic A sinh bởi  cũng có cấp m với  là đa thức đối xứng (đa thức bù) của  .
13 Chứng minh: Để chứng minh cho trường hợp trên, ta cần phải chứng minh   k . k Thật vậy, với k  2 , do :    0   (với  0 là lũy đẳng nuốt trên vành đa thức) nên :     2 2   2   2 2     2 2 Giả sử đẳng thức trên đúng với giá trị k có nghĩa là     k . k Khi đó ta có:       k 1 k      0   k  0    k 1     k   0   02   k 1   k    1  0 Từ tính chất chẵn lẻ về trọng số của đa thức, ta có  k   cùng tính chất chẵn lẻ và do đó  k    1 là đa thức có trọng số lẻ. Từ tính chất của lũy đẳng nuốt, ta có:  k    1  0   0   k 1 Suy ra:   k 1   0   k 1 A   , 2 , 3 , Do đó: A   , , , 2 3 Bổ đề được chứng minh. Ví dụ 2.11: Cho n  5,  1  x   0,1  0,1 ,  0, 2  ,  0,1, 2,3 ,  0, 4  , 1, 4  ,  0,1, 2, 4  , 3, 4   A   0,3 ,  0,1,3, 4  ,  2,3 ,  2, 4  ,  0, 2,3, 4  , 1, 2  , 1,3  , 1, 2, 3, 4    2,3, 4  , 1,3, 4  ,  4 1, 2,3 ,  0, 2,3  ,  3 ,  0,1, 2   A  1, 2, 4  ,  2  ,  0,1, 4  ,  0,1,3 , 1 ,  0,3, 4  ,  0, 2, 4  ,  0   A  A  ord a  x   15
14 Các phần tử có cùng cấp 15 trên A : 1  x,1  x 2 ,1  x3 ,1  x 4 , x  x 2 , x  x 3 , x  x 4 Các phần tử có cùng cấp 15 trên A : x 2  x3  x 4 , x  x3  x 4 , x  x 2  x 3 ,1  x 2  x 4 ,1  x 2  x 3 2.4.5 Tích của các nhóm nhân xyclic trên phân hoạch vành đa thức Định lý 2.7. Cho   1.Rn* và    2 .Rn* . Kí hiệu k  ord Rn  và h  ord Rn  . Khi đó ta có: (i) ord Rn   | k .h (2.27) (ii) Nếu gcd  k , h   1 thì  k .h khi 1   2 ord Rn      ord  . 1 2  Rn*   khi 1   2 Ví dụ 2.12: Trên vành 2  x  /  x9  1 xét hai nhóm nhân xyclic có các phần tử sinh:   x 2  x 5  x 6  x8 ~  2,5,6,8   x 2  x3  x 6  x 7 ~  2,3,6,7  Ta có: G1   2,5,6,8 , 1,3, 4,7  , 1, 2,3, 4,5,6,7,8 ord  G1   3 G2   2,3,6,7  ,  3, 4,5,6  , 1,3,6,8 ,  2,7  , 1,8 , 1, 2,3, 4,5,6,7,8 ord  G2   7 Nhận thấy hai nhóm nhân trên có cấp là nguyên tố cùng nhau và có cùng lũy đẳng   1, 2,3, 4,5,6,7,8  , dựa vào Định lý 2.7 vừa chứng minh được ở trên, ta có nhóm nhân sinh bởi phần tử sinh       1,6,7,8  sẽ có cấp ord   ord     3.7  21 . Kiểm tra lại: 1,6,7,8 ,  2,3,5,7  ,  4,5  , 1, 4,5,6  ,  0,1,3,6,8 1,8  ,  2,5,6,8 , 1, 2,3,8     G   2, 4,5,6  ,  0, 2,3, 4,6,7  ,  3, 4,5,8  2,7  2,7  ,  0,1,3, 4,5,6  , 1,3, 4,7  ,  2,3,6,7      2, 4,6,7  ,  0, 2,3,5,6,7  , 1,3,6,8  ,  0,1,3,6,7,8  ,  0,3, 4,5,6,7 1, 2,3, 4,5,6,7,8   Rõ ràng ord  G   21 .
15 Như vậy, theo định lý 2.7 nêu trên, có thể nhận thấy, từ các phần tử có cấp nhỏ, ta có thể xây dựng được các phần tử có cấp là n nếu các phần tử được chọn có cấp nguyên tố cùng nhau và có cùng đa thức lũy đẳng. 2.5 Thuật toán tìm cấp của đa thức trong F  x  /  x n  1 Định lý 2.8:   Rq ,n  Fq  x  /  x n  1 với Fq là trường đặc số p hữu hạn và n không là bội của p , ta có   ord Rq ,n  | p ord n p  1 (2.28) Thuật toán xác định cấp của nhóm nhân xyclic Input: a  x   Fq  x  /  x n  1 với p  char  Fq  , n không là bội của p Output: d  ord  a  x   mod  Fq , x1n  1. m  ord n p 2. d  pm  1 k 1 3. Phân tích ra các thừa số nguyên tố của d   pici và lưu vào i 0 mảng k chiều P cặp số  pi , ci  . 4. e  a d mod  Fq , x n  1 . 5. If  a  e  return 1. 6. For i  0 to k  1 do 6.1.  p, c   P i  6.2. t d / p 6.3. j 0 6.4.   While at mod  Fq , x n  1  e and j  c do 6.4.1. d  t // d luôn là bội của ord  a  mod  Fq , x n  1 . 6.4.2. t  d / p // Ứng với j  c  1 thì t không phải là số nguyên. 6.4.3. j  j  1 7. Return d
16 KẾT LUẬN CHƯƠNG 2 Mã xyclic và mã xyclic cục bộ đều xây dựng trên cơ sở của các cấu trúc đại số: nhóm, vành trường. Trong lý thuyết mã đã chỉ ra là mã được xây dựng trên cơ sở cấu trúc đại số càng phức tạp sẽ càng có điều kiện để xây dựng nên các lớp mã tốt. Các kết quả trình bày trong chương 2: Xác định cấp của các nhóm nhân xyclic trên phân hoạch vành đa thức bằng cách kiến thiết thông qua hai phương án: - Xác định cấp của đa thức thông qua việc xác định cấp của các nhị thức trên phân hoạch vành đa thức - Xác định cấp của đa thức tích thông qua việc xác định cấp của các đa thức thành phần với điều kiện các đa thức thành phần có cùng đa thức lũy đẳng và có cấp nguyên tố cùng nhau. - Chứng minh các tính chất và đề xuất thuật toán hiệu quả xác định cấp của đa thức trên một vành hữu hạn bất kì. CHƯƠNG 3 CÁC MÃ ĐỐI NGẪU CỦA NHÓM NHÂN XYCLIC 3.1 Các mã đối ngẫu của mã khối tuyến tính Phần này tác giả đề cập đến cấu trúc của một mã khối tuyến tính xây dựng trên không gian k chiều của không gian tuyến tính n chiều, mã khối tuyến tính hệ thống và phương pháp xây dựng mã đối ngẫu của mã khối tuyến tính tông qua việc biến đổi mã tuyến tình về dạng hệ thống. 3.2 Các mã đối ngẫu của mã xyclic Nội dung phần này tập trung vào định nghĩa mã xyclic, ma trận sinh và ma trận kiểm tra của mã xyclic trên một vành đa thức. 3.3 Các mã xyclic cục bộ xây dựng từ một lớp kề xyclic. Đối với mã xyclic, việc khảo sát và lựa chọn để tìm ra một bộ mã tối ưu trên các vành đa thức có giá trị n lớn là rất phức tạp và khó
17 khăn, thậm chí để nhớ được đa thức sinh của những bộ mã xyclic này cũng là một vấn đề. Để giải quyết được yêu cầu nêu trên, tác giả đề suất thật toán và chứng minh một thính chất của mã xyclic cục bộ xây dựng từ một lớp kề xyclic. Tình chất trên được phát biểu thông qua định lý 3.2, kèm theo đó là thuật toán xác định đa thức sinh của mã xyclic thông qua khảo sát và xây dựng mã xyclic cục bộ từ nhóm nhân xyclic (là một dạng lớp kề xyclic (trên phân hoạch vành đa thức). Định lý 3.2: Mã xyclic cục bộ xây dựng từ một lớp kề xyclic trên phân hoạch vành đa thức cũng là một mã xyclic. Mã xyclic này được xây dựng trên vành đa thức có bậc là cấp của lớp kề xyclic trong phân hoạch của vành đa thức xây dựng lớp kề xyclic. Thuật toán xác định mã xyclic xây dựng từ nhóm nhân xyclic Input: Nhóm nhân xyclic trên phân hoạch vành đa thức. Output: Mã xyclic xây dựng từ nhóm nhân xyclic ở trên Bước 1: - Xây dựng một nhóm nhân xyclic   a  x  bất kì trên vành đa thức. - Đặt n  ord  a  x   - Lập ma trận mã xyclic cục bộ từ các phần tử của nhóm nhân xyclic a  x  thu được. - Sử dụng thuật toán Gauss-Jordan để chuyển ma trận lập được ở trên về dạng ma trận hệ thống - Loại bỏ các hàng bằng 0 (nếu có) của ma trận mã. Ta được ma trận sinh G  m, k  Bước 2: - Chuyển đổi ma trận sinh G  n, k  về dạng các phần tử trong nhóm - Đặt h  x   Ak  k ; h  x   2 /  xn  1 *  xn  1  - Tính g  x      h x  g  x  chính là đa thức sinh của mã xyclic cần tìm.
18 Ví dụ 3.7: Trong vành 2  x  /  x9  1 , đa thức x9  1 được phân tích thành 3 đa thức bất khả quy:  x9  1  1  x  1  x  x 2 1  x3  x 6   Xét nhóm nhân a  x   1  x  x  x 4 ~  0 1 2 4  trên vành 2 2  x  /  x9  1 . Xây dựng nhóm nhân này ta được nhóm nhân:  0 1 2 4  0 2 4 8  4 5  0 4 7 8  0 3 5 6 7 8 1 8  0 2 5 8      0 5 7 8  3 4 5 6  0 1 3 5 6 7  0 1 2 5  2 7  0 3 4 6 7 8   A   0 1 4 7 2 3 6 7  0 1 5 7  0 2 3 4 6 8 1 3 6 8    0   1 2 3 4 6  0 1 2 3 5 6 1 2 3 4 5 6 7 8   Tiến hành lập ma trận và chuyển ma trận lập được về ma trận hệ thống, loại bỏ các hàng có kết quả bằng 0 ta được ma trận mã hệ thống:  0 1 2  3 4  0 11 2  2 3 3 4  0 1 4  0 2 1 3  2 4  0 1 3   G  1 2 4  0 1 2 31 2 3 4  0 1 2 3 4  0 2 3 4  0 3 4  0 4   Dễ dàng nhận thấy G là nhóm nhân được xây dựng trên phân hoạch vành đa thức theo modulo h  x  với h  x   1  x  x 5  1  x  x 2 1  x 2  x 3  . Theo tính chất của mã xyclic cục bộ xây dựng theo modulo h  x  , *  xn  1  ta có g  x      h x  Xét vành đa thức 2  x  /  x 21  1 , ta có: x 21  1  1  x  1  x  x 2 1  x  x 3 1  x 2  x 3 1  x 2  x 4  x 6 1  x 2  x 4  x 5  x 6  Xét *  x 21  1  g  x    1  x  1  x  x3 1  x  x 2  x 4  x 6 1  x 2  x3  x 4  x5  x 6    * 5  1 x  x   1 1 1 1 1 1 1 1 1   x16 1   2  3  4  6  8  11  12  16    x x x x x x x x x   1  x 4  x5  x8  x10  x12  x13  x14  x15  x16 Theo định nghĩa ma trận sinh G của mã xyclic được thiết lập: