Deljenje po modulu 2

Ko tudi učitelj ne more pomagati...
Odgovori
Uporabniški avatar
sniper
Prispevkov: 231
Pridružen: 30.10.2006 13:08

Deljenje po modulu 2

Odgovor Napisal/-a sniper »

Živjo!

Mi lahko nekdo prosim malo pomaga pri tem deljenju. Zanima me namreč vrstica označena z rumeno. Imamo število 010100 in gledamo ali "gre v njega" število 11001(število z katerim delimo). Se pravi ali "gre" 11001 v 010100. Po mojem mnenju ne gre, na sliki pa je prikazano kot da gre... ??



Slika

Uporabniški avatar
GJ
Prispevkov: 2635
Pridružen: 27.1.2003 22:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a GJ »

sniper napisal/-a:Mi lahko nekdo prosim malo pomaga pri tem deljenju.
Saj tole ni binarno deljenje..
V omenjenem primeru imaš logični stroj, ki ti uporablja dve dvojiški finkciji, in sicer 'shl' (pomik števila v levo za eno mesto, oziroma n*2) in pa 'xor' torej eksluzivni ali.

Zgornji algoritem služi le za izdelavo CRC-ja!

Lep dan..

Uporabniški avatar
sniper
Prispevkov: 231
Pridružen: 30.10.2006 13:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a sniper »

am ja CRC ravno zato to potrebujem. Kako ni deljenje? Kaj ni tako da se M(X) se pravi sporočilo deli po modulu 2 z generatorskim polinomom G(X) ?

Uporabniški avatar
GJ
Prispevkov: 2635
Pridružen: 27.1.2003 22:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a GJ »

sniper napisal/-a:am ja CRC ravno zato to potrebujem. Kako ni deljenje? Kaj ni tako da se M(X) se pravi sporočilo deli po modulu 2 z generatorskim polinomom G(X) ?
Ne tole ni deljenje..
Pri deljenju potrebuješ najprej primerjavo 'cmp' in funkciji odštevanje in binarni pomik v levo (shl).

Za izračun CRC-ja pa ni nujno, da koristiš deljenje temveč lahko uporabiš kak drugi algoritem.
Aha, deljenje z 2 je pomik v desno za eno binarno mesto, oziroma funkcija 'shr'.

Lep dan..

Uporabniški avatar
shrink
Prispevkov: 14575
Pridružen: 4.9.2004 18:45

Re: Deljenje po modulu 2

Odgovor Napisal/-a shrink »

sniper napisal/-a:Imamo število 010100 in gledamo ali "gre v njega" število 11001(število z katerim delimo). Se pravi ali "gre" 11001 v 010100. Po mojem mnenju ne gre, na sliki pa je prikazano kot da gre... ??
Glede na to, da je (0)10100 < 11001, očitno prvo ne more biti deljivo z drugim.

Uporabniški avatar
sniper
Prispevkov: 231
Pridružen: 30.10.2006 13:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a sniper »

shrink napisal/-a:
sniper napisal/-a:Imamo število 010100 in gledamo ali "gre v njega" število 11001(število z katerim delimo). Se pravi ali "gre" 11001 v 010100. Po mojem mnenju ne gre, na sliki pa je prikazano kot da gre... ??
Glede na to, da je (0)10100 < 11001, očitno prvo ne more biti deljivo z drugim.

no sj glih to me zanima, zakaj je pa na sliki prikazano kot da je deljivo (kot da gre 11001 v 010100 )

Uporabniški avatar
GJ
Prispevkov: 2635
Pridružen: 27.1.2003 22:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a GJ »

sniper napisal/-a:no sj glih to me zanima, zakaj je pa na sliki prikazano kot da je deljivo (kot da gre 11001 v 010100 )
Pa saj sem ti napisal, da v tvojem primeru algoritma ne gre za deljenje!
Pri algoritmu deljenja mora biti uporabljena funkcija odštevanje, ti pa imaš uporabljeno funkcijo 'xor' namesto odštevanja (predhodno pa 'rotate shift left').

Algoritem desetiškega in binarnega deljenja je popolnoma enak!

Če hočeš deliti, moraš pred odštevanjem primerjati vrednosti, kar pa v tvojem algoritmu ni zajeto. Še več, algoritem je prej podoben binarnemu množenju kot pa deljenju, saj glede na 'šiftani high bit' kvocienta uporablja 'deljitelj'.

Če hočeš algoritem razumeti ga prevedi v nek programski jezik oziroma 'flowchart'. Tako pa imam občutek, da ne veš kakšen je potek logičnih operacij.

Zgornji algoritem je varianta izračuna CRC in ne deljenja a / b!

Še enkrat!
Na tvoji sliki ni nikjer uporabljeno odštevanje, temveč le binarni 'xor' in 'rotate shift left', ki ni deljenje z 2 temveč moženje z 2!

Kaj ti ni jasno?

Lahko noč..

Uporabniški avatar
sniper
Prispevkov: 231
Pridružen: 30.10.2006 13:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a sniper »

Problem je v tem, da ko pri vajah rešujemo take naloge vedno govorimo, da delimo po modulu 2. Mogoče sem zbral napačno sliko.

Recimo imam nalogo:
Sprejemnik je pravkar prejel sporocilo T(X) = X7 + X5 + X3 + X2. Za odkrivanje
napak uporablja metodo CRC z generatorskim polinomom G(X) = X3 + X + 1. Tukaj
prikazite izracun CRC z aritmetiko po modulu 2, ki ga izvede sprejemnik. Ali bo menil,
da je prejeto sporocilo napacno ali pravilno? Odgovor utemeljite. V sporocilu T oznacite,
kateri prejeti biti so informacijski (tj. M iz zapiskov), ce vemo, da je ostanek CRC na
koncu kot ponavadi.
Kot mi je znano moram sedaj narediti sledeče:

10101100000 : 1011 =

in sedaj ne vem kako gre ta postopek ?

Uporabniški avatar
GJ
Prispevkov: 2635
Pridružen: 27.1.2003 22:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a GJ »

sniper napisal/-a: Kot mi je znano moram sedaj narediti sledeče:

10101100000 : 1011 =

in sedaj ne vem kako gre ta postopek ?
Ahh, osnovna šola!

Če hočeš 'pravilno' deliti je to zelo, zelo preprosto in gre takole..
Torej klasičen način naučen v tretjem razredu osnovne šole (devetletke) le da tokrat delamo v dvojiškem sistemu namesto desetiškem.

Od tukaj naprej je vse v dvojiškem sistemu..

Vzameš prvi bit deljenca (tvoj primer) in dobiš..
00001 primerjaš z 1011 ker je manjši pripišeš rezultatu 0
00010 primerjaš z 1011 ker je manjši pripišeš rezultatu 0 in shiftaš deljenec, preneseš 0001 * 0010 + bit deljenca
00101 primerjaš z 1011 ker je manjši pripišeš rezultatu 0 in shiftaš deljenec ,preneseš 0010 * 0010 + bit deljenca
01010 primerjaš z 1011 ker je manjši pripišeš rezultatu 0 in shiftaš deljenec, preneseš 0101 * 0010 + bit deljenca
10101 primerjaš z 1011 ker je večji odšteješ in pripišeš rezultatu 1, ostanek preneseš 1010 * 0010 + bit deljenca
10101 primerjaš z 1011 ker je večji odšteješ in pripišeš rezultatu 1, ostanek preneseš 1010 * 0010 + bit deljenca
10100 primerjaš z 1011 ker je večji odšteješ in pripišeš rezultatu 1, ostanek preneseš 1010 * 0010 + bit deljenca
10100 primerjaš z 1011 ker je večji odšteješ in pripišeš rezultatu 1, ostanek preneseš 1001 * 0010 + bit deljenca
10010 primerjaš z 1011 ker je večji odšteješ in pripišeš rezultatu 1, ostanek preneseš 0101 * 0010 + bit deljenca
01010 primerjaš z 1011 ker je manjši pripišeš rezultatu 0 in shiftaš deljenec, preneseš 1010 * 0010 + bit deljenca
10100 primerjaš z 1011 ker je večji odšteješ in pripišeš rezultatu 1, ostanek prepišeš ostanek je 1001
ostanek 1001 lahko deliš še naprej vendar moraš postaviti decimalno piko!

Rezultat je torej: 00001111101 preverimo še v desetiškem in vidimo da je vse OK!

Lep dan..

Uporabniški avatar
sniper
Prispevkov: 231
Pridružen: 30.10.2006 13:08

Re: Deljenje po modulu 2

Odgovor Napisal/-a sniper »

aha, ok hvala

Odgovori