Bell Labs, 1947
Richard Hamming 1946 წელს Bell Telephone Laboratories-ში გაწევრდა. იქ ჯერ გამოთვლილი მანქანები მხოლოდ კვირის დღეებში მუშაობდნენ, როდესაც ტექნიკოსებს შეუძლიათ მათი რეაგირება შეცდომების შემდეგ. კვირის ბოლოებში მანქანები ჩერდებოდნენ, როდესაც რომელიმე რამე არ შედეგობდა — სამუშაოებს დილემა დაემართებოდა მომდევნო ორშაბათამდე.
Hamming გაბრაზდა. "თუ მანქანამ შეუძლია შეცდომის აღმოჩენა," მან იფიქრა, "რატომ არ შეუძლია მის პოვნა და გამკრთალება?" ეს განწუხვა, კომბინირებული ორობითი არითმეტიკაში ღრმა ცოდნის და პარიტეტის შემოწმებასთან, ადგილი გააკეთა აღმოჩენას.
პირველი შეხედულება: მართკუთხა კოდები
Hamming-ის პირველი იდეა: შეტყობინების ბიტები მ×ნ მართკუთხედში განლაგოთ, დაამატოთ პარიტეტის შემოწმება ყველა სტრიქონისა და ყველა სვეტის. ერთი შეცდომა ზუსტად ერთი ფაილი სტრიქონის შემოწმება & ერთი ფაილი სვეტის შემოწმება. მათი გადაკვეთა აძებს შეცდომის პოზიციას.
სიჭარბე თანაფარდობა: (m+1)(n+1) / mn. კალკულუსი გეუბნებთ, რომ კვადრატი ამინიმებს ამას ფიქსირებული შეტყობინების ზომისთვის. მაგრამ m & n რომ გაიზრდება, ორმაგი შეცდომა უფრო სავარაუდო ხდება — ინჟინერული გადაწყვეტილება არ აქვს უნივერსალური პასუხი.
მართკუთხა სიჭარბის მინიმიზაცია
4×4 მართკუთხედი 16 შეტყობინების ბიტი ატარებს 4 სტრიქონის შემოწმება & 4 სვეტის შემოწმება, პლიუს 1 კუთხის პარიტეტი = 9 შემოწმების ბიტი 16 შეტყობინების ბიტისთვის.
სიჭარბე თანაფარდობა: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
10×10 მართკუთხედის: 100 შეტყობინების ბიტი, 121 სულ ბიტი, სიჭარბე ≈ 1.21.
სინდრომი, როგორც ორობითი რიცხვი
რამდენიმე კვირის შემდეგ მართკუთხა კოდის ინსაიტის, Hamming ჯერელი ძველი Jersey ფერმების მეშვეობით მართავდა New York-მდე, მის წარმატებებს გონებაში მიმოიხილა. სამკუთხედი კოდი დაგვხვდა — უკეთ სიჭარბე. შემდეგ კუბი. შემდეგ 4-განზომილებიანი, 5-განზომილებიანი...
თითოეული დამატებითი განზომილება უმჯობესდა სიჭარბეს. n განზომილებაში გვერდის ჰიპერკუბი 2 გამოიყენებს მხოლოდ n+1 პარიტეტის შემოწმება 2^n წვერი. მაგრამ ოპტიმალური იყო?
დათვლის არგუმენტი
n+1 პარიტეტის ბიტი წარმოქმნის სინდრომს: (n+1)-ბიტი ორობითი რიცხვი. ეს სინდრომი საჭიროა 2^n + 1 მკაფიო შედეგი: თითოეული 2^n შეცდომის პოზიცია, პლიუს სპეციალური 'შეცდომა არა' შედეგი.
2^(n+1) = 2·2^n — თითქმის საკმარისი. 2 ფაქტორით დავკარგეთ. Hamming პრობლემა სამუშაო მაგიდაზე დასვა.
გასაბამი ინსაიტი
მოგვიანებით, Hamming დაბრუნდა ახალი იდეით: სინდრომი თავად გამოიყენო ორობითი რიცხვი რომელიც აძებს შეცდომის პოზიცია. პოზიცია 1 = ორობითი 001, პოზიცია 2 = ორობითი 010, პოზიცია 3 = ორობითი 011, და ა.შ. რეზერვი ყველა-ნულის 'შეცდომა არა.'
ეს გადასცემს სინდრომს პარიტეტის შემოწმებების აწარმოობიდან მისამართად. პარიტეტის შემოწმებები დაფიქსირდებიან წარმოქმნელი ზუსტი მისამართი რომელი ერთი ბიტი გამორთაა.
(7,4) კოდის დიზაინი
7-ბიტი კოდისთვის (3 პარიტეტის ბიტი, 4 შეტყობინების ბიტი), პოზიციები 1 ხელმძღვანელობა 7 ორობითად არის: 001, 010, 011, 100, 101, 110, 111.
პარიტეტის შემოწმება 1 ფარავს პოზიციებს სადაც ბიტი 0 = 1: პოზიციები 1, 3, 5, 7.
პარიტეტის შემოწმება 2 ფარავს პოზიციებს სადაც ბიტი 1 = 1: პოზიციები 2, 3, 6, 7.
პარიტეტის შემოწმება 3 ფარავს პოზიციებს სადაც ბიტი 2 = 1: პოზიციები 4, 5, 6, 7.
პარიტეტის ბიტი ოკუპირებს ძალაუფლების-ორი პოზიციები: 1, 2, 4. შეტყობინების ბიტი ოკუპირებს დანარჩენი: 3, 5, 6, 7.
თუ ბიტი 6 გამორთა, პარიტეტის შემოწმება 2 & 3 წარუმატებელი (110 ორობითად = 6). სინდრომი კითხულობს 110 = 6. გამორთვა პოზიცია 6. შესრულებული.
ერთი შეცდომა გასწორება, ორმაგი შეცდომა აღმოჩენა
(7,4) Hamming კოდი გასწორებს ერთი შეცდომები. მაგრამ რა თუ ორი ბიტი გამორთა? დამატებითი დაცვა გარეშე, დეკოდერი იყენებს სინდრომის წესი და 'გამკრთალება' კოდსიტი არასწორი შეტყობინება — ჩუმი მიკორექტია.
SECDED: ერთი მეტი პარიტეტი ბიტი
დამატოთ ერთი პარიტეტი ბიტი p₀ დამფარი მთელი კოდსიტი (ყველა 7 ბიტი). ახლა სინდრომი აქვს 4 ჩანაწერი: ორიგინალური 3 შემოწმება პლიუს p₀.
``
ძველი სინდრომი ახალი p₀ მნიშვნელობა
000 0 სწორი
000 1 შეცდომა p₀ მხოლოდ
xxx 1 ერთი შეცდომა, ძველი სინდრომი აძებს იგი
xxx 0 ორმაგი შეცდომა — დროშა იგი
``
ოთხი შემთხვევა აქვს ანტოლოგია. ორმაგი შეცდომა გამორთა ორი ბიტი: ძველი სინდრომი არ იკითხებ 000 (ორივე ბიტი ერთად კორუპტი ორი მისი შემოწმება), მაგრამ p₀ გამორთა ორჯერ და აბრუნებს 0. ნიმუში xxx + 0 არის გარკვევამი.
რატომ SECDED მუშაობს
SECDED წესი სარჩეზია პარიტეტის მოდულური სტრუქტურა. თუთიუ პარიტეტი, ნებისმიერი ერთი გამორთვა უცვლელი p₀. ნებისმიერი ორმაგი გამორთვა ტოვებს p₀ უცვლელი. ასე რომ p₀ თვლის შეცდომები მოდულო 2.
გეომეტრიული სურათი
Hamming ამოვიდა იმავე ადგილი განსხვავებული მიმართულება: ანალიტიკური გეომეტრია. წარმოდგენა თითოეული n-ბიტი სიმებიანი როგორც წვერი n-განზომილებიანი ჰიპერკუბი. ერთი ბიტი გამორთვა გადაიტანს წერტილი ერთი ზღვარი-სიგრძე გასწვრივ ერთი ღერძი. ორი გამორთვა: ორი ზღვარი. მეტრი არის Hamming მანძილი.
განსაზღვრება Hamming ბურთი რადიუსი t ირგვლივ კოდსიტი c: ყველა წერტილი დაშორებული t ბიტი-გამორთვა c. ერთი-შეცდომა გასწორება, t = 1.
პირობა ერთი-შეცდომა გასწორება: ბურთი რადიუსი 1 გარშემო ყველა წყვილი მკაფიო კოდსიტი უნდა არ მოიპაროს. თუ ისინი მოიპაროს, მიღებული სიტყვა ოვერლაპი შეიძლება კუთვნილი ან კოდსიტი და დეკოდერი ხარვეზი.
ეს გადაწერა პირდაპირი მინიმალური მანძილი: ორი ბურთი რადიუსი 1 არ მოიპაროს თუ და მხოლოდ თუ კოდსიტი ეზე მინიმუმ 3 მეშორეობა (d_min ≥ 3).
(7,4) კოდი აღწევს d_min = 3. Hamming შემოსაზღვრულობა: 2^7 / (1 + 7) = 16 = 2^4. ზუსტი 16 კოდსიტი. A სრულ კოდი: 16 ბურთი რადიუსი 1 ფილე {0,1}^7 გარეთ არა გამოტოვა ან ოვერლაპი.
ინჟინერული სამსჯელო
Hamming იყო მკაფიო: შეცდომის-კორექტირება კოდი მოიცავს ინჟინერული სამსჯელო, არა სუფთა მათემატიკა.
შეტყობინების სიგრძე: უფრო დიდი შეტყობინება ხელმძღვანელობა უფრო ეფექტური კოდირება (ჟურნალი n პარიტეტი ბიტი n შეტყობინება ბიტი). მაგრამ უფრო დიდი შეტყობინება აგრეთვე დაგროვება მეტი ხმა, ასაკი მეტი შეცდომა ორმაგი შეცდომა სკვიზი წყვილი ერთად ყალბი ერთი გასწორება.
დონე გასწორება vs. აღმოჩენა: ვაჭრობა ერთი შეცდომა გასწორება ორი დამატებითი შეცდომა აღმოჩენა. მეტი ოპტიმალური გაყოფა დამოკიდებული არხი ხმა მახასიათებელი.
ველი შენარჩუნება ღირებულება: როგორც აპარატურა იზრდება უფრო კოთხე, ველი ტექნიკოსი არ შეუძლია დიაგნოზი ყოველი ხარვეზი წაბინიშვნიდან პრინციპი. თვით-დიაგნოსტირება სისტემა აკვილი ამცირებს მას გაწერება საჭირო შენარჩუნება. Hamming ფარი აი ერთი ყველაზე მნიშვნელოვანი სარგებელი, ხშირად უფრო მნიშვნელოვანი ვიდრე ნაჭუჭ საიმედოობა მოგება.
სტილი: იღბალი მომზადებულ გონებას ემხნიათ
Hamming დახურა თავი 12 პირდაპირი გამოწვევა. აღწერა აღმოჩენა როგორც მოითხოვა სამ ხვიდან ექვსი თვე काम, უმეტესწილი კენწირ მომენტი ხელმძღვანელობა მას მთავარი კარტი Bell Labs.
აღმოჩენილი სამი რამ რომელმაც მას შესაძლებელი გაკეთება:
1. მომზადება: ღრმა მიმდინარე პარიტეტი შემოწმება, ორობითი არითმეტიკა, & ჯგუფი თეორია, მანამდე პრობლემა გაჩნდა.
2. ბიჭ წარმატებები: სასიცოცხლო რეპლეი წარსული გამოსავალი ინტერნალაიზ იმათი სტილი. სამკუთხედი კოდი მოხდა მას მანამდე მიმოიხილა მართკუთხა კოდი კომ.
3. არ მოკმედება 'გამოიყურება კარგი': აღწერა წაკიდა თავი მას მხარდამჭერი გამოკვლეულ ოპტიმალური. მან თხოვა სანამ აღწერა დამტკიცება კოდი იყო საუკეთესო.