Stopping and trapping sets in generalized covering arrays

Olgica Milenkovie; Emina Soljanin; Philip Whiting

doi:10.1109/CISS.2006.286475

Stopping and trapping sets in generalized covering arrays

Olgica Milenkovie^*, Emina Soljanin, Philip Whiting

^*Corresponding author for this work

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

6 Citations (Scopus)

Abstract

Certain combinatorial structures embedded in the parity-check matrix of linear codes, such as stopping and trapping sets, are known to govern the behavior of the codes' bit error rate curves under iterative decoding. We show how the Lovász Local Lemma can be used to obtain ε-probability bounds on the frequency of occurrence of such structures. In particular, the results are developed for two random ensembles of arrays. Arrays in the first ensemble consist of i.i.d. Bernoulli random variables, while the rows of the arrays in the second ensemble are chosen uniformly at random from the set of codewords of a linear block-code.

Original language	English
Title of host publication	2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	259-264
Number of pages	6
ISBN (Print)	1424403502, 9781424403509
DOIs	https://doi.org/10.1109/CISS.2006.286475
Publication status	Published - 2007
Externally published	Yes
Event	2006 40th Annual Conference on Information Sciences and Systems, CISS 2006 - Princeton, NJ, United States Duration: 22 Mar 2006 → 24 Mar 2006

Other

Other	2006 40th Annual Conference on Information Sciences and Systems, CISS 2006
Country/Territory	United States
City	Princeton, NJ
Period	22/03/06 → 24/03/06

Access to Document

10.1109/CISS.2006.286475

Cite this

@inproceedings{c137116bac154ca4b4c3cf5ca1d0136b,

title = "Stopping and trapping sets in generalized covering arrays",

abstract = "Certain combinatorial structures embedded in the parity-check matrix of linear codes, such as stopping and trapping sets, are known to govern the behavior of the codes' bit error rate curves under iterative decoding. We show how the Lov{\'a}sz Local Lemma can be used to obtain ε-probability bounds on the frequency of occurrence of such structures. In particular, the results are developed for two random ensembles of arrays. Arrays in the first ensemble consist of i.i.d. Bernoulli random variables, while the rows of the arrays in the second ensemble are chosen uniformly at random from the set of codewords of a linear block-code.",

author = "Olgica Milenkovie and Emina Soljanin and Philip Whiting",

year = "2007",

doi = "10.1109/CISS.2006.286475",

language = "English",

isbn = "1424403502",

pages = "259--264",

booktitle = "2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "2006 40th Annual Conference on Information Sciences and Systems, CISS 2006 ; Conference date: 22-03-2006 Through 24-03-2006",

}

Milenkovie, O, Soljanin, E & Whiting, P 2007, Stopping and trapping sets in generalized covering arrays. in 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings., 4067816, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 259-264, 2006 40th Annual Conference on Information Sciences and Systems, CISS 2006, Princeton, NJ, United States, 22/03/06. https://doi.org/10.1109/CISS.2006.286475

Stopping and trapping sets in generalized covering arrays. / Milenkovie, Olgica; Soljanin, Emina; Whiting, Philip.
2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings. Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE), 2007. p. 259-264 4067816.

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

TY - GEN

T1 - Stopping and trapping sets in generalized covering arrays

AU - Milenkovie, Olgica

AU - Soljanin, Emina

AU - Whiting, Philip

PY - 2007

Y1 - 2007

N2 - Certain combinatorial structures embedded in the parity-check matrix of linear codes, such as stopping and trapping sets, are known to govern the behavior of the codes' bit error rate curves under iterative decoding. We show how the Lovász Local Lemma can be used to obtain ε-probability bounds on the frequency of occurrence of such structures. In particular, the results are developed for two random ensembles of arrays. Arrays in the first ensemble consist of i.i.d. Bernoulli random variables, while the rows of the arrays in the second ensemble are chosen uniformly at random from the set of codewords of a linear block-code.

AB - Certain combinatorial structures embedded in the parity-check matrix of linear codes, such as stopping and trapping sets, are known to govern the behavior of the codes' bit error rate curves under iterative decoding. We show how the Lovász Local Lemma can be used to obtain ε-probability bounds on the frequency of occurrence of such structures. In particular, the results are developed for two random ensembles of arrays. Arrays in the first ensemble consist of i.i.d. Bernoulli random variables, while the rows of the arrays in the second ensemble are chosen uniformly at random from the set of codewords of a linear block-code.

UR - https://www.scopus.com/pages/publications/44049105099

U2 - 10.1109/CISS.2006.286475

DO - 10.1109/CISS.2006.286475

M3 - Conference proceeding contribution

SN - 1424403502

SN - 9781424403509

SP - 259

EP - 264

BT - 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

T2 - 2006 40th Annual Conference on Information Sciences and Systems, CISS 2006

Y2 - 22 March 2006 through 24 March 2006

ER -

Stopping and trapping sets in generalized covering arrays

Abstract

Other

Access to Document

Other files and links

Fingerprint

Cite this