Difference between revisions of "De Bruijn sequence"

From TheAlmightyGuru
Jump to: navigation, search
(Cryptography)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
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.
 
 
 
[[Image:De Bruijn Sequence - Example.svg|thumb|256x256px|De Bruijn sequence example.]]
 
[[Image:De Bruijn Sequence - Example.svg|thumb|256x256px|De Bruijn sequence example.]]
  
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. See the illustration to the right. 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.
+
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.
  
Especially useful in computers is the De Bruijn sequence for all the combinations of a byte. A byte can be described as a length of eight with an alphabet of two characters (0 or 1). To list all possible combinations of , and a byte uses that alphabet to a length of eight, it takes 2,048 characters to list all 256 bytes, however, the De Bruijn sequence is only 256 characters long:
+
==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>
 
<pre>
Line 11: Line 14:
 
</pre>
 
</pre>
  
==Applications==
+
===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://en.wikipedia.org/wiki/De_Bruijn_sequence en.wikipedia.org/wiki/De_Bruijn_sequence] - Wikipedia.
 
* [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.
 
* [http://mathworld.wolfram.com/deBruijnSequence.html mathworld.wolfram.com/deBruijnSequence.html] - Wolfram MathWorld.
* [https://www.youtube.com/watch?v=CNodxp9Jy4A youtube.com/watch?v=CNodxp9Jy4A] - Veritasium - Using De Bruijn sequences to open wireless gates and doors.
 
  
  
Line 23: 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