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

研究成果: Article › 同行評審

6 引文斯高帕斯（Scopus）

摘要

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

原文	English
頁（從 - 到）	571-577
頁數	7
期刊	Electronic Notes in Discrete Mathematics
卷	29
發行號	SPEC. ISS.
DOIs	https://doi.org/10.1016/j.endm.2007.07.091
出版狀態	Published - 15 8月 2007
對外發佈	是

存取文件

10.1016/j.endm.2007.07.091

其它文件與鏈接

Link to publication in Scopus

引用此

@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 BV",

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 - https://www.scopus.com/pages/publications/34547657696

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

摘要

存取文件

其它文件與鏈接

指紋

引用此