Lĩnh vực Công nghệ thông tin
Khảo sát một số mã xiclic trên vành đa thức x
9
+ 1
PGS.TS. Nguyễn Bình, KS. Ngô Đức Thiện
Khoa Kỹ thuật điện tử 1
Tóm tắt: Các mã xyclic đã có nhiều ứng dụng rất hiệu quả trong thực tiễn. Chúng đợc xây
dựng trên các Ideal của vành đa thức, tuy nhiên số Ideal trên một vành đa thức ít nên số bộ
tạo ra cũng hạn chế. Để mở rộng khả năng tạo thêm các mã trên một vành đa thức, bài báo
đề cập đến phơng pháp phân hoạch vành đa thức (cụ thể trên vành đa thức
[ ]
9
2
Z x x 1
+
),
trên cơ sở đó khảo sát một số bộ mã xyclic không có trên vành X
9
+1 theo quan điểm xây
dựng mã xyclic truyền thống.
1. Một sô khái niệm
1.1. Vành đa thức
Nếu R là một vành giao hoán thì vành đa thức R[x] là một vành đợc tạo bởi tập tất cả
các đa thức của biến x có các hệ số trong R. Hai phép toán là phép cộng và phép nhân đa
thức thông thờng với số học các hệ số đợc thực hiện trong vành R.
Trong trờng nhị phân, vành đa thức đợc ký hiệu:
(f(x); f, ) = Z
2
[x]/ x
n
+ 1

Nhóm nhân xyclic trong vành đa thức là tập hợp các phần tử đều 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 xyclic, số nhóm nhân bằng số
các lũy đẳng có thể có trong vành.
A = {

,

2
,

3
, }
Trong đó: A là nhóm nhân xyclic; là phần tử sinh (đa thức sinh), cấp của phần tử sinh là
cấp của nhóm (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 e(x).
Học viện Công nghệ BCVT
Hội nghị Khoa học lần thứ 5
b) Nhóm nhân xyclic đơn vị
Nhóm nhân xyclic đơn vị là một nhóm bao gồm mọi đơn thức và có cấp là n. Ký hiệu là I ,
hay nhóm nhân xyclic đơn vị là nhóm nhân xyclic với phần tử sinh là x.
I = {x, (x)
2
, (x)
3
, , (x)
n-1
, 1}
c) Nhóm nhân xyclic với phần tử sinh a(x)
Nhóm nhân xyclic với phần tử sinh là đa thức a(x) 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: A = {a(x), (a(x))

9
+ 1 = (1 + x)(1 + x + x
2
)(1 + x
3
+ x
6
).
Vành đa thức này có có 2
9
- 1 = 511 phần tử khác 0.
Trong đó có: 256 phần tử có trọng số lẻ.
255 phần tử có trọng số chẵn.
+ Cấp cực đại của đa thức a(x) đợc xác định nh sau:
Max ord(a(x)) = 2
m
-1 = 2
6
- 1 = 63.
ở đây m cũng chính bằng max m
s
= 6, hay cấp lớn nhất của đa thức bất khả quy trong khai
triển nhị thức x
9
+1.
+ Phân tích max ord(a(x)) ra thừa số nguyên tố để xác định các ớc của nó:
Max ord(a(x)) = 63 = 3.3.7.
+ Cấp các phần tử trong vành là các ớc số của max ord(a(x)), tơng ứng các nhóm nhân trong
vành có các cấp là: 1, 3, 7, 9, 21, 63.
+ Xác định các chu trình C

C
1
= {1, 2, 4, 8, 7, 5} |C
1
| = m
1
= 6
C
3
= {3, 6} |C
3
| = m
3
= 2
Đa thức e(x) là một lũy đẳng khi và chỉ khi tập các hệ số khác không của nó là hợp một số
các chu trình C
s
nào đó. Các lũy đẳng chính là các phần tử đơn vị của các nhóm nhân xyclic
trong vành đa thức. Ta tìm đợc các lũy đẵng nh sau:
Bảng 1: Các lũy đẳng của vành đa thức Z
2
[x]/ x
9
+ 1
Học viện Công nghệ BCVT
Lĩnh vực Công nghệ thông tin
Các lũy đẳng
Dạng số mũ
của đa thức
Các chu trình

3
(x) = e
0
(x) = 1 + x + x
2
+ x
3
+ x
4
+ x
5
+ x
6
+ x
7
+ x
8
(012345678)
C
0
C
1
C
3
e
4
(x) = 1 (0) C
0
e
5

+ x
6
+ x
7
+ x
8
(12345678)
C
1
C
3
256 phần tử có trọng số lẻ bao gồm:
1 nhóm nhân cấp 63 với phần tử sinh a
1
(x) = (012), với lũy đẳng e
1
(x) = (0124578).
1 nhóm nhân cấp 3 với phần tử sinh a
2
(x) = (147), với lũy đẳng e
2
(x) = (036).
1 nhóm nhân cấp 1 với phần tử sinh a
3
(x) = e
3
(x) = (012345678).
3 nhóm nhân cấp 63 với phần tử sinh a
4
(x) = (014), a

- Tìm phần tử sinh có cấp lớn nhất.
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. Hơn nữa do vành đối xứng nên khi biết nửa vành có
thể suy ra nửa vành kia. Vì vậy trớc tiên ta đi xác định các phần tử có trọng số lể. Trong các
phần tử có trọng số lẻ xác định các phần tử sinh có cấp lớn nhất.
Sau đó xây dựng tất cả các nhóm nhân chứa các phần tử có trọng số lẻ. Để xây dựng đợc tất
cả các nhóm nhân ta phải thực hiện các bớc:
o 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.
o 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 xyclic 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.
3. Khảo sát một số mã xyclic và xyclic cục bộ trên vành đa thức X
9
+ 1
3.1. Khái niệm mã xyclic cục bộ (XCB)
Mã xyclic cục bộ là mã hệ thống tuyến tính (n, k) trong đó:
Học viện Công nghệ BCVT
Hội nghị Khoa học lần thứ 5
k dấu thông tin đợc chọn là k đơn thức có dạng
( )
0,1, 2, , 1
i
x i k=
và là nhóm nhân xyclic
cấp k của vành
[ ]
( )
2

x x x x

= = = = =
.
Trên cơ sở phân tích nh vậy thì mã xyclic là một lớp kề đặc biệt của mã XCB. Hay mã xyclic
là một dạng đặc biệt của mã XCB.
3.3. Khảo sát một số mã xyclic và xyclic cục bộ trên vành đa thức x
9
+ 1
a) Khảo sát mã xyclic (n, k) với k = m.
Trong một vành đa thức luôn tồn tại mã xyclic (m, m) có d
0
= 1, mã này đợc xây dựng từ
nhóm nhân đơn vị.
{ }
, 1, 1
i
I x i m= =
Mã này không có khả năng phát hiện và sửa sai. Do số dấu thông tin k = m, nên để tạo các mã có
khả năng phát hiện và sửa sai xây dựng trên các nhóm nhân xyclic thì yêu cầu phải thỏa mãn
điều kiện n > m . Hay nói cách khác là cấp của nhóm nhân xyclic tạo mã phải lớn hơn và bằng
bội của m, nhóm nhân đơn vị I phải là nhóm nhân con của nhóm nhân xyclic tạo mã.
Nhóm nhân xyclic tạo mã (n, m) phải thỏa mãn 2 điều kiện:
Nhóm nhân xyclic đơn vị có cấp m phải là một nhóm con của nhóm nhân xyclic cấp n
( )
n m m nM hoặc
.
Cấp của nhóm nhân xyclic tạo mã (n, m) phải là ớc nào đó của cấp số lớn nhất các phần
tử trong vành:
( )

A a x i= =
.
* Mã xyclic (63, 9) xây dựng trên nhóm nhân cấp 63
Xét đa thức sinh a = (1 + x
2
+ x
3
+ x
5
+ x
7
), đa thức này có cấp 63. Cấu trúc của nhóm nhân là
A = {a
i
= (1 + x
2
+ x
3
+ x
5
+ x
7
); i = 0, 1, 2, , 62}.
Đánh giá:
Số tổng kiểm tra (TKT) tự trực giao của mã này: J = 17, do đó khoảng cách tối thiểu d
0
= 18.
Theo giới hạn dới của độ dài từ mã (giới hạn Griesmer):
1
0

Với mã này có độ dài từ mã là n = 63 > 41 mã không tối u.
b) Khảo sát các mã xyclic (n, k) với k < m.
* Mã xyclic (63, 7).
Chọn nhóm nhân xyclic theo modulo
( )
3 4 6 7
1h x x x x x x= + + + + +
với phần tử sinh của
nhóm nhân là:
( )
( )
4
1 014x x

= + +
có cấp là 63, làm mã xyclic (63,7).
Nhóm nhân này có dạng nh sau:
( )
{ }
( ) ( )
{ }
mod , 0,1, 2, ,62 014 mod , 0,1, 2, , 62
i
i
A h x i h x i

= = = =
Do mã này là mã xyclic có khả năng trực giao, cho nên phải giải mã 2 cấp. ở cấp ngỡng thứ
nhất giải mã ra các cặp dấu thông tin, sau đó qua bớc giải mã cấp ngỡng thứ hai mới giải mã
đợc toàn bộ các dấu thông tin.


= = + + + + + + =

Mã này là mã tối u.
c) Khảo sát mã xyclic cục bộ.
* Mã XCB (27, 9)
Mã XCB (27 9) đợc xây dựng từ 3 cấp số nhân (CGP) xyclic lấy trong phân hoạch vành đa
thức
[ ]
9
2
/ 1Z x x +
thành các CGP cấp 9. CGP1 chính là nhóm nhân xyclic đơn vị (là đa thức
thông tin). Chọn CGP2 (trởng lớp kề là (7)) và CGP3 (trởng lớp là (11)) làm các dấu kiểm
tra. Do CGP2 và CGP3 là 2 lớp kề lẻ liên tiếp, cho nên mã này sẽ là mã XCB có khả năng
trực giao.
Học viện Công nghệ BCVT
Hội nghị Khoa học lần thứ 5
Cấu trúc từ mã XCB (27,9) này nh sau: (các dấu mã biểu diễn ở dạng thập phân).
1 2 4 8 16 32 64 128256 7 14 28 56 112224448385259 11 22 44 88 176352193386261
Nếu biểu diển mã XCB này theo trởng lớp kề thì có dạng {1, 7, 11}.
Số TKT có khả năng trực giao J = 6 d
0
= 7. Theo giới hạn Griesmer thì mã này cũng
không tối u:
3.4. Phơng pháp giải mã ngỡng
Có các phuơng pháp giải mã nguỡng sử dụng cho việc giải mã XCB:

là số nguyên nhỏ nhất lớn hơn hoặc bằng x.
Thì coi e
i
= 1 có sai ở dấu thứ i, ngợc lại e
i
= 0: dấu thứ i thu đúng.
Mỗi tổng kiểm tra (TKT) trong hệ J TKT này cho phép đa ra các dấu a
i
ở 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 TKT. Vì vậy có 2t TKT (2t = d
0
1 = J)
để giải mã đúng các dấu a
i
theo biểu quyết đa số.
Do các TKT 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. Do vậy 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ứ 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ã xyclic 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ệ TKT có khả năng trực giao.
Một hệ TKT có khả năng trực giao nếu tồn tại một tổ hợp tuyến tính các dấu mã:
1 2

i i im
M x x x= + + +
thỏa mãn điều kiện sau:
+ Tổ hợp tuyến tính các dấu mã M có mặt trong mọi TKT.

cục bộ. Khác với các mã xyclic thông thờng (mỗi từ mã là một phần tử có cấu trúc đại số),
với mã xyclic cục bộ mỗi dấu mã trong một từ mã là một phần tử có cấu trúc đại số. Do đó
mã xyclic cục bộ có cấu trúc đại số tinh tế hơn và cũng vì thế mà khả năng sửa sai của nó tốt
hơn.
Học viện Công nghệ BCVT
Hội nghị Khoa học lần thứ 5
Tài liệu tham khảo
[1] F.J. Mac Williams, N.J.A. Sloane: The theory of error-correcting codes. North-Holland
Publisher Com. 1977.
[2] A.J. Menezes, P.C. Van Oorchot, S.A. Vanstone: Handbook of Applied Cryptography.
CRC Press 1998.
[3] Ass.Prof. Nguyễn Bình, Nguyễn Quốc Hng: Circuland Crypto-System based on
polynominal ring with two cycloctomic cosets.
[4] PGS. TS. Nguyễn Bình, ThS. Vũ Việt, KS. Trần Đức Sự: Các vành đa thức có hai lớp kề
xyclic trong lý thuyết mã hóa.
[6] Vũ Việt: Phân hoạch vành đa thức. Chuyên đề tiến sĩ, 2001
[7] Nguyen Binh. Tran Duc Su, Pham Viet Trung.
"Decomposition of polynomial ring according to the classes of conjugate elements".
ATC - 26. Hanoi, 10.2001.
[8] Nguyen Binh, Vu Viet, Pham Viet Trung.
"Decomposition of polynomial ring and coding with random clock". CAFEO 2000.
Hanoi, 22-24 Nov, 2000.
Học viện Công nghệ BCVT