Re: XORing bits to eliminate skew
Sarad AV wrote: --- Sandy Harris [EMAIL PROTECTED] wrote: [EMAIL PROTECTED] wrote: there's a well known simple scheme ... I read that Intel chipsets use something similar, its given in rfc 1750 5.2.2 Using Transition Mappings to De-Skew I know the von Neumann technique for pairs of bits. George explained it correctly, and RFC 1750 and various other sources also do so. My question was: What is the technique with three input bits that Intel is reported to use?
Re: XORing bits to eliminate skew
at Thursday, October 17, 2002 4:38 PM, Sarad AV [EMAIL PROTECTED] was seen to say: He wanted to know how I was able to do XOR on P(0) and P(1) when xor is defined only on binary digits. you don't. P(x) is a probability of digit x in the output. ideally, P(0)=P(1)=0.5 (obviously in binary, only 0 and 1 are defined, so they are the only two possible outcomes. Now assume that one output (1 say) is more probable than the other. If this is true, you can define some value of probability (e) that is the amount a given outcome is more or less probable than the ideal. Now add a second bit. assume that the bits are (i) and (ii) so we know that the probability of (i) being 1 is 0.5-e and and being 0 is 0.5+e (there isn't a bias btw in that notation - e could be negative) so all the possible combinations are P(i=1, ii=1) =(0.5-e)(0.5-e) P(i=1, ii=0) =(0.5-e)(0.5+e) P(i=0, ii=1) =(0.5+e)(0.5-e) P(i=0, ii=0) =(0.5+e)(0.5+e) but of course if you XOR (i) and (ii) together, then (i=1, ii=1) = 0 (i=1, ii=0) = 1 (i=0, ii=1) = 1 (i=0, ii=0) = 0 collecting identical outputs allows you to say P(0)=P(i=1, ii=1)+P(i=0, ii=0) = (0.5-e)(0.5-e)+(0.5+e)(0.5+e) P(1) P(i=1, ii=0) + P(i=0, ii=1) = (0.5-e)(0.5+e)+(0.5+e)(0.5-e) reducing P(0) as in the example you gave gives you the probability of P(0) being 0.5+(2*(e^2)) so the answer is - you don't ever apply XOR to anything but binary - you do straight algebraic math on the *probabilities* of a given output (0 or 1)
XORing bits to eliminate skew
hi, In the book on Applied Cryptography by Bruce Schenier,it goes like this... let p(0) be the probability of occurance of 0 and p(1) be the probability od occurance of one. let p(0)=0.5+e p(1)=0.5-e where e is the bias of the bit towards 0 or 1 ideally e=0 P(0)=P(1)=0.5(no bias condition,ideal) XORing 2 bits together yeilds let ^ denote-to the power of p(0)=(0.5+e)^2+(0.5-e)^2=0.5+2*(e^2) Xoring 4 bits together we get, P(0)=0.5+((8*(e^4)) How are these results obtained? It is my understanding that the result is obtained because a=p(0)=0.5+e b=p(1)=0.5-e If ~ denotes negation,~a means negation of a. Xor of 2 bits a b is y=~a.b+a.~b P(0)=(0.5-e)(0.5-e) + (0.5+e)(0.5+e) P(0)=(0.5-e)^2 + (0.5+e)^2 P(0)=0.5+(2*(e^2)) and similarly by xoring 4 bits we get P(0)=0.5+((8*(e^4)) This is how I understand this result is obtained. My teacher how ever asked me,how I was possible to do such an arithmetic when xor is defined only for binary digits (0 and 1). He wanted to know how I was able to do XOR on P(0) and P(1) when xor is defined only on binary digits. I am stumped now and may be i am making a mistake some where. how was the actual result shown below obtained? XORing 2 bits together p(0)=(0.5+e)^2+(0.5-e)^2=0.5+2*(e^2) Xoring 4 bits together , P(0)=0.5+((8*(e^4)) Pls help. thank you very much Regards Sarath. __ Do you Yahoo!? Faith Hill - Exclusive Performances, Videos More http://faith.yahoo.com
