# Blind Interleaver Parameters Estimation Using Kolmogorov-Smirnov Test
## 1 Introduction  
The use of error correcting codes (ECCs) is essential for designing reliable digital communication systems. However, while ECCs helps to accurately transmit and receive information for random errors, it has relatively low probabilities to to correct burst errors. To improve the error correction performance for burst type errors, an interleaving technique is used to convert burst errors occurring in the channel into random errors [1]. For reconstructing the real bitstreams, the receiver has to find the structure and parameters of the channel code. A blind interleaver parameters estimation must be performed first, following which the other parameters can be easily deduced. A deinterleaving problem is usually considered in a non-cooperative context. Considering that receivers only know the intercepted sequences, blind interleaver parameters estimation algorithms exploit the fact that the codewords generated by ECCs have linear dependence [2, 3, 4, 5, 6]. In [2], Gaussian elimination is used to find the interleaver parameters. However, because this method does not consider channel noise, the performance of estimation deteriorates steeply as the number of errors increases. A blind interleaver parameters estimation algorithm that uses Gauss-Jordan elimination through pivoting and considers channel noises is described in [3]. This method finds almost dependent columns which have the minimum Hamming weight and uses it as a measure for predicting interleaver period. Some algorithms use the rank distribution of random square matrices, \(\rho\), as a criterion for blind interleaver parameters estimation [4, 5, 6]. In [7, 8], they estimate interleaver parameters using the variation of rank ratio depending on the column length of the matrix. These algorithms are based on the fact that the rank distribution of square matrices consisting ofcodewords, \(\rho_{C}\), is far different from \(\rho\). Because \(\rho\) follows a specific distribution, the interleaver period of the intercepted bitstreams can be estimated by comparing this distribution with \(\rho_{C}\). In [4], when \(s\) represents rank deficiency factor, which is the difference in ranks between the rank of the \(l\times l\) random binary square matrix, \(\Lambda\), and \(l\), they defined success events as the rank deficiency \(s\) is greater than \(2\), \(s>2\). The number of success events is used as a measure to estimate the interleaver periods by modeling \(\rho\) as a Bernoulli trial that classifies events into success and failure based on the rank values. In addition, the Kullback-Leibler divergence (KLD) was used as a measure for estimating the interleaver parameters [5]. KLD calculates the degree of rank distribution difference between random square matrices and square matrices of the intercepted stream. Further, KLD was also partially applied for false alarm control. In [9], maximum difference selection (MDS) is proposed by selecting vectors having fewer errors and they adopted KLD to control false alarm rates. As an extension to [4], more events are considered using Multinomial distributions [6]. Because multinomial distributions can calculate the probability that each event will occur, it predicts interleaver periods by finding the event that has the lowest probability. According to the methodology of the analytical and histogram approach, zero mean ratio values are used to estimate an interleaver period in [7]. Recently, normalized non-zero-mean-ratio values are introduced as a measure for estimation of interleaver period [8]. Also, blind interleaver parameters estimation algorithms have been proposed focused on the case of a short length of received data [10; 11]. In order to overcome degrading estimation performance caused by the lack of available data, they generated additional data by combining received data [10]. Then, the collected and generated data were used to construct matrices. The rank deficiency of the matrices can be utilized to estimate interleaver periods.