Коригиране на грешки на Рийд-Соломон
Коригирането на грешки на Рийд-Соломон е код за коригиране на грешки в права посока. Тя работи чрез свръхизбиране на полином, конструиран от данните. Полиномът се оценява в няколко точки и тези стойности се изпращат или записват. Вземането на проби от полинома по-често, отколкото е необходимо, прави полинома свръхдетерминиран. Докато получава "много" от точките правилно, приемникът може да възстанови оригиналния полином дори при наличието на "няколко" лоши точки.
Рийд-Соломоновите кодове се използват в много различни видове търговски приложения, например в компактдискове, DVD и Blu-ray дискове, в технологии за предаване на данни като DSL и WiMAX и в системи за излъчване като DVB и ATSC.
Преглед
Кодовете на Рийд-Соломон са блокови кодове. Това означава, че фиксиран блок от входни данни се обработва във фиксиран блок от изходни данни. В случая на най-често използвания R-S код (255, 223) - 223 входни символа на Рийд-Соломон (всеки с дължина осем бита) се кодират в 255 изходни символа.
- Повечето R-S ECC схеми са систематични. Това означава, че известна част от изходната кодова дума съдържа входните данни в оригиналния им вид.
- Избран е размер на символа на Рийд-Соломон от осем бита, тъй като декодерите за по-големи размери на символите биха били трудни за изпълнение с настоящата технология. Този избор на конструкция налага най-дългата кодова дума да бъде 255 символа.
- Стандартният код (255, 223) на Рийд-Соломон може да коригира до 16 грешки на символа на Рийд-Соломон във всяка кодова дума. Тъй като всеки символ всъщност е осем бита, това означава, че кодът може да коригира до 16 кратки серии от грешки, дължащи се на вътрешния конволюционен декодер.
Кодът на Рийд-Соломон, както и конволюционният код, е прозрачен код. Това означава, че ако символите на канала са били инвертирани някъде по линията, декодерите ще продължат да работят. Резултатът ще бъде допълнение на оригиналните данни. Въпреки това кодът на Рийд-Соломон губи своята прозрачност, ако се използва виртуално запълване с нула. Поради тази причина е задължително смисълът на данните (т.е. истински или допълнен) да бъде определен преди декодирането на Рийд-Соломон.
В случая на програмата Voyager R-S кодовете достигат почти оптимална производителност, когато са конкатенирани с (7, 1/2) конволюционен (Viterbi) вътрешен код. Тъй като за всяка грешка, която трябва да бъде коригирана, са необходими два контролни символа, това води до общо 32 контролни символа и 223 информационни символа на кодова дума.
Освен това кодовите думи на Рийд-Соломон могат да се редуват по символи, преди да бъдат кодирани по конволюционен път. Тъй като по този начин се разделят символите в кодовата дума, вероятността взрив от декодера на Витерби да наруши повече от един символ на Рийд-Соломон във всяка една кодова дума става по-малка.
Основна идея
Основната идея на кода на Рийд-Соломон е, че кодираните данни първо се визуализират като полином. Кодът се основава на теорема от алгебрата, която гласи, че всякакви k отделни точки определят еднозначно полином от степен най-много k-1.
Изпращачът определя степен k - 1 {\displaystyle k-1}
полином над крайно поле, който представя k {\displaystyle k}
точки с данни. След това полиномът се "кодира" чрез оценяването му в различни точки и тези стойности са това, което всъщност се изпраща. По време на предаването някои от тези стойности могат да се повредят. Затова в действителност се изпращат повече от k точки. Стига достатъчно стойности да бъдат получени правилно, приемникът може да заключи какъв е бил оригиналният полином и да декодира оригиналните данни.
В същия смисъл, в който може да се коригира крива чрез интерполиране на празнина, кодът на Рийд-Соломон може да преодолее поредица от грешки в блок от данни, за да възстанови коефициентите на полинома, който е начертал оригиналната крива.
История
Кодът е изобретен през 1960 г. от Ървинг С. Рийд и Густав Соломон, които тогава са членове на лабораторията "Линкълн" на Масачузетския технологичен институт. Тяхната основополагаща статия е озаглавена "Полиномиални кодове над определени крайни полета". Когато тя е написана, цифровата технология не е достатъчно напреднала, за да се приложи концепцията. Първото приложение през 1982 г. на RS кодове в масово произвеждани продукти е компактдискът, в който се използват два преплетени RS кода. Ефективен алгоритъм за декодиране на RS кодове на големи разстояния е разработен от Елуин Берлекамп и Джеймс Маси през 1969 г. Днес RS кодовете се използват в твърдите дискове, DVD, телекомуникациите и протоколите за цифрово излъчване.
