Hulp bij formule

Het forum voor overige vragen betreffende wiskunde uit het hoger onderwijs.
arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hulp bij formule

Bericht door arie » 31 mei 2014, 19:17

Een volledigere methode dan in het artikel:

In stap 4 bepaal je de toename van de bijdrage van elke element (i,j) aan mH als je bit (i,j) omflipt.
De elementen waarvoor Vb(i,j)==0 dragen W(i,j) bij,
de elementen waarvoor Vb(i,j)==1 dragen (2^r)-W(i,j) bij.

Zet deze waarden in een matrix A:



In A lees je nu direct af dat A(2,2) = 10, dus dat flippen van bit (2,2) de gewenste toename d = 10 geeft.

Voor dubbele bitflips ga je alle tweetallen elementen van A af en zoek je de tweetallen die samen opgeteld 10 of 26 (=10 mod 16) zijn.
Voorbeeld:
A(1,1) + A(2,1) = 15 + 11 = 26 = 10 mod 16.

Dus
Ib =
0 1 1 0
1 0 1 0
0 1 0 1
0 1 1 1
wordt
Ib' =
1 1 1 0
0 0 1 0
0 1 0 1
0 1 1 1
en ook dit levert
SUM( (Ib' XOR K) .* W) mod 16 = 13 = B

Je vindt op deze manier alle mogelijke tweetallen (i1,j1) en (i2,j2) die voldoen, en dat zijn er duidelijk meer dan in dat artikel via stap 6.
De verzamelingen Si (i = 0 t/m (2^r)-1) heb je hierbij niet meer nodig.

Mogelijk gebruiken ze de methode in het artikel omdat dat sneller is: alle tweetallen afgaan kost een tijd die kwadratisch evenredig met het aantal elementen (tijd = O(n^2)). Voor hele grote blokafmetingen en verwerken van heel veel figuren zal dit mogelijk te lang duren.

pixebility
Vast lid
Vast lid
Berichten: 77
Lid geworden op: 20 okt 2010, 14:37

Re: Hulp bij formule

Bericht door pixebility » 02 jun 2014, 10:56

Ok waarschijnlijk is het verstandig om de snelle versie te gebruiken dan.
S0 heeft een bijzondere plaats: deze is weliswaar leeg, maar hebben ook niet nodig:
in bovenstaand voorbeeld vinden we S0 voor h = 0, 1, 8 of 9:
S0 wordt in al deze 4 gevallen gecombineerd met S10, dus S10 levert in zijn eentje een mogelijke oplossing:
S10 = { (2,2) }, dus flip ALLEEN bit (2,2) en je hebt een oplossing: dit is gedaan in Table 7.
Ok dus als de waarde van of de waarde van 10 is in dit geval dan is dat een index waar ik een bitflip op uit kan voeren?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hulp bij formule

Bericht door arie » 02 jun 2014, 17:25

Klopt.

Als
-(h-1)*d = d (mod 2^r)
dan is (werk links de haakjes weg):
-hd + d = d (mod 2^r)
ofwel
-hd = 0 (mod 2^r)
ofwel
hd = 0 (mod 2^r).
Dus in dit geval vind je altijd S_0 en S_d, waarbij je S_0 niet gebruikt, en alleen een bit op een locatie uit S_d omflipt.

Omgekeerd: als
hd = d (mod 2^r)
dan is:
hd-d = 0 (mod 2^r)
waardoor ook:
-(hd-d) = 0 (mod 2^r)
ofwel
-(h-1)d = 0 (mod 2^r)
In dit geval vinden we dus ook S_d en S_0.

Conclusie: als 1 van de twee gelijk is aan d, dan is de andere gelijk aan nul.
Dat is ook logisch, want bij elkaar opgeteld moeten de twee indices altijd d geven.

Let wel op:
We hadden gezien:
mH = 3
bitstring b1b2b3b4 = 1101 dus B = 13
waardoor d = B - mH = 10 (mod 16),
en 10 is aanwezig: S_10 = { (2,2) }
(alternatief: zie matrix A hierboven: daarin staat een 10, en wel direct op de plaats van de bitflip die we nodig hebben)

Echter:
Als de bitstring in dit geval B = 15 of B = 0 zou zijn, dan zou d = 12 resp d = 13 zijn,
en die vind je niet terug in A: S_12 en S_13 zijn leeg.
In dat geval kom je niet uit met 1 bitflip, maar heb je er echt 2 nodig.

pixebility
Vast lid
Vast lid
Berichten: 77
Lid geworden op: 20 okt 2010, 14:37

Re: Hulp bij formule

Bericht door pixebility » 05 jun 2014, 15:24

Ik heb nog een probleem met mijn implementatie er zit bij mij nog iets niet helemaal goed.
Bij stap 6 moet ik in mijn geval een dubbele bitflip doen.
Hieronder het voorbeeld ik moet de op de positie van 3 en 6 in de weight table een bitflip doen.
Bij h=2 heb ik de juiste posities in S namelijk S(10) en S(3).
Wat is in mijn geval de berekening die ik moet doen om deze posities te flippen?

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

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 2

1 2 0 0
5 6 7 8
9 10 11 12
13 0 15 0

0 - (1+2+5+6+7+8+9+10+11+12+13+15) mod 16 = -3
-3 mod 16 = 13

VB (0,0) = 1 S(16 - W(0,0)) = S(16-1) = S(15)
VB (0,1) = 1 S(16 - W(0,1)) = S(16-2) = S(14)
VB (0,2) = 0 S(W(0,2)) = S(3) <-- 3
VB (0,3) = 0 S(W(0,3)) = S(4)

VB (1,0) = 1 S(16 - W(1,0)) S(16 - 5) = S(11)
VB (1,1) = 1 S(16 - W(1,1)) S(16 - 6) = S(10) <-- 6
VB (1,2) = 1 S(16 - W(1,2)) = S(16 - 7) = S(9)
VB (1,3) = 1 S(16 - W(1,3)) = S(16 - 8 ) = S(8)

VB (2,0) = 1 S(16 - W(2,0)) = S(16 - 9) = S(7) <-- 9
VB (2,1) = 1 S(16 - W(2,1)) = S(16 - 10) = S(6) <-- 10
VB (2,2) = 1 S(16 - W(2,2)) = S(16 - 11) = S(5)
VB (2,3) = 1 S(16 - W(2,3)) = S(16 - 12) = S(4)

VB (3,0) = 1 S(16 - W(2,0)) = S(16 - 13) = S(3) <-- 13
VB (3,1) = 0 S(W(2,1)) = S(14)
VB (3,2) = 1 S(16 - W(2,2)) = S(16 - 15) = S(1)
VB (3,3) = 0 S(W(2,3)) = S(2)

h a b
0 0 13
1 13 0
2 10 3
3 7 6
4 4 9
5 1 12
6 14 15
7 11 2
8 8 5
9 5 8
10 2 11
11 15 14
12 12 1
13 9 4
14 6 7
15 3 10

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hulp bij formule

Bericht door arie » 05 jun 2014, 20:20

pixebility schreef: Bij stap 6 moet ik in mijn geval een dubbele bitflip doen.
Een dubbele bitflip is niet strikt noodzakelijk, zie de opmerking in het artikel onder step 6:
"if S0 is encountered then skip" (ze bedoelen niet de hele stap 6 maar het onderdeel 6b of 6c waar de S0 staat).
Als je S0 tegenkomt laat je die weg, en heb je aan 1 bitflip voldoende.
Dit hebben ze ook gedaan in Table 8: daar komen ze zelfs in alle 3 de voorbeeldblokken met elk slechts 1 bitflip uit.

pixebility schreef: Hieronder het voorbeeld ik moet de op de positie van 3 en 6 in de weight table een bitflip doen.
Bij h=2 heb ik de juiste posities in S namelijk S(10) en S(3).
Wat is in mijn geval de berekening die ik moet doen om deze posities te flippen?
Als h=2 dan vind je S10 en S3
Eerst zullen we deze S-verzamelingen moeten gaan bepalen.
S0 t/m S15 zijn verzamelingen van idex-paren (i, j) voor je matrix.
Bij jou lopen i en j van 0 t/m 3, in mijn voorbeeld hierboven van 1 t/m 4, maar dat maakt in essentie niets uit.

Bij dit onderdeel bepaal je de verzamelingen S:
pixebility schreef: VB (0,0) = 1 S(16 - W(0,0)) = S(16-1) = S(15)
VB (0,1) = 1 S(16 - W(0,1)) = S(16-2) = S(14)
VB (0,2) = 0 S(W(0,2)) = S(3) <-- 3
VB (0,3) = 0 S(W(0,3)) = S(4)

VB (1,0) = 1 S(16 - W(1,0)) S(16 - 5) = S(11)
VB (1,1) = 1 S(16 - W(1,1)) S(16 - 6) = S(10) <-- 6
VB (1,2) = 1 S(16 - W(1,2)) = S(16 - 7) = S(9)
VB (1,3) = 1 S(16 - W(1,3)) = S(16 - 8 ) = S(8)

VB (2,0) = 1 S(16 - W(2,0)) = S(16 - 9) = S(7) <-- 9
VB (2,1) = 1 S(16 - W(2,1)) = S(16 - 10) = S(6) <-- 10
VB (2,2) = 1 S(16 - W(2,2)) = S(16 - 11) = S(5)
VB (2,3) = 1 S(16 - W(2,3)) = S(16 - 12) = S(4)

VB (3,0) = 1 S(16 - W(2,0)) = S(16 - 13) = S(3) <-- 13
VB (3,1) = 0 S(W(2,1)) = S(14)
VB (3,2) = 1 S(16 - W(2,2)) = S(16 - 15) = S(1)
VB (3,3) = 0 S(W(2,3)) = S(2)
Bij het begin zijn alle S-verzamelingen leeg, je voegt 1 voor 1 de indexparen toe aan de juiste S-verzameling.
Omdat VB(0,2) = 0, wordt het indexpaar (0,2) toegevoegd aan verzameling

Op dat moment is je verzameling S3:

Later levert ook VB(3,0) S3 op, dus indexpaar (3,0) wordt dan aan S3 toegevoegd, en

S3 bevat dan 2 elementen = 2 indexparen, namelijk indexpaar (0,2) en indexpaar (3,0).

Op dezelfde manier vind je


Nu terug naar:
pixebility schreef: Bij h=2 heb ik de juiste posities in S namelijk S(10) en S(3).
Wat is in mijn geval de berekening die ik moet doen om deze posities te flippen?
Je kiest dan random een indexpaar uit S10 en random een indexpaar uit S3:
- S10 bevat slechts 1 element, het indexpaar (1,1), hier valt dus niets te kiezen, we nemen dit paar
- S3 bevat 2 elementen, kies bijvoorbeeld de tweede = (3,0)
Als we nu beide bits (1,1) en (3,0) in de image omflippen (dat wil zeggen: de LSB's van de bytes op positie (1,1) en (3,0) in het blok), dan komen we goed uit.
(Merk op dat we ook goed uit zouden komen als we (1,1) en (0,2) (= het andere element van S3) beide zouden omflippen.)

pixebility
Vast lid
Vast lid
Berichten: 77
Lid geworden op: 20 okt 2010, 14:37

Re: Hulp bij formule

Bericht door pixebility » 05 jun 2014, 21:43

De verzameling indexparen heb ik berekend. Maar hoe weet ik nou welk indexpaar ik moet hebben op basis van de onderstaande waarden?

h a b
0 0 13
1 13 0
2 10 3
3 7 6
4 4 9
5 1 12
6 14 15
7 11 2
8 8 5
9 5 8
10 2 11
11 15 14
12 12 1
13 9 4
14 6 7
15 3 10

Niet alle resultaten geven goede indexparen weer uit S.
Dus hoe kan ik bepalen dat ik moet hebben in dit geval?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hulp bij formule

Bericht door arie » 05 jun 2014, 22:12

Verwijder alle regels waarin S_a en/of S_b de lege verzameling is.
(S0 neemt alleen een bijzondere plaats in, die leidt tot een 1-bitflip-oplossing)

Maar kijk ook nog eens goed naar deze berekening:
pixebility schreef: 0 - (1+2+5+6+7+8+9+10+11+12+13+15) mod 16 = -3
-3 mod 16 = 13
de d die je zoekt is
d = 13 - (1+2+5+6+7+8+9+10+11+12+13+15) mod 16 = ...
(de code-bitstring = 1101 = 13 tientallig)
Daarmee zullen ook de waarden voor a en b in je verdere berekening anders zijn.

pixebility
Vast lid
Vast lid
Berichten: 77
Lid geworden op: 20 okt 2010, 14:37

Re: Hulp bij formule

Bericht door pixebility » 06 jun 2014, 10:56

Arie bedankt ik heb hem eruit nu.
Mijn implementatie werkt.

Plaats reactie