Connections between the Error Probability and the r-wise Hamming Distances

Hsuan Yin Lin; Stefan Michael Moser; Po-Ning Chen

doi:10.23919/ISITA.2018.8664296

Connections between the Error Probability and the r-wise Hamming Distances

Hsuan Yin Lin, Stefan Michael Moser, Po-Ning Chen

Department of Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

An extension from the pairwise Hamming distance to the r-wise Hamming distance is presented. It can be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code over the binary erasure channel (BEC). By noting that good codes always have large minimum r-wise Hamming distances for all r, a new design criterion for a code is introduced: the minimum r-wise Hamming distance. We then prove an upper bound for the minimum r-wise Hamming distance of an arbitrary code, called the generalized Plotkin bound, and provide a class of (nonlinear) codes that achieve the bound for every r.

Original language	English
Title of host publication	Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	130-134
Number of pages	5
ISBN (Electronic)	9784885523182
DOIs	https://doi.org/10.23919/ISITA.2018.8664296
State	Published - 8 Mar 2019
Event	15th International Symposium on Information Theory and Its Applications, ISITA 2018 - Singapore, Singapore Duration: 28 Oct 2018 → 31 Oct 2018

Publication series

Name	Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018

Conference

Conference	15th International Symposium on Information Theory and Its Applications, ISITA 2018
Country/Territory	Singapore
City	Singapore
Period	28/10/18 → 31/10/18

Access to Document

10.23919/ISITA.2018.8664296

Cite this

Lin, H. Y., Moser, S. M., & Chen, P.-N. (2019). Connections between the Error Probability and the r-wise Hamming Distances. In Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018 (pp. 130-134). Article 8664296 (Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/ISITA.2018.8664296

Lin, Hsuan Yin ; Moser, Stefan Michael ; Chen, Po-Ning. / Connections between the Error Probability and the r-wise Hamming Distances. Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 130-134 (Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018).

@inproceedings{a87db236c7e24af384ebd25f85cd3898,

title = "Connections between the Error Probability and the r-wise Hamming Distances",

abstract = "An extension from the pairwise Hamming distance to the r-wise Hamming distance is presented. It can be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code over the binary erasure channel (BEC). By noting that good codes always have large minimum r-wise Hamming distances for all r, a new design criterion for a code is introduced: the minimum r-wise Hamming distance. We then prove an upper bound for the minimum r-wise Hamming distance of an arbitrary code, called the generalized Plotkin bound, and provide a class of (nonlinear) codes that achieve the bound for every r.",

author = "Lin, {Hsuan Yin} and Moser, {Stefan Michael} and Po-Ning Chen",

note = "Publisher Copyright: {\textcopyright} 2018 IEICE.; 15th International Symposium on Information Theory and Its Applications, ISITA 2018 ; Conference date: 28-10-2018 Through 31-10-2018",

year = "2019",

month = mar,

day = "8",

doi = "10.23919/ISITA.2018.8664296",

language = "English",

series = "Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "130--134",

booktitle = "Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018",

address = "美國",

}

Lin, HY, Moser, SM & Chen, P-N 2019, Connections between the Error Probability and the r-wise Hamming Distances. in Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018., 8664296, Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018, Institute of Electrical and Electronics Engineers Inc., pp. 130-134, 15th International Symposium on Information Theory and Its Applications, ISITA 2018, Singapore, Singapore, 28/10/18. https://doi.org/10.23919/ISITA.2018.8664296

Connections between the Error Probability and the r-wise Hamming Distances. / Lin, Hsuan Yin; Moser, Stefan Michael; Chen, Po-Ning.
Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018. Institute of Electrical and Electronics Engineers Inc., 2019. p. 130-134 8664296 (Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Connections between the Error Probability and the r-wise Hamming Distances

AU - Lin, Hsuan Yin

AU - Moser, Stefan Michael

AU - Chen, Po-Ning

PY - 2019/3/8

Y1 - 2019/3/8

N2 - An extension from the pairwise Hamming distance to the r-wise Hamming distance is presented. It can be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code over the binary erasure channel (BEC). By noting that good codes always have large minimum r-wise Hamming distances for all r, a new design criterion for a code is introduced: the minimum r-wise Hamming distance. We then prove an upper bound for the minimum r-wise Hamming distance of an arbitrary code, called the generalized Plotkin bound, and provide a class of (nonlinear) codes that achieve the bound for every r.

AB - An extension from the pairwise Hamming distance to the r-wise Hamming distance is presented. It can be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code over the binary erasure channel (BEC). By noting that good codes always have large minimum r-wise Hamming distances for all r, a new design criterion for a code is introduced: the minimum r-wise Hamming distance. We then prove an upper bound for the minimum r-wise Hamming distance of an arbitrary code, called the generalized Plotkin bound, and provide a class of (nonlinear) codes that achieve the bound for every r.

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

U2 - 10.23919/ISITA.2018.8664296

DO - 10.23919/ISITA.2018.8664296

M3 - Conference contribution

AN - SCOPUS:85063909445

T3 - Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018

SP - 130

EP - 134

BT - Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th International Symposium on Information Theory and Its Applications, ISITA 2018

Y2 - 28 October 2018 through 31 October 2018

ER -

Lin HY, Moser SM, Chen PN. Connections between the Error Probability and the r-wise Hamming Distances. In Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018. Institute of Electrical and Electronics Engineers Inc. 2019. p. 130-134. 8664296. (Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018). doi: 10.23919/ISITA.2018.8664296

Connections between the Error Probability and the r-wise Hamming Distances

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this