1

ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

BÁO CÁO
BÀI TẬP LỚN ĐẠI SỐ TUYẾN TÍNH
ĐỀ TÀI 6:
MÃ HAMMING

Giảng viên hướng dẫn : TS. Nguyễn Xuân Mỹ


2

Lớp : L14
Nhóm : 6

MỤC LỤC

1. Giới thiệu Mã Hamming (7,4) ...................................................................1
1.1.

Lịch sử .................................................................................1

1.2.

Khái niệm ............................................................................1

1.3.

Ưu điểm ..............................................................................2

1.4.

Nhược điểm.........................................................................2

2. Ví dụ ........................................................................................................ 2
3. Minh họa mã Hamming bằng Matlab .......................................................4
3.1.

Vấn đề .................................................................................4

3.2.

Code .................................................................................... 5

3.3.

Ví dụ ....................................................................................

4. Ứng dụng vào đời sống ............................................................................6
Truyền tin trong không gian ...........................................................6
Tài liệu tham khảo .............................................................................................. 7
Kết luận.............................................................................................................. 7


1

Mã Hamming (7,4) là một trong những nguyên lý về mật mã đặt nền móng cho sự
phát triển của quá trình truyền tải, sửa lỗi thơng tin và ứng dụng thông tin vào các

mặt của của đời sống hiện đại. Thơng qua các cơ sở lý thuyết, ví dụ, cũng như
các chương trình minh họa và các ứng dụng thực tiễn, chúng ta sẽ hiểu rõ hơn về
tính chất của loại mã này.
1. GIỚI THIỆU VỀ MÃ HAMMING (7,4)
1.1.

Lịch sử:

Từ những lỗi phát sinh khó chịu thường gặp trong việc vận hành máy điện cơ:
-

Tốc độ hoạt động chậm.

-

Luôn gây ra lỗi khi đọc.

-

Không tự sửa lỗi được mà chuyển sang công việc khác

Hamming đã xây dựng hàng loạt các thuật tốn có hiệu quả cao để giải quyết vấn đề sửa
lỗi. Năm 1950, ông đã công bố một phương pháp mà hiện nay được biết là Mã Hamming.
1.2.

Khái niệm

Với mỗi nhóm 4 bit dữ liệu, mã Hamming thêm 3 bit kiểm tra. Thuật tốn (7,4) của
Hamming có thể sửa chữa bất cứ một bit lỗi nào, và phát hiện tất cả lỗi của 1 bit, và các lỗi
của 2 bit gây ra.

Sơ đồ:


2

Thêm
bit
kiểm
tra

Mã
ban
đầu

1.3.
-

Mã gửi
đi

Mã
nhận
được

Kiểm
tra,
sửa lỗi

Mã đã
sửa lỗi


Ưu điểm

Có thể phát hiện tối đa các lỗi trong trường 2 bit hoặc sửa lỗi trong trường 1 bit mà
khơng cần tìm ra cụ thể lõi đó là lỗi thế nào, nằm ở đâu.

-

Phương pháp mã Hamming có hiệu quả trên các mạng nơi các luồng dữ liệu được
cung cấp cho các lỗi 1 bit.

-

Mã Hamming sử dụng dễ dàng nên phù hợp ứng dụng trong các bộ nhớ máy tính và
sửa lỗi đơn.
1.4.

Nhược điểm

Nếu nhiều bit bị lỗi,có thể dẫn đến 1 bit khác bị thay đổi,điều này có thể khiến dữ liệu bị
sai sót thêm.
2. Ví dụ
Ngun lý của mã Hamming bắt nguồn từ việc khai triển và mở rộng quan điểm chẵn lẻ.
Việc khai triển này bắt đầu bằng việc nhân các ma trận, được gọi là Ma trận Hamming.
Ta có ma trận:


3

và


-

Để truyền gửi dữ liệu, chúng ta hãy nhóm các bit dữ liệu mà mình muốn gửi thành
một vectơ. Lấy ví dụ, nếu dữ liệu là "1011" thì vectơ của nó là:

P=
-

Giả sử, chúng ta muốn truyền gửi dữ liệu trên. Chúng ta tìm tích của He và P

He P =

=

= r

TH1: Giả sử khơng có lỗi xảy ra thì tín hiệu máy thu thu được là r’ giống với r
-

Máy thu sẽ nhân Hd  với r’, để kiểm tra xem có lỗi xảy ra hay không


4

=
-

Vì chúng ta được một vectơ tồn số khơng cho nên máy thu có thể kết luận là khơng
có lỗi xảy ra.


TH2: Nếu có lỗi xảy ra ở 1 bit. Ví dụ là bit số 5
Thì vector mà máy thu nhận được là:
-

Máy thu sẽ nhân Hd với r’ thu được kết quả là

Ta được một vector giống với cột thứ 5 của Hd nên bit thứ 5 của r’ bị lỗi. Ta chỉ việc
chuyển 0 thành 1 và ngược lại.
3. MINH HỌA MÃ HAMMING BẰNG CHƯƠNG TRÌNH SỬA LỖI TRONG
MƠI TRƯỜNG MATLAB
3.1.

Vấn đề:
Nhập một đoạn mã có số bất kì từ hai số 0 và 1, sau đó truyền đi. Để nhận
được mã chính xác ban đầu, ta phải thêm vào một đoạn ba bit để sửa lỗi phát
sinh trong q trình truyền đi, khi đó đoạn mã nhận được sẽ chính xác.


5

3.2.

Code

function Hamming_Code
syms w v a i t x
a=input('Nhap thong tin can chuyen a=');
H=[1 1 0 1 1 0 0 ;1 0 1 1 0 1 0;0 1 1 1 0 0 1];
G=[1 1 1 0 0 0 0; 1 1 0 1 1 0 0 ; 0 1 0 1 0 1 0; 1 0 0 1 0 0 1];

v=a*G;
for i=1:7
if mod(v(1,i),2)==0;
v(1,i)=0;
else v(1,i)=1;
end
end
num2str(v);
fprintf('Ma tran chuyen di\n');
disp(v);
w=input ('Nhap vector nhan duoc w=');
x=H*w';
for i=1:3
if mod(x(i,1),2)==0;%chuyen ve 0 va 1
x(i,1)=0;
else x(i,1)=1;
end
end
for i=1:7
if x==H(:,i);
t=i;
break;
else t=0;
end
end
if t~=0
if w(1,t)==0;
w(1,t)=1;
else w(1,t)=0;
end

end
num2str(w);
fprintf('Ma tran sau khi chuyen doi \n');
disp(v);
end

3.3.

Ví dụ minh họa

Một tín hiệu gửi đi gồm 4 bit “1 0 0 1”. Tín hiệu nhận được là “0 1 1 1 0 0 0”. Thực
hiện trong môi trường Matlab để tìm bit sai và sửa lại cho đúng.


6

4. ỨNG DỤNG THỰC TẾ VÀO ĐỜI SỐNG:
Được sử dụng vào tính tốn máy tính, thơng tin liên lạc, nén thông tin.
Ứng dụng truyền thông tin trong không gian:
-

Các vệ tinh, các tàu thám hiểm trong vũ trụ khi thường chụp các ảnh của các hành tinh
khác, sau đó gửi về Trái Đất.

-

Trong q trình truyền thơng tin đi, ảnh chụp được mã hóa bằng các đoạn mã 0 và 1,
và mơi trường truyền ln có từ trường làm nhiễu loạn thơng tin, dẫn đến thơng tin bị
sai, khi đó ảnh sẽ bị nhiễu hay hư hỏng, khơng cịn giữ được trạng thái ban đầu.


-

Khi đó mã Hamming được áp dụng để nhận biết và sửa các thông tin sai trước khi
trạm ở mặt đất nhận được thơng tin chính xác.

Ngoài ra, nhờ việc ứng dụng mã Hamming vào việc truyền thơng tin mà ta có được những
bức ảnh từ vệ tinh với chất lượng ảnh rõ nét.


7

Lỗi khi truyền hình ảnh dưới dạng mã qua mơi trường vũ trụ
Nguồn :youtube


8

TÀI LIỆU THAM KHẢO
[1] Mã Hamming. Truy câp 2/12/2019 .
[2] Ứng dụng thực tế mã sửa sai.Truy câp 2/12/2019