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.

Neck"lace (?; 48), n.

1.

A string of beads, etc., or any continuous band or chain, worn around the neck as an ornament.

2. Naut.

A rope or chain fitted around the masthead to hold hanging blocks for jibs and stays.

 

© Webster 1913.

Log in or registerto write something here or to contact authors.