Nhóm Nhân Cyclic Và Mã Cyclic Trên Vành đa Thức (LA Tiến Sĩ) - 123doc

Tải bản đầy đủ (.pdf) (165 trang)

1. Trang chủ
>>
2. Công Nghệ Thông Tin
>>
3. Kỹ thuật lập trình

Nhóm nhân cyclic và mã cyclic trên vành đa thức (LA tiến sĩ)

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (3.83 MB, 165 trang )

BỘ THÔNG TIN VÀ TRUYỀN THÔNGHỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNGNGUYỄN TRUNG HIẾUNHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊNVÀNH ĐA THỨCLUẬN ÁN TIẾN SĨ KỸ THUẬTHÀ NỘI – 2017BỘ THÔNG TIN VÀ TRUYỀN THÔNGHỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNGNGUYỄN TRUNG HIẾUNHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊNVÀNH ĐA THỨCCHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬMÃ SỐ: 9520203LUẬN ÁN TIẾN SĨ KỸ THUẬTNGƯỜI HƯỚNG DẪN LUẬN ÁN:1. GS.TS. NGUYỄN BÌNH2. TS. NGUYỄN NGỌC MINHHÀ NỘI – 2017iLỜI CAM ĐOANTô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ếtquả trình bày trong luận án là trung thực và chưa được công bố ở bất kỳ côngtrình nào khác.Tác giảNguyễn Trung HiếuiiLỜI CẢM ƠNLuậ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ưuchí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ọcMinh. 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ầytrự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 trongHộ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ễnthô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 đangcô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 2017iiiMỤC LỤCLỜI CAM ĐOAN ................................................................................................................ ILỜI CẢM ƠN .................................................................................................................... IIDANH MỤC CÁC TỪ VIẾT TẮT ................................................................................... VDANH MỤC CÁC KÝ HIỆU .........................................................................................VIIDANH MỤC CÁC BẢNG ............................................................................................... IXDANH MỤC CÁC HÌNH VẼ ........................................................................................... XMỞ ĐẦU ............................................................................................................................ 11. LÝ DO NGHIÊN CỨU ................................................................................... 12. MỤC ĐÍCH NGHIÊN CỨU ............................................................................ 13. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU................................................. 24. PHƯƠNG PHÁP VÀ CÔNG CỤ NGHIÊN CỨU .......................................... 25. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI .............................. 26. CẤU TRÚC CỦA LUẬN ÁN ......................................................................... 3CHƯƠNG 1: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU .............................................. 51.1. GIỚI THIỆU CHUNG .................................................................................. 51.2. VÀNH ĐA THỨC ........................................................................................ 71.2.1. Một số khái niệm cơ bản ..................................................................... 71.2.2. Chu trình và lũy đẳng ........................................................................ 101.3. MÃ TUYẾN TÍNH ..................................................................................... 131.3.1. Mã cyclic truyền thống ...................................................................... 131.3.2. Một số mã tuyến tính khác ................................................................ 161.3.3. Một số tiêu chuẩn đánh giá mã tuyến tính ........................................ 181.4. PHÂN HOẠCH VÀNH ĐA THỨC VÀ MÃ CYCLIC CỤC BỘ ............. 191.4.1. Nhóm nhân cyclic .............................................................................. 191.4.2. Cấp số nhân cyclic ............................................................................. 241.4.3. Phân hoạch vành đa thức ................................................................... 241.4.4. Mã cyclic cục bộ trên vành đa thức ................................................... 311.5. HƯỚNG NGHIÊN CỨU CỦA LUẬN ÁN VÀ MỘT SỐ KẾT QUẢ LIÊNQUAN.......................................................................................................... 341.6. KẾT LUẬN CHƯƠNG .............................................................................. 37CHƯƠ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 ................................. 392.1. GIỚI THIỆU ............................................................................................... 39iv2.2. XÁC ĐỊNH CẤP CỦA ĐA THỨC ............................................................ 402.2.1. Đề xuất phương pháp xác định cấp của tích các đa thức .................. 402.2.2. Đề xuất phương pháp xác định cấp của nhị thức .............................. 452.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ênvành ................................................................................................... 512.2.4. Xác suất chọn đa thức có cấp cực đại ............................................... 562.3. QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLICVỚI MÃ CYCLIC TRUYỀN THỐNG ...................................................... 582.3.1. Cơ sở toán học ................................................................................... 582.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 ............................................................................ 602.3.3. Thuật toán xác định nhóm nhân cyclic tương đương mã cyclic truyềnthống .................................................................................................. 632.4. MỘT CÁCH PHÂN LOẠI MÃ TUYẾN TÍNH MỚI ................................ 692.5. KẾT LUẬN CHƯƠNG .............................................................................. 73CHƯƠNG 3: ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC ......... 753.1. PHƯƠNG PHÁP XÂY DỰNG MÃ CYCLIC ........................................... 753.1.1. Phương pháp xây dựng mạch mã hóa ............................................... 753.1.2. Phương pháp xây dựng mạch giải mã ............................................... 773.2. ĐỀ XUẤT MỘT SỐ MÃ CYCLIC TỐT TRÊN VÀNH ĐA THỨC ........ 793.2.1. Phương pháp tìm mã cyclic tốt .......................................................... 793.2.2. Mô phỏng, đánh giá một số bộ mã cyclic tốt .................................... 903.2.3. Đề xuất thực hiện các bộ mã trên FPGA ........................................... 953.3. ĐỀ XUẤT PHƯƠNG PHÁP TẠO KHÓA CHO MỘT SỐ HỆ MẬT ...... 973.3.1. Quan hệ giữa vành đa thức có hai lớp kề cyclic và trường số .......... 973.3.2. Hệ mật Omura-Massey trên vành đa thức có hai lớp kề cyclic ...... 1003.4. KẾT LUẬN CHƯƠNG ............................................................................ 105KẾT LUẬN ..................................................................................................................... 107CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ................................................... 108TÀI LIỆU THAM KHẢO .............................................................................................. 110PHỤ LỤC........................................................................................................................ 119vDANH MỤC CÁC TỪ VIẾT TẮTTừ viết tắtBCHNghĩa tiếng AnhBose,Chaudhuri,HocquenghemNghĩa tiếng Việtand (Tên ba tác giả nghiên cứu ramã BCH)CGPCyclic Geometic Progressions Cấp số nhân cyclicCMGCyclic Multiplicate GroupNhóm nhân cyclicCRCCyclic Redundancy CheckKiểm tra dư thừa vòngECCError Correcting CodeMã sửa lỗiFPGAField Programable Gate Array Mảng cổng logic khả trìnhMTDMajority-basedThreshold Giải mã ngưỡng theo đa sốDecodeMã cyclic cục bộLCCLocal Cyclic CodeOALCCOrthogonalable Local Cyclic Mã cyclic cục bộ có khả năngCodetrực giaoOLCCOrthogonal Local Cyclic Code Mã cyclic cục bộ tự trực giaoLDPCLow-Density Parity CheckMã kiểm tra chẵn lẻ mật độthấpTiến hóa dài hạnLTELong Term EvolutionRSMARepeated Square and Multiply Thuật toán nhân và bìnhAlgorithmphương lặpSTBCSpace-Time Block CodeMã khối không gian-thời gianTCMTrellis Coded ModulationĐiều chế mã lướiCSCheck-sumTổng kiểm traviOACSOrthogonalable check-sumTổng kiểm tra có khả năng trựcgiaoTổng kiểm tra trực giaoOCSOrthogonal check-sumVHDLVHSIC Hardware Discription Ngôn ngữ mô tả phần cứngLanguageWCDMAWidebandCodeMultiple AccessDivision Đa truy nhập phân chia theo mãbăng rộngviiDANH MỤC CÁC KÝ HIỆUKý hiệuNghĩa tiếng AnhNghĩa tiếng ViệtCSet of cyclesTập hợp các chu trìnhCSCycleChu trìnhd0Hamming distanceKhoảng cách HammingdegDegreeBậc của đa thứce( x )IdempotentĐa thức lũy đẳnge0 ( x)Swallowing IdempotentLũy đẳng nuốtFieldTrườngGGroupNhómGF ( p)Galois FieldTrường GaloisgcdGreatest common divisorƯớc chung lớn nhấtIIdealIdeallcmLeast common multipleBội chung nhỏ nhấtModModuloPhép chia lấy phần dưordOrderCấp của đa thứcRRingVànhWWeightTrọng số2[ x] / ( x n  1)Polynomial for Integer mod 2 Vành đa thức trênIntersectionGiaoUnionHợpEmpty setTập hợp rỗng2viii# hoặc ...CardinalityLực lượng hay số phần tử~SimilarityTương đươngSummationTổngNon-redundant divisionPhép chia hếtDivisor or dividesƯớcNot divisor or not dividesKhông là ướcCeilingSố nguyên nhỏ nhất lớn hơn|...hoặc bằng giá trị trong ngoặcixDANH MỤC CÁC BẢNGBảng 1.1. Bảng giá trị củannhỏ hơn 1000 thỏa mãn2[ x] / ( x n  1) là một vànhđa thức có 2 lớp kề cyclic ................................................................. 10Bảng 1.2. Số kiểu phân hoạch không suy biến M của một số vành ................ 27Bảng 1.3. Tổng số các kiểu phân hoạch của vành2[ x] / ( x n  1) ...................... 28Bả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................ 48Bảng 2.2. So sánh thời gian tính toán của hai thuật toán ................................... 54Bảng 2.3. Kết quả khảo sát 35 giá trịn............................................................. 57Bảng 3.1. Một số cặp vành có thể phân hoạch hỗn hợp .................................... 84Bảng 3.2. Đề xuất một số bộ mã cyclic tốt ........................................................ 89Bả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ố…98Bả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..99xDANH 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 ...................... 55Hình 2.2. So sánh các mã cyclic và mã cyclic cục bộ........................................70Hì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..72Hì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ị .. 76Hình 3.2. Phân hoạch vành có nhóm nhân sinh là nhóm nhân cyclic bất kỳ .... 77Hì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âncyclic............................................................................................................ 88Hình 3.4. Sơ đồ hệ thống thông tin sử dụng mô phỏng, đánh giá mã cyclic ..... 90Hình 3.5. Kết quả mô phỏng bộ mã cyclic (255,9,127) ..................................... 92Hình 3.6. Kết quả mô phỏng bộ mã cyclic (15,5,7) ........................................... 93Hình 3.7. Kết quả mô phỏng bộ mã cyclic (27,9,9) ........................................... 94Hình 3.8. Giao thức truyền thông sử dụng hệ mật O-M .................................. 1011MỞ ĐẦU1. LÝ DO NGHIÊN CỨULý thuyết mã hóa đã được nghiên cứu từ những năm 1940 và được ứng dụngrộ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ângcao 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ốituyế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ạimã 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âncyclic trên vành đa thức, và mã được gọi là mã cyclic cục bộ (LCC- Local CyclicCode). Các nghiên cứu gần đây đã đưa ra một số phương pháp phân hoạch vành đathứ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ụcbộ. Chính vì lẽ đó, nghiên cứu sinh đã chọn đề tài “Nhóm nhân cyclic và mã cyclictrê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ửalỗi và mật mã trong các hệ thống truyền thông.2. MỤC ĐÍCH NGHIÊN CỨUMụ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ệmvề nhóm nhân cyclic và mã cyclic trên các vành đa thức, trong đó các kết quả nghiêncứ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ớimã 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ốiquan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, cấpcủ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ựchóa các mã cyclic trên FPGA (Field Programable Gate Array).4. PHƯƠNG PHÁP VÀ CÔNG CỤ NGHIÊN CỨUPhươ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ôngcụ 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ỏngtrên máy tính và các chương trình phần mềm xử lý (C++, Matlab, VHDL (VHSICHardware Discription Language), Excel).5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀINhữ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ópchí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 quaviệ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ớimã 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 ÁNNộ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ếtquả 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 đathứ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 dungvề 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, chutrình, luỹ đẳng, vành đa thức có hai lớp kề cyclic, trong đó Luận án đề cập việcchứ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ứccó 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 trongchươ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ạchvà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ôngtrì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ápkiế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 đathứ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ànchỉnh bài toán đặt ra. Nội dung thứ hai là nghiên cứu, đánh giá mối quan hệ giữa4các nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, đã góp phầnchỉ ra có một mối quan hệ tương đương giữa mã cyclic truyền thống với mã cyclicxâ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ứutrê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 khoahọ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ộidung 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ấtmộ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ươngphá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ứngFPGA, đư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ã chophù 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âncyclic 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ópkể trên và đưa ra những vấn đề mở trong tương lai.5CHƯƠNG 1: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨUNội dung của chương trình bày lý thuyết tổng quan về vành đa thức, nhómnhân cyclic, cấp số nhân cyclic và mã cyclic. Các tiêu chuẩn đánh giá mã sửa lỗicũ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ácnghiê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ứutrước đây và đề xuất hướng nghiên cứu, phạm vi nghiên cứu và phương thức tiếpcận của luận án.1.1. GIỚI THIỆU CHUNGLý thuyết mã hoá được bắt đầu nghiên cứu từ những năm 1940 và được pháttriể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 haină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êncứ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ácmạ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ệnnay đề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ếtkế 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ácnghiê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ướngnà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ử trongtrườ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áchthiết lập các phương trình đại số và tìm nghiệm của chúng.6Trong những năm gần đây các nghiên cứu về lý thuyết mã tập trung vào việcxâ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áchướ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ốikhô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ênlý 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ưỡngcủa Messey [51], giải mã liên tiếp của Zigalgirov, giải mã Viterbi [7], giải mã hợplý 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 CorrectingCode) 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áccấ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 trongthự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ênvà sửa lỗi cụm. Nhiều lớp mã cyclic đã được xây dựng trong những năm này, baogồ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ứcsinh 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ínhcó liên hệ ngược [51]. Có thể đánh giá rằng các nghiên cứu về mã cyclic đã đượchoà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ã cyclicnhư sau: Mã cyclic (n, k ) chủ yếu được xây dựng cho các giá trị n lẻ, số các đathứ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ấtkhả 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ềunày đặc biệt thấy rõ đối với các vành đa thức có hai lớp kề cyclic (vớin= 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 haimã 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ữnghạ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 choviệ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ỨC1.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ànhR là một biểu thức có dạng [7]:n 1f ( x)   f i xii 0(1.1)8Trong đó: 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  1f ( 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ộtvà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éptoá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ệu2[ 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ãnf ( x)  g ( x)  0 .n 1n 1i 0i 0* Phép cộng hai đa thức: Xét hai đa thức a( x)   ai xi và b( x)   bi xi , đathức c( x) là tổng của hai đa thức này và được tính như sau:n 1c( x)  a( x)  b( x) với c( x)   ci xi và ci  ai  bi(1.2)i 0Phép cộng các hệ số ai và bi được thực hiện trên trườngBậc của c( x) : deg c( x)  max deg a( x), deg b( x)* Phép nhân hai đa thức:(cộng theo modulo).9Xét 2 đa thức a( x) , b( x) ; c( x) là tích của hai đa thức và được tính như sau: n 1 i   n 1c( x)  a( x).b( x)    ai x    b j x j  mod  x n  1 i 0  j 0(1.3)* Đa thức bất khả quy:Định nghĩa 1.3: Đa thức f ( x) với deg f ( x)  1 được gọi là đa thức bất khảquy nếu nó chỉ chia hết cho 1 và chính nó [7].Như vậy đa thức bất khả quy là đa thức không thể phân tích được thành tíchcủa các đa thức có bậc nhỏ hơn.Định lý 1.1: Bất kỳ đa thức bất khả quy nào trên trường GF (2m ) đều là ướccủa x 2m1 1 [7].Định nghĩa 1.4: Đa thức g *( x) được gọi là đa thức đối ngẫu của đa thứcg ( x) nếu g *( x)  x deg g ( x ) .g ( x 1 ) [7].* Đa thức đối xứng:Định nghĩa 1.5: Đa thức a ( x) được gọi là đa thức đối xứng với đa thức a( x)nếu [20]:a( x)   ai xi thì a ( x)   a j x jiIVới: IJ =; I(1.4)jJJ  S  0,1,..., n  1 .Dựa vào tính chất của lũy đẳng nuốt, ta có: a  x   en  x   a  x * Vành đa thức có hai lớp kề cyclic:Định nghĩa 1.6: Vành đa thức theo modulo x n  1 được gọi là vành đa thứccó hai lớp kề cyclic nếu phân tích của x n  1 dưới dạng tích các đa thức bất khả quytrên trường GF(2) có dạng [1]:n 1x n  1  ( x  1) xii 0(1.5)10n 1trong đó, ( x  1) và en ( x)   xi là các đa thức bất khả quy.i 0Nhận xét:- Vành đa thức2[ x] / ( x n  1) có hai lớp kề cyclic là vành đa thức mà trong đóchỉ có 2 chu trình (mục 1.2.2.1): C0  0 , C1  1, 2, 22 ,..., 2n 2  với 2n1  1mod n .- Vì en ( x) là một đa thức bất khả quy nên n phải là một số lẻ.Bổ đề 1.1: Vành đa thức theo modulo x n  1 là một vành đa thức có hai lớp kềcyclic nếu n thoả mãn [1]:nphần tử 2 phải thoả mãn điều kiện 2 ( n)/ p  1mod n với mỗi ước nguyên tốphải là một số nguyên tố;p của  (n) , với  (n) là hàm phi Euler.Căn cứ vào đặc điểm trên của vành đa thức có hai lớp kề cyclic, tác giả của[1] đề xuất một thuật toán xác định giá trị n thỏa mãn vành đa thức có hai lớp kềcyclic. Ví dụ, các số n nhỏ hơn 1000 thoả mãn điều kiện2[ x] / ( x n  1) là một vànhđa thức có 2 lớp kề cyclic được liệt kê trong Bảng 1.1.Bảng 1.1. Bảng giá trị của n nhỏ hơn 1000 thỏa mãn2[ x] / ( x n  1) là một vànhđa thức có 2 lớp kề cyclicn = 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 163 173 179 181 197 211 227 269293 317 347 349 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613 619 653659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 9471.2.2. Chu trình và lũy đẳng1.2.2.1. Chu trình* Khái niệm [6]Các chu trình Ci theo modulo n trên trường GF (2) được xác định như sau:Ci  i.2 j , j  0,1, 2,...(1.6)11Tập các số nguyên theo modulo n được phân hoạch thành các chu trình.Sn  0, 1, 2, 3,..., n (1.7)CiiSố phần tử của chu trình Ci được gọi là lực lượng của chu trình, ký hiệu Ci .* Một số ý nghĩa của việc phân tích chu trình:+ Số lượng chu trình cho biết số đa thức bất khả quy trong vành2[ 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 ứngtrong phân tích của nhị thức x n  1 .+ Các số trong một chu trình cho biết số mũ tương ứng của lũy đẳng e( x) .1.2.2.2. Lũy đẳngĐịnh nghĩa 1.7: Trong vành đa thức2[ x] / ( x n  1) , đa thức có giá trị bìnhphương bằng chính nó thì được gọi là đa thức lũy đẳng, ký hiệu e( x) [6].e( x)  e2 ( x)  e( x 2 )(1.8)Các lũy đẳng e( x) được xác định trên cơ sở phân tích chu trình Ci .Ví dụ 1.1:n  5:C0  0 ; C1  1, 2, 4,3 . Do đó, có các lũy đẳng:e0  1; e1  x  x 2  x3  x 4n  7:C0  0 ; C1  1, 2, 4 ; C3  3, 6,5 . Do đó, có các lũy đẳng:e0  1; e1  x  x 2  x 4 ; e2  x 3  x 5  x 6n  9:C0  0 ; C1  1, 2, 4,8, 7,5 ; C3  3, 6 . Do đó, có các lũy đẳng:e0  1; e1  x  x 2  x 4  x5  x 7  x8 ; e2  x 3  x 6Định nghĩa 1.8: Trong vành đa thức2[ x] / ( x n  1) với n lẻ, luôn tồn tại duyn 1nhất một lũy đẳng “nuốt” (Swallowing Idempotent) en ( x)   xi [6].i 012Bổ đề 1.2: Cho f ( x) n, en ( x) 2 [ x] / ( x  1)n 1xilà lũy đẳng nuốt.i 01) f ( x).en ( x)  W ( f ( x)) mod 2  .en ( x) mod ( x n  1)2) en ( x)  en2 ( x) mod ( x n  1) với n lẻ.Hệ quả: Với f ( x) 2[ x] / ( x n  1) , thì:𝑓 (𝑥). 𝑒𝑛 (𝑥) = {𝑒𝑛 (𝑥) nếu 𝑊(𝑓(𝑥)) lẻ0nếu 𝑊(𝑓(𝑥)) chẵn(1.9)Định nghĩa 1.9: Lũy đẳng nguyên thủy là các đa thức chứa các đơn thức vớisố mũ thuộc Ci . Tập các lũy đẳng nguyên thủy với phần tử 0 tạo nên vành lũy đẳng[7].Ví dụ 1.2: Xét vành x9  1 , theo định nghĩa về chu trình, ta có:C0  0 e0  x   1C1  1, 2, 4,8,7,5 e1  x   x  x 2  x 4  x5  x 7  x8C3  3,6 e3  x   x3  x6C0 C1  0,1, 2, 4,8,7,5 e01  x   1  x  x 2  x 4  x5  x7  x8C0 C3  0,3,6 e03  1  x3  x 6C1 C3  1, 2,3, 4,5,6,7,8 e23  x   x  x2  x3  x4  x5  x6  x7  x8C0 C1 C3  0,1, 2,3, 4,5,6  e013  x   1  x  x 2  x3  x 4  x5  x6  x7  x8Trong trường hợp này, e013  x  chính là lũy đẳng nuốt của vành.Vành đa thức x9  1 sẽ được phân tích dưới dạng tích của 03 đa thức bất khả9236quy: x  1  (1  x)(1  x  x )(1  x  x ) . Số đa thức bất khả quy bằng với số lượngchu trình và bậc của các đa thức này bằng với số chữ số trong các chu trình (tươngứng là 1 ( C0 ), 2 ( C3 ) và 6 ( C1 )).131.3. MÃ TUYẾN TÍNHMã tuyến tính độ dàinlà mã mà từ mã của nó có các dấu mã là các dạng tuyếntính. Mã hệ thống tuyến tính (n, k ) là mã tuyến tính độ dàintrong đó ta có thể chỉra được vị trí của k dấu thông tin trong từ mã. Mã tuyến tính ngẫu nhiên là mã tuyếntính có các dấu mã được chọn ngẫu nhiên từ các dạng tuyến tính có thể có [7]. Mộtsố mã tuyến tính phổ biến như: mã chẵn lẻ, mã lặp, mã vòng, mã Hamming, mãGolay, mã BCH, mã Reed-Solomon, mã Goppa,… [7], [35], [74]. Tiếp theo luận ángiới hạn trình bày về mã cyclic, một số mã có tính chất tương tự có thể xây dựngtrên vành đa thức, và một số tiêu chuẩn đánh giá mã tuyến tính phổ biến.1.3.1. Mã cyclic truyền thống1.3.1.1. Ideal của vành đa thứcĐịnh nghĩa 1.10: Ideal I của vành đa thức gồm tập các đa thức a( x) là bộicủa một đa thức g ( x) thỏa mãn [7]:nn+ g ( x) | ( x  1) ( g ( x) là ước của ( x  1) ).+ deg g ( x)  r  min deg a( x) với a( x)  I, a( x)  0 .riKý hiệu Ideal trong vành đa thức là I  g ( x) . Với mọi g ( x)   gi x , ta có:i 0g0  gr  1, gi 0,1 vớii  1, r  1 .Để tìm các tất cả các Ideal trong vành đa thứcx n  1 cần phải thực hiện phân tích vành này thành tích của các đa thức bất khả quy.1.3.1.2. Định nghĩa mã cyclicMã cyclic được định nghĩa theo một trong hai cách dưới đây:Định nghĩa 1.11: Mã cyclic (n, k ) là Ideal I  g ( x)2[x]/(x n  1)của vành đa thức[7].Trong đó,n là bậc của đa thứcx n  1 (cũng là độ dài từ mã),thức sinh g ( x) và k  n  r (cũng là số bit thông tin của từ mã).rlà bậc của đa

Tài liệu liên quan

• Một số ứng dụng điển hình và các dự án điển hình đã được triển khai trên nền tảng mã nguồn mở NUKEVIET
  • 18
  • 739
  • 2
• Lập trình điều khiển đèn LED1 và LED2 qua các nút nhấn trên giao diện máy tính
  • 16
  • 897
  • 5
• Tài liệu Vẽ mắt cho nhân vật docx
  • 16
  • 477
  • 1
• Tài liệu Vẽ Mặt Cho Nhân Vật docx
  • 8
  • 386
  • 0
• 05 quản lý tài khoản người dùng và nhóm trên AD
  • 8
  • 411
  • 3
• Tài liệu Bài toán nhận dạng vân tay và ứng dụng trên môi trường Web - Internet pptx
  • 6
  • 636
  • 6
• Tài liệu Làm Blog dựa trên mã nguồn mở và Freehost doc
  • 8
  • 329
  • 0
• Tài liệu Phân hoá của vành đa thức theo các phần tử liên hợp và ứng dụng trong lý thuyết mã docx
  • 8
  • 669
  • 0
• Tài liệu Mã hóa & bảo vệ bookmark trên Firefox và Chrome ppt
  • 3
  • 250
  • 0
• Tài liệu Mã hóa và bảo vệ bookmark trên Firefox và Chrome doc
  • 3
  • 389
  • 0

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(3.83 MB - 165 trang) - Nhóm nhân cyclic và mã cyclic trên vành đa thức (LA tiến sĩ) Tải bản đầy đủ ngay ×