Unforgeable Marker Sequences

D.J. Greaves
University of Cambridge Computer Laboratory
New Museums Site, Pembroke Street
Cambridge CB2 3QG, United Kingdom.

S.J. Montgomery-Smith¹
Department of Mathematics
University of Missouri
Columbia, MO 65211, U.S.A.

A binary number of $n$ bits consists of an ordered sequence of $n$ digits taken from the set $\{0, 1 \}$. A sequence is said to be an unforgeable marker if all subsequences of consecutive digits starting at the left-hand end are dissimilar from the sequence of the same length which ends at the right-hand end. Unforgeable marker sequences are so called because, when misaligned in a shift-register or other view port of the correct length, there is no possibility of adjacent random digits impersonating the true sequence. Such sequences are used for frame alignment purposes in serial data communications systems [1]. In many communications systems, the unforgeable marker is also a `comma sequence' in that it is guaranteed not to occur in any aligned or misaligned view of the data between the markers, but this relies on constraints on the data and does not impact on whether a sequence is an unforgeable marker or not

A sequence which is unforgeable with respect to right-hand misalignment is also unforgeable with respect to left-hand misalignment, and so there is a single set of unforgeable sequences of a given length.

It is useful to denote a particular sequence by a decimal number by weighting its digits with power of 2 in the conventional way. We can then concisely tabulate the unforgeable sequences for $n$ up to 6.

$n = 1$:	{0,1}
$n = 2$:	{1,2}
$n = 3$:	{1,3,4,6}
$n = 4$:	{1,3,7,8,12,14}
$n = 5$:	{1,3,5,7,11,15,16,20,24,26,28,30}
$n = 6$:	{1,3,5,7,11,13,15,19,23,31,32,40,44,48,50,52,56,58,60,62}

There is an even number of elements in each set because if a number is unforgeable, so is the sequence obtained by complementing every digit. This property is useful in NRZI (non-return to zero invert on ones) modulation since, in general, the absolute polarity of the sequence will not be known by the decoding hardware.