Коригиращи кодове - Информатика, програмиране
Курс: Теория на информацията и кодиране
Тема: КОРЕКЦИОННИ КОДОВЕ
1. КОРЕКЦИОННИ КОДОВЕ. ОСНОВНИ ПОНЯТИЯ
2. ЛИНЕЙНИ ГРУПОВИ КОДОВЕ
1. КОРЕКЦИОННИ КОДОВЕ. ОСНОВНИ ПОНЯТИЯ
В съответствие с теоремата на Шанън за дискретен канал с шум, вероятността от грешка при предаване на данни по комуникационен канал може да бъде произволно малка при избора на подходящ метод за кодиране на сигнала, т.е. шумът не налага значителни ограничения върху точността на предаване на информация (данни). Надеждността на предадената информация може да се гарантира чрез използването на коригиращи кодове.
Кодовете за коригиране или коригиране на шума се наричат кодове, които ви позволяват да откривате и премахвате грешки при предаването на информация поради смущения.
Най-разпространен е класът кодове с единична корекция на грешки и двойно откриване на грешки (CO-OD). Най-известният сред тези кодове е кодът на Хеминг, който има прост и технически удобен алгоритъм за откриване и коригиране на една грешка.
В компютрите тези кодове се използват за подобряване на надеждността на паметта с произволен достъп (RAM) и магнитните дискове. Броят на грешките в компютъра зависи от вида на неизправностите в елементите на веригата (например повреда в един елемент на интегрална схема (ИС) причинява единична грешка, а в цялата ОП на ИС - множествена). За откриване на множество грешки се използва кодът CO-OD-OG (корекция на единична грешка, откриване на двойна грешка и откриване на множество грешки в група от битове със същото име).
Сред коригиращите кодове широко се използват циклични кодове; в компютъра тези кодове се използват за сериен трансфер на данни между компютър и външни устройства, както и за предаване на данни по комуникационни канали. За коригиране на две или повече грешки (d0 ³ 5)използват се циклични BCH кодове (Bose - Chowdhury - Hockwingham), както и Reed-Solomon, които се използват широко в устройствата за цифров звукозапис на магнитна лента или оптични CD и позволяват групова корекция на грешки. Способността на кода да открива и коригира грешки се постига чрез въвеждане на излишък в кодови комбинации, т.е. кодови комбинации от k двоични информационни символи, влизащи на входа на енкодера, съответстват на последователност от n двоични символа на изхода (такъв код се нарича (n, k) - код).
Ако N0 = 2 n е общият брой кодови комбинации, а N = 2 k е броят на разрешените, тогава броят на забранените кодови комбинации е равен на
В този случай броят на грешките, които водят до забранена кодова комбинация е равен на:
, (1)
където S е множествеността на грешката, т.е. броят на изкривените символи в кодовата комбинация S = 0, 1, 2, .
Cn i - комбинации от n елемента по i, изчислени по формулата:
, (2)
за S = 0;
S = 1;
S = 2;
S = 3; и т.н.
За да се коригират S грешки, броят на комбинациите на кодовата дума, съставена от m контролни бита N = 2 m, трябва да бъде по-голям от възможния брой грешки (2), докато броят на откритите грешки е два пъти по-голям от коригирания
(3)
2 m ³ от където .
За единична грешка, като най-вероятната .
В зависимост от първоначалните кодови данни (n или k), можете да използвате
. (4)
В този случай m = [log2(1+n)] или m = [log2 2(k+1)]>], където квадратните скоби означават закръгляване до по-високо цяло число.
Таблица 1 показва връзката между дължината на кодовата комбинация и броя на информационните и контролните битове за коригиращия код.единична грешка, както и ефективността на използване на комуникационния канал.
За коригиране на двойна грешка
или . (5)
Въвеждането на излишък в кодовите комбинации при използване на коригиращи кодове значително намалява скоростта на предаване на информация и ефективността на използване на комуникационния канал.
Например за код (31, 26) скоростта на предаване на информация е равна на
,
т.е. скоростта на предаване е намалена с 16%.
Таблица 1
| н | 7 | 10 | 15 | 31 | 63 | 127 | 255 |
Както може да се види от таблица 1, колкото по-голямо е n, толкова по-ефективно се използва каналът.
Пример 1. Определете броя на контролните цифри за систематичен код, който коригира една грешка и се състои от 20 информационни бита.
Решение: Общата дължина на кодовата комбинация е n = k + m, където k е броят на информационните битове, а m са битовете за проверка.
За откриване на двойна грешка и коригиране на единична грешка, зависимостите за битовете имат формата , докато