Kun otetaan huomioon kokoelma avaruuden pisteitä, voitko löytää tietyn tyyppisen käyrän, joka kulkee kaikkien niiden läpi? Tämä kysymys – versio niin sanotusta interpolointiongelmasta – on kiinnostanut matemaatikoita antiikista lähtien. Aiemmin tänä vuonna matemaatikot Eric Larson ja Isabel Vogt ratkaisi sen kokonaan.
Mutta vaikka työ on herättänyt paljon jännitystä puhtaiden matemaatikoiden keskuudessa, interpoloinnilla on käytännön seurauksia, jotka ulottuvat paljon geometrian alan ulkopuolelle. Interpolointi on keskeistä sähköisen tiedon tallentamisessa ja välittämisessä, salausjärjestelmien rakentamisessa ja muissa asioissa. Tästä syystä voit naarmuttaa CD-levyä ja silti kuunnella musiikkia tai likaa QR-koodin ja silti skannata sen. Siksi Voyager-ohjelman kaltaiset avaruustehtävät voisivat lähettää selkeitä digitaalisia kuvia takaisin Maahan. Tästä syystä tietokoneryhmä voi suorittaa monimutkaisia laskelmia, vaikka jokin näistä tietokoneista epäonnistuisi.
Kaikki nämä sovellukset perustuvat hämmästyttävän kauniiseen ja käsitteellisesti yksinkertaiseen interpoloinnin käyttöön: niin sanottuihin Reed-Solomon-koodeihin ja niihin perustuviin koodeihin.
Piste pisteeltä
Oletetaan, että haluat lähettää viestin, joka koostuu kahdesta numerosta: 2 ja 7. On mahdollista, että osa lähettämistäsi tiedoista katoaa tai vioittuu – 2 voi esimerkiksi kääntyä -2:ksi. Pelkän tietojen lähettämisen sijaan voit lisätä lisätietoja, jotka auttavat vastaanottajaa tunnistamaan ja korjaamaan mahdollisesti ilmenevät virheet. Tätä kutsutaan virheenkorjauskoodiksi.
Yksinkertaisin esimerkki tällaisesta koodista sisältää saman viestin lähettämisen useita kertoja. Jotta vastaanottaja voi tunnistaa virheen, lähetä sama viesti kahdesti: 2, 7, 2, 7. Jos vastaavien paikkojen numerot eivät täsmää (esim. jos lähetys on sen sijaan 2, 7, −2, 7), vastaanottaja tietää, että yksi niistä on väärässä – mutta ei kumpi. Jotta he voivat selvittää asian ja korjata virheen, lähetä sama viesti kolme kertaa: 2, 7, 2, 7, 2, 7. Vastaanottajan on yksinkertaisesti saatava enemmistö äänestääkseen viestisi.
Mutta tämä tapa korjata virheitä on erittäin tehoton. Tässä on älykkäämpi lähestymistapa: Koodaa viesti käyräksi ja lähetä juuri tarpeeksi tietoa, jotta vastaanottaja voi rekonstruoida käyrän.
Yksinkertaisessa tapauksessamme lähettää 2 ja 7, käyrä olisi viiva y = 2x + 7. Arvioi tämä käyrä kahdella ennalta määrätyllä arvolla xja lähetä tulos y-arvot. Vastaanottajalla on nyt kaksi pistettä, ja koska interpolointiongelma kertoo meille, että kaksi pistettä määrittävät ainutlaatuisen suoran, vastaanottajan on yksinkertaisesti löydettävä viiva, joka kulkee vastaanottamiensa pisteiden läpi. Viivan kertoimet paljastavat tarkoitetun viestin.
Virheiden välttämiseksi lisäät vielä kerran lisätietoja. Tässä lähetät y-arvo, joka vastaa toista ennalta määrättyä x-koordinaatti. Jos kolme pistettä eivät osu samalle viivalle, kyseessä on virhe. Ja selvittääksesi, missä virhe on, lähetät vain yhden arvon lisää – eli olet lähettänyt yhteensä neljä numeroa edellisen menetelmän edellyttämien kuuden sijaan.
Etu kasvaa viestin koon myötä. Oletetaan, että haluat lähettää pidemmän viestin – 1,000 2,000 numeroa. Tehokkaampi koodi vaatisi 3,000 1,001 numeron lähettämistä virheen tunnistamiseksi ja 1,002 XNUMX numeron lähettämistä sen korjaamiseksi. Mutta jos käytät koodia, joka sisältää polynomin interpoloinnin annettujen pisteiden kautta, tarvitset vain XNUMX XNUMX numeroa virheen löytämiseen ja XNUMX XNUMX numeroa sen korjaamiseen. (Voit lisätä pisteitä tunnistaaksesi ja korjataksesi enemmän mahdollisia virheitä.) Viestisi pituuden kasvaessa näiden kahden koodin tehokkuusero kasvaa.
Tehokkaampaa koodia kutsutaan Reed-Solomon-koodiksi. Sen käyttöönoton jälkeen vuonna 1960 matemaatikot ovat tehneet uusia läpimurtoja kehittämällä algoritmeja, jotka voivat korjata enemmän virheitä tehokkaammin. "Se on erittäin tyylikäs, puhdas, konkreettinen", sanoi Swastik Kopparty, matemaatikko ja tietojenkäsittelytieteilijä Toronton yliopistosta. "Se voidaan opettaa toisen vuoden perustutkinto-opiskelijalle puolessa tunnissa."
Reed-Solomon-koodit ovat olleet erityisen hyödyllisiä tiedon tallentamiseen ja välittämiseen sähköisesti. Mutta sama konsepti on ollut olennainen myös kryptografiassa ja hajautetussa tietojenkäsittelyssä.
Otetaan salaisuuden jakaminen: Oletetaan, että haluat jakaa salaisuuden useiden osapuolten kesken siten, että kukaan ei pääse käsiksi koko salaisuuteen, mutta yhdessä he voivat. (Kuvittele esimerkiksi salausavain tai ohjuksen laukaisukoodi.) Koodaat numerot polynomiin, arvioit tämän polynomin ennalta määrätyssä pistejoukossa ja jaat jokaisen tuloksen eri henkilölle.
Viime aikoina Reed-Solomon-koodeja on käytetty sellaisilla aloilla kuin pilvilaskenta ja lohkoketjutekniikka. Oletetaan, että sinun on suoritettava laskenta, joka on liian monimutkainen kannettavallesi tietokoneellesi, joten sinulla on suuri laskentaklusteri, joka suorittaa sen – mutta nyt sinun on varmistettava, että saamasi laskenta on oikea. Reed-Solomon-koodien avulla voit pyytää lisätietoja, joita klusteri ei todennäköisesti pysty tuottamaan, jos se ei ole suorittanut laskentaa oikein. "Tämä toimii maagisesti", sanoi Jade Nardi, tutkija Rennesin matematiikan instituutissa Ranskassa. "Tämä prosessi on todella upea, ja tapa, jolla se perustuu [näihin koodeihin], räjäyttää mieleni."
Mutta Reed-Solomon-koodeilla on myös tärkeä rajoitus. Ne on rakennettu siten, että voit arvioida polynomin vain kiinteällä (ja yleensä suhteellisen pienellä) arvojoukolla. Toisin sanoen olet rajoitettu käyttämään tiettyä numerosarjaa viestisi koodaamiseen. Tuon sarjan tai aakkosten koko puolestaan rajoittaa lähetettävien viestien pituutta – ja mitä suurempia yrität tehdä aakkosista, sitä enemmän laskentatehoa tarvitset näiden viestien purkamiseen.
Ja niin matemaatikot etsivät vieläkin optimaalisemman koodin.
Tulevaisuuden koodit
Yleisempi, tehokkaampi koodi mahdollistaisi pidempien viestien tallentamisen tai lähettämisen ilman, että sinun tarvitsee suurentaa aakkosesi kokoa. Tätä varten matemaatikot kehittivät koodeja, jotka sisältävät funktion - joka asuu erityisessä tilassa, joka liittyy monimutkaisempaan käyrään - interpoloimisen käyrän tiettyjen pisteiden kautta. Nämä niin kutsutut algebrallisen geometrian koodit "tulivat tyhjästä, ja ne ovat parempia kuin mikään muu koodi, jonka osaamme tehdä [pienemmällä aakkosella]", Kopparty sanoi. "Tämä voittaa kaiken. Se oli todellinen shokki."
On vain yksi ongelma. Käytännössä Reed-Solomon-koodin toteuttaminen on paljon, paljon helpompaa kuin algebrallisen geometrian koodin toteuttaminen. "Tämä on viimeisintä tekniikkaa, mutta sitä tutkitaan edelleen, jotta siitä tulisi jotain käytännöllistä", kryptologi sanoi. Simon Abelard. "Se sisältää melko abstraktia matematiikkaa, ja näitä koodeja on vaikea käsitellä tietokoneella."
Toistaiseksi se ei ole huolestuttavaa: Tosimaailman sovelluksissa Reed-Solomon-koodit ja niihin liittyvät virheenkorjausmuodot ovat riittäviä. Mutta näin ei välttämättä aina ole. Jos esimerkiksi tehokkaita kvanttitietokoneita tulee saataville tulevaisuudessa, he pystyvät siihen rikkoa nykypäivän salausprotokollat. Tämän seurauksena tutkijat ovat etsineet järjestelmiä, jotka voivat vastustaa kvanttihyökkäyksiä. Yksi huippuehdokas tällaisiin järjestelmiin vaatisi jotain vahvempaa kuin Reed-Solomon -koodit. Tietyt versiot algebrallisista geometriakoodeista saattavat vain toimia. Muut tutkijat ovat toiveikkaita algebrallisen geometrian koodien roolista pilvitekniikassa.
Mutta vaikka tällaisia potentiaalisia käyttötarkoituksia ei olisikaan, "matematiikan historiassa joskus löytää uusia asioita, joille ei todellakaan ole sovelluksia nykyään", sanoi Elena Berardini, tutkija Eindhovenin teknillisessä yliopistossa Alankomaissa, joka työskentelee algebrallisen geometrian koodien parissa. "Mutta sitten 50 vuoden jälkeen huomaat, että siitä voi olla hyötyä jollekin täysin odottamattomalle" - aivan kuten itse interpoloinnin muinainen ongelma.
