Forward-Backward Algorithm for Boxplus Algorithm
Published:
Introduction
Assume that you are using boxplus algorim to calulate check-to-varible (C2V) messages for check node $c$ that connects 4 variable nodes $v_1$, $v_2$, $v_3$ and $v_4$. Let \(u_{c\rightarrow v_j}\) and \(l_{v_j \rightarrow c}\) be the C2V and variable-to-check (V2C) messages, respectively. Hence, the check node will do the following calculations:
\[\begin{aligned} u_{c\rightarrow v_1} &= l_{v_2 \rightarrow c} \boxplus l_{v_3 \rightarrow c} \boxplus l_{v_4 \rightarrow c} \\ u_{c\rightarrow v_2} &= l_{v_1 \rightarrow c} \boxplus l_{v_3 \rightarrow c} \boxplus l_{v_4 \rightarrow c} \\ u_{c\rightarrow v_3} &= l_{v_1 \rightarrow c} \boxplus l_{v_2 \rightarrow c} \boxplus l_{v_4 \rightarrow c} \\ u_{c\rightarrow v_4} &= l_{v_1 \rightarrow c} \boxplus l_{v_2 \rightarrow c} \boxplus l_{v_3 \rightarrow c} \\ \end{aligned}\]It can be seen that the time complexity to calculate C2V messages for a degree-\(d_c\) check node is propotional to \(d_c^2\).
The Forward-Backward algorithm allow to calulate C2V messages with a time complexity that is linear to \(d_c\).
Attached is the forward-backward algorithm. unfortunately, I didn’t find a reference for this algorithm. If you find the source, please let me know and I can cite here.