Bài giảng môn Kỹ thuật viễn thông - Mạng viễn thông - Lý thuyết thông tin

9/12/2010 1 Mạng viễn thơng - lý thuyết thơng tin 29/12/2010 Outline • Giới thiệu Mạng viễn thơng • Khái niệm cơ bản • Thơng tin • Entropy • Mã hĩa nguồn 39/12/2010 Giới thiệu • Viễn thơng là gì? • Tiếng Hi Lạp : "tele” - xa; và và Latin, "communicate“ –chia sẻ . Viễn thơng là truyền thơng cự ly xa. • Bản chất của Viễn thơng là truyền Thơng tin đến 1 hay nhiều người dùng trong bất kỳ dạng nào cĩ thể 49/12/2010 Viễn thơng • Cĩ xu hướng nghĩ Viễn thơng là điện thoại, mạng máy tính, Internet, truyền hình cáp. • Bao gồm phương tiện điện, điện từ, và quang đã được nhắc đến, đồng thời Bao gồm dây dẫn đơn giản, radio, hay dạng khác. 59/12/2010 Viễn thơng thời kỳ đầu • trống và cịi • khĩi/Tín hiệu lửa • ánh sáng • bồ câu trống khĩi bồ câuTower using mirrors 69/12/2010 Viễn thơng phát triển • điện tín (Morse) • điện thoại (Bell) • truyền thơng khơng dây • truyền thơng vệ tinh A BTS (Mobile Communication) VINASAT-1 satellite 79/12/2010 hệ thống chuyển mạch hệ thống truyền thơng quang hệ thống thoại và truyền hình Hệ thống truyền thơng vệ t hệ thống truyền thơng di động Hệ thống truyền thơng khơng dây hệ thống truyền thơng dữ liệu Mạng viễn thơng 89/12/2010 • Mạng viễn thơng là mạng gồm liên kết và nút mạng viễn thơng được sắp xếp để thơng tin chuyển từ 1 phần của mạng đến mạng khác qua nhiều kết nối và thơng qua chế độ khác nhau. 99/12/2010 Mạng viễn thơng • Mạng viễn thơng được chia thành: – thiết bị chuyển mạch và thiết bị truyền nhận cùng nhau hình thành mạng lõi – thiết bị đầu cuối hướng khách hàng kết nối đến mạng lõi thơng qua truy nhập mạng • truyền tải và chuyển mạch là 2 chức năng cơ bản để truyền tải Thơng tin người dùng. Transport thiết bị truyền nhận chuyển mạch Switch hay Exchange hay Central Office (CO) truy nhập thiết bị để truy nhập của thuê bao (truy nhập mạngs AN) Customer Premises Equipment (CPE) thiết bị đầu cuối thuê bao 109/12/2010 Transport AN AN N T N T AN N T AN N T Exchange truy nhập mạng (AN) với đầu cuối thuê bao (CPE) truyền tải kênh truyền(trao đổi liên kết kết nối): • trung kế để truyềnThơng tin người dùng • tín hiệu kết nối để truyền thơng tin điều khiển SIEMENS NIXDORF SIEMENS NIXDORF SIEMENS NIXDORF SIEMENS NIXDORF 119/12/2010 Khái niệm cơ bản • sơ đồ khối của hệ thống truyền thơng số mã hĩa nguồn mã hĩa kênh truyền bộ điều chế kênh truyền nhiễu bộ giải mã kênh bộ giải mã nguồn bộ giải điều chế nguồn đích 129/12/2010 lý thuyết thơng tin? • lý thuyết thơng tin cung cấp cách đo lường của nguồn Thơng tin, dung lương thơng tin của một kênh truyền • mã hĩa là phương tiện tối ưu hĩa dung lượng kênh truyền để lưu chuyển Thơng tin • lý thuyết mã hĩa của Shannon: “Nếu tốc độ của Thơng tin từ nguồn ko vượt quá dung lượng của kênh truyền thơng tin, thì tồn tại kỹ thuật mã hĩa mà Thơng tin được phát qua kênh truyền với xác suất lỗi nhỏ, bất chấp sự tồn tại của lỗi” 139/12/2010 đo lường Thơng tin • lý thuyết thơng tin: bao nhiêu Thơng tin – chứa trong tín hiệu? – hệ thống phát sinh? – một kênh truyền truyền tải? • Thơng tin là 1 dạng hàng hĩa sản xuất bởi nguồn để đến vài người dùng ở đích • Ví dụ : Barcelona vs GĐT-LA 149/12/2010 đo lường Thơng tin • 3 kết quả: thắng, hịa, thua • Sự kiện càng ít khả năng, càng chưa nhiều thơng tin • Thơng tin định nghĩa tốn học như thế nào? Cases sự kiệns Thơng tin khả năng 1 Barca thắng khơng cĩ Thơng tin ≈1, chắc chắn 2 Barca hịa với GĐT-LA Thơng tin nhiều hơn Tương đối thấp 3 Barca thua Lượng Thơng tin lớn Xác suất thấp xuất hiện trong tình huống đặc biệt i 159/12/2010 Thơng tin • xj là sự kiện với p(xj) là khả năng của sự kiện xj được chọn để truyền dẫn • Nếu xj xảy ra 1( ) log log ( ) ( )j a a jj I x p x p x = = − đơn vị của Thơng tin „ I(xj) được gọi self-information … I(xj)≥0 for 0≤ p(xj)≤1 … I(xj)→0 for p(xj)→1 … I(xj)>I(xi) for p(xj)<p(xi) (1) 169/12/2010 Thơng tin • cơ số của logarithm – 10 → đo lường của Thơng tin là hartley – e → đo lường của Thơng tin là nat – 2 → đo lường của Thơng tin là bit • Ví dụ : thí nghiệm ngẫu nhiên với 16 kết quả tương đương: – Thơng tin tương ứng với mỗi kết quả : • I(xj)=-log2(1/16)=log216=4 bits – Thơng tin là lớn hơn1 bit,do khả năng của mỗi kết quả là ít hơn ½. 179/12/2010 Entropy và Thơng tin tốc độ • xem xét nguồn Thơng tin phát 1 chuỗi symbols từ tập X={x1,x2..,xM} • mỗi symbol xi được xem như 1 thơng tin với khả năng p(xi) và self-informationI(xi) • Nguồn cĩ tốc độ trung bình r symbols/sec • Nguồn ko bộ nhớ gián đoạn • Lượng Thơng tin cung cấp bởi nguồn trong khoảng tùy ý symbol là biến X gián đoạn ngẫu nhiên . • Thơng tin trung bình mỗi symbol là n : • Entropy = Thơng tin = sự ko chắc chắn • Nếu tín hiệu là hồn tồn dự đốn được, nĩ cĩ 0 entropy và khơng cĩ Thơng tin • Entropy = số trung bình bits yêu cầu để truyền tải tín hiệu bit/symbo )(log)()}({)( 1 2∑ = −== M j jjj xpxpxIEXH (2) 189/12/2010 Ví dụ • biến ngẫu nhiên với phân bố chính tắc qua 32 kết quả – H(X) = - ∑ (1/32).log(1/32) = log 32 = 5 – # bits yêu cầu = log 32 = 5 bits! – do đĩ H(X) = số bits yêu cầu để đại diện sự kiện ngẫu nhiên • Bao nhiêu bits là cần thiết : – kết quả của thảy đồng xu – “ngày mai là Thứ 5 ” 199/12/2010 Entropy • giá trị của H(X) từ 1 nguồn phụ thuộc vào xác suất symbol p(xi) và M • Tuy nhiên , • Biên thấp tương xứng đến khơng cĩ sự ko chắc chắn • biên trên tương xứng đến sự ko chắc chắn lớn nhất, xảy ra khi mỗi symbol là tương đương cĩ thể xảy ra • chứng minh của sư khơng cân bằng được thể hiện trong [2] Chapter 15 MXH 2log)(0 ≤≤ (3) 209/12/2010 chứng minh • Biên thấp với tùy ý M dễ dàng chứng minh, ghi nhớ là a.log(a)→0 as a→0 • chứng minh của biên trên là phức tạp hơn • Dựa vào bất đẳng thức ln a ≤ (a-1) MXH 2log)(0 ≤≤ Mxpxp MxpxpXH M i ii X 2 1 2 log)(log).( log)(log.)()( ≤−= ≤−= ∑ ∑ = 219/12/2010 • xem xét: MXHMXH xp M eMXH xp M eMXH xpM xpe xpM xpe xpM xpxpMxpxp MxpxpMXH M i M i i M i i i M i i M i i i M i i i M i i M i ii X 22 1 1 22 1 22 1 2 1 2 1 2 1 2 1 2 22 log)(0log)( )(1loglog)( )(1.loglog)( 1 )(. 1).(.log )(. 1ln).(.log )(. 1log).()(.log)(log).( log)(log.)(log)( ≤⇒≤−⇔ ⎟⎠ ⎞⎜⎝ ⎛ −≤−⇔ ⎟⎠ ⎞⎜⎝ ⎛ −≤−⇒ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −≤= =−−= −−=− ∑ ∑ ∑ ∑∑ ∑∑∑ ∑ = = = == === chứng minh MXH 2log)(0 ≤≤ dấu bằng xảy ra khi: M xp xpM ii 1)(1 )(. 1 =⇒= 229/12/2010 Ví dụ • Với nguồn nhị phân (M=2), p(1)=α và p(0)=1-α = β. • từ (2), entropy nhị phân: • H(X)= -α.logα -(1-α).log(1-α) 239/12/2010 lý thuyết mã hĩa nguồn • Thơng tin từ 1 nguồn tạo ra symbols khác nhau diễn tả bởi entropy H(X) • tốc độ nguồn Thơng tin (bit/s): Rs = rH(X) (bit/s) – H(X): entropy nguồn (bits/symbol) – r: tốc độ symbol(symbols/s) • giả định nguồn là đầu vào đến một kênh truyền: – C: dung lượng (bits/symbol) – S: tốc độ symbol(symbols/s) – S.C: bits/s 249/12/2010 lý thuyết mã hĩa nguồn(t.t. ) • Thuyết Shannon(lý thuyết mã hĩa ko nhiễu ): – “Cho một kênh truyền và 1 nguồn phát sinh Thơng tin ở tốc độ ít hơn dung lượng kênh truyền, cĩ thể mã hĩa đầu ra của nguồn bằng cách phát thơng qua kênh truyền” • Biểu diễn của Mã hĩa nguồn bằng Ví dụ : nguồn nhị phân rời rạc mã hĩa nguồn kênh truyền nhị phân nguồn tốc độ symbol = r = 3.5 symbols/s C = 1 bit/symbol S = 2 symbols/s SC = 2 bits/s 259/12/2010 Ví dụ của Mã hĩa nguồn • nguồn nhị phân rời rạc: A(p=0.9), B(p=0.1) • nguồn tốc độ symbol (3.5) >dung lượng kênh truyền(2) Ư nguồn symbols cĩ thể ko được phát đi trực tiếp • Kiểm tra thuyết Shannon: – H(X)=-0.1 log20.1-0.9log20.9=0.469bits/symbol – Rs = rH(X) = 3.5(0.469)=1.642 bits/s < S.C = 2 bits/s • truyền dẫn cĩ thể dùng Mã hĩa nguồn để làm giảm tốc độ symbol trung bình 269/12/2010 Ví dụ của Mã hĩa nguồn(t.t. ) • Từ mã được gán nhĩm n-symbol của nguồn symbols • QUy luật: – Từ mã ngắn nhất đến nhĩm khả năng lớn nhất – Từ mã dài nhất đến nhĩm thấp khả năng nhất • Nhĩm n -symbol của nguồn symbols # mở rộng thứ n của nguồn nguyên gốc 279/12/2010 mở rộng thứ nhất • tốc độ symbol của bộ mã hĩa = tốc độ symbol của nguồn • lớn hơn của kênh truyền cĩ thể chứa nguồn symbol P () từ mã [P()].[số mã hĩa Symbols] A 0.9 0 0.9 B 0.1 1 0.1 L=1.0 289/12/2010 mở rộng thứ hai i i i lxpL n *)( 2 1 ∑ = = nguồn symbol P () từ mã [P()].[số của mã hĩa Symbols] AA 0.81 0 0.81 AB 0.09 10 0.18 BA 0.09 110 0.27 BB 0.01 111 0.03 L=1.29 L: trung bình chiều dài mã p(xi): khả năng symbol i th của nguồn mở rộng li : chiều dài của từ mã tương ứng với i th symbol nhĩm 2 nguồn symbols cùng 1 thời điểm : 299/12/2010 mở rộng thứ hai symbol urcesymbols/so code 645.0 2 29.1 == n L 258.2)645.0(5.3 == n Lr tốc độ symbol tại đầu ra bộ mã hĩa : vẫn lớn hơn 2 symbols/s của kênh truyền Tiếp tục với mở rộng thứ 3 mã hĩa symbols/sec >2 309/12/2010 mở rộng thứ ba nhĩm 3 nguồn symbols cùng 1 thời điểm : nguồn symbol P () từ mã [P()].[số của mã hĩa Symbols] AAA 0.729 0 0.729 AAB 0.081 100 0.243 ABA 0.081 101 0.243 BAA 0.081 110 0.243 ABB 0.009 11100 0.045 BAB 0.009 11101 0.045 BBA 0.009 11110 0.045 BBB 0.001 11111 0.005 L=1.598 319/12/2010 mở rộng thứ ba 533.0 3 598.1 == n L condsymbols/se code 864.1)533.0(5.3 == n Lr tốc độ symbol tại đầu ra bộ mã hĩa : tốc độ này là chấp nhận được bởi kênh truyền mã hĩa symbols/nguồn symbol 329/12/2010 hiệu quả của nguồn mã hĩa • Độ hiệu quả là cách đo khả năng của nguồn mã hĩa ∑ = == n i ii lxp L L Leff 1 minmin )( D XHL 2 min log )(= DL XHeff 2log )(= L XHeff )(= H(X): entropy của nguồn D: số symbols trong coding alphabet Trong đĩ ” or Cho alphabet nhị phân 339/12/2010 Entropy và hiệu quả của nguồn mở rộng nhị phân • Entropy mở rộng thứ n của nguồn rời rạc ko nhớ : H (X n)=n*H (X) • hiệu quả của nguồn mở rộng: L XHneff )(.= 349/12/2010 Biểu diễn của L/n n n L 1.0 0.8 0.6 0.4 0.2 0 0 1 3 42 0.469 H(X) ƒL/n luơn vượt quá entropy nguồn và hội tụ đến entropy nguồn khi n lớn ƒgiảm chiều dài trung bình từ mã dẫn đến tăng độ phức tạp của mã hĩa 359/12/2010 Mã hĩa Shannon-Fano [1] • Trình tự : 3 bước 1. liệt kê nguồn symbols theo thứ tự giảm xác suất 2. phân chia tập thành 2 tập con gần nhất cĩ thể. 0’s được gán đến tập trên và 1’s đến tập dưới 3. tiếp tục phân chia tập con cho đến khi ko thể phân chia được nữa • Ví dụ : 369/12/2010 Ví dụ Mã hĩa Shannon-Fano Ui pi 1 2 3 4 5 Từ mã U1 .34 U2 .23 U3 .19 U4 .1 U5 .07 U6 .06 U7 .01 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 00 01 10 110 1110 11110 11111 379/12/2010 Mã hĩa Shannon-Fano 41.2 7 1 ==∑ = i i ilpL 37.2log)( 2 7 1 =−= ∑ = i i i ppUH 98.0 41.2 37.2)( === L UHeff ƒ mã hĩa phát sinh là tiền mã hĩa do khả năng phân chia ƒ khơng dẫn đến tiền mã hĩa đặc biệt. nhiều tiền mã hĩa cĩ hiệu quả giống nhau. 389/12/2010 Mã Huffman [1][2][3] • Trình tự : 3 bước 1. liệt kê nguồn symbols theo thứ tự giảm xác suất. 2 nguồn symbols xác suất thấp nhất được gán a 0 và a 1. 2. 2 nguồn symbols kết hợp thành nguồn symbol mới với xác suất tương đương tổng của 2 xác suất nguyên gốc. xác suất mới đặt trong danh sách tương ứng với giá trị của nĩ. 3. lập lại cho đến khi khả năng cuối cùng của symbol kết hợp mới là 1.0. • Ví dụ : 399/12/2010 Ví dụ của Mã hĩa Huffman .01U7 .06U6 .07U5 .1U4 .19U3 .23U2 .34U1 piUi 0 1 .07 0 1 .14 0 1 .24 0 1 .42 0 1 .58 0 1 1.0 01011U7 01010U6 0100U5 011U4 11U3 10U2 00U1 Từ mãUi 409/12/2010 Mã hĩa Huffman : khuyết điểm • khi nguồn cĩ nhiều symbols (đầu ra/thơng tin ), mã hĩa trở thành cồng kềnhƯmã hĩa Hufman + chiều dài mã hĩa cố định . • vẫn cĩ dư thừa và dư thừa là lớn so với tập nhỏ thơng tin Ưnhĩm nhiều thơng tin đơc lập 419/12/2010 Mã hĩa Huffman : khuyết điểm • Ví dụ 9.8 và 9.9 ([2],pp. 437-438) • nhĩm tạo dư thừa nhỏ nhưng số Từ mã tăng lũy thừa, mã hĩa trở thành phức tạp hơn và trì hỗn phát sinh . 429/12/2010 Entropy Ví dụ 2 • Đua ngựa với 8 con ngựa, với xác suất thắng ½, ¼, 1/8, 1/16, 1/64, 1/64, 1/64, 1/64 • Entropy H(X) = 2 bits • Bao nhiêu bits cần thiết? • (a) Chỉ số mỗi con ngựaỴ log8 = 3 bits • (b) gán mã hĩa ngắn hơn đến con ngựa với khả năng cao hơn : 0, 10, 110, 1110, 111100, 111101, 111110, 111111 Ỵ chiều dài mơ tả trung bình = 2 bits! 439/12/2010 Entropy • Cần ít nhất H(X) bits để đại diện X • H(X) là Biên thấp on chiều dài miêu tả theo yêu cầu • Entropy = sự ko chắc chắn của biến ngẫu nhiên 449/12/2010 Entropy kết hợp và điều kiện • entropy kết hợp : H(X,Y) = ∑x ∑y p(x,y) log p(x,y) • mở rộng đơn giản của entropy đến 2 RVs • entropy điều kiện : H(Y|X) = ∑x p(x) H(Y|X=x) = ∑x ∑y p(x,y) log p(y|x) Ỵ“Entropy của Y Nếu X được biết?” • Dễ kiểm chứng: Ỵ Nếu X, Y độc lập , H(Y|X) = H(Y) Ỵ Nếu Y = X, H(Y|X) = 0 H(Y|X) = Thơng tin thêm giữa X & Y • Thực tế : H(X,Y) = H(X) + H(Y|X) 459/12/2010 Thơng tin tương hỗ • I(X;Y) = H(X) – H(X|Y) = suy giảm entropy do biến khác • I(X;Y) = ∑x ∑y p(x,y) log p(x,y)/{p(x)p(y)} • “Bao nhiêu Thơng tin về Y chứa trong X?” • Nếu X,Y độc lập , I(X;Y) = 0 • Nếu X,Y giống nhau , I(X;Y) = H(X) = H(Y) • đối xứng và khơng âm 469/12/2010 Thơng tin tương hỗ Quan hệ giữa entropy, Thơng tin kết hợp và tương hỗ 479/12/2010 Thơng tin tương hỗ • I(X;Y) đo lường sự tương tự giữa X và Y • sử dụng rộng rãi trong xử lý ảnh /tín hiệu • Ảnh y khoa Ví dụ : – đăng ký ảnh dựa trên MI • tại sao ? MI ko nhạy cảm với độ lợi và bias 489/12/2010 Bài tập về nhà 1 • tính tốn H(X) để nguồn rời rạc ko nhớ cĩ 6 symbols với xác suất : PA=1/2, PB=1/4, PC=1/8, PD=PE=1/20,PF=1/40 • tìm lượng Thơng tin chứa trong thơng tin ABABBA và FDDFDF và so sánh với lượng Thơng tin mong đợi trong 1 thơng điệp 6-symbol. 499/12/2010 Bài tập về nhà 2 • Một nguồn dữ liệu cĩ 16 symbols xác suất bằng nhau, mỗi symbol 1ms . Symbols phát sinh trong khối 15, cách nhau khoảng 5-ms. Tìm tốc độ nguồn symbol . 509/12/2010 Bài tập về nhà 3 • Tìm mã Shannon-Fano của nguồn trong Bài tập về nhà 1, và tính độ hiệu quả. 519/12/2010 Tham khảo [1]. R. E. Ziemer & W. H. Transter, “Information Theory and Coding”, Principles of Communications: Systems, Modulation, and Noise, 5th edition. John Wiley, pp. 667-720, 2002. [2]. A. Bruce Carlson, “Communications Systems”, Mc Graw-Hill, 1986, ISBN 0-07- 100560-9 [3]. S. Haykin, “Fundamental Limits in Information Theory”, Communication Systems, 4th edition, John Wiley & Sons Inc, pp. 567-625, 2001