De basisalgebra achter geheime codes en ruimtecommunicatie

Ruimteverkenning vereist enorme precisie. Wanneer je een rover op Mars laat landen op 70 miljoen mijl afstand van het dichtstbijzijnde tankstation, moet je de efficiëntie maximaliseren en je voorbereiden op het onverwachte. Dit geldt voor alles, van het ontwerp van ruimtevaartuigen tot gegevensoverdracht: die berichten die als een gestage stroom van nullen en enen naar de aarde terugkeren, zullen ongetwijfeld enkele fouten bevatten, dus je moet ze kunnen identificeren en corrigeren zonder kostbare tijd en energie te verspillen.

Dat is waar wiskunde om de hoek komt kijken. Wiskundigen hebben ingenieuze manieren bedacht om informatie over te dragen en op te slaan. Een verrassend effectieve methode gebruikt Reed-Solomon-codes, die zijn gebaseerd op dezelfde basisalgebra die studenten op school leren. Laten we eens een wiskundeles volgen om te zien hoe Reed-Solomon-codes helpen bij het verzenden en beveiligen van informatie en het corrigeren van eventuele kostbare fouten die opduiken.

Twee studenten, Art en Zeke, wisselen geheime berichten uit in de wiskundeles van mevrouw Al-Jabr. Art ontvouwt Zeke's laatste briefje om de nummers 57 en 99 te onthullen. Hij weet dat hij de x-coördinaten 3 en 6 om de punten (3, 57) en (6, 99) te creëren. Art plugt elk punt in de lineaire vergelijking y = Ax + B en produceert het volgende stelsel vergelijkingen:

57 = 3A + B

99 = 6A + B

Om de boodschap te ontcijferen, moet Art oplossen A en B. Hij begint met het aftrekken van de eerste vergelijking van de tweede:

Dit elimineert B. Door beide zijden van deze nieuwe vergelijking door 3 te delen, weet Art dat A = 14, en dit vervolgens weer in de eerste vergelijking substitueren, 57 = 3 × 14 + B, geeft B = 15.

De kunst weet nu dat de lijn die door (3, 57) en (6, 99) gaat, wordt beschreven door de vergelijking y = 14x + 15. Maar hij weet ook dat in een Reed-Solomon-code de geheime boodschap verborgen zit in de coëfficiënten. Hij decodeert Zeke's bericht met behulp van hun eenvoudige overeengekomen alfabetische cijfer: 14 is "N" en 15 is "O", wat Art vertelt dat Zeke vandaag na school geen videogames kan spelen.

Het geheim van deze eenvoudige Reed-Solomon-code begint met twee basisfeiten van geometrie. Ten eerste loopt er door twee willekeurige punten een unieke lijn. Ten tweede, voor coëfficiënten A en B, kan elke (niet-verticale) regel in het formulier worden geschreven y = Ax + B. Samen garanderen deze twee feiten dat als je twee punten op een lijn kent, je ze kunt vinden A en B, en als je het weet A en B, je kent alle punten op de lijn. Kortom, het bezit van een van beide soorten informatie staat gelijk aan het kennen van de lijn.

Reed-Solomon-codes maken gebruik van deze equivalente informatiesets. Het geheime bericht is gecodeerd als de coëfficiënten A en B, en de punten van de lijn worden opgedeeld in stukken, waarvan sommige openbaar worden uitgezonden en andere privé worden gehouden. Om de boodschap te ontcijferen, verzamel je gewoon de stukjes en zet je ze weer in elkaar. En alles wat hiervoor nodig is, is wat eenvoudige algebra.

Zeke's stukken waren de nummers 57 en 99, die hij naar Art stuurde. Deze nummers zijn het openbare deel van het bericht. Art voegde die samen met zijn eigen stukken, 3 en 6, om de punten (3, 57) en (6, 99) te reconstrueren. Hier vormen de 3 en de 6 het besloten deel van het bericht, waarover Art en Zeke het vooraf eens waren.

De twee punten liggen op een lijn, en om het bericht te decoderen, hoef je alleen maar de vergelijking van die lijn te vinden. Elk punt inpluggen y = Ax + B geeft je een stelsel van twee vergelijkingen over de lijn die beide waar moeten zijn. Nu is de strategie duidelijk: los het systeem op, bepaal de regel en decodeer het bericht.

In de algebrales heb je waarschijnlijk veel methoden geleerd om stelsels van vergelijkingen op te lossen, zoals grafieken maken, raden en controleren, en substitueren. Art gebruikte eliminatie, een methode waarbij je de vergelijkingen algebraïsch manipuleert om de variabelen één voor één te elimineren. Elke keer dat u een variabele elimineert, wordt het systeem iets gemakkelijker op te lossen.

Net als bij andere coderingsschema's, is het de slimme combinatie van openbare en privé-informatie die berichten veilig houdt. Zeke zou zijn nummers 57 en 99 door het klaslokaal kunnen schreeuwen zonder de veiligheid van zijn bericht aan Art in gevaar te brengen (hoewel hij hierdoor in de problemen zou kunnen komen met mevrouw Al-Jabr). Dat komt omdat zonder de bijbehorende privé-informatie - de x-coördinaten 3 en 6 — het is onmogelijk om de vergelijking van de lijn te identificeren. Zolang ze die waarden voor zichzelf houden, kunnen ze hun geheime berichten veilig in het openbaar doorgeven.

De lijn y = 14x + 15 is prima voor het overbrengen van het tweeletterige woord 'nee', maar wat als de leerlingen een langer geheim willen delen? Hier komt de volledige kracht van algebra, meetkunde en stelsels van lineaire vergelijkingen om de hoek kijken.

Stel dat Zeke wil weten hoe Art denkt dat hij het morgen zal doen bij de toets Engels. Art zet zijn antwoord van drie letters om in de cijfers 14, 59 en 82 en geeft die door aan Zeke. De leerlingen waren het er van tevoren over eens dat wanneer ze Reed-Solomon-codes met een lengte van 3 gebruiken, hun privénummers 2, 5 en 6 zijn, dus legt Zeke de stukjes bij elkaar om de punten (2, 14), (5, 59) en (6, 82).

Nu is er geen lineaire functie die door deze drie punten gaat. Maar er is een unieke kwadratische functie die dat wel doet. En aangezien elke kwadratische functie in de vorm kan worden geschreven y = Ax² + Bx + Ckan dezelfde algemene methode worden toegepast. Het enige verschil is de grootte van het systeem.

Elk punt inpluggen y = Ax² + Bx + C levert één vergelijking op, dus de drie punten produceren het volgende stelsel van drie vergelijkingen:

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

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

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

Een stelsel van drie vergelijkingen met drie onbekenden vereist iets meer werk om op te lossen dan een stelsel van twee vergelijkingen met twee onbekenden, maar het doel is hetzelfde: combineer op een slimme manier paren vergelijkingen om variabelen te elimineren.

Als u bijvoorbeeld de eerste vergelijking aftrekt van de tweede, krijgt u de nieuwe vergelijking 45 = 21A + 3B. Evenzo, als je de tweede vergelijking aftrekt van de derde, krijg je 23 = 11A + B. Deze algebraïsche manipulaties produceren een nieuw systeem:

45 = 21A + 3B

23 = 11A + B

Nu heb je een "twee-bij-twee" systeem: twee vergelijkingen met twee onbekenden. Om het op te lossen, kun je de tweede vergelijking vermenigvuldigen met −3 en optellen bij de eerste vergelijking:

Merk op hoe herhaalde eliminatie het oorspronkelijke systeem van drie vergelijkingen heeft veranderd in een enkele vergelijking die gemakkelijk kan worden opgelost: A = 2. Achterwaarts werkend, kunt u pluggen A = 2 in een van de vergelijkingen in het twee-bij-twee stelsel zoeken B = 1, en plug vervolgens beide waarden in een van de originele vergelijkingen om te krijgen C = 4. Na het eenvoudige alfabetische cijfer op 2, 1 en 4 te hebben gebruikt, weet Zeke dat Art "SLECHT" gaat doen op de Engelse test van morgen. Hij oefent tenminste veel algebra.

Dankzij een speciaal feit over polynoomfuncties, kunt u een bericht van elke lengte verzenden met behulp van Reed-Solomon-codes. De sleutel is dit: elke gegeven n punten in het vlak met verschillende x-coördinaten, is er een uniek polynoom van "graad" n − 1 die er doorheen gaat. De graad van een polynoom is de hoogste macht van een variabele in de uitdrukking, dus een kwadratische functie zoals Ax² + Bx + C heeft graad 2, aangezien de hoogste macht van x is 2. En een lineaire functie heeft graad 1, aangezien in de vergelijking y = Ax + B, de hoogste macht van x is 1.

In het eerste voorbeeld gebruikten we het feit dat twee punten een uniek lineair of graad-1 polynoom bepalen. In de tweede vertrouwden we op het feit dat drie punten een uniek graad-2, of kwadratisch, polynoom bepalen. En als je een bericht van lengte 10 wilt verzenden, codeer het bericht dan als de 10 coëfficiënten van een graad-9 polynoomfunctie. Zodra je je functie hebt, bereken je de 10 public y-waarden door de functie te evalueren op de eerder afgesproken 10 privé x-waarden. Als je dat eenmaal hebt gedaan, kun je die veilig passeren y-coördinaten in het openbaar zodat uw ontvanger ze kan decoderen. In de praktijk zijn Reed-Solomon-codes iets complexer dan dit, ze gebruiken meer geavanceerde soorten coëfficiënten en vertaalschema's, maar het fundamentele idee is hetzelfde.

Naast het veilig houden van uw bericht, bieden Reed-Solomon-codes ook eenvoudige en efficiënte manieren om fouten op te sporen en zelfs te corrigeren. Dit is belangrijk wanneer er gegevens worden verzonden of opgeslagen, omdat er altijd een kans bestaat dat een deel van de informatie verloren gaat of beschadigd raakt.

Een oplossing voor dit probleem zou zijn om gewoon extra kopieën van de gegevens te sturen. Zeke kan bijvoorbeeld het bericht [14, 14, 14, 15, 15, 15] verzenden in plaats van [14, 15]. Zolang Art weet dat elk deel van het bericht in drievoud wordt verzonden, kan hij het bericht decoderen en controleren op fouten. Als hij fouten vindt, heeft hij zelfs een goede kans om ze te corrigeren. Als Art [14, 14, 24, 15, 15, 15] ontvangt, waarschuwt het feit dat de eerste drie nummers verschillend zijn hem voor een fout, en aangezien twee ervan 14 zijn, kan hij raden dat de 24 waarschijnlijk een 14 ook. In plaats van te vragen om het bericht opnieuw te verzenden, kan Art doorgaan met zijn decodering. Dit is een effectieve maar kostbare strategie. Welke tijd, energie en moeite er ook voor nodig is om te verzenden n stukjes informatie, daar is drie keer zoveel voor nodig.

Maar de wiskunde achter Reed-Solomon-codes biedt een efficiënt alternatief. In plaats van meerdere exemplaren van elk stuk gegevens te verzenden, kunt u gewoon één extra punt verzenden! Als dat extra punt past bij uw polynoom, dan is de informatie correct. Als dit niet het geval is, is er een fout opgetreden.

Om te zien hoe dit werkt, stel dat u het bericht "NEE" in het eerste voorbeeld wilt controleren. Zeke kan gewoon de extra sturen y-coördinaat 155. Ervan uitgaande dat hij en Art het eens waren over een derde soldaat x-vooraf coördineren, zeg maar x = 10, kan Art dit derde punt vergelijken met de lijn die hij heeft gedecodeerd. Als hij aansluit x = 10 in y = 14x + 15 en ziet dat het resultaat 155 is, weet hij dat er geen fouten in de verzending waren.

Dit werkt niet alleen voor lijnen. Om Zeke in staat te stellen "SLECHT" aan te vinken in het tweede voorbeeld, kan Art verzenden y = 25. Als ze hebben afgesproken dat 3 de extra private is x-coördinaat, Zeke kan pluggen x = 3 in zijn kwadratische functie y = 2x² + x + 4 en controleer of het punt (3, 25) past, nogmaals een foutloze verzending bevestigen met slechts één punt meer.

En dat extra punt kan mogelijk ook fouten corrigeren. Als er een fout wordt gedetecteerd en de ontvanger de polynoomfunctie die het bericht bevat niet kan construeren, kan hij in plaats daarvan de "best passende" polynoom construeren met behulp van regressietechnieken. Net als een best passende lijn in de statistiekklasse, is dit de polynoomfunctie waarvan wiskundig is bepaald dat deze het dichtst bij de gegeven punten past, zelfs als deze niet door alle punten gaat. Afhankelijk van de structuur van het bericht en hoeveel extra informatie u verzendt, kan deze best passende polynoom u helpen de juiste polynoom – en dus het juiste bericht – te reconstrueren, zelfs op basis van corrupte informatie.

Deze efficiëntie bij het verzenden en corrigeren van communicatie verklaart waarom NASA Reed-Solomon-codes heeft gebruikt tijdens haar missies naar de maan en naar Mars. En het geeft je iets om over na te denken terwijl je je volgende stelsel vergelijkingen oplost. Zoals u raadt, controleert of elimineert u uw weg naar de oplossing, denk aan de kracht en elegantie van Reed-Solomon-codes en alle geheimen die uw systeem zou kunnen onthullen.

Oefeningen

1. Met hetzelfde schema dat ze in de klas gebruikten, plaatst Art de openbare nummers 33 en 57 zodat Zeke ze kan decoderen. Wat is de boodschap?

2. Hoe kunnen Art en Zeke er zeker van zijn dat het systeem van vergelijkingen dat voortvloeit uit hun privénummers x = 3 en x = 6 zal altijd een oplossing hebben?

3. In antwoord op Art's bericht van “SLECHT” over de Engelse test, stuurt Zeke [90, 387, 534] terug. Ervan uitgaande dat ze hetzelfde schema gebruiken als in de klas, wat is dan zijn boodschap?

4. Lola stuurt je een bericht van twee letters plus een foutcontrolenummer met behulp van een Reed-Solomon-code en hetzelfde eenvoudige alfabetische cijfer dat wordt gebruikt door Art en Zeke. Je hebt in het geheim afgesproken over de x-coördinaten 1, 3 en 10 vooraf, en Lola zendt de openbare nummers uit [27, 43, 90]. Bevat het bericht een fout?