Bài giảng Kỹ thuật truyền số liệu - Chương 2: Truyền dẫn số - Nguyễn Thị Quỳnh Hoa

Nội dung text: Bài giảng Kỹ thuật truyền số liệu - Chương 2: Truyền dẫn số - Nguyễn Thị Quỳnh Hoa

1. Chương 2 Truyền dẫn số
2. Sơ đồ khối chức năng của hệ thống thông tin số đầy đủ
3. Chức năng của các khối • Khối định dạng: làm nhiệm vụ chuyển đổi tín hiệu tương tự sang dãy từ mã số. • Khối mã hóa: nguồn làm giảm số bit nhị phân yêu cầu để truyền bản tin . • Khối mật mã hóa: làm nhiệm vụ mật mã hóa bản tin gốc nhằm mục đích an ninh • Khối mã hóa kênh: làm nhiệm vụ đưa them các bit dư vào tín hiệu số theo một quy luật nào đấy • Giải mã nguồn,giải mật mã và giải mã hóa kênh được thực hiện ở bộ thu ,các quá trình này ngược với quá trình mã hóa bên bộ phát.
4. tt • Khối ghép kênh: giúp cho tuyến truyền thông tin có thể cùng chia sẻ một đường truyền vật lý chung như là cáp,đường truyền vô tuyến • Khối điều chế: giúp cho dòng tín hiệu số có thể truyền qua một phương tiện vật lý cụ thể theo một tốc độ cho trước,với mức độ méo chấp nhận được,yêu cầu một băng thông tần số cho phép. • Khối đa truy cập: liên quan đến các kỹ thuật hoặc nguyên tắc nào đó,cho phép nhiều cặp thu phát cùng chia sẻ một phương tiện vật lý chung
5. → Khái niệm mã hóa • Cho nguồn tin rời rạc X sinh ra N tin hay ký tự độc lập (x 1,x 2,.,x i, ,x N).Xét một tập hợp M có M phần tử hữu hạn (m 1,m 2, ,m q). • Mã hóa (encoding) nguồn tin X bằng tập M có nghĩa là biến đổi mỗi tin x của nguồn tin X thành một tập các phần tử thuộc M nhằm thỏa mãn một yêu cầu nào đó của hệ thống thông tin: • Phép biến đổi ngược lại được gọi là giải mã (decoding).
6. Các tham số cơ bản của mã hóa: • Tập M được gọi là mã hiệu(code),các phần tử m gọi là ký hiệu mã (symbol),số ký hiệu mã khác nhau trong mã gọi là cơ số của mã • Dãy liên tục các ký hiệu mã dùng để mã hóa một tin của nguồn được gọi là từ mã (codeword) • Số ký hiệu mã có trong một từ mã được gọi là độ dài của từ mã (codeword length) • Khoảng cách mã (distance),ký hiệu là d,là số ký hiệu cùng vị trí khác nhau giữa hai từ mã dài bằng nhau
7. Các phương pháp biểu diễn mã a/Phương pháp liệt kê: • Chỉ cần liệt kê các tin của nguồn và các từ mã tương ứng. • Ví dụ: nguồn tin có 8 tin (ký tự),các tin được mã hóa như bảng dưới đây:
8. Các phương pháp biểu diễn mã(tt) b/Phương pháp ma trận: • Từ ví dụ trên,ta thấy:có những từ mã là tổ hợp tuyến tính của các từ mã khác.Chẳng hạn: • Ví dụ ma trân sinh tương ứng với bảng mã trên là :
9. Các phương pháp biểu diễn mã(tt) c/Phương pháp cây : • Cây mã(code tree) – nút gốc (root node), 0 1 – nút lá (leaf node) và các – nút nhánh (branch). • Mỗi nhánh mang một ký hiệu mã,đó là giá trị của nhánh. • Nhánh được bắt đầu ở nút mức i và kết thúc ở nút mức i+1. • Từ mỗi nút nhánh phân ra tối đa q nhánh. • Từ mã bao gồm các ký hiệu mã là giá trị của các nhánh theo thứ tự đi từ nút gốc qua các nút nhánh đến nút lá.
10. Ví dụ • Hình dưới đây là ví dụ về cây mã cho bộ mã gồm các từ mã là 00, 01, 10, 1101, 11001
11. Các phương pháp biểu diễn mã(tt) d/Phương pháp đa thức: • Phương pháp này dùng làm mô hình toán để biểu diễn mã vòng • Từ mã k bit m k-1m k-2 m 2m 1m 0 (theo thứ tự từ trái qua phải là msb đến lsb) có thể được biểu diễn bằng đa thức sau: • Ví dụ từ mã nhị phân 1101001 có thể biểu diễn bằng đa thức:
12. Mục đích của mã hóa • Định dạng: để chuyển tin từ dạng gốc tự nhiên sang dạng chuẩn ví dụ sang dạng số PCM. • Mã hóa đường: để đảm bảo dạng song của ký tự truyền đi phù hợp với các đặc điểm của kênh truyền. • Mã hóa nguồn (source encoding): nhằm giảm số ký tự trung bình yêu cầu để truyền bản tin. • Mật mã hóa (encryption): để mã hóa bản tin bằng một khóa mật mã nhằm tránh sự thâm nhập trái phép,đảm bảo độ an toàn cho thông tin. • Mã hóa kênh truyền (channel encoding): cho phép bên thu có thể phát hiện,kể cả sửa được các lỗi trong bản tin thu để tăng độ tin cậy của thông tin.Do những đặc điểm riêng,phần mất mã hóa sẽ không được đề cập trong môn học này.
13. Điều mã xung (Pulse code modulation- PCM) • Mã hóa: là một phương pháp biến đổi tín hiệu tương tự sang tín hiệu số trong đó thông tin đầu vào biến đổi theo mã tín hiệu thành các tổ hợp bit nối tiếp ở đầu ra
14. a/ Lấy mẫu và giữ mẫu • Rời rạc hóa tín hiệu theo thời gian, thay vì truyền tín hiệu f(t) liên tục theo thời gian thì ta chỉ phải truyền tín hiệu tại các thời điểm f(Ts), f(2Ts), f(3Ts)
15. tt • Ts : là chu kỳ lấy mẫu, thỏa mãn định lý lấy mẫu • Định lý lấy mẫu (Shannon) : Nếu một tín hiệu f(t) có phổ tần hữu hạn, fm là thành phần phổ có tần số cao nhất thì các mẫu được lấy với chu kỳ Ts 1/2fm. • Chức năng của bộ lấy mẫu trong bộ phát PCM là lấy mẫu một cách chu kỳ
16. tt • Có hai kiểu lấy mẫu tuỳ theo dạng của đỉnh độ rộng xung • + Lấy mẫu tự nhiên • + Lấy mẫu đỉnh phẳng.
17. b/ Lượng tử hóa • Lượng tử hóa biên độ: là các ánh xạ các mẫu tín hiệu vào có biên độ liên tục trên một tập hữu hạn các mức biên độ
18. tt • Đặc điểm: + Rời rạc hóa tín hiệu + Ép thang đo vào dải tín hiệu + Đo biên độ mẫu tín hiệu và làm tròn tín hiệu đó, thành một 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.
19. tt • : Bước lượng tử hóa
20. c/ Mã hóa • Mã hoá là một quá trình so các giá trị rời rạc nhận được bởi quá trình lượng tử hoá với các xung mã. • Thông thường các mã nhị phân được sử dụng cho việc mã hoá là các mã nhị phân tự nhiên, các mã Gray (các mã nhị phân phản xạ), và các mã nhị phân kép.
21. tt a/ Tín hiệu tương tự liên tục b/ Xung PAM sau lấy mẫu 0111 0110 0101 0100 0011 0010 0001 0000 1000 1001 1010 c/ Tín hiệu thu được sau khi lượng tử hóa
22. tt • Dãy xung PCM thu được: 0011 0100 0101 0110 0110 0111 0111 0111 • Mã hóa tín hiệu hai mức bit 0= 0V, bit 1= +5V
23. Định dạng tín hiệu số • 1/Các yếu tố cần xem xét khi chọn mã đường • 2/Một số loại mã đường phổ biến
24. Định dạng tín hiệu số • 1/Các yếu tố cần xem xét khi chọn mã đường • 2/Một số loại mã đường phổ biến
25. 1/Các yếu tố cần xem xét khi chọn mã đường: • Thành phần một chiều DC : Nếu trong thành phần của mã đường có chứa thành phần DC thì thành phần này sẽ bị ngăn lại gây méo tín hiệu thu khi đường truyền kết nối AC như dùng tụ điện,biến áp. • Băng thông : Băng thông của mã đường càng nhỏ sẽ càng tiết kiệm được băng thông • Tỷ lệ lỗi bit BER : càng nhỏ càng tốt • Tính trong suốt (transparancy) : phải bảo đảm tính trong suốt có thể truyền chính xác tới bên thu. • Khả năng dễ dàng khôi phục đồng hồ • Khả năng tự phát hiện lỗi : Căn cứ vào quy luật mã hóa để phát hiện lỗi. • Đơn giản trong việc thực hiện mã hóa và giải mã.
26. Định dạng tín hiệu số • 1/Các yếu tố cần xem xét khi chọn mã đường • 2/Một số loại mã đường phổ biến
27. 2/Một số loại mã đường phổ biến: • a/Mã Unipolar • b/Mã Polar • c/Mã Bipolar • d/Mã Manchester • e/Mã HDB3
28. 2/Một số loại mã đường phổ biến: a/Mã Unipolar : • Bit 1 biểu diễn bởi mức điện áp cap (+V), • Bit 0 biểu diễn bởi mức 0 gọi là space. b/Mã Polar : • Bit 1 biểu diễn bởi mức cao (+V), • Bit 0 biểu diễn bởi mức thấp (-V) c/Mã Bipolar : • Dùng 3 mức điện áp để biểu diễn hai loại bit nhị phân • +Dòng bit 1 biểu diễn bởi sự thay đổi mức luân phiên (+V,-V) • +Dòng bit 0 biểu diễn bởi mức 0
29. tt d/Mã Manchester : • Bit 1 biểu diễn bởi mức +V trong một nửa đầu và –V trong một nửa sau. • Bit 0 biểu diễn bởi mức –V trong một nửa đầu và +V trong một nửa sau. e/Mã HDB3 : • Là một loại mã Bipolar nhưng khi trong dòng bit PCM có xuất hiện 4 bit 0 liên tiếp thì thay 4 bit 0 đó bằng một cụm 4 bit đặc biêt.Cụm 4 bit đặc biệt đó là 000V hay B000V trong đó B là bit tuân theo luật bipolar,V là bit trái luật bipolar(+V,+V hoặc –V,-V).
30. Cực tính của xung Số bít 1 từ lần thay trước đó thế cuối cùng Lẻ chẵn - 000- +00+ + 000+ -00-
31. Mã hóa nguồn • Nguồn tin có 2 loại chính : +nguồn liên tục(continuos source) như nguồn âm thanh,nguồn video +nguồn rời rạc (discrete source) như nguồn dữ liệu từ máy tính • Do đó có hai kỹ thuật mã hóa nguồn chính là +mã hóa nguồn liên tục +mã hóa nguồn rời rạc. • Nguyên tắc của mã hóa nguồn rời rạc là mã hóa các ký tự có xác suất sinh ra lớn bằng các từ mã ngắn và mã hóa các ký tự có xác suất sinh ra bé bằng các từ mã dài.Loại mã này gọi là mã hóa thống kê(statistical encoding)
32. Lý thuyết tin • Đo tin tức • Entropy của nguồn • Tốc độ lập tin tức • Thông lượng kênh
33. Đo tin tức • Lượng tin liên quan đến giá trị của tin: khả năng dự đoán của tin → một tin có khả năng dự đoán dự đoán càng nhiều thì càng chứa ít tin. • Xác suất càng cao thì bản tin càng chứa ít các tin và ngược lại. • P(bản tin)=1 : không mang tin • P(bản tin)=0 : mang một lượng tin vô hạn
34. • Hàm loga(1/p(i)) được chọn để đánh giá định lượng cho tin.Lượng tin của một tin i là : • Đơn vị đo của lượng tin phụ thuộc vào cơ số của loga • Đơn vị của lượng tin là bit, nat hay harley khi cơ số của loga lần lượt là 2,e,10 • Khi chọn cơ số 2 thì lượng tin của i là :
35. Entropy của nguồn tin • Entropy H được định nghĩa là giá trị trung bình thống kê của lượng tin • Xét một nguồn tin sinh ra M ký tự độc lập thống kê.Entropy của nguồn này là: • Trong đó p(m) là xác suất chon ký tự thứ m • Lý thuyết tin đã chứng minh giá trị lớn nhất của Entropy là:
36. • Đối với nguồn tin ASCII có M=128 thì entropy cực đại là : • Thực tế điều này khó xảy ra • Đối với nguồn tin nhị phân có M=2, nếu p(1)=p; p(0)=1-p thì entropy cực đại của nguồn là :
37. Mã hóa Huffman • Huffman đưa ra thuật toán dựa trên xác suất xuất hiện của các ký tự • Không có tính sửa lỗi nhưng có tính giải mã duy nhất và tức thời • Mã hóa Huffman thực hiện mã hóa sử dụng ít bit hơn cho các ký tự có xác suất xuất hiện cao vì chúng được truyền đi thường xuyên hơn và ngược lại, nhiều bit hơn cho các ký tự có xác suất xuất hiện thấp nên có thể tăng được hiệu suất.
38. Thuật toán Huffman gồm các bước sau : • Sắp xếp các ký tự theo xác suất giảm dần.Gán cho hai ký tự có xác suất xuất hiện thấp nhất với hai nhánh (0) và (1) của cây mã.Từ hai ký tự có xác suất thấp nhất giảm còn một ký tự với xác suất bằng tổng của hai xác suất. • Lặp lại từ bước 1 cho đến khi chỉ còn lại một ký tự duy nhất với xác suất là 1. • Duyệt cây mã để tìm ra từ mã tương ứng với từng ký tự của nguồn.
39. B1: Sắp xếp ký tự theo thứ tự xs giảm dần Tin A B C D E F G H Từ 000 001 010 011 100 101 110 111 mã Xác 0,1 0,18 0,4 0,05 0,06 0,1 0,07 0,04 suất
40. B1: Sắp xếp ký tự theo thứ tự xs giảm dần C 0,4 B 0,18 A 0,1 F 0,1 G 0,07 E 0,06 D 0,05 H 0,04
41. B2: Gán 2 ký tự có xs thấp nhất thành một ký tự có xs bằng tổng của 2 xs đó rồi làm lại B1 C 0,4 0,4 0,4 0,4 0,4 0,4 0,6 1 B 0,18 0,18 0,18 0,19 0,23 0,37 0,4 A 0,1 0,1 0,13 0,18 0,19 0,23 F 0,1 0,1 0,1 0,13 0,18 G 0,07 0,09 0,1 0,1 E 0,06 0,07 0,09 D 0,05 0,06 H 0,04
42. B3: Gán cho hai nhánh có xs thấp nhất giá trị 0 và 1 C 0,4 0,4 0,4 0,4 0,4 0,4 0,6 11 B 0,18 0,18 0,18 0,19 0,23 0,37 10,4 0 A 0,1 0,1 0,13 0,18 0,19 10,23 0 F 0,1 0,1 0,1 0,13 0,18 1 0 G 0,07 0,09 0,1 10,1 0 E 0,06 0,07 1 0,09 0 D 0,05 1 0,06 0 H 0,04 0
43. B4: Duyệt cây mã C 0,4 0,4 0,4 0,4 0,4 0,4 0,6 11 B 0,18 0,18 0,18 0,19 0,23 0,37 10,4 0 A 0,1 0,1 0,13 0,18 0,19 10,23 0 F 0,1 0,1 0,1 0,13 0,18 1 0 G 0,07 0,09 0,1 10,1 0 E 0,06 0,07 1 0,09 0 D 0,05 10,06 0 H 0,04 0 F(1111) G(1011) C(0) B(110) A(100)
44. Tin A B C D E F G H Từ 100 110 0 11101 100 1010 1111 11100 mã Xác 0,1 0,18 0,4 0,05 0,06 0,1 0,07 0,04 suấ t
45. Cây mã
46. tt • Nhìn vào cây mã ta thấy kết quả mã hóa Huffman của nguồn tin trên như sau: • Độ dài từ mã trung bình bây giờ là : • Vậy độ lợi mã hóa là : • Vậy hiệu suất của đường truyền đã tăng từ 85% lên 97,7%
47. Mã hóa nguồn Huffman • “AN TOAN GIAO THONG”
48. Mã hóa nguồn Shanon_Fano • B1 : Sắp xếp tất cả các tin của nguồn tin X theo thứ tự xs xuất hiện tăng dần (giảm dần) • B2 : Chia toàn bộ các tin của nguồn tin thành 2 nhóm có tổng xs xấp xỉ nhau • B3 : Gán cho mỗi nhóm một chữ mã nhị phân (0,1) • B4 : Lặp lại các bước 2,3 cho đến khi mỗi nhóm còn lại một ký hiệu • B5 : Duyệt từ mã từ gốc đến ngọn