VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
LỜI MỞ ĐẦU
Thông tin liên lạc đóng vai trò hết sức quan trọng trong cuộc sống, hầu hết chúng
ta luôn gắn liền với một vài dạng trao đổi thông tin nào đó. Các dạng trao đổi thông tin
có thể như: đàm thoại giữa người với người, đọc sách, gửi và nhận thư, nói chuyện qua
điện thoại, xem phim hay truyền hình, triển lãm tranh, tham dự diễn đàn…
Có hàng nghìn ví dụ khác nhau về thông tin liên lạc, trong đó thông tin số liệu là
một phần đặc biệt quan trọng trong toàn bộ lĩnh vực thông tin.
Thông tin để truyền được từ điểm này đến điểm khác phải có sự tham gia của 3
thành phần: nguồn tin là nơi phát sinh và chuyển thông điệp lên môi trường truyền,
môi trường truyền là phương tiện mang thông điệp và đích thu. Nếu một trong các
thành phần này không tồn tại thì truyền tin không thể xảy ra.
Một yếu tố quan trọng trong hệ thống thông tin là độ chính xác, thiếu yếu tố này hệ
thống xem như không có giá trị sử dụng, nên kèm theo bản tin thường phải thêm vào
các từ mã có khả năng phát hiện lỗi và thậm chí sửa được lỗi. Đó là sự ra đời của mã
phát hiện và sửa lổi, nhằm sửa những lỗi, sai sót trên đường truyền, đảm bảo sự tin
cậy, độ chính xác thông tin.
Nhóm chúng em đã làm đồ án môn học của mình để nghiên cứu về đề tài “mã phát
hiện lỗi và sửa lỗi trong truyền dẫn”. Đồ án gồm 3 chương:
Chương 1: Tổng quan về mã phát hiện lỗi và sửa lỗi.
Chương 2: Mã phát hiện lỗi và sửa lỗi.
Nhóm em xin chân thành cảm ơn thầy Nguyễn Vũ Anh Quang đã tận tình hướng
dẫn để nhóm hoàn thành đồ án. Trong quá trình làm bài còn có nhiều thiếu sót moang
thầy và các bạn góp ý và bổ sung để bài đồ án được hoàn thiện hơn.
SVTH: Thanh Hoa – Thanh Thúy Trang
i
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
MỤC LỤC
SVTH: Thanh Hoa – Thanh Thúy Trang
ii
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI

Các thống kê cho thấy rằng 88% các lỗi xẩy ra do sai lệch một bit và 10% các lỗi
xảy ra do sự sai lệch 2 bit kề nhau. Chính vì thế ta ưu tiên cho vấn đề phát hiện các lỗi
trên một bit và sửa đổi chúng một cách tự động.
1.2. Cơ chế lập mã
Như đã nói ở trên, mã phát hiện và sửa lỗi được thiết lập bằng cách thêm vào
thông tin cần truyền một số đượckiểm tra kết quả là làm cho tốc độ bit tăng lên nhưng
lại đạt được độ an toàn chống lỗi cao hơn. Ta hãy xét một ví dụ để minh hoạ điều này.
Giả sử ta muốn gửi đi một bít “0” hay một bít “1”. Để các bít này được bảo vệ ta
bổ sung thêm 3 bít kiểm tra theo cách sau:
Thông tin Bổ sung Gửi đi
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
SVTH: Thanh Hoa – Thanh Thúy Trang
2
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
Ðối với mỗi bit (0 hay 1) chỉ có một khối mã đúng (0 0 0 0 hay 1 1 1 1). Nếu thu
được bất cứ cái gì khác 0 0 0 0 hay 1 1 1 1 thì có nghĩa là đã xảy ra lỗi trên đường
truyền. Tỉ lệ mã ở đây là 1: 4 (1 bit thông tin: 4 bit phải truyền đi). Như vậy việc phát
hiện và sửa lỗi xảy ra như thế nào ? Ta hãy xét các khối mã dưới đây làm ví dụ:
Phát đi 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0
Thu được 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0
Quyết định 1 0 0 x 1 1
Nếu đường truyền không có lỗi thì các nhóm bit sẽ là 0 0 0 0 và hoặc 1 1 1 1 và
sẽ không có vấn đề gì trong việc quyết định phía phát đã phát đi 0 hay 1. Nếu 1 bit
trong số 4 bit bị lỗi ta có thể sửa nó, chẳng hạn phát đi 0 0 0 0, thu được 0 0 0 1, ta
quyết định là 0 đã được phát hay phát đi 1 1 1 1, thu được 0 1 1 1, ta quyết định là 1 đã
được phát Nhưng nếu có 2 bit bị mắc lỗi ta chỉ có thể phát hiện nhưng không thể
sửa lỗi, chẳng hạn phát đi 0 0 0 0, thu được 0 1 1 0 thì ta không thể quyết định là bit 1
hay bit 0 đã được phát. Cuối cùng nếu xảy ra 3 hay 4 lỗi thì ta không thể phát hiện
được và như vậy thông tin sẽ bị lỗi 1 bit. Có thể nói rằng với cách lập mã như trên ta

Hình 1.3: Mã hóa xoắn
CHƯƠNG 2: MÃ PHÁT HIỆN LỖI, SỬA LỖI
SVTH: Thanh Hoa – Thanh Thúy Trang
MÃ HÓA XOẴN
Khối tin N-1
Khối mã N
Khối tin
Khối tin sau mã hóa
Khối tin N
MÃ HÓA KHỐI
Thông tin Thông tin K.tra
Khối tin Khối tin sau mã hóa
4
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
2.1. Bộ mã phát hiện lỗi (Error-Detecting Codes)
Nhằm phát hiện lỗi người ta thêm vào dòng dữ liệu các bit kiểm tra. Phương pháp
này gọi chung là kiểm tra lỗi dư thừa (Redundancy error check methode), từ dư thừa
được dùng vì các bit thêm vào không phải là phần thông tin cần gửi đi.
2.1.1. Mã kiểm tra bit chẵn lẻ (Parity Bit)
2.1.1.1. Khái niệm
Mã chẵn - lẻ là một loại mã khối, trong đó bit kiểm tra được thiết lập dựa trên
việc đánh giá tính chẵn hoặc lẻ của các bit 0 hay 1 của các bit tin trong khối tin. Có thể
có một hoặc nhiều bit kiểm tra chẵn, lẻ trong một khối mã.
2.1.1.2. Dùng kiểm tra chẵn lẻ để dò ra một bit sai
Cơ chế lập mã: đây là phương pháp kiểm tra đơn giản nhất, bằng cách thêm vào
sau chuỗi dữ liệu (thường là một ký tự) một bit sao cho tổng số bit 1 kể cả bit thêm
vào là số chẵn (hoặc lẻ), ở máy thu kiểm tra lại tổng số này để biết có lỗi hay không.
Phương pháp đơn giản nên chất lượng không cao, nếu số lỗi là chẵn thì máy thu không
nhận ra.
Ví dụ 1: Lập mã chẵn, lẻ cho khối tin 0 0 1 0. Biết rằng mã được lập theo đặc tính

được chia ra thành các khung (frames), thực hiện kiểm tra cho từng khung, thay vì
phát mỗi lần một khung, người ta phát các tổ hợp bit cùng vị trí của các khung, nhiễu
có thể làm hỏng một trong các tổ hợp này và chuỗi bit sai này có thể được nhận ra ở
máy thu.
SVTH: Thanh Hoa – Thanh Thúy Trang
6
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
Ví dụ dưới đây minh họa cho việc kiểm tra phát hiện chuỗi dữ liệu sai:
Máy thu dò ra các khung có lỗi (các bit parity có dấu *) nhưng không xác định
được cột nào bị sai do đó phải yêu cầu máy phát phát lại tất cả các cột.
Như vậy phương pháp này có thể hiểu:
 Bên gửi bổ sung thêm các thông tin dư thừa vào số liệu cần gửi đi
một cách thích hợp.
 Bên nhận dựa trên các thông tin dư thừa để xác định xem gói tin nhận được có
bị lỗi hay không.
Đặc điểm:
 Chỉ dò được lỗi sai một số lẻ bit, không dò được lỗi sai một số chẵn bit
 Không sửa được lỗi
 Ít được dùng trong truyền dữ liệu đi xa, đặc biệt ở tốc độ cao
2.1.2. Mã kiểm tra tổng (Block Sum Check, BSC).
Một cải tiến của kiểm tra chẵn lẻ là kiểm tra tổng (Block Sum Check, BSC).
Cơ chế lập mã: thông tin được chia thành các nhóm, mỗi nhóm có n khối, mỗi
khối gồm m bit thông tin, sau đó thêm vào mỗi nhóm một khối m bit kiểm tra chẵn lẻ
[như vậy bản tin sau khi mã hoá có (n + 1) khối]. Việc thiết lập các bit kiểm tra chẵn lẻ
SVTH: Thanh Hoa – Thanh Thúy Trang
7
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
được thực hiện bằng cách kiểm tra đặc tính chẵn, lẻ của các bit 1 có cùng thứ tự trong
các khối tin của cùng một nhóm và đưa giá trị vào vị trí tương ứng trong khối bit kiểm
tra chẵn lẻ. Kiểm tra chẵn lẻ được thực hiện theo cả 2 chiều dọc (Vertical

)
Nguyên tắc tạo mã CRC: Tín hiệu cần phát đi trong khung gồm k bit và sẽ được
bên phát thêm vào n bit nữa để kiểm tra được gọi là FCS (Frame Check Sequence).
SVTH: Thanh Hoa – Thanh Thúy Trang
8
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
Như vậy tín hiệu phát đi bao gồm (k+n). Bên thu khi nhận được tín hiệu sẽ đem
chia cho một đa thức gọi là đa thức sinh đã biết trước (bên phát và bên thu đều cùng
chọn đa thức này). Và nếu phép chia không dư thì khung dữ liệu nhận không chứa lỗi.
Vấn đề được đặt ra là n bit thêm vào sẽ được xác định như thế nào khi đã biết
khung tin càn truyền đi, biết đa thức sinh nào đã được chọn.
N bit thêm vào đó được gọi là CRC (Cyclic Redundancy Check).
Các bước tính FCS:
Bước 1: chuyển thông báo nhị phân thành đa thức M(x). Chọn hàm cho trước G(x)
có bậc c, G(x) = x
c
+1 (c chính là độ dài của CRC)
Bước 2: nhân M(x) với x
c
Bước 3: thực hiện phép tính M(x). x
c
/ G(x) ta được phần nguyên và số dư:
Q(x) + R(x)/G(x) (R(x): chính là CRC)
Bước 4: thành lập FCS chính là thông báo cần truyền đi
FCS = x
c
.M(x) + R(x).
Ví dụ: thông tin cần truyền 110101
1) Tạo M(x) = X
5

+ X
3
+ X + 1
Thông tin cần truyền là: 110101011
Thu và kiểm tra CRC:
Ta có thông tin phát đi: FCS = x
c
.M(x) + R(x)
Và X
c
. M(x)/G(x) = Q(x) + R(x)/G(x)
Tại đầu thu ta thu được: FCS đem giá trị này chia cho Hàm sinh mã G(x) ta có:
Phần dư bằng 0
Ví dụ:
Thông tin cần truyền là: 110101011
Thông tin nhận được là: 110101011
Điều này có nghĩa là truyền đúng tức là R(x) phải bằng 0
Ta tiến hành kiểm tra CRC như sau:
Chuyển thông tin nhận được thành đa thức:
Đa thức sinh mà cả bên thu và bên phát đều đã biết G(x) = X
3
+ 1
Đem đa thức nhận được chia cho đa thức sinh G(x) phần dư sẽ bằng 0
Ta thực hiện phép chia như sau:
SVTH: Thanh Hoa – Thanh Thúy Trang
10
VIETHANIT MÃ PHÁT HIỆN & SỬA LỖI
Có 4 đa thức sinh chuẩn dùng để tạo mã CRC thông dụng:
CRC_12 = X
12

16
+ X
12
+ X
11
+ X
10
+ X
8
+ X
7
+ X
5
+ X
4
+ X
2
+ X + 1.
Hiệu quả của kỹ thuật của CRC: là phương pháp dò tìm lỗi rất hiệu quả. Nếu số
chia được chọn theo nguyên tắc đã nêu truớc đó thì:
 CRC có thể dò tất cả các lỗi bit chùm có chiều dài nhỏ hơn hoặc bằng bậc của
đa thức.
 CRC có thể dò tìm với khả năng tìm thấy lỗi bit chùm bit có chiều dài lớn hơn
bậc của đa thức.
2.2. Bộ mã sửa lỗi (Error-correcting codes)
Mã Hamming là một mã sửa lỗi tuyến tính (linear error-correcting code), được đặt
tên theo tên của người phát minh ra nó, Richard Hamming. Mã Hamming có thể phát
hiện một bit hoặc hai bit bị lỗi (single and double-bit errors). Mã Hamming còn có thể
sửa các lỗi do một bit bị sai gây ra.
SVTH: Thanh Hoa – Thanh Thúy Trang

KẾT LUẬN
Trong quá trình nghiên cứu về các loại mã phát hiện và sửa lỗi, chúng em đã thấy
được tầm quan trọng của việc phát hiện và sửa lổi, nhằm sửa những lỗi, sai sót trên
đường truyền, đảm bảo sự tin cậy, độ chính xác thông tin trong truyền dẫn. Biết được
các đặc điểm và cơ chế phát hiện và sửa lỗi của các loại mã.
Trong quá trình thực hiện, chúng em cũng không thể tránh được những thiếu sót,
mong thầy và các bạn góp ý và bổ sung để bài được hoàn thiện hơn
Em xin chân thành cảm ơn !
SVTH: Thanh Hoa – Thanh Thúy Trang
14