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

У рачунарству, телекомуникацијама, теорији информација и теорији кодирања, код за исправљање грешака, или код кориговања грешака (енгл. 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 битова).

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.
• -аутхор= -