545
1 INTRODUCTION
Apairoffinitebinarysequencesof the same length
withthesumoftheirautocorrelationfunctionsequals
zerowas introduced by Golay withconnection with
study of infrared spectrometry in [1, 2, 3]. These
sequences are called a pair of complementary
sequences. Generalized complementary sequences
were considered
in [4]. These generalized
complementary sequences, named group‐
complementary sequences, may contain more than
twosequencesandfindtheirapplicationsinradar[5‐
19] and communication [20, 21]. The properties of
complementarysequencesandtheirrelationtoother
typesofcodeswereinvestigatedbyseveralauthorsin
[3, 4, 5,
6, 7, 22] and in survey article [22]. The
problemsforfurtherresolvingwerepointedin[23].A
pairoffinitebinarycomplementarysequencesdoesn’t
exist for any lengths of sequences. The necessary
condition for existence a pair of finite binary
complementary sequences had been specified in [3].
Latter,necessarycondition
wasextendedtothecases
of Group‐complementary sequences [4]. Next
extension to the complementary sequences with the
mismatched filtering were done in [8, 11, 12, 13],
where filter design problem was addressed for a
givensetofsequenceswiththeconsideredsignal‐to‐
noise losses constraints and complementary
properties.
Attheapproach[8,11]noothertypes of
interferenceweresupposed.Thenumberofequations
tobesolvedin[8]wasequaltoPN+2N–1,whereP–
numbersequencesinset,N–lengthofeachsequence.
In[12,13]anotherapproachforthefilterdesign
with
the considered signal‐to‐noise losses constraints and
complementarypropertieswassuggested,whereonly
NP equations are needed to be solved. Most
importantly,thisapproachnotonlyallowsforsignal‐
to‐noise ratio maximization, but also provides a
possibilityforinterferingreflectionsuppressionwith
given range‐velocity distribution. Also synthesis
of
sequence code‐filter pairs under additional
constraints with group complementary properties is
suggested in [12]. The necessary condition for a
sequence code‐filter set to be complementary, under
themismatchedfilterconditionswasobtainedin[12].
It should be noted that the classical Golay
complementary pair does not exist
for odd N, but
does exist for the mismatched case. In [13]
demonstratedtheefficiency ofsuggestedapproachto
thefiltersynthesisunder additional constraints with
group‐complementary properties on the base of
numerical calculations. It was shown that signal‐to‐
Synthesis of Binary Group-Complementary Sequences
V.M.Koshevyy
NationalUniversity“OdessaMaritimeAcademy”,Odessa,Ukraine
ABSTRACT:Algorithmofbinary{‐1,1}group‐complementarysequencesdirectconstructionforanysequences
lengthNissuggested. Ontheba se ofthesesequencesthesignalswithverywidefrequencybandwidthmaybe
constructed(uptotheultrawideband(UWB)signals).Synthesizedsequences
mayfoundtheirapplicationin
radarandcommunication.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 12
Number 3
September 2018
DOI:10.12716/1001.12.03.14
546
noiseratiolosesisdecreasewithincreasingmemory
of optimizing filters in set.Methods of sequences
and corresponding mismatched (in common case)
filters synthesis, which worked out in [12] and
provides complementary properties, relates to the
directmethodsof sequencesandfiltersconstruction.
Thosedirectconstructionmethodsgive thepossibility
to obtain sequences and corresponding filters with
complementary properties for any given length.
Besides in [12, 13] were suggested the recursive
constructionsofnewsetsofsequencesandfilterson
thebaseofknown setsofsequencesand filterswith
complementary properties without any additional
calculations. The counting of filters,
which provides
thetoleranceforDopplershiftstogetherwithproper
choosing the order of sequences and corresponding
filterdislocationwasconsideredin[14].Designofthe
binary complementary sequences under matched
filtering more frequently is provided by recursive
constructions.Itisknownonlyonemethodfordirect
constructioninconditionof
matchsequencesfiltering,
suggestedbyGolay[3].Butitwasworkedoutforthe
sequences with lengths N=
Thou essentially
restricted the possibility of practical using of this
approach.Itnotonlycouldn’tbeuseforoddN,but
alsoformostofevenNeither.Forexampleitcouldn’t
beusedforN=6;10;12;14;18;20;22;24;26andsoon.
In paper
[20] was given a particularly compact
description of this construction by using Algebraic
NormalForms.
In this paper we present the direct construction
method for binary complementary sequences under
matched filtering for any sequences lengths N.
ChoosingNbigenoughonecangetsignalswithbig
producttimelengthon
frequencybandwidth,socan
getUWBsignalswithcomplementaryproperties.
2 DIRECTCONSTRACTION
SetofPsequences(lengthN)
pNpp
t)N(
p
s,...,s,sS
110
where
t
S meanstransposedvector S, ordernumber
p=1
P, with elements
11
,s
np
, (n=0 N‐1), which
for providing group‐complementary properties may
bederivedbythenextway:
np
zj
np
es
(1)
2
1
1
1
1
221
mod
n
n
m
m
mpnp
/zpz
(2)
02
1
1
1
n
m
m
mp
z
,forn=0,n=1;p=1 P,P=
1
2
N
In fact
1
1
1
2
N
m
m
mp
z
p‐1, which is the 2‐adic
decomposition ofp‐1.Thus a code of sequence in
set i s determined only by its lengthN and order
numberpinset.Forexample,directconstructionof
the group‐complementary binary sequences set with
lengthN=3willbeconsidered.Numberofsequences
isequalP=
1
2
N
=4From(2),(1)weget:
01
z
=0;
11
z
=0;
21
z
=0;
01
s
=1;
11
s
=1;
21
s
=1;
02
z
=0;
12
z
=1;
22
z
=0;
02
s
=1;
12
s
=‐1;
22
s
=1;
03
z
=0;
13
z
=0;
23
z
=1;
03
s
=1;
13
s
=1;
23
s
=‐1;
04
z
=0;
14
z
=1;
24
z
=1;
04
s
=1;
14
s
=‐1;
24
s
=‐1;
Thus the matrix of group‐complementary
sequencesset:
()
1
()
()
.
Nt
N
P
Nt
P
S
S
S
(3)
forconsideredexampleN=3;P=4havetheform:
111
111
111
111
3
4
)(
S (4)
Theaperiodicauto‐correlationfunctionof
t)N(
p
S
1
0
kN
n
p)kn(np
aS
k
ssR
)N(
p
,0
k
N‐1:
(N)
p
)N(
p
S
k
S
k
RR
(5)
For
)(
S
3
4
wehave:
32
13
4
1
2
0
3
pk
S
k
)(
p
R
(6)
So, group- complementary property is
fulfilled. The proving group-complementary
property of sequences, derived on the base of
expressions (1), (2), for any
N can be gotten by
means of mathematical induction method.
Suggest that the property is true for
N. Consider
what follows from this fact for
N+1. Matrix for N
is
)(N
P
S
(P=
1
2
N
). For N+1 this matrix transforms
by the next:
)(
)(
)(
1
1
N
P
N
P
N
P
S
S
S
(7)
To matrix, getting by this way (7), with the size
N
N 2 should be added at the right new last column
withsize:
N
N
N
N
N
s
s
s
2
2
1
;21
(8)
Theresultingmatrix
)N(
N
S
1
2
consistsofmatrix(7)
with additional column (8) and has the size (N+1)
N
2 . Forrow p of the matrix
)N(
N
S
1
2
the sum of
aperiodicauto‐correlationfunctionvalues(5)overall
k(k=1
N)withconsidering(5),(7)and(8)wehave:
547
N
k
kNNp
N
k
S
kNp
S
N
k
pkNNp
N
k
S
k
N
k
S
k
p
N
p
N
p
N
p
N
p
ssRs
RssRR
1
)(
1
1
2
0
0
)(
1
00
)(
)()()1(
(9)
Thesumofauto‐correlationfunctionsforallrows
canbewrittenas:
NN
p
N
p
N
N
p
N
N
p
N
p
pp
N
k
kNNp
N
k
S
k
p
N
k
S
k
p
S
N
p
N
k
S
k
ssR
RRR
2
1
2
11
)(
1
1
2
1
1
1
2
1
0
2
10
)(
)()1()1(
(10)
where
2
00
)(
)()1(
Np
SS
sRR
N
p
N
p
. Considering (7),
expression(10)mayberewritteninthenextform:
N
N
N
p
N
N
p
N
N
p
N
p
p
Np
p
Np
N
k
kN
p
N
k
S
k
p
S
N
p
N
k
S
k
sss
RRR
2
12
2
11
)(
2
1
1
1
2
1
0
2
10
1
1
1
)()1()1(
2
(11)
According to (2) and (1) expression in square
brackets in (11) is equal zero
N
N
N
p
Np
p
Np
ss
2
12
2
1
1
1
=0. Next term in (11) is
also equal zero
1
2
1
1
1
2
N
p
N
k
)N(
p
S
k
R =0‐according our
supposingforN.Expression(11)canbewrittenas
N
p
)N(
p
S
N
p
N
k
)N(
p
S
k
RR
2
1
1
0
2
10
1
(12)
Compare with (6). Thus, group‐complementary
propertyofbinarysequencesforN+1isproved.
So, expressions (1), (2) for direct construction of
binary sequences with group‐complementary
propertyaretrueforanysequenceslengthN.
3 REDUCTIONOFTHENUMBERSEQUENCESIN
SET
Above‐cited direct method of
construction gives the
possibility to get binary sequences with group‐
complementary property for any length N. The
numberofsequencesinsetforthatisequal
.
It does mean that the set of
sequences with
lengthNaregroup‐complementary.Butinsideofthis
setexistalotanothersetswiththesamelengthsand
withlessnumbersequencesinthem.Forexampleif
N=4,soP=8.Sequenceswithordernumbersp=3and
p=5createcomplementarypair,thesameforp=2and
p=8.
Sequenceswithordernumbersp=1,p=4,p=6,p=7
create the group‐complementary set of four signals,
andwithordernumbers p=1,p=3,p=4,p=5,p=6,p=7–
of six signals. For N=5, the number of sequences is
P=16. Sequences with order numbers p=2, p=5, p=10,
p=13 create the group‐complementary
set of four
signals; the same we have for sequences with order
numbers p=3, p=8, p=11, p=16. Sequences with order
numbers p=1, p=4, p=6, p=7, p=9, p=12, p=14, p=15
creategroup‐complementarysetofeightsignals.And
soon.ForN=7wehaveP=64andwilldiscussonlya
part
ofsequenceswithreductionnumbersignalsina
set. Sequences with order numbers p=5, p=27, p=50,
p=59;p=17,p=23,p=45,p=47;p=5,p=12,p=50,p=53;
p=2, p=14, p=47, p=58; create group‐complementary
sets with four signals in each. Sequences with order
numbersp=8, p=9,p=19,p=30,p=34,p=47,p=53,p=60;
p=1, p=12, p=23, p=30, p=40, p=45, p=50, p=59; create
group complementary sets which contain eight
signalsineach.Usinggivenlengthandcorresponding
ordernumbersonecangetthegroup‐complementary
sequencesonthebaseofexpressions(2)and(1).For
example, in the case of sequences length N=7 and
ordernumberssequencesinsetp=17,p=23,p=45,p=47;
whichmentionedabove,onthebase(2),(1)canbegot
np
z ,
np
s :
17
0, 0, 0,0, 0,1, 0
n
z
;
17
1, 1, 1,1,1, 1, 1
n
s
;n=0 6;p=17;
23
0, 0,1,1, 0,1, 0
n
z
;
23
1, 1, 1, 1, 1, 1, 1
n
s
;n=0 6;p=23;
45
0, 0,0,1,1, 0,1
n
z
;
45
1,1, 1, 1, 1,1, 1
n
s
;n=0 6;p=45;
47
0, 0,1,1,1, 0,1
n
z
;
47
1, 1, 1, 1, 1, 1. 1
n
s
;n=0 6;p=47.
For N=10 we have P=512. Sequences with order
numbers p=201, p=390; p=236, p=320; create
complementary pairs. From (2), (1) can be got for
thesecases:
201
0, 0, 0, 0,1, 0, 0,1,1, 0
n
z
;
201
1,1, 1,1, 1,1, 1, 1, 1, 1
n
s
;n=0
9;p=201;
390
0,1, 0,1, 0, 0, 0, 0,1, 0
n
z
;
390
1, 1, 1, 1, 1, 1,1, 1, 1, 1
n
s
;n=0
9;p=390;
236
0, 1,1, 0, 1, 0,1, 1,1, 0
n
z
;
236
1, 1, 1, 1, 1, 1, 1, 1, 1,1
n
s
;n=0
9;
p=236;
320
1, 1, 1, 1, 1, 1, 1, 1,1 1
n
z
;
320
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
n
s
;
n=0
9;p=320.
Obtained complementary pairs coincides with
Golay complementary pairs for N=10 [3]. Sequences
withordernumbersp=32,p=107,p=133,p=218,p=232,
p=280, p=298, p=373, p=387, p=496; create the group‐
complementary set of ten signals with length N=10.
ForN=11sequenceswithordernumbersp=245,p=421,
p=581,p=789; create the group‐
complementary set of
four signals and with order numbers p=1, p=184,
p=234,p=286,p=367,p=467,p=571,p=584,p=733,p=882,
p=908,p=933;create the group‐complementarysetof
twelve signals. And so on. So, these examples show
thatforanylengthN inside general set withP=
1
2
N
exist a lot of sets with less number signals in it. As
example, N=18 contain the set of four group‐
complementarysequences:
[1‐11‐11111‐1‐111‐11111‐1]
[1‐11‐11111‐1‐1‐1‐11‐1‐1‐1‐11]
[1111‐111‐1‐1111‐11‐1‐1‐11]
[1111‐111‐
1‐11‐1‐11‐1111‐1],
Many others sets of sequences with group‐
complementary properties and different number
sequencesineachgroupexistinN=18generalset(the
numbersofsequencesineachgrouparealwayseven
numbers). For N=24 general set of sequences also
contain a lot of sets with group‐complementary
property with different number sequences. We can
demonstrateoneofthosesetswithfoursequencesin
it:
[11‐11111‐111‐111‐1‐1‐111‐11111‐1]
[11‐11111‐111‐111‐1‐1‐1‐1‐11‐1‐1‐1‐11]
548
[11‐11111‐1‐1‐11‐1111‐111‐11‐1‐1‐11]
[11‐11111‐1‐1‐11‐1111‐1‐1‐11‐1111‐1].
For N=26 can be demonstrated a few set with
group‐complementary property which been
containedingeneralset:
Thesetwithtwosequencesinit
[111‐1‐1111
‐11‐1‐11‐11‐11‐1‐111‐11111]
[111‐1‐1111‐11‐1‐1‐1 ‐1‐11‐111‐1‐11‐1‐1‐1 ‐1].
This pair of sequences is coincide with pair that
was obtained in [25] using a ‘by hand’ technique. It
was shown thatcomplementary sequences of length
26haveonlyonebasic‘kernel’.Thenextsetcontains
foursequencesinit:
[1‐1‐11‐11111111‐11111‐111‐11‐1‐1‐11]
[1‐1‐11‐111111‐1‐11‐1‐1‐1‐11‐1‐11‐1111‐1]
[11‐1‐1111‐11‐111‐11111‐1‐1 ‐11‐1111‐1]
[11‐1
‐1111‐11‐1‐1‐11‐1‐1‐1‐1111‐11‐1‐1‐11].
4 CONCLUSION
In the paper the direct method of group‐
complementarybinarysequencesconstructionforany
length N is suggested. It was shown that inside of
generalgroup‐complementarysetofsequencesexista
lot of group‐
complementary sets with less number
sequences in it. That gives wide possibility for
reductionnumberofsequencesineachset.
REFERENCES
[1]M.J.E. Golay. Multislit spectroscopy. J. Opt. Soc. Amer.,
vol.39,pp.437‐444,1949.
[2]M.J.E. Golay. Static multislit spectrometry and its
applicationtothepanoramicdisplayofinfraredspectra.
.J.Opt.Soc.Amer.,vol.41,pp.468‐472,1951.
[3]M.J.E. Golay. Complementary series. IRE Trans. Inform.
Theory,
vol.T‐7,pp.82‐87,1961.
[4]C.C.Tseng,C.L. Liu.Complementarysetsofsequences.
IEEETrans.Inform. Theory,vol.IT‐18,pp.644‐652,Sept.
1972.
[5]G.Welti.Quaternarycodesforpulsedradar.IRETrans.
Inform.Theory,vol.IT‐6,pp.400‐408,June1960
[6]R.J. Turyn.
Ambiguity functions of complementary
sequences.IEEETrans. Inform.Theory,vol.IT‐9,pp.46‐
47,Jan.1963.
[7]R. Sivaswamy. Digital and analog sub‐complementary
sequencesforpulsecompression.IEEETrans.onAerosp.
andElectron.Syst.,vol.AES‐14,pp.343‐350, Mar.1978.
[8]G. Weathers, E. M. Holiday. Group
‐complementary
array coding for radar clutter rejection. IEEE Trans. on
Aerosp.andElectron.Syst.,vol.AES‐19,pp.369‐379,May
1983.
[9]N. Levanon, E. Mozeson. Radar signals. New York:
Wiley,2004.
[10]T.R. Quereshi, M.D. Zolowski, R. Calderbank. Target
detection in MIMO radar in the presence of Doppler
using complementary sequences. Proc. ICASSP‐2010,
pp.2766‐2769.
[11]J. Bi, H. Rohling, Complementary binary code design
basedonmismatchedfilter..IEEETrans.onAerosp.and
Electron.Syst.,vol.AES‐48,Jan.2012.
[12]V.M. Koshevyy. Synthesis of waveform‐filter pairs
underadditionalconstraintswithgroupcomplementary
properties. IEEE Radar
Conference 2015, Arlington, VA
(USA),pp.0616‐0621,May2015.
[13]V.M. Koshevyy. Efficiency of filter synthesis under
additional constraints with group‐complementary
properties. IEEE 2016 International Conference
“Radioelectronics & InfoCommunications” (UkrMico),
Kiev,Ukraine,pp.978‐982,September11‐16,2016.
[14]V. Koshevyy, V. Popova. Complementary coded
waveforms sets
inmarineradar application. IEEE First
UkraineConferenceonElectricalandComputerEngineering
(UKRCON),May29‐June2,2017,Kyiv,pp.215‐222.
[15]V. Koshevyy, V. Popova. Sets of Waveform and
MismatchedFilterPairsforClutterSupressioninMarine
Radar Application. TransNav the International Journal
onMarineNavigationand
SafetyofSeaTransportation,
vol.11,N3,pp.505‐510,Sept.2017.
[16]V.M. Koshevyy, O.L. Pashenko. Improved compound
multiphase waveforms with additional amplitude
modulation (periodic mode) for marine radars. The
second International Conference on Information and
Telecommunication Technologies and Radio Electronics
(UkrMiCo’2017), 11‐15 September 2017, Odessa, Ukraine,
pp.
1‐6.
[17]A.Pezeshki,A.R.Calderbank,W.Moran,S.D.Howard.
Doppler resilient Golay complementaru waveforms.
IEEETras.Inform.Theory,vol.54,no.9,pp.4254‐4266,
Sep.2008.
[18]N. Levanon, I. Cohen. Complementary Pair Radar
Waveforms – Evaluating and Mitigating Some
Drowbacks.IEEE A&ESystemsMagazin,no.10,pp.40‐
50,March2017.
[19]A.Jayakumar,A.Durafe.FPGABasedUltra‐Wideband
Psevdo‐Noise Radar. Proceedings of IEEE ICSCON
2011,pp.46‐49.2011.
[20]J.A. Davis, J. Jetwab. Peak‐to‐mean power control in
OFDM, Golay complementary sequences and Reed‐
Mullercodes.IEEETrans.Inform.Theory,vol.IT‐45,no.
7,pp.2397‐2417,Nov.1999.
[21]S.Emami.UWBCommunicationSystems:Conventional
and60GHz.Principles,DesignandStandards.Springer,
2013
[22]M.G. Parker, K.G. Paterson, Ch. Tellambura. Golay
Complementary Sequences. In Wiley Encyclopedia of
Telecommunications(J.G.Proakis,ed.),Wiley,2004.
[23]J.Jetwab, M.G. Parker. Golay complementary array
pairs.Designs,
CodesandCryptography.pp. 1‐10, May
2007.
[24]P.B.Borwein,R.A.Ferguson.Acompletedescriptionof
Golay pairs for lenghts up to 100. Mathmetics of
Computation,vol.73,no.246,pp.967‐985,Julay2003.
[25]S.Jauregui,Jr.Complementaryseriesoflength26,IRE
Tras.Inform.Theory.Vol.IT‐7,p.323,1962
