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

MÃ SỐ: 9520203

CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ

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

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

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

CHƯƠNG 1: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU .............................................. 5

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 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

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

2.1. GIỚI THIỆU ............................................................................................... 39

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ã

CHƯƠNG 3: ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC ......... 75

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

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

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

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)

Cyclic Geometic Progressions Cấp số nhân cyclic CGP

Cyclic Multiplicate Group Nhóm nhân cyclic CMG

Cyclic Redundancy Check Kiểm tra dư thừa vòng CRC

Error Correcting Code Mã sửa lỗi ECC

Field Programable Gate Array Mảng cổng logic khả trình FPGA

Majority-based Threshold Giải mã ngưỡng theo đa số MTD

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

Orthogonal Local Cyclic Code Mã cyclic cục bộ tự trực giao OLCC

Low-Density Parity Check Mã kiểm tra chẵn lẻ mật độ LDPC

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

Space-Time Block Code Mã khối không gian-thời gian STBC

Trellis Coded Modulation Điều chế mã lưới TCM

Check-sum Tổng kiểm tra CS

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

Set of cycles Tập hợp các chu trình

Cycle Chu trình

Hamming distance Khoảng cách Hamming

Bậc của đa thức Degree

Đa thức lũy đẳng Idempotent

Swallowing Idempotent Lũy đẳng nuốt

Trường Field

Nhóm Group

Galois Field Trường Galois

Greatest common divisor Ước chung lớn nhất

Ideal Ideal

Least common multiple Bội chung nhỏ nhất

Mod Modulo Phép chia lấy phần dư

Cấp của đa thức Order

Vành Ring

Trọng số Weight

Polynomial for Integer mod 2 Vành đa thức trên

Giao Intersection

Hợp Union

Tập hợp rỗng Empty set

viii

Cardinality Lực lượng hay số phần tử # hoặc

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

DANH MỤC CÁC BẢNG

Bảng 1.1. Bảng giá trị của nhỏ hơn 1000 thỏa mãn 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 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 ...................... 28

Bảng 2.1. Bảng khảo sát cấp của đa thức 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ị ............................................................. 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

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

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:

- 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.

- Đề 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 với . 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

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.

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.

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 , với [74].

Từ mã hay đa thức mã của mã cyclic là một phần tử của ideal thoả mãn

điều kiện [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ã

[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 chủ yếu được xây dựng cho các giá trị 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 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 = 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ã (mã kiểm tra chẵn) và mã (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: là một vành giao hoán, một đa thức của biến trên vành

là một biểu thức có dạng [7]:

(1.1)

Trong đó: – là hệ số, . Trong trường , nhận giá trị 0 hoặc 1.

– biến, ẩn hình thức.

Bậc của đa thức là:

được gọi là định chuẩn nếu hệ số cao nhất của nó .

Nếu (đa thức hằng số), thì có bậc 0.

Nếu với , thì được gọi là đa thức 0.

Định nghĩa 1.2: Cho là một vành giao hoán, vành đa thức là một

vành được tạo bởi tập tất cả các đa thức của biến có các hệ số trong . Hai phép

toán là phép cộng và phép nhân đa thức theo modulo [7], [63].

Khi các hệ số của đa thức nằm trong trường nhị phân , phép cộng và

phép trừ là tương đương, vành đa thức được ký hiệu .

Trong trường nhị phân, vành đa thức ký hiệu: .

gọi là phần tử đơn vị, .

là một nhóm đối với phép cộng, thỏa mãn tiên đề của nhóm.

là nửa nhóm đối với phép nhân, tồn tại , thỏa mãn

* Phép cộng hai đa thức: Xét hai đa thức và , đa

thức là tổng của hai đa thức này và được tính như sau:

với và (1.2)

Phép cộng các hệ số và được thực hiện trên trường (cộng theo modulo).

Bậc của :

* Phép nhân hai đa thức:

Xét 2 đa thức , ; là tích của hai đa thức và được tính như sau:

(1.3)

* Đa thức bất khả quy:

Định nghĩa 1.3: Đa thức với đượ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ích

củ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 đều là ước

của [7].

Định nghĩa 1.4: Đa thức được gọi là đa thức đối ngẫu của đa thức

nếu [7].

* Đa thức đối xứng:

Định nghĩa 1.5: Đa thức được gọi là đa thức đối xứng với đa thức

nếu [20]:

thì (1.4)

Với: .

Dựa vào tính chất của lũy đẳng nuốt, ta có:

* Vành đa thức có hai lớp kề cyclic:

Định nghĩa 1.6: Vành đa thức theo modulo được gọi là vành đa thức

có hai lớp kề cyclic nếu phân tích của dưới dạng tích các đa thức bất khả quy

trên trường GF(2) có dạng [1]:

(1.5)

trong đó, và là các đa thức bất khả quy.

Nhận xét:

- Vành đa thức 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): , với .

- Vì là một đa thức bất khả quy nên phải là một số lẻ.

Bổ đề 1.1: Vành đa thức theo modulo là một vành đa thức có hai lớp kề

cyclic nếu thoả mãn [1]:

phải là một số nguyên tố; 

 phần tử 2 phải thoả mãn điều kiện với mỗi ước nguyên tố

của , với 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ị thỏa mãn vành đa thức có hai lớp kề

cyclic. Ví dụ, các số nhỏ hơn 1000 thoả mãn điều kiện 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 nhỏ hơn 1000 thỏa mãn là một vành

= 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 163 173 179 181 197 211 227 269

293 317 347 349 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613 619 653

659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 947

đa thức có 2 lớp kề cyclic

1.2.2. Chu trình và lũy đẳng

1.2.2.1. Chu trình

* Khái niệm [6]

Các chu trình theo modulo n trên trường được xác định như sau:

(1.6)

Tập các số nguyên theo modulo n được phân hoạch thành các chu trình.

(1.7)

Số phần tử của chu trình được gọi là lực lượng của chu trình, ký hiệu .

* 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ành .

+ 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 .

+ Các số trong một chu trình cho biết số mũ tương ứng của lũy đẳng .

1.2.2.2. Lũy đẳng

Định nghĩa 1.7: Trong vành đa thức , đa thức có giá trị bình

phương bằng chính nó thì được gọi là đa thức lũy đẳng, ký hiệu [6].

(1.8)

Các lũy đẳng được xác định trên cơ sở phân tích chu trình .

Ví dụ 1.1:

. Do đó, có các lũy đẳng:

Định nghĩa 1.8: Trong vành đa thức với lẻ, luôn tồn tại duy

nhất một lũy đẳng “nuốt” (Swallowing Idempotent) [6].

Bổ đề 1.2: Cho , là lũy đẳng nuốt.

với lẻ. 2)

Hệ quả: Với , thì:

(1.9) 𝑓(𝑥). 𝑒𝑛(𝑥) = { 𝑒𝑛(𝑥) nếu 𝑊(𝑓(𝑥)) lẻ 0 nếu 𝑊(𝑓(𝑥)) chẵn

Đị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ới

số mũ thuộc . 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 , theo định nghĩa về chu trình, ta có:

Trong trường hợp này, chính là lũy đẳng nuốt của vành.

Vành đa thức sẽ được phân tích dưới dạng tích của 03 đa thức bất khả

quy: . Số đa thức bất khả quy bằng với số lượng

chu 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 ( ), 2 ( ) và 6 ( )).

1.3. MÃ TUYẾN TÍNH

Mã tuyến tính độ dài là mã mà từ mã của nó có các dấu mã là các dạng tuyến

tính. Mã hệ thống tuyến tính là mã tuyến tính độ dài trong đó ta có thể chỉ

ra được vị trí của dấu thông tin trong từ mã. Mã tuyến tính ngẫu nhiên là mã tuyến

tí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ột

số 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 án

giớ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ựng

trê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ống

1.3.1.1. Ideal của vành đa thức

Định nghĩa 1.10: Ideal của vành đa thức gồm tập các đa thức là bội

của một đa thức thỏa mãn [7]:

( là ước của ). +

với . +

Ký hiệu Ideal trong vành đa thức là . Với mọi , ta có:

với . Để tìm các tất cả các Ideal trong vành đa thức

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ã cyclic

Mã cyclic được định nghĩa theo một trong hai cách dưới đây:

Định nghĩa 1.11: Mã cyclic là Ideal của vành đa thức

[7].

Trong đó, là bậc của đa thức (cũng là độ dài từ mã), là bậc của đa

thức sinh và (cũng là số bit thông tin của từ mã).

Định nghĩa 1.12: Mã cyclic là một bộ mã tuyến tính có tính chất sau: Nếu

là một từ mã thì dịch vòng của cũng là một từ mã thuộc bộ mã này [7].

Đa thức được gọi là đa thức sinh của mã cyclic. Vì Ideal chứa tất

cả các bội của nên nếu thì và hiển nhiên:

hay .

Ví dụ 1.3: Trong vành , đa thức được phân tích thành 3 đa

thức bất khả quy như sau:

sẽ có 7 đa thức sinh tương ứng để tạo ra 7 bộ mã cyclic khác nhau.

1.3.1.3. Ma trận sinh và ma trận kiểm tra của mã cyclic

Vì mã cyclic là một mã tuyến tính nên có thể mô tả nó thông qua ma

trận sinh chứa véc tơ hàng độc lập tuyến tính. Ma trận được viết như sau:

(1.10)

Vì nên có thể viết , hay:

(1.11)

Đa thức được gọi là đa thức kiểm tra.

Vì nên các đa thức và được gọi là các đa

thức trực giao.

Ta có với với

Ma trận kiểm tra của mã cyclic với đa thức sinh như sau:

(1.12)

Trong đó là đa thức đối ngẫu của

Từ công thức (1.9), (1.10) và (1.11) ta rút ra: .

. Với là một từ mã ta có:

1.3.1.4. Một số nhận xét về mã cyclic

Đặc điểm của mã cyclic:

- Mã cyclic được xây dựng trên các Ideal của vành đa thức nên số các mã

cyclic bằng số các Ideal trên vành đa thức.

- Số các Ideal phụ thuộc vào phân tích của nhị thức thành tích của các

đa thức bất khả quy.

- Khi biểu diễn một bộ mã cyclic thì thường dưới dạng đa thức sinh

của bộ mã, từ có thể tạo ra ma trận sinh hàng cột để tạo ra

mã cyclic hệ thống và không hệ thống.

Các phương pháp giải mã cho mã cyclic [7]: dùng thuật toán Megrit để giải

mã theo thuật toán dịch vòng; giải mã theo thuật toán Berlekamp; giải mã dựa vào

biến đổi Fourier trên trường hữu hạn; dùng các hệ tổng kiểm tra theo phương pháp

giải mã ngưỡng.

Các mạch lập mã và giải mã cho mã cyclic thường là các mạch nhân hoặc

mạch chia bằng các bộ ghi kết hợp với mạch cộng nhị phân.

Ưu điểm của mã cyclic [7]:

- Có cấu trúc tường minh nên dễ thực hiện về mặt kĩ thuật. Thiết bị mã hóa và giải

mã đơn giản nhờ sử dụng tính chất dịch vòng của từ mã.

- Có nhiều phương pháp giải mã hiệu quả.

- Có thể xây dựng bộ mã có khả năng sửa lỗi với số lượng tùy ý.

Do có những ưu điểm nổi bật như trên mà mã cyclic được sử dụng trong nhiều

thủ tục truyền tin thực tế [7]. Một trong các loại mã hay được sử dụng trong các

kênh thông thường hiện nay là mã cyclic-RC với các đa thức sinh có bậc khác nhau

từ RC-4 đến RC-32 [74].

Nhược điểm của mã cyclic [1], [7]: Do tính hạn chế về cấu trúc nên số các bộ

mã xây dựng được trên một phân hoạch vành bị hạn chế bởi với một số giá trị của

có rất ít các Ideal. Đặc biệt, với vành đa thức có hai chu trình chỉ

có thể xây dựng được hai bộ mã cyclic tầm thường là mã và . Với

mỗi bộ mã cyclic thì chỉ có duy nhất một phương án thiết kế mạch mã hoá và giải

mã, hơn nữa tốc độ mã hoá và giải mã chậm, cụ thể là cần phải có đúng nhịp để

tạo ra được bộ mã và giải mã thì cần xung nhịp.

Dựa vào một số giá trị có tính chất đặc biệt, mã cyclic đã tạo được một số

loại mã riêng như mã cyclic Hamming, mã BCH, mã tựa cyclic,… [7].

1.3.2. Một số mã tuyến tính khác

Mã cyclic Hamming

Mã Hamming biểu diễn dưới dạng đa thức được gọi là mã cyclic Hamming

[7]. Các bộ mã này có các đa thức sinh là các đa thức nguyên thủy, một phần tử

nguyên thủy bất kì có thể là nghiệm của đa thức mã. Trong thực tế, nếu mã cyclic

Hamming biểu diễn dưới dạng các phần tử 𝛼 là nghiệm trên trường hữu hạn thì ma

trận kiểm tra 𝐻 có thể xây dựng trên trường hữu hạn tương ứng. Mặc dù mã

Hamming là một mã hoàn thiện đạt đến giới hạn Hamming nhưng nhược điểm của

nó là chỉ sửa được một lỗi.

Mã BCH

Mã BCH là một bộ mã được đề cập tới nhiều do có được những ưu điểm sau [7]: Có

thể tạo ra các bộ mã có độ dài mã 𝑛 cũng như tốc độ mã 𝑅 = 𝑘/𝑛 đa dạng, phong

phú; Là loại mã tuyến tính rất hiệu quả; Có thuật toán giải mã đại số tổng quát.

Với mã BCH tổng quát, ta có hệ:

Trong đó:

- 𝑞: cơ số của bộ mã

- 𝑚: là một số nguyên nào đó

- 𝛿: là khoảng cách mã theo theo thiết kế (định trước).

Để giải mã cho mã BCH, cần phải giải quyết được hai vấn đề chính:

- Xác định được vị trí bit sai.

- Xác định được giá trị của bit sai.

Trường hợp mã BCH nhị phân, ta có:

Để giải mã trong trường hợp BCH nhị phân thì chỉ cần xác định được vị trí bit

sai là đủ. Để giải quyết được hai vấn đề trên cho việc thực hiện giải mã thì trình tự

giải mã cho mã BCH thường bao gồm các bước chính sau:

- Tính syndrome (lập hệ các tổng kiểm tra cho từ mã thu được), lập hàm đối

xứng cơ sở dựa trên các vị trí sai.

- Tính các số định vị sai.

- Tính giá trị của biên độ sai.

Ngoài các nhược điểm chung như mã cyclic, mã BCH còn có nhược điểm nữa

là việc xác định các đa thức sinh tạo mã rất khó khăn, vì theo định nghĩa, mã

BCH muốn sửa được sai thì đa thức sinh của nó phải là bội số chung nhỏ nhất của

các đa thức có nghiệm liên tiếp là , với là số nguyên tố có bậc ).

Với mỗi giá trị khác nhau của thì các đa thức chứa nghiệm lại khác nhau, dẫn

đến việc tìm đa thức sinh rất khó.

Mã tựa cylic (Quasi cyclic)

Mã tựa cylic là một biến thể của mã cyclic, được nghiên cứu đầu tiên bởi

Townsend R.L vào năm 1967 [75]. Theo Townsend và Weldon, mã khối tuyến tính

kích thước và được gọi là mã tựa cyclic nếu dịch vòng từ

mã đi ký hiệu thì có thể thu được từ mã khác.

Những năm gần đây, cùng với sự tiến bộ của công nghệ chế tạo vật liệu bán

dẫn, các nhà khoa học tiếp tục nghiên cứu và phát triển các mã tựa cyclic có hướng

tiếp cận với xu thế nghiên cứu hiện tại của thế giới, trong đó nổi bật là mã quasi

cyclic LDPC [56], [67], [68].

Với đặc điểm bất biến với phép quay nên mã tựa cyclic có thể dễ dàng thực

hiện trong việc lập các mạch mã hóa và giải mã. Hầu hết các công trình nghiên cứu

về mã tựa cyclic đều chưa đưa ra được một phương pháp tổng quát nào để tạo ra

được mã tựa cyclic tối ưu mà chỉ là công bố các kết quả cụ thể tìm được.

1.3.3. Một số tiêu chuẩn đánh giá mã tuyến tính

Mã cyclic là một mã tuyến tính có đặc điểm chung nổi bật là khả năng

lựa chọn mã khá phong phú, tuy nhiên để có thể thực hiện việc lựa chọn các bộ mã

tốt thỏa mãn được định lý mã hóa thứ hai của Shanon, các nhà nghiên cứu về mã

sửa lỗi đã xây dựng một bộ các tiêu chuẩn giới hạn để xác định và lựa chọn các bộ

mã tốt, trong đó phổ biến là ba giới hạn cơ bản là: Griesmer, Plotkin, Hamming [7],

[35]. Như vậy, tiêu chí xây dựng mã cyclic tốt gắn liền với việc đánh giá bộ mã tiến

tới một trong số các giới hạn này.

Giới hạn Griesmer

Với mã tuyến tính nhị phân, giới hạn Griesmer được xây dựng theo công thức:

(1.13)

Trong đó là độ dài của từ mã, là số dấu thông tin trong từ mã và là

khoảng cực tiểu của từ mã.

Giới hạn Griesmer được sử dụng trong trường hợp cố định khoảng cách cực

tiểu và số dấu thông tin , với yêu cầu tìm độ dài từ mã là nhỏ nhất.

Trường hợp tổng quát đối với mã tuyến tính phân, ta có công thức của giới

hạn Griesmer:

Giới hạn Plotkin

Với mã tuyến tính nhị phân, giới hạn Plotkin được xây dựng theo công thức:

(1.14)

Giới hạn Plotkin được xây dựng trong trường hợp cố định độ dài từ mã và

dấu thông tin, yêu cầu tìm giá trị lớn nhất của khoảng cách cực tiểu .

Trường hợp tổng quát đối với mã tuyến tính phân, giới hạn Plotkin được xây

dựng theo công thức:

Giới hạn Hamming

Với mã tuyến tính nhị phân, giới hạn Hamming được xây dựng theo công thức:

(1.15)

Giới hạn Hamming được xây dựng trong trường hợp cố định độ dài từ mã

và số lượng sai có thể sửa được cho trước, xác định độ thừa của từ mã là

nhỏ nhất (tương đương với việc xác định số dấu thông tin lớn nhất).

Mã đạt được giới hạn Hamming được gọi là mã hoàn thiện.

1.4. PHÂN HOẠCH VÀNH ĐA THỨC VÀ MÃ CYCLIC CỤC BỘ

1.4.1. Nhóm nhân cyclic

Định nghĩa 1.13: Nhóm nhân cyclic (CMG-Cyclic Multiplicate Group) trong

vành đa thức là tập hợp các phần tử bằng lũy thừa của một phần tử gọi là phần tử

sinh. Trong vành đa thức có nhiều nhóm nhân mỗi nhóm nhân có thể gồm nhiều

nhóm nhân cyclic, số nhóm nhân bằng số các lũy đẳng có thể có trong vành [6].

(1.16)

Trong đó:

là nhóm nhân cyclic.

là phần tử sinh (đa thức sinh).

là cấp của nhóm nhân, cũng chính là cấp của phần tử sinh . Cấp

của nhóm là tổng số các phần tử của nhóm.

Phần tử đơn vị của nhóm chính là một lũy đẳng có cấp bằng 1.

1.4.1.1. Nhóm nhân cyclic đơn vị

Định nghĩa 1.14: Nhóm nhân cyclic đơn vị là một nhóm nhân bao gồm mọi

đơn thức có trong vành và nó có cấp là . Ký hiệu là [7].

Hay nhóm nhân cyclic đơn vị là nhóm nhân cyclic có phần tử sinh là x.

(1.17)

1.4.1.2. Nhóm nhân cyclic với phần tử sinh

Định nghĩa 1.15: Nhóm nhân cyclic với phần tử sinh là đa thức bao gồm

các phần tử là lũy thừa của phần tử sinh và có thể viết dưới dạng sau [7]:

(1.18)

Trong đó: là cấp của .

1.4.1.3. Nhóm nhân cyclic đối xứng

Bổ đề 1.3: (Nhóm nhân cyclic đối xứng)

Xét là một phần tử sinh của nhóm nhân cyclic A, là phần tử sinh

của nhóm nhân cyclic ( được gọi là đối xứng của nhóm nhân A) [19]. Ta có:

(1.19)

Do đó, có thể khẳng định tính chất của nhóm nhân cyclic đối xứng:

(1.20)

Từ việc khảo sát các nhóm nhân đối xứng trong vành đa thức, ta thấy chỉ cần

khảo sát các nhóm nhân trong một nửa vành là ta có thể suy ra kết quả khảo sát cho

toàn bộ vành. Khi coi mỗi nhóm nhân là một mã tương ứng mà ta có thể xây dựng

được trên nó, ta sẽ khảo sát được các mã trên vành.

1.4.1.4. Cấp của đa thức và phân bố đa thức theo cấp trong CMG

a) Khái niệm cấp của đa thức

Định nghĩa 1.16: Cấp của đa thức (ký hiệu ) là số

nguyên dương nhỏ nhất thỏa mãn [59]:

hoặc (1.21)

Trong đó là lũy đẳng trong vành, thỏa mãn .

Như vậy, tạo nên một nhóm cyclic cấp trong nhóm nhân của vành.

Định lý 1.2: Xét vành đa thức với trong đó

là các đa thức bất khả quy, cấp cực đại của một đa thức nào đó được xác định

như sau [19]:

- Nếu lẻ thì .

- Nếu chẵn và có dạng thì .

* Nhận xét

Trong đó .

- Trường hợp là số Mersen: thì ta có .

- Vành chứa một số nhóm nhân với các lũy đẳng khác nhau. Số

các nhóm nhân này bằng số các Ideal trong vành. Mỗi nhóm nhân lại bao gồm một

số các nhóm con cyclic có cấp được xác định theo [25] và các ước của giá trị đó.

- Vành với lẻ được gọi là vành cơ sở. Số các Ideal trong một

vành cơ sở được xác định bằng: . Trong đó là số đa thức bất khả quy

trong phân tích nhị thức .

Ví dụ 1.4: Xét các nhóm nhân trong vành

Do nên vành này là vành cơ sở. Số Ideal trong vành này là ,

với là số đa thức bất khả quy trong phân tích nhị thức .

ứng với .

Số Ideal trong vành là . Cấp cực đại của một phần tử trong vành

này là: . Trong đó .

b) Phân bố đa thức theo cấp của đa thức trên CMG

Bổ đề 1.4: Trong một nhóm nhân cyclic cấp , cấp của đa thức thứ bằng

[44]:

(1.22)

Hệ quả: Trong một nhóm nhân cyclic cấp thì:

+ Các đa thức tại vị trí thứ nguyên tố với thì có cấp bằng , nghĩa là

thì có cấp bằng (hay ).

+ Số đa thức đạt cấp là . Trong đó: là hàm Phi-

Euler, với ; - các số nguyên tố; - các số nguyên dương.

Ví dụ 1.5: Xét vành đa thức , không xét lũy đẳng nuốt

, có 2 nhóm nhân như sau:

Cả hai nhóm nhân đều có cấp bằng 15. Xem xét CMG :

Có 8 đa thức ở các vị trí 1, 2, 4, 7, 8, 11, 13, 14 có cấp bằng 15 và là cấp cực

đại, phù hợp với hệ quả: .

Các đa thức ở vị trí thứ 3, 6, 9, 12 có cấp bằng 5 (có ). Các

đa thức này cùng với đa thức thứ 15 tạo thành nhóm nhân con {3, 1, 4, 2, 0}.

Các đa thức ở vị trí thứ 5 và 10 có cấp bằng 3 (có ). Các đa

thức này cùng với đa thức thứ 15 tạo thành nhóm nhân con {(023), (014), (0)}.

Bổ đề 1.5: Số các đa thức đạt cấp cực đại trên vành được tính bằng ,

với là cấp cực đại và là số nhóm nhân cyclic đạt cấp cực đại độc lập (nghĩa

là không có nhóm nhân nào là hoán vị của nhóm nhân khác).

Ví dụ 1.6: Xem xét các đa thức trên vành

Số đa thức đạt cấp cực đại là . Ta có 16 đa thức đạt cấp cực đại:

(012), (024), (034), (123), (013), (134), (234), (124), (01), (02), (04), (34), (03),

(23), (24), (12), (13).

1.4.2. Cấp số nhân cyclic

Xét vành đa thức với n lẻ, giả sử là số hạng đầu tiên của

cấp số nhân cyclic và là công bội của cấp số nhân.

Định nghĩa 1.17: Cấp số nhân cyclic (CGP - Cyclic Geometic Progressions)

trên vành đa thức là một tập hợp con có dạng sau [6]:

(1.23)

Trong đó: m là số các số hạng khác nhau của cấp số nhân.

là số hạng đầu của cấp số nhân.

là công bội.

Giá trị của m chính là cấp của nhóm nhân sinh với phần tử sinh và lũy

đẳng .

Trong trường hợp chọn số hạng đầu , công bội là thì

(với ) là cấp số nhân cyclic cấp m.

Như vậy, trong vành đa thức , nếu chọn số hạng đầu và hạt

nhân phân hoạch khác nhau thì sẽ tạo ra nhiều kiểu phân hoạch khác nhau của

vành, do đó sẽ có các cấp số nhân cyclic tương ứng để xây dựng được các mã cyclic

có cấu trúc khác nhau với đặc tính sửa lỗi tốt.

1.4.3. Phân hoạch vành đa thức

Quá trình phân hoạch vành đa thức thực chất là quá trình phân chia các phần

tử trong vành đa thức thành các tập (hay các lớp kề) không trùng nhau. Các phần tử

sinh của nhóm nhân sinh được gọi là các hạt nhân của phân hoạch. Trong mỗi phân

hoạch vành đa thức, các lớp kề của nó là các cấp số nhân cyclic với cùng một công

bội. Dựa vào các lớp kề này ta có thể tạo được mã LCC và các mã cyclic khác nhau.

Trong vành đa thức, số phân hoạch là khá lớn nên có thể xây dựng được nhiều mã

cyclic có đặc tính sửa lỗi tốt.

1.4.3.1. Các bước phân hoạch vành đa thức

Để phân hoạch một vành đa thức ta thực hiện theo các bước sau đây [13]:

Bước 1: + Chọn một phần tử sinh .

+ Xây dựng nhóm nhân cyclic: ,

trong đó: .

+ ;

Bước 2: + Chọn .

+ Xây dựng cấp số nhân cyclic:

Bước 3: Lặp lại bước 2 cho đến khi

Thông số là cấp của (ký hiệu ). Giá trị chỉ có thể bằng

hoặc ước số của .

Do vành đa thức có cấu trúc đối xứng, một nửa vành gồm các phần tử có trọng

số lẻ, một nửa vành gồm các phần tử có trọng số chẵn. Vì vậy, khi phân hoạch ta

chỉ cần tìm các phần tử có trọng số lẻ của vành rồi có thể dễ dàng suy ra các phần

tử chẵn (với lẻ).

Để xây dựng được tất cả các nhóm nhân của vành, ta thực hiện các bước sau:

 Xác định tất cả các đa thức lũy đẳng trong vành, trên cơ sở phân tích các

chu trình.

 Chọn các đa thức lũy đẳng có trọng số lẻ để xây dựng các nhóm nhân

chứa chúng.

 Xây dựng tất cả các nhóm nhân cyclic có thể có của vành. Tùy theo từng

lũy đẳng mà mỗi lũy đẳng có thể tham gia trong nhiều nhóm nhân.

 Lấy đối xứng tất cả các nhóm nhân có chứa các phần tử có trọng số lẻ sẽ

tạo được tất cả các nhóm nhân có chứa các phần tử có trọng số chẵn.

1.4.3.2. Phân hoạch vành đa thức suy biến và không suy biến

Quá trình phân hoạch vành đa thức thực chất là quá trình phân chia các phần

tử trong vành thành các tập không trùng nhau. Có nhiều dạng phân hoạch vành đa

thức khác nhau, song dạng phân hoạch chung nhất là phân hoạch suy biến và phân

hoạch không suy biến.

Định nghĩa 1.18: Phân hoạch vành đa thức được gọi là không suy biến nếu

phân hoạch bao gồm tất cả các phần tử khác 0 trong vành đa thức. Ngược lại, phân

hoạch là phân hoạch suy biến [13].

Bổ đề 1.6: Trong một phân hoạch không suy biến tùy ý, số lớp kề trong phân

hoạch xác định theo biểu thức [13]:

(1.24)

* Điều kiện để phân hoạch không suy biến

Định lý 1.3: Điều kiện cần và đủ để phân hoạch vành không suy biến là nhóm

nhân sinh của phân hoạch có lũy đẳng bằng 1 [13].

Bổ đề 1.7: Số kiểu phân hoạch không suy biến khác nhau bằng số các bậc khác

nhau của các phần tử trong vành (trừ các phần tử lũy đẳng có bậc là 1), ký hiệu là

[13].

Số kiểu phân hoạch không suy biến khác nhau chính là số ước khác nhau của

giá trị cấp lớn nhất của phần tử ( [25]).

Kết quả tính số kiểu phân hoạch không suy biến của một số vành được

thống kê trong Bảng 1.2.

Bảng 1.2. Số kiểu phân hoạch không suy biến của một số vành

Biểu diễn dưới n dạng tích các số nguyên tố

15 3.5 3 5

7 7 1 7

63 3.3.7 5 9

1023 3.11.31 7 11

4095 3.3.5.7.13 16 13

15 3.5 3 15

Bổ đề 1.8: Số kiểu phân hoạch suy biến (ký hiệu là ) bằng số Ideal trong vành

đa thức [13].

Trong vành đa thức , số Ideal của vành được xây dựng tương

ứng với các đa thức sinh , mỗi Ideal tương ứng với bộ mã cyclic (theo quan

điểm xây dựng mã cyclic cổ điển).

Các đa thức sinh tương ứng với mỗi Ideal được lập từ tổ hợp các đa thức

bất khả quy trong phân tích của nhị thức xn + 1.

, với (1.25)

, với | xn + 1, (1.26)

Như vậy, số đa thức sinh g(x) (tương ứng là Ideal) có thể thiết lập được từ t đa

thức bất khả quy trong phân tích nhị thức xn + 1 được xác định: .

Bổ đề 1.9: Tổng số các kiểu phân hoạch có trong một vành đa thức (ký hiệu là

) được xác định bởi biểu thức: [30].

Tổng số các kiểu phân hoạch của một số vành khác nhau

như trong trong Bảng 1.3.

Bảng 1.3. Tổng số các kiểu phân hoạch của vành

Số đa thức bất khả quy

n

M

I

C = M.I

trong phân tích xn + 1

5 2 3 2 6

7 3 1 6 6

9 3 5 6 30

11 2 7 2 14

13 2 16 2 32

15 5 3 30 90

Như vậy, trong một vành đa thức , với mỗi giá trị n thì số kiểu

phân hoạch cũng khá lớn, tạo ra khả năng lớn để chọn dạng mã cyclic có đặc tính

sửa lỗi tốt. Trong mỗi dạng mã đã xác định, tiến hành lựa chọn các mã sửa lỗi tối

ưu để sử dụng.

1.4.3.3. Các kiểu phân hoạch

a) Phân hoạch chuẩn

Phân hoạch chuẩn hay phân hoạch theo – nhóm nhân cyclic đơn vị.

(1.27)

Hạt nhân của phân hoạch là , có cấp .

+ Các lớp kề có độ lớn bằng hoặc ước của .

Bổ đề 1.10: Trong phân hoạch chuẩn thì số lớp kề trong phân hoạch được xác

định theo biểu thức [13]:

(1.28)

+ Khi n là số nguyên tố có thể tính chính xác được số lớp kề trong phân hoạch.

Có một lớp kề chỉ chứa , số phần tử còn lại trong các lớp kề là

. Do đó số các lớp kề là: .

b) Phân hoạch cực đại

Định nghĩa 1.19: Phân hoạch được gọi là cực đại nếu nhóm nhân cyclic sinh

có phần tử sinh với cấp lớn nhất, [6].

Bổ đề 1.11: Với , trong phân hoạch cực đại thì số lớp kề

của phân hoạch được xác định theo công thức sau [13]:

(1.29)

c) Phân hoạch cực tiểu

Định nghĩa 1.20: Phân hoạch là cực tiểu (hay phân hoạch tầm thường) là phân

hoạch có phần tử sinh của nhóm nhân cyclic là [6].

Bổ đề 1.12: Trong phân hoạch cực tiểu với phần tử của nhóm nhân , số

lớp kề trong phân hoạch được xác định [13]:

(1.30)

Trong phân hoạch cực tiểu, mỗi lớp kề chỉ gồm 1 phần tử, do vậy số lớp kề

trong phân hoạch này đúng bằng số phần tử khác 0 có trong vành: 2n – 1 .

d) Phân hoạch vành thành các cấp số nhân có cùng trọng số

Trong trường hợp và thì cấp số nhân bao gồm các

đa thức có cùng trọng số. Vành đa thức được phân hoạch thành các cấp số nhân với

các phần tử trong mỗi cấp số nhân sẽ có cùng trọng số.

Dạng phân hoạch này chính là phân hoạch không suy biến và phân hoạch theo

nhóm nhân đơn vị.

e) 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ố

Xét cấp số nhân cyclic có dạng sau:

- Nếu lẻ.

+ Phần tử đầu tiên là đa thức có trọng số lẻ thì tất cả các phần tử của

cấp số nhân đều là đa thức có trọng số lẻ. Vì tích của các đa thức có trọng

số lẻ là một đa thức có trọng số lẻ.

+ Phần tử đầu tiên là đa thức có trọng số chẵn thì tất cả các phần tử

của cấp số nhân đều là đa thức có trọng số chẵn.

Vậy khi lẻ  các lớp kề có các đa thức có trọng số chẵn hoặc lẻ.

- Nếu chẵn, với phần tử đầu tiên là đa thức bất kỳ thì tất cả các

phần tử của cấp số nhân đều là đa thức có trọng số chẵn  phân hoạch suy biến.

Tóm lại, nếu công bội (hạt nhân phân hoạch) là một đa thức có trọng số

lẻ thì các phần tử của mỗi cấp số nhân trong phân hoạch sẽ cùng tính chẵn lẻ về

trọng số.

f) Phân hoạch vành đa thức thành các cấp số nhân theo modulo h(x)

Vành đa thức có thể được phân hoạch thành các cấp số nhân

theo modulo với .

Từ phân tích nhị thức

Trong đó, là các đa thức bất khả quy.

Như vậy, là tổ hợp của các sao cho . Tuỳ theo giá

trị mà có số đa thức bất khả quy khác nhau, nên sẽ có số khác nhau. Khi đó,

trên vành sẽ có nhiều phân hoạch ứng với các khác nhau.

Trong trường hợp này phân hoạch vành chỉ gồm phần tử cho nên phân

hoạch sẽ suy biến và vành đa thức bị suy biến thành các vành nhỏ hơn.

1.4.4. Mã cyclic cục bộ trên vành đa thức

1.4.4.1. Khái niệm

Định nghĩa 1.21: Mã cyclic cục bộ là một mã tuyến tính có các dấu mã là một

tập con không trống tuỳ ý các lớp kề trong phân hoạch của vành đa thức theo một

nhóm nhân cyclic [6].

Nhận xét:

 Nếu chỉ chọn 1 lớp kề, khi đó mã LCC trở thành mã cyclic.

 Nếu các lớp kề được chọn có chứa nhóm nhân cyclic đơn vị

thì ta có mã LCC hệ thống.

Tập các trưởng lớp kề tạo mã sẽ mô tả đầy đủ mã LCC.

1.4.4.2. Cách biểu diễn mã cyclic cục bộ

Để có khả năng tạo ra các mã LCC có đặc tính tốt cần phải sử dụng các cấu

trúc đại số phức tạp. Việc xây dựng các mã LCC, sự phức tạp thể hiện ở chỗ: mỗi

từ mã đặc đặt lên nó hai cấu trúc đại số, mỗi từ mã là một phần tử của không gian

con tuyến tính chiều trong không gian chiều. Mặt khác, mỗi từ mã lại là một bộ

phận của vành giao hoán (hoặc ). Vì vậy, ta có thể biểu diễn từ mã LCC

theo các cách khác nhau:

a) Biểu diễn theo trưởng lớp kề

Định nghĩa 1.22: Lớp kề là một tập hợp có tối đa phần tử mà giá trị của

chúng được xác định từ phần tử trưởng lớp kề theo một biểu thức toán học (trưởng

lớp kề là phần tử đứng đầu tiên trong một lớp kề). Nếu gọi giá trị của trưởng lớp kề

là thì các phần tử khác trong lớp kề được tính [12]:

(1.31)

Cách biểu diễn này đơn giản, vì khi biểu diễn mã chỉ việc nêu các trưởng lớp

kề tham gia tạo mã và các trưởng lớp kề này được để trong dấu “{}”.

b) Biểu diễn theo ma trận sinh

Mã LCC là mã hệ thống tuyến tính nên có thể mô tả theo ma trận sinh

có hàng và cột.

(1.32)

trong đó: là ma trận đơn vị cấp .

là ma trận kiểm tra.

Biểu diễn theo trưởng lớp kề sẽ đơn giản hơn, song để biết rõ về bộ mã thì cần

phải biết cụ thể các lớp kề tham gia tạo mã, hay nói cách khác là phải biết phân

hoạch vành đa thức tương ứng với giá trị đó.

1.4.4.3. Các lớp mã LCC

a) Mã cyclic cục bộ tự trực giao (OLCC)

Do tính tính chất đơn giản của thiết bị lập mã, giải mã nên các mã OLCC là

một lớp mã quan trọng nhất trong loại mã LCC. Vì vậy việc nghiên cứu cách tạo

mã OLCC và đánh giá hiệu quả của nó là rất quan trọng [2].

Định nghĩa 1.23: Mã OLCC là bộ mã LCC với [2]:

(1.33)

Trong đó: dấu thông tin là phần tử của nhóm nhân cyclic cấp .

Các dấu kiểm tra là một tập con không trống nào đó của tất cả các phần tử

trong nhóm kề liên tiếp (từ nhóm kề thứ hai trở đi).

Định lý 1.4: Mã OLCC với sẽ có [2]

. (1.34)

Bổ đề 1.13: Giới hạn trên số tổng kiểm tra trực giao (OCS) của bộ mã OLCC

là [2]:

(1.35)

Nhận xét: Muốn thiết lập một OCS thì chỉ việc lấy tổng của 2 CS tương ứng.

Trong trường hợp mã không phải là mã OLCC thì có thể phải lấy nhiều hơn 2 CS

mới nhận được một OCS. Tuy nhiên, khi lấy càng nhiều CS thì mã xây dựng được

sẽ không tối ưu vì khi đó số OCS lập được ít và do đó d0 sẽ nhỏ.

b) Mã LCC có khả năng trực giao (OALCC)

Mã OALCC là một lớp quan trọng tiếp theo sau mã OLCC [3]. Hệ CS có khả

năng trực giao (OACS) cho một cặp dấu mã. Mạch giải mã của nó phải dùng hai

cấp ngưỡng (hoặc nhiều hơn) mới tìm được dấu cần giải mã, trong khi đó mã OLCC

chỉ cần một cấp ngưỡng.

Định nghĩa 1.24: Mã Cyclic cục bộ có khả năng trực giao là mã LCC

với [3].

Mã OALCC được xây dựng theo nguyên tắc sau:

 k dấu thông tin là k phần tử của nhóm nhân cyclic cấp k.

 Các dấu kiểm tra được lấy là các phần tử ở các lớp kề lẻ liên tiếp.

như vậy mỗi giá trị của k có thể lập được bộ mã OALCC.

Định lý 1.5: Mã OALCC với , có [3]:

(1.36)

Từ trước đến nay các nghiên cứu về mã LCC hầu như tập trung vào hai lớp

mã tự trực giao và có khả năng trực giao, ngoài ra còn có thể xây dựng được các

lớp mã được khác tùy thuộc vào việc chọn các lớp kề cyclic tương ứng.

1.5. HƯỚNG NGHIÊN CỨU CỦA LUẬN ÁN VÀ MỘT SỐ KẾT QUẢ

LIÊN QUAN

Trên thế giới, việc nghiên cứu cấu trúc đại số cho các cấu trúc mã hiện nay

vẫn đang được nghiên cứu và hoàn thiện như mã LDPC [32], [55], [66], mã Turbo

[36], [61], [76][75] nhằm mục đích tối ưu hóa các mã kênh, mã truyền tin trong các

mạng thông tin di động thế hệ mới.

Đối với mã cyclic, một số hướng nghiên cứu trên thế giới hiện nay như xem

xét một số giới hạn của mã cyclic [37], [46], [81], [82], đánh giá giới hạn Schaub

trên vành đa thức với [52], đánh giá trọng số của mã cyclic

[34], [39], [41], [42], [78], đề xuất phương án giải mã tối ưu cho mã cyclic [50],

[58]. Một số nghiên cứu đề cập đến mã tuyến tính và đặc tính của các đa thức sinh

dựa trên cấu trúc trellis [33], [49], [66], xây dựng mã cyclic [44], [53], [60], [79],

đề xuất xây dựng mã khác dựa trên mã cyclic [71], [80]. Hiện nay các công trình

nghiên cứu đề cập đến mã cyclic đều đang tìm thêm các ứng dụng dựa trên tính chất

dịch vòng của mã cyclic ví dụ tính các chuỗi nhảy tần tối ưu trong thông tin di động

[43], xác định việc đồng bộ các cell trong hệ thống WCDMA (Wideband Code

Division Multiple Access) [21], [72], xây dựng cấu trúc đại số mới để hình thành

mã quasi cyclic [57], hay quasi cyclic LDPC [56], [67], [68], hiện thực hóa các mã

cyclic trên các cấu kiện phần cứng logic khả trình FPGA (Field Programable Gate

Array) [48]. Theo lý thuyết mã cyclic cổ điển, từ cấu trúc đại số của Berlekamp

[45], đến các nghiên cứu hoàn chỉnh về xây dựng mã cyclic theo Ideal được

MacWilliams, F.J., và Sloane, N.J.A [59] tổng kết, việc nghiên cứu các mã cyclic

còn chưa chặt chẽ và mang tính tổng thể đối với vành đa thức với các

giá trị bất kỳ.

Ở Việt Nam, vào năm 1987, hai nhà khoa học Nguyễn Bình và Nguyễn Xuân

Quỳnh đã bắt đầu một hướng nghiên cứu mới về mã sửa lỗi đó là mã cyclic cục bộ

(LCC) [6], [12], [14], [24], [25]. Các nghiên cứu đầu tiên về mã LCC được thực

hiện trênh vành số . Tuy nhiên chỉ tới khi được xây dựng trên các vành đa thức

vào năm 1996 các nghiên cứu về mã LCC mới được thúc đẩy mạnh mẽ và thu được

nhiều kết quả khích lệ [6]. Các công trình có liên quan đến vấn đề này đều kèm theo

các nghiên cứu tường minh về các phương pháp giải mã ngưỡng theo các hệ tổng

kiểm tra trực giao [5], [11].

Về cơ bản, mã LCC cũng có được các ưu điểm của mã cyclic, ngoài ra mã

LCC còn có nhiều ưu điểm nổi trội khác [6], [18]:

 Số lượng mã LCC tìm được rất nhiều. Với cùng một thông số có

rất nhiều bộ mã LCC khác nhau (tương ứng có nhiều mạch mã hóa và

giải mã khác nhau).

 Có thể xây dựng được các bộ mã trên mọi vành đa thức, tức là mã LCC

có thể có các độ dài khác nhau kể cả độ dài chẵn, điều này thì mã cyclic

không thể thực hiện được.

 Về mặt kỹ thuật thì các mạch mã hóa và giải mã LCC có thể thực hiện

được tương tự các mã cyclic. Đặc biệt nếu sử dụng phương pháp giải mã

ngưỡng thì bộ giải mã rất đơn giản.

 Tốc độ lập mã LCC nhanh, mã LCC có thể tạo các khối kiểm tra (độ dài

một khối tối đa là ) một cách song song. Với mã cyclic thì phải

dùng đến nhịp, còn với một số mã LCC cùng với tham số thì chỉ

cần nhịp là tạo xong mã.

Đánh giá các công trình nghiên cứu trong nước hiện nay về mã cyclic và cyclic

cục bộ, ngoài các kết quả của các tác giả Nguyễn Bình, Nguyễn Xuân Quỳnh và

Nguyễn Thế Truyện về các mã LCC xây dựng trên các vành số [11], [16], các kết

quả còn lại đều đề cập đến việc xây dựng các mã LCC trên các vành đa thức. Các

kết quả này hiện đã hoàn thiện một số nghiên cứu 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 các mã LCC của tác giả Vũ Việt [18], [29]. Một số kết quả của tác giả Lê

Đình Thích đã chứng minh các mã cyclic là một lớp con trong các mã cyclic cục bộ

[12], [24]. Một số nghiên cứu đã xây dựng được một số lớp mã cyclic cục bộ tự trực

giao và mã cyclic cục bộ có khả năng trực giao [2], [3]. Trong một số nghiên cứu

của mình, tác giả Trần Đức Sự cũng đưa ra phương thức xây dựng được một số mã

cyclic cục bộ đối xứng và tự đối xứng trên các lớp kề (các cấp số nhân) đối xứng và

tự đối xứng [26], [27], [28]. Gần đây, tác giả Ngô Đức Thiện cũng đã đề xuất các

phương thức mới tạo ra được các bộ mã cyclic cục bộ dựa trên các phân hoạch hỗn

hợp [13], [30], tác giả Đặng Hoài Bắc nghiên cứu về các mã cyclic và cyclic cục bộ

trên vành đa thức có 2 lớp kề cyclic [1], [19], [20]. Một số cấu trúc đại số mới cũng

được ứng dụng để xây dựng hệ mật đa biểu trên một số loại vành đặc biệt [22], [23],

ứng dụng cấp số nhân cyclic và mã cyclic trong việc xây dựng các hệ mật, hàm băm

trong nghiên cứu của tác giả Hồ Quang Bửu và Ngô Đức Thiện [9], [14]. Một số

hướng nghiên cứu đang được thực hiện và có kết quả bước đầu của tác giả Nguyễn

Văn Trung nghiên cứu về các mã đối ngẫu của mã cyclic [15], tác giả Vương Đức

Hạnh nghiên cứu ứng dụng mã cyclic cục bộ xây dựng các mã khối Turbo [10].

Các công trình này đều có ý nghĩa về mặt lý thuyết, đạt được những thành tựu

và kết quả nhất định. Tuy nhiên, lý thuyết và thực nghiệm về mã cyclic cục bộ đặc

biệt là mã cyclic nói chung vẫn chưa hoàn thiện và có một số hướng nghiên cứu mở

về các mã cyclic được đề cập như sau:

- Về việc kiến thiết mã cyclic, gồm các nội dung như: Nghiên cứu mối quan

hệ giữa nhóm nhân, cấp số nhân cyclic với mã cyclic truyền thống; Xác

định cấp của đa thức và kiến thiết nhóm nhân cyclic có cấp cực đại trong

vành đa thức.

- Về phương án hiện thực bộ mã gồm các nội dung như: Phương pháp xây

dựng thiết bị mã hóa và giải mã cyclic xây dựng trên nhóm nhân cyclic

bằng các cấu kiện phần cứng khả trình FPGA; Nghiên cứu các phương pháp

giải mã khác (ngoài giải mã ngưỡng).

- Về đánh giá mã cyclic, gồm các nội dung như: Xác định mã tốt (đạt hoặc

gần đạt một trong số các tiêu chuẩn Griesmer, Plotkin, Hamming); Xây

dựng ma trận kiểm tra của mã LCC; Nghiên cứu mã LCC trên miền tần số;

Nghiên cứu phổ trọng số của mã LCC; Xây dựng tiêu chí chọn các lớp kề

để tạo các mã tốt.

- Về cấu trúc mã cyclic, gồm các nội dung như: Nghiên cứu các mã ghép xây

dựng từ mã LCC; Nghiên cứu mã LCC trên trường mở rộng ;

Nghiên cứu mã LCC theo quan điểm lý thuyết hệ thống.

Trên cơ sở tìm hiểu và đánh giá các kết quả nghiên cứu, nghiên cứu sinh xác

định tập trung luận án nghiên cứu về các hướng: kiến thiết mã cyclic, lựa chọn và

đánh giá mã cyclic tốt xây dựng trên vành đa thức, hiện thực các bộ mã cyclic trên

cấu kiện phần cứng. Cụ thể là nghiên cứu nghiên cứu việc kiến thiết nhóm nhân

cyclic có cấp cực đại, mối quan hệ của mã cyclic cục bộ (mã cyclic xây dựng từ

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 lựa chọn mã cyclic tốt, ứng dụng của nhóm nhân cyclic, cấp số nhân

cyclic trong mã sửa lỗi, mật mã, và khả năng thực hiện các bộ mã cyclic trên cấu

kiện phần cứng.

1.6. KẾT LUẬN CHƯƠNG

Trong chương này, Luận án đã trình bày cơ sở lý thuyết cho các nội dung

nghiên cứu của luận án bao gồm các nội dung về vành đa thức, vành đa thức có hai

lớp kề cyclic, tính chất đa thức, chu trình, luỹ đẳng, mã tuyến tính, mã cyclic truyền

thống, một số tiêu chuẩn đánh giá mã tuyến tính, 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ộ. Ở cuối chương trình bày

hướng nghiên của của luận án và thảo luận một số kết quả nghiên cứu liên quan từ

đó làm rõ hơn nội dung nghiên cứu của luận án.

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

Trong chương này, Luận án trình bày các kết quả nghiên cứu về phương pháp

kiến thiết nhóm nhân cyclic có cấp cực đại, 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 góp phần bổ sung và hoàn thiện lý

thuyết về mã cyclic. Nội dung chương 2 được bố cục gồm ba phần và kết luận

chương. Phần đầu tiên giới thiệu chung về nội dung của chương và các vấn đề liên

quan. Nội dung tiếp theo trình bày một số kết quả nghiên cứu mới của tác giả về

cấp của đa thức. Phần cuối cùng trình bày kết quả nghiên cứu mới về 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 qua đó chứng

minh được sự tương đương giữa nhóm nhân và cấp số nhân cyclic với mã cyclic

truyền thống.

2.1. GIỚI THIỆU

Trong chương 1 đã đề cập đến việc xây dựng mã cyclic được thực hiện dựa

trên phân hoạch vành đa thức, trong đó các phần tử sinh của nhóm nhân sinh được

coi là hạt nhân của phân hoạch. Trong số các kiểu phân hoạch thì phân hoạch cực

đại (tức là dựa trên phần tử sinh/nhóm nhân sinh có cấp cực đại) có vai trò quan

trọng nhất và có nhiều ứng dụng mã sửa lỗi, mật mã [6], [9], [13]. Như vậy, có thể

thấy rằng việc tìm phần tử sinh của nhóm nhân sinh có cấp cực đại hay nói cách

khác là tìm đa thức có cấp cực đại (phần tử sinh của nhóm nhân cyclic cấp cực đại)

trên vành đa thức có nhiều ý nghĩa trong mã sửa lỗi, mật mã. Tuy nhiên, đến thời

điểm hiện tại, chưa có công trình nào tập trung nghiên cứu và có kết quả đầy đủ về

cấp của đa thức, về kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức.

Đặc biệt cũng chưa có tiêu chuẩn toán học nào cho việc tìm kiếm đa thức có cấp

cực đại trên vành. Chính điều này gợi mở cho nghiên cứu sinh hướng nghiên cứu

về xác định cấp của đa thức, từ đó kiến thiết nhóm nhân cyclic có cấp cực đại trên

vành đa thức. Các kết quả nghiên cứu sẽ được trình bày chi tiết trong mục 2.2.

Cũng trên cơ sở nghiên cứu về mã cyclic cục bộ (xây dựng từ nhóm nhân

cyclic, cấp số nhân cyclic trên vành đa thức), nghiên cứu sinh thấy rằng có thể tồn

tại mối quan hệ giữa mã cyclic cục bộ (hay nhóm nhân cyclic, cấp số nhân cyclic)

với mã cyclic truyền thống và việc chứng minh bằng toán học, khảo sát đánh giá

mối quan hệ này hiện nay vẫn là một vấn đề mở cần được nghiên cứu. Việc chứng

minh được mối quan hệ này sẽ góp phần làm sáng tỏ mối liên hệ và tạo ra cầu nối

giữa các cách xây dựng mã cyclic khác nhau. Một kết quả nghiên cứu về vấn đề này

được trình bày trong mục 2.3.

Khi giải quyết được hai nội dung lý thuyết quan trọng như đề cập sẽ góp thêm

sở cứ cho việc đề xuất mộ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ộ.

2.2. XÁC ĐỊNH CẤP CỦA ĐA THỨC

Việc xác định được cấp của đa thức, đặc biệt cấp cực đại của đa thức có ý

nghĩa quan trọng trong lý thuyết mã hóa. Nếu đa thức là phần tử sinh của nhóm

nhân cyclic thì cấp đa thức chính là cấp của nhóm nhân, khi đa thức được sử dụng

làm khóa trong các hệ mật thì ở góc độ nào đó cấp đa thức giúp xác định một phần

độ phức tạp của hệ mật. Ngoài ra, xác định được cấp đa thức giúp chỉ ra bộ mã

cyclic tối ưu, hoặc hạ bậc của đa thức để tạo ra bộ mã cyclic tối ưu xây dựng trên

vành nhỏ hơn (chi tiết về ứng dụng này được trình bày trong chương 3). Như vậy,

trong nội dung nghiên cứu này luận án sẽ đề xuất một số phương pháp và thuật toán

xác định cấp của đa thức trên vành, đồng thời cũng đề xuất đánh giá về xác suất

chọn đa thức có cấp cực đại trên vành đa thức có hai lớp kề cyclic.

2.2.1. Đề xuất phương pháp xác định cấp của tích các đa thức

Hiện tại vẫn chưa có phương pháp chung để xác định cấp của đa thức trên

vành, do đó trong nội dung này luận án tập trung trình bày một hướng nghiên cứu

xác định cấp của đa thức thông qua việc tìm cấp của đa thức là tích của các đa thức

thông qua việc đề xuất và chứng minh đầy đủ hai bổ đề liên quan.

Bổ đề 2.1: Xét đa thức ; trong đó là các đa thức có cấp

tương ứng là . Khi đó, cấp của thỏa mãn công thức sau [J5]:

, với là bội số chung nhỏ nhất (2.1)

Chứng minh:

Đặt , ( - bội số chung nhỏ nhất).

Ta có , do đó:

Theo tính chất về cấp của đa thức, ta có: .

Bổ đề 2.2: Xét . Cấp của đa thức

xác định như sau [J5]:

1) Trường hợp 1: Xét hai đa thức và (hoặc

), cấp thì

(2.2)

2) Trường hợp 2: Nếu và , với và

không đối xứng nhau, cấp tương ứng của , là , thì

(2.3)

Đặc biệt nếu , thì

(2.4)

Chứng minh:

1) Xét hai trường hợp:

+ Trường hợp 1: và

Ta có:

Áp dụng bổ đề 1.4 [C5], suy ra:

+ Trường hợp 2: và

Ta có:

Áp dụng bổ đề 1.2 [J5], có:

- Nếu chẵn thì , ta có:

- Nếu lẻ thì , áp dụng bổ đề

1.3 ta có:

. Như vậy, trong cả hai trường hợp thì

2) Xét hai đa thức thuộc hai nhóm nhân cyclic độc lập và không đối xứng

Giả sử hay

hay

Trong đó: , là các lũy đẳng.

Gọi là lũy đẳng của CMG với đa thức sinh .

Ta có: , với và .

Xảy ra các trường hợp như sau:

+ Khi và , có

+ Khi và , có:

+ Khi và , có: . Khi đó:

 Nếu cả đều có trọng số lẻ thì lũy đẳng

và ta có:

 Nếu ít nhất 1 trong 2 đa thức có trọng số chẵn thì lũy đẳng của nó

tương ứng là . Ta có:

 Nếu ít nhất 1 trong 2 đa thức có trọng số chẵn thì lũy đẳng nguyên

thủy của nó tương ứng là . Khi đó:

Như vậy, ta có:

Trường hợp thì .

Bổ đề đã được chứng minh.

Hệ quả:

- Cấp của đa thức là tích hai đa thức bất kỳ thuộc cùng CMG hoặc hai CMG

đối xứng không lớn hơn cấp cực đại của CMG đó.

- Có thể tìm đa thức cấp cực đại bằng việc lấy tích của các đa thức có cấp là

nguyên tố cùng nhau.

Ví dụ 2.1: Trên vành đa thức , xét 2 nhóm nhân:

Các đa thức , , đều có

cấp là 15.

Ta có: và là

hai đa thức có cấp bằng nhau và bằng 3.

Trong khi đó, nếu áp dụng bổ đề 1.4, cấp của hai đa thức này được tính theo

công thức: (với 1 và 4 là các số mũ hay vị trí tương ứng trong

nhóm nhân cyclic của các đa thức hạng tích).

Ví dụ 2.2: Trên vành đa thức , xét 2 nhóm nhân:

, ; và ,

Ta có: là đa thức có cấp bằng 63

(theo kết quả thuật toán 2.2). Kết quả này thỏa mãn bổ đề 2.2.

Từ đây, có thể khẳng định rằng dễ dàng xây dựng đa thức đạt cấp cực đại từ

các đa thức có cấp nhỏ hơn và nguyên tố cùng nhau, từ đa thức kết quả có thể xây

dựng được nhóm nhân cyclic tương ứng trên vành đa thức. Vì vậy, bổ đề 2.2 góp

phần khẳng định và mở ra một hướng kiết thiết mới trong việc xây dựng các nhóm

nhân đạt cấp cực đại trên vành đa thức. Kết quả này được công bố trong [J5].

Việc xác định phần tử có cấp cực đại còn là cơ sở để tạo các CMG hoặc CGP

có cấp cực đại. Các CMG và CGP có cấp cực đại được sử dụng trong một số ứng

dụng khác nhau như: tạo dãy giả ngẫu nhiên [1], tạo các khóa cho một số hệ mật

khóa đối xứng [9].

2.2.2. Đề xuất phương pháp xác định cấp của nhị thức

Nhị thức là một đa thức có biểu diễn khá đơn giản và có khả năng đạt cực đại

trên vành đa thức. Việc nghiên cứu cấp của nhị thức có thể tìm ra nhị thức đạt cấp

cực đại hoặc làm cơ sở tìm đa thức có cấp phù hợp để nhân với nhị thức tạo thành

đa thức có cấp cực đại. Trong phần này, luận án trình bày kết quả nghiên cứu về

cấp của nhị thức thông qua đề xuất và chứng minh hoàn chỉnh một định lý, một bổ

đề, đồng thời đề xuất một thuật toán xác định cấp nhị thức.

Định lý 2.1: Cấp của nhị thức trên được xác định [J3]:

(2.5)

Chứng minh:

Xét chu trình

Với , ta có: . Rõ ràng .

Xét nhóm nhân cyclic sinh bởi , nhóm này chứa tất cả các nhị thức

với . Như vậy mọi phần tử đều có cùng cấp và chúng có cấp là ước của

với là số nguyên dương nhỏ nhất thỏa mãn .

Bổ đề 2.3: Trên vành đa thức [J5].

+ Các nhị thức với là các nhị thức có cấp lớn nhất.

+ Nhị thức là phần tử có cấp cực đại trong số tất cả các nhị thức.

Chứng minh:

1) Xác định nhị thức đạt cấp lớn nhất

Xét chu trình

. Với ,

, với . Với ,

, đi đến kết luận . Ta có:

Mở rộng hơn, đặt (với và ).

Ta có , cho nên

Do , vì vậy , mà nên

suy ra .

Như vậy có thể đi đến kết luận: , với . Nói cách khác, là chu

trình có lực lượng lớn nhất.

2) Xác định cấp nhị thức .

Ta có phân tích , với , trong đó

và .

Như vậy, nhị thức trong phân tích trên luôn là một phần tử của CMG

với phần tử sinh là nhị thức . Áp dụng bổ đề 1.4, có thể xác định cấp của nhị

thức như sau: . Rõ ràng , với (cấp

của CMG có phần tử sinh ).

Xét trường hợp , với , và . Áp

dụng bổ đề 2.2, có: và , trong đó

. Như vậy, .

Có thể đi đến kết luận: nhị thức là phần tử có cấp cực đại trong số tất

cả các nhị thức trên vành đa thức.

Bổ đề đã được chứng minh.

Ví dụ 2.3: Xét vành đa thức .

+ Với : và .

Các nhị thức: , có cấp bằng 3.

+ Với : và .

Nhị thức cấp bằng 1: .

Nhị thức cấp bằng 3: , .

Nhị thức cấp bằng 7: , , .

Nhị thức cấp bằng 9: , , , , ,

Nhị thức cấp bằng 21: , , , , ,

Việc xác định các phần tử có cấp cực đại trên vành đa thức là một vấn đề quan

trọng khi xây dựng nhóm nhân cyclic. Bổ đề 2.3 đã đề xuất và chứng minh tường

minh về cấp của nhị thức trên vành, tiếp theo nghiên cứu sinh sẽ trình bày thuật toán

xác định cấp của nhị thức trên một số vành đa thức được xây dựng để kiểm

nghiệm lại kết quả bổ đề đã được chứng minh về lý thuyết như trình bày ở trên.

Thuật toán xác định cấp của nhị thức (Thuật toán 2.1) [J3]

VÀO: Giá trị n

RA: Cấp của nhị thức trên vành đa thức ( )

1. Chuyển nhị thức về mảng có kích thước bằng giá trị của vành.

2. Đặt và

3. Lấy

4. So sánh với :

4.1. Nếu thì và lặp lại bước 2

4.2. Nếu , dừng chương trình và in kết quả

Thực hiện thuật toán xác định cấp của nhị thức , thu được kết quả khảo

sát trên một số vành đa thức như trong Bảng 2.1.

Bảng 2.1. Bảng khảo sát cấp của đa thức trên một số vành đa thức [J3]

Cấp tương ứng của Cấp cực đại của đa Giá trị Ghi chú nhị thức thức trên vành trên vành

3 Đạt cực đại 3 3

15 Đạt cực đại 15 5

7 Đạt cực đại 7 7

63 Đạt cực đại 63 9

1023 Không đạt cực đại 341 11

4095 Không đạt cực đại 819 13

15 Đạt cực đại 15 15

255 Đạt cực đại 255 17

262143 Không đạt cực đại 9709 19

63 Đạt cực đại 63 21

2047 Đạt cực đại 2047 23

1048575 Không đạt cực đại 25575 25

262143 Không đạt cực đại 13797 27

Cấp tương ứng của Cấp cực đại của đa Giá trị Ghi chú nhị thức thức trên vành trên vành

3 Đạt cực đại 3 3

15 Đạt cực đại 15 5

7 Đạt cực đại 7 7

63 Đạt cực đại 63 9

341 Không đạt cực đại 1023 11

819 Không đạt cực đại 4095 13

15 Đạt cực đại 15 15

255 Đạt cực đại 255 17

9709 262143 Không đạt cực đại 19

63 63 Đạt cực đại 21

475107 268435455 Không đạt cực đại 29

31 Đạt cực đại 31 31

1023 Đạt cực đại 1023 33

4095 Đạt cực đại 4095 35

3233097 68719476735 Không đạt cực đại 37

4095 Đạt cực đại 4095 39

41943 1048575 Không đạt cực đại 41

5461 16383 Không đạt cực đại 43

4095 4095 Đạt cực đại 45

Từ kết quả khảo sát này, ta có thể nhận thấy rằng nhị thức có khả năng đạt cấp

cực đại trên khá nhiều vành, do đó có thể lựa chọn làm phần tử sinh để tạo ra nhóm nhân

đạt cấp cực đại trên những vành mà nhị thức này đạt cấp cực đại. Ngoài ra, ta có một

phương pháp để tìm đa thức có cấp cực đại từ nhị thức , bằng cách chọn

đa thức (với điều kiện ).

Ví dụ 2.4: Xét vành đa thức .

.

+ Với , có

Xét đa thức có cấp bằng 3 là . Áp dụng bổ đề 2.2,

ta có . Tích của hai đa thức đã cho là

đa thức cũng có cấp bằng 1023.

.

+ Với , có

Xét đa thức có cấp bằng 5 . Áp dụng bổ đề 2.2, ta có

. So sánh với kết quả thu được từ thuật

toán 2.3 (thuật toán cải tiến), tích của hai đa thức đã cho là đa thức

có cấp bằng 4095.

Vậy với các trường hợp như khảo sát ở trên thì nhị thức

không đạt cấp cực đại.

Khảo sát với các giá trị lớn hơn mà cấp của nhị thức không đạt giá

trị cực đại của vành, So sánh với kết quả thu được từ thuật toán tìm cấp của các đa

thức trên vành, nhận thấy đa thức là tích của nhị thức với các đa thức có cấp nguyên

tố với nhị thức có thể đạt cấp cực đại trong vành.

Theo bổ đề 2.2 và bổ đề 2.3, cùng với kết quả khảo sát cấp của nhị thức

trong Bảng 2.1, suy ra có thể tìm đa thức đạt cấp cực đại trên một số vành đa thức

mà nhị thức không đạt cấp cực đại bằng cách lấy nhị thức

nhân với các đa thức có cấp nguyên tố với cấp của nó (lưu ý là đa thức được nhân

không thuộc cùng một nhóm nhân cyclic hoặc nhóm nhân cyclic đối xứng với nhị

thức ).

Kết quả nghiên cứu này góp phần khẳng định rằng việc xác định đa thức đạt

cấp cực đại trở nên khá dễ dàng, do đó bài toán quan trọng trong việc xây dựng các

CMG có cấp cực đại đã có một hướng giải quyết mới và hiệu quả. Kết quả này được

công bố trong [J3], [J5].

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

Như đã trình bày, việc tìm cấp của tất cả các đa thức trên vành là một vấn đề

quan trọng trong tính toán và xác định các đa thức đạt cấp cực đại trên vành là cơ

sở cho việc kiến thiết các nhóm nhân cyclic và các mã cyclic tương ứng. Hai phương

pháp được trình bày ở trên đã góp phần hoàn thiện lý thuyết và mở ra hướng tiếp

cận mới. Trong phần này nghiên cứu sinh tiếp tục trình bày một phương pháp thực

nghiệm đó là đề xuất thuật toán tìm và liệt kê cấp của đa thức trên vành.

Có đa thức trên một vành (nếu không tính lũy đẳng nuốt, một vành có

đa thức), việc tìm và liệt kê cấp của tất cả các đa thức trên mỗi vành thường

được thực hiện theo phương pháp vét cạn (vừa phức tạp và mất nhiều thời gian). Để

minh chứng nhận định này, phần tiếp theo nghiên cứu sinh sẽ trình bày thuật toán

vét cạn và một thuật toán cải tiến do nghiên cứu sinh đề xuất. Từ kết quả thu được

sẽ tiến hành so sánh, đánh giá về các thuật toán này. Chú ý, trong đó các thuật toán

thì mỗi đa thức được biểu diễn bằng một số nguyên, các hệ số của đa thức là biểu

diễn của số nguyên đó trong hệ nhị phân, ví dụ .

2.2.3.1. Thuật toán vét cạn (Thuật toán 2.2)

a) Ý tưởng: Thử lần lượt tất cả các đa thức có trên vành đa thức và kiểm tra

cấp của từng đa thức.

b) Độ phức tạp thuật toán: , với O(n) là chi phí kiểm tra

mỗi đa thức có n hệ số.

c) Thuật toán 2.2:

Thuật toán vét cạn (Thuật toán 2.2) [25]

INPUT: integer n.

OUTPUT: order of all polynomials.

For k from 1 to ( ) do:

1. Convert k to polynomial

2. Set

3. Set

4. While(1) do:

4.1. Set

4.2.

then and break the loop 4.3. If

End while

End for

Chạy chương trình phần mềm ứng với thuật toán này cho thấy hạn chế về mặt

thời gian và khả năng tính toán đối với các vành lớn.

2.2.3.2. Thuật toán cải tiến (Thuật toán 2.3)

Do thuật toán 2.2 sử dụng phương pháp vét cạn để xác định cấp của tất cả các

phần tử trên mỗi vành đa thức nên độ phức tạp thuật toán là khá cao, đặc biệt là đòi

hỏi thời gian tính toán lớn và kém hiệu quả đối với các vành lớn. Trên cơ sở các

tính chất của nhóm nhân cyclic, đa thức và cấp của đa thức đã trình bày trong

chương 1, phần dưới đây sẽ áp dụng kết hợp một số bổ đề liên quan để xây dựng

một thuật toán cải tiến với mong muốn làm giảm độ phức tạp thuật toán, giảm thời

gian tính toán trong việc tìm cấp của các đa thức trong vành.

a) Ý tưởng chủ đạo của thuật toán là sử dụng các kết quả nghiên cứu về cấp

đa thức và CMG đối xứng đã được trình bày trong chương 1, trong đó dựa trên ba

vấn đề cụ thể sau:

(1) Tìm cấp cực đại của đa thức trên vành bằng việc kiểm tra chiều dài cực

đại của các lớp kề cyclic (hay chính là các chu trình). Độ phức tạp O(n).

(2) Áp dụng bổ đề 1.4. Tìm các CMG, các đa thức ở vị trí thứ với cấp

, trong đó là cấp của đa thức sinh của CMG.

(3) Áp dụng bổ đề 1.3 để tìm các CMG đối xứng.

b) Độ phức tạp thuật toán: , N là số nhóm nhân cyclic

đạt cấp cực đại độc lập (theo bổ đề 1.5 [C5]).

c) Thuật toán 2.3:

Thuật toán cải tiến do nghiên cứu sinh đề xuất (Thuật toán 2.3) [C5]

INPUT: integer n.

OUTPUT: order of all polynomials.

1. Set all

2. For k from 1 to ( ) do

2.1. If then continue

2.2. Convert k to polynomial

2.3. Set

2.4. Set

2.5. While(1) do

2.5.1. Set

2.5.2. Convert inversely to an integer M

2.5.3.

2.5.3. If then break the loop

End while

2.6. For i from 1 to count

2.6.1.

2.6.2.

2.6.3. , and

2.6.4. and

End for

2.2.3.3. Đánh giá các thuật toán

Sử dụng cấu hình máy tính CPU Core i5 3230M, 2.6 Ghz, RAM 12 Gb, thời

gian tính toán cho mỗi thuật toán với ( lẻ) được liệt kê trong Bảng 2.2.

Bảng 2.2. So sánh thời gian tính toán của hai thuật toán

Nội dung Số lượng đa thức Cấp cực đại Thuật toán vét cạn (s) Thuật toán cải tiến (s) N

5 31 15 0.686 0.78

7 127 7 0.671 0.79

9 511 63 0.718 0.81

11 2047 1023 6.349 0.83

13 8191 4095 77.439 0.89

15 32767 15 3.182 1.03

17 131071 255 170.446 1.4

19 524287 262143 x 2.2

21 2097151 63 x 12

23 838807 2047 x 28

25 27 33554431 1048575 262143 134217726 x x 152 716

Trong đó “x” thể hiện thời gian tính toán lớn hơn 48 giờ hoặc tràn bộ nhớ.

10000000

Thuật toán vét cạn

1000000

Thuật toán cải tiến

100000

i

10000

1000

100

) s ( n ệ h c ự h t n a i g i

ờ h T

N

Hình 2.1. Biểu đồ so sánh thời gian tính toán của hai thuật toán

Từ kết quả tổng hợp ở Bảng 2.2 và Hình 2.1, có thể khẳng định thuật toán cải

tiến do nghiên cứu sinh đề xuất đã rút ngắn thời gian tính toán một cách đáng kể so

với thuật toán vét cạn, đặc biệt khi vành lớn hơn, thuật toán cải tiến có thời gian tính

toán ngắn hơn đến hàng nghìn lần và thực hiện được với những vành lớn mà thuật

toán vét cạn không thể thực hiện trong cùng một cấu hình máy tính.

Việc xác định cấp của đa thức trên vành có vai trò quan trọng trong việc xác

định cấp của CMG – một thành phần quan trọng để kiến trúc mã LCC [6]. Có một

số nghiên cứu và kết quả tính toán về vấn đề này, tuy nhiên các tác giả chủ yếu sử

dụng thuật toán vét cạn với các hạn chế về năng lực, thời gian tính toán và dung

lượng bộ nhớ [19], [25]. Luận án đã đề xuất thuật toán cải tiến giúp giảm độ phức

tạp và thời gian tính toán trong khi độ chính xác là tương đương với thuật toán vét

cạn, đặc biệt thuật toán có thể thực hiện trên các vành lớn mà thuật toán vét cạn

không thể thực hiện trong cùng một điều kiện về cấu hình máy tính. Một số kết quả

của việc xác định phân bố đa thức theo cấp trên vành được đưa ra trong Phụ lục 1.

Từ kết quả trong Phụ lục 1, có thể thấy rằng số đa thức đạt cấp cực đại chiếm

một tỉ lệ lớn trong tổng số đa thức trên vành, do đó thuận lợi cho việc tìm chọn phần

tử đạt cấp cực đại để kiến thiết các mã cyclic. Danh sách đa thức phân bố theo cấp

trong các vành (với ) đã được tính toán đến giá trị ,

danh sách này sẽ giúp ích cho việc kiểm tra, đánh giá các kết quả nghiên cứu, khảo

sát. Kết quả nghiên cứu này được công bố trong [C5].

2.2.4. Xác suất chọn đa thức có cấp cực đại

Vành đa thức có hai lớp kề cyclic là một kiểu vành đa thức đặc biệt trong lý

thuyết mã. Các nhóm nhân có cấp cực đại trong các vành đa thức này là cơ sở để

xây dựng các mã cylic cục bộ có ứng dụng hiệu quả trong viễn thông và trong lĩnh

vực bảo mật [20]. Trong phần này, nghiên cứu sinh tập trung tìm hiểu khả năng xây

dựng các CMG có cấp cực đại trên các vành đa thức có hai lớp kề cyclic.

Áp dụng Định nghĩa 1.6, Định nghĩa 1.16 và Định lý 1.2 có thể xác định cấp

cực đại của đa thức trên vành đa thức có hai lớp kề cyclic như sau:

(2.6)

Ví dụ 2.5: Xét vành đa thức có hai lớp kề cyclic , từ kết quả phụ

lục 1 vành này có 2046 đa thức phân bổ các đa thức theo cấp như sau:

Cấp của đa thức Số lượng đa thức theo cấp

2 1

4 3

20 11

60 31

40 33

120 93

600 341

1200 1023

Với , nhóm nhân có cấp cực đại .

Để xây dựng được các CMG ta phải tìm được các phần tử sinh (hay phần tử

nguyên thủy). Có thể đánh giá khả năng tìm phần tử sinh đạt cấp cực đại thông qua

tính xác suất chọn theo công thức sau:

Số phần tử đạt cấp cực

đại (2.7)

Số phần tử được lựa chọn

trong đó, là số phần tử trong nhóm nhân cyclic đơn vị

: tổng số phần tử trừ số phần tử là đơn thức và lũy đẳng nuốt.

là hàm Phi-Euler có ý nghĩa và cách tính như đã được đề cập tại

bổ đề 2.2.

Bảng 2.3 chỉ ra kết quả khảo sát và đánh giá xác suất tìm cấp cực đại của phần

tử trên vành đa thức có hai lớp kề cyclic của 35 giá trị đầu tiên của .

Bảng 2.3. Kết quả khảo sát 35 giá trị

TT

n

p(n)

n

p(n)

179

~0,5

~0,663

181

~0,586

~0,315

197

~0,42

~0,492

211

~0,534

~0,377

227

~0,494

~0,664

269

~0,378

~0,531

293

~0,529

~0,530

317

~0,65

~0,532

347

~0,35

~0,665

349

~0,53

~0,445

389

~0,658

~0,531

101

419

~0,45

~0,629

107

421

~0,66

~0,318

131

443

~0,575

~0,665

139

461

~0,559

~0,444

163

467

~0,530

~0,665

173

491

~0,529

~0,557

173

491

~0,529

~0,557

Từ bảng này, có thể nhận thấy xác suất thấp nhất là 0,31 và phần lớn xác suất

là trên 0,5 nên khả năng chọn ra phần tử nguyên thủy (không phải đơn thức) thông

thường đạt trên 50%.

Chúng ta luôn mong muốn tìm ra được tiêu chuẩn lựa chọn phần tử sinh (phần

tử nguyên thủy), nhưng trong khi chưa có được tiêu chuẩn lựa chọn phần tử sinh thì

việc đánh giá xác suất lựa chọn phần tử sinh như kết quả ở trên khẳng định rằng khả

năng lựa chọn phần tử nguyên thủy thông thường đạt trên 50%. Kết quả nghiên cứu

này được công bố trong [J2].

Từ phân tích, các số nguyên tố n thỏa mãn vành đa thức có hai lớp kề cyclic

có thể được sử dụng để xây dựng các nhóm nhân cyclic đạt cấp cực đại cho việc tạo

ra các chuỗi giả ngẫu nhiên.

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

Một số nghiên cứu trước đây đã dự đoán hoặc cho ví dụ trong một số trường

hợp riêng về một quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic

truyền thống [6], [13], tuy nhiên cho đến hiện tại vẫn chưa có công trình nghiên cứu

nào đưa ra chứng minh toán học chặt chẽ cho trường hợp tổng quát về mối quan hệ

này. Trong nội dung này của luận án, nghiên cứu sinh sẽ đề xuất một cách chứng

minh toán học chặt chẽ cho mối quan hệ này trong trường hợp tổng quát và kết quả

khảo sát thực nghiệm trên công cụ mô phỏng mối 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.

2.3.1. Cơ sở toán học

2.3.1.1. Quan hệ giữa phép nhân và ánh xạ tuyến tính trên

Định nghĩa 2.1: Với mỗi đa thức ký hiệu ánh xạ được

xác định như sau: , thì và được gọi là ánh xạ nhân với [38].

Định lý 2.2: Với mọi thì là ánh xạ tuyến tính với ma trận

được xác định theo đẳng thức sau:

(2.8)

Chứng minh:

Giả sử , ta có:

(2.9)

Như vậy hệ số của trong đa thức tích chính là và theo công

thức tích vô hướng của hai vector thì:

(2.10)

Với

Lập ma trận thì từ (2.10) và phép nhân vector

với ma trận [38], ta có:

(2.11)

Đẳng thức (2.11) có nghĩa hay là ánh xạ tuyến tính.

Mặt khác các phần tử trên dòng thứ của ma trận lần lượt sẽ là các tọa độ

thứ của các vector , đó là và đây chính là

tọa độ của vector và điều này đã chứng minh đẳng thức (2.8). Như vậy, định lý

đã được chứng minh.

Hệ quả: Nếu là ma trận của thì với mọi ta có là ma trận của .

2.3.1.2. Một tính chất của tích vô hướng

Tính chất 2.1: Với mọi và mọi ma

trận vuông cấp , ta có:

(2.12)

Chứng minh:

Ký hiệu là vector cột thứ của ma trận , ta có

Do đó

(2.13)

Tương tự, kí hiệu là vector cột thứ của ma trận và do đó là vector

dòng thứ của ma trận , ta có:

Do đó:

(2.14)

Từ đẳng thức (2.13) và (2.14) suy ra (2.12), tính chất được chứng minh.

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

Trong mục 2.3.1 các kết quả được trình bày cho một trường tổng quát, còn

tại mục này ta quay lại với trường vì khái niệm về mã cyclic cục bộ được

phát biểu trên với lẻ và do đó, cần đến một số tính chất mà vành

này có được. Dễ thấy, trong các phép toán cộng và trừ là như nhau nên

có thể sử dụng thay cho . Nhóm nhân cyclic và mã cyclic cục bộ trên

với lẻ, có tính chất sau:

Tính chất 2.2: Với mọi với lẻ thì là

ước của [25]. Hơn thế nữa, ta có:

(2.15)

Trên cơ sở đó, ta có bổ đề về tính cyclic của mã cyclic cục bộ được tạo từ một

cấp số nhân cyclic (hay lớp kề cyclic) như sau.

Bổ đề 2.4: Mã cyclic cục bộ xây dựng từ một cấp số nhân cyclic cũng là một

mã cyclic truyền thống. Mã cyclic này được xây dựng trên vành đa thức có bậc là

cấp của cấp số nhân cyclic trong phân hoạch của vành đa thức xây dựng cấp số nhân

cyclic [J4].

Chứng minh:

Theo định nghĩa của mã cyclic cục bộ xây dựng từ cấp số nhân cyclic với

nhóm nhân cyclic và đa thức là không gian tuyến tính

con của với sinh bởi vector dòng của ma trận cấp

dưới đây:

(2.16)

Ký hiệu các vector dòng của lần lượt là .

Vậy mỗi từ của mã này là một tổ hợp tuyến tính của vector nói trên. Giả sử

là một từ mã với ( ) nếu kí hiệu , ta có:

(2.17)

Chọn:

(2.18)

Với là ma trận của phép nhân với trong

Xét từ mã , ta có:

Áp dụng (2.12), ta có:

Áp dụng (2.18), ta có:

Áp dụng (2.15), ta có:

(2.19)

Từ (2.17) và (2.19) cho thấy chính là dịch vòng đi một vị trí. Điều này

có nghĩa là mã cyclic cục bộ xây dựng trên chính là mã cyclic và đây là điều cần

chứng minh.

Chứng minh này đưa đến khẳng định rằng mã cyclic cục bộ xây dựng từ cấp

số nhân cyclic là một mã cyclic, từ đây có thể mở ra một phương án mới để xây

dựng các lớp mã cyclic. Với phương án tiếp cận này, việc xây dựng các mã cyclic

(nhất là với các mã cyclic ở trên các vành lớn) trở nên đơn giản hơn, ta chỉ cần khảo

sát các cấp số nhân cyclic trên các vành nhỏ cũng có thể xây dựng được các mã

cyclic ở trên các vành lớn, trong khi đối với các vành lớn (số mũ lớn), việc phân

tích giá trị ra thành các đa thức bất khả quy cũng là một trở ngại cho việc

xây dựng mã cyclic.

2.3.3. Thuật toán xác định nhóm nhân cyclic tương đương mã cyclic

truyền thống

Một số nghiên cứu bước đầu về mã cyclic cục bộ đã chỉ ra rằng giữa nhóm

nhân cyclic và mã cyclic truyền thống có mối quan hệ với nhau [6]. Từ kết quả bổ

đề 2.4, khi thì cấp số nhân cyclic tương đương nhóm nhân cyclic, do đó có

thể nhận định rằng mã LCC xây dựng trên nhóm nhân cyclic cũng tương đương với

mã cyclic truyền thống. Phần này sẽ trình bày kết quả khảo sát và đánh giá về sự

tương đương giữa mã LCC xây dựng trên nhóm nhân cyclic và mã cyclic truyền

thống.

Do vành đa thức có cấu trúc đối xứng, một nửa vành gồm các phần tử có trọng

số lẻ, một nửa vành có trọng số chẵn nên khi phân hoạch chỉ cần tìm các phần tử có

trọng số lẻ và suy ra các phần tử có trọng số chẵn với cấu trúc tương tự.

Để xây dựng được tất cả các nhóm nhân của vành, ta thực hiện các bước như

trình bày trong mục 1.4.3.1.

Đối với mã cyclic, 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ị lớn là rất phức tạp và khó khăn, bằng việc chứng minh

được sự tương đương giữa các mã cyclic cục bộ được xây dựng trên các vành có

giá trị nhỏ tương đương với các mã cyclic truyền thống được xây dựng trên các

vành có giá trị lớn là một kết quả quan trọng giúp cho việc khảo sát và tìm kiếm

các bộ mã cyclic tối ưu được dễ dàng hơn.

Để chứng minh cho sự tương đương này, ta xét một số ví dụ.

Ví dụ 2.6:

Trong vành , đa thức được phân tích dưới dạng tích của ba

đa thức bất khả quy: .

Xét trên vành , xây dựng nhóm nhân:

Lập ma trận mã từ các phần tử của nhóm nhân , ta được ma trận mã:

(2.20)

Sử dụng phương pháp Gauss-Jordan biến đổi ma trận mã trên về ma trận hệ

thống [38], [40], ta được ma trận:

(2.21)

Loại bỏ các hàng bằng 0 của ma trận ta được ma trận hệ thống tương đương:

(2.22)

Dễ dàng nhận thấy là nhóm nhân được xây dựng trên phân hoạch vành đa

thức theo modulo hay trên

vành .

Theo tính chất của mã cyclic cục bộ được xây dựng theo modulo , ta luôn

tìm được mã cyclic truyền thống với đa thức sinh tương đương với

mã cyclic cục bộ xây dựng theo modulo .

Ta có:

(2.23)

Trên vành , xét mã cyclic truyền thống được xây dựng theo đa thức sinh

Theo định nghĩa ma trận sinh của mã cyclic truyền thống được thiết lập:

(2.24)

Sử dụng phương pháp Gauss-Jordan biến đổi về ma trận hệ thống [38], [40],

ta được:

(2.25)

Từ (2.22) và (2.25) suy ra hay hai phương pháp thực hiện cùng đi đến

kết quả là ma trận mã hệ thống bằng nhau.

Ví dụ 2.7:

Trong vành , đa thức được phân tích dưới dạng tích của ba

. đa thức bất khả quy:

Xét trên vành , xây dựng nhóm nhân:

(2.26)

Tiến hành tương tự, 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 ta được ma trận mã hệ thống:

(2.27)

Biểu thức (2.27) là ma trận mã cyclic cục bộ được xây dựng theo CMG

trên vành .

Có thể nhận thấy là ma trận sinh đối với mã cyclic cục bộ được sinh bởi

CMG xây dựng theo modulo trên

vành .

Xét vành đa thức , phân tích đa thức dưới dạng tích của

các đa thức bất khả quy:

Xét , biến đổi ta có:

(2.28)

Theo định nghĩa ma trận sinh của mã cyclic truyền thống được thiết lập:

(2.29)

(2.30)

Dùng công thức Gauss-Jordan biến đổi về ma trận hệ thống, ta có ma trận

tương đương:

2.31)

Biểu thức (2.31) là ma trận mã cyclic truyền thống xây dựng theo đa thức sinh

trên vành .

Từ (2.27) và (2.31) suy ra , hay mã cyclic cục bộ xây dựng theo nhóm

nhân cyclic trên vành và mã cyclic truyền thống

xây dựng theo đa thức sinh trên vành cùng đi đến kết quả là ma

trận mã hệ thống bằng nhau.

Nhận xét: Qua hai ví dụ trên, có thể nhận thấy rằng hai phương pháp xây dựng

mã khác nhau là xây dựng mã cyclic cục bộ theo nhóm nhân cyclic trên phân hoạch

vành đa thức và xây dựng mã cyclic truyền thống theo đa thức sinh đều dẫn đến một

ma trận mã hệ thống như nhau.

Tiếp tục quá trình khảo sát và đánh giá ta xây dựng được thuật toán 2.4 để xác

định mã cyclic truyền thống tương đương với các nhóm nhân cyclic trên phân hoạch

vành đa thức.

Kết quả khảo sát với các toàn bộ nhóm nhân khác nhau trên các vành đa thức

khác nhau (các giá trị lẻ ) cũng cho kết quả tương tự, có nghĩa là có mã

cyclic cục bộ được xây dựng theo nhóm nhân trên phân hoạch vành đa thức sẽ tương

đương với một mã cyclic truyền thống được xây dựng trên vành là cấp của nhóm

nhân trên vành đa thức đã xét. Kết quả nghiên cứu được công bố trong [C3].

Thuật toán xác định mã cyclic truyền thống tương đương (Thuật toán 2.4)

VÀO:

RA: Mã cyclic truyền thống tương đương với CMG

Bước 1:

- Xây dựng .

- Đặt

- Lập ma trận mã LCC từ các phần tử của CMG .

- 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 (nếu có) của ma trận mã, được ma trận sinh .

Bước 2:

- Chuyển đổi ma trận sinh về dạng các phần tử trong nhóm

- Đặt

- Tính

- Từ đa thức sinh , được ma trận mã tương đương với mã cyclic

truyền thống.

Một số kết quả khảo sát trên các vành đa thức với các giá trị khác nhau được

trình bày trong Phụ lục 3.

2.4. MỘT CÁCH PHÂN LOẠI MÃ TUYẾN TÍNH MỚI

Từ quan điểm xây dựng mã cyclic và LCC, ta thấy có thể thực hiện việc mô

tả mã cyclic theo quan điểm xây dựng các mã LCC dựa trên phân hoạch vành đa

thức [6], [18].

 Theo quan điểm xây dựng mã cyclic: mã cyclic là một Ideal của vành đa

thức; trong đó mỗi từ mã là một phần tử của Ideal đó trên vành đa thức.

 Theo quan điểm xây dựng mã LCC mỗi dấu mã là một phần tử của Ideal;

toàn bộ từ mã là một bộ phận của vành gồm phần tử xác định của Ideal.

Như vậy, có thể dùng lý thuyết xây dựng các đa thức sinh của mã cyclic để

tạo các trưởng lớp kề cho các mã LCC. Với quan điểm đó, lớp kề được xây dựng

theo cách sau đây sẽ tạo nên một mã cyclic [6], [7]:

- Đa thức sinh là ước của .

- Bậc của đa thức sinh bằng .

- Sử dụng dấu thông tin giả khi tạo lớp kề này; tức là cho trước:

Như vậy, có thể nói rằng mã cyclic là một lớp kề đặc biệt của mã LCC.

Hình 2.2. So sánh các mã cyclic và mã cyclic cục bộ

Có thể hình dung mã cyclic như một chuỗi hạt có tốc độ xử lý khác nhau như trong

Hình 2.2. Mã cyclic truyền thống có nhịp dịch của từ mã là , mã cyclic xây dựng từ mã

LCC (hay CMG) có nhịp dịch khác , còn mã LCC chứa các từ mã khác nhau, mỗi từ

mã có thể có nhịp dịch khác nhau.

Theo quan điểm trên thì các mã cyclic xây dựng trên các Ideal là một trường

hợp đặc biệt của mã LCC. Có thể xem xét:

Nhóm nhân cyclic: ; và

Nhóm nhân là một mã cyclic (n,k) có đa thức sinh với:

và là đa thức đối ngẫu của .

Nhận xét:

 Với mã cyclic truyền thống, ma trận sinh của mã được xây dựng từ

phương trình đồng dư sau:

(2.32)

 Với mã cyclic xây dựng từ mã LCC, ma trận sinh của mã được xây

dựng từ phương trình đồng dư sau:

(2.33)

Chú ý: (1.29) là phương trình tạo các hàng của

(1.30) là phương trình tạo các cột của

Một ưu điểm của mã LCC đó là có thể xây dựng được mã trên mọi vành đa

thức ( bất kỳ), với các vành chẵn ta có thể xây dựng mã LCC trên các lớp các phần

tử liên hợp [23], trong khi mã cyclic thì chỉ có thể xây dựng trên các vành lẻ. Có

những vành không thể xây dựng được mã cyclic tốt (ví dụ với các vành có hai lớp

kề cyclic thì khó tìm được mã cyclic tốt), nhưng ngược lại ta có thể tìm được nhiều

mã LCC trên các vành này [1]. Việc xây dựng mã LCC trên phân hoạch vành đa

thức sẽ cho nhiều bộ mã hơn và trên cơ sở đó cũng có nhiều bộ mã tốt hơn với các

độ dài từ mã khác nhau.

Mặc dù đã có một số cách phân loại mã tuyến tính nhưng chỉ dựa vào cấu trúc

đại số mà không đề cập tới mã LCC, vì vậy các kiểu phân loại đã có là chưa toàn

diện. Nghiên cứu các mã cyclic cục bộ trong mối quan hệ với mã cyclic nói riêng

và trong hệ thống mã tuyến tính xây dựng trên các cấu trúc đại số nói chung, với

các dạng phân hoạch khác nhau có thể cho ra các loại mã sửa lỗi khác nhau, hệ

thống phân loại các mã tuyến tính xây dựng trên các cấu trúc đại số được trình bày

trong Hình 2.3.

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 [C4]

Trước hết, về mặt cấu trúc thì mã tuyến tính được chia thành hai loại là có cấu

trúc và không có cấu trúc. Trong đó mã không có cấu trúc là cơ sở xây dựng mã

tuyến tính ngẫu nhiên có khả năng đạt được được giới hạn của Shanon nhưng việc

thực hiện mạch mã hoá và giải mã gặp nhiều khó khăn chính vì tính không có cấu

trúc nên ít được nghiên cứu. Các loại mã tuyến tính có cấu trúc được tập trung

nghiên cứu chủ yếu dựa trên cấu trúc vành số (tiêu biểu như mã cyclic AN [74]),

vành ma trận (tiêu biểu như mã Goppa, mã BCH [74], [77]) và vành đa thức (tiêu

biểu là các loại mã cyclic). Hướng xây dựng mã tuyến tính có cấu trúc dựa trên vành

đa thức lại gồm các loại như: vành chẵn ( chẵn) hướng đến xây dựng

các mã cyclic dựa trên vành các lớp liên hợp (trong số này tiêu biểu là LCC), vành

lẻ ( lẻ) thường tập trung nghiên cứu các mã cyclic truyền thống, đối với vành bất

kỳ (hay bất kỳ) thì một hướng nghiên cứu được đề xuất đó là thực hiện phân hoạch

vành theo nhóm nhân cyclic với một số kết quả được công bố trong [6], [12], [13],

[30].

Trên cơ sở tham khảo và đánh giá kết quả nghiên cứu về mã cyclic cục bộ,

một số mã khối tuyến tính đề cập ở trên và cấu trúc đại số, nghiên cứu sinh đề xuất

sơ đồ thể hiện mối quan hệ như Hình 2.3 với trọng tâm tập trung vào mã cyclic và

cyclic cục bộ. Các nội dung đã nghiên cứu trong hai mục trên bao gồm: phương

pháp kiến thiết nhóm nhân cyclic có cấp cực đại (liên quan trực tiếp đến phân hoạch

cực đại, nội dung được đánh giá là quan trọng nhất trong phân hoạch vành đa thức

theo CMG); 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 (liên quan đến mối quan hệ giữa mã cyclic nhịp đa thức, nhịp và mã

cyclic truyền thống), ngoài ra có thể chỉ ra được những mối quan hệ khác mà chưa

thể hiện trong sơ đồ. Hai kết quả chính đó góp phần hoàn thiện lý thuyết và thực

nghiệm về các nội dung được tô sẫm trong Hình 2.3.

2.5. KẾT LUẬN CHƯƠNG

Chương 2 của luận án đã trình bày các nội dung liên quan đến nhóm nhân và

cấp số nhân cyclic trên vành đa thức. Trên cơ sở đó, Luận án cũng đã trình bày kết

quả nghiên cứu mới đóng góp vào việc bổ sung, hoàn thiện lý thuyết về mã cyclic.

Các kết quả nghiên cứu này được công bố trong các công trình [J2], [J3], [J4], [J5],

[C3], [C5] và tập trung vào hai nội dung chính:

1) Kiến thiết các nhóm nhân cyclic trên vành đa thức thông qua việc đề xuất

phương pháp xác định cấp của đa thức và đa thức đạt cấp cực đại, đồng thời chứng

minh hoàn chỉnh một số bổ đề quan trọng, cụ thể: (a) Đề xuất phương pháp xác

định cấp của đa thức là tích các đa thức trên vành đa thức với đóng góp quan trọng

nhất là đề xuất và chứng minh hoàn chỉnh bổ đề 2.2 cùng các hệ quả của bổ đề góp

phần khẳng định một hướng tiếp cận mới để xây dựng đa thức có cấp cực đại trên

vành đa thức [J5]; (b) Đề xuất phương pháp xác định cấp của nhị thức trên vành đa

thức với đóng góp là đề xuất và chứng minh hoàn chỉnh bổ đề 2.3 cùng với bảng

2.3 khảo sát cấp của dẫn tới một hướng xây dựng đa thức có cấp cực đại trên

vành đa thức bằng việc chọn nhị thức hoặc đa thức là tích của đa thức có

cấp nguyên tố với cấp của nhị thức [J3], [J5]; (c) Đề 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 đa thức, thuật toán 2.3 được đề xuất giúp

giảm độ phức tạp và thời gian tính toán, cũng như giúp thu được các kết quả về cấp

của đa thức trên các vành lớn [C5]; (d) Đánh giá xác suấ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 cho thấy xác suất lựa chọn phần tử sinh

là khá cao (hầu hết là trên 50%) [J2].

2) Chứng minh sự tương đương giữa các nhóm nhân cyclic, cấp số nhân cyclic

với mã cyclic truyền thống, với việc trình bày một chứng minh về lý thuyết (bổ đề

2.4), xây dựng thuật toán (thuật toán 2.4), sau đó tiến hành khảo sát, đánh giá và

xây dựng được một phụ lục minh chứng cho tính tương đương này [J4], [C3]. Kết

quả này góp phần mở ra một hướng tiếp cận mới là xây dựng mã cyclic truyền thống

từ các nhóm nhân, cấp số nhân cyclic trên vành đa thức có bậc bằng cấp của nhóm

nhân/cấp số nhân cyclic, điều này đặc biệt có ý nghĩa khi các nhóm nhân cyclic trên

các vành nhỏ có thể được dùng để kiến thiết nên mã cyclic truyền thống trên các

vành lớn hơn và bằng cấp của nhóm nhân cyclic.

Ở cuối chương, Luận án đã trình bày và thảo luận một sơ đồ phân loại các mã

tuyến tính dựa trên cấu trúc đại số và mã cyclic cục bộ, góp phần khẳng định mối

quan hệ giữa mã cyclic với mã cyclic cục bộ và đánh giá vai trò của mã cyclic cục

bộ trong hệ thống mã tuyến tính, mã sửa lỗi [C4].

CHƯƠNG 3: ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ

NHÂN CYCLIC

Các kết quả đạt được trong chương 2 về việc kiến thiết nhóm nhân cyclic, mối

quan hệ tương đương của mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân

cyclic với mã cyclic truyền thống là cơ sở để tiếp tục nghiên cứu ứng dụng của nhóm

nhân cyclic, cấp số nhân cyclic trong mã sửa lỗi và mật mã. Một đặc điểm nổi bật

của các bộ mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic là có độ dài

thay đổi được có khả năng ứng dụng trong LTE, mã mạng [62], [64], [73]. Trong

số các nhóm nhân trên một vành đa thức thì nhóm nhân có cấp cực đại có độ ngẫu

nhiên của các phần tử cao nhất do đó có thể sử dụng các phần tử có cấp cao nhất

trong nhóm nhân cấp cực đại trên vành đa thức làm khóa cho một số hệ mật.

Trong chương này, luận án sẽ 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

trình bày đề 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ã, đồng thời đề xuất phương pháp xây dựng bộ mã

trên cấu kiện phần cứng FPGA. 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.

3.1. PHƯƠNG PHÁP XÂY DỰNG MÃ CYCLIC

3.1.1. Phương pháp xây dựng mạch mã hóa

Bước đầu tiên để xây dựng mã LCC là xác định tất cả các nhóm nhân cyclic

có thể có trên một vành đa thức, các nhóm nhân này có cấp khác nhau. Sau đó cần

xác định nhóm nhân sinh (hay lớp kề sinh của vành) để xây dựng các cấp số nhân.

Nó tương ứng với việc xác định đa thức sinh trong mã cyclic cổ điển.

Trên cơ sở đã xác định được các nhóm nhân sinh, ta chọn phần tử đầu tiên

nhân với nhóm nhân sinh (lớp kề sinh) sẽ tạo được cấp số nhân cyclic tương đương

với lớp kề mới, phần tử sinh của lớp kề (trưởng lớp kề) tương ứng số hạng đầu của

cấp số nhân cyclic. Nếu gắn dấu thông tin cho nhóm nhân sinh, ta sẽ tạo được mã

LCC tương ứng với nhóm nhân đó. Có hai cách chọn nhóm nhân sinh:

+ Cách thứ nhất: Chọn nhóm nhân đơn vị I, các dấu thông tin được gắn vào

nhóm nhân đơn vị I để tạo mã. Việc tạo mã LCC dựa trên cách phân hoạch vành

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ị

trong trường hợp này được mô tả trên Hình 3.1.

+ Cách thứ hai: Chọn nhóm nhân sinh là nhóm nhân cyclic bất kỳ.

Hoàn toàn tương tự cách thứ nhất, ta chọn phần tử đầu tiên nhân với

nhóm nhân sinh đó sẽ tạo ra được cấp số nhân cyclic tương ứng với một lớp kề tạo

mã.

Phân hoạch vành đa thức có nhóm nhân sinh là nhóm nhân cyclic bất kỳ để

tạo mã được mô tả trên Hình 3.2.

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ỳ

3.1.2. Phương pháp xây dựng mạch giải mã

Có nhiều phương pháp giải mã cho mã cyclic và LCC, trong số đó phương

pháp giải mã ngưỡng là một phương pháp khá hiệu quả và có sơ đồ giải mã đơn

giản [5], [31], [51]. Các phương pháp giải mã ngưỡng bao gồm:

 Giải mã ngưỡng theo đa số (MTD) các tổng kiểm tra.

 Giải mã ngưỡng theo đa số 1 biểu quyết (MTD + 1), giải mã ngưỡng theo

đa số 2 biểu quyết (MTD + 2).

Các phương pháp giải mã ngưỡng đều sử dụng các OCS, hoặc các OACS,

hoặc CS  liên hệ [4], [7], [11], [16].

a) Hệ tổng kiểm tra trực giao

Xét mã tuyến tính (n, k) trên trường GF(2), gọi H là ma trận kiểm tra của nó,

khi đó với mọi từ mã , ta có:

(3.1)

Trong đó: là ma trận chuyển vị của H.

Khi đó mỗi hàng hj của H là:

với . (3.2)

Sẽ cho một tổng kiểm tra của các dấu mã:

(3.3)

Giả sử sau khi truyền từ mã a qua kênh ta nhận được từ mã

khác với từ mã a đã phát một dãy lỗi: .

Tức là:

với (3.4)

Như vậy nếu xác định được dãy lỗi e ta sẽ xác định được từ mã đã phát đi ở

đầu phát: .

Với một từ mã thu được b bất kỳ ta có:

(3.5)

Tập các Aj sẽ tạo nên tập các CS đối với các dấu lỗi.

Tập các CS được gọi là hệ OCS nếu từ tập giá trị ta lập được giá trị

thỏa mãn:

 Một dấu lỗi nào đó nằm trong tất cả các CS với .

 Một dấu lỗi bất kỳ chỉ nằm ở nhiều nhất trong một CS.

Khi đó ta gọi tập là hệ OCS với dấu . Như vậy trong các OCS

với dấu , thông tin về nằm trong CS, còn thông tin về chỉ nằm nhiều

nhất trong một CS; cho nên với CS sẽ cho ta thông tin khá đầy đủ về để giải mã

cho dấu .

b) Phương pháp giải mã ngưỡng theo đa số

Giả sử ta xét một bộ mã tự trực giao nào đó, với bộ mã này ta có thể xây dựng

được OCS cho một dấu mã nào đó.

(3.6)

Nếu (trong đó là số nguyên nhỏ nhất lớn hơn hoặc bằng x),

thì coi có lỗi ở dấu thứ , ngược lại là dấu thứ thu đúng.

Mỗi CS trong hệ CS này cho phép đưa ra các dấu ở dạng tổ hợp tuyến

tính của các dấu khác mà nó không nằm trong một CS. Vì vậy hệ thống có CS

để giải mã đúng các dấu theo biểu quyết đa số. Do các CS phải

thỏa mãn với bất kỳ từ mã nào thì tính chất tuần hoàn của bộ mã mới có hiệu quả

để giải mã các dấu tiếp theo, nên ta dịch chuyển tuần hoàn từ mã và lại áp dụng biểu

quyết theo đa số. Cứ làm như vậy sẽ thực hiện giải mã cho tất cả các dấu mã.

Như vậy với mã cyclic tự trực giao thì phương pháp giải mã ngưỡng đơn giản

hơn nhiều so với các phương pháp giải mã khác về thiết bị giải mã với bộ mã có

cùng chiều dài. Thiết bị giải mã chỉ gồm bộ ghi, bộ cộng và thiết bị ngưỡng theo đa

số. Chính có ưu điểm này nên việc thực hiện kỹ thuật sẽ đơn giản.

Đối với các mã có khả năng trực giao, ta có thể thiết lập được hệ Tổng kiểm tra

có khả năng trực giao (OACS). Một hệ OACS nếu tồn tại một tổ hợp tuyến tính các

dấu mã thỏa mãn điều kiện sau:

 Tổ hợp tuyến tính các dấu mã có mặt trong mọi CS.

 Các dấu còn lại: chỉ nằm ở nhiều nhất một CS.

Trên cơ sở đó ta có thể coi tập đóng vai trò như một dấu mã trong hệ

OCS. Theo nguyên tắc giải mã theo đa số, ta có thể giải mã cho tập hay có thể

nói đây là hệ OCS với tập (thông thường tập là một cặp dấu mã).

3.2. ĐỀ XUẤT MỘT SỐ MÃ CYCLIC TỐT TRÊN VÀNH ĐA THỨC

3.2.1. Phương pháp tìm mã cyclic tốt

Trong phần này, nghiên cứu sinh sẽ trình bày phương pháp tìm mã cyclic

(n,k,d) tốt phù hợp theo các tiêu chí đánh giá trình bày trong chương 1. Các kết quả

nghiên cứu liên quan đến mã cyclic xây dựng từ nhóm nhân, cấp số nhân cyclic.

3.2.1.1. Mã cyclic tối ưu xây dựng từ nhóm nhân, cấp số nhân cyclic

) làm dấu mã là mã tối ưu đạt giới 𝑥𝑖

Định lý 3.1: Mã cyclic (2𝑘 − 2, 𝑘) trên vành đa thức 𝑍2[𝑥]/(𝑥𝑘 + 1) sử dụng 𝑘−1 tất cả đa thức khác không (trừ 𝑒0(𝑥) = ∑ 𝑖=0 hạn Griesmer và thỏa mãn giới hạn Plotkin, có khoảng cách mã 𝑑0 = 2𝑘−1 − 1 [J6].

Chứng minh:

Dựa vào tính chất của phân hoạch vành đa thức theo nhóm nhân cyclic đơn vị,

ta có 2𝑘−1 đa thức có trọng số lẻ và 2𝑘−1 đa thức có trọng số chẵn. Khi thiết lập

tổng kiểm tra trực giao ứng với một dấu mã bất kỳ, ta cần ít nhất 3 dấu mã [2]:

(3.7) 𝑎𝑖(𝑥) + 𝑎𝑗(𝑥) = 𝑎𝑚(𝑥)

Nếu cố định dấu 𝑎𝑖(𝑥) và cho 𝑎𝑗(𝑥) biến đổi thì phương trình (3.7) luôn tồn

tại nghiệm với ∀𝑗 ≠ 𝑖, có nghĩa là ứng với mỗi 𝑎𝑗(𝑥), ta xác định được 𝑎𝑚(𝑥). Vậy

ta có tổng kiểm tra trực giao với dấu 𝑎𝑖(𝑥) như phương trình (3.8):

(3.8) 𝑎𝑖(𝑥) = 𝑎𝑗(𝑥) + 𝑎𝑚(𝑥)

𝑘−1 𝑖=0

𝑥𝑖

Theo định lý, số dấu của từ mã là 𝑛 = 2𝑘 − 2 (loại bỏ đa thức 𝑒0(𝑥) = ∑ lớp kề có một đa thức), để thiết lập số tổng kiểm tra trực giao giải mã cho một dấu

mã nào đó sẽ đạt tối đa là:

(3.9) ⌋ = ⌊2𝑘−2−1 ⌋ = 2𝑘−1 − 2 𝐽max = ⌊𝑛−1

Theo phương pháp giải mã ngưỡng, khoảng cách mã 𝑑0 được xác định:

(3.10) 𝑑0 = 𝐽max + 1 = 2𝑘−1 − 1

𝑘−1 𝑗=0

Kiểm tra theo giới hạn Griesmer: 𝑛 ≥ ∑ thay 𝑑0 = 2𝑘−1 − 1 , ta được: ⌈𝑑0 2𝑖 ⌉

𝑛 ≥ (2𝑘−1 − 1) + 2𝑘−2 + ⋯ + 1

Áp dụng công thức tính tổng của cấp số nhân, ta được:

𝑛 ≥ 2𝑘 − 2

Theo định lý, số dấu của bộ mã là: 𝑛 = 2𝑘 − 2. Vậy bộ mã (2𝑘 − 2, 𝑘) đạt

được giới hạn Griesmer.

2𝑘−1 2𝑘−1

Kiểm tra giới hạn Plotkin: 𝑑0 ≤ 𝑛.

Thay 𝑛 = 2𝑘 − 2 vào vế phải, kết quả của vế phải bằng:

1 (2𝑘 − 2). = = 2𝑘−1 − 2𝑘−1 2𝑘 − 1 (2𝑘 − 1). 2𝑘−1 − 2𝑘−1 2𝑘 − 1 2 − ( 1 2𝑘−1)

Với 𝑑0 = 2𝑘−1 − 1 nên bộ mã thỏa mãn giới hạn Plotkin.

Định lý 3.2: Mã cyclic (2𝑘−1 − 1, 𝑘) trên vành đa thức 𝑍2[𝑥]/(𝑥𝑘 + 1) với 𝑘

𝑘−1 𝑖=0

) làm dấu mã 𝑥𝑖 lẻ và sử dụng tất cả đa thức trọng số lẻ (trừ đa thức 𝑒0(𝑥) = ∑

là mã tối ưu đạt giới hạn Griesmer và thỏa mãn giới hạn Plotkin, có khoảng cách

𝑑0 = 2𝑘−2 − 1 [J6].

Chứng minh:

Phân hoạch của vành 𝑍2[𝑥]/(𝑥𝑘 + 1) theo nhóm nhân đơn vị {𝑥𝑖} cấp k luôn tồn tại 2𝑘−1 đa thức có trọng số chẵn và 2𝑘−1 đa thức có trọng số lẻ (theo tính chất

của vành đa thức).

𝑘−1 𝑖=0

𝑥𝑖 Trọng số của đa thức 𝑒0(𝑥) = 𝑊(∑ ) = 𝑘. Khi 𝑘 lẻ, đa thức 𝑒0(𝑥) có

trọng số lẻ, thuộc lớp kề trọng số lẻ một phần tử và là một lũy đẳng. Khi 𝑘 chẵn, đa

thức 𝑒0(𝑥) có trọng số chẵn không được chọn làm dấu mã và cũng không tồn tại

lớp kề trọng số lẻ có một phần tử.

Nếu số dấu mã bớt đi một dấu là đa thức 𝑒0(𝑥), thì số dấu mã của bộ mã là

𝑛 = 2𝑘−1 − 1.

Theo phương pháp giải mã ngưỡng để thiết lập được một tổng kiểm tra có khả

năng trực giao cho hai dấu mã nào đó, ta cần ít nhất 4 dấu mã như trong phương

trình (3.11) [3]:

(3.11) 𝑎𝑖(𝑥) + 𝑎𝑗(𝑥) + 𝑎𝑠(𝑥) = 𝑎𝑚(𝑥)

Theo phương trình (3.11), vế phải là một tổng 3 dấu mã của từ mã và mỗi dấu

mã là một đa thức có trọng số lẻ, do đó kết quả vế phải là một đa thức có trọng số

lẻ. Vậy phương trình (3.11) luôn cón nghiệm với ∀𝑖 ≠ 𝑗 ≠ 𝑠 ≠ 𝑚. Nếu ta cố định

một cặp hai dấu 𝑎𝑖(𝑥), 𝑎𝑗(𝑥), thì ứng với mỗi 𝑎𝑠(𝑥) ta luôn xác định được 𝑎𝑚(𝑥).

Phương trình (3.11) có dạng:

(3.12) [𝑎𝑖(𝑥) + 𝑎𝑗(𝑥)] = 𝑎𝑠(𝑥) + 𝑎𝑚(𝑥)

Số dấu còn lại của từ mã bằng (𝑛 − 2). Như vậy số tổng kiểm tra thiết lập

được để giải mã là:

(3.13) ⌋ = ⌊(2𝑘−1−1)−2 ⌋ = 2𝑘−2 − 2 𝐽max = ⌊𝑛−2

Khoảng cách mã Hamming 𝑑0 xác định là:

(3.14) 𝑑0 = 𝐽max + 1 = 2𝑘−2 − 1

𝑘−1 𝑗=0

Kiểm tra theo giới hạn Griesmer: 𝑛 ≥ ∑ thay 𝑑0 = 2𝑘−2 − 1 , ta được: ⌈𝑑0 2𝑖 ⌉

𝑛 ≥ (2𝑘−2 − 1) + 2𝑘−3 + ⋯ + 1 + 1

Áp dụng công thức tính tổng của cấp số nhân, ta được:

(3.15) 𝑛 ≥ 2𝑘−1 − 1

Theo định lý 3.2, số dấu của bộ mã: 𝑛 = 2𝑘−1 − 1. Vậy bộ mã (2𝑘−1 − 1, 𝑘)

đạt được giới hạn Griesmer.

2𝑘−1 2𝑘−1

Kiểm tra giới hạn Plotkin: 𝑑0 ≤ 𝑛.

Thay 𝑛 = 2𝑘−1 − 1 vào vế phải, kết quả của vế phải bằng:

1 (2𝑘−1 − 1). = = 2𝑘−2 − 2𝑘−1 2𝑘 − 1 (2𝑘 − 1). 2𝑘−2 + 2𝑘−2 − 2𝑘−1 2𝑘 − 1 4 − ( 1 2𝑘−2)

Với 𝑑0 = 2𝑘−2 − 1 nên bộ mã thỏa mãn giới hạn Plotkin.

Như vậy, theo định lý 3.1 và 3.2 thì các bộ mã cyclic được xây dựng từ các

nhóm nhân cyclic, cấp số nhân cyclic có dạng (2𝑘 − 2, 𝑘) và (2𝑘−1 − 1, 𝑘) là các

bộ mã tối ưu đặt giới hạn Griesmer và Plotkin.

Đối với mã cyclic xây dựng từ các cấp số nhân cyclic, về cơ bản có thể xây

dựng mã (2𝑘 − 2, 𝑘) bằng việc lấy tất cả các lớp kề của vành đa thức trừ phần tử 0

𝑘−1 𝑖=0

𝑥𝑖 ; có thể xây dựng mã (2𝑘−1 − 1, 𝑘) bằng việc lấy tất cả và phần tử 𝑒0(𝑥) = ∑

𝑘−1 𝑖=0

. 𝑥𝑖 các lớp kề có trọng số lẻ của vành đa thức trừ phần tử 𝑒0(𝑥) = ∑

Đối với mã cyclic xây dựng từ các nhóm nhân cyclic thì có thể xây dựng các

bộ mã này như sau:

+ Nếu cấp cực đại của các đa thức thuộc vành 𝑍2/(𝑥𝑘 + 1) bằng 2𝑘−1 − 1 thì

chọn đa thức có cấp cực đại làm phần tử sinh của bộ mã.

+ Nếu cấp cực đại của các đa thức thuộc vành 𝑍2/(𝑥𝑘 + 1) không nhỏ hơn 2𝑘−1 − 1 thì chọn đa thức thuộc vành lớn hơn (vành 𝑍2/(𝑥𝑝 + 1), với 𝑝 > 𝑘) và có cấp bằng với 2𝑘−1 − 1 sau đó hạ bậc đa thức theo ℎ(𝑥) [13] thì được đa thức mới

có thể chọn làm phần tử sinh của bộ mã.

Việc thực hiện hạ bậc đa thức theo ℎ(𝑥) như vậy là trường hợp thực hiện phân

hoạch hỗn hợp trên hai vành đa thức bất kỳ [13]. Xét 2 vành và với

nếu trên vành ta tìm được đa thức thỏa mãn điều kiện:

là tích của một vài đa thức bất khả quy và thì ta có thể thực hiện được

phân hoạch hỗn hợp trên hai vành này.

Để có thể dễ dàng tìm được đa thức ta nên chọn ít nhất một vành là vành

lẻ. Xét phân tích của một số vành đa thức sau:

Theo các phân tích này ta có thể tìm được các giá trị và đa thức

thỏa mãn điều kiện phân hoạch hỗn hợp như trong Bảng 3.1.

Bảng 3.1. Một số cặp vành có thể phân hoạch hỗn hợp

phù hợp

Các đa thức

thỏa mãn

(

)

(vành

)

6, 9, 15, 21 ; 3 7, 21 ;

5, 15, 25

7 ;

4 15 ;

21 ;

15, 25 ; 5 15 ;

7 ;

;

6 15 ;

; 21 ;

Dựa trên kết quả hai định lý 3.1, 3.2 cùng với phân tích trong Bảng 3.1 có thể

nhận thấy rằng luôn có thể xây dựng được các bộ cyclic mã tối ưu trên các vành đa

thức từ các cấp số nhân (hay lớp kề) cyclic.

Khi xây dựng mã cyclic từ các nhóm nhân với phần tử sinh là đa thức có cấp

cực đại trên vành 𝑍2/(𝑥𝑘 + 1) và thỏa mãn cấp của đa thức là 2𝑘−1 − 1 thì bộ mã cũng đạt giới hạn tối ưu.

Trường hợp cấp cực đại của đa thức trên vành không đạt 2𝑘−1 − 1 thì có thể

hạ bậc của đa thức có cấp bằng 2𝑘−1 − 1 và thuộc vành lớn hơn theo ℎ(𝑥) như Bảng

3.1 thì có thể tìm được bộ mã tối ưu.

Xét vành 𝑍2/(𝑥9 + 1), cấp cực đại của các đa thức bằng 63 (theo phụ lục 1) nên không xây dựng được mã cyclic tối ưu từ các nhóm nhân cyclic với phần tử

sinh là đa thức thuộc vành, tuy nhiên theo Bảng 3.1 ta thấy rằng có thể hạ bậc đa thức có cấp bằng 255 trong vành 𝑍2/(𝑥17 + 1) theo ℎ1(𝑥) hoặc ℎ2(𝑥) để xây dựng mã. Ví dụ chọn đa thức 𝑎(𝑥) = 1 + 𝑥 + 𝑥2 + 𝑥3 + 𝑥8 + 𝑥9 + 𝑥10 + 𝑥11 + 𝑥12 có

cấp là 255 (theo phụ lục 1) là phần tử sinh của nhóm nhân cyclic xây dựng trên vành 𝑍2/(𝑥17 + 1), chọn ℎ1(𝑥) để hạ bậc các phần tử trong nhóm nhân cyclic trên ta được một nhóm nhân có cấp là 255 trên vành vành 𝑍2/(𝑥9 + 1), từ đây xây dựng được bộ mã cyclic (255,9,127) là mã tối ưu đạt giới hạn Griesmer và Plotkin.

3.2.1.2. Mã cyclic tốt xây dựng từ cấp số nhân cyclic trên vành đa thức

Các mã cyclic tối ưu (𝑛, 𝑘, 𝑑) được nghiên cứu và đề xuất ở trên có ưu điểm

là sửa sai tốt (𝑑 lớn), xây dựng bộ mã dễ dàng, tuy nhiên tồn tại một nhược điểm

lớn là hiệu suất mã (𝑘/𝑛) thường khá nhỏ, do đó nghiên cứu sinh cũng tiến hành

nghiên cứu và đề xuất phương pháp tìm mã cyclic tốt xây dựng từ các cấp số nhân/

𝑘

lớp kề cyclic với các giá trị (𝑛, 𝑘, 𝑑) phù hợp, đặc biệt là đề xuất các mã tốt xây

𝑛

dựng từ 3 lớp kề cyclic trên vành (hướng tới mục tiêu đạt hiệu suất mã với >

khả năng sửa lỗi hợp lý).

Để tìm mã cyclic tốt xây dựng trên 3 lớp kề cyclic sử dụng phương pháp giải

mã ngưỡng [2], [3], [5], [7], ta thực hiện theo các bước sau đây:

Bước 1: + Cho giá trị 𝑘 của vành đa thức 𝑍2/(𝑥𝑘 + 1).

+ Lập phân hoạch cho vành đa thức, xác định số lớp kề 𝑚 (số lượng

lớp kề trong vành)

+ Cho 𝑖 = 2

Bước 2: + Gán 𝑗 = 𝑖 + 1

Bước 3: + Lập mã gồm 3 lớp kề {1, 𝑖, 𝑗}

+ Xác định giá trị 𝑛 trong bộ mã (𝑛, 𝑘, 𝑑) , trong đó 𝑛 là tổng số

phần tử của 3 lớp kề được chọn (cũng là độ dài từ mã).

+ Tính tổng kiểm tra của bộ mã theo cả 3 trường hợp CS trực giao,

CS có khả năng trực giao, CS  liên hệ, sau đó lưu lại số CS của bộ mã ứng với mỗi

trường hợp. Từ số tổng kiểm tra sẽ tính được khoảng cách Hamming 𝑑.

+ Nếu 𝑗 = 𝑚 thì chuyển sang bước 4, nếu 𝑗 < 𝑚 thì tăng 𝑗 và lặp

lại bước 3.

Bước 4: + Nếu 𝑖 = 𝑚 − 1 thì chuyển sang bước 5, nếu 𝑖 < 𝑚 − 1 thì tăng

𝑖 và lặp lại bước 2.

Bước 5: Tính toán bộ tham số (𝑛, 𝑘, 𝑑) ứng với các bộ mã, so sánh với các

giới hạn tối ưu. Liệt kê bộ mã (𝑛, 𝑘, 𝑑) tốt nhất thu được.

Từ các bước trên có thể xây dựng được lưu đồ thuật tìm các bộ mã cyclic tốt

theo lưu đồ thuật toán như trên Hình 3.3 và danh sách một số bộ mã cyclic tốt tìm

được như trong Bảng 3.2.

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

Bảng 3.2. Đề xuất một số bộ mã cyclic tốt

Vành CGPs/CMG TTG CKNTG TTGLH

{(1), (7), (11)} (15,5,7) 𝑥5 + 1

{(1), (11), (21)} 𝑥6 + 1

(14,6,5)  = 2, CS = 8

{(1), (13), (21)}

(14,6,5)  = 2, CS = 8

{(1), (23), (29)} (21,7,7) 𝑥7 + 1

{(1), (11), (87)} (24,8,7) 𝑥8 + 1

{(1), (13), (87)} (24,8,7)

{(1), (31), (91)} (24,8,7)

{(1), (47), (61)} (24,8,7)

{(1), (13), (19)}

(24,8,7)  = 2, CS = 12

{(1), (13), (25)}

(24,8,7)  = 2, CS = 12

{(1), (37), (47)}

(24,8,7)  = 2, CS = 12

{(1), (37), (61)}

(24,8,7)  = 2, CS = 12

{(1), (11), (61)} (27,9,9) 𝑥9 + 1

{(1), (13), (47)} (27,9,9)

{(1), (19), (59)} (27,9,9)

{(1), (25), (55)} (27,9,9)

{(1), (41), (87)} (27,9,9)

{(1), (41), (117)} (27,9,9)

Thực hiện tìm mã cyclic tốt với nhiều lớp kề hơn cũng cho những bộ mã tốt,

tuy nhiên lại phải trả giá về hiệu suất mã (tỉ số 𝑘/𝑛 thấp). Hướng nghiên cứu tiếp

theo, nghiên cứu sinh sẽ tiếp tục tìm các bộ mã cyclic tốt với nhiều lớp kề hơn và

các bộ mã cyclic ứng với các phương pháp giải mã khác.

3.2.2. Mô phỏng, đánh giá một số bộ mã cyclic tốt

3.2.2.1. Đề xuất kịch bản mô phỏng, đánh giá

Trong phần này, nghiên cứu sinh đề xuất một sơ đồ truyền thông dùng để mô

phỏng, đánh giá mã cyclic như Hình 3.4, trong đó sử dụng các phương pháp điều

chế/giải điều chế khác nhau và kênh truyền sử dụng nhiễu Gauss trắng cộng, các bộ

Hình 3.4. Sơ đồ hệ thống thông tin sử dụng mô phỏng, đánh giá mã cyclic

mã cyclic cần mô phỏng, đánh giá được đưa vào các khối mã hóa và giải mã hóa.

Phân tích sơ đồ hệ thống

Bên phát gồm:

- Dữ liệu phát: là phần thông tin gốc được truyền đi.

- Mã hóa: là bước sử dụng bộ mã cyclic để mã hóa tín hiệu gốc. Các bộ mã

thay đổi sẽ ảnh hưởng đến dãy bit đưa tới khối điều chế.

- Điều chế: là các phương pháp điều chế, chương trình mô phỏng sẽ sử dụng

các kiểu điều chế khác nhau để hỗ trợ đánh giá bộ mã.

Kênh truyền gồm:

- Nhiễu: được tạo ra trên kênh truyền, trong các mô phỏng ở phần này đều sử

dụng bộ tạo nhiễu Gauss.

Bên thu: Là các bước ngược của bên phát, bao gồm: giải điều chế, giải mã hóa

và khôi phục thông tin từ phía phát. Phần giải điều chế, giải mã hóa được thực hiện

tương ứng với phương pháp điều chế và bộ mã hóa được xây dựng ở phía phát.

Hoạt động của hệ thống

Trong một chu kỳ mô phỏng cần thực hiện:

- Tạo nhiễu Gauss trắng cộng.

- Cố định bộ mã cyclic, phương pháp điều chế.

- Tạo ngẫu nhiên dãy dữ liệu phát.

- Lần lượt tăng tỉ số 𝐸𝑏/𝑁0 ở phía phát theo bước nhảy phù hợp.

- Đo tỉ số lỗi bit 𝐵𝐸𝑅 của chuỗi bit nhận được.

Phương pháp đánh giá:

- Vẽ đồ thị biểu thị mối quan hệ 𝐸𝑏/𝑁0 và 𝐵𝐸𝑅 của bộ mã từ nguồn dữ liệu

mô phỏng thu được.

- Thực hiện đánh giá hiệu của của bộ mã, so sánh bộ mã với các bộ mã khác

(nếu có).

3.2.2.2. Kết quả mô phỏng, đánh giá một số bộ mã cyclic

a) Bộ mã cyclic (255,9,127)

Chọn đa thức 𝑎(𝑥) = 1 + 𝑥 + 𝑥2 + 𝑥3 + 𝑥8 + 𝑥9 + 𝑥10 + 𝑥11 + 𝑥12 có cấp

là 255 (theo phụ lục 1) là phần tử sinh của CMG xây dựng trên vành 𝑍2/(𝑥17 + 1), chọn ℎ1(𝑥) = (1 + 𝑥)(1 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥8) để hạ bậc 𝑎(𝑥) ta xây dựng được CMG tương ứng có cấp 255 trên vành 𝑍2/(𝑥9 + 1), tiến hành xây dựng bộ mã hóa và giải mã ứng với CMG này ta thu được bộ mã cyclic (255,9,127) đạt giới hạn

Griesmer và Plotkin. Kết quả mô phỏng bộ mã cyclic (255,9,127) thể hiện như

Hình 3.5.

Trong mô phỏng ứng với bộ mã này, nghiên cứu sinh sử dụng nhiễu Gauss

trắng cộng trên kênh truyền. Thử nghiệm với các phương pháp điều chế khác nhau

(QPSK, 16QAM,...), cho chất lượng rất tốt. Trên Hình 3.5 biểu thị kết quả mô phỏng

của bộ mã ứng với điều chế 64QAM, 128QAM và so sánh với trường hợp truyền

dẫn chỉ điều chế 64QAM không mã hóa và trường hợp truyền dẫn không điều chế,

𝐸𝑏 𝑁0

không mã hóa. Kết quả cho thấy bộ mã đạt 𝐵𝐸𝑅 ≈ 10−7 với = 5 (trường hợp

𝐸𝑏 𝑁0

Hình 3.5. Kết quả mô phỏng bộ mã cyclic (255,9,127)

điều chế 64QAM), và 𝐵𝐸𝑅 ≈ 10−7 với = 6,5 (trường hợp điều chế 128QAM).

b) Bộ mã cyclic (15,5,7)

Chọn mã cyclic cục bộ xây dựng từ ba lớp kề cyclic {(1), (7), (11)} trên vành

𝑍2/(𝑥5 + 1) sẽ tạo ra bộ mã (15,5) (các phần tử của ma trận sinh của bộ mã này cũng tương đương CMG được tạo bởi phần tử sinh là đa thức trọng số lẻ đạt cấp

cực đại trên vành 𝑍2/(𝑥5 + 1)), tiến hành xây dựng bộ mã hóa và giải mã ta thu được bộ mã cyclic (15,5,7) đạt giới hạn Griesmer và Plotkin. Kết quả mô phỏng bộ

mã cyclic (15,5,7) thể hiện như Hình 3.6.

Tương tự như mô phỏng bộ mã (255,9,127), ta sử dụng nhiễu Gauss trắng

cộng trên kênh truyền. Thử nghiệm với các phương pháp điều chế QPSK, 4QAM,

16QAM cho chất lượng khá tốt. Trên Hình 3.6 biểu thị kết quả mô phỏng của bộ

mã ứng với điều chế QPSK, 16QAM và so sánh với trường hợp truyền dẫn tín hiệu

chỉ điều chế (QPSK, 16QAM) không mã hóa. Kết quả cho thấy với điều chế QPSK

𝐸𝑏 𝑁0

tại = 7, nếu không mã hóa thì kênh truyền đạt 𝐵𝐸𝑅 ≈ 1,2.10−3, nếu sử dụng bộ

mã cyclic (15,5,7) thì kênh truyền đạt 𝐵𝐸𝑅 ≈ 1,5.10−7 (tốt hơn trường hợp không

𝐸𝑏 𝑁0

mã hóa khoảng 8000 lần); với điều chế 16QAM tại = 10, nếu không mã hóa thì

kênh truyền đạt 𝐵𝐸𝑅 ≈ 2,5.10−3, sử dụng bộ mã cyclic (15,5,7) thì kênh truyền đạt

𝐵𝐸𝑅 ≈ 1,5.10−6 (tốt hơn trường hợp không mã hóa hơn 1600 lần). Kết quả mô

phỏng cũng cho thấy đường truyền sử dụng cùng một bộ mã, thì điều chế QPSK

𝐸𝑏 𝑁0

cho 𝐵𝐸𝑅 tốt hơn 16QAM (ví dụ, tại = 7, điều chế QPSK cho 𝐵𝐸𝑅 ≈ 1,5.10−7,

Hình 3.6. Kết quả mô phỏng bộ mã cyclic (15,5,7)

trong khi điều chế 16QAM cho 𝐵𝐸𝑅 ≈ 10−3) là phù hợp với lý thuyết.

c) Bộ mã cyclic (27,9,9)

Chọn mã cyclic cục bộ xây dựng từ ba lớp kề cyclic {(1), (11), (61)} trên vành 𝑍2/(𝑥9 + 1), tiến hành xây dựng bộ mã hóa và giải mã ta thu được bộ mã cyclic (27,9,9). Kết quả mô phỏng bộ mã cyclic (27,9,9) thể hiện như Hình 3.7.

Hình 3.7. Kết quả mô phỏng bộ mã cyclic (27,9,9)

Tương tự, nghiên cứu sinh sử dụng nhiễu Gauss trắng cộng trên kênh truyền.

Thử nghiệm với các phương pháp điều chế QPSK, 4QAM, 16QAM cho chất lượng

khá tốt. Trên Hình 3.7 biểu thị kết quả mô phỏng của bộ mã ứng với điều chế QPSK,

16QAM, so sánh với trường hợp truyền dẫn sử dụng bộ mã cyclic (15,5,7) và trườn

hợp truyền dẫn tín hiệu chỉ điều chế (QPSK, 16QAM) không mã hóa. Kết quả cho

𝐸𝑏 𝑁0 đạt 𝐵𝐸𝑅 ≈ 1,2.10−3, nếu sử dụng bộ mã cyclic (27,9,9) thì kênh truyền đạt 𝐵𝐸𝑅 ≈

thấy với phương pháp điều chế QPSK tại = 7, nếu không mã hóa thì kênh truyền

2,4.10−5, sử dụng bộ mã cyclic (15,5,7) thì đạt 𝐵𝐸𝑅 ≈ 1,5.10−7; với phương pháp

𝐸𝑏 𝑁0

điều chế 16QAM tại = 10, nếu không mã hóa thì kênh truyền đạt 𝐵𝐸𝑅 ≈

2,5.10−3, sử dụng bộ mã cyclic (27,9,9) thì kênh truyền đạt 𝐵𝐸𝑅 ≈ 9.10−5, sử dụng

bộ mã cyclic (15,5,7) thì đạt 𝐵𝐸𝑅 ≈ 1,5.10−6. Kết quả mô phỏng trên Hình 3.7 cho

thấy dù sử dụng phương pháp điều chế nào thì bộ mã cyclic (15,5,7) đạt giới hạn

tối ưu Griesmer và Plotkin (có khả năng sửa 𝑡 = 3 bit lỗi, và 𝑡/𝑛 = 3/15) cho khả

năng sửa lỗi tốt hơn (hay tỉ số 𝐵𝐸𝑅 thấp hơn) bộ mã cyclic (27,9,9) là mã cyclic tốt

(có khả năng sửa 𝑡 = 4 bit lỗi, và 𝑡/𝑛 = 4/27) . Tác giả cũng đã mô phỏng đánh

giá bộ mã với điều chế 64QAM, 128QAM thì cho tỉ lệ lỗi lớn và khả năng sửa lỗi

không tốt như mã (255,9,127).

3.2.3. Đề xuất thực hiện các bộ mã trên FPGA

Trong phần này, nghiên cứu sinh sẽ trình bày việc xây dựng một số bộ mã

cyclic trên FPGA với các nội dung: nghiên cứu phương pháp xây dựng bộ mã, thực

hiện thiết kế và mô phỏng bộ mã trên FPGA. Trước hết, có thể thấy rằng mỗi bộ mã

cyclic khác nhau đều có sơ đồ mã hoá và giải mã khác nhau [6], [12], [19], do đó

theo lý thuyết về phương pháp xây dựng mã cyclic thì với mỗi bộ mã ta cần phải có

một cấu kiện phần cứng tương ứng với sơ đồ mạch điện của nó. Tuy nhiên với sự

phát triển của công nghệ điện tử, ngày nay công nghệ FPGA đã góp phần cung cấp

cho thị trường các chip logic số có số lượng cổng logic lớn và đặc biệt là có thể viết

chương trình để tạo ra các mạch điện thực hiện chức năng theo yêu cầu.

Nhằm kết hợp ưu điểm của cấu kiện logic khả trình và hướng tới xây dựng

một mạch điện tử thực hiện được chức năng một số bộ mã cyclic, phần tiếp theo

luận án trình bày phương pháp xây dựng mạch mã hoá và giải mã trên cấu kiện logic

khả trình FPGA để thực hiện chức năng của một số bộ mã có đặc điểm tương tự

nhau. Dưới đây sẽ trình bày kết quả nghiên cứu xây dựng hai bộ mã LCC(15,5) và

LCC(27,9) là những mã tốt được đề xuất ở trên.

3.2.3.1. Đề xuất thực hiện thuật toán nhân và bình phương trên FPGA

Từ thuật toán nhân và bình phương lặp (RSMA – Repeated Square-and-

Multiply Algorithm) trong , [63], nghiên cứu sinh đề xuất thực hiện thuật toán

trên FPGA để tiến tới ứng dụng xây dựng CMG cho bộ mã cyclic trên cấu kiện phần

cứng logic khả trình. Kết quả nghiên cứu về nội dung này được trình bày tại hội

nghị khoa học quốc tế và công bố trong [C1]. Chi tiết nội dung được nghiên cứu

sinh trình bày tại phụ lục 5.

3.2.3.2. Thiết kế bộ mã LCC (15, 5) trên FPGA

Muốn xây dựng bộ mã LCC (15,5) cần phải làm hai phần việc như sau: Thứ

nhất, là xây dựng mạch mã hóa theo phương pháp xây dựng mã LCC đã được trình

bày; Thứ hai, là xây dựng mạch giải mã theo phương pháp giải mã ngưỡng.

Chọn đa thức sinh có cấp 15 (cấp cực đại của vành)

trên vành đa thức 𝑍2/(𝑥5 + 1). Tiếp đến, ta xây dựng xây dựng mạch mã hóa và giải mã, sau đó thực hiện thiết kế và mô phỏng bộ mã trên FPGA. Chi tiết nội dung

được trình bày trong phụ lục 5.

Kết quả mô phỏng cho thấy rằng bộ mã có khả năng sửa tới 3 bit lỗi, trong đó

có ưu điểm trong việc sửa lỗi cụm. Tài nguyên logic được sử dụng để xây dựng bộ

mã hóa là rất nhỏ, do đó hoàn toàn có thể tận dụng phần tài nguyên FPGA trong các

hệ thống số để xây dựng các bộ mã cyclic hỗ trợ sửa lỗi cho quá trình truyền tin.

Ưu điểm nổi bật của phương pháp này là chỉ với một chương trình phần mềm

được viết sẵn, ta có thể thay đổi phần tử sinh thì tự động tổng hợp được mạch mã

hoá và giải mã tương ứng trên FPGA để thực hiện chức năng của mạch. Nghiên cứu

sinh cũng đang thực hiện việc xây dựng các bộ mã cyclic trên các bộ vi điều khiển,

kết quả bước đầu cho thấy việc thực hiện mạch mã hoá và giải mã các bộ mã LCC

trên FPGA có nhiều ưu điểm về tài nguyên, tốc độ.

3.2.3.3. Thiết kế bộ mã LCC (27, 9) trên FPGA

Phần này đề xuất việc xây dựng bộ mã LCC (27, 9, 9) từ 3 cấp số nhân cyclic

lấy trong phân hoạch vành đa thức thành các CGP cấp 9 [6]. Trước

hết nghiên cứu phương pháp xây dựng bộ mã, sau đó thực hiện thiết kế và mô phỏng

bộ mã trên FPGA. Chi tiết nội dung được trình bày trong phụ lục 5.

Tài nguyên logic sử dụng để xây dựng bộ mã là tương đối nhỏ, có thể nhận

thấy tài nguyên phần cứng sử dụng cho bộ mã LCC (29,9,9) lớn hơn bộ mã LCC

(15,5,7) khoảng hai lần, trong đó điểm đặc biệt là số trigơ sử dụng tăng gấp nhiều

lần là do trong quá trình mô phỏng bộ mã LCC(15,5,7) được xây dựng từ CMG của

một phần sinh, còn bộ mã LCC(27,9,9) được xây dựng từ 3 lớp kề cyclic.

Kết quả mô phỏng cho thấy rằng bộ mã có khả năng sửa tới 4 bit lỗi, trong đó

có ưu điểm trong việc sửa lỗi cụm.

Như vậy, trong phần này nghiên cứu sinh đã trình bày một kết quả nghiên cứu

mới là thực hiện xây dựng và cứng hóa một số bộ mã hóa và giải mã cylic, cyclic

cục bộ trên cấu kiện phần cứng FPGA với hướng tiếp cận xây dựng mã trên vành

đa thức cho kết quả tương đối khả quan [J1]. Nhóm tác giả Gaurav Chawla and

Vishal Chaudhary cũng công bố kết quả thực hiện bộ mã hóa và giải mã trên FPGA

đối với mã cyclic theo phương pháp truyền thống [48], tuy nhiên chưa đề cập đến

việc thực hiện xây dựng bộ mã theo quan điểm vành đa thức, hay các bộ mã LCC.

3.3. ĐỀ XUẤT PHƯƠNG PHÁP TẠO KHÓA CHO MỘT SỐ HỆ MẬT

Nghiên cứu sinh đã nghiên cứu ứng dụng CMG và CGP có cấp cực đại trong

việc tạo khóa để xây dựng hệ mật mã khối kết hợp sơ đồ Lai-Massey với sơ đồ

Feistel và ứng dụng vào hàm băm công bố trong bài báo [C2].

Trong phần này nghiên cứu sinh đề xuất một hướng tiếp cận mới về sự tương

đương của vành đa thức có hai lớp kề cyclic với trường số. Từ đó trình bày một ứng

dụng của nhóm nhân cyclic có cấp cực đại trên một số vành đa thức có hai lớp kề

cyclic đặc biệt để làm khóa cho một số hệ mật.

3.3.1. Quan hệ giữa vành đa thức có hai lớp kề cyclic và trường số

∗ = 𝑍𝑝/{0} là một

∗ : 𝑎. 𝑏 ≡ 1 mod 𝑝

Xét 𝑝 = 2𝑛 − 1 là số nguyên tố. Khi đó ℤ𝑝 → 𝐺𝐹(𝑝), ℤ𝑝

∗ | = 2𝑛 − 2 với 𝑎 ∈ ℤ𝑝

∗ → ∃𝑏 ∈ ℤ𝑝

nhóm nhân cyclic cấp |ℤ𝑝

Xét 𝑊(𝑎(𝑥)) lẻ. Khi đó ∃𝑏(𝑥) với 𝑊(𝑏(𝑥)) lẻ thỏa mãn

𝑎(𝑥). 𝑏(𝑥) ≡ 1 mod (𝑥𝑛 − 1)

Do vậy, có thể xây dựng phép tương ứng sau:

∗ ∈ ℤ𝑝

𝑖∈𝐼

𝑎(𝑥) = ∑ 𝑓𝑖𝑥𝑖 ↦ 𝑎 = ∑ 𝑓𝑖2𝑖

𝑛−1 𝑖=0

𝑥𝑖 = 0. Với 𝑒0(𝑥) = ∑

Khi đó ta có thể coi ánh xạ trên là một ánh xạ 1-1 giữa các phần tử của ℤ2[𝑥]/(𝑥𝑛 − 1) và các phần tử của 𝐺𝐹(𝑝). Như vậy, vành đa thức có hai lớp kề cyclic và trường số 𝐺𝐹(𝑝) với 𝑝 = 2𝑛 − 1 là số nguyên tố được gọi là tựa đẳng cấu

(quasi-isomorphism). Ta có thể so sánh việc thực hiện các phép toán cộng và nhân

trên hai cấu trúc này như Bảng 3.3.

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ố

Phép tính Trường số 𝐺𝐹(𝑝) Vành đa thức ℤ2[𝑥]/(𝑥𝑛 − 1)

𝑖∈𝐼⊂ℤ𝑛

𝑖∈𝐽⊂ℤ𝑛

𝑎, 𝑏 ∈ 𝐺𝐹(𝑝) Phép cộng 𝑎(𝑥) = ∑ 𝑎𝑖𝑥𝑖 ; 𝑏(𝑥) = ∑ 𝑏𝑗𝑥 𝑗

𝑎 + 𝑏 ≡ (𝑎 + 𝑏) mod 𝑝

𝑘∈𝐾⊂ℤ𝑛

𝑎(𝑥) + 𝑏(𝑥) = 𝑐(𝑥) = ∑ 𝑐𝑘𝑥𝑘

𝐾 = (𝐼 ∪ 𝐽) − (𝐼 ∩ 𝐽)

Phép nhân 𝑎(𝑥). 𝑏(𝑥) ≡ 𝑎(𝑥). 𝑏(𝑥) mod (𝑥𝑛 − 1) 𝑎. 𝑏 ≡ 𝑎. 𝑏 mod 𝑝

Ví dụ 3.1:

Trường số 𝐺𝐹(31) Vành đa thức ℤ2[𝑥]/(𝑥5 − 1)

Phép cộng 𝑎(𝑥) = 1 + 𝑥 + 𝑥3 𝑎 = 11

𝑏(𝑥) = 1 + 𝑥2 + 𝑥4 𝑏 = 21

𝑎 + 𝑏 ≡ (11 + 21) mod 31 𝑎(𝑥) + 𝑏(𝑥) = 𝑐(𝑥)

𝑐(𝑥) = 𝑥 + 𝑥2 + 𝑥3 + 𝑥4 𝑎 + 𝑏 ≡ 32 mod 31 = 1

Phép nhân 𝑎(𝑥). 𝑏(𝑥) 𝑎. 𝑏 ≡ 11.21 mod 31

≡ 𝑎(𝑥). 𝑏(𝑥) mod (𝑥31 − 1) 𝑎. 𝑏 ≡ 14 ↔ (𝑥 + 𝑥2 + 𝑥3)

𝑎(𝑥). 𝑏(𝑥) ≡ (1 + 𝑥 + 𝑥4) ↔ 19

Bảng 3.4 chỉ ra các phần tử nghịch đảo tương quan trên trường số 𝐺𝐹(31) và

vành ℤ2[𝑥]/(𝑥5 − 1). Trong đó các phần tử 𝑎(𝑥) và 𝑏(𝑥) là các đa thức có giá trị tương đương hoặc bù với giá trị trong trường số.

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

TT Trên 𝐺𝐹(31) Trên ℤ2[𝑥]/(𝑥5 − 1)

𝑎. 𝑏 ≡ 1 mod 31 𝑎(𝑥). 𝑏(𝑥) ≡ 1 mod (𝑥5 − 1)

1 𝑎(𝑥) = (234), 𝑏(𝑥) = (024) 3.21 ≡ 1

2 𝑎(𝑥) = (124), 𝑏(𝑥) = (012) 9.7 ≡ 1

3 𝑎(𝑥) = (2), 𝑏(𝑥) = (3) 27.23 ≡ 1

4 𝑎(𝑥) = (014), 𝑏(𝑥) = (023) 19.18 ≡ 1

5 𝑎(𝑥) = (134), 𝑏(𝑥) = (034) 26.6 ≡ 1

6 𝑎(𝑥) = (4), 𝑏(𝑥) = (1) 16.2 ≡ 1

7 𝑎(𝑥) = (123), 𝑏(𝑥) = (013) 17.11 ≡ 1

8 𝑎(𝑥) = (013), 𝑏(𝑥) = (123) 20.14 ≡ 1

9 𝑎(𝑥) = (1), 𝑏(𝑥) = (4) 29.15 ≡ 1

10 𝑎(𝑥) = (034), 𝑏(𝑥) = (134) 25.5 ≡ 1

11 𝑎(𝑥) = (023), 𝑏(𝑥) = (014) 13.12 ≡ 1

12 𝑎(𝑥) = (3), 𝑏(𝑥) = (2) 8.4 ≡ 1

13 𝑎(𝑥) = (012), 𝑏(𝑥) = (124) 24.22 ≡ 1

14 𝑎(𝑥) = (024), 𝑏(𝑥) = (234) 10.28 ≡ 1

15 𝑎(𝑥) = (0), 𝑏(𝑥) = (0) 30.30 ≡ 1

Với tính đặc thù như trình bày ở trên, quan hệ tựa đồng cấu chỉ xảy ra đối với

một số vành đa thức có hai lớp kề cyclic đặc biệt, các vành đa thức này được liệt kê

trong phụ lục 4.

100

Nhận xét: Có thể sử dụng quan hệ tựa đồng cấu này để xây dựng một số hệ

mật trên vành đa thức có 2 lớp kề cyclic.

3.3.2. Hệ mật Omura-Massey trên vành đa thức có hai lớp kề cyclic

Hệ mật Omura-Massey (O-M) được đề xuất bởi James Massey và Jim. K.

Omura lần đầu tiên vào năm 1982 được xem như một cải thiện tích cực trên giao

thức Shamir (1980) [8], [63]. Trong phần này, trên cơ sở hệ mật gốc, kết hợp với

tính chất đặc biệt của một số vành đa thức có hai lớp kề cyclic được trình bày ở

phần trên, nghiên cứu sinh sẽ trình bày hệ mật O-M và một số biến thể mới của hệ

mật O-M được xây dựng trên vành đa thức có hai lớp kề cyclic trong đó sử dụng

phần tử có cấp cao nhất của nhóm nhân cyclic đạt cấp cực đại trên vành làm khóa

cho hệ mật.

3.3.2.1. Hệ mật O-M gốc

a) Tạo khóa

Khóa công khai: 𝑝 (là một số nguyên tố lớn)

Khóa riêng của A: A chọn ngẫu nhiên (𝑚, 𝑛): 𝑚. 𝑛 ≡ 1 mod (𝑝 − 1)

Khóa riêng của B: B chọn ngẫu nhiên (𝑢, 𝑣): 𝑢. 𝑣 ≡ 1 mod (𝑝 − 1)

b) Quá trình truyền thông

A muốn gửi một bản tin 𝑀 tới B

𝐴(𝑚, 𝑛) 𝐵(𝑢, 𝑣)

𝐴 tính: (𝑀)𝑚 mod 𝑝 →

← 𝐵 tính: (𝑀𝑚)𝑢 mod 𝑝

𝐴 tính: (𝑀𝑚𝑢)𝑛 mod 𝑝 = (𝑀)𝑢 mod 𝑝 →

𝐵 tính: (𝑀)𝑢𝑣 mod 𝑝 = 𝑀

c) Nhận xét

- K. Sakurai & H. Shizyya chỉ ra rằng với những giải thiết nhất định, việc bẻ

khóa hệ mật O-M liên quan tới giả thiết D-H.

101

- Giao thức được trình bày ở trên chưa bao gồm tính xác thực.

- Đối với giao thức này, hệ số mở rộng bản tin là 3.

Hình 3.8. Giao thức truyền thông sử dụng hệ mật O-M

- Chúng ta có thể minh họa giao thức này như Hình 3.8.

Hệ mật này phải là một hệ mật không suy biến và có tính giao hoán.

3.3.2.2. Hệ mật O-M trên vành đa thức có hai lớp kề cyclic

a) Tạo khóa

Khóa công khai: ℤ2[𝑥]/(𝑥𝑛 + 1) – Vành đa thức có hai lớp kề cyclic.

Khóa riêng của A: A chọn ngẫu nhiên (𝑚, 𝑛): 𝑚. 𝑛 ≡ 1 mod (2𝑛−1 − 1)

Khóa riêng của B: B chọn ngẫu nhiên (𝑢, 𝑣): 𝑢. 𝑣 ≡ 1 mod (2𝑛−1 − 1)

b) Quá trình truyền thông

A muốn gửi bản tin 𝑀(𝑥) tới B

𝐴(𝑚, 𝑛) 𝐵(𝑢, 𝑣)

𝐴 tính: [𝑀(𝑥)]𝑚 mod (𝑥𝑛 + 1) →

← 𝐵 tính: [𝑀𝑚(𝑥)]𝑢 mod (𝑥𝑛 + 1)

𝐴 tính: →

[𝑀𝑚𝑢(𝑥)]𝑛 mod (𝑥𝑛 + 1) =

[𝑀(𝑥)]𝑢 mod (𝑥𝑛 + 1)

← 𝐵 tính: [𝑀𝑢(𝑥)]𝑣 mod (𝑥𝑛 + 1) = 𝑀(𝑥)

c) Ví dụ 3.2

Khóa công khai: Đặt ℤ2[𝑥]/(𝑥𝑛 + 1) = ℤ2[𝑥]/(𝑥5 + 1).

Khóa riêng của A: (𝑚, 𝑛) = (2,8): 2.8 ≡ 1 mod 15

102

Khóa riêng của B: (𝑢, 𝑣) = (4,4): 4.4 ≡ 1 mod 15

A muốn gửi bản tin 𝑀 = (034) tới B

𝐴(2,8) 𝐵(4,4)

𝐴 tính: (034)2 mod (𝑥5 + 1) = (013) →

← 𝐵 tính:

(013)4 mod (𝑥5 + 1) = (024)

𝐴 tính: (024)8 mod (𝑥5 + 1) = (012) →

← 𝐵 tính:

(012)4 mod (𝑥5 + 1) = (034)

d) Nhận xét

- Hệ mật là an toàn nếu bài toán logarit rời rạc trên vành đa thức có hai lớp kề

cyclic là bất khả giải.

- Hệ mật này là không xác thực.

- Hệ số mở rộng bản tin của hệ mật này là 3.

3.3.2.3. Một số biến thể của hệ mật O-M trên vành đa thức có hai lớp kề

cyclic

a) Hệ mật O-M cộng trên vành đa thức có hai lớp kề cyclic

Tạo khóa

Khóa công khai: ℤ2[𝑥]/(𝑥𝑛 + 1) – Vành đa thức có hai lớp kề cyclic.

Khóa riêng của A: một đa thức ngẫu nhiên 𝑎(𝑥) ∈ ℤ2[𝑥]/(𝑥𝑛 + 1)

Khóa riêng của B: một đa thức ngẫu nhiên 𝑏(𝑥) ∈ ℤ2[𝑥]/(𝑥𝑛 + 1)

103

Quá trình truyền thông

A muốn gửi bản tin 𝑀(𝑥) ∈ ℤ2[𝑥]/(𝑥𝑛 + 1) tới B

𝐴 tính: [𝑀(𝑥) + 𝑎(𝑥)] mod (𝑥𝑛 + 1)

→

← 𝐵 tính:

[𝑀(𝑥) + 𝑎(𝑥) + 𝑏(𝑥)] mod (𝑥𝑛 + 1)

𝐴 tính:

→

{[𝑀(𝑥) + 𝑎(𝑥) + 𝑏(𝑥)] + 𝑎(𝑥)} mod (𝑥𝑛 + 1)

= [𝑀(𝑥) + 𝑏(𝑥)] mod (𝑥𝑛 + 1)

← 𝐵 tính: {[𝑀(𝑥) + 𝑏(𝑥)] +

𝑏(𝑥)} mod (𝑥𝑛 + 1) = 𝑀(𝑥)

𝐴 𝑎(𝑥) 𝐵 𝑏(𝑥)

Ví dụ 3.3:

Khóa công khai: Đặt ℤ2[𝑥]/(𝑥𝑛 + 1) = ℤ2[𝑥]/(𝑥5 + 1).

Khóa riêng của A: 𝑎(𝑥) = (013)

Khóa riêng của B: 𝑏(𝑥) = (124)

A muốn gửi bản tin 𝑀(𝑥) = (034) tới B

𝐴 (013) 𝐵 (124)

𝐴 tính: (034) + (013) = (14) →

← 𝐵 tính: (14) + (124) = (2)

𝐴 tính: (2) + (013) = (0123) →

← 𝐵 tính: (0123) + (124) = (034)

Nhận xét

- Nếu khóa bí mật được chọn ngẫu nhiên thì hệ mật là an toàn nếu không gian

khóa được cung cấp đủ lớn.

- Hệ mật này là không xác thực.

104

- Hệ số mở rộng bản tin của hệ mật này là 3.

- Việc tính toán của hệ mật này rất đơn giản.

b) Hệ mật O-M có tính nhân trên vành đa thức có hai lớp kề cyclic

Tạo khóa

Khóa công khai: ℤ2[𝑥]/(𝑥𝑛 + 1) – Vành đa thức có hai lớp kề cyclic.

Khóa riêng của A: đa thức ngẫu nhiên 𝑎(𝑥) ∈ ℤ2[𝑥]/(𝑥𝑛 + 1), 𝑤(𝑎(𝑥)) lẻ.

Khóa riêng của B: đa thức ngẫu nhiên 𝑏(𝑥) ∈ ℤ2[𝑥]/(𝑥𝑛 + 1), 𝑤(𝑏(𝑥)) lẻ.

Quá trình truyền thông

A muốn gửi một bản tin 𝑀(𝑥) ∈ ℤ2[𝑥]/(𝑥𝑛 + 1) tới B

𝐴 𝑎(𝑥) 𝐵 𝑏(𝑥)

𝐴 tính: →

[𝑀(𝑥). 𝑎(𝑥)] mod (𝑥𝑛 + 1)

← 𝐵 tính:

[𝑀(𝑥). 𝑎(𝑥). 𝑏(𝑥)] mod (𝑥𝑛 + 1)

{[𝑀(𝑥). 𝑎(𝑥). 𝑏(𝑥)]. 𝑎−1(𝑥)} mod (𝑥𝑛 + 1)

𝐴 tính: →

= [𝑀(𝑥). 𝑏(𝑥)] mod (𝑥𝑛 + 1)

{[𝑀(𝑥). 𝑏(𝑥)]. 𝑏−1(𝑥)} mod (𝑥𝑛 + 1)

← 𝐵 tính:

= 𝑀(𝑥)

Ví dụ 3.4:

Lấy ℤ2[𝑥]/(𝑥𝑛 + 1) = ℤ2[𝑥]/(𝑥5 + 1).

Khóa riêng của A: 𝑎(𝑥) = (013) → 𝑎−1(𝑥) = (123)

Khóa riêng của B: 𝑏(𝑥) = (124) → 𝑏−1(𝑥) = (012)

105

A muốn gửi một bản tin 𝑀(𝑥) = (034) tới B

𝐴 𝑎(𝑥) 𝐵 𝑏(𝑥)

𝐴 tính: →

[𝑀(𝑥). 𝑎(𝑥)]

= [(034). (013)] mod (𝑥5 + 1) = (2)

← 𝐵 tính

[(2). (124)] mod (𝑥5 + 1)

= (134)

𝐴 tính: →

[(134). (123)] mod (𝑥5 + 1) = (3)

← 𝐵 tính

[(3). (012)] mod (𝑥5 + 1)

= (034)

Nhận xét

- Nếu các khóa bí mật được chọn ngẫu nhiên thì hệ mật là an toàn nếu không

gian khóa đủ lớn.

- Hệ mật là không xác thực.

- Hệ số mở rộng bản tin của hệ mật là 3.

- Việc tính toán hệ mật này là đơn giản.

- Để tránh phép tấn công “Kẻ đứng giữa” (Man in the midle) có thể sử dụng

thêm các phương pháp xác thực.

3.4. KẾT LUẬN CHƯƠNG

Chương 3 của luận án đã trình bày các nội dung liên quan đến phương pháp

xây dựng mã cyclic, đề xuất phương pháp tìm kiếm mã cyclic tốt, hiện thực hóa các

bộ mã cyclic trên cấu kiện logic khả trình FPGA, đồng thời nghiên cứu khả năng

ứng dụng nhóm nhân và cấp số nhân cyclic làm khóa cho một số hệ mật.

106

Kết quả chính và mới của chương này là: đề xuất phương pháp tìm mã cyclic

tốt thông qua việc chứng minh hai định lý về mã cyclic tối ưu, xây dựng thuât toán

tìm kiếm mã cyclic tốt và bước đầu lập được bảng một số mã cyclic tốt, thông qua

kết quả mô phỏng, đánh giá hiệu năng của các bộ mã có thể nhận xét rằng kết quả

nghiên cứu đã góp phần chỉ ra cách xác định các mã cyclic tốt có thể ứng dụng vào

thực tế [J6]; Đề xuất việc xây dựng các thiết bị mã hóa và giải mã ngưỡng cho các

nhóm nhân cyclic và cấp số nhân cyclic trên cấu kiện logic khả trình FPGA. Các

kết quả này góp phần minh chứng và khẳng định khả năng xây dựng các bộ mã

cyclic đặc biệt là cyclic cục bộ, cũng như việc cứng hóa các bộ mã này trên cấu kiện

logic khả trình. Đồng thời, các phương pháp xây dựng các bộ mã cyclic trên cấu

kiện phần cứng logic khả trình FPGA được trình bày một cách tường minh góp phần

bổ sung kiến thức lý thuyết và thực nghiệm về mã cyclic, có thể làm tài liệu tham

khảo cho các nghiên cứu tiếp theo trong việc xây dựng và cứng hóa trên các cấu

kiện điện tử khả trình đối với bộ mã này. Kết quả nghiên cứu được công bố trong

các bài báo [J1], [C1]; Nghiên cứu sinh cũng trình bày một đề xuất ứng dụng nhóm

nhân, cấp số nhân cyclic làm khóa cho một số hệ mật là một hướng nghiên cứu mở

có thể tiếp tục nghiên cứu [C2].

107

KẾT LUẬN

Những đóng góp chính của luận án:

1. Đề xuất một số phương pháp xác định đa thức có cấp cực đại, bao gồm kết quả

quan trọng: đề xuất và chứng minh bổ đề về cấp của đa thức là tích của các đa

thức trên vành; Đề xuất và chứng minh bổ đề về cấp nhị thức trên vành đa thức,

đồng thời đánh giá cấp nhị thức trên vành đa thức; Đề xuất thuật toán cải

tiến xác định cấp của đa thức trên vành; Đánh giá xác suất tìm phần tử có cấp

cực đại giúp kiến thiết các nhóm nhân và mã cyclic trên vành đa thức có hai lớp

kề cyclic ([J2], [J3], [J5], [C5]).

2. Chứng minh được 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, góp phần mở ra một hướng tiếp cận mới là xây dựng mã

cyclic truyền thống từ các nhóm nhân cyclic, cấp số nhân cyclic trên vành đa

thức có bậc bằng cấp của nhóm nhân cyclic, cấp số nhân cyclic ([J4], [C3], [C4]).

3. Đề xuất phương pháp tìm mã cyclic tốt xây dựng từ nhóm nhân cyclic, cấp số

nhân cyclic trên vành đa thức và bước đầu lập được bảng một số mã cyclic tốt,

đánh giá 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

(như FPGA). Các kết quả này góp phần chỉ ra các mã cyclic tốt có thể sử dụng

trong thực tế, đồng thời minh chứng và khẳng định khả năng xây dựng các bộ

mã cyclic đặc biệt là cyclic cục bộ, cũng như việc mô phỏng các bộ mã này trên

cấu kiện logic khả trình ([J1], [J6], [C1]).

Các định hướng nghiên cứu tiếp theo

Nghiên cứu các mã LCC trên trường mở rộng GF (2m)

Tiếp tục nghiên cứu ứng dụng nhóm nhân cyclic, cấp số nhân cyclic và mã

cyclic cục bộ vào các kỹ thuật mã hóa, bảo mật, hệ thống truyền thông.

108

CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ

[J1] Nguyen Trung Hieu, Dang Hoai Bac, Nguyen Ngoc Minh (2012), “An

FPGA-based implementation method for local cyclic code encoder/decoder”,

Journal of Science and Technology, Vietnam, ISSN 0866 708X, 50(2A), pp.

38-49.

[J2] Nguyen Trung Hieu, Ngo Duc Thien, Tran Duc Su (2012), “On constructing

cyclic multiplicative groups with maximum order over polynomial ring with

two cyclotomic cosets”, Tạp chí Nghiên cứu khoa học và Công nghệ Quân sự,

Hà Nội, Việt Nam, ISSN 1859-1043, Số 17, 02-2012, tr. 133-140.

[J3] Nguyễn Trung Hiếu, Nguyễn Văn Trung, Nguyễn Bình (2013), “Về cấp của

các đa thức trên vành”, Tạp chí Khoa học và Công nghệ, Việt Nam, ISSN

0866 708X, 51(1A) , tr. 101-107.

[J4] Nguyễn Văn Trung, Nguyễn Trung Hiếu (2015), “Mã cyclic cục bộ xây dựng

từ một lớp kề cyclic”, Tạp chí Nghiên cứu khoa học và Công nghệ Quân sự,

Hà Nội, Việt Nam, ISSN 1859-1043, số Đặc san KH-CNQS, 10-2015, tr. 331-

336.

[J5] Nguyễn Trung Hiếu, Ngô Đức Thiện (2016), “Một phương pháp tìm kiếm

các đa thức có cấp cực đại trên vành đa thức”, Tạp chí Khoa học và Công nghệ

các trường Đại học Kỹ thuật, Việt Nam, ISSN 2354-1083, số 110, 2016, tr.

75-80.

[J6] Nguyễn Trung Hiếu, Nguyễn Bình (2017), “Một số bộ mã cyclic tốt xây dựng

trên vành đa thức”, Tạp chí Khoa học công nghệ Thông tin và Truyền thông,

Việt Nam, ISSN 2525-2224, số 01 (CS.01) 2017, tr. 20-27.

[C1] Hieu T. Nguyen, Minh N. Nguyen, Cuong L. Nguyen, Edhem Custovic

(2011), “An FPGA-based Implementation for Repeated Square-and-Multiply

Polynomials”, Proceedings of the 6th International Conference on Broadband

Communications & Biomedical Applications, November 21 - 24, 2011,

109

Melbourne, Australia, ISBN: 978-0-9872129-0-0, pp. 173-178 (publication in

IEEE Xplore).

[C2] Ngô Đức Thiện, Nguyễn Trung Hiếu, Nguyễn Toàn Thắng, Đặng Hoài Bắc

(2013), “Một phương pháp xây dựng hệ mật mã khối kết hợp sơ đồ Lai-

Massey với sơ đồ Feistel và ứng dụng vào hàm băm”, Kỷ yếu Hội nghị Quốc

gia về Điện tử - Truyền thông (REV2013-KC01), Hà Nội, Việt Nam, ngày 17-

18/12/2013, tr. 75-80.

[C3] Nguyễn Trung Hiếu, Nguyễn Văn Trung, Phạm Việt Trung (2013), “Sự

tương đương giữa mã Cyclic cục bộ xây dựng trên 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

(REV2013-KC01), Hà Nội, Việt Nam, ngày 17-18/12/2013, tr. 225-230.

[C4] Nguyen Trung Hieu, Nguyen Van Trung, Nguyen Binh (2014), “A

Classification of Linear Codes Based on Algebraic Structures and Local

Cyclic Codes”, Proceedings of The 2014 International Conference on

Advanced Technologies for Communications, October 15-17, 2014, Hanoi,

Vietnam, ISBN: 978-1-4799-6955-5, pp. 349-354 (publication in IEEE

Xplore).

[C5] Nguyễn Trung Hiếu (2015), “Một số phương pháp mới xác định cấp của đa

thức trên vành đa thức sử dụng tính chất của nhóm nhân cyclic đối xứng”, Hội

thảo quốc gia 2015 về Điện tử, Truyền thông và Công nghệ thông tin (ECIT-

2015), tháng 12/2015, TP. Hồ Chí Minh, Việt Nam, tr. 248-252.

110

TÀI LIỆU THAM KHẢO

Tài liệu tham khảo Tiếng Việt

[1] Đặng Hoài Bắc (2010), Các mã xyclic và xyclic cục bộ trên các vành đa thức

có 2 lớp kề xyclic, Luận án Tiến sĩ kỹ thuật, Học viện Công nghệ Bưu chính

Viễn thông.

[2] Nguyễn Bình, Nguyễn Thế Truyện (1996), “Các mã xyclic cục bộ tự trực

giao”, Hội nghị Vô tuyến Điện tử toàn quốc lần thứ 6 (REV’96).

[3] Nguyễn Bình, Nguyễn Thế Truyện (1996), “Các mã xyclic cục bộ có khả năng

trực giao”, Hội nghị Vô tuyến Điện tử toàn quốc lần thứ 6 (REV’96).

[4] Nguyễn Bình, Nguyễn Xuân Quỳnh (1998), “Thiết lập các tổng kiểm tra cho

mã xyclic tạo từ các mã xyclic cục bộ”, Hội nghị tự động hóa toàn quốc lần

thứ ba (VICA-3).

[5] Nguyễn Bình, Nguyễn Xuân Quỳnh (1996), “Giải mã ngưỡng dựa trên hệ tổng

kiểm tra liên kết chặt”, Hội nghị tự động hóa toàn quốc lần 2 (VICA-2).

[6] Nguyễn Bình (2012), “Các mã xyclic và xyclic cục bộ trên vành đa thức”, Tạp

chí Khoa học và Công nghệ, ISSN 0866 708X, Tập 50, Số 6, trang 735-749.

[7] Học viện Công nghệ Bưu chính Viễn thông (2008), Giáo trình Lý thuyết thông

tin, Nhà xuất bản Bưu điện.

[8] Học viện Công nghệ Bưu chính Viễn thông (2007), Giáo trình Mật mã học,

Nhà xuất bản Bưu điện.

[9] Hồ Quang Bửu, Ngô Đức Thiện, Trần Đức Sự (2012), “Xây dựng hệ mật trên

các cấp số nhân cyclic của vành đa thức”, Tạp chí Khoa học và Công nghệ,

ISSN 0866 780X, Tập 50, số 2A, trang 109-119.

[10] Vương Đức Hạnh, Nguyễn Lê Cường, Nguyễn Bình (2013), “Đánh giá hiệu

quả của các mã Turbo xây dựng trên các mã cyclic cục bộ”, Tạp chí Khoa học

và Công nghệ, ISSN 0866 708X, Tập 51, số 4A, trang 98-108.

111

[11] Nguyễn Xuân Quỳnh, Nguyễn Thế Truyện (1996), “Thuật toán thiết lập hệ

tổng kiểm tra tự trực giao cho mã xyclic cục bộ”, Hội nghị tự động hóa toàn

quốc lần thứ hai (VICA-2).

[12] Lê Đình Thích (2002), Nghiên cứu các mã xyclic cục bộ trên vành đa thức,

Luận án Tiến sĩ kỹ thuật.

[13] Ngô Đức Thiện (2010), Các mã xyclic cục bộ xây dựng trên các phân hoạch

hỗn hợp, Luận án Tiến sĩ kỹ thuật, Học viện Công nghệ Bưu chính Viễn thông.

[14] Ngô Đức Thiện, Nguyễn Toàn Thắng, “Một phương pháp xây dựng hệ mật

mã khối theo sơ đồ Lai – Massey và khả năng ứng dụng vào các hàm băm”,

Tạp chí Khoa học và Công nghệ Việt Nam, ISSN 0866 780X, Tập 51, số 4A,

trang 109-119.

[15] Nguyễn Văn Trung (2015), “Các mã cyclic trên vành Mersenne”, Tạp chí

Nghiên cứu Khoa học và Công nghệ Quân sự, ISSN 1859-1043, số tháng

2/2015, trang 44-49.

[16] Nguyễn Thế Truyện (1999), Các thuật toán để tự động lập mã sửa sai mới –

mã xyclic cục bộ, Luận án tiến sĩ kỹ thuật.

[17] Nguyễn Thúy Vân (1999), Lý thuyết mã, Nhà xuất bản KHKT, Hà Nội.

[18] Vũ Việt (2002), Đánh giá hiệu quả của mã xyclic cục bộ, Luận án Tiến sĩ Kỹ

thuật, Học viện Kỹ thuật Quân sự.

Tài liệu tham khảo Tiếng Anh

[19] Dang Hoai Bac, Nguyen Binh, Nguyen Xuan Quynh (2007), "Novel Algebraic

Structure for Cyclic Codes", Applied Algebra, Algebraic Algorithms, and

Error Correcting Codes –Conf. AAECC 17, LNCS 4851, December, Springer-

Verlag Berlin Heidelberg, pp. 301-310.

[20] Dang Hoai Bac, Nguyen Binh, Nguyen Xuan Quynh (2007), "New Algebraic

Structure Based on Cyclic Geometric Progressions over Polynomial Ring

Applied for Cryptography", IEEE, International Conference on

112

Computational Intelligence and Security (CIS) CIS'07, December 15-19,

Harbin, China.

[21] Dang Hoai Bac, Le Ngoc Hung (2008), “Using cyclic code in WCDMA cell

search algorithm”, Journal on Information and Communications

Technologies, ISSN: 0866-7039, issue 3, pp34-38, June 2008.

[22] Nguyen Binh (2002), “Crypto-System Based on Cyclic Geometric

Progressions over Polynomial Ring (Part I)”, REV’02, Vietnam.

[23] Nguyen Binh (2002), “Circulant Crypto System over Polynomial Ring

(Part II)”, REV’02, Vietnam.

[24] Nguyen Binh, Le Dinh Thich (1998), “Systematic cyclic codes constructed

from LCCs over polynomial ring”, REV’98, Vietnam.

[25] Nguyen Binh, Le Dinh Thich (2002), “The Oders of Polynomials and

Algorithms for Defining Oder of Polynomial over Polynomial Ping”, 5th

Vietnam Conference on Automation (VICA-5), Hanoi, Vietnam, October

2002.

[26] Nguyen Binh, Tran Duc Su (2002), “Local Cyclic Codes Constructed on

Conjugate Elements of Swallowing Idempotent”, REV’02, Vietnam.

[27] Nguyen Binh, Tran Duc Su (2002), “Self-symmetric Cosets and Local Cyclic

Codes”, REV’02, Vietnam.

[28] Nguyen Binh, Tran Duc Su, Pham Viet Trung (2001), “Decomposition of

polynomial ring according to the classes of conjugate elements”, AIC-26,

Hanoi, Vietnam.

[29] Nguyen Binh, Vu Viet, Pham Viet Trung (2000), “Decomposition of

Polynomial Ring and Coding with Random Clock”, Proceedings of the 18th

Conference of ASEAN Federation of Engineering Organisations (CAFEO),

22-24 November 2000, Hanoi, Vietnam.

[30] Ngo Duc Thien, Nguyen Binh (2008), “Some Local Cyclic Codes Based on

Compound Decomposition of Two Polynomial Rings”, 2008 International

113

Conference on Advanced Technologies for Communications (ATC 2008 -

REV’11). October 6th-9th, 2008, Hanoi, Vietnam. IEEE Catalog Number:

CFP08ATC-PRT; ISBN: 978-1-4244-2680-5.

[31] Nguyen Xuan Quynh, Nguyen Binh (1993), “Threshold-Decoding Method for

Local Cyclic Orthogonalable Codes”, System Modeling Control, Volume II,

p119-120, Zakopane, Poland.

[32] Amin Shokrollahi (2003), LDPC Codes: An Introduction, Digital Foutain, Inc.,

[33] A. Vardy (1998), “Trellis structure of codes”, Handbook of Coding Theory,

V. S. Pless and W. C. Huffman, Eds. Amsterdam, The Netherlands: Elsevier,

1998, pp. 1989–2118.

[34] Baocheng Wang, Chunming Tang, Yanfeng Qi, Yixian Yang (2012), “The

Weight Distributions of Cyclic Codes and Elliptic Curves”, IEEE

Transactions on Information Theory, ISSN 0018-9448, Vol. 58, No. 12, pp

7253 - 7259.

[35] Blahut R. E. (1983), Theory and Practice of Error Control Codes, Addision-

Wesley, Reading Mass.

[36] Breddermann. T., Vary. P. (2014), “Rate-Compatible Insertion Convolutional

Turbo Codes: Analysis and Application to LTE”, IEEE Transactions on

Wireless Communications, ISSN 1536-1276, Vol. 13, No. 3, pp 1356 - 1366.

[37] B. Heijne, J. Top (2009), “On the minimal distance of binary self-dual cyclic

codes”, IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 55,

No. 11, pp. 4860–4863.

[38] Carl D. Mayer (2000), Matrix Analysis and Applied Linear Algebra, Society

for Industrial and Applied Mathematics Philadelphia, PA, USA, 2000.

[39] Changli Ma, Liwei Zeng, Yang Liu, Dengguo Feng, and Cunsheng Ding

(2011), “The Weight Enumerator of a Class of Cyclic Codes”, IEEE

Transactions on Information Theory, ISSN 0018-9448, Vol. 57, No. 1, pp.

397-402.

114

[40] Charles L. Byrne (2013), Applied and Computational Linear Algebra: A First

Course, University of Massachusetts Lowell, 2013.

[41] Chengju Li, Qin Yue (2014), “Weight Distributions of Two Classes of Cyclic

Codes With Respect to Two Distinct Order Elements”, IEEE Transactions

on Information Theory, ISSN 0018-9448, Vol. 60, No. 1, pp 296 – 303.

[42] Chunlei Li, Nian Li, Helleseth, T., Cunsheng Ding (2014), “The Weight

Distributions of Several Classes of Cyclic Codes From APN Monomials”,

IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 60, No. 8,

pp 4710 – 4721.

[43] Cunsheng Ding, Yang Yang, Xiaohu Tang (2010), “Optimal Sets of

Frequency Hopping Sequences From Linear Cyclic Codes”, IEEE

Transactions on Information Theory, ISSN 0018-9448, Vol. 56, No. 7, pp

3605 - 3612.

[44] C. Ding (2012), “Cyclic codes from the two-prime sequences”, IEEE

Transactions on Information Theory, ISSN 0018-9448, 58(6), pp. 357–363.

[45] Elwyn R. Berlekamp (1968), Algebraic Coding Theory, McGraw-Hill Book

Company.

[46] Emanuele Betti and Massimiliano Sala (2006), “A New Bound for the

Minimum Distance of a Cyclic Code From Its Defining Set”, IEEE

Transactrions on Information theory, ISSN 0018-9448, Vol. 52, No. 8, pp

3700 - 3706.

[47] Erik G. Larsson and Petre Stoica (2008), Space-Time Block Coding for

Wireless Communications, Cambridge University Press.

[48] Gaurav Chawla and Vishal Chaudhary (2014), “FPGA Implementation of

Cyclic Code Encoder and Decoder”, Advance in Electronic and Electric

Engineering, ISSN 2231-1297, Volume 4, Number 3, pp. 273-278.

115

[49] Haibin Kan, Hong Shen (2005), “A Relation Between the Characteristic

Generators of a Linear Code and its Dual”, IEEE Transactions on Information

theory, ISSN 0018-9448, Vol. 51, No. 3, March 2005, pp. 1199-1202.

[50] Houshou CHEN (2006), “Optimal Encoding of Binary Cyclic Codes”, IEICE

Transactions on Communications, ISSN 0090-6778, Vol.E89–B, No.12,

Decemer 2006, pp 3280-3287.

[51] James L. Massey (1963), Threshold Decoding, M.I.T Press, Cambridge

Massachusetts.

[52] Junru ZHENG, Takayasu KAIDA (2006), “On Linear Complexity and Schaub

Bound for Cyclic Codes by Defining Sequence with Unknown Elements”,

IEICE Trans. Fundamentals, Vol.E89–A, No. 9 September 2006, pp 2337-

2340.

[53] J. Luo, K. Feng (2008), “Cyclic codes and sequences from generalized

Coulter-Matthews function”, IEEE Transactions on Information Theory,

ISSN 0018-9448, Vol. 54, No. 12, pp. 5345–5353.

[54] Kaneko T., Nishijima. T., Inazumi. H., Hirasawa. S. (2002), “An Efficent

maximum-likelihood decoding algorithm for linear block codes with algebraic

decoder”, IEEE Transactions on Information Theory, ISSN 0018-9448, Vol.

40, No. 2, pp 320-327.

[55] Kechao Huang, Mitchell. D.G.M., Lai Wei, Xiao Ma, Costello. D.J. (2015),

“Performance Comparison of LDPC Block and Spatially Coupled Codes Over

GF”, IEEE Transactions on Communications, ISSN 0090-6778, Vol. 63, No.

3, pp. 592-604.

[56] Keke Liu, Shu Lin, Abdel-Ghaffar. K. (2013), “A Revolving Iterative

Algorithm for Decoding Algebraic Cyclic and Quasi-Cyclic LDPC Codes”,

IEEE Transactions on Communications, ISSN 0090-6778, Vol. 61, No. 12, pp

4816 - 4827.

116

[57] Kristine Lally, Patrick Fitzpatrick (2001), “Algebraic structure of quasicyclic

codes”, Discrete Applied Mathematics, 111, pp 157–175.

[58] Li Zhang, Qin Huang, Shu Lin (2011), “Iterative Algorithms for Decoding a

Class of Two-Step Majority-Logic Decodable Cyclic Codes”, IEEE

Transactions on Communications, ISSN 0090-6778, Vol. 59, No. 2, pp 416 -

427.

[59] Mac Williams F. J., Sloane N. J .A. (1997), The Theory of Error-Correcting

Codes, North-Holland Mathematical Library, Vol. 16, Netherlands.

[60] Maosheng Xiong, Nian Li (2015), “Optimal Cyclic Codes With Generalized

Niho-Type Zeros and the Weight Distribution”, IEEE Transactions

on Information Theory, ISSN 0018-9448, Vol. 61, No. 9, pp 4914 – 4922.

[61] Mark Sum Chuen Ho (2002), Serial and Parallel Concatenated Turbo Codes,

Institute of Telecommunications Research School of Electrical and

Information Engineering, The University of South Australia.

[62] Md. Abbas Ali, Alcardo Alex Barakabitze (2015), “Evolution of LTE and

Related Technologies towards IMT Advanced”, International Journal of

Advanced Research in Computer Science and Software Engineering, Vol. 5

(1), 2015, pp. 16 - 22.

[63] Menezes A. J, Van Oorchot P. C. (1998), Handbook of Applied Cryptography,

CRC Press.

[64] Mikio Iwamura, Hideaki Takahashi, Satoshi Nagata (2010), “Relay

Technology in LTE-Advanced”, NTT DOCOMO Technical Journal Vol. 12

(2), 2010, pp. 29 - 36.

[65] E. Prange (1957), Cyclic error-correcting codes in two symbols, Electronics

Research Directorate, Air Force Cambridge Research Center.

[66] Pisek. E., Rajan. D., Cleveland. J.R (2015), “Trellis-Based QC-LDPC

Convolutional Codes Enabling Low Power Decoders”, IEEE Transactions

on Communications, ISSN 0090-6778, Vol. 63 , No. 6, pp. 1939 - 1951.

117

[67] Qin Huang, Qiuju Diao, Shu Lin, Abdel-Ghaffar. K. (2011), “Cyclic and

quasi-cyclic LDPC codes: New developments”, Information Theory and

Applications Workshop (ITA), 6-11 Feb. 2011, La Jolla, CA, ISBN 978-1-

4577-0360-7, pp 1-10.

[68] Qin Huang, Qiuju Diao, Shu Lin, Abdel-Ghaffar. K. (2012), “Cyclic and

Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their

Trapping Sets”, IEEE Transactions on Information Theory, ISSN 0018-

9448, Vol. 58, No. 5, pp 2648 - 2671.

[69] Rudolf Lidl, Harald Neiderreiter (1983), Finite Fields, Addision-Wesley

Publishing Company.

[70] Shannon C. E. (1948), A mathematical theory of communication, Bell Syst Tech J.

[71] Shum. K.W., Hanxu Hou, Minghua Chen, Huanle Xu, Hui Le (2014),

“Regenerating codes over a binary cyclic code”, 2014 IEEE International

Symposium on Information Theory (ISIT), June 29 2014-July 4 2014, pp.

1046 – 1050.

[72] Siemens (1998), A new correlation sequence for the Primary Synchronisation Code

with good correlation properties and low detector complexity, Tdoc SMG2 UMTS-

L1 427/98, Oct. 14-16

[73] Suwen Wu, Jinkang Zhu, Ling Qiu, Ming Zhao (2010), “Network-coding-

based coded cooperation”, Journal of Communications and Networks, Vol 12

(4), 2010, pp. 366 - 374.

[74] Todd K. Moon (2005), Error Correction Coding: Mathematical Methods and

Algorithm, John Wiley & Sons, Inc, 2005.

[75] Townsend R. L and Weldon E. J., Jr. (1967), "Self-orthogonal quasi-cyclic

codes", IEEE Trans. Inform. Theory, vol. IT-13, no. 2, pp. 183-195.

[76] Vucetic, B., Yonghui Li, Perez, L.C, Fan Jiang (2007), “Recent Advances in

Turbo Code Design and Theory”, Proceedings of the IEEE, June 2007, ISSN

0018-9219, Vol. 95, No. 6, pp 1323-1344.

118

[77] Weldon E. J, Peterson W. W. (1972), Error correcting codes, M.I.T. Press.

[78] Vega. G., Morales. L.B. (2013), “A General Description for the Weight

Distribution of Some Reducible Cyclic Codes”, IEEE Transactions

on Information Theory, ISSN 0018-9448, Vol. 59, No. 9, pp 5994 – 6001.

[79] Yan Jia, San Ling, Chaopin Xing (2011), “On Self-Dual Cyclic Codes over

Finite Fields”, IEEE Transactions on Information Theory, ISSN 0018-9448,

57(4), 2243 - 2251.

[80] Zeh. A., Bezzateev. S. (2012), “Describing a cyclic code by another cyclic

code”, 2012 IEEE International Symposium on Information Theory (ISIT),

ISSN 2157-8095, 1-6 July 2014, pp. 2896 - 2900.

[81] Zeh. A., Wachter-Zeh. A., Bezzateev. S.V. (2012), “Decoding Cyclic Codes

up to a New Bound on the Minimum Distance”, IEEE Transactions

on Information Theory, ISSN 0018-9448, Vol. 58, No. 6, pp 3951-3960.

[82] Zeh. A., Wachter-Zeh. A., Bezzateev. S.V. (2013), “Generalizing bounds on

the minimum distance of cyclic codes using cyclic product codes”, 2013 IEEE

International Symposiom on Information Theory Proceedings, ISSN 2157-

8095, pp 126-130.

119

PHỤ LỤC

Phụ lục 1: Phân bố đa thức theo cấp đa thức trên vành 𝒁𝟐[𝒙]/(𝒙𝒏 + 𝟏)

(không bao gồm đa thức lũy đẳng nuốt)

Vành Cấp của đa

thức

Số lượng đa thức theo cấp

Tổng số đa thức

Xác suất chọn đa thức đạt cấp cực đại

n = 5

0.533

126

n = 7

0.952

510

n = 9

0.565

2046

n = 11

0.587

n = 13

8190

1 3 5 15 1 7 1 3 7 9 21 63 1 3 11 31 33 93 341 1023 1 3 5 7 9 13 15 21 35 39 45 63 65 91 105

2 4 8 16 6 120 6 24 24 48 120 288 2 4 20 60 40 120 600 1200 2 4 8 12 12 24 16 24 48 48 48 72 96 144 96

120

Vành Cấp của đa

thức

Số lượng đa thức theo cấp

Tổng số đa thức

Xác suất chọn đa thức đạt cấp cực đại

0.422

n = 15

32766

0.959

n = 17

131070

0.848

n = 19

524286

117 195 273 315 455 585 819 1365 4095 1 3 5 15 1 3 5 15 17 51 85 255 1 3 7 9 19 21 27 57 63 73 133 171 189 219 399 511 513 657 1197 1387 1533

144 192 288 288 576 576 864 1152 3456 30 480 832 31424 6 24 64 416 640 4736 14080 111104 2 4 12 12 36 24 36 72 72 144 216 216 216 288 432 864 648 864 1296 2592 1728

121

Vành Cấp của đa

thức

Số lượng đa thức theo cấp

Tổng số đa thức

Xác suất chọn đa thức đạt cấp cực đại

0.534

n = 21

2097150

0.881

8388606

n = 23

0.998

33554430

n = 25

1971 3591 4161 4599 9709 12483 13797 29127 37449 87381 262143 1 3 7 9 21 63 1 23 89 2047 1 3 5 11 15 25 31 33 41 55 75 93 123 155 165 205 275 341 451 465 615

2592 3888 5184 5184 15552 15552 15552 31104 46656 93312 279936 62 448 16320 2688 230976 1846656 6 1144 16192 8371264 6 24 64 40 416 240 120 200 160 560 1680 600 800 1680 4000 2240 2400 1200 1600 12000 16000

122

Vành Cấp của đa

Số lượng đa thức theo cấp

Tổng số đa thức

thức

Xác suất chọn đa thức đạt cấp cực đại

0.601

n = 27

134217726

775 825 1023 1025 1271 1353 1705 2255 2325 3075 3813 5115 6355 6765 8525 11275 13981 19065 25575 31775 33825 41943 69905 95325 209715 349525 1048575 1 3 7 9 19 21 27 57 63 73 133 171 189 219 399

7200 16800 6000 9600 4800 8000 16800 22400 50400 67200 24000 120000 67200 160000 72000 96000 48000 480000 504000 288000 672000 240000 672000 2016000 4800000 2880000 20160000 14 112 240 672 144 3504 1440 1584 28224 576 3888 11232 63072 6336 60912

123

Vành Cấp của đa

thức

Số lượng đa thức theo cấp

Tổng số đa thức

Xác suất chọn đa thức đạt cấp cực đại

511 513 657 1197 1387 1533 1971 3591 4161 4599 9709 12483 13797 29127 37449 87381 262143

15552 25920 44928 502848 10368 243648 103680 1135296 114048 2011392 279936 808704 4541184 4385664 1866240 36205056 81741312

0.609

Phụ lục 2: Xác suất chọn đa thức có cấp cực đại trên vành đa có hai lớp kề

cyclic với 35 giá trị đầu tiên của

2n-1 – 1

p(n)

𝒏

3 3 5 15 11 1023 13 4095 19 262143 29 268 435455

TT 1 2 3 4 5 6

68719 476735

~0,5 ~0,5 ~0,586 ~0,42 ~0,534 ~0,494 ~0,378

4503 599627 370495

~0,529

288230 376151 711743

~0,65

1152921 504606 846975

~0,35

73786976 294838 206463

~0,53

Phân tích nguyên tố 3 3.5 3.11.31 3.3.5.7.13 3.3.3.7.19.73 3.5.29.43.113.127 3.3.3.5.7.13.19.37.73. 109 3.5.53.157.1613.2731. 8191 3.59.233.1103.2089.3 033169 3.3.5.5.7.11.13.31.41. 61.151.331.1321 3.3.7.23.67.89.683.12 503333503

124

TT

2n-1 – 1

𝒏

4835703 278458 516698 824703

p(n) ~0,658

~0,45

101

1267650 600228 229401 496703 205375

~0,66

107

~0,575

131

81129638 414606 681695 789005 144063 1361129467 683753 853853 498429 727072 845823

Phân tích nguyên tố 3.83.19420495094 210910 437047 3.5.5.5.11.31.41.101.2 51.601.1801.4051.217 5126601 3.107.6361.39732794 621531167436196823 3.11.31.131.2731.3 719039 635089 626747 719861 3.3.7.47.139..

~0,559

139

~0,530

163

3.3.3.3.3.7.19.73.163. 1467.2593… 3.5.173.431…

~0,529

173

3.179…

~0,663

179

~0,315

348449 143727 040986 586495 598010 130648 530943 5846006 549323 611672 814739 330865 132078 623730 171903 5986310706 507378 352962 293074 805895 248510 699696 029695 383123 885216 472214 589586 756787 577295 904684 780545 900543 1532495 540865 888858 358347 027150 309183 618739 122183 602175

181

~0,492

197

~0,377

211

3.3.3.5.5.7.11.13.19.3 1.37.41.61.73.109.151 .181.331.631.1321… 3.5.29.43.113.127.197 … 3.3.5.7.7.11.31.43.71. 127.151.211.281.331. 337.5419… 3.227.3391…

~0,664

227

3.5.269…

~0,531

269

3.5.293.439.9929…

~0,530

293

3.5.317.2687…

~0,532

317

3.347.4153…

~0,665

347

100433 627766 186892 221372 630771 322662 657637 687111 424552 206335 1645 504557 321206 042154 969182 557350 504982 735865 633579 863348 609023 107839786 668602 559178 668060 348078 522694 548577 690162 289924 414440 996863 474284397 516047 136454 946754 595585 670566 993857 190463 750305 618264 096412 179005 177855 7957171782 556586 274486 115970 349133 441607 298412 757563 479047 423630 290551 952200 534008 528895 133499 189745 056880 149688 856635 597007 162669 032647 290798 121690 100488 888732 861290 034376 435130 433535 143343663 499379 469475 676305 956380 433799 785311 823017 570233

125

TT

Phân tích nguyên tố

p(n)

𝒏

~0,445

3.3.5.7.13.59.233.349. 1103.2089.4177…

349

~0,531

3.5.389.971.1553.388 1.4657.5821.11447...

389

3.23.89.419...

~0,629

419

~0,318

421

3.3.5.5.7.11.13.29.31. 41.43.61.71.113.127.1 51.211.281.331.337.4 21.1321.1429.5419…

~0,665

3.443.1327.2731.8191 …

443

~0,444

3.5.5.11.31.41.47.277. 461.691.1013.1657.14 951…

461

3.467.1399…

~0,665

467

~0,557

3.11.31.43.71.127.281 .491.1471…

491

2n-1 – 1 599302 461682 679755 530300 504376 159569 382855 409663 573374653 997517 877902 705223 825521 735199 141247 292070 280934 397209 846730 719022 121202 017504 638277 531421 638655 630432099 142311 667396 464641 602297 820881 275828 327447 146687 172694 467931 548343 955369 782628 260078 158650 252906 047844 909055 676921 312041 214565 326761 275425 557544 784286 395355 423968 547480 366360 991530 225982 818124 993751 490268 451683 933401 113623 918903 558143 2707685 248164 858261 307045 101702 230179 137145 581421 695874 189921 465443 966120 903931 272499 975005 961073 806735 733604 454495 675614 232575 11356855 067118 857664 833184 498250 070849 275646 260739 344691 898284 362197 488876 771842 551971 735167 402555 711886 914400 097909 030211 478150 447103 2977131 414714 805823 690030 317109 266572 712515 013375 254774 912983 855843 898524 112477 893944 078543 723575 564536 883288 499266 264815 757728 270805 630975 190536410 541747 572716 161940 294993 060653 600960 856016 305594 430966 774009 505543 198585 212421 026798 308836 130360 530463 953040 948208 494609 331560 382463 3196670515 523576 044934 755563 308202 297086 564498 088930 458479 776726 656380 660551 439995 003193 449537 015778 467662 777468 320381 844938 727095 591204 153641 140223

126

Phụ lục 3: Bảng khảo sát các mã cyclic cục bộ xây dựng trên nhóm nhân

VĐT mã

(0 1 2), (1 3),

(0 1 2 4) (0 1 3)

(2 3),

(0 1 2 3 5)

(0 2 3 4) (0 2 3)

(0 1 3), (0 2

3), (0 3 4), (2

3 4), (0 1 2 3

(1 2), (1 2 3 5)

(0 1 3 )

(0 1 2 4)

(0 2 3)

(0 2 3 4)

(3 4), (0 2 3

4), (1 2 3 4)

(0 3 6)

(0 3)

(1 4)

(1 2 4)

(0 1 4 6) (0 2 4 5 8 9 10 12 13 14 15) (0 4 5 8 10 12 13 14 15 16) (0 1 5)

(0 1 2 4)

(1 4 5), (2 4 5)

(0 1 2 3 5

(0 2 3 6 8 11 12)

6 7 9)

(1 4 5 6), (2 4

(0 1 3 6

(0 2 4 5 6 7 9 11 12 13)

5 6)

(0 1)

0 1 2 3 4 5 6 7 9 11 13 15 16 19 20 23 27 31 32 33 34 39 41 47 48 55

(0 1 2)

(0 7 8) (0 2 6 7) 0 1 2 3 4 6 7 8 9 12 13 14 16 18 19 24 26 27 28 32 33 35 36 38 41 45

48 49 52 54 56

(0 1 3)

(0 1 2 3 4

0 1 2 4 5 6 7 8 10 16 17 20 23 24 26 27 28 29 32 33 34 38 40 41 42

6 8 9)

45 49 53 54

(0 1 4)

(0 2 3 5 6

0 1 3 5 7 8 9 12 13 18 22 24 27 29 30 33 36 37 38 40 41 43 44 45 46

50 51 52 53 54 56

(0 1 3 4)

(0 1 2 5

0 1 2 3 6 9 11 13 16 17 19 24 28 30 31 33 34 35 36 37 38 40 42 43

44 48 49 52 53 54 56 57

(0 2 3 4)

(0 2 4 7) 0 3 5 6 7 9 10 11 12 14 17 18 20 22 24 25 27 28 33 34 35 36 37 40

44 45 48 49 50 54 56

(0 1 2 3 4)

(0 2 8 9) 0 1 2 3 4 5 6 8 9 10 11 12 13 16 17 18 19 20 22 24 25 26 27 32 33 34

36 37 38 40 41 44 45 48 50 52 54

(1 2 3 5)

(0 1 8)

0 7 8 14 16 21 22 23 24 28 32 35 36 39 40 42 44 46 48 49 50 51 52

53 54 55

cyclic trên phân hoạch vành đa thức và mã cyclic tương ứng

VĐT mã

(0 1)

0 1 4 5 11 13 16 17 19 20 22 23 24 25 26 27 28 29 30 31 33 34 35 37

(0 1 2 7 8 9 10)

38 39 40 41 42 45 46 47 49 50 52 53 55 57 59 61 63 64 66 69 71 73

77 79 80 82 83 85 86 89 90 93 94 96 97 101 102 105 106 107 108

111 114 117 121 125 128 133 137 139 143 144 145 149 150 151 152

157 158 159 165 166 167 168 171 172 173 174 176 181 183 189 191

192 193 194 195 196 198 200 201 202 204 206 207 213 214 221 222

224 226 228 229 232 234 235 238 245 253 256 257 260 264 265 267

268 269 277 278 279 280 281 282 283 284 288 292 293 294 295 297

298 300 309 311 313 315 320 321 322 323 325 327 328 330 331

(0 1 2)

(0 5 8 9

0 1 4 5 6 9 11 13 15 16 20 22 25 26 27 30 31 32 33 34 35 36 37 38

10 11)

40 42 44 45 47 55 57 58 63 65 66 68 70 71 72 73 74 75 76 77 84 88

89 90 91 92 93 97 99 100 101 105 110 111 112 113 114 115 116 118

119 120 121 122 125 126 128 129 130 131 132 134 135 139 140 142

143 146 147 148 150 151 152 153 154 155 158 159 160 161 163 165

168 169 170 171 174 176 177 179 182 184 186 187 190 191 192 193

194 196 198 199 200 206 208 209 210 212 216 220 226 228 230 231

232 233 238 239 241 242 243 244 248 249 253 254 257 258 261 262

263 264 270 271 272 274 275 276 278 281 282 283 285 286 288 290

291 293 295 297 299 301 302 303 305 306 307 308 310 311 314 315

319 321 322 325 330

127

VĐT mã

(0 1 3)

0 1 4 5 7 8 9 10 14 18 20 22 23 24 25 26 27 29 35 36 40 41 42 44 46

(0 1 2 4 8 9 10 11)

49 50 54 55 62 64 67 68 69 70 71 74 75 77 81 82 83 86 88 89 93 95

97 99 101 105 109 110 111 112 113 115 118 120 121 124 125 126

127 128 129 130 133 135 137 138 139 141 146 147 150 154 156 157

158 160 162 164 165 168 175 179 180 182 187 190 191 192 194 197

198 201 202 205 207 208 210 217 218 220 221 225 234 237 238 243

244 246 248 249 250 252 253 255 258 259 260 261 264 265 269 272

274 276 279 281 282 283 286 288 291 296 297 299 300 301 303 304

305 307 308 312 313 315 317 319 320 321 325 327 328 330 332 334

336 337 339 340 341 343 345 346 347 350 351 352 353 357 358 360

361 362 363 364 366 367 368 370 373 376 377 380 383 384 385 386

388 389 392 395 397 401 402 403 404 409 410 411 413 417 418 421

422 423 424 426 429 430 431 434 435 438 439 440 445 446 451 457

459 460 461 468 469 470 471 474 477 481 484 490 491 492 494 495

497 498 501 503 504 505 506 507 509 511 512 513 514 517 519 520

521 523 524 525 526 527 530 535 539 544 546 550 552 555 557 559

560 565 567 569 575 578 581 583 584 586 587 589 591 596 597 598

602 605 606 607 608 609 610 613 614 615 616 617 619 620 625 626

627 628 629 630 632 633 635 637 638 640 643 645 648 649 651 654

655 657 658 661 662 663 665 667 668 671 672 674 676 679 682 685

686 687 691 692 695 697 702 704 705 707 708 709 710 711 712 713

715 716 717 718 719 720 724 726 734 735 736 739 740 741 744 747

748 750 751 752 755 759 760 761 763 764 765 766 769 770 771 773

774 775 778 779 781 782 784 785 787 788 789 790 792 796 799 800

802 804 805 809 810 811 812 813 814 815 816 824 826 827 830 832

834 836 837 838 839 841 842 843 844 846 847 849 850 851 856 859

861 862 863 864 870 875 876 877 878 880 881 882 886 887 888 894

895 897 900 904 905 909 911 912 913 914 915 916 917 918 919 921

923 925 928 929 930 932 933 936 937 943 944 945 946 947 951 952

953 954 956 958 959 961 962 968 970 972 973 975 977 978 979 980

981 986 988 989 990 991 993 995 999 1000 1002 1003 1005 1009

1011 1012

128

VĐT mã

(0 1 2 4)

(0 1 4 5 6

0 1 7 8 9 10 11 12 14 15 18 19 21 24 27 29 31 32 33 34 35 38 39 40

7 8 9 10)

42 48 49 50 53 55 56 58 61 63 66 68 69 73 74 76 78 79 81 82 84 85

86 93 94 96 97 100 101 102 106 110 112 115 122 123 124 126 129

130 132 133 134 136 138 141 142 143 144 145 148 152 156 157 161

164 165 166 167 170 171 179 180 181 182 186 187 192 194 195 196

197 198 199 202 203 205 206 211 215 216 217 218 220 223 227 228

230 231 232 235 236 239 240 244 245 248 249 250 252 253 254 258

259 261 262 264 266 267 272 273 274 276 277 278 279 280 282 283

285 287 289 293 294 296 301 302 304 307 308 309 310 312 314 319

320 321 325 326 327 329 331 333 335 336 337 338 340 342 343 344

347 348 349 350 351 352 358 359 362 363 365 366 367 368 371 374

379 380 381 382 383 385 386 387 390 392 394 395 398 401 402 404

406 407 408 410 412 413 414 415 416 417 418 419 420 421 423 424

425 426 427 428 430 432 434 435 437 438 439 441 442 446 447 448

451 452 454 456 460 462 463 470 472 473 474 477 480 481 482 485

486 487 490 495 498 499 501 502 504 505 507 515 518 522 524 525

526 527 532 533 537 538 539 540 541 542 543 545 548 549 550 552

553 555 558 559 563 565 567 568 569 574 575 576 577 579 580 581

582 586 588 592 601 603 608 614 615 617 619 621 622 623 625 626

628 629 630 631 632 637 639 642 643 644 649 652 654 655 656 658

659 660 662 663 664 665 667 668 669 671 674 676 677 678 679 681

682 684 685 688 694 696 697 699 701 704 707 708 711 712 713 714

716 717 723 726 727 728 730 732 733 736 737 738 739 740 742 747

749 750 753 754 757 759 762 763 765 769 771 773 780 784 787 789

793 794 795 801 803 805 806 808 812 813 816 820 821 822 824 825

828 830 831 834 836 838 840 842 845 847 849 852 853 856 859 861

862 864 865 866 867 869 873 876 877 882 883 885 886 887 888 889

890 891 894 896 897 898 902 904 905 906 908 912 913 914 915 916

920 923 926 929 930 931 932 933 934 935 936 940 941 942 943 946

948 954 959 961 963 965 966 970 972 973 975 976 980 985 986 989

991 992 993 994 995 997 999 1000 1002 1004 1005 1006 1007 1010

1011 1012 1013

129

130

Phụ lục 4: Số mersenne và một số vành đa thức có hai lớp kề cyclic có

- Mersenne prime: 2𝑝 − 1

𝑝 = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 52, 607, 1279, 2203,

3217, 4253, 9689, 9941, 19937, …, 74207281.

- PR’s with two cyclotomic cosets

𝑛 = 5, 11, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, …, 523,

613, 1277, 2213, 3203, 3253, 4253, …, 9941

cấu trúc đặc biệt

131

Ví dụ 5.1p: Mã LCC đơn nhịp với nhịp

Phụ lục 5: Một số sơ đồ mã hóa và giải mã cyclic cục bộ

Từ mã của mã này có thể được mô tả như hình 5.1.

Hình 5.1p: Từ mã của LCC với nhịp x

Sơ đồ mã hóa được trình bày trong hình 5.2p.

Chú ý: Biểu diễn nhị phân của một số là tương ứng với một đa thức, chẳng

hạn như

Hình 5.2p: Sơ đồ mã hóa cho mã LCC đơn nhịp (15,5,7) với nhịp x

Sơ đồ giải mã ngưỡng được trình bày trong hình 5.3p.

Hệ tổng kiểm tra trực giao với cặp dấu Hệ thổng kiểm tra trực giao với dấu mã

(12) tại mức ngưỡng đầu tiên (1) tại mức ngưỡng thứ hai

S1’ = (1.2) + 2 S1 = 1 + 2

S2’ = (2.4) + 7 S2 = 7 + 4

S3’ = (4.8) + 13 S3 = 25 + 26

S4’ = (8.6) + 25 S4 = 19 + 16

S5’ = (16.1) + 16 S5 = 11 + 8

S6’ = (1.2) + (2.4) + 4 S6 = 13 + 14

132

S7’ = (2.4) + (4.8) +11 S7 = 21 + 22

Ví dụ 5.2p: Mã LCC đơn nhịp với nhịp (024):

Hình 5.3p: Sơ đồ giải mã cho mã LCC đơn nhịp (15,5,7) với nhịp x

Sơ đồ mã hóa và bộ tạo nhịp (clock) được trình bày trong hình 5.4 và 5.5.

Hình 5.4p: Sơ đồ mã hóa cho mã LCC đơn nhịp (15,5,7) với nhịp (024)

133

Hình 5.5p: Bộ tạo nhịp (clock)

Sơ đồ giải mã ngưỡng được trình bày trong hình 5.6p.

Hình 5.6p: Sơ đồ giải mã ngưỡng cho mã LCC đơn nhịp (15,5,7) với nhịp (024)

Ví dụ 5.3p: Mã LCC đa nhịp

Từ mã của mã này có thể được mô tả như hình 5.7p.

Hình 5.7p: Từ mã của LCC đa nhịp (15,5,7)

Sơ đồ mã hóa của mã này được trình bày trong hình 5.8p.

Hình 5.8p: Sơ đồ mã hóa cho mã LCC đa nhịp (15,5,7)

134

Sơ đồ giải mã ngưỡng của mã này được trình bày trong hình 5.9p.

Hình 5.9p: Sơ đồ giải mã cho mã LCC đa nhịp (15,5,7)

Tốc độ nhịp của thanh ghi B bằng hai lần tốc độ nhịp của thanh ghi A và D.

Tốc độ nhịp của thanh ghi C bằng ba lần tốc độ nhịp của thanh ghi A và D.

Tốc độ cơ sở là căn nguyên thủy thứ n của 1 ( )

135

Phụ lục 6: Phương pháp thực hiện bộ mã cyclic trên cấu kiện phần cứng