Sequential decoding: Difference between revisions

Revision as of 21:40, 18 January 2022

Latest revision as of 10:17, 10 April 2025

(2 intermediate revisions by one other user not shown)

Line 16:

Given a partially explored tree (represented by a set of nodes which are limit of exploration), we would like to know the best node from which to explore further. The Fano metric (named after [[Robert Fano]]) allows one to calculate from which is the best node to explore further. This metric is optimal given no other constraints (e.g. memory).

For a [[binary symmetric channel]] (with error probability <math>p</math>) the Fano metric can be derived via [[Bayes' theorem]]. We are interested in following the most likely path <math>P_i</math> given an explored state of the tree <math>X</math> and a received sequence <math>{\mathbf r}</math>. Using the language of [[probability]] and [[Bayes' theorem]] we want to choose the maximum over <math>i</math> of:

:<math>\Pr(P_i|X,{\mathbf r}) \propto \Pr({\mathbf r}|P_i,X)\Pr(P_i|X)</math>

Line 49:

==Computational cutoff rate==

For sequential decoding to be a good choice of decoding algorithm, the number of states explored wants toshould remain small (otherwise an algorithm which deliberately explores all states, e.g. 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>

Line 65:

# At each decoding stage, the Fano algorithm retains the information regarding three paths: the current path, its immediate predecessor path, and one of its successor paths.

# Based on this information, the Fano algorithm can move from the current path to either its immediate predecessor path or the selected successor path; hence, no stack is required for queuing all examined paths.

# The movement of the Fano algorithm is guided by a dynamic threshold {{var|T}} that is an integer multiple of a fixed step size ¢Δ.

# Only the path whose path metric is no less than {{var|T}} can be next visited. According to the algorithm, the process of codeword search continues to move forward along a code path, as long as the Fano metric along the code path remains non-decreasing.

# Once all the successor path metrics are smaller than {{var|T}}, the algorithm moves backward to the predecessor path if the predecessor path metric beats {{var|T}}; thereafter, threshold examination will be subsequently performed on another successor path of this revisited predecessor.