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

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