Bài giảng Lý thuyết thông tin

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA ĐIỆN-ĐIỆN TỬ BÀI GIẢNG LÝ THUYẾT THÔNG TIN Hưng Yên 2015 (Tài liệu lưu hành nội bộ) TỔNG QUAN VỀ MÔN HỌC Chƣơng 1: Khái niệm chung. Chƣơng này giới thiệu những khái niệm và các vấn đề cơ bản trong lý thuyết truyền tin nhƣ thông tin, tín hiệu, mô hình của hệ thống truyền tin gồm những thành phần nào và các tham số cơ bản của hệ thống là gì. Mặt khác chƣơng này cũng nhắc lại phƣơng pháp rời rạc hóa một nguồn tin liên tục thành nguồn rời rạc. Cuối chƣơng đƣa ra khái niệm về độ đo thông tin và nhắc lại những cơ sở toán học cần thiết cho việc khảo sát các hệ thống truyền tin. Chƣơng 2: Thông tin Chƣơng này trình bày những vấn đề về định lƣợng thông tin của nguồn tin nhƣ lƣợng tin riêng, lƣợng tin trung bình, lƣợng tin tƣơng hỗ, lƣợng tin có điều kiện (vì tín hiệu truyền trên kênh bị nhiễu tác động nên khi thu đƣợc tín hiệu ta phải tìm khả năng đầu phát đã phát đi tín hiệu nào vì vậy chƣơng này liên quan nhiều đến xác suất. Cụ thể là xác suất riêng, xác suất đồng thời và xác suất có điều kiện và mối liên hệ chúng). Sau đó tập trung giải quyết các vấn đề về entropy để đo lƣợng tin không chắc chắn của một sự kiện hay phân phối ngẫu nhiên cũng nhƣ các tính chất của nó. Khi tín hiệu đƣợc truyền đi trên kênh nên chƣơng này cũng đƣa ra các loại kênh truyền và các tham số kỹ thuật của kênh đồng thời xác định độ không chắc chắn khi nhận đƣợc một tin cụ thể đã bị nhiễu phá hủy một phần trên kênh từ đó tính toán dung lƣợng C của kênh truyền để xác định giới hạn trên của tốc độ mà ta có thể truyền không lỗi. Phần cuối của chƣơng sẽ đề cập đến việc giải mã (tức nhận đƣợc một tin ta phải đi tìm tin nào đã đƣợc truyền đi ở bên phát). Sau đó tính các xác suất truyền sai một từ mã và xác suất truyền sai trung bình. Chƣơng 3: Mã hiệu. Chƣơng này ta tập trung vào các khả năng và các định nghĩa về mã cũng nhƣ các điều kiện và yêu cầu đối với mã hiệu, tức là đƣa ra các phƣơng pháp để lựa chọn, kiểm tra một bộ mã là phân tách đƣợc và khi nào thì có thể giải mã (độ chậm giải mã). Phần cuối của chƣơng nói về việc lập một bộ mã hệ thống. Chƣơng 4: Mã hóa nguồn. Chƣơng này nghiên cứu các vấn đề mã hóa nguồn trên cơ sở mô hình toán học của nguồn và các khả năng về lƣợng tin đã xét. Cụ thể chƣơng này đề cập đến 3 phƣơng pháp mã hóa để loại bỏ sự dƣ thừa của thông tin. Ba phƣơng pháp đó là:  Phƣơng pháp mã hóa Shannon.  Phƣơng pháp mã hóa Fano.  Phƣơng pháp mã hóa Huffman. Mỗi phƣơng pháp đều đƣa ra phƣơng pháp chuyển các tin thành các từ mã dựa vào xác suất xuất hiện của nó (tức là các tin có xác suất xuất hiện bé thì mã hóa bằng từ mã có chiều dài lớn và các tin có xác suất xuất hiện lớn thì mã hóa bằng từ mã có chiều dài nhỏ) và sau đó tính hiệu suất lập mã. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 2 Chƣơng 5. Mã phát hiện lỗi và sửa lỗi Trong chƣơng 4 ta nghiên cứu các phƣơng pháp để giảm chiều dài trung bình của một bộ mã dựa vào xác suất xuất hiện của từng lớp tin thì trong chƣơng này ta lại thêm vào một số bít kiểm tra để phát hiện sai và sửa sai để đảm bảo chất lƣợng. Cụ thể ta nghiên cứu đến 4 loại mã là:  Mã khối tuyến tính.  Mã Hamming  Mã vòng.  Mã chập. Mỗi loại mã đều đƣa ra phƣơng pháp lập mã và giải mã. Để học tốt về chƣơng này sinh viên cần có kiến thức về nhân chia đa thức và các phép biến đổi sơ cấp về ma trận. Chƣơng 6: Mã mật. Chƣơng 4 đƣợc nghiên cứu với mục đích đảm bảo tính hữu hiệu của hệ thống truyền tin thì chƣơng 5 đƣợc nghiên cứu với mục đích đảm bảo chất lƣợng và chƣơng 6 sẽ đảm bảo tính an toàn. Trong chƣơng này ta sẽ nghiên cứu một số hệ thống mật mã đơn giản để có cách nhìn sơ lƣợc về mã mật và sau đó tập trung vào trình bày các cách thức tấn công vào một hệ thống mật mã. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 3 CHƢƠNG 1: KHÁI NIỆM CHUNG 1.1 Khái niệm chung về hệ thống thông tin và truyền tin. 1.1.1. Thông tin. - Hai ngƣời nói chuyện với nhau. Cái mà họ trao đổi gọi là thông tin. - Một ngƣời xem tivi/nghe đài/đọc báo, ngƣời đó đang nhận thông tin từ đài phát/báo. - Quá trình giảng dạy trong lớp. Nhận xét: + Thông tin là cái đƣợc truyền từ đối tƣợng này sang đối tƣợng khác để báo một “điều” gì đó. Thông tin ch có ý nghĩa khi “điều” đó bên nhận chƣa biết. + Thông tin xuất hiện dƣới nhiều dạng nhƣ âm thanh, hình ảnh + Ngữ nghĩa của thông tin ch có thể hiểu đƣợc khi bên nhận hiểu đƣợc cách biểu diễn ngữ nghĩa của bên phát. + Một trong các phƣơng tiện để diễn đạt thông tin là ngôn ngữ. + Có hai trạng thái của thông tin: Truyền và lƣu trữ. Môi trƣờng truyền/lƣu trữ đƣợc gọi chung là môi trƣờng chứa tin hay kênh tin. Định nghĩa: Thông tin là sự cảm hiểu của con ngƣời về thế giới xung quanh (thông qua sự tiếp xúc với nó). 1.1.2. Tín hiệu. Thông tin là một hiện tƣợng vật lý, nó thƣờng tồn tại và đƣợc truyền đi dƣới dạng vật chất nào đó. Những dạng vật chất dùng để mang thông tin đƣợc gọi là tín hiệu. Định nghĩa: Tín hiệu là biểu diễn vật lý của thông tin. Ví dụ: Các tín hiệu nhìn thấy là các song ánh sang mang thông tin tới mắt của chúng ta. Các tín hiệu nghe thấy là các sự biến đổi của áp suất không khí truyền thông tin tới tai chúng ta. Chú ý: Không phải bản thân quá trình vật lý là tín hiệu, mà sự biến đổi các tham số riêng của quá trình vật lý mới là tín hiệu. Các đặc trƣng vật lý có thể là dòng điện, điện áp, ánh sáng, âm thanh, trƣờng điện từ. 1.2 Mô hình của hệ thống truyền tin. Sự truyền tin (transmission): Là sự dịch chuyển thông tin từ điểm này đến điểm khác trong một môi trƣờng xác định. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 4 Hệ thống thông tin (hệ thống truyền tin) là hệ thống thực hiện việc chuyển tin từ nguồn đến đích. Ta xét một hệ thống thông tin tổng quát nhƣ hình vẽ dƣới đây. Ba phần tử cơ bản nhất của bất cứ hệ thống thông tin nào cũng phải có đó là máy phát, máy thu và kênh truyền. Mỗi phần tử có một vai trò nhất định trong việc truyền dẫn tín hiệu. Máy phát xử lý tín hiệu đầu vào và tạo ra tín hiệu có những đặc tính thích hợp với kênh truyền dẫn. Quá trình xử lý tín hiệu để truyền dẫn chủ yếu là điều chế và mã hóa (modulation and coding). Kênh truyền là môi trƣờng giữa điểm phát và điểm thu. Kênh truyền có thể là cáp song hành, cáp đồng trục, cáp quang hay môi trƣờng vô tuyến. Mọi kênh truyền đều gây ra độ suy hao hay là độ tổn thất truyền dẫn. Vì thế cƣờng độ tín hiệu bị suy giảm dần theo khoảng cách. Máy thu lấy tín hiệu đầu ra từ kênh truyền để xử lý và tái tạo ngƣợc lại tín hiệu ở đầu phát. Các hoạt động của máy thu bao gồm khuếch đại để bù vào tổn hao truyền dẫn, và giải điều chế và giải mã tín hiệu đã đƣợc điều chế và mã hóa ở máy phát. 1.3. Các yêu cầu cơ bản của hệ thống truyền tin. 1.3.1. Tính hữu hiệu. Thể hiện trên các mặt sau: - Tốc độ truyền tin cao. - Truyền đƣợc đồng thời nhiều tin khác nhau. - Chi phí cho một bit thông tin thấp. 1.3.2. Độ tin cậy. Đảm bảo độ chính xác của việc thu nhận tin cao, xác suất thu sai thấp (BER – Bit Error Rate). Hai ch tiêu trên mâu thuẫn nhau. Giải quyết mâu thuẫn trên là nhiệm vụ của Nguồn tin Bộ phát Kênh truyền Bộ thu Ngƣời dùng Nhiễu §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 5 lý thuyết thông tin. 1.3.3. An toàn. - Bí mật: + Không thể khai thác thông tin trái phép. + Ch có ngƣời nhận hợp lệ mới hiểu đƣợc thông tin. - Xác thực: Gắn trách nhiệm của bên gửi – bên nhận với bản tin (chữ ký số). - Toàn vẹn: + Thông tin không bị bóp méo (cắt xén, xuyên tạc, sửa đổi). + Thông tin đƣợc nhận phải nguyên vẹn cả về nội dung và hình thức. - Khả dụng: Mọi tài nguyên và dịch vụ của hệ thống phải đƣợc cung cấp đầy đủ cho ngƣời dùng hợp pháp. 1.4. Độ đo thông tin. Các mục về sau chúng ta sẽ khảo sát lƣợng đo thông tin một cách chi tiết hơn, ở đây chúng ta ch nêu một khái niệm ban đầu về lƣợng tin để có thể so sánh định lƣợng các thông tin với nhau. Từ đó giúp cho chúng ta dễ nhận thức hơn những ch tiêu chất lƣợng đề ra khi xây dựng các phƣơng pháp xử lý thông tin. Một tin tức đối với ngƣời nhận đều mang hai đặc tính: Độ bất ngờ của tin và ý nghĩa của tin. Để so sánh giữa các tin với nhau ngƣời ta có thể dùng một trong hai đặc tính trên hoặc dùng cả hai đặc tính trên làm thƣớc đo. Tuy nhiên những nội dung mang tính ý nghĩa của tin không ảnh hƣởng đến các vấn đề cơ bản của hệ thống thông tin (hệ thống thông tin đòi hỏi hai vấn đề cơ bản đó là tốc độ truyền tin và độ chính xác). Trong khi đó độ bất ngờ của tin lại liên quan đến những vấn đề đó. Một tin có xác suất xuất hiện càng nhỏ thì độ bất ngờ càng lớn (càng bất ngờ) thì khi xuất hiện tác động càng mạnh lên giác quan của con ngƣời, và chúng ta cho rằng lƣợng tin của chúng càng lớn. Xét một tin x có xác suất xuất hiện là p(x) thì chúng ta có thể xem tin này nhƣ là một tin trong một tập có 1/p(x) tin với các tin có xác suất xuất hiện nhƣ nhau. Nếu p(x) càng nhỏ thì 1/p(x) càng lớn và vì vậy “lƣợng tin” khi nhận đƣợc tin này cũng sẽ càng lớn. Vậy “lƣợng tin” của một tin t lệ thuận với số khả năng của một tin và t lệ nghịch với xác suất xuất hiện của tin đó. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 6 Định nghĩa lƣợng tin: Lƣợng đo thông tin của một tin đƣợc đo bằng logarit độ bất ngờ của tin hay nghịch đảo xác suất xuất hiện của tin đó.    n i iap xp xI 1 )(log )( 1 log)( Đơn vị lƣợng tin: Cơ số 2: đơn vị là Bit. Cơ số e: đơn vị là Nat Cơ số 10: đơn vị là Hartley. 1.5. Số hóa nguồn tin liên tục. Rời rạc hoá thƣờng bao gồm hai loại: Rời rạc hoá theo trục thời gian, còn đƣợc gọi là lấy mẫu (sampling) và rời rạc hoá theo biên độ, còn đƣợc gọi là lượng tử hoá (quantize). 1.5.1 Lấy mẫu (Sampling). Lấy mẫu là bƣớc đầu tiên trong quá trình biến đổi tín hiệu tƣơng tự sang số. Mục đích của bƣớc lấy mẫu này là từ tín hiệu tƣơng tự tạo nên một dãy xung rời rạc theo thời gian (thực chất là việc nhân tín hiệu thoại đầu vào với một chuỗi xung nhịp f s = t 1 Ví dụ: x a (t) là một hàm theo thời gian, t là biến thì lẫy mẫu là rời rạc hóa biến t. Định lý lấy mẫu: Nếu ta muốn khôi phục tín hiệu tƣơng tự thì tín hiệu lấy mẫu một cách trung thành thì tần số lấy mẫu lớn hơn hoặc bằng hai lần bề rộng phổ của tín hiệu (bề rộng của băng tần cơ bản). Fs  2B B Ts 2 1  Fs Tần số lấy mẫu. Ts Chu kỳ lấy mẫu. B Bề rộng phổ tín hiệu. Nếu Fs = 2B thì tần số lấy mẫu này gọi là tần số Nyquist. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 7 1.5.2 Lƣợng tử hóa (Quantizing) Lƣợng tử hóa tức là rời rạc hóa hàm  a (t) hay nói cách khác chia dải động tín hiệu thành M mức (mức biên độ chuẩn đã đƣợc định nghĩa sẵn trong một dải biên độ tín hiệu cho trƣớc. ) sau đó thực hiện làm tròn các xung lấy mẫu về các mức gần nhất. Việc lƣợng tử hoá sẽ biến đổi hàm s(t) ban đầu thành một hàm s’(t) có dạng hình bậc thang. Sự khác nhau giữa s(t) và s’(t) đƣợc gọi là sai số lƣợng tử. Sai số lƣợng tử càng nhỏ thì s’(t) biểu diễn càng chính xác s(t). 1.5.3 Mã hóa (Coding) Quá trình mã hóa biến đổi các mức lƣợng tử hóa thành các từ mã, thông thƣờng là từ mã nhị phân. Trong tín hiệu nhị phân, “0” và “1” đƣợc thể hiện bằng hai mức điện áp khác nhau. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 8 CHƢƠNG 2: THÔNG TIN 2.1 Lƣợng tin nguồn rời rạc 2.1.1 Khái niệm nguồn tin rời rạc - Nguồn rời rạc: nguồn tạo ra một chuỗi các biến ngẫu nhiên, rời rạc - Ký hiệu: Phần tử nhỏ nhất chứa thông tin. VD các ký tự trong bộ chữ cái - Bộ ký hiệu: Tập tất cả các ký hiệu [X]={x1,x2,xn} - Từ: Tập hợp hữu hạn các ký hiệu trong bộ ký hiệu - Bộ từ: Tập hợp tất cả các từ mà bộ ký tự có thể tạo ra - Nguồn rời rạc không nhớ: Xác suất xuất hiện của một ký hiệu không phụ thuộc vào các ký hiệu trƣớc đó. - Nguồn rời rạc có nhớ: Xác suất xuất hiện một ký tự phụ thuộc vào một hoặc nhiều các ký tự xuất hiện trƣớc đó 2.1.2 Lƣợng tin nguồn rời rạc Lƣợng tin riêng: Mỗi lớp tin xi trong nguồn tin X đều có một lƣợng tin riêng đƣợc xác định theo công thức: )(log )( 1 log)( in i ni xp xp xI  Đơn vị lƣợng tin: - Cơ số n = 2: Bit (Binary – nhị phân) - Cơ số n = e: Nat (đọc là nit – nature) - Cơ số n = 10: Harley. Trong môn học này tập trung trình bày mã nhị phân nên mặc định n = 2. Trong hệ thống thông tin, việc truyền tin từ nguồn tin X đến nơi nhận Y đƣợc coi nhƣ một phép biến đổi (ánh xạ) từ một không gian X tới một không gian Y. Do tác động của nhiễu nên ánh xạ này không phải là ánh xạ 1-1. Nói cách khác, việc nhận đƣợc một lớp tin yj cụ thể ở nơi nhận ch cho chúng ta biết khả năng tin tức của nguồn tin X truyền đi lớp tin xi, điều này theo quan điểm thống kê có thể xác định đƣợc xác suất có điều kiện về sự xuất hiện các lớp tin xi ở nguồn với điều kiện nơi nhận nhận đƣợc lớp tin yj. Xác suất này đƣợc gọi là xác suất có điều kiện, ký hiệu là p(xi/yj). p(xi/yj): xác suất có điều kiện về sự xuất hiện các lớp tin xi ở nguồn với điều kiện nơi nhận nhận đƣợc lớp tin yj p(yj/xi):xác suất có điều kiện về sự xuất hiện các lớp tin yj ở nơi nhận tin với điều kiện nguồn tin phát đi lớp tin xi §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 9 Ngoài ra ta còn xác định đƣợc xác suất xuất hiện đồng thời các lớp tin xi ở nguồn và yi ở nơi nhận là p(xi,yi) Theo quy luật phân bố xác suất có điều kiện ta có:       m i ij n j ji xyp yxp 1 1 1)/( 1)/( Để giải quyết bài toán truyền tin đặt ra khi nhận đƣợc một lớp tin yj của tập của tập YM, hãy xác định lớp tin tƣơng ứng của tập XN ở đầu vào. Ở đây ta không thể xác định đƣợc chính xác duy nhất một lớp tin xi ở đầu vào mà ch đƣa ra các khả năng có thể xảy ra ở nguồn. Lƣợng tin tƣơng hỗ: Là lƣợng tin về một tin bất kỳ xi trong nguồn tin XN chứa trong một tin bất kỳ yj của nơi nhận tin YM đƣợc gọi là lƣợng tin tƣơng hỗ giữa xi và yj bằng lƣợng tin ban đầu của xi trừ đi lƣợng tin còn lại của xi sau khi đã nhận đƣợc yj. )|()(),( jii yxIxIyjxiI  )|(log)(log),( jii yxPxPyjxiI  )( )|( log),( i ji xP yxP yjxiI  Lƣợng tin có điều kiện: Lƣợng tin còn lại của xi sau khi đã nhận đƣợc yj đƣợc gọi là lƣợng tin có điều kiện của xi với điều kiện nơi nhận nhận đƣợc yj )|(log)|( jiji yxpyxI  Lƣợng tin còn lại này chính là lƣợng tin do nhiễu phá hủy không đến đƣợc nơi nhận 2.2 Entropi nguồn rời rạc 2.2.1 Định nghĩa Lƣợng tin trung bình đƣợc hiểu là lƣợng tin trung bình trong một tin bất kỳ của nguồn tin đã cho. Khi nhận đƣợc một tin, ta sẽ nhận đƣợc một lƣợng tin trung bình, đồng thời độ bất ngờ của tin cũng đƣợc giải thoát, do vậy độ bất ngờ của tin và lƣợng tin về ý nghĩa vật lý trái ngƣợc nhau nhƣng về số đo lại bằng nhau. Độ bất ngờ của lớp tin xi trong nguồn tin XN đƣợc tính bằng entropy riêng của lớp tin xi trong nguồn tin XN §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 10 Entropy là một đại lƣợng toán học dùng để đo lƣợng tin không chắc (hay lƣợng ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trƣớc - Uncertainty Measure (độ bất ngờ) hay là lƣợng tin không chắc chắn Entropy riêng của của lớp tin i: H(xi) = -logn p(xi) Độ bất ngờ trung bình của nguồn tin XN đƣợc gọi là entropy riêng trung bình hay là entropy riêng của nguồn tin XN, đây chính là một thông số thống kê cơ bản của nguồn: H(X) =   N i ii xHxp 1 )()( (bít/ký hiệu)       N n nn ppXH 1 log (bít/ký hiệu) Ví dụ: Cho X = {0, 1}, P(0) = p, còn P(1) = 1–p. Tính H(X)? H(X) = –{plog(p) + (1– p) log(1– p)} 2.2.2 Tính chất của Entropy  Entropy là đại lƣợng luôn dƣơng hoặc bằng 0: H(X)  0  Entropy bằng 0 khi nguồn có một ký hiệu bất kỳ có xác suất xuất hiện bằng 1 và tất cả các ký hiệu còn lại có xác suất xuất hiện bằng 0. Khi đó giá trị tin tức của nguồn không còn ý nghĩa H(X) = 0  ( xi /p(xi) =1)  (xj/p(xj) = 0  j  i)  Entropi cực đại khi xác suất xuất hiện các ký hiệu của nguồn bằng nhau, lúc đó độ bất định của một tin bất kỳ trong nguồn là lớn nhất: H(X) ≤ H(X)max ≤ logn(N). Dấu bằng xảy ra khi p1=p2==pn=1/N 2.3 Kênh rời rạc. 2.3.1 Định nghĩa. Nguồn tin và nhận tin liên hệ với nhau qua kênh thông tin, và kênh thông tin thực hiện một phép biến đổi từ không gian các ký hiệu ở đầu vào tới không gian các ký hiệu ở đầu ra của kênh. Kênh đƣợc gọi là rời rạc nếu không gian ký hiệu vào và không gian ký hiệu ra là rời rạc. Kênh đƣợc gọi là liên tục nếu các hai không gian ký hiệu vào ra là liên tục. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 11 Nếu sự truyền tin trong kênh là liên tục theo thời gian thì kênh đƣợc gọi là liên tục thời gian và nếu sự truyền tin ch thực hiện ở những thời điểm rời rạc theo thời gian thì kênh đƣợc gọi là rời rạc theo thời gian. 2.3.2 Entropy đồng thời. Giả thiết X là tập các ký hiệu đầu vào [X]=[x1, x2, . xn] với xác suất xuất hiện là [P(x)]=[p(x1), p(x2), .., p(xN)] . [P(x)] Phản ánh tính chất của nguồn tin. [Y ]=[y1, y2, , yM]: Tập các ký hiệu ở đầu ra với các xác suất xuất hiện tƣơng ứng [P(y)]=[p(y1), p(y2), .., p(yM)] Do nhiễu trên kênh thông tin nên không gian Y có thể khác không gian X, cũng nhƣ các xác suất P(Y) cũng có thể khác các xác suất ở đầu vào P(X). Với không gian các ký hiệu ở đầu vào kênh và ở đầu ra kênh, ta có thể định nghĩa một trƣờng tích:                mnnn m m yxyxyx yxyxyx yxyxyx YX ... ............ ... ... , 21 22212 12111 Trong đó tích xiyj là sự xuất hiện đồng thời hai sự kiện xi và yj. Chú ý rằng ở đây ta không giả thiết gì về sự độc lập hay phụ thuộc giữa xi và yj. Ma trận trên tƣơng ứng với ma trận xác suất sau: P                               mnnn m m yxpyxpyxp yxpyxyxp yxpyxpyxp YX ... ............ ... ... , 21 22212 12111 Từ ma trận xác suất ta có: p(xi) =   m j ji yxp 1 ),( p(yj) =  n i ji yxp 1 ),( Nhƣ vậy ta có thể định nghĩa ba trƣờng sự kiện: - Trƣờng ở đầu vào kênh với entropy H(X):         N i ii xpxpXH 1 log. - Trƣờng ở đầu ra kênh với entropy H(Y):         M j ii ypypYH 1 log. - Trƣờng ở giữa đầu vào và đầu ra kênh với entropy H(X,Y). §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 12 Entropi đồng thời là độ bất định trung bình của một cặp (x,y) bất kỳ trong tập tích XY          N i M j jiji yxpyxpYXH 1 1 log., Các công thức liên quan:       M j jii yxpxp 1 ;       N i jij yxpyp 1 Ví dụ: Cho hai biến X, Y độc lập nhau và có phân phối: X 0 1 P 0.5 0.5 Y 0 1 2 P 0.25 0.5 0.25 Tính H(X,Y)?  H(X,Y)= 0.125*log0.125 + 0.25*log0.25 + 0.125*log0.125 + 0.125*log0.125 + 0.25*log0.25 + 0.125*log0.125=2.5 (bit/ký hiệu) Tính chất của Entropy đồng thời : H(X,Y)  H(X) + H(Y) Dấu bằng xảy ra khi X, Y độc lập tuyến tính. (SV tự chứng minh tính chất này) 2.3.3 Entropi có điều kiện. Khi đầu ra của kênh đã biết, do nhiễu tác động vẫn còn sự bất định về đầu vào của kênh. Giá trị trung bình của độ bất định này đƣợc gọi là entropi của trƣờng X khi trƣờng Y đã biết H(X|Y): Là entropy có điều kiện đặc trƣng cho độ bất định về nguồn tin XN còn lại khi đã nhận đƣợc các lớp tin YM. Độ không xác định này do nhiễu trên kênh thông tin gây ra. H(Y|X): Entropy có điều kiện cho biết độ bất định của nguồn tin nơi nhận YM khi biết nguồn tin XN. Độ không xác định này cũng do nhiễu trên kênh thông tin gây ra, H(Y|X) còn đƣợc gọi là entropy gây nhiễu hay còn gọi là sai số trung bình bởi vì nó cho biết độ bất định (sai số) của đầu ra khi đầu vào đã biết. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 13                           N i M j ijji ij N i M j iji M j ijiji N i ii xypyxpXYH xypxypxpXYH xypxypxXYH xXYHxpXYH 1 1 1 1 1 2 1 )|(log),( )|(log)|()( )|(log)|( | Nếu trên kênh không có nhiễu thì p(xi|yj) = 1 và p(yj|xi) = 1 do đó: H(X|Y) = H(Y|X) = 0 Nếu nhiễu trên kênh đủ lớn để đầu vào và đầu ra kênh độc lập với nhau tức là p(xi|yj) = p(xi) và p(yj|xi) = p(yj) thì: H(X|Y) = H(X) H(Y|X) = H(Y) Cuối cùng, để xác định các entropy có điều kiện, cần phải biết các xác suất có điều kiện dựa vào công thức xác suất hậu nghiệm (Bayes)                                  MNNN M M yxpyxpyxp yxpyxpyxp yxpyxpyxp YXP |...|| ............ |...|| |...|| | 21 22212 12111                                  nmnn m m xypxypxyp xypxypxyp xypxypxyp XYP |...|| ............ |...|| |...|| | 21 22221 11211 Ma trận P(Y|X) gọi là ma trận kênh truyền Gọi A = [P(Y|X)] là ma trận truyền tin hay mô hình truyền tin của kênh truyền rời rạc không nhớ. Và pij = p(Y=yj/X=xi) = p(yj/xi) là xác suất nhận đƣợc lớp tin yj khi đã truyền giá trị xi.  Phân phối đầu nhận             M i iji M i ijijj pxpxypxpypyYp 11 .|. Hay    Axpyp ij )].([ , Ví dụ: Cho ma trận truyền tin nhƣ sau. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 14            5.03.02.0 2.05.03.0 3.02.05.0 A , p(x1)=0.5; p(x2)=p(x3)=0.25 Khi đó ta tính đƣợc P(Y) nhƣ sau:   jyp [p(x1) p(x2) p(x3)].           5.03.02.0 2.05.03.0 3.02.05.0 = [ 0.375 0.3 0.325] Hay p(y1) = 0.375, p(y2) = 0.3, p(y3) = 0.325 Tính chất của Entropy có điều kiện: 1. H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) 2. Nếu không có nhiễu trên kênh, giữa đầu vào và đầu ra có quan hệ một – một, sai số trung bình bằng không khi đó H(X,Y) = H(X) = H(Y) 3. H(X) ≥ H(X|Y); H(Y) ≥ H(Y|X). Dấu bằng xảy ra khi X, Y độc lập thống kê với nhau. Điều này có nghĩa là độ bất định trung bình của một tin bất kỳ bao giờ cũng lớn hơn độ bất định trung bình của tin đó khi đã biết một tin bất kỳ khác có liên hệ thống kê với nhau. 2.3.4 Quan hệ giữa lƣợng tin tƣơng hỗ trung bình và entropy. Ở chƣơng 1 ta đã tính đƣợc I(xi,yj). Thông thƣờng ở bên phát phát đi một tập tin X = {xi}, Y = {yj}. Do đó ta không quan tâm tới một tin cụ thể xi mà ch quan tâm tới lƣợng thông tin trung bình về mỗi tin của tập X do mỗi tin của tập Y mang lại. I(X,Y) = )( )/( log),( i ji N M ji xp yxp yxp Lƣợng tin tƣơng hỗ trung bình bằng tổng độ bất định trung bình về tin phát và tin thu trừ độ bất định trung bình về sự xuất hiện đồng thời của chúng (SV tự chứng minh) I(X,Y) = H(X) – H(X|Y) = H(Y) – H(Y|X) I(X,Y) = H(X) + H(Y) – H(X,Y) Tính chất của I(X,Y)  I(X,Y) ≥ 0 Ta đã chứng minh H(X) ≥ H(X|Y) §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 15 Mà I(X,Y) = H(X) – H(X|Y)  ĐPCM và đẳng thức xảy ra khi H(X) = H(X|Y) tức kênh bị đứt.  I(X,Y)  H(X) và đẳng thức xảy ra khi kênh không có nhiễu  I(X,X) = H(X)  I(X,Y)=I(Y,X) Giản đồ Venn mô tả quan hệ I và H 2.3.5 Các dạng kênh truyền 2.3.5.1 Kênh truyền không mất thông tin (Lossless Channel) Đầu ra xác định duy nhất một đầu vào Đặc trƣng: H(X|Y)=0; Lƣợng tin chƣa biết về X khi nhận Y là bằng 0, tức là khi nhận đƣợc Y thì hoàn toàn nhận đƣợc X Dung lƣợng: C = maxI(X,Y) = max(H(X)) = log2 N 2.3.5.2 Kênh đơn định (Deterministic channel) Đầu vào xác định duy nhất đầu ra - Đặc trƣng: H(Y|X)=0; Lƣợng tin chƣa biết về Y khi truyền X bằng 0 hay truyền X thì sẽ nhận đƣợc Y - Dung lƣợng: C = max I(X,Y) =max H(Y) = log2 M 2.3.5.3 Kênh truyền không nhiễu Kết hợp của kênh truyền xác định và kênh truyền không mất thông tin Truyền ký tự nào thì nhận đƣợc ký tự đấy H(Y|X) = H(X|Y) = 0, C = log2 M 2.3.5.4 Kênh vô dụng (Useless Channel) Mô hình: Khi truyền giá trị nào thì mất giá trị đó hoặc xác suất nhiễu thông tin trên kênh truyền lớn hơn xác suất nhận đƣợc Đặc điểm: o Kênh truyền vô dụng nếu và ch nếu X và Y độc lập với mọi sự phân bố của nguồn phát o H(Y|X) và H(X|Y) đạt cực đại và C = 0 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 16 2.3.5.5 Kênh truyền đối xứng Đặc điểm: Ma trận kênh truyền có tính chất đối xứng. Tức các tham số ở hai bên đƣờng chéo của ma trận bằng nhau VD:            312161 216131 613121 A Khi ma trận kênh truyền là đối xứng thì H(Y/X) là không đổi là bằng entropy của một hàng của ma trận kênh truyền 2.3.6Lƣợc đồ giải mã tối ƣu Khi truyền xi nhận đƣợc yj. Đầu thu cần phải giải mã yj về xi tƣơng ứng Yêu cầu: Tìm giải pháp tạo mã sao cho sai số giải mã nhỏ hơn ε bất kỳ đồng thời phải duy trì R <= C Các dạng sai số: - Xác suất truyền sai từ mã xi:      iiji xXByYpxeP || - Xác suất truyền sai trung bình:         M i ii xepxXPeP 1 | - Xác suất truyền sai lớn nhất:     Miim xePeP ,1 |max   Giải thuật: Bƣớc 0: Khởi tạo các B i = φ (∀ i) Bƣớc lặp: xét với mọi Yy j  + Tính: p(w 1 ).p(y j /w 1 ) p(w 2 ).p(y j /w 2 ) p(w M ).p(y j /w M ) + So sánh các giá trị tính trên và chọn giá trị w* i sao cho p(w* i ).p(y j /w* i )= Max + B i = B i + {y j } và g(y j ) = w* i . §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 17 Ví dụ: Cho ma trận truyền tin            312161 216131 613121 A , P(x1)=1/2; P(x2)=P(x3)=1/4 Yêu cầu: Xây dựng lƣợc đồ giải mã tối ƣu, tính các xác xuất truyền sai? Khởi tạo B1={}, B2={}, B3={} * Khi nhận đƣợc y1. p(x1).p(y1|x1)=1/4  max Liệt kê y1 vào B1 tƣơng ứng với x1 p(x2).p(y1|x2)=1/12 p(x3).p(y1|x3)=1/24 Quá trình tƣơng tự khi nhận đƣợc y2, y3. Kết quả ta có lƣợc đồ giải mã sau; * Tính các xác suất truyền sai: - Xác suất truyền sai từ mã x1:       6/1||| 13111  xypxXByYpxep j - Xác suất truyền sai từ mã x2:   21| 2 xep - Xác suất truyền sai từ mã x3:   1| 2 xep Xác suất truyền sai trung bình: p(e)=11/24 Xác suất truyền sai lớn nhất: pm(e) = 1 2.4 Entropy của nguồn liên tục. Ta biết rằng nguồn liên tục cũng đƣợc coi nhƣ một tập các thể hiện của một quá trình ngẫu nhiên. Nguồn tin X là nguồn tin liên tục với các thể hiện x(t) có quy luật phân bố xác suất (mật độ phân bố xác suất pdf) đƣợc biểu diễn theo hàm fx(x), entropy riêng của nguồn tin X đƣợc xác định bằng: H(X) = -    dxxpxp )(log)( 2.5 Vấn đề phối hợp nguồn kênh. Shannon đã phát biểu hai định lý cơ bản của lý thuyết tin tức liên quan tới sự phối hợp giữa nguồn tin và kênh thông tin. Shannon khẳng định sự tồn tại của các loại mã tối ƣu làm giảm độ dƣ của nguồn và sửa sai chống lại các tác động của nhiễu. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 18  Định lý Shannon 1: Giả sử nguồn tin có entropi H (bít/ký hiệu), và kênh có thông lƣợng C (bít/s), có thể mã hóa tin tức ở đầu ra của nguồn làm cho sự truyền tin trong kênh không nhiễu theo một tốc độ trung bình C/H – ε (ký hiệu/s) với ε bé tùy ý, và không thể truyền nhanh hơn C/H.  Định lý Shannon 2: Kênh có thông lƣợng C (bít/s), tốc độ lập tin của nguồn là R (bít/s) o Nếu R<C: Có thể tìm đƣợc một phƣơng pháp mã hóa để cho sự truyền tin tỏng kênh có nhiễu với sai bé tùy ý. o Nếu R>C: Có thể mã hóa nguồn để cho lƣợng sai bé hơn R – C + ε, với ε bé tùy ý, không tồn tại mã hiệu đảm bảo độ sai cảu sự truyền tin nhỏ hơn R – C. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 19 CHƢƠNG 3: M HIỆU 3.1 Khái niệm và định nghĩa. Trong các hệ thống truyền tin rời rạc hoặc truyền các tín hiệu liên tục nhƣng đã đƣợc rời rạc hóa, bản tin thƣờng phải thông qua một số phép biến đổi: biến đổi tƣơng tự sang số, mã hóa ở phía phát, còn ở đầu thu phải thông qua quá trình biến đổi ngƣợc lại là giải mã. Sự mã hóa thông tin cho phép chúng ta ký hiệu hóa thông tin hay sử dụng các ký hiệu quy ƣớc để biểu diễn bản tin. Chính nhờ mã hóa, chúng ta có thể hiển thị đƣợc thông tin có bản chất là các khái niệm. Vai trò của mã hóa: - Tăng tính hữu hiệu: Tăng tốc độ truyền tin  Mã thống kê tối ƣu - Tăng độ tin cậy của hệ thống: Tăng khả năng chống nhiễu  Mã phát hiện và sửa sai. 3.1.1 Các khái niệm: - Mã hiệu (Code): Tập hữu hạn các dấu hiệu riêng (symbol) và các phép ánh xạ các tin hoặc bản tin của nguồn tin thành các ký hiệu tƣơng ứng. Tập các ký hiệu này phải thỏa mãn một số yêu cầu của hệ thống truyền tin đặt ra (Tốc độ truyền hay độ chính xác)  Mã hiệu là tập hữu hạn các ký tự (Symbol) hay bảng chữ riêng (dấu mã – ký hiệu mã). Số các ký hiệu gọi là cơ số mã m (Ví dụ m = 2  mã nhị phân). - Mã hóa (Encoding): Quá trình dùng các ký hiệu mã để biểu diễn các tin của nguồn, biến nguồn tin thành mã hiệu hay biến đổi nguồn tin theo đặc tính thống kê theo yêu cầu. Ngƣợc với quá trình mã hóa là quá trình giải mã (decoding). - Từ mã (Code Word): Chuỗi các ký hiệu mã biểu diễn cho tin của nguồn. Tập tất cả các từ mã tƣơng ứng với các tin của nguồn đƣợc gọi là bộ mã. Nguồn tin tƣơng ứng với bộ mã. Ký hiệu của từ mã là u,v hoặc w 3.1.2 Các thông số cơ bản của một bộ mã: - Chiều dài từ mã: Số ký hiệu có trong từ mã. Ký hiệu: l (hoặc n) - Chiều dài trung bình của bộ mã:    N i ii lxPl 1 ).( §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 20 Trong đó: - N: Số tin của nguồn - li: Chiều dài từ mã tƣơng ứng với tin xi của nguồn - p(xi): Xác suất xuất hiện tin xi của nguồn - Nếu tất cả các từ mã trong bộ mã có chiều dài từ mã li = l thì bộ mã đƣợc gọi là bộ mã đều, còn nếu li  l thì gọi là bộ mã không đều. (Mã đều: Tất cả các từ mã có độ dài bằng nhau) - Khi bộ mã có tất cả các tổ hợp là mã của các lớp tin tƣơng ứng, ta gọi là bộ mã đầy. (Mã đầy: Là mã đều và N = ml. (l: Chiều dài từ mã đều)) - Khi bộ mã tồn tại ít nhất một tổ hợp không là mã của một lớp tin nào, ta gọ i là bộ mã không đầy – bộ mã vơi. (Mã vơi: Là mã đều và N < ml) Ví dụ: A = {0,1} là bảng ký hiệu mã. Bộ mã: X1 = {0, 10, 11}  mã không đều  Có khả năng trở thành mã tối ƣu. X2 = {00, 10, 11}  Mã đều nhƣng là mã vơi . X3 = {00, 10, 11, 01}  Mã đều và đầy  có khả năng chống nhiễu. 3.2 Các phƣơng pháp biểu diễn mã 3.2.1 Các bảng mã a. Bảng đối chiếu mã: Liệt kê các tin của nguồn và từ mã tƣơng ứng trong một bảng Ví dụ: Lớp tin a1 a2 a3 a4 a5 a6 Từ mã 00 010 011 10 110 111 b. Mặt tọa độ mã: Dựa trên hai thông số chính của một từ mã là trọng số bi và độ dài li, ta lập một bề mặt có hai tọa độ (l,b), trên đó mỗi từ mã đƣợc biểu diễn bằng một điểm duy nhất, theo định lý sau: Định lý: Không có hai từ mã mã hóa hai tin khác nhau của cùng một bộ mã thỏa mãn đồng thời li = lj và bi = bj Từ mã w=a0a1a2 ... al-1. Với ai là các ký tự thứ i tính từ trái sang thuộc tập A. w đƣợc biểu diễn bằng 1 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 21 điểm (l,b) trong mặt phẳng tọa độ 2 chiều. Trong đó l là chiều dài từ mã, b là trọng số     1 0 l i i imab với m là cơ số mã Ví dụ : Tin a1 a2 a3 a4 a5 a6 Từ mã 00 010 011 10 110 111 Chiều dài l 2 3 3 2 3 3 Trọng số b 0 2 6 1 3 7 3.2.2 Đồ hình mã Các phƣơng pháp đồ hình sử dụng một đồ hình để biểu diễn một mã hiệu. Nó cho phép trình bày mã một cách gọn hơn các bảng mã, đồng thời cho thấy r các tính chất quan trọng của mã hiệu một cách trực quan hơn. Các phƣơng pháp biểu diễn mã hiệu bằng đồ hình gồm có cây mã và đồ hình kết cấu mã. a. Biểu diễn cây mã: Là cách biểu diễn gồm các nút và nhánh cây. Gốc cây gọi là nút gốc. Từ mỗi nút phân đi hai nhánh tƣơng ứng với chữ mã 0, 1. Nút cuối không có nhánh nào đại diện cho một từ mã mà thứ tự đƣợc xác định bằng cách lấy các ký hiệu từ nút gốc đi qua các nút trung gian đến nút cuối. R ràng có thể có những nút cuối mà không có nhánh nào đi ra từ nó, và cũng có thể có những nút cuối của từ mã này là nút trung gian của từ mã khác. Mã hiệu có nút cuối trùng với một nút trung gian của từ mã khác sẽ có đặc điểm là từ mã ngắn hơn là phần đầu của từ mã dài hơn và nó không cho phép phân tách một chuỗi mã bất kỳ thành một dãy duy nhất các từ mã. Nhìn vào cây mã ta có thể biết các tính chất đặc trƣng của bộ mã nhƣ mã đầy, mã đều Tuy nhiên cách biểu diễn này khá cồng kềnh khi bộ mã có từ mã dài, và cũng không xác định đƣợc tính thiết lập từ mã của việc mã hóa. Mã có cơ số m thì cây mã tƣơng ứng sẽ là cây m phân. b. Đồ hình kết cấu mã Là một dạng rút gọn của cây mã, trong đó các nút §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 22 lá trùng với nút gốc và ngoài ra mỗi cạnh của đồ hình kết cấu mã đều là cạnh có hƣớng. Vì vậy một từ mã đƣợc biểu diễn bằng một vòng kín xuất phát từ nút gốc theo các nhánh có hƣớng (chiều mũi tên) qua các nút trung gian và quay trở về lại nút gốc. Mỗi nhánh đại diện cho một trị của ký hiệu mã. 3.2.3 Hàm cấu trúc mã Là cách biểu diễn sự phân bố các từ mã theo độ dài của chúng. Phƣơng pháp này biểu diễn bằng một hàm G(li) cho biết có bao nhiêu từ mã có chiều dài li. Ví dụ: Bộ mã X1 = {00, 01, 100, 1010, 1011} có hàm G(li) dƣới dạng sau: G(li) = 2, khi li = 2 G(li) = 1, khi li = 3 G(li) = 2, khi li = 4 3.3 Điều kiện phân tách của mã hiệu. Trong mục này chúng ta sẽ xem xét các tiêu chuẩn đƣợc sử dụng để đánh giá một mã hiệu có thỏa mãn điều kiện thiết lập mã hay không. 3.3.1 Điều kiện chung đối với một bảng mã phân tách đƣợc. Điều kiện: Để một bộ mã là phân tách đƣợc thì trong bộ mã không tồn tại một từ mã trùng với dãy từ mã khác của bộ mã. Ví dụ: Xét bộ mã X1 ={0, 10, 11} mã hóa cho nguồn tin A = {a,b,c} Bên phát: tin x = abaac  chuỗi từ mã tƣơng ứng phát đi là 0100011. Bên nhận: Giả thiết kênh truyền không nhiễu thu đƣợc chuỗi 0100011. Thực hiện tách mã thành từ mã duy nhất 0 10 0 0 11 tƣơng ứng với abaac. Vậy X1 là bộ mã phân tách đƣợc Xét bộ mã X2 = {0, 10, 01} mã hóa cho nguồn A trên. Nếu bên nhận Y = 01010 thì ta có thể tách thành 0 10 10 hoặc 01 01 0 hoặc 01 0 10  Không biết chính xác bên phát đã truyền đi từ mã nào  X2 không phân tách đƣợc Prefix của một từ mã là một bộ phận của từ mã sau khi đã bỏ đi một hay nhiều ký hiệu cuối. Khái niệm mã Prefix: là bộ mã không có từ mã nào là tiếp đầu của từ mã khác, nói cách khác bộ mã có tính prefix là bộ mã không có một từ mã ngắn hơn nào lại là phần đầu của từ mã dài hơn nó. Những bộ mã có tính Prefix là bộ mã tách đƣợc. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 23 3.3.2 Bảng thử mã. Giải thuật: B1: Đem các từ mã xếp thành một cột, theo thứ tự chiều dài của từ mã từ nhỏ đến lớn, đánh dấu là cột 1. B2: Trong cột này, đối chiếu các từ mã ngắn với các từ mã dài hơn, nếu từ mã ngắn là tiếp đầu ngữ của từ mã dài thì ghi tiếp vị ngữ vào cột tiếp theo và đánh dấu là cột 2. B3: Tiếp tục, đối chiếu các chuỗi trong cột 1 và cột 2 với nhau, nếu có chuỗi nào trong cột này là tiếp đầu ngữ của chuỗi trong cột kia thì tiếp vị ngữ sẽ đƣợc ghi vào cột tiếp theo là cột 3. B4 Tiếp tục theo khuôn mẫu này nếu đang xét cột thứ j thì đối chiếu các chuỗi trong cột này với cột 1. Nếu có chuỗi nào trong cột này là tiếp đầu ngữ của chuỗi trong cột kia thì tiếp vĩ ngữ sẽ đƣợc ghi vào cột j + 1. Thực hiện cho đến khi không thể điền thêm đƣợc nữa hoặc cột mới thêm vào trùng với một cột trƣớc đó hoặc có một chuỗi trong cột mới trùng với một từ mã. Điều kiện cần và đủ để một bộ mã phân tách đƣợc là không có phần tử nào trong các cột từ j ≥ 2 trùng với một phần tử trong cột 1. Ví dụ: Lập bảng thử mã cho bộ mã A = {00, 01, 011, 1100, 00010}. Cột 5 xuất hiện từ mã 00 trùng với từ mã ở cột 1. Vậy bộ mã A là mã không phân tách đƣợc. Bài tập: Hãy lập bảng thử mã cho những bộ mã sau. Cho biết mã có phân tách đƣợc không,. � X1 = {00, 01, 100, 1010, 1011} � X2 = {00, 01, 101, 1010} � X3 = {00, 01, 110, 111, 1100} � X4 = {00, 01, 110, 111, 1110} §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 24 � X5 = {00, 01, 110, 111, 0111} � X6 = {00, 01, 110, 111, 1011, 1101} � X7 = {01, 10, 011, 100} 3.3.3 Bất đẳng thức Kraft Cho l1, l2, ..., lK là các chiều dài của một bộ mã prefix có bảng kí hiệu mã kích thƣớc m (tức gồm m kí hiệu mã). Thì: 1 1    K i lim Ngƣợc lại, nếu các số nguyên l1, l2, ..., lK thoã bất đẳng thức trên thì tồn tại một bộ mã prefix với các từ mã có chiều dài là l1, l2, ..., lK. Định lý: Một bộ mã phân tách đƣợc thì có các chiều dài từ mã thoã mãn bất đẳng thức Kraft. Độ chậm giải mã: là số ký hiệu cần phải nhận đƣợc đủ để có thể phân tách (nhận dạng) đƣợc từ mã. Độ chậm giải mã của mã prefix bằng độ dài của từ mã dài nhất. Ví dụ: Bộ mã X1 = {x1, x2, x3} với K = 3, l1=1, l2 = 2, l3 = 3, m =2. Ta có: 1 8 7 2 3 1    i li  Bộ mã X1 là bộ mã phân tách đƣợc. Bộ mã X2 = {x1, x2, x3}, l1=l2=1; l3=2, m=2 Ta có: 125.12 3 1    i li  bộ mã không phân tách đƣợc. 3.3.4 Thủ tục tạo mã phân tách đƣợc dựa vào độ dài đã biết của các từ mã Xét N={n1, n2, ,nM} và cơ số sinh mã là m: Bƣớc 1: Ta xếp thứ tự n1≤ n2 ≤ ≤ nL, xây dựng cây bậc m cỡ lN và sinh mã cho các nút. Bƣớc 2: Chọn nút bất kỳ trên cây có độ dài l1 gán cho từ mã w1 và xóa tất cả các nút kề sau nó. Bƣớc 3: Lặp lại các bƣớc 2 đối với việc chọn các từ mã còn lại w2,,wN ứng với l2, lN. Bảng mã W={w1,w2,,wM} là bảng mã tức thời. Ví dụ 1: Xét bảng mã thỏa M=3, m=2, l 1 =1, l 2 =2, l 3 =3. Vậy ta kiểm tra xem có tạo đƣợc bảng mã tức thời hay không §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 25 Bài tập: 1. Tìm bộ mã tức thời cho các bộ mã có các từ mã với chiều dài tƣơng ứng sau: {2,2,3,4,4}, {2,2,3,3,3,4,4}, {2,2,3,4,4,4,5,5} 2. Có tồn tại bộ mã có khả năng tách đƣợc có độ độ dài từ mã là {1,2,2,3,4} với cơ số 3 {0,1,2} 3.4 Mã hệ thống. 3.4.1 Mã hệ thống tổng quát. - Mã hệ thống là một loại mã mà mỗi từ mã đƣợc xây dựng bằng cách liên kết một số từ mã của bộ mã gốc. Vì bộ mã gốc có tính phân tách nên bộ mã hệ thống cũng có tính phân tách. Nếu bộ mã gốc có tính prefix thì bộ mã hệ thống cũng có thính prefix - Tổ hợp sơ đẳng: Sử dụng một số từ mã của bộ mã gốc làm các tổ hợp tạo thành phần đầu của từ mã hệ thống - Biểu diễn mã hệ thống: có thể sử dụng các phƣơng pháp biểu diễn mã bất kỳ. Thông thƣờng sử dụng phƣơng pháp đồ hình - Giải mã đối với từ mã hệ thống thông qua hai bƣớc: Tách chuỗi ký hiệu mã nhận đƣợc thành chuỗi các tổ hợp sơ đẳng và các tổ hợp cuối; Tìm các tổ hợp cuối và xác định điểm kết thúc từ mã tại đây. - Phƣơng pháp giải mã hệ thống bằng đồ hình kết cấu thực hiện nhƣ sau: xuất phát từ nút gốc theo đƣờng mũi tên của các nhánh một cách tuần tự, mỗi khi quay về gốc là kết thúc một tổ hợp sơ đẳng, và khi vào đƣờng cụt là kết thúc tổ hợp cuối cùng, đồng thời kết thúc từ mã hệ thống. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 26 3.4.2 Mã hệ thống có tính prefi . Mã hệ thống có tính prefix đƣợc xây dựng từ một bộ mã gốc có tính prefix bằng cách lấy một số từ mã của mã prefix gốc làm tổ hợp sơ đẳng và các từ mã còn lại làm tổ hợp cuối. Ghép các tổ hợp sơ đẳng với nhau và nối một trong các tổ hợp cuối vào thành từ mã của mã mới gọi là mã hệ thống có tính prefix. Ví dụ: Lấy bộ mã prefix 1,00, 010, 011 làm gốc, trong đó các tổ hợp: 1, 00, 010 là tổ hợp sơ đẳng còn 011 là tổ hợp cuối. Các từ mã đƣợc hình thành nhƣ sau đều có thể là từ mã của mã hệ thống: 1011, 11011, 00011, 100011, 01011, 01001011011. Khi giải mã phải qua hai bƣớc. Bƣớc thứ nhất từ dãy ký hiệu nhận đƣợc phân tách thành giải các tổ hợp sơ đẳng và tổ hợp cuối, sau đó giải thành dãy các tổ hợp của mã hệ thống. Vẫn lấy ví dụ trên khi nhận tin dƣới dạng dãy ký hiệu mã: 010011 010011 100011 01001011011 1011 11011 1011 Bƣớc thứ nhất tách thành dãy: 010-011-010-1-00-011-010-010-1-1-011-1-011-1-1-011-1-011 Bƣớc thứ hai phân tách thành dãy tổ hợp mã hệ thống: 010011-010011-100011-01001011011-1011-11011-1011. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 27 CHƢƠNG 4: M HÓA NGU N Hệ thống truyền tin đƣợc sử dụng để truyền thông tin từ nguồn tin tới nơi nhận tin. Nguồn thông tin có thể có nhiều dạng là nguồn tƣơng tự hoặc nguồn rời rạc. Với sự phát triển của kỹ thuật số, hệ thống truyền tin sử dụng kỹ thuật số có thể dùng để truyền thông tin từ nguồn tƣơng tự hay rời rạc dƣới dạng số. Nhƣ vậy, đầu ra của nguồn phải chuyển thành dạng có thể chuyển đi bằng kỹ thuật số và quá trình này gọi là mã hóa nguồn. 4.1 Mô hình toán học của nguồn thông tin. 4.1.1 Định lý giới hạn dƣới về độ dài trung bình của các từ mã. Định lý Shannon (1948) về giới hạn dƣới của chiều dài trung bình từ mã Cho nguồn tin X = {a1, a2, ...aK} với các xác suất xuất hiện tƣơng ứng là {p1, p2, ..., pK}. Một bộ mã phân tách đƣợc bất kỳ cho nguồn này với cơ số mã m, chiều dài trung bình từ mã thỏa mãn: m XH l log )(  với         K i ii lxpl 1 )( , H(X): Entropi của nguồn Dấu bằng xảy ra khi p(xi) = m -li hay     K i lim 1 1 Ý nghĩa: - Mã tách đƣợc có độ dài trung bình của mã có cận dƣới là m XH log )( . - Mã không tách đƣợc có độ dài trung bình có thể nhỏ hơn cận dƣới - Mã tách đƣợc, không tối ƣu có độ dài trung bình từ mã lớn hơn nhiều so với cận dƣới - Mã tách đƣợc tối ƣu có chiều dài trung bình từ mã gần với cận dƣới Chứng minh định lý: Xét      K i K i iiii mlxpxpxpmlXH 1 1 log)()(log)(log)( =     K i li ii mxpxp 1 log)(log)( =       K i i lK i i l xp m xip xp m xip ii 11 )1 )( )(( )( log)( = 1 1    K i lim <1-1=0 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 28 Hiệu suất lập mã: %100. )( l XH h  4.1.2 Định lý giới hạn trên về độ dài trung bình của các từ mã. Có thể xây dựng đƣợc một bộ mã thỏa mãn tính chất tối ƣu khi chiều dài trung bình của từ mã nằm trong khoảng H(x) H(x)+1 1)()(  xHlxH Cách nhận biết bảng mã tối ƣu - Xác suất pi càng lớn thì độ dài li càng nhỏ - Trong các từ mã có độ dài bằng nhau và cùng bằng lK lớn nhất. Tồn tại ít nhất 2 từ mã có K-1 ký tự đầu giống nhau và khác nhau ở ký tự thứ K 4.2 Mã hóa nguồn rời rạc. 4.2.1 Phƣơng pháp mã hóa Shannon Nguyên lý: Dựa trên cơ sở độ dài từ mã tỷ lệ với xác suất xuất hiện Giải thuật: B1: Sắp xếp theo thứ tự giảm dần: Kppp  ...21 B2: Định nghĩa q1=0;   Kixpq i j ji ...2,1 1 1    B3: Đổi qi sang cơ số 2 (m)  Chuỗi ký tự (chuỗi nhị phân) B4: Từ mã đƣợc gán cho ai là li ký hiệu lấy từ vị trí sau dấu phẩy của chuỗi nhị phân tƣơng ứng với qi. Trong đó iii plp 22 log1log  Ví dụ: Lập mã tối ƣu mã hóa nguồn S = {a1, a2, a3,a4, a5, a6} với các xác suất {0.3, 0.25, 0.2, 0.12, 0.08, 0.05} H = 2.36, l = 2,75, h = 2,36/2,75 = 85,82% §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 29 Nhận xét: - Kết quả cho mã Prefix - Có thể mở rộng cho m>2 Bài tập: Hãy mã hoá các nguồn sau bằng phƣơng pháp Shannon. Tính entropy của nguồn, chiều dài trung bình và hiệu suất của phép mã hóa. � S1 = {a1, a2, a3, a4, a5, a6} với các xác suất lần lƣợt là 0,25; 0,21; 0,19; 0,16; 0,14; 0,05. � S2 = {a1, a2, a3, a4, a5, a6 , a7, a8} với các xác suất lần lƣợt là 0,21; 0,18; 0,15; 0,14; 0,12; 0,01; 0,06 ; 0,04. � S3 = {a1, a2, a3, a4, a5, a6 , a7, a8 , a9} với các xác suất lần lƣợt là 0,25; 0,19; 0,15; 0,11; 0,09; 0,07; 0,06; 0,04; 0,04. 4.2.2 Phƣơng pháp mã hóa Fano Giải thuật: B1. Sắp xếp các xác suất theo thứ tự giảm dần. Không mất tổng quát giả sử p1 ≥ ... ≥ pK. B2. Phân các xác suất thành 2 nhóm có tổng xác suất gần bằng nhau nhất. B3. Gán cho hai nhóm lần lƣợt các kí hiệu 0 và 1 (hoặc ngƣợc lại). B4. Lặp lại bƣớc 2 cho các nhóm con cho đến khi không thể tiếp tục đƣợc nữa. B5. Từ mã ứng với mỗi tin là chuỗi bao gồm các kí hiệu theo thứ tự lần lƣợt đƣợc gán cho các nhóm có chứa xác suất tƣơng ứng của tin. Ví dụ: Hãy mã hoá nguồn S = {a1, a2, a3, a4, a5, a6} với các xác suất lần lƣợt là 0,3; 0,25; 0,2; 0,12; 0,08; 0,05. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 30 H = 2.36, l = 2,38, h = 2,36/2,38 = 99,17% Chú ý, trong nhiều trƣờng hợp có nhiều hơn một cách chia thành các nhóm có tổng xác suất gần bằng nhau, ứng với mỗi cách chia có thể sẽ cho ra các bộ mã có chiều dài trung bình khác nhau. Ví dụ: Hãy mã hoá nguồn S = {a1, a2, a3, a4, a5, a6, a7, a8} với các xác suất lần lƣợt là 0,23; 0,2; 0,14; 0,12; 0,1; 0,09; 0,06; 0,06. 88.2l 89.2l Nhận ét: Phƣơng pháp Fano thƣờng cho kết quả tốt hơn Shannon Bài tập: Hãy mã hoá các nguồn sau bằng phƣơng pháp Fano. Tính hiệu suất của phép mã hóa. � S1 = {a1, a2, a3, a4, a5, a6} với các xác suất lần lƣợt là 0,25;0,21; 0,19; 0,16; 0,14; 0,05. � S2 = {a1, a2, a3, a4, a5, a6 , a7, a8} với các xác suất lần lƣợt là 0,21; 0,18; 0,15; 0,14; 0,12; 0,1; 0,06 ; 0,04. � S3 = {a1, a2, a3, a4, a5, a6 , a7, a8 , a9} với các xác suất lần lƣợt là 0,25; 0,19; 0,15; 0,11; 0,09; 0,07; 0,06; 0,04; 0,04. 4.2.3 Phƣơng pháp mã hóa Huffman Năm 1952 đã đƣa ra một thuật toán mã hóa dựa trên xác suất xuất hiện của các ký hiệu. Thuật toán tối ƣu theo nghĩa số ký hiệu nhị phân trung bình để mã hóa cho một ký hiệu của nguồn là cực tiểu. Phƣơng pháp mã hóa này cho một bộ mã có tính prefix và tất nhiên quá trình giải mã là duy nhất. Giải thuật: B1: Sắp xếp các ký hiệu theo thứ tự giảm dần của xác suất. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 31 B2: Mã hóa hai ký hiệu có xác suất xuất hiện nhỏ nhất. Hai ký hiệu đƣợc hợp lại với nhau, hai nhánh đƣợc gán cho một trong hai ký hiệu 0 hoặc 1. B3: Nút của hai nhánh đƣợc coi là một ký hiệu mới có xác suất xuất hiện bằng tổng hai xác suất của hai ký hiệu tạo ra nó. B4: Lặp lại bƣớc 2 cho tới khi ch còn một ký hiệu với xác suất xuất xuất hiện bằng 1. B5: Từ mã là tổ hợp các ký hiệu mã ở các nhánh của cây mã tính từ gốc. Ví dụ: Hãy mã hoá nguồn S = {a1, a2, a3, a4, a5, a6} với các xác suất lần lƣợt là 0,3; 0,25; 0,2; 0,12; 0,08; 0,05. 0.3 0.25 0.2 0.12 0.08 0.05 1 0 0 1 1 0 1 1 0 0.13 0.25 0.45 0.55 1 0 Ký hiệu Xác suất Từ mã a1 0.3 00 a2 0.25 01 a3 0.2 10 a4 0.12 111 a5 0.08 1100 a6 0.05 1101 � H = 2.36, l= 2,38, h = 2,36/2,38 = 99,17% Mở rộng với cơ số m > 2 Chúng ta sẽ bổ sung vào một số tin “phụ” có xác suất bằng 0 sao cho tổng số tin của nguồn bằng với m + n(m – 1) Sau đó thủ tục mã hoá trên đƣợc điều ch nh nhƣ sau B1. Sắp xếp các xác suất theo thứ tự giảm dần chẳng hạn p1 ≥ ... ≥ pK B2. Gán lần lƣợt các kí hiệu 0, 1, ..., m – 1 tới các bit cuối của m từ mã có xác suất nhỏ nhất B3. Kết hợp m xác suất nhỏ nhất lại thành một và tạo với K – m xác suất còn lại thành một tập mới. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 32 B4. Lặp lại các bƣớc trên cho tập mới này. Ví dụ: Hãy mã hoá nguồn S = {a1, a2, a3, a4, a5, a6} với các xác suất lần lƣợt là 0,3; 0,25; 0,2; 0,12; 0,08; 0,05 với m = 3. H = 1.49, l= 1,58, h = 1,49/1,58 = 94,24% Bài tập : Hãy mã hoá các nguồn sau bằng phƣơng pháp Huffman theo các cơ số m = 2 và m = 3. Tính hiệu suất của phép mã hóa trong mỗi trƣờng hợp. � S1 = {a1, a2, a3, a4, a5, a6} với các xác suất lần lƣợt là 0,25; 0,21; 0,19; 0,16; 0,14; 0,05. � S2 = {a1, a2, a3, a4, a5, a6 , a7, a8} với các xác suất lần lƣợt là 0,23; 0,2; 0,14; 0,12; 0,1; 0,09; 0,06 ; 0,06. � S3 = {a1, a2, a3, a4, a5, a6 , a7, a8} với các xác suất lần lƣợt là 0,21; 0,18; 0,15; 0,14; 0,12; 0,01; 0,06 ; 0,04. � S4 = {a1, a2, a3, a4, a5, a6 , a7, a8 , a9} với các xác suất lần lƣợt là 0,25; 0,19; 0,15; 0,11; 0,09; 0,07; 0,06; 0,04; 0,04. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 33 CHƢƠNG 5: M HÓA KÊNH Các loại mã hóa kênh chủ yếu đó là mã khối (block code), mã chập (convolution code) và mã vòng (Xyclic code) 5.1 Mã khối tuyến tính (Block code) 5.1.1 Các khái niệm: Mã khối tuyến tính đƣợc mô tả bằng hai số nguyên n, k và một đa thức sinh hay ma trận sinh. Tham số k là số bít dữ liệu của bản tin nguồn, tham số n là tổng số bít của từ mã tại đầu ra của bộ mã hóa. Kênh truy n a k=4 n=7 Tính chất của mã khối tuyến tính là mỗi từ mã đƣợc xác định duy nhất từ một bản tin nguồn. Tỷ số R=k/n gọi là tỷ lệ mã. a. Không gian vector. Một tập gồm tất cả các khối n, Vn đƣợc gọi là một không gian vector trên trƣờng nhị phân có hai phần tử 0 và 1. Trƣờng nhị phân có hai phép cộng và nhân nhƣ sau: Phép cộng Phép nhân 0  0 = 0 0.0 = 0 0  1 = 1 0.1 = 0 1  0 = 1 1.0 = 0 1  1 = 0 1.1 = 1 Trọng số Hamming: Trọng số hamming của một dãy ký hiệu là số ký hiệu khác 0 của dãy. Ký hiệu w(v) Khoảng cách hamming: khoảng cách của hai dãy ký hiệu v1 và v2 có cùng chiều dài là số vị trí khác nhau của hai dãy. Ký hiệu d(v1,v2) Ví dụ: w(10110)=3 w(0111101)=5 d(10100,10001)=2 1011  1101 = 0110 Bổ đề: d(v1,v2)=w(v1  v2) d(v1,v2) + d(v2,v3) ≥ d(v1,v3) §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 34 w(v1) + w(v2) ≥ w(v1 v2) Khoảng cách Hamming của bộ mã: Xét bộ mã A là bộ mã đều, d(A) là khoảng cách Hamming của bộ mã là khoảng cách Hamming nhỏ nhất trong tất cả các khoảng cách giữa 2 từ mã bất kỳ của A Định lý: Một bộ mã nhị phân có khoảng cách Hamming d thì có thể: o Phát hiện sai đƣợc t bit nếu d ≥ t+1 o Sửa sai đƣợc t bit lỗi nếu d ≥ 2t+1 5.1.2 Ma trận sinh. Nếu k lớn, việc thực hiện tra bảng mã hóa sẽ gặp khó khăn. Ta có thể giảm độ phức tạp bằng việc có thể tạo ra các vector mã cần thiết. Vì tập các vector mã xác định mã khối tuyến tính là một không gian con k chiều thuộc không gian nhị phân n chiều, ta luôn tìm đƣợc một tập tuýp n ít hơn 2k có thể tạo ra tất cả 2 k các vector thành phần của không gian con. Việc tạo ra tập các vector đƣợc gọi là mở rộng không gian con. Tập độc lập tuyến tính nhỏ nhất mở rộng không gian con đƣợc gọi là cơ sở cả không gian con và số vector trong tập cơ sở này là kích thƣớc của không gian con. Bất kỳ tập cơ sở của k tuýp n độc lập tuyến tính g0, g1, ..., gk–1 có thể đƣợc sử dụng để tạo ra các vector mã khối tuyến tính yêu cầu, vì vector mã là một kết hợp tuyến tính của g0, g1, ..., gk–1. Nhƣ vậy, mỗi tập của các vector mã 2 k , v có thể mô tả: v = a0g0 + a1g1 + ... + ak–1gk–1 với ai = 0 hoặc bằng 1 là các bít bản tin cần mã hóa ( i = 0, ..., k-1). Tổng quát ta có thể định nghĩa ma trận sinh cấp k × n nhƣ sau Với gi = (gi0, gi1, , gi(n–1)), với i = 0, 1, , k–1. Các vector mã thƣờng đƣợc biểu diễn dƣới dạng vector hàng. Nhu vậy bản tin u là một chuỗi k bít là một vector hàng ( 1 hàng và k cột): u = (a0 a1 ak–1) Vector mã v, dƣới dạng ký hiệu ma trận là tích của u và G nhƣ sau: §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 35 v = u × G hay v = a0g0 + a1g1 + + ak–1gk–1 Vì các từ mã tƣơng ứng với các thông báo đƣợc sinh ra bởi G theo cách trên nên G đƣợc gọi là ma trận sinh của bộ mã. Ví dụ: Cho ma trận sinh của một mã tuyến tính C(7, 4) sau  Nếu u = (1101) là thông tin cần mã hoá thì từ mã tƣơng ứng là w = 1.g0 + 1.g1 + 0.g2 + 1.g3 = (1100101)  Bất kỳ k từ mã độc lập tuyến tính nào cũng có thể đƣợc dùng để làm ma trận sinh cho bộ mã.  Một bộ mã tuyến tính (hay còn gọi là không gian mã) có thể có nhiều ma trận sinh khác nhau cùng biểu diễn.  Mỗi ma trận sinh tƣơng ứng với một cách mã hóa khác nhau. Cách giải mã: u = (a0, a1, a2, a3) là bản tin nguồn, v = (b0, b1, b2, b3, b4, b5, b6) là từ mã tƣơng ứng. Chúng ta có hệ phƣơng trình sau liên hệ giữa u và v. v = u × G b0 = a0 + a1 + a3 (1) b1 = a0 + a2 (2) b2 = a1 + a3 (3) b3 = a0 + a1 (4) b4 = a1 (5) b5 = a2 (6) b6 = a2 + a3 (7) Chọn bốn phƣơng trình đơn giản nhất để giải các ai theo các bj. Chẳng hạn các phƣơng trình (4), (5), (6), (7) chúng ta giải đƣợc a0 = b3 + b4 a1 = b4 a2 = b5 a3 = b5 + b6 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 36 - Hệ phƣơng trình trên đƣợc gọi là hệ phƣơng trình giải mã. - Có thể có nhiều hệ phƣơng trình giải mã khác nhau nhƣng sẽ cho kết quả nhƣ nhau.  v = 1001011 ⇒ u = ?  v = 0101110 ⇒ u = ? 5.1.3 Mã khối tuyến tính hệ thống. Mã khối tuyến tính hệ thống (n,k) thực hiện việc ánh xạ từ một vector bản tin k bit tới một vector mã n bít sao cho trong số n bít này có k bít bản tin. Phần còn lại (n-k) bít là các bít kiểm tra. Một mã tuyến tính C(n, k) đƣợc gọi là mã tuyến tính hệ thống nếu mỗi từ mã có một trong hai dạng sau:  Dạng 1: Từ mã bao gồm phần thông tin k bit đi trƣớc và phần còn lại (gồm n – k bit) đi sau (phần này còn đƣợc gọi là phần dƣ thừa hay phần kiểm tra).  Dạng 2: Ngƣợc của dạng 1, từ mã bao gồm phần kiểm tra đi trƣớc và phần thông tin đi sau. Ma trận sinh của mã khối tuyến tính có dạng: Trong đó P là một phần tử mảng kiểm tra của ma trận sinh (hay còn gọi là ma trận quan hệ). Ikk: là ma trận đơn vị k x k (giá trị 1 nằm trên đƣờng chéo chính và các giá trị 0 ở vị trí còn lại) Chú ý rằng với mã hệ thống thì giảm độ phức tạp vì ta không cần phải lƣu trữ phần ma trận đồng nhất. Từ biểu thức v = u x G và ma trận sinh của mã khối tuyến tính, mỗi vector mã đƣợc biểu diễn nhƣ sau: v = [v0 v1 v2 vk-1] §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 37 = [a0 a1 a2 ak-1].                    1...00...... ........................... ........................... 0...10...... 0...01...... )(21 )(22221 )(11211 knkkk kn kn ppp ppp ppp Ở đây: v = a0 p1i + a1 p2i + ...+ ak-1pki Ví dụ: Sử dụng các biến đổi sơ cấp biến đổi các ma trận sinh sau thành các ma trận sinh hệ thống. 5.1.4 Giải mã. - Nguyên lý phát hiện sai: Kiểm tra xem tổ hợp nhận có phải là từ mã hay không, nếu không thì tổ hợp nhận là sai. - Mỗi ma trận G bất kỳ kích thƣớc k × n với k hàng độc lập tuyến tính luôn tồn tại ma trận H kích thƣớc (n – k) × n với (n – k) hàng độc lập tuyến tính sao cho G × H T = 0, trong đó HT là ma trận chuyển vị của ma trận H. - Nói cách khác các vectơ hàng của H đều trực giao với các vectơ hàng của G. Cách phát hiện sai - Nếu v là một từ mã đƣợc sinh ra từ ma trận sinh G có ma trận kiểm tra tƣơng ứng là H thì o v × H T = 0 - Ngƣợc lại nếu o v × H T = 0 thì v là một từ mã đúng. Ma trận kiểm tra - Ma trận kiểm tra của một bộ mã có ma trận sinh Gk×n là ma trận H có kích thƣớc (n – k) × n sao cho G × HT = 0 vì vậy nếu G có dạng: G(kxn) = [P|Ikk] =                    1...00...... ........................... ........................... 0...10...... 0...01...... )(21 )(22221 )(11211 knkkk kn kn ppp ppp ppp Thì H(n-k)xn = [I(n-k)x(n-k)|P T ] §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 38 Syndrome – vectơ sửa sai (corrector) - v × H T đƣợc gọi là syndrome hay vectơ sửa sai của v và đƣợc kí hiệu là s. v là từ mã khi và ch khi s là ma trận toàn không. Quy tắc giải mã:  Bƣớc 1: Giả sử thu đƣợc từ mã v. Tính s = v.HT . o Nếu s = 0 thì từ mã thu đƣợc là đúng. Bỏ đi phần kiểm tra ta thu đƣợc từ mã chứa thông tin u = [u1 u2 ... uk] o Nếu s  0 thì từ mã thu đƣợc là sai. Chuyển sang bƣớc 2.  Bƣớc 2: Sửa sai. Lập bảng lỗi trên cơ sở số lỗi thu đƣợc. Sai số () Syndrome (s) 0000000 000 1000000 101 0100000 011 0010000 110 0001000 111 0000100 100 0000010 010 0000001 001 Trên cơ sở giá trị s thu đƣợc, tra bảng lỗi xác định đƣợc . Từ đó xác định đƣợc từ mã vđ = v  . Bỏ đi phần kiểm tra ta thu đƣợc từ mã chứa thông tin u = [u1 u2 ... uk]. Ví dụ: Cho ma trận quan hệ: P =             111 011 010 101 a. Cho thông tin u = [ 0 0 1 1]. Tìm từ mã v. b. Cho từ mã v = [ 1 0 1 0 0 1 0]. Tìm thông tin ban đầu u. Giải: a. Từ ma trận quan hệ P ta lập ma trận sinh G nhƣ sau: G =             1111000 0110100 0100010 1010001 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 39 Vậy từ mã v đƣợc tính nhƣ sau: v = u.G = [ 0 0 1 1].             1111000 0110100 0100010 1010001 =[0 0 1 1 0 0 1] b. Từ ma trận quan hệ P ta lập ma trận kiểm tra H: H(n-k)xn = [I(n-k)x(n-k)|P T ] H =           1001001 0101110 0011101 Tính ma trận s: s = v.H T = [ 1 0 1 0 0 1 0].                       100 010 001 111 011 010 101 = [0 0 1] s = [0 0 1] ≠ [0 0 0]. Vậy từ mã thu đƣợc là sai. Do vậy ta tiến hành sửa sai nhƣ sau: Tra bảng lỗi để tìm sai số Sai số () Syndrome (s) 0000000 000 1000000 101 0100000 011 0010000 110 0001000 111 0000100 100 0000010 010 0000001 001 Vậy vđ = v  ε = [ 1 0 1 0 0 1 0]  [0 0 0 0 0 0 1]= [1 0 1 0 0 1 1] Bỏ đi 3 bít kiểm tra ta thu đƣợc thông tin u = [1 0 1 0] §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 40 5.2. Mã Hamming (Hamming Code) 5.2.1. Khái niệm. Mã Hamming là mã có cấu trúc n,k với n = 2m -1; k = 2m – m – 1; m = n – k. Mã Hamming là mã ch sửa đƣợc một lỗi sai. 5.2.2 Phƣơng pháp tạo mã. Yêu cầu: cho thông tin u = [u1 u2 ... uk]. Xác định từ mã Hamming. Cách tạo mã:  Bƣớc 1: Cho thông tin u = [u1 u2 ... uk]. Xác định đƣợc k, k =2 m – m – 1 nên xác định đƣợc m.  Bƣớc 2: Từ m lập tổng kiểm tra.  Bƣớc 3: Xác định vị trí các bít kiểm tra nằm tại vị trí 2 j, (j = 0 m-1)  Bƣớc 4: Ghép từ mã chứa thông tin vào từ mã Hamming. Cho các tổng kiểm tra bằng không từ đó xác định đƣợc các bít kiểm tra và từ mã Hamming. Ví dụ: Cho u = [1 1 1 0]. Tìm từ mã Hamming. Giải: Ta có: u = [ 1 1 1 0] nên k = 4, k = 2 m – m – 1  m = 3, n = 7. Gọi từ mã Hamming có dạng sau: vH = [a7 a6 a5 a4 a3 a2 a1] Lập tổng kiểm tra: m = 3 vậy ta có 23 = 8 tổ hợp giá trị nhƣ sau: ai e2 e1 e0 a1 0 0 1 a2 0 1 0 a3 0 1 1 a4 1 0 0 a5 1 0 1 a6 1 1 0 a7 1 0 1 Vậy e0 = a1 + a3 + a5 +a7 e1 = a2 + a3 + a6 + a7 e2 = a4 + a5 + a6 + a7 Xác định vị trí các bít kiểm tra nằm tại vị trí 2 j, (j = 0 2) nên các bít kiểm tra là a1 , a2 , a4 Ghép thông tin vào từ mã ta có: vH = [1 1 1 a4 0 a2 a1] §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 41 Cho các tổng kiểm tra bằng 0 ta thu đƣợc a1 = 0, a2 = 0, a4 = 1 Vậy từ mã Hamming là vH = [1 1 1 1 0 0 0] 5.2.3 Giải mã. Bài toán giải mã là bài toán ngƣợc của mã hóa tức là ta thu đƣợc vH và phải đi tìm thông tin ban đầu u. Cách giải mã:  Bƣớc 1: Cho từ mã Hamming ta xác định đƣợc n. Từ n suy ra k và m.  Bƣớc 2: Từ m lập tổng kiểm tra. Trên cơ sở từ mã thu đƣợc xác định các bít tƣơng ứng. Tính các tổng kiểm tra. o Nếu tất cả các tổng kiểm tra bằng 0 thì từ mã thu đƣợc là đúng. Bỏ đi các bít kiểm tra (tại các vị trí 2 j) ta thu đƣợc thông tin ban đầu u. o Nếu bất kỳ một tổng kiểm tra nào khác không thì từ mã thu đƣợc là sai  Chuyển sang bƣớc 3 để sửa sai.  Bƣớc 3: Sửa sai. Chuyển (er-1er-2...e0) từ hệ nhị phân sang hệ thập phân. Giá trị ở hệ thập phân là giá trị sai  sửa lại. Bỏ đi các bít kiểm tra (tại các vị trí 2j) ta thu đƣợc thông tin ban đầu u. Ví dụ: Cho từ mã Hamming 1010000. Tìm thông tin ban đầu u. Giải: Từ mã Hamming vH = [1 0 1 0 0 0 0]  n = 7  m = 3. a7 = 1, a6 = 0, a5 = 1, a4 = 0, a3 = 0, a2 = 0, a1 = 0 Tính các tổng kiểm tra: e0 = a1 + a3 + a5 +a7 = 0 e1 = a2 + a3 + a6 + a7 = 1 e2 = a4 + a5 + a6 + a7 = 0 Ta thấy e1 = 1 ≠ 0 nên từ mã thu đƣợc là sai. Sửa sai: Chuyển (e2e1e0) từ hệ nhị phân sang hệ thập phân: (e2e1e0)2 = (010)2 = (2)10. Vậy a2 sai mà a2 sai = 0  a2đ = 1. Từ mã Hamming đúng là: vHđ = [1 0 1 0 0 1 0]. Bỏ đi các bít kiểm tra ta thu đƣợc thông tin u = [ 1 0 1 0] §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 42 5.3 Mã vòng (Xyclic code) 5.3.1 Khái niệm. Một mã khối tuyến tính đƣợc gọi là mã vòng nếu đƣợc mô tả bằng tính chất: Nếu v = (v0 v1 ...vn-1) là một vector mã thì v (1) = (vn-1 v0 v1 ... vn-2) nhận đƣợc từ v bằng phép quay cũng là một từ mã. Tổng quát v (i) = (vn-i ...v0 v1 ...vn-i-1) cũng là một vector mã. Các thành phần của vector mã v có thể đƣợc xem là hệ số của đa thức v(x) nhƣ sau: v(x) = an-1x n-1 + an-2x n-2 +.... + a1x + a0 Trong đó ai bằng 0 hoặc bằng 1. Các từ mã chạy trên một vòng tuân thủ 4 quy tắc sau:  Quy tắc cộng: xk + xk = 0  Quy tắc nhân: xp . xq = x(p+q) mod n  Dịch phải: v (-i) (x) =  Dịch trái: v (i) (x) = x i .v(x) Bản chất dịch vòng của mã thể hiện theo cách sau: Nếu v(x) là một đa thức từ mã bậc (n-1) thì v (i) (x) (là phần dƣ khi chia i .v(x) cho x n +1) cũng là một từ mã. Vậy ta có: v (i) (x) = x i .v(x) mod (x n + 1) 5.3.2 Đa thức sinh và ma trận sinh. Ta có thể tạo ra mã vòng bằng cách sử dụng một đa thức sinh giống nhƣ mã khối tuyến tính sử dụng ma trận sinh. Đa thức sinh g(x) cho một mã vòng (n,k) là duy nhất và có dạng: g(x) = gmx m + gm-1x m-1 + g1x +... g0 trong đó: g0 và gm bằng 1 Khi v(x) là một từ mã đƣợc sinh bởi g(x) thì: v(x) = u(x).g(x) Trong đó u(x) là đa thức bản tin có bậc n-m-1. Bản tin u(x) đƣợc viết: u(x) = un-m-1x n-m-1 + ... +u1x + u0 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 43 Ví dụ 5.3.2.1: x 7 + 1 = (1 + x + x 3 )(1 + x + x 2 + x 4 ) Nên ta có thể sử dụng g(x) = (1 + x + x3) là đa thức sinh khi đó m = 3, n = 7  k = 4. Ta có mã vòng (n,k) = (7,4) Nếu sử dụng g(x) = (1 + x + x2 + x4) là đa thức sinh khi đó m = 4, n = 7  k = 3. Ta có mã vòng (n,k) = (7,3) Ví dụ 5.3.2.2: Cho vector bản tin u = 1101. Từ mã vòng đƣợc sinh ra bởi đa thức sinh g(x) = (x 3 + x +1). Tìm từ mã v. Giải: Vector bản tin đƣợc viết dƣới dạng đa thức nhƣ sau: u(x) = (x3 + x2 +1) Từ mã v đƣợc sinh ra bởi đa thức sinh nhƣ sau: v(x) = u(x).g(x) v(x) = (x 3 + x 2 +1) (x 3 + x +1)= (1+x+x 2 +x 3 +x 4 +x 5 +x 6 ) Từ mã viết dƣới dạng vector: v = 1111111. Mặt khác, ta cũng có thể tìm đƣợc từ mã v bằng cách sử dụng ma trận sinh đƣợc xây dựng từ đa thức sinh g(x) nhƣ sau: G =                  )( ........ )( )( )( 1 2 xgx xgx xxg xg k =                 m m m ggg ggg ggg ...0...00 ........ ........ 0...0...0 00...0... 10 10 10 Ví dụ 5.3.2.3: Cho vector bản tin u = 1101. Từ mã vòng đƣợc sinh ra bởi đa thức sinh g(x) = (1 + x 2 + x 3). Tìm từ mã v bằng ma trận sinh G. Giải: Ma trận sinh đƣợc xây dựng từ đa thức sinh g(x) nhƣ sau: G =             1011000 0101100 0010110 0001011 v = u.G = [1 1 0 1].             1011000 0101100 0010110 0001011 = [1 0 1 0 0 0 1] §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 44 5.3.3. Mã vòng hệ thống Cũng giống nhƣ mã khối tuyến tính để giảm độ phức tạp ta dùng mã vòng hệ thống. Thủ tục tạo mã vòng hệ thống nhƣ sau: Vector bản tin biểu diễn dƣới dạng đa thức: u(x) = uk-1x k-1 +... + u1x+u0 Ở dạng hệ thống, các bít bản tin là một thành phần của vector mã, bằng cách dịch các bít bản tin vào k tầng cuối cùng bên phải của thanh ghi từ mã, sau đó thêm các bít kiểm tra vào n – k tầng cuối cùng bên trái. Để đƣợc nhƣ vậy chúng ta tính toán về mặt đại số sao cho đa thức bản tin bị dịch traí n-k vị trí. x n-k u(x) = uk-1x n-1 +... u1x n-k+1 +x n-k u0 Nếu tiếp tục chia công thức trên cho g(x) thì kết quả đƣợc biểu diễn nhƣ sau: x n-k u(x) = q(x)g(x) + r(x) Hay r(x) = x n-k u(x) mod g(x) r(x) = r n-k-1x n-k-1 +... +r1x+ r0 Khi đó đa thức từ mã tƣơng ứng với vector mã v = (uk uk-1 ...u0 rn-k-1 ...r1 r0 ) Ví dụ 5.3.3: Tạo mã vòng ở dạng hệ thống sử dụng đa thức sinh g(x) = x3+x2+ 1cho mã vòng (7,4) cho vector bản tin u = [1 1 0 1] Giải: Từ vector bản tin u = [1 1 0 1] ta suy ra đa thức bản tin u(x) = (1 + x2 + x3) Vậy n = 7, k = 4  m = n – k = 3 Nhân x 3u(x) ta đƣợc: x 3 u(x) = x 3 (1 + x 2 + x 3 ) = x 3 + x 5 + x 6 Chia x 3u(x) cho g(x) theo cách chia đa thức ta có: x 3 + x 5 + x 6 = (1 +x + x 2 + x 3 ) (1+x+x 3 ) + 1 Thƣơng g(x) Phần dƣ Vậy v(x) = x3u(x)+ r(x) = x6+ x5+ x3 +1 v = 1 1 0 1 0 0 1 Bít bản tin Bít kiểm tra  Phƣơng pháp tạo mã Bài toán đặt ra là: Cho từ mã u, cho số lỗi sai có khả năng sửa là s. Tìm từ mã mang tin v. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 45 Các bƣớc tạo mã nhƣ sau:  Bƣớc 1: Cho từ mã chứa thông tin, xác định đƣợc . Từ và số sai có thể sửa là suy ra n dựa vào công thức: ∑  Bƣớc 2: Phân tích xn+1 thành nhân tử. Chọn g(x) là đa thức sinh có bậc cao nhất trong số các đa thức phân tích (thƣờng có bậc n-k)  Bƣớc 3: Nếu mã không hệ thống thì từ mã v(x)=u(x).g(x). Nếu mã hệ thống thì lấy xn-ku(x) sau đó chia cho g(x) đƣợc phần dƣ là r(x) thì v(x) =x n-k u(x)+r(x) Ví dụ: Cho u = 1010, s = 1 tìm v. 5.3.4. Phƣơng pháp giải mã. Giải mã là bài toán tại đầu thu ta thu đƣợc từ mã v, biết đa thức sinh và số lỗi có thể sửa s từ đó đi tìm từ mã chứa thông tin ban đầu u. Nguyên tắc cơ bản của giải mã là dựa trên phép chia dịch vòng. Các bƣớc giải mã:  Bƣớc 1: Từ v ta suy ra v(x). Lấy v(x) chia cho đa thức sinh g(x) ta thu đƣợc thƣơng số và phần dƣ r(x). Nếu phần dƣ r(x)=0 thì từ mã thu đƣợc là đúng chuyển sang bƣớc 3, ngƣợc lại phần dƣ r(x) ≠0 thì từ mã thu đƣợc là sai chuyển sang bƣớc 2.  Bƣớc 2: Ta chuyển phần dƣ sang dạng vector rồi tính trọng số Hamming của phần dƣ, ký hiệu là w(r) o Nếu w(r)  s thì v(x)=u(x)+r(x) chuyển sang bƣớc 3. o Nếu w(r) > s. Tiến hành dịch trái hoặc dịch phải đi một số lần cho đến khi w(r)  s thì dừng lại. Khi đó v(i)đ(x) = v (i) (x) + r (i) (x). Dịch theo chiều ngƣợc lại đúng bằng số lần đã dịch để tìm từ mã đúng.  Bƣớc 3: o Nếu mã không hệ thống thì u(x) = )( )()( xg xv iđ o Nếu là mã hệ thống thì bỏ đi r bít vị trí cuối của v(x) ta thu đƣợc u(x). Chúng ta đã biết rằng, dịch vòng của một từ mã và việc mã hóa một đa thức bản tin liên quan đến việc nhân một đa thức này với một đa thức khác. Để thực hiện việc này ta sử dụng mạch nhân. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 46 5.4 Mã chập (Convolution code) 5.4.1 Khái niệm Mã chập đƣợc tạo ra bằng cách cho dãy thông tin đi qua một thanh ghi dịch tuyến tính có hữu hạn trạng thái. Thanh ghi dịch gồm K nhịp, mỗi nhịp gồm k bit và n bộ tạo hàm đại số tuyến tính. Mã chập là mã tuyến tính có ma trận sinh có cấu trúc sao cho phép mã hóa có thể xem nhƣ một phép lọc (hoặc lấy tổng chập). Mã chập đƣợc sử dụng rộng rãi trong thực tế. Bởi mã hóa đƣợc xem nhƣ một tập hợp các bộ lọc số tuyến tính với dãy mã là các đầu ra của bộ lọc đƣợc phép xen kẽ. Các mã chập là các mã đầu tiên đƣợc xây dựng các thuật toán giải mã quyết định mềm hiệu quả. Mã chập thƣờng biểu diễn thông qua ba thông số (n, k, K) trong đó: k: số bít dữ liệu đầu vào. n: số bít dữ liệu đầu ra. K: Số phần tử ghi dịch. Ta ch xem xét các bộ lập mã chập nhị phân thông dụng với k = 1 tức là bộ mã hóa trong đó các bít bản tin đƣợc dịch vào bộ mã hóa từng bít một. Tốc độ lập mã: Rc = n k 5.4.2 Biểu diễn bộ lập mã chập Để mô tả bộ lập mã chập ta cần xác định đặc tính của hàm lập mã sao cho từ chuỗi đầu vào có thể tính đƣợc chuỗi đầu ra. Những phƣơng pháp chung thƣờng đƣợc sử dụng để biểu diễn bộ lập mã chập đó là biểu đồ liên kết, sơ đồ trạng thái, sơ đồ cây và sơ đồ lƣới. Sau đây ta sẽ khảo sát chi tiết từng cách biểu diễn. a. Biểu đồ liên kết. Ta sẽ sử dụng một cấu trúc cụ thể để khảo sát mã hóa chập nhƣ sau: C uỗi đầu vào u C uỗi đầu ra v zzz v1 v2 Với cấu trúc này k = 1, n =2 (hai đầu ra ứng với hai bộ cộng modul 2), số phần tử ghi dịch K = 3. Tỷ lệ lập mã chập là ½; §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 47 Với mỗi bít thời gian đầu vào, một bít đƣợc dịch vào tầng đầu tiên (tầng đầu tiên bên trái) và các bít trong thanh ghi đƣợc dịch một vị trí về bên phải. Sau đó chuyển mạch đầu ra lâ ý mẫu tại đầu ra của các bộ cộng modul 2. Một cách mã hóa là ch ra tập n các vector liên kết, mỗi vector liên kết là một bộ cộng modul 2. Mỗi vector liên kết có kích thƣớc K và mô tả liên kết của thanh ghi. Với bộ lập mã trên hình trên ta chso thể viết vector liên kết g1 cho bộ cộng modul 2 trên và g2 cho bộ cộng modul 2 dƣới. g1 = 111 và g2 = 101 Ta xét vector bản tin u = 101. Ba bít mang tin ở đầu vào, từng bít một tại các thời điểm t1, t2, t3 . Thời điểm t4, t5 để làm sạch thanh ghi. Thời điểm Tín hiệu vào Z1 Z2 Z3 v1 v2 v t0 0 0 0 0 0 0 00 t1 1 1 0 0 1 1 11 t2, 0 0 1 0 1 0 10 t3 1 1 0 1 0 0 00 t4 0 0 1 0 1 0 10 t5 0 0 0 1 1 1 11  Biểu diễn đa thức Trong một vài trƣờng hợp, những liên kết của bộ lập mã đƣợc biểu diễn bởi đa thức tổng hợp. Ta có thể mô tả bộ lập mã nhƣ một tập n đa thức tổng hợp. Mỗi đa thức có bậc là K-1 hoặc nhỏ hơn và biểu diễn sự liên kết của thanh ghi dịch mã hóa với bộ cộng modul 2, tƣơng tự nhƣ vector liên kết. Hệ số cả các phần tử trong đa thức bậc K-1 là 1 hoặc 0, phụ thuộc vào ở vị trí cố hay không có sự liên kết giữa hai thanh ghi dịch mã với bộ cộng. Trong ví dụ trên ta có thể viết đa thức g1(x) cho sự liên kết với bộ cộng trên và đa thức g2(x) với sự liên kết với bộ cộng dƣới: g1 = 1 + x + x 2 và g2 = 1 + x 2 Ở đây các phần tử trong đa thức đƣợc sắp xếp phù hợp với các tầng đầu vào của thanh ghi. Dãy đầu ra tìm đƣợc nhƣ sau: v(x) = u(x) . g1(x) kết hợp với v(x) = u(x) . g2(x) Ví dụ vector bản tin u = 101, đa thức, đa thức tƣơng ứng là 1 + x2. Chúng ta lại sử dụng các số 0 theo sau các bít bản tin để flush thanh ghi. Dãy đầu ra hay đa thức đầu ra v(x): u(x) . g1(x) = (1 + x 2 )(1 + x + x 2 ) = 1 + x + x 3 + x 4 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 48 u(x) . g2(x) = (1 + x 2 )(1 + x 2 ) = 1 + x 4  u(x) = (1,1) + (1,0)x + (0,0)x2 + (1,0)x3 + (1,1)x4 u = 11 10 00 10 11 b. Mô tả trạng thái. Trạng thái của bộ lập mã chập tốc độ 1/n đƣợc xác định bằng nội dung của K-1 tầng cuối. Các trạng thái đƣợc thể hiện trong các hộp chữ nhật của sơ đồ, biểu diễn các khả năng nội dung của K-1 tầng cuối thanh ghi dịch (2 K-1 trạng thái) và giữa các hộp chữ nhật có chuyển đổi trạng thái theo các hƣơng mũi tên. Trên các mũi tên có ghi giá trị đầu vào và đầu ra khi chuyển trạng thái. Với ví dụ này có 2 thanh ghi cuối vậy có 4 trạng thái là 00, 01, 10, 11. Sơ đồ sau minh họa tất cả các chuyển tiếp trạng thái có thể có của bộ lập mã: 10 01 00 11 0/00 1/10 1/11 0/10 1/01 0/01 0/11 1/00 Nhƣợc điểm của sơ đồ: không cho biết thời gian bắt đầu và kết thúc. c. Sơ đồ cây. Mặc dù sơ đồ trạng thái đƣa ra hoàn ch nh các đặc tính của bộ lập mã nhƣng không không cho biết thời gian bắt đầu và kết thúc. Sơ đồ cây cộng với chiều của thời gian sẽ cải tiến vấn đề này. Với mỗi chuỗi bít đầu vào đƣợc mô tả bởi đƣờng đi trên sơ đồ từ trái qua phải, mỗi nhánh cây mô tả một từ nhánh đầu ra. Quy luật nhƣ sau:  Nếu đầu vào là 0 thì từ nhánh liên kết đƣợc tìm bởi dịch chuyển đến nhánh tiếp theo về bên trên.  Nếu đầu vào là 1 thì từ nhánh liên kết đƣợc tìm bởi dịch chuyển đến nhánh tiếp theo về bên dƣới. Cộng với chiều thời gian của sơ đồ cây cho phép mô tả một cách linh hoạt bộ lập mã nhƣ là hàm của chuỗi đầu vào đặc biệt. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 49 0 1 00 11 00 11 00 11 10 01 10 01 11 00 01 10 Nhƣợc điểm: Khi chuỗi đầu vào có độ dài lớn thì số nhánh tăng lên theo hàm mũ. d. Sơ đồ lƣới. Sơ đồ lƣới không những cho biết về mặt thời gian cũng nhƣ sự chuyển đổi trạng thái giá trị đầu vào và giá trị đầu ra mà sơ đồ lƣới còn đƣợc dùng để giải mã chập. Quy ƣớc: Nếu bít đầu vào là 1 thì là đƣờng nét đứt. Nếu bít đầu vào là 0 thì là đƣờng nét liền. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 50 t1 t2 t3 t4 t5 t600 00 00 00 00 00 10 01 11 Trạng thái n-k thanh g i cuối 11 11 11 11 11 10 10 10 10 11 11 11 01 01 01 01 01 01 01 10 10 10 00 00 00 5.4.3 Giải mã chập Để giải mã chập ngƣời ta dùng sơ đồ lƣới sử dụng thuật toán Viterbi. Thuật toán này dựa trên các giá trị đầu ra thu đƣợc, so sánh với các giá trị đầu ra trên lƣới. Tính các khoảng cách mã (Khoảng cách Hamming giữa hai từ mã). Sau một khoảng thời gian đủ lớn ta sẽ loại bỏ dần những đƣờng khoảng cách lớn, ch giữ lại những đƣờng có khoảng cách nhỏ gọi là đƣờng sống sót. Đây chính là đƣờng mã cần tìm. Giả sử đầu ra ta thu đƣợc từ mã 11 10 00 10 11, ta tiến hành so sánh các giá trị đầu ra thu đƣợc với các giá trị đầu ra trên lƣới. Tính các khoảng cách Hamming giữa hai từ mã. Sau đó tìm đƣờng mã sao cho khoảng cách mã là nhỏ nhất t1 t2 t3 t4 t5 t62 1 0 1 2 00 10 01 11 Trạng thái n-k thanh g i cuối 0 1 2 1 0 0 1 0 1 2 1 0 2 1 2 1 1 2 1 1 0 1 0 1 2 11 10 00 10 11Gía trị t u được Gía trị đầu vào 1 0 1 0 0 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 51 Giả sử đầu ra ta thu đƣợc từ mã 11 11 10 01 00, ta tiến hành so sánh các giá trị đầu ra thu đƣợc với các giá trị đầu ra trên lƣới. Tính các khoảng cách Hamming giữa hai từ mã. Sau đó tìm đƣờng mã sao cho khoảng cách mã là nhỏ nhất 11 11 10 01 00Gía trị t u được Gía trị đầu vào 1 1 1 0 1 t1 t2 t3 t4 t5 t62 2 1 1 0 00 10 01 11 Trạng thái n-k thanh g i cuối 0 0 1 1 0 1 0 2 1 1 1 2 1 2 0 1 2 0 1 0 2 1 1 1 0 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 52 CHƢƠNG 6: M MẬT 6.1 Giới thiệu chung về các hệ thống mật mã Mong muốn đƣợc trao đổi thông tin một cách bí mật là một trong những đòi hỏi của con ngƣời xuất hiên từ rất sớm trong lịch sử. Vì thế lịch sử của việc trao đổi thông tin mật rất phong phú và bao gồm những phát minh độc đáo. Ngành học nghiên cứu cách thức che dấu thông tin đối với những đối tƣợng không mong muốn đƣợc gọi là mật mã học.  Phân loại các hệ thống mật mã.  Xét cách thức tiến hành mã hóa ta có thể chia quá trình mật mã thành hai loại:  Mã hóa khối: Dữ liệu trƣớc khi mã hóa sẽ bị chia nhỏ thành từng khối có độ dài cố định, sau đó mỗi khối đƣợc mã hóa một cách độc lập. Do đó, §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 53 nếu sử dụng cùng khóa thì việc mã hóa các các khối văn bản gốc giống nhau sẽ cho ta các khối văn bản mã hóa giống nhau.  Mã hóa chuỗi dữ liệu: Tƣơng tự nhƣ mã chập, độ dài không cố định. Mỗi bít của văn bản gốc m đƣợc mã hóa bằng thành phần thứ i của chuỗi ký hiệu đƣợc hình thành từ từ khóa.  Xét về mối quan hệ giữa mã hóa và giải mã ta có thể chia quá trình mật mã thành hai loại:  Hệ thống mật mã đối xứng (bí mật): Là hệ thống sử dụng một khóa duy nhất cho cả mã hóa và giải mã.  Hệ thống mật mã không đối xứng (công khai): Có hai khóa, một khóa dùng cho lập mã và có thể công bố rộng rãi, khóa còn lại dùng để giải mã đƣợc giữ bí mật 6.2 Một số hệ thống mật mã.  Bảng chữ cái. Ví dụ: §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 54  Ma trận vuông Polybius: Bảng chữ cái đƣợc xếp thành một ma trận 5x5 (chữ i và chữ J đƣợc gộp lại nhƣ một chữ) 1 2 3 4 5 1 A B C D E 2 F G H IJ K 3 L M N O P 4 Q R S T U 5 V W X Y Z  Mã lũy tiến Đây là một ví dụ của mã hóa bản chữ cái bội Hàng 0: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Hàng 1: B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Hàng 2: C D E F G H I J K L M N O P Q R S T U V W X Y Z A B ........................................................................................................... Hàng 25:Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Phƣơng pháp sử dụng bản chữ cái này là chữ đầu tiên mã hóa ở hàng 1, chữ thứ 2 mã hóa ở hàng 2 và cứ nhƣ thế tiếp tục. 6.3. Những cách thức tấn công vào một hệ thống mật mã. Hệ thống tấn công có thể có một trong bốn khả năng tấn công một hệ thống mật mã tùy thuộc vào những thông tin có thể thu thập đƣợc.  Ch biết bản tin mật mã: Trong trƣờng hợp này hệ thống tấn công ch có trong tay các bản tin mật mã. Quá trình phân tích phải dựa trên tính chất thống kê, phân bố và các tính chất khác của bản tin mật mã – những điều đƣợc truyền công khai trên kênh truyền. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 55  Biết đầy đủ hoặc một phần bản tin gốc và bản tin mật mã tƣơng ứng: Trong trƣờng hợp này hệ thống phân tích may mắn hoặc tình cờ có đƣợc bản tin gốc cùng với bản tin mật mã tƣơng ứng. Chẳng hạn, những thông báo ngoại giao hoặc pháp lý th nh thoảng đƣợc công bố và đồng thời hệ thống phân tích lại thu đƣợc cả bản tin mật mã trên kênh truyền. Gọi C là bản tin mật mã, P là bản tin gốc, E là thuật toán mã hóa. D là thuật toán giải mã thì C = E(P). Hệ thống phân tích có đƣợc C, P và cố gắng tìm ra E hoặc D. Những cấu trúc cố định của các mẫu văn bản kinh tế, ngoại giao cũng nhƣ những cấu trúc của các ngôn ngữ lập trình thƣờng cung cấp những thông tin về văn bản gốc để hệ thống tấn công thực hiện dạng tấn công loại này.  Biết bản tin mật mã của bất cứ bản tin gốc nào: Trong một số trƣờng hợp hệ thống phân tích có thể thâm nhập vào hệ thống gửi để có thể mã hóa và gửi đi một bản tin theo ý muốn. Tấn công loại này còn đƣợc gọi là tấn công lựa chọn bản tin gốc. Chẳng hạn hệ thống phân tích có thể chèn hoặc xóa các bản ghi trong một cơ sở dữ liệu rồi quan sát những thay đổi xảy ra đối với bản tin mật mã. Cách tấn công này rất hay đƣợc các hệ thống phân tích tận dụng. Mặc dù việc tấn công biết trƣớc văn bản gốc không phải lúc nào cũng thực hiện đƣợc nhƣng tần suất của nó đủ để cho một hệ thống không thể coi là an toàn trừ khi hệ thống đó chống lại đƣợc kiểu tấn công này.  Biết bản tin gốc và thuật toán: Hệ thống phân tích cũng có thể có đƣợc thuật toán mật mã cùng với các bản tin mật mã thu đƣợc trên kênh truyền. Hệ thống phân tích có thể tấn công bằng cách đơn giản là thử mã hóa một số lƣợng rất lớn các bản tin gốc có thể cho đến khi nhận đƣợc bản tin mật mã thu đƣợc trên kênh. Mục đích của quá trình thử là xác định khóa đang sử dụng để có thể sử dụng cho giải mã các bản tin trong tƣơng lai. §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 56 MỤC LỤC CHƢƠNG 1: KHÁI NIỆM CHUNG .....................................................................................3 1.1 Khái niệm chung về hệ thống thông tin và truyền tin. .................................................3 1.1.1. Thông tin. .............................................................................................................3 1.1.2. Tín hiệu.................................................................................................................3 1.2 Mô hình của hệ thống truyền tin. .................................................................................3 1.3. Các yêu cầu cơ bản của hệ thống truyền tin. ..............................................................4 1.3.1. Tính hữu hiệu. ......................................................................................................4 1.3.2. Độ tin cậy. ............................................................................................................4 1.3.3. An toàn. ................................................................................................................5 1.4. Độ đo thông tin. ..........................................................................................................5 1.5. Số hóa nguồn tin liên tục. ...........................................................................................6 1.5.1 Lấy mẫu (Sampling). .............................................................................................6 1.5.2 Lƣợng tử hóa (Quantizing) ....................................................................................7 1.5.3 Mã hóa (Coding)....................................................................................................7 CHƢƠNG 2: THÔNG TIN ....................................................................................................8 2.1 Lƣợng tin nguồn rời rạc ................................................................................................8 2.1.1 Khái niệm nguồn tin rời rạc ...................................................................................8 2.1.2 Lƣợng tin nguồn rời rạc .........................................................................................8 2.2 Entropi nguồn rời rạc ....................................................................................................9 2.2.1 Định nghĩa .............................................................................................................9 2.2.2 Tính chất của Entropy .........................................................................................10 2.3 Kênh rời rạc. ..............................................................................................................10 2.3.1 Định nghĩa. ..........................................................................................................10 2.3.2 Entropy đồng thời. ...............................................................................................11 2.3.3 Entropi có điều kiện. ............................................................................................12 2.3.4 Quan hệ giữa lƣợng tin tƣơng hỗ trung bình và entropy. ....................................14 2.3.5 Các dạng kênh truyền ........................................................................................156 2.3.6Lƣợc đồ giải mã tối ƣu .........................................................................................16 2.4 Entropy của nguồn liên tục. ........................................................................................17 2.5 Vấn đề phối hợp nguồn kênh. .....................................................................................17 CHƢƠNG 3: M HIỆU.......................................................................................................19 3.1 Khái niệm và định nghĩa. ............................................................................................19 3.1.1 Các khái niệm: .....................................................................................................19 3.1.2 Các thông số cơ bản của một bộ mã: ...................................................................19 3.2 Các phƣơng pháp biểu diễn mã ..................................................................................20 3.2.1 Các bảng mã ........................................................................................................20 3.2.2 Đồ hình mã ..........................................................................................................21 3.2.3 Hàm cấu trúc mã..................................................................................................22 3.3 Điều kiện phân tách của mã hiệu. ...............................................................................22 3.3.1 Điều kiện chung đối với một bảng mã phân tách đƣợc. ......................................22 3.3.2 Bảng thử mã.........................................................................................................23 §Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 57 3.3.3 Bất đẳng thức Kraft............................................................................................. 24 3.3.4 Thủ tục tạo mã phân tách đƣợc dựa vào độ dài đã biết của các từ mã ............... 24 3.4 Mã hệ thống. .............................................................................................................. 25 3.4.1 Mã hệ thống tổng quát. ....................................................................................... 25 3.4.2 Mã hệ thống có tính prefix. ................................................................................. 26 CHƢƠNG 4: M H A NGU N ....................................................................................... 27 4.1 Mô hình toán học của nguồn thông tin. ..................................................................... 27 4.1.1 Định lý giới hạn dƣới về độ dài trung bình của các từ mã. ................................ 27 4.1.2 Định lý giới hạn trên về độ dài trung bình của các từ mã. .................................. 28 4.2 Mã hóa nguồn rời rạc. ................................................................................................ 28 4.2.1 Phƣơng pháp mã hóa Shannon ........................................................................... 28 4.2.2 Phƣơng pháp mã hóa Fano ................................................................................. 29 4.2.3 Phƣơng pháp mã hóa Huffman ........................................................................... 30 CHƢƠNG 5: M H A K NH........................................................................................... 33 5.1 Mã khối tuyến tính (Block code) ............................................................................... 33 5.1.1 Các khái niệm: ................................................................................................... 33 5.1.2 Ma trận sinh. ....................................................................................................... 34 5.1.3 Mã khối tuyến tính hệ thống. .............................................................................. 36 5.1.4 Giải mã................................................................................................................ 37 5.2. Mã Hamming (Hamming Code) ............................................................................... 40 5.2.1. Khái niệm. .......................................................................................................... 40 5.2.2 Phƣơng pháp tạo mã. .......................................................................................... 40 5.2.3 Giải mã................................................................................................................ 41 5.3 Mã vòng (Xyclic code) .............................................................................................. 42 5.3.1 Khái niệm............................................................................................................ 42 5.3.2 Đa thức sinh và ma trận sinh. ............................................................................. 42 5.3.3. Mã vòng hệ thống .............................................................................................. 44 5.3.4. Phƣơng pháp giải mã. ........................................................................................ 45 5.4 Mã chập (Convolution code) ..................................................................................... 46 5.4.1 Khái niệm............................................................................................................ 46 5.4.2 Biểu diễn bộ lập mã chập .................................................................................... 46 5.4.3 Giải mã chập ....................................................................................................... 50 CHƢƠNG 6: M MẬT....................................................................................................... 52 6.1 Giới thiệu chung về các hệ thống mật mã ................................................................. 52 6.2 Một số hệ thống mật mã. ........................................................................................... 53 6.3. Những cách thức tấn công vào một hệ thống mật mã. ............................................. 54