imported>Urhixidur: duplicate ref

2025-05-29T17:05:26Z

duplicate ref

New page

{{Short description|Sequence of digital values used for synchronisation}}
{{Redirect|Barker sequence|the sequence of [[generalized Wieferich prime]]s|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.

==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 (radio)|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 [[synchronization|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.<ref name="Barker comms theory">{{cite book |last=Barker |first=Ronald Hugh |author-link=Ronald Hugh Barker |chapter=Group Synchronizing of Binary Digital Systems |title=Communication Theory |place=London |publisher=Butterworth |pages=273–287 |year=1953 }}</ref> 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” <ref>{{cite web |first=David |last=Tsa |url=https://www.quantamagazine.org/how-claude-shannons-information-theory-invented-the-future-20201222/ |title=How Claude Shannon invented the Future |date=2020 |volume=mathematics |access-date=February 5, 2023 }}</ref> or see original.<ref>{{cite web|first=Claude |last=Shannon |url=https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf |title=A Mathematical Theory of Communication |date=1922 |publisher=The Bell System Technical Journal |volume=27 |pages=380–381 |access-date=February 5, 2023 }}</ref>
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.<ref>{{cite web|first=Thomas |last=Roddam |url=https://worldradiohistory.com/UK/Wireless-World/40s/Wireless-World-1948-11.pdf |title=Frequency Shift Keying |publisher=Wireless World |date=November 1948 |pages=400–402 |access-date=February 5, 2023 }}</ref>

In 1953 R. H. 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”<ref name="Siegel1971">{{cite journal |first=Irv D. |last=Siegel |title=Development of a Set of Optimum Synchronisation Codes for a Unique Decoder Mechanization |url=https://scholarsmine.mst.edu/masters_theses/5479 |date=1971 |page=13 |journal=Masters Theses |publisher=Missouri S & T Library and Learning Resources |access-date=February 5, 2023 }}</ref>

==Definition==

[[File:Barker7code.svg|thumb|Graphical representation of a Barker-7 code]]
[[File:Barker7corr.svg|thumb|Autocorrelation function of a Barker-7 code]]
[[File:3D Doppler Radar Spectrum showing a Barker Code of 13.jpg|thumb|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,

:<math>a_j \text{ for } j = 1, 2, \dots, N</math>

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

:<math>c_v = \sum_{j=1}^{N-v} a_j a_{j+v} </math>

are as small as possible:

:<math>|c_v| \le 1\,</math>

for all <math>1 \le v < N</math>.<ref name="Barker comms theory" />

Only nine Barker sequences<ref>{{Cite OEIS |1=A091704 }}</ref> are known, all of length ''N'' at most 13.<ref name="BM">{{cite book |title=Number Theory and Polynomials |editor=James McKee |editor2=Chris Smyth |publisher=Cambridge University Press |isbn=978-0-521-71467-9 |series=LMS Lecture Notes |volume=352 |year=2008 |first1=Peter |last1=Borwein |author-link1=Peter Borwein |first2=Michael J. |last2=Mossinghoff |chapter=Barker sequences and flat polynomials |pages=71–88 }}</ref> [[Ronald Hugh Barker|Barker]]'s 1953 paper asked for sequences with the stronger condition
:<math>c_v \in \{-1, 0\}.</math>
Only four such sequences are known, shown in bold in the table below.<ref name="JEACE">Using different pulse shape in Barker code also improves certain autocorrelation properties.</ref>

== 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.<ref>{{MathWorld |urlname=BarkerCode |title=Barker Code}}</ref><ref>{{Cite web |first=Greg |last=Coxson |url=http://www.math.wpi.edu/MPI2008/TSC/TSC-MPI.pdf |title=Do the Barker codes End? |date=2008 |publisher= Worcester Polytechnic Institute |access-date=February 1, 2023 }}</ref> (It has been proven that there are no further odd-length codes,<ref>Turyn and Storer, "On binary sequences", Proceedings of the AMS, volume 12 (1961), pages 394–399</ref> nor even-length codes of {{nowrap|''N'' < 10<sup>22</sup>}}.<ref>Leung, K.; and Schmidt, B.; "The Field Descent Method", ''Design, Codes and [[Cryptography]]'', volume 36, pages 171–188</ref>)

{| class="wikitable"
|+ Known Barker codes
|-
! Length
! colspan="2" | Codes !! Sidelobe level ratio<ref>{{Cite web |url=http://www.radartutorial.eu/08.transmitters/Intrapulse%20Modulation.en.html |title=Pulse Compression – Radartutorial |publisher=Christian Wolff |access-date= February 1, 2023 }}</ref><ref>{{Cite web |first1=Greg |last1=Coxson |first2=Tahal |last2=Darwich |url=http://www.cacs.louisiana.edu/~library/TR/TR_pdf/TR_2006/TR_darwich_2006-4-1.pdf |title=Amplitude Shifting for Sidelobes Cancellation Pulse Compression |publisher=University of Louisiana at Lafayette |access-date=February 1, 2023 }}</ref>
|-
| 2 || '''+1 −1''' || +1 +1 || −6 dB
|-
| 3 || colspan="2" | '''+1 +1 −1''' || −9.5 dB
|-
| 4 || +1 +1 −1 +1 || +1 +1 +1 −1 || −12 dB
|-
| 5 || colspan="2" | +1 +1 +1 −1 +1 || −14 dB
|-
| 7 || colspan="2" | '''+1 +1 +1 −1 −1 +1 −1''' || −16.9 dB
|-
| 11 || colspan="2" | '''+1 +1 +1 −1 −1 −1 +1 −1 −1 +1 −1''' || −20.8 dB
|-
| 13 || colspan="2" | +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|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).<ref>Sklonik, Merrill I.; ''Introduction to Radar Systems'', 3rd edition, McGraw–Hill, 2001</ref> 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 [[phase shifting|change of phase]] in the [[carrier wave]] is 180 degrees.

Similar to the Barker codes are the [[complementary sequence]]s, 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 symbol|Legendre sequences]], [[Zadoff–Chu sequence]]s (used in 3rd- and 4th-generation cellular radio) and <math>2^n - 1</math> [[maximum length sequence]]s (MLS). Arbitrarily long cyclic sequences can be constructed.

==Barker modulation==

[[Image:BarkerMod-BPSK.jpg|thumb|400px|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/s 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.<ref>{{Cite web |url=http://literature.cdn.keysight.com/litweb/pdf/5988-3762EN.pdf |title=RF Testing of WLAN Products |website=Keysight Technologies }}</ref>

== Examples of applications ==
Applications of Barker codes are found in [[radar]],<ref>{{Cite journal |last=Majid |first=Alolaibi |year=2021 |title=Low noise moving target detection in high resolution radar using binary code |journal=EURASIP Journal on Advances in Signal Processing |volume=2021 |issue=1 |page=8 |bibcode=2021EJASP2021....8A |doi=10.1186/s13634-020-00716-0 |doi-access=free }}</ref> [[mobile phone]],<ref>{{cite web |title=802.11b White Paper |url=https://vocal.com/wp-content/uploads/2012/05/802.11b_wp1.pdf |access-date=December 30, 2022 |publisher=Vocal Technologies, Ltd. }}</ref> [[telemetry]],<ref name="Siegel1971" /> [[ultrasound]] imaging and testing,<ref>{{Cite journal |last1=Zhao |first1=Heng |last2=L. Mo |first2=Larry |last3=Gao |first3=Shangkai |year=2007 |title=Barker-coded ultrasound color flow imaging: Theoretical and practical design considerations |url=https://ieeexplore.ieee.org/document/4107691 |journal=IEEE Transactions on Ultrasonics, Ferroelectrics and Frequency Control |volume=54 |issue=2 |pages=319–331 |doi=10.1109/tuffc.2007.246 |pmid=17328329 |s2cid=19527352|url-access=subscription }}</ref><ref>{{Cite journal |last1=Fan |first1=Zeng |last2=Rudlin |first2=Ohn |last3=Asfis |first3=Giorgos |last4=Meng |first4=Hongying |year=2019 |title=Convolution of Barker and Golay Codes for Low Voltage Ultrasonic Testing |journal=Technologies |volume=7 |issue=4 |page=72 |doi=10.3390/technologies7040072 |doi-access=free}}</ref> [[GPS]],<ref>{{Cite book |last1=Matsuyuki |first1=Shota |title=2018 International Conference on Information and Communication Technology Convergence (ICTC) |last2=Tsuneda |first2=Akio |year=2018 |isbn=978-1-5386-5041-7 |pages=664–666 |chapter=A Study on Aperiodic Auto-Correlation Properties of Concatenated Codes by Barker Sequences and NFSR Sequences |doi=10.1109/ICTC.2018.8539367 |s2cid=53713772}}</ref> and [[Wi-Fi]].<ref>{{Cite book |last1=Mikulka |first1=Jan |title=2007 17th International Conference Radioelektronikachapter = CCK and Barker Coding Implementation in IEEE 802.11b Standard |last2=Hanus |first2=Stanislav |year=2007 |pages=1–4 |doi=10.1109/RADIOELEK.2007.371484 |s2cid=34865532}}</ref>

Many of these technologies use [[DSSS]]. This technique incorporates Barker code to improve the received signal quality and improve security.<ref>{{Cite book |last1=Latif |first1=Shahid |title=2012 International Conference on Emerging Technologies |last2=Kamran |first2=Muhammad |last3=Masoud |first3=Fahad |last4=Sohaib |first4=Muhammad |year=2012 |isbn=978-1-4673-4451-7 |pages=1–5 |chapter=Improving DSSS transmission security using Barker code along binary compliments (CBC12-DSSS) |doi=10.1109/ICET.2012.6375426 |s2cid=2901603}}</ref>

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.<ref>{{cite journal |last1=Amin |first1=Syedul |last2=Reaz |first2=Mamun Bin Ibne |last3=Jalil |first3=Jubayer |last4=Raham |first4=LF |year=2012 |title=Digital Modulator and Demodulator IC for RFID Tag Employing DSSS and Barker Code |journal=Journal of Applied Research and Technology |volume=10 |issue=6 |pages=819–825 |doi=10.22201/ICAT.16656423.2012.10.6.341 |s2cid=16796254 |doi-access=free}}</ref> It is also used extensively for [[Intelligent Transport Systems]] (ITS) i.e. for vehicle guidance<ref>{{cite journal |last1=Bekar |first1=Muge |last2=Baker |first2=Chris |last3=Hoare |first3=Edward |last4=Gashinova |first4=Marina |year=2021 |title=Joint MIMO Radar and Communication System Using a PSK-LFM Waveform With TDM and CDM Approaches |journal=IEEE Sensors Journal |volume=21 |issue=5 |pages=6115–6124 |bibcode=2021ISenJ..21.6115B |doi=10.1109/JSEN.2020.3043085 |s2cid=231852192 |doi-access=free}}</ref>

== 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:
<math>
\alpha\left(x\rightarrow x^\prime\right)=\frac{P\left(x^\prime\right)}{P\left(x\right)+P\left(x^\prime\right)}
</math><br>
The formula doesn't satisfy detailed balance, but makes sure that the balanced condition is met.

==References==
<references/>

{{DEFAULTSORT:Barker code}}
[[Category:Wireless networking]]
[[Category:Line codes]]
[[Category:Binary sequences]]
[[Category:Coding theory]]
[[Category:Digital signal processing]]
[[Category:Radar]]

Barker code - Revision history

imported>Urhixidur: duplicate ref