Giáo trình Lý thuyết thông tin

từ mã gần v, nhưng do tồn tại cùng lúc nhiều từ mã gần nhất với v dẫn đến không giải mã được, ngược lại hoàn toàn tương tự. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 62 Giáo trình: Lý thuyết thông tin. Minh họa: a. d(wi, wj)= 2e+1= 7, e=3 Nếu v∈Bi thì v được giải mã về wi Nếu v∈Bj thì v được giải mã về wj * wj v wi * b. d(wi, wj) = 2e = 8 (e = 4, e - 1=3) nếu v∉Bi , v∉Bj => các điểm cách tâm khoảng cách 3 thì luôn được giải mã, còn các điểm cách tâm 4 thì chỉ phát hiện lỗi chứ không thể giải mã được. c. Mã 3 chiều (x, y, z) bắt đầu từ gốc 000. Cứ một tín hiệu thay đổi thì mã bị đẩy đi theo 1 cạnh, chẳng hạn: 000 cách 010, 001 bởi 1 cạnh, 011 cách 010, 111 và 001 bởi 1 cạnh. Như vậy, nếu ta chọn w1=010, w2=001, w3=111 thì khoảng cách giữa chúng là 2 d(w1, w2)=d(w1, w3)=d(w2, w3)=2 vậy nếu có lỗi phát sinh thì chỉ phát hiện chứ không sửa được. y 110 101 100 w3=111 w2=001 w1=010 000 x z Cận Hamming. Đặt vấn đề: trong tổng số 2n dãy nhị nhân dài n bit có thể chọn ra bao nhiêu dãy để tạo thành một bộ mã có thể tự điều chỉnh được e bit lỗi. Định lý cận Hamming cho chúng ta xác định số từ mã có độ dài n bit với giả thiết: có khả năng tự sửa được e bit lỗi (điều kiện cần tự sửa lỗi). Định lý: Nếu bộ mã W có s từ mã có độ dài n bit có thể tự sửa được e bit lỗi thì ∑ = ≤ e i i n n C s 1 2 Ghi chú: Cni = n!/(i!*(n-i)!) Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 63 Giáo trình: Lý thuyết thông tin. Chứng minh: Xét từ mã nhị phân wi có độ dài n bit và có khả năng tự sửa được e bit lỗi. Số dãy vj sai khác với wi từ 0 đến e bit là : ∑ = =++++ e i i n e nnnn CCCCC 0 210 ... Tương ứng với s từ mã, tổng số dãy vj có thể tự sửa lỗi là : n e i i nCs 2. 0 ≤∑ = (2n là tổng số dãy nhị phân dài n bits). => ∑ = ≤ e i i n n C s 1 2 Phân các dạng lỗi Giả sử ta truyền từ mã n bit wi ∈ W ( 1 ≤ i ≤ s) và nhận được dãy n bit vj ( 1≤ j ≤ 2n). Các loại lỗi có thể phát hiện sau: Lỗi có thể tự điều chỉnh: Trong trường hợp này tồn tại duy nhất từ mã w*i sao cho d(vj, w*i)= Min d(vj, wk) với ∀wk ∈ W. => vj được giải mã về w*i Lỗi chỉ phát hiện không điều chỉnh được: Trong trường hợp này tồn tại từ mã w*i và w**i sao cho d(vj, w*i)= d(vj, w**i)=Min d(vj, wk) với ∀wk ∈ W => vj không thể giải mã chính xác. Lỗi không phát hiện được. Trong trường hợp ta giải mã ra w*i nhưng khác với wi đã truyền. Bài tập 1. Cho n=7 và e=2, hãy áp dụng định lý cận Hamming cho biêt số từ mã tối đa của bộ mã W. 2. Cho n=7 và e=2, hãy áp dụng định lý cận Hamming cho biêt số từ mã tối đa của bộ mã W. 3. Hãy cho một ví dụ cụ thể minh họa các trường hợp phân loại lỗi. BÀI 5.3: Mà KIỂM TRA CHẴN LẺ Mục tiêu: Sau khi hoàn tất bài học này bạn có thể: - Hiểu bộ mã kiểm tra chẵn lẻ, - Hiểu phương pháp kiểm tra chẵn lẻ, Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 64 Giáo trình: Lý thuyết thông tin. - Biết tính chất cơ bản của phương pháp kiểm tra chẵn lẻ, - Hiểu và vận dụng tốt phương pháp sinh mã kiểm tra chẵn lẻ, - Hiểu và vận dụng tốt Định lý quan hệ giữa độ dài mã n, số bit kiểm tra m và số lỗi tự sửa e, - Vận dụng cho các bài học tiếp theo. Bộ mã kiểm tra chẵn lẻ Bộ mã kiểm tra chẵn lẻ là bộ mã gồm s từ mã, trong đó mỗi từ mã có dạng sau: w’=r1r2r3rm rm+1rm+2rm+k (với n = m+k). m bit kiểm tra k bit thông tin Ghi chú: trong một số trường hợp sinh mã theo phương pháp kiểm tra chẵn lẻ, thứ tự các bit kiểm tra và các bit thông tin có thể xen kẻ nhau (theo một thứ tự nào đó, chẳng hạn như mã Hamming,) hay cũng có thể theo một thứ tự khác (theo quy ước khác). Ở đây, ta chọn thứ tự các bit kiểm tra chẵn lẻ và các bit thông tin như trên để dễ tính toán nhưng vẫn mất tính tổng quát hóa. Trong đó: w’ viết theo dong là chuyển vị của w (w được viết theo cột) + ri: là bit thứ i của từ mã ( 1≤ i ≤ n). + n: độ dài của từ mã hay số bit của từ mã chẵn lẻ. + m: số bit kiểm tra. + k = n-m: số bit thông tin ⇒ s=2k (vì với k bit thông tin thì ta chỉ có thể biểu diên tối đa 2k trạng thái thông tin k bit). + Đoạn kiểm tra: gồm m bit dùng để kiểm tra mã sai. + Đoạn thông tin: gồm k bit thông tin. Mỗi đoạn mã thông tin có duy nhất một đoạn mã kiểm tra và được xác định bởi hệ phương trình tuyến tính nhị phân sau: 0 ... 0 0 ... ............ ... ... 2211 2222121 1212111 = = = ⎪⎪⎩ ⎪⎪⎨ ⎧ +++ +++ +++ nnnnn nn nn rarara rarara rarara Gọi A=||aij|| =Am x n , aij ∈{0,1}, i= m,1 , j= n,1 . Ma trận A được gọi là ma trận kiểm tra chẵn lẻ có hạng là m (hay Rank(A) = m). Các phép toán trong Modulo 2 (+,-): 0 + 1 = 1 + 0 = 1; 0 – 1 = 1 – 0 = 1; 1 + 1 = 1 – 1 = 0; Phương pháp kiểm tra chẵn lẻ Gọi w’=r1r2rn là từ mã truyền (hay dãy n bit truyền) và v’=r1r2rn là dãy n bit nhận được. Qui ước: v’, w’ (lần lượt là chuyển vị của v và w) được viết theo dòng. Còn v, w được viết theo cột. Nếu A.v = 0 thì v = w, ta gọi v là chẵn (trường hợp nhận đúng) Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 65 Giáo trình: Lý thuyết thông tin. Nếu A.v ≠ 0 thì v ≠ w, ta gọi v là lẻ (trường hợp nhận sai). Ta gọi z = v-w là bộ lỗi giữa v và w. Nghĩa là tại các vị trí z = {0} thì bit nhận được tương ứng là bit đúng và tại các vị trí z = {1} thì bit nhận được tương ứng là bit sai (hay bit lỗi). Ta gọi C = A.v là bộ sửa lỗi (hay bộ điều chỉnh lỗi). Ta có C = A.z = A.(v-w) = A.v-A.w = A.v ⇒ C = A.v = A.z Tính chất của bộ sửa lỗi: dãy n bit nhận được v và bộ lỗi tương ứng có cùng bộ điều chỉnh. Phương pháp sinh mã kiểm tra chẵn lẻ Giả sử: cho trước ma trận kiểm tra chẵn lẻ A với Rank(A) = m. Tìm bộ mã chẵn lẻ W={w1, w2, w3,,ws} Bước 0: Xác định các giá trị n, m, k, s Độ dài của từ mã n= số cột của ma trận A. Số bit kiểm tra m= số dòng của ma trận A. Số bit thông tin: k = n-m. Số từ mã s=2k của bộ mã. Bước i: Tìm các từ mã thứ i (1≤ i ≤ s): Gọi kpi là triển khai nhị phân k bit của số i Từ mã cần tìm là: w’i=r1r2..rmkpi Giải hệ phương trình A.wi=0 để tìm m bit kiểm tra ứng với k bit thông tin (kpi) đã biết => từ mã wi Ví dụ sinh mã kiểm tra chẵn lẻ Xây dựng bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: A= Rank(A) = 3 ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 101101 101110 011001 Bước 0: n=6 (= số dòng của ma trận A) m=3 (= số cột của ma trận A) Số bit thông tin k = n – m = 3 => Số từ mã s=2k=8 từ mã. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 66 Giáo trình: Lý thuyết thông tin. Bước i: Tìm từ mã thứ i (1≤ i ≤ s): w’1=r1r2r3000 (000 là triển khai nhị phân k=3 bits của số i=0) w’1=r1r2r3001 (001 là triển khai nhị phân k=3 bits của số i=1) w’2=r1r2r3010 (010 là triển khai nhị phân k=3 bits của số i=2) w’3=r1r2r3011 (011 là triển khai nhị phân k=3 bits của số i=3) w’4=r1r2r3100 (100 là triển khai nhị phân k=3 bits của số i=4) w’5=r1r2r3101 (101 là triển khai nhị phân k=3 bits của số i=5) w’6=r1r2r3110 (110 là triển khai nhị phân k=3 bits của số i=6) w’7=r1r2r3111 (111 là triển khai nhị phân k=3 bits của số i=7) Giải hệ phương trình A.w1=0 = => => w’ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 101101 101110 011001 ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ 1 0 0 3 2 1 r r r ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 0 0 0 ⎪⎩ ⎪⎨ ⎧ = = = => ⎪⎩ ⎪⎨ ⎧ =+ =+ = 1 0 0 1 1 0 3 2 1 31 32 1 r r r rr rr r 1=001001 Giải hệ phương trình A.w2=0 ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 101101 101110 011001 ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ 0 1 0 3 2 1 r r r = => =>w’ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 0 0 0 ⎪⎩ ⎪⎨ ⎧ = = = => ⎪⎩ ⎪⎨ ⎧ =+ =+ = 1 1 1 0 0 1 3 2 1 31 32 1 r r r rr rr r 2=111010 Giải tương tự cho các trường hợp còn lại ta có: w’0=000000, w’3=110011, w’4=110100, w’5=111101, w’6=001110, w’7=000111. ⇒ W={000000, 001001, 111010, 110011, 110100, 111101, 001110, 000111} Định lý quan hệ giữa độ dài mã n, số bit kiểm tra m và số lỗi tự sửa e Điều kiện cần (Cận Hamming): Điều kiện cần để bộ mã chẵn lẻ có độ dài n bit có thể tự sửa được e bit lỗi với k bit thông tin và m bit kiểm tra là: ∑ = ≥ e i i n m C 0 2 Điều kiện đủ ( ĐK Vasharmov-Gilbert-Sacks): Điều kiện đủ để bộ mã kiểm tra chẵn lẻ có độ dài n bit với m bit kiểm tra chẵn lẻ có thể tự sửa được e bit lỗi là: ∑− = −> 12 0 12 e i i n m C Ghi chú: Cni = n!/(i!*(n-i)!) Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 67 Giáo trình: Lý thuyết thông tin. Ví dụ tìm m nhỏ nhất từ n và e Giả sử biết trước n=7 và e=1. Tìm số bit kiểm tra tối thiểu cần thiết của bộ mã chẵn lẻ. Theo định lý điều kiện cần (Cận Hamming): Ta có: ∑ = ≥ e i i n m C 0 2 ⇔ (*) ∑= = ≥ 1 0 72 e i im C m = 1 ⇒ (*) sai. m = 2 ⇒ (*) sai. m ≥ 3 ⇒ (*) đúng. Vậy số bit kiểm tra tối thiểu cần thiết là m = 3. Ví dụ tìm e lớn nhất từ m và n Giả sử cho trước m=3, k=2. Tìm số bit lỗi lớn nhất có thể tự sửa e? Theo định lý điều kiện đủ (ĐK Vassharmov-Gilbert-Sacks): ∑− = −≥ 12 0 12 e i i n m C ⇔ (*) ∑− = −≥ 12 0 15 32 e i iC e =1 ⇒ (*) đúng. e > 1 ⇒ (*) sai. Vậy số bit lỗi lớn nhất có thể tự sửa là e = 1. Bài tập 1. Xây dựng bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 101101 101110 111001 A 2. Tìm bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 101101 101010 111001 A ¾ Gợi ý giải bài tập 1 & 2: dựa vào phương pháp sinh mã kiểm tra chẵn lẻ và tham khảo ví dụ sinh mã kiểm tra chẵn lẻ. 3. Xét bộ mã kiểm tra chẵn lẻ độ dài 15 bit có thể tự sửa được 1 bit lỗi trên đường truyền, hãy cho biết số bit kiểm tra chẵn lẻ tối thiểu? 4. Xét bộ mã kiểm tra chẵn lẻ độ dài 8 bit với 4 bit kiểm tra chẵn lẻ. Hãy cho biết số lỗi tự sửa tối đa của bộ mã? Gợi ý giải bài tập 3 & 4: dựa vào đinh lý Điều kiện cần (Cận Hamming) và Điều kiện đủ (ĐK Varshamov-Gilbert-Sacks). Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 68 Giáo trình: Lý thuyết thông tin. BÀI 5.4: NHÓM CỘNG TÍNH VÀ BỘ TỪ Mà CHẴN LẺ Mục tiêu. Sau khi hoàn tất bài học này bạn có thể: ƒ Hiểu Khái niệm nhóm cộng tính, ƒ Biết các tính chất của bộ mã chẵn lẻ, ƒ Vận dụng sinh ma trận kiểm tra chắn lẻ từ bộ mã kiểm tra chẵn lẻ. ƒ Vận dụng tốt phương pháp sinh bộ mã kiểm tra chẵn lẻ từ các từ mã độc lập tuyến tính của bộ mã. Khái niệm nhóm cộng tính. Đặt vấn đề: Như chúng ta đã biết, phương pháp sinh mã kiểm tra chẵn lẻ giúp ta sinh bộ mã kiểm tra chẵn lẻ với số từ mã tương ứng là s=2k. Với phương pháp này, ta phải xác định từng từ mã một (bằng cách giải hệ phương trình tuyến tính nhị phân). Giả sử: k=5 ta phải xác định s=25 =32 từ mã hay k=10 ta phải xác định s=210=1024 từ mã,Điều này sẽ mất nhiều thời gian nếu k càng lớn. Vấn đề đặt ra ở đây là tìm ra một phương pháp sinh bộ mã kiểm tra chẵn lẻ nhanh hơn về mặt thời gian. Phương pháp sinh mã kiểm tra chẵn lẻ dựa theo lý thuyết nhóm sẽ giải quyết vấn đề này. Khái niệm nhóm cộng tính: Nhóm G được gọi là một nhóm cộng tính nếu G có các tính chất: - ∀ a, b ∈ G ⇒ a+b ∈ G ( tính chất cộng). - ∀ a, b, c ∈ G ⇒ a + (b + c)= (a + b) + c ( tính chất kết hợp). - ∃ ∅ ∈ G sao cho ∅ + a = a + ∅ = a, ∀a∈ G (∅ là Identity Element của G). - ∀ a ∈ G ∃ -a∈G : a + (-a)=∅ Nhóm G là nhóm hoán vị (nhóm Aben) nếu ∀a,b ∈ G=> a + b = b + a. Ví dụ: - Tập hợp các số nguyên với phép + thông thường là nhóm Aben. - Tập hợp các số nhị phân có độ dài n bit cùng với phép + trong Modulo 2 tạo thành nhóm Aben. Tính chất của bộ mã chẵn lẻ Tính tương đương của bộ mã nhóm cộng tính và bộ từ mã kiểm tra chẵn lẻ được thể hiện qua 2 định lý sau: Định lý 1: tập hợp các từ mã trong bộ mã kiểm tra chẵn lẻ là một nhóm cộng tính. (Đề nghị sinh viên chứng minh định lý này dựa vào các tính chất của nhóm cộng tính) Định lý 2: Nếu tập hợp W là tập các dãy nhị phân với độ dài các dãy cùng bằng n và W là một nhóm Aben với phép cộng Modulo 2 thì W có thể xem như một bộ mã kiểm tra chẵn lẻ được sinh ra từ ma trận A có dạng như sau: Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 69 Giáo trình: Lý thuyết thông tin. ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = mkmm k k m bbb bbb bbb IA ... ............ ... ... 21 22221 11211 Trong đó: - Ma trận A có m dòng và n cột. - Im : là ma trận đơn vị cấp m. - k: là số dãy nhị phân (hay từ mã) độc lập tuyến tính lớn nhất. - n: là độ dài của từ mã và m = n-k: - bij: được xác định bằng cách dựa vào hệ phương trình tuyến tính (*) và k từ mã độc lập tuyến tính như sau: w’i=r1r2r3rm rm+1rm+2rn. ),1( ki =∀ Đoạn kiểm tra Đoạn thông tin ⎪⎩ ⎪⎨ ⎧ ++= ++= ++ ++ kmmkmmm kmkm rbrbr rbrbr ... .................................... ... (*) 11 11111 Thế k từ mã độc lập tuyến tính vào hệ pt (*) để tìm các bij ⇒ ma trận A. Ví dụ minh họa Xét tập hợp M gồm có 8 dãy nhị phân dài 6 bits như sau: r1 r2 r3 r4 r5 r6 w’0 = 0 0 0 0 0 0 w’1 = 1 0 1 0 0 1 w’2 = 1 1 0 0 1 0 w’3 = 0 1 0 1 0 1 w’4 = 0 1 1 0 1 1 (w’1+w’2) w’5 = 1 1 1 1 0 0 (w’1+w’3) w’6 = 1 0 0 1 1 1 (w’2+w’3) w’7 = 0 0 1 1 1 0 (w’1+w’2+w’3) Ta thấy {w1, w2, w3} là tập hợp lớn nhất các từ mã độc lập tuyến tính từ tập hợp M: w’1 = 1 0 1 0 0 1 w’2 = 1 1 0 0 1 0 w’3 = 0 1 0 1 0 1 ⇒ n=6 và k=3. => m = n – k = 3. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 70 Giáo trình: Lý thuyết thông tin. Như vậy: ma trận kiểm tra chẵn lẻ có dạng như sau: ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 333231 232221 131211 3 bbb bbb bbb IA Các bij ( 3,1, =∀ ii ) được xác định từ hệ phương trình tuyến tính nhị phân sau: => ⎪⎪ ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎪⎪ ⎨ ⎧ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 333231 232221 131211 bbb bbb bbb b11 = 1 b12 = 1 b13 = 1 => b21 = 1 b22 = 1 b23 = 0 b31 = 1 b32 = 0 b33 = 1 => A= ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 101100 011010 111001 Vậy ta có thể sử dụng nhóm M như là một bộ mã kiểm tra chẵn lẻ. Phương pháp sinh mã kiểm tra chẵn lẻ nhanh Bước khởi tạo: xác định các giá trị n, m, k, s. Bước 1: sinh k từ mã độc lập tuyến tính (đltt). Bước 2: cộng tổ hợp các từ mã: + Cộng các tổ hợp của 2 từ mã từ k mã đltt => có từ mã. 2kC ---- + Cộng các tổ hợp của k từ mã từ k từ mã đltt => có từ mã. kkC Bước 3: Cộng s-1 từ mã đã tìm được để tìm từ mã cuối cùng => = 1 từ mã. 0kC Tổng số từ mã s= từ mã. k k i i kC 2 0 =∑ = Ví dụ sinh mã kiểm tra chẵn lẻ nhanh Tìm bộ mã nhóm khi biết trước ma trận kiểm tra ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 101101 101110 011001 A Bước khởi tạo: n = 6, m = 3, k = 3, s = 2k = 8. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 71 Giáo trình: Lý thuyết thông tin. Bước 1: Sinh k = 3 từ độc lập truyến tính: w’1=001001, w’2=111010, w’3=110100 Bước 2: Cộng tổ hợp các từ mã. + Cộng các tổ hợp 2 từ mã đltt: w’4=w’1+w’2=110011 w’5=w’1+w’3=111101 w’6=w’2+w’3=001110 + Cộng các tổ hợp 3 từ mã đltt: w’7=w’1+w’2+w’3=001111 Bước 3: xác định từ mã cuối cùng: w’0=w’1+w’2+w’3+w’4+w’5+w’6+w’7=000000 Bài tập 1. Sử dụng phương pháp sinh mã nhanh cho bộ mã từ ma trận kiểm tra A như sau: ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 101101 101110 111001 A 2. Sử dụng phương pháp sinh mã nhanh cho bộ mã từ ma trận kiểm tra A trong các trường hợp sau: ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ = 000101 001010 010100 101000 A ; ; ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ = 100111 001111 011110 111100 A ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ = 101000 110100 010010 110001 A Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 72 Giáo trình: Lý thuyết thông tin. BÀI 5.5: LƯỢC ĐỒ SỬA LỖI TỐI ƯU Mục tiêu Sau khi hoàn tất bài học này bạn có thể: - Biết được vấn đề của bài toán, - Hiểu Định nghĩa Hiệp hợp, - Vận dụng để xây dựng lược đồ sửa lỗi theo các hiệp hợp, - Vận dụng để xây dựng lược đồ sửa lỗi thông qua bộ sửa lỗi, - Vận dụng tính Xác suất truyền đúng cho lược đồ sửa lỗi, - Kiến thức đạt được sẽ là cơ sở để các bạn có thể ứng dụng cho việc thiết kế một hệ, thống mã hóa, giải mã và bảo mật thông tin. Đặt vấn đề Trong một hệ thống liên lạc truyền tin, bên cạnh các yêu cầu thiết bị (như nguồn phát, bộ mã hóa, kênh truyền, bộ giải mã,) đảm bảo tốt cho việc truyền và nhận dữ liệu thì còn có các khía cạnh khác như phương pháp mã hóa và giải mã sao cho tối ưu là phần rất quan trọng trong hệ thống. Vấn đề luôn được đặt ra ở đây là làm thế nào để chỉ ra một phương pháp giải mã tối ưu, có nghĩa là hệ thống phải có khả năng phát hiện và sửa lỗi một cách chính xác nhất có thể có khi nhiễu xảy ra. Đây chính là vấn đề chính được thảo luận trong suốt bài học này. Định nghĩa Hiệp hợp Gọi W={w1, w2, ,ws} là bộ mã kiểm tra chẵn lẻ. V ={v1, v2, , } là tập hợp các dãy n bit có thể nhận được ở cuối kênh. nv2 Ta gọi một hiệp hợp của W trong V là tập hợp có dạng z + W (z là bộ lỗi) Ví dụ: Cho ma trận kiểm tra chẵn lẻ sau: ⎥⎦ ⎤⎢⎣ ⎡= 1110 0101 A Từ A, ta có thể xây dựng được bộ mã tương ứng sau: W={w’0=0000, w’1=0101, w’2=1110, w’3=1011}. Ta có thể thấy rằng, các bộ lỗi một bit khác nhau có thể có là z={1000, 0100, 0010, 0001}. Do đó các hiệp hợp ứng với các bộ lỗi 1 bit sẽ là: w0 w1 w2 w3 0000 0101 1110 1011 Hiệp hợp 1 1000 1101 0110 0011 (với z1=1000) Hiệp hợp 2 0100 0001 1010 1111 (với z2=0100) Hiệp hợp 3 0010 0111 1100 1001 (với z3=0010) Hiệp hợp 4 0001 0100 1111 1010 (với z4=0001) Trong đó: hiệp hợp i = wi + zi, các bạn có thể xét thêm các bộ lỗi sai 2 bit, 3 bit, để được các hiệp hợp ứng với các bộ lỗi sai 2 bit, 3bit,. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 73 Giáo trình: Lý thuyết thông tin. Lược đồ sửa lỗi theo các hiệp hợp Bước 1: Lập bảng các hiệp hợp ứng với các bộ lỗi cần thiết - Dòng đầu tiên viết các từ mã wi ∈ W. - Các dòng tiếp theo ứng với cột w0 = 0000 viết các bộ lỗi z (các bộ lỗi 1 bit, 2 bit,). - Các dòng ở cột thứ i được xác định bởi z + wi Bước 2: Quá trình giải mã Giải mã: khi nhận v, ta xác định cột thứ i chứa v và giải mã về wi tương ứng. Ví dụ: xây dựng lược đồ sửa lỗi theo các hiệp hợp cho bộ mã được sinh từ ma trận kiểm tra chẵn lẻ sau: ⎥⎦ ⎤⎢⎣ ⎡= 1110 0101 A Từ A, ta có thể xây dựng được bộ mã tương ứng sau: W={w’0=0000, w’1=0101, w’2=1110, w’3=1011}. Bước 1: Lập bảng các hiệp hợp ứng với các bộ lỗi cần thiết: Ta xây dựng các hiệp hợp ứng với các bộ lỗi sai 1 bit. Vậy z={1000, 0100, 0010, 0001}. w0 w1 w2 w3 0000 0101 1110 1011 Hiệp hợp 1 1000 1101 0110 0011 (với z1=1000) Hiệp hợp 2 0100 0001 1010 1111 (với z2=0100) Hiệp hợp 3 0010 0111 1100 1001 (với z3=0010) Hiệp hợp 4 0001 0100 1111 1010 (với z4=0001) (Bảng các hiệp hợp) Bước 2: Quá trình giải mã: Giả sử nhận v = 0111. Tra tìm v trên bảng các Hiệp hợp ta có v ở cột 1. Do đó, v được giải mã về w1 = 0101. Giả sử nhận v = 1010. Tra tìm v trên bảng các Hiệp hợp ta có v ở cột 2 hay cột 3. Do đó, v được giải mã về w2 hay w3, trong trường hợp này giải mã không chính xác. Đề nghị các bạn lưu ý và cho ý kiến của bạn về các trường hợp giải mã không chính xác này. Lược đồ sửa lỗi thong qua bộ lỗi Để xây dựng lược đồ sửa lỗi thông qua bộ sửa lỗi, ta dựa vào tính chất của bộ sửa lỗi. Như vậy ta có thể thấy lược đồ giải mã gồm 2 bước sau: Bước 1: Lập bảng sửa lỗi: Bộ lỗi (Z) – Bộ sửa lỗi (C=A*Z). Bước 2: Quá trình sửa lỗi - Khi nhận được dãy n bit v ∈V, ta xác định bộ điều lỗi C cho v với C=A.v - Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C. - Giải mã w=v+z0. Ví dụ minh họa lược đồ sửa lỗi 1 bit Xét bộ mã được sinh từ ma trận ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 101000 110100 010010 110001 A Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 74 Giáo trình: Lý thuyết thông tin. Bộ mã tương ứng được xác định là: w1=000000, w2=101101, w3=111010, w4=010111 (Đề nghị các bạn tham khảo phương pháp sinh mã chẵn lẻ và xây dựng lại bộ mã từ ma trận kiểm tra chẵn lẻ A). Lược đồ sửa lỗi: Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 1) Bộ lỗi (z’) Bộ điều chỉnh (C’=A.z) Bộ 0 lỗi 000000 0000 1 Bộ Bộ lối 1 bit 100000 1000 010000 0100 001000 0010 6 Bộ 000100 0001 000010 1110 000001 1011 Bước 2: Quá trình sửa lỗi - Giả sử nhận v=001101, tính C = A.v = 1000 - Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C, ta có z0 = 100000 - Giải mã w = v + z0 = 001101 + 100000 = 101101 = w2 Ví dụ minh họa lược đồ sửa lỗi 2 bit Lược đồ sửa lỗi: Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 2) Bộ lỗi (z’) Bộ điều chỉnh (C’=A.z) Bộ lỗi 2 bit 110000 1100 101000 1010 100100 1001 100010 0110 100001 0011 7 Bộ 011000 0110 010100 0101 (Tất cả các bộ 2 lỗi còn lại có trùng bộ điều chỉnh với các bộ ở trên) Bước 2: Quy trình sửa lỗi - Giả sử nhận v=100111, tính C = A.v = 1100 - Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C, ta có z0 = 110000 - Giải mã w = v + z0 = 100111 + 110000 = 010111 = w4 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 75 Giáo trình: Lý thuyết thông tin. Ví dụ minh họa lược đồ sửa lỗi 3 bit Lược đồ sửa lỗi: Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 3) z’ C=A.z Bộ lỗi 3 bit 110100 1101 2 Bộ 110001 0111 (Tất cả các bộ 3 lỗi còn lại có trùng bộ điều chỉnh với các bộ ở trên) Bước 2: Quy trình sửa lỗi Giả sử nhận v=011001, tính C = A.v = 1101 Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C, ta có z0 = 110100 Giải mã w=v + z0 = 011001 + 110100 = 101101 = w2 Chú ý: Tổng số bộ điều chỉnh = 2m. Trong một số trường hợp, bộ mã chẵn lẻ chỉ cho phép phát hiện lỗi trên đường truyền và không thể giải mã chính xác do tổng số bộ điều chỉnh = 2m và số bộ lỗi có thể lớn hơn nhiều (so với tống số bộ điều chỉnh). Xác suất truyền đúng Gọi Ni là số bộ lỗi ứng với i lỗi có thể tự sửa, khi đó xác suất truyền đúng và tự điều chỉnh sẽ là: ∑ = −−= n i iniiNieP 0 )1.(.)'( ββ Với n là độ dài từ mã Ví dụ: xét trường hợp các ví dụ trên với n= 6 và tự sửa e = 3 bit lỗi. Áp dụng công thức trên ta có: 334256 3 0 )1(2)1(7)1(6)1()1.(.)'( βββββββββ −+−+−+−=−= ∑ = − i iniiNieP Bài tập 1. Cho ma trận kiểm tra chẵn lẻ sau: ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 101101 101110 111001 A - Xây dựng bộ mã kiểm tra chẵn lẻ. - Minh họa quy trình sửa lỗi 1 bit. 2. Từ kết quả của bài tập 1, hãy minh họa lược đồ sửa lỗi thông qua bộ điều chỉnh trong các trường hợp lỗi 1 bit, 2 bit. Tính xác suất truyền đúng cho các trường hợp có thể tự sửa được. BÀI 5.6: Mà HAMMING Mục tiêu Sau khi hoàn tất bài học này bạn có thể: Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 76 Giáo trình: Lý thuyết thông tin. - Hiểu Mã Hamming, - Hiểu tính chất của mã Hamming. Mã Hammin Mã Hamming là một dạng mã nhóm (mã kiểm tra chẵn lẻ) được xác định từ ma trận kiểm tra chẵn lẻ A có dạng sau: - Cột thứ j của ma trận A là biểu diễn nhị phân m bit (m là số bit kiểm tra chẵn lẻ) của số j theo qui ước biểu diễn nhị phân của số j được viết theo thứ tự từ dưới lên trên (viết theo cột), tương đương với viết từ trái sang phải (viết theo dòng). - Các bit ở vị trí 2i ( i = 0, 1, 2, ) được chọn làm bit kiểm tra. Ví dụ 1: biểu diễn nhị phân của số j = 3 có m = 3 bit như sau: Viết theo dòng: 011 (viết từ trái sang phải) Viết theo cột: (viết từ dưới lên) ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 0 1 1 Ví dụ 2: ma trận kiểm tra chẵn lẻ với n=6, m=3 có thể viết như sau: ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 111000 100110 010101 A Từ mã Hamming có dạng: w=r1r2r3r4r5r6. Trong đó, r1r2r4 là các bit kiểm tra và r3r5r6 là các bit thông tin (vì các bit ở vị trí 2i (với i = 0, 1, 2, ) được chọn làm bits kiểm tra). Tính chất Nếu cho trước số bit (m) và số bit lỗi tự sửa (e) thì số bit tối đa của bộ mã Hamming (n) có thể được ước lượng từ bất đẳng thức sau: ∑ = ≥ e oi i n m C2 Ví dụ minh họa Tìm bộ mã Hamming với n = 6 và m =3 Ta có thể viết ngay ma trận kiểm tra chẵn lẻ cho bộ mã Hamming ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 111000 100110 010101 A Từ A ⇒ k = n – m = 3. Các bit ở các vị trí 1, 2, 4 được chọn làm các bit kiểm tra. => số từ mã của bộ mã Hamming là s = 2k = 8 Tìm k từ mã độc lập tuyến tính có dạng: w’1=r1r20r401 w’2=r1r20r410 w’3=r1r21r400 Giải các hệ phương trình: A.w1=0, A.w2=0, A.w3=0 Các từ mã còn lại được xác định theo phương pháp sinh mã nhanh. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 77 Giáo trình: Lý thuyết thông tin. Ghi chú: Kết quả chi tiết xây dựng bảng mã Hamming dành cho sinh viên tự làm. Bài tập 1. Viết ma trận kiểm tra chẵn lẻ cho bộ mã Hamming với n = 15. 2. Từ kết quả bài tập 1, hãy tìm các từ mã Hamming độc lập tuyến tính tương ứng. 3. Xét bộ mã Hamming với số bit kiểm tra cho trước là m, khi đó: - Độ dài mã tối thiểu là bao nhiêu? - Độ dài mã tối đa là bao nhiêu? Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 78 Giáo trình: Lý thuyết thông tin. BÀI 5.7: THANH GHI LÙI TỪNG BƯỚC Mục tiêu Sau khi hoàn tất bài học này bạn có thể biết: - Đặt vấn đề về thanh ghi lùi từng bước, - Cách biểu diễn vật lý của thanh ghi, - Cách biểu diễn toán học của thanh ghi, - Tìm chu kỳ của thanh ghi. Đặt vấn đề Như chúng ta đã biết, phương pháp sinh bộ mã kiểm tra chẵn lẻ dựa trên lý thuyết nhóm cho phép chúng ta sinh mã nhanh bằng cách chỉ sinh ra k từ mã độc lập tuyến tính trong tổng số s=2k từ mã, từ k từ mã này ta có thể xác định các từ mã còn lại (bằng cách cộng tổ hợp các từ mã). Vấn đề đặt ra ở đây là làm sao để tìm ra một phương pháp sinh mã khác sao cho số từ mã sinh ban đầu nhỏ hơn k (k là số từ mã độc lập tuyến tính của bộ mã kiểm tra chẵn lẻ) và từ đây ta có thể xác định nhanh các từ mã còn. Cụ thể dựa trên mô hình của thanh ghi lùi từng bước có thể giải quyết được vấn đề này. Biểu diễn vật lý của thanh ghi Để gọi một cách ngắn gọn, ta qui ước gọi thanh ghi thay vì goi thanh ghi lùi từng bước. Biểu diễn vật lý của thanh ghi có thể thấy như hình vẽ dưới đây: - Fm-1, Fm-2, , F1, F0 : các bit lưu trữ dữ liệu nhị phân. - am-1, am-2, , a1, a0 : các công tắc (switch) dùng để đóng (=1) hay mở ( =0). - : là bộ làm tính cộng trong phép toán mudulo 2 sau mỗi xung đồng hồ với dữ liệu do các bit của thanh ghi gửi về. + Fm-1 Fm-2 F1 F0 am-1 a0 a1 am-2 + Quá trình dịch chuyển lùi từng bước: sau mỗi xung đồng hồ thì dữ liệu trong bit Fi sẽ được chuyển về lưu trữ ở bit Fi-1 (F1-> F0; F2->F1; ; Fm-2->Fm-3; Fm-1->Fm-2). Tất cả các giá trị trên các Fi (trước khi có xung điện) sẽ được chuyển về bộ cộng (tùy theo các công tắc đóng hay mở), tổng của các giá trị này sẽ được đưa vào lưu trữ ở bit Fm-1. Ta sẽ nghiên cứu thanh ghi này cụ thể hơn trong các nội dung tiếp theo nhằm tìm ra một phương pháp sinh mã mà ta có thể gọi là mã xoay vòng. Đây cũng là một dạng mã kiểm tra chẵn lẻ. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 79 Giáo trình: Lý thuyết thông tin. Biểu diễn toán học của thanh ghi Mục tiêu của việc biểu diễn toán học là để tìm ra các mô hình tính toán phục vụ cho việc nghiên cứu sinh mã xoay vong chẵn lẻ từ thanh ghi. Gọi x = (x0, x1, , xm-2, xm-1) là giá trị các bit của thanh ghi tại thời điểm trước khi có nhịp xung đồng hồ. x’ = (x’0, x’1, , x’m-2, x’m-1) là giá trị các bit của thanh ghi sau khi có nhịp xung đồng hồ. Khi đó ta có: x’0=x1 x’1=x2 x’2=x3 ---------- x’m-2=xm-1 x’m-1=a0x0 + a1x1 + + am-1xm-1. Hay viết theo dạng ma trận ta có x’ = T.x Trong đó: T= ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ −− 123210 ... 10..0000 ..................... 00...0000 0001000 0000100 0000010 mm aaaaaa - T: Ma trận vuông cấp m. - Dòng cuối của ma trân: là các hệ số: a0, a1, , am-1. - Gốc trên bên phải: là ma trận đơn vị cấp m-1. T được gọi là ma trận đặc trưng của thanh ghi lùi từng bư Quá trình dịch chuyển lùi từng bước của thanh ghi: Gọi x(0)= ⎟⎟ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎝ ⎛ −1 3 2 0 mx x x x M là véc tơ chỉ giá trị của thanh ghi tại thời Giá trị của thanh ghi sau 1 xung đồng hồ là x(1)=T.x(0) Giá trị của thanh ghi sau 2 xung đồng hồ là x(2)=T.x(1)=T2 Giá trị của thanh ghi sau 3 xung đồng hồ là x(3)=T.x(2)=T3 ----------- Ví dụ thanh ghi lui từng bước Cho thanh ghi lui từng bước sau: + F3 F1 F2 Từ thanh ghi, ta có: m=4, a0=1, a1=0, a2=1, a3=0. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Kớc. điểm đang xét. .x(0) .x(0) F0 s. Dương Văn Hiếu. 80 Giáo trình: Lý thuyết thông tin. Ma trận đặc trưng của thanh ghi: T= ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ 0101 1000 0100 0010 Chu kỳ của thanh ghi Như đã trình bày ở trên về quá trình dịch chuyển lùi từng bước của thanh ghi: Nếu ta gọi x(0)= ⎟⎟ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎝ ⎛ −1 3 2 0 mx x x x M là véc tơ chỉ giá trị của thanh ghi tại thời điểm khởi tạo thì các giá trị của thanh ghi ở các thời điểm tiếp theo như sau: Giá trị của thanh ghi sau 1 xung đồng hồ là x(1)=T.x(0) Giá trị của thanh ghi sau 2 xung đồng hồ là x(2)=T.x(1)=T2.x(0) Giá trị của thanh ghi sau 3 xung đồng hồ là x(3)=T.x(2)=T3.x(0) ---------------- Giá trị của thanh ghi sau n xung đồng hồ là x(n)=T.x(n-1)=Tn.x(0) (bởi vì số trạng thái thông tin khác nhau có thể có là 2m) Vậy chu kỳ của thanh ghi là số xung nhịp đồng hồ để thanh ghi lặp lại trạng thái ban đầu. Nghĩa là nếu x(0)≠0 và ∃ n>0 sao cho x(n) = x(0) thì ta nói n là chu kỳ của thanh ghi. Lưu ý: Cách viết biểu diễn nhị phân cho giá trị của x(i) theo thứ tự từ trên xuống (theo cột), tương ứng với viết từ trái sang phải (theo dòng). Ví dụ: biểu diễn nhị phân của x(i) = 3 có m = 3 bit như sau: Viết theo dòng: x(i) = 011 (viết từ trái sang phải) Viết theo cột: (viết từ trên xuống) ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ = 1 1 0 x (i) Ví dụ tìm chu kỳ của thanh ghi Cho thanh ghi lui từng bước như hình sau: + F3 F1 F2 F0 Từ thanh ghi ta có: m=4, a0=1, a1=0, a2=1, a3=0. Ma trận đặc trưng của thanh ghi: T= ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ 0101 1000 0100 0010 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 81 Giáo trình: Lý thuyết thông tin. Đặc giá trị khởi tạo của thanh ghi x(0)=1= = ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 3 2 1 0 x x x x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 0 0 Tìm chu kỳ: X(1)=T.x(0)= ⇒ x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 1 0 0 (2)=T.x(1)= ⇒ x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 1 0 (3)=T.x(2)= ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 1 0 1 ⇒ x(4)=T.x(3)= ⇒ x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 0 1 0 (5)=T.x(4)= ⇒ x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 0 0 1 (6)=T.x(5)= = x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 0 0 (0) Tương tự: + Khi chọn x(0) = 3 thi ta cũng có chu kỳ n = 6. + Khi chọn x(0) = 6 thì ta có chu kỳ n = 3. + Khi chọn x(0) = 0 thì ta có chu kỳ n = 1. Chu kỳ n=6 Chu kỳ n=6 Chu kỳ n=3 Chu kỳ n=1 14 8 4 1 7 3 5 2 10 0 11 13 6 1512 9 Thanh ghi trên có 4 chu kỳ. Bài tập 1. Tìm các chu kỳ của thanh ghi lui từng bước như hình sau: + F2 F0F1F2 2. Tìm các chu kỳ của thanh ghi lui từng bước như hình sau: F2 F1 F0+ BÀI 5.8: Mà XOAY VÒNG Mục tiêu Sau khi hoàn tất bài học này bạn có thể: Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 82 Giáo trình: Lý thuyết thông tin. - Biết cách xác định ma trận kiểm tra chẵn lẻ cho mã xoay vòng (hay còn gọi là mã vòng), - Hiểu định nghĩa mã xoay vòng, - Vận dụng xây dựng bộ mã xoay vòng, - Vận dụng phương pháp sinh nhanh bộ mã xoay vòng để sinh bộ mã kiểm tra chẵn lẻ. Ma trận kiểm tra chẵn lẻ mã xoay vòng Định nghĩa: ma trận kiểm tra chẵn lẻ được thiết kế từ thanh ghi lùi từng bước là ma trận có dạng sau: A=[x(0)| T x(0)|T2 x(0) ||Tn-1 x(0)] với n là chu kỳ của thanh ghi (n > m) Trong đó: - T là ma trận đặc trưng của thanh ghi. - x(0) ≠ 0: là giá trị khởi tạo của thanh ghi. - n : là chiều dài của từ mã và cũng là chu kỳ của thanh ghi. - m: là số bit kiểm tra hay số bit của thanh ghi. Ví dụ: xét lại ví dụ tìm chu kỳ thanh ghi, nếu chọn giá trị khởi tạo của thanh ghi là x(0) = 1 thì ta có ma trận kiểm tra với chu kỳ n=6 như sau: ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ == 000101 001010 010100 101000 ] x x x x x x[A (5)(4)(3)(2)(1)(0) Định nghĩa mã xoay vòng Mã xoay vòng là mã kiểm tra chẵn lẻ được sinh ra từ ma trận kiểm tra chẵn lẻ ứng với chu kỳ n của thanh ghi lùi từng bước có dạng như: A=[x(0)| Tx(0)|T2x(0) ||Tn-1x(0) ] Ví dụ: xét lại ma trận kiểm tra chẵn lẻ ở trên ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 000101 001010 010100 101000 A (chu kỳ n = 6) Ta có n = 6, m = 3, k = 2 ⇒ s = 2k = 22 = 4 từ mã. Áp dụng Phương pháp sinh mã nhanh bộ mã kiểm tra chẵn lẻ ta có bộ mã kiểm tra chẵn lẻ gồm 4 từ mã sau : w0 = 000000, w1 = 101010, w2 = 010101, w4 = 111111, đây chính là một trong các bộ mã xoay vòng sinh từ thanh ghi lùi từng bước nêu trên (Các bước sinh mã nhanh đề nghị các bạn tự làm) Phương pháp sinh nhanh bộ mã xoay vòng Cách sinh nhanh k từ mã độc lập tuyến tính của bộ mã vòng từ a0, a1, a2, , am-1: Bước 1: sinh mã xoay vòng đầu tiên Sinh mã xoay vòng đầu tiên có dạng w1=a0a1a2am-1 100000 k-1 bit 0 Bước 2: sinh k -1 từ mã độc lập tuyến tính còn lại Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 83 Giáo trình: Lý thuyết thông tin. w2= 0a0a1a2am-110000 (dịch w1 sang phải 1 bit). k-2 bit 0 . wk= 00000a0a1a2am-11 (dịch từ wk-1 sang phải 1 bit). k-1 bit 0 Bước 3: xác định các từ mã còn lại của bộ mã Các từ mã còn lại gồm (2k – k từ mã) được xác định bằng cách cộng tổ hợp của 2, 3, , k từ mã từ k từ mã độc lập tuyến tính ở trên. Ví dụ sinh nhanh bộ mã xoay vòng Cho thanh ghi lui từng bước như hình sau: + F3 F1 F2 F0 Từ thanh ghi, ta có: m=4, n=6, a0=1, a1=0, a2=1, a3=0. Bước 1: Sinh mã xoay vòng đầu tiên w1=101010 Bước 2: Sinh k -1 từ mã độc lập tuyến tính còn lại w2=010101 Bước 3: Xác định các từ mã còn lại của bộ mã w3 =111111 (w1+w2), w0 =000000 (w1+w2 + w3) Bộ mã vòng vừa sinh là W={000000, 101010, 010101, 111111) Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 84 Giáo trình: Lý thuyết thông tin. Bài tập 1. Cho thanh ghi lùi từng bước sau: - Tìm ma trận kiểm tra chẵn lẻ có số cột n > 4 + F0 F1 F2 - Từ kết quả câu a, xác định bộ mã xoay vòng tương ứng. - Tìm bộ mã xoay vòng theo phương pháp sinh nhanh bộ mã xoay vòng 2. Cho thanh ghi lùi từng bước sau: + F3 F0 F1 F2 - Tìm ma trận kiểm tra chẵn lẻ có số cột n > 4 - Từ kết quả câu a, xác định bộ mã xoay vòng tương ứng. - Tìm bộ mã xoay vòng theo phương pháp sinh nhanh bộ mã xoay vòng. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 85 Giáo trình: Lý thuyết thông tin. BÀI 5.9: ĐA THỨC ĐẶC TRƯNG CỦA THANH GHI Mục tiêu Sau khi hoàn tất bài học này bạn có thể: - Hiểu định nghĩa đa thức đặc trưng của thanh ghi, - Hiểu Quan hệ giữa chu kỳ n, đa thức đặc trưng và đa thức (xn + 1), - Vận dụng sinh thanh ghi lùi từng bước, - Làm cơ sở để vận dụng sinh bộ mã vòng. Định nghĩa đa thức đặc trưng của thanh ghi Định nghĩa: đa thức đặc trưng của thanh ghi có ma trận đặc trưng là T là đa thức có dạng gm(x)=a0 + a1x+ a2 x2+ +am-1xm-1 + xm. với a0, a1, a2,, am-1 là các công tắc của thanh ghi và m là số bit của thanh ghi Ví dụ: xét lại thanh ghi như hình sau: + F3 F0 F1 F2 a0 = 1, a1= 0, a2 = 1, a3 = 0 Đa thức đặc trưng của thanh ghi có dạng: gm(x)=1 + x2 + x4. Quan hệ giữa chu kỳ n, đa thức đăc trưng và đa thức (xn + 1) Đa thức đặc trưng của thanh ghi gm(x)=a0 + a1x+ a2 x2+ +am-1xm-1 + xm luôn chia hết đa thức (xn + 1). Ví dụ: xét lại thanh ghi lui từng bước như hình sau: + F3 F0 F1 F2 Từ thanh ghi ta có thể xác định các kết quả sau: - a0 = 1, a1= 0, a2 = 1, a3 = 0 - Đa thức đặc trưng của thanh ghi có dạng: g4(x)=1 + x2 + x4. - Thanh ghi này có chu kỳ n = 6. Thực hiện phép chia đa thức (x6 + 1) : (1 + x2 + x4) = (x2 + 1) ⇒ chia hết. Ghi chú: phép toán trên đa thức nhị phân vẫn là phép toán Modulo 2. Ví dụ: xét lại thanh ghi lui từng bước như hình sau: + F3 F0 F1 F2 a0 = 1, a1= 0, a2 = 1, a3 = 0 đa thức đặc trưng của thanh ghi có dạng: g4(x)=1 + x2 + x4. thanh ghi này có chu kỳ n = 6 và (x6 + 1) : 1 + x2 + x4 = x2 + 1. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 86 Giáo trình: Lý thuyết thông tin. Thủ tục sinh thanh ghi lùi từng bước Để sinh thanh ghi lùi từng bước với số bit là m và có chu kỳ n, ta có thể thực hiện theo các bước sau: Bước 1: xác định đa thức đặc trưng của thanh ghi - Tìm 2 đa thức gm(x)=a0 + a1x+ a2 x2+ +am-1xm-1 + xm và hk(x)=h0 + h1x+ h2x2 + +hk-1xk-1 + xk sao cho (xn + 1) = gm(x)* hk(x). - Nếu ∃ (xn + 1) = gm(x)* hk(x) thì ta chọn gm(x) làm đa thức đặc trưng cho thanh ghi (vì số bit kiểm tra của bộ mã là m) và thực hiện bước 2. - Ngược lại: không tồn tại thanh ghi theo yêu cầu. Bước 2: vẽ thanh ghi Từ gm(x)=a0 + a1x+ a2 x2+ +am-1xm-1 + xm ⇒ a0, a1, a2,, am-1 ⇒ thanh ghi có dạng: + Fm-1 Fm-2 F1 F0 am-1 a0 a1 am-2 Ví dụ minh họa Thiết kế thanh ghi có m=3 bit và chu kỳ n=7, ta thực hiện theo 2 bước sau: Bước 1: Xác định đa thức đặc trưng của thanh ghi Ta có (x7 + 1) : (1 + x2 + x3) = (1 + x2 + x3 + x4) Do m=3 nên chọn g3(x) = (1 + x2 + x3) làm đa thức đặc trưng của thanh ghi. Bước 2: Vẽ thanh ghi Từ g3(x) = (1 + x2 + x3) ta có, a0=1, a1=0, a2=1 + F0 F1 F2 Bài tập 1. Trong các thanh ghi sau đây, thanh ghi nào sinh ra bộ mã vòng có độ dài n=15 bit? (R1): + F3 F0 F1 F2 + F3 F0 F1 F2 + F3 F0 F1 F2 (R2): (R3): 2. Nêu các bước cần thiết để thiết kế bộ mã xoay vòng độ dài 15 bit với số bit kiểm tra là 4. Vẽ sơ đồ thanh ghi dạng tổng quát. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 87 Giáo trình: Lý thuyết thông tin. Bài 5.10: PHƯƠNG PHÁP SINH Mà XOAY VÒNG Mục tiêu Sau khi hoàn tất bài học này bạn có thể: - Hiểu các phương pháp sinh mã vòng, - Biết bảng liệt kê một số đa thức đặc trưng, - Vận dụng để sinh mã vòng theo nhiều cách khách nhau. Đặt vấn đề Để sinh bộ mã kiểm tra chẵn lẻ, ta có thể dựa theo nhiều phương pháp khác nhau như: sinh mã dựa theo lý thuyết nhóm, mã Hamming,... Vấn đề đặt ra ở đây là làm sao để sinh bộ mã xoay vòng với độ dài n bit và m bit kiểm tra chẵn lẻ. Phương pháp sinh mã xoay vòng dựa trên lý thuyết về đa thức đặc trưng nhị phân của thanh ghi giúp ta có cái nhìn tổng quát về vấn đề sinh bộ mã xoay vòng theo nhiều cách khác nhau. Phương pháp sinh bảng mã xoay vòng Để sinh mã xoay vòng độ dài n bit với m bit kiểm tra và k bit thông tin, ta có thể thực hiện theo các bước sau: Bước 1: tìm 2 đa thức gm(x)=a0 + a1x+ a2 x2+ +am-1xm-1 + xm và hk(x)=h0 + h1x+ h2x2 + +hk-1xk-1 + xk sao cho (xn + 1) = gm(x)* hk(x). Nếu ∃ (xn + 1) = gm(x)* hk(x) thì chuyển sang bước 2 Ngược lại không thể sinh bộ mã vòng theo yêu cầu. Bước 2: ta có thể sinh bộ mã xoay vòng theo các cách như dưới đây: Cách 1: Chọn đa thức gm(x)=a0 + a1x+ a2 x2+ +am-1xm-1 + xm ⇒ a0, a1, a2,, am-1 ⇒ thanh ghi ⇒ ma trận đặc trưng T ⇒ chu kỳ n ⇒ ma trận kiểm tra chẵn lẻ A. ⇒ Bộ mã xoay vòng. Cách 2: chọn đa thức gm(x)=a0 + a1x+ a2 x2+ +am-1xm-1 + xm ⇒ a0, a1, a2,, am-1 ⇒ Sinh nhanh k từ mã độc lập tuyến tính với từ mã sinh độc lập tuyến tính đầu tiên có dạng: w1=a0a1a2am-1100000 ⇒ Bộ mã xoay vòng. k-1 bit 0 Cách 3: chọn hk(x)=h0 + h1x+ h2x2 + +hk-1xk-1 + xk làm đa thức sinh ma trận kiểm tra chẵn lẻ cho bộ mã vòng có dạng: ⎟⎟ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎝ ⎛ −−−−−− −−−−−− −−−−−−−−−−−−−− −−−−−− −−−−−− − − − − 00001 00010 01000 10000 011 011 011 011 hhh hhk hhh hhh k k k k m (m-1) bits ⇒ Sinh bộ mã xoay vòng theo Phương pháp sinh nhanh bộ mã xoay vòng. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 88 Giáo trình: Lý thuyết thông tin. Nhận xét: kết quả theo 3 cách sinh bộ mã xoay vòng nói trên la như nhau (cho cùng bộ mã). Ví dụ minh họa 1 Thiết kế thanh ghi và sinh ma trận kiểm tra chẵn lẻ. Chọn đa thức gm(x)= 1+x+x4 ⇒ a0 = 1, a1 = 1, a2 = 0, a3 = 0 + F3 F0 F1 F2 Ma trận đặc trưng của thanh ghi: T= ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ 0011 1000 0100 0010 Tìm chu kỳ của thanh ghi: Chọn giá trị khởi tạo x(0)=1= ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 0 0 x(1)=T.x(0)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 1 0 0 (2)=Tx(1)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 0 1 0 (3)=Tx(2)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 0 1 (4)=Tx(3)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 1 0 0 (5)=Tx(4)= ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 1 1 0 x(6)=Tx(5)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 1 1 (7)=Tx(6)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 1 0 1 (8)=Tx(7)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 1 0 (9)=Tx(8)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 1 0 1 (10)=Tx(9)= ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 1 1 0 x(11)=Tx(12)= ;x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 1 1 1 (12)=Tx(11)= ;x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 1 1 1 (13)=Tx(12)= ;x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 0 1 1 (14)=Tx(13)= ; x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0 0 0 1 (15)=T.x(14) = = x ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 1 0 0 0 (0) Ma trận kiểm tra chẳn lẻ : A= ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 000111101011001 001111010110010 011110101100100 111101011001000 ⇒ Bộ mã xoay vòng vớin=14, m=4, k=11. Ví dụ minh họa 2 Chọn đa thức gm(x)= 1+x+x4 ⇒ a0 = 1, a1 = 1, a2 = 0, a3 = 0. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 89 Giáo trình: Lý thuyết thông tin. Bước 1: Sinh mã xoay vòng đầu tiên w1 =110010000000000 Bước 2: Sinh k -1 từ mã độc lập tuyến tính còn lại w2 =011001000000000 w3 =001100100000000 w4 =000110010000000 w5 =000011001000000 w6 =000001100100000 w7 =000000110010000 w8 =000000011001000 w9 =000000001100100 w10=000000000110010 w11=000000000011001 Bước 3: Xác định các từ mã còn lại của bộ mã (215 - 11) từ mã còn lại được xác định bằng cách cộng tổ hợp 2, 3, 4,.., k = 11 từ mã từ k=11 từ mã độc lập tuyến tính. Ví dụ minh họa 3 Chọn hk(x)= 1+ x + x2 + x3 +x5 + x7 + x8 + x11 làm đa thức sinh ma trận kiểm tra chẵn lẻ cho bộ mã vòng ⇒ h0 = 1, h1 = 1, h2 = 1, h3 = 1, h4 = 0, h5 = 1, h6 = 0, h7 = 1, h8 =1, h9 = 0, h10 = 0. A= ⇒ Bộ mã xoay vòng ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 000111101011001 001111010110010 011110101100100 111101011001000 Bảng liệt kê một số đa thức đặc trưng M Đa thức M Đa thức 3 1+x+x3 14 1+x+x6+x10+x14 4 1+x+x4 15 1+x+x15 5 1+x2+x5 16 1+x+x3+x12+x16 6 1+x+x6 17 1+x3+x7 7 1+x3+x7 18 1+x7+x18 8 1+x2+x3+x4+x8 19 1+x+x2+x5+x19 9 1+x4+x9 20 1+x3+x20 10 1+x3+x10 21 1+x2+x21 11 1+x2+x11 22 1+x+x22 12 1+x+x4+x6+x12 23 1+x3+x23 13 1+x+x3+x4+x13 24 1+x+x2+x7+x24 Bài tập 1. Tìm bộ mã vòng có độ dài 7 bit. 2. Tìm thanh ghi sinh bộ mã vòng có độ dài 15 bit. 3. Tìm thanh ghi sinh bộ mã vòng có độ dài 31 bit. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 90 Giáo trình: Lý thuyết thông tin. BÀI TẬP TỔNG HỢP Mục tiêu Sau khi hoàn tất bài học này bạn có thể: - Hiểu rõ hơn về nội dung môn học. - Vận dụng nội dung môn học để giải quyết một số bài tập tổng hợp. Bài 1 Xét một mô hình chẩn đoán bệnh từ các triệu chứng: A, B và C; để chẩn đoán 1 trong 4 bệnh: 1, 2, 3 và 4 với ma trận chẩn đoán (hay ma trận truyền tin). Bệnh Triệu chứng 1 2 3 4 A 0,6 0,3 0 0,1 B 0,2 0,6 0,2 0 C 0 0 0,3 0,7 Yêu cầu: Câu 1: Vẽ sơ đồ mô tả mô hình chẩn đoán bệnh trên và diễn giải các ý nghĩa của sơ đồ. Câu 2: Nếu phân phối của Triệu chứng có dạng: Triệu chứng A B C P 0,5 0,3 0,2 Tính các lượng sau : ¾ Lượng ngẫu nhiên (Entropy) của Triệu chứng . ¾ Lượng ngẫu nhiên của Bệnh. ¾ Lượng ngẫu nhiên của Bệnh khi biết Triệu chứng. ¾ Lượng chẩn đoán đúng.(Lượng thông tin biết về Bệnh thông qua Triệu chứng) và tỷ lệ chẩn đoán đúng là bao nhiêu phần trăm. Câu 3: Bây giờ người ta sử dụng 2 bit để mã thông tin về Triệu chứng (có 1 triệu chứng dự trữ) và 5 bit để mã các triệu chứng khi chẩn đoán bệnh trực tuyến. Mô tả các đoạn của dãy 5 bit trong phương pháp kiểm tra chẵn lẻ. Câu 4: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 A = Tính các từ mã. Xây dựng Bộ sửa lỗi 1 bit dùng cho tự động sửa lỗi tối ưu trong quá trình chẩn đoán trực tuyến. Cho một ví dụ. Bài 2 Xét một kênh truyền tin đặc biệt dạng : Truyền X Æ Nhận Y. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 91 Giáo trình: Lý thuyết thông tin. Truyền một giá trị của X có thể nhận được nhiều giá trị khác nhau của Y với các xác suất khác nhau. Bảng xác suất truyền X và nhận các Y khác nhau được cho dưới đây: Y X y1 y2 y3 y4 y5 y6 x0 0,6 0,1 0,1 0,05 0,05 0,1 x1 0,1 0,05 0,6 0,1 0,1 0,05 x2 0,05 0,1 0,1 0,05 0,6 0,1 x3 0,1 0,05 0,05 0,1 0,1 0,6 Yêu cầu: Câu 1: Vẽ sơ đồ mô tả kênh truyền tin trên và diễn giải các ý nghĩa của sơ đồ. Câu 2: Nếu phân phối của X có dạng : X x0 x1 x3 x4 P 0.5 0.25 0.15 0.1 tính thông lượng về X truyền trên kênh. Câu 3: Phân phối của X cần có dạng như thế nào để thông lượng truyền trên kênh là lớn nhất. Tính dung lượng kênh truyền. Câu 4: Bây giờ người ta sử dụng 2 bit để mã thông tin về X và 4 bit để mã các giá trị truyền trên kênh. Mô tả các đoạn của dãy 4 bit trong phương pháp kiểm tra chẵn lẻ. Câu 5: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 1 1 1 0 0 1 0 1 A = Tính các từ mã. Xây dựng Bộ sửa lỗi dùng cho tự động sửa lỗi tối ưu trong quá trình truyền tin. Cho một ví dụ. Bài 3 Người ta cần đánh giá kênh truyền tin và chuẩn bị thực hiện truyền một loại tín hiệu đặc biệt: X = {x0, x1, x2, x3} Công việc đầu tiên là phải khảo sát kênh truyền. Kết quả khảo sát cho thấy: Kênh có thể truyền nhận được 8 giá trị khác nhau, để có khả năng phát hiện lỗi hoặc điều chỉnh lỗi. Ma trận truyền tin có dạng: Y X y1 y2 y3 y4 y5 y6 y7 y8 x0 0,6 0,1 0,05 0,05 0,05 0,05 0,05 0,05 x1 0,05 0,05 0,6 0,1 0,05 0,05 0,05 0,05 x2 0,05 0,05 0,05 0,05 0,6 0,1 0,05 0,05 x3 0,05 0,05 0,05 0,05 0,05 0,05 0,6 0,1 Yêu cầu: Câu 1: Vẽ sơ đồ mô tả kênh truyền tin trên và diễn giải các ý nghĩa của sơ đồ. Nếu phân phối của X có dạng : X x0 x1 x3 x4 P 0.5 0.25 0.15 0.1 tính thông lượng về X truyền trên kênh. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 92 Giáo trình: Lý thuyết thông tin. Câu 2: Phân lớp các giá trị của Y về các lớp B0, B1, B2, và B3 dùng để giải mã tối ưu Y tốt nhất về các giá trị tương ứng của X. Câu 3 : Bây giờ người ta sử dụng 2 bit để mã thông tin về X và 4 bit để mã các giá trị truyền trên kênh. Mô tả các đoạn của dãy 4 bit trong phương pháp kiểm tra chẵn lẻ. Câu 4: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 1 0 0 1 0 1 1 1 A = Tính các từ mã. Xây dựng Bộ sửa lỗi dùng cho tự động sửa lỗi tối ưu trong quá trình truyền tin. Cho một ví dụ. Bài 4 Xét một mô hình chẩn đoán bệnh từ các triệu chứng: A, B và C; để chẩn đoán 1 trong 4 bệnh: 1, 2, 3 và 4 với ma trận chẩn đoán (hay ma trận truyền tin) Bệnh Triệu chứng 1 2 3 4 A 0,5 0,3 0 0,2 B 0,1 0,2 0,7 0 C 0 0,1 0,3 0,6 Yêu cầu: Câu 1: Giả sử người ta biết thêm 3 triệu chứng gây bệnh khác đó là : D, E và F và muốn ghi lại các triệu chứng này thông qua bảng ký hiệu A = {+, - }. Hãy kiểm tra tính tách được của bảng mã sau : Triệu chứng : X A B C D E F Mã : W + -+ ++- --+- ++-+ -- Câu 2: Nếu các triệu chứng ở câu 1 có phân phối : Triệu chứng : X A B C D E F P 0.5 0.2 0.2 0.05 0.03 0.2 Giử sử có một người bệnh với 1 trong 5 triệu chứng trên đến khám bệnh và bác sĩ sẽ hỏi bệnh với nguyên tắc, sao cho người bệnh chỉ trả lời bằng 2 câu : Đúng hoặc Sai. ¾ Tìm phương pháp hỏi bệnh với số câu hỏi trung bình ít nhất. ¾ Tính số câu hỏi trung bình. ¾ Tính lượng ngẫu nhiên của Triệu chứng. ¾ Nhận xét gì về số câu hỏi trung bình và lượng ngẫu nhiên của triệu chứng. Câu 3: Bây giờ sử dụng mô hình 3 triệu chứng {A, B, C} và 4 bệnh. Vẽ sơ đồ mô tả mô hình chẩn đoán bệnh và diễn giải các ý nghĩa của sơ đồ. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 93 Giáo trình: Lý thuyết thông tin. Câu 4: Từ kết quả câu 3, người ta sử dụng 2 bit để mã thông tin về Triệu chứng (có 1 triệu chứng dự trữ) và 5 bit để mã các triệu chứng khi chẩn đoán bệnh trực tuyến. Mô tả các đoạn của dãy 5 bit trong phương pháp kiểm tra chẵn lẻ. Câu 5: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 A = Tính các từ mã. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 94 Giáo trình: Lý thuyết thông tin. TÀI LIỆU THAM KHẢO 12. G.J.ChaiTin, Algorithmic Information Theory, CamBridge University Express-1992. 13. David J.C. Mackey, Information Theory, Infernce, and Learning Algorithms, CamBridge University Express-2003. 14. Sanford Goldman, Information Theory. 15. 16. 17. 18. 19. 20. 21. 22. Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 95