Re: Q: SAC

Scott Fluhrer wrote:
"Maaartin" <grajcar1@xxxxxxxxx> wrote:
Mok-Kong Shen <mok-kong.s...@xxxxxxxxxxx> wrote:
For n = 0 (mod 4), n > 4, do there exist bijective functions
(by necessity nonlinear, see (1) above) which satisfy the condition
that flipping any one input bit always causes exactly 2 output bits
to flip?
No idea.

The answer is no (and that answer is still 'no' even without the conditions on n). If we flip any input bit, then two output bits will flip; this implies that the parity of the output (whether there's an even number of '1' bits) will remain the same. We can move to any input setting by successively flipping input bits, this means that the output parity will still be fixed, and so half the possible outputs will be impossible (and hence the function cannot be bijective).

Pardon! There was a typo in my previous post. I am sorry. That question
should read:

For n = 0 (mod 4), n > 4, do there exist bijective functions
(by necessity nonlinear, see (1) above) which satisfy the condition
that flipping any one input bit always causes exactly n/2 output bits
to flip?

Thanks,

M. K. Shen

.

Relevant Pages

  • Re: Q: SAC
    ... (by necessity nonlinear, see (1) ... above) which satisfy the condition ... If we flip any input bit, ... setting by successively flipping input bits, ...
    (sci.crypt)
  • Re: Ocean Kayak and 27footer: store / tow
    ... I don't think the kayak would be immune to flipping. ... The kayak can't fill with water and will either dive or just ... flip back again. ...
    (rec.boats.cruising)
  • Re: Newbie: problem with strncpy
    ... >> the string to all zeros. ... sometimes it is not possible to just pick and flip ... By flipping bits 3-4, we get "00000". ... flipping bits 2-9 yields "0001110000" ...
    (comp.lang.c)
  • Re: crank preferences for flipping
    ... tried flipping on one then the other side by side. ... It seems like longer cranks will give you ... more torque so a fast flip but with shorter cranks naturally flip ... Spencer Hochberg ...
    (rec.sport.unicycling)
  • Re: Q: SAC
    ... above) which satisfy the condition ... If we flip any input bit, then two output bits will flip; ... successively flipping input bits, this means that the output parity will ...
    (sci.crypt)
Quantcast