›

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

ppt 51 trang huongle 5180
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng viễn thông-Lý thuyết thông tin", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_mang_vien_thong_ly_thuyet_thong_tin.ppt

Nội dung text: Bài giảng Mạng viễn thông-Lý thuyết thông tin

  1. Mạng viễn thông - lý thuyết thông tin By: Vinh Dang 6/12/2021 1
  2. 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 6/12/2021 2
  3. 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ể 6/12/2021 3
  4. 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. 6/12/2021 4
  5. Viễn thông thời kỳ đầu ◼ trống và còi ◼ khói/Tín hiệu lửa ◼ ánh sáng trống khói ◼ bồ câu Tower using mirrors bồ câu 6/12/2021 5 horn
  6. 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 A BTS (Mobile ◼ truyền thông vệ tinh Communication) 6/12/2021 VINASAT-1 satellite 6
  7. Hệ thống truyền thông không dây hệ thống truyền thông di động hệ thống truyền thông dữ liệu Mạng viễn thông Hệ thống truyền thông vệ tinh 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 6/12/2021 7
  8. ◼ 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. 6/12/2021 8
  9. Mạng viễn thông ◼ Mạng viễn thông được chia thành: 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 thiết bị đầu cuối thuê bao Premises Equipment (CPE)  thiết bị chuyển mạch và thiết bị truyền nhận cùng nhau từ 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. 6/12/2021 9
  10. AN N T Transport AN AN N N T T SIEMENS NIXDORF truy nhập mạng (AN) với đầu cuối thuê bao Exchange AN (CPE) N T 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 6/12/2021 • tín hiệu kết nối để truyền thông tin điều khiển 10
  11. Khái niệm cơ bản ◼ sơ đồ khối của hệ thống truyền thông số mã hóa kênh nguồn mã hóa bộ điều kênh truyền nguồn chế truyền nhiễu bộ giải đích bộ giải bộ giải điều mã mã kênh chế nguồn 6/12/2021 11
  12. lý thuyết thông tin? ◼ lý thuyết thông tin cugn 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 Shan không có n: “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, 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” 6/12/2021 12
  13. đ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 6/12/2021 13
  14. đo lường Thông tin ◼ 3 kết quả: thắng, hòa, thua 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 Thông tin nhiều hơn Tương đối thấp GĐT-LA 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 ◼ Sự kiện càng ít khả năng, càng chưa nhiều thông tin ◼ Thông tin định nghĩa toán học như thế nào? 6/12/2021 14 wins
  15. 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 I( xj )= log a = − log a p ( x j ) (1) px()j đơ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) 6/12/2021 15
  16. 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 ½. 6/12/2021 16
  17. 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 cugn 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 : M (2) H(X ) = E{I(x j )} = − p(x j )log 2 p(x j ) bit/symbol j=1 ◼ Entropy = Thông tin = sự ko chắc chắn ◼ Nếu tín hiệu là hoàn toàn dự đoá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 6/12/2021 17 emittingdisrete
  18. 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 ” 6/12/2021 18
  19. 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 , (3) 0 H(X) log 2 M ◼ 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 6/12/2021 19
  20. chứng minh 0 H(X ) log2 M ◼ 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 H(X ) = − p(x).log p(x) log 2 M X M = − p(xi ).log p(xi ) log 2 M i=1 ◼ Dựa vào bất đẳng thức ln a (a-1) 6/12/2021 20
  21. chứng minh 0 H(X ) log2 M ◼ xem xét: H (X ) − log 2 M = − p(x).log p(x) − log 2 M X M M M 1 = − p(xi ).log 2 p(xi ) −log 2 M. p(xi ) =  p(xi ).log 2 i=1 i=1 i=1 M.p(xi ) M 1 M 1 = log 2 e. p(xi ).ln log 2 e. p(xi ). −1 i=1 M.p(xi ) i=1 M.p(xi ) M 1 H (X ) − log 2 M log 2 e. − p(xi ) i=1 M M 1 M H (X ) − log 2 M log 2 e  −  p(xi ) i=1 M i=1 H (X ) − log 2 M 0 H (X ) log 2 M 1 1 dấu bằng xảy ra khi: =1 p(xi ) = M.p(xi ) M 6/12/2021 21
  22. 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- ) 6/12/2021 22
  23. 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 6/12/2021 23
  24. 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 mã hóa kênh nhị phân nguồn truyền rời rạc nhị phân nguồn tốc độ symbol C = 1 bit/symbol = r = 3.5 symbols/s S = 2 symbols/s 6/12/2021 SC = 2 bits/s 24
  25. 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 6/12/2021 25
  26. 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 6/12/2021 26
  27. mở rộng thứ nhất nguồn P () từ mã [P()].[số mã hóa symbol Symbols] A 0.9 0 0.9 B 0.1 1 0.1 L=1.0 ◼ 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 6/12/2021 27
  28. mở rộng thứ hai nhóm 2 nguồn symbols cùng 1 thời điểm : 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 2n L: trung bình chiều dài mã L =  p(xi )*li th i=1 p(xi): khả năng symbol i của nguồn mở rộng l : chiều dài của từ mã tương ứng với i th 6/12/2021 i 28 symbol
  29. mở rộng thứ hai L 1.29 = = 0.645 code symbols/so urce symbol n 2 tốc độ symbol tại đầu ra bộ mã hóa : L r = 3.5(0.645) = 2.258 mã hóa symbols/sec n >2 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 6/12/2021 29
  30. mở rộng thứ ba nhóm 3 nguồn symbols cùng 1 thời điểm : nguồn P () từ mã [P()].[số của mã hóa Symbols] symbol 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 6/12/2021 30
  31. mở rộng thứ ba L 1.598 = = 0.533 mã hóa symbols/nguồn n 3 symbol tốc độ symbol tại đầu ra bộ mã hóa : L r = 3.5(0.533) =1.864 code symbols/se cond n tốc độ này là chấp nhận được bởi kênh truyền 6/12/2021 31
  32. 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 L L eff = min = min L n  p(xi )li i=1 H (X ) L = min Trong H(X): entropy của nguồn log 2 D đó D: số symbols trong coding alphabet H (X )  eff = L log 2 D H (X ) or eff = Cho alphabet nhị L phân 6/12/2021 32
  33. 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: n.H (X ) eff = L 6/12/2021 33
  34. Biểu diễn của L/n L 1.0 n ▪L/n luôn vượt quá entropy nguồn và 0.8 hội tụ đến entropy nguồn khi n lớn 0.6 ▪giảm chiều dài 0.469 H(X)trung bình từ mã dẫn 0.4 đến tăng độ phức tạp của mã hóa 0.2 0 n 0 1 2 3 4 6/12/2021 34
  35. 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ụ : 6/12/2021 35
  36. Ví dụ Mã hóa Shannon-Fano Ui pi 1 2 3 4 5 Từ mã U1 .34 0 0 00 U2 .23 0 1 01 U3 .19 1 0 10 U4 .1 1 1 0 110 U5 .07 1 1 1 0 1110 U6 .06 1 1 1 1 0 11110 U7 .01 1 1 1 1 1 11111 6/12/2021 36
  37. Mã hóa Shannon-Fano 7 L =  pili = 2.41 i=1 7 H (U ) = − pi log 2 pi = 2.37 i=1 H (U ) 2.37 eff = = = 0.98 L 2.41 ▪ 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. 6/12/2021 37
  38. 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ụ : 6/12/2021 38
  39. Ví dụ của Mã hóa Huffman 0 1.0 U p i i 1 0 Ui Từ mã U1 .34 .58 U1 00 1 0 U2 10 U2 .23 .42 U3 .19 U3 11 0 1 .24 U4 011 U .1 4 1 0 U5 0100 U5 .07 .14 U6 01010 0 1 U6 .06 .07 U7 01011 U7 .01 6/12/2021 1 39
  40. 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 6/12/2021 40
  41. 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ì hoãn phát sinh . 6/12/2021 41
  42. 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! 6/12/2021 42
  43. 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 6/12/2021 43
  44. 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 6/12/2021 ◼ Thực tế : H(X,Y) = H(X) + H(Y|X) 44
  45. 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 6/12/2021 45
  46. Thông tin tương hỗ Quan hệ giữa entropy, Thông tin kết hợp và tương hỗ 6/12/2021 46
  47. 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 6/12/2021 47
  48. Bài tập về nhà 1 ◼ tính toá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. 6/12/2021 48
  49. 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 . 6/12/2021 49
  50. 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ả. 6/12/2021 50
  51. 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 6/12/2021 51