Thạc Sĩ Lý thuyết đồng dư và ứng dụng trong mã sửa sai

LỜI NÓI ĐẦU
Có thể nói, số học, lý thuyết số là một trong những kiến thức toán học
lâu đời nhất. Từ trước tới nay, người ta thường coi lý thuyết số như một lĩnh
vực đẹp, nhưng thuần túy lý thuyết, của toán học. Với sự phát triển của khoa
học máy tính và công nghệ thông tin, lý thuyết số đã đóng góp những ứng
dụng thực tế bất ngờ và quan trọng, đặc biệt trong lĩnh vực mã hóa thông tin.
Nhiều khía cạnh khác nhau của mã hóa thông tin được các nhà toán học
và tin học quan tâm. Thường thường thông tin được mã hóa qua dãy các chữ
số trong hệ đếm cơ số 2, cơ số 10, hoặc cơ số p nào đó. Trong quá trình
truyền tin hoặc nhận tin, vì nhiều lý do, thông tin có thể bị sai lệch. Thí dụ,
một tin nhắn được mã hóa trong cơ số 2 khi truyền đi bị sai một lỗi (lỗi đơn)
thì điều này có nghĩa là chữ số 1 tại vị trí nào đó đã bị đổi thành chữ số 0 hoặc
ngược lại. Một trong những vấn đề cần giải quyết là phát hiện ra các lỗi sai và
sửa chúng.
Vì yêu cầu thực tiễn đó, lý thuyết mã sửa sai đã ra đời, phát triển và có
những ứng dụng thực tiễn quan trọng. Để xây dựng lý thuyết mã sửa sai, các
nhà toán học và khoa học máy tính đã sử dụng nhiều thành tựu của toán học
hiện đại (số học, toán rời rạc, đại số tuyến tính, .,) đặc biệt là số học trên tập
số nguyên, trong đó có lý thuyết đồng dư.
Luận văn này có mục đích tìm hiểu và trình bày những kiến thức cơ
bản nhất của lý thuyết mã sửa sai trên cơ sở lý thuyết đồng dư và lý thuyết
trường hữu hạn.
Luận văn gồm hai chương.
Chương 1 trình bày các kiến thức cơ bản nhất của lý thuyết đồng dư
và lý thuyết trường hữu hạn, chủ yếu dựa theo tài liệu [2], có tham khảo thêm
các tài liệu [4] và [6].
Chương 2 trình bày một số vấn đề cơ bản của mã sửa sai: khoảng cách
Hamming; phát hiện và sửa lỗi; các thuật toán giải mã; mã hoàn hảo; mã
tuyến tính và ma trận kiểm tra, xây dựng mã tuyến tính, .
Nội dung của Chương 2 trình bày chủ yếu dựa theo tài liệu [6], có tham
khảo thêm các tài liệu [1] và [7]. Ngoài ra, chúng tôi cũng quan tâm đến khía
cạnh thực tế của vấn đề: mã vạch, mã hàng hóa, mã sách tiêu chuẩn quốc
tế, Chúng tôi cũng cố gắng tìm hiểu, tuy chưa được đầy đủ, các mã hàng
hóa, mã văn hóa phẩm của Việt Nam và kiểm nghiệm các tiêu chuẩn giải mã
cho các ví dụ cụ thể của các mã này.
Luận văn được hoàn thành dưới sự hướng dẫn khoa học của PGS TS Tạ
Duy Phượng. Xin được tỏ lòng cám ơn chân thành nhất tới Thầy.

MỤC LỤC
LỜI NÓI ĐẦU 1
Chương 1: LÝ THUYẾT ĐỒNG Dư 3
§ 1. Quan hệ đồng dư . 3
1.1. Định nghĩa đồng dư . 3
1.2. Các tính chất của quan hệ đồng dư 4
§ 2. Thặng dư 7
2.1. Tập các lớp thặng dư . 7
2.2. Các tính chất của lớp thặng dư . 7
2.3. Tập các lớp thặng dư nguyên tố với môđun . 9
2.4. Vành các lớp thặng dư . 9
§ 3. Hệ thặng dư đầy đủ - Hệ thặng dư thu gọn 11
3.1. Hệ thặng dư đầy đủ 11
3.2. Hệ thặng dư thu gọn 13
3.3. Các định lí quan trọng . 16
§ 4. Phương trình đồng dư . 17
4.1. Các khái niệm chung . 17
4.2. Phương trình và hệ phương trình đồng dư bậc nhất một ẩn 23
4.2.1. Phương trình đồng dư bậc nhất một ẩn . 23
4.2.2. Hệ phương trình đồng dư bậc nhất một ẩn 26
4.3. Phương trình đồng dư bậc cao theo môđun nguyên tố 31
4.3.1. Nhận xét . 31
4.3.2. Phương trình bậc cao theo môđun nguyên tố 32
Chương 2: ỨNG DỤNG CỦA LÝ THUYẾT ĐỒNG Dư TRONG
MÃ SỬA SAI 36
§ 1. Khái niệm mã . 36
§ 2. Những ví dụ về mã . 39
2.1. Mã lặp . 39
2.2. Mã chẵn lẻ . 41
2.3. Mã vạch 44
§ 3. Khoảng cách Hamming 48
§ 4. Mã tuyến tính . 53
4.1. Mã nhị phân tuyến tính 53
4.2. Biểu diễn ma trận của các mã nhị phân 55
4.3. Thuật toán hội chứng giải mã cho các mã nhị phân . 65
4.4. Mã nhị phân Hamming 67
4.5. Các tính chất của mã nhị phân Hamming [n,k] 70
4.6. Các p-mã Hamming . 71
4.7. Các tính chất của p-mã Hamming [n,k] . 74
§ 5. Mã thập phân 77
5.1. Mã số sách tiêu chuẩn quốc tế (ISBN) . 77
5.2. Mã sửa lỗi đơn . 82
5.3. Mã sửa lỗi kép . 84
KẾT LUẬN . 88
TÀI LIỆU THAM KHẢO 89