Matematické Fórum

Je tím myšleno že se má kodovat čtyřbitová informační čás a opravovat dvojité chyby. Tedy chyby ve dvou bitech

Nikdy jsem toto neresil, akorat jsem se dival na toto, doufam, ze dal pak neplacam nesmysly :-)

Kdyz p je pocet paritnich bitu, tak celkem budes mit 4+p bitu. Jestlize potrebujes opravovat 2 chyby, tak to bude:

1 moznost zadna chyba
4+p moznosti pro jednu chybu
(4+p)*(4+p-1)/2 moznosti pro 2 chyby

Takze dohromady moznosti chyb:

11+4.5p+p^2/2

Paritni bity ti daji 2^p moznosti, takze potrebujes, aby:

2^p >= 11+4.5p+p^2/2

Coz plati pro p>=6, takze budes potrebovat 6 paritnich bitu - celkem 10. Co dal, to presne nevim, to bude podle me ten hlavni orisek :-) Co presne mate za ukol? Staci vytvorit tabulku pro ty parity?

Napadaji me treba tyhle moznosti:

ddddpppppp

x x x x x
xx  xx  x 
xxxx   x   
   x xxx x
 xx xx   x
   x  xxxx

nefunkcni, a to hodne - 4. a 8. sloupec je stejny! :)

Ale moc jsem to neproveroval, kdyztak to opravim nebo vymazu. V tom druhem by asi bylo slozitejsi nastavovat ty paritni bity, nevim presne, jak se pracuje s tema maticema. Jeste se na to mozna podivam. Treba se jeste nekdo jiny ozve, kdo by vedel.

Co jsem daval za priklad jsou vlastne ty kontrolni matice (x jsou jednicky, mezery nuly). Ten prvni priklad co jsem psal by nefungoval, tak to mazu (ten druhy asi taky, ale necham to tam zatim). Podle me je treba, aby zadne dva sloupce nebyly stejne a zaroven aby nebyly stejne soucty jakychkoliv dvou sloupcu - to zaruci, ze pro jakoukoliv jednu nebo dve chyby budou vysledne chybove parity davat jinou kombinaci, a pujde tak jednoznacne urcit, ktere bity jsou spatne. Vytvorit tu matici tak, aby kombinace tech sloupcu nebyly stejne mi nejak nejde, je to slozite asi :-) Ale kdyby slo pouzit vic bitu, tak by to tak slozite nebylo, nevim, jestli to mate mit s maximalni efektivitou nebo ne. Mozna se na to jeste podivam, jestli se mi to povede nejak nakombinovat ty sloupce (nebo zjistit jak se to dela).
Co se tyce dvou paritnich bitu k jednou informacimu, tak kdyz budou chyby v obou paritnich, tak nepoznas, jestli jsou spatne oba paritni, nebo jen informacni, ale mozna to vis a je to to, co chces dotahnout do konce.

Jeste jsem to zkousel, a myslim, ze pro 6 paritnich bitu to nepujde. Ten dalsi priklad co jsem psal nefunguje. Podarilo se mi vytvorit tu kontrolni matici pro 7 paritnich (11 celkem), ktera by mela opravdu fungovat:

1 1 1 0 1 0 0 0 0 0 0 
1 1 0 1 0 1 0 0 0 0 0 
1 0 1 0 0 0 1 0 0 0 0 
1 0 0 1 0 0 0 1 0 0 0 
0 1 1 0 0 0 0 0 1 0 0 
0 1 0 1 0 0 0 0 0 1 0 
0 0 1 1 0 0 0 0 0 0 1

Jestli chces, muzes z toho vytvorit tu generacni matici, nebo s tim cokoliv zkouset jineho. Obavam se, ze vic uz s tim asi nepomuzu :-)

Ahoj, nechť kóduji (4 bitové) slovo xyzw pomocí n čtveřic bitů A1A2A3...An a dále nechť kóduji slovo abcd pomocí B1B2...Bn. Potom lze docílit poruchy C1C2...Cn, že Ci se liší od Ai i od Bi nejvýše o 2 bity, tedy nejsem schopen určit, zda tento porouchaný kód odpovídá slovu xyzw nebo abcd. Tedy dle mého nelze úlohu vyřešit.

↑ Lumikodlak:
Jak tedy prosím zakóduješ slovo 0000 a jak slovo 1111? Díky

V mém předchozím důkazu je xyzw=0000, abcd=1111, A1A2A3=0000|0000|000x (to je kód 0000) a B1B2B3=1111|1100|000x (to je kód 1111). Jen jsem oddělil svislou čarou čtveřeci bitů a poslední bit označil x (jako libovolný), aby čtveřice byla úplná. Nyní uvažujme kód C1C2C3=1100|1100|000x. Na tento kód se vlivem poruch může "přeměnit" jak A1A2A3, tak i B1B2B3 - jak tedy poznám, zda C1C2C3 je zakódované 0000 či 1111?

To mi ale nedává smysl - i když bude mít zpráva 2 bity nebo 10000bitů, pořád dojde k maximálně dvěma chybám? To by byl trošku divný přenosový kanál... Já to chápal tak, že dojde k max. dvěma chybám v každém 4bitovém bloku...

Ale asi by se k tomuto měl vyjádřit autor tohoto příspěvku, jak to myslel.

↑ Lumikodlak:
Tak jednou tvrdíš, že v kódovaném slovu může být 5000 chyb a jindy zas jen dvě chyby.
Takže kdyby se 4bitové slovo kódovalo 10000bitovým slovem, kolik by tedy v tomto 10000bitovém slovu mohlo být nejvýše chyb - 2 nebo 5000?... Pokud 2 tak bych se mohl tvářit, že kóduji 4bitové slovo, ale ve skutečnosti bych kódoval 4bitových slov víc - a hle - jako zázrakem bych měl v tomto kódu stále jen dvě chyby. :-)

↑ check_drummer:
Netvrdim, ze v kodovem slovu muze byt 5000 chyb. V jednom muzou byt dve, takze ve 2500 slovech (10000 informacnich bitech) muze byt dohromady 5000 chyb (reagoval jsem na tohle: "To mi ale nedává smysl - i když bude mít zpráva 2 bity nebo 10000bitů, pořád dojde k maximálně dvěma chybám? To by byl trošku divný přenosový kanál..."). Nechtel jsem kodovat 4 bity 10000bitovym slovem, to akorat 10000 bitu by se kodovalo v 2500 slovech po 4 bitech informace. Asi to ale nedovedu vysvetlit. Ted vazne nevim, v cem vidis problem :-)

↑ check_drummer:
Ano, ale to neni tak efektivni, pri 4 bitove informaci by bylo treba 20 bitu, da se to zaridit i s 11 bity jak jsem psal. Mozna, ze by to ale ke splneni autorova ukolu stacilo.

↑ Redby:
Tak ještě pro upřesnění - co se myslí dvojitou chybou? Jedná se o to, že v zakódovaném slovu (tj. v kódu pro dané 4bitové slovo) - ať je dlouhé třeba 4 bity nebo 10000bitů - se mohou vyskytovat jen nejvýše dvě chyby? A nebo, že v každém 4bitovém bloku, které tvoří zakódované slovo, se mohou vyskytnout nejvýše 2 chyby?

Např. zakóduju-li 0000 pomocí 000000000000 - může se mi vlivem chyb změnit toto slovo na 110011001100?

Ja nevim, jestli ma smysl tu o tom diskutovat :-) O tech samoopravnych kodech se preci daji najit informace normalne na internetu napriklad. Ty zakladni principy jsem si odvodil podle tohot clanku na wikipedii. Kdyby to nefungovalo, tak nevim, proc by se to normalne uz desitky let pouzivalo.

↑ check_drummer:
Nemyslim si, ze by tu tak slo o to, ke kolika chybam dojde. Rozdil je mezi tim, ke kolika chybam dojde (coz nezavisi na tom kodu, ale na tom prenosovem kanale), a mezi tim, kolik chyb umi kod opravit. Ten kod muzes vytvorit jakykoliv ches (teoreticky), a podle toho, jaky ten kod bude, tak podle toho bude mit informacnich bitu, zakodovanych bitu, bude schopen opravovat nejaky pocet chyb a podobne. Nevim, jaky ma smysl ten priklad s kodovanim 4 bitu na 10000 - to zase zalezi na tom, jak to zakodujes, pri kodovani ze 4 bitu na 10000 by urcite slo opravovat mnohem vic chyb nez jen 2. Kodovani, podle te tabulky, co jsem tu popsal, koduje ze 4 bitu na 11 a je schopno opravit 2 chyby. Hemminguv kod pro 4 informacni bity koduje ze 4 na 7 a umi opravit jednu chybu. To co jsi popsal predtim koduje z m bitu na m(2p+1) bitu a je chopno opravit p chyb.

Kdyz 4 bity zakodujes 4m bity, tak to nema zadny vliv na to, kolik tam bude chyb. Predpokladam, ze ses chtel zeptat na to, kolik chyb bude umet opravit - nepopsal jsi, jak by se to kodovalo, takze nevim, kolik by to umelo opravit chyb (akorat treba pro m=1 zadnou chybu protoze takove nemuze existovat, coz uz jsi vlastne sam psal).