რა ეწოდა შენონმა ინფორმაციას
შენონმა ინფორმაცია გაზომა სიურპრიზით. სიტყვა ალბათობით p ატარებს:
I = −log₂(p) ბიტი
გარკვეული მოვლენა (p = 1) ატარებს 0 ბიტს — არ არის სიურპრიზი, არ არის ინფორმაცია. იშვიათი მოვლენა (p = 1/1024) ატარებს 10 ბიტს.
ჰამინგი დაუყოვნებლივ აღნიშნავს პრობლემას: ეს არის ფორმულა რაოდენობის გასაზომად, არა ცნების განსაზღვრება. ის ზომავს მეშინე-ის-სახის სიურპრიზს, არა ადამიანის მნიშვნელობას. სტუდენტი, რომელიც უკვე იცის პასუხი კითხვაზე, იღებს 0 ბიტს პასუხიდან — მიუხედავად იმისა, რამდენად მნიშვნელოვანია პასუხი სხვებისთვის.
ფორმულა კარგად მუშაობს სატელეფონო სისტემებში, რადიოში, კომპიუტერებში. ის ცუდად მუშაობს ადამიანის კომუნიკაციაში, ბიოლოგიაში ან მნიშვნელობაში. ჰამინგის სასურველი სახელი: 'კომუნიკაციის თეორია', არა 'ინფორმაციის თეორია'.
ენტროპია
ანბანისთვის q სიმბოლოთი და ალბათობებით p₁, p₂, ..., p_q, საშუალო ინფორმაცია სიმბოლოზე არის ენტროპია:
H = −Σᵢ pᵢ log₂(pᵢ)
H მაქსიმუმს აღწევს როდესაც ყველა ალბათობა თანაბარია: H_max = log₂(q) ბიტი. ნებისმიერი არათანაბარი განაწილება აქვს დაბალი ენტროპია.
ენტროპიის გამოთვლა
ორობითი ენტროპია: წყარო ორი სიმბოლოთი, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 როდესაც p = 0 ან p = 1 (სრულად იწინასწარმეტყველებელი). H(p) = 1 ბიტი როდესაც p = 0.5 (სრულად უწინასწარმეტყველებელი).
გიბსის უტოლობა & ხმაურის გარეშე კოდირება
გიბსის უტოლობა: ორი ალბათობის განაწილებისთვის p = {pᵢ} და q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
სტოლობა მხოლოდ როდესაც p = q. ეს ეყრდნობა ელემენტარულ ფაქტს რომ ln(x) ≤ x − 1 ყველა x > 0-სთვის, სტოლობა x = 1-ში.
შედეგი: ენტროპია H(p) მაქსიმიზირდება როდესაც ყველა სიმბოლო თანაბარი ალბათობის მქონეა. q სიმბოლოსთვის: H_max = log₂(q).
ხმაურის გარეშე კოდირების თეორემა: უნიკალურად გაშიფრებადი კოდის გამოყენებისას, კრაფტის უტოლობა მოითხოვს Σ 2^(−lᵢ) ≤ 1 სადაც lᵢ არის კოდის სიგრძე სიმბოლო i-სთვის. გიბსის უტოლობით, საშუალო კოდის სიგრძე L = Σ pᵢ lᵢ აკმაყოფილებს:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
თქვენ არ შეგიძლიათ ენტროპიაზე უკეთეს მედეგით საშუალოდ. ჰაფმენის კოდირება აღწევს L < H + 1.
არხის სიმძლავრე
ორობითი სიმეტრიული არხი (BSC) აბრუნებს თითოეულ ბიტს დამოუკიდებლად შეცდომის ალბათობით Q = 1 − P. BSC-ის სიმძლავრე — საიმედო ინფორმაციის მაქსიმალური გადაცემის სიჩქარე — არის:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
სადაც H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) არის შეცდომის ხარისხის ორობითი ენტროპია.
Q = 0-ში (შეცდომა არ არის): C = 1 ბიტი/გადაცემა (სრულყოფილი არხი). Q = 0.5-ში (შემთხვევითი ბრუნება): C = 0 (არხი გადაცემას არ ატარებს). Q = 1-ში (ყველა ბიტი აბრუნებს): C = 1 (თქვენ ზუსტად იცით რა იგზავნა გამომგებელმა, უბრალოდ ყველაფერი უკან გააბრუნეთ).
C ზომავს მაქსიმალურ ხარის R, რომელზეც შეგიძლიათ გადასცეთ თვითნებურად მცირე შეცდომის ალბათობით. თუ R < C, ასეთი კოდები არსებობს. თუ R > C, ისინი არ არსებობს — არ იმსახურებს კოდი სიმძლავრეს.
არხის სიმძლავრის გამოთვლა
P = 0.9-ით (10% შეცდომის სიხშირე, Q = 0.1):
C = 1 + 0.9 log₂(0.9) + 0.1 log₂(0.1)
log₂(0.9) ≈ −0.152, log₂(0.1) ≈ −3.322
C ≈ 1 + 0.9×(−0.152) + 0.1×(−3.322) = 1 − 0.137 − 0.332 ≈ 0.531 ბიტი/გადაცემა
რა ამტკიცებს თეორემა
შენონის ფუნდამენტური თეორემა: ნებისმიერი გადაცემის სიჩქარე R < C-სთვის, კოდები ბლოკის სიგრძე n (n → ∞-ით) შეცდომის ალბათობა P_E → 0-ით წარმოიქმნება.
მტკიცებულება იყენებს გასაკვირ არგუმენტს: შემთხვევითი კოდები. მაგივრად კონკრეტული კოდის აგების, შენონმა საშუალო ზემოთ ყველა შესაძლო შემთხვევითი კოდის წიგნები (მონეტის აგრძობისთვის კოდირება). მან აჩვენა საშუალო შეცდომა ყველა კოდის წიგნებზე მცირეა. თუ საშუალო მცირეა, თუნდაც ერთი კოდი აღწევს მცირე შეცდომას.
სფერის ভিত്তিক ანალიზი: გამომგებელი ირჩევს შეტყობინება aᵢ → სფერი რადიუსი n(Q + ε₂) ირგვლივ aᵢ n-განზომილებიანი ორობითი სივრცეში. დიდი n-სთვის, მიღებული სიტყვა bⱼ მდგომარეობს ამ სფეროში მაღალი ალბათობით. მიმღები გაშიფრავს კოდს, რომლის სფერი შეიცავს bⱼ-ს.
ოთხი შემთხვევა განსაზღვრებს შეცდომის ალბათობა P_E:
``
aᵢ სფეროში სხვა aⱼ სფეროში შედეგი
დიახ არა სწორი (შეცდომა არ არის)
დიახ დიახ ორაზროვანი → შეცდომა
არა დიახ ცდომილი გაშიფვრა → შეცდომა
არა არა ყველა სფეროს გარეთ → შეცდომა
``
P_E-სთვის საზღვარი მუშაობს: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) კორექტად არჩეული d და ε₂-ზე. ε₂ აირჩევა რომ H(Q+ε₂) < C უარყოფით მაჩვენებელი. დიდი n-სთვის, მეორე წევრი → 0.
თეორემის ობიექტიური ბუნება
ჰამინგი ზუსტი იყო რა ამტკიცებს თეორემა და რა არა.
რა ის ამტკიცებს: საიმედო კომუნიკაცია გადაცემის სიჩქარე R < C-ზე შესაძლებელია, პრინციპში, საკმარისად დიდი n-სთვის.
რა ის არ იძლევა: გამკრთალი კოდის აგება. შემთხვევითი კოდი სიგრძე n საკმარისი სიმძლავრეზე მიახლოებითი აქვს კოდის წიგნი ზომა M × n ბიტი, სადაც ორივე M და n ასტრონომიულად დიდია. თქვენ არ შეგიძლიათ ის შეინახოთ ან გამოთვალოთ.
შეცდომის გასწორება კოდი vs. შენონი: შეცდომის გასწორება კოდი (ჰამინგი, რიდ-სოლომონი, ტურბო, LDPC) იძლევს ცხადი, გამოთვლადი აგება. ისინი ზღვრიდან რამდენი მანძილი სიმძლავრეზე გამოკვლეულ გაზომვას აკრეფენ თხოვნით პრაქტიკული კოდერი & დეკოდერი. რაც უფრო დიდია n და მეტი შეცდომა გასწორდება თითო ბლოკში, პრაქტიკული კოდი უფრო მოახლოვდება სიმძლავრეს.
კოსმოსური თანამგზავრების მაგალითი: ვოიჯერი და პიონერი გამოიყენეს მძლავრი შეცდომის გასწორება კოდი ბილიონი მილის დისტანციებზე კომუნიკაციისთვის 5-20 ვატების სიმძლავრეზე. დიდი ბლოკის სიგრძე უშვა უფრო მეტი შეცდომა თითო ბლოკში გასწორდეს, უკიდეგანი ხმაურიდან დისტანციზე სიმძლავრეზე უბიძგა.
კრიტიკული შეფასება
ჰამინგი დაასრულა 13-ე თავი ფართო კრიტიკით სამეცნიერო განსაზღვრებებზე. შენონის ინფორმაციის ფორმულა ზომავს მეშინე-ის-სახის სიურპრიზს, მეცნიერული მნიშვნელობა. სახელი 'ინფორმაციის თეორია' ზედმეტი აპირებელი. თევზე მოლუქვის შედარება: თევზის ჯერი ხელოსანი, რომელი იჭერს მხოლოდ თევზი მეშ ფილტრზე დიდი დაასკვნის: არ არის მცირე თევზი. უჯრის შეზღუდვა აყალიბებს სამყაროს მოჩვენებული შეზღუდვა.