Small stopping sets in Steiner triple systems
Small stopping sets in Steiner triple systems
复制标题
DOI：
10.1007/s12095-008-0002-y
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
C. Colbourn;Yuichiro Fujiwara
中科院分区：
文献类型：
--
作者：
C. Colbourn;Yuichiro Fujiwara
低密度奇偶校验（LDPC）码中最小停止集的大小在一定程度上决定了二进制擦除信道上迭代解码方法的性能。在由块设计产生的LDPC代码中，停止集是其块的子集，具有属于所选块之一的每个点至少属于其中两个块的特性。虽然某些斯坦纳三系统没有大小为5或更小的停止集，但证明了每个斯坦纳三系统都有大小不超过7的停止集。这个证明可以看作是多项式恒等式在构形计数中的应用，它推广了已知的线性恒等式族。虽然没有已知的最小停止集为7的Steiner三重系统的例子，但证明了具有c·v1.8三元组的部分Steiner三重系统不存在大小小于7的停止集。
The size of the smallest stopping set in a low-density parity check (LDPC) code determines, to an extent, the performance of iterative decoding methods over the binary erasure channel. In an LDPC code arising from a block design, a stopping set is a subset of its blocks with the property that every point belonging to one of the selected blocks belongs to at least two of them. While some Steiner triple systems have no stopping sets of size 5 or less, it is shown that every Steiner triple system has a stopping set of size at most 7. The proof can be viewed as an application of polynomial identities among configuration counts that generalize the family of known linear identities. While no example of a Steiner triple system whose smallest stopping set has size seven is known, it is shown that a partial Steiner triple system onvpoints withc·v1.8triples that has no stopping set of size less than 7 exists.