Код за исправљање грешака

У рачунарству, телекомуникацијама, теорији информација и теорији кодирања, код за исправљање грешака, или код кориговања грешака (енгл. error correcting code - ECC) користи се за контролу грешака у подацима преко непоузданих или бучних комуникационих канала. Централна идеја је да пошиљалац кодира поруку излишним информацијама у облику ЕЦЦ-а. Прекомерност омогућава примаоцу да открије ограничени број грешака које се могу појавити било где у поруци и често да их исправи без поновног преноса. Амерички математичар Ричард Хаминг је био пионир овог поља током 1940-их и изумео је први код за исправљање грешака 1950: Хемингов (7,4) код.

ЕЦЦ се разликује од откривања грешака јер се грешке које се нађу могу исправити, а не једноставно открити. Предност је у томе што систем који користи ЕЦЦ не захтева реверзни канал да захтева поновни пренос података када дође до грешке. Лоша страна је што се фиксни траснмисиони трошкови додају у поруку, што захтева већу пропусну ширину канала унапред. ЕЦЦ се стога примењује у ситуацијама када су поновни преноси скупи или немогући, као што су једносмерне комуникационе везе и приликом преноса на више пријемника у мултикасту. Од оваквог приступа такође имају користи и везе са дугим кашњењем; у случају да сателит кружи око Урана, поновни пренос због грешака може створити кашњење од пет сати.

Корекција грешака унапред

У телекомуникацијама, теорији информација и теорији кодирања, исправљање грешака унапред (енгл. forward error correction - FEC) или кодирање канала је техника која се користи за контролу грешака у преносу података преко непоузданих или бучних комуникационих канала. Централна идеја је да пошиљалац кодира поруку на редундантан начин, најчешће користећи ЕЦЦ.

Излишност омогућава примаоцу да открије ограничени број грешака које се могу појавити било где у поруци и често да их исправи без поновног преноса. ФЕЦ даје примаоцу могућност исправљања грешака без потребе за реверзним каналом да би се захтевао поновни пренос података, али по цени фиксног, већег пропусног опсега унапред. ФЕЦ се стога примењује у ситуацијама када су поновни преноси скупи или немогући, као што су једносмерне комуникационе везе и приликом преноса на више пријемника у мултикасту. ФЕЦ информације се обично додају у уређаје за масовно складиштење (магнетни, оптички и ССД/флеш) како би се омогућио опоравак оштећених података, широко се користи у модемима, користи се у системима у којима је примарна меморија ЕЦЦ меморија и у ситуацијама емитовања где пријемник нема могућност да захтева поновни пренос или где би то изазвало значајно кашњење. На пример, у случају да сателит кружи око Урана, поновни пренос због грешака у декодирању може створити кашњење од најмање 5 сати.

ФЕЦ обрада у пријемнику може се применити на дигитални ток бита или у демодулацији дигитално модулисаног носача. За ово друго, ФЕЦ је саставни део почетне аналогно-дигиталне конверзије у пријемнику. Витерби декодер примењује алгоритам меке одлуке за демодулацију дигиталних података из аналогног сигнала оштећеног буком. Многи ФЕЦ кодери такође могу да генеришу сигнал стопе грешке у битовима (енгл. bit-error rate - BER) који се може користити као повратна информација за фино подешавање аналогне пријемне електронике.

Максимални удео грешака или недостајућих битова који се могу исправити одређен је дизајном ЕЦЦ-а, тако да су различити кодови за исправљање грешака унапред погодни за различите услове. Генерално, јачи код индукује већу сувишност коју треба пренети користећи расположиву пропусну ширину, што смањује ефективну брзину протока, истовремено побољшавајући примљени ефективни однос сигнала и шума. Теорема кодирања бучног канала Клода Шенона одговара на питање колико је пропусног опсега преостало за комуникацију података, при чему се користи најефикаснији код који вероватноћу грешке у декодирању своди на нулу. Ово успоставља границе теоретске максималне брзине преноса информација канала са одређеним основним нивоом шума. Његов доказ није конструктиван, и стога не даје увид у то како да се изгради код за постизање капацитета. Међутим, након више година истраживања, неки напредни ФЕЦ системи попут поларног кода постижу капацитет Шеноновог канала под хипотезом о бесконачној дужини оквира.

Начин рада

ЕЦЦ се остварује додавањем излишности у трансмитоване информације користећи алгоритам. Излишни бит може бити сложена функција многих оригиналних информационих битова. Оригиналне информације могу се или не морају појавити дословно у кодираном излазу; кодови који укључују немодификовани улаз у излаз су систематски, док су они који то нису несистематски.

Поједностављени пример ЕЦЦ-а је пренос сваког бита података 3 пута, што је познато као (3,1) код понављања. Кроз бучни канал, пријемник може видети 8 верзија излаза, погледајте доњу табелу.

Триплет примљен	Протумачен као
000	0 (без грешке)
001	0
010	0
100	0
111	1 (без грешке)
110	1
101	1
011	1

Ово омогућава исправљање грешке у било ком од три узорка „већинским гласањем” или „демократским гласањем”. Способност исправљања овог ЕЦЦ је:

• До 1 бита триплета при грешки, или
• До 2 бита из триплета изостављена (случајеви нису приказани у табели).

Иако је једноставан за примену и широко се користи, ова трострука модуларна излишност је релативно неефикасан ЕЦЦ. Бољи ЕЦЦ кодови обично испитују последњих неколико десетина или чак последњих неколико стотина претходно примљених битова како би се утврдило како да се декодира тренутни мали сет битова (обично у групама од 2 до 8 битова).

Усредњавање буке за редукцију грешака

Могло би се рећи да ЕЦЦ ради тако што „усредњава шум“; пошто сваки бит података утиче на многе пренете симболе, оштећење неких симбола шумом обично омогућава да се оригинални кориснички подаци екстрахују из других, неоштећених примљених симбола који такође зависе од истих корисничких података.

• Због овог ефекта „удружења ризика“, дигитални комуникациони системи који користе ЕЦЦ имају тенденцију да раде знатно изнад одређеног минималног односа сигнал-шум, а не испод њега.
• Ова тенденција све или ништа – ефекат литице – постаје све израженија како се користе јачи кодови који се ближе приближавају теоријској Шеноновој граници.
• Преплитање ЕЦЦ кодираних података може редуковат својства „све или ништа” пренетих ЕЦЦ кодова када се грешке канала обично јављају у рафалима. Међутим, овај метод има ограничења; најбоље се користи на ускопојасним подацима.

Већина телекомуникационих система користи фиксни каналски код дизајниран да толерише очекивану стопу битне грешке у најгорем случају, а затим уопште не функционишу ако је стопа грешака у битовима још гора. Међутим, неки системи се прилагођавају датим условима грешке канала: неки случајеви хибридног аутоматског захтева за понављање користе фиксни ЕЦЦ метод све док ЕЦЦ може да обради стопу грешке, а затим се пребацује на АРQ када стопа грешке постане превисока; адаптивна модулација и кодирање користи различите ЕЦЦ брзине, додајући више битова за исправљање грешака по пакету када постоје веће стопе грешака у каналу, или их уклањају када нису потребне.

Типови

Главни чланци: Блок код и Конволуциони код

Блоцк код (посебно Хамингов код) где се редундантни битови додају као блок на крај почетне поруке

Континуални конволуциони код где се редундантни битови континуирано додају у структуру кодне речи

Две главне категорије ЕЦЦ кодова су блок кодови и конволуцијски кодови.

• Блок кодови раде на блоковима (пакетима) фиксне величине битова или симбола унапред-одређене величине. Практични блок кодови се генерално могу тешко декодирати у полиномском времену до њихове дужине блока.
• Конволуцијски кодови раде на токовима битова или симбола произвољне дужине. Они се најчешће меко декодирају Витербијевим алгоритмом, мада се понекад користе и други алгоритми. Витербијево декодирање омогућава асимптотски оптималну ефикасност декодирања са повећањем дужине ограничења конволуционог кода, али на рачун експоненцијално растуће сложености. Конволуцијски код који је прекинут је такође 'блок код' по томе што кодира блок улазних података, али је величина блока конволуционог кода генерално произвољна, док кодови блока имају фиксну величину коју диктирају њихове алгебарске карактеристике. Типови завршетка за конволуционе кодове укључују „одгризање репа” и „испирање бита”.

Постоји много типова блок кодова; Рид–Соломоново кодирање је вредно пажње због своје широке употребе на компакт дисковима, ДВД-овима и хард дисковима. Други примери класичних блок кодова укључују Голаy, БЦХ, вишедимензионални паритет и Хамингове кодове.

Хамингов ЕЦЦ се обично користи за исправљање грешака НАНД флеш меморије. Ово обезбеђује једнобитну корекцију грешке и детекцију 2-битне грешке. Хамингови кодови су погодни само за поузданије НАНД ћелије са једним нивоом (СЛЦ). НАНД гушћих ћелија на више нивоа (МЛЦ) може да користи више-битни исправљајући ЕЦЦ као што је БЦХ или Рид-Соломон. НОР Флаш обично не користи никакву исправку грешака.

Класични блок кодови се обично декодирају коришћењем алгоритама тврдог одлучивања, што значи да се за сваки улазни и излазни сигнал доноси тешка одлука да ли одговара јединичном или нултом биту. Насупрот томе, конволуцијски кодови се обично декодирају коришћењем алгоритама меке одлуке као што су Витерби, МАП или БЦЈР алгоритми, који обрађују (дискретизоване) аналогне сигнале и који омогућавају много више перформансе исправљања грешака од декодирања са тврдом одлуком.

Скоро сви класични блок кодови примењују алгебарска својства коначних поља. Стога се класични блок кодови често називају алгебарским кодовима.

За разлику од класичних блок кодова који често специфицирају способност откривања или исправљања грешака, многим модерним блок кодовима као што су ЛДПЦ кодови недостају такве гаранције. Уместо тога, савремени кодови се процењују у смислу њихове стопе битних грешака.

Већина кодова за исправљање грешака унапред исправља само преокрет битова, али не и уметања или брисања битова. У овој поставци, Хемингова удаљеност је одговарајући начин за мерење стопе битне грешке. Неколико кодова за исправљање грешака унапред је дизајнирано да исправљају уметање и брисање битова, као што су кодови маркера и кодови водених жигова. Левенштајнова удаљеност је прикладнији начин за мерење стопе битне грешке када се користе такви кодови.

Брзина кода и компромис између поузданости и брзине преноса података

Основни принцип ЕЦЦ-а је додавање редундантних битова како би се помогло декодеру да сазна праву поруку коју је кодирао предајник. Брзина кода датог ЕЦЦ система је дефинисана као однос између броја битова информација и укупног броја битова (тј. информација плус битова редунданције) у датом комуникационом пакету. Отуда је брзина кода реалан број. Ниска брзина кода близу нуле имплицира јак код који користи много редундантних битова за постизање добрих перформанси, док велика брзина кода близу 1 имплицира слаб код.

Редундантни битови који штите информације морају се пренети користећи исте комуникационе ресурсе које покушавају да заштите. Ово узрокује фундаментални компромис између поузданости и брзине преноса података. У једном екстрему, јак код (са ниском брзином кода) може да изазове значајно повећање СНР пријемника (однос сигнал-шум) смањујући стопу грешке у биту, по цену смањења ефективне брзине преноса података. Са друге стране, некоришћење било каквог ЕЦЦ-а (тј. брзина кода једнака 1) користи цео канал за потребе преноса информација, по цену остављања битова без икакве додатне заштите.

Једно интересантно питање је: колико ефикасан у смислу преноса информација може бити ЕЦЦ који има занемарљиву стопу грешака у декодирању? На ово питање је одговорио Клод Шенон својом другом теоремом, која каже да је капацитет канала максимална брзина битова коју може постићи било који ЕЦЦ чија стопа грешака тежи нули. Његов доказ се ослања на Гаусово насумично кодирање, које није погодно за апликације у стварном свету. Горња граница коју је дао Шенонов рад инспирисала је дуго путовање у дизајнирању ЕЦЦ-а који се могу приближити крајњој граници перформанси. Различити кодови данас могу достићи скоро Шенонову границу. Међутим, ЕЦЦ-и за постизање капацитета су обично изузетно сложени за имплементацију.

Најпопуларнији ЕЦЦ-ови имају компромис између перформанси и рачунарске сложености. Обично њихови параметри дају распон могућих брзина кода, који се може оптимизовати у зависности од сценарија. Обично се ова оптимизација ради како би се постигла ниска вероватноћа грешке у декодирању уз минимизирање утицаја на брзину преноса података. Други критеријум за оптимизацију брзине кода је балансирање ниске стопе грешке и броја ретрансмисија како би се постигла енергетска цена комуникације.

Literatura

• Clark, Jr., George C.; Cain, J. Bibb (1981). Error-Correction Coding for Digital Communications. New York, USA: Plenum Press. ISBN 0-306-40615-2. ISBN 978-0-306-40615-7. 
• Wицкер, Степхен Б. (1995). Еррор Цонтрол Сyстемс фор Дигитал Цоммуницатион анд Стораге. Енглеwоод Цлиффс, Њ, УСА: Прентице-Халл. ИСБН 0-13-200809-2. ISBN 978-0-13-200809-9. 
• Wилсон, Степхен Г. (1996). Дигитал Модулатион анд Цодинг. Енглеwоод Цлиффс, Њ, УСА: Прентице-Халл. ИСБН 0-13-210071-1. ISBN 978-0-13-210071-7. 
• "Error Correction Code in Single Level Cell NAND Flash memories" 16 February 2007
• "Error Correction Code in NAND Flash memories" 29 November 2004
• Observations on Errors, Corrections, & Trust of Dependent Systems, by James Hamilton, 26 February 2012
• Sphere Packings, Lattices and Groups, By J. H. Conway, N. J. A. Sloane, Springer Science & Business Media, 9 March 2013 – Mathematics – 682 pages.
• J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (2nd изд.). Springer-Verlag. стр. 31. ISBN 3-540-54894-7. 
• F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. стр. 35. ISBN 0-444-85193-3. 
• W. Huffman; V.Pless (2003). Fundamentals of error-correcting codes. Cambridge University Press. ISBN 978-0-521-78280-7. 
• Charan Langton (2001) Coding Concepts and Block Coding
• Francis, Michael. "Viterbi Decoder Block Decoding-Trellis Termination and Tail Biting." Xilinx XAPP551 v2. 0, DD (2005): 1-21.
• Chen, Qingchun, Wai Ho Mow, and Pingzhi Fan. "Some new results on recursive convolutional codes and their applications." Information Theory Workshop, 2006. ITW'06 Chengdu. IEEE. IEEE, 2006.
• Fiebig, U-C., and Patrick Robertson. "Soft-decision and erasure decoding in fast frequency-hopping systems with convolutional, turbo, and Reed-Solomon codes." IEEE Transactions on Communications 47.11 (1999): 1646-1654.
• Bhaskar, Vidhyacharan, and Laurie L. Joiner. "Performance of punctured convolutional codes in asynchronous CDMA communications under perfect phase-tracking conditions." Computers & Electrical Engineering 30.8 (2004): 573-592.
• Modestino, J., and Shou Mui. "Convolutional code performance in the Rician fading channel." IEEE Transactions on Communications 24.6 (1976): 592-606.
• Chen, Yuh-Long, and Che-Ho Wei. "Performance evaluation of convolutional codes with MPSK on Rician fading channels." IEE Proceedings F-Communications, Radar and Signal Processing. Vol. 134. No. 2. IET, 1987.
• G. D. Forney (1967). „Concatenated codes”. Cambridge, Massachusetts: MIT Press. 
• Shu Lin; Daniel J. Costello Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. стр. 278–280. ISBN 978-0-13-283796-5. 
• Forney, G. David (април 1966). „Generalized Minimum Distance Decoding”. IEEE Transactions on Information Theory. 12 (2): 125—131. doi:10.1109/TIT.1966.1053873. CS1 одржавање: Формат датума (веза)
• Yu, Christopher C.H.; Costello, Daniel J. (март 1980). „Generalized Minimum Distance Decoding for Qary Output Channels”. IEEE Transactions on Information Theory. 26 (2): 238—243. doi:10.1109/TIT.1980.1056148. CS1 одржавање: Формат датума (веза)
• Wu, Yingquan; Hadjicostis, Christoforos (јануар 2007). „Soft-Decision Decoding of Linear Block Codes Using Preprocessing and Diversification”. IEEE Transactions on Information Theory. 53 (1): 387—393. doi:10.1109/tit.2006.887478. CS1 одржавање: Формат датума (веза)
• J. P. Odenwalder (1970). „Optimal decoding of convolutional codes”. U.C.L.A., Systems Science Dept. (dissertation). 
• Robert J. McEliece; Laif Swanson (20. 8. 1993). „Reed–Solomon Codes and the Exploration of the Solar System”. JPL. CS1 одржавање: Формат датума (веза)
• Robert G. Gallager (1963). Low Density Parity Check Codes (PDF). Monograph, M.I.T. Press. Приступљено 7. 8. 2013. CS1 одржавање: Формат датума (веза)
• Tahir, B., Schwarz, S., & Rupp, M. (2017, May). BER comparison between Convolutional, Turbo, LDPC, and Polar codes. In 2017 24th International Conference on Telecommunications (ICT) (pp. 1-7). IEEE.
• Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. ISBN 0-471-64800-0.
• Андреwс, Кеннетх С., ет ал. "Тхе девелопмент оф турбо анд ЛДПЦ цодес фор дееп-спаце апплицатионс." Процеедингс оф тхе ИЕЕЕ 95.11 (2007): 2142-2156.
• Хассан, А.Е.С., Дессоукy, M., Абоу Елазм, А. анд Схокаир, M., 2012. Евалуатион оф цомплеxитy версус перформанце фор турбо цоде анд ЛДПЦ ундер дифферент цоде ратес. Проц. СПАЦОММ, пп.93-98.

Спољашње везе

• Морелос-Зарагоза, Роберт (2004). „Тхе Цоррецтинг Цодес (ЕЦЦ) Паге”. Приступљено 2006-03-05. 
• lpdec: library for LP decoding and related things (Python)
• Introducing Low-Density Parity-Check Codes (by Sarah J Johnson, 2010) Архивирано на сајту Wayback Machine (7. новембар 2019)
• LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005)
• LDPC Codes (TU Wien) Архивирано на сајту Wayback Machine (28. фебруар 2019)
• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses LDPC codes in Chapter 47.
• -аутхор= -