Кодове с откриване и коригиране на грешки
Когато информацията се прехвърля постоянно между различни части на компютъра, съхранена в устройство с памет, има вероятност полученият битов модел да бъде различен от оригинала. Частици мръсотия или мазнини върху повърхността на магнитния запис, случайна грешка в работата на електронната верига - всичко това може да причини грешки при запис или четене на данни. Освен това при някои технологии за съхранение на данни фоновото излъчване може да промени моделите на битове, съхранени в основната памет на машината.
За да се решат тези проблеми, са разработени много технологии за кодиране на данни за откриване и дори коригиране на такива грешки. В момента тези технологии се използват широко при създаването на вътрешните компоненти на компютрите, така че остават невидими за потребителите, работещи с машината. Те обаче са изключително важни и това още веднъж подчертава важността на резултатите от проведените изследвания. Всъщност по-голямата част от работата по създаването на такива технологии беше извършена от теоретични математици. По-долу разглеждаме някои от методите, които гарантират надеждността на функционирането на съвременните компютри.
Код за паритет
Има доста прост начин за откриване на грешки, базиран на принципа, че ако всяка обработена битова комбинация се състои от четен брой единици, тогава откриването на комбинация с нечетен брой единици ще покаже грешка.
За да се използва този принцип, е необходимо да се създаде система, в която всяка битова комбинация ще съдържа четен брой единици. Това обикновено се постига чрез добавяне на допълнителен бит към вече съществуващия код [който се нарича битпаритет или контролен бит], най-често поставен в горния край на комбинацията. В резултат на това осембитовият ASCII код става деветбитов, а шестнадесетбитовият битов модел в комплемента на две става седемнадесетбитов. Във всеки случай стойността на бита за паритет е зададена на 0 или 1 въз основа на изискването целият битов модел да съдържа нечетен брой единици. Например знак A в ASCII код ще бъде представен като 101000000 [бит за четност 0], докато символ F в същия код ще бъде 001000111 [бит за четност 1]. Въпреки че оригиналният осембитов модел, представляващ буквата A, съдържа четен брой единици, а аналогичният модел, представляващ буквата F, има нечетен брой единици, и двата деветбитови кода имат четен брой единици. Ако системата е изградена по този начин, тогава появата на битов шаблон с нечетен брой единици ще покаже грешка и ще сигнализира, че данните, които се обработват, са неправилни.
В наши дни използването на паритетни битове е обичайно решение за основната памет на машината. Въпреки че на пръв поглед изглежда, че компютрите използват осембитови клетки с памет, те всъщност са деветбитови, като деветият бит се използва като контрол. Всеки път, когато в паметта се записва осембитов модел, схемата за управление на паметта автоматично добавя необходимия контролен бит към него, за да произведе деветбитов модел. При четене на информация схемата за управление на паметта отчита броя на единиците в получената комбинация. Ако не бъде открита грешка, контролният бит се премахва и се формира оригиналният осембитов битов модел. Иначе схемата за управлениепаметта връща прочетената осембитова стойност, което показва, че тя е изкривена и може да се различава от оригинала.
Дългите модели на битове често се допълват с група контролни битове, за да образуват контролен байт. Всеки бит в този байт е контролен бит и се отнася до специфична група от битове, разпръснати в основния битов модел. Например, един контролен бит може да бъде всеки осми бит, започващ от първия, докато друг би бил всеки осми бит, започвайки от втория и т.н. В този случай е по-лесно да се открият грешки, концентрирани в една област на оригиналната комбинация, тъй като тяхното присъствие ще се контролира от група контролни битове. Различни варианти на този подход за проектиране на контролни вериги се наричат метод на контролна сума и метод на код за проверка на цикличното излишък [CRC].
Кодове за корекция на грешки
Въпреки че битът за паритет е ефективен метод за откриване на грешки, той не предоставя необходимата информация за коригиране на възникналата грешка. Мнозина са изненадани от самия факт, че е възможно да се разработят кодове за коригиране на грешки, които позволяват не само да откриват грешки, но и да ги коригират. В крайна сметка интуицията ни подсказва, че не сме в състояние да коригираме грешка в полученото съобщение, ако не знаем предварително за какво става дума. Въпреки това има доста прост код, който ви позволява да коригирате възникналите грешки.
За да разберете как работи този код, първо трябва да определите разстоянието на Хеминг между две кодови комбинации, което ще бъде равно на броя на битовете, които се различават в тези комбинации. Концепцията за разстоянието на Хеминг получи името си в чест на R.V. Хеминг [R.W. Hamming], който проведе първото изследване в разработването на кодове за коригиране на грешки.Той се обърна към този проблем през 40-те години на миналия век поради изключителната ненадеждност на релейните компютри, които съществуваха по това време. Разгледайте следния код:
A 000000 B 001111 C 010011 D 011100 E 100110 F 101001 G 110101 H 111010
Разстоянието на Хеминг между кодовете за букви A и B е четири, а разстоянието на Хеминг между кодовете за букви B и C е три. Важна характеристика на този код е, че разстоянието на Хеминг между всеки две комбинации ще бъде поне три. Ако повреда доведе до грешна стойност в който и да е бит, тогава грешката ще бъде лесно открита, тъй като получената комбинация не е валидна кодова стойност. Всяка комбинация ще трябва да промени поне три бита, преди да стане отново валидна.
Ако възникне една единствена грешка във всяка комбинация, нейната първоначална стойност може лесно да бъде изчислена. Факт е, че разстоянието на Хеминг за модифицираната комбинация по отношение на оригиналната форма ще бъде равно на единица, докато по отношение на други разрешени комбинации ще бъде равно на поне две. Когато декодирате съобщение, е достатъчно просто да сравните всяка получена битова комбинация с валидни кодови комбинации, докато се намери комбинация, която е на разстояние равно на единица от получената комбинация. Намерената валидна кодова комбинация се приема като правилен знак, получен в резултат на декодирането. Да приемем, че е получена битова комбинация 010100. Ако я сравним с валидните битови комбинации на кода, ще се получи таблица на разстоянията:
A 2 B 4 C 3 D 1 E 3 F 5 G 2 H 4
Въз основа на съдържанието на тази таблица можем да заключим, че входящият знак е буквата D, тъй като нейната битова комбинация внай-съответстващо на полученото.