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

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 1, 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 1 7/2/2010Chương 2:Bài toán mã trư ng h pkênh không b nhi u2.1 Tính gi i đư c c a m t b mã 2 7/2/2010 Huỳnh Văn KhaGi i thi u bài toán mã• Bi n ng u nhiên X nh n các giá tr x1, x2, … , xM (g i là các tr ng thái c a X) v i xác su t tương ng p1, p2, …., pM• Dãy h u h n các giá tr c a X g i là m u tin (message)• T p h p {a1, a2, …, aD} g i là t p các ký t mã (code character)• M i xi tương ng v i m t dãy h u h n các ký t mã g i là t mã (character word)• T p các t mã g i là b mã (code) 1 7/2/2010 3 7/2/2010 Huỳnh Văn KhaGi i thi u bài toán mã• Gi s các t mã là khác nhau• M u tin do bi n X sinh ra đư c mã hóa thành m t dãy các t mã• M c tiêu c a bài toán là c c ti u hóa chi u dài trung bình c a mã• Chi u dài c a t mã ng v i xi là ni, i = 1, 2, …, M. M c tiêu là c c ti u hóa: 4 7/2/2010 Huỳnh Văn KhaMã ti n t và mã gi i ñư c• Xét b mã nh phân x1 0 x2 010 x3 01 x4 10• Dãy 010 có th tương ng v i m t trong ba m u tin: x2, x3x1, x1x4. Nên không th gi i mã• C n có m t s gi i h n trên các t mã c a 1 b mã 2 7/2/2010 5 7/2/2010 Huỳnh Văn KhaMã ti n t và mã gi i ñư c• B mã g i là gi i đư c n u m i dãy h u h n các t mã đ u tương ng v i nhi u nh t m t m u tin• Dãy A g i là ti n t c a dãy B n u dãy B có th đư c vi t dư i d ng AC, v i C là m t dãy nào đó• B mã ti n t là b mã có tính ch t: không t mã nào là ti n t c a t mã khác• B mã ti n t là gi i đư c, nhưng b mã gi i đư c chưa ch c là b mã ti n t• B mã ti n t có th đư c gi i mã t ng bư c 6 7/2/2010 Huỳnh Văn KhaMã ti n t và mã gi i ñư c• B mã sau là b mã ti n t x1 0 x2 100 x3 101 x4 11• B mã sau là gi i đư c nhưng không là ti n t x1 0 x2 01 3 7/2/2010 7 7/2/2010 Huỳnh Văn KhaGi i thu t ki m tra tính gi i ñư c• G i S0 là t p các t mã ban đ u• Xét t t c các c p t mã trong S0. N u có các t mã Wi, Wj sao cho Wj = WiA, cho h u t A vào t p S1• Gi s có t p Sn-1 (n>1). N u có W trong S0 và A trong Sn-1 sao cho A=WB, cho B vào Sn. N u có W’ trong So và A’ trong Sn-1 sao cho W’=A’B’, cho B’ vào Sn• Đ nh lý 2.1:M t b mã là gi i đư c n u và ch n u không t p nào trong các t p S1, S2, S3, … ch a b t kỳ t mã nào 8 7/2/2010 Huỳnh Văn KhaThu t toán ki m tra tính gi i ñư c x1 a x2 c x3 ad x4 abb x5 bad x6 deb x7 bbcde 4 7/2/2010 9 7/2/2010 Huỳnh Văn KhaThu t toán ki m tra tính gi i ñư cS0 S1 S2 S3 S4 S5 S6 S7a d eb de b ad d ebc bb cde bcdead • Sn r ng v i m i n>7abb • ad thu c S5 nên b mã là khôngbad gi i đư c • abbcdebad có th gi i mã thànhdeb x1x7x5 ho c x4x2x6x3bbcde 10 7/2/20 ...