Prev: How many will Kruh bamboozle today?
Next: affine cipher problem
From: Mok-Kong Shen on 10 Dec 2009 11:33
Hi,

As far as I know, the two schemes run as follows (D=discard):

00 01 10 11
von Neumann: D 0 1 D
self-shrinking: D D 0 1

Both discard one half of groups of 2 consecutive bits in a given
bit stream. Are there any "inherent" scientific reasons favouring the
one scheme over the other? If none, what's the raison d'etre of
the comparatively later invented scheme of self-shrinking?

Thanks.

M. K. Shen
From: unruh on 10 Dec 2009 12:58
["Followup-To:" header set to sci.crypt.]
On 2009-12-10, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote:
> Hi,
>
> As far as I know, the two schemes run as follows (D=discard):
>
> 00 01 10 11
> von Neumann: D 0 1 D
> self-shrinking: D D 0 1
>
> Both discard one half of groups of 2 consecutive bits in a given
> bit stream. Are there any "inherent" scientific reasons favouring the
> one scheme over the other? If none, what's the raison d'etre of

YEs, the second does absolutely nothing to remove the bias in the 0,1
probabilities which is what the vN was designed to do.


> the comparatively later invented scheme of self-shrinking?

Why don't you read the papers in which it was suggested?

>
> Thanks.
>
> M. K. Shen
From: Mok-Kong Shen on 12 Dec 2009 04:08
unruh wrote:
> Mok-Kong Shen wrote:
>> As far as I know, the two schemes run as follows (D=discard):
>>
>> 00 01 10 11
>> von Neumann: D 0 1 D
>> self-shrinking: D D 0 1
>>
>> Both discard one half of groups of 2 consecutive bits in a given
>> bit stream. Are there any "inherent" scientific reasons favouring the
>> one scheme over the other? If none, what's the raison d'etre of
>
> YEs, the second does absolutely nothing to remove the bias in the 0,1
> probabilities which is what the vN was designed to do.

I have a layman's question: Since the scheme of von Neumann removes
the bias and simultaneously discard half of the materials (hence
redering prediction of the generator hard), doesn't it constitute a
'self-shrinking' and thus does what self-shrinking wants to achieve?

M. K. Shen
From: Joe Green on 17 Dec 2009 19:48
> As far as I know, the two schemes run as follows (D=discard):
>
> 00 01 10 11
> von Neumann: D 0 1 D
> self-shrinking: D D 0 1
>
Consider radioactive decay. Run a clock at 10x the average decay rate. Output a zero for each clock period in which no decay event occurs. Output a one if one or more decay event occurs.

Possible output string 0000001000000000000001000000000100000000000000000001000

von Neumann outputs only when pairs of values are different. It matters not if the first or second bit is output. Decide before you start and don't change. Self-shrinking will not remove bias. "10" is MUCH more common than "11".
 | 
Pages: 1
Prev: How many will Kruh bamboozle today?
Next: affine cipher problem