mã hamming và ứng dụng để sửa lỗi cho đoạn dữ liệu
Chơng 1 : tổng quan về mã
Đ 1.1 - Một số khái niệm và định nghĩa
1- Định nghĩa :
1.1 Mã hoá : Là quá trình làm tơng ứng 1-1 giữa một tin của nguồn cần mã hoá
với một từ mã của bộ mã .
Nếu ký hiệu a
i
là một tin của nguồn cần mã hoá còn i là một từ mã của bộ mã
ta có thể biểu diễn quá trình mã hoá nh sau:
a
i

mã hoá

i

1.2- Giải mã : Là quá trình làm tơng ứng 1-1 một từ mã với một tin của nguồn
(giải mã là quá trình ngợc với quá trình mã hoá ) . Quá trình giải mã đợc biểu diễn
nh sau :
a
i

giải mã

i
Để giải mã đợc thì yêu cầu mã hoá phải có quy luật . Nh vậy có thể coi mã hoá
nguồn tin theo bộ mã là phép ánh xạ 1:1 biến đổi một tin của nguồn thành một tổ
hợp các ký hiệu của bộ mã , trong đó giải mã là phép ánh xạ ngợc .
Giả sử có nguồn tin X cần mã hoá có s tin với xác suất xuất hiện các tin là p(x
i

) :
1)(
1
=

=
s
i
i
xp
X = { x
i
} ; i = 1,s
Bộ mã hoá M có N từ mã : = {
i
} ; i =
N,1
từ khái niệm mã hoá và giải mã ta suy ra các quan hệ sau :
p(x
i
) = p(
i
) N S (1)
trong đó p(
i
) là xác suất xuất hiện từ mã
i
ứng với tin x
i
2 - Một số khái niệm về mã .

2.1 - Cơ số của bộ mã .
Cơ số của bộ mã kí hiệu là m , chính là số ký hiệu khác nhau dùng để lập nên
các từ mã .
Các ký hiệu khác nhau này là các chữ số hệ đếm m .
Ví dụ : m = 2 các ký hiệu là 0;1
m = 3 các ký hiệu là 0;1;2

m = 16 các ký hiệu là 0;1;2 9 ,A, B,C, D,E,F
Cơ số thờng dùng làm tên các bộ mã . Mã nhị phân (m=2) , mã tam phân (m=3)
mã thập lục phân (m=16).
2.2- Độ dài từ mã : là số ký hiệu của bộ mã dùng để mã hoá cho từ mã đó . Độ dài
từ mã ký hiệu là n , là số lợng ký hiệu trong từ .
Ví dụ : mã nhị phân m = 2 từ mã
1
= 0011001 có độ dài n=7.
mã tam phân m =3 từ mã
1
= 012010 có độ dài n=6.
Nếu các từ mã có độ dài nh nhau ta sẽ có bộ mã đều . Khi này số từ mã của bộ mã
xác định theo công t
N = m
n
(2)
3
Nếu các từ mã của bộ mã có độ dài khác nhau ta có bộ mã không đều . Trong trờng
hợp này độ dài trung bình , tức mã của bộ mã ký hiệu là n và đợc xác định theo công
thức :




= =
==
1 1
)()(
i
s
i
iii
xpnpn

(3)
Trong đó n
i
là độ dài từ mã thứ i
2.3 - Trọng lợng từ mã .
Là tổng số các ký hiệu khác không của từ mã . Trọng lợng của từ mã
i
ký hiệu là
W(
i
).
Ví dụ :
1
= 101011 W(
1
) = 4.

2
= 111111 W(
1

) = 6.
0 W(
i
) n (4)
2.4- Khoảng cách mã .
Khoảng cách mã là số ký hiệu khác nhau tơng ứng giữa hai từ mã có độ dài bằng
nhau .
Gọi
i
và


j
là hai từ mã có độ dài bằng nhau . Khoảng cách mã ký hiệu d (
i

j
)


là phép toán cộng modul - 2
d (
i

j
) có một số tính chất sau :
+ d (
i

j

) = d (
j
i) hay d (
i

j
) = 0 khi i j
+ 0 d (
i

j
) n i j
d (
j

i
) min i j = d
0
, đợc gọi là khoảng cách mã tối thiểu của bộ mã .
+ [d (
j
i)

d (
i

k
) d (
i


k
) ]
Ví dụ :
1
= 10101

2
= 01101

3
= 11011
Ta có : d (
1

2
) = W (
1


2
) = 2
d (
1

3
) = 3
d (
2

3

) = 3
d (
1

2
)

d(
1

3
) = 5
Do đó : d (
1

2
)

d (
1

3
) d (
1

3
) .
+ d (
i


j
) = W (
i


j
) .
Tính chất này nói về mối quan hệ giữa khoảng cách mã và trọng số khoảng cách
giữa hai từ mã chính bằng trọng số của từ mã mà tổng modul - 2 của hai từ mã .
2.5- Độ thừa của bộ mã (D):
Độ thừa của bộ mã ký hiệu là D và đợc định nghĩa nh sau :
D =
( ) ( )
( )
max
maxmax
H
XHH


(5)
Trong đó : H()
max
; là Entropi cực đại của bộ mã , H()
max
là lợng thông tin
trung bình cực đại chứa trong từ mã (hay do từ mã mang lại)
H()
max
= n log

2
m (6)
Trong đó : m là cơ số của bộ mã
n là độ dài từ mã
H(x)
max
: Entropi cực đại của nguồn tin cần mã hoá .
H(x)
max
: là lợng thông tin trung bình cực đại chứa trong mỗi tin của nguồn (do
mỗi tin của nguồn mang lại )
H(x)
max
= H(x)
các tin của nguồn
= log
2
S (7)
4
S : Số tin của nguồn cần mã hoá .
Dạng khác của (5) :
max
max
)(H
)X(H
1


(8)
Thay (6) và (7) vào (8) ta có:


mlogn
Slog
1D
2
2
=
(9)
Với bộ mã đều nhị phân : m =2 ta có
n
Slog
1DD
2
2
==
(10)
Với bộ mã đầy : N= N
1
= m
n
= 2
n
= S
Do đó :
0
n
2log
1
n
Slog

1D
n
22
day
2
===
(11)
Với bộ mã vơi N1 < N => S < 2
n
Hay n > log
2
S do đó :
0
n
Slog
1D
2
2
voi
>=
(12)
2.6- Bộ mã đầy - bộ mã vơi .
N là số từ mã của bộ mã .N
1
là số từ mã dùng để mã hoá các tin của nguồn (N
1
= S).
Nếu N
1
= N ta có bộ mã đầy (các từ mã đều đợc dùng để mã hoá các tin của nguồn,

trong trờng hợp này N
1
= N = S) . Nếu N
1
< N , ta có bộ mã vơi (Số lợng từ mã dùng
để mã hoá các tin ít hơn số từ mã của bộ mã trong trờng hợp này N
1
= S <N).
Với từ mã vơi , số từ mã còn lại (số từ mã không đợc dùng ) là N
1
-N đợc gọi là các
từ mã cấm ( Hay bộ mã cấm).
2.7 - Điều kiện để mã phân tách đợc .
Điều kiện quan trọng của việc tạo mã là cho phép khi nhận đợc một chuỗi các ký
hiệu chúng ta phải phân tách đợc thành các thành phần cơ bản là các từ mã , các từ
mã này phải là duy nhất và đúng đắn . Để đạt đợc điều này thì bộ mã phải thoả mãn
điều kiện cần và đủ sau : Bất kỳ dãy các từ mã nào của bộ mã cũng không đợc trùng
với một dãy từ mã khác của cùng bộ mã .
Độ chậm giải mã : độ chậm giải mã là số ký hiệu nhận đợc cần thiết có thể phân
tách đợc thành các từ mã . Đối với bộ mã phân tách đợc độ chậm giải mã là hữu hạn
có khi là vô hạn , trong trờng hợp là vô hạn thì ta có thể xem là không phân tách đợc
.
Để xác minh tính phân tách của bộ mã và nếu phân tách đợc xác định độ chậm giải
mã và xây dựng bảng thử mã phân tách .
Bảng giải mã phân tách đợc xây dựng theo bảng sau :
1 - Đem các từ mã xếp thành một cột , đánh dấu số 1.
2- Đối chiếu các từ mã ngắn với các từ mã dài hơn trong cột ,nếu từ mã ngắn hơn
trùng với phần đầu của từ mã dài thì phần còn lại ghi vào cột thứ 2 .
3 - Lặp lại bớc 2 , nghĩa là cột thứ j sẽ là kết quả khi ta chiếu cột (j - 1) với cột
(j - 2) , tiếp tục làm cho đến khi cột phải dần trở nên trống rỗng .

Ví dụ 1:Lập bảng thử mã phân tách cho bộ mã 00 ; 01 ; 100 ; 1010 ; 1011.
5
1 2
00
100
1010
1011

Cột 2 trống rỗng , độ chậm giải mã bằng 0 .
Ví dụ 2 : Lập bảng mã thử phân tách cho bộ mã 10 ; 100 ; 01 ; 011.
1 2 3 4 5
10 0 1 0 1
100 11 00 11
01 1 0 1 0
011 00 11 00

Trờng hợp này ta thấy bộ mã có khả năng phân tách đợc vì trong các cột 2,3,4
không có các từ mã nào trùng với các từ mã trong cột một , nhng vì cột j là vô hạn
nên độ chậm giải mã là vô hạn .
Bảng thử mã phân tách cho phép đánh giá độ chậm giải mã nếu j là giá trị của cột
rỗng thì độ chậm giải mã T
ch
đợc tính theo công thức :

maxmin
22
1
n
J
Tn

j
ch














(13)
n
min
, n
max
là độ dài ngắn nhất và dài nhất của bộ mã .
Kết luận : Để mã có tính phân tách đợc thì điều kiện cần và đủ là bất kỳ tổ hợp mã
nào cũng không đợc trùng với phần đầu của bất kỳ tổ hợp mà khác cùng bộ mã
Đ 1.2 - Phân loại Mã .
1.2- 1 : Phân loại theo trọng lợng từ mã .
- Mã có trọng lợng không đổi .
- Mã có trọng lợng thay đổi .
1.2- 2 : Phân loại mã theo chiều dài từ mã .
- Mã có chiều dài thay đổi .

- Mã có chiều dài thay đổi .
1.2- 3 : Phân loại mã theo hiệu xuất thông tin.
- Mã tối u .
- Mã cha tối u.
1.2- 4 : Phân loại theo độ tin cậy .
- Mã không có khả năng phát hiện và sửa sai.
- Mã có khả năng phát hiện và sửa sai.
1.2- 5 : Phân loại theo cơ số của bộ mã .
Có thể xây dựng bộ mã có cơ số bất kỳ , tuy nhiên mã có cơ số 2 (nhị phân)
là thông dụng nhất .
1.2- 6 : Phân loại mã theo thứ tự các cột số trong từ mã .
- Mã không có có trọng số : Thứ tự các cột số không ảnh hởng đến nội dung
của từ mã .
- Mã có trọng số : Thứ tự các cột số ảnh hởng đến nội dung của từ mã .
1.2- 7 : Phân loại theo mục đích sử dụng mã .
- Mã số .
- Mã ký tự.
6
1.2- 8 : Phân loại mã theo khoảng cách d giữa hai từ mã kế cận .
- d const : mã vòng .
- d = const : mã Gray ; mã JohnSon .
1.2- 9 : Phân loại theo cách tạo mã .
Trong việc truyền tin có hai loại mã đợc sử dụng phổ biến là Mã khối
(Block code) và Mã xoắn (Con volutional code) .
a- Mã khối :
Bộ mã hoá của bộ mã khối sẽ chia dòng thông tin thành những khối tin (message
Block ) có Kbit . Mỗi tin đợc biểu diễn bằng một khối K ,thành phần nhị phân U =
{U
1
; U

2
U
k
} . U đợc gọi là Veetor thông tin có tổng cộng 2
k
Veetor thông tin khác
nhau . Bộ mã hoá sẽ chuyển Veetor thông tin U thành một bộ n thành phần V =
(V
1
; V
2
V
n
) đợc gọi là từ mã . Nh vậy ứng với 2
k
Veetor thông tin sẽ có 2
k
từ mã
khác nhau . Tổng hợp 2
k
từ mã có chiều dài n đợc gọi là mã khối (n,k) . Tỷ số R =
k/n gọi là tỷ số mã , R là số bit thông tin đa vào bộ giải mã trên số bit đợc truyền .
Do n bit ra chỉ phụ thuộc vào k bit thông tin vào bộ giải mã không cần nhớ và có thể
thực hiện đợc bằng mạch logic tổ hợp .
b- Mã xoắn :
Bộ mã hoá của mã xoắn giống nh bộ mã hoá mã khối , cũng nhận k bit thông tin u
và tạo thành từ mã v là những khối n bit . Nhng n bit của từ mã v không phụ thuộc
vào k bit , thông tin nmã còn phụ thuộc vào m bit thông tin trớc đó . Do đó bộ mã
hoá có một bộ nhớ m . Tập hợp dòng mã hoá n bit sinh bởi k bit thông tin và bộ nhớ
m đợc gọi là mã xoắn (n,m,k). Tỷ số R=k/n cũng đợc gọi là tỷ số mã . Do tính chất

của mã xoắn nên nó phải đợc thực hiện bằng mạch dãy .
Đ 1.3 - Các ph ơng pháp biểu diễn mã .
1.3 - 1 : Phơng pháp liệt kê .
Đây là cách trình bày đơn giản nhất , liệt kê trong bảng những tin của nguồn tin
kèm theo là từ mã tơng
Ví dụ : Nguồn tin A = {a
1
, a
2
, a
3
, a
4
, a
5
} các lớp tin đợc mã hoá nh bảng sau .
Tin a
1
a
2
a
3
a
4
a
5
Từ mã 00 01 100 1010 1011

Bảng đối chiếu có u điểm là cho thấy cụ thể và tức thời tin và từ mã của nó .
Những bộ mã lớn thì quá cồng kềnh và khuyết điểm chính là không cho phép thấy

các tính chất quan trọng của bộ mã .
1.3 -2 : Phơng pháp mặt phẳng toạ độ của mã .
Phơng pháp này chỉ thích hợp loại mã có trọng số . Dựa trên 2 thông số của từ mã,
là độ dài n và trọng số b để lập một bề mặt có hai toạ độ . Trên đó mỗi từ mã đợc
biểu diễn bằng một điểm trọng số b của của từ mã là tổng trọng số các ký hiệu
trong từ
b =
1
1



m
n

(14)

k
: Trị của ký hiệu thứ k trong từ mã kể từ trái sang phải , với mã nhị phân
k
7
có hai trị 0 và 1.
k : số thứ tự của ký hiệu trong từ mã .
m : cơ số của mã .
Ví dụ : Trọng số của từ mã 1011 bằng :
b = 1 x 2
0
+0 x 2
1
+ 1 x 2

2
+ 1 x 2
3
= 13
Nh vậy , mỗi từ mã đợc biểu diễn bằng cặp n, b duy nhất .
Định lý : Không có hai từ mã khác nhau của một bộ mã thoả mãn đồng thời
n
i
= n
j
, b
i
= b
j
(i j ) .
Thật vậy giả thiét n
i
= n
j
để hai từ mã khác nhau thì ít nhất với một vị trí L nào đó
trị của ký hiệu của hai từ mã khác nhau , nghĩa là b
i
b
j .
Hoặc giả thiết b
i
= b
j
để hai từ mã khác nhau độ dài từ mã phải khác nhau n
i

n
j
Bộ mã đợc trình bày ở phơng pháp liệt kê nay đợc biểu diễn trong mặt toạ độ .
15
14
13 a
5
12
11
10
9
8
7
6
5 a
4
4
3
2 a
2
1 a
3
0 a
1

b
1.3 - 3 : Phơng pháp cây.
Cây mã gồm có nút và nhánh , gốc của cây gọi là nút gốc . Từ gốc phân đi m
nhánh hoặc ít hơn , mỗi nhánh đại biểu cho một trị ký hiệu với mã nhị phân (m=2)
có hai trị ký hiệu là 0 hoặc 1 . Mỗi nhánh kết thúc ở mức cao hơn nút xuất phát . Từ

mỗi nút ở mức i có thể phân m nhánh hoặc ít hơn , mỗi nhánh mang một trị ký hiệu
và kết thúc ở nút mức i + 1 . Nút cuối (nút kết rthúc không có nhánh nào xuât phát )
đại biểu cho một mã mà thứ tự các trị ký hiệu đi từ nút gốc đến nút cuối qua các nút
trung gian lấy theo thứ tự các trị ký hiệu trên các nhánh đi qua .
Ví dụ : Ta biểu diễn ví dụ trên bằng phơng pháp cây mã .
mức gốc mức (0)
0 1
mức 1 (n=1)
0 1 0
mức 2(n=2)
(00) (01)
mức 3 (n=3)
(100) 0 1
mức 4 (n=4)
(1010) (1011)
8
1
2
3
4
n
Phơng pháp này cho phép trình bày bộ mã một cách gọn hơn hai phơng pháp tr-
ớc , đồng thời cho thấy rõ tính chất quan trọng của mã nh tính phân cách đợc hay
tính Prefix
Nhìn cây mã ta có thể biết loại mã đã cho đều hay không đều , đầy hay vơi . Mã
đều là các nút nhánh có cùng bậc , ngợc lại là không đều . Mã đầy khi tất ca các nút
trung gian bậc trớc các nút nhánh là đều có m nhánh . Cây mã thuộc ví dụ trên thuộc
loại mã không đều .
1.3- 4: Phơng pháp đồ hình kết cấu .
Gồm những nút và những nhánh có hớng . Đây là một cách biểu diễn cây mã rút

gọn . Mỗi từ đợc biểu diễn bằng một vòng kín , xuất phát từ nút gốc theo nhánh có
hớng (chiều mũi tên) . Qua các nút trung gian và trở về kết thúc tại nút gốc . Thứ tự
giá trị các ký hiệu là theo thứ tự giá trị các nhánh trên đờng đi .

OV 1
0 1
0 0
1
OV
1

Đồ hình kết cấu của bộ mã : 00 ;01;100;1010;1011
Các nhánh đợc ghi ở đầu xuất phát của nhánh đầu biểu diễn toán tử hoặc các
nút đợc đánh số theo thứ tự xa dần nút gốc . Đồ hình nút gốc không chỉ dùng mô tả
mã mà còn đợc dùng để xét cách vận hành thiết bị mã hoá và giải mã .
1.3- 5 : Phơng pháp hàm cấu trúc mã .
Phơng pháp này mô tả rõ ràng một đặc tính quan trọng của mã là sự phân bố các
từ mã có độ dài khác nhau . Ký hiệu là G(n
i
) .
Ví dụ : Bộ mã 00,01,100,1010,1011; có G(n) dới dạng sau :
G(n
i
) =











=
=
=
4;2
3;1
1;2
i
i
i
n
n
n
Từ hàm cấu trúc có thể phân biệt đợc mã đều hay không đều , trờng hợp hàm cấu
trúc bằng không với tất cả các n
i
, trừ tai một điểm chúng ta có loại mã đều . Nếu
hàm cấu trúc có hai hoặc nhiều điểm khác 0 chúng ta có loại mã không đều, cũng từ
hàm cấu trúc có thể xác minh thoả mãn điều kiện có thể xác minh điều kiện phân
tách đợc hay không .
1.3 -6 : Phơng pháp ma trận sinh.
Phơng pháp này là mô hình toán để biểu diễn mã tuyến tính đây là công cụ toán
học đợc dùng để tạo mã tuyến tính .
Ma trận sinh là một ma trận mà từ ma trận đó có thể tạo ra tất cả các từ mã của bộ
mã bằng cách tổ hợp tuyến tính các hàng trong ma trận sinh là một bộ các số trong
các hàng hoặc các cột , số lợng cột bằng độ dài từ mã . Số hàng là số từ mã cơ sở
độc lập tuýen tính với nhau trong từ mã .

Mã tuyến tính C(n,k) là một không gian con K chiều của một không gian vectơ n
thàhh phần . Do vậy có thể tìm đợc k từ mã độc lập tuyến tính (g
0
,g
1
g
k-1
) trong C.
Mỗi từ mã trong C là một tổ hợp tuyến tính của k từ mã độc lập tuyến tính này .
V= u
0
g
0
+ u
1
g
1
+ + u
k-1
g
k-1
(15)
9
0
1
2
3
4
Với u
i

= 0 hoặc 1 và 0 i k .
Đạt k từ mã độc lập tuyến tính này thành những hàng của ma trận cấp k x n , nh
sau :
G =




















=

























1,1.1,10,1
1,11110
1,00100
1
1
0

.
.
.



.
.
.
nkkk
n
n
k
ggg
ggg
ggg
g
g
g
(16)
Với g
i
= (g
i0
g
i1
g
i,n-1
) , với 0 i <k
Nếu U = (u
0
u
1
u
k-1

) là thông tin cần đợc mã hoá các từ mã tạo ra là v đợc tính
theo công thức :
V = u x G = (u
0
, u
1
u
k-1
)




















1

1
0
.
.
.
k
g
g
g
(17)
V = u
0
g
0
+ u
1
g
1
+ + u
k-1
g
k-1
Các hàng của G tạo ra từ mã V , vậy G là ma trận sinh của C .
Ví dụ : Ta có mã hiệu 00000 : 10011: 0101010: 11001: 00101: 10110 : 01111 :
11100 .Đợc biểu diễn bằng ma trận sau :
G =











00101
01010
10011

G =












=













1010001
1110010
0110100
1101000
3
2
1
0
g
g
g
g

Nếu (1101) là thông tin cần mã hoá từ mã tơng đơng của nó là :
V = u
0
g
0


u
1
g
1



u
2
g
2


u
3
g
3
= (1101000)

(0110100)

(1010001) =
(0001101) .
1.3-7 Phơng pháp dùng đa thức sinh .
Dùng làm mô hình toán để biểu diễn mã đa thức, mã vòng .
Một từ mã có thể biểu diễn thuận tiện dới một đa thức .
f(x) = a
n-1
x
n-1
+ a
n-2
x
n-2
+ + a

2
x
2
+ a
1
x
1
+ a
0
(18)
+ Số hạng của đa thức trên là độ dài từ mã ( a
0
a
n-1
) .
+ Bậc của đa thức không vợt quá n-1 .
+ Hệ số a
i
nhận giá trị 0 koặc 1 .
+ x là ẩn số hình thức .
Ví dụ trong trờng hợp mã nhị phân với từ mã 1100110 có thể biểu diễn nh sau :
f(x) = x
6
+ x
5
+ x
2
+ x .
10
Đa thức sinh biểu diễn cho mã vòng ta thấy nh sau : Nếu a

1
a
2
a
n-1
, là một từ
mã thì tổ hợp đợc dịch chuyển một bậc a
n-1
a
1
a
2
a
n-2
cũng sẽ là một tổ hợp của
mã .
Một đặc điểm quan trọng dùng để giải mã là những từ mã đều chia chẵn cho một
đa thức p(x) gọi là đa thức sinh ( đa thức tạo mã ) . Sở dĩ gọi nh vậy là vì từ đa thức
này có thể tạo ra các từ mã của mã vòng , xuất phát từ những mã đơn giản , Nếu bậc
của mã đơn giản A(x) là k , bậc của mã vòng p(x) là n thì bậc của đa thức sinh bằng
n -k = r .
Đ 1.4 - Một số giới hạn mã .
Trong các loại mã , tiêu chuẩn quan trọng hàng đầu là khả năng phát hiện sai và
sửa sai của mã . Khả năng này đợc biểu thị bằng số ký hiệu sai tối đa có thẻ sửa đợc
trong tổ hợp nvà có liên quan đến trọng lợng tối thiểu của mã ( quãng cách mã ) .
Cũng nh số ký hiệu thử tối thiểu (nói cách khác là đọ dài n = r + k , tối thiểu khi giữ
không đổi số ký hiệu mang tin k ) . Cho nên khi xây dựng các loại mã sửa sai tối u
cần phải xác định trớc một số giới hạn của mã tuyến tính , nh : giới hạn trên về trọng
lợng tối thiểu (quãng cách mã ) . Giới hạn dới về số ký hiệu thử đối với mã tuyến
tính (n,k) .

1.4- 1: Giới hạn trên của quãng cách mã tối thiểu .
Giả sử bộ mã dùng cơ số m và có m
k
từ mã với độ dài từ mã là n .
Tổng số các ký hiệu trong m
k
sẽ là n m
k
.
Bộ mã dùng m ký hiệu khác nhau để lập nên các từ mã của bộ mã , nến coi sự
xuất hiện một ký hiệu nào đó trong từ mã là nh nhau thì xác suất xuất hiện của các
ký hiệu khác nhau trong từ mã sẽ là
m
1
.
Do đó tổng một số loại ký hiệu nào đó trong m
k
từ mã sẽ là .
n m
k

m
1
= n m
k-1
(19)
Trong m ký hiệu khác nhau , nhng chỉ có m-1 ký hiệu khác 0 , do đó tổng trọng
số các từ mã sẽ là :
W(


)

= n.m
k
m
1
(m-1) = n m
k-1
(m-1) . (20)
Với bộ mã đều nhị phân dài n , tổng trọng số các từ mã là :
W(

)

= n 2
k-1
(2-1) = n.2
k-1
. (21)
Trọng số trung bình của mỗi từ mã sẽ là :
( )
WƯ
=
1
)(
0
)(

=


k
m
w
khacmatucacsotong
w

(21)

( )
WƯ
=
1
)1(.
1



k
k
m
mmn
(22)
Với mã nhị phân trọng số trung bình của mỗi từ mã sẽ là :

( )
WƯ
=
12
2
1



k
k
n
(23)
Khoảng cách mã tối thiểu không thể vợt quá trọng số trung bình của từ mã . Do đó
giới hạn trên của khoảng cách từ mã tối thiểu của mã nhị phân đợc xác định theo
công thức:

d
0



12
2
1


k
k
n
(24)
11
Giới hạn dới của số ký hiệu thử đối với một mã dài mà trọng số tối thiểu bằng d .
1.4-2 - Giới hạn Plotkin E .
Chỉ có thể lập đợc bộ mã sửa hệ thống nhị phân (n,k) có khoảng cách tối thiểu d
0
, nếu số dấu kiểm tra r = n-k thoả mãn giới hạn dới :

r

2 (d
0
-1) - log
2
d
0
(25)
1.4-3- Giới hạn Griesmes (Đối với mã nhị phân).
Độ dài từ mã phải thoả mãn bất đẳng thức sau:
n




=






1
0
0
2
k
j
d

(26)
Trong đó : k - số dấu mang tin .
d
0
- khoảmg cách mã tối thiểu .







,
0
2
d
- lấy phần nguyên của
2
0
d
.
Dạng khác của (26) là : n

d
0
+ d
1
+ d
2
+ + d

k-1
(27)
Trong đó : d
1
=






+
2
1
0
d
; d
i+1
=






+
2
1
i
d


1.4- 4 - Giới hạn Hamming R.W .
Chỉ có thể lập đợc một bộ mã sửa hệ thống nhị phân (n,k) có độ dài n với
khoảng cách mã tối thiểu d
0
= 2e + 1, nếu số dấu kiểm tra thoả mãn giới hạn dới sau
:
r

log
2








=
e
0i
i
n
C
(28)
Trong đó : e - là số dấu sai có thể sửa đợc .
1.4- 5 - Varshamov .
Chỉ có thể xây dựng đợc một bộ mã sửa hệ thống nhị phân có độ dài n và khoảng
cách mã tối thiểu d

0
với r dấu kiểm tra phải thoả mãn bất đẳng thức sau :
2
r




=

20
d
0i
i
1n
C
(29)
1.4- 6 - Giới hạn GILBERT.E .
Khoảng cách mã tối thiểu thờng đợc xác định theo khả năng phát hiện sai
(d
0


t+1) hoặc khả năng sửa sai (d
0


2e + 1) hoặc theo khả năng phát hiện đợc t sai
và sửa đợc e sai (d
0



e+ t + 1).
Bớc 1 : Viết tất cả 2
n
từ mã có thể có .
Bớc 2 : Chọn một từ mã tuỳ ý trong 2
n
từ mã .
Bớc 3 : Bỏ đi (loại bỏ ) tất cả các từ mã có khoảng cách mã với từ mã đã chọn
nhỏ hơn hoặc bằng (d
0
-1) . Nếu sau khi loại bỏ các từ mã này ra khỏi 2
n
từ mã mà
không còn một từ mã nào thì kết thúc qúa trình lựa chọn số từ mã còn lại lập thành
bộ mã có khoảng cách mã tối thiểu lớn hơn hoặc bằng d
0
. Ngợc lại ta lặp lại bớc 2
rồi bớc 3 .
Để xác định số lợng từ mã tối thiểu có thể chọn đợc , ta tiến hành nh sau:
- Tổng số các từ mã có khoảng cách mã với từ mã đã chọn không vợt quá (d
0
-1)
là :


=
10
0

d
i
n
i
C
, với một từ mã đã chọn thì số từ mã bị loại bỏ đi ( vì có khoảng cách với
từ mã đã chọn ) nhỏ hơn hoặc bằng (d
0
- 1) không vợt quá


=
10
d
0i
i
n
C
.
12
Nh vậy , khi chọn N từ mã (số lần chọn) mà


=
10
d
0i
i
n
C

< 2
n
, thì ta có thể chọn đợc lần
nữa . Sau khi kết thúc quá trình chọn ta phải có :


=
10
0
d
i
n
i
C

2
n
.
Vậy số các đã chọn theo phơng pháp trên phải thoả mãn bất đẳng thức :
N


=

1d
0i
i
n
n
0

C
2
(30)

Định lý GILBERT E .
2.1. Mã sửa hệ thống nhị phân

2.1-1 - Khái niệm về mã phát hiện sai và sửa sai .
Mã phát hiện sai và sửa sai gồm các loại mã phát hiện sai , mã sửa sai và mã
phát hiện và sửa sai . Thông thờng chúng thuộc loại mã đều nhị phân .
Trong quá trình truyền tin trên kênh ( từ nơi gửi đến nơi nhận ) do tác động của
nhiều từ mã nhận đợc có thể bị sai . Có hai loại sai , một loại gọi là sai độc lập ,
nghĩa là trong quá trình truyền tin do nhiều tác động một hoặc nhiều ký hiệu trong
các tổ hợp mã có thể bị sai , nhầm . Nhng những sai , nhầm đó không có liên quan
đến nhau . Loại thứ hai , là những sai phụ thuộc lẫn nhau gọi là sai tơng quan gây ra
do bởi nhiều tơng quan . Trong trờng hợp sai thứ hai này hay sảy ra trờng hợp sai
từng chùm kí hiệu kế cận nhau, gọi là sai cụm.
Sự chọn cấu trúc của mã chống nhiễu phải dựa trên tính chất thống kê của kênh,
nói cách khác trên sự phân bố xác suất sai nhầm trong một kênh nhị phân đối xứng.
Kênh nhị phân đối xứng thuộc kênh chứa sai lầm không tơng quan và xác suất
chuyển đổi sai một ký hiệu 1 thành 0 hoặc ngợc lại 0 thành 1 nh nhau, nếu ký hiệu
các xác suất chuyển đổi đó bằng:
P(1/0) và P(0/1) thì có: P(1/0) = P(0/1) = P
Vậy xác suất nhận đúng một ký hiệu là 1 - P. Xác suất nhận đúng một từ mã gồm
n ký hiệu sẽ là (1 - P)
n
. Xác suất thu sai một từ mã đó bằng:
P
sai
= P

s
= 1 - (1 - P)
n
vì P <<
n
1
nên (1 - P)
n
= 1 - nP
Vì vậy xác suất thu sai một từ mã nào đó đợc tính gần đúng theo công thức P
s
= nP
Xác suất thu sai một từ mã tỷ lệ với độ dài từ mã n và xác suất thu sai một dấu nào
đó là P. Trong thực tế kỹ thuật truyền tin, xác suất thu sai một từ mã không đợc vợt
quá giới hạn cho phép P
s
cho phép ta có nP P
s
hay P
n
p
schophep
2.1.2. Xác suất thu sai i dấu bị sai trong từ mã gồm n ký hiệu.
Xác suất xảy ra i sai đồng thời bằng
i
s
P
. Xác suất xảy ra trong một từ mã có n
ký hiệu n - i ký hiệu xuất hiện đúng bằng.
(1 - P)

n-i
. Vậy xác suất xảy ra trong một từ mã n ký hiệu có i ký hiệu sai sẽ là:
( )
in
i
in
i
P1PP
=

=
Tổng số các từ mã n ký hiệu có i ký hiệu sai bất kỳ bằng
( )
!in!i
!n
C
i
n

=
Xác suất xuất hiện một từ mã n ký hiệu có i sai bất kỳ sẽ là
P
(n,i)
=
( )
in
ii
n
p1PC



13
P <<
n
1
=> P
s
=
( )
in
i
n
1i
i
n
P1PC

=


2.1.3. Cơ chế phát hiện sai
Khả năng phát hiện sai của mã dựa trên cơ chế sau: Nếu mã là tập hợp những
từ mã n ký hiệu, thì số các từ mã đợc chọn bé hơn tổng số các tổ hợp n ký hiệu. Số
các tổ hợp không đợc dùng làm từ mã đợc gọi là những tổ hợp cấm. Khi do sai nhầm
một từ mã chuyển đổi thành một tổ hợp mã cấm lúc đó sẽ phát hiện đợc đã thu sai.
Ví dụ trong từ mã nhị phân N là số từ mã đợc dùng và N
0
= 2
n
là tổng số các tổ hợp

ký hiệu mã có khả năng phát hiện sai khi N < N
0
; N = 2
k
khi đó N
0
- N là tổ hợp mã
cấm .
Khi truyền một từ mã nào đó do có nhiễu nên bị sai một dấu nào đó thì từ mã
này trở thành một trong những từ mã cấm, dựa vào đặc điểm này ta có thể phát hiện
đợc sai.
Khi truyền một từ mã nào đó khi có nhiễu sẽ trở thành N
0
từ mã có thể có .
Nh vậy khi truyền N từ mã đã dùng để mã các tin thì số các trờng hợp có thể có sẽ là
N
0
N = 2
n
2
k
. Trong số những trờng hợp này có N = 2
k
trờng hợp không bị sai, có N
(N - 1) = 2
k
(2
k
- 1) trờng hợp từ mã dùng chuyển thành từ mã khác ở trong trờng hợp
này không thể phát hiện đợc. Có N(N

0
- N) = 2
k
(2
n
- 2
k
) trờng hợp từ mã dùng
chuyển thành từ mã cấm ở trờng hợp này phát hiện đợc sai. Lập tỷ số ta có:
( )
( )
0
n
k
kn
knk
0
0
N
N
1
2
2
1
22
222
NN
NNN
==


=

Tỷ số này tiến đến 1 thì khả năng phát hiện sai càng lớn tức là N << N
0
=> n
>> k (k là số ít mang tin).
2.1.4. Cơ chế sửa sai
Để có thể sửa đợc sai ngời ta chia các từ mã cấm (N
0
- N) thành N tập con
không giao nhau M
i
với i =
N,1
. Mỗi tập con M
i
đáp ứng với một từ mã dùng. Nếu
từ mã nhận đợc nằm trong tập con M
i
thì coi rằng phía phát đã truyền đi tin a
i
. Nh
vậy số các trờng hợp sai có thể sửa đợc chính bằng số các từ mã cấm trong tập M và
bằng
( )
( )
NNN
N
NN
0

0
=

Do đó số các trờng hợp sửa đúng đợc là (N
0
- N) trong số các trờng hợp sai.
Vậy tỷ số giữa các trờng hợp sai có thể sẽ là:
( )
( )
N
1
2
1
NNN
NN
k
0
0
==


Quá trình sửa sai trong mã chống nhiễu đợc thực hiện nh sau
+ Để có thể sửa đợc sai thì bộ mã đều nhị phân phải có khoảng cách tối thiểu
d
0
đạt đợc một giá trị xác định nào đó d
0
d
0


cho phép
+ Khi nhận đợc một từ mã nào đó, ta so sánh với tất cả các từ mã dùng (N từ
mã) để tìm khoảng cách mã. Nếu khoảng cách mã tối thiểu d
0
< d
0 cho phép
thì kết luận
từ mã thu đợc đã bị sai. Sau đó chuyển từ mã sai về từ mã dùng có khoảng cách nhỏ
nhất với nó.
2.1.5. Điều kiện bộ mã đều nhị phân có khả năng phát hiện sai và sửa sai.
14
Bộ mã đều nhị phân và đầy (
1d;0D
0
day
2
==
) không có khả năng phát hiện sai,
không có khả năng chống nhiễu. Chỉ có bộ mã vơi mới có khả năng chống nhiễu
(phát hiện sai và sửa sai)
Nh vậy điều kiện để bộ mã đều nhị phân có khả năng chống nhiễu liên quan
đến khoảng cách tối thiểu d
0
.
+ Để bộ mã có thể phát hiện đợc t
sai
thì khoảng cách mã tối thiểu d
0
phải thỏa
mãn

d
0
t + 1
+ Để bộ mã có khả năng sửa đợc e sai thì khoảng cách tối thiểu d
0
phải thỏa
mã .
d
0
2e + 1
+ Để bộ mã có khả năng phát hiện đợc t
sai
và sửa đợc e
sai
thì d
0
phải thỏa mãn
d
0
e + t + 1
2.1- 6 -Bộ mã sửa hệ thống nhị phân .
Bộ mã sửa hệ thống nhị phân ký hiệu (n,k) là bộ mã đều có độ dài n và trong đó
có k dấu thông tin, số dấu còn lại r=n-k đợc gọi là các dấu kiểm tra, cơ số của bộ mã
m = 2.
Bộ mã sửa hệ thống nhị phân thuộc lớp mã khối tuyến tính ,không chỉ có khả
năng phát hiện sai mà còn có khả năng sửa sai.
Số dấu mà bộ mã có thể phát hiện hoặc sửa đợc sai phụ thuộc vào số lợng dấu
kiểm tra trong từ mã. Số lợng các dấu thông tin trong từ mã phụ thuộc số lợng các
tin cần mã hoá(2
k

= s, do đó k = log
2
s).
Ví dụ các dấu thông tin và các dấu kiểm tra trong mỗi từ mã của bộ mã sửa hệ
thống nhị phânđợc tách thành hai khối riêng biệt thì bộ mã sửa hệ thống nhị phân đ-
ợc xếp vào lớp mã khối tuyến tính . Nếu kí hiệu x
i
là dấu thứ i trong bộ mã ,ta có thể
biểu diễn các dấu thông tin của bộ mã sửa hệ thống nhị phân nh sau:
x
0
x
1
x
2
x
k-1
x
k
.x
n-1

k dấu thông tin r dấu kiểm tra
Kí hiệu

i
là từ mã thứ i của bộ mã sửa hệ thông nhị phân (n,k) đa thức
f
i
(x) biểu diễn


i
có

dạng tổng quát nh sau:
f
i
(x) = a
0
x
0
+ a
1
x
1
+ +a
k-1
x
k-1
+ a
k
x
k
+ +a
n-1
x
n-1
đa thức mang tin đa thức kiểm tra
f
i

(x)=f
k
(x) + f
r
(x)
Trong đó :
f
k
(x) : đa thức mang tin
f
r
(x) : đa thức kiểm tra
f
k
(x) = a
0
x
0
+a
1
x
1
+ +a
k-1
x
k-1
f
r
(x) = a
k

x
k
+a
k+1
x
k+1
+ +a
n-1
x
n-1
Hệ số a
i
nhận các giá trị 0 hoặc 1
( là các chữ số hay kí hiệu của hệ đếm a
i
=
1n,0
)
các dấu kiểm tra đợc xác định từ các dấu thông tin qua các phơng trình (còn đợc gọi
là tổng kiểm tra)
15
xCC
k
i
jij


=
=
1

0
j
với i =
1k,0

j =
1n,k
Trong đó


: tổng modul 2
C
ji
là phần tử hàng thứ j và cột thứ i của ma trận kiểm tra H(k,r) có dạng tổng quát

Hk,r)=



















+++
1,1,1 0,1
1,,0,
,1,10,1



kninn
kjijJ
kkikK
CCC
CCC
CCC
Phát hiện sai và sửa sai của bộ mã sửa hệ thống nhị phân thực hiện theo các bớc
nh sau:
+Mang từ mã thu đợc , tách thành các dấu mang tin và các dấu kiểm tra.
+Từ các dấu mang tin và ma trận kiểm tra H(k,r) lập lại các dấu kiểm tra.
So sánh các dấu kiểm tra lập đợc và các dấu kiểm tra trong từ mã thu đợc (so sánh
từng cặp cùng vị trí). Nếu có ít nhất một cặp khác nhau thì chứng tỏ từ mã thu đợc
đã bị sai.
Nếu có một cặp nào đó sai khác thì sai ở vị trí dấu kiểm tra và vị trí dấu sai chính
là vị trí của cặp sai khác đó. Lấy đảo của dấu sai sẽ đợc dấu đúng.
+ Nếu có hai hay nhiều cặp sai khác nhau thì vị dấu sai các dấu thông tin. Dấu
sai là dấu thông tin có mặt đồng thời trong các cặp sai khácđo.
Để minh hoạ cho quá trình phát hiện sai và sửa sai trong bộ mã sửa hệ thống nhị
phân ta xét ví dụ .

Bộ mã sửa hệ thống nhị phân (7,4) có ma trận kiểm tra H(4,3) nh dới đây:
H(4,3)=










1110
1101
1011
Hỏi từ mã nhận đợc

i
= 1011111 đúng hay sai. Nếu sai thì sai ở vị trí nào,hãy
sửa dấu sai đó.
Bộ mã sửa hệ thông nhị phân (7,4) có độ dài n = 7 ,số dấu thông tin k=4 và số dấu
kiểm tra r = n-k = 3.
Vị trí dấu thông tin và kiểm tra trong từ mã nhận đợc

i
1 0 1 1 1 1 1
x
0
x
1

x
2
x
3
x
4
x
5
x
6
Từ các dấu thông tin và kiểm tra
1 0 1 1
x
0
x
1
x
2
x
3
Và ma trận kiểm tra trong từ mã cho ta lập đợc các dấu kiểm tra.
x
4
=x
0

x
2

x

3
= 1

1

1 = 1
16
x
5
= x
0

x
1

x
3
= 1

0

1= 0
x
6
=x
0

x
1


x
2
= 1

0

1 = 0
So sánh
x
4
= 1 = x
4
= 1
x
5
= 0

x
5
= 1
x
6
= 0

x
6
= 1
Có hai cặp dấu kiểm tra sai khác nhau . Vậy sai ở vị trí dấu thông tin .Vì dấu
kiểm tra x
4

đúng nên các dấu thông tin x
0
,x
2
,x
3
đúng còn dấu thông tin x
1
có mặt
đồng thời ở trong 2 cặp khác nhau x
5
và x
6
. Do đó sai xảy ra ở vị trí dấu thông tin
thứ x
1
Từ mã tơng ứng sẽ là:

i
đúng =1111111 dấu sai đã đợc sửa
Bộ mã sửa hệ thông nhị phân (7,4) có khoảng cách mã tối thiểu d
0
=3(là bộ mã vơi )
nên có khả năng phát hiện đợc 2 sai và sửa đợc 1 sai vì thỏa mãn giới hạn Hamming
t

d
0
-1 và e









2
1
0
d
2.1.7. Bộ mã xyclic (mã vòng)
Mã vòng C(n,k) là bộ mã đều nhị phân có độ dài n, có k dấu thông tin và r= n-k
dấu kiểm tra . Mã Vòng C(n,k) cũng thuộc lớp mã khối tuyến tính
Định nghĩa 1: Mã C(n,k) là bộ mã đều nhị có độ dài n, có k dấu thông tin và
r = n - k dấu kiểm tra, trong đó mỗi từ mã của bộ mã đều là dịch vòng của một từ mã
khác trong cùng bộ mã và đợc kí hiêụ là C(n,k)
Để có khái niệm về phép dịch vòng trong mã C(n,k) ta biểu diễn từ mã

i
của mã
C(n,k) dới dạng đa thức


n
i

f
i
(x) =

1
1
1
1
0
0



+++
n
n
xaxaxa
(1)
Trong đó : a
i
nhận một trong các giá trị 0 hoặc 1 .
x là ẩn số hình thức , nó chỉ thứ tự (vị trí ) của dấu trong từ mã .
Thực hiện phép nhân hai vế của biểu thức trên với x ta đợc .
x f
i
(x) =
n
n
xaxaxa
1
2
1
1
0



+++
(2)
Để biểu thức trên biểu diễn một từ mã có độ dài n thì x
n
phải với 1(để bậc của
(2) không vợt quá n-1 , khi này ta có :


n
i

f
i
(x) =
1
2
1
0
0
1



+++
n
nn
xaxaxa
(3)

Và phép nhân haivế của (1) với x đợc coi phép dịch vòng một nhịp từ mã
n
i

thành từ mã
n
i

. Từ đó có định nghĩa 2 Mã C(n,k) .
Định nghĩa 2 : Mã C(n,k) là bộ mã đều nhị phân độ dài n , có k dấu thông tin và r
dấu kiểm tra , trong đó mỗi từ mã là dịch vòng của một từ mã khác cùng bộ mã lấy
theo mod (x
n
+1 ) (coi x
n
= 1).
Mã C(n,k) có đặc trng là đa thức sinh thờng đợc ký hiệu là g(x) . Dạng tổng quát
của g(x) nh sau :
g(x) = 1+ g
1
x
1
+ g
2
x
2
+ . + g
r
x
r

(4)
Trong đó : r là số dấu kiểm tra .
Bậc cao nhất của g(x) bằng số dấu kiểm tra của mã C(n,k) , g
i
nhận một trong các
giá trị 0 hoặc 1 , g(x) biểu diễn một từ mã khác 0 (từ mã có ít nhất một dấu khác 0)
và là đa thức biểu diễn từ mã có bậc thấp nhất .
Đa thức sinh g(x) là một nhân tử của đa thức : x
n
+1 :
17
x
n
+1= h(x) * g(x) .
Đa thức sinh có thể cho trớc hoặc đợc chọn là một nhân tử của đa thức x
n
+1 và
có các tính chất của đa thức sinh .
Một trong số các phơng pháp xây dựng mã C(n,k) là xuất phát từ đa thức sinh g(x) .
từ mã đầu tiên đợc xây dựng từ đa thức sinh (Vì đa thức sinh biểu diễn một từ mã
có bậc thấp nhất ) . Sau đó lần lợt thực hiện dịch vòng (k-1) nhịp để có đợc k từ mã.
Các từ mã này độc lập tuyến tính nhau và đợc gọi là các từ mã cơ sở (có k từ mã cơ
sở). Sau đó thực hiện lấy tổ hợp tuyến tính trong k từ mã cơ msở sẽ có đợc các từ mã
của bộ mã C(n,k) . Để mô tả nguyên tắc trên ta xét ví dụ sau:
Xây dựng bộ mã C(7.,4) , với g(x) = 1+x + x
3
. Từ mã đầu tiên viết từ g(x) :









=
=
=
=
) (0001101
.) (0011010
) (0110100
) tan (1101000
34
23
12
1




tuvongdich
tuvongdich
nhipmottuvongdich
phaibencungnhatcaobit

1

2


3

4
là các từ mã cơ sở .

5
=
1


2
= 1011100 .

6
=
1


3
= 1110010.

7
=
1


4
= 1100101.

8

=
2


3
= 0101110.

9
=
2



4
= 0110111.

10
=
3



4
= 001011.

11
=
1



2


3
=1000110.

12
=
1



2


4
= 1010001.

13
=
4



2


3
= 010001.


14
=
1



3


4
= 1111111.

15
=
1



2


4



3
= 100101.
Các từ mã trên có thể biểu diễn qua đa thức sinh nh sau :

socomatuCac

xgx
xgx
xgx
xg

)(.
)(.
)(.
)(
3
4
2
3
2
1







=
=
=
=






5
= (x+1)g(x)

6
= (x
2
+1)g(x)

7
= (x
3
+1)g(x)

8
= (x+1).x .g(x)

9
= (x
2
+1).x.g(x)

10
= (x
3
+1).x.g(x)


15
= (x

3
+x
2
+ x +1).x
2
.g(x)
Nếu lấy một từ mã nào đó trong các từ mã trên chia cho g(x) thì phép chia
bao giờ cũng không còn d (phép chia hết hay phép có số d = 0 ).
Tổng quát ta viết :
i
g(x).
Từ đó ngời ta đa ra định nghĩa thứ 3 mã C(n,k) .
18
Định nghĩa 3 : Mã C(n,k) là bộ mã đều nhị phân có độ dài n , k dấu thông
tin , r = n k dấu kiểm tra . Mỗi từ mã của bộ mã đều chia hêt cho đa thức
sinh g(x) của nó .
Định nghĩa 3 mã C(n,k) có nghĩa thực tế kỹ thuật , vị trí định nghĩa này ng-
ời ta dựng nguyên tắc mã hoá (tạo mã) và giải mã cùng các sơ đồ kèm theo
các nguyên tắc đó . Để xây dựng nguyên tắc chung tạo các từ mã
i
của mã
C(n,k) ta biểu diễn từ mã đó dới dạng đa thức sau :

i



kn
n
kn

kni
xaxaxaxaxf




+++++=
1
1
1
1
1
0
0
)(
Hay :

=)(xf
i
kn
kn
kn
kn
kn
kn
xaxaxaxaxa







++++++
1
1
1
1
0
0
r.số hạng. k. số hạng.
n. số hạng
f
i
(x) = f
r
(x)+ f
k

(x)
Trong đó: f
r
(x) = r( x) - Đa thức kiểm tra
=)(xf
k
kn
i
xa

).(
- Đa thức mang tin dịch vòng đi (n-k) nhịp

Mang
i
chia cho g(x) ta có:
f(x) có bậc nhỏ hơn g(x) nên r( x) chính là một phần d của phép chia.
Mặt khác ta có:
a
i
(x).x
n-k
= q (x)+
r (x)
g (x) g (x)
Trong đó: q (x) là thơng của phép chia:
a
i
(x).x
n-k
g (x)
r
,
(x) là phần d của phép chia:
a
i
(x).x
n-k
g (x)
(Bậc của r
,
(x) bé hơn bậc của g (x))
Nh vậy:


i
=
fi (x)
= q (x) +
r (x)
+
r
,
(x)
g (x) g (x) g (x) g (x)
Theo định nghĩa 3, thì
i
:
.
g (x) do đó:
r (x)
=
r
,
(x)
hay r (x) = r
,
(x)
g (x) g (x)
Để phép cộng modul 2 của
r (x)
và
r
,

(x)
sẽ bằng 0
g (x) g (x)
19
)(
).(
)(
)(
)(
)(
)( xg
xxa
xg
xr
xg
xf
xg
kn
iii

+==

Từ kết quả trên ta có thể biểu diễn
i
nh sau:

i
=
a
i

(x).x
n-k
+
r
,
(x)
g (x) g (x) g (x)
Hay:
i
= r
,
(x) + a
i
(x). x
n-k
Trong đó: r
,
(x) là phần d của phép chia:
a
i
(x).x
n-k
g (x)
a
i
(x)
n-k
là phần mang tin đã đợc dịch vòng (n-k) nhịp.
Ta có quy tắc sau:
+ Mang phần mang tin dịch đi (n-k) nhịp (r nhịp rồi) rồi chia cho đa thức sinh

để tìm phần d r (x). Lấy lấy phần mang tin đã dịch vòng (n-k) nhịp cộng với phần d r
(x) sẽ cho mã của bộ mã C (n,k) ứng với phần mang tin đó.
+ Mỗi phần mang tin đợc thực hiện theo quy tắc tạo mã C (n-k) nh trên sẽ đợc
bộ mã C (n-k). Mặt khác ta đã biết phép chia cho g (x) gồm các phép dịch vòng sang
phải và cộng modul 2 đợc thực hiện lần lợt cho đến khi phần d là đa thức r (x) có
bậc nhỏ hơn g (x).
sơ đồ tạo mã C (n,k) nh Hình (1)
V1 Xung nhịp 1ữk
go g1 g2 gr-1 gr
a
i
(x) vào
.
M1 M2 Mr-1 Mr H
V2
Xung nhịp ữn
Xung nhịp k + 1 ữ n Ra
(r (x) + a
i
(x))
( Hình :1) .
Từ sơ đồ tạo mã tổng quát ta có thể vẽ sơ đồ tạo mã C (n,k) với g (x) cụ thể:
Ví dụ: Sơ đồ tạo mã C (7,4) với g (x) = 1 + x
2
+ x
3
nh trên hình 2
Mạch chia cho g (x) V1

go=1 g2=1

20
1
2
r
1
2
3
Xung nhịp 5 ữ 7
r
i
(x) + a
i
.x
3
Xung nhịp 1 ữ 4
a
i
(x).x
3
vào
(Bít cao vào trớc)
M1 M2
H
Xung nhịp 1ữ7
V2
V2 Ra
( Hình : 2) .
Dựa vào định nghĩa 3 mã C (n,k) ta có quy tắc giải mã cho mã C (n,k).
Lấy từ mã nhận đợc chia cho g (x), nếu phép chia không còn d chứng tỏ từ đã
thu đợc là đúng ngợc lại từ mã thu đợc là sai.

Để thực hiện sửa sai, trớc hết phải xác định có sai và vị trí dấu sai, sau đó đa
dấu "l" cộng modul 2 với dấu sai sẽ cho dấu đúng. Từ quy tắc trên ta có sơ đồ giải
mã tổng quát cho mã C (n,k) nh hình 3
21
VI Bộ ghi dịch
Xung nhịp V2
1 ữ n al a2 an
Ra
Vào từ mã nhận (Từ mã
đúng)
đợc ít bao vào trớc Xung nhịp 1 ữ 2n

go g1 gr-l gr C. xung nhịp
M0 M1 M2 Mr-l

Xung nhịp lữn H
Ra c C (Mạch cấm)
o
*
Xung nhịp
Hình 3
Sơ đồ giải mã C (n,k) có sửa sai nh hình 4
V Bộ dịch n bít
Xung nhịp Cộng modul 2
l ữn al an Ra
Vào (Từ mã đúng)
Từ mã thu đợc Bộ chia cho g (x)
2.1.8. Mã truy toán (Mã xoắn, mã chập):
Mã truy toán còn đợc gọi là mã chập hay mã xoắn. Mã truy toán thuộc vào lớp
các mã liên tục nhị phân. So với mã sửa hệ thống nhị phân thì các dấu thông tin và

các dấu kiểm tra không tách thành từng khối riêng biệt. Do đó quán trình mã hoá và
giải mã các mã này đợc thực hiện liên tục trên dãy các dấu mã.
Nếu ký hiệu K là số dấu mang tin trong từ mã, n là độ dài từ mã thì số dấu kiểm
tra r = n k.
22
1 1
r
Bộ phân tích phần d để
xác định vị trí dấu sai
và đa ra bít "l"
Hình 4
Cũng nh các mã chống nhiễu tuyến tính số dấu kiểm ta càng nhiều thì đppj d
(độ thừa) của bộ mã càng lớn và do đó khả năng sửa đợc số sai càng lớn. Các dấu
kiểm tra trong mã truy toán cũng đợc tạo từ các dấu thông tin. Mỗi dấu kiểm tra là
tổ hợp tuyến tính của các dấu thông tin ở cách nhau một khoảng gọi là bớc coọng.
Các mã truy toán có khả năng sửa đợc sai chùm (sai chùm xảy ra dới tác động
của nhiễu xung có độ rộng lớn hơn độ rộng một dấu một ký hiệu trong từ mã).
Sơ đồ khối tổng quát tạo mã chập biểu diễn trên hình 5
Bộ ghi dịch
Xung nhịp
Các bít
Vào R1 R2 RR-1 RR
Thông tin
M1 M2 MR-1 MR
(Bộ cộng Modul)

2 0
0 0
1 0 0 M
CM 0 Dãy bít ra

(Chuyển mạch)
( Hình : 5) .
Sơ đồ khối tổng quát
+ Bộ ghi dịch : Gồm R tầng
+ Bộ cộng Modul 2 : M
+ Chuyển mạch CM : Gồm M tiếp điểm
Một số đặc trng cơ bản của mã chập.
Tốc độ mã hoá:
Giả sử vào hình 5 có một dấu thông tin, cứ sau mối xung nhịp dấu thông tinh
ghi dịch trong bộ ghi dịch. Chuyển mạch lần lợt dịch chuyển đến các đầu ra của các
bộ cộng Modul2 để nhận dãy các bít ra. Số các bít ra là M (bằng số bộ cộng Modul
2).
23
Tốc độ mã hoá đợc đánh giá bằng tỷ số 1/M ta có:
Tốc độ mã hoá
=
l
M
Tỷ lệ mã:
Nếu đầu vào có m dấu thông tin thì trong một chu trình chuyển mạnh thì sẽ
nhận đợc tốc độ mã hoá là
m
l
M
Đại lợng này đợc gọi là tỷ lệ mã:
Tỷ lệ mã =
l
M
Độ dài bắt buộc (hay khối lợng nhớ của bộ mã chập).
Nếu đầu vào của sơ đồ hình 5 có m dấu thông tin thì trong một chu trình

chuyển mạch bộ ghi dịch chỉ ghi đợc R dấu ( hay là một trong số m/R nhóm dấu
thông tin đầu vào).
Dãy bít ra ứng với m dấu thông tin đầu vào sẽ bằng:
m
. M
M
Đại lợng
m
. M
R
đợc gọi là độ dài bắt buộc của bộ mã chập. Đó cũng chính là khối lợng nhớ
(kích thớc nhớ) cần thiết của bộ mã chập.
Ta có: Độ dài bắt buộc của bộ mã chập
m
. M
R
Khoảng cách bảo vệ của bộ mã chập.
24
Nh trên đã phân tích, bộ mã chập có khả năng sửa đợc chùm sai. Nếu ký hiệu
độ dài chùm sai là b thì mã chập có khả năng sửa đợc chùm sai có độ dài là bội số
của n (b = 2,4,6,8, ).
Để sửa đợc chùm sai có độ dài càng lớn thì thiết bị mã hoá và giải mã càng phức tạp.
Các sai mà mã truy toán có thể sửa đợc cũng là những chùm sai đơn.
Do đó khoảng cách giữa hai chùn sai xảy ra phải cách nhau một khoảng cách
xác định tối thiểu đợc gọi là khoảng cách bảo vệ và ký hiệu là d. Để mã truy toán có
thể sửa đợc chùm sai thì trong khoảng cách bảo vệ không có bất cứ một sai nào xảy
ra.
Độ lớn khoảng bảo vệ d phụ thuộc từng sơ đồ tạo mã chập và phụ thuộc vào
độ dài chùm sai: d 3b + 1
Ví dụ về sơ đồ tạo mã chập (1/2) nh trên hình 6.

m bít thông tin vào M1
1 K


Ra 1 2 3 4
2 (CM)
A B C M2
Xung nhịp
( Hình : 6 )
Bộ ghi dịch (4 khâu) : R = 4
Có 2 bộ cộng modul2 : M = 2
Tốc độ mã hoá. Chuyển mạch k đợc đồng bộ bởi các dấu thông tin và kiểm tra.
Giả sử dãy m dấu thông tin đầu vào:
m = 1 0 1 1 0 1 1 1 0 0 0 1
25
Khi này trạng thái các khâu ghi dịch trong sơ đồ hình 6 biểu diễn trên bảng sau:
Xung
nhịp
Vào (dãy m)
Trạng thái các khâu ghi dịch
Các dấu
kiểm tra
1 2 3 4
1` 1 1 0 0 0 0
2 0 0 1 0 0 0
3 1 1 0 1 0 1
4 1 1 1 0 1 0
5 0 0 1 1 0 0
6 1 1 0 1 1 1
7 1 1 1 0 1 1

8 1 1 1 1 0 0
9 0 0 1 1 1 1
10 0 0 0 1 1 0
11 1 1 0 0 1 1
Dãy các bít (dấu) đầu ra của sơ đồ hình 6
1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1
( Có sơ đồ tạo mã hình 6) biểu diễn trên hình 7:
Xung nhịp M3

c u
a 1 2 3 4 5 6
Ra
l
Dấu thông tin
M1 V
h
Vào Dấu kiểm tra lập đợc
i
(CM) j
d p

Dấu kiểm tra
g
7 8 9 10

Xung nhịp
Tính Syndrom Sửa sai
( Hình : 6 )
Sơ đồ giải mã chập (1/2) với b = 4
26

Về nguyên tắc chung, mối sửa đợc sai trớc hết phải xác định đợc vị trí dấu sai,
rồi đa ra dấu "1" tơng ứng để cộng modul 2 với dấu sai (ở bộ cộng M3) sẽ cho dấu
đúng.
Để xác định vị trí dấu sai phải tách ra các dấu thông tin và các dấu kiểm tra
trong dãy các dấu nhận đợc. Từ các dấu thông tin lập lại các dấu kiểm tra và so sánh
với các dấu kiểm tra nhận đợc. Nếu không có sự sai khác nào, dãy các dấu nhận đợc
là đúng, ngợc lại đã có sai (khi này g = "1"). Khi này sơ đồ sửa sai đa ra dấu "l" ở
mạch và V đến cộng với dấu sai ở U. Đầu ra M3 cho dãy dấu đúng.
Trong thực tế bộ mã chập đợc sử dụng khá rộng rãi do khả năng sửa sai mã
nó. Ngời ta còn phân bộ mã chập thành bộ mã chập không hệ thống. Với các bộ mã
chập loại này, ngoài các đặc trng chung nh trên đã nêu ngời ta còn sử dụng các đặc
trng khác nh:
+ Véc tơ kết nối
+ Đa thức kết nối
+ Sơ đồ lới
+ Sơ đồ trạng thái
+ Cây mã.
Cũng có nhiều phơng pháp sử lý mã, đặc biết là phơng pháp giải mã cho các
bộ mã chập không hệ thống.
Thuật toán Viterbi (thuật toán chọn đờng đi ngắn nhât giữa 2 điểm theo trọng
số của các đoạn đờng đi) là thuật toán sử lý mã châp cho lời giải đúng với xác xuất
cao nhất (hay cho lời giải đúng với xác xuất nhỏ nhất).
27