# Sequential Polar Decoding with Cost Metric Threshold
## 3 Our Contribution
### SC-Creper and Additional Threshold  
The recurrent procedure for the identification of nodes when moving forward is as follows. Let it be known for some node whether it is new or old. If a node is new, then all its descendants are, by definition, new nodes. If a node is old, then its descendants retain this gradation as long as their metrics are greater than or equal to the current \(\mu^{\prime}_{i}\) value (here, \(\mu^{\prime}_{i}\) is the current threshold with which node \(i\) was visited the penultimate time). The first child of a node whose metric has a value less than the cost of the given one \(\mu^{\prime}_{i}\) is new. Then, the recurrent procedure is repeated. As a criterion for changing the value at a vertex when moving forward, we can use one of the following conditions: either the parent vertex is a new node or a neighboring vertex in the tree, or the vertex itself will become a new node and update the cost by \(+\infty\). Suppose that, for some node \(i\), in addition to the metric \(\mu^{\prime}_{i}\), the metric \(\gamma_{i}\) from the \(\Gamma\)-function is also known. Then, for the sibling's metric of the cost function, the following equation is correct:  
Figure 1: SC-Creper scheme with cost metric \(\Gamma\). \[\gamma^{\prime}_{i}= \begin{cases}\infty,\ i\text{-th node is new,}\\ \mu^{\prime}_{i},\ \text{otherwise.}\end{cases}  \tag{3}\]  
As a controlled functional \(\Gamma\), it is necessary to consider models that satisfy the following relations:  
* \(\Gamma(l)=\Gamma(l^{\prime})=T(l^{\prime})\), \(l^{\prime}\leq l\) (maintaining the direction of movement of the decoder);
* \(\Gamma(l)=-\infty\), \(l<0\) (positive certainty);
* \(\Gamma(l)=\Gamma(l-1)\) if and only if the cost function is not updated (hence, \(T(l)=T(l-1)\)). A detailed description of SC-Creeper with cost function is contained in the Algorithm 1. This algorithm is based on the basic SC-Creeper, but steps are specified that include manipulation of metrics and stack recalculation. ```
0:\(y_{0}^{N-1}\)--received output LLRs, \(\Delta\)--Creeper step parameter, \(\Gamma(. )\)--cost  function definition, \(T(. )\)--threshold function definition;
0: estimated codeword with the path \(v_{i}\). \(v_{0}\)--the root of tree, \(\mu_{0}=T(v_{0})\), \(\Gamma(v_{0})=\gamma_{0}\); \(\mathcal{N}=\mathcal{T}=\varnothing\), \(i=0\), \(t=-\infty\), \(t^{\prime}=\infty\); while\(i<N\) or \(\mu_{i}>t+\Delta\)do \(i=i+1\);  Calculate PMF values \(\mu_{i}\), \(\mu^{\prime}_{i}\) and cost metrics \(\gamma_{i}\), \(\gamma^{\prime}_{i}\);  Current node is \(v_{i}\): \(t^{\prime}=\gamma_{i}\); if\(\gamma_{i}<t+\Delta\)then  Update \(\mathcal{T}\), \(\mathcal{N}\) stacks with the basic Creeper algorithm; \(push(\mathcal{T},\mu^{\prime}_{i})\), \(push(\mathcal{N},\gamma^{\prime}_{i})\); else \(push(\mathcal{T},\mu_{i})\), \(push(\mathcal{N},\gamma_{i})\); if\(-t^{\prime}=\infty\)then \(t=T(i)\); else \(t=\Gamma(i)\); endif else  Go to alternative node, \(i\)-th level: \(v_{alt}=Pos(\mathcal{N})\); \(t^{\prime}=\gamma^{\prime}_{i}\); if\(T(i)<\gamma_{i-1}+\Delta\)then \(t=\gamma_{i-1}\); endif  Update \(\mathcal{T}\), \(\mathcal{N}\) stacks with the basic Creeper algorithm; endif endwhile
```  
**Algorithm 1**SC-Creeper with cost function  
When viewing the branches of the code tree once, the operation of the decoder completely coincides with decoding according to the original algorithm. With repeated passes of the same branches, the control thresholds are lowered (there is some similarity here with the adaptive Fano algorithm [17]). This eliminates the side effect of the original version. At each iteration, updated Creeper decoding performs a local search within a neighborhood of the current decoding solution. This search explores nearby candidate solutions, evaluating their likelihood based on the received symbols and the properties of the error-correcting code. This version of the Creeper algorithm also provides a better \"lookup\" ability to return to vertices that the original Creeper would have already eliminated from its stack.