Коды для точного нахождения носителя разреженного вектора по ошибочным линейным измерениям и их декодирование

Обложка

Цитировать

Полный текст

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

Аннотация

Построены коды, позволяющие точно находить носитель неизвестного разреженного вектора, у которого модули всех ненулевых координат примерно равны, по результатам линейных измерений в присутствии шума с ограниченной сверху ℓp-нормой. Предложен алгоритм декодирования, имеющий асимптотически минимальную сложность.

Об авторах

Марсель Фернандес

Политехнический университет Каталонии

Email: marcelf@entel.upc.edu
Барселона, Испания

Григорий Анатольевич Кабатянский

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

Email: g.kabatyansky@skoltech.ru
Москва, Россия

Станислав Александрович Круглик

Наньянский технологический университет

Email: stanislav.kruglik@ntu.edu.sg
Сингапур

Ин Мяо

Университет Цукубы

Email: miao@sk.tsukuba.ac.jp
Цукуба, префектура Ибараки, Япония

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

  1. Egorova E., Fernandez M., Kabatiansky G., Lee M.H. Signature Codes for Weighted Noisy Adder Channel, Multimedia Fingerprinting and Compressed Sensing // Des. Codes Cryptogr. 2019. V. 87. № 2-3. P. 455-462. https://doi.org/10.1007/s10623-018-0551-9
  2. Егорова Е.Е., Фернандес М., Кабатянский Г.А., Мяо И. Существование и конструкции мультимедийных кодов, способных находить полную коалицию при атаке усреднения и шуме // Пробл. передачи информ. 2020. Т. 56. № 4. С. 97-108. https://doi.org/10.31857/S0555292320040087
  3. Fan J., Gu Y., Hachimori M., Miao Y. Signature Codes for Weighted Binary Adder Channel and Multimedia Fingerprinting // IEEE Trans. Inform. Theory. 2021. V. 67. № 1. P. 200-216. https://doi.org/10.1109/TIT.2020.3033445
  4. Егорова Е.Е., Кабатянский Г.А. Разделимые коды для защиты мультимедиа от нелегального копирования коалициями // Пробл. передачи информ. 2021. Т. 57. № 2. С. 90-111. https://doi.org/10.31857/S0555292321020066
  5. Джанабекова А., Кабатянский Г.А., Камель И., Рабие Т.Ф. Неперекрывающиеся выпуклые многогранники с вершинами из булева куба и другие задачи теории кодирования // Пробл. передачи информ. 2022. Т. 58. № 4. С. 50-61. https://www.mathnet.ru/rus/ppi2383
  6. Fernandez M., Kabatiansky G., Miao Y. A Novel Support Recovery Algorithms and Its Applications to Multiple-Access Channels // Proc. 2022 IEEE Int. Multi-Conf. on Engineering, Computer and Information Sciences (SIBIRCON). Yekaterinburg, Russian Federation. Nov. 11-13, 2022. P. 170-173. https://doi.org/10.1109/SIBIRCON56155.2022.10017094
  7. Polyanskiy Y. A Perspective on Massive Random-Access // Proc. 2017 IEEE Int. Symp. on Information Theory (ISIT'2017). Aachen, Germany. June 25-30, 2017. P. 2523-2527. https://doi.org/10.1109/ISIT.2017.8006984
  8. Donoho D.L.Compressed Sensing // IEEE Trans. Inform. Theory. 2006. V. 52. № 4. P. 1289-1306. https://doi.org/10.1109/TIT.2006.871582
  9. Candès E.J., Tao T. Near-Optimal Signal Recovery from Random Projections: Universal Encoding Strategies? // IEEE Trans. Inform. Theory. 2006. V. 52. № 12. P. 5406-5425. https://doi.org/10.1109/TIT.2006.885507
  10. Gkagkos M., Pradhan A.K., Amalladinne V., Narayanan K., Chamberland J-F., Georghiades C.N. Approximate Support Recovery Using Codes for Unsourced Multiple Access // Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT'2021). Melbourne, Australia. July 12-20, 2021. P. 2948-2953. https://doi.org/10.1109/ISIT45174.2021.9517995
  11. Wen J., Zhou Z., Wang J., Tang X., Mo Q. A Sharp Condition for Exact Support Recovery with Orthogonal Matching Pursuit // IEEE Trans. Signal Process. 2017. V. 65. № 6. P. 1370-1382. https://doi.org/10.1109/TSP.2016.2634550
  12. Mehrabi M., Tchamkerten A. Error-Correction for Sparse Support Recovery Algorithms // Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT'2021). Melbourne, Australia. July 12-20, 2021. P. 1754-1759. https://doi.org/10.1109/ISIT45174.2021.9518027
  13. Ericson T., Levenshtein V.I. Superimposed Codes in the Hamming Space // IEEE Trans. Inform. Theory. 1994. V. 40. № 6. P. 1882-1893. https://doi.org/10.1109/18.340463
  14. Влэдуц С.Г., Кабатянский Г.А., Ломаков В.В. Об исправлении ошибок при искажениях в канале и синдроме // Пробл. передачи информ. 2015. Т. 51. № 2. С. 50-56. http://mi.mathnet.ru/ppi2169
  15. Sipser M., Spielman D.A. Expander Codes // IEEE Trans. Inform. Theory. 1996. V. 42. № 6. Part 1. P. 1710-1722. https://doi.org/10.1109/18.556667
  16. Spielman D. Linear-Time Encodable and Decodable Error-Correcting Codes // IEEE Trans. Inform. Theory. 1996. V. 42. № 6. P. 1723-1731. https://doi.org/10.1109/18.556668
  17. 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

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

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

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