Author |
Topic: HARD: 3-BIT SENSORS (Read 4547 times) |
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
HARD: 3-BIT SENSORS
« on: Jul 31st, 2002, 7:40pm » |
 Quote  Modify
|
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?
|
| « Last Edit: Jul 31st, 2002, 9:27pm by S. Owen » |
 IP Logged |
|
|
|
-D-
Guest
|
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-
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: HARD: 3-BIT SENSORS
« Reply #2 on: Jul 31st, 2002, 9:07pm » |
Quote Modify
|
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 
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.
|
| « Last Edit: Jul 31st, 2002, 9:14pm by AlexH » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: HARD: 3-BIT SENSORS
« Reply #3 on: Jul 31st, 2002, 9:15pm » |
Quote Modify
|
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.
|
| « Last Edit: Jul 31st, 2002, 9:17pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: HARD: 3-BIT SENSORS
« Reply #4 on: Jul 31st, 2002, 9:19pm » |
Quote Modify
|
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...
|
| « Last Edit: Jul 31st, 2002, 9:27pm by S. Owen » |
IP Logged |
|
|
|
Ryan
Guest
|
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.
|
|
IP Logged |
|
|
|
-D-
Guest
|
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.
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-
|
|
IP Logged |
|
|
|
Ryan
Guest
|
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.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: HARD: 3-BIT SENSORS
« Reply #8 on: Jul 31st, 2002, 11:52pm » |
Quote Modify
|
on Jul 31st, 2002, 10:19pm, Ryan wrote: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. |
|
OOPS. You're right, that's a serious error in the problem statement. I'll change it when I get home. Thanks.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
kul
Guest
|
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.
|
|
IP Logged |
|
|
|
-D-
Guest
|
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 log2(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-
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: HARD: 3-BIT SENSORS
« Reply #11 on: Aug 2nd, 2002, 8:42am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
-D-
Guest
|
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-
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: HARD: 3-BIT SENSORS
« Reply #13 on: Aug 2nd, 2002, 10:55am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 2nd, 2002, 11:04am by AlexH » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: 3-BIT SENSORS
« Reply #14 on: Aug 22nd, 2002, 10:24am » |
Quote Modify
|
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
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove