wu :: forums - Print Page


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

        riddles >> medium >> Communicating on a Grid of Bits
        
(Message started by: william wu on May 18^th, 2007, 1:24am)

Title: Communicating on a Grid of Bits
Post by william wu on May 18^th, 2007, 1:24am

Alice is given a m x n checkerboard, where m and n are both powers of 2. Each square on the board is already filled with either a 1 or a 0, according to some pattern previously unknown to Alice.

Alice is required to flip exactly one bit on this board of bits, and then send the board to Bob. However, Bob is unaware of what bit pattern was on the board prior to Alice's modification.

Question: How many bits of information can Alice send to Bob? In other words, what is the maximum number of distinguishable messages that Alice can send to Bob?

Source: Paul Cuff; Thomas Cover

Title: Re: Communicating on a Grid of Bits
Post by towr on May 18^th, 2007, 3:13am

Well, it's easy to get 1 bit. But I presume the best will be more in the range of log(n*m). Haven't a clue as to how yet though.

Title: Re: Communicating on a Grid of Bits
Post by Barukh on May 18^th, 2007, 3:53am

How do you get 1 bit on a 1x1 board?

Title: Re: Communicating on a Grid of Bits
Post by SMQ on May 18^th, 2007, 7:21am

I can see a simple way to get 2 bits (with m,n > 1).

--SMQ

Title: Re: Communicating on a Grid of Bits
Post by william wu on May 19^th, 2007, 7:23am

Turns out we can get on the order of log(mn) bits.

Title: Re: Communicating on a Grid of Bits
Post by Barukh on May 19^th, 2007, 9:30am

By flipping one bit? Sending to Bob once?

Title: Re: Communicating on a Grid of Bits
Post by towr on May 19^th, 2007, 1:17pm

I can get two bits accorss when I have 4 (random) bits; you can divide them in 4 equivalence classes
e.g
0000,0001,1111,1110
0010,0011,1101,1100
0100,0101,1011,1010
1000,1001,0111,0110
You can either stay in the same class (flipping the last bit), or go to any of the other classes by choosing one of the first three bits to flip.

I imagine something similar may work for higher numbers of bits. However I don't see how a rectangular board helps.

on 05/18/07 at 03:53:07, Barukh wrote:

How do you get 1 bit on a 1x1 board?

Not, admittedly.

on 05/19/07 at 07:23:06, william wu wrote:

Turns out we can get on the order of log(mn) bits.

Hah, I guessed correctly then. Now if only I could find a practical means to do it. (Or a provable means at least)

Title: Re: Communicating on a Grid of Bits
Post by rmsgrey on May 20^th, 2007, 7:53am

One way:

Let m=2ⁱ, n=2^j

Your aim is to encode an (i+j)-bit message, C.

Each cell in the grid has binary co-ordinates, given by a number with i bits, x, and a number with j bits, y.

To decode the message in the grid, for the k'th bit of the message, when k<i set the bit to 1 if the sum of the contents of all cells with the k'th bit of the x co-ordinate 1 is odd; 0 if the sum is even. Similarly, if k>i, set the bit to 1 if the sum of the contents of all cells with the (k-i)'th bit of the y co-ordinate 1 is odd; 0 if the sum is even.

To encode the message C into a grid currently encoding the message D, find P=C XOR D, and treat P as co-ordinates by taking the first i bits as the x co-ordinate, and the remaining j bits as the y co-ordinate, and flip that cell's contents.

It's clear that this is the maximum amount of information that can be sent since you only have 2^i+j possible actions, so you can't have more than 2^i+j different messages.

Title: Re: Communicating on a Grid of Bits
Post by Grimbal on May 20^th, 2007, 11:56am

In short: [hide]Hamming code[/hide].

Title: Re: Communicating on a Grid of Bits
Post by Grimbal on May 20^th, 2007, 11:59am

on 05/18/07 at 03:53:07, Barukh wrote:

How do you get 1 bit on a 1x1 board?

You can not. log₂(m·n) is 0 for m=n=1.

Title: Re: Communicating on a Grid of Bits
Post by Barukh on May 21^st, 2007, 4:24am

rmsgrey, your solution looks very intriguing. I feel it should be correct! ;D

However, I don't quite get the decoding process.

Title: Re: Communicating on a Grid of Bits
Post by Grimbal on May 21^st, 2007, 5:00am

Decoding to D:
D = XOR _k=0..mn (bit(k)·k)

Encoding C
compute D as above
flip bit #(C xor D)

[oops, corrected! Thanks, rmsgrey]

Title: Re: Communicating on a Grid of Bits
Post by rmsgrey on May 21^st, 2007, 11:32am

on 05/21/07 at 05:00:44, Grimbal wrote:

Decoding to D:
D = XOR _k=0..i+j (bit(k)·k)

Not quite. Taking bit(P) to be the bit at point P in the grid

D = XOR _P=0...mn (bit(P)*P)

In other words, XOR together the co-ordinates of every '1' in the grid.

Title: Re: Communicating on a Grid of Bits
Post by Eigenray on May 21^st, 2007, 1:04pm

(Sounds [link=http://www.ocf.berkeley.edu/%7Ewwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1132879285]familiar[/link].)