See veebileht kasutab küpsiseid kasutaja sessiooni andmete hoidmiseks. Veebilehe kasutamisega nõustute ETISe kasutustingimustega. Loe rohkem
Olen nõus
"Mobilitas Pluss Returning Researcher Grant / Mobilitas Pluss tagasipöörduva teadlase toetus" projekt MOBTP57
MOBTP57 "Koodide üle permutatsioonide matemaatilised alused rakendustega välkmälude jaoks (1.10.2017−31.12.2017)", Ago-Erik Riet, Tartu Ülikool, Loodus- ja täppisteaduste valdkond, matemaatika ja statistika instituut.
MOBTP57
Koodide üle permutatsioonide matemaatilised alused rakendustega välkmälude jaoks
Mathematical foundations of codes over permutations with applications to flash memories
1.10.2017
31.12.2017
Teadus- ja arendusprojekt
Mobilitas Pluss Returning Researcher Grant / Mobilitas Pluss tagasipöörduva teadlase toetus
ValdkondAlamvaldkondCERCS erialaFrascati Manual’i erialaProtsent
4. Loodusteadused ja tehnika4.4. MatemaatikaP110 Matemaatiline loogika, hulgateooria, kombinatoorika1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)50,0
4. Loodusteadused ja tehnika4.6. ArvutiteadusedP170 Arvutiteadus, arvutusmeetodid, süsteemid, juhtimine (automaatjuhtimisteooria)1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)50,0
PerioodSumma
01.10.2017−31.12.201713 706,12 EUR
13 706,12 EUR
0,00 EUR

Permutatsioonikoode saab potentsiaalselt rakendada elektriliinikommunikatsioonis ja püsimälude jaoks, mis motiveerib vastava teooria ülesehitamist. Teooria võib leida rakendusi praktilistes süsteemides mitte kuigi kauges tulevikus. Ma kavatsen leida, kuidas töötada efektiivselt permutatsioonide ja permutatsioonikoodidega, uurides permutatsioonikoodide kanalkodeerimist erinevates meetrikates: kavatsen tõestada tõkkeid maksimaalsele koodisuurusele ja leida koodikonstruktsioone teoreetiliselt ja arvuti abil, leida ja uurida kodeerimise ja dekodeerimise efektiivseid algoritme erinevates meetrikates. Samuti soovin uurida allikas- ja allikas-kanalkodeerimist permutatsioonideks. Üldiselt kavatsen aidata kaasa parema matemaatilise raamistiku leidmisele permutatsioonide ja permutatsioonikoodidega töötamiseks, mille motivatsiooniks on järgumodulatsioon välkmälude jaoks.
Permutation codes can potentially be applied to power-line communication and to non-volatile (flash) memories, which motivates building their theory. The theory may have applications in practical systems in the not-so-distant future. I intend to research how to efficiently work with permutations and permutation codes by studying channel coding of permutation codes in various metrics: I intend to prove bounds on maximum code size and find code constructions theoretically and with the help of computers, find and study efficient algorithms for encoding and decoding in various metrics. I intend to research source and source-channel coding into permutations. Overall I would like to contribute to arriving at a better mathematical framework of working with permutations and permutation codes, with motivation coming from rank modulation for flash memories.
Olin sunnitud lõpetama projekti ennetähtaegselt, täites projekti kahe aasta asemel esimesed kolm kuud. Tegin põhiliselt projektiavalduse esimese kolme kuu tegevusi. Põhiliselt tegelesin arvuti abil võimalike koodide uurimisega. See ülesanne nõuab arvutuslikku variantide läbivaatust, et genereerida häid (suuri) koode või näidata veelgi suuremate koodide võimatust. Ulami meetrikas antud permutatsioonikoodide puhul saab läbivaatust teha, kui probleemi vaadelda graafide keeles. Graafide keeles otsime graafis suurimat klikki, kusjuures graafi tipud on mingil loomulikul viisil korrektselt värvitud, st jaotatud sõltumatuteks hulkadeks. Seejuures Singleton-optimaalne kood vastaks klikile, kuhu kuulub igast sõltumatust hulgast täpselt üks tipp. Kui vaatleme koodsõnu, milleks on osad permutatsioonid n fikseeritud elemendist ning koodi minimaalne (kõigi koodsõnade paaride vaheline) Ulami kaugus on d, siis Singletoni tõke annab, et koodi maksimaalne suurus (maksimaalne koodsõnade arv) on ülimalt (n-d+1)!. Singleton-optimaalse Ulami kauguses koodi olemasolu küsimus arvupaari (n,d) jaoks on seega küsimus sellise suurusega koodi olemasolust või puudumisest. Vähimad lahtised juhud on (n,d)=(7,4) ja (7,3). Üheks konkreetseks probleemiks oleks programmi optimiseerimine arvutusklastri jaoks, mis võimaldaks neid juhtusid arvuti abil lahendada. Projekti täitmise ajal õnnestus mul osa võtta Eesti ja Läti arvutiteaduse teooriapäevadest, kus mul õnnestus rääkida Helsingi Aalto ülikooli teadlastega. Neil on kogemus kombinatoorikaülesannete lahendamisel arvuti abil ning suurima kliki leidmisest. Õnnestus saada sissevaadet, kuidas oleks kõige parem vastavaid eelmises lõigus mainitud arvutusi optimiseerida. Üldiselt mingi piirini tuleks teha analoogiliste juhtude (isomorfsete juhtude) väljaviskamist ja alates mingist piirist juba läbivaatust. Eesmärgiks oleks läbivaatusprogrammi tööaja vähendamine. Konkreetsed parameetrid optimiseerimiseks saab leida eksperimentidega arvuti abil.