Osnovna algebra za tajnimi kodami in vesoljsko komunikacijo

Raziskovanje vesolja zahteva izjemno natančnost. Ko pristajate z roverjem na Marsu, 70 milijonov milj stran od najbližje bencinske črpalke, morate povečati učinkovitost in se pripraviti na nepričakovano. To velja za vse, od zasnove vesoljskega plovila do prenosa podatkov: tista sporočila, ki se vračajo na Zemljo kot enakomeren tok 0 in 1, bodo zagotovo vsebovala nekaj napak, zato jih morate znati prepoznati in popraviti, ne da bi pri tem izgubljali dragoceni čas in energijo.

Tu nastopi matematika. Matematiki so iznašli domiselne načine za prenos in shranjevanje informacij. Ena presenetljivo učinkovita metoda uporablja Reed-Solomonove kode, ki so zgrajene na isti osnovni algebri, ki se je učenci učijo v šoli. Pojdimo na tečaj matematike, da vidimo, kako kode Reed-Solomon pomagajo prenašati in varovati informacije, medtem ko popravljajo morebitne drage napake, ki se pojavijo.

Dva študenta, Art in Zeke, si izmenjujeta skrivna sporočila v razredu matematike gospe Al-Jabr. Art razgrne Zekejev najnovejši zapis, da razkrije števili 57 in 99. Ve, da mora priskrbeti x-koordinati 3 in 6 za ustvarjanje točk (3, 57) in (6, 99). Art vključi vsako točko v linearno enačbo y = Ax + B in ustvari naslednji sistem enačb:

57 = 3A + B

99 = 6A + B

Da bi dekodiral sporočilo, ga mora Art rešiti A in B. Začne z odštevanjem prve enačbe od druge:

To odpravlja B. Če obe strani te nove enačbe delimo s 3, Art to pove A = 14, in nato to nadomestimo nazaj v prvo enačbo, 57 = 3 × 14 + B, daje B = 15.

Art zdaj ve, da je premica, ki poteka skozi (3, 57) in (6, 99), opisana z enačbo y = 14x + 15. Ve pa tudi, da se v Reed-Solomonovi kodi skrivno sporočilo skriva v koeficientih. Dekodira Zekovo sporočilo z njihovo preprosto dogovorjeno abecedno šifro: 14 je »N« in 15 je »O«, kar Artu pove, da ne, Zeke danes po šoli ne more igrati videoiger.

Skrivnost te preproste Reed-Solomonove kode se začne z dvema osnovnima geometrijskima dejstvoma. Prvič, skozi katerikoli dve točki poteka edinstvena premica. Drugič, za koeficiente A in B, lahko vsako (nenavpično) vrstico zapišemo v obliki y = Ax + B. Ti dve dejstvi skupaj zagotavljata, da jih lahko najdete, če poznate dve točki na premici A in B, in če veš A in B, poznate vse točke na črti. Skratka, posedovanje katerega koli niza informacij je enakovredno poznavanju linije.

Reed-Solomonove kode izkoriščajo te enakovredne nize informacij. Skrivno sporočilo je kodirano kot koeficienti A in B, točke črte pa so razdeljene na dele, od katerih se nekateri prenašajo javno, nekateri pa ostanejo zasebni. Če želite dekodirati sporočilo, preprosto zberete koščke in jih sestavite nazaj. In vse, kar to zahteva, je preprosta algebra.

Zekejeva dela sta bili številki 57 in 99, ki ju je poslal Art. Te številke so javni del sporočila. Art jih je združil s svojimi deli, 3 in 6, da bi rekonstruiral točke (3, 57) in (6, 99). Tukaj 3 in 6 predstavljata zasebni del sporočila, o katerem sta se Art in Zeke predhodno dogovorila.

Dve točki ležita na premici in za dekodiranje sporočila morate samo najti enačbo te premice. Vključitev vsake točke v y = Ax + B vam poda sistem dveh enačb o premici, ki morata biti obe resnični. Zdaj je strategija preprosta: rešite sistem, določite vrstico in dekodirajte sporočilo.

Pri pouku algebre ste se verjetno naučili veliko metod reševanja sistemov enačb, kot so grafi, ugibanje in preverjanje ter substitucija. Art je uporabil eliminacijo, metodo, pri kateri algebraično manipulirate z enačbami, da izločite spremenljivke eno za drugo. Vsakič, ko odpravite spremenljivko, postane sistem nekoliko lažji za reševanje.

Tako kot pri drugih šifrirnih shemah je pametna kombinacija javnih in zasebnih informacij tista, ki varuje sporočila. Zeke bi lahko kričal svoji številki 57 in 99 po učilnici in to ne bi ogrozilo varnosti njegovega sporočila Artu (čeprav bi ga lahko spravilo v težave z gospo Al-Jabr). To je zato, ker brez ustreznih zasebnih podatkov — x-koordinati 3 in 6 — nemogoče je identificirati enačbo premice. Dokler te vrednote obdržijo zase, lahko svoja skrivna sporočila varno posredujejo javnosti.

Linija y = 14x + 15 je v redu za prenos besede z dvema črkama "ne", kaj pa, če študentje želijo deliti daljšo skrivnost? Tukaj pride do izraza vsa moč algebre, geometrije in sistemov linearnih enačb.

Denimo, da Zeke želi vedeti, kako Art misli, da bo opravil jutrišnji test iz angleščine. Art svoj odgovor s tremi črkami pretvori v številke 14, 59 in 82 in jih posreduje Zeku. Študentje so se predhodno dogovorili, da so pri uporabi Reed-Solomonovih kod dolžine 3 njihova zasebna števila 2, 5 in 6, zato Zeke sestavi koščke skupaj, da rekonstruira točke (2, 14), (5, 59) in (6, 82).

Ni linearne funkcije, ki bi šla skozi te tri točke. Toda obstaja edinstvena kvadratna funkcija, ki to počne. In ker lahko vsako kvadratno funkcijo zapišemo v obliki y = Ax² + Bx + C, se lahko uporabi ista splošna metoda. Edina razlika je velikost sistema.

Vključitev vsake točke v y = Ax² + Bx + C daje eno enačbo, tako da tri točke ustvarijo naslednji sistem treh enačb:

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

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

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

Rešitev sistema treh enačb s tremi neznankami zahteva malo več dela kot rešitev sistema dveh enačb z dvema neznankama, vendar je cilj enak: pametno združiti pare enačb, da izločiš spremenljivke.

Na primer, če prvo enačbo odštejete od druge, dobite novo enačbo 45 = 21A + 3B. Podobno, če drugo enačbo odštejete od tretje, dobite 23 = 11A + B. Te algebraične manipulacije ustvarijo nov sistem:

45 = 21A + 3B

23 = 11A + B

Zdaj imate sistem "dva za dva": dve enačbi z dvema neznankama. Če želite to rešiti, lahko drugo enačbo pomnožite z −3 in jo dodate prvi enačbi:

Opazite, kako je ponavljajoča se izločitev prvotni sistem treh enačb spremenila v eno samo enačbo, ki jo je mogoče zlahka rešiti: A = 2. Če delate nazaj, lahko priključite A = 2 v eno od enačb v sistemu dva za dva B = 1 in nato obe vrednosti vključite v eno od prvotnih enačb, da dobite C = 4. Po uporabi preproste abecedne šifre pri 2, 1 in 4 Zeke ve, da bo Art pri jutrišnjem testu angleščine dosegel "SLABO". Vsaj veliko vadi algebro.

Zahvaljujoč posebnemu dejstvu o polinomskih funkcijah lahko z uporabo Reed-Solomonovih kod prenesete sporočilo katere koli dolžine. Ključno je naslednje: Glede na vse n točke v ravnini z različnimi x-koordinate, obstaja edinstven polinom "stopnje" n − 1, ki gre skozi njih. Stopnja polinoma je največja potenca spremenljivke v izrazu, zato je kvadratna funkcija, kot je Ax² + Bx + C ima stopnjo 2, saj ima največjo moč x je 2. In linearna funkcija ima stopnjo 1, saj v enačbi y = Ax + B, največja moč x je 1.

V prvem primeru smo uporabili dejstvo, da dve točki določata edinstven linearni polinom ali stopnja 1. Pri drugem smo se zanašali na dejstvo, da tri točke določajo edinstven polinom stopnje 2 ali kvadratni polinom. In če želite poslati sporočilo dolžine 10, samo kodirajte sporočilo kot 10 koeficientov polinomske funkcije stopnje 9. Ko imate svojo funkcijo, izračunajte 10 javnosti y-vrednosti z vrednotenjem funkcije na predhodno dogovorjenih 10 zasebnih x-vrednote. Ko to storite, jih lahko varno prenesete y-javne koordinate, ki jih lahko vaš sprejemnik dekodira. V praksi so Reed-Solomonove kode nekoliko bolj zapletene od tega, saj uporabljajo bolj sofisticirane vrste koeficientov in prevodnih shem, vendar je temeljna ideja enaka.

Poleg tega, da ohranjajo vaše sporočilo varno, kode Reed-Solomon ponujajo tudi preproste in učinkovite načine za odkrivanje in celo odpravljanje napak. To je pomembno vsakič, ko se podatki prenašajo ali shranjujejo, saj vedno obstaja možnost, da se nekatere informacije izgubijo ali poškodujejo.

Ena od rešitev tega problema bi bila preprosto pošiljanje dodatnih kopij podatkov. Na primer, Zeke lahko namesto [14, 14] pošlje sporočilo [14, 15, 15, 15, 14, 15]. Dokler Art ve, da je vsak del sporočila poslan v trojniku, lahko dekodira sporočilo in preveri napake. Pravzaprav, če najde napake, ima dobre možnosti, da jih popravi. Če Art prejme [14, 14, 24, 15, 15, 15], ga dejstvo, da so prve tri številke različne, opozori na napako, in ker sta dve 14, lahko ugiba, da bi moralo biti 24 verjetno 14 tudi. Namesto da zahteva ponovno pošiljanje sporočila, lahko Art nadaljuje s svojim dekodiranjem. To je učinkovita, a draga strategija. Ne glede na čas, energijo in trud, ki so potrebni za pošiljanje n informacij, to zahteva trikrat toliko.

Toda matematika za kodami Reed-Solomon ponuja učinkovito alternativo. Namesto pošiljanja več kopij vsakega podatka lahko pošljete le eno dodatno točko! Če ta dodatna točka ustreza vašemu polinomu, potem je informacija pravilna. Če se ne, je prišlo do napake.

Če želite videti, kako to deluje, predpostavimo, da želite označiti sporočilo »NE« v prvem primeru. Zeke lahko samo pošlje dodatno y-koordinata 155. Ob predpostavki, da sta se z Artom dogovorila za tretje zasebno x- predhodno uskladiti, recimo x = 10, Art lahko to tretjo točko preveri glede na vrstico, ki jo je dekodiral. Ko zamaši x = 10 v y = 14x + 15 in vidi, da je rezultat 155, ve, da pri prenosu ni bilo napak.

To ne deluje samo za črte. Art lahko pošlje, da omogoči Zekeju, da preveri "BAD" v drugem primeru y = 25. Če so se dogovorili, da je 3 dodatno zasebno x-koordiniraj, Zeke se lahko priključi x = 3 v njegovo kvadratno funkcijo y = 2x² + x + 4 in preverite, ali točka (3, 25) ustreza, ponovno potrdite prenos brez napak s samo še eno točko.

In ta dodatna točka lahko potencialno popravi tudi napake. Če je zaznana napaka in prejemnik ne more sestaviti polinomske funkcije, ki vsebuje sporočilo, lahko namesto tega s pomočjo regresijskih tehnik sestavi »najprimernejši« polinom. Tako kot premica najboljšega prileganja v statističnem razredu je to polinomska funkcija, za katero je matematično določeno, da se najbolj prilega danim točkam, tudi če ne poteka skozi vse. Odvisno od strukture sporočila in količine dodatnih informacij, ki jih pošljete, vam lahko ta polinom, ki se najbolje prilega, pomaga rekonstruirati pravilen polinom – in s tem pravilno sporočilo – tudi iz poškodovanih informacij.

Ta učinkovitost pri prenosu in popravljanju komunikacij pojasnjuje, zakaj je NASA uporabljala kode Reed-Solomon na svojih misijah na Luno in Mars. In daje vam nekaj za premislek, ko rešujete naslednji sistem enačb. Ko ugibate, preverite ali odpravite svojo pot do rešitve, pomislite na moč in eleganco kod Reed-Solomon in vse skrivnosti, ki bi jih lahko razkril vaš sistem.

vaje

1. Z isto shemo, kot so jo uporabljali v razredu, Art objavi javni številki 33 in 57, da jih Zeke dekodira. Kaj je sporočilo?

2. Kako sta lahko Art in Zeke prepričana, da je sistem enačb, ki izhaja iz njunih zasebnih števil x = 3 in x = 6 bo vedno imel rešitev?

3. Kot odgovor na Artovo sporočilo “BAD” o testu angleščine Zeke pošlje nazaj [90, 387, 534]. Kakšno je njegovo sporočilo, če predpostavimo, da uporabljajo isto shemo kot v razredu?

4. Lola vam pošlje dvočrkovno sporočilo in eno številko za preverjanje napak z uporabo Reed-Solomonove kode in iste preproste abecedne šifre, kot jo uporabljata Art in Zeke. Na skrivaj ste se dogovorili za x-koordinira 1, 3 in 10 vnaprej, Lola pa posreduje javne številke [27, 43, 90]. Ali sporočilo vsebuje napako?