# Soft Decision Decoding with Cyclic Information Set and the Decoder Architecture for Cyclic Codes
## 4 The Architecture and Complexity Analysis of the Proposed Decoder
### Implementation Complexity of the Proposed Decoder  
Considering that the OSD algorithm is the most efficient and classical algorithm nearly achieving the ML decoding performance, the complexity evaluation is based on the comparison between the proposed algorithm and the OSD algorithm. Compared with the order-\(t\) OSD algorithm of the \(k\)-dimensional sequences in [16], the proposed algorithm effectively reduces the computation complexity, as the number of all the tested candidate codewords, \(I\cdot C\), is smaller than \(\sum_{i=0}^{t}\left(\begin{array}{c}k\\ i\end{array}\right)\). We utilize the (31, 21) BCH code as an example. Table 1 shows the size of the candidate codeword list for different decoding algorithms. The (31, 21) BCH code only requires 80 candidate codewords under the appropriate parameters, and the corresponding parameter optimization will be shown in Section 5.2 below. The proposed decoding algorithm can effectively reduce the number of the candidate codewords, compared with the OSD algorithm.  
For the re-encoding, the OSD algorithm needs to obtain the generator matrix for each candidate codeword through complex matrix operations. The proposed decoding algorithm employs the cyclic property of cyclic block codes, enabling the utilization of the uniform systematic generator matrix in re-encoding. The cyclic codes can be encoded using the very simple encoding circuits with shift-registers.  
All our implementations are on the Vertex-5 LX 110T Field Programmable Gate Array (FPGA) (xc5 vlx110t-1 ff1136), and the synthesis software is the XST program of ISE 13.2, all  
Figure 5: The architecture of the correlation discrepancy calculation unit.  
by Xilinx Inc. This FPGA chip is mainly used for high-performance general logic applications, containing 17,280 configurable slices and 128 block RAM blocks (BRAMs), where each slice has 4 LUTs and 4 flips-flops. The proposed hardware architecture is implemented on the FPGA platform using different parameters. The proposed soft decision decoding algorithm contains two very important parameters, that is, the number of information sequences, \(I\), and the number of candidate codewords, \(C\). As \(I\) increases, the number of computation operations, required to generate a list of candidate codewords, increases linearly. Another advantage is that the systolic arrays operate in parallel, and the operations are only limited by the number of candidate codewords, \(C\).  
To illustrate the required hardware resources of the decoder, Table 2 presents the main units for the key modules. Here, \(weight(g)\) is the weight of the generator polynomial for cyclic codes. The adder and comparators have the width of \((w+d)\) bits in the \(d\)-th PE. Furthermore, each processing element of the candidate sequence generator requires two FIFOs with the same size. In the \(d\)-th processing element (\(d\leq\lfloor\log_{2}C\rfloor\)), each FIFO has a width of \((w+d)\) bits and a depth of \(\left\{2^{d-1},C\right\}\), where \(w\) is the quantization bit width of correlation discrepancy. The total storage space of the FIFOs (in bits) can be expressed as  
\[M_{F}=2\cdot(\sum_{i=1}^{\lfloor\log_{2}C\rfloor}(2^{i-1}\cdot(w+i))+\sum_{i= \lfloor\log_{2}C\rfloor+1}^{k}(C\cdot(w+i))). \tag{14}\]