RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Пробл. передачи информ., 2014, том 50, выпуск 1, страницы 31–63 (Mi ppi2131)  

Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)

Теория кодирования

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

А. Г. Дьячков, И. В. Воробьев, Н. А. Полянский, В. Ю. Щукин

Московский государственный университет им. М. В. Ломоносова, механико-математический факультет, кафедра теории вероятностей

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

Полный текст: PDF файл (393 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Problems of Information Transmission, 2014, 50:1, 27–56

Реферативные базы данных:

Тип публикации: Статья
УДК: 621.391.15
Поступила в редакцию: 15.04.2013
После переработки: 09.01.2014

Образец цитирования: А. Г. Дьячков, И. В. Воробьев, Н. А. Полянский, В. Ю. Щукин, “Границы скорости дизъюнктивных кодов”, Пробл. передачи информ., 50:1 (2014), 31–63; Problems Inform. Transmission, 50:1 (2014), 27–56

Цитирование в формате AMSBIB
\RBibitem{DyaVorPol14}
\by А.~Г.~Дьячков, И.~В.~Воробьев, Н.~А.~Полянский, В.~Ю.~Щукин
\paper Границы скорости дизъюнктивных кодов
\jour Пробл. передачи информ.
\yr 2014
\vol 50
\issue 1
\pages 31--63
\mathnet{http://mi.mathnet.ru/ppi2131}
\transl
\jour Problems Inform. Transmission
\yr 2014
\vol 50
\issue 1
\pages 27--56
\crossref{https://doi.org/10.1134/S0032946014010037}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000334517000003}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84899519079}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ppi2131
  • http://mi.mathnet.ru/rus/ppi/v50/i1/p31

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Исправления
    • Письмо в редакцию
      А. Г. Дьячков, И. В. Воробьев, Н. А. Полянский, В. Ю. Щукин
      Пробл. передачи информ., 2016, 52:2, 111


    Эта публикация цитируется в следующих статьяx:
    1. А. Г. Дьячков, И. В. Воробьев, Н. А. Полянский, В. Ю. Щукин, “Почти дизъюнктивные коды со списочным декодированием”, Пробл. передачи информ., 51:2 (2015), 27–49  mathnet; A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, V. Yu. Shchukin, “Almost disjunctive list-decoding codes”, Problems Inform. Transmission, 51:2 (2015), 110–131  crossref  isi  elib
    2. Н. А. Полянский, “Почти свободные от перекрытий коды”, Пробл. передачи информ., 52:2 (2016), 46–60  mathnet  mathscinet  elib; N. A. Polyansky, “Almost cover-free codes”, Problems Inform. Transmission, 52:2 (2016), 142–155  crossref  isi  elib
    3. В. Ю. Щукин, “Списочное декодирование для гиперканала множественного доступа”, Пробл. передачи информ., 52:4 (2016), 14–30  mathnet; V. Yu. Shchukin, “List decoding for a multiple access hyperchannel”, Problems Inform. Transmission, 52:4 (2016), 329–343  crossref  isi  elib
    4. И. В. Воробьев, “Границы скоростей разделяющих кодов”, Пробл. передачи информ., 53:1 (2017), 34–46  mathnet  elib; I. V. Vorob'ev, “Bounds on the rate of separating codes”, Problems Inform. Transmission, 53:1 (2017), 30–41  crossref  isi
    5. N. H. Bshouty, A. Gabizon, “Almost Optimal Cover-Free Families”, Algorithms and Complexity, CIAC 2017, Lecture Notes in Computer Science, 10236, eds. D. Fotakis, A. Pagourtzis, V. Paschos, Springer International Publishing Ag, 2017, 140–151  crossref  mathscinet  zmath  isi  scopus
    6. A. De Bonis, U. Vaccaro, “A New Kind of Selectors and Their Applications to Conflict Resolution in Wireless Multichannels Networks”, Algorithms For Sensor Systems, ALGOSENSORS 2016, Lecture Notes in Computer Science, 10050, eds. M. Chrobak, A. Anta, L. Gasieniec, R. Klasing, Springer International Publishing Ag, 2017, 45–61  crossref  isi  scopus
    7. M. Aldridge, L. Baldassini, K. Gunderson, “Almost Separable Matrices”, J. Comb. Optim., 33:1 (2017), 215–236  crossref  mathscinet  zmath  isi  scopus
    8. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Cover-Free Codes and Separating System Codes”, Designs Codes Cryptogr., 82:1-2, SI (2017), 197–209  crossref  mathscinet  zmath  isi  scopus
    9. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Symmetric Disjunctive List-Decoding Codes”, Designs Codes Cryptogr., 82:1-2, SI (2017), 211–229  crossref  mathscinet  zmath  isi  scopus
    10. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Almost Cover-Free Codes and Designs”, Designs Codes Cryptogr., 82:1-2, SI (2017), 231–247  crossref  mathscinet  zmath  isi  scopus
    11. N. H. Bshouty, “Exact learning from an honest teacher that answers membership queries”, Theor. Comput. Sci., 733:SI (2018), 4–43  crossref  mathscinet  zmath  isi  scopus
    12. A. D'yachkov, N. Polyanskii, V. Shchukin, I. Vorobyev, “Separable codes for the symmetric multiple-access channel”, 2018 IEEE International Symposium on Information Theory (ISIT), IEEE, 2018, 291–295  crossref  isi
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:379
    Полный текст:53
    Литература:35
    Первая стр.:24
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020