Luận án tiến sĩ Kỹ thuật: Nhóm nhân cyclic và mã cyclic trên vành đa thức

Chia sẻ: Trần Văn Yan | Ngày: | Loại File: PDF | Số trang:165

Thêm vào BST

Báo xấu

20
lượt xem 3
download

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

Mục đích chính của luận án là góp phần hoàn thiện lý thuyết và thực nghiệm về nhóm nhân cyclic và mã cyclic trên các vành đa thức, trong đó các kết quả nghiên cứu đạt được của luận án nhằm giải quyết các vấn đề cụ thể sau: Quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức với mã cyclic truyền thống. Phương pháp kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. Đề xuất ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic để tìm một số bộ mã cyclic tốt, hay ứng dụng trong các hệ mật.

Chủ đề:

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

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuật: Nhóm nhân cyclic và mã cyclic trên vành đa thức

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN TRUNG HIẾU NHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊN VÀNH ĐA THỨC LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI – 2017
BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN TRUNG HIẾU NHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊN VÀNH ĐA THỨC CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ MÃ SỐ: 9520203 LUẬN ÁN TIẾN SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN LUẬN ÁN: 1. GS.TS. NGUYỄN BÌNH 2. TS. NGUYỄN NGỌC MINH HÀ NỘI – 2017
i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi, các số liệu và kết quả trình bày trong luận án là trung thực và chưa được công bố ở bất kỳ công trình nào khác. Tác giả Nguyễn Trung Hiếu
ii LỜI CẢM ƠN Luận án Tiến sĩ kỹ thuật này được thực hiện tại Học viện Công nghệ Bưu chính Viễn thông dưới sự hướng dẫn của GS.TS. Nguyễn Bình và TS. Nguyễn Ngọc Minh. Nghiên cứu sinh bày tỏ lòng biết ơn sâu sắc tới GS.TS. Nguyễn Bình, thầy trực tiếp hướng dẫn, giúp đỡ, cung cấp những kiến thức quý báu và có rất nhiều ý kiến gợi mở về hướng nghiên cứu để nghiên cứu sinh thực hiện thành công đề tài. Nghiên cứu sinh cũng xin chân thành cảm ơn TS. Nguyễn Ngọc Minh, người lãnh đạo trực tiếp đã luôn ủng hộ, giúp đỡ nghiên cứu sinh trong quá trình nghiên cứu. Nghiên cứu sinh xin dành lời cảm ơn sâu sắc tới các Thầy giáo, nhà khoa học trong Hội đồng bảo vệ Luận án các cấp, các buổi hội thảo luận án đã nhiệt tình chỉ bảo, giúp đỡ và có nhiều góp ý quý báu giúp nghiên cứu sinh hoàn thiện luận án. Tôi cũng xin cảm ơn Ban giám đốc Học viện Công nghệ Bưu chính Viễn thông, Khoa Quốc tế và Đào tạo Sau đại học, Khoa Kỹ thuật Điện tử 1 (nơi tôi đang công tác), cũng như các đồng nghiệp đã tạo điều kiện và giúp đỡ tôi hoàn thành được đề tài nghiên cứu của mình. Cuối cùng là sự biết ơn tới gia đình, bạn bè đã thông cảm, động viên giúp đỡ cho tôi có đủ nghị lực để hoàn thành luận án. Hà Nội, tháng 12 năm 2017
iii MỤC LỤC LỜI CAM ĐOAN ................................................................................................................ I LỜI CẢM ƠN .................................................................................................................... II DANH MỤC CÁC TỪ VIẾT TẮT ................................................................................... V DANH MỤC CÁC KÝ HIỆU .........................................................................................VII DANH MỤC CÁC BẢNG ............................................................................................... IX DANH MỤC CÁC HÌNH VẼ ........................................................................................... X MỞ ĐẦU ............................................................................................................................ 1 1. LÝ DO NGHIÊN CỨU ................................................................................... 1 2. MỤC ĐÍCH NGHIÊN CỨU ............................................................................ 1 3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU................................................. 2 4. PHƯƠNG PHÁP VÀ CÔNG CỤ NGHIÊN CỨU .......................................... 2 5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI .............................. 2 6. CẤU TRÚC CỦA LUẬN ÁN ......................................................................... 3 CHƯƠNG 1: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU .............................................. 5 1.1. GIỚI THIỆU CHUNG .................................................................................. 5 1.2. VÀNH ĐA THỨC ........................................................................................ 7 1.2.1. Một số khái niệm cơ bản ..................................................................... 7 1.2.2. Chu trình và lũy đẳng ........................................................................ 10 1.3. MÃ TUYẾN TÍNH ..................................................................................... 13 1.3.1. Mã cyclic truyền thống ...................................................................... 13 1.3.2. Một số mã tuyến tính khác ................................................................ 16 1.3.3. Một số tiêu chuẩn đánh giá mã tuyến tính ........................................ 18 1.4. PHÂN HOẠCH VÀNH ĐA THỨC VÀ MÃ CYCLIC CỤC BỘ ............. 19 1.4.1. Nhóm nhân cyclic .............................................................................. 19 1.4.2. Cấp số nhân cyclic ............................................................................. 24 1.4.3. Phân hoạch vành đa thức ................................................................... 24 1.4.4. Mã cyclic cục bộ trên vành đa thức ................................................... 31 1.5. HƯỚNG NGHIÊN CỨU CỦA LUẬN ÁN VÀ MỘT SỐ KẾT QUẢ LIÊN QUAN.......................................................................................................... 34 1.6. KẾT LUẬN CHƯƠNG .............................................................................. 37 CHƯƠNG 2: CẤP CỦA ĐA THỨC VÀ QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC VỚI MÃ CYCLIC TRUYỀN THỐNG ................................. 39 2.1. GIỚI THIỆU ............................................................................................... 39
iv 2.2. XÁC ĐỊNH CẤP CỦA ĐA THỨC ............................................................ 40 2.2.1. Đề xuất phương pháp xác định cấp của tích các đa thức .................. 40 2.2.2. Đề xuất phương pháp xác định cấp của nhị thức .............................. 45 2.2.3. Đề xuất thuật toán cải tiến để tìm và liệt kê cấp của đa thức trên vành ................................................................................................... 51 2.2.4. Xác suất chọn đa thức có cấp cực đại ............................................... 56 2.3. QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC VỚI MÃ CYCLIC TRUYỀN THỐNG ...................................................... 58 2.3.1. Cơ sở toán học ................................................................................... 58 2.3.2. Sự tương đương của nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống ............................................................................ 60 2.3.3. Thuật toán xác định nhóm nhân cyclic tương đương mã cyclic truyền thống .................................................................................................. 63 2.4. MỘT CÁCH PHÂN LOẠI MÃ TUYẾN TÍNH MỚI ................................ 69 2.5. KẾT LUẬN CHƯƠNG .............................................................................. 73 CHƯƠNG 3: ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC ......... 75 3.1. PHƯƠNG PHÁP XÂY DỰNG MÃ CYCLIC ........................................... 75 3.1.1. Phương pháp xây dựng mạch mã hóa ............................................... 75 3.1.2. Phương pháp xây dựng mạch giải mã ............................................... 77 3.2. ĐỀ XUẤT MỘT SỐ MÃ CYCLIC TỐT TRÊN VÀNH ĐA THỨC ........ 79 3.2.1. Phương pháp tìm mã cyclic tốt .......................................................... 79 3.2.2. Mô phỏng, đánh giá một số bộ mã cyclic tốt .................................... 90 3.2.3. Đề xuất thực hiện các bộ mã trên FPGA ........................................... 95 3.3. ĐỀ XUẤT PHƯƠNG PHÁP TẠO KHÓA CHO MỘT SỐ HỆ MẬT ...... 97 3.3.1. Quan hệ giữa vành đa thức có hai lớp kề cyclic và trường số .......... 97 3.3.2. Hệ mật Omura-Massey trên vành đa thức có hai lớp kề cyclic ...... 100 3.4. KẾT LUẬN CHƯƠNG ............................................................................ 105 KẾT LUẬN ..................................................................................................................... 107 CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ................................................... 108 TÀI LIỆU THAM KHẢO .............................................................................................. 110 PHỤ LỤC........................................................................................................................ 119
v DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Nghĩa tiếng Anh Nghĩa tiếng Việt BCH Bose, Chaudhuri, and (Tên ba tác giả nghiên cứu ra Hocquenghem mã BCH) CGP Cyclic Geometic Progressions Cấp số nhân cyclic CMG Cyclic Multiplicate Group Nhóm nhân cyclic CRC Cyclic Redundancy Check Kiểm tra dư thừa vòng ECC Error Correcting Code Mã sửa lỗi FPGA Field Programable Gate Array Mảng cổng logic khả trình MTD Majority-based Threshold Giải mã ngưỡng theo đa số Decode LCC Local Cyclic Code Mã cyclic cục bộ OALCC Orthogonalable Local Cyclic Mã cyclic cục bộ có khả năng Code trực giao OLCC Orthogonal Local Cyclic Code Mã cyclic cục bộ tự trực giao LDPC Low-Density Parity Check Mã kiểm tra chẵn lẻ mật độ thấp LTE Long Term Evolution Tiến hóa dài hạn RSMA Repeated Square and Multiply Thuật toán nhân và bình Algorithm phương lặp STBC Space-Time Block Code Mã khối không gian-thời gian TCM Trellis Coded Modulation Điều chế mã lưới CS Check-sum Tổng kiểm tra
vi OACS Orthogonalable check-sum Tổng kiểm tra có khả năng trực giao OCS Orthogonal check-sum Tổng kiểm tra trực giao VHDL VHSIC Hardware Discription Ngôn ngữ mô tả phần cứng Language WCDMA Wideband Code Division Đa truy nhập phân chia theo mã Multiple Access băng rộng
vii DANH MỤC CÁC KÝ HIỆU Ký hiệu Nghĩa tiếng Anh Nghĩa tiếng Việt C Set of cycles Tập hợp các chu trình CS Cycle Chu trình d0 Hamming distance Khoảng cách Hamming deg Degree Bậc của đa thức e( x ) Idempotent Đa thức lũy đẳng e0 ( x) Swallowing Idempotent Lũy đẳng nuốt Field Trường G Group Nhóm GF ( p) Galois Field Trường Galois gcd Greatest common divisor Ước chung lớn nhất I Ideal Ideal lcm Least common multiple Bội chung nhỏ nhất Mod Modulo Phép chia lấy phần dư ord Order Cấp của đa thức R Ring Vành W Weight Trọng số 2 [ x] / ( x n  1) Polynomial for Integer mod 2 Vành đa thức trên 2 Intersection Giao Union Hợp  Empty set Tập hợp rỗng
viii # hoặc ... Cardinality Lực lượng hay số phần tử ~ Similarity Tương đương  Summation Tổng Non-redundant division Phép chia hết | Divisor or divides Ước Not divisor or not divides Không là ước ... Ceiling Số nguyên nhỏ nhất lớn hơn hoặc bằng giá trị trong ngoặc
ix DANH MỤC CÁC BẢNG Bảng 1.1. Bảng giá trị của n nhỏ hơn 1000 thỏa mãn 2 [ x] / ( x n  1) là một vành đa thức có 2 lớp kề cyclic ................................................................. 10 Bảng 1.2. Số kiểu phân hoạch không suy biến M của một số vành ................ 27 Bảng 1.3. Tổng số các kiểu phân hoạch của vành 2 [ x] / ( x n  1) ...................... 28 Bảng 2.1. Bảng khảo sát cấp của đa thức 1  x trên một số vành đa thức................ 48 Bảng 2.2. So sánh thời gian tính toán của hai thuật toán ................................... 54 Bảng 2.3. Kết quả khảo sát 35 giá trị n ............................................................. 57 Bảng 3.1. Một số cặp vành có thể phân hoạch hỗn hợp .................................... 84 Bảng 3.2. Đề xuất một số bộ mã cyclic tốt ........................................................ 89 Bảng 3.3. Phép toán cộng và nhân trên hai cấu trúc vành đa thức và vành số…98 Bảng 3.4. Các phần tử nghịch đảo tương quan trên trường số và vành đa thức..99
x DANH MỤC CÁC HÌNH VẼ Hình 2.1. Biểu đồ so sánh thời gian tính toán của hai thuật toán ...................... 55 Hình 2.2. So sánh các mã cyclic và mã cyclic cục bộ........................................70 Hình 2.3. Sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã LCC..72 Hình 3.1. Phân hoạch vành đa thức có nhóm nhân sinh là nhóm nhân đơn vị .. 76 Hình 3.2. Phân hoạch vành có nhóm nhân sinh là nhóm nhân cyclic bất kỳ .... 77 Hình 3.3. Lưu đồ thuật toán tìm bộ mã cyclic tốt xây dựng từ cấp số nhân cyclic............................................................................................................ 88 Hình 3.4. Sơ đồ hệ thống thông tin sử dụng mô phỏng, đánh giá mã cyclic ..... 90 Hình 3.5. Kết quả mô phỏng bộ mã cyclic (255,9,127) ..................................... 92 Hình 3.6. Kết quả mô phỏng bộ mã cyclic (15,5,7) ........................................... 93 Hình 3.7. Kết quả mô phỏng bộ mã cyclic (27,9,9) ........................................... 94 Hình 3.8. Giao thức truyền thông sử dụng hệ mật O-M .................................. 101
1 MỞ ĐẦU 1. LÝ DO NGHIÊN CỨU Lý thuyết mã hóa đã được nghiên cứu từ những năm 1940 và được ứng dụng rộng rãi trong nhiều lĩnh vực, đặc biệt là trong lĩnh vực truyền thông góp phần nâng cao hiệu quả của hệ thống truyền tin. Một trong các lớp mã quan trọng của mã khối tuyến tính đó là các mã cyclic. Mã cyclic có nhiều ứng dụng trong điện tử dân dụng, các hệ thống lưu trữ dữ liệu, các hệ thống truyền thông vì có nhiều phương pháp mã hóa và giải mã hiệu quả. Việc nghiên cứu truyền thống về mã cyclic đã khá hoàn chỉnh, tuy nhiên loại mã này có nhược điểm là số lượng từ mã được tạo ra hạn chế, độ dài của mã chỉ cố định ở một số giá trị cụ thể. Trong những năm trở lại đây một phương pháp khác để xây dựng mã cyclic được nghiên cứu đó là sử dụng nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức, và mã được gọi là mã cyclic cục bộ (LCC- Local Cyclic Code). Các nghiên cứu gần đây đã đưa ra một số phương pháp phân hoạch vành đa thức, xây dựng mã cyclic cục bộ, cùng các phương pháp giải mã tương đối hiệu quả. Nghiên cứu sinh nhận thấy rằng có thể tồn tại mối quan hệ giữa mã cyclic và cyclic cục bộ, điều đó thôi thúc nghiên cứu sinh nghiên cứu sâu hơn lý thuyết về mã cyclic cục bộ (mã cyclic được xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic), tìm hiểu, chứng minh mối quan hệ có thể tồn tại giữa mã cyclic và mã cyclic cục bộ. Chính vì lẽ đó, nghiên cứu sinh đã chọn đề tài “Nhóm nhân cyclic và mã cyclic trên vành đa thức” để định hướng nghiên cứu luận án tiến sĩ của mình. Trên cơ sở kết quả nghiên cứu lý thuyết đạt được sẽ đề xuất một số ứng dụng có thể về mã sửa lỗi và mật mã trong các hệ thống truyền thông. 2. MỤC ĐÍCH NGHIÊN CỨU Mục đích chính của luận án là góp phần hoàn thiện lý thuyết và thực nghiệm về nhóm nhân cyclic và mã cyclic trên các vành đa thức, trong đó các kết quả nghiên cứu đạt được của luận án nhằm giải quyết các vấn đề cụ thể sau:
2 - Quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức với mã cyclic truyền thống. - Phương pháp kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. - Đề xuất ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic để tìm một số bộ mã cyclic tốt, hay ứng dụng trong các hệ mật. 3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU Đối tượng nghiên cứu của luận án là các đa thức, nhóm nhân cyclic, cấp số nhân cyclic và mã cyclic trên vành đa thức. Phạm vi nghiên cứu của luận án này được giới hạn trong việc nghiên cứu mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, cấp của đa thức và phương pháp xây dựng nhóm nhân cyclic có cấp cực đại trên vành đa thức, trên cơ sở đó có thể đề xuất một số mã cyclic tốt và phương pháp hiện thực hóa các mã cyclic trên FPGA (Field Programable Gate Array). 4. PHƯƠNG PHÁP VÀ CÔNG CỤ NGHIÊN CỨU Phương pháp nghiên cứu của đề tài là phân tích và tổng hợp dựa vào các công cụ toán học, đặc biệt là đại số, lý thuyết mã hóa, lý thuyết xác suất... Luận án sử dụng các công cụ toán học, kết hợp với việc tính toán, mô phỏng trên máy tính và các chương trình phần mềm xử lý (C++, Matlab, VHDL (VHSIC Hardware Discription Language), Excel). 5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI Những kết quả trong luận án này góp phần phát triển hoàn thiện lý thuyết mã cyclic, mã cyclic cục bộ nói riêng và lý thuyết mã sửa lỗi nói chung. Các đóng góp chính của Luận án: - Kiến thiết các nhóm nhân cyclic có cấp cực đại trên vành đa thức thông qua việc đề xuất phương pháp xác định đa thức có cấp cực đại. - Chứng minh sự tương đương giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống.
3 - Đề xuất một số bộ mã cyclic tốt xây dựng trên vành đa thức, đề xuất khả năng thực hiện các bộ mã cyclic cục bộ trên cấu kiện phần cứng. 6. CẤU TRÚC CỦA LUẬN ÁN Nội dung luận án bao gồm các phần: Mở đầu, ba chương và kết luận. Trong đó, chương 1 trình bày tổng quan và lý thuyết cơ bản về vấn đề nghiên cứu, các kết quả nghiên cứu chính của Luận án được trình bày trong hai chương còn lại, cụ thể như sau: Chương 1 trình bày tổng quan vấn đề nghiên cứu, lý thuyết cơ bản về vành đa thức, mã cyclic làm cơ sở cho các nội dung nghiên cứu của luận án. Các nội dung về vành đa thức bao gồm các khái niệm vành đa thức, các tính chất đa thức, chu trình, luỹ đẳng, vành đa thức có hai lớp kề cyclic, trong đó Luận án đề cập việc chứng minh bổ đề về một tính chất luỹ đẳng nuốt, chính xác hoá các vành đa thức có hai lớp kề cyclic Z 2 [x] /  x n  1 với n  1000 . Tiếp theo, luận án trình bày lý thuyết về nhóm nhân cyclic và cấp số nhân cyclic cùng các bổ đề liên quan. Lý thuyết về mã cyclic truyền thống và các mã tuyến tính khác cũng được đề cập trong chương, kèm theo đó là trình bày về một số tiêu chuẩn đánh giá mã tuyến tính tốt. Tiếp đến, Luận án trình bày về phân hoạch vành đa thức và các mã cyclic cục bộ với các nội dung liên quan đến nhóm nhân cyclic, cấp số nhân cyclic, phân hoạch vành đa thức và mã cyclic cục bộ. Nội dung cuối cùng, luận án nhận xét về công trình nghiên cứu của các tác giả khác và hướng nghiên cứu của luận án. Trong Chương 2, luận án tập trung trình bày các kết quả nghiên cứu mới và hai đóng góp quan trọng của Luận án: Nội dung thứ nhất là đề xuất phương pháp kiến thiết các nhóm nhân cyclic có cấp cực đại thông qua việc xác định cấp của đa thức với nhiều hướng tiếp cận cùng các đề xuất quan trọng như: phương pháp xác định cấp của đa thức là tích các đa thức, phương pháp xác định cấp của nhị thức, thuật toán tìm và liệt kê cấp của đa thức trên vành, đánh giá xác xuất tìm phần tử có cấp cực đại trên vành đa thức có hai lớp kề cyclic đã góp phần giải quyết khá hoàn chỉnh bài toán đặt ra. Nội dung thứ hai là nghiên cứu, đánh giá mối quan hệ giữa
4 các nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, đã góp phần chỉ ra có một mối quan hệ tương đương giữa mã cyclic truyền thống với mã cyclic xây dựng trên nhóm nhân, cấp số nhân trên vành đa thức. Từ hai kết quả nghiên cứu trên, luận án đề xuất sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã cyclic cục bộ. Đóng góp của chương này được công bố trong các công trình khoa học [J2], [J3], [J4], [J5], [C3], [C4], [C5]. Ở Chương 3, Luận án trình bày phương pháp xây dựng mã cyclic với các nội dung liên quan đến việc xây dựng khối mã hoá và giải mã, tiếp đến luận án đề xuất một số mã cyclic tốt xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic gồm phương pháp tìm mã cyclic tốt, danh sách một số mã cyclic tốt được đề xuất, mô phỏng đánh giá bộ mã; đề xuất phương pháp xây dựng bộ mã trên cấu kiện phần cứng FPGA, đưa ra một phương pháp cải tiến việc xây dựng bộ mã hoá và giải mã cho phù hợp với đặc điểm phần cứng logic khả trình và góp phần minh chứng cho khả năng hiện thực hoá các bộ mã cyclic, cyclic cục bộ trên cấu kiện logic khả trình. Nội dung cuối, luận án trình bày ứng dụng của nhóm nhân cyclic và cấp số nhân cyclic trong việc làm khóa một số hệ mật. Đóng góp của chương này được công bố trong các công trình khoa học [J1], [J6], [C1], [C2]. Phần kết luận sẽ đưa ra những kết luận của Luận án đối với những đóng góp kể trên và đưa ra những vấn đề mở trong tương lai.
5 CHƯƠNG 1: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU Nội dung của chương trình bày lý thuyết tổng quan về vành đa thức, nhóm nhân cyclic, cấp số nhân cyclic và mã cyclic. Các tiêu chuẩn đánh giá mã sửa lỗi cũng được giới thiệu trong chương này. Chương này cũng sẽ tập trung khảo sát các nghiên cứu liên quan đến mã cyclic để từ đó tìm ra các hạn chế của các nghiên cứu trước đây và đề xuất hướng nghiên cứu, phạm vi nghiên cứu và phương thức tiếp cận của luận án. 1.1. GIỚI THIỆU CHUNG Lý thuyết mã hoá được bắt đầu nghiên cứu từ những năm 1940 và được phát triển theo ba hướng lớn đó là: mã nguồn [7], [17], mã kênh (có khả năng sửa lỗi [35], [74]) và mật mã [8], [63]. Đặt nền móng cho lý thuyết mã hoá là các nghiên cứu của Shannon trong hai năm 1948-1949 về độ tin cậy của truyền tin trên các kênh truyền có nhiễu [59]. Khởi đầu cho việc thiết kế các bộ mã tốt và các phương pháp giải mã hiệu quả đó là mã Hamming, mã Golay [59] và các mã khác vào cuối những năm 1940. Các nghiên cứu về mã hóa những năm 1950, 1960 tập trung vào việc phát triển lý thuyết về các mạch mã hóa và giải mã hiệu quả. Trên thực tế, các sơ đồ mã hoá và giải mã hiện nay đều không thoả mãn giới hạn của Shannon, nhưng bộ giải mã có độ phức tạp (giá thành) thấp hơn. Vì lý do này, các hướng nghiên cứu tập trung vào việc thiết kế các sơ đồ mã hoá và giải mã với mục tiêu dễ dàng thực hiện về mặt kỹ thuật. Các nghiên cứu của Reed và Solomon (1960), Hocquenghem (1959), Bose và Chaudhuri (1960), Gorenstein và Zierler (1961) và Peterson (1961) đều tập trung theo hướng này [45], [59], [74]. Bằng cách kết hợp mỗi con số của mã với một phần tử trong trường Galois, có thể tìm được phương trình đại số mà các nghiệm của nó mô tả vị trí của các lỗi. Do đó, độ phức tạp tính toán khi giải mã cũng giảm đi bằng cách thiết lập các phương trình đại số và tìm nghiệm của chúng.
6 Trong những năm gần đây các nghiên cứu về lý thuyết mã tập trung vào việc xây dựng các phương pháp mã hóa đạt được giới hạn của Shannon bao gồm các hướng: điều chế mã lưới - TCM (Trellis Coded Modulation), mã Turbo [61], mã kiểm tra chẵn lẻ mật độ thấp - LDPC (Low-Density Parity Check) [32], mã khối không gian-thời gian – STBC (Space-Time Block Code) [47]. Các quan điểm xây dựng mã cũng rất phong phú: dựa trên các cấu trúc đại số, dựa trên lý thuyết dàn, dựa trên hình học – đại số, dựa trên hình học chiếu, dựa trên lý thuyết tổ hợp, dựa trên Graph. Các phương pháp giải mã chính được nghiên cứu bao gồm: giải mã ngưỡng của Messey [51], giải mã liên tiếp của Zigalgirov, giải mã Viterbi [7], giải mã hợp lý tối đa [54], giải mã lặp và giải mã có liên hệ ngược, giải mã đại số [7]. Các công trình nghiên cứu cho thấy, các mã sửa lỗi (ECC - Error Correcting Code) là hướng kiến thiết cho định lý tồn tại là định lý mã hoá thứ hai của CE. Shannon [59], [70]. Hướng nghiên cứu chủ đạo ở đây là xây dựng các mã trên các cấu trúc đại số khác nhau như nhóm, vành, trường, module, không gian tuyến tính [69], [74]. Mã (hay bộ mã) được xem là một tập con có cấu trúc trong một cấu trúc đại số nào đó [35]. Một trong các lớp mã quan trọng của mã khối tuyến tính đó là các mã cylic, trong đó thành tựu nổi bật nhất và được ứng dụng rộng rãi nhất trong thực tế là các mã cyclic trên vành đa thức [17], [59]. Mã cyclic được Eugene Prange nghiên cứu đầu tiên năm 1957 [65]. Sau đó quá trình nghiên cứu về mã cyclic tập trung theo cả hai hướng sửa lỗi ngẫu nhiên và sửa lỗi cụm. Nhiều lớp mã cyclic đã được xây dựng trong những năm này, bao gồm các mã BCH (Bose, Chaudhuri, and Hocquenghem), các mã Reed-Solomon, các mã hình học Euclid [74], [77]. Mã cyclic gồm các từ mã là bội của đa thức sinh g ( x) , với g ( x) | ( x n  1) [74]. Từ mã hay đa thức mã a( x) của mã cyclic là một phần tử của ideal g ( x) thoả mãn điều kiện a ( x) g ( x) [59]. Một tính chất quan trọng rất thuận lợi cho việc mã hoá và giải mã cho các mã cyclic là dịch vòng của một đa thức mã cũng là một đa thức mã
7 [59], [7]. Các mã cyclic được ứng dụng rất rộng rãi trong thực tế. Rất nhiều đa thức sinh cụ thể đã được sử dụng trong các chuẩn truyền tin [74]. Các thiết bị mã hoá và giải mã trong thực tế được thực hiện rất đơn giản bằng các bộ ghi dịch tuyến tính có liên hệ ngược [51]. Có thể đánh giá rằng các nghiên cứu về mã cyclic đã được hoàn thiện vào những năm 70 của thế kỷ 20 [77]. Mặc dù có nhiều ưu điểm nhưng có thể nhận thấy một số hạn chế của mã cyclic như sau: Mã cyclic (n, k ) chủ yếu được xây dựng cho các giá trị n lẻ, số các đa thức sinh có thể được lựa chọn để tạo các mã tốt không nhiều và phụ thuộc vào số ideal có thể xây dựng. Nếu phân tích nhị thức  x n  1 thành tích của các đa thức bất khả qui thì khả năng lựa chọn rất thấp khi không có nhiều đa thức bất khả qui. Điều này đặc biệt thấy rõ đối với các vành đa thức có hai lớp kề cyclic (với n = 3, 5, 11, 13, 17, 19,…), các vành này không thể xây dựng được các mã cyclic tốt ngoài hai mã tầm thường duy nhất là mã (n, n  1) (mã kiểm tra chẵn) và mã (n,1) (mã lặp) [1]. Các hạn chế này có thể xem là do tính chặt chẽ về cấu trúc của mã cyclic. Ngược lại, với mã ngẫu nhiên tuyến tính của Shannon ta thấy không có những hạn chế này. Shannon đã chứng minh rằng luôn tồn tại các mã tốt thỏa mãn định lý mã hóa thứ hai. Tuy nhiên do tính lỏng lẻo về mặt cấu trúc nên rất khó khăn cho việc thực hiện mã hóa và giải mã có hiệu quả cho các mã này. Cần chú ý thêm là việc nghiên cứu các ideal trên vành số đã xây dựng được các mã AN-cyclic [74] được sử dụng có hiệu quả trong kỹ thuật máy tính. Phần tiếp theo luận án sẽ trình bày một số nội dung lý thuyết về mã tuyến tính, cơ sở lý thuyết về mã cyclic xây dựng trên vành đa thức. 1.2. VÀNH ĐA THỨC 1.2.1. Một số khái niệm cơ bản Định nghĩa 1.1: R là một vành giao hoán, một đa thức của biến x trên vành R là một biểu thức có dạng [7]: n 1 f ( x)   f i xi (1.1) i 0
8 Trong đó: f i – là hệ số, fi  R . Trong trường GF (2) , f i nhận giá trị 0 hoặc 1. x – biến, ẩn hình thức. Bậc của đa thức f ( x) là: deg f ( x)  n  1 f ( x) được gọi là định chuẩn nếu hệ số cao nhất của nó f n 1  1 . Nếu f ( x)  f 0 (đa thức hằng số), f 0  0 thì f ( x) có bậc 0. Nếu f i  0 với i  0   n  1 , thì f ( x) được gọi là đa thức 0. Định nghĩa 1.2: Cho R là một vành giao hoán, vành đa thức R[ x] là một vành được tạo bởi tập tất cả các đa thức của biến x có các hệ số trong R . Hai phép toán là phép cộng và phép nhân đa thức theo modulo ( x n  1) [7], [63]. Khi các hệ số của đa thức nằm trong trường nhị phân GF (2) , phép cộng và phép trừ là tương đương, vành đa thức được ký hiệu 2 [ x] / ( x n  1) . Trong trường nhị phân, vành đa thức ký hiệu: ( f ( x); , )  2 [ x] / ( x n  1) . e( x)  0 gọi là phần tử đơn vị, deg e( x)  0 . ( f ( x), ) là một nhóm đối với phép cộng, thỏa mãn tiên đề của nhóm. ( f ( x), ) là nửa nhóm đối với phép nhân, tồn tại f ( x) , g ( x) thỏa mãn f ( x)  g ( x)  0 . n 1 n 1 * Phép cộng hai đa thức: Xét hai đa thức a( x)   ai xi và b( x)   bi xi , đa i 0 i 0 thức c( x) là tổng của hai đa thức này và được tính như sau: n 1 c( x)  a( x)  b( x) với c( x)   ci xi và ci  ai  bi (1.2) i 0 Phép cộng các hệ số ai và bi được thực hiện trên trường (cộng theo modulo). Bậc của c( x) : deg c( x)  max deg a( x), deg b( x) * Phép nhân hai đa thức: