Determining the complexity of FH/SS sequence by approximate entropy

High complexity of frequency-hopping (FH)/spreadspectrum (SS) sequence is of great importance to high-security multiple-access communication systems, for it makes FH/SS sequence difficult to be analyzed. With the growing development in the design of FH/SS sequence in much wider fields, the wellknown complexity measuresiquestthe linear complexity (LC), the linear complexity profile (LCP) and the k-error linear complexity (k-error LC)iquestare widely used but not sufficient to evaluate the complexities of the sequences available, such as the cryptographical sequence and the chaotic sequence families. In this paper, a new complexity metric to evaluate the unpredictability of FH/SS sequence based on the approximate entropy (ApEn) is proposed in the view of the maximal randomness of the sequences with arbitrary length. And the theoretical bounds of the ApEn are derived from a probabilistic point of view. Simulations and analysis results show that, the proposed ApEn works effectively to discern the changing complexities of the FH/SS sequences with small number of samples, which provide superior performance over its candidates.

I. Introduction

FREQUENCY-hopping (FH)/spread-spectrum (SS) techniques are widely used in multi-user communication systems, where the security is always one of the most important factors to be considered. The construction of FH/SS codes has always been as much art as science. Besides good correlation properties, long period and uniform distribution, it is desirable to employ those sets of FH/SS patterns derived from the sequences with high complexities [1]–[7]. It is a fact that a persistent eavesdropper can obtain some samples and thereby get the pseudo-random sequence. Therefore, the FH/SS sequences must be computationally complex to be secure against common attacks, so that they are computationally infeasible to be recovered from a relatively short segment. The complexity of a finite, fully specified sequence usually refers to the difficulty in predicting or regenerating the given sequence. Most of the works in this area associated the complexity of a given sequence with that of an algorithm by which the sequence is to be generated [8]–[11], such as the nonlinear span that defines the complexity as the length of the shortest feedback shift register (FSR) of any order that generates the given sequence [10]. In order to determine the complexities of given sequences, great attentions have been focused on determining the linear complexity (LC) [12]–[15] because of its tractability, which is considered as a useful measure to evaluate the linear equivalence by the wellknown Berlekamp-Massey (BM) algorithm [16]. In fact, the sequences with high LC may be well approximated by those with very low LC up to a few different bits, based on which the linear complexity profile (LCP) is presented as a more effective measure [17]–[19], which is obtained by plotting the LCs of the sequence against the observation length. Another popular complexity measure motivated by the sequence with a few terms changed is the famous -error linear complexity (-error LC) [18]–[20].