Perusalgebra salaisten koodien ja avaruusviestinnän takana

Avaruustutkimus vaatii valtavaa tarkkuutta. Kun laskeudut mönkijän Marsiin 70 miljoonan mailin päässä lähimmästä huoltoasemasta, sinun on maksimoitava tehokkuus ja varauduttava odottamattomiin. Tämä koskee kaikkea avaruusalusten suunnittelusta tiedonsiirtoon: Viestit, jotka palaavat Maahan tasaisena 0:n ja 1:n virtana, sisältävät varmasti joitain virheitä, joten sinun on kyettävä tunnistamaan ja korjaamaan ne tuhlaamatta arvokasta aikaa ja energiaa.

Siellä matematiikka tulee esiin. Matemaatikot ovat keksineet nerokkaita tapoja välittää ja tallentaa tietoa. Yksi yllättävän tehokas tapa käyttää Reed-Solomon koodit, jotka rakentuvat samalle perusalgebralle, jonka oppilaat oppivat koulussa. Lähdetään matematiikan tunnille nähdäksesi, kuinka Reed-Solomon-koodit auttavat välittämään ja suojaamaan tietoja samalla kun korjaavat mahdolliset kalliit virheet.

Kaksi opiskelijaa, Art ja Zeke, vaihtavat salaisia ​​viestejä Ms Al-Jabrin matematiikan tunnilla. Art paljastaa Zeken viimeisimmän nuotin paljastaakseen numerot 57 ja 99. Hän tietää, että hänen on toimitettava x-koordinaatit 3 ja 6 luodaksesi pisteet (3, 57) ja (6, 99). Taide kytkee jokaisen pisteen lineaariseen yhtälöön y = Ax + B ja tuottaa seuraavan yhtälöjärjestelmän:

57 = 3A + B

99 = 6A + B

Taiteen on ratkaistava viestin purkaakseen A ja B. Hän aloittaa vähentämällä ensimmäisen yhtälön toisesta:

Tämä eliminoi B. Tämän uuden yhtälön molempien puolten jakaminen kolmella kertoo Artille sen A = 14, ja korvaamalla tämä takaisin ensimmäiseen yhtälöön, 57 = 3 × 14 + B, antaa B = 15.

Taide tietää nyt, että viiva, joka kulkee kohtien (3, 57) ja (6, 99) kautta, kuvataan yhtälöllä y = 14x + 15. Mutta hän tietää myös, että Reed-Solomon -koodissa salainen viesti piilee kertoimissa. Hän purkaa Zeken viestin käyttämällä heidän yksinkertaista sovittua aakkossalausta: 14 on "N" ja 15 on "O", mikä kertoo Artille, että ei, Zeke ei voi pelata videopelejä koulun jälkeen tänään.

Tämän yksinkertaisen Reed-Solomon-koodin salaisuus alkaa kahdesta geometrian perusasiasta. Ensinnäkin minkä tahansa kahden pisteen läpi on ainutlaatuinen viiva. Toiseksi kertoimille A ja B, jokainen (ei pystysuora) rivi voidaan kirjoittaa muotoon y = Ax + B. Yhdessä nämä kaksi tosiasiaa takaavat, että jos tiedät kaksi pistettä viivalla, voit löytää A ja B, ja jos tiedät A ja B, tiedät kaikki pisteet viivalla. Lyhyesti sanottuna kumman tahansa tietojoukon hallussapito vastaa linjan tuntemista.

Reed-Solomonin koodit hyödyntävät näitä vastaavia tietojoukkoja. Salainen viesti on koodattu kertoimilla A ja B, ja linjan pisteet hajotetaan osiin, joista osa lähetetään julkisesti ja osa pidetään yksityisinä. Viestin purkamiseksi sinun tarvitsee vain kerätä palaset ja laittaa ne takaisin yhteen. Ja kaikki mitä tämä vaatii, on yksinkertainen algebra.

Zeken kappaleita olivat numerot 57 ja 99, jotka hän lähetti Artille. Nämä numerot ovat viestin julkinen osa. Taide yhdisti ne omilla teoksillaan 3 ja 6 rekonstruoidakseen kohdat (3, 57) ja (6, 99). Tässä 3 ja 6 muodostavat viestin yksityisen osan, josta Art ja Zeke sopivat etukäteen.

Nämä kaksi pistettä sijaitsevat viivalla, ja viestin dekoodaamiseksi sinun tarvitsee vain löytää kyseisen viivan yhtälö. Jokaisen pisteen liittäminen y = Ax + B antaa sinulle kahden yhtälön järjestelmän suorasta, joiden molempien on oltava tosia. Nyt strategia on suoraviivainen: Ratkaise järjestelmä, määritä linja ja pura viesti.

Algebratunnilla olet luultavasti oppinut monia yhtälöjärjestelmien ratkaisumenetelmiä, kuten graafisen piirtämisen, arvaamisen ja tarkistamisen sekä korvaamisen. Taide käytti eliminaatiota, menetelmää, jossa yhtälöitä käsitellään algebrallisesti muuttujien eliminoimiseksi yksi kerrallaan. Joka kerta kun poistat muuttujan, järjestelmästä tulee hieman helpompi ratkaista.

Kuten muissakin salausjärjestelmissä, se on julkisten ja yksityisten tietojen fiksu yhdistelmä, joka pitää viestit turvassa. Zeke voisi huutaa numeroitaan 57 ja 99 luokkahuoneen poikki, eikä se vaarantaisi hänen Artille lähettämänsä viestin turvallisuutta (vaikka se saattaa saada hänet vaikeuksiin neiti Al-Jabrin kanssa). Tämä johtuu siitä, että ilman vastaavia yksityisiä tietoja - x-koordinaatit 3 ja 6 — suoran yhtälön tunnistaminen on mahdotonta. Niin kauan kuin he pitävät nämä arvot omana tietonaan, he voivat välittää salaiset viestinsä turvallisesti julkisesti.

Linja y = 14x + 15 on hyvä lähettää kaksikirjaiminen sana "ei", mutta entä jos oppilaat haluavat jakaa pidemmän salaisuuden? Tässä kohtaa algebran, geometrian ja lineaaristen yhtälöjärjestelmien täysi teho.

Oletetaan, että Zeke haluaa tietää, kuinka Art luulee pärjäävänsä huomisessa englannin kokeessa. Art muuntaa kolmikirjaimisen vastauksensa numeroiksi 14, 59 ja 82 ja välittää ne Zekelle. Opiskelijat sopivat etukäteen, että käytettäessä Reed-Solomon-koodeja, joiden pituus on 3, heidän yksityisnumeronsa ovat 2, 5 ja 6, joten Zeke yhdistää palaset rekonstruoidakseen pisteet (2, 14), (5, 59) ja (6, 82).

Nyt ei ole olemassa lineaarifunktiota, joka kulkee näiden kolmen pisteen läpi. Mutta on olemassa ainutlaatuinen neliöfunktio, joka toimii. Ja koska jokainen neliöfunktio voidaan kirjoittaa muotoon y = Ax² + Bx + C, voidaan soveltaa samaa yleistä menetelmää. Ainoa ero on järjestelmän koko.

Jokaisen pisteen liittäminen y = Ax² + Bx + C tuottaa yhden yhtälön, joten kolme pistettä tuottavat seuraavan kolmen yhtälöjärjestelmän:

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

Kolmen yhtälöjärjestelmän, jossa on kolme tuntematonta, ratkaiseminen vaatii hieman enemmän työtä kuin kahdesta yhtälöstä muodostuva järjestelmä, jossa on kaksi tuntematonta, mutta tavoite on sama: Yhdistä näppärästi yhtälöpareja muuttujien eliminoimiseksi.

Jos esimerkiksi vähennät ensimmäisen yhtälön toisesta, saat uuden yhtälön 45 = 21A + 3B. Samoin, jos vähennät toisen yhtälön kolmannesta, saat 23 = 11A + B. Nämä algebralliset manipulaatiot tuottavat uuden järjestelmän:

45 = 21A + 3B

23 = 11A + B

Nyt sinulla on "kaksi-kaksi"-järjestelmä: kaksi yhtälöä kahdella tuntemattomalla. Voit ratkaista sen kertomalla toisen yhtälön −3:lla ja lisäämällä sen ensimmäiseen yhtälöön:

Huomaa, kuinka toistuva eliminointi on muuttanut alkuperäisen kolmen yhtälön järjestelmän yhdeksi yhtälöksi, joka voidaan helposti ratkaista: A = 2. Työskennellä taaksepäin, voit kytkeä A = 2 johonkin kaksi kertaa kaksi -järjestelmän yhtälöistä löydettäväksi B = 1, ja liitä sitten molemmat arvot johonkin alkuperäisistä yhtälöistä saadaksesi C = 4. Käytettyään yksinkertaista aakkossalausta numeroissa 2, 1 ja 4, Zeke tietää, että Art tekee "HUONON" huomisessa englannin kokeessa. Ainakin hän harjoittelee paljon algebraa.

Polynomifunktioita koskevan erityisen tosiasian ansiosta voit lähettää minkä tahansa pituisen viestin Reed-Solomon-koodeilla. Avain on tämä: Jos mikä tahansa n tasossa eri pisteillä x-koordinaatit, on olemassa ainutlaatuinen "aste" polynomi n − 1, joka kulkee niiden läpi. Polynomin aste on lausekkeen muuttujan suurin potenssi, joten neliöfunktion kaltainen Ax² + Bx + C on aste 2, koska korkein potenssi x on 2. Ja lineaarifunktiolla on aste 1, koska yhtälössä y = Ax + B, suurin teho x on 1.

Ensimmäisessä esimerkissä käytimme sitä tosiasiaa, että kaksi pistettä määrittävät ainutlaatuisen lineaarisen eli aste-1 polynomin. Toisessa luotamme siihen tosiasiaan, että kolme pistettä määrittävät ainutlaatuisen aste-2 tai toisen asteen polynomin. Ja jos haluat lähettää viestin, jonka pituus on 10, koodaa viesti vain 10-asteisen polynomifunktion 9 kertoimeksi. Kun olet saanut funktiosi, laske 10 julkista y-arvot arvioimalla toiminto aiemmin sovitulla 10 yksityisellä x-arvot. Kun teet sen, voit ohittaa ne turvallisesti y-koordinoi julkisesti, jotta vastaanotin voi purkaa. Käytännössä Reed-Solomon-koodit ovat tätä hieman monimutkaisempia, ja niissä käytetään kehittyneempiä kertoimia ja käännösskeemoja, mutta perusidea on sama.

Sen lisäksi, että Reed-Solomon-koodit pitävät viestisi turvassa, ne tarjoavat myös yksinkertaisia ​​ja tehokkaita tapoja havaita ja jopa korjata virheet. Tämä on tärkeää aina, kun tietoja siirretään tai tallennetaan, koska on aina mahdollisuus, että osa tiedoista katoaa tai vioittuu.

Yksi ratkaisu tähän ongelmaan olisi yksinkertaisesti lähettää ylimääräisiä kopioita tiedoista. Esimerkiksi Zeke voi lähettää viestin [14, 14, 14, 15, 15, 15] [14, 15] sijaan. Niin kauan kuin Art tietää, että jokainen viestin osa lähetetään kolmena kappaleena, hän voi purkaa viestin ja tarkistaa virheiden varalta. Itse asiassa, jos hän löytää virheitä, hänellä on hyvät mahdollisuudet korjata ne. Jos Art saa [14, 14, 24, 15, 15, 15], se tosiasia, että kolme ensimmäistä numeroa ovat erilaiset, varoittaa häntä virheestä, ja koska kaksi niistä on 14, hän voi arvata, että 24:n pitäisi luultavasti olla 14 samoin. Sen sijaan, että Art pyytäisi viestin lähettämistä uudelleen, hän voi jatkaa dekoodaamistaan. Tämä on tehokas mutta kallis strategia. Mitä tahansa aikaa, energiaa ja vaivaa lähettäminen vaatii n Tietoa, tämä vaatii kolme kertaa niin paljon.

Mutta Reed-Solomon-koodien takana oleva matematiikka tarjoaa tehokkaan vaihtoehdon. Sen sijaan, että lähettäisit useita kopioita jokaisesta tiedosta, voit lähettää vain yhden lisäpisteen! Jos tämä lisäpiste sopii polynomiisi, tiedot ovat oikein. Jos ei, on tapahtunut virhe.

Jos haluat nähdä, miten tämä toimii, oletetaan, että haluat tarkistaa viestin "EI" ensimmäisessä esimerkissä. Zeke voi vain lähettää ylimääräisen y-koordinaatti 155. Olettaen, että hän ja Art sopivat kolmannesta yksityisestä x- Koordinoi etukäteen, sano x = 10, Art voi tarkistaa tämän kolmannen pisteen dekoodaamaansa viivaa vastaan. Kun hän kytkeytyy x = 10 sisään y = 14x + 15 ja näkee tuloksen 155, hän tietää, että lähetyksessä ei ollut virheitä.

Tämä ei sovellu vain linjoille. Jotta Zeke voi tarkistaa "BAD" toisessa esimerkissä, Art voi lähettää y = 25. Jos he ovat sopineet, että 3 on ylimääräinen yksityinen x-koordinaatti, Zeke voi kytkeä x = 3 hänen toisen asteen funktioon y = 2x² + x + 4 ja varmista, että piste (3, 25) sopii, vahvistaen jälleen virheettömän lähetyksen yhdellä lisäpisteellä.

Ja tämä lisäpiste voi myös mahdollisesti korjata virheet. Jos havaitaan virhe eikä vastaanottaja voi rakentaa viestin sisältävää polynomifunktiota, se voi sen sijaan rakentaa "parhaiten sopivan" polynomin käyttämällä regressiotekniikoita. Kuten tilastoluokassa parhaiten sopiva viiva, tämä on polynomifunktio, joka on matemaattisesti määritetty sopimaan parhaiten annettuihin pisteisiin, vaikka se ei kulkisikaan kaikkien läpi. Riippuen viestin rakenteesta ja lähettämästäsi lisäinformaatiosta, tämä parhaiten sopiva polynomi voi auttaa sinua rekonstruoimaan oikean polynomin – ja siten oikean viestin – jopa vioittuneesta tiedosta.

Tämä tehokkuus viestinnän välittämisessä ja korjaamisessa selittää, miksi NASA on käyttänyt Reed-Solomon-koodeja lennoillaan kuuhun ja Marsiin. Ja se antaa sinulle pohdittavaa, kun ratkaiset seuraavaa yhtälöjärjestelmääsi. Kun arvaat, tarkista tai poista tiesi ratkaisuun, ajattele Reed-Solomon-koodien voimaa ja eleganssia sekä kaikkia salaisuuksia, joita järjestelmäsi saattaa paljastaa.

Harjoitukset

1. Käyttäen samaa kaavaa, jota he käyttivät luokassa, Art lähettää julkiset numerot 33 ja 57 Zeken dekoodattavaksi. Mikä on viesti?

2. Miten Art ja Zeke voivat olla varmoja, että yhtälöjärjestelmä, joka johtuu heidän yksityisistä numeroistaan x = 3 ja x = 6:lla on aina ratkaisu?

3. Vastauksena Artin viestiin "BAD" englannin kokeesta Zeke lähettää takaisin [90, 387, 534]. Olettaen, että he käyttävät samaa menetelmää kuin luokassa, mikä on hänen viestinsä?

4. Lola lähettää sinulle kaksikirjaimisen viestin sekä yhden virheentarkistusnumeron käyttäen Reed-Solomon-koodia ja samaa yksinkertaista aakkossalausta, jota Art ja Zeke käyttävät. Olet salaa sopinut asiasta x-koordinaatit 1, 3 ja 10 etukäteen, ja Lola lähettää julkiset numerot [27, 43, 90]. Sisältääkö viesti virheen?