Bài giảng Lý thuyết thông tin - Chương 6: Nhắc lại một số kiến thức đại số liên quan

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 6: Nhắc lại một số kiến thức đại số liên quan

1. Chương 6. Nhắc lại một số kiến thức đại số liên quan ntnhut@hcmus.edu.vn 1
2. Nhóm giao hoán Đ : Tập G cùng với một phép toán cộng trên G, ký hiệu (G,+) là một nhóm giao hoán nếu: i. (Kết hợp) ∀x, y, z ∈ G: x + (y + z) = (x + y) + z. ii. (Giao hoán) ∀x, y ∈ G: x + y = y + x. iii. (Có ptử trung hoà) ∃0 ∈ G: x + 0 = x, ∀x ∈ G. iv. (Có ptử đối) ∀x ∈ G, ∃(x) ∈ G: x + (x) = 0. Đối với (G,*), ta viết xy thay cho x*y, ptử đơn vị là 1, ptử nghịch đảo là x 1. n VD : ( Z,+), (R,+), ( Mn(R),+), ( R\{0},*), ({0,1} ,+), (Zp,⊕). ntnhut@hcmus.edu.vn 2
3. VD1 : Nhóm ({0,1} n,+) • {0,1} n là tập tất cả các chuỗi nhị phân độ dài n. • Phép + là phép cộng bit không nhớ. • Phần tử đối –x của x ∈ {0,1} n cũng là x. • Phần tử trung hoà là 00 0. VD: {0,1} 2 = {00, 01, 10, 11}.
   01 + 11 = 10.
   11 + 11 = 00. ntnhut@hcmus.edu.vn 3
4. VD2 : Nhóm ( Zp, ⊕) • Zp = {0, 1, 2, , p – 1}. • Phép cộng: với x, y ∈ Zp, – Nếu x + y < p thì x ⊕ y = x + y. – Nếu x + y ≥ p thì x ⊕ y = x + y – p. • Phần tử trung hoà là 0. • Phần tử đối của x là p – x. • Nếu không có gì nhập nhằng ta viết + thay cho ⊕. ntnhut@hcmus.edu.vn 4
5. Phép trừ và phép chia x – y := x + (– y). x/y := xy 1. ntnhut@hcmus.edu.vn 5
6. Nhóm con Đ : Cho G là nhóm giao hoán, và K ⊆ G. 1. K được gọi là nhóm con (subgroup) của G, ký hiệu K ≤ G, nếu nó đóng với phép toán +, tức là: – ∀x, y ∈ K: x + y ∈ K. – 0 ∈ K. – Nếu x ∈ K thì –x ∈ K. 2. Lớp ghép (coset) của x ∈ G modulo K là tập x + K = {x + k | k ∈ K}. ntnhut@hcmus.edu.vn 6
7. Ví dụ • Tập tất cả các số nguyên chẵn Zeven là một tập con của Z. • Lớp ghép của 1 là tập tất cả các số lẻ: • 1 + Zeven = {1 + k | k chẵn} = Zodd . • Zodd = 1 + Zeven = 3 + Zeven = 1 + Zeven = • Lớp ghép của 0 cũng chính là Zeven : • 0 + Zeven = Zeven = 2 + Zeven = 4 + Zeven = • Như vậy: Z = Zodd ∪ Zeven . ntnhut@hcmus.edu.vn 7
8. Bài tập 1. CMR mọi nhóm con của ( Z,+) đều có dạng pZ với p = 0, 1, 2, 2. Tìm tất cả các nhóm con của ( Z12 ,+). 3. CMR trong mọi nhóm giao hoán G: a) Có duy nhất một pt trung hoà/pt đơn vị. b) Mỗi x ∈ G, có duy nhất một phần tử đối/nghịch đảo. ntnhut@hcmus.edu.vn 8
9. Mã tuyến tính nhị phân Mệnh đề : Mọi mã tuyến tính nhị phân K độ dài n đều là một nhóm con của nhóm {0, 1} n. Chứng minh : Thực vậy, nó thoả 3 tính chất của nhóm con: – Đóng với phép cộng – Có phần tử trung hoà – Có phần tử đối. ntnhut@hcmus.edu.vn 9
10. Tính chất của lớp ghép Mệnh đề : các lớp ghép modulo K trong một nhóm G thoả các tính chất sau: – Mỗi phần tử của G đều nằm trong một lớp nào đó. – Hai lớp phân biệt thì không có phần tử chung. – Hai phần tử x, y cùng nằm trong một lớp khi và chỉ khi hiệu của chúng x – y thuộc nhóm con K. – Nếu |K| = r thì các lớp có cùng r phần tử. Chứng minh : (bài tập) ntnhut@hcmus.edu.vn 10
11. Nhận xét • Một nhóm G có thể phân hoạch thành các lớp rời nhau cùng kích thước. • Nếu G là một nhóm hữu hạn n phần tử, K là một nhóm con r phần tử của G thì số các lớp là n/r. • Mỗi lớp ghép ta chọn một phần tử đại diện, gọi là coset leader . • Tập tất cả các coset leader ký hiệu là G/K. ntnhut@hcmus.edu.vn 11
12. Lớp Z/p Z • Với mỗi số tự nhiên p, đặt p Z = {pn | n ∈ Z}. • pZ là một nhóm con của ( Z,+) • Có đúng p lớp ghép của ( Z,+) modulo p Z: 0 + p Z, 1 + p Z, , p – 1 + p Z. • Ta chọn 0, 1, , p – 1 làm các coset leader cho các lớp ghép này • Vậy Z/p Z = Zp. ntnhut@hcmus.edu.vn 12
13. Đồng dư Đ : hai số nguyên x, y được gọi là đồng dư modulo p , ký hiệu x ≡ y (mod p) , nếu chúng cùng nằm trong một lớp ghép modulo p Z. Nói cách khác x – y chia hết cho p. VD : 1 ≡ 1 (mod 2). • 14 ≡ 2 (mod 12). ntnhut@hcmus.edu.vn 13
14. Dãy chuNn trong mã nhị phân tuyến tính • K là nhóm con của {0, 1} n. •  K phân hoạch được thành các coset • Với mỗi coset, ta chọn coset leader c có w(c) nhỏ nhất. Đ : standard array của K là bảng tất cả các từ mã độ dài n được sắp như sau: Coset leaders K Leader 1 = codeword 1 = Codeword 2 Codeword m 00 0 Leader 2 Codeword 2 + leader 2 Codeword m + leader 2 Leader i Codeword 2 + leader i Codeword m + leader i ntnhut@hcmus.edu.vn 14
15. Chọn coset leader?  Xem giáo trình VD : Mã K 5 ntnhut@hcmus.edu.vn 15
16. Giải mã bằng các dãy chuNn Giải mã hận được ntnhut@hcmus.edu.vn 16
17. Bài tập 1. Tìm một dãy chuNn cho a) mã lặp K N . b) Mã Hamming (7,4). 2. Gọi K là mã tuyến tính tạo bởi các tổng của các từ 101011, 011101, 011010. a) Tìm ma trận parity check H của K. b) Tìm một dãy chuNn của K. Giải mã chuỗi nhận được 111011. ntnhut@hcmus.edu.vn 17
18. Trường Đ : Tập F với hai phép toán + và * được gọi là trường (field) nếu thoả các tính chất sau: 1) (F,+) là một nhóm giao hoán với pt trung hoà 0. 2) (F {0},*) là một nhóm giao hoán với pt đơn vị 1 . 3) x(y + z) = xy + xz với mọi x, y, z ∈ F. VD : R, Q, C, Z2, Zp (với p nguyên tố). Z không là một trường (mà là một vành ). ntnhut@hcmus.edu.vn 18
19. Lưu ý 1. xy = 0 ⇒ x = 0 hoặc y = 0. 2. x0 = 0 với mọi x. 3. với a ≠ 0: ax = ay ⇒ x = y. Bài tập : 1. N hắc lại ĐN của vành (ring) . 2. CM: (x 1)1 = x với mọi x khác 0. ntnhut@hcmus.edu.vn 19
20. Trường Zp Đ : ( Zp,+) đã được ĐN . ( Zp,*) được ĐN như sau: x*y = số dư của phép chia xy cho p. • ếu p là số nguyên tố thì Zp là một trường. VD ntnhut@hcmus.edu.vn 20
21. Bài tập 1 1. Viết bảng phép toán cho Z 5. Tìm x cho các x khác 0 thuộc Z 5. 2. CMR tập sau cùng với hai phép toán lập thành một trường ntnhut@hcmus.edu.vn 21
22. Không gian vector Đ : Cho F là một trường, các phần tử ∈ F gọi là các scalar (vô hướng) . Tập L gồm các phần tử gọi là vector , cùng với phép cộng vector và phép nhân với vô hướng được gọi là một không gian vector (vector space) nếu: – (L,+) là một nhóm giao hoán. – st(a) = s(ta) với mọi a ∈ L, s, t ∈ F. – t(a + b) = ta + tb và (s + t)a = sa + ta với mọi s, t ∈ F, a, b ∈ L. – 1a = a với mọi a. n VD : Z2 = {từ nhị phân độ dài n} là một KGVT ntnhut@hcmus.edu.vn 22
23. Lưu ý 1. 0a = 0 với mọi a ∈ L. 2. (1)a = a với mọi a ∈ L. 3. t0 = 0 với mọi t ∈ F. Bài tập: n n 1. Có bao nhiêu vector trong KGVT Z2 , Z3 2. CM tập các ma trận với phép toán cộng và nhân vô hướng lập thành một KGVT. ntnhut@hcmus.edu.vn 23
24. KGVT con Đ : Tập K ⊂ L được gọi là KGVT con (subspace) nếu nó đóng với phép cộng và nhân: – a + b ∈ K với mọi a, b ∈ K. – ta ∈ K với mọi a ∈ K, t ∈ F. VD : Một mã nhị phân tuyến tính độ dài n là một n KGVT con của Z2 ntnhut@hcmus.edu.vn 24
25. Tổ hợp tuyến tính Đ: Tổ hợp tuyến tính (linear combination) của các vector a 1, a 2, , a m ∈ L là tổng t1a1 + t 2a2 + + t mam với t 1, , t m ∈ F. • Span(a 1, , a m) := {t1a1 + t 2a2 + + t mam | t 1, , t m ∈ F} là KGVT sinh bởi {a 1, , a m} ĐL : Span(a 1, , a m) là KGVT con nhỏ nhất chứa {a1, , a m}. ntnhut@hcmus.edu.vn 25
26. Ví dụ 1. Vector (1,0,1) trong R3 sinh đường thẳng K = t(1,0,1) gồm các vector (t,0,t) với t ∈ R. 2. Hai vector (1,0, 1) và (0,1,1) sinh mặt phẳng P = t(1,0,1) + s(0,1,1). 3. Mã kiểm chẵn lẻ độ dài 4 có thể sinh bởi ba vector 1100, 1010, 1001! ntnhut@hcmus.edu.vn 26
27. Độc lập tuyến tính Đ : các vector a 1, , a m được gọi là độc lập tuyến tính (linearly independent) nếu không vector nào là tổ hợp tuyến tính của các vector còn lại. • Một tập các vector độc lập tuyến tính sinh ra được chính L được gọi là cơ sở (basis) của KGVT L. Số vector trong một cơ sở của L được gọi là số chiều (dimension) của L. ntnhut@hcmus.edu.vn 27
28. Ví dụ 1. R2 là một KGVT 2 chiều. Một cơ sở là {(0,1),(1,0)}. 2. {0,1} n = {từ nhị phân độ dài n} có n chiều. Một cơ sở là tập tất cả các từ có w(e) = 1. 3. Mã kiểm chẵn lẻ độ dài 4 có thể sinh bởi ba vector 1100, 1010, 1001 độc lập tuyến tính.  số chiều = 3. ntnhut@hcmus.edu.vn 28
29. Tổ hợp tuyến tính của cơ sở ĐL : Cho {e 1, e 2, , e m} là một cơ sở của L. Với mỗi vector a ∈ L, tồn tại duy nhất các vô hướng t 1, , t m sao cho a = t 1e1 + t 2e2 + + t mem. VD : Một từ mã kiểm chẵn lẻ độ dài 4 bất kỳ, chẳn hạn 0110 có thể viết dưới tổ hợp tuyến tính của tập sinh {1100, 1010, 1001} là 0110 = 1100 + 1010. ntnhut@hcmus.edu.vn 29
30. Tính chất của cơ sở MĐ : trong mọi KGVT kchiều L: 1) Mọi cơ sở của L có k vector 2) Mọi bộ k vector độc lập tuyến tính tạo thành một cơ sở. 3) k là số phần tử lớn nhất của một tập độc lập tuyến tính các vector trong L. 4) Các KGVT con của L có số chiều nhỏ hơn k. ntnhut@hcmus.edu.vn 30
31. Tích vô hướng Đ : Tích vô hướng (inner product) của hai vector a = (a 1, a 2, , a n) và b = (b 1, b 2, , b n) là: a·b = a 1b1 + a 2b2 + + a nbn. • Hai vector được gọi là trực giao (orthogonal) nếu tích vô hướng của chúng = 0. VD : Cho L là một ntnhut@hcmus.edu.vn 31
32. Bù trực giao Đ: Cho L là một KGVT con của F n. Phần bù trực giao của L, ký hiệu L ⊥ là tập các vector của F n trực giao với tất cả các vector trong L. L⊥ = {a ∈ Fn | a ·b = 0 với mọi b ∈ L}. VD : Cho L là một đường thẳng trong R2. Khi đó, L⊥ là đường thẳng vuông góc với L và đi qua gốc toạ độ ntnhut@hcmus.edu.vn 32
33. Tính chất của phần bù trực giao 1. L⊥ cũng là một KGVT con. 2. N ếu dim(L) = k thì dim(L ⊥)= n – k. 3. (L ⊥)⊥ = L. ntnhut@hcmus.edu.vn 33
34. Tóm tắt • ĐN nhóm, nhóm con, lớp ghép, trường. • N hóm Z p, Z/pZ. • Standard array • Coset leader • Trường Z p. • ĐLập TT, Tổ Hợp TT, Cơ Sở • Tích vô hướng • Bù trực giao ntnhut@hcmus.edu.vn 34
35. Homework • Đọc và làm Chương 6+7 [1] • Đọc trước chương 8 [1] ntnhut@hcmus.edu.vn 35