Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Self-schrinking vs von Neumann unbiasing

3 views
Skip to first unread message

Mok-Kong Shen

unread,
Dec 10, 2009, 11:33:56 AM12/10/09
to
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

unruh

unread,
Dec 10, 2009, 12:58:59 PM12/10/09
to
["Followup-To:" header set to sci.crypt.]

On 2009-12-10, Mok-Kong Shen <mok-ko...@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

Mok-Kong Shen

unread,
Dec 12, 2009, 4:08:23 AM12/12/09
to
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

Joe Green

unread,
Dec 17, 2009, 7:48:06 PM12/17/09
to
> 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".

0 new messages