Error : correction and tolerance

[A23]

Hi everybody,

 

a) I have the following problem : a source of data S sends data series towards 1 and 2.

 

1 <--------- S ----------> 2

 

 

:confused: Let say there can be differences between the series received in 1 and 2, but not more than p%.

 

c) I would need certain codings of data coming from the source, that permit to make both codes in 1 and 2 remain the same if this amount of difference is less than p%.

 

 

Thanks for ideas.

[alexander]

I have no clue what you are asking, hopefully you can clarify, but if you have a source that sends the data to 2 nodes and that data needs to be the same as what is sent by the source, checksums are your friends...

[A23]

Checksums may decide if errors occurred along the transmission line.

 

What to do if the problem is : the starting codes from S towards 1 and 2 may not be exactly the same, with a small probability, but I need them to be the same in 1 and 2 (with some transformation, or average I don't know)

[alexander]

i am still not sure what you are asking

 

can you give an example of what you are talking about.

 

for example, the way i described it, server1 sends "abc" to server2 and server3, with a checksum of say 123, server 2 receives the data and the checksum, and everything checks out, but server 3 receives the data and the checksum adds up to 321, so data corruption has occurred. server 3 rerequests the data from server 1, server1 resends "abc" with checksum 123, server 3 receives data with checksum 123, thus both server1, server2 and server3 now have data "abc".

[Pyrotex]

The idea of the checksum is excellent and can solve A23's problem if you do not mind resending the data.

 

However, the idea of the checksum can be expanded to indicate that corruption has occurred, AND supply enough data to correct the error immediately. The checksum works because it is sending redundant data. If the redundancy is increaed enough to enable both destinations to reconstruct the data two different ways, then A23's problem is solved.

 

However, with this much redundancy, the information packet must be (at worst) twice as long. You are doing the equivalent of sending each message twice in each information packet. Algorithms exist that can compress the redundancy, but the packets must still be larger. If A23's original packets were [math]N[/math] bytes long, I suspect an ideal expanded checksum with compression would still require the packets to be at least [math]N + \sqrt{N} [/math] bytes long.

 

Now, each message can be verified correct (simple checksum) or made correct (expanded checksum), but at the cost of it taking much longer to send each message.

[A23]

In this case the data cannot be resent.

 

Could a fuzzy-logic be used, in order not to take into account every small-changes ?

[alexander]

No, no Pyro, if you are sending data, such as text data for example, checksum is 1 character long appended to the end of the data and is the xor all of the characters before it. A, its stupid fast, b, it works, proven since the time of serial...

 

If this is a network transaction then you dont have to worry about it, packets are checksummed as a part of the network stack...

If this is a disk transaction, and you are actually designing a system, then you should use ZFS with raid-z as it checksums its blocks so data corruption is made nearly impossible (hence why CERN uses it for storage at the LHC data-center) or alternately btrfs with raid 1, 0 or 10, as it will do the same thing...

[Pyrotex]

No, no Pyro, if you are sending data, such as text data for example, checksum is 1 character long appended to the end of the data and is the xor all of the characters before it. A, its stupid fast, ...

Yes, yes Alexander.

 

IBM developed a space rated computer. It had, not 8-bit bytes, but 11-bit bytes. The extra 3 bits behaved much like a mini-checksum on the other 8 bits. A random reset of any bit in memory could not only be detected, but could be corrected. Caveat: as long as there was just 1 error in the 11-bit byte. If there were 2 errors in the 11-bit byte, you could detect an error but could not fix it. The whole idea was to "harden" the computer against cosmic rays, which often contain enough energy to flip a bit in a modern computer.

 

So, uploading 10 megabytes (with a single 11-bit checksum) to this computer would allow the computer to not only detect an error, but also FIX the error.

However, the cost was that 10 megabytes of actual data (measured in 8-bit bytes) was really 13.75 megabytes long.

 

If A23 cannot handle resending bad data packets, AND he doesn't mind his data packets growing by almost 40%, then this two stage, high redundancy checksum technique would solve his problem.

I think. :shrug:

[Buffy]

...It had, not 8-bit bytes, but 11-bit bytes. The extra 3 bits behaved much like a mini-checksum on the other 8 bits. A random reset of any bit in memory could not only be detected, but could be corrected. Caveat: as long as there was just 1 error in the 11-bit byte. If there were 2 errors in the 11-bit byte, you could detect an error but could not fix it....

:shrug:

 

I don't have it handy but Dick Feynman gave a great lecture on this--I think it was in "Feynman Lectures on Computation"--in which he demonstrated the above and discussed the general solution for the limit on the number of bits you'd need to have varying levels of probability of accuracy/correctability (you know, like the "what is the probability of catastrophic failure" that you love soooo much Mr. Pyro! :bouquet: ). Great book!

 

Amazon.com: Feynman Lectures on Computation (9780738202969): Richard P. Feynman, Anthony Hey, Tony Hey, Robin W. Allen: Books http://www.amazon.com/Feynman-Lectures-Computation-Richard-P/dp/0738202967

 

On the infrequent occasions when I have been called upon in a formal place to play the bongo drums, the introducer never seems to find it necessary to mention that I also do theoretical physics, :P

Buffy

[alexander]

My point still is that he needs to tell us what he is trying to do, because there may be a much easier way to do it then he's thinking...

[Pyrotex]

:shrug:

 

I don't have it handy but Dick Feynman gave a great lecture on this--I think it was in "Feynman Lectures on Computation"--in which he demonstrated the above and discussed the general solution for the limit on the number of bits you'd need to have varying levels of probability of accuracy/correctability (you know, like the "what is the probability of catastrophic failure" that you love soooo much Mr. Pyro! :bouquet: ). Great book!...

Uhhh...

 

Dudess, where do you think Dick got his information? :P

[Buffy]

Uhhh...Dudess, where do you think Dick got his information? :P

Pbbbbbt. Pissing matches on academic priority are for *boys*.... :wilted: :shrug:

 

Feynman had an interest in computing for many years, dating back to the Manhattan project and the modeling of the plutonium implosion bomb...(where) he was put in charge of the 'IBM group' to calculate the energy release during implosion...

 

Stuff goes both ways, duderino... :bouquet:

 

For the record, the lectures were given at Cal Tech in the 80's, and it was for several interdisciplinary computing courses, that to everyone's surprise--even his own--he was talked into giving....

 

Computers can do lots of things. They can add millions of numbers in the twinkling of an eye. They can outwit chess grandmasters. They can guide weapons to their targets. They can book you onto a plane between a guitar-strumming nun and a non-smoking physics professor. Some can even play the bongoes. That's quite a variety!

Buffy

[CraigD]

IBM developed a space rated computer. It had, not 8-bit bytes, but 11-bit bytes. The extra 3 bits behaved much like a mini-checksum on the other 8 bits. A random reset of any bit in memory could not only be detected, but could be corrected. Caveat: as long as there was just 1 error in the 11-bit byte. If there were 2 errors in the 11-bit byte, you could detect an error but could not fix it. The whole idea was to "harden" the computer against cosmic rays, which often contain enough energy to flip a bit in a modern computer.

Sound like a nifty scheme, though I think it would have to be 3 fix bits for 7 data bits, 4 fix bits for 15 data bits, etc, as the fix bits must reserve one value, such as zero, to mean “don’t fix any data bit”.

 

To see if I’ve got the idea, for example

00001001000 00101000100 00001001100 00001001100 11001101100

corrects to

---01001000 ---01000101 ---01001100 ---01001100 ---01001100

 

Notice that I use 11 rather than 10 bit words, ignoring the 128’s place bit.

 

Nifty as it seems, It looks to me that about 27% of the time a bit gets zapped into wrongness by a cosmic ray, it’ll be one of the error-fixing bits, resulting in bad data after the correction, eg:

00001001000 00001000101 01001001100 00001001100 00001001100

corrects (incorrectly) to

---01001000 ---01000101 ---01001110 ---01001100 ---01001100

 

So this scheme’ll still need some sort of check-value and resend-requesting scheme to be reasonably safe.

 

Back in the 1980s, I did a lot of machine-machine communication programming across unreliable serial cables (essentially analog-audio grade amplifiers being used to boost signals meant only to go 100s of feet to cross campus-size distances via all sorts of electronically noisy holes-in-walls, power lines, and metal gutters) that had to keep up a data rate not too much less than the ports’ typical 8 Kb/s. A pretty effective technique was to send the data in packets prefixed by ascii decimal digits for length and 2 checksums that the machines could do quickly – a bytesum and a XORed CRC, if memory serves – something like this (though much longer):

5,372,66,HELLO

 

The receiver sends back a OK/Fail message (not a 1-byte ACK or NAK, but a long-ish something) /

the sender sends the same packet, the next packet, or a special message saying the OK/Fail message was bad /

and if it sent back an OK and didn’t receive an OK/Fail message bad message, the receiver accepts the previous packet.

 

The nice and easy thing about this is that it’s easy to make self-adjusting for line quality, by having it increase the packet length until the error rate became high, then reduce it until it was acceptable. I don’t have my notes handy, but I worked out a neat program that, without significant computing overhead, allowed the line to run at close to best speed for its quality, even as its quality changed due to weather, sun position, or any other factor that vexed it. It could even cope gracefully with a near of complete drop in quality, ie: a line getting temporarily unplugged.

 

Along with the packet length-optimizer program, I worked out the probability of an undetected failure given any line conditions, and it was astronomically low.

 

I bid a fond farewell to all this old hardware and programming ca 1992, when real ethernet hardware that reliably delivered never-bad data at thousands of times greater rates rolled into my life. What I really did was give up this bit of programming turf to whoever wrote the embedded software in all those wonderful ethernet appliances.

My point still is that he needs to tell us what he is trying to do, because there may be a much easier way to do it then he's thinking...

I think A23 asked for a scheme to transform any bit string with fewer than a given fraction of incorrect bits into the correct string, with 100% certainly of success, and no need to ask the sender to resend.

 

I don’t think this is possible. Schemes like Pyro describes can correct data without asking for a resend, but still need whole or partitioned message check values to assure bad bits weren’t in the repair section of the extended word, and to request a resend if that happens.

 

Even a scheme that includes resend requests can’t be 100% reliable, because bad bits in the message’s checksum might unluckily change it to the correct value for a message with bad bits. The best that can be hoped for is a scheme where the probability of this happening is so low that we’d not expect it to occur. Life if fraught with inescapable uncertainty.

[alexander]

from writing code for serial interfaces, something i still do as a part of my job, usually serial packets are postfixed with something (as opposed to prefixed, but it really doesn't matter), usually just a simple XOR, i guess in more trivial systems you'd want a better checksum, i mean possibility of collisions with XOR check sum is still high, flipping 2 bits can lead to the same result, but that is a bit harder with something like CRC or MD5 (CRC having an advantage in speed ofcourse, as some processors actually have circuits dedicated to CRC operation, and BTRFS and ZFS both use them for checksumming blocks for that reason, md5 having the advantage of smaller possibility of collisions)...

 

I think A23 asked for a scheme to transform any bit string with fewer than a given fraction of incorrect bits into the correct string, with 100% certainly of success, and no need to ask the sender to resend.

I think he was asking about fuzzy logic, if you have 2 pieces of data that are not the same, but are close, how do you use fuzzy logic to determine if they are close to being the same data...

 

This is why, to me, it seems like this is a "how do i implement these abstract ideas i came up with for solving this problem" rather then "here's the problem, how would you solve it" question...