Barker code

"Barker sequence" redirects here. For the sequence of generalized Wieferich primes, see Wieferich pair § Barker sequence.

In telecommunication technology, a Barker code or Barker sequence is a finite sequence of digital values with the ideal autocorrelation property. It is used as a synchronising pattern between the sender and receiver of a stream of bits. Apart from the trivial sequence of length 1, the known Barker sequences have lengths 2, 3, 4, 5, 7, 11 and 13. It is conjectured that no longer sequence exists; this is proved for odd lengths, while the possible existence of an even Barker sequence longer than 4 remains open.

Explanation

A stream of binary digits carries no timing information by itself: the receiver cannot tell where one group of digits ends and the next begins. Transmitting a pre-arranged pattern of digits resolves this, provided the receiver can recognise that pattern reliably. In simple terms it is equivalent to attaching a label to one digit, after which the positions of the remaining digits follow by counting.

Such a pattern is useful only if it is unlikely to be imitated by the surrounding data or by noise, and if a partial overlap between the received signal and the stored pattern gives a much weaker response than exact alignment. The relevant measure is the pattern's autocorrelation: the correlation of the pattern with a shifted copy of itself should be large at zero shift and small at every other shift, so that a correlator or matched filter in the receiver produces a sharp, unambiguous indication of the correct position. Barker sequences are the binary patterns for which these off-peak values are as small as possible; they are named after Ronald Hugh Barker, who set out this requirement for group synchronisation in 1953.

Origins and historical development

Barker sequences originate in the problem of group synchronisation in early digital communication systems: a receiver presented with a continuous stream of binary digits must establish where each group of digits begins, and does so by recognising a pre-arranged pattern inserted into the stream. In a 1953 chapter on the group synchronising of binary digital systems, Ronald Hugh Barker argued that such a pattern should have an autocorrelation function with very low off-peak values, so that it can be recognised unambiguously by the detector and is unlikely to be imitated by a random series of noise-generated bits.

Binary patterns with low off-peak autocorrelation proved useful both for synchronisation in data transmission and telemetry and, as binary phase codes, for pulse compression in radar. The question of which lengths admit such patterns was subsequently recast as a problem about binary sequences, cyclic difference sets and character sums, and was taken up by Richard Turyn, James Storer and later authors.

Definition

Graphical representation of a Barker-7 code

Autocorrelation function of a Barker-7 code

3D Doppler radar spectrum showing a Barker code of 13

A Barker code or Barker sequence is a finite sequence of N values of +1 and −1,

$a_{j}{\text{ for }}j=1,2,\dots ,N$

with the ideal autocorrelation property, such that the off-peak (non-cyclic) autocorrelation coefficients

$c_{v}=\sum _{j=1}^{N-v}a_{j}a_{j+v}$

are as small as possible:

$|c_{v}|\leq 1\,$

for all $1\leq v<N$.

Apart from the trivial sequence of length 1, nine Barker sequences are known when sequences are identified up to negation and reversal, all of length N at most 13. A stricter equivalence that also identifies sequences related by alternating sign changes reduces this to seven representatives. Barker's 1953 chapter instead imposed the stronger, one-sided condition

$c_{v}\in \{-1,0\}.$

Only four of the known sequences satisfy this stricter condition; these are shown in bold in the table below.

Since $c_{0}=N$ trivially, and for $v>0$ the sum $c_{v}$ consists of $N-v$ terms each equal to +1 or −1, it follows that $c_{v}\equiv N-v{\pmod {2}}$. Consequently the smallest value $|c_{v}|$ can take is 0 when $N-v$ is even and 1 when $N-v$ is odd; a Barker sequence attains this minimum at every nonzero shift. The Barker property is unaffected by negating every term, by reversing the sequence, and (up to a sign change in $c_{v}$) by alternating negation $a_{j}\mapsto (-1)^{j}a_{j}$; sequences related by these operations are usually treated as equivalent.

Known Barker codes

Here is a table of all known nontrivial Barker codes, where negations and reversals of the codes have been omitted. Their off-peak aperiodic autocorrelations have magnitude no greater than 1. The question whether any further codes exist is discussed in the Barker sequence conjecture section.

Known Barker codes

Length	Codes		Sidelobe level ratio
2	+1 −1	+1 +1	−6 dB
3	+1 +1 −1		−9.5 dB
4	+1 +1 −1 +1	+1 +1 +1 −1	−12 dB
5	+1 +1 +1 −1 +1		−14 dB
7	+1 +1 +1 −1 −1 +1 −1		−16.9 dB
11	+1 +1 +1 −1 −1 −1 +1 −1 −1 +1 −1		−20.8 dB
13	+1 +1 +1 +1 +1 −1 −1 +1 +1 −1 +1 −1 +1		−22.3 dB

Barker codes of length N equal to 11 and 13 are used in direct-sequence spread spectrum and pulse compression radar systems because of their low autocorrelation properties (the sidelobe level of amplitude of the Barker codes is 1/N that of the peak signal). A Barker code resembles a discrete version of a continuous chirp, another low-autocorrelation signal used in other pulse compression radars.

The positive and negative amplitudes of the pulses forming the Barker codes imply the use of biphase modulation or binary phase-shift keying; that is, the change of phase in the carrier wave is 180 degrees.

Similar to the Barker codes are the complementary sequences, which cancel sidelobes exactly when summed; the even-length Barker code pairs are also complementary pairs. There is a simple constructive method to create arbitrarily long complementary sequences.

For the case of cyclic autocorrelation, other sequences have the same property of having perfect (and uniform) sidelobes, such as prime-length Legendre sequences, Zadoff–Chu sequences (used in 3rd- and 4th-generation cellular radio) and $2^{n}-1$ maximum length sequences (MLS). Arbitrarily long cyclic sequences can be constructed.

Barker sequence conjecture

Unsolved problem in mathematics

Does there exist a Barker sequence of length greater than 13? Equivalently, does one exist of even length greater than 4?

More unsolved problems in mathematics

The Barker sequence conjecture, often attributed to Richard Turyn, states that no Barker sequence has length greater than 13. The odd-length case has been settled; the remaining question is whether an even Barker sequence of length greater than 4 exists.

Odd lengths

Turyn and Storer concluded in 1961 that, apart from the trivial length-1 case, an odd-length Barker sequence must have

$N\in \{3,5,7,11,13\}.$

In 2014, Jürgen Willms exhibited counterexamples to an intermediate theorem used in their published proof, showing that the proof as written was incomplete. The classification itself remains valid: Peter Borwein and Tamás Erdélyi gave a different proof using Barker polynomials, and Schmidt and Willms later gave a new proof.

Even lengths and exclusion bounds

A hypothetical even Barker sequence of length $N>4$ must have

$N=4u^{2}$

for an odd integer $u$, and the prime divisors of $u$ must satisfy further number-theoretic restrictions.

Successive field-descent and computational results have pushed the rigorous exclusion range far beyond the lengths accessible by direct enumeration. Bernhard Schmidt excluded $13<N<4\times 10^{12}$ in 2002, and Leung and Schmidt extended this to $13<N<10^{22}$ in 2005. In 2014, Borwein and Mossinghoff showed that a Barker sequence longer than 13 would have either

$N=3\,979\,201\,339\,721\,749\,133\,016\,171\,583\,224\,100$

or $N>4\times 10^{33}$. Leung and Schmidt subsequently eliminated the exceptional value, proving that no Barker sequence exists for $13<N\leq 4\times 10^{33}$.

Logan and Mossinghoff reported in 2017 that the smallest known integer surviving all restrictions they tested was $N=4u^{2}$, where

$u=19\,804\,304\,830\,012\,264\,298\,738\,041,$

so that $N\approx 1.57\times 10^{51}$. They noted, however, that their enumeration was complete only over a smaller parameter range, so this is not a rigorous improvement of the $4\times 10^{33}$ exclusion bound.

A 2021 preprint by Willms derived a form of weak symmetry for a hypothetical even Barker sequence and proved that none of length $N>4$ can satisfy

$c_{1}=c_{3}=\cdots =c_{N/2-1}.$

This excludes a special pattern of odd-shift correlations but does not settle the general even-length case.

Relation to circulant Hadamard matrices

For a sequence of length $N$, its periodic autocorrelation at shift $v$ is $r_{v}=c_{v}+c_{N-v}$. If a Barker sequence has even length $N>2$, then $r_{v}=0$ at every nonzero shift. The circulant matrix whose first row is the sequence therefore has mutually orthogonal rows and is a circulant Hadamard matrix of order $N$.

Ryser's conjecture on circulant Hadamard matrices states that no circulant Hadamard matrix has order greater than 4. It would therefore imply the Barker sequence conjecture. The implication is one-way: the circulant Hadamard condition controls the sums $c_{v}+c_{N-v}$, whereas the Barker condition separately requires $|c_{v}|\leq 1$.

Polynomial formulation

To a Barker sequence one may associate the Littlewood polynomial

$P(z)=\sum _{j=1}^{N}a_{j}z^{j-1}.$

Its autocorrelations occur as the coefficients in

$P(z)P(z^{-1})=N+\sum _{v=1}^{N-1}c_{v}(z^{v}+z^{-v}).$

This formulation connects Barker sequences with flat-polynomial problems, Mahler measure and norms of Littlewood polynomials. Gang Yu obtained improved estimates in 2023 for the $L^{1}$-norms of Barker polynomials and, more generally, Littlewood polynomials; the estimates do not resolve the conjecture.

Implementation in communication systems

A Barker code transmitted using binary phase-shift keying

A Barker sequence is a code or spreading sequence rather than a modulation scheme in its own right; its symbols are normally transmitted using binary phase modulation, with $+1$ and $-1$ represented by carrier phases differing by $\pi$ radians (180 degrees), that is, by binary phase-shift keying.

In wireless systems, spreading and synchronisation sequences are chosen for their autocorrelation properties, for low cross correlation with other sequences likely to interfere, and for their spectral characteristics. The legacy direct-sequence spread spectrum modes of IEEE 802.11b use the length-11 Barker sequence for the 1 and 2 Mbit/s data rates. With the sign convention used there, the aperiodic autocorrelation of that particular sequence takes the value +11 at zero shift and 0 or −1 at every other shift.

Applications

Established applications

Barker sequences are used as synchronisation patterns in digital communication and telemetry systems: a correlator or matched filter detects the known pattern in the received bit stream and thereby establishes group, frame or symbol timing.

They are also used as short binary phase codes for pulse compression in radar and sonar. Because the aperiodic autocorrelation of a Barker sequence of length N has a peak of N and off-peak values of magnitude at most 1, matched filtering gives fine range resolution while keeping range sidelobes low.

In Wi-Fi, the length-11 Barker sequence was standardised for the direct-sequence 1 and 2 Mbit/s modes of IEEE 802.11b; the 5.5 and 11 Mbit/s modes use complementary code keying instead.

Other studied applications

Barker-coded excitation has been investigated for ultrasound imaging and for ultrasonic nondestructive testing, where coding the transmitted pulse improves the signal-to-noise ratio available at low drive voltages.

Barker sequences have also appeared in individual designs and experimental systems. Reported examples include a digital modulator and demodulator for RFID tags using direct-sequence spread spectrum with Barker coding, codes formed by concatenating Barker sequences with nonlinear feedback shift register sequences, a proposed scheme combining Barker codes with binary complements with the stated aim of improving the security of spread-spectrum transmissions, and joint radar-and-communication waveforms studied for automotive and intelligent transport use. These are particular implementations or research proposals; they do not by themselves establish widespread deployment.

See also

• Littlewood polynomial
• Ryser's conjecture on circulant Hadamard matrices