On the Combinatorial Version of the Slepian-Wolf Problemстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 26 декабря 2018 г.
Аннотация:Аннотация: Мы изучаем следующий комбинаторный вариант схемы кодирования Вольфа и Слепяна. Мы предполагаем, что два отправителя имеют в своем распоряжении двоичные слова X и Y соответственно; длина каждого слова равна n, а расстояние Хэмминга между ними не более $\alpha n$. Отправители сжимают свои слова и пересылают результаты Получателю. Затем Получатель должен восстановить оба слова X и Y. Цель состоит в том, чтобы минимизировать длину передаваемых сообщений. Для асимметричного варианта этой задачи (когда один из Отправителей передает Получателю cвоё слово без сжатия) с детерминированным кодированием Орлицкий и Вишванатани нашли нетривиальную нижнюю оценку. В этой статье мы доказываем новую нижнюю оценку для схем с так называемым синдромным кодированием, в котором хотя бы один из Отправителей использует линейное кодирование входной строки. Для комбинаторной задачи Вольфа--Слепяна с рандомизированным кодированием теоретический оптимум коммуникационной сложности был известен ранее, однако эффективные протоколы с оптимальной длиной сообщений оставались неизвестными. Мы закрываем этот пробел и представляем рандомизированный коммуникационный протокол с полиомиальным временем кодирования и декодиования, который обеспечивает оптимальную коммуникационную сложность.