Evolutionary Construction of de Bruijn Sequences

<!DOCTYPE html> <html lang="en-us" xml:lang="en-us"> <head><script type="text/javascript" src="/_static/js/bundle-playback.js?v=HxkREWBo" charset="utf-8"></script> <script type="text/javascript" src="/_static/js/wombat.js?v=txqj7nKC" charset="utf-8"></script> <script>window.RufflePlayer=window.RufflePlayer||{};window.RufflePlayer.config={"autoplay":"on","unmuteOverlay":"hidden"};</script> <script type="text/javascript" src="/_static/js/ruffle/ruffle.js"></script> <script type="text/javascript"> __wm.init("https://web.archive.org/web"); __wm.wombat("https://csrc.nist.gov/pubs/conference/2012/07/20/evolutionary-construction-of-de-bruijn-sequences/final","20240105002050","https://web.archive.org/","web","/_static/", "1704414050"); </script> <link rel="stylesheet" type="text/css" href="/_static/css/banner-styles.css?v=S1zqJCYt" /> <link rel="stylesheet" type="text/css" href="/_static/css/iconochive.css?v=3PDvdIFv" />  <meta charset="utf-8"/> <title>Evolutionary Construction of de Bruijn Sequences | CSRC</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8"/> <meta http-equiv="content-style-type" content="text/css"/> <meta http-equiv="content-script-type" content="text/javascript"/> <meta name="viewport" content="width=device-width, initial-scale=1.0"/> <meta name="msapplication-config" content="/CSRC/Media/images/favicons/browserconfig.xml"/> <meta name="theme-color" content="#000000"/> <meta name="google-site-verification" content="xbrnrVYDgLD-Bd64xHLCt4XsPXzUhQ-4lGMj4TdUUTA"/> <meta description="A binary de Bruijn sequence of order n is a cyclic sequence of period 2^n, in which each n-bit pattern appears exactly once. These sequences are commonly used in applications such as stream cipher design, pseudo-random number generation, 3-D pattern recognition, network modeling, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n"/>  <meta name="dcterms.title" content="Evolutionary Construction of de Bruijn Sequences"/> <meta name="dcterms.description" content="A binary de Bruijn sequence of order n is a cyclic sequence of period 2^n, in which each n-bit pattern appears exactly once. These sequences are commonly used in applications such as stream cipher design, pseudo-random number generation, 3-D pattern recognition, network modeling, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n"/>  <meta name="dcterms.creator" content="Author: Meltem S枚nmez Turan"/>  <meta name="dcterms.date.created" schema="ISO8601" content="2012-07-20"/> <meta name="dcterms.identifier" content="https://csrc.nist.gov/pubs/conference/2012/07/20/evolutionary-construction-of-de-bruijn-sequences/final"/> <meta name="dcterms.language" scheme="DCTERMS.RFC1766" content="EN-US"/>  <meta name="citation_title" content="Evolutionary Construction of de Bruijn Sequences"/> <meta name="citation_publication_date" content="2012/07/20"/> <meta name="citation_doi" content="https://doi.org/10.1145/2046684.2046696"/> <meta name="citation_publisher" content="ACM"/> <meta name="citation_firstpage" content="81"/> <meta name="citation_lastpage" content="86"/> <meta name="citation_keywords" content="De Bruijn sequences,genetic algorithms,traveling salesman problem"/> <meta name="citation_language" content="en"/> <meta name="citation_pdf_url" content="https://doi.org/10.1145/2046684.2046696"/> <meta name="citation_abstract_html_url" content="https://csrc.nist.gov/pubs/conference/2012/07/20/evolutionary-construction-of-de-bruijn-sequences/final"/> <meta name="citation_conference_title" content="4th ACM Workshop on Security and Artificial Intelligence (AISec '11); 10/21/2011; Chicago, Illinois, United States"/> <meta name="citation_inbook_title" content="Proceedings of the 4th ACM Workshop on Security and Artificial Intelligence (AISec '11)"/>  <meta name="citation_author" content="S枚nmez Turan, Meltem"/>  <meta name="og:site_name" content="CSRC | NIST"/> <meta name="og:type" content="article"/> <meta name="og:url" content="https://web.archive.org/web/20240105002050im_/https://csrc.nist.gov/pubs/conference/2012/07/20/evolutionary-construction-of-de-bruijn-sequences/final"/> <meta name="og:title" content="Evolutionary Construction of de Bruijn Sequences"/> <meta name="og:description" content="A binary de Bruijn sequence of order n is a cyclic sequence of period 2^n, in which each n-bit pattern appears exactly once. These sequences are commonly used in applications such as stream cipher design, pseudo-random number generation, 3-D pattern recognition, network modeling, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n"/> <meta name="article:author" content="S枚nmez Turan, Meltem"/> <meta name="article:tag" content="De Bruijn sequences,genetic algorithms,traveling salesman problem"/> <meta name="article:published_time" content="2012-07-20"/> <link rel="apple-touch-icon" sizes="180x180" href="/web/20240105002050im_/https://csrc.nist.gov/images/icons/apple-touch-icon.png"/> <link rel="icon" type="image/png" href="/web/20240105002050im_/https://csrc.nist.gov/images/icons/favicon-32x32.png" sizes="32x32"/> <link rel="icon" type="image/png" href="/web/20240105002050im_/https://csrc.nist.gov/images/icons/favicon-16x16.png" sizes="16x16"/> <link rel="manifest" href="/web/20240105002050/https://csrc.nist.gov/images/icons/manifest.json"/> <link rel="mask-icon" href="/web/20240105002050im_/https://csrc.nist.gov/images/icons/safari-pinned-tab.svg" color="#000000"/> <link href="/web/20240105002050im_/https://csrc.nist.gov/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="shortcut icon"/> <link href="/web/20240105002050im_/https://csrc.nist.gov/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="icon"/> <link href="/web/20240105002050cs_/https://csrc.nist.gov/dist/app.css" rel="stylesheet"/>  <style> .grecaptcha-badge { visibility: hidden; } </style> <script async type="text/javascript" id="_fed_an_ua_tag" src="https://web.archive.org/web/20240105002050js_/https://dap.digitalgov.gov/Universal-Federated-Analytics-Min.js?agency=nist&subagency=csrc&pua=UA-66610693-15&yt=true&exts=xsd,xml,wav,mpg,mpeg,avi,rtf,webm,ogg,ogv,oga,map,otf,eot,svg,ttf,woff"></script> <style id="antiClickjackCss"> body > * { display: none !important; } #antiClickjack { display: block !important; } </style> <noscript> <style id="antiClickjackNoScript"> body > * { display: block !important; } #antiClickjack { display: none !important; } </style> </noscript> <script type="text/javascript" id="antiClickjackScript"> if (self === top) { // no clickjacking var antiClickjack = document.getElementById("antiClickjackCss"); antiClickjack.parentNode.removeChild(antiClickjack); } else { setTimeout(tryForward(), 5000); } function tryForward() { top.location = self.location; } </script>  <script async src="https://web.archive.org/web/20240105002050js_/https://www.googletagmanager.com/gtag/js?id=G-TSQ0PLGJZP"></script> <script> 聽聽window.dataLayer = window.dataLayer || []; 聽聽function gtag(){dataLayer.push(arguments);} 聽聽gtag('js', new Date()); 聽聽gtag('config', 'G-TSQ0PLGJZP'); </script>  <script>(function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://web.archive.org/web/20240105002050/https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-MZQC4NCJ');</script>  </head> <body>  <noscript><iframe src="https://web.archive.org/web/20240105002050if_/https://www.googletagmanager.com/ns.html?id=GTM-MZQC4NCJ" height="0" width="0" style="display:none;visibility:hidden"></iframe></noscript>  <div id="antiClickjack" style="display: none;"> <strong style="font-size: 1.6rem;">You are viewing this page in an unauthorized frame window.</strong> <p>This is a potential security issue, you are being redirected to <a href="https://web.archive.org/web/20240105002050/https://csrc.nist.gov/">https://csrc.nist.gov</a>.</p> </div> <section class="usa-banner" aria-label="Official government website"> <div class="usa-accordion container"> <header class="usa-banner__header"> <noscript> <p style="font-size: 0.85rem; font-weight: bold;">You have JavaScript disabled. This site requires JavaScript to be enabled for complete site functionality.</p> </noscript> <img class="usa-banner__header-flag" src="/web/20240105002050im_/https://csrc.nist.gov/images/usbanner/us_flag_small.png" alt="U.S. flag">   <span class="usa-banner__header-text">An official website of the United States government</span> <button id="gov-banner-button" class="usa-accordion__button usa-banner__button" data-toggle="collapse" data-target="#gov-banner" aria-expanded="true" aria-controls="gov-banner"> <span class="usa-banner__button-text">Here's how you know</span> </button> </header> <div class="usa-banner__content usa-accordion__content collapse in" role="tabpanel" id="gov-banner" aria-expanded="true"> <div class="row"> <div class="col-md-5 col-sm-12"> <div class="row"> <div class="col-sm-2 col-xs-3"> <img class="usa-banner__icon usa-media-block__img" src="/web/20240105002050im_/https://csrc.nist.gov/images/usbanner/icon-dot-gov.svg" alt="Dot gov"> </div> <div class="col-sm-10 col-xs-9"> <p> <strong>Official websites use .gov</strong> <br> A <strong>.gov</strong> website belongs to an official government organization in the United States. </p> </div> </div> </div> <div class="col-md-5 col-sm-12"> <div class="row"> <div class="col-sm-2 col-xs-3"> <img class="usa-banner__icon usa-media-block__img" src="/web/20240105002050im_/https://csrc.nist.gov/images/usbanner/icon-https.svg" alt="Https"> </div> <div class="col-sm-10 col-xs-9"> <p> <strong>Secure .gov websites use HTTPS</strong> <br> A <strong>lock</strong> (<img class="usa-banner__lock" src="/web/20240105002050im_/https://csrc.nist.gov/images/usbanner/lock.svg" alt="Dot gov">) or <strong>https://</strong> means you've safely connected to the .gov website. Share sensitive information only on official, secure websites. </p> </div> </div> </div> </div> </div> </div> </section> <nav id="navbar" class="navbar"> <div id="nist-menu-container" class="container"> <div class="row">  <div class="col-xs-6 col-md-4 navbar-header"> <a class="navbar-brand" href="https://web.archive.org/web/20240105002050/https://www.nist.gov/" target="_blank" id="navbar-brand-image"> <img src="/web/20240105002050im_/https://csrc.nist.gov/CSRC/media/images/svg/nist-logo.svg" alt="National Institute of Standards and Technology" width="110" height="30"> </a> </div> <div class="col-xs-6 col-md-8 navbar-nist-logo"> <div class="form-inline hidden-sm hidden-xs"> <form name="site-search" id="site-search-form" action="/web/20240105002050/https://csrc.nist.gov/search" method="GET"> <label for="search-csrc-query" class="element-invisible">Search</label> <input autocomplete="off" class="form-control" id="search-csrc-query" name="keywords" type="text" size="15" maxlength="128" placeholder="Search CSRC"/> <input type="hidden" name="ipp" value="25"/> <input type="hidden" name="sortBy" value="relevance"/> <input type="hidden" name="showOnly" value="publications,projects,news,events,presentations,glossary,topics"/> <input type="hidden" name="topicsMatch" value="ANY"/> <input type="hidden" name="status" value="Final,Draft"/> <button type="submit" id="search-csrc-submit-btn" class="form-submit"> <span class="element-invisible">Search</span> <i class="fa fa-search"></i> </button> </form> </div> <span id="nvd-menu-button" class="pull-right"> <a href="#" id="nvd-menu-button-link"> <span class="fa fa-bars"></span> <span id="nvd-menu-full-text">CSRC MENU</span> </a> </span> </div> </div> </div> <div class="form-inline hidden-md hidden-lg"> <form name="site-search-mobile" id="site-search-form-mobile" action="/web/20240105002050/https://csrc.nist.gov/search" method="GET"> <label for="search-csrc-query-mobile" class="element-invisible">Search</label> <input autocomplete="off" class="form-control" id="search-csrc-query-mobile" name="keywords" type="text" size="15" maxlength="128" placeholder="Search CSRC"/> <button type="submit" id="search-csrc-submit-btn-mobile" class="form-submit"> <span class="element-invisible">Search</span> <i class="fa fa-search"></i> </button> </form> </div> <div class="main-menu-row container">  <div id="main-menu-drop" class="col-lg-12" style="display: none;"> <ul> <li><a href="/web/20240105002050/https://csrc.nist.gov/projects">Projects</a></li> <li> <a href="/web/20240105002050/https://csrc.nist.gov/publications"> Publications <span class="expander fa fa-plus" id="main-menu-pubs-expander" data-expander-name="publications" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="publications" id="main-menu-pubs-expanded"> <div class="row"> <div class="col-lg-4"> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/drafts-open-for-comment">Drafts for Public Comment</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/draft-pubs">All Public Drafts</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/final-pubs">Final Pubs</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/fips">FIPS <small>(standards)</small></a></p> </div> <div class="col-lg-4"> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/sp">Special Publications (SP<small>s</small>)</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/ir">IR <small>(interagency/internal reports)</small></a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/cswp">CSWP <small>(cybersecurity white papers)</small></a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/itl-bulletin">ITL Bulletins</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/project-description">Project Descriptions</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/journal-article">Journal Articles</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/conference-paper">Conference Papers</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/publications/book">Books</a></p> </div> </div> </div> </li> <li> <a href="/web/20240105002050/https://csrc.nist.gov/topics"> Topics <span class="expander fa fa-plus" id="main-menu-topics-expander" data-expander-name="topics" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="topics" id="main-menu-topics-expanded"> <div class="row"> <div class="col-lg-4"> <p><a href="/web/20240105002050/https://csrc.nist.gov/Topics/Security-and-Privacy">Security & Privacy</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/Topics/Applications">Applications</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20240105002050/https://csrc.nist.gov/Topics/Technologies">Technologies</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/Topics/Sectors">Sectors</a></p> </div> <div class="col-lg-4"> <p><a href="/web/20240105002050/https://csrc.nist.gov/Topics/Laws-and-Regulations">Laws & Regulations</a></p> <p><a href="/web/20240105002050/https://csrc.nist.gov/Topics/Activities-and-Products">Activities & Products</a></p> </div> </div> </div> </li> <li><a href="/web/20240105002050/https://csrc.nist.gov/news">News & Updates</a></li> <li><a href="/web/20240105002050/https://csrc.nist.gov/events">Events</a></li> <li><a href="/web/20240105002050/https://csrc.nist.gov/glossary">Glossary</a></li> <li> <a href="/web/20240105002050/https://csrc.nist.gov/about"> About CSRC <span class="expander fa fa-plus" id="main-menu-about-expander" data-expander-name="about" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="about" id="main-menu-about-expanded"> <div class="row"> <div class="col-lg-6"> <p> <strong><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Computer-Security-Division">Computer Security Division</a></strong><br/> <ul> <li><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Computer-Security-Division/Cryptographic-Technology">Cryptographic Technology</a></li> <li><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Computer-Security-Division/Secure-Systems-and-Applications">Secure Systems and Applications</a></li> <li><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Components-and-Mechanisms">Security Components and Mechanisms</a></li> <li><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Engineering-and-Risk-Management">Security Engineering and Risk Management</a></li> <li><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Computer-Security-Division/Security-Testing-Validation-and-Measurement">Security Testing, Validation, and Measurement</a></li> </ul> </p> </div> <div class="col-lg-6"> <p> <strong><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division">Applied Cybersecurity Division</a></strong><br/> <ul> <li><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division/Cybersecurity-and-Privacy-Applications">Cybersecurity and Privacy Applications</a></li> <li><a href="/web/20240105002050/https://csrc.nist.gov/Groups/Applied-Cybersecurity-Division/National-Cybersecurity-Center-of-Excellence">National Cybersecurity Center of Excellence (NCCoE)</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/nice/">National Initiative for Cybersecurity Education (NICE)</a></li> </ul> </p> <p> <a href="/web/20240105002050/https://csrc.nist.gov/contact"> Contact Us </a> </p> </div> </div> </div> </li> </ul> </div> </div> </nav> <section id="itl-header" class="has-menu"> <div class="container"> <div class="row"> <div class="col-sm-12 col-md-8"> <div class="hidden-xs hidden-sm" id="itl-header-lg"> <a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/itl" target="_blank" id="itl-header-link">Information Technology Laboratory</a> </div> <div class="hidden-xs hidden-sm" id="csrc-header-lg"> <a href="/web/20240105002050/https://csrc.nist.gov/" id="csrc-header-link-lg">Computer Security Resource Center</a> </div> </div> <div class="col-sm-12 col-md-4"> <div class="hidden-xs hidden-sm hidden-md"> <a id="logo-csrc-lg" href="/web/20240105002050/https://csrc.nist.gov/"><img id="img-logo-csrc-lg" src="/web/20240105002050im_/https://csrc.nist.gov/CSRC/Media/images/nist-logo-csrc-white.svg" alt="CSRC Logo" class="csrc-header-logo"></a> </div> <div class="hidden-lg"> <a id="logo-csrc-sm" href="/web/20240105002050/https://csrc.nist.gov/"><img id="img-logo-csrc-sm" src="/web/20240105002050im_/https://csrc.nist.gov/CSRC/Media/images/nist-logo-csrc-white.svg" alt="CSRC Logo" class="csrc-header-logo"></a> </div> </div> </div> </div> </section> <div id="body-section" class="container"> <div class="publications-detail"> <ol class="breadcrumb"> <a href="/web/20240105002050/https://csrc.nist.gov/publications" class="breadcrumb-link">Publications</a> </ol> <h3 id="pub-header-display-container"> <span id="pub-header-full-display"> Conference Paper </span> </h3> <h1 id="pub-title">Evolutionary Construction of de Bruijn Sequences</h1> <div class="page-social-buttons" id=""page-social-buttons""> <a href="https://web.archive.org/web/20240105002050/https://www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fcsrc.nist.gov%2Fpubs%2Fconference%2F2012%2F07%2F20%2Fevolutionary-construction-of-de-bruijn-sequences%2Ffinal" class="social-facebook"><i class="fa fa-facebook fa-fw" aria-hidden="true"></i><span class="sr-only">Share to Facebook</span></a> <a href="https://web.archive.org/web/20240105002050/https://twitter.com/share?url=https%3A%2F%2Fcsrc.nist.gov%2Fpubs%2Fconference%2F2012%2F07%2F20%2Fevolutionary-construction-of-de-bruijn-sequences%2Ffinal" class="social-twitter"><i class="fa fa-twitter fa-fw" aria-hidden="true"></i><span class="sr-only">Share to Twitter</span></a> <a href="https://web.archive.org/web/20240105002050/https://www.linkedin.com/shareArticle?mini=true&url=https%3A%2F%2Fcsrc.nist.gov%2Fpubs%2Fconference%2F2012%2F07%2F20%2Fevolutionary-construction-of-de-bruijn-sequences%2Ffinal&source=csrc.nist.gov" class="social-linked-in"><i class="fa fa-linkedin fa-fw" aria-hidden="true"></i><span class="sr-only">Share to LinkedIn</span></a> <a href="https://web.archive.org/web/20240105002050/mailto:/?subject=csrc.nist.gov&body=Check out this site https://csrc.nist.gov/pubs/conference/2012/07/20/evolutionary-construction-of-de-bruijn-sequences/final" class="social-email"><i class="fa fa-envelope fa-fw" aria-hidden="true"></i><span class="sr-only">Share ia Email</span></a> </div> <p class="hidden-lg hidden-md">     <a href="#pubs-documentation" class="btn btn-lg btn-info" id="pub-topics-anchor-sm">Documentation</a> </p> <div class="row"> <div class="col-md-8 col-sm-12 publication-panel"> <p> <strong>Published:</strong> <span id="pub-release-date" data-date-type="release">July 20, 2012</span><br/> </p> <h4>Author(s)</h4> <p id="pub-authors-container" data-total="1"> <span id="pub-author-0">Meltem S枚nmez Turan</span> </p> <h4>Conference</h4> <p> <strong>Name:</strong> <span id="pub-conf-name">4th ACM Workshop on Security and Artificial Intelligence (AISec '11)</span><br/> <strong>Dates:</strong> <span id="pub-conf-dates">10/21/2011</span><br/> <strong>Location:</strong> <span id="pub-conf-location">Chicago, Illinois, United States</span><br/> <strong>Citation:</strong> <span id="pub-conf-citation">Proceedings of the 4th ACM Workshop on Security and Artificial Intelligence (AISec '11), pp. 81-86</span><br/> </p> <div class="bs-callout bs-callout-success pub-abstract-callout"> <h4 id="pubs-abstract-header">Abstract</h4> <div class="hidden-sm hidden-xs hidden-xxs" id="pub-detail-abstract-info">A binary de Bruijn sequence of order n is a cyclic sequence of period 2^n, in which each n-bit pattern appears exactly once. These sequences are commonly used in applications such as stream cipher design, pseudo-random number generation, 3-D pattern recognition, network modeling, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n<=14.</div> <div class="hidden-lg hidden-md"> <div id="pub-detail-abstract-min"> A binary de Bruijn sequence of order n is a cyclic sequence of period 2^n, in which each n-bit pattern appears exactly once. These sequences are commonly used in applications such as stream cipher design, pseudo-random number generation, 3-D pattern recognition, network modeling, mainly due to their... <a href="#pubs-abstract-header" id="pub-detail-abs-show">See full abstract</a> </div> <div id="pub-detail-abstract-all" style="display: none;"> A binary de Bruijn sequence of order n is a cyclic sequence of period 2^n, in which each n-bit pattern appears exactly once. These sequences are commonly used in applications such as stream cipher design, pseudo-random number generation, 3-D pattern recognition, network modeling, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n<=14.<br/> <a href="#pubs-abstract-header" id="pub-detail-abs-hide">Hide full abstract</a> </div> </div> <h4>Keywords</h4> <span id="pub-keywords-container" data-total="3"> <span id="pub-keyword-0">De Bruijn sequences</span>; <span id="pub-keyword-1">genetic algorithms</span>; <span id="pub-keyword-2">traveling salesman problem</span> </span> </div> <h5>Control Families</h5> <p> <span id="pub-control-fam-container" data-total="0">None selected</span> </p> </div> <div class="col-md-4 col-sm-12"> <div class="bs-callout bs-callout-success" id="pubs-documentation"> <h4>Documentation</h4> <p> <strong>Publication:</strong><br/> <a href="https://web.archive.org/web/20240105002050/https://doi.org/10.1145/2046684.2046696" id="pub-doi-link"> <i class="fa fa-external-link" aria-hidden="true"></i> https://doi.org/10.1145/2046684.2046696 </a><br/> </p> <p> <strong>Supplemental Material:</strong><br/> <span id="pub-supp-container" data-total="0">None available</span><br/> </p> <p> <strong>Document History:</strong><br/> <span id="pub-history-container" data-total="1"> 07/20/12: <span id="pub-history-link-0" data-current-document="true">Conference Paper (Final)</span><br/> </span> </p> </div> </div> </div> </div> <div id="footer-pusher"></div> </div> <footer id="footer"> <div class="container"> <div class="row"> <div class="col-sm-6"> <span class="hidden-xs"> <a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/" title="National Institute of Standards and Technology" rel="home" target="_blank" class="footer-nist-logo" id="footer-nist-logo-link"> <img src="/web/20240105002050im_/https://csrc.nist.gov/CSRC/Media/images/nist-logo-brand-white.svg" alt="National Institute of Standards and Technology logo" id="footer-nist-logo"/> </a> </span> <div class="row footer-contact-container"> <div class="col-sm-12" id="footer-address"> <strong>HEADQUARTERS</strong><br> 100 Bureau Drive<br> Gaithersburg, MD 20899 </div> </div> </div> <div class="col-sm-6"> <ul class="social-list text-right" style="display: block;"> <li class="field-item service-twitter list-horiz"> <a href="https://web.archive.org/web/20240105002050/https://twitter.com/NISTCyber" class="social-btn social-btn--large extlink ext" id="footer-social-twitter-link"> <i class="fa fa-twitter fa-fw"><span class="element-invisible">twitter</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-facebook list-horiz"> <a href="https://web.archive.org/web/20240105002050/https://www.facebook.com/NIST" class="social-btn social-btn--large extlink ext" id="footer-social-facebook-link"> <i class="fa fa-facebook fa-fw"><span class="element-invisible">facebook</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-linkedin list-horiz"> <a href="https://web.archive.org/web/20240105002050/https://www.linkedin.com/company/nist" class="social-btn social-btn--large extlink ext" id="footer-social-linkedin-link"> <i class="fa fa-linkedin fa-fw"><span class="element-invisible">linkedin</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-instagram list-horiz"> <a href="https://web.archive.org/web/20240105002050/https://www.instagram.com/usnistgov/" class="social-btn social-btn--large extlink ext" id="footer-social-instagram-link"> <i class="fa fa-instagram fa-fw"><span class="element-invisible">instagram</span></i> <span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-youtube list-horiz"> <a href="https://web.archive.org/web/20240105002050/https://www.youtube.com/user/USNISTGOV" class="social-btn social-btn--large extlink ext" id="footer-social-youtube-link"> <i class="fa fa-youtube fa-fw"><span class="element-invisible">youtube</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-rss list-horiz"> <a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/news-events/nist-rss-feeds" class="social-btn social-btn--large extlink" id="footer-social-rss-link"> <i class="fa fa-rss fa-fw"><span class="element-invisible">rss</span></i> </a> </li> <li class="field-item service-govdelivery list-horiz last"> <a href="https://web.archive.org/web/20240105002050/https://public.govdelivery.com/accounts/USNIST/subscriber/new?qsp=USNIST_3" class="social-btn social-btn--large extlink ext" title="Subscribe to CSRC and publication updates, and other NIST cybersecurity news" id="footer-social-govdelivery-link"> <i class="fa fa-envelope fa-fw"><span class="element-invisible">govdelivery</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> </ul> <p class="text-right"> Want updates about CSRC and our publications? <a href="https://web.archive.org/web/20240105002050/https://public.govdelivery.com/accounts/USNIST/subscriber/new?qsp=USNIST_3" class="btn btn-lg btn-primary" style="background-color: #12659c!important; border-color: #12659c!important;" id="footer-subscribe-link">Subscribe</a> </p> </div> </div> <div class="row hidden-sm hidden-md hidden-lg"> <div class="col-sm-12"> <a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/" title="National Institute of Standards and Technology" rel="home" target="_blank" class="footer-nist-logo" id="footer-bottom-nist-logo-link"> <img src="/web/20240105002050im_/https://csrc.nist.gov/CSRC/Media/images/logo_rev.png" alt="National Institute of Standards and Technology logo" id="footer-bottom-nist-logo"/> </a> </div> </div> <div class="row"> <div class="col-sm-6"> <p> <a href="/web/20240105002050/https://csrc.nist.gov/about/contact" id="footer-contact-us-link">Contact Us</a> | <a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/about-nist/our-organization" style="display: inline-block;" id="footer-org-link">Our Other Offices</a> </p> </div> <div class="col-sm-6"> <span class="pull-right text-right"> Send inquiries to <a href="https://web.archive.org/web/20240105002050/mailto:csrc-inquiry@nist.gov?subject=CSRC Inquiry" style="display: inline-block;" id="footer-inquiries-link">csrc-inquiry@nist.gov</a> </span> </div> </div> <div class="row"> <div class="footer-bottom-links-container" id="footer-bottom-links-container"> <ul> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/privacy-policy">Site Privacy</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/oism/accessibility">Accessibility</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/privacy">Privacy Program</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/oism/copyrights">Copyrights</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.commerce.gov/vulnerability-disclosure-policy">Vulnerability Disclosure</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/no-fear-act-policy">No Fear Act Policy</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/foia">FOIA</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/environmental-policy-statement">Environmental Policy</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/summary-report-scientific-integrity">Scientific Integrity</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.nist.gov/nist-information-quality-standards">Information Quality Standards</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.commerce.gov/">Commerce.gov</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.science.gov/">Science.gov</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://www.usa.gov/">USA.gov</a></li> <li><a href="https://web.archive.org/web/20240105002050/https://vote.gov/">Vote.gov</a></li> </ul> </div> </div> </div> </footer> <script type="text/javascript" src="/web/20240105002050js_/https://csrc.nist.gov/dist/js/quick-collapse.js"></script> <script type="text/javascript" src="/web/20240105002050js_/https://csrc.nist.gov/dist/app.bundle.js"></script> </body> </html>

CINXE.COM

Evolutionary Construction of de Bruijn Sequences | CSRC