Content deleted Content added
Translating p_d into rate, 'weight' in this educating simulator is practically Fano metric |
Added computational cutoff rate |
||
Line 48:
This last expression is the Fano metric. The important point to see is that we have two terms here: one based on the number of wrong bits and one based on the number of right bits. We can therefore update the Fano metric simply by adding <math> \log_2 p +1-R</math> for each non-matching bit and <math>\log_2 (1-p) + 1-R</math> for each matching bit.
==Computational cutoff rate==
For sequential decoding to a good choice of decoding algorithm, the number of states explored wants to remain small (otherwise an algorithm which deliberately explores all states, eg the [[Viterbi algorithm]], may be more suitable). For a particular noise level there is a maximum coding rate <math>R_0</math> called the computational cutoff rate where there is a finite backtracking limit. For the binary symmetric channel:
:<math>R_0 = 1-\log_2(1+2\sqrt{p(1-p)})</math>
==Algorithms==
| |||