›
›

Bài giảng Truyền thông số (Tuần 9)

ppt 45 trang huongle 3110
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Truyền thông số (Tuần 9)", để 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_truyen_thong_so_tuan_9.ppt

Nội dung text: Bài giảng Truyền thông số (Tuần 9)

  1. TRUYỀN THÔNG SỐ DIGITAL COMMUNICATION Week 9
  2. Reference • “Digital communications: Fundamentals and Applications” by Bernard Sklar • Telecommunication Networks - Information Theory, Vinh Dang (*) Hồ Văn Quân – Khoa CNTT – ĐH Bách Khoa TpHCM [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
  3. Tuần trước • Bộ giải mã Maximum likelihood • Quyết định mềm / cứng (soft decisions and hard decisions) • Giải thuật Viterbi
  4. Block diagram of the DCS Information Rate 1/n Modulator source Conv. encoder m=(m,m, ,m, ) U=G(m) 12i =(U,U,U, ,U, ) Channel Inputsequence 1 23i Codeword sequence U = u, ,u, ,u i 1ijini Branch rd wo (n coded bits) Information Rate 1/n Demodulator sink Conv. decoder mˆ=(mˆ,mˆ, ,mˆ, ) Z=(Z,Z,Z, ,Z, ) 1 2 i 123i received sequence Z =z, ,z, ,z i 1ijini Demodulatoroutputs n outputs perBranch d wor forBranch d i wor
  5. Quyết định mềm / cứng
  6. Giải thuật Viterbi • Giải thuật Viterbi biểu diễn giải mã Maximum likelihood. • Nó tìm 1 đường có sự tương quan lớn nhất hoặc khoảng cách nhỏ nhất. – Là 1 quá trình lặp. – Trong mỗi bước tính toán, nó chỉ giữ đường nào có khoảng cách nhỏ nhất, gọi là đường sống (the survivor).
  7. Ví dụ ½ Conv. code Input bits Tail bits 1 0 1 0 0 Output bits 11 10 00 10 11 0/00 0/00 0/00 0/00 0/00 1/11 1/11 1/11 0/11 0/11 0/11 0/10 1/00 0/10 0/10 1/01 1/01 0/01 0/01 1/01 t1 t2 t3 t4 t5 t6
  8. VD 1 hard-decision Viterbi decoding mˆ = (10000) Z=(1110111001) Uˆ=(1110110011) m = (10100) U=(1110001011) 0 2 2 1 3 2 0 1 1 1 2 1 0 0 0 3 2 0 1 1 1 2 Partial metric 0 0 0 3 2 (S(ti),ti ) 1 2 2 Branch metric 2 1 3 1 t1 t2 t3 t4 t5 t6
  9. VD 1 soft-decision Viterbi decoding 22−2−22−2 ˆ Z=(1,,, , ,1,,−1, ,1) m = (10100) 33333 3 Uˆ=(1110001011) m = (10100) U=(1110001011) 0 -5/3 -5/3 0 -5/3 -1/3 10/3 1/3 1/3 -1/3 14/3 0 1/3 1/3 5/3 5/3 5/3 8/3 1/3 -5/3 -1/3 4/3 1/3 5/3 3 2 13/3 -4/3 5/3 -5/3 1/3 5/3 10/3 -5/3 t1 t2 t3 t4 t5 t6
  10. Tuần này • Mã hóa kênh (Channel Coding): – Sự đan xen (Interleaving) – Mã ghép (Concatenated codes) – Mã Turbo (Turbo Codes) • Mã hóa nguồn (Source Coding): – Nguồn (sources) – Entropy và Information rate – Lý thuyết mã hóa nguồn (Thuyết Shannon) – Hiệu quả của mã hóa nguồn – Mã Shannon-Fano – Mã Huffman
  11. Sự đan xen (Interleaving) • Mã chập (Convolutional codes) thích hợp cho kênh truyền không nhớ (memoryless channels) vì các lỗi là ngẫu nhiên (random error events). • Trên thực tế, có loại lỗi chùm (bursty errors) vì kênh truyền có nhớ (channel with memory). – Ví dụ: lỗi trong kênh multipath fading, lỗi do nhiễu • Sự đan xen (Interleaving) giúp cho kênh truyền trở thành như kênh truyền không nhớ (memoryless channel) ở bộ giải mã.
  12. Interleaving • Sự đan xen được thực hiện bằng cách chia các coded symbols theo thời gian trước khi truyền đi. • Quá trình ngược lại tại đầu thu gọi là giải đan xen (deinterleaving). • Sự đan xen giúp cho lỗi chùm (bursty errors) giống như trở thành lỗi ngẫu nhiên (random errors) → có thể dùng mã chập. • Các loại đan xen: – Đan xen khối (Block interleaving) – Đan xen chồng chập/chéo (Convolutional or cross interleaving)
  13. Ví dụ minh họa – Xét 1 mã có 3 coded bits. – Nếu 1 chùm lỗi có độ dài 3 bit: A1 A2 A3 B1 B2 B3 C1 C2 C3 2 errors – Nếu dùng 1 khối đan xen 3X3: A1 A2 A3 B1 B2 B3 C1 C2 C3 A1 B1 C1 A2 B2 C2 A3 B3 C3 Interleaver Deinterleaver A1 B1 C1 A2 B2 C2 A3 B3 C3 A1 A2 A3 B1 B2 B3 C1 C2 C3 1 errors 1 errors 1 errors
  14. Ví dụ Đan xen chồng chập
  15. Mã ghép (Concatenated codes) • Mã ghép dùng 2 lần mã hóa, gọi là mã hóa trong và mã hóa ngoài (có tốc độ cao hơn) - an inner code and an outer code (higher rate). – Thông thường 1 mã ghép dùng mã chập và giải mã Viterbi ở phần mã hóa trong, mã Reed-Solomon ở phần mã hóa ngoài • Mã ghép giảm sự phức tạp, tăng hiệu quả sửa lỗi. Input Outer Inner Interleaver Modulate data encoder encoder Channel Output Outer Deinterleaver Inner Demodulate data decoder decoder
  16. Mã Turbo (Turbo codes) • Mã Turbo là mã ghép nhưng có thêm giải thuật lặp (iterative algorithm) • Dùng soft-decision → lặp nhiều lần để có giá trị tin cậy hơn.
  17. Ví dụ 1 dạng mã Turbo: RSC code
  18. Mã hóa nguồn (Source Coding) • Nguồn (sources) • Entropy và Information rate • Lý thuyết mã hóa nguồn (Thuyết Shannon) • Hiệu quả của mã hóa nguồn • Mã Shannon-Fano • Huffman Coding
  19. Nguồn tin - Sources • Nguồn tin ta đang xét là nguồn rời rạc (discrete sources) có 1 chuỗi X(k), k =1 N symbols • Xác suất của mỗi symbol Xj là P(XJ) • Ta định nghĩa I(XJ) - self-information là đơn vị thông tin: I(X j ) = −log 2 ( p j )
  20. Nguồn tin - Sources • Trị trung bình của các symbol gọi là source entropy: N N bit/symbol H(X ) = E{I(X j )} =  p j I(X j ) = − p j log 2 ( p j ) j=1 j=1 • E{X} là giá trị trung bình (expected value) của X. • Source entropy H(X): lượng thông tin trung bình của nguồn tin X là lượng tin trung bình chứa trong một kí hiệu bất kỳ Xj của nguồn tin X.
  21. Entropy và Information rate • Entropy = information = uncertainty • Nếu 1 tín hiệu hoàn toàn có thể tiên đoán được (completely predictable), thì entropy = 0 và không có thông tin • Entropy = là số bits trung bình đòi hỏi để truyền tín hiệu 0 H(X) log 2 N
  22. Ví dụ(*): Trả lời:
  23. Lý thuyết mã hóa nguồn • Tốc độ nguồn thông tin - Source information rate (bit/s): Rs = rH(X) (bit/s) – H(X): entropy nguồn (bits/symbol) – r : tốc độ symbol (symbol rate) (symbols/s) • Giả sử nguồn này là đầu vào của 1 kênh : – C: dung lượng - capacity (bits/symbol) – S: tốc độ symbol - available symbol rate (symbols/s) – S.C = bits/s
  24. Mã hóa nguồn (t.t) • Thuyết Shannon (noiseless coding theorem): – Cho một kênh truyền và một nguồn phát sinh thông tin. Ta có thể mã hóa nguồn bằng cách phát trên kênh truyền này khi nguồn tin có tốc độ nhỏ hơn dung lượng kênh truyền. – “Given a channel and a source that generates information at a rate less than the channel capacity, it is possible to encode the source output in such a manner that it can be transmitted through the channel”
  25. Ví dụ Source encoding Discrete Source Binary binary encoder channel C = 1 bit/symbol source S = 2 symbols/s Tốc độ symbol nguồn (Source symbol SC = 2 bits/s rate) = r = 3.5 symbols/s • Cho nguồn nhị phân rời rạc: A (p=0.9), B (p=0.1) • Source symbol rate (3.5) >channel capacity (2)  nguồn symbols không thể truyền đ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 • Có thể truyền đi bằng cách mã hóa nguồn để giảm tốc độ symbol trung bình (average symbol rate)
  26. • Codewords được nhóm thành n-symbol groups of source symbols • Quy luật: – Codewords ngắn nhất gán cho nhóm có xác suất xảy ra nhiều nhất (Shortest codewords for the most probable group) – Codewords dài nhất gán cho nhóm có xác suất xảy ra ít nhất (Longest codewords for the least probable group) • Có n -symbol groups tức là có n bậc mở rộng (n th- order extension of original source)
  27. First-Order extension Source P () Codeword [P()].[Number of Code symbol Symbols] A 0.9 0 0.9 B 0.1 1 0.1 L=1.0 2n L: độ dài code trung bình (average code length) L =  p(xi )*li th i=1 p(xi): xác suất của symbol thứ i th li : độ dài của codeword tương ứng với symbol thứ i
  28. Second-Order extension Grouping 2 source symbols at a time: Source symbol P () Codeword [P()].[Number of Code 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 =  p(xi )*li i=1
  29. Second-Order extension L 1.29 = = 0.645 code symbols/so urce symbol n 2 Tốc độ symbol (symbol rate) tại ngõ ra bộ mã hóa: L r = 3.5(0.645) = 2.258 code symbols/sec n >2 → Tốc độ symbol > dung lượng kênh là 2 symbols/second ➔ Ta tiếp tục làm mã hóa mở rộng bậc 3 (the third-order extension)
  30. Third-Order extension Grouping 3 source symbols at a time: Source P () Codeword [P()].[Number of Code symbol 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
  31. Third-Order extension L 1.598 = = 0.533 code symbols/source n 3 symbol The symbol rate at the encoder output: L r = 3.5(0.533) =1.864 code symbols/se cond n ➔ Kênh truyền chấp nhận tốc độ này
  32. Hiệu quả của mã hóa nguồn • Efficiency là thước đo đo hiệu quả của mã hóa nguồn L L eff = min = min L n  p(xi )li i=1 H (X ) where H(X): entropy nguồn Lmin = log 2 D D : số symbols trong coding alphabet H (X )  eff = L log 2 D H (X ) or eff = for a binary alphabet L
  33. Hiệu quả của mã hóa nguồn nhị phân • Entropy của nguồn mở rộng n bậc : H (X n)=n*H (X) • Hiệu quả của nguồn mở rộng: n.H (X ) eff = L
  34. Mã Shannon-Fano[1] Gồm 3 bước: 1. Liệt kê source symbols theo thứ tự xác suất giảm dần 2. Chia chúng thành 2 nhóm nhỏ: “0” đặt cho nhóm trên và “1” cho nhóm dưới 3. Tiếp tục chia tới khi không thể chia nữa
  35. Ví dụ về Shannon-Fano Coding Ui pi 1 2 3 4 5 Codewords 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
  36. Shannon-Fano coding 7 L =  pili = 2.45 i=1 7 H (U ) = − pi log 2 pi = 2.37 i=1 H (U ) 2.37 eff = = = 0.97 L 2.45
  37. Huffman Coding [1][2][3] Thực hiện theo 3 bước 1. Liệt kê source symbols theo thứ tự xác suất giảm dần. Hai source symbols có xác suất nhỏ nhất được gán 0 và 1. 2. Hai source symbols này kết hợp thành 1 source symbol mới có xác suất bằng tổng 2 xác suất gốc. Xác suất mới được ghi vào The new probability is placed in the list in accordance with its value. 3. Lặp lại cho tới khi xác suất mới kết hợp cuối cùng = 1.0.
  38. Examples of Huffman Coding 0 1.0 U p i i 1 0 Ui Codewords 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 U .06 0 1 6 .07 U 01011 U .01 7 7 1
  39. Khuyết điểm của Huffman Coding • Khi nguồn có nhiều symbols thì mã Huffman trở nên quá lớn. • Vẫn còn nhiều sự dư thừa (redundancy) • Số codewords tăng theo cấp số mũ (exponentially), mã trở nên phức tạp và tăng độ trì hoãn.
  40. Bài tập • Một nguồn rời rạc có 3 sysbols: A, B, và C với xác suất tương ứng là 0.9, 0.08 và 0.02. Tìm entropy của nguồn
  41. Bài tập Vẽ sơ đồ trạng thái (dùng trellis diagram) của hệ thống RSC trên
  42. Next time 1. Ngày 3/5 nhà trường nghỉ 2. Ngày 10/5: buổi học cuối: – Công bố điểm giữa kỳ (điểm bài tập về nhà) – Học tiếp + Ôn tập
  43. Bài tập nộp cho GV • Cách 1: nộp trực tiếp cho GV (sau mỗi buổi học) • Cách 2: gửi email tới: truyenthongsodtvt@gmail.com • Thời hạn nộp bài: thứ ba ngày 26 tháng 4 • Trong email và file nộp ghi rõ họ tên và mã số SV • Điểm bài tập: 30% tổng điểm • Hạn chót nhận email: thứ 2 ngày 2/5
  44. Bài tập nộp cho GV Chọn 1 trong các bài sau: 1. Tìm hiểu về Non-coherent detection (D-PSK và Bin D-PSK) 2. Tìm hiểu về Cyclic block codes 3. Dùng Matlab mô phỏng để so sánh sự khác nhau của các kiểu điều chế (vẽ SNR vs PE)