# Blind Interleaver Parameters Estimation Using Kolmogorov-Smirnov Test
## 3 Proposed Algorithm
### Proposed Algorithm  
Motivated by the foregoing observations, this subsection describes how to exploit rank distributions to estimate interleaver periods in detail. First, to exploit rank distributions for interleaver period estimation, the rank distribution must be obtained.  
We describe the process of getting rank distribution as shown in Figure 4. Given the received bitstream, \(l\) vectors of length \(l\) are randomly selected to construct \(\Lambda\) and the rank distribution is calculated by counting the rank of the matrices \(N\) times.  
Sufficiently large \(N\) shall be considered to guarantee reliable rank distributions. For example, if \(N\) is set to 10,000, we must receive a captured sequence of length at least 280,000  
Figure 3: Illustration of the K–S statistic. The black arrow is the two-sample K–S statistic.  
when the interleaver period is 28. To resolve this excessive requirement, we exploited the linearity of linear codes; i.e., the sum of two codewords is also a codeword.  
Then, we use the K-S test as a measure of the probability matching problem. In other words, we find \(l\) which has the most different distribution from that of random square matrices. Equation (5) represents how we can predict interleaver period exploiting K-S test.  
\[l_{S}=\operatorname*{arg\,max}_{l}D_{l}=\operatorname*{arg\,max}_{l}sup_{x_{l }}|P_{ran}(x_{l})-Q_{con}(x_{l})| \tag{5}\]  
where \(P_{ran}\) represents the CDF of the rank distribution from the random square matrices and \(Q_{con}\) represents the CDF of the rank distribution from constructed square matrices, respectively.  
If \(l\) is not equal to the interleaver period, \(S\), there is no linear dependence in the rows of the constructed matrix. Therefore, the distribution may follow that shown in Table 1 with high probability. This results in the K-S test value, \(D_{l}\), converging to near zero.  
On the contrary, if \(l\) equals \(S\), the rows of \(\Lambda\) consist of codewords. The distribution is totally different from that given in Table 1 owing to the linear dependence of the codewords. Therefore, \(D_{l}\) can reach the maximum value and \(l\) can be predicted as the interleaver period.  
Finally, multinomial distribution is used for false alarm control. It ensures that the probability of the rank distribution at that time is lower than a threshold, which is sufficient to judge that it does not happen by chance. The proposed algorithm is summarized in Algorithm 1.  
Figure 4: Processes used to obtain the rank distribution from the received bitstream.  
```
0: received sequence \(\mathbf{r}\), translate parameter \(d=0\), predicted interleaver period \(l=7\)
0: estimated interleaver period \(l_{S}\)
1: Translate the received sequence by the length \(d\).
2: Divide the translated sequence by the length \(l\).
3: Randomly select \(l\) vectors and construct an \(l\times l\) square matrix \(\Lambda\).
4: Calculate the rank of the matrix.
5: Repeat the third and the fourth steps \(N\) times.
6: Construct rank distribution \(R_{l}^{i}\)
7:if\(d<l-1\)then Go to the first step with increment \(d\) as \(d\)+1.
8:if\(l<S+1\)then Set \(d\) to 0.
9: Go to the first step with increment \(l\) as \(l\)+1.
10: Compute (5) and declare \(l_{S}\) to be an interleaver period.
```  
**Algorithm 1** Proposed Algorithm