Difference between revisions of "De Bruijn sequence"

From TheAlmightyGuru
Jump to: navigation, search
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.
+
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.
 +
 
 +
Especially useful in computers is the De Bruijn sequence for a byte. Since a bit is an alphabet of two characters (0 or 1), and a byte is eight bits long, to list all 256 possible bit combinations that could make up a byte would require 2,048 characters (256 bytes). However, the De Bruijn sequence is only 256 characters long (32 bytes):
 +
 
 +
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
  
 
==Links==
 
==Links==
 +
* [https://en.wikipedia.org/wiki/De_Bruijn_sequence en.wikipedia.org/wiki/De_Bruijn_sequence] - Wikipedia.
 
* [https://www.youtube.com/watch?v=CNodxp9Jy4A youtube.com/watch?v=CNodxp9Jy4A] - Veritasium - Using De Bruijn sequences to open wireless gates and doors.
 
* [https://www.youtube.com/watch?v=CNodxp9Jy4A youtube.com/watch?v=CNodxp9Jy4A] - Veritasium - Using De Bruijn sequences to open wireless gates and doors.
  

Revision as of 10:32, 24 September 2018

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.

Especially useful in computers is the De Bruijn sequence for a byte. Since a bit is an alphabet of two characters (0 or 1), and a byte is eight bits long, to list all 256 possible bit combinations that could make up a byte would require 2,048 characters (256 bytes). However, the De Bruijn sequence is only 256 characters long (32 bytes):

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

Links