Универсальные коды в модели общих случайных бит для каналов с обобщёнными способностями искажения

Концепция универсальных кодов была недавно введена в статье `Universal codes in the shared-randomness model for channels with general distortion capabilities' [1], авторами которой являются B. Bauwens и M. Zimand. Универсальные коды расширяют идею кодов с исправлением ошибок, рассматривая каналы более общего вида, чем каналы, меняющие не более, чем заданное количество бит сообщения. В этой работе исследуется задача универсального кодирования в \textit{слабом сценарии} \textit{(oblivious scenario)}, которая также описана в [1]. В данной постановке задачи универсальный код имеет несколько параметров, таких как число передаваемых сообщений, длина кода и общая случайность (или, эквивалентно, число общих случайных бит кодирующей и декодирующей функций, равное логарифму общей случайности), в то время как способность канала искажать сообщения определяется одним параметром ——- размером канала. Возникает естественная задача выбора оптимальных параметров кода в зависимости от размера канала. В статье [1] доказывается нижняя оценка на число общих случайных бит в терминах размера канала, но она не учитывает длину кода. Поэтому всё ещё актуальным является вопрос о том, как устроена точная зависимость между оптимальными параметрами универсального кода при фиксированном размере канала. В данной работе изучается этот вопрос для случая с двумя передаваемыми сообщениями, в ходе чего находится точная зависимость между оптимальными параметрами кода при условии, что длина кода не меньше общей случайности. Кроме того, описывается возможный подход к определению точной зависимости в случае, когда длина кода строго меньше общей случайности, а также доказывается нижняя оценка на длину кода в этом случае. Ключевые слова: универсальный код, слабый сценарий, длина кода, общая случайность, размер канала, точная зависимость.