Tóm tắt Luận án 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 các phần tử liên hợp của lũy đẳng nuốt   1 0 n i i e x x    trên các 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ó 2kn  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 ngẫu nhiên Vành ma trận Vành đa thức Z2[x]/x n +1 Vành các lớp liên hợp Ma trận Cauchy Vành đồng dư Phân hoạch vành theo các nhóm nhân cyclic Mã cyclic cục bộ Ma trận Vandermon Mã Gopa Mã BCH Mã cyclic theo Ideal I= Trên 1 vành Trên 2 vành Phân hoạch cực tiểu Phân hoạch cực đại Vành và vành ước của vành Hai vành bất kì Phân hoạch chuẩn Mã cyclic cục bộ đa tốc độ Mã cyclic cục bộ liên hợp Mã tựa cyclic cục bộ Mã cyclic đơn nhịp Mã cyclic với nhịp đa thức Mã cyclic với nhịp x: I={x i mod h(x)} n chẵn n lẻ 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 2n - 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  1nx  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 / 1nx x  , ký hiệu:  e x .      2 2e x e x e x  (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 / 1nx x  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 ,1e x là ước không tầm thường của  1nx  Trong mỗi vành đa thức    2 / 1nx x  đều tồn tại một lũy đẳng   1 0 0 n i i e x x    , lũy đẳng này được gọi là lũy đẳng nuốt (Swallowing Idempotent). Trong một vành đa thức    2 / 1nx x  bất kì, với n lẻ luôn tồn tại một lớp kề chỉ chứa một lũy đẳng nuốt  0e x . Tính chất của lũy đẳng nuốt: - Nếu      2 / 1na x x x  và   W a x là một số lẻ thì      0 0a x e x e x . 8 - Nếu      2 / 1na x x x  và   W a x là một số chẵn thì    0 0a x e x  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 sC (cyclotomic coset) theo modulo n trên trường  2GF được xác định theo công thức sau:  12,2 ,2 ,..2 smsC s s s  (2.12) Trong đó 12 mods m s 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,.., s s n C . Số các phần tử của chu trình sC được gọi là lực lượng của chu trình, ký hiệu: # sC Tính chất của chu trình Nếu n lẻ, tập các quỹ đạo  :s nC C s   tạo thành một phân hoạch trên vành n 0# 1C  , ns  , ta có: 1# | #sC C . Nói một cách khác, chu trình 1C 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    72 / 1x x  , theo định nghĩa về chu trình, ta có:    0 00 1C e x       2 41 11,2,4C e x x x x     9     3 5 63 33,6,5C e x x x x         2 40 1 010,1,2,4 1C C e x x x x         3 5 60 3 030,3,6,5 1C C e x x x           2 3 4 5 61 3 231,2,3,4,5,6C C e x x x x x x x             2 3 4 5 60 1 0133 0,1,2,3,4,5,6 1C C C e x x x x x x x           Đâ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 / 1nx x  . - 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  1nx  . - 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.  2, ,.. mA    (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    2 41 ~ 0 1 2 4a x x x x    trên vành    92 / 1x x  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 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 A                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    , / 1nq n qR x x  Đị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      mod 1m na x e x x  (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  ord m 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  , 1,2,ia i   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ị , 1j k  sao cho j j ka a  (2.15) Từ (2.14) dễ dàng suy ra với mọi giá trị t , ta có: j j t ka a   (2.16) Với (2.15), thế t j , ta được:  1j kja a    (2.17) Như vậy, từ (2.17), thu được:       2 1 1j k j kj k j ka a a a       Như vậy j ka  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    / 1nqF x x   và mọi số tự nhiên m , ta có:    gcd , 1 gcd , 1m n nx x    (2.19) Bổ đề 2.5: Mọi ước  của  1nx  luôn tồn tại lũy đẳng  của nR sao cho **| * nR    (2.20) Với * nR là tập các đa thức nguyên tố cùng nhau với  1nx  . Bổ đề 2.6: nR  , ta có *  trong đó  là một lũy đẳng nào đó của nR và * thỏa mãn tính chất  *gcd , 1 1nx   . Nói cách khác, ta có thể viết   *n n nR E R R Bổ đề 2.7:  nE R  ta có  * * * *, ,. . |q n q nR R       là nhóm nhân với phần tử đơn vị  . Định lý 2.4.    ,, / 1nq n qR F x x     với qF là trường đặc số p hữu hạn và n không là bội của p . Nếu *,q nR  , 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 / 1nx x  , cấp cực đại của đa thức  được xác định như sau: Nếu n lẻ và  1n ix f x  , trong đó  if x là các đa thức bất khả quy. Khi đó  ord 2 1m   . Trong đó  max deg im f x Nếu n chẵn,  2 2 1s kn   và  2 1 1k ix f x   . Khi đó    max ord 2 2 1s m   . Trong đó  max deg im f x 12 2.4.4 Cấp của nhị thức Định lý 2.6: Cấp của nhị thức 1 jx được xác định như sau: ord 1 | 2 1 v i i mj ix j C  í (2.26) Chứng minh: Xét chu trình  11 2, .2 , .2 ,.., .2 imiC i i i i  Với ij C , ta có:   2 21 1j jx x   . Rõ ràng 2 ij C . Xét nhóm nhân xyclic sinh bởi  1 jx , nhóm này chứa tất cả các nhị thức  1 jx với ij C . 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 2 1i m  với im là số nguyên dương nhỏ nhất thỏa mãn .2 mod ,im i ii i n m C  . Nhận xét: - Các nhị thức  1 jx với ij C là các nhị thức có cấp lớn nhất maxi i i m m Ví dụ 2.9: 0 1 39; 1; 6; 2n m m m    Ta có:     6 3 2 1 2 1 63 1 2 1 3 ord x ord x         - 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 5n  ta có:     41 11,2,4,3 4 1 2 1 15jC m ord x        Bổ đề 2.11: Với n lẻ, xét nhóm nhân xyclic sinh bởi  a x  :   ; 1,2,..iA a x i   ord A 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 2k  , 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ó:            1 0 0 1 2 0 0 1 01 k k k k k k k                               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 đó 1k   là đa thức có trọng số lẻ. Từ tính chất của lũy đẳng nuốt, ta có:   0 01k      Suy ra:   1 1 1 0 k k k         Do đó:     2 3 2 3 , , , , , , A A           Bổ đề được chứng minh. Ví dụ 2.11: Cho  5, 1 0,1n x                                  0,1 , 0,2 , 0,1,2,3 , 0,4 , 1,4 , 0,1,2,4 , 3,4 0,3 , 0,1,3,4 , 2,3 , 2,4 , 0,2,3,4 , 1,2 , 1,3 , 1,2,3,4 A                                       2,3,4 , 1,3,4 , 4 1,2,3 , 0,2,3 , 3 , 0,1,2 1,2,4 , 2 , 0,1,4 , 0,1,3 , 1 , 0,3,4 , 0,2,4 , 0 A           ord 15A A a x   14 Các phần tử có cùng cấp 15 trên A : 2 3 4 2 3 41 ,1 ,1 ,1 , , ,x x x x x x x x x x       Các phần tử có cùng cấp 15 trên A : 2 3 4 3 4 2 3 2 4 2 3, , ,1 ,1x x x x x x x x x x x x x          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. nR  và * 2. nR  . Kí hiệu ord nRk  và ord nR h  . Khi đó ta có: (i)  ord | . nR k h (2.27) (ii) Nếu  gcd , 1k h  thì      * 1 2 1 2 1 2. . khi ord ord khi n n R R k h             Ví dụ 2.12: Trên vành    92 / 1x x  xét hai nhóm nhân xyclic có các phần tử sinh:     2 5 6 8 2 3 6 7 ~ 2,5,6,8 ~ 2,3,6,7 x x x x x x x x           Ta có:                         1 1 2 2 2,5,6,8 , 1,3,4,7 , 1,2,3,4,5,6,7,8 ord 3 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 7 G G G G     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 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 G            Rõ ràng  ord 21G  . 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    / 1nF x x  Định lý 2.8:    , / 1nq n qR F x x    với qF là trường đặc số p hữu hạn và n không là bội của p , ta có   , ord ord | 1n q n p R p  (2.28) Thuật toán xác định cấp của nhóm nhân xyclic Input:      / 1nqa x F x x  với  arch qp F , n không là bội của p Output:     1ord mod , nqd a x F x 1. ordnm p 2. 1md p  3. Phân tích ra các thừa số nguyên tố của 1 0 i k c i i d p    và lưu vào mảng k chiều P cặp số  ,i ip c . 4.  mod , 1d nqe a F x  . 5. If  a e return 1. 6. For 0i  to 1k  do 6.1.    ,p c P i 6.2. /t d p 6.3. 0j 6.4. While   mod , 1t nqa F x e  and j c do 6.4.1. d t // d luôn là bội của    ord mod , 1nqa F x  . 6.4.2. /t d p // Ứng với 1j c  thì t không phải là số nguyên. 6.4.3. 1j j  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        2; / 1nh x A k k h x x    - Tính     * 1nx 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    92 / 1x x  , đa thức 9 1x  được phân tích thành 3 đa thức bất khả quy:    9 2 3 61 1 1 1x x x x x x       Xét nhóm nhân    2 41 ~ 0 1 2 4a x x x x    trên vành    92 / 1x x  . 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 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 A                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 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 G          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     5 2 2 31 1 1h x x x x x x x        . Theo tính chất của mã xyclic cục bộ xây dựng theo modulo  h x , ta có     * 1nx g x h x         Xét vành đa thức    212 / 1x x  , ta có:       21 2 3 2 3 2 4 6 2 4 5 61 1 1 1 1 1 1x x x x x x x x x x x x x x x                Xét        * 21 * 3 2 4 6 2 3 4 5 6 5 16 2 3 4 6 8 11 12 16 4 5 8 10 12 13 14 15 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x g x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x                                                  Theo định nghĩa ma trận sinh G của mã xyclic được thiết lập: 19           4 5 8 10 12 13 14 15 16 5 6 9 11 13 14 15 16 17 2 2 6 7 10 12 14 15 16 17 18 3 3 7 8 10 13 15 16 17 18 19 3 4 8 9 12 14 16 1g x x x x x x x x x x xg x x x x x x x x x x x x g x x x x x x x x x x xG x g x x x x x x x x x x x x g x x x x x x x x                                                           17 18 19 20x x x                   1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 G                 Dùng công thức Gauss-Jordan biến đổi về ma trận hệ thống, ta có ma trận:                        1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 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 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 G                         Có thể thấy, đây chính là ma trận mã xyclic cục bộ xây dựng theo modulo  h x trên vành    212 / 1x x  hay là ma trận mã xyclic cục bộ được xây dựng theo nhóm nhân  a x với   2 41a x x x x    trên vành    92 / 1x x  mà chúng ta đã xây dựng ở trên. 3.4 Các mã xyclic trên vành Mersenne Nội dung phần này đề cập đến một tính chất của mã xyclic cục bộ xây dựng theo nhóm nhân xyclic trên vành Mersenne, tính chất đó được trình bày theo bổ đề 3.3 Bổ đề 3.3: Trên vành Mersenne ( 2 1mn   ), tất cả mã xyclic cục bộ xây dựng từ nhóm nhân xyclic là mã xyclic được xây dựng trên vành này và và các vành ước của nó. 20 3.5 Các mã đối ngẫu của mã xyclic cục bộ xây dựng từ nhóm nhân xyclic trên phân hoạch vành đa thức Trong phần này, tác giả đề xuất thuật toán 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 trên phân hoạch vành đa thức. Phân tích những khó khăn gặp phải trong quá trình nghiên cứu về mã xyclic cục bộ và mã đối ngẫu của nó. Dựa trên những nội dung và tính chất được trình bày trong phần đầu của chương, từ đó đề xuất thuật toán xây dựng mã đói ngẫu của mã xyclic cục bộ xây dựng từ nhóm nhân xyclic trên phân hoạch vành đa thức. Thuật toán xác định mã đối ngẫu của mã xyclic cục bộ xây dựng từ nhóm nhân xyclic: Input: Đa thức xây dựng mã theo nhóm nhân xyclic trên phân hoạch vành đa thức    2 / 1mx x  Output: Mã đối ngẫu của mã xyclic cục bộ xây dựng từ nhóm nhân xyclic 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 các cột bằng 0 (nếu có) của ma trận mã. Ta được ma trận hệ thống  ,G n k với k là số các hàng của ma trận 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        2; [ ] / 1nh x A k k h x x x    - Mã đối ngẫu của mã xyclic cục bộ xây dựng theo nhóm nhân xyclic ở trên là mã có đa thức sinh  h x 21 Nhận xét: Đối với mã xyclic cục bộ xây dựng từ nhóm nhân cylic, sau khi chuyển về ma trận hệ thống có thể dễ dàng chỉ ra ngay được đa thức sinh của mã xyclic cũng như mã đối ngẫu của mã xyclic này: - Để tìm đa thức sinh của mã xyclic truyền thống tương ứng, ta lấy giá trị của hàng cuối cùng của ma trận hệ thống đọc các giá trị từ trái sang phải và loại bỏ đi 1k  giá trị đầu tiên. - Để tìm mã đối ngẫu của mã xyclic, từ ma trận hệ thống ta lấy giá trị của cột thứ 1k  của ma trận hệ thống đọc các giá trị từ dưới lên trên và thêm một giá trị k vào cuối giá trị nhận được. Bảng 3.2: Kết quả khảo sát mã xyclic cục bộ xây dựng từ nhóm nhân xyclic và mã xyclic tương ứng trên vành    72 / 1x x  1nx   a x VĐT mã tt  h x  g x 7 1x  (0,1,2), (1,3), (2,3), (0,1,2,3,5) 7 1x  (0,1,2,4) (0,1,3) (0,1,3), (0,2,3), (0,3,4), (2,3,4) (0,1,2,3,4) (0,2,3,4) (0,2,3) (1,2), (1,2,3,5) (0,1,3) (0,1,2,4) (3,4), (0,2,3,4), (1,2,3,4) (0,2,3) (0,2,3,4) 3.6 Đánh giá hiệu quả giải mã mã xyclic và mã xyclic cục bộ Đối với 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, tác giả đã chứng minh được mã xyclic cục bộ xây dựng từ một lớp kề xyclic là mã xyclic, như vậy có thể sử dụng các phương pháp giải mã của mã xyclic cho mã xyclic cục bộ và ngược lại, có thể sử dụng phương pháp giải mã cho mã xyclic cục bộ cho mã xyclic, nghiên cứu sinh tiến hành xây dựng, đánh giá hiệu năng thông qua hai bộ mã tương đương với nhau đối với mã xyclic  15,5,7 sau: Mã xyclic  15,5,7 với ma trận sinh:      2 4 2 3 4 2 4 5 8 101 1 1 1g x x x x x x x x x x x x x x x                22 Bộ mã xyclic này chính là 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    52 / 1x x  với   31a x x x   Quá trình đánh giả hiệu quả giải mã mã xyclic được thực hiện theo sơ đồ hình 3.4. Tạo bit Mã hóa Điều chế BPSK Kênh AWGN Tính BER Giải điều chế BPSK Giải mã Noise Hình 3.4: Sơ đồ tạo quá trình tạo mã và đánh giá hiệu quả sửa sai của bộ mã Với bộ mã xyclic trên, có thể sử dụng phương pháp giải mã theo syndom để giải mã cho mã xyclic. Với mã xyclic cục bộ, sử dụng phương pháp giải mã ngưỡng để tiến hành khảo sát đánh giá hiệu quả sửa sai của hai bộ mã. Kết quả đánh giá, mô phỏng được trình bày trong hình 3.6 Từ kết quả nhận được, có thể thấy về cơ bản không có sự khác biệt về hiệu năng của hai mã này, cho dù sử dụng hai phương pháp giải mã khác nhau. Về mặt cấu trúc, các mã này đều có 0 7d  và sửa được 3 sai ngẫu nhiên. Các mã này đều là các mã  15,5,7 là những mã có độ dài ngắn. Hình 3.6: Kết quả mô phỏng đánh giá tỷ lệ lỗi bit của hai bộ mã xyclic và mã xyclic cục bộ 23 Với kết quả mô phỏng thu được như trên, ta có thể áp dụng các sơ đồ truyền tin, mã hóa và giải mã tín hiệu để có thể nâng cao hiệu năng của chúng theo sơ đồ truyền tin được trình bày trong Hình 3.7. Hình 3.7: Các sơ đồ mã hóa tín hiệu dùng cho mã hóa và giải mã mã xyclic cục bộ xây dựng theo nhóm nhân xyclic và mã xyclic. Với cách sử dụng sơ đồ turbo đơn giản trên, hiệu năng của mã có thể tăng lên tương đối khi sử dụng với các bộ mã có độ dài lớn với cỡ 100n bit KẾT LUẬN CHƯƠNG 3 Trong nội dung của chương đã thực hiện được một số công việc sau: Khảo sát và chứng mình đượ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    2 / 1nx x  là mã xyclic với n là cấp của lớp kề xyclic trên phân hoạch vành đa thức. Kết quả này được chứng minh chặt chẽ về mặt toán học. Khảo sát và chứng minh được tính chất của nhóm nhân xyclic trên phân hoạch vành đa thức đối với vành Mersenne. Từ những tính chất đã chứng mih được ở trên đề xuất thuật toán tìm kiếm 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. 24 KẾT LUẬN Những đóng góp chính của luận án - Xây dựng một số phương án kiến thiết nhằm xác định cấp của lớp kề xyclic trên phân hoạch vành đa thức: o Chứng minh tính chất và xây dựng thuật toán tính cấp của các đa thức trên phân hoạch vành đa thức trên một vành hữu hạn bất kì. o Chứng minh tích của các nhóm nhân xyclic là một nhóm nhân xyclic với cấp được xác định là ước của bội số chung nhỏ nhất của các nhóm nhân xyclic thành phần. o Chứng minh các tính chất được sử dụng để xác định cấp của cấp số nhân xyclic trong trường hợp đặc biệt - Khảo sát và chứng minh được khẳng định 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. Từ khẳng định trên xác định tính chất của mã xyclic cục bộ xây dựng từ nhóm nhân xyclic trên phân hoạch vành Mersenne, dựa vào đó đề xuất thuật toán xây dựng các mã đối ngẫu của mã xyclic cục bộ xây dựng trên vành Mersenne và trên một vành đa thức tổng quát. Các vấn đề mà luận án đã giải quyết được công bộ trên các tạp chí chuyên ngành và hội nghị khoa học. Hướng nghiên cứu tiếp theo Tiếp cận với các cách xây dựng mã xyclic cục bộ khác để có thể đề xuất được các phương án xây dựng mã đối ngẫu của mã xyclic cục bộ cho từng phương án xây dựng mã xyclic. Mở rộng phạm vi nghiên cứu về mã xyclic cục bộ trên các trường hữu hạn bất kì. CÁC CÔNG TRÌNH CỦA TÁC GIẢ ĐÃ CÔNG BỐ [1]. Nguyễn Bình, Nguyễn Trung Hiếu, Nguyễn Văn Trung (2013) “Về cấp của các đa thức trong vành”. Tạp chí khoa học và công nghệ, Học viện Bưu chính Viễn thông; Tập 51 số 1A/2013 [2]. Nguyễn Văn Trung, Nguyễn Trung Hiếu, Phạm Việt Trung (2013), “Sự tương đương giữa mã Xyclic cục bộ xây dựng trên nhóm nhân Xyclic và mã Xyclic truyền thống”. Kỷ yếu hội nghị Quốc gia về điện tử truyền thông, Hội Vô tuyến điện tử Việt nam. Ngày 17-18/12/2013 [3]. Nguyễn Văn Trung, Nguyễn Trung Hiếu (2014), “Tích các nhóm nhân Xyclic trên phân hoạch vành đa thức”. Tạp chí Nghiên cứu Khoa học và công nghệ quân sự. Số tháng 4/2014 ISSN 1859-1043. [4]. Nguyen Binh, Nguyen Trung Hieu, Nguyen Van Trung (2014), “A Classification of Linear Codes Based on Algebraic Structures and Local Xyclic Codes”, International on ATC’14 15- 17/10/2014. er=7043410 [5]. Nguyễn Văn Trung (2015) “Các mã xyclic trên vành Mersenne”, Tạp chí Nghiên cứu Khoa học và công nghệ quân sự. Số tháng 2/2015. ISSN1859- 1043. [6]. Nguyễn Văn Trung, Nguyễn Trung Hiếu (2015), “Các mã xyclic xây dựng từ một lớp kề xyclic”, Tạp chí Nghiên cứu Khoa học và công nghệ quân sự. Đặc san KHCNQS. Số tháng 10.2015. ISSN 1859-1043.