wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Spy transmission 15bit
        
(Message started by: Eigenray on Nov 24^th, 2005, 4:41pm)

Title: Spy transmission 15bit
Post by Eigenray on Nov 24^th, 2005, 4:41pm

Alice, as usual, wants to send a message to Bob.

This time Alice is a spy in an enemy transmission tower, which sends out exactly 15 bits each day. Alice sees the whole message before it is sent, and is capable of then flipping at most one bit. How much information can she send to Bob?

(Of course they discuss their scheme ahead of time, but without any knowledge of the enemy's bits other than that there are 15 of them.)

Title: Re: Spy transmission 15bit
Post by Icarus on Nov 24^th, 2005, 7:32pm

I could be wrong, but if they don't know anything about the 15 bits before hand, it seems to me that [hide] she can send only one bit per day, by having him count even bit parity as 0, and odd bit parity as 1.[/hide]

Of course, whatever the scheme is, it is going to have to take days to transmit any useful information. She had better hope no one notices that the messages they are trying to send (which must be important for them to have set up this weird transmitter in the first place) are being screwed up by her.

Title: Re: Spy transmission 15bit
Post by Eigenray on Nov 24^th, 2005, 10:45pm

She can do much better than that...

And as for why they wouldn't notice what she's doing, well, that's just part of the puzzle ;)

Title: Re: Spy transmission 15bit
Post by towr on Nov 25^th, 2005, 12:54am

I can see how she could send [hide]log₂3[/hide] bits. But that's not a lot more

Title: Re: Spy transmission 15bit
Post by Grimbal on Nov 26^th, 2005, 7:06am

Just with 3 bits she could transmit 2:

[hideb]
The receiver computes
abc --> a^b, a^c (^ = xor)

Alice first checks a^b and a^c. If one of the 2 bits is wrong, Alice can change b or c. If both are wrong, Alice can change a.
[/hideb]

Title: Re: Spy transmission 15bit
Post by BNC on Nov 26^th, 2005, 7:20am

To continue Grimbal's idea:
[hide]
With 7 bits, transmitting 3 bits is possible:

Receiving calculates:

A=a^b^c^d
B=b^d^e^f
C=c^d^e^g

Alice check the 3 values:
all ok: change nothing
A wrong: change a
B wrong: change f
C wrong: change g
A,B wrong: change b
A,C wrong: change c
B,C wrong: change e
A,B,C wrong: change d

This way, with 15 bits, 4 bit may be transmitted:
A=xor(a,e,f,g,k,l,m,o)
B=xor(b,e,h,i,k,l,n,o)
C=xor(c,f,h,j,k,m,n,o)
D=xor(d,g,i,j,l,m,n,o)
[/hide]

Title: Re: Spy transmission 15bit
Post by Grimbal on Nov 26^th, 2005, 7:34am

And here is the solution:

[hideb]
You have a 15-bit preexisting message P.
You have a 4-bit message M to pass.

Number the 15 bits of P from 1 to 15, express the numbers in binary.
Compute A = the xor of the numbers of the bits that are set in P. P' = P.
If A = M, you don't need to change anything.
If not, B=A^M is a number from 1 to 15. Change bit #B in P giving P'.
Send P'.

The receiver gets P'.
He computes A' = xor of the numbers of the bits that are set in P'.
If no bit was changed, A' = M.
If one was, by construction, A' differs from A in that the bits of B were inverted once more or once left.
A' = A^B = A^(A^M) = M.

So, computing A' yields the message M.
[/hideb]

Title: Re: Spy transmission 15bit
Post by Grimbal on Nov 26^th, 2005, 7:35am

As you see, I was about to say that.... :'(

Title: Re: Spy transmission 15bit
Post by JocK on Nov 26^th, 2005, 7:36am

.. which is obviously the optimum, as by tweeking at most one bit out of a stream of 2ⁿ-1 bits, one can not send more than n bits of information.

Title: Re: Spy transmission 15bit
Post by Eigenray on Nov 26^th, 2005, 1:01pm

Yes, exactly. And the reason the enemy won't notice is because they're using a (15,11) hamming code, which detects and corrects single-bit errors. They're only sending 11 bits of information, and Alice manages to use the other 4 bits for herself :)

Title: Re: Spy transmission 15bit
Post by JocK on Nov 26^th, 2005, 1:26pm

Nice problem Eigenray!

Title: Re: Spy transmission 15bit
Post by Grimbal on Nov 29^th, 2005, 5:31am

on 11/26/05 at 13:01:14, Eigenray wrote:

I guessed so. And if you know you start with a correct hamming code, you can just reverse the bit you want and detect the changed bit at the receiving side.

Title: Re: Spy transmission 15bit
Post by Joe Fendel on Nov 29^th, 2005, 7:44am

So if the transmission is 5 bits, and Alice can flip 2 of them, how can she send a 4-bit message?

(I think this is actually easier than the original problem.)