Weak Superimposed Codes of Improved Asymptotic Rate and Their Randomized Construction
Weak Superimposed Codes of Improved Asymptotic Rate and Their Randomized Construction
复制标题
改进渐近率的弱叠加码及其随机构造
DOI：
10.1109/isit50566.2022.9834680
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Y. Tsunoda and Y. Fujiwara
中科院分区：
文献类型：
--
作者：
窪田友樹;藤田英二;久保誠吾;小濱剛;楠正暢;竹島伸生;柏原賢二;飯塚勝美;Y. Tsunoda and Y. Fujiwara
弱叠加码是一种与广义无覆盖族、叠加码和析取矩阵密切相关的组合结构，它们只需要满足相似但不那么严格的条件。这类代码也可以被视为组合数学中所知的局部瘦族的更严格的变体。最初，在防止非法分发副本的多媒体内容保护的环境中引入了弱叠加代码，假设恶意用户的联盟可能采用带有对抗性噪声的平均攻击。正如信息论中的许多其他类型的码一样，在弱重叠码的研究中，寻找渐近状态下的最高可达速率并给出一种有效的构造以产生实现它的无限序列是很有意义和重要的。在这里，我们证明了最优弱叠加码码率的一个比已知的最强下界更紧的下界，并给出了一个多项式时间的随机构造算法，它以很高的概率渐近地达到我们的改进界。我们的概率方法是通用的，并适用于许多其他相关的代码和数组。
Weak superimposed codes are combinatorial structures related closely to generalized cover-free families, superimposed codes, and disjunct matrices in that they are only required to satisfy similar but less stringent conditions. This class of codes may also be seen as a stricter variant of what are known as locally thin families in combinatorics. Originally, weak superimposed codes were introduced in the context of multimedia content protection against illegal distribution of copies under the assumption that a coalition of malicious users may employ the averaging attack with adversarial noise. As in many other kinds of codes in information theory, it is of interest and importance in the study of weak superimposed codes to find the highest achievable rate in the asymptotic regime and give an efficient construction that produces an infinite sequence of codes that achieve it. Here, we prove a tighter lower bound than the sharpest known one on the rate of optimal weak superimposed codes and give a polynomial-time randomized construction algorithm for codes that asymptotically attain our improved bound with high probability. Our probabilistic approach is versatile and applicable to many other related codes and arrays.
新的选择器和局部精简系列，适用于支持同时传输的多路访问通道
影响因子：
1.1
作者：
Annalisa De Bonis
通讯作者：
Annalisa De Bonis