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

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

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

are as small as possible:

.

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

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

terms each equal to +1 or is odd; a Barker sequence attains this minimum at every nonzero shift.; 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.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 maximum length sequences (MLS). Arbitrarily long cyclic sequences can be constructed.

Barker sequence conjecture

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

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

must have

must satisfy further number-theoretic restrictions.

in 2002, in 2005. In 2014, Borwein and Mossinghoff showed that a Barker sequence longer than 13 would have either

..

Logan and Mossinghoff reported in 2017 that the smallest known, where

exclusion bound.

can satisfy

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

Relation to circulant Hadamard matrices

at every nonzero shift. The circulant matrix whose first row is the sequence therefore has mutually orthogonal rows and is a circulant Hadamard matrix.

Ryser's conjecture on circulant Hadamard matrices.

Polynomial formulation

To a Barker sequence one may associate the Littlewood polynomial

Its autocorrelations occur as the coefficients in

This formulation connects Barker sequences with flat-polynomial problems, Mahler measure and norms of Littlewood polynomials.-norms of Barker polynomials and, more generally, Littlewood polynomials; the estimates do not resolve the conjecture.

Implementation in communication systems

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 2Mbit/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 2Mbit/s modes of IEEE 802.11b; the 5.5 and 11Mbit/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

References