Bài thảo luận Cơ sở thông tin số
lượt xem 22
download
Mã hóa tối ưu là phép mã hóa mà kết quả là một bọ mã có chiều dài trung bình là nhỏ nhất trong tất cả các phép mã hóa có thể có cho nguồn. Bộ mã hóa của phép mã hóa tối ưu cho nguồn được gọi là mã hóa tối ưu. Ba phép mã hóa shnnon, fano, huffman.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài thảo luận Cơ sở thông tin số
- Bài thảo luận Môn : Cơ sở thông tin số Nhóm thảo luận : 02 1-Trần Văn Dũng 1-Tr 2-Trần Xuân Dũng 3-Trương Văn Dương 4-Nguyễn Tiến Đại 5-Trần Khương Đạt 6-Hạ Tiến Đức 7-Nguyễn Hữu Đức . Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Câu hỏi : Trình bày mã hóa thống kê tối ưu Fano-Shannon Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Mã hóa tối ưu - Là phép mã hóa mà kết quả là một bộ mã có chiều dài trung bình là nhỏ nhất trong tất cả các phép mã hóa có thể có cho nguồn - Bộ mã của phép mã hóa tối ưu cho nguồn được gọi là mã hóa tối ưu - Ba phép mã hóa :Shannon,Fano,Huffman - Trong mỗi phép mã hóa chúng ta sẽ mã hóa với cơ số mã m=2 (mã hóa nhị phân) sau đó mở rộng cho trường hợp m>2 Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Giới thiệu về nhà khoa học Shannon • Shannon sinh ngày 30-4-1916 ở Petoskey,bang Michigan . Ông là một nhà khoa học vĩ đại trong lĩnh vực viễn thông.Ông là người đã phát minh ra một môn khoa học mới đó là lý thuyết thông tin.Đó là một môn học trừu tượng mô tả về những nguyên lý của truyền thông tin,nó đặt nền móng cho các ứng dụng thưc tiễn như internet,máy tính,v.v. Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Claude shannon Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Nội dung phương pháp Shannon • B1. Sắp xếp các xác suất theo thứ tự giảm dần .Không mất tính tổng quát giả sử P1 ≥ ……≥ Pk i −1 ∑ pj • B2. Định nghĩa q1=0 , với mọi i=1,2,…..,K qi= j =1 • B3. Đổi qi sang cơ số 2(biểu diễn qi trong cơ số 2) sẽ được một chuỗi nhị phân • B4.Từ mã được gán cho ai và li kí hiệu lấy từ vị trí sau dấu phẩy của chuỗi nhị phân tương ứng với qi , [ -log ] trong đó li = pi 2 Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Ví dụ:hãy mã hóa nguồn S={ a1,a2,a3,a4,a5,a6}với các xác suất lần lượt là : 0.3;0.25; 0.2;0.12;0.08; 0.05 Xác suất Biểu diễn Từ mã Tin i −1 ∑ pj nhị phân ai pi qi= li =[ -log2pi] wi j =1 a1 0.3 0 0.00 2 00 a2 0.25 0.3 0.01001… 2 01 a3 0.2 0.55 0.10001… 3 100 a4 0.12 0.75 0.11000… 4 1100 a5 0.08 0.87 0.11011… 4 1101 a6 0.05 0.95 0.111100 5 11110 …
- • Độ dài trung bình của từ mã : n=0.05*5+0.08*4+0.12*4+0.2*3+0.25*2+0.3*2=2.75 - Entropi của nguồn tin H(s)= - [0.05*log2(0.05)+ 0.08*log2(0.08)+ 0.12*log2(0.12)+ 0.2*log2(0.2)+ 0.25*log2(0.25)+ 0.3*log2(0.3)]=2.36 - Trị số kinh tế ρ=H(s)\n =2.36/2.75=85.82% Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Giới thiệu về nha khoa học Robert Fano • Robert Mario Fano (sinh ra tại Torino, Italia vào ngày 11 tháng 11 năm 1917 ) là một người Ý – Mỹ, hiện nay giáo sư danh dự của Viện kỹ sư Điện và Khoa học tại Viện Công nghệ Massachusetts . Fano được biết đến chủ yếu cho công việc của ông về lý thuyết thông tin , phát minh ra (với Claude shannon ) shannon – fano. Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Nhà khoa học Robert Mario Fano Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Nội dung phương pháp Fano • B1. Sắp xếp các xác suất theo thứ tự giảm dần .Không mất tính tổng quát giả sử P1 ≥ ……≥ Pk • B2.Phân các xác suất thành 2 nhóm có tổng xác suất gần bằng nhau • B3.Gán cho 2 nhóm lần lượt các kí hiệu 0 và 1 (hoặc ngược lại) • B4. Lập lại bước 2 cho các nhóm con cho tới khi không thể tiếp tục được nữa • B5. Từ mã ứng với mỗi tin là chuỗi bao gồm các kí hiệu theo thứ tự lần lượt được gán cho các nhóm có chứa xác suất tương ứng của tin Trường đại học kỹ thuật công nghiệp Thái Nguyên
- Ví dụ:hãy mã hóa nguồn S={ a1,a2,a3,a4,a5,a6 }với các xác suất lần lượt là 0.3;0.25; 0.2; 0.12;0.08; 0.05 lần Từ Tin Xác phân nhóm suất 1 2 3 4 mã a1 0.3 0 0 00 a2 0.25 0 1 01 a3 0.2 1 0 10 a4 0.12 1 1 0 110 a5 0.08 1 1 1 0 1110 a6 0.05 1 1 1 1 1111
- • Độ dài trung bình của từ mã : • n=0.05*4+0.08*4+0.12*3+0.2*2+0.25*2+0.3*2=2.38 • - Entropi của nguồn tin • H(s)= - [0.05*log2(0.05)+ 0.08*log2(0.08)+ 0.12*log2(0.12)+ 0.2*log2(0.2)+ 0.25*log2(0.25)+ 0.3*log2(0.3)]=2.36 • Trị số kinh tế • ρ=H(s)\n =2.36/2.38=99.16%
- Nhận xét Phương pháp Fano cho kết quả tốt hơn phương pháp Shannon • Hai phương pháp trên thực chất là một , không cho phép lập mã một cách duy nhất vì sự chia nhóm dựa trên cơ sở đồng đều và tổng xác suất nên có thể có nhiều cách chia. • Sự lập mã theo cách chia nhóm trên cơ sở đồng xác suất tạo cho bộ mã có tính prefix. • Phương pháp mã hóa từng tin của nguồn tin chỉ có hiệu quả khi entropy của nguồn lớn hơn 1 ( H(u)>1 ). Trường hợp H(u)
- Khi đó entropi của nguồn sẽ là H.N. Lúc đó độ dài trung bình − của từ mã cho các khối tin phải thỏa mãn điều kiệ.n: ≤ n N ≤ H .N + 1 HN Độ dài trung bình của từ mã cho một tin có thể tính theo tỷ lệ: − nN − n= N 1 − H ≤n ≤H + Do đó: N H ≤ ρ ≤1 Hay: H +1 Khi H
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bảo mật mạng LAN không dây
9 p | 787 | 403
-
Kiến thức cơ bản về mạng: Phần 1 - Các thiết bị phần cứng mạng
6 p | 420 | 202
-
Các hàm Ranking mới trong SQL Server 2005
8 p | 301 | 112
-
Kiến thức cơ bản về mạng: Phần 1
9 p | 261 | 110
-
Quản trị Exchange 2003 từ xa
15 p | 205 | 102
-
Bài thảo luận môn Quản trị cơ sở dữ liệu và phần mềm ứng dụng (P2)
4 p | 257 | 75
-
Bài thảo luận môn Quản trị cơ sở dữ liệu và phần mềm ứng dụng (P3)
5 p | 246 | 69
-
Bài thảo luận môn Quản trị cơ sở dữ liệu và phần mềm ứng dụng (P4)
6 p | 275 | 61
-
Quản trị Exchange 2003 từ xa
16 p | 158 | 57
-
Hàng đợi thư về trong Exchange 2007
10 p | 99 | 37
-
Giới thiệu về Network Access Protection (Phần 2)
4 p | 130 | 37
-
Liên kết động trong Linux và Windows (Phần 1)
17 p | 123 | 28
-
Liên kết động trong Linux và Windows (phần II)
16 p | 129 | 23
-
Hàng đợi thư trong Exchange 2007
11 p | 167 | 22
-
Truy cập Exchange 2007 từ máy tính Apple Macintosh
9 p | 111 | 18
-
Kiểm tra khả năng tương thích của Windows 7 – Phần 1
4 p | 108 | 8
-
Truy cập Exchange 2007 từ máy tính Apple Macintosh (Phần 1)
9 p | 74 | 6
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