Jarek Duda
Guest
|
 Posted: Thu Oct 02, 2008 7:04 am Post subject: Data correction methods used today are far from being optima |
 |
|
Let>s think about theoretical limit of bits of redundancy we have to
add for bit of information for assumed statistical error distribution
to be able to fully correct the file.
To find this threshold, let>s think about simpler looking question:
how many information is stored in such uncertain bit?
Let>s take the simplest error distribution model - for each bit
probability that it>s switched is equal e (near zero), so if we see
'1' we know that with probability 1-e it>s really '1', and with
probability e it>s 0.
So if we would know which of this cases we have, what is worth h(e)=-e
lg(e) - (1-e) lg(1-e) bits, we would have whole bit.
So such uncertain bit contains 1-h(e) bits.
To transfer n real bits, we have to use at least n/(1-h(e)) these
uncertain bits - the theoretical limit to be able to read a message is
(asymptotically)
h(e)/(1-h(e)) additional bits of redundancy /bit of information.
So a perfect data correction coder for e=1/100 error probability,
would need only additional 0.088 bits/bit to be able to restore the
message.
Hamming 4+3 in spite of using additional 0.75 bits/bit, looses 16bits/
kilobyte with the same error distribution.
There are two main reasons of being far from optimal:
- they place the data in independent blocks, making them sensible to
pessimistic cases,
- they don>t correspond to the error distribution. For example Hamming
4+3 assumes that we have one of 8 error scenarios - no error, or
changed one of 7 bits. It encodes all of this cases equally, but
usually the scenario that we have no error is much more probable.
One of approaches to came closer to the optimal data correction method
is using new coder: Asymmetric numeral system.
It has huge freedom of choice, for example we can get Hamming code or
bit tripling as some degenerated cases.
Here is demonstration about it:
http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/
Here is more information about it>s use for data correction:
http://www.thescienceforum.com/Data-correction-methods-resistant-to-pessimistic-cases-13416t.php |
|
