Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда Люби трансформациясы кодтары (LT кодтары) – өшіруді оңтайлы түзету кодтарына жақын тұратын практикалық фонтан кодтарының алғашқы класы. Олар 1998 жылы Майкл Любимен ойлап табылып, 2002 жылы жарияланды. Басқа фонтан кодтары сияқты, LT кодтары да кодтау және декодтау жылдамдығы үшін қабылдау артықшылығын екі жақты графтар арқылы алмастырады. LT кодтарының ерекшелігі – хабарламаны кодтау және декодтау үшін эксклюзивті немесе операциясына негізделген өте қарапайым алгоритмді қолдану болып табылады. LT кодтары – жылдамдықсыз, себебі кодтау алгоритмі теориялық тұрғыдан шексіз көп хабарлама пакеттерін (яғни, хабарламаны декодтау үшін қабылдануы тиіс пакеттердің үлесі кез келгендей кішкентай болуы мүмкін) өндіре алады. Олар өшіруді түзету кодтары, өйткені оларды өшіру арнасы арқылы цифрлық деректерді сенімді түрде беру үшін пайдалануға болады. LT кодтарынан кейінгі буын – Raptor кодтары (мысалы, IETF RFC 5053 немесе IETF RFC 6330 қараңыз), олардың кодтау және декодтау уақыты сызықтық. Raptor кодтары негізінен LT кодтарына негізделген, яғни Raptor кодтарын кодтау екі кезеңді қамтиды, олардың екінші кезеңі LT кодтау болып табылады. Сол сияқты, Raptor кодтарымен декодтау негізінен LT декодтауға сүйенеді, бірақ LT декодтау одан да жетілдірілген декодтау техникаларымен үйлеседі. IETF RFC 6330-да сипатталған RaptorQ коды – ең жетілдірілген фонтан коды, ол LT кодын ғана пайдаланумен салыстырғанда әлдеқайда жоғары декодтау ықтималдығына және өнімділікке ие.
In computer science, Luby transform codes (LT codes) are the first class of practical fountain codes that are near optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002. Like some other fountain codes, LT codes depend on sparse bipartite graphs to trade reception overhead for encoding and decoding speed. The distinguishing characteristic of LT codes is in employing a particularly simple algorithm based on the exclusive or operation to encode and decode the message. LT codes are rateless because the encoding algorithm can in principle produce an infinite number of message packets (i. e., the percentage of packets that must be received to decode the message can be arbitrarily small). They are erasure correcting codes because they can be used to transmit digital data reliably on an erasure channel. The next generation beyond LT codes are Raptor codes (see for example IETF RFC 5053 or IETF RFC 6330), which have linear time encoding and decoding. Raptor codes are fundamentally based on LT codes, i. e., encoding for Raptor codes uses two encoding stages, where the second stage is LT encoding. Similarly, decoding with Raptor codes primarily relies upon LT decoding, but LT decoding is intermixed with more advanced decoding techniques. The RaptorQ code specified in IETF RFC 6330, which is the most advanced fountain code, has vastly superior decoding probabilities and performance compared to using only an LT code.
Неге LT кодын қолдану керек?
Деректерді өшіру арнасы арқылы берудің дәстүрлі схемасы үздіксіз екі жақты байланысқа тәуелді. Жіберуші ақпаратты кодтап, пакет жібереді. Қабылдаушы алынған пакетті декодтауға тырысады. Егер декодтау мүмкін болса, қабылдаушы жіберушіге қуаттау хабарламасын жібереді. Әйтпесе, қабылдаушы жіберушіден пакетті қайта жіберуді сұрайды. Бұл екі жақты процесс хабарламадағы барлық пакеттер сәтті берілгенше жалғасады. Кейбір желілер, мысалы, ұялы сымсыз хабар тарату желілері кері байланыс арнасына ие болмайды. Бұл желілердегі қолданбалардың сенімді болуы қажет. Фонтандық кодтар, жалпы алғанда, және LT кодтары, атап айтқанда, бір бағытты байланыс протоколын қабылдау арқылы бұл мәселені шешеді. Жіберуші ақпаратты пакеттеп, бірінен соң бірін жібереді. Қабылдаушы әрбір пакетті алған кезде бағалайды. Егер қателік болса, қате пакет жойылады. Әйтпесе, пакет хабарламаның бір бөлігі ретінде сақталады. Соңында қабылдаушыда бүкіл хабарламаны қайта құруға жеткілікті жарамды пакеттер жиналады. Барлық хабарлама сәтті қабылданғанда, қабылдаушы берудің аяқталғанын хабарлайды. Жоғарыда айтылғандай, IETF RFC 6330 стандартында сипатталған RaptorQ коды LT кодынан жақсы нәтижелер көрсетеді.
The traditional scheme for transferring data across an erasure channel depends on continuous two way communication. The sender encodes and sends a packet of information. The receiver attempts to decode the received packet. If it can be decoded, the receiver sends an acknowledgment back to the transmitter. Otherwise, the receiver asks the transmitter to send the packet again. This two way process continues until all the packets in the message have been transferred successfully. Certain networks, such as ones used for cellular wireless broadcasting, do not have a feedback channel. Applications on these networks still require reliability. Fountain codes in general, and LT codes in particular, get around this problem by adopting an essentially one way communication protocol. The sender encodes and sends packet after packet of information. The receiver evaluates each packet as it is received. If there is an error, the erroneous packet is discarded. Otherwise the packet is saved as a piece of the message. Eventually the receiver has enough valid packets to reconstruct the entire message. When the entire message has been received successfully the receiver signals that transmission is complete. As mentioned above, the RaptorQ code specified in IETF RFC 6330 outperforms an LT code in practice.
LT кодтау
Декодтау процесі кодталған хабарламаны алу үшін "ексклюзивті немесе" операциясын қолданады. Егер ағымдағы пакет таза болмаса немесе ол бұрын өңделген пакетті қайталаса, ағымдағы пакет жойылады. Егер қазіргі таза алынған пакет d > 1 дәрежелі болса, ол алдымен хабар кезегі аймағындағы толық декодталған барлық блоктармен (келесі қадамда толық сипатталғандай) өңделеді, содан кейін буферлік аймақта сақталады, егер оның төмендетілген дәрежесі 1-ден жоғары болса. d = 1 дәрежелі жаңа, таза пакет (блок Mi) алынғанда (немесе алдыңғы қадамда ағымдағы пакеттің дәрежесі 1-ге дейін төмендетілсе), ол хабарлама кезегіне орналастырылады, содан кейін буферде орналасқан d > 1 дәрежелі барлық пакеттермен салыстырылады. Ол Mi арқылы кодталған кез келген буферленген пакеттің дерек бөлігіне эксклюзивті түрде қосылады, сәйкес пакеттердің дәрежесі азайтылады және осы пакеттердің индекс тізімі Mi қолданылғанын көрсету үшін түзетіледі. Бұл процесс буфердегі d = 2 дәрежелі блокты ашқанда, бұл блок 1 дәрежеге дейін азайтылады және өз кезегінде хабарлама кезегіне көшіріледі, содан кейін буферде қалған пакеттерге қатысты өңделеді. Хабардың барлық n блогы хабарлама кезегіне орналастырылған аймаққа жылжытылған кезде, қабылдаушы хабардың сәтті декодталғандығын хабарлайтын сигнал береді. Бұл декодтау процедурасы A ⊕ A = 0 кез келген A биттік тізбегі үшін жұмыс істейді. d - 1 бөлек блоктар d дәрежелі пакетке эксклюзивті түрде қосылғаннан кейін, сәйкес келмеген блоктың бастапқы кодталмаған мазмұны ғана қалады. Символдармен мынадай:
The decoding process uses the "exclusive or" operation to retrieve the encoded message. If the current packet isn't clean, or if it replicates a packet that has already been processed, the current packet is discarded. If the current cleanly received packet is of degree d > 1, it is first processed against all the fully decoded blocks in the message queuing area (as described more fully in the next step), then stored in a buffer area if its reduced degree is greater than 1. When a new, clean packet of degree d = 1 (block Mi) is received (or the degree of the current packet is reduced to 1 by the preceding step), it is moved to the message queueing area, and then matched against all the packets of degree d > 1 residing in the buffer. It is exclusive ored into the data portion of any buffered packet that was encoded using Mi, the degree of that matching packet is decremented, and the list of indices for that packet is adjusted to reflect the application of Mi. When this process unlocks a block of degree d = 2 in the buffer, that block is reduced to degree 1 and is in its turn moved to the message queueing area, and then processed against the packets remaining in the buffer. When all n blocks of the message have been moved to the message queueing area, the receiver signals the transmitter that the message has been successfully decoded. This decoding procedure works because A A = 0 for any bit string A. After d − 1 distinct blocks have been exclusive ored into a packet of degree d, the original unencoded content of the unmatched block is all that remains. In symbols we have
Вариациялар
Жоғарыда сипатталған кодтау және декодтау процестерінің бірнеше нұсқасын жасау мүмкін. Мысалы, әрбір пакеттің басына нақты хабарлама блогының индекстерінің тізімі {i1, i2, …, id} қоюдың орнына, кодтаушы индекстер тізімін құру үшін пайдаланылатын псевдокездейі сан генераторының (PRNG) немесе индекс кестесінің бастамасы ретінде қызмет ететін қысқа "кілт" жіберуі мүмкін. Осы RNG немесе индекс кестесімен жабдықталған қабылдағыш осы бастамадан индекстердің "кездейсоқ" тізімін сенімді түрде қайта жасай алатындықтан, декодтау процесін сәтті аяқтауға болады. Басқаша айтқанда, орташа дәрежесі төмен қарапайым LT кодын сенімді қателерді түзету кодын қосу арқылы, тәжірибеде жақсартылған LT кодынан артық болатын raptor кодын құрастыруға болады.
Several variations of the encoding and decoding processes described above are possible. For instance, instead of prefixing each packet with a list of the actual message block indices {i1, i2, , id}, the encoder might simply send a short "key" which served as the seed for the pseudorandom number generator (PRNG) or index table used to construct the list of indices. Since the receiver equipped with the same RNG or index table can reliably recreate the "random" list of indices from this seed, the decoding process can be completed successfully. Alternatively, by combining a simple LT code of low average degree with a robust error correcting code, a raptor code can be constructed that will outperform an optimized LT code in practice.