Den grundlæggende algebra bag hemmelige koder og rumkommunikation

Udforskning af rummet kræver enorm præcision. Når du lander en rover på Mars 70 millioner miles væk fra den nærmeste tankstation, skal du maksimere effektiviteten og forberede dig på det uventede. Dette gælder alt fra rumfartøjsdesign til datatransmission: De meddelelser, der vender tilbage til Jorden som en lind strøm af 0'ere og 1'ere, er bundet til at indeholde nogle fejl, så du skal være i stand til at identificere og rette dem uden at spilde kostbar tid og energi.

Det er her matematik kommer ind i billedet. Matematikere har opfundet geniale måder at overføre og gemme information på. En overraskende effektiv metode bruger Reed-Solomon koder, som er bygget på den samme grundlæggende algebra, som eleverne lærer i skolen. Lad os kigge ind på en matematiktime for at se, hvordan Reed-Solomon-koder hjælper med at overføre og sikre informationer, mens de retter eventuelle dyre fejl, der dukker op.

To elever, Art og Zeke, udveksler hemmelige beskeder i Ms. Al-Jabrs matematiktime. Kunst udfolder Zekes seneste seddel for at afsløre tallene 57 og 99. Han ved, at han skal levere x-koordinaterne 3 og 6 for at skabe punkterne (3, 57) og (6, 99). Kunst sætter hvert punkt ind i den lineære ligning y = Ax + B og producerer følgende ligningssystem:

57 = 3A + B

99 = 6A + B

For at afkode budskabet, skal Kunsten løse for A , B. Han starter med at trække den første ligning fra den anden:

Dette eliminerer B. At dividere begge sider af denne nye ligning med 3 fortæller Art det A = 14, og derefter erstatte dette tilbage i den første ligning, 57 = 3 × 14 + B, giver B = 15.

Kunsten ved nu, at linjen, der går gennem (3, 57) og (6, 99), er beskrevet af ligningen y = 14x + 15. Men han ved også, at i en Reed-Solomon-kode gemmer den hemmelige besked sig i koefficienterne. Han afkoder Zekes besked ved hjælp af deres simple aftalte alfabetkryptering: 14 er "N" og 15 er "O", hvilket fortæller Art, at nej, Zeke kan ikke spille videospil efter skole i dag.

Hemmeligheden bag denne simple Reed-Solomon-kode starter med to grundlæggende fakta om geometri. For det første er der gennem to punkter en unik linje. For det andet for koefficienter A , B, hver (ikke-lodret) linje kan skrives i formen y = Ax + B. Tilsammen garanterer disse to fakta, at hvis du kender to punkter på en linje, kan du finde A , B, og hvis du ved det A , B, du kender alle punkterne på linjen. Kort sagt, at besidde begge sæt informationer svarer til at kende linjen.

Reed-Solomon-koder udnytter disse tilsvarende sæt informationer. Den hemmelige besked er kodet som koefficienterne A , B, og linjens punkter er opdelt i stykker, hvoraf nogle sendes offentligt, og nogle holdes private. For at afkode beskeden samler du bare brikkerne og sætter dem sammen igen. Og alt hvad dette kræver er en simpel algebra.

Zekes brikker var tallene 57 og 99, som han sendte til Art. Disse numre er den offentlige del af beskeden. Kunst satte dem sammen med sine egne stykker, 3 og 6, for at rekonstruere punkterne (3, 57) og (6, 99). Her udgør 3'eren og 6'eren den private del af beskeden, som Art og Zeke var enige om på forhånd.

De to punkter ligger på en linje, og for at afkode beskeden skal du blot finde den linjes ligning. Sæt hvert punkt i y = Ax + B giver dig et system af to ligninger om linjen, der begge skal være sande. Nu er strategien ligetil: Løs systemet, bestem linjen og afkode budskabet.

I algebraklassen lærte du sikkert mange metoder til at løse ligningssystemer, såsom at tegne grafer, gætte og tjekke og substituere. Art used elimination, en metode hvor man manipulerer ligningerne algebraisk for at eliminere variablerne én ad gangen. Hver gang du eliminerer en variabel, bliver systemet lidt nemmere at løse.

Som med andre krypteringssystemer er det den smarte kombination af offentlige og private oplysninger, der holder beskeder sikre. Zeke kunne råbe sine numre 57 og 99 ud over klasseværelset, og det ville ikke bringe sikkerheden i hans besked til Art i fare (selvom det kunne få ham i problemer med Ms. Al-Jabr). Det er fordi uden de tilsvarende private oplysninger - den x-koordinater 3 og 6 — det er umuligt at identificere linjens ligning. Så længe de holder disse værdier for sig selv, kan de trygt videregive deres hemmelige budskaber offentligt.

Linjen y = 14x + 15 er fint til at overføre ordet "nej" på to bogstaver, men hvad nu hvis eleverne vil dele en længere hemmelighed? Det er her den fulde kraft af algebra, geometri og systemer af lineære ligninger kommer i spil.

Antag, at Zeke vil vide, hvordan Art tror, ​​han vil klare sig på morgendagens engelskprøve. Art konverterer sit svar på tre bogstaver til tallene 14, 59 og 82 og giver dem videre til Zeke. Eleverne var på forhånd enige om, at når de bruger Reed-Solomon-koder af længde 3, er deres private tal 2, 5 og 6, så Zeke sætter brikkerne sammen for at rekonstruere punkterne (2, 14), (5, 59) og (6, 82).

Nu er der ingen lineær funktion, der passerer gennem disse tre punkter. Men der er en unik kvadratisk funktion, der gør. Og da hver andengradsfunktion kan skrives i formen y = Ax² + Bx + C, kan den samme generelle metode anvendes. Den eneste forskel er størrelsen af ​​systemet.

Sæt hvert punkt i y = Ax² + Bx + C giver én ligning, så de tre punkter producerer følgende system af tre ligninger:

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

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

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

Et system med tre ligninger med tre ubekendte kræver lidt mere arbejde at løse end et system med to ligninger med to ubekendte, men målet er det samme: Kombiner ligningspar på smart måde for at eliminere variable.

For eksempel, hvis du trækker den første ligning fra den anden, får du den nye ligning 45 = 21A + 3B. Ligeledes, hvis du trækker den anden ligning fra den tredje, får du 23 = 11A + B. Disse algebraiske manipulationer producerer et nyt system:

45 = 21A + 3B

23 = 11A + B

Nu har du et "to-til-to"-system: to ligninger med to ukendte. For at løse det kan du gange den anden ligning med −3 og lægge den til den første ligning:

Læg mærke til, hvordan gentagen eliminering har forvandlet det oprindelige system med tre ligninger til en enkelt ligning, der let kan løses: A = 2. Arbejder baglæns, kan du tilslutte A = 2 i en af ​​ligningerne i to-til-to-systemet for at finde B = 1, og sæt derefter begge værdier ind i en af ​​de oprindelige ligninger for at få C = 4. Efter at have brugt den simple alfabet-chiffer på 2, 1 og 4, ved Zeke, at Art kommer til at gøre "BAD" på morgendagens engelskprøve. Han får i det mindste masser af algebraøvelse.

Takket være en særlig kendsgerning om polynomielle funktioner, kan du sende en besked af enhver længde ved hjælp af Reed-Solomon-koder. Nøglen er dette: Givet nogen n punkter i flyet med forskellige x-koordinater, er der et unikt polynomium af "grad" n − 1, der passerer gennem dem. Graden af ​​et polynomium er den højeste potens af en variabel i udtrykket, så en andengradsfunktion som Ax² + Bx + C har grad 2, da den højeste magt af x er 2. Og en lineær funktion har grad 1, da i ligningen y = Ax + B, den højeste magt af x er 1.

I det første eksempel brugte vi det faktum, at to punkter bestemmer et unikt lineært, eller grad-1, polynomium. I den anden stolede vi på det faktum, at tre punkter bestemmer et unikt grad-2 eller kvadratisk polynomium. Og hvis du vil sende en besked med længden 10, skal du blot kode beskeden som de 10 koefficienter for en polynomisk funktion på 9 grader. Når du har din funktion, skal du beregne de 10 offentlige y-værdier ved at evaluere funktionen på den tidligere aftalte 10 menige x-værdier. Når du har gjort det, kan du trygt passere dem y-koordinater offentligt for din modtager at afkode. I praksis er Reed-Solomon-koder en smule mere komplekse end dette, idet de bruger mere sofistikerede former for koefficienter og oversættelsesskemaer, men den grundlæggende idé er den samme.

Udover at holde din besked sikker, tilbyder Reed-Solomon-koder også enkle og effektive måder at fange og endda rette fejl. Dette er vigtigt, når som helst data overføres eller gemmes, da der altid er en chance for, at nogle af oplysningerne går tabt eller beskadiges.

En løsning på dette problem ville være blot at sende ekstra kopier af dataene. For eksempel kan Zeke sende beskeden [14, 14, 14, 15, 15, 15] i stedet for [14, 15]. Så længe Art ved, at hver del af beskeden sendes i tre eksemplarer, kan han afkode beskeden og tjekke for fejl. Faktisk, hvis han finder fejl, har han en god chance for at rette dem. Hvis Art modtager [14, 14, 24, 15, 15, 15], advarer det faktum, at de første tre tal er forskellige, ham om en fejl, og da to af dem er 14, kan han gætte, at 24'eren nok skulle være en 14 også. I stedet for at bede om, at budskabet bliver forarget, kan Art fortsætte med sin afkodning. Dette er en effektiv, men dyr strategi. Uanset hvilken tid, energi og indsats der kræves for at sende n oplysninger, kræver dette tre gange så meget.

Men matematikken bag Reed-Solomon-koder tilbyder et effektivt alternativ. I stedet for at sende flere kopier af hvert stykke data, kan du bare sende et ekstra point! Hvis det ekstra punkt passer til dit polynomium, så er informationen korrekt. Hvis det ikke gør det, er der sket en fejl.

For at se, hvordan dette fungerer, antag, at du vil kontrollere meddelelsen "NEJ" i det første eksempel. Zeke kan bare sende det ekstra y-koordinat 155. Forudsat at han og Art blev enige om en tredje menig x-koordinere på forhånd, siger x = 10, Art kan kontrollere dette tredje punkt mod den linje, han afkodede. Når han plugger x = 10 ind y = 14x + 15 og ser, at resultatet er 155, han ved, at der ikke var nogen fejl i transmissionen.

Dette virker ikke kun for linjer. For at gøre det muligt for Zeke at markere "BAD" i det andet eksempel, kan Art sende y = 25. Hvis de har aftalt, at 3 er den ekstra private x-koordinat, Zeke kan tilslutte x = 3 i sin andengradsfunktion y = 2x² + x + 4 og kontroller, at punktet (3, 25) passer, hvilket igen bekræfter en fejlfri transmission med kun et punkt mere.

Og det ekstra punkt kan potentielt også rette fejl. Hvis der opdages en fejl, og modtageren ikke kan konstruere den polynomiefunktion, der indeholder beskeden, kan de i stedet konstruere det "bedst passende" polynomium ved hjælp af regressionsteknikker. Som en linje med bedste tilpasning i statistikklassen, er dette den polynomiefunktion, der er matematisk bestemt til at passe tættest til de givne punkter, selvom den ikke passerer gennem dem alle. Afhængigt af meddelelsens struktur og hvor meget ekstra information du sender, kan dette bedst egnede polynomium hjælpe dig med at rekonstruere det korrekte polynomium - og dermed den korrekte meddelelse - selv fra korrupte oplysninger.

Denne effektivitet i transmission og korrektion af kommunikation forklarer, hvorfor NASA har brugt Reed-Solomon-koder på sine missioner til månen og til Mars. Og det giver dig noget at overveje, mens du løser dit næste ligningssystem. Mens du gætter, tjek eller eliminer din vej til løsningen, tænk på kraften og elegancen ved Reed-Solomon-koder og alle de hemmeligheder, dit system kan afsløre.

Øvelser

1. Ved at bruge det samme skema, som de brugte i klassen, poster Art de offentlige numre 33 og 57, som Zeke kan afkode. Hvad er budskabet?

2. Hvordan kan Art og Zeke være sikre på, at det system af ligninger, der er resultatet af deres private tal x = 3 og x = 6 vil altid have en løsning?

3. Som svar på Arts besked om "DÅRLIG" om den engelske test, sender Zeke tilbage [90, 387, 534]. Hvis vi antager, at de bruger det samme skema, som de brugte i klassen, hvad er hans budskab?

4. Lola sender dig en besked på to bogstaver plus et fejlkontrolnummer ved hjælp af en Reed-Solomon-kode og den samme enkle alfabetkryptering, som Art og Zeke bruger. Du er i al hemmelighed blevet enige om x-koordinater 1, 3 og 10 på forhånd, og Lola sender de offentlige numre [27, 43, 90]. Indeholder meddelelsen en fejl?