Luận án Nhóm nhân cyclic và mã cyclic trên vành đa thức

BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
NGUYỄN TRUNG HIẾU 
NHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊN 
VÀNH ĐA THỨC 
LUẬN ÁN TIẾN SĨ KỸ THUẬT 
HÀ NỘI – 2017 
BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
NGUYỄN TRUNG HIẾU 
NHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊN 
VÀNH ĐA THỨC 
 CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ 
 MÃ SỐ: 9520203 
LUẬN ÁN TIẾN SĨ KỸ THUẬT 
NGƯỜI HƯỚNG DẪN LUẬN ÁN: 
 1. GS.TS. NGUYỄN BÌNH 
 2. TS. NGUYỄN NGỌC MINH 
HÀ NỘI – 2017 
i 
LỜI CAM ĐOAN 
Tôi xin cam đoan đây là công trình nghiên cứu của tôi, các số liệu và kết 
quả trình bày trong luận án là trung thực và chưa được công bố ở bất kỳ công 
trình nào khác. 
 Tác giả 
 Nguyễn Trung Hiếu 
ii 
LỜI CẢM ƠN 
Luận án Tiến sĩ kỹ thuật này được thực hiện tại Học viện Công nghệ Bưu 
chính Viễn thông dưới sự hướng dẫn của GS.TS. Nguyễn Bình và TS. Nguyễn Ngọc 
Minh. Nghiên cứu sinh bày tỏ lòng biết ơn sâu sắc tới GS.TS. Nguyễn Bình, thầy 
trực tiếp hướng dẫn, giúp đỡ, cung cấp những kiến thức quý báu và có rất nhiều ý 
kiến gợi mở về hướng nghiên cứu để nghiên cứu sinh thực hiện thành công đề tài. 
Nghiên cứu sinh cũng xin chân thành cảm ơn TS. Nguyễn Ngọc Minh, người lãnh 
đạo trực tiếp đã luôn ủng hộ, giúp đỡ nghiên cứu sinh trong quá trình nghiên cứu. 
Nghiên cứu sinh xin dành lời cảm ơn sâu sắc tới các Thầy giáo, nhà khoa học trong 
Hội đồng bảo vệ Luận án các cấp, các buổi hội thảo luận án đã nhiệt tình chỉ bảo, 
giúp đỡ và có nhiều góp ý quý báu giúp nghiên cứu sinh hoàn thiện luận án. 
Tôi cũng xin cảm ơn Ban giám đốc Học viện Công nghệ Bưu chính Viễn 
thông, Khoa Quốc tế và Đào tạo Sau đại học, Khoa Kỹ thuật Điện tử 1 (nơi tôi đang 
công tác), cũng như các đồng nghiệp đã tạo điều kiện và giúp đỡ tôi hoàn thành 
được đề tài nghiên cứu của mình. 
Cuối cùng là sự biết ơn tới gia đình, bạn bè đã thông cảm, động viên giúp đỡ 
cho tôi có đủ nghị lực để hoàn thành luận án. 
 Hà Nội, tháng 12 năm 2017 
iii 
MỤC LỤC 
LỜI CAM ĐOAN ................................................................................................................ I 
LỜI CẢM ƠN .................................................................................................................... II 
DANH MỤC CÁC TỪ VIẾT TẮT ................................................................................... V 
DANH MỤC CÁC KÝ HIỆU ......................................................................................... VII 
DANH MỤC CÁC BẢNG ............................................................................................... IX 
DANH MỤC CÁC HÌNH VẼ ........................................................................................... X 
MỞ ĐẦU ............................................................................................................................ 1 
1. LÝ DO NGHIÊN CỨU ................................................................................... 1 
2. MỤC ĐÍCH NGHIÊN CỨU ............................................................................ 1 
3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU ................................................. 2 
4. PHƯƠNG PHÁP VÀ CÔNG CỤ NGHIÊN CỨU .......................................... 2 
5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI .............................. 2 
6. CẤU TRÚC CỦA LUẬN ÁN ......................................................................... 3 
CHƯƠNG 1: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU .............................................. 5 
1.1. GIỚI THIỆU CHUNG .................................................................................. 5 
1.2. VÀNH ĐA THỨC ........................................................................................ 7 
1.2.1. Một số khái niệm cơ bản ..................................................................... 7 
1.2.2. Chu trình và lũy đẳng ........................................................................ 10 
1.3. MÃ TUYẾN TÍNH ..................................................................................... 13 
1.3.1. Mã cyclic truyền thống ...................................................................... 13 
1.3.2. Một số mã tuyến tính khác ................................................................ 16 
1.3.3. Một số tiêu chuẩn đánh giá mã tuyến tính ........................................ 18 
1.4. PHÂN HOẠCH VÀNH ĐA THỨC VÀ MÃ CYCLIC CỤC BỘ ............. 19 
1.4.1. Nhóm nhân cyclic .............................................................................. 19 
1.4.2. Cấp số nhân cyclic ............................................................................. 24 
1.4.3. Phân hoạch vành đa thức ................................................................... 24 
1.4.4. Mã cyclic cục bộ trên vành đa thức ................................................... 31 
1.5. HƯỚNG NGHIÊN CỨU CỦA LUẬN ÁN VÀ MỘT SỐ KẾT QUẢ LIÊN 
QUAN.......................................................................................................... 34 
1.6. KẾT LUẬN CHƯƠNG .............................................................................. 37 
CHƯƠNG 2: CẤP CỦA ĐA THỨC VÀ QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, 
CẤP SỐ NHÂN CYCLIC VỚI MÃ CYCLIC TRUYỀN THỐNG ................................. 39 
2.1. GIỚI THIỆU ............................................................................................... 39 
iv 
2.2. XÁC ĐỊNH CẤP CỦA ĐA THỨC ............................................................ 40 
2.2.1. Đề xuất phương pháp xác định cấp của tích các đa thức .................. 40 
2.2.2. Đề xuất phương pháp xác định cấp của nhị thức .............................. 45 
2.2.3. Đề xuất thuật toán cải tiến để tìm và liệt kê cấp của đa thức trên 
vành ................................................................................................... 51 
2.2.4. Xác suất chọn đa thức có cấp cực đại ............................................... 56 
2.3. QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC 
VỚI MÃ CYCLIC TRUYỀN THỐNG ...................................................... 58 
2.3.1. Cơ sở toán học ................................................................................... 58 
2.3.2. Sự tương đương của nhóm nhân cyclic, cấp số nhân cyclic với mã 
cyclic truyền thống ............................................................................ 60 
2.3.3. Thuật toán xác định nhóm nhân cyclic tương đương mã cyclic truyền 
thống .................................................................................................. 63 
2.4. MỘT CÁCH PHÂN LOẠI MÃ TUYẾN TÍNH MỚI ................................ 69 
2.5. KẾT LUẬN CHƯƠNG .............................................................................. 73 
CHƯƠNG 3: ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC ......... 75 
3.1. PHƯƠNG PHÁP XÂY DỰNG MÃ CYCLIC ........................................... 75 
3.1.1. Phương pháp xây dựng mạch mã hóa ............................................... 75 
3.1.2. Phương pháp xây dựng mạch giải mã ............................................... 77 
3.2. ĐỀ XUẤT MỘT SỐ MÃ CYCLIC TỐT TRÊN VÀNH ĐA THỨC ........ 79 
3.2.1. Phương pháp tìm mã cyclic tốt .......................................................... 79 
3.2.2. Mô phỏng, đánh giá một số bộ mã cyclic tốt .................................... 90 
3.2.3. Đề xuất thực hiện các bộ mã trên FPGA ........................................... 95 
3.3. ĐỀ XUẤT PHƯƠNG PHÁP TẠO KHÓA CHO MỘT SỐ HỆ MẬT ...... 97 
3.3.1. Quan hệ giữa vành đa thức có hai lớp kề cyclic và trường số .......... 97 
3.3.2. Hệ mật Omura-Massey trên vành đa thức có hai lớp kề cyclic ...... 100 
3.4. KẾT LUẬN CHƯƠNG ............................................................................ 105 
KẾT LUẬN ..................................................................................................................... 107 
CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ................................................... 108 
TÀI LIỆU THAM KHẢO .............................................................................................. 110 
PHỤ LỤC........................................................................................................................ 119 
v 
DANH MỤC CÁC TỪ VIẾT TẮT 
Từ viết tắt Nghĩa tiếng Anh Nghĩa tiếng Việt 
BCH Bose, Chaudhuri, and 
Hocquenghem 
(Tên ba tác giả nghiên cứu ra 
mã BCH) 
CGP Cyclic Geometic Progressions Cấp số nhân cyclic 
CMG Cyclic Multiplicate Group Nhóm nhân cyclic 
CRC Cyclic Redundancy Check Kiểm tra dư thừa vòng 
ECC Error Correcting Code Mã sửa lỗi 
FPGA Field Programable Gate Array Mảng cổng logic khả trình 
MTD Majority-based Threshold 
Decode 
Giải mã ngưỡng theo đa số 
LCC Local Cyclic Code Mã cyclic cục bộ 
OALCC Orthogonalable Local Cyclic 
Code 
Mã cyclic cục bộ có khả năng 
trực giao 
OLCC Orthogonal Local Cyclic Code Mã cyclic cục bộ tự trực giao 
LDPC Low-Density Parity Check Mã kiểm tra chẵn lẻ mật độ 
thấp 
LTE Long Term Evolution Tiến hóa dài hạn 
RSMA Repeated Square and Multiply 
Algorithm 
Thuật toán nhân và bình 
phương lặp 
STBC Space-Time Block Code Mã khối không gian-thời gian 
TCM Trellis Coded Modulation Điều chế mã lưới 
CS Check-sum Tổng kiểm tra 
vi 
OACS Orthogonalable check-sum Tổng kiểm tra có khả năng trực 
giao 
OCS Orthogonal check-sum Tổng kiểm tra trực giao 
VHDL VHSIC Hardware Discription 
Language 
Ngôn ngữ mô tả phần cứng 
WCDMA Wideband Code Division 
Multiple Access 
Đa truy nhập phân chia theo mã 
băng rộng 
vii 
DANH MỤC CÁC KÝ HIỆU 
Ký hiệu Nghĩa tiếng Anh Nghĩa tiếng Việt 
C Set of cycles Tập hợp các chu trình 
SC Cycle Chu trình 
0d Hamming distance Khoảng cách Hamming 
deg Degree Bậc của đa thức 
( )e x Idempotent Đa thức lũy đẳng 
0 ( )e x Swallowing Idempotent Lũy đẳng nuốt 
 Field Trường 
G Group Nhóm 
( )GF p Galois Field Trường Galois 
gcd Greatest common divisor Ước chung lớn nhất 
I Ideal Ideal 
lcm Least common multiple Bội chung nhỏ nhất 
Mod Modulo Phép chia lấy phần dư 
ord Order Cấp của đa thức 
R Ring Vành 
W Weight Trọng số 
2[ ] / ( 1)
nx x Polynomial for Integer mod 2 Vành đa thức trên 2 
 Intersection Giao 
 Union Hợp 
 Empty set Tập hợp rỗng 
viii 
# hoặc ... Cardinality Lực lượng hay số phần tử 
~ Similarity Tương đương 
 Summation Tổng 
 Non-redundant division Phép chia hết 
| Divisor or divides Ước 
 Not divisor or not divides Không là ước 
... Ceiling Số nguyên nhỏ nhất lớn hơn 
hoặc bằng giá trị trong ngoặc 
ix 
DANH MỤC CÁC BẢNG 
Bảng 1.1. Bảng giá trị của n nhỏ hơn 1000 thỏa mãn 2[ ] / ( 1)
nx x là một vành 
đa thức có 2 lớp kề cyclic ................................................................. 10 
Bảng 1.2. Số kiểu phân hoạch không suy biến M của một số vành ................ 27 
Bảng 1.3. Tổng số các kiểu phân hoạch của vành 
2[ ] / ( 1)
nx x ...................... 28 
Bảng 2.1. Bảng khảo sát cấp của đa thức 1 x trên một số vành đa thức................ 48 
Bảng 2.2. So sánh thời gian tính toán của hai thuật toán ................................... 54 
Bảng 2.3. Kết quả khảo sát 35 giá trị n ............................................................. 57 
Bảng 3.1. Một số cặp vành có thể phân hoạch hỗn hợp .................................... 84 
Bảng 3.2. Đề xuất một số bộ mã cyclic tốt ........................................................ 89 
Bảng 3.3. Phép toán cộng và nhân trên hai cấu trúc vành đa thức và vành số98 
Bảng 3.4. Các phần tử nghịch đảo tương quan trên trường số và vành đa thức..99 
x 
DANH MỤC CÁC HÌNH VẼ 
Hình 2.1. Biểu đồ so sánh thời gian tính toán của hai thuật toán ...................... 55 
Hình 2.2. So sánh các mã cyclic và mã cyclic cục bộ........................................70 
Hình 2.3. Sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã LCC..72 
Hình 3.1. Phân hoạch vành đa thức có nhóm nhân sinh là nhóm nhân đơn vị .. 76 
Hình 3.2. Phân hoạch vành có nhóm nhân sinh là nhóm nhân cyclic bất kỳ .... 77 
Hình 3.3. Lưu đồ thuật toán tìm bộ mã cyclic tốt xây dựng từ cấp số nhân 
cyclic............................................................................................................ 88 
Hình 3.4. Sơ đồ hệ thống thông tin sử dụng mô phỏng, đánh giá mã cyclic ..... 90 
Hình 3.5. Kết quả mô phỏng bộ mã cyclic (255,9,127) ..................................... 92 
Hình 3.6. Kết quả mô phỏng bộ mã cyclic (15,5,7) ........................................... 93 
Hình 3.7. Kết quả mô phỏng bộ mã cyclic (27,9,9) ........................................... 94 
Hình 3.8. Giao thức truyền thông sử dụng hệ mật O-M .................................. 101 
1 
MỞ ĐẦU 
1. LÝ DO NGHIÊN CỨU 
Lý thuyết mã hóa đã được nghiên cứu từ những năm 1940 và được ứng dụng 
rộng rãi trong nhiều lĩnh vực, đặc biệt là trong lĩnh vực truyền thông góp phần nâng 
cao hiệu quả của hệ thống truyền tin. Một trong các lớp mã quan trọng của mã khối 
tuyến tính đó là các mã cyclic. Mã cyclic có nhiều ứng dụng trong điện tử dân dụng, 
các hệ thống lưu trữ dữ liệu, các hệ thống truyền thông vì có nhiều phương pháp mã 
hóa và giải mã hiệu quả. 
Việc nghiên cứu truyền thống về mã cyclic đã khá hoàn chỉnh, tuy nhiên loại 
mã này có nhược điểm là số lượng từ mã được tạo ra hạn chế, độ dài của mã chỉ cố 
định ở một số giá trị cụ thể. Trong những năm trở lại đây một phương pháp khác để 
xây dựng mã cyclic được nghiên cứu đó là sử dụng nhóm nhân cyclic, cấp số nhân 
cyclic trên vành đa thức, và mã được gọi là mã cyclic cục bộ (LCC- Local Cyclic 
Code). Các nghiên cứu gần đây đã đưa ra một số phương pháp phân hoạch vành đa 
thức, xây dựng mã cyclic cục bộ, cùng các phương pháp giải mã tương đối hiệu quả. 
Nghiên cứu sinh nhận thấy rằng có thể tồn tại mối quan hệ giữa mã cyclic và 
cyclic cục bộ, điều đó thôi thúc nghiên cứu sinh nghiên cứu sâu hơn lý thuyết về mã 
cyclic cục bộ (mã cyclic được xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic), 
tìm hiểu, chứng minh mối quan hệ có thể tồn tại giữa mã cyclic và mã cyclic cục 
bộ. Chính vì lẽ đó, nghiên cứu sinh đã chọn đề tài “Nhóm nhân cyclic và mã cyclic 
trên vành đa thức” để định hướng nghiên cứu luận án tiến sĩ của mình. Trên cơ sở 
kết quả nghiên cứu lý thuyết đạt được sẽ đề xuất một số ứng dụng có thể về mã sửa 
lỗi và mật mã trong các hệ thống truyền thông. 
2. MỤC ĐÍCH NGHIÊN CỨU 
Mục đích chính của luận án là góp phần hoàn thiện lý thuyết và thực nghiệm 
về nhóm nhân cyclic và mã cyclic trên các vành đa thức, trong đó các kết quả nghiên 
cứu đạt được của luận án nhằm giải quyết các vấn đề cụ thể sau: 
2 
- Quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức với 
mã cyclic truyền thống. 
- Phương pháp kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. 
- Đề xuất ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic để tìm một số 
bộ mã cyclic tốt, hay ứng dụng trong các hệ mật. 
3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU 
Đối tượng nghiên cứu ...  
16 (01) 19 (12) 22 (23) 25 (34) 28 (04) 
31 (0) 34 (1) 37 (2) 40 (3) 43 (4) 
P6.2.2. Thiết kế và mô phỏng trên FPGA 
Mô hình thử nghiệm thuật toán mã hóa và giải mã cyclic cục bộ trên vành 
  52 / ( 1)x x tức vành 5 bằng FPGA như hình 6.5p. Mô hình gồm các khối: 
1a 2a 3a 4a 5a 6a 7a 8a 9a 10a 11a 12a 13a 14a 15a
12 15a a 9 12a a 6 9a a 3 6a a 3 15a a 
1+x
M=4
M=4
1
B
A
142 
Coding: Khối mã hóa, thực hiện thuật toán mã hóa cyclic trên vành 5 chuỗi 
thông tin đầu vào 5 bit (dulieuvao), thành từ mã 15 bit (Bi). 
Channel: mô phỏng một kênh truyền đơn giản trong đó từ mã vào (Bi) được 
đánh lỗi ngẫu nhiên, từ mã ra khỏi kênh (Bo) có từ 0 đến 3 bit lỗi. Nguyên lý thiết 
kế: Sử dụng một bộ đếm 15 bit mà đầu ra 15 bit đó có số bit 1 từ 0 đến 3 và vị trí 
xuất hiện ngẫu nhiên. Chuỗi bit đó được cộng modul 2 với từ mã vào (Bi) để làm 
lỗi từ mã từ 0 đến 3 bit. 
DeCoding: Khối giải mã, thực hiện thuật toán giải mã cyclic trên vành 5 
(giải mã ngưỡng) chuỗi từ mã nhận được, tạo ra từ mã thông tin 5 bit dulieura. 
Hình 6.5p: Sơ đồ mô hình thử nghiệm dưới dạng RTL 
a) Thiết kế mạch mã hóa 
Phương án 1: Thiết kế mạch mã hóa giống như sơ đồ lý thuyết tại hình 6.3p. 
Phương án 2: Thiết lập mạch mã hóa theo sơ đồ như hình 6.6p. Thành phần 
mạch bao gồm một thanh ghi lưu trữ thông tin cần mã hóa, các cổng AND và XOR 
để thực hiện. Tiếp theo sẽ trình bày theo phương án 2. 
143 
Nhóm nhân xyclic
x15 x14 x13 x12 x11 x10 x9 x8 x7 x6 x5 x4 x3 x2 x1
d0d1d2d3d4
g0g1g2g3g4
Hình 6.6p: Sơ đồ mã hóa thông tin theo nhóm nhân cyclic 
Thông tin được phát theo nhóm 5 bit, sử dụng mạch mã hóa (15,5), nghĩa là 
mỗi nhóm 5 bit thông tin được mã hóa theo 15 phần tử của nhóm nhân cyclic thành 
15 bit nhị phân và phát đi. Với Di = 0 1 2 3 4d d d d d là nhóm 5 bit thông tin, được mã hóa 
bằng 15 tổ hợp Gi = 0 1 2 3 4g g g g g thông qua cấu trúc mạch mã hóa như hình 6.6p. 
Hoạt động của mạch mã hóa trong 15 nhịp đầu tiên: 
- Nhịp 1: Chuyển nhóm 5 bit thông tin D0 = 0 1 2 3 4d d d d d vào 5 ô nhớ dành cho 
D; chuyển tổ hợp G0 vào 5 ô nhớ dành cho G. Tiến hành các phép toán logic AND, 
XOR tương ứng. Kết quả được 1 bit X1. 
- Nhịp 2: Giữ nhóm 5 bit thông tin D0 trong 5 ô nhớ dành cho D; chuyển tổ 
hợp G1 vào 5 ô nhớ dành cho G. Tiến hành các phép logic, kết quả lưu vào X2. 
- Nhịp 3->15: Làm tương tự như nhịp 2 (giữ nguyên 5 bit thông tin D0), thay 
đổi nội dung trong các ô nhớ G bằng các tổ hợp G2->G14. Kết quả lưu vào X2-> X14. 
Kết quả là từ 5 bit thông tin ban đầu 0 1 2 3 4d d d d d , sau mã hóa thu được dãy 15 
bit phát đi với thứ tự như sau: 
x15 x14 x13 x12 x11 x10 x9 x8 x7 x6 x5 x4 x3 x2 x1
Với cách làm như trên, cứ sau mỗi 15 nhịp ta sẽ mã hóa được 5 bit thông tin 
theo 15 phần tử của nhóm nhân thành dãy 15 bit và phát đi trên đường truyền. Trong 
144 
đó 15 phần tử của nhóm nhân được tìm ra theo phương pháp thực hiện thuật toán 
nhân và bình phương đa thức đã nghiên cứu trong mục P6.1. 
b) Thiết kế mạch giải mã 
Khối DeCoding như trong hình 6.7p, gồm 5 nhánh để thực hiện giải mã song 
song cả 5 bit thông tin Io(0:4). Mỗi nhánh gồm: 
+ Mạch đệm dịch vòng trái “rol” từ mã 15 bit đầu vào b(1:15). Phần dịch vòng 
được thiết kế theo kiểu tổ hợp, nên mạch thực hiện dịch vòng số lần mong muốn 
ngay sau một chu kỳ đồng hồ (1 clk). 
+ Mạch tính tổng kiểm tra “S”: Mạch tổ hợp để tính ra 7 CS cho cấp ngưỡng 
đầu tiên và 7 CS cho cấp ngưỡng 2 theo thuật toán giải mã như ở phần trên. 
+ Mạch giải mã ngưỡng “M”: Thực hiện giải mã ngưỡng để xác định giá trị 
bit thông tin tương ứng. Nguyên lý mạch giải mã ngưỡng “M”: Thiết kế mạch cộng 
logic tổ hợp cho 7 CS, kết quả là m và sử dụng mạch logic tổ hợp so sánh m với 4, 
nếu m ≥ 4 thì bit thông tin ra là 1, ngược lại bit thông tin ra là 0. Cấp ngưỡng thứ 
nhất giải mã ra 5 bit I_t(0:4), cấp ngưỡng thứ hai giải mã ra 5 bit thông tin Io(0:4). 
rol 0
rol 3
rol 6
rol 9
rol 12
S
b0(1:15)
S
b1(1:15)
S
b2(1:15)
S
b3(1:15)
S
b4(1:15)
M
S0(1:7)
M
S1(1:7)
M
S2(1:7)
M
S3(1:7)
M
S0(1:7)
(01)
(12)
(23)
(34)
(04)
(01)(12)(23)(34)(04)
ror 0
ror 1
ror 2
ror 3
ror 4
Sb0(1:15)
Sb1(1:15)
Sb2(1:15)
Sb3(1:15)
Sb4(1:15)
I_t(0:4)
I_t0(0:4)
I_t1(0:4)
I_t2(0:4)
I_t3(0:4)
I_t4(0:4)
M
M
M
M
M
Io(0)
S0(1:7)
S1(1:7)
S2(1:7)
S3(1:7)
S0(1:7)
Io(1)
Io(2)
Io(3)
Io(4)
b(1:15)
Clk
Hình 6.7p: Sơ đồ RTL của mạch khối DeCoding 
145 
Với thiết kế mạch giải mã như vậy tốc độ giải mã là lớn nhất, gần như là tức 
thời, tuy số tài nguyên cổng logic cần sử dụng nhiều nhưng đó lại là ưu thế của 
FPGA vì số lượng cổng logic tương đương rất lớn của nó. Ngoài ra, khi xây dựng 
chương trình có thể cài đặt tham số để ứng với mỗi nhóm nhân cyclic sẽ có mạch 
giải mã tương ứng. 
Hình 6.8p: Kết quả mô phỏng bộ mã cyclic (15, 5) với phần tử sinh (024) 
Toàn bộ các khối được thiết kế theo mô hình mạch mã hóa và giải mã đã được 
trình bày và được mô tả bằng ngôn ngữ mô tả phần cứng VHDL, sau đó được tổng 
hợp và thực hiện bằng FPGA XC3S500E-4CPG132. Kết quả của của quá trình tổng 
hợp, cấu hình và mô phỏng như trong hình 6.8p. Tài nguyên logic được sử dụng chỉ 
ra trong bảng 3.1p. 
Bảng 3.1p: Tài nguyên logic được sử dụng xây dựng bộ mã LCC(15,5) 
Tiện ích Logic Đã sử dụng Hiệu suất 
Số cổng logic 135 2% 
Số tri gơ 6 0% 
146 
Số LUT 4 đầu vào 238 2% 
Số cổng vào/ra (IO) 46 50% 
Số GCLK 1 4% 
Kết quả mô phỏng trên hình 6.8p 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ừ bảng 1p cho thấy 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 độ. 
P6.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 9
2[ ] / ( 1)x x 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. 
P6.3.1. Phương pháp xây dựng bộ mã 
Mã LCC (27, 9) được xây dựng từ 3 cấp số nhân cyclic lấy trong phân hoạch 
vành đa thức 9
2[ ] / ( 1)x x thành các CGP cấp 9. CGP1 chính là nhóm nhân cyclic 
đơn vị (là đa thức thông tin). Chọn CGP6 (trưởng lớp kề là (11)) và CGP29 (trưởng 
lớp là (61)) làm các dấu kiểm tra. 
Cấu trúc từ mã LCC (27, 9) với các dấu mã biểu diễn ở dạng thập phân: 
1 2 4 8 16 32 64 128 256 11 22 44 88 176 352 193 386 261 61 122 244 488 465 419 327 143 286 
Nếu biểu diển mã LCC này theo trưởng lớp kề thì có dạng {1, 11, 61}. 
147 
Trong đó: Lớp kề 1 có trưởng lớp kề là 311 1 x x (CGP6). 
 Lớp kề 2 có trưởng lớp kề là 2 3 4 561 1 x x x x (CGP29). 
Sơ đồ mã hóa cho mã LCC này được trình bày trong hình 6.9p. 
X0 X1 X2 X3 X4
RA
X5 X6 X7 X8
Nhịp 1 ÷ 9
Nhịp 10 ÷ 18
Nhịp 19 ÷ 27
Nhịp 1 ÷ 27
Lớp kề 1
Lớp kề 2
Hình 6.9p: Sơ đồ mã hóa LCC (27, 9, 9) với ba lớp kề {(1), (11), (61)} 
Số nhịp dịch: Đa thức thông tin: 9 nhịp; Lớp kề 1: 9 nhịp; Lớp kề 2: 9 nhịp. 
Tổng cộng sau 27 nhịp thì được toàn bộ từ mã. 
* Giải mã: 
Do đây là mã OLCC nên ta đi xây dựng hệ OCS, giải mã một cấp ngưỡng, cho 
các dấu thông tin: (0), (1), (2),, (7), (8). Cụ thể ta xây dựng hệ OCS cho dấu (0) 
 1, sau đó dịch vòng trong từng lớp kề của từ mã đi một nhịp ta sẽ có OCS của 
dấu (1), và cứ như thế sẽ tìm được tất cả các dấu còn lại. 
 (0) = (1) + (3) + (013) 
 = (2) + (8) + (028) 
 = (4) + (235) + (02345) 
 = (5) + (178) + (01578) 
 = (6) + (7) + (067) 
 = (346) + (01268) + (12348) 
 = (457) + (568) + (04678) 
 = (13456) + (24567) + (01237) 
148 
Trong mã này, khoảng cách Hamming là d0 = 9, sửa được 4 bit lỗi. Sơ đồ giải 
mã LCC (27, 9, 9) với ba lớp kề {(1), (11), (61)} như trên hình 6.10p. 
(457)
(568)
(067)
(178)
(028)
(346)
(124)
(235)
(013)
(3) (4) (5) (6) (7) (8)(1) (2)(0)
M=5
Hình 6.10p: Sơ đồ khối giải mã LCC (27, 9, 9) với ba lớp kề {(1), (11), (61)} 
Hoạt động: 27 nhịp đầu đưa từ mã nhận vào các ô nhớ. 
Nhịp Giải mã Nhịp Giải mã Nhịp Giải mã 
28 (0) 31 (3) 34 (6) 
29 (1) 32 (4) 35 (7) 
30 (2) 33 (5) 36 (8) 
149 
P6.3.2. Thiết kế và mô phỏng trên FPGA 
Mô hình thử nghiệm thuật toán mã hóa và giải mã cyclic cục bộ trên vành 
Z2[x]/x9+1 bằng FPGA như hình 6.11p. 
Hình 6.11p: Sơ đồ mô hình thử nghiệm dưới dạng RTL 
Mô hình gồm các khối: 
- Coding: Khối mã hóa, thực hiện thuật toán mã hóa cyclic trên vành Z9 
chuỗi thông tin vào 9 bit Ii, thành từ mã 27 bit Bi. 
- Channel: mô phỏng một kênh truyền đơn giản trong đó từ mã vào Bi được 
đánh lỗi ngẫu nhiên, từ mã ra khỏi kênh Bo có từ 0 đến 3 bit lỗi. Nguyên 
lý thiết kế: Sử dụng một bộ đếm 27 bit mà đầu ra 27 bit đó có số bit 1 từ 0 
đến 4 và vị trí xuất hiện ngẫu nhiên. Chuỗi bit đó được cộng modul 2 với 
từ mã vào Bi để làm lỗi từ mã từ 0 đến 4 bit. 
- DeCoding: Khối giải mã, thực hiện thuật toán giải mã cyclic trên vành Z9 
(giải mã ngưỡng) chuỗi từ mà Bi nhận được tạo ra từ mã thông tin 9 bit Io. 
a) Thiết kế mạch mã hóa 
Sơ đồ thiết kế mạch mã hóa như hình 6.12p. Thành phần mạch bao gồm một 
thanh ghi lưu trữ thông tin cần mã hóa, các cổng AND và XOR để thực hiện. 
150 
3 Nhóm nhân thuộc 3 lớp kề xyclic
It27 ... It19 It18 ... It10 It9 ... It1
I6I7I8
g0g1g2g3g4
I0I1I2I3I4I5
g0g1g2g3
Hình 6.12p: Sơ đồ mã hóa thông tin theo 3 nhóm nhân thuộc 3 lớp kề cyclic 
Thông tin được phát theo nhóm 9 bit, sử dụng mạch mã hóa LCC (27, 9, 9) 
với ba lớp kề {(1), (11), (61)}, có nghĩa là mỗi nhóm 9 bit thông tin sẽ được mã hóa 
theo 27 phần tử của 3 nhóm nhân thuộc 3 lớp kề cyclic thành 27 bit nhị phân và 
phát đi. Với Ii = 0 1 2 3 4 5 6 7 8I I I I I I I I I là nhóm 9 bit thông tin, sẽ được mã hóa bằng 27 tổ 
hợp Gi = 0 1 2 3 4 5 6 7 8g g g g g g g g g thông qua cấu trúc mạch mã hóa như hình 6.12p. 
Hoạt động của mạch mã hóa như sau: 
27 nhịp đầu tiên: 
- Nhịp 1->9: 9 bit thông tin I0 = 0 1 2 3 4 5 6 7 8I I I I I I I I I vào 9 ô nhớ dành cho I; 
chuyển lần lượt 9 tổ hợp G1-> G9 (theo 9 nhịp) vào 9 ô nhớ dành cho G (với G1÷G9 
là 9 phần tử thuộc nhóm nhân cyclic đơn vị CGP1). Tại mỗi nhịp đồng hồ tiến hành 
các phép toán logic AND, XOR tương ứng. Kết quả là sau 9 nhịp đầu tiên được 9 
bit It1It2It3It4It5It6It7It8It9. 
- Nhịp 10->18: Lưu 9 bit thông tin I0 = 0 1 2 3 4 5 6 7 8I I I I I I I I I vào 9 ô nhớ dành cho 
I; chuyển lần lượt 9 tổ hợp G10-> G18 (theo 9 nhịp) vào 9 ô nhớ dành cho G (với 
G9÷G18 là 9 phần tử thuộc CGP6). Tại mỗi nhịp đồng hồ tiến hành các phép toán 
logic AND, XOR. Kết quả là sau 9 nhịp được 9 bit It10It11It12It13It14It15It16It17It18. 
- Nhịp 19->27: Lưu 9 bit thông tin I0 = 0 1 2 3 4 5 6 7 8I I I I I I I I I vào 9 ô nhớ dành cho 
I; chuyển lần lượt 9 tổ hợp G19-> G27 (theo 9 nhịp) vào 9 ô nhớ dành cho G (với 
151 
G19÷G27 là 9 phần tử thuộc CGP29). Tại mỗi nhịp đồng hồ tiến hành các phép toán 
logic AND, XOR. Kết quả là sau 9 nhịp được 9 bit It19It20It21It22It23It24It25It26It27. 
Kết quả là từ 9 bit thông tin ban đầu 0 1 2 3 4 5 6 7 8I I I I I I I I I , sau mã hóa thu được dãy 
27 bit phát đi với thứ tự như sau: 
It27 ... It19 It18 ... It10 It9 ... It1
Với cách làm như trên, cứ sau mỗi 27 nhịp ta sẽ mã hóa được 9 bit thông tin 
theo 27 phần tử (thuộc 3 nhóm nhân thuộc 3 lớp kề cyclic) thành dãy 27 bit và phát 
đi trên đường truyền. 
b) Thiết kế mạch giải mã 
Khối DeCoding như hình 6.13p, gồm 9 nhánh để thực hiện giải mã song song 
cả 9 bit thông tin Io(0:8). Mỗi nhánh gồm: 
+ Mạch đệm dịch vòng trái “rol” từ mã 27 bit đầu vào b(1:27). Phần dịch vòng 
được thiết kế theo kiểu tổ hợp, nên mạch thực hiện dịch vòng số lần mong muốn 
ngay sau một chu kỳ đồng hồ (1 clk). 
+ Mạch tính tổng kiểm tra “S”: Mạch tổ hợp để tính ra 8 CS theo thuật toán 
giải mã như ở phần trên. 
+ Mạch giải mã ngưỡng “M”: Thực hiện giải mã ngưỡng để xác định giá trị 
bit thông tin tương ứng. Nguyên lý mạch giải mã ngưỡng “M”: Thiết kế mạch cộng 
logic tổ hợp cho các tổng kiểm tra và mạch logic tổ hợp so sánh cho m, sử dụng 8 
CS, nếu m ≥ 5 thì bit thông tin ra là 1, ngược lại bit thông tin ra là 0. Kết quả giải 
mã cho ra 9 bit thông tin Io(0:8). 
Với thiết kế mạch giải mã như vậy tốc độ giải mã là lớn nhất, gần như là tức 
thời, tuy số tài nguyên cổng logic cần sử dụng nhiều nhưng đó lại là ưu thế của 
FPGA vì số lượng cổng logic tương đương rất lớn của nó. Toàn bộ các khối được 
thiết kế theo mô hình mạch mã hóa và giải mã đã được trình bày và được mô tả 
152 
bằng ngôn ngữ mô tả phần cứng VHDL. Kết quả tổng hợp, cấu hình và mô phỏng 
sử dụng FPGA XC3S500E-4CPG132 như trong bảng 3.2p và hình 3.14p. 
rol 0
rol 1
rol 2
rol 3
rol 4
S
b0(1:27)
S
b1(1:27)
S
b2(1:27)
S
b3(1:27)
S
b4(1:27)
M
S0(1:8)
M
S1(1:8)
M
S2(1:8)
M
S3(1:8)
M
S4(1:8)
Io(0)
Io(1)
Io(2)
Io(3)
Io(4)
b(1:27)
Clk
rol 5
rol 6
rol 7
rol 8
S
b5(1:27)
S
b6(1:27)
S
b7(1:27)
S
b8(1:27)
M
S5(1:8)
M
S6(1:8)
M
S7(1:8)
M
S8(1:8)
Io(5)
Io(6)
Io(7)
Io(8)
Hình 6.13p: Sơ đồ RTL của mạch khối DeCoding 
Bảng 3.2p: Tài nguyên logic được sử dụng xây dựng bộ mã LCC(27, 9, 9) 
Tiện ích Logic Đã sử dụng Hiệu suất 
Số cổng logic 327 7% 
Số tri gơ 240 2% 
Số LUT 4 đầu vào 631 6% 
Số cổng vào/ra (IO) 19 20% 
Số GCLK 1 4% 
Từ kết quả trong bảng 3.2p, có thể thấy rằng tài nguyên logic sử dụng để xây 
dựng bộ mã là tương đối nhỏ, so sánh với kết quả trong bảng 3.1p có thể nhận xét 
153 
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. 
Hình 6.14p: Kết quả mô phỏng bộ mã LCC (27,9,9) với ba lớp kề {(1), (11), (61)} 
Kết quả mô phỏng trên hình 6.14p 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. 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.