# Design of A Parallel Decoding Method for LDPC Code Generated via Primitive Polynomial
## 3 Parallel Decoding Method for m-Sequence Codes
### Parallel Decoding Method with Multiple Sub-Decoders  
Now let us discuss the affection of short cycles on decoding first. In BP algorithm, the information of each node is transferred and iterated according to the connection relation of Tanner graph. If there exist short cycles in the Tanner graph, the information of nodes in the cycles cannot receive enough extrinsic information, resulting in overestimation of node information and errors in decoding results. Figure 2 shows information flows of short cycles in a Tanner graph, where Figure 2a,b are 4-cycle and 6-cycle cases respectively. The solid line represents the information transfer in the first iteration, while the segment line and dotted line represent the information flow in the second and third iteration, respectively. In Figure 2a, information is first passed to variable node \(v_{2}\) through the check node \(c_{1}\). In the second iteration, \(v_{2}\) passes the information back to \(v_{1}\) through \(c_{2}\). This is an information loop. Similarly, the 6-cycle case in Figure 2b completes a loop through 3 iterations. It can be seen from Figure 2, if the number of iterations is half of the girth, then the information flowing in a short cycle will not back to the original node. As a consequence, the overestimation problem caused by the short cycle will never happen. However, if the iteration times of BP algorithm is set as half of the girth of parity-check matrix, the BP decoding algorithm is hardly to output a codeword. To tackle this difficult, this paper proposes a new parallel decoding method whose decoding structure is shown in Figure 3.  
The sub-decoders of the designed parallel decoding method are of two types. The first type of sub-decoder \(D_{0}\) only contains the decoding module that directly outputs the codeword \(\hat{\mathfrak{c}}_{0}\). The parity-check matrix employed by decoding module is the basic parity-check matrix \(H_{0}\). The second type of sub-decoders \(D_{i}\), \(i=1,2,\cdots,N\) are composed by a pre-decode module and a decoding module. In these sub-decoders, after receiving LLR \(\mathbf{L}_{ch}\) of channel received value \(\mathbf{y}\), the pre-decode module uses the BP algorithm to output extrinsic information \(\mathbf{L}_{xx}^{i}\). The employed parity-check matrix \(H_{i}\) is generated by Algorithm 1. The number of iterations in the pre-decode module is set as half of the girth of \(H_{i}\). Therefore, \(\mathbf{L}_{xx}^{i}\) is not affected by the cycle structure of \(H_{i}\). Then, \(\mathbf{L}_{xx}^{i}\) plus \(\mathbf{L}_{ch}\) is sent into the decoding module to get candidate codeword \(\hat{\mathfrak{c}}_{i}\) by BP decoding with \(H_{0}\). Figure 3: The structure of parallel decoding method. Figure 2: Information flows of short cycles in a Tanner graph. (**a**) 4-cycle. (**b**) 6-cycle. The pre-decode modules employ different parity-check matrices, resulting in different outputted extrinsic information. It enables the decoding modules to output different candidate codewords, which are valuable for the LMS to choose the best final codeword. The parallel decoding method is summarized in Algorithm 2, where \(BP_{h}(H,\mathbf{L},t)\) and \(BP_{s}(H,\mathbf{L},t)\) represents that using BP algorithm with parity-check matrix \(H\) to decode the input LLR \(\mathbf{L}\). The maximum iteration number ist. The output is hard decision sequence for \(BP_{h}(H,\mathbf{L},t)\) and soft extrinsic information for \(BP_{s}(H,\mathbf{L},t)\), respectively. In Algorithm 2, the LLR value \(\mathbf{L}_{ch}\) of channel output is simultaneously entered into \(N+1\) sub-decoders. Then these sub-decoders \(D_{i}\), \(i=0,1,\cdots,N\) output the candidate codewords \(\mathbf{\hat{c}}_{i}\) respectively. Let \(S\) be the set of candidates which satisfy \(H_{0}\mathbf{\hat{c}}_{i}^{T}=0\). If \(S=\emptyset\), then let \(S=\{\delta_{0},\mathbf{\hat{c}}_{1},\mathbf{\hat{c}}_{2},\cdots,\mathbf{\hat{c }}_{N}\}\) be the set of all candidates. The decoding result \(\mathbf{\hat{c}}\) is selected from \(S\) by an LMS with MAP rule.