Iterative message-passing-based algorithms to detect spreading codes

(1)

U  P

D  I ’I:

E, I, T

Doctorate inI E Curriculum inC S

Iterative Message-Passing-Based

Algorithms to Detect Spreading Codes

Presented by:

F P

. . . .

Supervisor:

Prof. Marco Luise

. . . .

Accepted by: Doctorate Council of Dip. di Ingegneria dell’Informazione

President: Prof. Lanfranco Lopriore

(2)

(3)

... to my father, I miss you ...

(4)

(5)

Acknowledgements

I would like to thank Margherita, because during these three years she has been always with me. She has lovingly supported me in bad times and enjoyed happy moments with me.

I thank my mother and my brother because they have always believed in my capabili-ties and skills, so approving and supporting every my decisions and work experiences.

I thank Prof. Marco Luise for his precious suggestions and for the great working en-vironment, that he have created with the collaboration of the DSP-lab staff. It has been a wonderful experience working together!

I would like to thank Prof. Keith M. Chugg and his staff for the opportunity that they gave me to visit USC and LA, their great hospitality, and the precious help and collabo-ration to perform the research topic, which is the base of this thesis.

Thank you very much!!!

(6)

(7)

Abstract

This thesis tackles the issue of the rapid acquisition of spreading codes in Direct-Sequence Spread-Spectrum (DS/SS) communication systems. In particular, a new algorithm is pro-posed that exploits the experience of the iterative decoding of modern codes (LDPC and turbo codes) to detect these sequences. This new method is a Message-Passing-based

algorithm. In other words, instead of correlating the received signal with local replicas

of the transmitted linear feedback shift register (LFSR) sequence, an iterative Message-Passing (iMP) algorithm is implemented to be run on a loopy graph. In particular, these graphical models are designed by manipulating the generating polynomial structure of the considered LFSR sequence. Therefore, this contribution is a detailed analysis of the detection technique based on Message-Passing (MP) algorithms to acquire m-Sequences and Gold codes. More in detail, a unified treatment to design and implement a specific set of graphical models for these codes is reported. A theoretical study on the acquisition time performance and their comparison to the standard algorithms (full-parallel, simple-serial, and hybrid searches) is done. A preliminary architectural design is also provided. Finally, the analysis is also enriched by comparing this new technique to the standard algorithms in terms of computational complexity and (missed/wrong/correct) acquisition probabilities as derived by simulations.

(8)

(9)

List of Figures

2.1 Generic configuration of a FSR generator. . . 9

2.2 GPS/SBAS Gold code generator. . . 32

3.1 DS/SS communication system model. . . 34

3.2 General representation of an r -stage LFSR generator. . . . 35

3.3 An example of a tracking stage in a DS/SS receiver. . . 38

3.4 A general design of a coherent single-dwell detector. . . 40

3.5 A simplified scheme of a full-parallel algorithm. . . 42

3.6 A simplified scheme of a simple-serial algorithm. . . 44

3.7 A simplified scheme of a hybrid search. . . 47

4.1 Iterative Detection Unit with an iMP algorithm. . . 52

4.2 Main stages of the iDU. . . 55

4.3 An example of TG. . . 57

4.4 An example of a free-loop graph. . . 60

4.5 Markov chain of an iDU with all stages. . . 65

4.6 A simplified flow graph of an iDU. . . 67 xi

(14)

5.1 Performance in case of the m-sequence [15341]8(r = 12). . . . 80

5.2 Performance in case of the GPS/SBAS codes. . . 82

5.3 Multi-TGs activation schedule. . . 84

5.4 Comparison between the two activation schedules. . . 84

5.5 Example of hierarchical model for GPS/SBAS codes. . . 87

5.6 Hierarchical model performance. . . 87

5.7 The SSA PFAvs iMP PWD and PMD. . . 89

5.8 PCDof the iDU, the SSA, and the FPA. . . 89

5.9 The mean of the acquisition time of a hybrid detector. . . 93

(15)

List of Tables

2.1 Shift-equivalent class of G(f ). . . . 25

4.1 The Zech’s Logarithm table of P(D) = D5_{+ D}4_{+ D}3_{+ D}2_{+ 1. . . .} ₇₃

4.2 List of trinomial multiples of P(D) = D5_{+ D}4_{+ D}3_{+ D}2_{+ 1. . . .} ₇₄

5.1 Comparison of the acquisition time between the SSA and the iDU. . . 91

5.2 Comparison of the acquisition time between the FPA and the iDU. . . 91

5.3 Comparison of the implementation complexity of the iDU, the FPA, and the SSA. . . 91

(16)

(17)

List of Abbreviations, Operators,

and Symbols

Acronyms

AWGN Additive White Gaussian Noise

BB Base-Band

BGM Basic Graphical Model

CD Correct Detection

CDMA Code Division Multiple Access

DLL Delay Locked-Loop

DS/SS Direct-Sequence/Spread-Spectrum e.g. Exempli Gratia (from Latin: For Example)

FA False Alarm

FBA Forward Backward Algorithm FLL Frequency Locked-Loop FPA Full-Parallel Algorithm FSM Finite State Machine FSR Feedback Shift Register

(18)

GF Galois Field

GPS Global Positioning System

HA Hybrid Algorithm

HM Hierarchical Model

IB Input Buffer

iDU Iterative Detection Unit iMP Iterative Message Passing iPU Iterative Processing Unit

LDPC Low-Density Parity-Check (codes) LSFR Linear Feedback Shift Register

MD Missed Detection

MGF Moment Generating Function

ML Maximum Likelihood

MP Message Passing

MS Min-Sum

NLSFR Nonlinear Feedback Shift Register PCU Parity Control Unit

PLL Phase Locked-Loop

PN Pseudo Noise

RB Refresh Buffer

RGM Redundant Graphical Model

SBAS Satellite Based Augmentation System SNR Signal-to-Noise Ratio

SP Sum-Product

(19)

List of Abbreviations, Operators, and Symbols xvii SSA Simple-Serial Algorithm

SS Spread Spectrum

TG Tanner Graph

UWB Ultra Wide-Band

WD Wrong Detection

Algebra

a Infinite sequence, whose elements {ai} ∈ F , i = 0, 1, . . .

A(a) Set of all polynomials that satisfy f (D)a = 0, on a prefixed a

F [x ] Polynomial ring over F = GF (2) = {0, 1}

F Finite field of order 2, F = GF (2) = {0, 1}

G∗ _{Multiplicative group with nonzero elements, for a finite field G}

G(f ) Set of all sequences a ∈ V (f ) such that f (D)a = 0

GF (q) Finite field of order q (q is a prime or a power of a prime) N Set of natural numbers (positive integers)

N∗ _{Set of natural numbers (positive integers), without 0}

V (F ) Set of all infinite sequences whose elements are taken in F

Z Set of integers

Operators

D Left-shift operator

g(x ) | f (x ) The polynomial g(x ) is a divisor of the polynomial f (x ) | G | Order of the finite group G

(20)

ord (α) Order of an element α ∈ G, with G is a group per (a) Period of the sequence a

per (f (x )) Period of the polynomial f (x )

Q () Complementary cumulative distribution function of a standard Gaussian random variable

S () Sign function S () = sgn ()

a v b The sequences a and b are shift equivalent ⊕ Modulo-2 addition or exclusive or-operator

Symbols

CAlg Complexity of FPA, SSA, HA, or iMP (respectively CFP, CSS, CH,

CiMP)

Ec Chip energy

Ec/N0 SNR

IMAX Maximum number of iterations

M Number of observations at the receiver side

N PN sequence period

PCase Probability of WD, MD, FA, and CD (respectively PWD, PMD, PFA,

PCD)

π Its value is about 3.1415926535898

Tc Chip time (Rc= 1/Tcis the chip rate)

τd Dwell Time

τiPU Time delay of iPU

Tit Iteration time (Rit = 1/Titis the iteration rate)

τMD Time delay in case of MD

τpt Penalty Time

(21)

Chapter

1

Introduction

1.1 Motivations

D

-S/S-S (DS/SS) systems have been developed since the mid-1950’s. They are widely used in wireless military and civil communications as well as in satellite positioning systems, because they provide low probability of in-terception, strong anti-jam protection, and low co-channel interferences. All these pro-prieties are basically due to use of long high-rate binary pseudo-noise (PN) sequences that spread the spectrum bandwidth and make it difficult to be detected and corrupted by jammers. Therefore, long period sequences are more desirable than shorter ones that make the link susceptible to repeat-back jamming or interception/detection via delay and correlate methods, [53].

At the receiver side, to correctly demodulate SS signals, a despreading operation is accomplished by correlating the incoming signal with local replicas of its PN sequence. Because of this, a precise code timing synchronization is necessary. This result is gen-erally got in two receiver stages ([42], [44], [49], and [53]): the acquisition stage, that provides a preliminary coarse alignment between the received PN sequence and its local

(22)

replica, and the tracking stage, in which fine synchronization is realized and maintained by a delay locked-loop (DLL) unit ([12] and [13]), exploiting the previous rough align-ment. Therefore, PN acquisition is the critical point to have rapid and correct synchro-nization between DS/SS transmitters and receivers. Of course, this condition is important to design a more dynamic receiver, that better tracks any change of the channel condition. The standard and well-known acquisition techniques used to detect such sequences are ([23], [41], [44], [45], and [53]): full-parallel, simple-serial, and hybrid searches. The common denominator of all these techniques is that the received and local SS sequences are correlated and then processed by a suitable detector/decision rule to decide whether the two codes are in synchronism or not. Specifically, the first method implements a

maximum likelihood (ML) estimation algorithm with a fully parallel search. Hence, it

provides fast detection at price of a high implementation complexity, especially in case of long SS sequences. The opposite solution is the simple serial search, that has the lowest complexity, but its acquisition time is prohibitively long. The hybrid search mixes the two previous methods, resulting in a trade-off between these algorithms.

In this context, new techniques to acquire linear feedback shift register (LSFR) se-quences have been, recently, presented in [10], [59], [61], and [62]. All these methods are based on the paradigm of Message Passing (MP) on graphical models, or, more specifi-cally, on iterative Message Passing (iMP) algorithms to be run on loopy graphs ([1], [9], [34], [37], [56], and [60]). In other words, instead of correlating the received signal with a local PN replica (as in all standard methods), this algorithm uses all the information, provided by the incoming signal, as messages to be run on a predetermined graphical model with cycles, thus approximating the ML method. This results in a sub-optimal algorithm, that searches all possible code phases in parallel with a complexity typically lower than the full-parallel implementation, and an acquisition time shorter than that of the simple-serial algorithm. Furthermore, considering LFSR sequences characterized by sparse generating polynomials, it has been shown in [63] that significant improvements in terms of acquisition probability can be obtained using redundant graphical models

(23)

1.2. Key Points and Contributions 3 (RGMs) made up of a set of redundant parity check equations.

These motivations have induced us to investigate iMP algorithms to detect long LFSR sequences, so laying the bases of the present dissertation. More specifically, focusing on the approach presented in [10] and [63], we fully describe and analyze the iMP detector in terms of acquisition time, detection performance, and algorithm complexity. Further-more, exploiting the algebraic description of LFSR sequences, based on Galois Field (GF) theory [20], we propose a unified treatment to detect m-sequences and Gold codes. All previous papers ([10], [59], [61], [62], and [63]) were only addressed to acquire m-sequences, and they showed that the acquisition performance decreases dramatically in case of dense primitive polynomials. Our methodology outperforms these results, show-ing better acquisition probability at low signal-to-noise-ratio (SNR) and low complexity, for a broader class of LFRS sequences that includes Gold codes.

We also remark that the analysis of iMP detectors is enriched with theoretical studies on the acquisition-time performance, based on the Holmes seminal work ([26] and [27]), and related measurements. Of course, all these results are compared to the corresponding parameters of the standard algorithms (full-parallel,[23] and [45], hybrid, and simple-serial search, [53]).

1.2 Key Points and Contributions

The equivalence between a SS acquisition problem and a decoding one is the cardinal point on which this thesis is based. Because of this, it is possible to exploit the iterative decoding techniques of modern codes (tubo codes, [6], and LDPC, [17]) to acquire LFRS sequences as demonstrated in [10], [59], [61], and [62]. More specifically, focusing on the techniques presented in [10] and [63], SS signals can be acquired running MP algorithms on loopy graphs, that are obtained manipulating generating polynomials of the considered LFSR sequences. In this way it is possible to perform a full parallel detection with low-complexity and rapid acquisition.

(24)

Nevertheless, we will see that to have good performance in case of LFSR sequences characterized by dense generating polynomials and also acquire Gold codes, it will be nec-essary to resort to GF properties and related algorithms typically applied in cryptography problems, [20], [21] and [38]. Such techniques allow us to easy manipulate generating polynomials, so producing RGMs, that guarantee very interesting performance in terms of acquisition probability at low-complexity.

In this context, the contributions of this thesis are listed below.

• The algebraic introduction of LFSR sequences (based on GF theory) allows to de-fine m-sequences and Gold codes as sub-sets of the LFSR sequence family (see [18], [19], and [20]). This consideration lays the bases to have a unified treatment to acquire m-sequences and Gold codes, so adapting and improving the algorithms proposed in [10] and [63].

• About the design of graphical models used to be run iMP algorithms, we pro-pose some simple algorithms (typically used in cryptographic applications, [30] and [24]) that easy manipulate dense primitive polynomials to obtain sparse poly-nomials multiple of them. These polypoly-nomials can be efficiently used to implement sparse TGs with redundancy (called RGMs), that offer very good performance at low SNR and low-complexity.

• A preliminary architectural design of an iMP detector is provided with a detailed description of the acquisition algorithm.

• We also present a theoretical study to evaluate the acquisition-time performance of an iMP detector (based on [27] and [26]) and related measurements, so comparing them to those of the standard algorithms (full-parallel, hybrid, and simple-serial searches), [46].

• Finally, to reduce the memory requirements, some different schedules are tested, and a distinct approach for acquiring Gold codes is also reported. This new method

(25)

1.3. Applications 5 basically runs an iMP algorithm on a hierarchical model (see also [47]) generated by the two primitive polynomials that comprise a Gold code.

1.3 Applications

As mentioned in Section 1.1, DS/SS techniques are widely applied in many communica-tion systems for several applicacommunica-tions, e.g.: civil/commercial, military, safety and rescue, satellite positioning systems, etc. Of course, each system is different from the others, so their requirements, in terms of performance, signal/data processing algorithms, etc., are different. Nevertheless, the common characteristic is the importance that the acquisition stage has in all these systems to have fast and reliable detections of PN sequences.

In this context, the acquisition algorithm, which is described in this dissertation, can find large applications, because it guarantees good performance and acquisition times that tend to that of a full-parallel search, but with a lower complexity. Furthermore, we remark that this algorithm has been successfully applied to acquire m-sequences in Ultra

Wide-Band (UWB) systems (see [10] and [63]). Therefore, its extension to Code Division Multiple Access (CDMA) systems could be an important innovation to solve the critical

issue of long spreading-sequence detection.

Taking into account these considerations, in this thesis the GPS/SBAS1 _{([2], [22],}

[33], and [51]) codes have been specially taken into consideration, in order to have a realistic context to evaluate the performance achievable using the iMP detector for the acquisition of Gold sequences.

1.4 Outline

The remainder of this thesis is structured as follows: Chapter 2 introduces LFSR se-quences in terms of finite field theory. More specifically m-sequence and Gold codes

(26)

are defined as subsets of LFSR sequence family, providing the basis to have a unified treatment to acquire these codes using MP algorithms. Chapter 3 gives a mathematical description of the communication system and the signal model that will be used to simu-late the detection of SS signals. Architectural design of the iterative detection unit (iDU) is presented in Chapter 4 with a description of MP algorithms, their characteristics, and implementations. Chapter 5 shows some interesting results obtained by computer simu-lations which prove that MP algorithms can effectively acquire spreading codes. Finally conclusions and suggestions for future work are reported in Chapter 6.

(27)

Chapter

2

Linear Feedback Shift Register

Sequences

Linear feedback shift register (LFSR) sequences have been widely used in many

appli-cations (as random number generators, scrambling codes, for white noise signals, etc.). Nevertheless, our interest is focused on the generation of m-sequences and Gold codes, that are commonly used in SS systems for their attractive properties of autocorrelation and cross-correlation ([14], [41], and [53]). Therefore, the outline of this chapter is reported below.

• Section 2.1 provides a definition of feedback shift register (FSR) sequences, their basic concepts, and properties.

• Section 2.2 presents LFSR sequences in terms of polynomial rings.

• Section 2.3 gives an algebraic characterization of m-sequences and also provides their properties.

• Section 2.4 contains an overview of Gold codes their definition and properties. 7

(28)

2.1 Feedback Shift Register Sequences

In this section, we define some basic concepts for FSR sequences. We denote the finite field F = GF (2) = {0, 1} and

Fn_{= {a = (a}

0, a1, . . . , an−1)|ai∈ F }

a vector space over F of dimension n. A function with n binary inputs and one binary output is called a Boolean function of n variables, that is f : Fn _{→ F which can be}

represented as

f (x0, x1, . . . , xn−1) =

X

i1,i2,...,it

ci1i2...itxi1xi2. . . xit, ci1i2...it ∈ F (2.1)

where the sum runs through all subsets {i1i2. . . it} of {0, 1, . . . , n − 1}. This shows that

there are 22n

different boolean functions of n variables.

2.1.1 Basic Concepts

An n-stage shift register (SR) is basically made up of n consecutive 2-state storage units (flip-flops) regulated by a single clock. At each clock pulse, the state (1 or 0) of each memory is shifted to the next stage in line. To have a code generator, a SR is integrated with a feedback loop, which computes a new term for the left-most stage, based on the n previous terms. So, a generic feedback shift register (FSR) generator is depicted in Fig. 2.1.

Typically, the n binary storage elements are called the stages of the SR, and their contents are a state of the SR. The initial state is (a0, a1, . . . , an−1) ∈ Fn. The feedback

function f (x0, . . . , xn−1) is a boolean function of n variables, as defined in (2.1). At every

clock pulse, there is a transition from one state to the next, so, to obtain a new value for the stage n, we compute f (x0, . . . , xn−1) of all present terms in the SR and use this in the

(29)

2.1. Feedback Shift Register Sequences 9

Figure 2.1: Generic configuration of a FSR generator.

stage n. Therefore, assuming that the FSR generator outputs a sequence

a0, a1, . . . , an, . . . , (2.2)

at the generic time k the following recursive equation is satisfied

ak +n = f (ak, ak +1, . . . , ak +n−2, ak +n−1) , k = 0, 1, 2, . . . (2.3)

so, more in general, any n consecutive terms of the sequence (2.2)

ak, ak +1, . . . , ak +n−2, ak +n−1, k = 0, 1, 2, . . .

represents a state of the shift register in Fig. 2.1. The output sequence is called a FSR sequence. Furthermore, if the feedback function, f (x0, . . . , xn−1), is a linear function, then

the output sequence is called linear feedback shift register (LFSR) sequence. Otherwise, it is called a nonlinear feedback shift register (NLFSR) sequence (see [20]). Over a binary field, linear means that the feedback function computes the modulo-2 sum of a subset of the stages of the SR.

We remark that this thesis is focused on LFSR sequences. In particular, we will see that their repetition periods are completely determined by their feedback functions in an easily predictable way. Furthermore, the design of LFSR sequences with desired proper-ties requires us to understand the functionality of three components of an LFSR generator:

(30)

• the initial state; • the feedback function; • the output sequence.

More specifically, we will show how the behavior of the output sequences is determined by initial states and feedback functions. We mainly treat the binary case F = GF (2), but a general analysis (with F = GF (q), where q > 2) is reported in [20].

2.1.2 Periodic Property

In this section, the periodic property of a generic FSR sequence is defined, [20].

Definition 2.1. The sequence a0, a1, . . . is denoted as a or {ai}. If ai ∈ F , then we say

that a is a binary sequence or a sequence over F. If there exist two integers r > 0 and u > 0 such that

ai+r = ai, ∀i > u (2.4)

then the sequence is said to be ultimately periodic with parameters (r , u) and r is called a period of the sequence. The smallest number r satisfying (2.4) is called a (least) period of the sequence. if u = 0, then the sequence is said to be periodic. When the context is clear, we simply say the period of a instead of the least period of a.

Let us see a simple example.

Example 2.1. Considering the output sequence 00011011011 . . . of a 4-stage LFSR with feedback function f (x0, x1, x2, x3) = x2+ x3 and initial state a0a1a2a3 = 0001, it is an

ultimately periodic sequence, where u = 2 and the period r is 3.

The following theorem gives a general property for any q-ary FSR sequence1_(with

F = GF (q) and q > 2).

1_{A binary FSR sequence can be considered as a particular case of a generic q-ary FSR sequence. In other}

word, let F = GF (q) where q is a prime or a power of a prime (so |F | = q and q > 2), and referring to Fig. 2.1, each stage is replaced by a q-state storage unit and the boolean feedback function (2.1) is replaced by a more general function from Fn_{to F . More details are given in [20].}

(31)

2.1. Feedback Shift Register Sequences 11 Theorem 2.1. Any q-ary FSR sequence is ultimately periodic with period r 6 qn_{, where}

n is the number of the stages. In particular, if q = 2 then r 6 2n_.

Proof. In a q-ary FSR with n stages, there are qn _{possible states. Each state uniquely}

determines its successor. Hence, the first time that a previous state is repeated, a period for the sequence is established. Thus, the maximum possible period is qn_{, that is the}

maximum number of different states.

2.1.3 Linear Feedback Shift Register Sequences

Assuming to have a linear feedback function

f (x0, x1, . . . , xn−1) = c0· x0+ c1· x1+ . . . + cn−1· xn−1, ci ∈ F = GF (2)

the recursive equation shown in (2.3) becomes

ak +n = n−1

X

i=0

ci· ak +i, k = 0, 1, . . . . (2.5)

Thus, an LFSR is also referred to as a linear recursive sequence over F . Note that it is possible to have only 2n _{different n-stage LFSRs. On this consideration it is based the}

following general theorem.

Theorem 2.2. Let a be a sequence generated by an n-stage LFSR over F = GF (q). Then

the period of a is less then or equal to qn_{− 1. In particular, if q = 2, the period of any}

binary n-stage LFSR sequence is less then or equal to 2n_{− 1.}

Proof. Consider that the successor of state 00 . . . 0 (n times 0) of an n-stage LFSR is

again 00 . . . 0. Using the same argumentations as in the proof of Theorem 2.1, we see that the period of a is 6 qn_{− 1, since the state 00 . . . 0 cannot be a part of any period.}

(32)

2.2 LFSR Sequences in Terms of Polynomial Rings

This section is addressed to characterize the periodicity property of LFRS sequences, giving an equivalent definition of these sequences over F in terms of polynomial ring,

F [x ]. Therefore, we provide the following definition.

Definition 2.2. The ring formed by the polynomials over F = GF (2) with the classic

modulo-2 sum and product operations is called the polynomial ring over F and denoted by F [x ] F [x ] =       f (x ) = n X i=0 cixi|ci ∈ F , n > 0       .

This analysis is conducted over F = GF (2), but its extension to F = GF (q), where

q is prime or power of a prime, is sometimes obvious, as shown in [20].

2.2.1 Characteristic Polynomial

Let V (F ) be a set made up of all infinite sequences whose elements are taken from F =

GF (2),

V (F ) = {a = (a0, a1, . . .) |ai ∈ F } .

Assuming to have two generic sequences

a = (a0, a1, a2, . . .) ∈ V (f )

b = (b0, b1, b2, . . .) ∈ V (f )

and c ∈ F , we define the addition and scalar multiplication on V (F ) as follows a + b = (a0+ b0, a1+ b1, a2+ b2, . . .)

(33)

2.2. LFSR Sequences in Terms of Polynomial Rings 13 Introducing the zero sequence 0 = (000 . . .), it is easy to verify that V (F ) is a vector

space over F under these two operations. Thus, an LFRS sequence is a sequence, a =

(a0, a1, . . .), in V (F ) whose elements satisfy the linear recursive equation

an+k = n−1

X

i=0

ciak +i, k = 0, 1, . . . . (2.6)

For any sequence a = (a0, a1, a2. . .) ∈ V (F ), we define a left shift operator D as follows

Da = (a1, a2, a3, . . .) .

Note that D is a linear transformation of V (F ). Generally, for any positive integer i, we have

Di_{a = (a}

i, ai+1, ai+2, . . .) .

By convention, we define D0_{a = I a = a, where I is the identity transformation on V (F ).}

Using the D operator, the recursive formula (2.6) becomes

Dn_{a =} n−1 X i=0 ciDia or equivalently Dna − n−1 X i=0 ciDia = 0. (2.7) So we can write f (x ) = xn₋_c n−1xn−1+ . . . + c0 f (D) = Dn₋_c n−1Dn−1+ . . . + c0I , and f (D)a = 0. and, considering (2.7), we give the following definition.

(34)

Definition 2.3. For any infinite sequence a ∈ V (F ), if there exists a nonzero monic2

polynomial f (x ) ∈ F [x ] such that

f (D)a = 0,

then a is called a linear recursive sequence, or equivalently LFSR sequence. The mial f (x ) is referred to as characteristic polynomial of a over F . The reciprocal polyno-mial is called the feedback polynopolyno-mial of a.

More details on reciprocal polynomials are reported in [20]. Here, we just give its definition over GF (2).

Definition 2.4. Let f (x ) = xn_{+ c}

n−1· xn−1+ . . . + c1· x + c0, ci∈ GF (2) and c0, 0 (so

c0= 1), the reciprocal polynomial of f (x ) is defined as

f−1(x ) , x

n

c0 · f (x

−1_{) = x}n_{+ c}

1· xn−1+ . . . + cn−1· x + 1.

One more definition is needed before proceeding further on.

Definition 2.5. For any nonzero polynomial f (x ) ∈ F [x ], G(f ) represents the set made

up of all sequences in V (F ) with f (D)a = 0

G(f ) = {a ∈ V (F )|f (D)a = 0, f (x ) ∈ F [x ]} .

Since f (D) is a linear transformation, G(f ) is a subspace of V (F ). Furthermore, we remark that, by convention, the constant polynomial 1 is the characteristic polynomial of the zero sequence 000 . . . .

Theorem 2.3. Let f (x ) ∈ F [x ] be a monic polynomial of degree n. Then G(f ) is a linear

space of dimension n. Hence, it contains 2n_{different binary sequences.}

2_{A monic polynomial is a polynomial in which the coefficient of the highest order term is 1, e.g.: x}n_{+ c} n−1·

xn−1_{+ . . . + c}

(35)

2.2. LFSR Sequences in Terms of Polynomial Rings 15

Proof. For a sequence

a = (a0, a1, . . . , an−1, an, . . .) ∈ G(f )

since deg(f ) = n, when the first n terms are given, all other terms of a can be determined by (2.6) starting from an. There are 2nways to choose and n-tuple (a0, a1, . . . , an−1) ∈ F .

Therefore |G(f )| = 2n_.

Note that the sequences in V (F ) may or may not be periodic, in particular, applying Def. 2.3 of LFSR sequences, it is easy to check the periodicity of these sequences, as we will show in the next section.

Finally, we just remark the key points of this section. More specifically, if a sequence, a = (a0, a1, a2, . . .), is generated by an n-stage LFSR, the following three equivalent

definitions are verified:

1. a = (a0, a1, a2, . . .) is an output sequence of an LFSR generator with the linear

feedback function f (x0, x1, . . . , xn−1) = n−1 X i=0 c1xi, ci ∈ F

and an initial state (a0, a1, . . . , an−1), so all elements of a satisfy the following

re-cursive relation an+k = n−1 X i=0 ciak +i, k = 0, 1, . . . . (2.8)

2. a is a linear recursive sequence that satisfies the above recursive equation, (2.8). 3. There exists a monic polynomial f (x ) = xn ₋Pn−1

i=0 cixi, with f (x ) ∈ F [x ], of

degree n such that f (D)a = 0 or, equivalently, a ∈ G(f ).

The polynomial f (x ) is referred to as characteristic polynomial of a and the reciprocal polynomial of f (x ) is called the feedback polynomial of a.

(36)

2.3 Minimal Polynomials and M-Sequences

In the previous section, LFSR sequences over F have been associated with polynomials over F . This result enables us to use the theory of the polynomial ring F [x ] to investigate the periods of LFSR sequences and discuss the minimal polynomials. In this way, it is possible to define m-sequences, or equivalently LFSR sequences with the maximum period.

2.3.1 Minimal Polynomials of LFSR Sequences

Let a be an LFSR sequence, so there is a nonzero monic polynomial f (x ) such that

f (D)a = 0. (2.9)

Nevertheless, for the fixed sequence a, there are many polynomials for which (2.9) is verified.

Example 2.2. Assuming to have the LFSR sequence a = 011011 . . ., then both the poly-nomials f1(x ) = x2+ x + 1 and f2(x ) = x3+ 1 satisfy the property (2.9).

Hence, we want to find the relation among these polynomials, for a fixed LFSR se-quence a. Therefore, we define

A(a) = {f (x ) ∈ F [x ]|f (D)a = 0} , (2.10)

in other words, A(a) is made up of all polynomials that verify the condition (2.9). The fol-lowing theorem gives a set of properties that are verified by all characteristic polynomials of A(a).

Theorem 2.4. Let a be an LFSR sequence and A(a) be defined as (2.10). Then A(a)

(37)

2.3. Minimal Polynomials andM-Sequences 17

1. The zero polynomial belongs to A(a).

2. if f (x ), g(x ) ∈ A(a), then f (x ) ± g(x ) ∈ A(a).

3. if f (x ) ∈ A(a) and h(x ) ∈ F [x ], then h(x ) · f (x ) ∈ A(a). Proof. We demonstrate all points in the following list.

1. 0a = 0 =⇒ 0 ∈ A(a).

2. Assuming f (x ), g(x ) ∈ A(a), then

f (D)a = 0 and g(D)a = 0

(f (D) ± g(D)) a = f (D)a ± g(D)a = 0

f (D) ± g(D) ∈ A(a).

3. Assuming f (x ) ∈ A(a), then

f (D)a = 0

(h(D) · f (D)) a = h(D) (f (D)a) = h(D)0 = 0.

Hence, all points are proved.

Since A(a) is closed with respect to all these operations, so A(a) is an algebra. Now, we can give the definition of minimal polynomial.

Definition 2.6. A monic polynomial of the lowest degree in A(a) is referred to as minimal polynomial of a over F .

According to Def. 2.6, we remark that the minimal polynomial of the zero sequence 000 . . . is 1, and the polynomial x −1 is the minimal polynomial of any constant sequence, (1, 1, 1, . . .). Furthermore, it is also possible to demonstrate the following theorem.

(38)

Theorem 2.5. Let a ∈ V (F ) and m(x ) be the minimal polynomial of a. Then the minimal

polynomial of a is unique and satisfies the following two properties. 1. m(D)a = 0.

2. For f (x ) ∈ F [x ], f (D)a = 0 iff m(x) is a divisor of f(x) (also pointed out m(x )|f (x )).

The proof is shown in [20]. Of course, for any a ∈ G(f ), f (x ) does not need to be the minimal polynomial of a, and so the following result is obvious.

Corollary 2.1. If f (x ) , 0, a ∈ G(f ), then the minimal polynomial of a, called as m(x ),

divides f (x ), or briefly m(x )|f (x ).

Proof. According to the definition of G(f ) (Def. 2.5), a ∈ G(f ) =⇒ f (D)a = 0. So

applying Theorem 2.5, m(x )|f (x ).

we introduce now the concept of irreducibility3_{over F[x] to obtain another interesting}

result can be obtained.

Definition 2.7. A polynomial f (x ) ∈ F [x ] is referred to as irreducible over F if f (x ) has

positive degree and f (x ) = h(x ) · g(x ) with h(x ), g(x ) ∈ F [x ] implies that either h(x ) or g(x ) is a constant polynomial. Otherwise, f (x ) is called reducible over F .

Corollary 2.2. If f (x ) is irreducible, then f (x ) is the minimal polynomial of any nonzero

sequence in G(f).

Proof. Considering that f (x ) has only 1 and itself as its factor and the zero sequence has

1 as its minimal polynomial, then f (x ) is a minimal polynomial of any nonzero sequence

in G(f ).

According to Def. 2.6, an important result is that the degree of the minimal polynomial of a is equal to the length of the shorter LFSR generator that can output a. Furthermore, the degree of a minimal polynomial of a sequence is called the linear span of the sequence, as shown in the next subsection.

(39)

2.3.2 Periodicity

For any periodic sequence, a, the following theorem is satisfied.

Theorem 2.6. If a is an ultimately periodic sequence with parameters (u, r ), then the

minimal polynomial of a is m(x ) = xu_m

1(x ) with m1(0) , 0 and m1(x )|(xr − 1). Hence,

it can be generated by an LFSR.

Proof. Note that ak +r= ak, k = u, u + 1, . . ., so

=⇒ (Dr_{− 1) D}u_{(a) = 0 =⇒ m(x )|x}u_(xr _{− 1) .}

Writing m(x ) = xu_m

1(x ), then m1(0) , 0 and m1(x ) divides xr− 1. Therefore, a can be

outputted by an LFSR with characteristic polynomial m(x ). The following corollary immediately follows Theorem 2.6.

Corollary 2.3. If a is a periodic sequence with period r (it means u = 0), then its minimal

polynomial m(x ) divides (xr _{− 1).}

Proof. From Theorem 2.6, if a is ultimately periodic, then the minimal polynomial is m(x ) = xu_m

1(x ), with m1(0) , 0. In this case u = 0, so the minimal polynomial

becomes m(x ) = m1(x ).

Now, we give the following definition.

Definition 2.8. Let a be an ultimately periodic sequence over F . Then the degree of the

minimal polynomial of a is called linear span or linear complexity of a.

Equivalently, the linear span of a periodic sequence is the length of the shortest LFSR generator that produce the sequence.

(40)

Proof. Assuming that r and l are two periods of a =⇒ Dr_{a = a and D}l_{a = a. So,}

applying the division algorithm, we can write

l = q · r + t, 0 6 t < r and q ∈ N,

because r is the smallest integer with this property (r < l). Considering that Dq·r_{a = a,}

thus

Dla = Dq·r +ta = Dt(Dq·r_{) a = D}t_{a = a}

so t = 0 and r |l.

Now, we introduce the definition of the period of a polynomial (see also [20]), f (x ), over F . This step is fundamental to characterize m-sequences in terms of their generating polynomials.

Definition 2.9. For a polynomial f (x ) over F , the period of f (x ) is the least positive

integer r such that f (x )|(xr _{− 1).}

Hence, denoting by per (a) a period of a sequence a and per (f (x )) a period of a poly-nomial f (x ), we prove the following theorem.

Theorem 2.7. Let a be an LFSR sequence with minimal polynomial m(x ).

1. If m(0) , 0, then a is periodic. In this case per (a) = per (m(x )). 2. If a is periodic, then m(0) , 0.

Proof. We prove both these points.

1. Let a be an ultimately periodic sequence over F and with parameters (u, r ) and

m(x ) be its minimal polynomial. According to Def. 2.1, a is periodic if and only

if u = 0. So, from Theorem 2.6, m(x ) = xx_m

1(x ) = m1(x ) with m1(0) , 0 and

m1(x )|(xr− 1). Thus, a is periodic if and only if m(x ) = m1(x ). According to Def.

(41)

2.3. Minimal Polynomials andM-Sequences 21 2. Conversely, if a is periodic, then u = 0 and xr _{− 1 ∈ A(a). According to}

The-orem 2.5, we have m(x )| (xr _{− 1) =⇒ m(0) , 0, which demonstrates the second}

assertion.

So, the theorem is demonstrated.

Thus far, we have got a criterion for determining whether an ultimately periodic se-quence is periodic evaluating its minimal polynomial at 0. Now, we want to show the relationships among the period of a sequence, the period of its minimal polynomial, and the order of a root of the minimal polynomial when the minimal polynomial is irreducible. Therefore, we first give a couple of definitions.

Definition 2.10. An element α ∈ F is called a root4_{(or a zero) of the polynomial f (x ) ∈}

F [x ], if f (α) = 0.

Definition 2.11. Let G be a group. For α ∈ G, if r is the smallest positive integer such

that αr _{= 1 , then r is called order of α, denoted by ord(α) = r .}

Now, we prove the following important theorem.

Theorem 2.8. Let a be an LFSR sequence with minimal polynomial m(x ). Assume that

m(x ) is an irreducible polynomial over F = GF (2) of degree n. Let α be a root of m(x ) in the extension field GF (2n₎5_{. Then}

per (a) = per (m(x )) = ord (α)

in other words, the period of a sequence a, the period of its minimal polynomial, and the order of a root of the minimal polynomial of a are equal.

4_{More details are contained in [20].}

5_{The construction of an extension field GF (2}n_{) is reported in App. A, but more details are contained in}

(42)

Proof. Noting that m(x ) is the minimal polynomial of α and according to Theorem A.2

in App. A, we have per (m(x )) = ord (α). Considering also Theorem 2.7 per (a) = per (m(x )) = ord (α) .

The assertion is established.

This important result is emphasized here.

The period of an LFSR sequence, a, is equal to the period of its minimal polynomial m(x ). If the minimal polynomial is irreducible, then the period of the sequence is equal to the order of a root6_{α of the minimal polynomial}

in the extension field. Briefly, per (a) = per (m(x )) = ord (α).

Thus, introducing the concept of cyclic group, it is possible to provide an algebraic defi-nition of primitive polynomial (see also [20] and [35]).

Definition 2.12. A multiplicative group G is said to be cyclic if there is an element a ∈ G

such that for any b ∈ G there is some integer i with b = ai_{. Such an element a is called}

a generator of the cyclic group, and we write G =< a >.

Definition 2.13. A generator of a cyclic group GF (2n₎∗_{(this is a multiplicative group,}

without the zero element of GF (2n_{)) is called a primitive element of GF (2}n_{). An}

irre-ducible polynomial over GF (2) having a primitive element in GF (2n_{) as a root is called}

a primitive polynomial over GF (2). Equivalently, an irreducible polynomial f (x ) of de-gree r is said to be primitive if the smallest positive integer p for which f (x ) divides xp₊₁

(or xp_{− 1) is p = 2}r_{− 1.}

Note that not all irreducible polynomials are primitive ([20] and [53]). We give an example.

(43)

2.3. Minimal Polynomials andM-Sequences 23 Example 2.3. According to Def. 2.7, the polynomial f (x ) = x4_{+ x}3_{+ x}2_{+ x + 1 is}

irreducible over GF (2), so it can be used to generate the field GF24_{. However, it is}

not a primitive polynomial. Indeed, let α be a root of f (x ), according to Def. 2.13, its order should be 24_{− 1 = 15, because α is a primitive element in GF}₂4_{. Nevertheless,}

it possible to prove that ord (α) = 5 < 24_{− 1 = 15, so f (x ) is not a primitive polynomial}

over GF (2).

2.3.3 M-Sequences

This section defines m-sequences in terms of the previous properties and theorems based on polynomial field theory, [20].

Definition 2.14. Two periodic sequences a = {ai} and b = {bi} are called shift equivalent

if there exists an integer k such that

ai = bi+k, ∀i > 0.

In this case, we write a = Dk_{b, or a v b. Otherwise, they are referred to as shift distinct.}

A set in which all sequences are shift equivalent is called a shift-equivalent class. One shift-equivalent class of G(f ) corresponds to one cycle of the states in the state diagram of the LFSR with f (x ). The number of shift-equivalent class is determined as follows. Theorem 2.9. Let f (x ) be an irreducible polynomial over GF (2) of degree n. Then the

number of shift-equivalent classes of nonzero LFSR sequences in G(f ) is given by

2n_{− 1}

per (f (x )).

This theorem shows that for an LFSR with an irreducible polynomial there are_{per(f (x ))}(2n−1) sequences with period equal to per (f (x )) and one sequence with period 1, that is the zero sequence. An example is useful to well understand this theorem.

(44)

Example 2.4. Considering the polynomial f (x ) = x4_{+ x}3_{+ x}2_{+ x + 1 ∈ F [x ] (see also}

Ex. 2.3), this is irreducible with per (f (x )) = 5. Hence, the number of shift-equivalent class is

2n_{− 1}

per (f (x )) = 3, n = 4, per (f (x )) = 5

,

or, equivalently, 3 sequences with period 5, as shown in Tab. 2.1, where each class is denoted by Gi, with i = 1, 2, 3. Thus we have

G(f ) = {0} ∪ G1∪ G2∪ G3.

As consequence of Theorem 2.9, we have the following corollary.

Corollary 2.4. If f (x ) is primitive over GF (2) of degree n, then any nonzero a ∈ G(f )

has period 2n_{− 1 and}

G(f ) =nDia|0 6 i 6 2n− 2o∪ {0}.

This result clearly means that if f (x ) is a primitive polynomial over GF (2) of degree

n, then the number of shift-equivalent class in G(f ) is always

2n_{− 1}

per (f (x )) = 1

because per (f (x )) = 2n_{− 1. So, m-sequences are defined as follows.}

Definition 2.15. A binary sequence, a, generated by an n-stage LFSR is called a maximal length sequence if it has period 2n_{−1, or, equivalently, if its polynomial, f (x ), is primitive,}

so satisfying the following equation

per (a) = per (f (x )) = ord (α) = 2n_{− 1.}

(45)

Table 2.1: Shift-equivalent class of G(f ).

G1 G2 G3 00011 01010 11110 00110 10100 11101 01100 01001 11011 11000 10010 10111 10001 00101 01111

According to Corollary 2.4 and Def. 2.15, in order to generate an m-sequence of period 2n _{− 1 over F = GF (2) by an LFSR, we only need to select a primitive}

polyno-mial over F of degree n as the characteristic polynopolyno-mial (also referred to as generating

polynomial) of this LFSR sequence. This result is summarized in the following theorem,

[53].

Theorem 2.10. An LFSR generator of a given memory, r , produces a sequence of

el-ements from GF (2), with the largest period, 2r _{− 1, iff its characteristic polynomial is}

primitive over GF (2).

2.3.3.1 M-Sequence Properties

A large bibliography is provided on m-sequence correlation properties and their applica-tions ([3], [14], [18], [19], [20], [21], [35], [36], [41], and [53]). Therefore, here we just give an overview of the statistical properties of these codes ([14], [41], and [53]). Property 2.1. A maximal length sequence, a, contains more ones than zeros. The number

of ones is1

2· (N + 1), where N = per (a) = 2r− 1 and r is the degree of its characteristic

polynomial.

Property 2.2. Let {an} be an m-sequence over GF (2) with linear span r (polynomial

degree). Then for any τ, with τ , 0 mod 2r_{− 1, the difference of the m-sequence {a} n}

(46)

and its τ-shift {an+τ} is another shiftan+τ0_(τ) of the same m-sequence. That is

an+τ0_(τ)= a_n+τ⊕ a_n ∀n,

where τ0_{(τ) is defined for all τ , 0 mod 2}r _{− 1 and ⊕ is modulo-2 sum. This property is}

referred to as shift-and-add property.

Property 2.3. If a window of width r is slid along the m-sequence (with period N = 2r_{− 1) for N shifts, each r -tuple, except the all zero r -tuple, appears exactly once.}

In data communication, binary sequences are often mapped on polar values (or BPSK values)

yk = (−1)ak, ∀k ∈ N and ak∈ GF (2) = {0, 1}.

We introduce now the periodic autocorrelation function of the sequence y as

R(k ) = 1 N ·    N X i=1 yi+k· yi∗    (2.11)

where N is the period. It is easy to show the following correlation properties of m-sequences.

Property 2.4. The period autocorrelation function R(k ) of a BPSK-mapped m-sequence

(with period N ) is two-valued and is given by

R(k ) =          1, k = l · N −1 N, k , l · N where l ∈ Z7_.

Nevertheless, in realistic contexts, correlation calculations are carried out over M

(47)

2.3. Minimal Polynomials andM-Sequences 27 symbols, such that

r M N = 2r _{− 1}

where r is the polynomial degree and N is the sequence period. So, the partial-period

correlation is defined as ([41] and [53])

r (M , n, τ) = 1 M ·    M −1_X i=0 yn+i+τ· yn+i∗    .

The partial-period correlation value depends on the initial location, n, in the sequence, where the correlation computation begins as well as on the window length M . Therefore, this correlation function is statistically characterized by its first and second time-average moments, that are denoted by hi and are calculated as follows respectively, [53]

hr (M , n, τ)i = 1 N ·    N X n=1 r (M , n, τ)    h|r (M , n, τ)|2i = 1 N ·    N X n=1 |r (M , n, τ)|2   

where N is the sequence period. Hence, the following property is satisfied ([41] and [53]). Property 2.5. Let y be a BPSK-mapped m-sequence of period N , then the first and

second time-average moments of the partial-period correlation function of y are given by

hr (M , n, τ)i =          −1 N, τ , 0 mod N 1, τ = 0 mod N h|r (M , n, τ)|2_{i =}          1 M · 1 −M −1 N , τ , 0 mod N 1, τ = 0 mod N for M 6 N .

(48)

with only three coefficients

f (x ) = xn+ xk+ 1, with n, k ∈ N∗ and n > k

referred to as trinomials. In this case, their implementation is very simple, because the LFSR generator is made up of a n-stage SR and a single exclusive-or gate (typically de-noted by ⊕). Thus, it is more efficient to use a primitive trinomial for generation of an

m-sequence than to use generating polynomials characterized by more nonzero

coeffi-cients.

2.4 Gold Codes

The main application of SS systems is to perform CDMA, so sharing the scarce channel resources. This is achieved by associating a code to each user. More in detail, each signal is spread by a pre-assigned code that identifies just one particular user. So, the overall SS signal is ideally a combination of all these spread signals and the Additive White Gaussian

Noise (AWGN). In this way, all users can transmit/receive simultaneously using the same

band of frequencies.

At the receiver side, a despreading operation is necessary to track and process the desired user signal. This operation is basically performed by a correlation between the in-coming signal and local replicas of the desired spreading code. Of course, in this context, all other spread signals will not be despread and will cause interference in the considered signal (or user channel). Therefore, the main goal of a SS system designer, for a multiple-access system, is to search a set of spreading codes such that as many users as possible can share a band of frequencies with the minimum mutual interference.

The amount of interference from a user employing a different spreading code is re-lated to the cross-correlation between the two different codes, thus the Gold codes8_{, [18]}

(49)

2.4. Gold Codes 29 and [19], were specifically introduced for multiple-access applications of SS systems. Relatively large sets of Gold codes exist which have well controlled cross-correlation properties. Furthermore, the large difference between the in-phase autocorrelation func-tion 2N _{− 1 (where N is the sequence period) and the cross-correlation function of any}

two Gold sequences makes these codes useful in CDMA communication systems. The full period cross-correlation between two spreading codes, anand bn, with period

N is defined C (k ) = 1 N · N −1_X n=0 an+k · bn∗. (2.12)

Roughly speaking, this is a list of all possible correlation values C (k ) as a function of the temporal index k that yields that particular cross-correlation figure. In the case an =

bn the cross-correlation coincides with the periodic autocorrelation and (2.12) becomes

(2.11).

Definition and properties of Gold codes are reported in the following section. Further details can be found in [3], [18], [20], [41], and [52].

2.4.1 Definition and Properties

The Gold codes are large families of linear binary sequences with uniformly low cross-correlation values. More specifically, in [18] and [19], Gold described a class of pairs of

m-sequence whose cross-correlation function have three low values which can be

deter-mined precisely.

Consider an m-sequence that is represented by a binary vector a of period N , and a second sequence b obtained sampling every qth _{symbol of a. The second sequence is}

said to be a decimation of the first, and the notation b = a[q] is used to indicate that b is obtained sampling every qth _{symbol of a. The decimation of an m-sequence may}

or may not yield another m-sequence. When the decimation yields an m-sequence, the decimation is said to be a proper decimation. It has been proven in [52] that b = a[q] has period N if and only if gcd (N , q) = 1 (where gcd is the greatest common divisor),

(50)

and the proper decimation by odd integers, q, will give all the m-sequences of period N . Thus, any pair of m-sequences having the same period N , can be related by b = a[q] for some q.

The cross-correlation of pairs of m-sequences computed using (2.12) can be three-valued, four-three-valued, or many-valued. In particular, certain special pairs of m-sequences, whose cross-correlation is three-valued (see also [41])

C (k ) ∈ ( −1 N t(r ), − 1 N, 1 N [t(r ) − 2] ) , where t(r ) =          1 + 2(r +1)/2_{, for r odd} 1 + 2(r +2)/2_{, for r even}

the code period is N = 2r _{− 1, and r is their characteristic polynomial degree, are called}

preferred pairs of m-sequences. Finding preferred pairs is necessary to define a set of

Gold codes. So, we give the following three conditions that are sufficient to define a preferred pair of m-sequences.

1. r , 0 mod 4, this means that r is odd or r = 2 mod 4;

2. b = a[q] where q is odd and either q = 2k_{+ 1 or q = 2}2·k_{− 2}k_{+ 1;}

3. gcd(r , k ) =          1, for r odd 2, for r = 2 mod 4 .

More details and an example to find a preferred pair of m-sequences are shown in [41]. Gold sequences are clearly defined by the following theorem, [3].

Theorem 2.11. Let f (x ) and g(x ) be a preferred pair of primitive polynomials over

GF (2) of degree r , r , 0 mod 4. The LFSR, with characteristic polynomial f (x ) · g(x ), will generate a set of 2r _{+ 1 different sequences of period N = 2}r _{− 1. Any pair of}

(51)

2.4. Gold Codes 31

sequences in this set has a three-valued cross-correlation, that is

C (k ) ∈ ( −1 N t(r ), −1 N , 1 N [t(r ) − 2] ) . (2.13)

These sequences are commonly called Gold codes.

Indeed, let a and b represent a preferred pair of m-sequences having period N = 2r_{− 1. The family of codes}

n

a, b, a + Db, a + D2b, . . . , a + DN −1bo

is called the set of Gold codes for the preferred pair a and b. The notation Dj_b

repre-sent the cyclic shift of the m-sequence b by j units (or equivalently j chips). As shown in Theorem 2.11, any set of Gold codes has the property that any pair of sequences in the set have a three-valued cross-correlation which takes on the values defined in (2.13). Furthermore, the number of sequences in any family of Gold codes is 2r _{+ 1.}

Example 2.5. A typical implementation used to generate Gold codes is illustrated in Fig. 2.2. More in detail, the picture shows the configuration used to obtain the GPS/SBAS Gold code set. The two m-sequences are

Pc0(D) = D10+ D3+ 1

Pc00(D) = D10+ D9+ D8+ D6+ D3+ D2+ 1

their degree is r = 10, so all the sequences of this set have period N = 2r_{− 1 = 1023 and}

the total number of codes is 2r _{+ 1 = N + 2 = 1025. The equivalent LFSR generator is}

characterized by the following polynomial of higher degree

P(D) = Pc0(D) · P_c00(D)

(52)

Figure 2.2: GPS/SBAS Gold code generator.

that provides the tap configuration of the LFSR generator of this Gold code set. This second implementation can also be used to generate the same set of N + 2 sequences, simply changing the initial word of its SR.

(53)

Chapter

3

Signal Model and Detection

Algorithms

This chapter provides a mathematical description of the communication system and the signal model that will be considered to compare the iMP detector to the standard correlation-based acquisition algorithms (full-parallel, hybrid, and simple-serial searches). Further-more, the second part of this chapter gives an overview of the standard detectors and presents the motivations that allow the application of MP algorithms to acquire spreading sequences. Thus, the outline is below.

• Section 3.1 contains a description of a simplified DS/SS communication system, including a mathematical characterization of the signal model.

• Section 3.2 is an overview of detection algorithms typically used to acquire SS codes. It also contains an introduction to MP algorithms and their application as detectors.

(54)

Figure 3.1: DS/SS communication system model.

3.1 Communication System

This section gives an overview of the communication system model that will be used to evaluate the performance of iMP algorithms to acquire PN sequences. The base-band (BB) representation of a DS/SS communication system is reported in Fig. 3.1. It is made up of: a BB transmitter, that outputs a predetermined spreading sequence1_{, a channel that}

introduces a propagation delay (∆ = 0), an additive white gaussian noise (AWGN), and finally a BB receiver that runs two important stages: acquisition and tracking stage. The first one is addressed to detect a SS signal, performing a rough estimation of its code delay. Then, the tracking stage exploits this coarse synchronization to run a DLL that improves the alignment between the transmitted spreading sequence and its local replica. This step is fundamental to avoid catastrophic SNR degradation and correctly process the incoming signal. The following sections provide more details on each stage of the proposed communication system model (Fig. 3.1).

3.1.1 Base-Band Transmitter

The BB transmitter is basically made up of a PN sequence generator that produces pseudo-random binary sequences, c (each element is ck ∈ {0, 1}) and a BPSK mapper that outputs

(55)

3.1. Communication System 35

Figure 3.2: General representation of an r -stage LFSR generator.

the correspondent antipodal sequences, y, where each component is yk = (−1)ck. Only

LFSR generators are taken into account in this thesis. A general representation of an LFSR generator is in Fig. 3.2. As shown in the picture, at the generic time k , assuming that ck is the SR output and ck +i (with 0 6 i 6 r ) is the content of the ithregister, the

following parity equation is verified

0 = gr· ck⊕ gr −1· ck +1⊕ gr −2· ck +2⊕ . . . ⊕ g2· ck +r −2⊕ g1· ck +r −1⊕ g0· ck +r = r M i=0 gr −i· ck +i (3.1)

where ⊕ is modulo-2 addition and gi ∈ {0, 1}, 0 6 i 6 r , are the feedback coefficients (also

referred to as taps). The most common way to represent an r -stage LFSR is providing its generating polynomial (that also gives the tap configuration of the code) as

P (D) = g0+ g1· D + . . . + gr −1· Dr −1+ gr · Dr = r X i=0 gi· Di (3.2)

where D is the unit delay operator2_{, and r is the polynomial degree. For a given degree}

r , g0and gr are always 1.

After the detailed introduction of m-sequences and Gold codes performed in Chapter

(56)

2, we highlight here that there also exits an equivalent way for producing Gold sequences using a single higher-order LFSR generator. Indeed, as demonstrated in [18], a Gold code can be generated by an r -stage LFSR unit (the scheme is in Fig. 3.2) with the tap configuration

P(D) = Pc0(D) · P_c00(D) (3.3)

where Pc0(D) and P_c00(D) are the primitive polynomials that specify the feedback

con-nections of the two q-stage SRs, where q = r

2, that output the generating m-sequences c0

and c00_{(as shows in Fig. 2.2).}

Example 3.1. The two m-sequence polynomials of GPS/SBAS Gold sequences are

Pc0(D) = D10+ D3+ 1 (3.4a)

Pc00(D) = D10+ D9+ D8+ D6+ D3+ D2+ 1 (3.4b)

q = 10 implies r = 2 · q = 20. From (3.3), the high-order LFSR (or Gold generating

polynomial) is

P(D) = D20_{+ D}19_{+ D}18_{+ D}16_{+ D}11_{+ D}8_{+ D}5_{+ D}2_{+ 1} _(3.5)

this important result allows Gold codes to be treated as LFSR sequences.

Note that typically the equivalent LFSR for Gold sequences (e.g., Eq. (3.5) for GPS/SBAS codes) is not a sparse (dense) generator, because it has more then 4 coeffi-cients.

3.1.2 Communication Channel

Referring to Fig. 3.1, the incoming BB spreading signal at the receiver side is found to be

zk=

p

Ec· yk+ nk =

p

Iterative message-passing-based algorithms to detect spreading codes

U  P

D  I ’I:

E, I, T

Iterative Message-Passing-Based

Algorithms to Detect Spreading Codes

Presented by:

F P

Supervisor:

Prof. Marco Luise

Acknowledgements

Abstract

Contents

List of Figures

List of Tables

List of Abbreviations, Operators,

and Symbols

Acronyms

Algebra

Operators

Symbols

Chapter

1

Introduction

1.1 Motivations

D

1.2 Key Points and Contributions

1.3 Applications

1.4 Outline

Chapter

2

Linear Feedback Shift Register

Sequences

2.1 Feedback Shift Register Sequences

2.1.1 Basic Concepts

2.1.2 Periodic Property

2.1.3 Linear Feedback Shift Register Sequences

2.2 LFSR Sequences in Terms of Polynomial Rings

2.2.1 Characteristic Polynomial

2.3 Minimal Polynomials and M-Sequences

2.3.1 Minimal Polynomials of LFSR Sequences

2.3.2 Periodicity

2.3.3 M-Sequences

2.4 Gold Codes

2.4.1 Definition and Properties

Chapter

3

Signal Model and Detection

Algorithms

3.1 Communication System

3.1.1 Base-Band Transmitter

3.1.2 Communication Channel