wu :: forums - Print Page


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

        riddles >> hard >> HARD: 3-BIT SENSORS
        
(Message started by: srowen on Jul 31^st, 2002, 7:40pm)

Title: HARD: 3-BIT SENSORS
Post by srowen on Jul 31^st, 2002, 7:40pm

I'm having trouble on this one, maybe because I'm misunderstanding the setup.

Is it that both sensors are effectively measuring a value from 0 to 7, and can be off by at most 1? Or is the idea that both are transmitting a 3-bit sequence, at most one of which is wrong?

The CPU gets some reading from A, and then two bits from B (4 possibilities). Given A's reading, there are up to 5 different values the CPU could expect from B in the first interpretation, and 6 in the second. With only 2 bits from B I'm having a hard time seeing how this can uniquely determine B's reading to the CPU.

Has anyone had more luck with this?

Title: Re: HARD: 3-BIT SENSORS
Post by -D- on Jul 31^st, 2002, 8:59pm

I never read this problem fully. If I interpret the problem correctly, then the answer is pretty simple but not for a non-EEE/CPE. You have a 2 sensors and each one can tell when the other one sends, so if sensor A sends an update to the CPU, the sensor B only needs to send 2 bits to validate the reading. This conserves 1 bit of bandwidth, not a whole lot but you can actually magnify this effect for more granular sensors. The answer is to use Hamming codes.

Hamming codes are a way of sending error correcting bits (parity bits essentially) so that you can detect AND correct 1 bit errors even if the error exists in the "parity" bits.

So, lets say A and B both detect the same value, A sends it and B sends the hamming-bits (just 2 needed for this), since all values are correct, the CPU reads the correct value.

However, since we can't tell which sensor read the correct values there is no way to for B to be able to use its value correct the reading from A.
-D-

Title: Re: HARD: 3-BIT SENSORS
Post by AlexH on Jul 31^st, 2002, 9:07pm

As I understand it A sends a 3 bit value to CPU and B knows that his 3-bit value is different in at most 1 bit from A's value (this is interpretation 2 from what you said).

Try recounting the possible number of things the CPU can expect given A's message ,I think you've made an error.

Answer a few lines down and in black:

if B's reading is b1,b2,b3 send b1 XOR b2 and b2 XOR b3

Editing to add this:

D snuck in on my post there :P

In response to that: this is technically not a hamming code situation. The hamming error correction required for a 3 bit signal is actually 3 bits not 2. The trick here is that, unlike in normal coding situations, only the original signal bits can be "wrong", the "correction" bits are guaranteed to be correct. In this case that enables us to get away with 1 fewer bit than we otherwise would need.

Title: Re: HARD: 3-BIT SENSORS
Post by william wu on Jul 31^st, 2002, 9:15pm

Both sensors are measuring the same thing, and both sensors return 3-bit sequences. These two sequences can differ by at most one bit. (So, the Hamming distance between the two sequences is at most 1.) We want to send both A's sequence and B's sequence to the CPU.

Now you might be wondering, why would you want to send both of these sequences if they measure the same thing? Why would I need two thermometers in a room? Why not just use one sensor? Well, if you use only one sensor and it malfunctions in some instance, you don't have that other sensor to back you up. So there's an interesting field of research on sensor networks ... how we can use multiple sensors measuring the same thing to correct for errors.

Back to the riddle. If you were designing a two sensor system, and each sensor makes a 3-bit measurement, you'd most likely design the system such that both sensors send all 3-bits of their measurements back to the CPU. Then you would compare these two sequences, and you'd be able to see if the readings matched or not. And if they didn't match, you could compute by how much they didn't match. However, the claim is that if sensor A has already sent its full 3-bit measurement to the CPU, sensor B only needs to send 2 bits to the CPU, and somehow the CPU can reconstruct B's full 3-bit measurement. So in effect, one bit of bandwidth is magically preserved. One bit of bandwidth seems trivial, but this riddle can be extrapolated to larger sensor networks, and substantial bandwidth can be saved if you know the trick behind this riddle.

It's important that we know beforehand that the sensors can only be off by at most one bit in Hamming distance.

Title: Re: HARD: 3-BIT SENSORS
Post by srowen on Jul 31^st, 2002, 9:19pm

Ah, I'm on the wrong end of the ambiguity in "their readings can be off by at most one bit.." I read this as "... one bit from the actual value" instead of the intended "... one bit from the other reading." That would allow for readings that differ in two bits.

Sure, good answer then. I know a little bit about Hamming codes, but couldn't figure out what sort of suped-up Hamming thingy could possibly sort *that* out...

Title: Re: HARD: 3-BIT SENSORS
Post by Ryan on Jul 31^st, 2002, 10:06pm

If we interpret it to mean the sensors only differ between one another OR are possibly inaccurate by one bit, then realistically this is only going to be the LSB. It would be rather pointless to have a sensor accurate at the 1st bit position but not the 2nd, and if they vary it will only be on the most precise part of the measurement - the LSB.

However, this would make the situation most trivial and the B sensor would only need send the LSB, since the rest would be the same. If the bit discrepancy only happens in the lower 2 bits, then it becomes trivial again because B just sends its lower 2 bits.

This leaves us with the situation where the bit discrepancy can be in any of the 3 bits. I would think B would send the varying bit and then one other bit, but B has no knowledge of what A has sent, just that A has sent a reading. From this, it is far too unlikely (1/3) that B will not send a varying bit. If B has a 1 bit difference and does not send that bit, the CPU cannot determine what the 3rd bit is. If B does send the varying bit and one other bit, then the CPU can conclude the 3rd bit is the same. The difficulty is that this does not establish exactly which 2 bits of the 3 that B will send. The CPU will have no way of determining this either, as it is simply receiving 2 bits. For this to work, there has to be some established standard for which 2 bits, but that's no good because the faulty bit could be any of the 3 bits. Without some additional signalling or existing standard, the CPU cannot determine both the position AND the value of the bits for sensor B.

So, the situation is either trivial, impossible, or requires more information.

Title: Re: HARD: 3-BIT SENSORS
Post by -D- on Jul 31^st, 2002, 10:07pm

Ah... well I interpreted this problem incorrectly. I'm a bit foggy as to what KIND of sensors would be within 1-bit of eachother, basically that means that they are always measuring values that are either 1, 2, or 4 units of magnitude different and not otherwise.

As far as this problem goes, it's actually much easier. The entire possible set of bits can be viewed from the hamming cube that william so elegantly provided.

http://www.ocf.berkeley.edu/~wwu/images/riddles/hamming_cube.gif

since the maximum hamming distance is one, there are 4 posibilities for what the value could be, the 3 values at distance 1 and the same value. 4 posibilities, 2 bits of encoding.

In actual implementation it would be slightly tricky to enumerate which of the 4 values represents what path. Your sense of direction is constantly changing with each vertex. You could probably devise a scheme where you always transmit the most significant 2 bits and the combination that is invalid represents the current value so that you don't have to deal with enumerating your branches.
-D-

Title: Re: HARD: 3-BIT SENSORS
Post by Ryan on Jul 31^st, 2002, 10:19pm

Don't you hate it when a bunch of stuff goes on while you are typing?

From what people are discussing, you are saying B can send ANY 2 bits. The original question had B sending 2 bits FROM THE READING. That can change things significantly, especially if this is extended to a larger scale.

Title: Re: HARD: 3-BIT SENSORS
Post by william wu on Jul 31^st, 2002, 11:52pm

on 07/31/02 at 22:19:12, Ryan wrote:

OOPS. You're right, that's a serious error in the problem statement. I'll change it when I get home. Thanks.

Title: Re: HARD: 3-BIT SENSORS
Post by kul on Aug 1^st, 2002, 9:13pm

The solution is to send two bits where

first bit is middle bit xor side bit
second bit is middle bit xor other side bit.

Comparing these two bits with other sensor's 3 bits, you can always predict what the two bits represent.

Title: Re: HARD: 3-BIT SENSORS
Post by -D- on Aug 2^nd, 2002, 8:24am

You can do better than just predict the result, you can just send exactly what value you recorded relative to the other sensors recording.

Actually this would extend into n bits. n bits will have n+1 possible values to send. You need log₂(n+1) round up bits to send enough information. You can even arrange it so that an encoding of "1" means change the first bit, "2" means second bit, etc. I imagine this would be more straight forward from a coding the cpu perspective than reversing a logic operation (ie: find a bitstring which is within hamming distance one such that parity between pairs of bits matches this sequence)

Not that XORing wouldn't work in theory.....
-D-

Title: Re: HARD: 3-BIT SENSORS
Post by AlexH on Aug 2^nd, 2002, 8:42am

We aren't given reason to think that B knows what reading A sent, only that it can't be too different from his own.

Asymptotically speaking we do nearly as well without that information.

Title: Re: HARD: 3-BIT SENSORS
Post by -D- on Aug 2^nd, 2002, 10:00am

You know.... I haven't been looking at the problem quite that way. These are the weirdest damn sensors I've ever heard of. You're solution is right though.

But in general, it doesn't seem like that solution would scale though to larger amounts of bits. If you had 5-bits of data you would still need 4-bits from the other sensor. If you had a large array of sensors and you saved 1-bit from every other sensor... well it doesn't seem like you're saving a whole lot of bandwith even then, especially if they sampled at a reasonable resolution.
-D-

Title: Re: HARD: 3-BIT SENSORS
Post by AlexH on Aug 2^nd, 2002, 10:55am

You can save a lot more than 1 bit for large values of N. This is just a slight variant of the hamming code, where in stead of using m check bits out of every 2^m-1 sent, we're sending the 2^m-1 as all data, and sending the m over some error free special channel.

So for your 5 bit sensor example we just need 3.

P(1,2,3)
P(1,2,4)
P(1,3,5)

on up to the 7 bit case of:

P(1,3,5,7)
P(2,3,6,7)
P(4,5,6,7)

Our only loss compared to actually seeing A's message is that we have more work encoding and decoding.

Title: Re: HARD: 3-BIT SENSORS
Post by James Fingas on Aug 22^nd, 2002, 10:24am

The XOR solutions are correct, but I'd just like to say that if the point of having two sensors is to reduce errors, then that's fine.

But by encoding the information like this, you ASSUME that sensor A got it right, and that sensor B couldn't be far off. Okay, but by throwing away the extra bit, you get rid of your error detection capability. Then why do you have two sensors ???

When I first read the question, I thought it meant 1 bit in value (this is much more like real sensors would behave). This makes the problem almost exactly the same, just a little easier. This is much more reasonable:

if sensor A says 011
then sensor B could say 010, 011 or 100