Switching of covering codes

Patric R.J. Östergård; William D. Weakley

doi:10.1016/j.disc.2017.10.020

Switching of covering codes

Patric R.J. Östergård, William D. Weakley^*

^*Corresponding author for this work

Information Theory

Indiana University-Purdue University Indianapolis

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

1 Citation (Scopus)

Abstract

Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length n≥3, the semiautomorphisms are exactly the bijections that preserve the set of r-balls for each radius r. Switching of optimal codes of size at most 7 and of codes attaining K(8,1)=32 is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes.

Original language	English
Pages (from-to)	1778-1788
Number of pages	11
Journal	Discrete Mathematics
Volume	341
Issue number	6
Early online date	2017
DOIs	https://doi.org/10.1016/j.disc.2017.10.020
Publication status	Published - Jun 2018
MoE publication type	A1 Journal article-refereed

Keywords

Automorphism group
Covering code
Dominating set
Error-correcting code
Hypercube
Switching

Access to Document

10.1016/j.disc.2017.10.020

Cite this

@article{8782916487994d44845555ae6494180f,

title = "Switching of covering codes",

abstract = "Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length n≥3, the semiautomorphisms are exactly the bijections that preserve the set of r-balls for each radius r. Switching of optimal codes of size at most 7 and of codes attaining K(8,1)=32 is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes.",

keywords = "Automorphism group, Covering code, Dominating set, Error-correcting code, Hypercube, Switching",

author = "{\"O}sterg{\aa}rd, {Patric R.J.} and Weakley, {William D.}",

year = "2018",

month = jun,

doi = "10.1016/j.disc.2017.10.020",

language = "English",

volume = "341",

pages = "1778--1788",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Switching of covering codes

AU - Östergård, Patric R.J.

AU - Weakley, William D.

PY - 2018/6

Y1 - 2018/6

N2 - Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length n≥3, the semiautomorphisms are exactly the bijections that preserve the set of r-balls for each radius r. Switching of optimal codes of size at most 7 and of codes attaining K(8,1)=32 is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes.

AB - Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length n≥3, the semiautomorphisms are exactly the bijections that preserve the set of r-balls for each radius r. Switching of optimal codes of size at most 7 and of codes attaining K(8,1)=32 is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes.

KW - Automorphism group

KW - Covering code

KW - Dominating set

KW - Error-correcting code

KW - Hypercube

KW - Switching

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

U2 - 10.1016/j.disc.2017.10.020

DO - 10.1016/j.disc.2017.10.020

M3 - Article

AN - SCOPUS:85034570723

SN - 0012-365X

VL - 341

SP - 1778

EP - 1788

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

ER -

Switching of covering codes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this