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.

Tác giả xin cám ơn chân thành tới Trường Đại học Khoa học Thái

Nguyên, nơi tác giả đã nhận được một học vấn sau đại học căn bản.

Và cuối cùng, xin cám ơn gia đình, bạn bè, đồng nghiệp đã cảm thông, ủng hộ và giúp đỡ trong suốt thời gian tác giả học Cao học và viết luận văn.




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