Границы скорости дизъюнктивных кодов

Двоичный код называется дизъюнктивным свободным от перекрытий $(s,\ell)$-кодом, если он является матрицей инцидентности семейства множеств, для которого пересечение любых $\ell$ множеств не покрывается объединением $s$ любых других множеств данного семейства. Двоичный код называется дизъюнктивным кодом со списочным декодированием силы $s$ с объемом списка $L$, если он является матрицей инцидентности семейства множеств, для которого объединение любых $s$ множеств может покрывать не более $L-1$ других множеств данного семейства. При $L=\ell=1$ оба определения совпадают, и соответствующий двоичный код называется дизъюнктивным $s$-кодом. Цель настоящей статьи – уточнение ранее известных и получение новых границ для скоростей данных кодов. Наиболее интересным новым результатом является найденная с помощью метода случайного кодирования на ансамбле двоичных равновесных кодов нижняя граница скорости дизъюнктивных свободных от перекрытий $(s,\ell)$-кодов, отношение которой к известной наилучшей верхней границе при $s\to\infty$ и любом фиксированном значении параметра $\ell\ge1$ сходится к пределу $2e^{-2}=0{,}271\dots$ В классическом частном случае $\ell=1$ это утверждение означает, что верхняя граница скорости дизъюнктивных $s$-кодов, построенная в 1982 г. А. Г. Дьячковым и В. В. Рыковым, асимптотически достигается с точностью до постоянного множителя $a$, $2e^{-2}\le a\le1$.