In mathematical terms, the set of necklaces is the set of strings with
equivalence under rotation.
A string is a (finite) list of symbols taken from some symbol set. A rotation of
a string is any other string that can be formed by splitting the original in two, and
appending the first substring to the second (so the two substrings are in the
opposite order, but the symbols within each remain in the same order). For example, given
the string "judge me by my size do you " (-- Yoda), it can be broken up into "judge me by
my size " and "do you ", so "do you judge me by my size " is the same necklace as "judge me
by my size do you ". However, "you do judge me by my size " is not the same
necklace, because there is no way to rotate the original string to get this string.
When a symbol set is considered to be a set of digits, a string can be interpreted as
a number, represented in a base equal to the size of the symbol set (e.g. when the
symbol set is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, a string can be interpreted as a decimal
integer). The equivalence of rotation then has a numerical interpretation, and as the
7-digit necklace "3579001" is equivalent to the 7-digit necklace "0013579", one can say that
in 7-digit necklace values, the number 3,579,001 is equivalent to 13,579). In this
manner, one can choose the lowest-valued rotation as a unique representation of a
string. This is useful in comparing necklaces to check if they are equivalent; e.g., given
two necklaces (say "8000246" and "246800"), find the lowest-valued rotation of each
("0002468" and "0002468") - if the lowest-valued rotations are equal as strings,
then the two original values are equal as necklaces. These 'lowest-valued'
rotations have the property that, given any substring, the value of that substring is
always greater than or equal to the value of the substring of the same length at the
beginning of the string. (Otherwise, one could split the string at the beginning of that
substring, swap the two parts and get a rotation which has a lower value.)
Necklaces are sometimes referred to as having a number of 'colour's, and a number of
'bead's. The number of colours is the same as the number of symbols in the symbol set.
The number of beads is the length of the string. The number of different necklaces with
n beads and k colours is given (using Eindhoven notation) by the
expression:
(1 / n) * (+ d : d divides n : totient(d) *
k(n / d))
A binary necklace is a necklace of two colours, i.e. a necklace in which the symbol set
only has two elements (e.g. binary digits). Binary necklaces are commonly used in
RFID (Radio Frequency IDentification). An ID tag is programmed
with a certain binary string, and it transmits that string over and over again
continuously. Thus, if a tag is programmed with the string '10001011', it transmits:
'…100010111000101110001011…'. A reader would have no way of identifying
where the tag 'starts', so all the reader can do is detect a binary necklace. In
this case, the reader would detect the necklace '00010111' (the lowest-valued rotation of
the string in the tag).
In order that ID codes in RFID be unique (a fundamental requirement of
any ID system), no two tags can be allowed to transmit the same
necklace (a stronger requirement than, no two tags can be allowed to transmit the same
string). This is usually accomplished by deciding on some synchronisation pattern, and
then ensuring that the same pattern appears nowhere else in the transmission. For
example, one might choose to have a sync pattern of '000001', and to avoid having that
pattern appear anywhere else in the transmission, a '1' could be stuffed after every 4
data bits. This way, the reader can rotate the necklace it receives until the sync
pattern is at the beginning of the string, can check that all the stuffing bits, and can
extract the data bits. Thus, even though the transmission has no physical starting
point, a logical starting point can be determined and data can be communicated
reliably, in an unambiguous fixed order with unambiguous start and end points.
There are many more sophisticated ways of synchronising, for example if the data is
broken up into 'chunk's of 8 bits, and an odd parity bit is appended to each chunk,
then the maximum '0's run-length is 16 bits. A sync pattern of 17 '0' bits could be used.
Many variations are used, most of them involve limiting the maximum run-length of one binary
value (or either binary value, when using differentially-coherent encoding) in
the data section, and then using a longer run-length for the synchronisation.