Az alapvető algebra a titkos kódok és az űrkommunikáció mögött

Az űrkutatás óriási precizitást igényel. Amikor leszáll egy roverrel a Marson, 70 millió mérföldre a legközelebbi töltőállomástól, maximalizálnia kell a hatékonyságot, és fel kell készülnie a váratlan eseményekre. Ez az űrhajók tervezésétől az adatátvitelig mindenre vonatkozik: Azok az üzenetek, amelyek 0-k és 1-ek folyamatos áramlásaként térnek vissza a Földre, bizonyosan tartalmaznak hibákat, ezért képesnek kell lenniük azonosítani és kijavítani azokat értékes idő és energia pazarlása nélkül.

Itt jön be a matematika. A matematikusok zseniális módszereket találtak ki az információk továbbítására és tárolására. Egy meglepően hatékony módszert használ Reed-Solomon kódok, amelyek ugyanarra az alapalgebrára épülnek, amelyet a diákok az iskolában tanulnak. Ugorjunk be egy matematikaórára, hogy megtudjuk, hogyan segítik a Reed-Solomon kódok az információk továbbítását és biztonságát, miközben kijavítják a felbukkanó költséges hibákat.

Két diák, Art és Zeke titkos üzeneteket váltanak Ms. Al-Jabr matematika óráján. Art kibontja Zeke legújabb jegyzetét, hogy felfedje az 57-es és 99-es számokat. Tudja, hogy meg kell adnia a x-a 3. és 6. koordináták a (3, 57) és (6, 99) pontok létrehozásához. A művészet minden pontot beilleszt a lineáris egyenletbe y = Ax + B és a következő egyenletrendszert állítja elő:

57 = 3A + B

99 = 6A + B

Az üzenet dekódolásához Artnak meg kell oldania A és a B. Úgy kezdi, hogy kivonja az első egyenletet a másodikból:

Ez kiküszöböli B. Ha ennek az új egyenletnek mindkét oldalát elosztjuk 3-mal, akkor az Art A = 14, majd ezt visszacserélve az első egyenletbe, 57 = 3 × 14 + B, ad B = 15.

A művészet ma már tudja, hogy a (3, 57) és (6, 99) pontokon átmenő egyenest az egyenlet írja le y = 14x + 15. De azt is tudja, hogy egy Reed-Solomon kódban a titkos üzenet az együtthatókban rejtőzik. Dekódolja Zeke üzenetét az egyszerű ábécé-rejtjelükkel: a 14 az „N”, a 15 pedig az „O”, ami azt mondja Artnak, hogy nem, Zeke ma nem tud videojátékokkal játszani iskola után.

Ennek az egyszerű Reed-Solomon kódnak a titka a geometria két alapvető tényével kezdődik. Először is, bármely két ponton keresztül van egy egyedi vonal. Másodszor, az együtthatók A és a B, minden (nem függőleges) sor beírható a formába y = Ax + B. Ez a két tény együttesen garantálja, hogy ha ismer két pontot egy egyenesen, akkor megtalálhatja A és a B, és ha tudja A és a B, ismeri a vonal összes pontját. Röviden, bármelyik információkészlet birtoklása egyenértékű a vonal ismeretével.

A Reed-Solomon kódok ezeket az egyenértékű információkészleteket használják fel. A titkos üzenet együtthatóként van kódolva A és a B, és a vonal pontjait darabokra bontják, amelyek egy részét nyilvánosan továbbítják, néhányat pedig privát módon. Az üzenet dekódolásához csak össze kell gyűjteni a darabokat, és össze kell rakni őket. És ehhez csak néhány egyszerű algebra kell.

Zeke darabjai az 57-es és 99-es számok voltak, amelyeket az Art.-nak küldött el. Ezek a számok az üzenet nyilvános részét képezik. A művészet ezeket a 3-as és 6-os darabjaival rakta össze, hogy rekonstruálja a (3, 57) és (6, 99) pontokat. Itt a 3 és a 6 jelentik az üzenet privát részét, amelyben Art és Zeke előzetesen megegyezett.

A két pont egy egyenesen fekszik, és az üzenet dekódolásához csak meg kell találnia a vonal egyenletét. Az egyes pontok csatlakoztatása y = Ax + B két egyenletrendszert ad az egyenesről, amelyeknek mindkettőnek igaznak kell lennie. Most a stratégia egyértelmű: oldja meg a rendszert, határozza meg a sort és dekódolja az üzenetet.

Az algebra órán valószínűleg számos módszert tanult meg az egyenletrendszerek megoldására, mint például a grafikonok ábrázolása, a találgatás és az ellenőrzés, valamint a helyettesítés. A művészet az eliminációt használta, egy olyan módszert, ahol algebrai módon manipulálják az egyenleteket, hogy egyenként eltávolítsák a változókat. Minden alkalommal, amikor kiiktat egy változót, a rendszer egy kicsit könnyebben megoldható.

Más titkosítási sémákhoz hasonlóan ez is a nyilvános és a privát adatok okos kombinációja biztosítja az üzenetek biztonságát. Zeke kiabálhatná az 57-es és 99-es számát az osztályteremben, és ez nem veszélyeztetné Artnak szóló üzenetének biztonságát (bár ezzel bajba kerülhet Ms. Al-Jabrral). Ennek az az oka, hogy a megfelelő személyes adatok nélkül – a x-3-as és 6-os koordináták — lehetetlen azonosítani az egyenes egyenletét. Amíg ezeket az értékeket megtartják maguknak, biztonságosan átadhatják titkos üzeneteiket a nyilvánosság előtt.

A vonal y = 14x A + 15 megfelelő a kétbetűs „nem” szó továbbítására, de mi van akkor, ha a diákok egy hosszabb titkot szeretnének megosztani? Itt jön képbe az algebra, a geometria és a lineáris egyenletrendszerek teljes ereje.

Tegyük fel, hogy Zeke tudni akarja, Art szerint hogyan fog teljesíteni a holnapi angol nyelvvizsgán. Art hárombetűs válaszát 14-re, 59-re és 82-re alakítja, és átadja Zeke-nek. A tanulók előzetesen megegyeztek abban, hogy a 3 hosszúságú Reed-Solomon kódok használatakor a privát számuk 2, 5 és 6, így Zeke összerakja a darabokat, hogy rekonstruálja a (2, 14), (5, 59) és (6, 82).

Nincs olyan lineáris függvény, amely áthaladna ezen a három ponton. De van egy egyedi kvadratikus függvény, amely igen. És mivel minden másodfokú függvény felírható a formába y = Ax² + Bx + C, ugyanaz az általános módszer alkalmazható. Az egyetlen különbség a rendszer mérete.

Az egyes pontok csatlakoztatása y = Ax² + Bx + C egy egyenletet ad, így a három pontból a következő három egyenletrendszer jön létre:

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

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

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

Egy három egyenletből álló rendszer három ismeretlennel valamivel több munkát igényel, mint egy két egyenletrendszer két ismeretlennel, de a cél ugyanaz: ügyesen kombinálja az egyenletpárokat a változók kiküszöbölésére.

Például, ha kivonja az első egyenletet a másodikból, akkor az új egyenletet kapja: 45 = 21A + 3B. Hasonlóképpen, ha kivonja a második egyenletet a harmadikból, akkor 23 = 11A + B. Ezek az algebrai manipulációk egy új rendszert hoznak létre:

45 = 21A + 3B

23 = 11A + B

Most van egy „kettő-kettő” rendszer: két egyenlet két ismeretlennel. A megoldáshoz megszorozhatja a második egyenletet -3-mal, és hozzáadhatja az első egyenlethez:

Figyeljük meg, hogy az ismételt elimináció hogyan változtatta az eredeti három egyenletrendszert egyetlen egyenletté, amely könnyen megoldható: A = 2. Visszafelé dolgozva bedughatod A = 2 a kettő-kettő rendszer egyenleteibe, hogy megtaláljuk B = 1, majd csatlakoztassa mindkét értéket az egyik eredeti egyenlethez, hogy megkapja C = 4. Miután az egyszerű ábécé-rejtjelet használta a 2-es, 1-es és 4-es számokon, Zeke tudja, hogy Art „ROSZT” fog teljesíteni a holnapi angol teszten. Legalább sokat gyakorol algebrát.

A polinomiális függvényekre vonatkozó különleges ténynek köszönhetően bármilyen hosszúságú üzenetet továbbíthat Reed-Solomon kódokkal. A kulcs a következő: Adott bármilyen n pontokat a síkban különböző x-koordináták, létezik egy egyedi „fok” polinom n − 1, amely áthalad rajtuk. A polinom foka egy változó legmagasabb hatványa a kifejezésben, tehát egy másodfokú függvény, mint pl Ax² + Bx + C fokozata 2, mivel a legmagasabb hatványa x 2. És egy lineáris függvénynek 1 foka van, mivel az egyenletben y = Ax + B, a legmagasabb ereje x az 1.

Az első példában azt a tényt használtuk, hogy két pont határoz meg egy egyedi lineáris vagy 1-es fokú polinomot. A másodikban arra a tényre támaszkodtunk, hogy három pont határoz meg egy egyedi 2-es fokos vagy másodfokú polinomot. Ha pedig 10-es hosszúságú üzenetet szeretne küldeni, csak kódolja az üzenetet egy 10-es fokos polinomfüggvény 9 együtthatójaként. Ha megvan a függvénye, számolja ki a 10 nyilvánosat y-értékek a függvény kiértékelésével a korábban egyeztetett 10 privát x-értékek. Ha ezt megtette, nyugodtan átadhatja azokat y-nyilvánosan koordinálja a vevőegység dekódolását. A gyakorlatban a Reed-Solomon kódok ennél valamivel bonyolultabbak, kifinomultabb együtthatókat és fordítási sémákat alkalmaznak, de az alapgondolat ugyanaz.

Az üzenet biztonságának megőrzése mellett a Reed-Solomon kódok egyszerű és hatékony módszereket is kínálnak a hibák észlelésére, sőt kijavítására is. Ez mindenkor fontos, amikor adatokat küldenek vagy tárolnak, mivel mindig fennáll annak a lehetősége, hogy az információk egy része elveszik vagy megsérül.

Az egyik megoldás erre a problémára az lenne, ha egyszerűen küldenénk extra másolatokat az adatokról. Például a Zeke elküldheti a [14, 14, 14, 15, 15, 15] üzenetet a [14, 15] helyett. Amíg Art tudja, hogy az üzenet minden részét három példányban küldik el, dekódolni tudja az üzenetet, és ellenőrizni tudja a hibákat. Valójában, ha hibát talál, jó eséllyel kijavítja azokat. Ha Art megkapja a [14, 14, 24, 15, 15, 15] értékeket, az a tény, hogy az első három szám különbözik, hibára figyelmezteti, és mivel ezek közül kettő 14, sejtheti, hogy a 24 valószínűleg egy 14 is. Ahelyett, hogy az üzenet újraküldését kérné, Art folytathatja a dekódolást. Ez egy hatékony, de költséges stratégia. Bármilyen időre, energiára és erőfeszítésre van szükség a küldéshez n információ, ehhez háromszor annyi kell.

De a Reed-Solomon kódok mögötti matematika hatékony alternatívát kínál. Ahelyett, hogy minden adatról több másolatot küldene, csak egy plusz pontot küldhet! Ha ez a további pont illeszkedik a polinomhoz, akkor az információ helyes. Ha nem, akkor hiba történt.

Ha látni szeretné, hogyan működik ez, tegyük fel, hogy ellenőrizni szeretné az első példában szereplő „NEM” üzenetet. Zeke csak küldheti a kiegészítőt y-155-ös koordináta. Feltéve, hogy ő és Art megállapodtak egy harmadik közlegényben x-koordinálja előre, mondjuk x = 10, Art ezt a harmadik pontot össze tudja hasonlítani az általa dekódolt sorral. Amikor bedugja x = 10 be y = 14x + 15, és látja, hogy az eredmény 155, tudja, hogy nem volt hiba az átvitelben.

Ez nem csak vonalakra vonatkozik. Ahhoz, hogy a Zeke a második példában ellenőrizhesse a „BAD”-t, az Art küldhet y = 25. Ha megegyeztek, hogy a 3 az extra privát x-koordináta, Zeke be tudja dugni x = 3 a másodfokú függvényébe y = 2x² + x + 4 és ellenőrizze, hogy a (3, 25) pont illeszkedik-e, ismét megerősítve a hibamentes átvitelt még egy ponttal.

És ez az extra pont potenciálisan javíthatja a hibákat is. Ha hibát észlel, és a vevő nem tudja megszerkeszteni az üzenetet tartalmazó polinomfüggvényt, ehelyett a „legjobban illeszkedő” polinomot megszerkesztheti regressziós technikák segítségével. A statisztikai osztályban a legjobban illeszkedő vonalhoz hasonlóan ez az a polinomfüggvény, amely matematikailag úgy van meghatározva, hogy a legjobban illeszkedjen az adott pontokhoz, még akkor is, ha nem megy át mindegyiken. Az üzenet szerkezetétől és az elküldött többletinformációtól függően ez a legjobban illeszkedő polinom segíthet a helyes polinom – és ezáltal a helyes üzenet – rekonstruálásában, még a sérült információkból is.

A kommunikáció továbbításának és javításának ez a hatékonysága megmagyarázza, hogy a NASA miért használt Reed-Solomon kódokat a Holdra és a Marsra irányuló küldetései során. És ez ad valami elgondolkodtatót, miközben megoldja a következő egyenletrendszerét. Ahogy találgatja, ellenőrizze vagy szüntesse meg a megoldáshoz vezető utat, gondoljon a Reed-Solomon kódok erejére és eleganciájára, valamint az összes titkra, amelyet a rendszer felfedhet.

Ünnepély

1. Ugyanazt a sémát használva, amelyet az órán használtak, Art közzéteszi a 33-as és 57-es nyilvános számokat Zeke számára, hogy dekódolja. Mi az üzenet?

2. Hogyan lehet biztos abban, hogy Art és Zeke a magánszámaikból eredő egyenletrendszer x = 3 és x = 6-nak mindig lesz megoldása?

3. Art „BAD” üzenetére válaszul az angol teszttel kapcsolatban Zeke visszaküldi [90, 387, 534]. Feltéve, hogy ugyanazt a sémát használják, mint az órán, mi az üzenete?

4. Lola küld neked egy kétbetűs üzenetet, plusz egy hibaellenőrző számot egy Reed-Solomon kóddal és ugyanazzal az egyszerű ábécé-rejtjellel, amelyet Art és Zeke használ. Titokban megállapodtál abban x- előre koordinálja az 1-et, 3-at és 10-et, Lola pedig továbbítja a nyilvános számokat [27, 43, 90]. Hibát tartalmaz az üzenet?