Barker code

Last updated

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.

Contents

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 are called Barker sequences or Barker codes, after the inventor Ronald Hugh Barker. The process is described in "Group Synchronisation of Binary Digital Systems" published in 1953. [1] These sequences were initially developed for radar, telemetry, and digital speech encryption in the 1940s and 1950s.

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 1950s 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 1948 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 autocorrelation 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 Barker7code.svg
Graphical representation of a Barker-7 code
Autocorrelation function of a Barker-7 code Barker7corr.svg
Autocorrelation function of a Barker-7 code
3D Doppler Radar Spectrum showing a Barker Code of 13 3D Doppler Radar Spectrum showing a Barker Code of 13.jpg
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,

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

are as small as possible:

for all . [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

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
LengthCodesSidelobe 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 maximum length sequences (MLS). Arbitrarily long cyclic sequences can be constructed.

Barker modulation

Barker code used in BPSK modulation BarkerMod-BPSK.jpg
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]

Examples of applications

Applications of Barker codes are found in radar, [17] mobile phone, [18] telemetry, [19] ultrasound imaging and testing, [20] [21] GPS, [22] and Wi-Fi. [23]

Many of these technologies use DSSS. This technique incorporates Barker code to improve the received signal quality and improve security. [24]

These codes also used in radio frequency identification RFID. Some examples where Barker code is used are: pet and livestock tracking, bar code scanners, inventory management, vehicle, parcel, asset and equipment tracking, inventory control, cargo and supply chain logistics. [25] It is also used extensively for Intelligent Transport Systems (ITS) i.e. for vehicle guidance [26]

Acceptance probability

Barker's algorithm is an alternative to Metropolis–Hastings, which doesn't satisfy the detailed balance condition. Barker's algorithm does converge to the target distribution. Given the current state, x, and the proposed state, x', the acceptance probability is defined as:
The formula doesn't satisfy detailed balance, but makes sure that the balanced condition is met.

Related Research Articles

<span class="mw-page-title-main">Code-division multiple access</span> Channel access method used by various radio communication technologies

Code-division multiple access (CDMA) is a channel access method used by various radio communication technologies. CDMA is an example of multiple access, where several transmitters can send information simultaneously over a single communication channel. This allows several users to share a band of frequencies. To permit this without undue interference between the users, CDMA employs spread spectrum technology and a special coding scheme.

<span class="mw-page-title-main">Digital data</span> Discrete, discontinuous representation of information

Digital data, in information theory and information systems, is information represented as a string of discrete symbols, each of which can take on one of only a finite number of values from some alphabet, such as letters or digits. An example is a text document, which consists of a string of alphanumeric characters. The most common form of digital data in modern information systems is binary data, which is represented by a string of binary digits (bits) each of which can have one of two values, either 0 or 1.

In electronics and telecommunications, modulation is the process of varying one or more properties of a periodic waveform, called the carrier signal, with a separate signal called the modulation signal that typically contains information to be transmitted. For example, the modulation signal might be an audio signal representing sound from a microphone, a video signal representing moving images from a video camera, or a digital signal representing a sequence of binary digits, a bitstream from a computer.

<span class="mw-page-title-main">Orthogonal frequency-division multiplexing</span> Method of encoding digital data on multiple carrier frequencies

In telecommunications, orthogonal frequency-division multiplexing (OFDM) is a type of digital transmission used in digital modulation for encoding digital (binary) data on multiple carrier frequencies. OFDM has developed into a popular scheme for wideband digital communication, used in applications such as digital television and audio broadcasting, DSL internet access, wireless networks, power line networks, and 4G/5G mobile communications.

In telecommunication and electronics, baud is a common unit of measurement of symbol rate, which is one of the components that determine the speed of communication over a data channel.

In digital transmission, the number of bit errors is the number of received bits of a data stream over a communication channel that have been altered due to noise, interference, distortion or bit synchronization errors.

In cryptography, pseudorandom noise (PRN) is a signal similar to noise which satisfies one or more of the standard tests for statistical randomness. Although it seems to lack any definite pattern, pseudorandom noise consists of a deterministic sequence of pulses that will repeat itself after its period.

Data communication, including data transmission and data reception, is the transfer of data, transmitted and received over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibers, wireless communication using radio spectrum, storage media and computer buses. The data are represented as an electromagnetic signal, such as an electrical voltage, radiowave, microwave, or infrared signal.

The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit.

In telecommunications, node-to-node data transfer is the movement of data from one node of a network to the next. In the OSI model it is handled by the lowest two layers, the data link layer and the physical layer.

In pulsed radar and sonar signal processing, an ambiguity function is a two-dimensional function of propagation delay and Doppler frequency , . It represents the distortion of a returned pulse due to the receiver matched filter of the return from a moving target. The ambiguity function is defined by the properties of the pulse and of the filter, and not any particular target scenario.

Beamforming or spatial filtering is a signal processing technique used in sensor arrays for directional signal transmission or reception. This is achieved by combining elements in an antenna array in such a way that signals at particular angles experience constructive interference while others experience destructive interference. Beamforming can be used at both the transmitting and receiving ends in order to achieve spatial selectivity. The improvement compared with omnidirectional reception/transmission is known as the directivity of the array.

A maximum length sequence (MLS) is a type of pseudorandom binary sequence.

In a digitally modulated signal or a line code, symbol rate, modulation rate or baud rate is the number of symbol changes, waveform changes, or signaling events across the transmission medium per unit of time. The symbol rate is measured in baud (Bd) or symbols per second. In the case of a line code, the symbol rate is the pulse rate in pulses per second. Each symbol can represent or convey one or several bits of data. The symbol rate is related to the gross bit rate, expressed in bits per second.

Pulse compression is a signal processing technique commonly used by radar, sonar and echography to either increase the range resolution when pulse length is constrained or increase the signal to noise ratio when the peak power and the bandwidth of the transmitted signal are constrained. This is achieved by modulating the transmitted pulse and then correlating the received signal with the transmitted pulse.

In applied mathematics, complementary sequences (CS) are pairs of sequences with the useful property that their out-of-phase aperiodic autocorrelation coefficients sum to zero. Binary complementary sequences were first introduced by Marcel J. E. Golay in 1949. In 1961–1962 Golay gave several methods for constructing sequences of length 2N and gave examples of complementary sequences of lengths 10 and 26. In 1974 R. J. Turyn gave a method for constructing sequences of length mn from sequences of lengths m and n which allows the construction of sequences of any length of the form 2N10K26M.

In mathematics, a sign sequence, or ±1–sequence or bipolar sequence, is a sequence of numbers, each of which is either 1 or −1. One example is the sequence.

<span class="mw-page-title-main">Antenna array</span> Set of multiple antennas which work together

An antenna array is a set of multiple connected antennas which work together as a single antenna, to transmit or receive radio waves. The individual antennas are usually connected to a single receiver or transmitter by feedlines that feed the power to the elements in a specific phase relationship. The radio waves radiated by each individual antenna combine and superpose, adding together to enhance the power radiated in desired directions, and cancelling to reduce the power radiated in other directions. Similarly, when used for receiving, the separate radio frequency currents from the individual antennas combine in the receiver with the correct phase relationship to enhance signals received from the desired directions and cancel signals from undesired directions. More sophisticated array antennas may have multiple transmitter or receiver modules, each connected to a separate antenna element or group of elements.

The chirp pulse compression process transforms a long duration frequency-coded pulse into a narrow pulse of greatly increased amplitude. It is a technique used in radar and sonar systems because it is a method whereby a narrow pulse with high peak power can be derived from a long duration pulse with low peak power. Furthermore, the process offers good range resolution because the half-power beam width of the compressed pulse is consistent with the system bandwidth.

<span class="mw-page-title-main">Ronald Hugh Barker</span> British physicist (1915–2015)

Ronald Hugh Barker FIEE was an Irish physicist and the inventor of Barker code. Barker code is a method for synchronising digital communication to avoid corruption of the data received. The method has been studied and researched worldwide and is commonly used in most data transmissions today. Examples of applications include radar, mobile phone technology, telemetry, digital speech, ultrasound imaging and testing, GPS, Wi-Fi, radio frequency identification, barcodes, tracking, stock control and vehicle guidance.

References

  1. 1 2 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. pp. 400–402. Retrieved February 5, 2023.
  5. Irv D Siegel (1971). "Development of a set of optimum synchronisation codes for a unique decoder mechanization". Masters Theses. Missouri S & T Library and Learning Resources: 13. Retrieved February 5, 2023.
  6. Sloane, N. J. A. (ed.). "SequenceA091704". 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. Weisstein, Eric W. "Barker Code". MathWorld .
  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.
  17. Majid, Alolaibi (2021). "Low noise moving target detection in high resolution radar using binary code". EURASIP Journal on Advances in Signal Processing. 2021 (1): 8. Bibcode:2021EJASP2021....8A. doi: 10.1186/s13634-020-00716-0 .
  18. "802.11b White Paper" (PDF). Vocal Technologies, Ltd. Retrieved December 30, 2022.
  19. Irv D Siegel. "Development of a set of optimum synchronization codes for a unique decoder mechanization, 1971". Missouri Science and Technology Library of Learning resources. Retrieved 18 June 2021.
  20. Zhao, Heng; l. Mo, Larry; Gao, Shangkai (2007). "Barker-coded ultrasound color flow imaging: Theoretical and practical design considerations". IEEE Transactions on Ultrasonics, Ferroelectrics and Frequency Control. 54 (2): 319–331. doi:10.1109/tuffc.2007.246. PMID   17328329. S2CID   19527352.
  21. Fan, Zeng; Rudlin, Ohn; Asfis, Giorgos; Meng, Hongying (2019). "Convolution of Barker and Golay Codes for Low Voltage Ultrasonic Testing". Technologies. 7 (4): 72. doi: 10.3390/technologies7040072 .
  22. Matsuyuki, Shota; Tsuneda, Akio (2018). "A Study on Aperiodic Auto-Correlation Properties of Concatenated Codes by Barker Sequences and NFSR Sequences". 2018 International Conference on Information and Communication Technology Convergence (ICTC). pp. 664–666. doi:10.1109/ICTC.2018.8539367. ISBN   978-1-5386-5041-7. S2CID   53713772.
  23. Mikulka, Jan; Hanus, Stanislav (2007). 2007 17th International Conference Radioelektronikachapter = CCK and Barker Coding Implementation in IEEE 802.11b Standard. pp. 1–4. doi:10.1109/RADIOELEK.2007.371484. S2CID   34865532.
  24. Latif, Shahid; Kamran, Muhammad; Masoud, Fahad; Sohaib, Muhammad (2012). "Improving DSSS transmission security using Barker code along binary compliments (CBC12-DSSS)". 2012 International Conference on Emerging Technologies. pp. 1–5. doi:10.1109/ICET.2012.6375426. ISBN   978-1-4673-4451-7. S2CID   2901603.
  25. Amin, Syedul; Reaz, Mamun Bin Ibne; Jalil, Jubayer; Raham, LF (2012). "Digital Modulator and Demodulator IC for RFID Tag Employing DSSS and Barker Code". Journal of Applied Research and Technology. 10 (6): 819–825. doi: 10.22201/ICAT.16656423.2012.10.6.341 . S2CID   16796254.
  26. Bekar, Muge; Baker, Chris; Hoare, Edward; Gashinova, Marina (2021). "Joint MIMO Radar and Communication System Using a PSK-LFM Waveform With TDM and CDM Approaches". IEEE Sensors Journal. 21 (5): 6115–6124. Bibcode:2021ISenJ..21.6115B. doi: 10.1109/JSEN.2020.3043085 . S2CID   231852192.