Content deleted Content added
→Fano algorithm: use var template |
|||
Line 1:
Recognised by [[John Wozencraft]], '''sequential decoding''' is a limited memory technique for decoding [[tree codes]]. Sequential decoding is mainly used as an approximate decoding algorithm for long constraint-length [[convolutional code]]s. This approach may not be as accurate as the [[Viterbi algorithm]] but can save a substantial amount of computer memory. It was used to decode a convolutional code in 1968 [[Pioneer 9]] mission.
Line 26 ⟶ 25:
*<math>n_i</math> to be the length of <math>P_i</math> in branches.
We express the [[likelihood]] <math>\Pr({\mathbf r}|P_i,X)</math> as <math>p^{d_i} (1-p)^{n_ib-d_i} 2^{-(N-n_i)b}</math> (by using the binary symmetric channel likelihood for the first <math>n_ib</math> bits followed by a uniform prior over the remaining bits).
We express the [[prior probability|prior]] <math>\Pr(P_i|X)</math> in terms of the number of branch choices one has made, <math>n_i</math>, and the number of branches from each node, <math>2^{Rb}</math>.
Therefore:
| |||