de Bruijn-sekvens

De Bruijn-sekvensen för k = 2 och n = 2. Den cykliska sekvensen 0011 innehåller alla två tecken långa strängar som kan bildas ur alfabetet {0,1}, d.v.s 00, 01, 10 och 11.

Inom kombinatoriken är en k-när de Bruijn-sekvens B(k, n) av ordningen n en cyklisk sekvens till ett givet alfabet A med storleken k i vilken varje möjlig delsekvens av längden n uppträder en och endast en gång som på varandra följande tecken. Sekvensen är uppkallad efter den holländske matematikern Nicolaas Govert de Bruijn.

Varje B(k, n) har längden kn.

Det finns skilda de Bruijn-sekvenser B(k, n).

Enligt de Bruijn själv[1] bevisades existensen av de Bruijn-sekvenser för alla ordningar med ovanstående egenskaper först för alfabet med två bokstäver av Camille Flye Sainte-Marie 1894,[2] medan utvidgningen till större alfabeten är ett verk av Tanja van Aardenne-Ehrenfest och honom själv.

Historia

Det tidigaste kända exemplet på en de Bruijn-sekvens kommer från sanskritsprosodi. Sedan Pingalas arbeten har varje möjligt trestavigt mönster av långa och korta vokaler ett namn i form av en konsonant: som "y" för kort-lång-lång och "r" för lång-kort-lång.[3][4] För att komma ihåg dessa namn, används minnesramsan yamātārājabhānasalagām[5], i vilken varje trestavigt mönster inleds av sitt "konsonantnamn": yamātā har alltså ett kort-lång-lång-mönster, rājabhā lång-kort-långt, och så vidare.[6] Denna minnesramsa, som är ekvivalent med en de Bruijn-sekvens av binära tripplar (0111010001 vilket motsvarar 11101000, med tillägg av första och sista tecknet i andra änden 0+11101000+1 för att kompensera för att ramsan är linjär och ej cyklisk), är av okänd ålder men är åtminstone lika gammal som C. P. Browns bok från 1869 om versmått på sanskrit som nämner den.[6][7][8][9]

I ett nummer av den franska pusseltidskriften L'Intermédiaire des Mathématiciens ställde A. de Rivière 1894 frågan om det fanns ett sätt att arrangera alla binärsekvenser av längden n i en cirkulär sträng med längden . Problemet löstes, tillsammans med räkningen av antalet lösningar , av C. Flye Sainte-Marie samma år. Detta glömdes dock mer eller mindre bort och Martin (1934) bevisade existensen av sådana cykler för generella storlekar av alfabet andra än två. Slutligen, när K. Posthumus ställde antagandet att antalet binära sekvenser var , bevisade de Bruijn antagandets riktighet 1946, genom vilket problemet blev välkänt.[1]

Karl Popper beskriver oberoende dessa binärsekvenser i avsnitt 55 av sin Logik der Forschung (1934) och kallar dem n-Nachwirkungsfreie Alternativen och ger även formeln för deras antal.[10]

De Bruijn skriver att "motsvarande räkningsproblem för ett alfabet med σ bokstäver verkar först ha ställts och lösts 1951" och avser då van Aardenne-Ehrenfest, de Bruijn (1951).[1]

Exempel

  • För A = {0, 1} finns det två distinkta B(2, 3): 00010111 och 11101000. Den ena är en negation eller spegling av den andra.
  • Två av de 2048 möjliga B(2, 5) i samma alfabet är 00000100011001010011101011011111 och 00000101001000111110111001101011.

Konstruktion

de Bruijn-sekvenser kan konstrueras genom att ta en Hamiltonväg på en n-dimensionell de Bruijn-graf över k tecken (eller, likvärdigt, en Eulercykel på en (n − 1)-dimensionell de Bruijn-graf).[11]

En alternativ konstruktion kan åstadkommas genom att konkatenera alla Lyndonord som har en längd som delar n i lexikografisk ordning.[12] Se artikeln om Lyndonord för en närmare beskrivning.

de Bruijn-sekvenser kan också skapas genom att använda skiftregister[13] eller via ändliga kroppar.[14]

Exempel

En de Bruijn-graf. Varje fyrsiffrig sekvens förekommer en och endast en gång om man färdas längs varje kant (båge) en och endast en gång och återvänder till startpunkten (en Eulercykel). Varje tresiffrig sekvens förekommer en och endast en gång om man passerar varje hörn (nod) en och endast en gång (en Hamiltonväg). Notera att det är en riktad graf, där varje hörn har en kant 0 och en kant 1 som leder från det och till det hörn som betecknas med den tresiffriga sekvens som blir resultatet om man lägger till 0 eller 1 i slutet och stryker första siffran.

Mål: Att konstruera en B(2, 4) de Bruijn-sekvens med längden 24 = 16 genom en Eulercykel på den (n − 1 = 4 − 1 = 3) tredimensionella de Bruin-graf som avbildas i figuren till höger. Notera att det leder två riktade kanter från varje hörn (och även två till varje hörn).

Varje kant (båge) i denna tredimensionella de Bruijn-graf motsvarar en sekvens på fyra siffror: de tre siffror som betecknar hörnet (noden) som kanten lämnar följda av den siffra som betecknar kanten. Om man från hörnet 000 färdas längs kanten betecknad 1 kommer man till hörnet 001 och får delsekvensen 000+1=0001 i de Bruijn-sekvensen (notera att hörnet 001, nästa utgångspunkt avslutar 0001). Att färdas längs alla sexton kanterna en och endast en gång innebär att man använder sig av varje av de sexton fyrsiffriga sekvenserna exakt en gång vardera, vilket genererar en de Bruijn-sekvens.

Om vi till exempel följer en Eulerkrets genom hörnen i denna ordning...

000, 000, 001, 011, 111, 111, 110, 101, 011,
110, 100, 001, 010, 101, 010, 100, 000.

..blir detta våra överlappande, och unika, fyrsiffriga sekvenser:

0 0 0 0
_ 0 0 0 1
_ _ 0 0 1 1
_ _ _ 0 1 1 1
etcetera

Vilket resulterar i denna de Bruijn-sekvens:

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

Nedan markeras med {X X X} hur de åtta hörnen passeras (de unika fyrsiffriga sekvenserna får man genom att lägga till siffran efter hörnet, som ju är vilken kant man följer från hörnet - notera också att man lämnar hörnet den ena gången längs ena kanten och den andra gången längs den andra, till exempel {0 0 0} 0 respektive {0 0 0} 1).

      {0  0  0} 0  1  1  1  1  0  1  1  0  0  1  0  1
       0 {0  0  0} 1  1  1  1  0  1  1  0  0  1  0  1
       0  0 {0  0  1} 1  1  1  0  1  1  0  0  1  0  1
       0  0  0 {0  1  1} 1  1  0  1  1  0  0  1  0  1
       0  0  0  0 {1  1  1} 1  0  1  1  0  0  1  0  1
       0  0  0  0  1 {1  1  1} 0  1  1  0  0  1  0  1
       0  0  0  0  1  1 {1  1  0} 1  1  0  0  1  0  1
       0  0  0  0  1  1  1 {1  0  1} 1  0  0  1  0  1
       0  0  0  0  1  1  1  1 {0  1  1} 0  0  1  0  1
       0  0  0  0  1  1  1  1  0 {1  1  0} 0  1  0  1
       0  0  0  0  1  1  1  1  0  1 {1  0  0} 1  0  1
       0  0  0  0  1  1  1  1  0  1  1 {0  0  1} 0  1
       0  0  0  0  1  1  1  1  0  1  1  0 {0  1  0} 1
       0  0  0  0  1  1  1  1  0  1  1  0  0 {1  0  1}
   ... 0} 0  0  0  1  1  1  1  0  1  1  0  0  1 {0  1 ...
   ... 0  0} 0  0  1  1  1  1  0  1  1  0  0  1  0 {1 ...

...och vi är tillbaka vid utgångspunkten. Varje av de åtta tresiffriga sekvenserna (motsvarande de åtta hörnen) förekommer exakt två gånger och varje av de sexton fyrsiffriga sekvenserna (motsvarande de sexton kanterna) förekommer exakt en gång.

Algoritm

Man kan bilda en de Bruijn-sekvens genom konkatenering i lexikografisk ordning av alla Lyndonord med en längd som delar n. Det finns en algoritm som genererar alla Lyndonord med längder upp till och med n i lexikografisk ordning. Det första Lyndonordet består endast av alfabetets första tecken (t.ex. strängen "a") och det sista endast av det sista (t.ex. strängen "ö"), så start- och slutpunkterna är givna (från "a" ger algoritmen nästa ("aaa...ab") och från denna får man nästa tills man kommer till "ö"). Om det erhållna Lyndonordets längd delar strängens längd n så läggs den till till den de Bruijn-sekvens man bygger (sålunda "a"&"aaa...ab"&...&"äööö...ö"&"ö").

de Bruijn-torus

En de Bruijn-torus som innehåller alla binära 2×2-matriser. Matrisen med fyra vita bildas exempelvis av de fyra "hörnen".

En de Bruijn-torus är en toroidal array med egenskapen att varje k-när m × n-matris förekommer exakt en gång. (Arrayen behöver inte uttryckas toroidalt utan kan skrivas som en tvådimensionell m × n-matris.) Om n är ett så har vi en de Bruijn-sekvens, och om m=n och jämnt kan man också skapa en torus, annars är det en öppen fråga om de går att tillverka. Den minsta är (4,4;2,2)2 eller B2 som är 4x4 stor och som innehåller alla binära 2×2-matriser (den enda möjliga konfigurationen, bortsett från symmetrioperationer, är avbildad till höger). Nästa är (256,256;4,4)2 som är 256×256 stor och innehåller alla binära 4×4-matriser.

Användning

En de Bruijn-sekvens kan användas för att förkorta en brute force-attack på en portkodsliknande sekvens som inte har en avslutningstangent ("enter" eller "klar") utan accepterar de sista n inslagna tecknen. Till exempel skulle alla fyrsiffriga decimala koder kunna matas in med 10000+3=10003 tangenttryckningar i stället för att mata in 10000 fyrsiffriga koder (40000 tangenttryckningar).

Tecknen i en de Bruijn-sekvens skrivna runt ett cirkulärt föremål kan användas för att analysera dettas riktningsvinkel genom att läsa en sekvens om n tecken som är vända mot en bestämd punkt. Graykoder kan användas på ett liknande sätt. En de Bruijn-torus kan användas för en motsvarande tvådimensionell positionsbestämning.

de Bruijn-sekvenser har allmän användning inom experimentell neurovetenskap och psykologi vid undersökning av betydelsen av ordningen av olika stimuli på ett nervsystem,[15] och kan utvecklas specifikt för funktionell magnetresonanstomografi.[16]

En de Bruijn-sekvens kan användas för att snabbt hitta index för minsta eller mest signifikanta siffra i ett ord genom bitvisa operationer.[17]

Noter

  1. ^ [a b c] De Bruijn (1975).
  2. ^ Flye Sainte-Marie, C. (1894), ”Solution to question nr. 48”, L'intermédiaire des Mathématiciens 1: 107–110 
  3. ^ van Nooten (1993)
  4. ^ Subhash Kak, 2000, Indian binary numbers and the Kațapayādi notation, Annals of the Bhandarkar Oriental Research Institute, vol. 81, 2000, sid. 269-272.
  5. ^ Skrivs egentligen yamātārājabhānasalagam, men gam är också en lång stavelse, och för tydlighets skull skrivs den här gām.
  6. ^ [a b] Subhash Kak,2000, Yamātārājabhānasalagāṃ an interesting combinatoric sūtra Arkiverad 29 oktober 2014 hämtat från the Wayback Machine., Indian Journal of History of Science, 35.2 (2000), 123-127.
  7. ^ Rachel W. Hall. Math for poets and drummers Arkiverad 12 februari 2012 hämtat från the Wayback Machine.. Math Horizons 15 (2008) 10-11.
  8. ^ Donald Ervin Knuth (2006). The Art of Computer Programming, Fascicle 4: Generating All Trees -- History of Combinatorial Generation. Addison-Wesley. Sid. 50. ISBN 978-0-321-33570-8. http://books.google.com/?id=56LNfE2QGtYC&pg=PA50&dq=Pingala 
  9. ^ Stein, Sherman K. (1963), ”Yamátárájabhánasalagám”, The Man-made Universe: An Introduction to the Spirit of Mathematics, s. 110–118 . Reprinted in Wardhaugh, Benjamin, ed. (2012), A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing, Princeton Univ. Press, pp. 139–144.
  10. ^ Karl Popper (1935) (på tyska). Logik der Forschung. Routledge. Sid. 108. ISBN 978-0-415-27843-0. http://monoskop.org/images/e/ea/Popper_Karl_Logik_der_Forschung_Zur_Erkenntnistheorie_der_Modernen_Naturwissens_chaft_1935.pdf. Läst 29 oktober 2014  Arkiverad 9 november 2014 hämtat från the Wayback Machine. ”Arkiverade kopian”. Arkiverad från originalet den 9 november 2014. https://web.archive.org/web/20141109094011/http://monoskop.org/images/e/ea/Popper_Karl_Logik_der_Forschung_Zur_Erkenntnistheorie_der_Modernen_Naturwissens_chaft_1935.pdf. Läst 29 oktober 2014. 
  11. ^ Klein, Andreas (2013), Stream Ciphers, Springer, s. 59, ISBN 9781447150794, http://books.google.com/books?id=GYpEAAAAQBAJ&pg=PA59 .
  12. ^ Enligt Berstel & Perrin (2007), beskrevs den sekvens som genereras på detta sätt först av Martin (1934) (strängen skapades med en annan metod), och sambandet mellan den och Lyndonorden observerades av Fredricksen & Maiorana (1978).
  13. ^ Goresky, Mark; Klapper, Andrew (2012), ”8.2.5 Shift register generation of de Bruijn sequences”, Algebraic Shift Register Sequences, Cambridge University Press, s. 174–175, ISBN 9781107014992, http://books.google.com/books?id=sd9AqHeeHh4C&pg=PA174 .
  14. ^ Ralston, Anthony (1982), ”de Bruijn sequences—a model example of the interaction of discrete mathematics and computer science”, Mathematics Magazine 55 (3): 131–143, doi:10.2307/2690079 . See in particular "the finite field approach", pp. 136–139.
  15. ^ GK Aguirre, MG Mattar, L Magis-Weinberg. (2011) ”de Bruijn cycles for neural decoding”. Arkiverad från originalet den 4 mars 2016. https://web.archive.org/web/20160304074335/https://cfn.upenn.edu/aguirre/wiki/public%3Ade_bruijn. . NeuroImage 56: 1293–1300
  16. ^ ”De Bruijn cycle generator”. Arkiverad från originalet den 26 januari 2016. https://web.archive.org/web/20160126133108/https://cfn.upenn.edu/aguirre/wiki/public%3Ade_bruijn_software. 
  17. ^ Anderson, Sean Eron (1997–2009). ”Bit Twiddling Hacks”. Stanford University. http://graphics.stanford.edu/~seander/bithacks.html. Läst 12 februari 2009. 

Referenser

Externa länkar

Media som används på denna webbplats

De Bruijn sequence.svg
Författare/Upphovsman: Eviatar Bach, Licens: CC0
A diagram showing the properties of De Bruijn sequences, in this case k=2, n=2, probably the smallest non-trivial sequence.
2-2-4-4-de-Bruijn-torus.svg
Depicts the graph of a de Bruijn torus for 2 by 2 square binary matrices. Image created by Daniel Demski using Inkscape, based on information found in Hurlburt's "On the de Bruijn Torus Problem".