Stopping and Trapping Sets in Generalized Covering Arrays
Olgica Milenković, Emina Soljanin, Philip Whiting · 2006
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 Lovasz local lemma can be used to obtain epsiv-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.