Skip to content

A Linear encoding method

20121110 (2012 November 10 Saturday)

A sequence of ones and zeros arranged in such a way that any sequence of n bits is unique.

The sequence will consist of 2n bits. The sequence can be circular,
or linear with the first n-1 digits repeated at the end.

This scheme has the advantage that you need not worry about lining up with the start of the word.
You just read n bits. It is probably prone to errors but this can be reduced by reading extra bits.
Each extra bit will reduce the error rate by &frac12.

Example

[Examples are in regular expression form.]

Sequence for n=4

0000100110101111(000)?

Alternative endings

This pattern allows you to know if you are out of range.
(0*)0000100110101111(0000+)

This Pattern allows you to know which end you have fallen off.
(0*)0000100110101111(1*)

Sequence for n=5

00000100011001010011101011011111

The sequence is not new, like many things it was invented several times. see:
http://en.wikipedia.org/wiki/De_Bruijn_sequence

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: