(TIỂU LUẬN) báo cáo bài tập lớn đại số TUYẾN TÍNH đề tài 6 mã HAMMING
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (419.37 KB, 10 trang )
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) ......................................
2.Ví dụ ...........................................................................
3.Minh họa mã Hamming bằng Matlab ..........................
4.Ứng dụng vào đời sống ...............................................
Truyền tin trong không gian ........................................
Tài liệu tham khảo ..............................................................................................
Kết luận..............................................................................................................
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
Mã
ban
đầu
1.3.
-
Ư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=[1101100;1011010;0111001];
G=[1110000;1101100;0101010;1001001]; 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
