# Soft Decision Decoding with Cyclic Information Set and the Decoder Architecture for Cyclic Codes
## 4 The Architecture and Complexity Analysis of the Proposed Decoder
### Architecture of the Correlation Discrepancy Calculation Unit  
The correlation discrepancy calculation unit computes the correlation discrepancy between candidate codeword \(\mathbf{v}_{l}=(v_{l,0},v_{l,1},\cdots,v_{l,n-1})\), \((1\leq l\leq C)\) and the received soft information sequence \(\mathbf{r}^{(i)}=(r_{0}^{(i)},r_{1}^{(i)},\cdots,r_{n-1}^{(i)})\). To simplify the hardware implementation, we consider the calculation of the correlation discrepancy corresponding to the part of the first \(k\) bits and the part of the last \((n-k)\) bits. The formula for calculating the correlation discrepancy can be expressed as  
\[\lambda\left(\mathbf{r}^{(i)},\mathbf{v}_{l}\right)=\sum_{j:u_{j}^{(i)}\in v_{j},j=1}| r_{j}^{(i)}|=\sum_{j=0}^{k-1}|r_{j}^{(i)}|\times(u_{j}^{(i)}\oplus v_{l,j})+ \sum_{j=k}^{n-1}|r_{j}^{(i)}|\times(u_{j}^{(i)}\oplus v_{l,j}), \tag{11}\]  
or concisely denoted as  
\[\lambda(\mathbf{r}^{(i)},\mathbf{v}_{l})=\lambda(\mathbf{m}^{(i)},\mathbf{s}_{l})+\lambda(\bm {p}^{(i)},\mathbf{q}_{l}). \tag{12}\]  
Here, \(\mathbf{r}^{(i)}=(\mathbf{m}^{(i)},\mathbf{p}^{(i)})\). \(\mathbf{u}^{(i)}=(u_{0}^{(i)},u_{1}^{(i)},\cdots,u_{n-1}^{(i)})\) is the hard decision result of \(\mathbf{r}^{(i)}\). The soft information sequence associated to the information bits is denoted as \(\mathbf{m}^{(i)}\), i.e., \(\mathbf{m}^{(i)}=(r_{0}^{(i)},r_{1}^{(i)},\cdots,r_{k-1}^{(i)})\), while \(\mathbf{p}^{(i)}\)\(=(r_{k}^{(i)},r_{k+1}^{(i)},\cdots,r_{n-1}^{(i)})\) is the part of the soft information sequence associated to the parity-check bits. Similarly, the candidate codeword \(\mathbf{v}_{l}\) is denoted as \(\mathbf{v}_{l}=(\mathbf{s}_{l},\mathbf{q}_{l})\). \(\mathbf{s}_{l}\) denotes the candidate information sequence associated with the information bits and \(\mathbf{s}_{l}=(v_{l,0},v_{l,1},\cdots,v_{l,k-1})\), while \(\mathbf{q}_{l}=(v_{l,k},v_{l,k+1},\cdots,v_{l,n-1})\). It can be observed that the first term in Equation (12) is the correlation discrepancy between the information sequence and the corresponding candidate sequence. The correlation discrepancy calculation unit only needs to calculate the second term \(\lambda(\mathbf{p}^{(i)},\mathbf{q}_{l})\). Considering the high computation complexity, our proposed correlation discrepancy calculation unit uses a systolic array architecture for sequential calculation. The architecture is shown in Figure 5, which consists of \((n-k)\) identical PEs. Taking the \(d\)-th PE as an example, the inputs are the soft information \(r_{k+d-1}^{(i)}\) with its corresponding hard decision result \(u_{k+d-1}^{(i)}\) and the list \(\xi_{d-1}\) from the previous PE. The \(d\)-th PE generates the list \(\xi_{d}\) as an output that is serially sent to the \((d+1)\)-th PE of the next stage. \(\xi_{d}\) (\(0\leq d\leq n-k\)) is a set containing \(C\) two-dimensional variables. The \(l\)-th two-dimensional variable of the set can be expressed as  
\[\xi_{d}(l)= \begin{cases}\left(v_{l},\lambda\left(\mathbf{m^{(i)}},\mathbf{s}_{l}\right) \right),d=0.\\ \\ \left(v_{l},\lambda\left(\mathbf{m^{(i)}},\mathbf{s}_{l}\right)+\sum\limits_{j=k}^{k+d -1}|r_{j}^{(i)}|\times\left(u_{j}^{(i)}\oplus v_{l,j}\right)\right),\ \ \ 1\leq d\leq n-k.\end{cases}  \tag{13}\]  
In the Formula (13), the first dimension variable of \(\xi_{d}(l)\) is the candidate codeword \(v_{l}\), and the second dimension variable is the correlation discrepancy between the first \((k+d)\) components of \(\mathbf{r}^{(i)}\) and the first \((k+d)\) bits of \(\mathbf{v}_{l}\). As shown in Figure 5, the architecture of the \(d\)-th PE is composed of an expansion unit, an XOR gate, and a data selector. The XOR operation generates the selection signal for the data selector. If \(u_{k+d-1}^{(i)}\oplus v_{l,k+d-1}=0\), select \(\left(0,u_{k+d-1}^{(i)}\right)\) to expand \(\xi_{d-1}(l)\), otherwise, if \(u_{k+d-1}^{(i)}\oplus v_{l,k+d-1}=1\), select \(\left(|r_{k+d-1}^{(i)}|,\bar{u}_{k+d-1}^{(i)}\right)\) to expand \(\xi_{d-1}(l)\) to obtain \(\xi_{d}(l)\).