![](images/graphics/blank.gif)
Bài giảng môn học Lý thuyết thông tin - Bùi Văn Thành
lượt xem 9
download
![](https://tailieu.vn/static/b2013az/templates/version1/default/images/down16x21.png)
Bài giảng môn học Lý thuyết thông tin do Bùi Văn Thành biên soạn hướng đến giới thiệu tới các bạn về mã vòng; các tính chất của mã vòng; ma trận sinh và ma trận kiểm tra của mã;... Hy vọng tài liệu là nguồn thông tin hữu ích cho quá trình học tập và nghiên cứu của các bạn.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng môn học Lý thuyết thông tin - Bùi Văn Thành
- BÀI GIẢNG MÔN HỌC LÝ THUYẾT THÔNG TIN
- Mã vòng 13.1 Giới thiệu 13.2 Các tính chất của mã vòng 13.3 Ma trận sinh và ma trận kiểm tra của mã 13.4 Mã BCH Trang 2
- Giới thiệu n Định nghĩa n Một mã tuyến tính C(n, k) được gọi là mã vòng nếu w = a0a1…an–2an–1 là một từ mã thì v = an–1a0a1…an–2 cũng là một từ mã. n Nghĩa là dịch vòng (sang trái hay phải) một từ mã thì kết quả cũng là một từ mã. Ở đây qui ước dịch phải. n Đa thức mã n Nếu w = a0a1…an–2an–1 là một từ mã thì w(x) = a0 + a1x + … + an–2xn 2 + an–1xn 1 là đa thức mã tương ứng với từ mã w. n Ví dụ n Bảng sau đây trình bày một mã vòng C(7, 4). Trang 3
- Ví dụ m w w(x) m w w(x) 0000 0000000 0 0001 0001101 x3 + x4 + x6 1000 1101000 1 + x + x3 1001 1100101 1 + x + x4 + x6 0100 0110100 x + x2 + x4 0101 0111001 x + x2 + x3 + x6 1100 1011100 1 + x2 + x3 + 1101 1010001 1 + x2 + x6 x4 0010 0011010 x2 + x3 + x5 0011 0010111 x2 + x4 + x5 + x6 1010 1110010 1 + x + x2 + 1011 1111111 1 + x + x2 + x3 x5 + x4 + x5 + x6 Trang 4 0110 0101110 x + x3 + x4 + 0111 0100011 x + x5 + x6
- Giới thiệu (tt) n w(i), w(i)(x) n w(i) là từ mã do dịch từ mã w i bit, và w(i)(x) là đa thức mã tương ứng của w(i). w(0) chính là w. i w(i) w(i)(x) 0 1101000 1 + x + x3 1 0110100 x + x2 + x4 = x * (1 + x + x3) = x * w(x) 2 0011010 x2 + x3 + x5 = x2 (1 + x + x3) = x2 * w(x) 3 0001101 x3 + x4 + x6 = x3 (1 + x + x3) = x3 * w(x) 4 1000110 Trang 5 1 + x4 + x5 = x4 + x5 + x7 mod 7
- Giới thiệu (tt) n w(i)(x) = xi * w(x) tuy nhiên nếu w(i)(x) có xp với p ≥ n thì xp được thay bằng xp mod n. n Mặc khác trên trường GF(2) chúng ta có xn + j = xj * (xn + 1) + xj hay xn + j mod (xn + 1) = xj n Bổ đề 13.1 w(i)(x) = [xi * w(x)] mod (xn + 1) Trang 6
- Các tính chất của mã vòng n Định lý 13.1 n Đa thức mã khác 0 có bậc nhỏ nhất là duy nhất. Hay nói cách khác không tồn tại hai đa thức mã khác 0, khác nhau và cùng có bậc nhỏ nhất. n Chứng minh n Giả sử hai đa thức mã khác nhau, cùng có bậc nhỏ nhất là r, 0
- Các tính chất của mã vòng (tt) n Kí hiệu đa thức mã có bậc nhỏ nhất là g(x) g(x) = g0 + g1x + … + gr–1xr 1 + xr n Định lý 13.2 n Hệ số tự do g0 của g(x) phải bằng 1. n Chứng minh n Giả sử g0 = 0. Suy ra g(x) = x * (g1 + … + gr–1xr 2 + xr 1) n Đặt f(x) = (g1 + … + gr–1xr 2 + xr 1), suy ra f(x) cũng là một đa thức mã. Vì f(x) tương ứng với từ mã được dịch trái 1 bit hay d ịch phải (n – 1) bit từ từ mã ứng với g(x). Trang 8 n
- Các tính chất của mã vòng (tt) n Định lý 13.3 n Một đa thức v(x) trên trường GF(2) có bậc ≤ n – 1 là đa thức mã nếu và chỉ nếu nó là một bội số của g(x). Tức là nó có thể viết v(x) = q(x) * g(x). n Chứng minh n Chiều thuận n Nếu v(x) = q(x) * g(x) và có bậc ≤ n – 1 thì v(x) là đa thức mã. p p v(x) q ( x) * g (x) qi xi * g (x) qi xi * g (x) i 0 i 0 với p là bậc của q(x) và p + r ≤ n – 1. Do xi * g(x) với 0 ≤ i ≤ p là đa thức mã, nên v(x) là đa th Trang 9 ức mã vì nó là một tổ hợp tuyến tính của
- Các tính chất của mã vòng (tt) n Chiều ngược n Nếu v(x) là đa thức mã thì chia v(x) cho g(x) v(x) = q(x) * g(x) + r(x) trong đó r(x) là đa thức dư và có bậc nhỏ hơn bậc của g(x). Đối với các đa thức trên trường GF(2) chúng ta có thể suy ra r(x) = q(x) * g(x) + v(x) Nên r(x) là một đa th ức mã. Theo định nghĩa của g(x) suy ra r(x) = 0. Trang 10
- Các tính chất của mã vòng (tt) n Định lý 13.4 n Đa thức sinh của một mã vòng C(n, k) có bậc r = n – k. n Chứng minh n Mỗi đa thức mã w(x) là một bội số của g(x) w(x) = q(x) * g(x) n Có 2k từ mã nên có 2k đa thức q(x). Suy ra bậc của q(x) là k – 1. Suy ra bậc của g(x) là n – k. n Từ định lý này đa thức sinh g(x) có thể được biểu diễn như sau g(x) = g0 + g1x + … + gn – kxn – k Trang 11 trong đó g0 =
- Các tính chất của mã vòng (tt) n Định lý 13.5 n Đa thức sinh của mã vòng C(n, k) là một ước số của xn + 1. n Chứng minh n Bổ đề 13.1 suy ra g(i)(x) = [xi * g(x)] mod (xn + 1) xi * g(x) = q(x) * (xn + 1) + g(i)(x) Chọn i = k q(x) = 1 tức xk * g(x) = Trang 12 (xn + 1) + g(i)(x)
- Các tính chất của mã vòng (tt) n Định lý 13.6 n Nếu g(x) là một đa thức có bậc (n – k) và là ước số của (xn + 1) thì g(x) sinh ra mã vòng C(n, k), hay nói cách khác g(x) là đa thức sinh của một mã vòng C(n, k) nào đó. n Chứng minh n Xét k đa thức g(x), x * g(x), …, xk – 1 * g(x). Các đa thức này đều có bậc ≤ n – 1. Gọi v(x) là một tổ hợp tuyến tính của k đa thức này với các hệ số ai GF(2). Trang 13 v(x) = a0g(x) + a1x * g(x) + … + ak – 1xk – 1 * g(x)
- Các tính chất của mã vòng (tt) n Có tất cả 2k tổ hợp tuyến tính v(x) khác nhau và tạo nên một không gian tuyến tính của các đa thức mã với g(x), x * g(x), …, xk – 1 * g(x) là các đa thức làm cơ sở. Chúng ta chứng minh rằng bộ mã tương ứng với không gian này là mã vòng. Gọi w(x) = b0 + b1x + … + bn – 1xn – 1 là một đa thức của không gian. Trang 14 Chúng ta
- Các tính chất của mã vòng (tt) n Theo Bổ đề 13.1 chúng ta có w(1)(x) = [x * w(x)] mod (xn + 1) Dựa vào biểu diễn của v(x) và w(1)(x) chúng ta suy ra x * w(x) = bn – 1(xn + 1) + w(1)(x) Do v(x) và (xn + 1) đều là bội của g(x) nên w(1)(x) cũng là bội của g(x). Suy ra w(1)(x) cũng là đa thức mã. Hoàn tất chứng minh. Trang 15
- Ma trận sinh n k 1 k 1 g0 g1 g 2 g n k 0 0 0 0 g 0 g1 g n k 1 g n k 0 0 Gk n 0 0 g0 gn k 2 gn k 1 gn k 0 0 0 0 g0 g1 g2 gn k n Ví dụ n Tìm một mã vòng C(7, 4). n Theo các tính ch Trang 16 ất của mã vòng suy ra đa thức sinh của mã có
- Ví dụ x7 + 1 = (1 + x)(1 + x + x3)(1 + x2 + x3) n Chọn chẳng hạn g(x) = (1 + x + x3) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 G4 7 0 0 1 1 0 1 0 0 0 0 1 1 0 1 Trang 17
- Mã vòng dạng hệ thống n Từ dạng hệ thống loại 1 chúng ta có thể dịch vòng k bit để biến đổi sang dạng hệ thống loại 2 và ngược lại. 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 G4 7 Ght ( 4 7) 0 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 n Mã hóa thành từ mã hệ thống n u(x) là thông báo, w(x) là từ mã hệ thống loại 2 tương ứng. xn–k * u(x) = q(x) * g(x) + a(x) Trang 18
- Ví dụ n Cho mã vòng C(7, 4) có ma trận sinh là g(x) = (1 + x + x3). Hãy mã hoá thông báo u = 1010 thành từ mã hệ thống dạng 2. u(x) = 1 + x2. Nhân u(x) với xn–k = x3 rồi chia cho g(x) chúng ta được. x3 * (1 + x2) = x3 + x5 = x2 * (1 + x + x3) + x2 n Từ đây suy ra w(x) = x2 + x3 + x5 w = 0011010 Trang 19 là từ mã hệ
- Ma trận kiểm tra của mã vòng n Có một cách khác để tìm ma trận kiểm tra của mã vòng xn + 1 = g(x) * h(x) n h(x) được gọi là đa thức đối ngẫu của g(x). h(x) có bậc k h(x) = h0 + k 1 n k 1 h1x + … + hkxk n hk hk 1 ột ma tr Ma trận sau là m hk 2 ận kiểhm tra c 0 0 ủa mã vòng 0 0 0 hk hk 1 h1 h0 0 0 H (n k) n 0 0 hk h2 h1 h0 0 0 0 0 hk hk 1 hk 2 h0 Trang 20
![](images/graphics/blank.gif)
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng môn học LÝ THUYẾT MẠCH
182 p |
945 |
308
-
BÀI GIẢNG MÔN HỌC LÝ THUYẾT TÀU (DÀNH CHO SINH VIÊN NGÀNH KHÔNG CHUYÊN)
68 p |
853 |
303
-
Đề cương môn học sức bền vật liệu
9 p |
358 |
65
-
Bài giảng môn học Lý thuyết điều khiển tự động - Chương 3: Khảo sát tính ổn định của hệ thống
97 p |
419 |
58
-
Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 3
0 p |
203 |
56
-
Bài giảng môn học Lý thuyết điều khiển tự động - Chương 5: Thiết kế hệ thống điều khiển liên tục
80 p |
221 |
54
-
Bài giảng môn học Lý thuyết điều khiển tự động - Chương 8: Hệ thống điều khiển phi tuyến
77 p |
262 |
50
-
Bài giảng môn học Lý thuyết điều khiển tự động - Chương 4: Đánh giá chất lượng hệ thống điều khiển
35 p |
204 |
41
-
Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 8
0 p |
147 |
33
-
Bài giảng môn học Lý thuyết điều khiển tự động - Chương 7: Phân tích và thiết kế hệ thống điều khiển rời rạc
87 p |
196 |
29
-
Bài giảng môn học Lý thuyết điều khiển tự động - Chương 6: Mô tả toán học hệ thống điều khiển rời rạc
51 p |
155 |
26
-
Đề cương lý thuyết điều khiển tự động hiện đại
6 p |
252 |
20
-
Bài giảng môn Động hóa học - Phạm Hữu Hùng (ĐH Sư Phạm Đà Nẵng)
57 p |
110 |
20
-
Bài giảng môn học Lý thuyết điều khiển tự động - Chương 2: Mô hình toán học hệ thống điều khiển liên tục
98 p |
177 |
19
-
Bài giảng môn Cơ học đất - Chương 4: Biến dạng và độ lún của nền đất
72 p |
11 |
3
-
Bài giảng Cơ học môi trường liên tục: Chương 1 - TS. Phạm Văn Đạt
27 p |
4 |
2
-
Bài giảng Cơ học đá: Giới thiệu môn học - GV. Kiều Lê Thủy Chung
7 p |
46 |
1
![](images/icons/closefanbox.gif)
![](images/icons/closefanbox.gif)
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn
![](https://tailieu.vn/static/b2013az/templates/version1/default/js/fancybox2/source/ajax_loader.gif)