Онлайн кодтар: жоғалған деректерді қалпына келтіру алгоритмі
Online codes
Онлайн кодтар – бұл қателерді жоюға арналған кодтар. Хабарды алу үшін символдардың бір бөлігі жеткілікті. Бұл деректерді қалпына келтіруге көмектеседі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда онлайн кодтар – қателерді жою кодтарының бір түрі. Бұл кодтар хабарды бірнеше символға кодтай алады, сонда олардың кез келген үлесін білу бастапқы хабарды қалпына келтіруге мүмкіндік береді (жоғары дәлдікпен). Қателерді жою кодтары қабылдаушылар жеткілікті символдар алғанға дейін таратылатын, шексіз көп символдарды жасайды. Онлайн кодтау алгоритмі бірнеше кезеңнен тұрады. Біріншіден, хабар n белгілі бір мөлшердегі хабар блоктарына бөлінеді. Содан кейін сыртқы кодтау – бұл қателерді жою коды, ол хабар блоктарына қосылатын қосымша блоктарды жасайды, олар біріктірілген хабарды құрайды. Осыдан ішкі кодтау тексеру блоктарын жасайды. Белгілі бір көлемдегі тексеру блоктарын алғаннан кейін біріктірілген хабардың бір бөлігін қалпына келтіруге болады. Жеткілікті көлемде қалпына келтірілгеннен кейін сыртқы кодтау бастапқы хабарды қалпына келтіру үшін қолданылады.
In computer science, online codes are an example of rateless erasure codes. These codes can encode a message into a number of symbols such that knowledge of any fraction of them allows one to recover the original message (with high probability). Rateless codes produce an arbitrarily large number of symbols which can be broadcast until the receivers have enough symbols. The online encoding algorithm consists of several phases. First the message is split into n fixed size message blocks. Then the outer encoding is an erasure code which produces auxiliary blocks that are appended to the message blocks to form a composite message. From this the inner encoding generates check blocks. Upon receiving a certain number of check blocks some fraction of the composite message can be recovered. Once enough has been recovered the outer decoding can be used to recover the original message.
Толық талқылау
Онлайн кодтар блок өлшемімен және екі скалярмен, q және ε параметрленеді. Авторлар q=3 және ε=0,01 деп ұсынады. Бұл параметрлер кодтаудың күрделілігі мен тиімділігі арасындағы қатынасты анықтайды. n блоктан тұратын хабарлама жоғары ықтималдылықпен (1+3ε)n тексеру блогынан қалпына келтіріледі. Сәтсіздік ықтималдығы (ε/2)q+1-ге тең.
Online codes are parameterised by the block size and two scalars, q and ε. The authors suggest q=3 and ε=0.01. These parameters set the balance between the complexity and performance of the encoding. A message of n blocks can be recovered, with high probability, from (1+3ε)n check blocks. The probability of failure is (ε/2)q+1.
Декодтау
Әлбетте, ішкі сатыдағы декодер қазіргі уақытта декодтау мүмкін емес бақылау блоктарын сақтауы керек. Бақылау блогын тек оған қосылған блоктардың біреуі ғана белгілі болғанда ғана декодтауға болады. Сол жақтағы графикте ішкі декодердің жұмыс істеу барысы көрсетілген. X осі бойынша алынған бақылау блоктарының саны, ал пунктирлі сызық бойынша қазіргі уақытта қолданылмайтын бақылау блоктарының саны көрсетілген. Бастапқыда бұл сызықтық түрде өседі, себебі 1-ден жоғары дәрежелі көптеген бақылау блоктары қабылданады, бірақ қолданылмайды. Бір кезде кейбір бақылау блоктарын бірден қолдануға болады, содан кейін олардың шешілуіне, ал одан кейін тағы да бақылау блоктарының қолданылуына мүмкіндік туады. Бүкіл файлдың декодталуы өте жылдам жүзеге асырылады. График көрсеткендей, ішкі декодер n бақылау блогын алғаннан кейін қысқа мерзімге толық декодтауға жетпейді. Сыртқы кодтау ішкі декодерден кейбір қиын декодталатын блоктардың мәселе тудырмайтынын қамтамасыз етеді, өйткені файлды оларсыз да қалпына келтіруге болады.
Obviously the decoder of the inner stage must hold check blocks which it cannot currently decode. A check block can only be decoded when all but one of the blocks which it is attached to are known. The graph to the left shows the progress of an inner decoder. The x axis plots the number of check blocks received and the dashed line shows the number of check blocks which cannot currently be used. This climbs almost linearly at first as many check blocks with degree > 1 are received but unusable. At a certain point, some of the check blocks are suddenly usable, resolving more blocks which then causes more check blocks to be usable. Very quickly the whole file can be decoded. As the graph also shows the inner decoder falls just shy of decoding everything for a little while after having received n check blocks. The outer encoding ensures that a few elusive blocks from the inner decoder are not an issue, as the file can be recovered without them.