tailieunhanh - 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 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ÀI GIẢNG MÔN HỌC LÝ THUYẾT THÔNG TIN 1 Trang 2 Mã vòng Giới thiệu 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ã Mã BCH 2 Trang 3 Giới thiệu Định nghĩa 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ã. 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. Đa thức mã 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. Ví dụ Bảng sau đây trình bày một mã vòng C(7, 4). 3 Trang 4 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 + x4 1101 1010001 1 + x2 + x6 0010 0011010 x2 + x3 + x5 0011 0010111 x2 + x4 + x5 + x6 1010 1110010 1 + x + x2 + x5 1011 1111111 1 + x + x2 + x3 + x4 + x5 + x6 0110 0101110 x + x3 + x4 + . | BÀI GIẢNG MÔN HỌC LÝ THUYẾT THÔNG TIN 1 Trang 2 Mã vòng Giới thiệu 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ã Mã BCH 2 Trang 3 Giới thiệu Định nghĩa 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ã. 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. Đa thức mã 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. Ví dụ Bảng sau đây trình bày một mã vòng C(7, 4). 3 Trang 4 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 + x4 1101 1010001 1 + x2 + x6 0010 0011010 x2 + x3 + x5 0011 0010111 x2 + x4 + x5 + x6 1010 1110010 1 + x + x2 + x5 1011 1111111 1 + x + x2 + x3 + x4 + x5 + x6 0110 0101110 x + x3 + x4 + x5 0111 0100011 x + x5 + x6 1110 1000110 1 + x4 + x5 1111 1001011 1 + x3 + x5 + x6 4 Trang 5 Giới thiệu (tt) w(i), w(i)(x) 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 1 + x4 + x5 = x4 + x5 + x7 mod 7 5 0100011 x + x5 + x6 = x5 + x6 + x8 mod 7 6 1010001 1 + x2 + x6 = x6 + x7 mod 7 + x9 mod 7 5 Trang 6 Giới thiệu (tt) 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. 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 Bổ đề w(i)(x) = [xi * w(x)] mod (xn + 1) 6 Trang 7 Các tính chất của mã vòng Định lý Đ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. Chứng