# Design of A Parallel Decoding Method for LDPC Code Generated via Primitive Polynomial
## 3 Parallel Decoding Method for m-Sequence Codes
### Construction of Parity-Check Matrices  
Finite field \(\mathbf{GF}(2^{k})\) can be represented by the powers of a primitive element \(\alpha\), i.e.,  
\[\mathbf{GF}(2^{k})=\{\alpha^{-1}=0,\;\alpha^{0}=1,\;\alpha,\;\alpha^{2}, \cdots,\;\alpha^{2^{k}-2}\}. \tag{8}\]  
Consequently, \(\alpha^{q}\in\mathbf{GF}(2^{k})\) is the primitive elements of this finite field if and only if \(gcd(q,2^{k}-1)=1\)[11], where \(gcd(a,b)\) is the greatest common divisor of \(a\) and \(b\). The new primitive element \(\alpha^{q}\) can regenerate \(\mathbf{GF}(2^{k})\) as follows.  
\[\mathbf{GF}(2^{k})=\{\left(\alpha^{q}\right)^{-1}=0,\left(\alpha^{q}\right)^{ 0}=1,\alpha^{q},\left(\alpha^{q}\right)^{2},\cdots,\left(\alpha^{q}\right)^{2 ^{k}-2}\}. \tag{9}\]  
Let \(f_{q}(x)\) be the primitive polynomial of which \(\alpha^{q}\) is a root,  
\[f_{q}(x)=x^{k}+\sum_{i=1}^{k-1}b_{i}x^{i}+1,\;b_{i}\in\{0,1\}. \tag{10}\]  
Polynomial \(f_{q}(x)\) is then used to generate a new m-sequence \((a_{i}^{(q)})\) with the same initial phase \(\beta\). Thus, sequence \((a_{i}^{(q)})\) meets the following constraints  
\[a_{i}^{(q)}+\sum_{j=1}^{k-1}b_{j}a_{i+j}^{(q)}+a_{i+k}^{(q)}=0. \tag{11}\]  
Figure 1: The structure of multiple-based belief propagation (MBBP) algorithm.  
In addition, using the trace function, we have  
\[a_{i}^{(q)}=tr_{1}^{k}(\beta(\alpha^{q})^{i})=a_{qi}. \tag{12}\]  
Now, it is clearly shown from (12) that the parity-check constraints of \(f_{q}(x)\) can be used to check the codeword \((a_{i})_{i=0}^{n-1}\)  
\[a_{i}+\sum_{j=1}^{k-1}b_{j}a_{i+qj}+a_{i+qk}=0,\;i=0,\;1,\cdots,\;n-qk-1 \tag{13}\]  
Based on the above analysis, we design a construction method of parity-check matrices as Algorithm 1 shown, where \(BM((a_{i}))\) is the function that using Berlekamp-Messey (BM) algorithm [12] to get the minimum generating polynomial of \((a_{i})\). \(Matrix(f_{q}(x),n)\) is the function to use \(f_{q}(x)\) to construct a parity-check matrix with code length n by cyclic shift as (13).  
In Algorithm 1, we first find all the candidate sampling intervals that are relatively prime with \(2^{k}-1\). Then we generate a segment of m-sequence \((a_{i})_{i=0}^{1000k}\) with length \(1000k\) to get the sampling segment \((a_{i}^{(q)})_{i=0}^{1000k/q}\) by the sampling interval \(q\). The BM algorithm can be employed to find the maximum generating polynomial \(f_{q}(x)\) of \((a_{i}^{(q)})_{i=0}^{1000k/q}\). Finally, we use \(f_{q}(x)\) to construct a parity-check matrix through the way of (13).  
```
0: A primitive polynomial \(f(x)\);  A code length \(n\).
0: The parity-check matrices \(H_{i},i=1,2,\cdots,N\).
1: Begin procedure
2: Initialize: Let \(Q\) be the set of sampling interval, \(k\) is the order of \(f(x)\), counter \(cnt=1\).
3:for\(i:=2\); \(i<\lfloor\frac{n}{k}\rfloor\); \(i++\)do
4:if\(gcd(i,2^{k}-1)=1\)then
5:\(Q=Q\cup\{i\}\).
6:endif
7:endfor
8: Generate an m-sequence \((a_{i})_{i=0}^{1000k}\) via \(f(x)\).
9:for\(q\in Q\)do
10: Sample \((a_{i})_{i=0}^{1000k}\) with sampling interval \(q\) to get \((a_{i}^{(q)})_{i=0}^{1000k/q}\).
11:\(f_{q}(x)=BM((a_{i}^{(q)})_{i=0}^{1000k/q})\).
12:\(H_{cnt}=Matrix(f_{q}(x),n)\).
13:\(cnt=cnt+1\).
14:endfor
15:return\(H_{i},i=1,2,\cdots,N\).
```  
**Algorithm 1**Construction of parity-check matrices for m-sequence code  
The parity-check matrix generated by this method is the result of cyclic shift of one parity-check constraint. Therefore, it has too many short cycles to be equipped into the sub-decoders of the MBBP algorithm. To take full advantage of the parity-check matrices, we thus design a new parallel decoding method in the next subsection.