Information Technology Reference
In-Depth Information
assign a symbol to
f
(
t
). This is done by removing all the symbols from
A
m
,
which will violate DMDP when it reaches the
t
-th position. When this set of
GOOD symbols for the current position becomes empty, the algorithm will out-
put the sequence constructed so far (if it has a new longer length) and then
back-track. The algorithm will stop when the set of GOOD symbols for the first
position becomes empty.
Figure1showsasituationfor
m
= 10, in which the algorithm has filled up
6termsandseekstoassignasymbolto
f
(7). Symbols (or numbers) in squares
at the top are the sequence
f
(
i
)for
i
=1
,
2
, ...,
6, and those in circles at level
h
deep are the differences mod 10 of terms in the distance
h
, i.e.,
f
(
i
+
h
)
f
(
i
)
(mod 10). They are said to form a modular difference triangle (MDT) with no
symbol repeating in any row (except for the top row that corresponds to the
sequence itself). The algorithm will remove a symbol from
A
10
(to build a set
of GOOD symbols for
f
(7)) if it does not satisfy DMDP with respect to the
given MDT of depth 5. Observe for example in this case that the symbol 4 will
be removed since
f
(2)
−
f
(6) (mod 10) from the rows of level
1 deep. Similarly, because of the differences 9, 1, 7, and 2 at level 1 deep, the
symbols 7, 9, 5 and 10 will also be removed. Because of the differences 5
,
0
,
8
,
9
at level 2 deep and
f
(5) = 6, the symbols 1
,
6
,
4
,
5 will also be removed. We note
that the symbol 5 had already been removed.
−
f
(1) = 6 = 4
−
Fact 1 .
Observe that the difference 9 at level 2 does not produce any new
constraint because if
f
(7)
−
f
(5) = 9 =
f
(6)
−
f
(4) then
f
(7)
−
f
(6) =
f
(5)
f
(4). Thus, the update process will become simpler when it considers
only those differences in the un-shaded circles.
−
We have focused on all existing examples of maximum length except for those
given by the algebraic constructions mentioned in the previous section and their
reductions. The initial search was to answer the following two questions:
Q.1.
Determine the maximum length
n
max
such that an
m
n
max
modular
sonar array exists. What would be the maximum length
n
e
if we count only
those that are NOT equivalent to any examples constructed by the three al-
gebraic methods mentioned in the previous section and/or their reductions?
Q.2.
How many inequivalent sequences of length
n
e
exist for a given
m
,ex-
cluding those which are equivalent to the one given by the three algebraic
constructions and/or their reductions?
×
The result of the search is shown in Table 1, from which we were able to detect
the following behaviors of values
m
and
n
e
.
Observation 1.
m
n
e
is monotonically non-decreasing as
m
is increasing.
Observation 2.
The number of inequivalent sequences of length
n
e
(not equiva-
lent to ones from the algebraic constructions) is decreasing as
m
is increasing
for the range where the value
m
−
−
n
e
remains the same.
Next section will be devoted to describing the above behaviors and more.
