ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
------------------------

VŨ HOÀNG DƢƠNG

NGHIÊN CỨU CÁC KỸ THUẬT ẨN TIN, GIẤU TIN KẾT HỢP MÃ
HÓA TRONG MÔI TRƢỜNG ĐA PHƢƠNG TIỆN ĐỂ
ĐẢM BẢO AN TOÀN THÔNG TIN VÀ XÂY DỰNG ỨNG DỤNG
Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. Hồ Văn Hƣơng

HÀ NỘI - 2015


1

LỜI CAM ĐOAN
Tôi xin cam đoan kết quả trong luận văn là sản phẩm của riêng cá nhân tôi.
Trong toàn bộ nội dung của luận văn, những điều đƣợc trình bày hoặc là của cá nhân
hoặc là đƣợc tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có
xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp.
Tôi xin hoàn toàn chịu trách nhiệm theo quy định cho lời cam đoan của mình.
Hà Nội, ngày 29/5/2015
Ngƣời cam đoan


MỤC LỤC .......................................................................................................................3
DANH MỤC CÁC KÝ HIỆU VIẾT TẮT ......................................................................6
DANH MỤC CÁC BẢNG ..............................................................................................7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .........................................................................8
LỜI MỞ ĐẦU .................................................................................................................9
Chƣơng 1: CƠ SỞ LÝ THUYẾT ..................................................................................11
1.1. Tổng quan về giấu tin .........................................................................................11
1.1.1. Khái niệm giấu tin ........................................................................................11
1.1.2. Các thành phần của hệ giấu tin .....................................................................11
1.1.3. Giấu tin và mật mã ........................................................................................12
1.1.4. Phân loại giấu tin ..........................................................................................12
1.1.5. Môi trƣờng giấu tin .......................................................................................13
1.1.6. Các tiêu chí đánh giá kỹ thuật giấu tin trong ảnh .........................................14
1.1.7. Đánh giá chất lƣợng ảnh sau khi giấu tin PSNR ..........................................15
1.1.8. Ứng dụng của giấu tin...................................................................................16
1.1.9. Kỹ thuật tấn công hệ giấu tin ........................................................................17
1.1.10. Một số chƣơng trình giấu tin ......................................................................18
1.2. Tổng quan mã hoá thông tin ...............................................................................19
1.2.1. Sơ lƣợc về lịch sử mật mã học ......................................................................19
1.2.2. Các khái niệm cơ bản....................................................................................19
1.2.3. Phân loại hệ mật mã ......................................................................................21
1.3. Mã Hamming ......................................................................................................24


4

1.3.1. Định nghĩa.....................................................................................................24
1.3.2. Vấn đề phát hiện sai và sửa sai .....................................................................24
1.3.3. Cách phát hiện sai .........................................................................................24
1.3.4. Cách sửa sai ..................................................................................................25

3.4. Kết chƣơng ..........................................................................................................62
KẾT LUẬN ...................................................................................................................63
TÀI LIỆU THAM KHẢO .............................................................................................64
PHỤ LỤC ......................................................................................................................66


6

DANH MỤC CÁC KÝ HIỆU VIẾT TẮT
VIẾT TẮT

TỪ GỐC

NGHĨA TIẾNG VIỆT

3-DES

Triple Data Encrytion Standard

Áp dụng giải thuật DES 3
lần cho mỗi khối dữ liệu

ADC

Analog to Digital Converter

Chuyển đổi từ tín hiệu
tƣơng tự sang tín hiệu số

AES


HAS

Human Auditory System

Hệ thông thính giác con
ngƣời

HVS

Human Vision System

Hệ thống thị giác của con
ngƣời

JPEG

Joint Photographic Experts
Group

Ảnh nén có mất mát thông
tin

LSB

Least Significant Bit

Bit có trọng số thấp hay Bit
ít quan trọng




8

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1: Sơ đồ chung của hệ giấu tin mật ...................................................................11
Hình 1.2: Các nhánh của giấu tin ..................................................................................12
Hình 1.3: Cân nhắc giữa chất lƣợng, dung lƣợng và tính bền vững .............................15
Hình 1.4: Quá trình mã hóa và giải mã .........................................................................20
Hình 1.5: Mô hình hệ thống mã hoá khoá bí mật ..........................................................21
Hình 1.6: Mô hình hệ thống mã hoá với khoá công khai ..............................................23
Hình 2.1: Ảnh số ............................................................................................................29
Hình 2.2: Cấu trúc tệp ảnh bitmap.................................................................................30
Hình 2. 3: Biểu đồ Historgram của ảnh đa cấp xám Lena.............................................32
Hình 2.4: Ma trận ảnh số ...............................................................................................35
Hình 2.5: Bit thay đổi từ 0 sang 1 .................................................................................36
Hình 3.1: Lƣợc đồ giấu tin phía ngƣời gửi ....................................................................52
Hình 3.2: Lƣợc đồ giấu tin phía ngƣời nhận .................................................................52
Hình 3.3: Mô tả hoạt động của RSA .............................................................................53
Hình 3.4: Thuật toán mã hóa RSA ................................................................................54
Hình 3.5: Sơ đồ giấu tin mật..........................................................................................56
Hình 3.6: Sơ đồ tách tin mật ..........................................................................................57
Hình 3.7: Giao diện giấu tin mật ...................................................................................58
Hình 3.8: Giao diện tách tin mật ...................................................................................58
Hình 3.9: Thông điệp bí mật dùng để giấu tin (272 bit) ................................................59
Hình 3.10: Tập ảnh thử nghiệm .....................................................................................59


9


việc kết hợp các kỹ thuật mã hoá thông tin, giấu tin mật.
Nội dung luận văn đƣợc tổ chức 3 chƣơng nhƣ sau:
Chƣơng 1: Cơ sở lý thuyết
Trình bày tổng quan về giấu tin, mã hóa thông tin và mã Hamming
Chƣơng 2: Một số phƣơng pháp giấu tin trong ảnh số


10

Trình bày về định nghĩa, phân loại ảnh số, một số phƣơng pháp giấu tin trong
ảnh, các thuật toán giấu tin trong ảnh và thuật toán giấu tin dựa trên mã Hamming.
Chƣơng 3: Xây dựng một ứng dụng kết hợp mã hóa và giấu tin để đảm bảo
an toàn thông tin.
Trình bày xây dựng chƣơng trình demo để thử nghiệm giải pháp đã đề xuất: kết
hợp kĩ thuật mã hóa và kĩ thuật giấu tin.


11

Chƣơng 1: CƠ SỞ LÝ THUYẾT
1.1. Tổng quan về giấu tin
1.1.1. Khái niệm giấu tin
Giấu tin là kỹ thuật nhúng (giấu) một lƣợng thông tin số nào đó vào một vật
mang tin khác. Giấu tin trong ảnh số là giấu tin các mẩu tin cũng dạng số trong máy
tính vào các tệp ảnh nhị phân sao cho không bị ngƣời ngoài phát hiện [2].
Kỹ thuật giấu tin nhằm hai mục đích: một là bảo mật cho dữ liệu đƣợc đem giấu,
hai là bảo vệ cho chính đối tƣợng mang tin giấu. Hai mục đích khác nhau này dẫn đến
hai kỹ thuật chủ yếu của giấu tin. Đó là giấu tin mật (Steganography) và thủy vân số
hay thủy ấn (Watermaking).
1.1.2. Các thành phần của hệ giấu tin

Hình 1.2: Các nhánh của giấu tin

Thủy ấn (Water marking) - Thủy vân là lĩnh vực nghiên cứu việc nhúng thông
tin phục vụ xác thực, ví dụ nhƣ xác nhận bản quyền… Nếu thông tin giấu là một định
danh duy nhất, ví dụ nhƣ định danh ngƣời dùng, thì ngƣời ta gọi đó là Fingerprinting
(nhận dạng vân tay, điểm chỉ).
Giấu tin mật (Steganography) là lĩnh vực nghiên cứu việc nhúng các tin mật vào
một môi trƣờng phủ. Trong quá trình giấu tin, để tăng tính bảo mật, ngƣời ta có thể
dùng một khoá viết mật, khi đó ngƣời ta nói về Intrinsic Steganography (giấu tin có
xử lý). Để giải mã ngƣời dùng cũng phải có khoá viết mật đó. Khoá này có thể không
phải là khoá dùng để lập mật mã mẩu tin, ví dụ nó có thể là khoá để sinh ra hàm băm
phục vụ rải tin vào môi trƣờng phủ. Ngƣợc lại nếu không dùng khoá viết mật thì ngƣời
ta chỉ giấu tin đơn thuần vào môi trƣờng phủ thì khi đó ngƣời ta nói về Pure
Steganography (giấu tin đơn thuần).
So sánh Thủy ấn (Watermaking) và Giấu tin mật (Steganography):
Xét về tính chất thuỷ ấn giống giấu tin mật ở chỗ tìm cách nhúng thông tin mật
vào một môi trƣờng. Tuy nhiên xét về bản chất thì thuỷ ấn có những nét khác ở một số


13

điểm:
- Mục tiêu của thuỷ ấn là nhúng thông tin không lớn thƣờng là biểu tƣợng, chữ
ký hay các đánh dấu khác vào môi trƣờng phủ nhằm phục vụ việc xác nhận bản quyền.
- Khác với giấu tin mật ở chỗ giấu tin mật sau đó cần tách lại tin còn thuỷ ấn tìm
cách biến tin giấu thành một thuộc tính của vật mang.
- Chỉ tiêu quan trọng nhất của một thuỷ ấn là tính bền vững, của giấu tin mật là
dung lƣợng giấu.
- Điểm khác nữa giữa thuỷ ấn và giấu tin mật là thuỷ ấn có thể vô hình hoặc hữu
hình trên vật mang.


Giấu thông tin vào các văn bản dạng text khó thực hiện hơn do có ít các thông tin
dƣ thừa, để làm đƣợc điều này ngƣời ta phải khéo léo khai thác các dƣ thừa tự nhiên
của ngôn ngữ. Một cách khác là tận dụng các định dạng văn bản (mã hóa thông tin và
khoảng cách giữa các từ khóa hay các dòng văn bản). Từ nội dung của thông điệp cần
truyền đi, ngƣời ta cũng có thể sử dụng văn phạm phi ngữ cảnh để tạo nên các văn bản
“phƣơng tiện chứa” rồi truyền đi.
1.1.6. Các tiêu chí đánh giá kỹ thuật giấu tin trong ảnh
Giấu tin mật là một lĩnh vực mới, đã và đang đƣợc nghiên cứu, thực nghiệm theo
nhiều phƣơng pháp khác nhau. Để đánh giá chất lƣợng của một phƣơng pháp giấu tin
mật, ngƣời ta thƣờng dựa vào các tiêu chí sau:
Đảm bảo tính vô hình
Giấu tin mật sẽ làm biến đổi vật mang tin. Tính vô hình thể hiện mức độ bị biến
đổi của vật mang. Phƣơng pháp giấu tin mật tốt sẽ làm cho thông tin cần giấu trở lên
vô hình trên vật mang, tức là làm ngƣời dùng khó có thể nhận ra trong vật mang có ẩn
chứa thông tin mật. Tuy nhiên, thực tế không phải lúc nào ngƣời ta cũng cố gắng để
đạt đƣợc tính vô hình cao nhất. Ví dụ trong truyền hình, ngƣời ta gắn hình ảnh mờ gọi
là thuỷ ấn để bảo vệ bản quyền bản tin.
Khả năng chống giả mạo
Mục đích của giấu tin mật là để truyền đi thông tin mật. Nếu không thể do thám
tin mật thì kẻ địch cũng cố tìm cách làm sai lạc tin mật, làm giả tạo tin mật đ gây bất
lợi cho đối phƣơng. Một phƣơng pháp giấu tin tốt phải đảm bảo tin mật không bị tấn
công một cách chủ động trên cơ sở những hiểu biết về thuật toán nhúng tin (nhƣng
không biết khoá giấu tin) và có vật mang.
Đối với lĩnh vực thủy ấn số thì khả năng chống giả mạo là yêu cầu vô cùng quan
trọng vì có nhƣ vậy mới bảo vệ đƣợc bản quyền, minh chứng tính pháp lý của sản
phẩm.
Dung lƣợng nhúng
Dung lƣợng giấu đƣợc tính bằng tỷ lệ của lƣợng tin cần giấu so với kích thƣớc
của vật mang tin. Các phƣơng pháp này đều cố gắng giấu đƣợc càng nhiều tin càng tốt

𝑚

𝑛

(𝑥𝑖𝑗 − 𝑦𝑖𝑗 )2
𝑖=1 𝑗 =1

Ở đây: xij biểu thị giá trị điểm ảnh gốc, và yij biểu thị giá trị điểm ảnh đã đƣợc
biến đổi, m và n lần lƣợt là chiều rộng và chiều cao của ảnh.
PSNR, đơn vị: deciben (dB), thƣờng đƣợc sử dụng trong nghiên cứu xử lý hình
ảnh:


16

2552
𝑃𝑆𝑁𝑅 = 10 ∗ log10 (
)
𝑀𝑆𝐸
Thông thƣờng, nếu PSNR >37 dB thì hệ thống mắt thƣờng gần nhƣ không phân
biệt đƣợc giữa ảnh gốc và ảnh giấu tin. PSNR càng cao thì chất lƣợng ảnh đã giấu tin
càng tốt. Khi hai hình ảnh giống hệt nhau, MSE sẽ bằng 0 và PSNR sẽ đi đến vô hạn.
1.1.8. Ứng dụng của giấu tin
Liên lạc bí mật
Trong mã hoá, bản mã của tin mật có thể gây ra sự chú ý của tin tặc nhƣng tin
mật đƣợc giấu vào trong môi trƣờng nào đó rồi gửi đi trên mạng máy tính thì ít gây ra
sự chú ý của tin tặc. Đó là một ứng dụng của giấu tin.
Hiện nay ngƣời ta phối hợp đồng thời nhiều giải pháp để truyền tin mật trên
mạng công khai. Đầu tiên tin mật đƣợc nén lại, sau đó đƣợc mã hoá, cuối cùng giấu
bản mã vào môi trƣờng nào đó.

lạc bí mật, việc phát hiện và chứng minh đƣợc một vật có chứa tin mật đƣợc coi là
thành công. Đối với bảo vệ bản quyền hay chống giả mạo thì việc tấn công đƣợc coi là
thành công nếu không chỉ phát hiện ra thuỷ ấn mà còn phá huỷ hay sửa đổi nó nhƣng
không làm giảm chất lƣợng của vật mang.
Có điểm giống nhau giữa mã hoá và giấu tin mật là ngƣời ta giả thiết thám tin
biết trƣớc phƣơng pháp mã hoá hay giấu tin mật. Nhƣ vậy, việc thám tin theo một
phƣơng pháp cụ thể (mã hoá hay giấu tin) phụ thuộc vào “khoá” chứ không phải là
phụ thuộc vào độ phức tạp của phƣơng pháp này (nguyên lý Kerkhoff).
Tƣơng tự nhƣ thám mã trong mã hoá, các kỹ thuật thám tin trong giấu tin mật
cũng đƣợc chia thành 5 nhóm:
- Biết vật mang tin (stego-object)
- Biết vật gốc (original object) và vật mang tin
- Biết có tin giấu trong vật mang tin
- Biết thuật toán giấu tin
- Biết thuật toán trích (tách) tin mật
Có nhiều phƣơng pháp để thám tin. Thám tin có thể phát hiện thủy ấn hay tin
mật bằng cách phân tích các trạng thái, ví dụ với ảnh có thể thám tin bằng cách phân
tích vùng nhiễu quá mức trên ảnh. Tin tặc kinh nghiệm có thể nhận thấy các vùng
nhiễu này bằng mắt thƣờng. Nếu biết đƣợc vật mang gốc thì việc thám tin còn đơn
giản hơn nữa, vì khi đó có thể so sánh ảnh mang tin với ảnh gốc để tách nhiễu. Nếu
thám tin biết đƣợc có tin giấu, ngƣời ta có thể tạo ra các cặp ảnh gốc và ảnh mang để
phân tích và xem xét liệu ảnh đang tìm hiểu có mang dấu ấn của chữ ký hay tin mật
hay không.
Việc phá tin mật có thể đơn giản hay phức tạp tuỳ thuộc vào phƣơng pháp giấu
tin mật. Ví dụ, đối với phƣơng pháp nhúng tin vào bit có trọng số thấp khi giấu tin
trong ảnh thì việc phá tin mật chỉ đơn thuần là thay đổi lại các bit này, nhƣ vậy ảnh
mang tin trở về trạng thái ban đầu.
Phá tin mật đối với các phƣơng pháp giấu tin mật mà vẫn giữ nguyên vật mang là
một việc khó. Vì mục tiêu của thuỷ ấn là phải đạt đƣợc độ bền vững sao cho nếu có ai
phá thuỷ ấn thì cũng làm hỏng ngay cả vật gốc.

Chƣơng trình S-Tools for Windows
Một chƣơng trình giấu ảnh tốt. Có thể giấu tin trong ảnh BMP, GIF, tệp âm thanh
WAV, các vùng chƣa dùng đến của đĩa mềm. Giao diện đồ họa kéo thả. Để giấu tin chỉ
cần kéo biểu tƣợng tệp tin cần giấu và thả lên ảnh.
Một yếu tố khác mà các hệ giấu tin nhắm tới và khai thác, đó là những điểm yếu
trong hệ thống thị giác con ngƣời. Một trong những phƣơng pháp giấu tin là tạo ra các
mặt nạ giác quan để đánh lừa mắt ngƣời. Vậy nên các nghiên cứu về phƣơng pháp giấu
tin trong ảnh có liên quan mật thiết với lĩnh vực xử lý ảnh, lý thuyết mật mã và các
kiến thức về hệ thống thị giác.


19

1.2. Tổng quan mã hoá thông tin
1.2.1. Sơ lƣợc về lịch sử mật mã học
Mật mã học nghiên cứu các kỹ thuật toán học nhằm cung cấp các dịch vụ bảo vệ
thông tin. Đây là ngành khoa học quan trọng, có nhiều ứng dụng trong đời sống xã hội.
Khoa học mật mã đã ra đời từ hàng nghìn năm. Tuy nhiên, trong suốt nhiều thế
kỷ, các kết quả của lĩnh vực này hầu nhƣ không đƣợc ứng dụng trong các lĩnh vực dân
sự thông thƣờng của đời sống xã hội mà chủ yếu đƣợc sử dụng trong lĩnh vực quân sự,
chính trị, ngoại giao...
Với sự phát triển ngày càng nhanh chóng của Internet và các ứng dụng giao dịch
điện tử trên mạng, nhu cầu bảo vệ thông tin trong các hệ thống và ứng dụng tin học
ngày càng đƣợc quan tâm và có ý nghĩa hết sức quan trọng. Các kết quả của khoa học
mật mã ngày càng đƣợc triển khai trong nhiều lĩnh vực khác nhau của đời sống xã hội,
trong đó phải kể đến rất nhiều những ứng dụng trong lĩnh vực dân sự, thƣơng
mại...Các ứng dụng mã hóa thông tin cá nhân, trao đổi thông tin kinh doanh, thực hiện
các giao dịch điện tử qua mạng... đã trở nên gần gũi và quen thuộc với mọi ngƣời.
Cùng với đó, các nghiên cứu và ứng dụng của mật mã học ngày càng trở nên đa
dạng hơn, mở ra nhiều hƣớng nghiên cứu chuyên sâu vào từng lĩnh vực ứng dụng cụ

thông tin “khó” thể đọc đƣợc theo cách thông thƣờng (gọi là Bản mã)
Đây là một trong những kỹ thuật để bảo mật thông tin.
- Giải mã là quá trình chuyển thông tin ngƣợc lại, từ Bản mã thành Bản rõ
- Thuật toán mã hóa hay giải mã là thủ tục tính toán để mã hóa hay giải mã
- Khóa mã hóa là một giá trị làm cho thuật toán mã hóa thực hiện theo cách riêng
biệt sinh ra bản rõ. Thông thƣờng khóa càng lớn (độ dài và tính ngẫu nhiên của khoá
càng lớn)thì bản mã càng an toàn. Phạm vi giá trị có thể có của khóa đƣợc gọi là
Không gian khóa
- Hệ mã hóa là tập các thuật toán, các khóa nhằm che giấu thông tin, cũng nhƣ
làm cho rõ nó.
Hệ mã hoá đƣợc định nghĩa là bộ năm (P, C, K, E, D), trong đó:
- P: là tập hữu hạn các bản rõ có thể.
- C: tập hữu hạn các bản mã có thể.
- K: tập hữu hạn các khoá có thể.
- E: tập các hàm lập mã.
- D: tập các hàm giải mã.
Với khoá lập mã ke  K, có hàm lập mã eke  E, eke: P →C.
Với khoá giải mã kd  K, có hàm giải mã dkd  D, dkd: C→P, sao cho
dkd(eke(x))=x, Với mọi x  P. Ở đây x đƣợc gọi là bản rõ, eke(x) đƣợc gọi là bản mã.
Quá trình mã hoá và giải mã:

Hình 1.4: Quá trình mã hóa và giải mã
Ngƣời gửi tin G muốn gửi bản tin T cho ngƣời nhận N. Để đảm báo bí mật, G
mã hoá bản tin bằng khoá lập mã ke, nhận đƣợc bản mã eke(T), sau đó gửi cho N. Tin
tặc có thể trộm bản mã eke(T) nhƣng cũng “khó” để hiểu đƣợc bản tin gốc T nếu không


21

có khoá giải mã kd.

22

dễ bị lộ. Khóa chung phải đƣợc gửi cho nhau trên kênh an toàn.
Mặt khác, khi ngƣời lập mã và ngƣời giải mã cùng biết chung một bí mật thì càng
khó giữ bí mật.
Hệ mã hoá khoá bí mật thƣờng đƣợc sử dụng trong môi trƣờng mà khoá chung có
thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ và để mã hoá
những bản tin lớn vì tốc độ mã hoá và giải mã nhanh hơn hệ mã hoá khoá công khai.
Hệ mã hoá khoá công khai
Nếu nhƣ vấn đề khó khăn đặt ra đối với các phƣơng pháp mã hóa khoá bí mật
chính là bài toán trao đổi mã khóa thì ngƣợc lại, các phƣơng pháp mã hóa khóa công
khai giúp cho việc trao đổi mã khóa trở nên dễ dàng hơn. Nội dung của khóa công khai
(public key) không cần phải giữ bí mật nhƣ đối với khóa bí mật trong các phƣơng pháp
mã hóa bí mật. Sử dụng khóa công khai, chúng ta có thể thiết lập một quy trình an toàn
để truy đổi khóa bí mật đƣợc sử dụng trong hệ thống mã hóa khoá bí mật.
Trong những năm gần đây, các phƣơng pháp mã hóa khóa công khai, đặc biệt là
phƣơng pháp RSA, đƣợc sử dụng ngày càng nhiều trong các ứng dụng mã hóa trên thế
giới và có thể xem nhƣ đây là phƣơng pháp chuẩn đƣợc sử dụng phổ biến nhất trên
Internet, ứng dụng trong việc bảo mật thông tin liên lạc cũng nhƣ trong lĩnh vực
thƣơng mại điện tử.
Có thể định nghĩa hệ mã hoá công khai nhƣ sau:
Hệ mã hoá công khai (Hệ mã hoá khoá phi đối xứng): là hệ mã hoá có khoá lập
mã và khoá giải mã khác nhau (ke khác kd). Hệ mã hoá này đƣợc gọi là Hệ mã hoá
khoá công khai vì:
- Khoá lập mã cho công khai, gọi là khoá công khai
- Khoá giải mã: giữ bí mật, còn gọi là khoá riêng hay khoá bí mật.
Một ngƣời bất kỳ có thể dùng khoá công khai để mã hoá bản tin nhƣng chỉ có
ngƣời nào có đúng khoá giải mã thì mới có khả năng đọc đƣợc bản rõ.



1.3.1. Định nghĩa
Trong viễn thông, mã Hamming đƣợc biết đến là một mã sửa lỗi tuyến tính, đƣợ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 và sửa các lỗi do một bit bị sai gây ra. Một mã có
khả năng tái dựng lại thông điệp gốc trong một môi trƣờng nhiễu lỗi đƣợc gọi là mã
"sửa lỗi" [3].
1.3.2. Vấn đề phát hiện sai và sửa sai
Nguyên lý phát hiện sai rất đơn giản nhƣ sau: kiểm tra xem tổ hợp nhận có phải
là từ mã hay không, nếu không thì tổ hợp nhận là sai. Việc kiểm tra này có thể đƣợc
thực hiện bằng cách so trùng tổ hợp nhận đƣợc với các từ mã.
Nhƣ vậy việc kiểm tra này sẽ tốn một số bƣớc bằng với số lƣợng các từ mã.
Tƣơng tự đối với việc sửa sai chúng ta có nguyên lý sau: Kiểm tra xem tổ hợp
nhận có khoảng cách Hamming gần với từ mã nào nhất, nếu gần với từ mã nào nhất thì
từ mã đó chính là từ mã đúng đã đƣợc phát đi. Nguyên lý này đƣợc gọi là nguyên lý
khoảng cách Hamming tối thiểu. Việc kiểm tra này tốn một số bƣớc bằng với số lƣợng
các từ mã.
Tuy nhiên đối với mã tuyến tính, dựa vào các tính chất của mã chúng ta sẽ có
cách phát hiện sai và sửa sai hiệu quả hơn. Các phần tiếp theo sẽ trình bày lần lƣợt về
vấn đề này, nhƣng trƣớc hết chúng ta sẽ trình bày một số kiến thức toán học cần thiết
cho việc chứng minh một số kết quả trong loại mã này.
Không gian bù trực giao.
Cho S là một không gian con k chiều của không gian n chiều V, Sd là tập tất cả
các vectơ trong V sao cho∀𝑢 ∈ 𝑆, 𝑣 ∈ 𝑆𝑑, thì u × v = 0 (phép nhân ở đây là phép nhân
vô hƣớng của hai vectơ) thì Sd là một không gian con của V và có số chiều là n – k. Sd
đƣợc gọi là không gian bù trực giao của S và ngƣợc lại.
Dựa trên kết quả này chúng ta suy ra rằng với ma trận G bất kỳ kích thƣớc k × n
với k hàng độc lập tuyến tính luôn tồn tại ma trận H kích thƣớc (n– k) × n với (n – k)
hàng độc lập tuyến tính sao cho G × HT = 0, trong đó HT là ma trận chuyển vị của ma
trận H. Hay nói cách khác các vectơ hàng của H đều trực giao với các vectơ hàng của
G.