Deljenje po modulu 2

Ko tudi učitelj ne more pomagati...
Post Reply
User avatar
sniper
Posts: 231
Joined: 30.10.2006 13:08

Deljenje po modulu 2

Post by sniper » 17.11.2008 0:50

Ž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... ??



Image

User avatar
GJ
Posts: 2635
Joined: 27.1.2003 22:08

Re: Deljenje po modulu 2

Post by GJ » 17.11.2008 15:02

sniper wrote: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..

User avatar
sniper
Posts: 231
Joined: 30.10.2006 13:08

Re: Deljenje po modulu 2

Post by sniper » 17.11.2008 15:08

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) ?

User avatar
GJ
Posts: 2635
Joined: 27.1.2003 22:08

Re: Deljenje po modulu 2

Post by GJ » 17.11.2008 15:40

sniper wrote: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..

User avatar
shrink
Posts: 14571
Joined: 4.9.2004 18:45

Re: Deljenje po modulu 2

Post by shrink » 17.11.2008 20:32

sniper wrote: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.

User avatar
sniper
Posts: 231
Joined: 30.10.2006 13:08

Re: Deljenje po modulu 2

Post by sniper » 17.11.2008 23:07

shrink wrote:
sniper wrote: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 )

User avatar
GJ
Posts: 2635
Joined: 27.1.2003 22:08

Re: Deljenje po modulu 2

Post by GJ » 17.11.2008 23:34

sniper wrote: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č..

User avatar
sniper
Posts: 231
Joined: 30.10.2006 13:08

Re: Deljenje po modulu 2

Post by sniper » 18.11.2008 0:58

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 ?

User avatar
GJ
Posts: 2635
Joined: 27.1.2003 22:08

Re: Deljenje po modulu 2

Post by GJ » 18.11.2008 10:16

sniper wrote: 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..

User avatar
sniper
Posts: 231
Joined: 30.10.2006 13:08

Re: Deljenje po modulu 2

Post by sniper » 18.11.2008 23:38

aha, ok hvala

Post Reply