Lĩnh vực Công nghệ thông tin
Phân hoạch của vành đa thức theo các phần tử liên hợp
và ứng dụng trong lý thuyết mã
PGS.TS Nguyễn Bình, KS. Đặng Hoài Bắc
Khoa Kỹ thuật điện tử 1
Tóm tắt: Mã xyclic cục bộ (XCB) tuy còn non trẻ nhng đã tỏ ra có nhiều u điểm thoả mãn đ-
ợc yêu cầu thực tế của hệ thống truyền tin. Trong bài báo này, chúng tôi sẽ đề cập đến một
cách phân hoạch mới trên vành đa thức chẵn Z
2
[x]/x
2n
+1 (ký hiệu là Z
2n
) đó là phân hoạch
theo lớp các phần tử liên hợp và từ đây xây dựng mã XCB cụ thể trên phân hoạch này.
1. Phân hoạch của vành đa thức Z
2n
theo các phần tử liên hợp
1.1 Các thặng d bậc 2 và các căn bậc 2 của chúng.
Định nghĩa 1.1: Đa thức f(x) đợc gọi là thặng d bậc 2 (quadratic residue - QR) trong Z
2n
nếu
tồn tại đa thức g(x) sau:
g
2
(x)

f(x) mod x
2n+1
(1.1)
Nh vậy g(x) Z

n
0i
i
n
C
=
1 2 3 ( 1)

n n
n n n n n
C C C C C

+ + + + +
= 2
n
(1.2)
Ví dụ 1.1: Ta xét vành Z
2n
với n=3

ta có vành Z
6
( n = 3)
Tập các thặng d bậc hai Q
2n
trong vành Z
6
đợc xác định theo bổ đề 2.1 nh sau:
Q
6

+








(1.3)
Trong đó U là một tập gồm các tổ hợp tuỳ ý các giá trị trong tập s = {0, 1, 2, , n-1}
Do vậy lực lợng của U sẽ bằng:U = 2
n
-1
Ví dụ 1.2: Trong tập Q
6
ở trên ta xét một QR bất kỳ để xác định căn bậc 2, chẳng hạn f(x)=x
2
áp dụng công thức (1.3) tính các căn bậc hai ở trên ta có
sqr(x
2
) = (1+x
3
)
xx
Ut
t
+



+x
4
Cứ nh vậy ta sẽ tìm đợc toàn bộ 2
2n
phần tử liên hợp của vành Z
6
.
Nhận xét:
- Trong vành Z
2n
có 2
n
thặng d bậc 2, mỗi thặng d bậc 2 có 2
n
căn bậc 2, vậy có tất cả 2
2n
căn bậc 2 trong vành, các căn bậc 2 này tạo nên toàn bộ vành Z
2n
.
- Ta sẽ gọi các căn bậc 2 của cùng một thặng d bậc 2 là các phần tử liên hợp (Conjugate
Elements ) tơng ứng với thặng d đó ký hiệu là CEs.
1.2 Phân hoạch vành Z
2
[x]/ x
2n
+1 theo các phần tử liên hợp
Để khảo sát sự phân hoạch theo các CE trên vành Z
2
[x]/x
2n

)
Sqr(1+x
2
)
Sqr(1+x
4
)
Sqr(0)
Sqr(x
4
)Sqr(x
2
)
Sqr(1+x
2
+x
4
)
Vành Z
6
Hội nghị Khoa học lần thứ 5
Hình 1. Phân hoạch vành Z
6
theo lớp các phần tử liên hợp
Ta thấy rằng, đối với phép cộng

các CEs ở hình 1 sẽ thoả mãn bảng 1 nh sau:

Sqr(1) Sqr(x
2

+x
4
) Sqr(1)
Sqr(x
2
)
Sqr(1+x
2
) Sqr(0) Sqr(x
2
+x
4
) Sqr(1) Sqr(1+x
2
+x
4
) Sqr(x
4
) Sqr(1+x
4
) Sqr(x
2
)
Sqrh(x
4
)
Sqr(1+x
4
) Sqr(x
2

) Sqr(1+x
2
)
Sqr(1+x
4
)
Sqr(x
4
) Sqr(1+x
2
+x
4
) Sqr(1) Sqr(x
2
+x
4
) Sqr(0) Sqr(1+x
2
) Sqr(x
2
) Sqr(1+x
4
)
Sqr(x
2
+x
4
)
Sqr(1+x
2

) Sqr(x
2
) Sqr(1) Sqr(0) Sqr(1+x
2
+x
4
)
Sqr(0)
Sqr(1) Sqr(x
2
) Sqr(x
4
) Sqr(1+x
2
) Sqr(1+x
4
) Sqr(x
2
+x
4
) Sqr(1+x
2
+x
4
) Sqr(0)
Bảng 1. Phép cộng modulo với các phần tử liên hợp trong vành Z
6
Ta kiểm tra một phép cộng modulo trong bảng trên chẳng hạn: Sqr(1)+Sqr(x
4
) = Sqr(1+x

4
) Sqr(1+x
2
) Sqr(1+x
4
) Sqr(x
2
+x
4
) Sqr(1+x
2
+x
4
) Sqr(0)
Sqr(1)
Sqr(1) Sqr(x
2
) Sqr(x
4
) Sqr(1+x
2
) Sqr(1+x
4
) Sqr(x
2
+x
4
) Sqr(1+x
2
+x

4
) Sqr(x
2
+x
4
) Sqr(1+x
2
) Sqr(1+x
2
+x
4
) Sqr(0)
Sqr(1+x
2
)
Sqr(1+x
2
) Sqr(x
2
+x
4
) Sqr(1+x
4
) Sqr(1+x
4
) Sqr(x
2
+x
4
) Sqr(1+x

4
) Sqr(x
2
+x
4
) Sqr(1+x
2
) Sqr(1+x
2
) Sqr(1+x
4
) Sqr(x
2
+x
4
) Sqr(0) Sqr(0)
Sqr(1+x
2
+x
4
)
Sqr(1+x
2
+x
4
) Sqr(1+x
2
+x
4
) Sqr(1+x

) Sqr(1+x
2
) và (1+x
2
+x
3
) Sqr(1+x+x
2
)
Ta có: (x
3
+x
4
)x(1+x
2
+x
3
) = (x
3
+x
4
+x
6
+x
5
+x
6
+x
7
)mod(x

+x
4
)
Khi thực hiện phép nhân: (x+x
3
) x (1+x
2
+x
4
) = (x+x
3
+x
3
+x
5
+x
5
+x
7
) mod (x
6
+1) = x+x = 0.
Vậy, các phần tử liên hợp của các thặng d bậc 2 trong vành Z
6
tạo nên một nửa nhóm nhân.
Học viện Công nghệ BCVT
Lĩnh vực Công nghệ thông tin
Nhận xét:
- Lớp các CE của các thặng d bậc 2 trong vành Z
6

x)x(e
đợc gọi là luỹ đẳng nuốt. Tơng
tự nh vậy, trong vành Z
2n
, ta cũng xác định đợc một lũy đẳng nuốt là
)x(e
2
0
với :


=
=
1n
0i
i22
0
x)x(e
(2.1)
Phép nhân một đa thức bất kỳ với luỹ đẳng nuốt giúp ta kiểm tra đợc tính chẵn lẻ.
Luỹ đẳng nuốt có những tính chất đặc biệt để xây dựng mã XCB.
Trong vành
1x]x[Z
10
2
+
, tức vành Z
2n
với n = 5 ta thấy rằng có tất cả 32 (2
n

+x
6
, x
2
+x
8
, x
4
+x
6
, x
4
+x
8
, x
6
+x
8
, 1+x
2
+x
4
,
1+x
2
+x
6
, 1+x
2
+x

8
, x
4
+x
6
+x
8
, 1+x
2
+x
4
+x
6
,
1+x
2
+x
4
+x
8
, 1+x
2
+x
6
+x
8
, 1+x
4
+x
6

8

Ta xác định CEs của luỹ đẳng nuốt e
0
(x
2
)=1+x
2
+x
4
+x
6
+x
8
trong tập Q
10
trên theo biểu thức:
Sqr(e
0
(x
2
)) = (1+x
n
)







4
+x
6
,1+x
2
+x
4
+x
6
+x
8
,
1+x
3
+x
4
+x
6
+x
7
, x+x
2
+x
3
+x
4
+x
5
, x+x
3

5
+x
6
,
x
2
+x
4
+x
5
+x
6
+x
8
, x
2
+x
5
+x
6
+x
8
+x
9
, x
3
+x
4
+x
5

7
+x
8
,
1+x
4
+x
6
+x
7
+x
8
, 1+x+x
4
+x
7
+x
8
, x
5
+x
6
+x
7
+x
8
+x
9
,
x+x

+x
9
, 1+x
2
+x
3
+x
6
+x
9
, 1+x
2
+x
7
+x
8
+x
9
,
1+x+x
3
+x
7
+x
9
, 1+x+x
3
+x
4
+x

2
+x
3
+x
5
+x
9
, x
2
+x
3
+x
5
+x
6
+x
9
}
N
0
C
1
C
2
C
3
C
3
1
(01234) (02346) (03467) (02468)

k
i
i
d
n

=


(2.2)
Nhận xét:
Học viện Công nghệ BCVT
Hội nghị Khoa học lần thứ 5
- Để trực giao hóa hệ tổng kiểm tra
n
x1)x(b)x(a +=+
, ta có thể chọn trớc giá trị của n
dấu thông tin. Để thuận tiện, bắt đầu từ đây khi lập mã ta sẽ chọn
0xxx
1n21nn
====
+

).
- Từ toàn bộ các lớp kề, ta có thể xây dựng mã (31, 5) với
16d
0

0
đến x
4
. Sau đây là sơ đồ giải mã.
Bộ giải mã ngỡng của mã này đợc thể hiện ở hình 3. Tại xung clock thứ nhất, đầu ra
của thiết bị giải mã M là x
0
. Tại xung clock thứ hai, đầu ra của M là x. Tại xung clock thứ ba,
đầu ra cuả M là x
2
. Tại xung clock thứ t, đầu ra là x
3
. Tại xung clock thứ 5, đầu ra là x
4
. Ng-
ỡng chính của thiết bị giải mã ngỡng M sẽ là 8. Bộ mã có khả năng sửa đợc 6 bit sai.
Lu đồ thuật toán mô phỏng cách lập, giải mã trên đợc thể hiện ở trang tiếp theo.
Học viện Công nghệ BCVT
x
0
x
1
x
2
x
3
x
4
00000
+ + + +

C
8
3
C
9
3
C
10
3
C
1
2
C
2
2
C
3
2
C
4
2
C
5
2
C
6
2
C
7
2

C
8
1
C
9
1
C
10
1
C
+
+
+
+
+
+
+
+
+
+
+
+
+
M=8
OUTPUT
Hình 3. Bộ giải mã mã XCB (29,5) theo phân hoạch chuẩn
Lĩnh vực Công nghệ thông tin

2.2 Xây dựng mã theo lớp CEs của luỹ đẳng nuốt trên vành Z
10

đợc phân hoạch theo hai lớp kề nh sau:
}30,1b,b{}29,0i),x(a)x(e{B
ii
01
====

B
1
= {(01234), (02346), (01478), (34567), (35679), (01347), (06789), (02689), (03467), (01239),
(12359), (03679), (23456), (24568), (02369), (56789), (15789), (23569), (01289), (01248), (25689),
(12345), (13457), (12589), (45678), (04678), (12458), (01789), (01374), (14578)}.
)}13579(),02468{(B
2
=
Ta sẽ sử dụng lớp kề B
1
để tạo mã xyclic cục bộ (29, 5) phần tử (5 6 7 8 9) = 0 vì theo giả
thiết x
5
=x
6
=x
7
=x
8
=x
9
=0
Lu đồ thuật toán và kết quả chơng trình mô phỏng
lập mã , giải mã mã (29, 5) theo phân hoạch chuẩn bằng Visual C

Cách mã hóa mã 29,5 theo phân hoạch cực đại:
Giả sử ta có đa thức thông tin là I = {1 0 1 0 0}
Bằng cách thay lần lợt đa thức thông tin vào các đa thức trong nhóm nhân xyclic ở trên, và
cộng modul 2 kết quả ta sẽ đợc toàn bộ từ mã tơng ứng với đa thức thông tin đó.Ví dụ, đa
thức đầu tiên của nhóm nhân là a = (1 + x + x
2
+ x
3
+ x
4
), thay tơng ứng đa thức thông tin ở
trên vào ta đợc bit đầu tiên của từ mã là:
(1 + x
2
) = 1

1 = 0. Thực hiện với tất cả các bit còn lại ta đợc toàn bộ từ mã xyclic theo
phân hoạch cực đại tơng ứng với đa thức thông tin trên là:
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
Hệ tổng kiểm tra trực giao với
5
x1+
đợc xây dựng từ
1
B
là:
221
1
bbS
+=

10
bbS
+=
2419
11
bbS
+=
2720
12
bbS +=
167
13
bbS
+=
2625
14
bbS
+=
Đối với hệ tổng kiểm tra trực giao này, ta có thể chọn
0xxxxx
98765
=====
.
Trong trờng hợp này, ta có mã xyclic
)5,29(
với
14d
0
=
.

b
16
b
15
b
14
b
13
b
12
b
11
b
10
b
9
b
8
b
7
b
6
b
5
b
4
b
3
b
2

. Tại xung clock
thứ 64, đầu ra của M là x
3
. Tại xung clock thứ 85, đầu ra của M là x
4
.Đây là xung nhịp clock
cuối cùng của quá trình giải mã. Ngỡng chính của M sẽ là 8. Bộ mã sửa đợc 6 bit sai.
Với thuật toán tơng tự ta xây dựng chơng trình mô phỏng bằng MATLAB và có đợc
kết quả nh sau:
3. Kết luận
Ta thấy rằng việc xây dựng các mã theo các phần tử liên hợp của luỹ đẳng nuốt có
nhiều u điểm nổi bật nh:
- Các mã tạo ra đều là mã gần tối u thoả mãn các giới hạn Griesmes.
- Khả năng tạo ra các bộ mã có cùng tham số là rất lớn. Điển hình nh mã (29,5) chúng
ta tạo ra có tới hơn 5400 khả năng.
- Các sơ đồ mã hoá và giải mã đều khá đơn giản chỉ cần các bộ cộng modulo 2 và nhân
đa thức thông thờng.
- Dựa vào phơng pháp phân hoạch theo các phần tử liên hợp của luỹ đẳng nuốt ta có thể
xây dựng mã trên mọi vành chẵn Z
2n
, điều mà trớc nay cha đợc đề cập đến.
Kết quả của bài báo nếu đợc hoàn thiện về phần cứng có thể đợc sử dụng trong việc
truyền tin trong các mạng Lan, Wan với những đặc tính truyền dẫn và sửa sai tốt, linh hoạt
trong việc thay đổi bộ mã.
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] Nguyen Binh, Nguyen Xuan Quynh.
"Application of symmetric characteristic of cosets for improving error - correcting
ability of local cyclic codes". Science conference. Electronics - Informatics Institute.