Den grundläggande algebra bakom hemliga koder och rymdkommunikation

Utforskning av rymden kräver enorm precision. När du landar en rover på Mars 70 miljoner miles från närmaste bensinstation måste du maximera effektiviteten och förbereda dig för det oväntade. Detta gäller allt från rymdskeppsdesign till dataöverföring: De meddelanden som återvänder till jorden som en stadig ström av 0:or och 1:or är skyldiga att innehålla vissa fel, så du måste kunna identifiera och korrigera dem utan att slösa dyrbar tid och energi.

Det är där matematik kommer in. Matematiker har uppfunnit geniala sätt att överföra och lagra information. En överraskande effektiv metod används Reed-Solomon-koder, som bygger på samma grundläggande algebra som eleverna lär sig i skolan. Låt oss gå in på en matematiklektion för att se hur Reed-Solomon-koder hjälper till att överföra och säkra information samtidigt som de korrigerar kostsamma fel som dyker upp.

Två elever, Art och Zeke, utbyter hemliga meddelanden i Al-Jabrs mattelektion. Art utvecklar Zekes senaste anteckning för att avslöja siffrorna 57 och 99. Han vet att han måste leverera x-koordinater 3 och 6 för att skapa punkterna (3, 57) och (6, 99). Art kopplar in varje punkt i den linjära ekvationen y = Ax + B och producerar följande ekvationssystem:

57 3 =A + B

99 6 =A + B

För att avkoda budskapet måste Art lösa A och B. Han börjar med att subtrahera den första ekvationen från den andra:

Detta eliminerar B. Att dividera båda sidorna av denna nya ekvation med 3 säger Art att A = 14, och sedan ersätta detta tillbaka i den första ekvationen, 57 = 3 × 14 + B, ger B = 15.

Konsten vet nu att linjen som går genom (3, 57) och (6, 99) beskrivs av ekvationen y = 14x + 15. Men han vet också att i en Reed-Solomon-kod döljer sig det hemliga meddelandet i koefficienterna. Han avkodar Zekes meddelande med hjälp av deras enkla överenskomna alfabetchiffer: 14 är "N" och 15 är "O", vilket säger till Art att, nej, Zeke kan inte spela tv-spel efter skolan idag.

Hemligheten med denna enkla Reed-Solomon-kod börjar med två grundläggande fakta om geometri. Först, genom två punkter finns det en unik linje. För det andra, för koefficienter A och B, varje (icke-vertikal) rad kan skrivas i formuläret y = Ax + B. Tillsammans garanterar dessa två fakta att om du känner till två punkter på en linje kan du hitta A och B, och om du vet A och B, du känner till alla punkter på linjen. Kort sagt, att ha endera uppsättningen av information är likvärdigt med att känna till linjen.

Reed-Solomon-koder utnyttjar dessa motsvarande uppsättningar av information. Det hemliga meddelandet kodas som koefficienterna A och B, och linjens punkter bryts upp i bitar, av vilka några sänds offentligt, och några av dem hålls privata. För att avkoda meddelandet samlar du bara ihop bitarna och sätter ihop dem igen. Och allt som detta kräver är någon enkel algebra.

Zekes pjäser var siffrorna 57 och 99, som han skickade till Art. Dessa nummer är den offentliga delen av meddelandet. Konst satte ihop dessa med sina egna verk, 3 och 6, för att rekonstruera punkterna (3, 57) och (6, 99). Här utgör 3:an och 6:an den privata delen av meddelandet, som Art och Zeke kommit överens om på förhand.

De två punkterna ligger på en linje, och för att avkoda meddelandet behöver du bara hitta den linjens ekvation. Ansluter varje punkt till y = Ax + B ger dig ett system med två ekvationer om linjen som båda måste vara sanna. Nu är strategin okomplicerad: Lös systemet, bestäm linjen och avkoda budskapet.

I algebrakursen lärde du dig förmodligen många metoder för att lösa ekvationssystem, som att rita grafer, gissa och kontrollera, och substitution. Art used elimination, en metod där man manipulerar ekvationerna algebraiskt för att eliminera variablerna en i taget. Varje gång du tar bort en variabel blir systemet lite lättare att lösa.

Som med andra krypteringsscheman är det den smarta kombinationen av offentlig och privat information som håller meddelanden säkra. Zeke kunde ropa sina nummer 57 och 99 över klassrummet och det skulle inte äventyra säkerheten för hans meddelande till Art (även om det kan få honom i trubbel med Al-Jabr). Det beror på att utan motsvarande privata information — x-koordinater 3 och 6 — det är omöjligt att identifiera linjens ekvation. Så länge de håller dessa värderingar för sig själva kan de säkert skicka sina hemliga meddelanden offentligt.

Linjen y = 14x + 15 är bra för att sända ordet "nej" på två bokstäver, men vad händer om eleverna vill dela med sig av en längre hemlighet? Det är här den fulla kraften hos algebra, geometri och linjära ekvationssystem kommer in i bilden.

Anta att Zeke vill veta hur Art tror att han kommer att klara sig på morgondagens engelska prov. Art konverterar sitt svar på tre bokstäver till siffrorna 14, 59 och 82 och skickar dem till Zeke. Eleverna var på förhand överens om att när man använder Reed-Solomon-koder med längd 3 är deras privata nummer 2, 5 och 6, så Zeke sätter ihop bitarna för att rekonstruera punkterna (2, 14), (5, 59) och (6, 82).

Nu finns det ingen linjär funktion som passerar genom dessa tre punkter. Men det finns en unik kvadratisk funktion som gör det. Och eftersom varje kvadratisk funktion kan skrivas i formen y = Ax² + Bx + C, kan samma allmänna metod tillämpas. Den enda skillnaden är storleken på systemet.

Ansluter varje punkt till y = Ax² + Bx + C ger en ekvation, så de tre punkterna ger följande system med tre ekvationer:

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

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

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

Ett system med tre ekvationer med tre okända kräver lite mer arbete att lösa än ett system med två ekvationer med två okända, men målet är detsamma: Kombinera på ett smart sätt ekvationspar för att eliminera variabler.

Om du till exempel subtraherar den första ekvationen från den andra får du den nya ekvationen 45 = 21A + 3B. På samma sätt, om du subtraherar den andra ekvationen från den tredje, får du 23 = 11A + B. Dessa algebraiska manipulationer producerar ett nytt system:

45 21 =A + 3B

23 11 =A + B

Nu har du ett "två-och-två"-system: två ekvationer med två okända. För att lösa det kan du multiplicera den andra ekvationen med −3 och lägga till den till den första ekvationen:

Lägg märke till hur upprepad eliminering har förvandlat det ursprungliga systemet med tre ekvationer till en enda ekvation som lätt kan lösas: A = 2. Arbetar du bakåt kan du plugga A = 2 i en av ekvationerna i två-till-två-systemet för att hitta B = 1, och koppla sedan in båda värdena till en av de ursprungliga ekvationerna för att få C = 4. Efter att ha använt det enkla alfabetchifferet på 2, 1 och 4, vet Zeke att Art kommer att göra "BAD" på morgondagens engelska prov. Åtminstone får han massor av algebraträning.

Tack vare ett speciellt faktum om polynomfunktioner kan du sända ett meddelande av valfri längd med hjälp av Reed-Solomon-koder. Nyckeln är detta: Givet någon n punkter i planet med olika x-koordinater finns det ett unikt polynom av "grad" n − 1 som passerar genom dem. Graden av ett polynom är den högsta potensen av en variabel i uttrycket, så en kvadratisk funktion som Ax² + Bx + C har grad 2, eftersom den högsta styrkan av x är 2. Och en linjär funktion har grad 1, eftersom i ekvationen y = Ax + B, den högsta kraften av x är 1.

I det första exemplet använde vi det faktum att två punkter bestämmer ett unikt linjärt, eller grad-1, polynom. I den andra förlitade vi oss på det faktum att tre punkter bestämmer ett unikt grad-2, eller kvadratiskt, polynom. Och om du vill skicka ett meddelande med längden 10, koda bara meddelandet som de 10 koefficienterna för en polynomfunktion på 9 grader. När du har din funktion, beräkna 10 publiken y-värden genom att utvärdera funktionen vid tidigare överenskomna 10 privata x-värden. När du gör det kan du säkert passera dem y-koordinater offentligt för din mottagare att avkoda. I praktiken är Reed-Solomon-koder lite mer komplexa än så, med mer sofistikerade typer av koefficienter och översättningsscheman, men den grundläggande idén är densamma.

Förutom att hålla ditt meddelande säkert, erbjuder Reed-Solomon-koder också enkla och effektiva sätt att fånga upp och till och med korrigera fel. Detta är viktigt när data överförs eller lagras, eftersom det alltid finns en chans att en del av informationen går förlorad eller skadas.

En lösning på detta problem skulle vara att helt enkelt skicka extra kopior av data. Till exempel kan Zeke skicka meddelandet [14, 14, 14, 15, 15, 15] istället för [14, 15]. Så länge Art vet att varje del av meddelandet skickas i tre exemplar kan han avkoda meddelandet och kontrollera om det finns fel. Faktum är att om han hittar några fel har han en god chans att rätta till dem. Om Art tar emot [14, 14, 24, 15, 15, 15], varnar det faktum att de tre första siffrorna är olika honom om ett fel, och eftersom två av dem är 14, kan han gissa att 24:an förmodligen borde vara en 14 likaså. Istället för att be om att budskapet ska sändas kan Art fortsätta med sin avkodning. Detta är en effektiv men kostsam strategi. Oavsett vilken tid, energi och ansträngning som krävs för att skicka n information kräver detta tre gånger så mycket.

Men matematiken bakom Reed-Solomon-koder erbjuder ett effektivt alternativ. Istället för att skicka flera kopior av varje del av data, kan du bara skicka en extra poäng! Om den ytterligare punkten passar ditt polynom är informationen korrekt. Om det inte gör det har det uppstått ett fel.

För att se hur detta fungerar, anta att du vill kontrollera meddelandet "NEJ" i det första exemplet. Zeke kan bara skicka tillägget y-koordinat 155. Förutsatt att han och Art kom överens om en tredje menig x-samordna i förväg, säg x = 10, Art kan kontrollera denna tredje punkt mot den linje han avkodade. När han pluggar x = 10 in y = 14x + 15 och ser att resultatet är 155, han vet att det inte fanns några fel i överföringen.

Detta fungerar inte bara för linjer. För att göra det möjligt för Zeke att markera "BAD" i det andra exemplet, kan Art skicka y = 25. Om de har kommit överens om att 3 är det extra privata x-koordinera, Zeke kan plugga x = 3 i sin kvadratiska funktion y = 2x² + x + 4 och verifiera att punkten (3, 25) passar, bekräftar återigen en felfri överföring med bara en punkt till.

Och den extra punkten kan potentiellt korrigera fel också. Om ett fel upptäcks och mottagaren inte kan konstruera polynomfunktionen som innehåller meddelandet, kan de istället konstruera det "bästa" polynomet med hjälp av regressionstekniker. Som en linje med bästa passform i statistikklassen är detta den polynomfunktion som matematiskt bestäms för att passa de givna punkterna närmast, även om den inte passerar genom alla. Beroende på meddelandets struktur och hur mycket extra information du skickar, kan detta polynom som bäst passar dig hjälpa dig att rekonstruera det korrekta polynomet – och därmed det korrekta meddelandet – även från korrupt information.

Denna effektivitet i att överföra och korrigera kommunikation förklarar varför NASA har använt Reed-Solomon-koder på sina uppdrag till månen och till Mars. Och det ger dig något att begrunda när du löser ditt nästa ekvationssystem. När du gissar, kontrollera eller eliminera din väg till lösningen, tänk på kraften och elegansen hos Reed-Solomon-koder och alla hemligheter som ditt system kan avslöja.

övningar

1. Genom att använda samma schema som de använde i klassen, lägger Art upp de offentliga numren 33 och 57 för Zeke att avkoda. Vad är budskapet?

2. Hur kan Art och Zeke vara säkra på att systemet av ekvationer som är resultatet av deras privata nummer x = 3 och x = 6 kommer alltid att ha en lösning?

3. Som svar på Arts meddelande om "BAD" om engelska testet, skickar Zeke tillbaka [90, 387, 534]. Förutsatt att de använder samma schema som de använde i klassen, vad är hans budskap?

4. Lola skickar ett meddelande på två bokstäver plus ett felkontrollnummer med hjälp av en Reed-Solomon-kod och samma enkla alfabetchiffer som används av Art och Zeke. Du har i hemlighet kommit överens om x-koordinater 1, 3 och 10 i förväg, och Lola sänder de allmänna numren [27, 43, 90]. Innehåller meddelandet ett fel?