НОВЫЕ НИЖНИЕ ГРАНИЦЫ СКОРОСТЕЙ ЛОКАЛЬНО ТОНКИХ СЕМЕЙСТВ И СЛАБЫХ ДИЗЪЮНКТИВНЫХ КОДОВ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Исследуются локально тонкие семейства множеств и слабые дизъюнктивные коды. Основным результатом является получение новых нижних границ скоростей исследуемых конструкций с использованием вероятностных методов. Дополнительно представлены новые нижние границы скорости мультимедийных кодов, определяющих коалицию при атаке усреднения и шуме, вытекающие из полученных оценок скорости слабых дизъюнктивных кодов.

Об авторах

Д. Ю Гошкодер

Сколковский институт науки и технологий

Email: danilgoshkoder@mail.ru
Москва

Список литературы

  1. Kautz W., Singleton R. Nonrandom Binary Superimposed Codes // IEEE Trans. Inform. Theory. 1964. V. 10. № 4. P. 363–377. https://doi.org/10.1109/TIT.1964.1053689
  2. Friedman A.D., Graham R.L., Ullman J.D. Universal Single Transition Time Asynchronous State Assignments // IEEE Trans. Comput. 1969. V. 18. № 6. P. 541–547. https://doi.org/10.1109/T-C.1969.222707
  3. Сагалович Ю.Л. Метод повышения надежности конечного автомата // Пробл. передачи информ. 1965. Т. 1. № 2. С. 27–35. http://mi.mathnet.ru/ppi734
  4. Erd˝os P., Rado R. Intersection Theorems for Systems of Sets // J. London Math. Soc. 1960. V. 35. № 2. P. 85–90. https://doi.org/10.1112/jlms/s1-35.1.85
  5. Alon N., K¨orner J., Monti A. String Quartets in Binary // Combin. Probab. Comput. 2000. V. 9. № 5. P. 381–390. https://doi.org/10.1017/S0963548300004375
  6. Егорова Е.Е., Фернандес М., Кабатянский Г.А., Мяо И. Существование и конструкции мультимедийных кодов, способных находить полную коалицию при атаке усреднения и шуме // Пробл. передачи информ. 2020. Т. 56. № 4. С. 97–108. https://doi.org/10.31857/S0555292320040087
  7. Fachini E., K¨orner J., Monti A. A Better Bound for Locally Thin Set Families // J. Combin. Theory Ser. A. 2001. V. 95. № 2. P. 209–218. https://doi.org/10.1006/jcta.2000.3162
  8. Alon N., Fachini E., K¨orner J. Locally Thin Set Families // Combin. Probab. Comput. 2000. V. 9. № 6. P. 481–488. https://doi.org/10.1017/S0963548300004521
  9. F¨uredi Z. 2-Cancellative Hypergraphs and Codes // Combin. Probab. Comput. 2012. V. 21. № 1–2. P. 159–177. https://doi.org/10.1017/S0963548311000563
  10. Fachini E., K¨orner J., Monti A. Self-Similarity Bounds for Locally Thin Set Families // Combin. Probab. Comput. 2001. V. 10. № 4. P. 309–315. https://doi.org/10.1017/S0963548301004667
  11. Qian B., Wang X., Ge G. Improved Lower Bounds for Strongly Separable Matrices and Related Combinatorial Structures // IEEE Trans. Inform. Theory. 2023. V. 69. № 5. P. 2801–2807. https://doi.org/10.1109/TIT.2022.3233395
  12. Tsunoda Y., Fujiwara Y. Weak Superimposed Codes of Improved Asymptotic Rate and Their Randomized Construction // Proc. 2022 IEEE Int. Symp. on Information Theory (ISIT’2022). Espoo, Finland. June 26, 2022 – July 1, 2022. P. 784–789. https://doi.org/10.1109/ISIT50566.2022.9834680
  13. Vorobyev I. Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate // Des. Codes Cryptogr. 2023. V. 4. № 4. P. 1183–1191. https://doi.org/10.1007/s10623-022-01144-x
  14. De Bonis A. Generalized Selectors and Locally Thin Families with Applications to Conflict Resolution in Multiple Access Channels Supporting Simultaneous Successful Transmissions // Proc. 20th Int. Conf. on Principles of Distributed Systems (OPODIS 2016).
  15. Leibniz Int. Proc. in Informatics (LIPIcs). V. 70. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik, 2017. P. 22:1–22:16. https://doi.org/10.4230/LIPIcs.OPODIS.2016.22
  16. De Bonis A. New Selectors and Locally Thin Families with Applications to Multi-Access Channels Supporting Simultaneous Transmissions // Theoret. Comput. Sci. 2019. V. 796. P. 34–50. https://doi.org/10.1016/j.tcs.2019.08.020
  17. D’yachkov A.G., Rykov V.V., Rashad A.M. Superimposed Distance Codes // Probl. Control Inform. Theory. 1989. V. 18. № 4. P. 237–250.
  18. Goshkoder D.Yu. Probabilistic Methods for Deriving New Lower Bounds on the Rates of Locally Thin Families and Weak Disjunctive Codes // Probl. Inf. Transm. 2025. V. 61. № 2 (to appear).
  19. Deuber W.A., Erd˝os P., Gunderson D.S., Kostochka A.V., Meyer A.G. Intersection Statements for Systems of Sets // J. Combin. Theory Ser. A. 1997. V. 79. № 1. P. 118–132. https://doi.org/10.1006/jcta.1997.2778

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025