BÀI GIẢNG MÔN HỌC
LÝ THUYẾT THÔNG TIN
Trang 2
Mã vòng
13.1 Giới thiệu
13.2 Các tính chất của mã vòng
13.3 Ma trận sinh và ma trận kiểm tra của mã
13.4 Mã BCH
Trang 3
Giới thiệu

Định nghĩa

Một mã tuyến tính C(n, k) được gọi là mã vòng nếu w = a0a1…
an–2an–1 là một từ mã thì v = an–1a0a1…an–2 cũng là một từ
mã.

Nghĩa là dịch vòng (sang trái hay phải) một từ mã thì kết quả cũng
là một từ mã. Ở đây qui ước dịch phải.

Đa thức mã

Nếu w = a0a1…an–2an–1 là một từ mã thì w(x) = a0 + a1x + … +
an–2xn - 2 + an–1xn - 1 là đa thức mã tương ứng với từ mã w.

Ví dụ

Bảng sau đây trình bày một mã vòng C(7, 4).
Trang 4
Ví dụ
m w w(x) m w w(x)

3 0001101 x3 + x4 + x6 = x3 (1 + x + x3) = x3 *
w(x)
4 1000110 1 + x4 + x5 = x4 + x5 + x7 mod 7
5 0100011 x + x5 + x6 = x5 + x6 + x8 mod 7
6 1010001 1 + x2 + x6 = x6 + x7 mod 7 + x9 mod
7
Trang 6
Giới thiệu (tt)

w(i)(x) = xi * w(x) tuy nhiên nếu w(i)(x) có xp với p ≥ n thì xp
được thay bằng xp mod n.

Mặc khác trên trường GF(2) chúng ta có
xn + j = xj *
(xn + 1) + xj hay xn + j mod (xn + 1) = xj

Bổ đề 13.1
w(i)(x) = [xi *
w(x)] mod (xn + 1)
Trang 7
Các tính chất của mã vòng

Định lý 13.1

Đa thức mã khác 0 có bậc nhỏ nhất là duy nhất. Hay nói cách khác không
tồn tại hai đa thức mã khác 0, khác nhau và cùng có bậc nhỏ nhất.

Chứng minh

Giả sử ∃ hai đa thức mã khác nhau, cùng có bậc nhỏ nhất là r, 0 < r < n.

Các tính chất của mã vòng (tt)

Định lý 13.3

Một đa thức v(x) trên trường GF(2) có bậc ≤ n – 1 là đa thức mã nếu và 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


Đ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 12
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)

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 15
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 16
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








  





1
0
00
000
1
000
00
0
21
1
0
20
110
210
k
ggg
gg
g
kn
g


=
×
1011000
0101100
0010110
0001011
74
G
Trang 18
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)










G
Trang 19
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 20
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





  





1
0
00
000
1
000
00
0
021
01
0
2
11
021
)(
kn
hhh
hh
h
k
h

1110100
0111010
0011101
73
H
Trang 22
Ứ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 23
Ứ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).














=
×
11000
10100
10010
10001
54
H
Trang 25
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