ГРАНИЦЫ СКОРОСТИ ДИЗЪЮНКТИВНЫХ КОДОВ

摘要

Двоичный код называется дизъюнктивным свободным от перекрытий (s,ℓ)-кодом, если он является матрицей инцидентности семейства множеств, для которого пересечение любых ℓ множеств не покрывается объединением s любых других множеств данного семейства. Двоичный код называется дизъюнктивным кодом со списочным декодированием силы s с объемом списка L, если он является матрицей инцидентности семейства множеств, для которого объединение любых s множеств может покрывать не более L- 1 других множеств данного семейства. При L = ℓ = 1 оба определения совпадают, и соответствующий двоичный код называется дизъюнктивным s-кодом. Цель настоящей статьи - уточнение ранее известных и получение новых границ для скоростей данных кодов. Наиболее интересным новым результатом является найденная с помощью метода случайного кодирования на ансамбле двоичных равновесных кодов нижняя граница скорости дизъюнктивных свободных от перекрытий (s,ℓ)-кодов, отношение которой к известной наилучшей верхней границе при s →∞ и любом фиксированном значении параметра ℓ≥1 сходится к пределу 2e~(-2) = 0,271… В классическом частном случае ℓ = 1 это утверждение означает, что верхняя граница скорости дизъюнктивных s-кодов, построенная в 1982 г. А.Г. Дьячко-вым и В.В. Рыковым, асимптотически достигается с точностью до постоянного множителя a, 2e~(-2)≤a≤1.