Bài giảng Lý thuyết thông tin - Hồ Văn Quân

 chỉ nếu nó là một bội số của g(x). Tức là nó có thể
viết v(x) = q(x) * g(x).
„ Chứng minh
„ Chiều thuận
„ Nếu v(x) = q(x) * g(x) và có bậc ≤ n – 1 thì v(x) là đa thức mã.
với p là bậc của q(x) và p + r ≤ n – 1. Do xi * g(x) với 0 ≤ i ≤ p
là đa thức mã, nên v(x) là đa thức mã vì nó là một tổ hợp tuyến 
tính của các đa thức mã.
( )∑∑
==
=⎟⎟⎠
⎞
⎜⎜⎝
⎛==
p
i
i
i
p
i
i
i gqgqgqv
00
)(*)(*)(*)()( xxxxxxx
Trang 291
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Các tính chất của mã vòng (tt)
„ Chiều ngược
„ Nếu v(x) là đa thức mã thì chia v(x) cho g(x)
v(x) = q(x) * g(x) + r(x)
trong đó r(x) là đa thức dư và có bậc nhỏ hơn bậc của g(x).
Đối với các đa thức trên trường GF(2) chúng ta có thể suy ra
r(x) = q(x) * g(x) + v(x)
Nên r(x) là một đa thức mã. Theo định nghĩa của g(x) suy ra 
r(x) = 0. Chứng minh hoàn tất.
„ Từ định lý này chúng ta gọi g(x) là đa thức sinh, vì từ g(x) có
thể sinh ra tất cả các đa thức mã khác.
Trang 292
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Các tính chất của mã vòng (tt)
„ Định lý 13.4
„ Đa thức sinh của một mã vòng C(n, k) có bậc r = n – k.
„ Chứng minh
„ Mỗi đa thức mã w(x) là một bội số của g(x)
w(x) = q(x) * g(x)
„ Có 2k từ mã nên có 2k đa thức q(x). Suy ra bậc của q(x) là ≤ k –
1. Suy ra bậc của g(x) là n – k.
„ Từ định lý này đa thức sinh g(x) có thể được biểu diễn như sau
g(x) = g0 + g1x +  + gn – kxn – k
trong đó g0 = gn – k = 1.
Trang 293
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Các tính chất của mã vòng (tt)
„ Định lý 13.5
„ Đa thức sinh của mã vòng C(n, k) là một ước số của xn+ 1.
„ Chứng minh
„ Bổ đề 13.1 suy ra
g(i)(x) = [xi * g(x)] mod (xn + 1)
⇔ xi * g(x) = q(x) * (xn + 1) + g(i)(x)
Chọn i = k⇒ q(x) = 1 tức
xk * g(x) = (xn + 1) + g(i)(x)
⇒ xn + 1 = xk * g(x) + g(i)(x)
Do g(i)(x) là một đa thức mã nên g(i)(x) là một bội của g(x), ⇒
xn+ 1 là một bội của g(x). Chứng minh hoàn tất.
Trang 294
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Các tính chất của mã vòng (tt)
„ Định lý 13.6
„ Nếu g(x) là một đa thức có bậc (n – k) và là ước số của (xn + 1)
thì g(x) sinh ra mã vòng C(n, k), hay nói cách khác g(x) là đa 
thức sinh của một mã vòng C(n, k) nào đó.
„ Chứng minh
„ Xét k đa thức g(x), x * g(x), , xk – 1 * g(x).
Các đa thức này đều có bậc ≤ n – 1.
Gọi v(x) là một tổ hợp tuyến tính của k đa thức này với các hệ
số ai ∈ GF(2).
v(x) = a0g(x) + a1x * g(x) +  + ak – 1xk – 1 * g(x)
v(x) là một đa thức có bậc ≤ n – 1 và là bội số của g(x).
Trang 295
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Các tính chất của mã vòng (tt)
„ Có tất cả 2k tổ hợp tuyến tính v(x) khác nhau và tạo nên một 
không gian tuyến tính của các đa thức mã với g(x), x * g(x), , 
xk – 1 * g(x) là các đa thức làm cơ sở.
Chúng ta chứng minh rằng bộ mã tương ứng với không gian 
này là mã vòng.
Gọi
w(x) = b0 + b1x +  + bn – 1xn – 1
là một đa thức của không gian.
Chúng ta chứng minh
w(1)(x) = bn – 1 + b0x + b1x2 +  + bn – 2xn – 1
cũng là một đa thức của không gian.
Trang 296
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Các tính chất của mã vòng (tt)
„ Theo Bổ đề 13.1 chúng ta có
w(1)(x) = [x * w(x)] mod (xn + 1)
Dựa vào biểu diễn của v(x) và w(1)(x) chúng ta suy ra
x * w(x) = bn – 1(xn + 1) + w(1)(x)
Do v(x) và (xn + 1) đều là bội của g(x) nên w(1)(x) cũng là bội 
của g(x). Suy ra w(1)(x) cũng là đa thức mã. Hoàn tất chứng 
minh.
Trang 297
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ma trận sinh
„ Ví dụ
„ Tìm một mã vòng C(7, 4).
„ Theo các tính chất của mã vòng suy ra đa thức sinh của mã có
bậc bằng 3 và là một ước số của x7 + 1. Phân tích đa thức này ra 
thừa số chúng ta được
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡ −+−
=
−
−−−
−
−−
−−
−
×
4444 84444 76
L
MMMM
L
L
L
4444 84444 76
L
MMMMM
L
L
L
1
0
00
000
1
000
00
0
21
1
0
20
110
210
k
ggg
gg
g
kn
g
gg
ggg
gggg
G
kn
knkn
kn
kn
kn
kn
nk
Trang 298
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ
x7 + 1 = (1 + x)(1 + x + x3)(1 + x2 + x3)
„ Chọn chẳng hạn
g(x) = (1 + x + x3)
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=×
1011000
0101100
0010110
0001011
74G
Trang 299
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Mã vòng dạng hệ thống
„ Từ dạng hệ thống loại 1 chúng ta có thể dịch vòng k bit để biến 
đổi sang dạng hệ thống loại 2 và ngược lại.
„ Mã hóa thành từ mã hệ thống
„ u(x) là thông báo, w(x) là từ mã hệ thống loại 2 tương ứng.
xn–k * u(x) = q(x) * g(x) + a(x)
w(x) = xn–k * u(x) + a(x) = q(x) * g(x)
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=×
1011000
0101100
0010110
0001011
74G
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=×
1011000
1110100
1100010
0110001
)74(htG
Trang 300
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ
„ Cho mã vòng C(7, 4) có ma trận sinh là g(x) = (1 + x + x3). Hãy 
mã hoá thông báo u = 1010 thành từ mã hệ thống dạng 2.
u(x) = 1 + x2.
Nhân u(x) với xn–k = x3 rồi chia cho g(x) chúng ta được.
x3 * (1 + x2) = x3 + x5 = x2 * (1 + x + x3) + x2
„ Từ đây suy ra
w(x) = x2 + x3 + x5
w = 0011010
là từ mã hệ thống dạng 2 tương ứng với u.
Trang 301
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ma trận kiểm tra của mã vòng
„ Có một cách khác để tìm ma trận kiểm tra của mã vòng
xn + 1 = g(x) * h(x)
„ h(x) được gọi là đa thức đối ngẫu của g(x). h(x) có bậc k
h(x) = h0 + h1x +  + hkxk
„ Ma trận sau là một ma trận kiểm tra của mã vòng
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡ −−+
=
−−
−
−−
×−
444 8444 76
L
MMMM
L
L
L
4444 84444 76
L
MMMMM
L
L
L
1
0
00
000
1
000
00
0
021
01
0
2
11
021
)(
kn
hhh
hh
h
k
h
hh
hhh
hhhh
H
kkk
k
kk
kkk
nkn
Trang 302
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ
„ Cho mã vòng C(7, 4) có ma trận sinh là g(x) = (1 + x + x3).
Từ đây suy ra
h(x) = (1 + x + x2 + x4)
„ Ma trận kiểm tra của bộ mã là
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=×
1110100
0111010
0011101
73H
Trang 303
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ứng dụng trường GF(2m)
để xây dựng mã vòng
„ Định lý 13.7
„ Cho a là một phần tử khác 0 của trường GF(2m) có chu kỳ là n, 
đa thức tối thiểu f(x) của a có bậc là m. Thì mã có ma trận sau 
làm ma trận kiểm tra là một mã vòng C(n, n – m), trong đó mỗi 
phần tử trong ma trận bên dưới được thay thế bằng vectơ m
thành phần tương ứng của nó.
Hm×n = [1 a a2  an – 2 an–1]
Hơn nữa mã vòng này có đa thức sinh chính là f(x).
„ Ví dụ
„ Xét trường GF(24) và a có đa thức tối thiểu là
f(x) = 1 + x + x4
Trang 304
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ứng dụng trường GF(2m)
để xây dựng mã vòng (tt)
„ Từ đây suy ra ma trận kiểm tra của mã vòng (15, 11).
„ Nếu đa thức tối thiểu của a là f(x) = 1 + x + x2 + x3 + x4 thì a có
chu kỳ là 5 và các phần tử 1, a, ..., a4 được biểu diễn như sau.
1 = (1000) a3 = (0001)
a = (0100) a4 = (1111)
a2 = (0010)
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=×
111101011001000
011110101100100
001111010110010
111010110010001
154H
Trang 305
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ứng dụng trường GF(2m)
để xây dựng mã vòng (tt)
„ Từ đây suy ra ma trận kiểm tra của mã vòng (5, 1)
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=×
11000
10100
10010
10001
54H
Trang 306
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Mã BCH nhị phân
„ Do Bose, Chaudhuri và Hocquenghem sáng lập ra.
„ Là mã vòng có khả năng sửa được nhiều lỗi.
„ Đối với các số nguyên dương m và t bất kỳ chúng ta sẽ xây 
dựng một mã BCH nhị phân có các thông số sau:
Độ dài từ mã: n = 2m – 1
Số bit kiểm tra: n – k ≤ mt
Khoảng cách Hamming: dmin ≥ 2t + 1
Trang 307
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Định lý
„ Định lý 13.8
„ Cho a là một phần tử của trường GF(2m) có đa thức tối thiểu là
một đa thức căn bản bậc m. Thì mã có ma trận sau làm ma trận 
kiểm tra là một mã vòng có khoảng cách Hamming ≥ 2t + 1, 
trong đó mỗi phần tử trong ma trận bên dưới được thay thế
bằng vectơ m thành phần tương ứng của nó.
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
−−−−−−
−−
−−
−−
)1)((12()2)((12()12(212
)1(5)2(5105
)1(3)2(363
122
1
1
1
1
ntnttt
nn
nn
nn
aaaa
aaaa
aaaa
aaaa
H
L
MMMMMM
L
L
L
Trang 308
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Định lý (tt)
„ Hơn nữa đa thức sinh g(x) của bộ mã là đa thức bội số chung 
nhỏ nhất của các đa thức tối thiểu của các phần tử a, a3, a5, , 
a2t–1.
„ Bổ đề 13.2
„ Ma trận A sau có định thức bằng 
với i, j ∈ {1, 2, , r}. Định thức này được gọi là định thức 
Vandermonde.
∏
>
−
ji
ji yy )(
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
−−− 11
2
1
1
22
2
2
1
21
111
r
r
rr
r
r
yyy
yyy
yyy
A
L
MMMM
L
L
L
Trang 309
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ
„ Cho m = 4, t = 2 chúng ta sẽ xây dựng một mã vòng có chiều 
dài từ mã là 24 – 1 = 15 và có khoảng cách Hamming d ≥ 5. 
Việc xây dựng sẽ dựa vào trường GF(24).
„ Gọi a là phần tử có đa thức tối thiểu là đa thức căn bản bậc 4 
sau f1(x) = 1 + x + x4
„ Đây chính là trường GF(24) trong ví dụ ở slide 250.
„ a có chu kỳ n = 2m – 1 = 15. Chúng ta có ma trận kiểm tra của 
bộ mã như sau.
„ Thay mỗi phần tử ai bằng vectơ 4 thành phần tương ứng
⎥⎦
⎤⎢⎣
⎡=
4239363330272421181512963
141212111098765432
1
1
aaaaaaaaaaaaaa
aaaaaaaaaaaaaa
H
Trang 310
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡
=
111101111011110
101001010010100
110001100011000
100011000110001
111101011001000
011110101100100
001111010110010
111010110010001
H
Trang 311
Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
„ Đa thức sinh g(x) là bội số của hai đa thức tối thiểu tương ứng 
với phần tử a và a3.
„ Theo ví dụ ở slide 250, đa thức tối thiểu của a3 là
f3(x) = 1 + x + x2 + x3 + x4.
„ Từ đây suy ra
g(x) = f1(x) * f3(x)
= (1 + x + x4) * (1 + x + x2 + x3 + x4)
= 1 + x4 + x6 + x7 + x8
„ Chú ý
„ Trong trường hợp đa thức tối thiểu của a không phải là đa thức 
căn bản, chúng ta sẽ tìm được mã vòng có chiều dài n ≠ 2m + 1, 
với n là chu kỳ của a.