რიჩარდ ჰამინგი: თავი 13. ინფორმაციის თეორია

Ჩვენ ეს შევძელით!

”ამ კურსის მიზანია მოგამზადოთ თქვენი ტექნიკური მომავლისთვის.”

გამარჯობა, ჰაბრ. გაიხსენეთ გასაოცარი სტატია "შენ და შენი საქმე" (+219, 2588 სანიშნე, 429 ათასი კითხვა)?

ასე რომ, ჰამინგი (დიახ, დიახ, თვითკონტროლი და თვითშესწორება ჰემინგის კოდები) არის მთელი книга, დაწერილი მისი ლექციების საფუძველზე. ჩვენ ვთარგმნით მას, რადგან კაცი თავის აზრს ამბობს.

ეს არის წიგნი არა მხოლოდ IT, ეს არის წიგნი წარმოუდგენლად მაგარი ადამიანების აზროვნების სტილზე. „ეს არ არის მხოლოდ პოზიტიური აზროვნების სტიმული; ის აღწერს პირობებს, რომლებიც ზრდის დიდი სამუშაოს შესრულების შანსებს“.

მადლობა ანდრეი პახომოვს თარგმანისთვის.

ინფორმაციის თეორია შეიმუშავა C. E. Shannon-მა 1940-იანი წლების ბოლოს. Bell Labs-ის მენეჯმენტი დაჟინებით მოითხოვდა, რომ მას "კომუნიკაციის თეორია" უწოდა, რადგან... ეს ბევრად უფრო ზუსტი სახელია. გასაგები მიზეზების გამო, სახელწოდება „ინფორმაციის თეორია“ გაცილებით დიდ გავლენას ახდენს საზოგადოებაზე, რის გამოც შენონმა აირჩია იგი და ეს არის ის სახელი, რომელიც დღემდე ვიცით. თავად სახელი ვარაუდობს, რომ თეორია ეხება ინფორმაციას, რაც მას მნიშვნელოვანს ხდის ინფორმაციის ეპოქაში უფრო ღრმად გადასვლისას. ამ თავში მე შევეხები ამ თეორიის რამდენიმე მთავარ დასკვნას, მე წარმოგიდგენთ ამ თეორიის ზოგიერთი ცალკეული დებულების არა მკაცრ, არამედ ინტუიციურ მტკიცებულებას, რათა გაიგოთ რა არის სინამდვილეში „ინფორმაციის თეორია“ და სად შეგიძლიათ მისი გამოყენება. და სად არა .

უპირველეს ყოვლისა, რა არის „ინფორმაცია“? შენონი ინფორმაციას აიგივებს გაურკვევლობასთან. მან აირჩია მოვლენის ალბათობის უარყოფითი ლოგარითმი, როგორც იმ ინფორმაციის რაოდენობრივი საზომი, რომელსაც იღებთ, როდესაც ხდება მოვლენა p ალბათობით. მაგალითად, თუ გეტყვით, რომ ლოს-ანჯელესში ამინდი ნისლია, მაშინ p არის 1-თან ახლოს, რაც ნამდვილად არ გვაძლევს დიდ ინფორმაციას. მაგრამ თუ ვიტყვი, რომ ივნისში მონტერეიში წვიმს, შეტყობინებაში გაურკვევლობა იქნება და ის შეიცავს მეტ ინფორმაციას. სანდო მოვლენა არ შეიცავს ინფორმაციას, რადგან ჟურნალი 1 = 0.

მოდით შევხედოთ ამას უფრო დეტალურად. შენონს სჯეროდა, რომ ინფორმაციის რაოდენობრივი საზომი უნდა იყოს p მოვლენის ალბათობის უწყვეტი ფუნქცია, ხოლო დამოუკიდებელი მოვლენებისთვის ის უნდა იყოს დანამატი - ორი დამოუკიდებელი მოვლენის გამოვლენის შედეგად მიღებული ინფორმაციის რაოდენობა უნდა იყოს ტოლი. ერთობლივი მოვლენის დადგომის შედეგად მიღებული ინფორმაციის რაოდენობა. მაგალითად, კამათლის და მონეტის გახვევის შედეგი ჩვეულებრივ განიხილება, როგორც დამოუკიდებელი მოვლენები. გადმოვთარგმნოთ ზემოაღნიშნული მათემატიკის ენაზე. თუ I (p) არის ინფორმაციის რაოდენობა, რომელიც შეიცავს მოვლენას p ალბათობით, მაშინ ერთობლივი მოვლენისთვის, რომელიც შედგება ორი დამოუკიდებელი მოვლენისგან x ალბათობით p1 და y ალბათობით p2 ვიღებთ.

(x და y დამოუკიდებელი მოვლენებია)

ეს არის კოშის ფუნქციური განტოლება, რომელიც შეესაბამება ყველა p1 და p2. ამ ფუნქციური განტოლების ამოსახსნელად, დავუშვათ, რომ

p1 = p2 = p,

ეს იძლევა

თუ p1 = p2 და p2 = p მაშინ

და ა.შ. ამ პროცესის გაფართოება ექსპონენციალებისთვის სტანდარტული მეთოდის გამოყენებით, ყველა რაციონალური რიცხვისთვის m/n შემდეგი სწორია

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

ინფორმაციის თეორიაში ჩვეულებრივია ლოგარითმის ბაზის აღება 2-ად, ამიტომ ორობითი არჩევანი შეიცავს ზუსტად 1 ბიტ ინფორმაციას. ამიტომ, ინფორმაცია იზომება ფორმულით

მოდით შევჩერდეთ და გავიგოთ რა მოხდა ზემოთ. პირველ რიგში, ჩვენ არ განვსაზღვრეთ „ინფორმაციის“ ცნება, ჩვენ უბრალოდ განვსაზღვრეთ მისი რაოდენობრივი საზომის ფორმულა.

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

მესამე, ეს არის შედარებითი ზომა, ეს დამოკიდებულია თქვენი ცოდნის ამჟამინდელ მდგომარეობაზე. თუ უყურებთ შემთხვევითი რიცხვების გენერატორიდან „შემთხვევითი რიცხვების“ ნაკადს, ჩათვლით, რომ ყოველი შემდეგი რიცხვი გაურკვეველია, მაგრამ თუ იცით „შემთხვევითი რიცხვების“ გამოთვლის ფორმულა, შემდეგი რიცხვი იქნება ცნობილი და, შესაბამისად, არ იქნება ცნობილი. შეიცავს ინფორმაციას.

ასე რომ, შენონის მიერ ინფორმაციის განმარტება ხშირ შემთხვევაში შესაბამისია მანქანებისთვის, მაგრამ, როგორც ჩანს, არ შეესაბამება ამ სიტყვის ადამიანის გაგებას. სწორედ ამ მიზეზით უნდა ეწოდოს „ინფორმაციის თეორიას“ „კომუნიკაციის თეორია“. თუმცა, უკვე გვიანია დეფინიციების შეცვლა (რომელმაც თეორიას თავდაპირველი პოპულარობა შესძინა და რომელიც ხალხს ჯერ კიდევ აფიქრებინებს, რომ ეს თეორია ეხება „ინფორმაციას“), ამიტომ მათთან ერთად უნდა ვიცხოვროთ, მაგრამ ამავე დროს თქვენ უნდა ნათლად გვესმის, რამდენად შორს არის შენონის ინფორმაციის განმარტება მისი ხშირად გამოყენებული მნიშვნელობისგან. შენონის ინფორმაცია სულ სხვა რამეს ეხება, კერძოდ გაურკვევლობას.

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

განვიხილოთ სისტემა, რომლის ანბანი შედგება q სიმბოლოებისგან pi ალბათობით. Ამ შემთხვევაში ინფორმაციის საშუალო რაოდენობა სისტემაში (მისი მოსალოდნელი მნიშვნელობა) უდრის:

ამას ეწოდება სისტემის ენტროპია ალბათობის განაწილებით {pi}. ჩვენ ვიყენებთ ტერმინს "ენტროპიას", რადგან იგივე მათემატიკური ფორმა ჩნდება თერმოდინამიკასა და სტატისტიკურ მექანიკაში. სწორედ ამიტომ, ტერმინი „ენტროპია“ ქმნის გარკვეულ მნიშვნელობის აურას თავის გარშემო, რაც საბოლოოდ არ არის გამართლებული. აღნიშვნის იგივე მათემატიკური ფორმა არ გულისხმობს სიმბოლოების ერთსა და იმავე ინტერპრეტაციას!

ალბათობის განაწილების ენტროპია მნიშვნელოვან როლს ასრულებს კოდირების თეორიაში. გიბსის უტოლობა ორი განსხვავებული ალბათობის განაწილებისთვის pi და qi არის ამ თეორიის ერთ-ერთი მნიშვნელოვანი შედეგი. ამიტომ ეს უნდა დავამტკიცოთ

მტკიცებულება ეფუძნება აშკარა გრაფიკს, ნახ. 13.I, რაც აჩვენებს იმას

და ტოლობა მიიღწევა მხოლოდ მაშინ, როდესაც x = 1. მოდით გამოვიყენოთ უტოლობა ჯამის თითოეულ წევრზე მარცხენა მხრიდან:

თუ საკომუნიკაციო სისტემის ანბანი შედგება q სიმბოლოსგან, მაშინ თითოეული სიმბოლოს გადაცემის ალბათობა qi = 1/q და q ჩანაცვლებით, მივიღებთ გიბსის უტოლობას.

სურათი 13.I

ეს ნიშნავს, რომ თუ ყველა q სიმბოლოს გადაცემის ალბათობა იგივეა და ტოლია - 1/q, მაშინ მაქსიმალური ენტროპია უდრის ln q, წინააღმდეგ შემთხვევაში უტოლობა მოქმედებს.

ცალსახად დეკოდირებადი კოდის შემთხვევაში გვაქვს კრაფტის უტოლობა

ახლა თუ განვსაზღვრავთ ფსევდო ალბათობებს

სადაც რა თქმა უნდა = 1, რომელიც გამომდინარეობს გიბსის უტოლობიდან,

და გამოვიყენოთ ცოტა ალგებრა (გახსოვდეთ, რომ K ≤ 1, ასე რომ, ჩვენ შეგვიძლია დავტოვოთ ლოგარითმული წევრი და, შესაძლოა, მოგვიანებით გავაძლიეროთ უტოლობა), მივიღებთ

სადაც L არის კოდის საშუალო სიგრძე.

ამრიგად, ენტროპია არის მინიმალური ზღვარი ნებისმიერი სიმბოლო-სიმბოლო კოდისთვის, საშუალო კოდური სიტყვის სიგრძით L. ეს არის შენონის თეორემა ჩარევისგან თავისუფალი არხისთვის.

ახლა განვიხილოთ მთავარი თეორემა საკომუნიკაციო სისტემების შეზღუდვების შესახებ, რომლებშიც ინფორმაცია გადაეცემა დამოუკიდებელი ბიტების ნაკადის სახით და არსებობს ხმაური. გასაგებია, რომ ერთი ბიტის სწორი გადაცემის ალბათობა არის P > 1/2, და ალბათობა იმისა, რომ ბიტის მნიშვნელობა გადაიქცევა გადაცემის დროს (დადგება შეცდომა) უდრის Q = 1 - P. მოხერხებულობისთვის, ჩვენ დავუშვათ, რომ შეცდომები დამოუკიდებელია და შეცდომის ალბათობა იგივეა თითოეული გაგზავნილი ბიტისთვის - ანუ არის "თეთრი ხმაური" საკომუნიკაციო არხში.

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

(გამომგზავნი)
განრიგი 13.II

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

სადაც, როგორც ადრე, P არის შეცდომის ალბათობა რომელიმე გაგზავნილ ბიტში. n დამოუკიდებელი ბიტის გაგზავნისას არხის მოცულობა მოცემულია

თუ ჩვენ ახლოს ვართ არხის სიმძლავრესთან, მაშინ უნდა გავაგზავნოთ თითქმის ამ რაოდენობის ინფორმაცია თითოეული სიმბოლოსთვის ai, i = 1, ..., M. იმის გათვალისწინებით, რომ ყოველი სიმბოლო ai-ის გაჩენის ალბათობა არის 1/M, ვიღებთ

როდესაც ვგზავნით რომელიმე M თანაბრად სავარაუდო შეტყობინებას ai, გვაქვს

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

ასე რომ, გადამცემის მხრიდან, მე ვიღებ გზავნილს ai, რომ გავაგზავნო და მის გარშემო რადიუსის მქონე სფერო დავხატო

რომელიც ოდნავ აღემატება e2-ის ტოლი ოდენობით Q შეცდომების მოსალოდნელ რაოდენობას (სურათი 13.II). თუ n საკმარისად დიდია, მაშინ არსებობს თვითნებურად მცირე ალბათობა იმისა, რომ შეტყობინების წერტილი bj გამოჩნდება მიმღების მხარეს, რომელიც ვრცელდება ამ სფეროს მიღმა. მოდით დავხატოთ სიტუაცია ისე, როგორც ამას მე ვხედავ გადამცემის თვალსაზრისით: ჩვენ გვაქვს ნებისმიერი რადიუსი გადაცემული გზავნილიდან ai-დან მიღებულ შეტყობინებამდე bj, შეცდომის ალბათობით ნორმალური განაწილების ტოლი (ან თითქმის ტოლი) და აღწევს მაქსიმუმს. nQ-ში. ნებისმიერი მოცემული e2-სთვის არის n იმდენად დიდი, რომ იმის ალბათობა, რომ შედეგი bj წერტილი იყოს ჩემი სფეროს გარეთ, ისეთივე მცირეა, რამდენიც გინდა.

ახლა მოდით შევხედოთ იმავე სიტუაციას თქვენი მხრიდან (სურ. 13.III). მიმღების მხარეს არის სფერო S(r) იგივე რადიუსით r მიღებულ bj წერტილის გარშემო n-განზომილებიან სივრცეში, ასე რომ თუ მიღებული შეტყობინება bj არის ჩემს სფეროს შიგნით, მაშინ ჩემს მიერ გაგზავნილი გზავნილი ai არის თქვენს შიგნით. სფერო.

როგორ შეიძლება მოხდეს შეცდომა? შეცდომა შეიძლება მოხდეს ქვემოთ მოცემულ ცხრილში აღწერილი შემთხვევებში:

სურათი 13.III

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

ჩვენ გვაქვს Pe შეცდომის ალბათობის მათემატიკური განტოლება, თუ გაგზავნილი იყო ai შეტყობინება

ჩვენ შეგვიძლია გადავაგდოთ პირველი ფაქტორი მეორე წევრში, ავიღოთ როგორც 1. ამრიგად მივიღებთ უტოლობას

ცხადია,

შესაბამისად

ხელახლა მიმართეთ ბოლო ტერმინს მარჯვნივ

n-ის საკმარისად დიდი მნიშვნელობით, პირველი ტერმინი შეიძლება მივიღოთ როგორც პატარა, როგორც გსურთ, ვთქვათ, d-ზე ნაკლები რიცხვი. ამიტომ გვაქვს

ახლა ვნახოთ, როგორ შეგვიძლია ავაშენოთ მარტივი ჩანაცვლების კოდი n ბიტისაგან შემდგარი M შეტყობინებების დაშიფვრისთვის. წარმოდგენა არ ჰქონდა, თუ როგორ უნდა აეშენებინა კოდი (შეცდომის გამოსწორების კოდები ჯერ არ იყო გამოგონილი), შენონმა აირჩია შემთხვევითი კოდირება. გადააბრუნეთ მონეტა შეტყობინებაში n ბიტიდან თითოეულისთვის და გაიმეორეთ პროცესი M შეტყობინებებისთვის. მთლიანობაში, nM მონეტის გადახვევა საჭიროა, ასე რომ შესაძლებელია

კოდის ლექსიკონები იგივე ალბათობით ½nM. რა თქმა უნდა, კოდის წიგნის შექმნის შემთხვევითი პროცესი ნიშნავს, რომ არსებობს დუბლიკატების შესაძლებლობა, ასევე კოდის წერტილები, რომლებიც ახლოს იქნება ერთმანეთთან და, შესაბამისად, იქნება სავარაუდო შეცდომების წყარო. უნდა დაამტკიცოს, რომ თუ ეს არ მოხდება შეცდომის რომელიმე მცირე არჩეულ დონეზე მეტი ალბათობით, მაშინ მოცემული n საკმარისად დიდია.
გადამწყვეტი წერტილი არის ის, რომ შენონმა საშუალო შეცდომის საპოვნელად ყველა შესაძლო კოდის წიგნაკი დაადგინა! ჩვენ გამოვიყენებთ სიმბოლოს Av[.], რათა აღვნიშნოთ საშუალო მნიშვნელობა ყველა შესაძლო შემთხვევითი კოდის წიგნის სიმრავლეზე. საშუალოდ d მუდმივზე, რა თქმა უნდა, იძლევა მუდმივას, რადგან საშუალოდ თითოეული წევრი იგივეა, რაც ყველა სხვა წევრი ჯამში,

რომელიც შეიძლება გაიზარდოს (M–1 მიდის M-მდე)

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

სადაც s=Q+e2 <1/2 და ns უნდა იყოს მთელი რიცხვი.

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

დააკვირდით, როგორ გამოჩნდა ენტროპია H(s) ბინომიალურ იდენტურობაში. გაითვალისწინეთ, რომ ტეილორის სერიის გაფართოება H(s)=H(Q+e2) იძლევა მიღებულ შეფასებას მხოლოდ პირველი წარმოებულის გათვალისწინებით და ყველა დანარჩენის იგნორირება. ახლა მოდით შევკრიბოთ საბოლოო გამონათქვამი:

სადაც

საკმარისია ავირჩიოთ e2 ისე, რომ e3 < e1, და შემდეგ ბოლო წევრი იქნება თვითნებურად მცირე, რამდენადაც n საკმარისად დიდია. შესაბამისად, საშუალო PE ცდომილება შეიძლება მიღებულ იქნეს რაც შეიძლება მცირე, არხის სიმძლავრით თვითნებურად ახლოს C-სთან.
თუ ყველა კოდის საშუალოს აქვს საკმარისად მცირე შეცდომა, მაშინ მინიმუმ ერთი კოდი უნდა იყოს შესაფერისი, შესაბამისად, არსებობს მინიმუმ ერთი შესაფერისი კოდირების სისტემა. ეს არის შენონის მიერ მიღებული მნიშვნელოვანი შედეგი - "შენონის თეორემა ხმაურიანი არხისთვის", თუმცა უნდა აღინიშნოს, რომ მან ეს დაამტკიცა ბევრად უფრო ზოგადი შემთხვევისთვის, ვიდრე უბრალო ორობითი სიმეტრიული არხისთვის, რომელიც მე გამოვიყენე. ზოგადი შემთხვევისთვის, მათემატიკური გამოთვლები ბევრად უფრო რთულია, მაგრამ იდეები არც თუ ისე განსხვავებულია, ამიტომ ძალიან ხშირად, კონკრეტული შემთხვევის მაგალითის გამოყენებით, შეგიძლიათ გამოავლინოთ თეორემის ნამდვილი მნიშვნელობა.

გავაკრიტიკოთ შედეგი. ჩვენ არაერთხელ გავიმეორეთ: „საკმარისად დიდი n-ისთვის“. მაგრამ რამდენად დიდია n? ძალიან, ძალიან დიდი, თუ ნამდვილად გსურთ იყოთ არხის სიმძლავრესთან ახლოს და დარწმუნებული იყოთ მონაცემთა სწორ გადაცემაში! იმდენად დიდი, ფაქტობრივად, რომ მოგიწევთ ძალიან დიდი ხნის ლოდინი, რათა დააგროვოთ საკმარისი ბიტის შეტყობინება, რათა მოგვიანებით დაშიფროთ. ამ შემთხვევაში, შემთხვევითი კოდის ლექსიკონის ზომა უბრალოდ უზარმაზარი იქნება (ბოლოს და ბოლოს, ასეთი ლექსიკონი არ შეიძლება იყოს წარმოდგენილი უფრო მოკლე ფორმით, ვიდრე ყველა Mn ბიტის სრული სია, მიუხედავად იმისა, რომ n და M ძალიან დიდია)!

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

ამასთან, ზემოთ დადასტურებული თეორემა მაინც არ არის უაზრო! ეს გვიჩვენებს, რომ ეფექტური გადაცემის სისტემებმა უნდა გამოიყენონ ჭკვიანური კოდირების სქემები ძალიან გრძელი ბიტიანი სტრიქონებისთვის. ამის მაგალითია თანამგზავრები, რომლებიც გაფრინდნენ გარე პლანეტების მიღმა; როდესაც ისინი შორდებიან დედამიწიდან და მზიდან, ისინი იძულებულნი არიან გამოასწორონ უფრო და უფრო მეტი შეცდომა მონაცემთა ბლოკში: ზოგიერთი თანამგზავრი იყენებს მზის პანელს, რომელიც უზრუნველყოფს დაახლოებით 5 ვტ-ს, ზოგი იყენებს ბირთვული ენერგიის წყაროებს, რომლებიც დაახლოებით იგივე სიმძლავრეს იძლევა. ელექტრომომარაგების დაბალი სიმძლავრე, გადამცემი ჭურჭლის მცირე ზომა და მიმღების ჭურჭლის შეზღუდული ზომა დედამიწაზე, უზარმაზარი მანძილი, რომელიც უნდა გაიაროს სიგნალმა - ეს ყველაფერი მოითხოვს კოდების გამოყენებას მაღალი დონის შეცდომის კორექტირებით. ეფექტური საკომუნიკაციო სისტემა.

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

ინფორმაციის თეორია არ გვეუბნება, თუ როგორ შევქმნათ ეფექტური სისტემა, მაგრამ ის მიუთითებს გზაზე ეფექტური საკომუნიკაციო სისტემებისკენ. ეს არის ღირებული ინსტრუმენტი მანქანა-მანქანა საკომუნიკაციო სისტემების შესაქმნელად, მაგრამ, როგორც უკვე აღვნიშნეთ, მას მცირე მნიშვნელობა აქვს იმასთან, თუ როგორ ურთიერთობენ ადამიანები ერთმანეთთან. რამდენად ჰგავს ბიოლოგიური მემკვიდრეობა ტექნიკური საკომუნიკაციო სისტემებს, უბრალოდ უცნობია, ამიტომ ამჟამად უცნობია, თუ როგორ ვრცელდება ინფორმაციის თეორია გენებზე. ჩვენ სხვა არჩევანი არ გვაქვს გარდა იმისა, რომ ვცადოთ და თუ წარმატება გვაჩვენებს ამ ფენომენის მანქანურ ბუნებას, მაშინ წარუმატებლობა მიუთითებს ინფორმაციის ბუნების სხვა მნიშვნელოვან ასპექტებზე.

მოდი, ზედმეტად ნუ დავივიწყებთ. ჩვენ დავინახეთ, რომ ყველა ორიგინალური განმარტება, მეტ-ნაკლებად, უნდა გამოხატავდეს ჩვენი თავდაპირველი რწმენის არსს, მაგრამ ისინი ხასიათდებიან გარკვეული დამახინჯებით და, შესაბამისად, არ გამოიყენება. ტრადიციულად მიღებულია, რომ საბოლოო ჯამში, ჩვენ მიერ გამოყენებული განმარტება რეალურად განსაზღვრავს არსს; მაგრამ, ეს მხოლოდ გვეუბნება, თუ როგორ უნდა დავამუშავოთ საგნები და არანაირად არ გადმოგვცემს რაიმე მნიშვნელობას. პოსტულაციური მიდგომა, რომელიც ასე ძლიერად არის მოწონებული მათემატიკურ წრეებში, პრაქტიკაში სასურველს ტოვებს.

ახლა ჩვენ განვიხილავთ IQ ტესტების მაგალითს, სადაც განმარტება ისეთივე წრიულია, როგორც თქვენ გინდათ, და, შედეგად, შეცდომაში შემყვანი. იქმნება ტესტი, რომელიც უნდა გაზომოს ინტელექტი. შემდეგ გადაიხედება, რათა მაქსიმალურად თანმიმდევრული იყოს, შემდეგ გამოქვეყნდება და, მარტივი მეთოდით, კალიბრირებულია ისე, რომ გაზომილი „ინტელექტი“ ნორმალურად განაწილებული აღმოჩნდეს (რა თქმა უნდა, კალიბრაციის მრუდზე). ყველა განმარტება ხელახლა უნდა გადამოწმდეს, არა მხოლოდ პირველად შემოთავაზებული, არამედ მოგვიანებით, როდესაც ისინი გამოიყენებენ გამოტანილ დასკვნებს. რამდენად შეესაბამება განსაზღვრული საზღვრები პრობლემის გადასაჭრელად? რამდენად ხშირად გამოიყენება ერთ პარამეტრში მოცემული განმარტებები სრულიად განსხვავებულ პარამეტრებში? ეს საკმაოდ ხშირად ხდება! ჰუმანიტარულ მეცნიერებებში, რომელსაც აუცილებლად შეხვდებით თქვენს ცხოვრებაში, ეს უფრო ხშირად ხდება.

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

ედინგტონის ცნობილი ისტორია მოგვითხრობს ადამიანებზე, რომლებიც ბადით თევზაობდნენ ზღვაში. მათ მიერ დაჭერილი თევზის ზომის შესწავლის შემდეგ დაადგინეს თევზის მინიმალური ზომა, რომელიც ზღვაში გვხვდება! მათი დასკვნა გამოწვეული იყო გამოყენებული ინსტრუმენტით და არა რეალობით.

გაგრძელება იქნება ...

ვისაც სურს დაგეხმაროთ წიგნის თარგმნაში, განლაგებაში და გამოცემაში - მოგვწერეთ პირად შეტყობინებაში ან მეილში [ელ.ფოსტით დაცულია]

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

ჩვენ განსაკუთრებით ვეძებთ ვისაც შეუძლია თარგმნაში დახმარება ბონუს თავი, რომელიც მხოლოდ ვიდეოზეა. (გადარიცხვა 10 წუთით, პირველი 20 უკვე აღებულია)

წიგნის შინაარსი და ნათარგმნი თავებიწინასიტყვაობა

1. შესავალი მეცნიერებისა და ინჟინერიის კეთების ხელოვნებაში: სწავლის სწავლა (28 წლის 1995 მარტი) თარგმანი: თავი 1
2. "ციფრული (დისკრეტული) რევოლუციის საფუძვლები" (30 წლის 1995 მარტი) თავი 2. ციფრული (დისკრეტული) რევოლუციის საფუძვლები
3. "კომპიუტერების ისტორია - აპარატურა" (31 მარტი, 1995 წ.) თავი 3. კომპიუტერების ისტორია – აპარატურა
4. "კომპიუტერების ისტორია - პროგრამული უზრუნველყოფა" (4 აპრილი, 1995 წ.) თავი 4. კომპიუტერების ისტორია – პროგრამული უზრუნველყოფა
5. "კომპიუტერების ისტორია - აპლიკაციები" (6 წლის 1995 აპრილი) თავი 5: კომპიუტერების ისტორია - პრაქტიკული აპლიკაციები
6. "ხელოვნური ინტელექტი - ნაწილი I" (7 წლის 1995 აპრილი) თავი 6. ხელოვნური ინტელექტი - 1
7. "ხელოვნური ინტელექტი - ნაწილი II" (11 წლის 1995 აპრილი) თავი 7. ხელოვნური ინტელექტი - II
8. "ხელოვნური ინტელექტი III" (13 წლის 1995 აპრილი) თავი 8. ხელოვნური ინტელექტი-III
9. "n-განზომილებიანი სივრცე" (14 წლის 1995 აპრილი) თავი 9. N-განზომილებიანი სივრცე
10. "კოდირების თეორია - ინფორმაციის წარმოდგენა, ნაწილი I" (18 წლის 1995 აპრილი) თავი 10. კოდირების თეორია - ი
11. "კოდირების თეორია - ინფორმაციის წარმოდგენა, ნაწილი II" (20 აპრილი, 1995 წ.) თავი 11. კოდირების თეორია - II
12. „შეცდომის გამოსწორების კოდები“ (21 წლის 1995 აპრილი) თავი 12. შეცდომების გამოსწორების კოდები
13. „ინფორმაციის თეორია“ (25 აპრილი, 1995 წ.) თავი 13. ინფორმაციის თეორია
14. "ციფრული ფილტრები, ნაწილი I" (27 წლის 1995 აპრილი) თავი 14. ციფრული ფილტრები - 1
15. "ციფრული ფილტრები, ნაწილი II" (28 აპრილი, 1995 წ.) თავი 15. ციფრული ფილტრები - 2
16. "ციფრული ფილტრები, ნაწილი III" (2 მაისი, 1995 წ.) თავი 16. ციფრული ფილტრები - 3
17. "ციფრული ფილტრები, ნაწილი IV" (4 წლის 1995 მაისი) თავი 17. ციფრული ფილტრები - IV
18. "სიმულაცია, ნაწილი I" (5 წლის 1995 მაისი) თავი 18. მოდელირება - ი
19. "სიმულაცია, ნაწილი II" (9 წლის 1995 მაისი) თავი 19. მოდელირება - II
20. "სიმულაცია, ნაწილი III" (11 მაისი, 1995 წ.) თავი 20. მოდელირება - III
21. "ოპტიკურ-ბოჭკოვანი" (12 წლის 1995 მაისი) თავი 21. ბოჭკოვანი ოპტიკა
22. "კომპიუტერული ინსტრუქცია" (16 წლის 1995 მაისი) თავი 22: კომპიუტერული ინსტრუქცია (CAI)
23. „მათემატიკა“ (18 წლის 1995 მაისი) თავი 23. მათემატიკა
24. "კვანტური მექანიკა" (19 წლის 1995 მაისი) თავი 24. კვანტური მექანიკა
25. „კრეატიულობა“ (23 წლის 1995 მაისი). თარგმანი: თავი 25. კრეატიულობა
26. "ექსპერტები" (25 წლის 1995 მაისი) თავი 26. ექსპერტები
27. "არასანდო მონაცემები" (26 წლის 1995 მაისი) თავი 27. არასანდო მონაცემები
28. "სისტემური ინჟინერია" (30 წლის 1995 მაისი) თავი 28. სისტემური ინჟინერია
29. "თქვენ მიიღებთ იმას, რასაც ზომავთ" (1 ივნისი, 1995 წ.) თავი 29: თქვენ მიიღებთ იმას, რასაც ზომავთ
30. "როგორ ვიცით ის, რაც ვიცით" (ივნისი 2, 1995) თარგმნა 10 წუთში
31. ჰამინგი, „შენ და შენი კვლევა“ (6 ივნისი, 1995 წ.). თარგმანი: შენ და შენი საქმე

ვისაც სურს დაგეხმაროთ წიგნის თარგმნაში, განლაგებაში და გამოცემაში - მოგვწერეთ პირად შეტყობინებაში ან მეილში [ელ.ფოსტით დაცულია]

წყარო: www.habr.com