On the quadratic spans of DeBruijn sequences

The quadratic span of a periodic binary sequence is defined to be the length of the shortest quadratic feedback shift register (FSR) that generates it. An algorithm for computing the quadratic span of a binary sequence is described. The required increase in quadratic span is determined for the speci...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 1990-07, Vol.36 (4), p.822-829
Main Authors: Chan, A.H., Games, R.A.
Format: Article
Language:English
Subjects:
Applied sciences
Binary sequences
Circuit testing
Communication systems
Costs
Cryptography
Exact sciences and technology
Feedback
Information theory
Information, signal and communications theory
Random sequences
Shift registers
Spread spectrum communication
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c303t-8394cc82aba25ce661af33cb0501008a503476c0af560d80725c8750a0e001d93
cites cdi_FETCH-LOGICAL-c303t-8394cc82aba25ce661af33cb0501008a503476c0af560d80725c8750a0e001d93
container_end_page 829
container_issue 4
container_start_page 822
container_title IEEE transactions on information theory
container_volume 36
creator Chan, A.H.
Games, R.A.
description The quadratic span of a periodic binary sequence is defined to be the length of the shortest quadratic feedback shift register (FSR) that generates it. An algorithm for computing the quadratic span of a binary sequence is described. The required increase in quadratic span is determined for the special case of when a discrepancy occurs in a linear FSR that generates an initial portion of a sequence. The quadratic spans of binary DeBruijn sequences are investigated. An upper bound for the quadratic span of a DeBruijn sequence of span n is given; this bound is attained by the class of DeBruijn sequences obtained from m-sequences. It is easy to see that a lower bound is n+1, but a lower bound of n+2 is conjectured. The distributions of quadratic spans of DeBruijn sequences of span 3, 4, 5 and 6 are presented.< >
doi_str_mv 10.1109/18.53741
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1109_18_53741</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>53741</ieee_id><sourcerecordid>28485318</sourcerecordid><originalsourceid>FETCH-LOGICAL-c303t-8394cc82aba25ce661af33cb0501008a503476c0af560d80725c8750a0e001d93</originalsourceid><addsrcrecordid>eNpF0E1PwzAMBuAIgcQYSFy59YAQBzqcJmnTI4xPadIucI68zBWdunaL2wP_nrBNcLIsP3ptWYhLCRMpobyXdmJUoeWRGEljirTMjT4WIwBp01JreyrOmFex1UZmI3E3b5P-i5LtgMuAfe0T3mDLSVclT_QYhnrVJkzbgVpPfC5OKmyYLg51LD5fnj-mb-ls_vo-fZilXoHqU6tK7b3NcIGZ8ZTnEiul_AIMSACLBpQucg9YmRyWFoqobGEAgeJdy1KNxc0-dxO6uJp7t67ZU9NgS93ALrPaGiVthLd76EPHHKhym1CvMXw7Ce73HU5at3tHpNeHTGSPTRWw9TX_eWN0lkMe2dWe1UT0P91F_AC59mP9</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>28485318</pqid></control><display><type>article</type><title>On the quadratic spans of DeBruijn sequences</title><source>IEEE Xplore (Online service)</source><creator>Chan, A.H. ; Games, R.A.</creator><creatorcontrib>Chan, A.H. ; Games, R.A.</creatorcontrib><description>The quadratic span of a periodic binary sequence is defined to be the length of the shortest quadratic feedback shift register (FSR) that generates it. An algorithm for computing the quadratic span of a binary sequence is described. The required increase in quadratic span is determined for the special case of when a discrepancy occurs in a linear FSR that generates an initial portion of a sequence. The quadratic spans of binary DeBruijn sequences are investigated. An upper bound for the quadratic span of a DeBruijn sequence of span n is given; this bound is attained by the class of DeBruijn sequences obtained from m-sequences. It is easy to see that a lower bound is n+1, but a lower bound of n+2 is conjectured. The distributions of quadratic spans of DeBruijn sequences of span 3, 4, 5 and 6 are presented.&lt; &gt;</description><identifier>ISSN: 0018-9448</identifier><identifier>EISSN: 1557-9654</identifier><identifier>DOI: 10.1109/18.53741</identifier><identifier>CODEN: IETTAW</identifier><language>eng</language><publisher>New York, NY: IEEE</publisher><subject>Applied sciences ; Binary sequences ; Circuit testing ; Communication systems ; Costs ; Cryptography ; Exact sciences and technology ; Feedback ; Information theory ; Information, signal and communications theory ; Random sequences ; Shift registers ; Spread spectrum communication ; Telecommunications and information theory</subject><ispartof>IEEE transactions on information theory, 1990-07, Vol.36 (4), p.822-829</ispartof><rights>1992 INIST-CNRS</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c303t-8394cc82aba25ce661af33cb0501008a503476c0af560d80725c8750a0e001d93</citedby><cites>FETCH-LOGICAL-c303t-8394cc82aba25ce661af33cb0501008a503476c0af560d80725c8750a0e001d93</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/53741$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=5542606$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Chan, A.H.</creatorcontrib><creatorcontrib>Games, R.A.</creatorcontrib><title>On the quadratic spans of DeBruijn sequences</title><title>IEEE transactions on information theory</title><addtitle>TIT</addtitle><description>The quadratic span of a periodic binary sequence is defined to be the length of the shortest quadratic feedback shift register (FSR) that generates it. An algorithm for computing the quadratic span of a binary sequence is described. The required increase in quadratic span is determined for the special case of when a discrepancy occurs in a linear FSR that generates an initial portion of a sequence. The quadratic spans of binary DeBruijn sequences are investigated. An upper bound for the quadratic span of a DeBruijn sequence of span n is given; this bound is attained by the class of DeBruijn sequences obtained from m-sequences. It is easy to see that a lower bound is n+1, but a lower bound of n+2 is conjectured. The distributions of quadratic spans of DeBruijn sequences of span 3, 4, 5 and 6 are presented.&lt; &gt;</description><subject>Applied sciences</subject><subject>Binary sequences</subject><subject>Circuit testing</subject><subject>Communication systems</subject><subject>Costs</subject><subject>Cryptography</subject><subject>Exact sciences and technology</subject><subject>Feedback</subject><subject>Information theory</subject><subject>Information, signal and communications theory</subject><subject>Random sequences</subject><subject>Shift registers</subject><subject>Spread spectrum communication</subject><subject>Telecommunications and information theory</subject><issn>0018-9448</issn><issn>1557-9654</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1990</creationdate><recordtype>article</recordtype><recordid>eNpF0E1PwzAMBuAIgcQYSFy59YAQBzqcJmnTI4xPadIucI68zBWdunaL2wP_nrBNcLIsP3ptWYhLCRMpobyXdmJUoeWRGEljirTMjT4WIwBp01JreyrOmFex1UZmI3E3b5P-i5LtgMuAfe0T3mDLSVclT_QYhnrVJkzbgVpPfC5OKmyYLg51LD5fnj-mb-ls_vo-fZilXoHqU6tK7b3NcIGZ8ZTnEiul_AIMSACLBpQucg9YmRyWFoqobGEAgeJdy1KNxc0-dxO6uJp7t67ZU9NgS93ALrPaGiVthLd76EPHHKhym1CvMXw7Ce73HU5at3tHpNeHTGSPTRWw9TX_eWN0lkMe2dWe1UT0P91F_AC59mP9</recordid><startdate>19900701</startdate><enddate>19900701</enddate><creator>Chan, A.H.</creator><creator>Games, R.A.</creator><general>IEEE</general><general>Institute of Electrical and Electronics Engineers</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>19900701</creationdate><title>On the quadratic spans of DeBruijn sequences</title><author>Chan, A.H. ; Games, R.A.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c303t-8394cc82aba25ce661af33cb0501008a503476c0af560d80725c8750a0e001d93</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1990</creationdate><topic>Applied sciences</topic><topic>Binary sequences</topic><topic>Circuit testing</topic><topic>Communication systems</topic><topic>Costs</topic><topic>Cryptography</topic><topic>Exact sciences and technology</topic><topic>Feedback</topic><topic>Information theory</topic><topic>Information, signal and communications theory</topic><topic>Random sequences</topic><topic>Shift registers</topic><topic>Spread spectrum communication</topic><topic>Telecommunications and information theory</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Chan, A.H.</creatorcontrib><creatorcontrib>Games, R.A.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on information theory</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Chan, A.H.</au><au>Games, R.A.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On the quadratic spans of DeBruijn sequences</atitle><jtitle>IEEE transactions on information theory</jtitle><stitle>TIT</stitle><date>1990-07-01</date><risdate>1990</risdate><volume>36</volume><issue>4</issue><spage>822</spage><epage>829</epage><pages>822-829</pages><issn>0018-9448</issn><eissn>1557-9654</eissn><coden>IETTAW</coden><abstract>The quadratic span of a periodic binary sequence is defined to be the length of the shortest quadratic feedback shift register (FSR) that generates it. An algorithm for computing the quadratic span of a binary sequence is described. The required increase in quadratic span is determined for the special case of when a discrepancy occurs in a linear FSR that generates an initial portion of a sequence. The quadratic spans of binary DeBruijn sequences are investigated. An upper bound for the quadratic span of a DeBruijn sequence of span n is given; this bound is attained by the class of DeBruijn sequences obtained from m-sequences. It is easy to see that a lower bound is n+1, but a lower bound of n+2 is conjectured. The distributions of quadratic spans of DeBruijn sequences of span 3, 4, 5 and 6 are presented.&lt; &gt;</abstract><cop>New York, NY</cop><pub>IEEE</pub><doi>10.1109/18.53741</doi><tpages>8</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0018-9448
ispartof IEEE transactions on information theory, 1990-07, Vol.36 (4), p.822-829
issn 0018-9448
1557-9654
language eng
recordid cdi_crossref_primary_10_1109_18_53741
source IEEE Xplore (Online service)
subjects Applied sciences
Binary sequences
Circuit testing
Communication systems
Costs
Cryptography
Exact sciences and technology
Feedback
Information theory
Information, signal and communications theory
Random sequences
Shift registers
Spread spectrum communication
Telecommunications and information theory
title On the quadratic spans of DeBruijn sequences
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T12%3A53%3A13IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=On%20the%20quadratic%20spans%20of%20DeBruijn%20sequences&rft.jtitle=IEEE%20transactions%20on%20information%20theory&rft.au=Chan,%20A.H.&rft.date=1990-07-01&rft.volume=36&rft.issue=4&rft.spage=822&rft.epage=829&rft.pages=822-829&rft.issn=0018-9448&rft.eissn=1557-9654&rft.coden=IETTAW&rft_id=info:doi/10.1109/18.53741&rft_dat=%3Cproquest_cross%3E28485318%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c303t-8394cc82aba25ce661af33cb0501008a503476c0af560d80725c8750a0e001d93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=28485318&rft_id=info:pmid/&rft_ieee_id=53741&rfr_iscdi=true