როდის შეიძლება თქვენ ცალსახად დეკოდი?

ცვლადი სიგრძის კოდი სასარგებლო რომ იყოს, მიმღები ბიტის ნაკადი ცალსახად დეკოდირება უნდა. ჰამინგი ხაზს უსვამს 4-სიმბოლო კოდს, რომელიც არ აკმაყოფილებს ამ ტეստს, შემდეგ წარმოადგენს გამოსავალი: პრეფიქსი-თავისუფალი კოდები.

პრეფიქსი-თავისუფალი პირობა

კოდი არის პრეფიქსი-თავისუფალი (ან ჩაშენება) თუ რომელი კოდური სიტყვა სხვა კოდური სიტყვის პრეფიქსი არ არის. მიღებული ბიტის ნაკადის გათვალისწინებით, თქვენ იცით სიმბოლო დასრულდა მომენტში, როდესაც მიაღწევთ ხის ფოთლს — წინსწარი ხედვა არ საჭიროა.

პრეფიქსი-თავისუფალი კოდის მაგალითი {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.

გადამოწმება: 0 არ არის პრეფიქსი 10, 110, ან 111. 10 არ არის პრეფიქსი 110 ან 111 (10 გაყოლებული მეტი ბიტი იძლევა 100... ან 101..., არცერთი რომელიც იწყება 110 ან 111). კოდი კვალიფიკაციას ახორციელებს.

დეკოდირების პროცედურა: მიჰყევით ხეს, განშტოვდით თითოეული შემომავალი ბიტით, გამოუშვით სიმბოლო რომ მიაღწევთ ფოთლს, დაბრუნდით ფესვს.

ქრაფტის უტოლობა

ნებისმიერი პრეფიქსი-თავისუფალი ორობითი კოდი კოდური სიტყვის სიგრძე l_1, l_2, ..., l_n:

Σ 2^(−l_i) ≤ 1

თანასწორობა დგება როდესაც კოდი სრული (ფოთლები მოთავსებულია სრული ორობით ხეში სიმაღლე გაფხვნილი). ეს აუცილებელი პირობა: პრეფიქსი-თავისუფალი კოდი არ შეიძლება მას დაარღვიოს. მეორეს მხრივ, ქრაფტის უტოლობა დამაკმაყოფილებელი სიგრძის ნებისმიერი ერთობლიობისთვის, პრეფიქსი-თავისუფალი კოდი არსებობს.

ქრაფტის უტოლობის გამოყენება

კოდის სიგრძე მოცემული, გადამოწმება ქრაფტი: Σ 2^(−l_i) ≤ 1.

{s1=0, s2=10, s3=110, s4=111}: სიგრძე არის 1, 2, 3, 3.

Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓

შენონის ენტროპია

საშუალო კოდის სიგრძე ცვლადი სიგრძის კოდი: L = Σ p_i · l_i, სადაც p_i არის ალბათობა სიმბოლო s_i და l_i არის მისი კოდის სიგრძე.

რა მოკლე შეიძლება L გახდეს? შენონის პასუხი: შეუძლია ჩამოდით ქვემოთ წყაროს ენტროპია.

შენონის ენტროპია: H = −Σ p_i · log₂(p_i) (ერთეული: ბიტი/სიმბოლო)

ენტროპია იზომება საშუალო ინფორმაცია თითოეული სიმბოლოზე. მაღალი ენტროპია ნიშნავს სიმბოლო დაახლოებით თანაბარი ალბათობა (მაქსიმალური გაურკვევლობა). დაბალი ენტროპია ნიშნავს ზოგიერთი სიმბოლო დომინანტი (მაღალი მოსალოდნელობა, უფრო შეკუმშვადი).

უხმაურო კოდირების თეორემა

ნებისმიერი პრეფიქსი-თავისუფალი კოდი, H(წყარო) ≤ L ≤ H(წყარო) + 1.

კოდი არ შეიძლება დაამარცხოს ენტროპია. ჰუფმენი კოდირება (შემდეგი თავი) აღწევს ზედა შემოსაზღვრას: L < H + 1. ბლოკი კოდები ზე n სიმბოლო, შემოსაზღვრა შედება: H ≤ L/n < H + 1/n.

ენტროპია ასევე არის თეორიული კომპრესია ზღვარი: თქვენ არ შეიძლება დაკომპრესია წყარო ქვემოთ H ბიტი თითოეული სიმბოლო მის ინფორმაცია დაკარგვის გარეშე.

ენტროპიის გამოთვლა

მაგალითი: 4 სიმბოლო ალბათობა p = [1/2, 1/4, 1/8, 1/8].

H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)

= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3

= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 ბიტი/სიმბოლო

და ჰუფმენი კოდი {0, 10, 110, 111} აღწევს L = 1.75 = H ზუსტად.

რატომ ენტროპია ქვედა შემოსაზღვრა

უხმაურო კოდირების თეორემის ქვედა შემოსაზღვრა არ არის თხელი ფორმულა — ის ასახავს რაიმე ღრმა ინფორმაციის შესახებ: თქვენ არ შეიძლება დაკომპრესია რაიმე რომელიც უკვე მაქსიმალურად გაურკვეველი.

როდესაც სიმბოლო თანაბრად სავარაუდო (უნიფორმი განაწილება), ენტროპია H = log₂(n) n სიმბოლოსთვის. ბლოკი კოდი სიგრძე log₂(n) ბიტი აღწევს ზუსტად H. რა კოდი შეიძლება უკეთესი.

როდესაც ერთი სიმბოლო დომინანტი (ვთქვათ, p(A) = 0.99, p(B) = 0.01), H მცირე — ახლოს 0. ცვლადი სიგრძე კოდი შეიძლება დაკეთებული A ძალიან მოკლე კოდი, კოდირება ნაკადი ძალიან ეფექტურად.

პრაქტიკული გაკვეთილი: დიდი კომპრესია მოგება გამოჩნდება მხოლოდ როდესაც სიმბოლო ალბათობა მნიშვნელოვნად განსხვავდება. თუ წყარო უკვე 'უნიფორმი' (შემთხვევითი გამოჩნდება), ჰუფმენი კოდირება მოგება არ რაიმე.