# Soft Decision Decoding with Cyclic Information Set and the Decoder Architecture for Cyclic Codes
## 3 Soft Decision Decoding Algorithm Based on Cyclic Information Set
### Efficient Iterative Generating Method for Adjacent Candidate Sequences  
The generation of the candidate information sequences and the metric calculation of candidate codewords are the main steps and have high computation complexity in the proposed soft decision decoding algorithm. For each information sequence, we only need to generate a small number, denoted as \(C\), of candidate information sequences to generate candidate codewords. Among all the \(2^{k}\) members, the candidate information sequences include \(C\) members, which have the most minimal correlation discrepancy with the information sequence. Aiming at reducing the complexity of generating candidate information sequences, an iterative algorithm is adopted to generate the candidate information sequence in this paper. This method avoids calculating the correlation discrepancies of all \(2^{k}\) sequences and sorting all the correlation discrepancies. This algorithm is first employed to calculate the log-likelihood ratio of non-binary symbols for non-binary low density parity check (LDPC) codes [55]. In this paper, this method is extended for the generation of candidate information sequences with some modifications. The algorithm works in the iterative mode with a total of \(k\) iterations. In the \(d\)-th iteration, the subsequence \(\mathbf{m}_{d}=(m_{0},m_{1},\cdots,m_{d-1})\), consisting of the first \(d\) components of the information sequence, needs to be considered. The set \(\varphi_{d}\) of the two-dimensional variables represents the generated partial binary sequence and its correlation discrepancy with \(\mathbf{m}_{d}\). If \(d=1\), \(\varphi_{1}=\{(u_{0},0),(\bar{u}_{0},|m_{0}|)\}\), where \(u_{0}\) represents the hard decision result of \(m_{0}\), \(\bar{u}_{0}\) represents the negative of \(u_{0}\). The calculation in the \(d\)-th iteration is divided into two steps. Take the \(l\)-th pair of elements, \(\varphi_{d}^{0}(l)\) and \(\varphi_{d}^{1}(l)\), as an example. Each element is expanded into two elements according to the \(d\)-th component \(m_{d-1}\) of the information sequence and the hard decision result \(u_{d-1}\). Extending the \(l\)-th element \((\mathbf{s}_{1}^{(d-1)},\lambda(\mathbf{m}_{d-1},\mathbf{s}_{l}^{(d-1)}))\) in \(\varphi_{d-1}\) to two elements \(\varphi_{d}^{0}(l)\) and \(\varphi_{d}^{1}(l)\) can be specifically expressed as  
\[ \begin{cases}\varphi_{d}^{0}(l)=(\mathbf{s}_{l}^{(d-1)}\&\kappa u_{d-1},\lambda( \mathbf{m}_{d-1},\mathbf{s}_{l}^{(d-1)})),\\ \varphi_{d}^{1}(l)=(\mathbf{s}_{l}^{(d-1)}\&\kappa\bar{u}_{d-1},\lambda(\mathbf{m}_{d- 1},\mathbf{s}_{l}^{(d-1)})+|m_{d-1}|),\end{cases}  \tag{10}\]  
where '\(\&\)' is the concatenation operation of two binary sequences. The two-dimensional variable sets \(\varphi_{d}^{0}\) and \(\varphi_{d}^{1}\) extended by \(\varphi_{d-1}\) can be obtained by calculating all \(\varphi_{d}^{0}(l)\) and \(\varphi_{d}^{1}(l)\). Then, the two sets \(\varphi_{d}^{0}\) and \(\varphi_{d}^{1}\) are merged to construct a new set \(\varphi_{d}\). It should be ensured that the elements in \(\varphi_{d}\) are arranged in descending order of the correlation discrepancy value. Considering that the algorithm is iterative, the elements in \(\varphi_{d}^{0}\) and \(\varphi_{d}^{1}\) are also in descending order. Therefore, only the first elements of the two sets that have not been placed into \(\varphi_{d}\) need to be compared and the element with smaller correlation discrepancy is put into the set \(\varphi_{d}\). When the number of elements in \(\varphi_{d}\) reaches the required number of candidate codewords, the construction of \(\varphi_{d}\) is stopped. After the \(k\)-th iteration, the first dimension component of each element in the obtained set \(\varphi_{k}\) constitutes \(C\) candidate sequences. The two main steps in the iterative algorithm are described in Algorithm 2. The candidate information sequences are the sequences with the minimum distance (correlation discrepancy) to the information sequence.