Қайталау коді: негізгі қателерді түзететін кодтардың қарапайым түрі
Repetition code
Қателерді түзету коды: қайталама код – қарапайым сызықтық код. Хабарды шулы канал арқылы бергенде қателерді азайту үшін бірнеше рет қайталайды. Бірақ тиімділігі төмен.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Кодтау теориясында қайталау коды – ең қарапайым сызықтық қателерді түзету кодтарының бірі. Шулы арна арқылы хабарды жіберу кезінде, арна хабарды бірнеше жерде бұзуы мүмкін болғандықтан, қайталау кодының идеясы – хабарды бірнеше рет қайталау болып табылады. Арна осы қайталаулардың аз ғана бөлігін бұзады деп үміттенеді. Осылайша қабылдаушы, алынған дерек ағыны бір хабарламаның қайталануы емес екенін байқап, жіберу қатесі болғанын анықтайды. Сонымен қатар, қабылдаушы дерек ағынында ең көп кездесетін хабарламаға қарап бастапқы хабарламаны қалпына келтіре алады. Қателерді түзетудің нашар тиімділігі және төмен кодтық жылдамдық (пайдалы ақпарат символдары мен жіберілген нақты символдар арақатынасы) салдарынан, көп жағдайда басқа қателерді түзету кодтары қолданылады. Қайталау кодының басты артықшылығы – оны жүзеге асырудың қарапайымдығы.
In coding theory, the repetition code is one of the most basic linear error correcting codes. In order to transmit a message over a noisy channel that may corrupt the transmission in a few places, the idea of the repetition code is to just repeat the message several times. The hope is that the channel corrupts only a minority of these repetitions. This way the receiver will notice that a transmission error occurred since the received data stream is not the repetition of a single message, and moreover, the receiver can recover the original message by looking at the received message in the data stream that occurs most often. Because of the bad error correcting performance coupled with the low code rate (ratio between useful information symbols and actual transmitted symbols), other error correction codes are preferred in most cases. The chief attraction of the repetition code is the ease of implementation.
Код параметрлері
Бинарлық қайталау коды жағдайында, барлық бірліктерден және барлық нөлдерден тұратын екі кодты сөз бар, олардың ұзындығы болады. Сондықтан, кодтың ең аз Хамминг қашықтығы оның ұзындығына тең. Бұл қайталау кодына қателерді түзетуге қабілеттілік береді (яғни, ол кез келген кодты сөздердегі дейін қателерді түзете алады). Егер бинарлық қайталау кодының ұзындығы тақ болса, онда ол кемел код болып табылады. Ұзындығы n-ге тең бинарлық қайталау коды (n, 1) Хамминг кодымен эквивалентті. (n, 1) BCH коды да қайталау коды болып табылады.
In the case of a binary repetition code, there exist two code words all ones and all zeros which have a length of Therefore, the minimum Hamming distance of the code equals its length This gives the repetition code an error correcting capacity of (i. e. it will correct up to errors in any code word). If the length of a binary repetition code is odd, then it's a perfect code. The binary repetition code of length n is equivalent to the (n, 1) Hamming code. A (n, 1) BCH code is also a repetition code.
Мысал
3 ұзындығы бар екілік қайталау кодын қарастырайық. Пайдаланушы 101 ақпарат битін жібергісі келеді. Содан кейін кодтау әр битті барлық бірліктерден немесе барлық нөлдерден тұратын кодты сөзбен алмастырады, нәтижесінде 111 000 111 шығады, ол жіберіледі. Егер үш қате жіберілген биттерді бұзса, ал алынған тізбек 111 010 100 болса, не болады? Декодтау әдетте әрбір кодты сөз үшін қарапайым көпшілік дауыс беру арқылы жасалады. Бұл бізді декодталған 100 ақпарат битіне жеткізеді, себебі бірінші және екінші кодты сөздерде екі қатеден аз болды, сондықтан биттердің көпшілігі дұрыс. Алайда үшінші кодты сөздің екі биті бұзылды, бұл қате ақпарат битіне әкеледі, өйткені екі қате қателерді түзету мүмкіндігінен асып түседі.
Consider a binary repetition code of length 3. The user wants to transmit the information bits 101. Then the encoding maps each bit either to the all ones or all zeros code word, so we get the 111 000 111, which will be transmitted. Let's say three errors corrupt the transmitted bits and the received sequence is 111 010 100. Decoding is usually done by a simple majority decision for each code word. That lead us to 100 as the decoded information bits, because in the first and second code word occurred less than two errors, so the majority of the bits are correct. But in the third code word two bits are corrupted, which results in an erroneous information bit, since two errors lie above the error correcting capacity.
Қолданбалар
Олардың дербес кодтар ретінде нашар жұмыс істеуіне қарамастан, Turbo кодтары сияқты, итеративті түрде декодталатын біріктірілген кодтау схемаларында, мысалы, қайталау-жинақтау (RA) және жинақтау-қайталау-жинақтау (ARA) кодтарында қолдану, үлкенге жақын қателерді түзету өнімділігін қамтамасыз етеді. Қайталау кодтары – кодтық жылдамдығы арна шуын жеңу үшін қажетті паритеттік ақпарат мөлшеріне байланысты арна сыйымдылығының өзгеруіне автоматты түрде бейімделе алатын, белгілі бірнеше кодтың бірі және бұл қасиетінен өшіруге келмейтін арналар үшін жалғыз белгілі код болып табылады. Өшіру арналары үшін практикалық бейімделген кодтар соңғы кезде ғана ойлап табылды және олар "бұлақ кодтары" деп аталады. Кейбір UART құрылғылары, мысалы FlexRay протоколында қолданылатындары, қысқа мерзімді шу импульстарын жою үшін көпшілік сүзгісін пайдаланады. Бұл импульстарды қабылдамау сүзгісін қайталау декодерінің бір түрі деп қарастыруға болады.
Despite their poor performance as stand alone codes, use in Turbo code like iteratively decoded concatenated coding schemes, such as repeat accumulate (RA) and accumulate repeat accumulate (ARA) codes, allows for surprisingly good error correction performance. Repetition codes are one of the few known codes whose code rate can be automatically adjusted to varying channel capacity, by sending more or less parity information as required to overcome the channel noise, and it is the only such code known for non erasure channels. Practical adaptive codes for erasure channels have been invented only recently, and are known as fountain codes. Some UARTs, such as the ones used in the FlexRay protocol, use a majority filter to ignore brief noise spikes. This spike rejection filter can be seen as a kind of repetition decoder.