Concatenation of pseudorandom binary sequences
- PDF / 202,676 Bytes
- 22 Pages / 595 x 842 pts (A4) Page_size
- 107 Downloads / 213 Views
CONCATENATION OF PSEUDORANDOM BINARY SEQUENCES Katalin Gyarmati1 [Communicated by Attila Peth˝ o] E¨ otv¨ os Lor´ and University, Department of Algebra and Number Theory H-1117 Budapest, P´ azm´ any P´eter s´et´ any 1/c, Hungary E-mail: [email protected] (Received July 28, 2008; Accepted November 5, 2008)
Abstract In the applications it may occur that our initial pseudorandom binary sequence turns out to be not long enough, thus we have to take the concatenation or merging of it with other pseudorandom binary sequences. Here our goal is study when we can form the concatenation of several pseudorandom binary sequences belonging to a given family? We introduce and study new measures which can be used for answering this question.
1. Introduction In a series of papers C. Mauduit and A. S´ark¨ozy (partly with coauthors) studied finite pseudorandom binary sequences EN = {e1 , e2 , . . . , eN } ∈ {−1, +1}N . In particular, in part I [14] first they introduced the following measures of pseudorandomness: Write t−1 X U (EN , t, a, b) = ea+jb j=0
and, for D = (d1 , . . . , dk ) with non-negative integers d1 < · · · < dk , V (EN , M, D) =
M X
en+d1 en+d2 · · · en+dk .
(1)
n=1
Mathematics subject classification number : 11K45. Key words and phrases: pseudorandom, concatenation, correlation. 1
Research partially supported by Hungarian NFSR, Grants No. K49693, K67676, K72264 and the J´ anos Bolyai Research Fellowship. 0031-5303/2009/$20.00
c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
100
K. GYARMATI
Then the well-distribution measure of EN is defined as t−1 X ea+jb , W (EN ) = max |U (EN (t, a, b)| = max a,b,t
a,b,t
j=0
where the maximum is taken over all a, b, t such that a, b, t ∈ N and 1 ≤ a ≤ a + (t − 1)b ≤ N , while the correlation measure of order k of EN is defined as M X en+d1 en+d2 · · · en+dk Ck (EN ) = max |V (EN , M, D)| = max M,D
M,D
(2)
n=1
where the maximum is taken over all D = (d1 , d2 , . . . , dk ) and M such that 1 ≤ d1 < d2 < · · · < dk < M + dk ≤ N . Then the sequence EN is considered a “good” pseudorandom sequence if both these measures W (EN ) and Ck (EN ) (at least for small k) are “small” in terms of N (in particular, both are o(N ) as N → ∞). The goal of this paper is to introduce new measures of families of binary sequences. First Anantharam [3] studied the correlation measure of a family. Here we will extend his definition. We may expect that if the correlation measure of a family is small, then the sequences in the family are independent in some sense. Definition 1. Let F ⊆ {−1, +1}N be a large family of pseudorandom binary sequences. The f -correlation measure of order k of F is defined by def
Ck (F) =
max
1≤ℓ≤k,
(1) (2) (ℓ) EN ,EN ,...,EN
(1)
(2)
(ℓ)
Ck ({EN , EN , . . . , EN }), (1)
(2)
(ℓ)
where the maximum is taken over all 1 ≤ ℓ ≤ k, different EN , EN , . . . , EN ∈ F, (1) (2) (ℓ) and where {EN , EN , . . . , EN } ∈ {−1, +1}ℓN is a binary sequence of length ℓN (1) (2) (ℓ) obtained by writing the elements of EN , EN , . . . , EN
Data Loading...
