A fast algorithm to generate Beckett-Gray codes. Extended Abstract

Joe Sawada; Dennis Chi Him Wong

doi:10.1016/j.endm.2007.07.091

A fast algorithm to generate Beckett-Gray codes. Extended Abstract

Joe Sawada, Dennis Chi Him Wong

University of Guelph

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

We provide several heuristics to improve the efficiency of exhaustively generating Gray codes on length n binary strings. We then apply the heuristics to a restricted class of Gray codes on binary strings known as Beckett-Gray codes. The resulting algoirthm has a speed-up by a factor of 60 over the fastest previously known algorithm when n = 6. It was also used to discover over 9500 new Beckett-Gray codes for n = 7 in the equivalent of three months of computation time. Crown

Original language	English
Pages (from-to)	571-577
Number of pages	7
Journal	Electronic Notes in Discrete Mathematics
Volume	29
Issue number	SPEC. ISS.
DOIs	https://doi.org/10.1016/j.endm.2007.07.091
Publication status	Published - 15 Aug 2007
Externally published	Yes

Keywords

Beckett-Gray codes
Code generation
Enumeration
Gray codes

Access to Document

10.1016/j.endm.2007.07.091

Cite this

@article{e1dc413fab9348da8c3aa640ceac7c53,

title = "A fast algorithm to generate Beckett-Gray codes. Extended Abstract",

abstract = "We provide several heuristics to improve the efficiency of exhaustively generating Gray codes on length n binary strings. We then apply the heuristics to a restricted class of Gray codes on binary strings known as Beckett-Gray codes. The resulting algoirthm has a speed-up by a factor of 60 over the fastest previously known algorithm when n = 6. It was also used to discover over 9500 new Beckett-Gray codes for n = 7 in the equivalent of three months of computation time. Crown",

keywords = "Beckett-Gray codes, Code generation, Enumeration, Gray codes",

author = "Joe Sawada and Wong, {Dennis Chi Him}",

note = "Funding Information: 1 Research supported by NSERC. 2 Email: [email protected] 3 Email: [email protected]",

year = "2007",

month = aug,

day = "15",

doi = "10.1016/j.endm.2007.07.091",

language = "English",

volume = "29",

pages = "571--577",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

number = "SPEC. ISS.",

}

TY - JOUR

T1 - A fast algorithm to generate Beckett-Gray codes. Extended Abstract

AU - Sawada, Joe

AU - Wong, Dennis Chi Him

N1 - Funding Information: 1 Research supported by NSERC. 2 Email: [email protected] 3 Email: [email protected]

PY - 2007/8/15

Y1 - 2007/8/15

N2 - We provide several heuristics to improve the efficiency of exhaustively generating Gray codes on length n binary strings. We then apply the heuristics to a restricted class of Gray codes on binary strings known as Beckett-Gray codes. The resulting algoirthm has a speed-up by a factor of 60 over the fastest previously known algorithm when n = 6. It was also used to discover over 9500 new Beckett-Gray codes for n = 7 in the equivalent of three months of computation time. Crown

AB - We provide several heuristics to improve the efficiency of exhaustively generating Gray codes on length n binary strings. We then apply the heuristics to a restricted class of Gray codes on binary strings known as Beckett-Gray codes. The resulting algoirthm has a speed-up by a factor of 60 over the fastest previously known algorithm when n = 6. It was also used to discover over 9500 new Beckett-Gray codes for n = 7 in the equivalent of three months of computation time. Crown

KW - Beckett-Gray codes

KW - Code generation

KW - Enumeration

KW - Gray codes

UR - http://www.scopus.com/inward/record.url?scp=34547657696&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2007.07.091

DO - 10.1016/j.endm.2007.07.091

M3 - Article

AN - SCOPUS:34547657696

SN - 1571-0653

VL - 29

SP - 571

EP - 577

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - SPEC. ISS.

ER -

A fast algorithm to generate Beckett-Gray codes. Extended Abstract

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this