Bài toán mã trường hợp kênh không bị nhiễu - Phần 2

Chia sẻ: Nguyen Uyen | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

61
lượt xem 4
download

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

Tham khảo tài liệu 'bài toán mã trường hợp kênh không bị nhiễu - phần 2', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Bài toán mã trường hợp kênh không bị nhiễu - Phần 2

7/2/2010 Chương 2: Bài toán mã trư ng h p kênh không b nhi u 2.2 S t n t i c a b mã ti n t và gi i đư c 2 7/2/2010 Huỳnh Văn Kha M ñu • Cho bi n ng u nhiên X có các giá tr x1, x2, …, xM. T p các ký t mã a1, a2, …, aD • Cho trư c các s nguyên dương n1, n2, …, nM • Bài toán đ t ra là: có th xây d ng b mã gi i đư c sao cho t mã ng v i xk có chi u dài là nk? • Mã ti n t có th gi i mã t ng bư c • Trong bài toán kênh không b nhi u, mã gi i đư c có th quy v mã ti n t • Đ u tiên ta s xét s t n t i c a b mã ti n t , sau đó m r ng cho b mã gi i đư c 1
7/2/2010 3 7/2/2010 Huỳnh Văn Kha Ví d • Ví d 1: M = 3, D = 2, n1 = 1, n2 = 2, n3 = 3 Có th ch n b mã {0, 10, 110} • Ví d 2: M = 3, D = 2, n1 = n2 = 1, n3 = 2 Không có b mã gi i đư c nào th a yêu c u bài toán (s ch ng minh sau) • Khi nào có th xây d ng đư c b mã th a yêu c u, khi nào không? 4 7/2/2010 Huỳnh Văn Kha ð nh lý 2.2 M t b mã ti n t v i chi u dài các t mã n1, n2, …, nM là t n t i khi và ch khi Trong đó D là s các ký t mã 2
7/2/2010 5 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.2 • Cây b c D kích thư c k là m t h th ng các đi m và đo n th ng • M i dãy s đư c t o thành t các ký t trong {0, 1, …, D – 1} có chi u dài không l n hơn k đư c bi u di n b i m t đi m Vs khác nhau • N u dãy t có đư c do thêm duy nh t m t ký t vào sau s thì n i Vs và Vt b ng m t đo n th ng • Các đi m ng v i dãy có chi u dài k g i là các đi m ng n c a cây kích thư c k 6 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.2 00 000 00 01 0 001 0 02 010 10 Cây b c 01 011 11 3 kích 1 Cây b c 2 thư c 2 kích thư c 3 100 12 10 101 20 1 110 2 21 11 22 111 3
7/2/2010 7 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.2 • Gi s n1 ≤ n2 ≤ … ≤ nM • M i t mã đư c đ ng nh t v i m t đi m trên cây b c D kích thư c nM 0 Cây ng v i b mã {0, 10, 111} 10 1 11 111 8 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.2 • Do b mã là ti n t nên khi đi m P đ i di n cho m t t mã, thì không đi m nào trên nhánh b t đ u t P đ i di n cho m t t mã khác • Đi m ng v i t mã chi u dài nk s che đi m ng n c a cây • S đi m ng n b toàn b b mã che ≤ T ng s các đi m ng n c a cây 4
7/2/2010 9 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.2 • Ngư c l i, gi s và n1 ≤ n2 ≤ … ≤ nM • Ch n đi m b t kỳ trên cây ng v i dãy có chi u dài n1. Đi m này che đi m ng n • Còn l i ít nh t 1 đi m ng n, ch n đư c đi m ng v i n2. Lúc đó, do ta ch n đư c đi m ng v i n3. Và c th cho đ n h t 10 7/2/2010 Huỳnh Văn Kha M r ng cho b mã gi i ñư c • Đi u ki n đ nh lý 2.2 cũng là đi u ki n c n và đ cho s t n t i c a b mã gi i đư c • Do b mã ti n t là gi i đư c nên ch c n ch ng minh đ nh lý sau là đ . Đ nh lý 2.3: N u b mã gi i đư c có chi u dài t mã l n lư t là n1, n2, …, nM thì: 5
7/2/2010 11 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.3 • G i ωj là s t mã chi u dài j và r là chi u dài l n nh t c a các t mã, ta có: • V i m i s t nhiên n cho trư c, nhân phân ph i và rút g n, ta đư c: 12 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.3 • Trong đó: • Nk chính là t ng s m u tin đư c t o thành t n tr ng thái xi sao cho đo n mã c a các m u tin này đ u có chi u dài k • B mã là gi i đư c nên m i dãy ký t mã tương ng v i nhi u nh t m t m u tin • Nk không vư t quá t ng s các dãy ký t mã có chi u dài k 6
7/2/2010 13 7/2/2010 Huỳnh Văn Kha Ch ng minh ñ nh lý 2.3 • Như v y Nk ≤ Dk và ta có: • L y căn b c n: • Cho n ti n ra vô c c ta đư c đi u c n ch ng minh 7