Một số bộ mã cyclic tốt xây dựng trên vành đa thức

Nguyễn Trung Hiếu, Nguyễn Bình 
Tác giả liên hệ: Nguyễn Trung Hiếu, 
email: hieunt@ptit.edu.vn 
Đến tòa soạn: 6/2017, chỉnh sửa: 8/2017, chấp nhận đăng: 9/2017 
MỘT SỐ BỘ MÃ CYCLIC TỐT XÂY DỰNG 
TRÊN VÀNH ĐA THỨC
Nguyễn Trung Hiếu*, Nguyễn Bình 
Khoa Kỹ thuật điện tử 1, Học viện Công nghệ Bưu chính Viễn thông 
Tóm tắt: Mã cyclic là một lớp mã tuyến tính và có khả năng 
ứng dụng trong điện tử dân dụng, các hệ thống lưu trữ dữ liệu 
và các hệ thống truyền thông. Phương pháp xây dựng mã 
cyclic dựa trên các phân hoạch của vành đa thức (gồm nhóm 
nhân cyclic, cấp số nhân cyclic) có nhiều ưu điểm nổi bật, 
được quan tâm nghiên cứu và có những kết quả bước đầu. Bài 
báo này trình bày phương pháp tìm mã cyclic cục bộ 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à đề xuất một số mã cyclic cụ thể. Đồng thời, bài báo 
cũng trình bày mô phỏng, đánh giá chất lượng của một số bộ 
mã tìm được và khả năng ứng dụng vào việc truyền thông tin. 
Từ khóa: Mã cyclic, Nhóm nhân cyclic (CMG- Cyclic 
Multiplicative Group), Cấp số nhân cyclic (CGP- Cyclic 
Geometric Progressions), tổng kiểm tra (CS- Check-sum), 
vành đa thức. 
I. MỞ ĐẦU 
Nghiên cứu về lý thuyết mã hóa được chia thành ba hướng 
chính: mã nguồn, mã kênh (có khả năng phát hiện và sửa lỗi) 
và mật mã [1], [2]. Hầu hết các mã sửa lỗi được cấu trúc theo 
lý thuyết mã hóa thứ hai của Shannon [2], với các phương pháp 
xây dựng cấu trúc mã điển hình như phương pháp tổ hợp, hình 
học và cấu trúc đại số. 
Mã cyclic là mã khối tuyến tính là một loại mã kênh được 
nghiên cứu trong một thời gian dài và ứng dụng trong nhiều 
lĩnh vực cuộc sống, đặc biệt trong lĩnh vực thông tin và truyền 
thông [3], [4]. Mã cyclic cục bộ (LCC- Local Cyclic Code) bắt 
đầu được nghiên cứu vào những năm 1980 [3]. Mã LCC có đầy 
đủ các ưu điểm của mã cyclic thông thường (xây dựng từ 
Ideal), ngoài ra nó còn có thêm các ưu điểm khác như: số 
lượng mã tạo được nhiều hơn trên cùng một vành đa thức, mức 
độ tính toán cũng dễ hơn so với bộ mã cyclic thông thường 
tương đương [5], [6].1 
Theo phương pháp cấu trúc đại số, mã cyclic và mã cyclic 
cục bộ được xây dựng từ các nhóm nhân cyclic, cấp số nhân 
cyclic trên vành đa thức [3], [5]. Trong đó mã cyclic được xây 
dựng dựa trên nhóm nhân cyclic, mã LCC được xây dựng từ 
các lớp kề của phân hoạch vành đa thức (hay các cấp số nhân 
cyclic) [5]. 
Bài báo này đề xuất phương pháp xây dựng mã cyclic tốt từ 
nhóm nhân, cấp số nhân cyclic trên vành đa thức, từ đó liệt kê 
một số mã cyclic tốt và mô phỏng đánh giá hiệu quả của một số 
bộ mã thông qua một mô hình truyền thông cơ bản. 
Nội dung bài báo được chia làm bốn phần. Phần 2, trình 
bày cơ sở lý thuyết về nhóm nhân và cấp số nhân cyclic, mã 
cyclic trên vành đa thức, một số tiêu chí đánh giá mã tốt. Trong 
phần 3, đề xuất phương pháp tìm kiếm mã cyclic và cyclic cục 
bộ tốt. Trong khi đó, phần 4 sẽ mô phỏng, đánh giá một số mã 
tốt tìm kiếm được. Cuối cùng, phần 5 là kết luận của bài báo. 
II. CƠ SỞ LÝ THUYẾT 
Phần này trình bày về nhóm nhân, cấp số nhân, mã cyclic, 
mã cyclic cục bộ, tiêu chí đánh giá mã tốt. 
A. Nhóm nhân và cấp số nhân cyclic 
Nhóm nhân cyclic A với phần tử sinh ( )a x trên vành đa 
thức  2 / ( 1)
nx x được thiết lập như sau [5]: 
 mod( 1), 1,i nA a x x i k (1) 
Trong đó, k là cấp của ( )a x . 
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 [5]: 
 1( , ) ( ), ( ) ( ),..., ( ) ( )ma qA a x a x q x a x q x (2) 
Trong đó: m là số các số hạng khác nhau của CGP. 
 ( )a x là số hạng đầu của CGP. 
 ( )q x là công bội. 
 ( ) ( ) ( )mod 1
m na x q x a x x 
B. Mã cyclic và cyclic cục bộ trên vành đa thức 
Mã cyclic ( , )n k là Ideal ( )I g x của vành đa thức 
2[ ]/( 1)
nx x . 
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 . 
Nhận xét: 
+ Nếu chỉ chọn 1 lớp kề, khi đó mã LCC trở thành mã 
cyclic. 
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 20
MỘT SỐ BỘ MÃ CYCLIC TỐT XÂY DỰNG TRÊN VÀNH ĐA THỨC 
+ Nếu các lớp kề được chọn có chứa nhóm nhân cyclic đơn 
vị , 1,2,3...iI x i 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. 
C. Một số tiêu chí đánh giá mã tuyến tính tốt 
Khả năng lựa chọn các mã tuyến tính 0, ,n k d làm mã sửa 
lỗi là khá phong phú, để 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, có thể 
đưa ra một số giới hạn cơ bản làm tiêu chí lựa chọn các bộ mã 
tốt sau [2], [3]: 
Giới hạn Griesmer 
Đối 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
0 2
k
i
i
d
n
 (3) 
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 , số dấu thông tin , với yêu cầu tìm độ 
dài từ mã là nhỏ nhất. 
Giới hạn Plotkin 
Giới hạn Plotkin được xây dựng theo công thức: 
1.2
2 1
k
k
n
d
 (4) 
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 xác định khoảng 
cách cực tiểu . 
Giới hạn Hamming 
Giới hạn Hamming được xây dựng theo công thức: 
0
2
t
n k i
n
i
C 
  (5) 
Giới hạn Hamming được xây dựng trong trường hợp cố 
định độ dài từ mã và giá trị sai có thể sửa được cho trước, 
xác định độ thừa của từ mã r n k là nhỏ nhất. 
III. PHƯƠNG PHÁP TÌM MÃ CYCLIC TỐT 
A. Mã cyclic tối ưu xây dựng từ nhóm nhân, cấp số nhân 
cyclic 
Định lý 3.1: 
Mã cyclic trên vành đa thức [ ] 
 sử 
dụng tất cả đa thức khác không (trừ đa thức ∑ 
 ) 
làm dấu mã 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 mã 
 . 
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ó đa thức có trọng số lẻ và đ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ã [10]: 
 (6) 
Nếu cố định dấu và cho biến đổi thì phương 
trình (6) 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 (7): 
 (7) 
Theo định lý, số dấu của từ mã là (loại bỏ đa 
thức ∑ 
 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à: 
 ⌊
⌋ ⌊
⌋ (8) 
Theo phương pháp giải mã ngưỡng, khoảng cách mã 
được xác định: 
 (9) 
Kiểm tra theo giới hạn Griesmer: ∑ ⌈
⌉ thay 
 , ta được: 
Áp dụng công thức tính tổng của cấp số nhân, có: 
Theo định lý, số dấu của bộ mã là: . Vậy bộ mã 
 đạt được giới hạn Griesmer. 
Kiểm tra giới hạn Plotkin: 
Thay vào vế phải, kết quả của vế phải: 
 (
)
Với 
 nên bộ mã thỏa mãn giới hạn Plotkin. 
Định lý 3.2: 
Mã cyclic trên vành đa thức [ ] 
với lẻ và sử dụng tất cả đa thức trọng số lẻ (trừ đa thức 
 ∑ 
 ) làm dấu mã 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 
 . 
Chứng minh: 
Phân hoạch của vành [ ] 
 theo nhóm nhân đơn 
vị cấp k luôn tồn tại đa thức có trọng số chẵn và 
 đa thức có trọng số lẻ (theo tính chất của vành đa thức). 
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 21
Nguyễn Trung Hiếu, Nguyễn Bình 
Trọng số của đa thức (∑ 
 ) . Khi lẻ, 
đa thức 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 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 , thì số dấu 
mã của bộ mã là . 
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 (10) [11]: 
 (10) 
Theo phương trình (10), 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 
(10) 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 (10) có dạng: 
[ ] (11) 
Số dấu còn lại của từ mã bằng . Như vậy số tổng 
kiểm tra thiết lập được để giải mã là: 
 ⌊
⌋ ⌊
⌋ (12) 
Khoảng cách mã Hamming xác định là: 
 (13) 
Kiểm tra theo giới hạn Griesmer: ∑ ⌈
⌉ thay 
 , ta được: 
Áp dụng công thức tính tổng của cấp số nhân, có: 
Theo định lý 3.2, số dấu của bộ mã: . Vậy bộ 
mã đạt được giới hạn Griesmer. 
Kiểm tra giới hạn Plotkin: 
Thay vào vế phải, kết quả vế phải: 
 (
)
Với 
 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ừ nhóm nhân cyclic, cấp số nhân cyclic có dạng 
 và 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ã 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 và phần tử 
∑ ; có thể xây dựng mã 
 bằng việc lấy tất cả 
các lớp kề có trọng số lẻ của vành đa thức trừ phần tử 
∑ . 
Đố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 
bằng thì chọn đa thức có cấp cực đại làm phần tử 
sinh của bộ mã [7]. 
+ Nếu cấp cực đại của các đa thức thuộc vành 
không nhỏ hơn thì chọn đa thức thuộc vành lớn hơn 
(vành 
 , với ) và có cấp bằng với 
sau đó hạ bậc đa thức theo [8] 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 còn được gọi là 
thực hiện phân hoạch hỗn hợp trên hai vành đa thức bất kỳ [8]. 
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: 
3 21 (1 )(1 )x x x x 
5 2 3 41 (1 )(1 )x x x x x x 
7 2 3 31 (1 )(1 )(1 )x x x x x x 
9 2 3 61 (1 )(1 )(1 )x x x x x x 
10
11
0
1 (1 ) i
i
x x x
  
12
13
0
1 (1 ) i
i
x x x
  
15 2 3 4
4 2 3 4
1 (1 )(1 )(1 )
(1 )(1 )
x x x x x x
x x x x x x
17 3 4 5 8
2 4 6 7 8
1 (1 )(1 )
(1 )
x x x x x x
x x x x x x
18
19
0
1 (1 ) i
i
x x x
  
21 2 3 2 3
2 4 6 2 4 5 6
1 (1 )(1 )(1 )(1 )
(1 )(1 )
x x x x x x x x
x x x x x x x x
23 2 4 5 6 10 11
5 6 7 9 11
1 (1 )(1 )
(1 )
x x x x x x x x
x x x x x x
25 2 3 4
5 10 15 20
1 (1 )(1 )
(1 )
x x x x x x
x x x x
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 22
MỘT SỐ BỘ MÃ CYCLIC TỐT XÂY DỰNG TRÊN VÀNH ĐA THỨC 
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 I. 
Bảng I. 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 
3 
6, 9, 
15, 
21 
3
1( ) 1h x x ; 
7, 21 
2 3
2( ) 1h x x x ; 
3
3( ) 1h x x x 
4 
5, 15, 
25 
2 3 4
1( ) 1h x x x x x 
7 
2 3
2( ) (1 )(1 )h x x x x ; 
3
3( ) (1 )(1 )h x x x x 
15 
2 3 4
1( ) 1h x x x x x 
3 4
4( ) 1h x x x ; 
4
5( ) 1h x x x 
21 
2 4
6( ) 1h x x x ; 
2 4
7( ) 1h x x x x 
5 
15, 
25 
5
1( ) 1h x x ; 
15 
3 4
2( ) (1 )(1 )h x x x x ; 
4
3( ) (1 )(1 )h x x x x 
6 
7 2 3 31( ) (1 )(1 )h x x x x x ; 
9 
3 6
2( ) (1 )h x x x 
15 
2 3 4
3( ) (1 )(1 )h x x x x x ; 
2 4
4( ) (1 )(1 )h x x x x x ; 
2
5
2 3 4
( ) (1 )
(1 )
h x x x
x x x x
21 
3 2 3
6( ) (1 )(1 )h x x x x x ; 
2 4 6
7( ) 1h x x x x x ; 
2 4 5 6
8( ) 1h x x x x x 
7 
9 
3 6
1( ) (1 )(1 )h x x x x 
15 
2 3 4
2( ) (1 )(1 )(1 )h x x x x x x 
2 4
3( ) (1 )(1 )(1 )h x x x x x x 
2
4
2 3 4
( ) (1 )(1 )
(1 )
h x x x x
x x x x
21 
7
5( ) 1h x x 
2 4 6
6( ) (1 )(1 )h x x x x x x 
2 4 5 6
7( ) (1 )(1 )h x x x x x x 
8 9 
2 3 6
1( ) (1 )(1 )h x x x x x 
phù 
hợp 
Các đa thức thỏa mãn 
15 
3 4 4
2( ) (1 )(1 )h x x x x x 
3 4
3
2 3 4
( ) (1 )
(1 )
h x x x
x x x x
4
4
2 3 4
( ) (1 )
(1 )
h x x x
x x x x
17 
3 4 5 8
5( ) (1 )h x x x x x 
2 4 6 7 8
6( ) (1 )h x x x x x x x 
21 
2
7
2 4 6
( ) (1 )
(1 )
h x x x
x x x x
2
8
2 4 5 6
( ) (1 )
(1 )
h x x x
x x x x
9 
17 
3 4 5 8
1( ) (1 )(1 )h x x x x x x 
2
2 4 6 7 8
( ) (1 )
(1 )
h x x
x x x x x x
21 
2
3
2 4 6
( ) (1 )(1 )
(1 )
h x x x x
x x x x
2
4
2 4 5 6
( ) (1 )(1 )
(1 )
h x x x x
x x x x
3
5
2 4 6
( ) (1 )
(1 )
h x x x
x x x x
3
6
2 4 5 6
( ) (1 )
(1 )
h x x x
x x x x
2 3
7
2 4 6
( ) (1 )
(1 )
h x x x
x x x x
2 3
8
2 4 5 6
( ) (1 )
(1 )
h x x x
x x x x
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 I 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 
 và thỏa mãn 
cấp của đa thức là 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 
 thì có thể hạ bậc của đa thức có cấp bằng 
và thuộc vành lớn hơn theo như bảng I thì có thể tìm 
được bộ mã tối ưu. 
Xét vành 
 , 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 I ta thấy rằng có thể hạ bậc đa thức có cấp 
bằng 255 trong vành 
 theo hoặc để 
xây dựng mã. Ví dụ chọn đa thức 
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 23
Nguyễn Trung Hiếu, Nguyễn Bình 
 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 
 , chọn để 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 
 , từ đây xây dựng được bộ mã cyclic 
 là mã tối ưu đạt giới hạn Griesmer và Plotkin. 
B. 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 đó tác giả 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ý). 
j = i + 1;
Lập hệ tổng kiểm tra của bộ mã
j = m
Sai
Đúng
Bắt đầu
Cho giá trị của k
Lập phân hoạch cho vành đa thức
Cho i = 2
Lập mã gồm 3 lớp kề {1, i, j}
Xác định n
j = j + 1
i = i + 1 i = m - 1
Sai
Đúng
Liệt kê bộ mã (n, k, d) tốt
Kết thúc
Hình 1. Lưu đồ thuật toán tìm bộ mã cyclic tốt từ cấp số nhân 
cyclic 
Để 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 [3], [9], [10], [11], 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 
 . 
+ 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 
Bước 2: + Gán 
Bước 3: 
+ Lập mã gồm 3 lớp kề 
+ 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ố CS 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 thì chuyển sang bước 5, nếu 
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 1 và danh 
sách một số bộ mã cyclic tốt tìm được như trong bảng II. 
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, tác giả 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. 
Bảng II. Đề xuất một số bộ mã cyclic tốt 
Vành CGPs/CMG TTG CKNTG TTGLH 
 {(1), (7), (11)} (15,5,7) 
 {(1), (11), 
(21)} 
 (14,6,5) 
 = 2, CS = 
8 
{(1), (13), 
(21)} 
 (14,6,5) 
 = 2, CS = 
8 
 {(1), (23), 
(29)} 
(21,7,7) 
 {(1), (11), 
(87)} 
(24,8,7) 
{(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 = 
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 24
MỘT SỐ BỘ MÃ CYCLIC TỐT XÂY DỰNG TRÊN VÀNH ĐA THỨC 
Vành CGPs/CMG TTG CKNTG TTGLH 
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) 
{(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) 
IV. MÔ PHỎNG ĐÁNH GIÁ MỘT SỐ BỘ MÃ 
A. Đề xuất kịch bản mô phỏng, đánh giá 
Sơ đồ tổng quát của một hệ thống truyền đề xuất để thực 
hiện mô phỏng, đánh giá mã cyclic như hình 2, 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 Gause trắng cộng, các bộ 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. 
Dữ liệu 
phát
Mã hóa Điều chế
Dữ liệu 
thu
Giải mã 
hóa
Giải điều 
chế
Bên phát
Bên thu
Nhiễu
K
ên
h 
tr
uy
ền
Hình 2. Sơ đồ hệ thống thông tin sử dụng mô phỏng đánh giá 
mã cyclic 
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 Gause. 
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 Gause 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ố ở 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ệ 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ó). 
B. Kết quả mô phỏng, đánh giá một số bộ mã cyclic 
Trong phần này, tác giả thực hiện mô phỏng, đánh giá một 
số bộ mã cyclic tốt được liệt kê trong bảng II. 
1) Bộ mã cyclic 
Chọn đa thức 
 có cấp là 255 [7] là phần tử sinh của CMG xây dựng 
trên vành 
 , chọn 
 để hạ bậc ta xây dựng được CMG tương 
ứng có cấp 255 trên vành 
 , 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 
 đạt giới hạn Griesmer và Plotkin. Kết quả mô 
phỏng bộ mã cyclic thể hiện như hình 3. 
Hình 3. Kết quả mô phỏng bộ mã cyclic (255,9,127) 
Trong mô phỏng ứng với bộ mã này, tác giả sử dụng nhiễu 
Gause 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 
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 25
Nguyễn Trung Hiếu, Nguyễn Bình 
chất lượng rất tốt. Trên hình 3 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ế, không mã hóa. Kết quả 
cho thấy bộ mã đạt với 
 (trường hợp điều 
chế 64QAM), và với 
 (trường hợp điều 
chế 128QAM). 
2) Bộ mã cyclic 
Chọn mã cyclic cục bộ xây dựng từ ba lớp kề cyclic {(1), 
(7), (11)} trên vành 
 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 
 ), tiến hành xây dựng bộ mã hóa 
và giải mã ta thu được bộ mã cyclic đạt giới hạn 
Griesmer và Plotkin. Kết quả mô phỏng bộ mã cyclic 
thể hiện như hình 3 và hình 4. 
Hình 4. Kết quả mô phỏng bộ mã cyclic (15,5,7) 
Tương tự như mô phỏng bộ mã (255,9,127), ta sử dụng 
nhiễu Gause 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 4 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 tại 
 , nếu không mã hóa 
thì kênh truyền đạt , nếu sử dụng bộ mã cyclic 
(15,5,7) thì kênh truyền đạt (tốt hơn trường 
hợp không mã hóa khoảng lần); với điều chế 16QAM tại 
 , nếu không mã hóa thì kênh truyền đạt 
 , sử dụng bộ mã cyclic (15,5,7) thì kênh truyền đạt 
 (tốt hơn trường hợp không mã hóa hơn 
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 cho tốt hơn 16QAM 
(ví dụ, tại 
 , điều chế QPSK cho , trong 
khi điều chế 16QAM cho ) là phù hợp với lý 
thuyết. 
3) Bộ mã cyclic 
Chọn mã cyclic cục bộ xây dựng từ ba lớp kề cyclic {(1), 
(11), (61)} trên vành 
 , tiến hành xây dựng bộ mã 
hóa và giải mã ta thu được bộ mã cyclic . Kết quả mô 
phỏng bộ mã cyclic thể hiện như hình 5. 
Tương tự, tác giả sử dụng nhiễu Gause 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 5 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 thấy với phương pháp 
điều chế QPSK tại 
 , nếu không mã hóa thì kênh truyền 
đạt , nếu sử dụng bộ mã cyclic (27,9,9) thì 
kênh truyền đạt , sử dụng bộ mã cyclic 
(15,5,7) thì đạt ; với phương pháp điều chế 
16QAM tại 
 , nếu không mã hóa thì kênh truyền đạt 
 , sử dụng bộ mã cyclic (27,9,9) thì kênh 
truyền đạt , sử dụng bộ mã cyclic (15,5,7) thì 
đạt . 
Hình 5. Kết quả mô phỏng bộ mã cyclic (27,9,9) 
Kết quả mô phỏng trên hình 5 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 bit lỗi, và 
 ) 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 
bit lỗi, và ). 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). 
V. KẾT LUẬN 
Mã cyclic có hạn chế lớn nhất là độ dự thừa từ mã khá lớn 
(hay hiệu suất mã hóa thông tin không cao), tuy nhiên ưu điểm 
nổi bật là dễ thực hiện về mặt kỹ thuật và số lượng mã nhiều. 
Các nghiên cứu trước đây thường tập trung vào việc kiến trúc 
mã chứ ít quan tâm đến việc tìm kiếm và đánh giá các bộ mã 
tốt về năng lực sửa lỗi. Bài báo này đã tập trung nghiên cứu để 
tìm kiếm các bộ mã cyclic tốt tiến tới các giới hạn tối ưu 
Griesmer và Plotkin. Nội dung bài báo đã trình bày phương 
pháp tìm mã cyclic tốt thông qua đề xuất và chứng minh hai 
định lý về mã cyclic tối ưu, xây dựng thuật toán tìm bộ mã 
cyclic tốt và bước đầu lập được bảng một số mã cyclic tốt, 
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 26
MỘT SỐ BỘ MÃ CYCLIC TỐT XÂY DỰNG TRÊN VÀNH ĐA THỨC 
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ế. 
Ngoài ra, các bộ mã cyclic xây dựng từ nhóm nhân cyclic, cấp 
số nhân cyclic như trình bày ở trên có khả năng thay đổi được 
độ dài từ mã tùy theo nhu cầu sử dụng là ưu điểm có thể ứng 
dụng trong mã mạng phục vụ các hệ thống truyền thông không 
dây hợp tác [12]. 
LỜI CẢM ƠN 
Tác giả xin chân thành cám ơn Học viện Công nghệ Bưu 
chính Viễn thông đã tạo điều kiện giúp đỡ, hỗ trợ tôi thực hiện 
hướng nghiên cứu này. 
TÀI LIỆU THAM KHẢO 
[1] Menezes A. J, Van Oorchot P. C., Handbook of Applied 
Cryptography, CRC Press, (1998). 
[2] Todd K. Moon, Error Correction Coding: Mathematical 
Methods and Algorithm. John Wiley & Sons, Inc, (2005). 
[3] Nguyễn Bình, Giáo trình Lý thuyết thông tin, Nhà xuất bản Bưu 
điện, (2008). 
[4] C. Ding, “Cyclic codes from the two-prime sequences”, IEEE 
Transactions on Information Theory, ISSN 0018-9448, 58(6), 
2012, pp. 357–363. 
[5] Nguyễn Bình, 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, 2012, trang 735-749. 
[6] Nguyen Trung Hieu, Nguyen Van Trung, Nguyen Binh, A 
Classification of Linear Codes Based on Algebraic Structures 
and Local Cyclic Codes, Proceedings of The 2014 International 
Conference on Advanced Technologies for Communications, 
Hanoi, Vietnam, October 15 - 17, 2014, Pages 349-354. 
[7] Nguyễn Trung Hiếu, Ngô Đức Thiện, 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, ISSN 2354-
1083, số 110, 2016, trang 75-80. 
[8] Ngo Duc Thien, Nguyen Binh, Some Local Cyclic Codes Based 
on Compound Decomposition of Two Polynomial Rings, 
International Conference on Advanced Technologies for 
Communications (ATC 2008 - REV’11), Hanoi, Vietnam, 
October 2008. 
[9] Nguyễn Bình, Nguyễn Xuân Quỳnh, 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), 1996. 
[10] Nguyễn Bình, Nguyễn Thế Truyện, 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), 
1996. 
[11] Nguyễn Bình, Nguyễn Thế Truyện, 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), 1996. 
[12] Suwen Wu; Jinkang Zhu; Ling Qiu; Ming Zhao, Network-
coding-based coded cooperation, Journal of Communications 
and Networks, Vol 12 (4), 2010, pp. 366 - 374. 
GOOD LOCAL CYCLIC CODERS ARE 
CONSTRUCTED ON POLYNOMIAL RING 
Abstract: The cyclic code is a linear code layer and is 
applicable in civil electronics, data storage systems, and 
communication systems. Cyclic code generation based on 
polynomial ring decomposition (cyclic multiplicative groups, 
cyclic geometric progressions) has many outstanding 
advantages, is of interest for research and has initial results. 
This paper presents the method of code generation and 
proposes some good local cyclic code from cyclic 
multiplicative group, cyclic geometric progressions on 
polynomial ring. At the same time, the article also presents 
simulations, evaluates the quality of some of the code found 
and its applicability to the transmission of information. 
Keywords: cyclic code, Cyclic Multiplicative Group 
(CMG), Cyclic Geometric Progressions (CGP), Check-sum 
(CS), polynomial ring. 
Nguyễn Trung Hiếu, Nhận 
học vị Thạc sỹ năm 2010. Hiện 
nay đang công tác và làm nghiên 
cứu sinh tiến sĩ tại Học viện Công 
nghệ Bưu chính Viễn thông. Lĩnh 
vực nghiên cứu: Lý thuyết thông 
tin, mã hóa, mật mã, hệ thống số, 
hệ thống nhúng. 
Nguyễn Bình, Nhận học vị 
Tiến sỹ năm 1984. Hiện là Giáo 
sư tại Học viện Công nghệ Bưu 
chính Viễn thông. Lĩnh vực 
nghiên cứu: Lý thuyết thông tin, 
mã hóa, mật mã. 
Số 01 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 27