±1-följd

±1-följd är inom matematiken en följd av tal som vardera antingen är 1 eller −1. Ett exempel är följden (x₁, x₂, x₃, ...), där x_i = (−1)ⁱ⁺¹.

Erdős problem

Antag att du får ett positivt tal C och en ±1-följd S=(x₁, x₂, x₃,...) där x_j betecknar den j:te termen. Erdős problem går ut på att svara på frågan om huruvida det givet vilka C och S som helst finns positiva heltal k och d sådana att

${\displaystyle \left|\sum _{i=1}^{k}x_{i\cdot d}\right|\leq C}$

Man vill alltså till varje par C och S hitta tal k och d sådana att summan av de första k talen som ligger på platser som är multipler av d är antingen C eller -C.

Barker-koder

En Barkerkod är en följd av N värden av 1 och −1.

${\displaystyle a_{j}}$ för j = 1, 2, …, N

sådant att

${\displaystyle \left|\sum _{j=1}^{N-v}a_{j}a_{j+v}\right|\leq 1\,}$

för alla ${\displaystyle 1\leq v<N}$.^[1]

Se även

• Binär följd

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, ±1-sequence, 25 december 2013.

1. Barker, R. H. (1953). ”Group Synchronizing of Binary Digital Sequences”. Communication Theory. London: Butterworth. sid. 273–287 

• Chazelle, Bernard. The Discrepancy Method: Randomness and Complexity. Cambridge University Press. ISBN 0-521-77093-9