Các mã Cyclic trấn vành Mersenne

Kỹ thuật điện tử & Khoa học máy tính 44 N. V. Trung, “Các mã cyclic trên vành Mersenne.” C¸c m· CYCLIC TRÊN Vµnh MERSENNE NGUYỄN VĂN TRUNG Tóm tắt: Bài báo này trình bày một số tính chất của các nhóm nhân cyclic trên vành Mersenne. Các nhóm nhân cyclic này là cơ sở cho việc xây dựng các mã cyclic cục bộ. Có thể thấy rằng tất cả các nhóm nhân cyclic trên vành Mersenne đều tương đương với tất cả các mã cyclic trên vành này và các vành ước của nó. Từ khóa: Cyclic, Nhóm nhân Cyclic, Cyclic cục bộ. 1. ĐẶT VẤN ĐỀ Lý thuyết mã hóa đã được phát triển từ lâu và được ứng dụng rộng rãi trong nhiều lĩnh vực của cuộc sống, đặc biệt là lĩnh vực thông tin. Lý thuyết mã hóa phát triển theo ba hướng cơ bản là mã nguồn, mã kênh và mật mã [1,2]. Đa số các mã khống chế sai thường xây dựng theo hướng kiến thiết cho định lý thứ hai của Shannon với hướng chủ đạo là xây dựng các mã trên các cấu trúc đại số theo quan điểm mã là một tập con có cấu trúc trong một cấu trúc đại số nào đó [3]. Thành tựu nổi bật trong hướng này là mã cyclic. Mã cyclic là mã khối tuyến tính được xây dựng trên các Ideal của vành đa thức, mỗi từ mã là một phần tử của Ideal trên vành đa thức đó. Với mã cyclic cục bộ, mỗi dấu mã là một phần tử của một bộ phận có cấu trúc trong vành. Có thể coi mã cyclic truyền thống là một lớp con của mã cyclic cục bộ hay mã cyclic truyền thống là một dạng đặc biệt của mã cyclic cục bộ[9]. Bài báo này trình bày về một số tính chất của mã cyclic cục bộ xây dựng trên vành Mersenne, dựa trên những kiến thức nền tảng về cấu trúc đại số và các kết quả nghiên cứu trước đó về mã cyclic cục bộ. 2. CẤP CỦA NHÓM NHÂN CYCLIC TRÊN VÀNH MERSENNE Định nghĩa 1: Vành đa thức Mersenne 1nx  là vành đa thức có giá trị n thỏa mãn: 2 1mn   . Định nghĩa 2: Cho  0,1,.. 1n nS n  , n lẻ Lớp kề cyclic iC theo modulo trên  2GF là tập hợp sau:     .2 mod , 0,1,.. .2 , .4 ,.. .2 1i j i mj j i C i n j C i i i     Trong đó: .2 modimi i n Ta có i nC S , i jC C  . Như vậy tập các lớp kề iC tạo nên một phân hoạch của n : ;i i i i C m m n  Nhận xét: Ta có phân tích:  1n i i x f x    if x : đa thức bất khả quy  Số các đa thức bất khả quy  if x bằng số các iC trong phân hoạch nS   deg i i if x C m  . Ví dụ 1: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 45 5n  :  0 0C   1 1,2,4,3C    5 2 3 41 1 1x x x x x x       7n  :  0 0C   1 1,2,4C   3 3,6,5C      7 3 2 31 1 1 1x x x x x x       15n  :  0 0C   1 1,2,4,8C   3 3,6,12,9C   5 5,10C   7 7,14,13,11C        15 2 3 4 4 2 3 41 1 1 1 1 1x x x x x x x x x x x x             Định lý 1 [4]: Trong vành Mersenne 2 1mn   đa thức 1nx  được phân tích thành tích của tất cả các đa thức bất khả quy có bậc m và ước của m Định nghĩa 3: Nhóm nhân cyclic A với phần tử sinh  a x trên vành đa thức  2[ ] / 1nx x  được thiết lập theo công thức:   mod ( 1), 1,i nA a x x i k   Trong đó k là cấp của  a x . Một số tính chất của nhóm nhân cyclic: - Tất cả các phần tử của nhóm nhân cyclic là bằng nhau với các trọng số chẵn và trọng số lẻ - Số lượng các phần tử của nhóm nhân A bằng với cấp của  a x , có nghĩa là: A k - Theo lý thuyết Lagrange thì k là ước số của 2 1m  : | 2 1mk  - Tích của hai nhóm nhân cyclic là một nhóm nhân cyclic [8]. - Hiển nhiên, n là ước số của 2 1m  : | 2 1mn  Với  max deg im f x    ,  if x là các đa thức bất khả quy trong phân tích của 1 nx  Định nghĩa 4: Cấp của đa thức  ord a x là số nguyên dương nhỏ nhất k được xác định theo công thức:      mod 1k na x e x x  Trong đó  e x là một lũy đẳng nào đó.  a x tạo nên một nhóm nhân cyclic với cấp là k trong nhóm nhân của vành. Kỹ thuật điện tử & Khoa học máy tính 46 N. V. Trung, “Các mã cyclic trên vành Mersenne.” Định lý 2:[5] Cấp cực đại của đa thức  a x trên vành đa thức được xác định theo công thức (với n lẻ):  max ord 2 1ma x   Nếu  a x là một phần tử của nhóm nhân, cấp cực đại của  a x được xác định theo: - Nếu n là một số lẻ ( 2 1n k  ) và  1n ix f x  với  if x là các đa thức bất khả quy. Khi đó  max ord 2 1ma x   với  max deg im f x . - Nếu n là một số chẵn (  2 2 1sn k  ) và  2 1 1k ix f x    với  if x là các đa thức bất khả quy, khi đó,    max ord 2 2 1s ma x   Chú ý: - Trong trường hợp n là số Mersenne: 2 1mn   , ta có:  max orda x n - Một vành  2 / 1 nx x  chứa các nhóm nhân với các lũy đẳng khác nhau. Số lượng các nhóm nhân bằng với số lượng Ideal trong vành. Mỗi nhóm nhân bao gồm các nhóm cyclic con với cấp cực đại được xác định theo định lý 2 và ước số của giá trị này. - Vành  2 / 1 nx x  với n là một số lẻ được gọi là một vành cơ sở. Số lượng các Ideal trên vành được xác định theo công thức: 2 1tM   với t là số lượng các đa thức bất khả quy trong phân tích của đa thức nhị phân 1nx  . Ví dụ 2: Xét các nhóm nhân trên vành   152 / 1x x  . Do 415 2 1n    là số Mersenne, vành trên là vành cơ sở và là vành Mersenne. Phân tích của đa thức 15 1:x        15 2 3 4 4 2 3 41 1 1 1 1 1x x x x x x x x x x x x             Với đa thức này, ta có 5t  ( t là số lượng các đa thức bất khả quy). Số lượng các Ideal trên vành: 52 1 31M    . Cấp cực đại của một phần tử trong vành:   4max ord 2 1 2 1 15ma x      với  max deg 4im f x  . Như vậy, theo định lý 1, định lý 2 và định nghĩa 3 ta có: Bổ đề 1:Trong vành Mersenne với 2 1mn   các nhóm nhân cyclic với phần tử sinh  a x bất kì sẽ có cấp là n hoặc ước của n . 3. CÁC MÃ CYCLIC TRÊN VÀNH MERSENNE Định lý 3 [7]: Với mỗi mã cyclic cục bộ tạo thành từ một nhóm nhân Cyclic được xây dựng trên một vành đa thức bất kì, ta luôn tìm được mã cyclic truyền thống có cùng đa thức sinh  g x , mã cyclic truyền thống trên được xây dựng theo modulo  h x trên vành đa thức có bậc là cấp của nhóm nhân trên vành đa thức của mã cyclic cục bộ đã tạo ở trên. Ví dụ 3: 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       Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 47 Xét nhóm nhân    2 41 ~ 0 1 2 4a x x x x    trên vành 9 1x  . Nhóm nhân cyclic A xây dựng theo phần tử sinh  a x :                                       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 cyclic A là nhóm nhân có cấp 21. Như vậy, theo định lý 3, mã cyclic truyền thống tương đương với nhóm nhân trên được xây dựng trên vành 212 / 1x  Bằng cách xây dựng theo thuật toán được trình bày trong [7], ta thu được mã cyclic truyền thống xây dựng trên vành 21 1x  , với đa thức sinh:   4 5 8 10 12 13 14 15 161g x x x x x x x x x x          Đây là ma trận sinh của mã cylic  21,5 Từ các định lý và bổ đề đã trình bày ở trên, có thể rút ra kết luận trên về các mã cyclic trên vành Mersenne sau: Bổ đề 2: Trên vành Mersenne ( 2 1mn   ), tất cả các nhóm nhân cyclic tương đương với mọi mã cyclic được xây dựng trên vành này và các vành ước của nó. Ví dụ 4: Trong vành Mersenne   152 / 1x x  xét đa thức:    3 4 6 8 9 10 111 0 3 4 6 8 9 10 11a x x x x x x x x         . Nhóm nhân cyclic xây dựng theo  a x :           0 3 4 6 8 9 10 11 , 0 1 3 5 6 7 8 12 , 0 2 3 4 5 9 12 13 , 0 1 2 6 9 10 12 14 , 3 6 7 9 11 12 13 14 A          Tương tự, bằng cách xây dựng thuật toán được trình bày trong [7], ta thu được mã cyclic trên vành   52 / 1x x  với đa thức sinh:    1g x x  . Bảng 1. Kết quả khảo sát trên vành Mersenne   152 / 1x x  :  a x Vành tương đương  h x  g x  1 4 ,  0 1 4 ,  2 5 8 ,  1 2 4 5 8 ,  0 1 2 4 5 8 ,  0 1 4 ,  1 4 6 9 ,  2 5 6 8 9 ,  1 2 4 5 6 8 9 ,  1 4 5 10 ,  1 4 5 6 9 10 ,  0 2 5 6 8 9 10 ,  0 1 4 7 10 13   32 / 1x x   1  0 5 ,  1 4 5 ,  0 2 5 8 ,  0 5  0 1 4 5 6 9 ,  0 1 2  0 1 Kỹ thuật điện tử & Khoa học máy tính 48 N. V. Trung, “Các mã cyclic trên vành Mersenne.”  0 1 2 4 6 8 9 10  0 1 3 4 6 7 9 10 12 13  0 2 3 6 7 9 ,  1 6 11 ,  0 2 3 6 7 9 12   52 / 1x x   1  1 2 3 6 7 8 ,  0 3 4 6 7 8 9 10 11  0 1 2 3 4  0 1 Kết quả khảo sát trên các vành Mersenne khác cũng cho kết quả tương tự. KẾT LUẬN Việc xác định và xây dựng lý thuyết về mã cyclic cục bộ trên các phân hoạch vành đa thức theo các nhóm nhân cyclic là một trong những mục tiêu quan trọng trong việc xây dựng và hoàn chỉnh về mặt lý thuyết của mã cyclic cục bộ. Việc xác định tính chất của các nhóm nhân cyclic trên vành Mersenne là một kết quả nằm trong nội dung hoàn thiện về mặt lý thuyết của mã cyclic cục bộ, là tiền đề để tiếp tục nghiên cứu, hoàn thiện, bổ sung về mặt lý thuyết cho vấn đề này. TÀI LIỆU THAM KHẢO [1]. Tood K. Moon,“Error Correction Coding:Mathematical Methods and Algorithm”, John Wiley & Son, Inc, 2005.Mac William F.J, Sloane N.J.A,“The theory of Error – Correcting Codes”, North – Holland PC, 1986. [2]. Lild. R. Niederreiter H., “Introduction to finite field and their appliction”, Cambridge University Press 2000. [3]. Berkelamp, E.R,“Algebraic coding theory”, NewYork, McGraw – Hill 1968. [4]. Nguyen Binh, Le Dinh Thich, “The order of polynomial and Algorithm for Defining Order of Polynomial over Polynomial Ring”, 5th Vietnam Conferrence on Automation (5th VICA), Hanoi, Vietnam 2002. [5]. Nguyễn Bình, Nguyễn Trung Hiếu, Nguyễn Văn Trung,“Về cấp của các đa thức trên vành” ,Tạp chí Khoa học và công nghệ, trang 101 – 107 , tập 51 – số 1A, 2013, Việt Nam ISSN 0866708X. [6]. Nguyễn Văn Trung, Nguyễn Trung Hiếu, Phạm Việt Trung,“Sự tương đương giữa mã cyclic cục bộ xây dựng trên các nhóm nhân cyclic và mã cyclic truyền thống”, Kỷ yếu Hội nghị Quốc gia về Điện tử truyền thông 17, 18/12/2013, trang 225, Việt Nam, ISBN 9786049346644. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 49 [7]. Nguyễn Văn Trung, Nguyễn Trung Hiếu,“Tích của các nhóm nhân cyclic trên phân hoạch vành đa thức”, Tạp chí nghiên cứu khoa học và quân sự tháng 4/2014, trang 48 – 53, ISSN 18591043. [8]. Nguyen Trung Hieu, Nguyen Van Trung, Nguyen Binh,“A clasification of linear codes bases on algebraic strutures on local cylic codes”, The 2014 International conference on Advanced Technologies for Communication, October 15-17 2014. ABSTRACT CYCLIC CODES ON MERSENNE RING In this paper, the properties of Cyclic Multiplicative Group in Mersenne ring are presented. The Cyclic Multiplicative Group are kenels in decomposition of the ring.Infact, all of Cyclic Multiplicative Group in Mersenne ring is equivalent with all of cylic codes in this ring and its divisor ring. Keywords: Cyclic, Cyclic Multiplicate Group, Local Cyclic Codes. Nhận bài ngày 18 tháng 9 năm 2014 Hoàn thiện ngày 15 tháng 01 năm 2015 Chấp nhận đăng ngày 10 tháng 02 năm 2015 Địa chỉ: Viện Công nghệ thông tin, Viện khoa học Công nghệ Quân sự, trungnv76@gmail.com