Bevezetés
Minden ezredmásodpercben billiószámra cikáznak az üzenetek a Föld és a szomszédos galaxisok között.
De az ilyen hatalmas távolságokon át történő átvitel nem egyszerű.
Az idegesítő napkitörések, az időbeli torzulások, a kóbor erők, sőt egy űrpillangó szárnyának a rebbenése is okozhatja, hogy az átvitel során egy véletlenszerű bit megváltozik.
Most pedig képzeld el a következményeket:
- Összeomlik a Csillagközi Tőzsde, amikor a „buy low”-ból „sell now” lesz.
- Elveszítjük a kapcsolatot a Kepler Whirl rendszerrel, amikor a „save new worm hole”-ból „cave new worm hole” lesz.
- Vagy az egész univerzumot egzisztenciális borzalomba taszítja, amikor egy cowboy emoji 🤠 helyére bohóc emoji 🤡 kerül.
A sérült üzenetek felismerése nem csupán fontos, hanem létfontosságú.
A vevőnek mindenképpen tudnia kell, ha valami hiba történt, még mielőtt a katasztrófa bekövetkezik.
De hogyan?
A világegyetem minden tájáról érkező tudósok és mérnökök évmilliók óta küzdenek ezzel a problémával.
Egész kozmikus AI-szuperklaszterek dolgozzák át az adatokat.
És aztán egy napon újra felbukkan egy legenda: egy ősi, hatalmas erejű módszer, amelyről debug fórumokon suttognak, és amit olyan mérnökök motyognak maguk elé, akik már túl sokat láttak...
A paritásbit!
Egy módszer, amely olyan egyszerű, olyan hatalmas erejű, hogy akár meg is mentheti a csillagközi kommunikációt.
Utasítások
A feladatod, hogy segíts megvalósítani
- az adót, amely kiszámítja az átviteli sorozatot, és
- a vevőt, amely dekódolja azt.
A paritásbit az átviteli hibák felismerésének egyszerű módja.
Az adók és a vevők egyszerre pontosan nyolc bitet tudnak adni és fogadni (a paritásbitet is beleértve).
A paritásbitet úgy állítják be, hogy minden átvitelben páros számú 1-es bit legyen, és a paritásbit mindig a jobbról az első bit.
Tehát ha a vevő olyat kap, mint 11000001, 01110101 vagy 01000000 (vagyis egy olyan átvitelt, amelyben páratlan számú 1-es bit van), tudja, hogy hiba történt.
Az üzenetek azonban ritkán ilyen rövidek, a hosszabbakat pedig sorozatban kell átvinni.
Vegyük például a 11000000 00000001 11000000 11011110 üzenetet (hexben C0 01 C0 DE).
Mivel minden átvitel pontosan nyolc bitből áll, abban csak hét bit adat és a paritásbit fér el.
Ezért minden hét bit adat után be kell szúrni egy paritásbitet:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
Az üzenet átviteli sorozata így néz ki:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
A sorozat első átvitelében az adat (1100000) két 1-es bitet tartalmaz (páros szám), ezért a paritásbit 0.
Az első átvitel így 11000000 lesz (hexben C0).
A következő átvitel adata (0000000) nulla 1-es bitet tartalmaz (megint páros szám), ezért a paritásbit ismét 0.
A második átvitel így 00000000 lesz (hexben 00).
A következő két átvitel adata (0111000 és 0001101) három 1-es bitet tartalmaz.
A paritásbitjüket 1-re állítják, hogy az átvitelben páros számú 1-es bit legyen.
Így 01110001 és 00011011 formájában mennek át (hexben 71 és 1B).
Az utolsó átvitel (1110) csak négy bit adatot tartalmaz.
Mivel egyszerre pontosan nyolc bitet visznek át, és a paritásbit a jobb szélső bit, három 0 bitet, majd a paritásbitet hozzáadják, hogy kijöjjön a nyolc bit.
Most így néz ki (ahol a _ a paritásbitet jelöli):
1110 000_
↑↑↑ (added 0 bits)
Megint páratlan számú 1-es bit van, ezért a paritásbit 1.
A sorozat utolsó átvitele így 11100001 lesz (hexben E1).
Az üzenet teljes átviteli sorozata 11000000 00000000 01110001 00011011 11100001 (hexben C0 00 71 1B E1).
Megvalósítás
Bár adatbájtokkal dolgozunk, a bemenetek és a kimenetek List<Integer> típusúak (a byte[] helyett), hogy ne kelljen az 128 és 255 közötti bájtok negatív értékeit kasztolni vagy konvertálni.
