Barker code

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 sender and receiver.

Explanation

Binary digits have very little meaning unless the significance of the individual digits is known. The transmission of a pre-arranged synchronising pattern of digits can enable a signal to be regenerated by a receiver with a low probability of error. In simple terms it is equivalent to tying a label to one digit after which others may be related by counting. This is achieved by transmitting a special pattern of digits which is unambiguously recognised by the receiver. The longer the pattern the more accurately the data can be synchronised and errors due to distortion omitted. These patterns, called Barker Sequences are better known as Barker code after the inventor Ronald Hugh Barker. The process is “Group Synchronisation of Binary Digital Systems” first published in 1953.[1] Initially developed for radar, telemetry and digital speech encryption in 1940 / 50’s

Historical Background

During and after WWII digital technology became a key subject for research e.g. for radar, missile and gun fire control and encryption. In the 1950’s scientists were trying various methods around the world to reduce errors in transmissions using code and to synchronise the received data. The problem being transmission noise, time delay and accuracy of received data. In 1922 the mathematician Claude Shannon published an article '"A mathematical Theory of Communication"' which laid out the basic elements of communication. In it he discusses the problems of noise.

Shannon realised that “communication signals must be treated in isolation from the meaning of the messages that they transmit” and laid down the theoretical foundations for digital circuits. “The problem of communication was primarily viewed as a deterministic signal-reconstruction problem: how to transform a received signal, distorted by the physical medium, to reconstruct the original as accurately as possible” [2]or see original.[3] In 1948 electronics was advancing fast but the problem of receiving accurate data had not. This is demonstrated in an article on Frequency Shift Keying published by Wireless World.[4] In 1953 RH Barker published a paper demonstrating how this problem to synchronise the data in transmissions could be overcome. The process is described in “Group Synchronisation of Binary Digital Systems”. When used in data transmissions the receiver can read and if necessary correct the data to be error free by auto and cross correlation by achieving zero autocorrelation except at the incidence position using specific codes. The Barker sequence process at the time produced great interest, particularly in the United States as his method solved the problem, initiating a huge leap forward in telecommunications. The process has remained at the forefront of radar, data transmission and telemetry and is now a very well known industry standard, still being researched in many technology fields. “In a pioneering examination of group synchronization of binary digital systems, Barker reasoned it would be desirable to start with an autocorrelation function having very low sidelobes. The governing code pattern, he insisted, could be unambiguously recognized by the detector. To assure this premise, Barker contended the selected pattern should be sufficiently unlikely to occur by chance, in a random series of noise generated bits”[5]

Graphical representation of a Barker-7 code
Autocorrelation function of a Barker-7 code
3D Doppler Radar Spectrum showing a Barker Code of 13

Definition

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

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

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

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

are as small as possible:

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

for all ${\displaystyle 1\leq v.[1]

Only nine Barker sequences[6] are known, all of length N at most 13.[7] Barker's 1953 paper asked for sequences with the stronger condition

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

Only four such sequences are known, shown in bold in the table below.[8]

Known Barker codes

Here is a table of all known Barker codes, where negations and reversals of the codes have been omitted. A Barker code has a maximum autocorrelation sequence which has sidelobes no larger than 1. It is generally accepted that no other perfect binary phase codes exist.[9][10] (It has been proven that there are no further odd-length codes,[11] nor even-length codes of N < 1022.[12])

Known Barker codes
Length Codes Sidelobe level ratio[13][14]
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).[15] 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 ${\displaystyle 2^{n}-1}$ maximum length sequences (MLS). Arbitrarily long cyclic sequences can be constructed.

Barker modulation

Barker code used in BPSK modulation

In wireless communications, sequences are usually chosen for their spectral properties and for low cross correlation with other sequences likely to interfere. In the 802.11 standard, an 11-chip Barker sequence is used for the 1 and 2 Mbit/sec rates. The value of the autocorrelation function for the Barker sequence is 0 or −1 at all offsets except zero, where it is +11. This makes for a more uniform spectrum, and better performance in the receivers.[16]

References

1. ^ a b Barker, R. H. (1953). "Group Synchronizing of Binary Digital Systems". Communication Theory. London: Butterworth. pp. 273–287.
2. ^ David Tsa (2020). "How Claude Shannon invented the Future". Retrieved February 5, 2023.
3. ^ Claude Shannon (1922). "Mathematical Theory of Communication". The Bell System Technical Journal. pp. 380–381. Retrieved February 5, 2023.
4. ^ Thomas Roddam (November 1948). "Frequency Shift Keying" (PDF). Wireless World. p. 400-402. Retrieved February 5, 2023.
5. ^ Irv D Siegel (1971). "Development of a set of optimum synchronisation codes for a unique decoder mechanization". Scholars' Mine. Missouri S & T Library and Learning Resources. p. 13. Retrieved February 5, 2023.
6. ^ Sloane, N. J. A. (ed.). "Sequence A091704". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
7. ^ Borwein, Peter; Mossinghoff, Michael J (2008). "Barker sequences and flat polynomials". In James McKee; Chris Smyth (eds.). Number Theory and Polynomials. LMS Lecture Notes. Vol. 352. Cambridge University Press. pp. 71–88. ISBN 978-0-521-71467-9.
8. ^ Using different pulse shape in Barker code also improves certain Autocorrelation properties.
9. ^
10. ^ Greg Coxson (2008). "Do the Barker codes End?" (PDF). Worcester Polytechnic Institute. Retrieved February 1, 2023.
11. ^ Turyn and Storer, "On binary sequences", Proceedings of the AMS, volume 12 (1961), pages 394–399
12. ^ Leung, K., and Schmidt, B., "The Field descent method", Design, Codes and Cryptography, volume 36, pages 171–188
13. ^ "Pulse Compression – Radartutorial". Christian Wolff. Retrieved February 1, 2023.
14. ^ Greg Coxson; Tahal Darwich. "Amplitude Shifting for Sidelobes Cancellation Pulse Compression" (PDF). University of Loisianna at Lafayette. Retrieved February 1, 2023.
15. ^ Introduction to Radar Systems, 3rd Edition, Merrill I. Skolnik, McGraw–Hill, 2001
16. ^ "RF Testing of WLAN Products" (PDF). Keysight Technologies.