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

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ả
Nội dung trích xuất từ tài liệu:
Bài toán mã trường hợp kênh không bị nhiễu - Phần 2 7/2/2010Chương 2:Bài toán mã trư ng h pkênh không b nhi u2.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 KhaM ñ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 KhaVí 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.2M 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 khiTrong đó D là s các ký t mã 2 7/2/2010 5 7/2/2010 Huỳnh Văn KhaCh 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 KhaCh ng minh ñ nh lý 2.2 00 000 00 01 0 0010 02 010 10 Cây b c 01 011 11 3 kích 1Cây b c 2 thư c 2kích thư c 3 100 12 10 101 201 110 2 21 11 22 111 3 7/2/2010 7 7/2/2010 Huỳnh Văn KhaCh 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 KhaCh 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 ...