zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Kỹ Thuật - Công Nghệ

» Kĩ thuật Viễn thông

Bài giảng Truyền dẫn số: Chương 2 - Vũ Thị Thúy Hà

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:127

Báo xấu

8
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Truyền dẫn số - Chương 2: Mã hóa nguồn, cung cấp cho người học những kiến thức như mô hình toán học của nguồn tin; đo lượng tin của nguồn tin; các kỹ thuật mã hóa nguồn rời rạc; các kỹ thuật mã hóa nguồn tương tự; lấy mẫu và điều chế xung; điều chế xung mã. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Truyền dẫn số: Chương 2 - Vũ Thị Thúy Hà

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Bài giảng môn học TRUYỀN DẪN SỐ BM: TH & HT KHOA: VT1 Giảng viên: Vũ Thị Thúy Hà 1 1
Chương 2 MÃ HÓA NGUỒN Nội dung: 2.1 Mô hình toán học của nguồn tin 2.2 Đo lượng tin của nguồn tin 2.3 Các kỹ thuật mã hóa nguồn rời rạc 2.4 Các kỹ thuật mã hóa nguồn tương tự 2.5.Lấy mẫu và điều chế xung 2.6 Điều chế xung mã Bài tập 2/11/2017 2 2
Chương 2 MÃ HÓA NGUỒN 2.1 Mô hình toán học của nguồn tin:  Nguồn tin: Nguồn tương tự: tín hiệu ngõ ra có dạng liên tục Nguồn rời rạc: tín hiệu ngõ ra có dạng rời rạc  Nguồn tin tạo ra các bản tin một cách ngẫu nhiên. Với nguồn rời rạc (Discrete source), ngõ ra là chuỗi các biến ngẫu nhiên rời rạc.  Mô hình cho nguồn rời rạc: Giả sử nguồn rời rạc gồm L ký hiệu :{x1, x2,…, xL}, với xác suất tương ứng là {p1,p2,…,pL}. Lúc đó: L p k 1 k  1, k  1,..., L Ví dụ: Nguồn rời rạc nhị phân X sẽ gồm hai ký hiệu: {0,1} và P(X=0)+ P(X=1)=1.  Nguồn rời rạc không nhớ DMS (Discrete Memoryless Source): phát ra chuỗi ký hiệu là độc lập thống kê, nghĩa là: P( xn | xn1 , xn2 ,...)  P( xn ) 2/11/2017 3 3
Chương 2 MÃ HÓA NGUỒN 2.2 Đo lượng tin của nguồn tin: 2.2.1 Lượng tin của nguồn rời rạc:  Tin tức liên quan đến sự ngạc nhiên mà chúng ta cảm nhận khi nhận được bản tin. Bản tin ít có khả năng xảy ra sẽ mang nhiều tin tức hơn. Từ đó, người ta đưa ra khái niệm lượng tin.  Lượng tin:  lượng tin riêng có được khi xuất hiện bản tin xi (xảy ra sự kiện X= xi )  1  I ( xi )  log     log P ( xi )  P ( xi )  • Đơn vị của lượng tin: Tùy vào cơ số hàm logarit (cơ số 2: đơn vị là bit, cơ số e: đơn vị là nat, cơ số 10: Hartley) • Tính chất: i/ I ( xi )  0, 0  pi  1 ii/ I ( xi )  I ( x j ), pi  p j 2/11/2017 4 4
Chương 2 MÃ HÓA NGUỒN 2.2 Đo lượng tin của nguồn tin (tt):  Lượng tin có điều kiện:  lượng tin có được khi sự kiện X = xi xảy ra sau khi quan sát sự kiện Y = yj đã xảy ra. I ( xi | y j )   log P( xi | y j )  Lượng tin tương hỗ:  lượng tin có được về sự kiện X =xi từ việc xảy ra sự kiện Y=yi. P ( xi ) I ( xi , y j )  I ( xi )  I ( xi | y j )   log P ( xi | y j )  Nhận xét: i/ Khi X, Y độc lập thống kê: I(xi,yj) = 0 ii/ I(xi,yj) = I(yj,xi)  lượng tin về sự kiện X = xi có được từ việc xảy ra sự kiện Y = yj giống với lượng tin về sự kiện Y = yj có được từ việc xảy ra sự kiện X = xi. 2/11/2017 5 5
Chương 2 MÃ HÓA NGUỒN 2.2 Đo lượng tin của nguồn tin (tt):  Lượng tin trung bình:  lượng tin trung bình chứa trong một ký hiệu bất kỳ của nguồn L I ( X )   P( xi ) log P( xi ) i 1  Nhận xét: lượng tin trung bình phản ánh được giá trị tin tức của cả nguồn tin. Ví dụ: Một nguồn DMS gồm 2 ký hiệu {x0,x1} với xác suất xuất hiện các ký hiệu tương ứng là 0.99 và 0.01. Lượng tin riêng của x1: I ( x1 )   log 2 [ p( x1 )]   log 2 (0.01)  6.5 [bits / symbol ] Lượng tin trung bình của nguồn: I ( X )  0.99log2 (0.99)  0.01log 2 (0.01)  0.081 [bits / symbol ]  Lượng tin tương hỗ trung bình: L K I ( X , Y )    P ( xi , y j )I ( xi , y j ) i 1 j 1 2/11/2017 6 6
Chương 2 MÃ HÓA NGUỒN 2.2.2 Entropy của nguồn rời rạc:  Giả sử nguồn rời rạc X gồm L ký hiệu {x1, x2,…, xL}, Entropy của nguồn X được định nghĩa là: L L H ( X )   P( xi ) log P( xi )  P( xi ) I ( xi ) i 1 i 1  Nhận xét: • Entropy của nguồn chính là lượng tin trung bình của nguồn đó. • H ( X )  log L .Nếu các ký hiệu của nguồn có xác suất xuất hiện bằng nhau thì Entropy sẽ đạt giá trị cực đại. L 1 1 1 P( xi )  , i  1,..., L  H ( X )   log  log L L i 1 L L • H ( X )  0 . Dấu = xảy ra khi một ký hiệu có xác suất xuất hiện bằng 1, còn xác suất xuất hiện của các ký hiệu còn lại là 0. 2/11/2017 7 7
Chương 2 MÃ HÓA NGUỒN 2.2.3 Entropy của nguồn liên tục:  Giả sử nguồn liên tục X(t) có hàm mật độ phân bố xác suất của hàm mẫu x(t) là p(x). Lúc đó, Entropy của nguồn X được định nghĩa là:  H ( X )    p ( x) log p ( x)dx  Ví dụ: Cho nguồn liên tục X có : 1/ a , 0  x  a p( x)    0 , x  0; x  a Tìm H(X) khi a=1; a=4. Lời giải:  a 1 1 Entropy của nguồn: H ( X )    p( x) log p2 ( x)dx    log 2 dx  log 2 a  0 a a Khi a= 1: H(X)=log21=0 [bits] Khi a= 4: H(X)=log24=2 [bits] 2/11/2017 8 8
Chương 2 MÃ HÓA NGUỒN 2.3 Các phương pháp mã hóa nguồn rời rạc (Nén dữ liệu)  Giả sử nguồn rời rạc X gồm L ký hiệu {x1, x2,…, xL}, với xác suất xuất hiện các ký hiệu tương ứng là {p1,p2,…,pL}. Mã hóa nguồn X chính là quá trình biểu diễn các ký hiệu xi của nguồn bởi các chuỗi bi có chiều dài Ri. (bi = [b1,b2,…,bRi], bi = 0/1) Nguồn rời {xi} Mã hóa {bi}: 0/1 rạc X nguồn  Yêu cầu của bộ mã hóa nguồn: • Các từ mã biểu diễn ở dạng nhị phân. • Quá trình mã hóa sao cho việc giải mã là duy nhất.  Đánh giá hiệu quả của bộ mã hóa nguồn: • Thông qua việc so sánh số lượng bit trung bình dùng để biểu diễn từ mã. • Hiệu suất mã hóa: H (X ) H(X): entropy của nguồn X. L 1  R pR R : chiều dài trung bình của từ mã. i i R i 0 2/11/2017 9 9
Chương 2 MÃ HÓA NGUỒN 2.3 Các phương pháp mã hóa nguồn rời rạc (tt) 2.3.1 Phương pháp mã hóa với từ mã có chiều dài bằng nhau:  Tất cả các ký hiệu của nguồn được mã hóa bằng các từ mã có chiều dài bằng nhau [từ mã R bit].  Quá trình mã hóa không tổn hao, và việc giải mã là dể dàng và duy nhất.  Ví dụ: mã ASCII, mã EBCDIC, mã Baudot,vv…  Quá trình mã hóa: • Giả sử nguồn gồm L ký hiệu đồng xác suất. Ta muốn mã hóa dùng R bit ? • Chọn giá trị của R:  log 2 L , L  2m , m   R  log 2 L   1   , otherwise • Lúc đó, hiệu suất mã hóa: H ( X ) log 2 L   R R o Khi L lũy thừa của 2: log 2 L log 2 L    1  100% R log 2 L 2/11/2017 10 10
Chương 2 MÃ HÓA NGUỒN 2.3.1 Phương pháp mã hóa với từ mã có chiều dài bằng nhau (tt): o Khi L không phải là lũy thừa của 2: log 2 L log 2 L   1 R  log 2 L   1   Khi L lớn thì log2L lớn hiệu suất cao. Ngược lại, khi L nhỏ, hiệu suất sẽ rất thấp  mã hóa từng khối J ký hiệu một lúc.  Quá trình mã hóa J ký hiệu cùng một lúc: • Số ký hiệu có thể có của nguồn: LJ . • Chọn chiều dài từ mã mã hóa: N. Yêu cầu giá trị của N phải thỏa: 2N  LJ  N  log2LJ = Jlog2L Do N phải là số nguyên, nên: N   J log 2 L   1   • Hiệu suất mã hóa: H (X ) JH ( X ) J log 2 L  chọn J lớn thì hiệu suất    R N  J log 2 L   1   sẽ cao (dù cho L nhỏ) 2/11/2017 11 11
Chương 2 MÃ HÓA NGUỒN 2.3.1 Phương pháp mã hóa với từ mã có chiều dài bằng nhau (tt) Ví dụ: Cho nguồn DMS có 100 ký hiệu đồng xác suất. a. Khi mỗi một ký hiệu được mã hóa tại một thời điểm. Tìm R=?  =? • Chiều dài của từ mã: R  log 2 L   1  log 2 100  1  7      Mỗi ký hiệu được biểu diễn bằng từ mã có chiều dài 7 bit. • Hiệu suất mã hóa: H ( X ) log 2 L log 2 100     94.91% R R 7 b. Khi 3 ký hiệu được mã hóa cùng một lúc. Tìm N=?  =? • Chiều dài của từ mã: R   J log 2 L   1  3log 2 100   1  20     • Hiệu suất mã hóa: J log 2 L 3 log 2 100    99.66%  J log 2 L   1   20 Nhận xét: khi xác suất xuất hiện các ký hiệu không bằng nhau, hiệu suất sẽ thấp hơn (do lúc đó H(X) < log2L)  dùng phương pháp mã hóa khác 2/11/2017 12 12
Chương 2 MÃ HÓA NGUỒN 2.3.2 Phương pháp mã hóa với từ mã có chiều dài thay đổi (còn gọi là phương pháp mã hóa thống kê tối ưu hay mã hóa entropy)  Các ký hiệu của nguồn được mã hóa bằng các từ mã có chiều dài thay đổi.  Các ký hiệu có xác suất xuất hiện lớn sẽ được mã hóa bằng từ mã có chiều dài nhỏ, và ngược lại. Kết quả là, chiều dài trung bình của từ mã sẽ nhỏ   cao.  Ví dụ: mã Morse, mã Huffman, mã Shannon-Fano,vv…  Vấn đề giải mã khi từ mã có chiều dài thay đổi: Ví dụ: Nguồn DMS có 4 ký hiệu, được mã hóa theo bảng sau: Ký hiệu ai Xác suất pi Tập mã 1 Tập mã 2 a1 1/2 1 0 a2 1/4 00 10 a3 1/8 01 110 a4 1/8 10 111 Giả sử chuỗi thu được: 001001…. Xác định ký hiệu đã mã hóa ????? 2/11/2017 13 13
Chương 2 MÃ HÓA NGUỒN Ví dụ (tt):  Theo tập mã 1: 00 1 00 1  a2a1a2a1 00 10 01  a2a4a3  quá trình giải mã là không duy nhất  Theo tập mã 2: 0 0 10 0 1  a1a1a2a1  giải mã duy nhất  Để giải mã duy nhất  mã phân tách được  mã có tính prefix  mã phải thỏa bất đẳng thức Kraft: L  2 Rk  1 k 1  Mã có tính prefix: không có từ mã nào có chiều dài n giống với n bit đầu tiên của từ mã có chiều dài m (m>n). Ví dụ: Tập mã 1: {1,00,01,10}: không có tính prefix Tập mã 1: {0,10,110,111}: có tính prefix 2/11/2017 14 14
Chương 2 MÃ HÓA NGUỒN 2.3.2 Phương pháp mã hóa với từ mã có chiều dài thay đổi (tt) a. Phương pháp mã hóa Shannon-Fano:  Các bước thực hiện:  Liệt kê các ký hiệu theo thứ tự xác suất giảm dần  Chia các ký hiệu làm hai nhóm sao cho tổng xác suất của mỗi nhóm là gần bằng nhau nhất. Ký hiệu nhóm đầu là 0, nhóm sau là 1.  Trong mỗi nhóm lại lại chia thành hai nhóm nhỏ có xác suất gần bằng nhau nhất. Quá trình cứ tiếp tục cho đến khi chỉ còn một ký hiệu thì kết thúc.  Ví dụ: Nguồn DMS có 7 ký hiệu với xác suất xuất hiện như sau: ui u1 u2 u3 u4 u5 u6 u7 pi 0.34 0.23 0.19 0.1 0.07 0.06 0.01 Hãy thực hiện quá trình mã hóa Fano và tính hiệu suất mã hóa? 2/11/2017 15 15
Chương 2 MÃ HÓA NGUỒN a. Phương pháp mã hóa Shannon-Fano (tt): Lời giải: Lập bảng như sau: Ký hiệu Xác suất Lần Lần Lần Lần Lần Töø maõ ui pi chia 1 chia 2 chia 3 chia 4 chia 5 u1 0.34 u2 0.23 u3 0.19 u4 0.10 u5 0.07 u6 0.06 u7 0.01 2/11/2017 16 16
Chương 2 MÃ HÓA NGUỒN a. Phương pháp mã hóa Shannon-Fano (tt): Lời giải: Lập bảng như sau: Ký hiệu Xác suất Lần Lần Lần Lần Lần Töø maõ ui pi chia 1 chia 2 chia 3 chia 4 chia 5 u1 0.34 0 u2 0.23 0 u3 0.19 1 u4 0.10 1 u5 0.07 1 u6 0.06 1 u7 0.01 1 Nhóm 1: p = 0.57, nhóm 2: p = 0.43:  = |0.57-0.43 |= 0.14: nhỏ nhất 2/11/2017 17 17
Chương 2 MÃ HÓA NGUỒN a. Phương pháp mã hóa Shannon-Fano (tt): Lời giải: Lập bảng như sau: Ký hiệu Xác suất Lần Lần Lần Lần Lần Töø maõ ui pi chia 1 chia 2 chia 3 chia 4 chia 5 u1 0.34 0 0 u2 0.23 0 1 u3 0.19 1 0 u4 0.10 1 1 u5 0.07 1 1 u6 0.06 1 1 u7 0.01 1 1 2/11/2017 18 18
Chương 2 MÃ HÓA NGUỒN a. Phương pháp mã hóa Shannon-Fano (tt): Lời giải: Lập bảng như sau: Ký hiệu Xác suất Lần Lần Lần Lần Lần Töø maõ ui pi chia 1 chia 2 chia 3 chia 4 chia 5 u1 0.34 0 0 u2 0.23 0 1 u3 0.19 1 0 u4 0.10 1 1 0 u5 0.07 1 1 1 u6 0.06 1 1 1 u7 0.01 1 1 1 19
Chương 2 MÃ HÓA NGUỒN a. Phương pháp mã hóa Shannon-Fano (tt): Lời giải: Lập bảng như sau: Ký hiệu Xác suất Lần Lần Lần Lần Lần Töø maõ ui pi chia 1 chia 2 chia 3 chia 4 chia 5 u1 0.34 0 0 u2 0.23 0 1 u3 0.19 1 0 u4 0.10 1 1 0 u5 0.07 1 1 1 0 u6 0.06 1 1 1 1 u7 0.01 1 1 1 1 20

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2431 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.