{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sq\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Kodet e tepric\u00ebs: me fjal\u00eb t\u00eb thjeshta p\u00ebr m\u00ebnyr\u00ebn se si t\u00eb ruani t\u00eb dh\u00ebnat n\u00eb m\u00ebnyr\u00eb t\u00eb besueshme dhe t\u00eb lir\u00eb.","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Kodet<\/p>\n

<\/p>\n

Kjo \u00ebsht\u00eb m\u00ebnyra e tep\u00ebrt<\/em><\/p>\n

<\/p>\n

Kodat e tep\u00ebrt* p\u00ebrdoren gjer\u00ebsisht n\u00eb sistemet kompjuterike p\u00ebr t\u00eb rritur besueshm\u00ebrin\u00eb e ruajtjes s\u00eb t\u00eb dh\u00ebnave. N\u00eb Yandex, ato p\u00ebrdoren n\u00eb shum\u00eb projekte. P\u00ebr shembull, p\u00ebrdorimi i kodave t\u00eb tep\u00ebrt n\u00eb vend t\u00eb riprodhimit n\u00eb magazin\u00ebn ton\u00eb t\u00eb brendshme t\u00eb objekteve kursen miliona pa ulur besueshm\u00ebrin\u00eb. Por, megjith\u00eb p\u00ebrhapjen e gjer\u00eb, nj\u00eb p\u00ebrshkrim i qart\u00eb i m\u00ebnyr\u00ebs se si funksionojn\u00eb kodet e tep\u00ebrt, \u00ebsht\u00eb shum\u00eb i rrall\u00eb. Ata q\u00eb duan t\u00eb kuptojn\u00eb p\u00ebrballen af\u00ebrsisht me k\u00ebt\u00eb (nga Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

Emri im \u00ebsht\u00eb Vadim, n\u00eb Yandex merrem me zhvillimin e magazin\u00ebs s\u00eb brendshme t\u00eb objekteve MDS. N\u00eb k\u00ebt\u00eb artikull, do t\u00eb p\u00ebrshkruaj n\u00eb m\u00ebnyr\u00eb t\u00eb thjesht\u00eb bazat teorike t\u00eb kodeve t\u00eb tep\u00ebrt (kodeve Reed-Solomon dhe LRC). Do t\u00eb tregoj se si funksionon, pa matematik\u00eb t\u00eb komplikuar dhe terma t\u00eb rrall\u00eb. N\u00eb fund do t\u00eb jap shembuj t\u00eb p\u00ebrdorimit t\u00eb kodeve t\u00eb tep\u00ebrt n\u00eb Yandex.<\/p>\n

<\/p>\n

Disa detaje matematikore nuk do t'i shqyrtoj n\u00eb detaje, por do t'u jap lidhje p\u00ebr ata q\u00eb d\u00ebshirojn\u00eb t\u00eb thellohen m\u00eb shum\u00eb. Po ashtu, dua t\u00eb theksoj se disa p\u00ebrkufizime matematikore mund t\u00eb mos jen\u00eb strikte, pasi artikulli nuk \u00ebsht\u00eb p\u00ebr matematikant\u00ebt, por p\u00ebr inxhinier\u00ebt q\u00eb duan t\u00eb kuptojn\u00eb thelbin e \u00e7\u00ebshtjes.<\/p>\n

<\/p>\n

* N\u00eb literatur\u00ebn anglishtfol\u00ebse, kodet e mbivler\u00ebsis\u00eb shpesh quhen kodet e fshirjes.<\/p>\n

<\/a><\/noindex><\/p>\n

1. Thelbi i kodeve t\u00eb mbivler\u00ebsis\u00eb<\/h1>\n

<\/p>\n

Thelbi i t\u00eb gjith\u00eb kodeve t\u00eb mbivler\u00ebsis\u00eb \u00ebsht\u00eb shum\u00eb i thjesht\u00eb: t\u00eb ruhet (ose t\u00eb transmetohet) t\u00eb dh\u00ebna n\u00eb m\u00ebnyr\u00eb q\u00eb ato t\u00eb mos humbasin kur ndodhin gabime (prishje disku, gabime n\u00eb transmetimin e t\u00eb dh\u00ebnave, etj.). <\/p>\n

<\/p>\n

N\u00eb shumic\u00ebn* e kodeve t\u00eb mbivler\u00ebsis\u00eb, t\u00eb dh\u00ebnat ndahen n\u00eb n blloqe t\u00eb dh\u00ebnash, p\u00ebr to llogariten m blloqe kode mbivler\u00ebsie, k\u00ebshtu q\u00eb gjithsej kemi n + m blloqe. Kodet e mbivler\u00ebsis\u00eb nd\u00ebrtohen n\u00eb m\u00ebnyr\u00eb q\u00eb t\u00eb jet\u00eb e mundur t\u00eb rikuperohen n blloqe t\u00eb dh\u00ebnash, duke p\u00ebrdorur vet\u00ebm nj\u00eb pjes\u00eb t\u00eb n + m blloqeve. M\u00eb posht\u00eb do t\u00eb shqyrtojm\u00eb vet\u00ebm kodet bllok t\u00eb mbivler\u00ebsis\u00eb, dmth ato ku t\u00eb dh\u00ebnat ndahen n\u00eb blloqe.<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

P\u00ebr t\u00eb rikuperuar t\u00eb gjitha n blloqet e t\u00eb dh\u00ebnave, nevojitet t\u00eb pakt\u00ebn n nga n + m blloqet, pasi nuk \u00ebsht\u00eb e mundur t\u00eb merrni n blloqe duke pasur vet\u00ebm n-1 bllok (n\u00eb k\u00ebt\u00eb rast do t\u00eb duhej t\u00eb merrni 1 bllok \u00abnga ajri\u00bb). A jan\u00eb t\u00eb mjaftueshme n blloqet arbitrare nga n + m p\u00ebr rikuperimin e t\u00eb gjith\u00eb t\u00eb dh\u00ebnave? Kjo varet nga lloji i kod\u00ebve t\u00eb tep\u00ebrt, p\u00ebr shembull, kodet Reed-Solomon lejojn\u00eb rikuperimin e t\u00eb gjitha t\u00eb dh\u00ebnave me ndihm\u00ebn e n blloqeve arbitrare, nd\u00ebrsa kodet e tep\u00ebrt LRC \u2014 jo gjithmon\u00eb.<\/p>\n

<\/p>\n

Ruajtja e t\u00eb dh\u00ebnave<\/h3>\n

<\/p>\n

N\u00eb sistemet e ruajtjes s\u00eb t\u00eb dh\u00ebnave, zakonisht, \u00e7do bllok t\u00eb dh\u00ebnash dhe bllok kodesh t\u00eb tep\u00ebrt shkruhet n\u00eb nj\u00eb disk t\u00eb ve\u00e7ant\u00eb. At\u00ebher\u00eb, n\u00eb rast t\u00eb nj\u00eb d\u00ebmtimi t\u00eb nj\u00eb disku, t\u00eb dh\u00ebnat origjinale mund t\u00eb rikuperohen dhe t\u00eb lexohen. T\u00eb dh\u00ebnat mund t\u00eb rikuperohen edhe n\u00ebse disa disqe d\u00ebmtohen n\u00eb t\u00eb nj\u00ebjt\u00ebn koh\u00eb.<\/p>\n

<\/p>\n

Transferta e t\u00eb dh\u00ebnave<\/h3>\n

<\/p>\n

Kode e mbipesh\u00ebs mund t\u00eb p\u00ebrdoren p\u00ebr transmetimin e besuesh\u00ebm t\u00eb t\u00eb dh\u00ebnave n\u00eb nj\u00eb rrjet t\u00eb pasigurt. T\u00eb dh\u00ebnat e transmetuara ndahen n\u00eb blloqe, p\u00ebr t\u00eb cilat llogariten kodet e mbipesh\u00ebs. Blloqet e t\u00eb dh\u00ebnave dhe blloqet e kodit t\u00eb mbipesh\u00ebs d\u00ebrgohen p\u00ebrmes rrjetit. N\u00eb rast se ndodhin gabime n\u00eb blloqe t\u00eb rastit (madje deri n\u00eb nj\u00eb num\u00ebr t\u00eb caktuar blloqesh), t\u00eb dh\u00ebnat prap\u00eb mund t\u00eb d\u00ebrgohen pa gabime p\u00ebrmes rrjetit. Kodet e Reed-Solomon, p\u00ebr shembull, p\u00ebrdoren p\u00ebr transmetimin e t\u00eb dh\u00ebnave p\u00ebrmes linjave optike t\u00eb komunikimit dhe n\u00eb komunikimin satelitor.<\/p>\n

<\/p>\n

* Ekzistojn\u00eb gjithashtu kode mbipeshash, ku t\u00eb dh\u00ebnat nuk ndahen n\u00eb blloqe, si\u00e7 jan\u00eb kodet Hamming dhe kodet CRC, t\u00eb cilat aplikohen gjer\u00ebsisht p\u00ebr transmetimin e t\u00eb dh\u00ebnave n\u00eb rrjetet Ethernet. K\u00ebto jan\u00eb kode p\u00ebr kodimin rezistent ndaj nd\u00ebrhyrjeve, jan\u00eb destinuar p\u00ebr zbuloj gabimesh dhe jo p\u00ebr t'i korrigjuar ato (kodi Hamming gjithashtu lejon korrigjimin e pjessh\u00ebm t\u00eb gabimeve).<\/p>\n

<\/p>\n

2. Kodet Reed-Solomon<\/h1>\n

<\/p>\n

Kodet Reed-Solomon jan\u00eb disa nga kodet e mbipesh\u00ebs m\u00eb t\u00eb shpeshta, t\u00eb shpikura q\u00eb n\u00eb vitet 1960 dhe q\u00eb p\u00ebr her\u00eb t\u00eb par\u00eb gjet\u00ebn p\u00ebrdorim t\u00eb gjer\u00eb n\u00eb vitet 1980 p\u00ebr prodhiminN\u00eb mas\u00eb t\u00eb disk\u00ebve kompakt.<\/p>\n

<\/p>\n

Dy pyetje ky\u00e7e p\u00ebr t\u00eb kuptuar kodet e Reid-Solomon jan\u00eb dy: 1) si t\u00eb krijoni blloqe kodesh tep\u00ebr; 2) si t\u00eb rikuperoni t\u00eb dh\u00ebna duke p\u00ebrdorur blloqet e kodesh tep\u00ebr. Do t\u00eb gjejm\u00eb p\u00ebrgjigjet p\u00ebr to.
\nP\u00ebr thjesht\u00ebsim, m\u00eb tej do t\u00eb supozojm\u00eb se n=6 dhe m=4. Schemat e tjera shqyrtohen n\u00eb p\u00ebrputhje.<\/p>\n

<\/p>\n

Si t\u00eb krijoni blloqe kodesh tep\u00ebr<\/h3>\n

<\/p>\n

\u00c7do bllok kodesh tep\u00ebr konsiderohet pavar\u00ebsisht nga t\u00eb tjer\u00ebt. P\u00ebr llogaritjen e \u00e7do blloku p\u00ebrdoren t\u00eb gjith\u00eb n blloket e t\u00eb dh\u00ebnave. N\u00eb diagramin m\u00eb posht\u00eb, X1-X6 jan\u00eb blloket e t\u00eb dh\u00ebnave, P1\u2013P4 jan\u00eb blloket e kodesh tep\u00ebr.<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

T\u00eb gjith\u00eb blloket e t\u00eb dh\u00ebnave duhet t\u00eb ken\u00eb t\u00eb nj\u00ebjtin madh\u00ebsi, p\u00ebr rregullimin mund t\u00eb p\u00ebrdoren bitet zero. Blloket e kodesh tep\u00ebr t\u00eb obtenuara do t\u00eb ken\u00eb t\u00eb nj\u00ebjtin madh\u00ebsi si blloket e t\u00eb dh\u00ebnave. T\u00eb gjith\u00eb blloket e t\u00eb dh\u00ebnave ndahen n\u00eb fjal\u00eb (p.sh., nga 16 bit). Le t\u00eb supozojm\u00eb se kemi ndar\u00eb blloket e t\u00eb dh\u00ebnave n\u00eb k fjal\u00eb. At\u00ebher\u00eb t\u00eb gjith\u00eb blloket e kodesh tep\u00ebr gjithashtu do t\u00eb shp\u00ebrndahen n\u00eb k fjal\u00eb.<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

P\u00ebr llogaritjen e fjal\u00ebs i t\u00eb \u00e7do blloku tep\u00ebr do t\u00eb p\u00ebrdoren fjal\u00ebt e i-ta t\u00eb t\u00eb gjith\u00eb blloket e t\u00eb dh\u00ebnave. Ato do t\u00eb llogariten sipas formul\u00ebs m\u00eb posht\u00eb:<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

K\u00ebtu, vlerat x jan\u00eb fjal\u00ebt e bllokut t\u00eb t\u00eb dh\u00ebnave, p jan\u00eb fjal\u00ebt e bllokut t\u00eb kodit t\u00eb tep\u00ebrt, t\u00eb gjith\u00eb alfa, beta, gamma dhe delta jan\u00eb numra t\u00eb zgjedhur ve\u00e7an\u00ebrisht, t\u00eb nj\u00ebjt\u00eb p\u00ebr t\u00eb gjith\u00eb i. Duhet th\u00ebn\u00eb menj\u00ebher\u00eb se t\u00eb gjitha k\u00ebto vlera nuk jan\u00eb numra t\u00eb zakonsh\u00ebm, por element\u00eb t\u00eb fush\u00ebs s\u00eb Galois, operacionet +, -, *, \/ jan\u00eb operacione speciale, t\u00eb futur mbi element\u00ebt e fush\u00ebs s\u00eb Galois.<\/p>\n

<\/p>\n

P\u00ebrse nevojiten fushat e Galois<\/h3>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

Duket se \u00ebsht\u00eb e thjesht\u00eb: ndajm\u00eb t\u00eb dh\u00ebnat n\u00eb blloqe, blloqet n\u00eb fjal\u00eb, me ndihm\u00ebn e fjal\u00ebve t\u00eb bllokut t\u00eb t\u00eb dh\u00ebnave llogarisim fjal\u00ebt e bllokut t\u00eb kodit t\u00eb tep\u00ebrt \u2014 marrim blloqe kodesh t\u00eb tep\u00ebrta. N\u00eb p\u00ebrgjith\u00ebsi, k\u00ebshtu funksionon, por djalli \u00ebsht\u00eb n\u00eb detaje:<\/p>\n

<\/p>\n

    \n
  1. Si\u00e7 u tha m\u00eb sip\u00ebr, madh\u00ebsia e fjal\u00ebs \u00ebsht\u00eb fikse, n\u00eb shembullin ton\u00eb, 16 bit. Formulat e m\u00ebsip\u00ebrme p\u00ebr kodet e Reed-Solomon jan\u00eb t\u00eb tilla q\u00eb p\u00ebrdorimi i numrave t\u00eb zakonsh\u00ebm t\u00eb plot\u00eb, rezultati i llogaritjes p mund t\u00eb mos paraqitet me nj\u00eb fjal\u00eb t\u00eb madh\u00ebsis\u00eb s\u00eb pranueshme.<\/li>\n
  2. Gjat\u00eb rikuperimit t\u00eb t\u00eb dh\u00ebnave, formulat e m\u00ebsip\u00ebrme do t\u00eb konsiderohen si nj\u00eb sistem ekuacionesh q\u00eb duhet t\u00eb zgjidhen p\u00ebr t\u00eb rikuperuar t\u00eb dh\u00ebnat. Gjat\u00eb procesit t\u00eb zgjidhjes, mund t\u00eb lind\u00eb nevoja p\u00ebr t\u00eb kryer ndarje t\u00eb numrave t\u00eb plot\u00eb ndaj nj\u00ebri-tjetrit, rezultat i t\u00eb cilit do t\u00eb jet\u00eb nj\u00eb num\u00ebr real q\u00eb nuk mund t\u00eb paraqitet sakt\u00ebsisht n\u00eb memorien e kompjuterit.<\/li>\n<\/ol>\n

    <\/p>\n

    K\u00ebto probleme nuk lejojn\u00eb p\u00ebrdorimin e numrave t\u00eb plot\u00eb p\u00ebr kodet e Reid-Solomonit. Zgjidhja e problemit \u00ebsht\u00eb origjinale dhe mund t\u00eb p\u00ebrshkruhet si m\u00eb posht\u00eb: le t\u00eb shpikim numra special\u00eb, t\u00eb cil\u00ebt mund t\u00eb p\u00ebrfaq\u00ebsohen me fjal\u00eb t\u00eb gjat\u00eb t\u00eb nevojshme (p.sh., 16 bit), dhe rezultati i ekzekutimit t\u00eb t\u00eb gjitha operacioneve mbi ta (shtimi, zbritja, shum\u00ebzimi, ndarja) gjithashtu do t\u00eb p\u00ebrfaq\u00ebsohet n\u00eb memorien e kompjuterit me fjal\u00eb t\u00eb gjat\u00eb t\u00eb nevojshme.<\/p>\n

    <\/p>\n

    K\u00ebto numra \"special\u00eb\" jan\u00eb studiuar prej koh\u00ebsh nga matematika dhe quhen fusha. Nj\u00eb fush\u00eb \u00ebsht\u00eb nj\u00eb sasi elementesh me operacione t\u00eb caktuara p\u00ebr ta, si shtimi, zbritja, shum\u00ebzimi dhe ndarja.<\/p>\n

    <\/p>\n

    Fushat Galois* jan\u00eb fushat p\u00ebr t\u00eb cilat ekziston nj\u00eb dhe vet\u00ebm nj\u00eb rezultat p\u00ebr secil\u00ebn operacion (+, -, *, \/) p\u00ebr \u00e7do dy elemente t\u00eb fush\u00ebs. Fushat Galois mund t\u00eb nd\u00ebrtohen p\u00ebr numra q\u00eb jan\u00eb fuqi t\u00eb 2: 2, 4, 8, 16 etj. (n\u00eb t\u00eb v\u00ebrtet\u00eb fuqi e \u00e7do numri t\u00eb thjesht\u00eb p, por n\u00eb praktik\u00eb na interesojn\u00eb vet\u00ebm fuqit\u00eb e 2). P\u00ebr shembull, p\u00ebr fjal\u00eb me madh\u00ebsi 16 bit, kjo fush\u00eb p\u00ebrmban 65,536 elemente, p\u00ebr \u00e7do \u00e7ift, ku mund t\u00eb gjenden rezultatet e \u00e7do operacioni (+, -, *, \/). Vlerat x, p, alfa, beta, gama, delta nga ekuacionet e m\u00ebsip\u00ebrme p\u00ebr llogaritjet do t\u00eb konsiderohen si elemente t\u00eb fush\u00ebs Galois.<\/p>\n

    <\/p>\n

    k\u00ebshtu, ne kemi nj\u00eb sistem ekuacionesh, p\u00ebrmes t\u00eb cilave mund t\u00eb nd\u00ebrtojm\u00eb blloqe kodi t\u00eb tep\u00ebrt, duke shkruar nj\u00eb program kompjuterik t\u00eb p\u00ebrshtatsh\u00ebm. Me k\u00ebt\u00eb sistem ekuacionesh mund t\u00eb kryhet gjithashtu rinovimi i t\u00eb dh\u00ebnave.<\/p>\n

    <\/p>\n

    * Kjo nuk \u00ebsht\u00eb nj\u00eb p\u00ebrkufizim i sakt\u00eb, m\u00eb shum\u00eb nj\u00eb p\u00ebrshkrim.<\/p>\n

    <\/p>\n

    Si t\u00eb rikuperoni t\u00eb dh\u00ebnat<\/h3>\n

    <\/p>\n

    Rivitalizimi \u00ebsht\u00eb i nevojsh\u00ebm kur nga n + m blloqe, disa blloqe mungojn\u00eb. K\u00ebto mund t\u00eb jen\u00eb si blloqe t\u00eb dh\u00ebnash ashtu dhe blloqe t\u00eb kodit t\u00eb tep\u00ebrt. Mungesa e blloqeve t\u00eb dh\u00ebnash dhe\/ose e blloqeve t\u00eb kodit t\u00eb tep\u00ebrt do t\u00eb thot\u00eb se n\u00eb ekuacionet e m\u00ebsip\u00ebrme, variablat p\u00ebrkat\u00ebs x dhe\/ose p jan\u00eb t\u00eb panjohura.<\/p>\n

    <\/p>\n

    Ekuacionet p\u00ebr kodet Reed-Solomon mund t\u00eb trajtohen si nj\u00eb sistem ekuacionesh, ku t\u00eb gjitha vlerat alfa, beta, gamma, delta - jan\u00eb konstanta, t\u00eb gjitha x dhe p, p\u00ebrkat\u00ebse blloqeve t\u00eb disponuesh\u00ebm, - jan\u00eb variabla t\u00eb njohur, nd\u00ebrsa x dhe p t\u00eb tjerat - jan\u00eb t\u00eb panjohur.<\/p>\n

    <\/p>\n

    P\u00ebr shembull, le t\u00eb supozojm\u00eb se blloqet e t\u00eb dh\u00ebnave 1, 2, 3 dhe blloku i kodit t\u00eb tep\u00ebrt 2 nuk jan\u00eb t\u00eb disponueshme, at\u00ebher\u00eb p\u00ebr grupin e fjal\u00ebve i do t\u00eb kemi sistemin e m\u00ebposht\u00ebm t\u00eb ekuacioneve (t\u00eb panjohurat sh\u00ebnohen me t\u00eb kuqe):<\/p>\n

    <\/p>\n

    \"Kodet<\/p>\n

    <\/p>\n

    Ne kemi nj\u00eb sistem prej 4 ekuacionesh me 4 t\u00eb panjohura, k\u00ebshtu q\u00eb mund ta zgjidhim at\u00eb dhe t\u00eb rivitalizojm\u00eb t\u00eb dh\u00ebnat!<\/p>\n

    <\/p>\n

    Nga ky sistem ekuacionesh, rrjedhin disa p\u00ebrfundime n\u00eb lidhje me rivitalizimin e t\u00eb dh\u00ebnave p\u00ebr kodet Reed-Solomon (n blloqe t\u00eb dh\u00ebnash, m blloqe t\u00eb kodit t\u00eb tep\u00ebrt):<\/p>\n

    <\/p>\n