Difference between revisions of "De Bruijn sequence"

From TheAlmightyGuru
Jump to: navigation, search
(Cryptography)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
A '''De Bruijn sequence''' is a series of characters which represents all possible character combinations of given length from a specified alphabet. For example, for an alphabet consisting of the characters A, B, and C, with a length of two, the total list of possible combinations are: AA, AB, AC, BA, BB, BC, CA, CB, and CC, which is 18 characters in length. However, the De Bruijn sequence would be: AABACBBCC, which includes all those those combinations, but is only nine characters in length. De Bruijn sequences are useful in compression, but also in encryption.
+
[[Image:De Bruijn Sequence - Example.svg|thumb|256x256px|De Bruijn sequence example.]]
 +
 
 +
A '''De Bruijn sequence''' is the sequence of characters which can represent all possible character combinations of a specified length from a given alphabet. This is used to compress a large set of possible combinations into the shortest possible amount of space. For example, to list all of the possible combinations of an alphabet consisting of the characters A, B, and C, with a combination length of two, you would need 18 characters: AA, AB, AC, BA, BB, BC, CA, CB, and CC. However, the De Bruijn sequence which includes all of those combinations would only be nine characters: AABACBBCC. You may notice that CA is not part of the sequence, but the De Bruijn sequence is expected to wrap from the end to the beginning, which includes CA.
 +
 
 +
==Applications==
 +
===Data Compression===
 +
Because a De Bruijn sequence can greatly reduce the space needed to list all possible combinations of a series of values, you can replace a complete list of possible combinations with its De Bruijn sequence, and then point to a place value to obtain the value.
 +
 
 +
===Computers===
 +
Especially useful in computers is the De Bruijn sequence for all the combinations of a byte. A byte can be described an alphabet of two characters (0 or 1) with a combination length of eight. To list all possible combinations of a byte requires 2,048 characters, however, the De Bruijn sequence is only 256 characters long:
 +
 
 +
<pre>
 +
00000000 10000001 10000010 10000011 10000100 10000101 10000110 10000111 10001000 10011000 10101000 10111000 11001000 11011000 11101000 11111001 00101001 00111001 01011001 01101001 01111001 10011010 10011011 10011101 10011110 10011111 10101010 11101011 01101011 11101101 11101110 11111111
 +
</pre>
 +
 
 +
===Cryptography===
 +
A De Bruijn sequence can greatly increase the speed of a [[brute force attack]] if the gateway processes keys based on the most recent data. For example, most early garage door openers merely compared the last eight bits they received with their internal key, and, if they matched, opened. Thus, you can send a non-stop De Bruijn sequence and be guaranteed entry.
 +
 
 +
For an example of this in action, see this [https://www.youtube.com/watch?v=CNodxp9Jy4A Veritasium video].
 +
 
 +
===Games===
 +
In addition to simply determining the De Bruijn sequence, several games have been made based on it. For example, there is a series of puzzles in the game [[Nelson Tethers: Puzzle Agent]] called "A Quorum of Crows" where several photographs of birds on a wire need to be line up to get as close to a De Bruijn sequence as possible.
  
 
==Links==
 
==Links==
* [https://www.youtube.com/watch?v=CNodxp9Jy4A youtube.com/watch?v=CNodxp9Jy4A] - Veritasium - Using De Bruijn sequences to open wireless gates and doors.
+
* [https://en.wikipedia.org/wiki/De_Bruijn_sequence en.wikipedia.org/wiki/De_Bruijn_sequence] - Wikipedia.
 +
* [http://mathworld.wolfram.com/deBruijnSequence.html mathworld.wolfram.com/deBruijnSequence.html] - Wolfram MathWorld.
  
  
Line 8: Line 30:
 
[[Category: Compression]]
 
[[Category: Compression]]
 
[[Category: Cryptography]]
 
[[Category: Cryptography]]
 +
[[Category: Game Theory]]

Latest revision as of 15:48, 30 November 2018

De Bruijn sequence example.

A De Bruijn sequence is the sequence of characters which can represent all possible character combinations of a specified length from a given alphabet. This is used to compress a large set of possible combinations into the shortest possible amount of space. For example, to list all of the possible combinations of an alphabet consisting of the characters A, B, and C, with a combination length of two, you would need 18 characters: AA, AB, AC, BA, BB, BC, CA, CB, and CC. However, the De Bruijn sequence which includes all of those combinations would only be nine characters: AABACBBCC. You may notice that CA is not part of the sequence, but the De Bruijn sequence is expected to wrap from the end to the beginning, which includes CA.

Applications

Data Compression

Because a De Bruijn sequence can greatly reduce the space needed to list all possible combinations of a series of values, you can replace a complete list of possible combinations with its De Bruijn sequence, and then point to a place value to obtain the value.

Computers

Especially useful in computers is the De Bruijn sequence for all the combinations of a byte. A byte can be described an alphabet of two characters (0 or 1) with a combination length of eight. To list all possible combinations of a byte requires 2,048 characters, however, the De Bruijn sequence is only 256 characters long:

00000000 10000001 10000010 10000011 10000100 10000101 10000110 10000111 10001000 10011000 10101000 10111000 11001000 11011000 11101000 11111001 00101001 00111001 01011001 01101001 01111001 10011010 10011011 10011101 10011110 10011111 10101010 11101011 01101011 11101101 11101110 11111111

Cryptography

A De Bruijn sequence can greatly increase the speed of a brute force attack if the gateway processes keys based on the most recent data. For example, most early garage door openers merely compared the last eight bits they received with their internal key, and, if they matched, opened. Thus, you can send a non-stop De Bruijn sequence and be guaranteed entry.

For an example of this in action, see this Veritasium video.

Games

In addition to simply determining the De Bruijn sequence, several games have been made based on it. For example, there is a series of puzzles in the game Nelson Tethers: Puzzle Agent called "A Quorum of Crows" where several photographs of birds on a wire need to be line up to get as close to a De Bruijn sequence as possible.

Links