Correction Trees
Correction Trees
Forward error correction methods are fundamental in the transmitting and storing of information. They allow increasing the size of the message using so-called redundancy to be able to repair errors of assumed statistics, for instance that each bit can be changed with probability . In the standard approach we encode the message in independent blocks.
p
b
This Demonstration simulates the creation of pseudorandom trees while using a new approach to error correction, in which we connect redundancies stored in blocks. Intuitively, this connection allows the transfer of surpluses of redundancy to cope with local error concentrations. Nodes of the tree correspond to corrections of the message up to a given point—they create a tree because each bit can be corrected or not.
For a given probability that bits are damaged ), we choose the parameter that corresponds to the amount of redundancy we add—the larger this parameter, the more we increase the size of the message, the easier it is to correct. The role of this parameter is that when we are not on the branch corresponding to the proper correction, at each step we have probability of spotting that, and so we can try to search somewhere else. At each step of the correction process we know the current tree and we use it to find a leaf that looks to be most probably correct and try to expand it.
(
p
b
p
d
p
d
The controls allow you to choose , , the lengths of bit blocks used in the process, and the number of steps to make. Choosing "rescale " makes that the slider for works in the most interesting range: . Using the "correction" or "errors" buttons, you can generate new corrections for the same error distribution or some random new one.
p
b
p
d
p
d
p
d
,
0
p
d
2
p
d
There is a variety of information at the top-right corner: the boundaries of this range, how much time the size of the message increases (theoretically it would be enough to increase to repair all damage (Shannon's limit)), and how many bits we would have in fact decoded or as an average for one step.
(H'/H)
The simulator presents the correction process (tree) in three ways: how the local width of the tree behaves, the weights used to choose the most probable node in succeeding steps, or the tree itself.