Röpke fejtörő

Legyen az input egy tetszőleges 64-bites szám (x) és egy tetszőleges bitpozíció (i, ami gyakorlatilag egy 6-bites szám). Feladatunk, hogy az i értékét továbbítsuk egy külső fél számára úgy, hogy egy x-től legfeljebb 1 Hamming-távolsagra levő számot tovabbítunk. Más szóval, x-et küldhetjuk csak tovább, úgy, hogy előtte 1 bitet átállítunk rajta, vagy meghagyjuk az eredeti számot.

Adjunk meg egy algoritmust (egy enkódert és egy dekódert) helyességigazolással együtt vagy egy bizonyítást arra, hogy ilyen algoritmus miért nem létezik. Ha algoritmust adunk meg, legyen épeszű tár- és időkorlátok közt.

( wachag | 2013. 04. 08., h – 07:51 )

x ismert mindkét fél számára? Ha igen, akkor elég triviálisnak tűnik.

( wauf | 2013. 04. 08., h – 13:39 )

Az "x-től legfeljebb 1 Hamming-távolsagra levő szám" megszoritas miatt a tovabbitando informacio maximalis hosszusagat lecsokkented egy bitre altalanos esetben, vagyis a feladat az lenne, hogy tovabbitsunk 1 biten 6 bitet. Ilyen algoritmus meg trivialisan nem letezik.

( asch v | 2013. 04. 08., h – 18:09 )

Addig eljutottam, hogy kell egy leképzés a 64 bites számokról az 1-64 számokra, ami olyan, hogy minden két Hamming-távolságra lévő számpárhoz különböző értéket rendel. Magyarul amikor megvan az x, akkor 64 féle számot küldhetünk tovább. Ha ezek mindegyikéhez más szám van rendelve, akkor mindig ki tudjuk választani azt, amelyikhez épp i van rendelve, és azt küldjük tovább.

Elkezdtem teljes indukcióval nézni. 2 bites számra működik. 3 bitesre nem. Jajj.

Magamtól valószínűleg még most is gondolkodnék, de szerencsére éppen nálunk volt egy matematikus barátom, aki percek alatt megoldotta a problémát reggeli közben. (bár csak én ettem, ő kizárólag szellemi táplálékkal él :-)

Gondolom tudod a megoldást, és csak gondolkodtatónak adtad fel, igaz? Úgyhogy nem spoilerezem el.

Az első commentemben hibásan fogalmaztam: "ami olyan, hogy minden két Hamming-távolságra lévő számpárhoz különböző értéket rendel" helyett: ami olyan, hogy x összes 1 Hamming távolságú szomszédjához különböző értéket rendel.

Spoiler:

Induljunk ki a moduló 2 maradékosztály feletti testből. (Lásd:
véges testek a Wikipédián ) Vegyük úgy, hogy az x egy 64 elemű vektor ezen test felett. (Tehát a 64 bites szám minden bitje egy vektor koordináta.) Amit hozzárendelünk, az pedig egy 6 hosszú vektor (ugye 2 a hatodikon 64, tehát pont 64 különböző 6 hosszú vektor van).

A hozzárendelés legyen lineáris, tehát egy mátrixszal meghatározható. A hozzárendelés mátrixa tehát 64x6-os lesz. Ha ezt úgy vesszük fel, hogy minden oszlopa különböző legyen (tehát mind a 64 különböző 6 hosszú vektor pontosan egyszer szerepel benne), akkor az x egy Hamming távolságú szomszédai mind különböző 6 hosszú vektorra fognak leképződni, tehát ez a leképzés megfelel a követelményeknek.

A levezetésből látszik, hogy a 64 bithez hasonlóan a kettő hatvány bitszámokra működik a megoldás. Ezért nem működött 3-ra a teljes indukciós próbálkozás :-).

( imp | 2013. 04. 08., h – 18:19 )

Osszuk a 2^64 számot 64 diszjunkt halmazba (G1..G64) úgy, hogy egy tetszőleges (x,i) párhoz létezzen a Gi halmaznak egy olyan eleme, aminek x-től vett távolsága 1. Mivel egy tetszőleges x-hez 65 olyan x' tartozik, aminek távolsága legfeljebb 1, ezért létezhet ilyen algoritmus.

A Gi halmazokat a küldő és a fogadó is ismeri. A küldő az x-et legfeljebb egy bittel változtatja úgy, hogy az x' az i-nek megfelelő csoportba kerüljön. A fogadó megnézi, hogy y melyik G-ben van, és ennyi.

ábra: https://dl.dropbox.com/u/3048596/graph4.png

Az ugyanolyan színek jelentenek egy G-t, az élek pedig az 1-távolságú átmeneteket. Egy tetszőleges számot legfeljebb egy bittel kell megváltoztatni, hogy adott színű legyen.