Sequências PN e outras - paginas.fe.up.ptpaginas.fe.up.pt/~sam/CCD/apontamentos_SS/Sequencias_PN.pdf · Sequências e funções de Walsh • As sequências e funções de Walsh baseiam-se

SSeeqquuêênncciiaass ppsseeuuddoo--aalleeaattóórriiaass ee oouuttrraass

Sílvio A. Abrantes DEEC/FEUP

Sequências pseudo-aleatórias e outras 2

Códigos ou sequências para espalhamento espectral

Propriedades desejáveis dos códigos espalhadores

• Devem ter dois valores.

• Devem ter uma função de autocorrelação com um único pico estreito, para ajudar na sincronização do código.

• Devem ter funções de correlação cruzada com valores baixos, para permitir mais utilizadores simultâneos.

• Devem ser balanceados (equilibrados) no número de “0” e “1”, para que a densidade espectral de potência esteja bem repartida nas frequências.

Códigos encontrados em sistemas de espalhamento espectral

• Códigos de Walsh-Hadamard

• Códigos de Barker

• Códigos (sequências) PN de comprimento máximo

• Códigos de Gold

• Códigos de Kasami

Podemos dividir os códigos em ortogonais e não-ortogonais. Os códigos de Walsh-Hadamard são ortogonais e os outros não.

Os termos “códigos” e “sequências” serão usados indistintamente.

Funções de correlação

Considerações prévias

• É autocorrelação se as sequências forem iguais

• É correlação cruzada se as sequências forem distintas

• É correlação periódica se o deslocamento for cíclico

• É correlação aperiódica se o deslocamento não for cíclico

• É correlação de período parcial se só uma parte das sequências estiver envolvida no cálculo

Definições

• Correlação cruzada periódica entre sequências c e d binárias ±1 de comprimento N

1

( )N

c ii

i jR j c d +=

= ∑ 0 1j N≤ ≤ −

• Correlação cruzada aperiódica entre sequências c e d binárias ±1 de comprimento N

1

( )N j

a i ii

jR j c d−

+=

= ∑ 0 1j N ≤ ≤ −

• Se as sequências c e d forem iguais passamos a ter funções de autocorrelação.


Sequências e funções de Walsh

• As sequências e funções de Walsh baseiam-se nas matrizes de Walsh-Hadamard.

• Estas matrizes são matrizes quadradas 2 2n n× de elementos ±1 e linhas (e colunas) ortogonais entre si. São construídas recursivamente a partir de H1 = [1]:

1 1

1 1

2 22

2 2

n n

nn n

− −

− −

⎡ ⎤= ⎢ ⎥

−⎢ ⎥⎣ ⎦

H HH

H H 2

1 11 1

⎡ ⎤= ⎢ ⎥−⎣ ⎦

H 2 24

2 2

1 1 1 11 1 1 11 1 1 11 1 1 1

⎡ ⎤⎢ ⎥− −⎡ ⎤ ⎢ ⎥= =⎢ ⎥ ⎢ ⎥− − −⎣ ⎦⎢ ⎥− −⎣ ⎦

H HH

H H

4 48

4 4

1 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 1

⎡ ⎤⎢ ⎥− − − −⎢ ⎥⎢ ⎥− − −⎢ ⎥− − − −⎡ ⎤ ⎢ ⎥= =⎢ ⎥ ⎢ ⎥−

−

− − − −⎣ ⎦ ⎢ ⎥− − − −⎢ ⎥

⎢ ⎥− − − −⎢ ⎥

− − − −⎢ ⎥⎣ ⎦

H HH

H H e assim por diante.

• Cada linha da matriz define uma sequência de Walsh.

• As sequências e funções de Walsh são ortogonais entre si (logo, não há interferência entre sinais sincronizados transmitidos da mesma estação CDMA).

Exemplo: Tomando H4 como ponto de partida criamos quatro sequências e quatro funções:

t T

s1(t)1

-1

t

s2(t)1

-1

t

s3(t)1

-1

t

s4(t)1

-1

Funções de Walsh Sequências de Walsh

s2 = +1 -1 +1 -1

s1 = +1 +1 +1 +1

s3 = +1 +1 -1 -1

s4 = +1 -1 -1 +1

si•sj = 0, i ≠ j

As funções de Walsh são ortogonais entre si. Por exemplo, . 1 30( ) ( ) 0

Ts t s t dt =∫


Sequências de Barker

Uma sequência de Barker é uma sequência de N valores 1ia = ± , tais que 1, ,i = … N

11i i j

ia a +

=≤∑

N j−1 para 1 j N≤ ≤ − . Por outras palavras, a função de autocorrelação

aperiódica ( )aR j satisfaz 1

( ) 1a i ii

R j a a +=

= ≤∑N j

j

− para 1, , 1j N= −… .

Só se conhecem as seguintes sequências de Barker:

Comprimento,

N

Sequência

2 + + / + -

3 + + -

4 + + + - / + + - +

5 + + + - +

7 + + + - - + -

11 + + + - - - + - - + -

13 + + + + + - - + + - + - +

(+ significa +1 e – significa -1)

Sabe-se1 que, se existir outra sequência de Barker, esta tem de ter comprimento N > 1 898 884.

As sequências de Barker são provavelmente o exemplo mais conhecido de sequências com valores baixos da função de autocorrelação aperiódica.

Exemplo com a sequência +1 +1 +1 -1 +1 (N = 5):

j = 1 + + + - + (1) 1 1 1 1 0aR = + − − =

+ + + - +

j = 2 + + + - + (2) 1 1 1 1aR = − + =

+ + + - +

Valores de Ra(j) para j= 0,1, …,4: {5 0 1 0 1}.

1 Fonte: The Mobile Communications Handbook, Jerry D. Gibson (ed.), CRC Press/IEEE Press, 2ª ed., 1999.


Sequências de Barker

Valores da autocorrelação aperiódica Ra(j)

N Sequência { }(0) (1) ( 1)a a aR R R N −…

2 +1 +1 {2 1} +1 -1 {2 -1}

3 +1 +1 -1 {3 0 -1}

4 +1 +1 +1 -1 {4 1 0 1} +1 +1 -1 +1 {4 -1 0 1}

5 +1 +1 +1 -1 +1 {5 0 1 0 1}

7 +1 +1 +1 -1 -1 +1 -1 {7 0 -1 0 -1 0 -1}

11 +1 +1 +1 -1 -1 -1 +1 -1 -1 +1 -1 {11 0 -1 0 -1 0 -1 0 -1 0 -1}

13 +1 +1 +1 +1 +1 -1 -1 +1 +1 -1 +1 -1 +1 {13 0 1 0 1 0 1 0 1 0 1 0 1}

A função de autocorrelação periódica de qualquer sequência só assume dois valores. Por exemplo, para N = 7:

{ } { }(0) (1) (6) 7 1 1 1 1 1 1R R R = − − − − − −… .


Sequências pseudo-aleatórias

• Uma sequência pseudo-aleatória (ou sequência PN, de “Pseudo Noise”) é gerada por um circuito com um registo de deslocamento, portas “OU exclusivo” e uma malha de realimentação.

• A sequência é periódica e tem características que a tornam parecida com uma sequência verdadeiramente aleatória.

• O período de uma sequência é, no máximo, 2nN 1= − , sendo n o número de andares do registo de deslocamento.

• Uma sequência de período máximo chama-se sequência de comprimento máximo, ou sequência m.

• É desejável que o período da sequência PN seja elevado para que esta seja aparentemente mais aleatória:

⇒ número de andares, n, deve ser elevado.

⇒ a sequência deve ser de comprimento máximo.

• Um gerador de sequências é definido por um polinómio de grau n de coeficientes binários – o polinómio gerador, ou polinómio característico (ver exemplo abaixo). Se a sequência tiver comprimento máximo o polinómio diz-se primitivo.

Exemplo de um gerador de sequências PN (n=6) (Configuração de Fibonacci)

++

1 1 0 1 0 0

O seu polinómio gerador, ou polinómio característico, é

6 4( ) 1g x x x x= + + +

O conteúdo inicial, 110100, corresponde ao polinómio 5 4( )a x x x x2= + + .



Polinómios e seus recíprocos

Vamos lidar com polinómios de coeficientes binários, habitualmente representados de três maneiras:

• Polinómio binário propriamente dito

(note-se a ordem decrescente das potências) 5( ) 1g x x x= + +

• Vector binário

5( ) 1g x x x= + + → 100011 (são os coeficientes do polinómio)

• Representação em octal

5( ) 1g x x x= + + → 100.011 → 438

O polinómio recíproco, , de um polinómio binário de grau n obtém-se ( )rg x ( )g xinvertendo a representação binária de . ( )g x

Analiticamente os dois polinómios estão relacionados por

( )( ) 1nrg x x g x=

Exemplo:

5 5( ) 1 100011 110001 ( ) 1rg x x x g x x x= + + → → → = + +4

+

ou

1 5 5 1 5 4( ) ( ) ( 1) 1nrg x x g x x x x x x− − −= = + + = +



Como calcular analiticamente a saída do gerador PN, sabendo o polinómio gerador e o conteúdo inicial?

Vamos tomar o gerador anterior como exemplo.

Polinómio: . Recíproco: 6 4( ) 1g x x x x= + + + 6 1 6 5 2( ) ( ) 1rg x x g x x x x−= = + + +

1. Multiplica-se o polinómio do conteúdo inicial pelo recíproco do polinómio gerador:

( )( )5 4 2 6 5 2 11 9 8 6 5

( )( ) ( ) 1r

a xa x g x x x x x x x x x x x x x

′= + + + + + = + + + + + 2

2. Obtém-se o polinómio de grau ( )a x′ 1n≤ − com os n termos de menor grau de : ( ) ( )a x g xr

5 2( )a x x x′ = +

3. A sequência PN (isto é, a saída do gerador) é o quociente

5 2

2 4 5 6 9 11 126 5 2

( )( )( ) 1r

a x x xb x x x x x x x xg x x x x

′ += = = + + + + + + +

+ + +…

A divisão faz-se escrevendo os polinómios por ordem crescente do grau, como se mostra a seguir:

2 5 2 5 6

2 4 7 8 2 4 5 6 9 11 12

4 5 7 8

4 6 9 10

5 6 7 8 9 10

5 7 10 11

6 8 9 11

6 8 11 12

9 12

9 11 14 15

11 12 14 15

11 13 16 17

12 13 14 15 16

1x x x x x

x x x x x x x x x x x

x x x x

x x x x

x x x x x x

x x x x

x x x x

x x x x

x x

x x x x

x x x x

x x x x

x x x x x x

+ + + +

+ + + + + + + + + +

+ + +

+ + +

+ + + + +

+ + +

+ + +

+ + +

+

+ + +

+ + +

+ + +

+ + + + +

…

17

( )b x

Saída: 0010111001011…

⇓



Outro exemplo de cálculo algébrico de uma sequência PN

++

1 0 0

b a c d

3 2( ) 1g x x x x= + + + 2( )a x x=

( )b x

Polinómio recíproco: ( ) 3 2 3 2( ) 1 1111 1111 ( ) 1rg x x x x g x x x x= + + + → → → = + + + ( )g x=

1. ( )2 3 2 5 4 3 2( ) ( ) 1ra x g x x x x x x x x x= + + + = + + +

2. 2( )a x x′ =

3. 2

2 3 6 7 10 112 3

( )( )( ) 1r

a x xb x x x x x x xg x x x x

′= = = + + + + + +

+ + +…

A sequência de saída é, portanto, b = 001100110011… e tem período 4.

Confirmação através do circuito:

a b c d (saída)

1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 : : : :

Esta não é uma sequência de comprimento máximo pois o seu período não é o

maior possível, . Logo, o polinómio 2 1 7nN = − = 3 2 1x x x+ + + não é primitivo.



O período de uma sequência PN depende do conteúdo inicial, excepto se a sequência for de comprimento máximo

Exemplo com o mesmo gerador mas com conteúdo inicial 101 ( ) 2( ) 1a x x= +

( )( )2 3 2 5 4

( )( ) ( ) 1 1 1r

a xa x g x x x x x x x x

′= + + + + = + + +

2 4 6 8 10 122 3

( ) 1( ) 1( ) 1r

a x xb x x x x x x xg x x x x

′ += = = + + + + + + +

+ + +…

Sequência de saída: 101010101010… (período: 2)

Confirmação através do circuito:

a b c d (saída)

0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 … … … …

Se o polinómio característico fosse primitivo qualquer conteúdo inicial originaria uma sequência de comprimento máximo.

Se experimentar com o polinómio 3 1x x+ + (um polinómio primitivo) verificará

que o período é 7, independentemente do conteúdo inicial.

Vamos ver em seguida como determinar o maior período atingível com um dado polinómio gerador.


Sequência pseudo-aleatórias

Como calcular o período máximo que é possível obter com um dado gerador de sequências PN

O período máximo é o menor inteiro m para o qual 1mx + é múltiplo de ( )g x

Vamos tomar como exemplo o polinómio 3 2( ) 1g x x x x= + + + atrás usado:

1 0 0 0 0 1 1 1 11 1 1 10 1 1 1 0

1 1 1 1 0 0 0 1

1 1

1x +

3 2 1x x x+ + +4x

Dividiu-se o polinómio mx (dado na forma vectorial 100000…) por 3 2 1x x x+ + +

(1111) até dar resto 1. Depois basta contar o número de zeros.

(Porquê? Porque se mod ( ) 1mx g x = então ( )1 mod ( ) 0mx g x+ = )

Como (4 3 2mod 1 1x x x x )+ + + = então o período máximo atingível por g(x) é 4.

Outros exemplos:

1. 4 2( ) 1g x x x x= + + +

O menor m tal que é múltiplo de é 7: 1mx + ( )g x

( ) ( )7 4 21 mod 1 0x x x x+ + + + = ⇒ período máximo é 7 com este g(x)

2. 8 6 4 2( ) 1g x x x x x= + + + +

O menor m tal que é múltiplo de é 10: 1mx + ( )g x

( ) ( )10 8 6 4 21 mod 1 0x x x x x+ + + + + = ⇒ período máximo é 10


Sequências de comprimento máximo

Algumas propriedades das sequências de comprimento máximo

1. Propriedade do balanço

Em cada período de uma sequência m o número de “uns” é igual ao número de “zeros” mais um:

Número de “uns”: 12n−

Número de “zeros”: 12 1n− −

2. Propriedade das séries

• Uma série é uma subsequência de bits iguais (0 ou 1). O número de bits iguais é o comprimento da série.

• Número total de séries (de zeros e uns): 1( 1) 2 2nN −+ =

Em cada período metade das séries de “uns” ou “zeros” têm comprimento 1, um quarto têm comprimento 2, um oitavo têm comprimento 3, etc.

Qualquer grupo não nulo de s bits, s n≤ , ocorre 2n s− vezes e o grupo de s bits

nulos ocorre 2 vezes. Assim, qualquer grupo de n bits ocorre só uma vez. 1n s− −

3. Função de autocorrelação

A função de autocorrelação é periódica (período N) e vale

(só tem dois valores) 0

( )1 1 2 2n

N jR j

j

=⎧⎪= ⎨− ≤ ≤ −⎪⎩

Uma maneira possível de calcular a função de autocorrelação é a seguinte: conta-se em quantos lugares a sequência a1a2…aN concorda com o seu deslocamento

. Se C for esse valor e D o número de lugares discordantes, então ajaj+1…aN a1…aj−1

( )R j C D= −



Exemplo de um gerador de sequência PN de comprimento máximo

+

5 4 3 2 1

• Período da sequência: 2 1 3nN = − = 1

(⇒ é uma sequência de comprimento máximo, ou sequência m)

• Modos de representação de sequências PN:

• através dos andares interligados

Neste caso: andares 1 e 3.

• através de um vector (binário ou em octal)

Neste caso: 1001012 = 458

• através de um polinómio binário (polinómio gerador ou característico)

Neste caso: x5 + x2 + 1

Um polinómio primitivo é um polinómio que gera uma sequência m. Logo, o

polinómio x5 + x2 + 1 é um polinómio primitivo.

• Exemplo de sequência:

1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 …

• Função de autocorrelação (normalizada)

-30 -20 -10 0 10 20 30-0.5

0

0.5

1



Exemplo de sequência PN de comprimento máximo (cont.)

As sequências m satisfazem a propriedade das séries:

Comprimento da série

Fracção

1 1 2

2 1 4

3 1 8

i 1 2 i

e ao todo existem 1

2N +

séries de “zeros” e “uns”.

Neste exemplo a sequência PN tem o seguinte período:

1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 …

• Número de séries:

1 162

N += (oito séries de “zeros” e oito séries de “uns”)

Comprimento

da série Número Fracção

1 4 séries de “zeros” 4 séries de “uns”

50%

2 2 séries de “zeros” 2 séries de “uns”

25%

3 1 série de “zeros” 1 série de “uns”

12,5%

4 1 série de “zeros” 0 séries de “uns”

6,25%

5 1 série de “uns” 6,25%

Quantas vezes num período surgem padrões de bits? Por exemplo, os grupos 110 e

0010 ocorrem vezes e 5 32 2 4n s− −= = 5 42 2 2n s− −= =5 22 1 2− −− = − =

vezes, respectivamente. Por seu

lado o grupo 00 aparece vezes. Confirmou? 1 7n s



Definição alternativa de polinómios primitivos

O polinómio de grau n g(x) é um polinómio primitivo se o menor m para o qual xm + 1 é divisível por g(x) for igual a m = 2n – 1.

Uma tabela de factorizações dos polinómios xm + 1 é útil para a determinação de polinómios primitivos.

O polinómio recíproco de um polinómio primitivo também é primitivo.

Exemplos (n = 5):

• é primitivo pois o menor m para o qual x5 4 2( ) 1g x x x x x= + + + + m + 1 é múltiplo de

g(x) é : 52 1 2 1 31nm = − = − =

) 31 1 ( ) (x g x Q x+ = (Q(x) é o quociente)

Pode provar-se que m = 31 é o menor possível dividindo-se a palavra binária 1000…0 (correspondente a xm ) por 110111 (representação de g(x) em binário) e terminando a divisão quando o resto for 1; depois é só contar o número de zeros do dividendo (31) para saber o valor de m.

Um gerador de sequências PN baseado neste polinómio gera sequências de comprimento 31 (ou seja, de comprimento máximo).

• não é primitivo pois 5 4 3 2( ) 1g x x x x x x= + + + + + 2 1 3nm 1= − = não é o menor inteiro

para o qual é múltiplo de g(x). De facto o menor m é 6, para o qual 311 1mx x+ = +6 1 ( 1) ( )x x+ = + g x .

Um gerador de sequências PN baseado neste polinómio gera sequências de período não superior a 6 (em vez de 31).



Número de sequências m com um determinado comprimento

P.: Com um registo de deslocamento de n andares quantas sequências PN de comprimento máximo se podem obter?

R.: Existem diversas interligações (ou polinómios primitivos) que conduzem a sequências de comprimento máximo. O seu número é dado por

(2 1)n

nφ −

em que φ (x ) é a função de Euler, que indica o número de inteiros não superiores e

primos com x.

Exemplo: φ (35) = 24 (confirme!)

Número de sequências m

n Período,

N = 2n −1

Nº de sequências m

3 7 2

4 15 2

5 31 6

6 63 6

7 127 18

8 255 16

9 511 48

10 1023 60

Por exemplo, os polinómios 5 3 1x x+ + (=518) e 5 4 3 1x x x x+ + + + (=738) produzem

duas das seis sequências m de comprimento 31.


A função de Euler

Como calcular a função de Euler?

Se quisermos calcular a função de Euler de um determinado número inteiro devemos em primeiro lugar factorizá-lo. Assim:

Se , 1, 2, ,ip i = … I , forem os I factores primos de N então:

φ (N ) = N pi −1pii=1

I

∏

Exemplo: N = 360 = 23 × 32 × 5 ⇒ p1 = 2 , p2 = 3 e p3 = 5

φ (360) = 360 pi −1pi

= 360 ×12i=1

3

∏ ×23

×45

= 96

Casos particulares

1. Se N for a potência de um número primo p, isto é, se N = pr , sendo r inteiro, então

φ (N ) = φ ( pr ) = pr p −1p

2. Se N tiver dois factores primos, p e q, isto é, se , sendo r e s inteiros, então r sN p q=

1 1( ) ( ) ( 1)( 1)r s r sN p q p q p qφ φ − −= = − −

Exemplo: 263 3 7N = = × ⇒ 3p = , 7q = , 2r = e 1s =

2 1 0(63) (3 7) 3 7 2 6 36φ φ= × = × × × =


A função de Euler

φ (N ) = N pi −1pii=1

I

∏

0 20 40 60 80 1000

10

20

30

40

50

60

70

80

90

100

φ(x)

x



Alguns polinómios primitivos para geração de sequências m

n Polinómios primitivos

3 x3 + x +1

4 x4 + x +1

5 x5 + x2 +1

6 x6 + x +1

7 x7 + x3 +1

8 x8 + x4 + x3 + x2 + 1

9 x9 + x4 +1

10 x10 + x3 +1

• Além dos polinómios da tabela existem outros polinómios primitivos com o mesmo grau (ver Tabela da página seguinte). Todos eles geram sequências de comprimento máximo.

• O número de polinómios primitivos de um determinado grau é igual ao número de

sequências m, isto é, (2 1)nφ −

n.

Exemplo: como existem 16 sequências m de comprimento 255 (logo, n = 8)

concluimos que existem 16 polinómios primitivos de grau 8.

• Estes polinómios indicam os andares do registo de deslocamento a interligar em “feedback”.

• Existem tabelas de polinómios primitivos publicadas. Um exemplo é o livro clássico de W. Peterson e E. Weldon, “Error Correcting Codes”, MIT Press, 1972.



Tabela de polinómios primitivos

A tabela seguinte indica metade dos polinómios primitivos de grau ≤10. A outra metade é constituída pelos seus recíprocos, pois estes também são primitivos.

Exemplos:

4 48 8( ) 1 23 10.011 11.001 31 ( ) 1rg x x x g x x x= + + → → → → → = + 3 +

2

3 3

8 8( ) 1 13 1.011 1.101 15 ( ) 1rg x x x g x x x= + + → → → → → = + +

Polinómios primitivos de grau n ≤ 10

Grau n

Representação em octal (menor potência à direita)

2 7* 3 13* 4 23* 5 45*, 75, 67 6 103*, 147, 155 7 211*, 217, 235, 367, 277, 325, 203*, 313, 345 8 435, 551, 747, 453, 545, 537, 703, 543 9 1021*, 1131, 1461, 1423, 1055, 1167, 1541,

1333, 1605, 1751, 1743, 1617, 1553, 1157 10 2011*, 2415, 3771, 2157, 3515, 2773, 2033,

2443, 2461, 3023, 3543, 2745, 2431, 3177

Nota 1: o asterisco indica um circuito com apenas duas interligações. O circuito torna-se mais

simples.

Nota 2: a tabela não inclui polinómios recíprocos pelo que só estão indicados metade dos polinómios

primitivos possíveis.

Nota 3: Tabela extraída de R. Peterson, R. Ziemer e D. Borth, “Introduction to Spread Spectrum

Communications”, Prentice-Hall, 1995.


Sequências binárias periódicas

Função de autocorrelação: definição genérica

Seja a sequência 1 2[ ]Na a a=a … uma sequência binária {0,1} e periódica (com

período N). A sua função de autocorrelação é definida como*

1

( ) (2 1)(2 1) 0 1N

i i ji

R j a a j N+=

= − − ≤ ≤∑ −

Como já se disse antes, uma maneira prática de calcular a função de autocorrelação é contar em quantos lugares a sequência 1 2 Na a a

1

… concorda com o seu deslocamento 1 1j j N j+ … …a a a a a − . Se C for esse valor e D o número de lugares

discordantes, então

( )R j C D= −

• A função de autocorrelação é periódica:

( ) ( )R j rN R j+ = , para r inteiro.

• Se c representar uma sequência polar {±1}:

1

( ) 0 1N

i i ji

R j c c j N+=

= ≤∑ ≤ −

Caso particular: sequências PN de comprimento máximo

• As funções de autocorrelação de sequências m só têm dois valores, N e -1 (ou 1 e -1/N, na versão normalizada).

* Há quem defina esta função normalizando-a por divisão por N. Sequências pseudo-aleatórias e outras 22

Sequências binárias periódicas

Função de correlação cruzada e minorante de Welch

Se 1 2[ ]Na a a=a … e 1 2[ ]Nb b b=b … forem duas sequências binárias de valores {0,1} e

periódicas (com período N), a função de correlação cruzada entre a e b é definida como

1

( ) (2 1)(2 1) 0 1N

c i i ji

R j a b j N+=

= − − ≤ ≤∑ −

Normalmente é desejável que a função de correlação cruzada entre sequências tenha valores baixos.

Minorante de Welch O valor absoluto máximo da correlação cruzada entre qualquer par de sequências

binárias com período N retirado de um conjunto de M sequências respeita

max1( )1c

MR j NMN

−≥

−

Se M e N elevados: max( )cR j N≥

Caso particular: sequências PN de comprimento máximo

• As funções de correlação cruzada entre sequências m diferentes têm vários valores, com picos relativamente elevados.

• Se as funções de correlação cruzada só tiverem três valores diz-se que as sequências constituem um par preferido, ou que se trata de sequências preferidas.

Esses três valores estão centrados em -1 e são:

{ }( ), 1, ( ) 2t n t n− − − , com ( 2) 2( ) 2 1nt n +⎢ ⎥⎣ ⎦= + .

• Não há pares preferidos para sequências com número de andares múltiplo de 4.



Exemplos de funções de correlação cruzada

• , polinómios 63N = 6 5 4 1x x x x+ + + + (1638) e 6 5 2 1x x x x+ + + + (1478)

• , polinómios 63N = 6 5 4 1x x x x+ + + + (1638) e 6 5 1x x+ + (1418)

Esta função de correlação cruzada só tem três valores, isto é, as sequências geradas por 1638 e 1418 são um par preferido.



Exemplos de funções de autocorrelação e correlação cruzada

Seja n = 10, para o qual o comprimento máximo é 1023. Assim:

• Existem (1023) 6010

φ= sequências. Com estas sequências podem-se formar

pares. Destes há três (apenas!) que entre si são pares preferidos.

601770

2⎛ ⎞

=⎜ ⎟⎝ ⎠

• A função de autocorrelação ( )R j tem dois valores: { }1023, 1− .

• O valor máximo absoluto das funções de correlação cruzada ( )cR j entre as sessenta

sequências m é igual a 383, isto é, 37% do valor máximo da autocorrelação, R(0)*.

• Com um par preferido ( )cR j assume três valores:

(10 2) 2(10) 2 1 65t +⎢ ⎥⎣ ⎦= + = ⇒ { }( ) 65, 1,63cR j ∈ − −

O valor máximo absoluto de ( )cR j vale max

( ) 65cR t n= = , isto é, 6% de (0)R .

Repare-se que, enquanto no conjunto das 60 sequências o pico da função de correlação cruzada é 37% de (0)R , no caso dos pares preferidos esse pico baixou para 6%

(cerca de seis vezes menos!).

Existem sequências derivadas das sequências m que têm funções de correlação cruzada periódica com melhores propriedades: as sequências de Gold e de Kasami.

* Ver tabela 8.2.1 de J. Proakis, “Digital Communications”, McGraw-Hill, 2ª edição, 1989. Sequências pseudo-aleatórias e outras 25


Decimações e pares preferidos

• O que é uma decimação?

A decimação de uma sequência por 4 (por exemplo) é obtida colhendo elementos da sequência de quatro em quatro valores.

Chamemos a a decimação da sequência a por q. [ ]qa

A decimação por 2 ou por uma potência de 2 é simplesmente uma versão ciclicamente

deslocada da sequência original.

• Uma sequência m de comprimento 2nN 1= − pode ser obtida a partir de outra sequência m de igual comprimento: faz-se a decimação da sequência por um inteiro q que seja primo com N:

. . .( , ) 1m d c N q =

Uma decimação que origina uma sequência de igual comprimento diz-se própria.

• Período da sequência , em que a é uma sequência m: [ ]qa. . .( , )

Nm d c N q

Exemplo: a = 1110100 ⇒ N = 7

Se q = 6 ⇒ m.d.c.(7,6) = 1 ⇒ é decimação própria ⇒ a[6] = 1001011.

Condições suficientes para que duas sequências a e b de comprimento máximo constituam um par preferido 2 1nN = −

1 1

1. (isto é, n não é múltiplo de 4) 0 mod 4n ≠

2. , em que q é ímpar e [ ]q=b a

ou 2kq = + 22 2k kq = − +

3. 1 n ímpar

. . .( , )2 =2 mod

m d c n kn

⎧= ⎨

⎩ 4



Exemplo de obtenção de pares preferidos

P.: Determinar um par preferido de sequências m de comprimento 31. Uma das sequências é gerada pelo polinómio 45.

R.: N = 31, n = 5

A determinação da outra sequência do par é feita decimando a primeira sequência por um inteiro ímpar q: . [ ]q=b a

Para que tenha o mesmo comprimento 31 a decimação tem de ser própria,

isto é, q e N têm de ser primos entre si:

[ ]q=b a

. . (31, ) 1m d c q =

Seja . Esta escolha é adequada porque satisfaz as três condições suficientes

para obtenção de pares preferidos:

3q =

1. O grau não é múltiplo de 4. 5n =

2. é ímpar. 3q =

⇒ ⇒ 3 2 1kq = = + 1k =

3. Sendo n ímpar: . . ( , ) . . (5,1) 1m d c n k m d c= =

As sequências preferidas obtidas são as seguintes:

a =b =

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 301 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 01 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0



Pares preferidos

As figuras seguintes apresentam todos os pares preferidos de comprimento 31 e 63. Os pares preferidos são aqueles que estão ligados através de uma linha.

Período 31

57

73 45

67

75

51

Período 63

163

133 103

155

147

141

In Sarwate, D. V. e Pursley, M. B., "Crosscorrelation Properties of Pseudorandom and Related

Sequences", Proceedings of the IEEE, Maio de 1980, pp. 593-619.


Sequências de Gold

Uma sequência de Gold é obtida combinando duas sequências PN preferidas por deslocamento de uma delas relativamente à outra.

• { }1, , , , , NGoldS T −= ⊕ ⊕ ⊕a b a b a b a b… T

12 2 1nN + = +

Tib – b é deslocada de i bits

• Como são possíveis deslocamentos de uma sequência relativamente à

outra, existem sequências de Gold de comprimento N (incluindo as duas sequências originais).

2nN = −

• As funções de correlação cruzada só têm três valores, como já acontecia com os pares preferidos originais:

{ }( ), 1, ( ) 2t n t n− − − .

n Período N Rc ( j) Frequência de ocorrência

n ímpar N = 2n −1 −1 ≈ 0,50 −t(n) ≈ 0,25 t(n) − 2 ≈ 0,25

n par e N = 2n −1 −1 ≈ 0,75 não divisível −t(n) ≈ 0,125 por 4 t(n) − 2 ≈ 0,125

• A vantagem relativamente às sequências m é que passa a haver mais sequências (de Gold) com funções de correlação cruzada só com três valores. Isso é desejável em certas aplicações (CDMA, por exemplo).

Exemplo: existem 3 (três!) sequências m preferidas de comprimento 1023;

existem 1025 sequências de Gold de comprimento 1023.

• As sequências preferidas originais são sequências m mas as outras N sequências não são, embora tenham o mesmo período; logo, as funções de autocorrelação destas têm mais de dois valores. Os valores fora do pico (j ≠ 0) são retirados do mesmo trio de valores acima.


Sequências de Gold

Geração de sequências de Gold

A partir de um par preferido 1 2[ ]Na a a=a … e 1 2[ ]Nb b b=b … constrói-se um

conjunto de novas sequências de igual comprimento N somando (módulo 2) uma das

sequências com cada um dos deslocamentos possíveis da outra. Obtêm-se

assim N novas sequências periódicas de período

2 1nN = −2 1nN = − .

Exemplo: Os polinómios e 5 2 1x x+ + 5 4 2 1x x x x+ + + + geram sequências preferidas de comprimento 31. Então podemos usar os geradores destas sequências para obter sequências de Gold:

+

++ +

+

Sequênciade Gold

Consoante o conteúdo inicial dos registos de deslocamento assim vamos obter N + 2 = 33 sequências de comprimento 31 cujas funções de correlação cruzada só têm três valores,

{ } { }(5), 1, (5) 2 9, 1, 7t t− − − = − −

Repare-se que só existem seis sequências m de comprimento 31; destas nem todas têm funções de correlação cruzada só com três valores. Em contrapartida, existem 33 sequências de Gold nessas condições.


Sequências de Kasami

Com um procedimento análogo ao usado para gerar sequências de Gold constrói-se um conjunto mais pequeno de sequências com propriedades de correlação cruzada ainda melhores: as sequências de Kasami (melhor dizendo, o "pequeno conjunto" de sequências de Kasami).

Uma sequência do pequeno conjunto de Kasami é obtida combinando uma sequência de comprimento máximo a (de período 2 1n − , com n par) com uma sua versão decimada, a a . ' [ ]q=

• 22nq = +1 ⇒ a' tem período 22 1n − .

• Repetindo a' q vezes obtém-se uma nova sequência, b, de comprimento 2 1nN = − ⇒

q

′ ′ ′=b a a a…

• Com a e b formamos um novo conjunto de sequências somando (mód. 2) a a b e a 2 2n2 − deslocações cíclicas de b:

( )22 2, , , ,

n

KS T T−⎧ ⎫= ⊕ ⊕ ⊕⎨ ⎬

⎩ ⎭a a b a b a b…

• Ao todo (incluindo a) temos 22n sequências no pequeno conjunto de Kasami.

• A função de correlação cruzada entre sequências de Kasami assume três valores centrados em -1:

{ }( ), 1, ( ) 2s n s n− − − , com [ ]2 1( ) 2 1 ( ) 12

ns n t n= + = +

Estes valores são ainda mais baixos que os obtidos com sequências de Gold.

• A função de autocorrelação (j ≠ 0) assume os mesmos três valores.

• max( ) ( )cR j s= n aproxima-se bastante do menor valor possível (o minorante de

Welch) ⇒ nesse respeito as sequências do pequeno conjunto de Kasami são assimptoticamente óptimas.


Pequeno conjunto de sequências de Kasami: um exemplo

Seja a uma sequência m com 6n = e período 63.

• Se se fizer uma decimação de a por 22 1nq 9= + = a sequência a' obtida tem período 22 1 7n − = .

• Considerem-se repetições de a'. A nova sequência é b. 9q =

• Como obter as sequências de Kasami?

+

a

b

Sequênciade Kasami

• Existem 22 2 2n − + = 8 sequências de Kasami de grau 6n = .

• A função de correlação cruzada entre sequências toma três valores:

{ } { }(6), 1, (6) 2 9, 1, 7s s− − − = − −

visto [ ]1(6) (6) 1 92

s t= + = .

• Comparação com sequências m e de Gold de igual período:

• Sequências m: 6 sequências (das quais 2 são preferidas)

• Sequências de Gold: 65 sequências e { }( ) 17, 1,15cR j ∈ − −


Pequeno conjunto de sequências de Kasami: outro exemplo

Seja n = 4 e o polinómio primitivo 4 1x x+ + produzindo a sequência m a = 100010011010111.

• 2 22 1 2 1nq = + = + = 5

• Decimando a por 5 obtemos a sequência a', de período 2 22 1 2 1n 3− = − = :

[5] 101′ = =a a

• Repetindo a' cinco vezes obtemos

b = 101101101101101

• Existem ao todo 22n = 4 sequências no pequeno conjunto de Kasami: uma delas é a própria sequência a e as outras três são obtidas somando essa sequência a b e aos seus deslocamentos:

100010011010111101101101101101

→→ ⊕⊕ →

aba b 001111110111010

100010011010111011011011011011T

T

→→ ⊕

⊕ →

ab

a b 111001000001100

2

2

100010011010111110110110110110T

T

→

→ ⊕

⊕ →

a

b010100101100001a b

Pode confirmar-se que a função de correlação cruzada entre quaisquer duas

sequências dos pares de sequências só tem valores do conjunto {4⎛ ⎞ 62

=⎜ ⎟⎝ ⎠

}5, 1, 3− − . O

mesmo se passa com a função de autocorrelação para j ≠ 0. Em a , por exemplo: , e .

⊕ b(1) 3R = (3) 1R = − (5) 5R = −


O “grande conjunto” de sequências de Kasami

• O grande conjunto de sequências de Kasami contém as sequências de Gold e o pequeno conjunto de sequências de Kasami.

• Tal como as do pequeno conjunto, também as sequências do grande conjunto têm

período 2 , em que n tem de ser par. 1n

1

−

• Vantagem sobre sequências de Gold: há mais sequências.

• Desvantagem sobre sequências do pequeno conjunto: correlação cruzada mais elevada.

Como obter estas sequências?

1. A partir de uma sequência a de comprimento máximo 2nN = − , n par, obtêm-se duas outras sequências m por decimação:

( 2) 2[ ( )] [2 1]nt n += =b a a +

2[ ( )] [2 1]ns n= =c a a + , período 22 1n −

2. As sequências do grande conjunto são formadas adicionando as três sequências a, b e c com diferentes deslocamentos de b e c:

Se : 0 (mod 4)n =

{ }( ) ( ) ( ), , , ,k j m j m k j mKLS T T T T′ ′ ′= ⊕ ⊕ ⊕ ⊕ ⊕a a b a c b c a b cT

2 2

0,1,2 0, , (2 1) 3 1

0, , 2 2 0, , (2 1) 3 1

n

n n

j k

m m

′= = −

′

−

= − = −

…

… … −

b(j), j = 0,1,2 é a decimação de Tja por t(n): ( )[ ]( ) ( )j jb T t n= a .

Se : 2 (mod 4)n =

{ }, , , , ,k m m kKLS T T T T= ⊕ ⊕ ⊕ ⊕ ⊕a b a b a c b c a b mT c

2

0, , 2 2

0, , 2 2

n

n

k

m

= −

= −

…

…


O “grande conjunto” de sequências de Kasami

• Número de sequências do grande conjunto de Kasami:

3 2 2

3 2 2

2 2 1 0(mod 4)

2 2 2(mod

n n

n n

M n

M n

⎧ = + − =⎪⎨

= + =⎪⎩ 4)

• As funções de correlação cruzada e de autocorrelação (para j ≠ 0) têm cinco valores:

{ } { }2 ( 2)( ), ( ), 1, ( ) 2, ( ) 2 1, 1 2 , 1 2n nt n s n s n t n +− − − − − = − − ± − ± 2

Exemplo: seja n = 4 e a sequência m a = 100010011010111.

• ( 2) 2

3 repetiçoes[ ( )] [2 1] [9] 100101001010010nt n += = + = =b a a a (período N/3 = 5)

• 2

2

2 +1=5 repetiçoes

[ ( )] [2 1] [5] 101101101101101n

ns n= = + = =c a a a (período 22 1n − = 3 )

• { }( ) 9, 5, 1,3,7cR j ∈ − − −

• Existem 3 2 22 2 1 6n n+ − = 7 sequências:

{ }( ) ( ) ( ), , , ,k j m j k j mKLS T T T′ ′= ⊕ ⊕ ⊕ ⊕ ⊕a a b a c b c a b cT

0,1, 20,1, , 40,1, 20

jkmm

=′ ==′ =

…

Vamos obter duas delas:

( )2 (1) 2

2 (1)

100010011010111( )[9] 111011110111101T T T

T

→

= → ⊕

⊕ →

a

b a011001101101010a b

3 (2)

2

3 (2) 2

100010011010111

110001100011000

110110110110110

T

T

T T

→

→

⊕→

⊕ ⊕ →

a

b

c

100101001111001a b c


Valores absolutos máximos da função de correlação cruzada

n Sequências m

Sequências de Gold


(peq. conj.)


(grande conj.)

Minor. de Welch,

Nº Valor máximo

Nº Valor máximo

Nº Valor máximo

Nº Valor máximo

N

3 2 5 9 5 — — — — 2,6

4 2 9 — — 4 5 67 9 3,9

5 6 11 33 9 — — — — 5,6

6 6 23 65 17 8 9 520 17 7,9

7 18 41 129 17 — — — — 11,3

8 16 95 — — 16 17 4111 33 16,0

9 48 113 513 33 — — — — 22,6

10 60 383 1025 65 32 33 32800 65 32,0

11 176 287 2049 65 — — — — 45,2

12 144 1407 — — 64 65 262207

129 64,0


Documents

Sequências PN e outras - paginas.fe.up.ptpaginas.fe.up.pt/~sam/CCD/apontamentos_SS/Sequencias_PN.pdf · Sequências e funções de Walsh • As sequências e funções de Walsh baseiam-se