# Design of Encoding Algorithm for Underwater Wireless Optical Communication Based on Spinal Code
## 4 Theoretical Complexity Analysis of Superposition UEP-Spinal Code  
Let \(\mathrm{E_{R}}\) and \(\mathrm{E_{S}}\) represent the encoding complexity after RNG mapping with the Spinal code and the Superposition UEP-Spinal Code, respectively. Similarly, \(\mathrm{C_{R}}\) and \(\mathrm{C_{S}}\) denote the decoding complexity after RNG mapping with the Spinal code and the Superposition UEP-Spinal Code, respectively. \(T_{R}\) and \(T_{S}\) represents the bubble complexity of the Spinal code and the Superposition UEP-Spinal Code; The complexity of generating a hash function of length \(v\) is \(O(v+k)\), where \(v\) is the length of the generated hash function and \(k\) is the block length of the original signal input to the hash function. The complexity of mapping to a random sequence of length \(l\) through RNG is \(O(v+k+l)\). Thus, the encoding complexity of the Spinal code after RNG mapping can be derived as follows:  
\[E_{R}=O(\frac{n}{k}(v+k+l)) \tag{10}\]  
where \(n\) is the original signal length. The decoding complexity and recognition time can be expressed as follows:  
\[C_{R}=O(\frac{n}{k}B_{F}2^{k}(v+k+\mathrm{lg}B_{F}+l)) \tag{11}\]  
\[ \begin{array}{l}T_{R}=\frac{n}{k}B_{F}2^{k}(v+k+\mathrm{lg}B_{F}+l)T_{h}\\ \leq\frac{n}{k}B2^{k}(v+k+\mathrm{lg}B+l)T_{h}\end{array}  \tag{12}\]  
Among them, \(T_{h}\) is the time required for the hash function to generate a single hash value, \(B\) is the number of optimal nodes retained during each decoding, \(\mathrm{lg}B\) is the complexity of the Fano metric used in decoding, and \(B_{F}\leq B\) represents the number of nodes expanded during decoding, meaning that the maximum number of demodulations for Spinal codes will not exceed \(B2^{k}\). In each layer, decoding ultimately selects the best node from the \(B_{F}\) candidate nodes, i.e., the lower bound of \(T_{R}\) is  
\[T_{R}\geq\frac{n}{k}2^{k}(v+k+l)T_{h} \tag{13}\]  
In the encoding of the Superposition UEP-Spinal Code, the original signal is divided into \(m_{m}\) and \(m_{l}\) for encoding; the encoding complexities \(E_{Sm}\) and \(E_{Sl}\) for \(m_{m}\) and \(m_{l}\) are the following:  
\[E_{Sm}=O(\frac{n_{m}}{k_{1}}(v+k_{1}+c)) \tag{14}\]\[E_{Sl}=O(\frac{n_{l}}{k_{2}}(v+k_{2}+k_{3})) \tag{15}\]  
where \(c\) is the time complexity of generating the check bits after the hash function generates the hash value for the \(m_{m}\) signal; \(n_{m}\) is the code length of \(m_{m}\), \(n_{l}\) is the code length of \(m_{l}\) and \(n_{m}+n_{l}=n\); \(k_{1}\) is the block length of \(m_{m}\), and \(k_{2}\) is the block length of \(m_{l}\). The total encoding complexity of the Superposition UEP-Spinal Code is  
\[E_{S}=O(\frac{n_{m}}{k_{1}}(v+k_{1}+c)+\frac{n_{l}}{k_{2}}(v+k_{2}+k_{3})) \tag{16}\]  
Since the elements in the weight factor matrix \(P\) affect the information content of \(m_{m}\) and \(m_{l}\) in the final encoding, thereby influencing the protection effectiveness of the transmitted \(m_{m}\) and \(m_{l}\) and the number of nodes expanded during decoding, the number of demodulation expanded nodes \(B_{Fm}\) for \(m_{m}\) and \(B_{Fl}\) for \(m_{l}\) will vary depending on the elements in \(P\). The decoding complexities \(C_{Sm}\) and \(C_{Sl}\) for \(m_{m}\) and \(m_{l}\) in the Superposition UEP-Spinal Code are, respectively  
\[C_{Sm}=O(\frac{n_{m}}{k_{1}}B_{Fm}2^{k_{1}}(v+k_{1}+\lg B_{Fm}+c)) \tag{17}\]  
\[C_{Sl}=O(\frac{n_{l}}{k_{2}}B_{Fl}2^{k_{2}}(v+k_{2}+k_{3}+\lg B_{Fl})) \tag{18}\]  
The total decoding time \(T_{S}\) is  
\[ \begin{array}{ll}T_{Sm}=\frac{n_{m}}{k_{1}}B_{Fm}2^{k_{1}}(v+k_{1}+\lg B_{ Fm}+c)T_{hm}\\ \leq\frac{n_{m}}{k_{1}}B2^{k_{1}}(v+k_{1}+\lg B+c)T_{hm}\end{array}  \tag{19}\]  
\[ \begin{array}{ll}T_{Sl}=\frac{n_{l}}{k_{2}}B_{Fl}2^{k_{2}}(v+k_{2}+k_{3}+ \lg B_{Fl})T_{hl}\\ \leq\frac{n_{l}}{k_{2}}B2^{k_{2}}(v+k_{2}+k_{3}+\lg B)T_{hl}\end{array}  \tag{20}\]  
\[