Кодты өшіру - Erasure code

Жылы кодтау теориясы, an өшіру коды Бұл алға қатені түзету Хабарламасын түрлендіретін биттік өшірулер (биттік қателіктерден гөрі) бойынша код (FEC) к таңбаларын ұзағырақ хабарламаға (код сөзі) қосыңыз n ішіндегі бастапқы хабарламаны қалпына келтіруге болатын белгілер n шартты белгілер. Бөлшек р = к/n деп аталады код жылдамдығы. Бөлшек к ’/ к, қайда k ’ қалпына келтіруге қажетті таңбалардың санын білдіреді, деп аталады қабылдау тиімділігі.

Оңтайлы өшіру кодтары

Оңтайлы өшіру кодтарының кез келген қасиеті бар к ішінен n кодты сөздер белгілері бастапқы хабарды қалпына келтіру үшін жеткілікті (яғни, қабылдаудың оңтайлы тиімділігі бар). Оңтайлы өшіру кодтары максималды арақашықтық кодтары (MDS кодтары).

Паритетті тексеру

Паритетті тексеру - бұл ерекше жағдай n = к + 1. жиынтығынан к құндылықтар ${ displaystyle {v_ {i} } _ {1 leq i leq k}}$ , бақылау сомасы есептеледі және қосылады к бастапқы мәндер:

{ displaystyle v_ {k + 1} = - sum _ {i = 1} ^ {k} v_ {i}.}

Жиынтығы к + 1 мән ${ displaystyle {v_ {i} } _ {1 leq i leq k + 1}}$ Енді бақылау сомасына сәйкес келеді, егер осы мәндердің бірі болса, ${ displaystyle v_ {e}}$ , өшіріледі, оны қалған айнымалыларды қосу арқылы қалпына келтіруге болады:

{ displaystyle v_ {e} = - sum _ {i = 1, i neq e} ^ {k + 1} v_ {i}.}

Көпмүшелік шамадан тыс таңдау

Мысалы: қате пошта (к = 2)

Қарапайым жағдайда қайда к = 2, артық белгілер екі бастапқы таңба арасындағы сызық бойымен әр түрлі нүктелерді іріктеу арқылы жасалуы мүмкін. Бұл err-mail деп аталатын қарапайым мысалда көрсетілген:

Алиса телефон нөмірін (555629) мына мекен-жайға жібергісі келеді Боб қате поштаны пайдалану. Err-mail электронды пошта сияқты жұмыс істейді, тек басқа

Барлық поштаның жартысына жуығы жоғалады.^[1]
5 таңбадан асатын хабарламалар заңсыз.
Бұл өте қымбат (поштаға ұқсас).

Бобтан жіберген хабарларын растауын сұраудың орнына Алиса келесі схеманы ойластырады.

Ол телефон нөмірін екі бөлікке бөледі а = 555, б = 629, және Бобқа 2 хабар жібереді - «A = 555» және «B = 629».
Ол сызықтық функция жасайды, ${ displaystyle f (i) = a + (b-a) (i-1)}$ , Бұл жағдайда ${ displaystyle f (i) = 555 + 74 (i-1)}$ , осылай ${ displaystyle f (1) = 555}$ және ${ displaystyle f (2) = 629}$ .

Код d'effacement оңтайлы 1.gif

Ол құндылықтарды есептейді f(3), f(4) және f(5), содан кейін үш артық хабарлама жібереді: «C = 703», «D = 777» және «E = 851».

Боб формасын біледі f(к) болып табылады ${ displaystyle f (i) = a + (b-a) (i-1)}$ , қайда а және б телефон нөмірінің екі бөлігі. Енді Боб «D = 777» және «E = 851» алады делік.

Кодтың тиімділігі оңтайлы 2.gif

Боб Алисаның телефон нөмірін мәндерін есептеу арқылы қалпына келтіре алады а және б мәндерінен (f(4) және f(5)) алды. Боб бұл процедураны кез-келген екі қате хаттарды қолдана отырып орындай алады, сондықтан мысалдағы өшіру коды 40% құрайды.

Алиса өзінің телефон нөмірін бір ғана қате пошта арқылы кодтай алмайтындығына назар аударыңыз, өйткені ол алты таңбадан тұрады және бір хат-хабардың максималды ұзындығы бес таңбадан тұрады. Егер ол өзінің телефон нөмірін Бобтан әр бөліктің алынғанын растауын сұрап, бөліктерге жіберсе, бәрібір кем дегенде төрт хабарлама жіберілуі керек еді (екеуі Алистен, екеуі Бобтан алынған хабарламалар). Сонымен, бес мысалды қажет ететін мысалдағы өшіру коды өте үнемді.

Бұл мысал сәл ойдан шығарылған. Кез-келген деректер жиынтығында жұмыс істейтін шынымен жалпы өшіру кодтары үшін бізге бұдан басқа нәрсе қажет болады f(мен) берілген.

Жалпы жағдай

Жоғарыдағы сызықтық құрылысты жалпылауға болады көпмүшелік интерполяция. Сонымен қатар, ұпайлар енді a арқылы есептеледі ақырлы өріс.

Алдымен біз шектеулі өрісті таңдаймыз F кем дегенде бұйрықпен n, бірақ көбінесе қуаты 2. Жіберуші деректер таңбаларын 0-ден бастап нөмірлейді к - 1 және оларды жібереді. Содан кейін ол а (Лагранж) көпмүшелік б(х) бұйрық к осындай б(мен) мәліметтер белгісіне тең мен. Содан кейін ол жібереді б(к), ..., б(n - 1). Енді қабылдағыш жоғалған пакеттерді қалпына келтіру үшін полиномдық интерполяцияны қолдана алады, егер ол алған болса к таңбалар сәтті. Егер тәртібі F 2-ден аз^б, мұндағы b - таңбадағы биттер саны, содан кейін бірнеше көпмүшелерді қолдануға болады.

Жіберуші белгілерді тұрғыза алады к дейін n - 1 'ұшып бара жатқанда', яғни белгілерді беру арасында жүктемені біркелкі бөліңіз. Егер қабылдағыш өзінің есептеулерін «ұшып жүргенде» жасағысы келсе, онда ол жаңа көпмүшелік құра алады q, осылай q(мен) = б(мен) егер таңба мен < к сәтті қабылданды және q(мен) = 0 болған кезде таңба мен < к қабылданбады. Енді рұқсат етіңіз р(мен) = б(мен) − q(мен). Біріншіден, біз мұны білеміз р(мен) = 0, егер таңба мен < к сәтті қабылданды. Екіншіден, егер символ мен ≥к сәтті қабылданды, сол кезде р(мен) = б(мен) − q(мен) есептеуге болады. Сондықтан бізде салу үшін деректер нүктелері жеткілікті р және жоғалған пакеттерді табу үшін оны бағалаңыз. Сондықтан жіберуші де, алушы да талап етеді O(n (n − к)) операциялар және тек O(n − к) ұшу кезінде жұмыс істеуге арналған кеңістік.

Нақты әлемде жүзеге асыру

Бұл процесс жүзеге асырылады Рид-Сүлеймен кодтары, а сөзінің көмегімен салынған ақырлы өріс пайдалану Вандермонд матрицасы.

Оңтайлы өшіру кодтары

Оңтайлы өшіру кодтары талап ету (1 + ε)к хабарламаны қалпына келтіруге арналған белгілер (мұнда ε> 0). Төмендетуді CPU процессордың жұмыс уақытының есебінен жасауға болады.Оңтайлы өшіру кодтары есептеу күрделілігі үшін сауданы түзету мүмкіндіктері: практикалық алгоритмдер уақыттың сызықтық күрделілігімен кодтай және декодтай алады.

Фонтан кодтары (сонымен бірге жарамсыз өшіру кодтары) -ның көрнекті мысалдары болып табылады оңтайлы өшіру кодтары. Олар а-ны өзгерте алады к символдық хабарлама іс жүзінде шексіз кодталған формаға, яғни олар қателіктерді түзету үшін пайдалануға болатын артық белгілердің ерікті мөлшерін жасай алады. Алушылар декодтауды олардан гөрі сәл көбірек алғаннан кейін бастауы мүмкін к кодталған белгілер.

Қалпына келтіру кодтары жоғалған кодталған фрагменттерді қолданыстағы кодталған фрагменттерден қалпына келтіру (жөндеу деп те аталады) мәселесін шешу. Бұл мәселе кодталған резервтеуді сақтауға арналған байланыс проблемасы болып табылатын бөлінген сақтау жүйелерінде пайда болады.

Мысалдар

Әр түрлі кодтарды енгізу мысалдары:

Оңтайлы өшіру кодтарының жанында

Фонтанның оңтайлы кодтары (өшірілмеген өшіру)

Оңтайлы өшіру кодтары

Паритет: қолданылған RAID сақтау жүйелері.
Пархив
Тахо-Лафс кіреді зфек
Рид-Сүлеймен кодтары
Резистентті жүйелік кодты өшіріңіз, Reed-Solomon-дан артық пакеттердің санынан артық болатын MDS коды, қараңыз RS (4,2) 2 битпен немесе RS (9,2) 3 битпен
Жаңаратын кодтар^[2] қараңыз Wiki сақтау орны.
кез келген басқа MDS коды («Ең үлкен қашықтықты бөлуге болатын код» түрі)

Басқа

Орфографиялық алфавит

Сондай-ақ қараңыз

Қатені алға жіберу кодтар.
Құпия бөлісу (бастапқы құпия шифрланған және декодтау кворумы болғанға дейін жасырылғандығымен ерекшеленеді)

Әдебиеттер тізімі

^ Бұл оқиғаның кейбір нұсқаларында қате пошталық демонсқа сілтеме жасалған.
^ Димакис, Александрос Г .; Годфри, П.Брайтен; Ву, Юньнань; Уэйнрайт, Мартин Дж .; Рамчандран, Каннан (қыркүйек 2010). «Таратылған сақтау жүйелеріне арналған желіні кодтау». Ақпараттық теория бойынша IEEE транзакциялары. 56 (9): 4539–4551. arXiv:cs / 0702015. CiteSeerX 10.1.1.117.6892. дои:10.1109 / TIT.2010.2054295.

Сыртқы сілтемелер

Джерасера бұл Рид-Соломон мен Кошидің SIMD оптимизациясымен өшіру коды техникасын іске асыратын ақысыз бағдарламалық жасақтама.
Компьютерлік байланыстағы FEC бағдарламалық жасақтамасы Луиджи Риццо өшірудің оңтайлы кодтарын сипаттайды
Feclib бұл матрицалық матрицаларды қолданатын Луиджи Риццоның жұмысына жақын оңтайлы кеңейту. Жолақтың ені мен ақырлы өрістің өлшемі сияқты көптеген параметрлерді орнатуға болады. Ол сонымен қатар үлкенді сәтті пайдаланады тіркелу қазіргі заманғы процессорлардың өлшемі. Оның жоғарыда аталған оңтайлы кодтармен салыстыру деңгейі белгісіз.
Таратылған сақтау викиіне кодтау кодтарды қалпына келтіруге және өшіру кодтарын қалпына келтіруге арналған.
ECIP «Интернет-протоколды өшіру» 1996 жылы жасалған, Интернеттегі «Алға жіберілген қателерді түзету» ФЭК-нің алғашқы қолданылуы. Ол алғаш рет коммерциялық мақсатта * қолданылдыШри-Ланкадағы сэр Артур К.Кларктың Индианадағы ДБОО-ға тікелей эфирдегі видеосы.

[1] Бұл оқиғаның кейбір нұсқаларында қате пошталық демонсқа сілтеме жасалған.

[regcodes-2] Димакис, Александрос Г .; Годфри, П.Брайтен; Ву, Юньнань; Уэйнрайт, Мартин Дж .; Рамчандран, Каннан (қыркүйек 2010). «Таратылған сақтау жүйелеріне арналған желіні кодтау». Ақпараттық теория бойынша IEEE транзакциялары. 56 (9): 4539–4551. arXiv:cs / 0702015. CiteSeerX 10.1.1.117.6892. дои:10.1109 / TIT.2010.2054295.

[1]

[2]