# Soft Decision Decoding with Cyclic Information Set and the Decoder Architecture for Cyclic Codes
## 3 Soft Decision Decoding Algorithm Based on Cyclic Information Set
### The Proposed Soft Decision Decoding Algorithm  
In this paper, multiple information sequences are used for re-encoding to generate the candidate codewords. We generate the information set using the cyclic property of the cyclic codes. The proposed soft decision decoding algorithm is depicted in Figure 1. Assuming that the received soft information sequence is \(\mathbf{r}=(r_{0},r_{1},\cdots,r_{n-1})\). First, the \((l-1)\) circular shifts are performed on \(\mathbf{r}\) to obtain \(n\)-dimensional soft information sequences \(\mathbf{r}^{(i_{1})},\mathbf{r}^{(i_{2})},\cdots,\mathbf{r}^{(i_{l-1})}\), where \(i_{1},i_{2},\cdots i_{l-1}\) denote the number of circular shifts. Then, the first k components in \(\mathbf{r}\), \(\mathbf{r}^{(i_{1})},\mathbf{r}^{(i_{2})},\cdots,\mathbf{r}^{(i_{l-1})}\) are selected to form the \(k\)-dimensional sequences \(\mathbf{m}^{(0)},\mathbf{m}^{(i_{1})},\cdots,\mathbf{m}^{(i_{l-1})}\), namely the information sequences. The information sequences represent the equivalent information bits in the codewords. The process of generating multiple information sequences by circularly shifting is shown in Figure 2. For each information sequence \(\mathbf{m}^{(l)}\), a group of \(k\)-dimensional sequences with the minimum correlation discrepancy to \(\mathbf{m}^{(i)}\) are obtained, denoted as \(\mathbf{s}_{j}^{(i)}(1\leq j\leq C)\), where the correlation discrepancy is calculated by the hard decision of the corresponding information sequence. All candidate information sequences are encoded to yield \(l\cdot C\) candidate codewords via the cyclic encoding method. In essence, the codewords of the cyclic code are still legitimate after circular shifting. The information sequence corresponding to each candidate information sequence is obtained by the circular shifting of \(\mathbf{r}^{(i)}\). The simple encoding circuits of cyclic codes can be used to encode the candidate information sequence based on the encoder using shift-registers [12]. This method saved the burden of computing the new generator matrices. Finally, the candidate codeword with the minimum correlation discrepancy to the corresponding information sequence in the received channel observation soft information sequence \(\mathbf{r},\mathbf{r}^{(i_{1})},\mathbf{r}^{(i_{2})},\cdots,\mathbf{r}^{(i_{l-1})}\)is selected as the optimal candidate codeword. If the candidate codeword is generated by the information sequence \(\mathbf{m}^{(0)}=\mathbf{m}\) from \(\mathbf{r}\), it is directly selected as the optimal decoding result. Otherwise, the candidate codeword needs to be circularly shifted to obtain the optimal decoding result. The four main steps of the algorithm are summarized in Algorithm 1. ```
Input: the received soft information sequence \(\mathbf{r}=(r_{0},r_{1},\cdots,r_{n-1})\). Output: the optimal decoding result. 1. Generate \(I\) independent information sequences. 1. Circularly shift \(\mathbf{r}\) uniformly, and obtain \(\mathbf{r}^{(i_{1})},\mathbf{r}^{(i_{2})},\cdots,\mathbf{r}^{(i_{l-1})}\). 1.2 Take the first \(k\) components of \(\{\mathbf{r},\mathbf{r}^{(i_{1})},\mathbf{r}^{(i_{2})},\cdots,\mathbf{r}^{(i_{l-1})}\}\) to generate the information sequences \(\mathbf{m}^{(0)},\mathbf{m}^{(i_{1})},\cdots,\mathbf{m}^{(i_{l-1})}\). 2. For each information sequence \(\mathbf{m}^{(i)}\), generate \(C\) candidate information sequences with the minimum correlation discrepancy, i.e., \(\mathbf{s}^{(i)}_{1},\mathbf{s}^{(i)}_{2},\cdots,\mathbf{s}^{(i)}_{C}\). 3. Encode the candidate sequences to obtain candidate codewords. 4. Select the optimal candidate codeword and make a decision. 4.1 Select the candidate codeword with the minimum correlation discrepancy and obtain the associated information sequence in \(\{\mathbf{r},\mathbf{r}^{(i_{1})},\mathbf{r}^{(i_{2})},\cdots,\mathbf{r}^{(i_{l-1})}\}\). 4.2 If the codeword is generated by \(\mathbf{m}^{(0)}=\mathbf{m}\), it is directly used as the decoding result. Otherwise, it is circularly shifted to obtain the decoding result.