Обеспечение помехоустойчивости канала связи за счет применения метода поиска слов малого веса в линейном блочном двоичном и тернарном кодах


Авторы

Усатюк В. С.1*, Егоров С. И.2**, Ватутин Э. И.1***, Чернецкая И. Е.2****

1. Юго-Западный государственный университет, 305040 г. Курск, ул. 50 лет Октября, 94
2. Юго-Западный государственный университет, ЮЗГУ, ул. 50 лет Октября, 94, Курск, 305040, Россия

*e-mail: l@lcrypto.com
**e-mail: sie58@mail.ru
***e-mail: evatutin@rambler.ru
****e-mail: white731@yandex.ru

Аннотация

Функциональность и надежность беспилотных летательных аппаратов во многом определяется используемым каналом передачи данных. Данные, в том числе видео, должны надежно передаваться в реальном времени с большой скоростью на возможно большее расстояние. Для этого необходимо применение продвинутых систем коррекции ошибок и шифрования. В контексте разработки таких систем возникает необходимость построения помехоустойчивых кодов с заданными свойствами, важнейшим из которых является минимальное кодовое расстояние.
Для оценки минимального расстояния кода в статье предложен новый метод поиска cлов малого веса в линейном блочном двоичном, тернарном кодах на основе геометрии чисел с использованием семейства эвристик. Метод предусматривает выполнение следующих этапов: 1) вложение (Каннана) кода в решетку; 2) приведение базиса решетки; 3) ортогонализация базиса решетки методами QR-разложения; 4) поиск кратчайшего вектора в решетке по методу Каннана-Финке-Поста (КФП). Количество отличных от нуля компонент найденного вектора равняется искомому весу кодового слова, дающему оценку кодового расстояния.
Быстродействие предложенного метода поиска слов малого веса определяется быстродействием метода поиска кратчайшего вектора КФП. Быстродействие последнего значительно увеличивается с применением эвристик. В качестве эвристик использовались следующие: Гауссово отсечение веток; экстремальное отсечение веток, основанное на замене гиперсферы Гауссовой эвристики телом пересечения цилиндров; эвристики округления, основанные на сведении задачи поиска кратчайшего вектора к задаче поиска ближайшего вектора с использованием алгоритма Бабаи и эвристики плотности.
Предложенный метод имеет высокое быстродействие при решении задач приближенной оценки кодового расстояния. Этот метод на задаче поиска слова малого веса 228 продемонстрировал 3172.9 кратное ускорение по сравнению с алгоритмом Брауэра-Циммермана, реализованном в пакете MAGMA V2.22-3. Кодовое слово малого веса 212 было найдено на основе предложенного метода за 4 147 201 секунд с использованием процессора Intel 7700K 64 ГБ и видеокарты 1070 8 ГБ. Нахождение этого кодового слова позволило занять первое место в международном конкурсе поиска слов малого веса, проводимом Французским национальным центром научных исследований (CNRS), Национальным институтом исследований в области цифровых наук и технологий (Inria, Paris) и Национальным исследовательским институтом математики и информатики в Нидерландах (CWI).

Ключевые слова:

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

Библиографический список

  1. Бородин В.В., Петраков А.М., Шевцов В.А. Анализ эффективности передачи данных в сети связи группировки беспилотных летательных аппаратов // Труды МАИ. 2015. № 81. URL: https://trudymai.ru/published.php?ID=57894
  2. Ананьев А.В., Иванников К.С., Филатов С.В. Основные принципы построения систем связи на базе беспилотных летательных аппаратов // Труды МАИ. 2022. № 125. URL: https://trudymai.ru/published.php?ID=168188. DOI: 10.34759/trd-2022-125-16
  3. Титов К.Д. Принципы построения сверхширокополосного канала связи на беспилотном летательном аппарате вертолетного типа легкого класса // Труды МАИ. 2022. № 122. URL: https://trudymai.ru/published.php?ID=164250. DOI: 10.34759/trd-2022-122-12
  4. Волков А.С. Разработка имитационной модели канала с группирующимися ошибками // Труды МАИ. 2023. № 128. URL: https://trudymai.ru/published.php?ID=171396. DOI: 10.34759/trd-2023-128-12
  5. Усатюк В.С., Егоров С.И. Построение квазициклических недвоичных низкоплотностных кодов на основе совместной оценки их дистантных свойств и спектров связности // Телекоммуникации. 2016. № 8. С. 32-40.
  6. Aragon N., Lavauzelle J., Lequesne M. Low-weight codewords problem challenge, 2019. URL: https://decodingchallenge.org/low-weight
  7. Burg A., Wenk M., Zellweger M., Wegmueller M., Felber N., and Fichtner W. VLSI implementation of the sphere decoding algorithm // Proceedings of the 30th European Solid-State Circuits Conference, Leuven, Belgium, 2004, pp. 303-306.
  8. Усатюк В.С. Приложение блочного метода Коркина-Золотарева для демодуляции сигналов MIMO // Обозрение прикладной и промышленной математики. 2015. № 5 (22). С. 600-602.
  9. Dumer I., Micciancio D., and Sudan M. Hardness of approximating the minimum distance of a linear code // IEEE Transactions on Information Theory, 2003, vol. 49, no. 1, pp. 22-37. DOI: 10.1109/SFFCS.1999.814620
  10. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы: В 2-х т. Пер. с англ. – М.: Мир, 1990. Т. 2. - 367 с.
  11. Goldstein D., Mayer A. On the equidistribution of Hecke points // Forum Mathematicum, 2003, vol. 15, no 2, pp. 165–189. DOI: 10.1515/form.2003.009
  12. Korkine A., Zolotareff G. Sur les formes quadratiques // Mathematische Annalen, 1873, no. 6, pp. 366-389. DOI: 10.1007/BF01442912
  13. Lagarias J.C., Jr. Lenstra H.W., Schnorr C.P. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice // Combinatorica, 1990, vol. 10 (4), pp. 333-348. DOI: 10.1007/BF02128669
  14. Schnorr C-P, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems // Fundamentals of Computation Theory, 1991, pp. 68-85.
  15. Lenstra A., Lenstra H., Lovász L. Factoring polynomials with rational coefficients // Mathematische Annalen, 1982, vol. 261 (4), pp. 515-534. DOI: 10.1007/BF01457454
  16. Kannan R. Minkowski’s convex body theorem and integer programming // Mathematics of operations research, 1987, vol. 12 (3), pp. 415-440. DOI: 10.1287/MOOR.12.3.415
  17. Betten A., Braun M., Fripertinger H. Error-Correcting Linear Codes Classification by Isometry and Applications, Berlin, Springer-Verlag, 2006, pp. 594-596.
  18. Усатюк В.С. Определение кодового расстояния недвоичного LDPC-кода блочным методом Коркина-Золотарева // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2015. № 3 (16). С. 76-85.
  19. Ivanova V.S. Lattice Basis Reduction in Infinity, Bachelor Thesis, Technische Universitat Darmstadt, 2010, 31 p.
  20. MacKay J., Davey M. C. Evaluation of Gallager codes for short block length and high rate applications, IMA Workshop on Codes, System and Graphical Models, Springer-Verlag, 2001, pp. 113-130.
  21. Smarandashe R., Vontobel P.O. Quasi-cyclic LDPC codes: influence of proto- and Tanner-graph structure on minimum hamming distance upper bounds // IEEE Transactions on Information Theory, 2012, vol. 58, no 2, pp. 585-607. DOI: 10.1109/TIT.2011.2173244
  22. Butler B.K., Siegel P.H. Bounds on the minimum distance of punctured quasi-cyclic LDPC codes // IEEE Transactions on Information Theory, 2013, vol. 59, no 7, pp. 4584-4597. DOI: 10.1109/TIT.2013.2253152
  23. Fontein F., Schneider M., Wagner U. PotLLL: a polynomial time version of LLL with deep insertions // Designs Codes and Cryptographym, 2014, vol. 73, pp. 355–368. DOI: 10.1007/s10623-014-9918-8
  24. Yasuda M., Yamaguchi J. A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths // Designs Codes and Cryptographym, 2019, vol. 87, pp. 2489–2505. DOI: 10.1007/s10623-019-00634-9
  25. Одед Р., Миссиансио Д. Криптография на основе решеток / перевод Усатюк В.С., 2010, 78 с. URL: https://www.researchgate.net/publication/331047955
  26. Micciancio D., Walter M. Practical predictable lattice basis reduction // Annual International Conference on Theory Applications of Cryptographic Techniques, Berlin, 2016, pp. 820–849. DOI: 10.1007/978-3-662-49890-3_31
  27. Neumaier A. Bounding basis reduction properties // Designs Codes and Cryptographym, 2017, vol. 84, pp. 237-259. DOI: 10.1007/s10623-016-0273-9
  28. Yamamura K., Wang Y. Fujisaki E. Improved lattice enumeration algorithms by primal and dual reordering methods // IET Information Security, 2023, vol. 17 (1), pp. 35-45. DOI: 10.1049/ise2.12083
  29. Schnorr C.P. Fast Factoring  Integers by SVP Algorithms // Cryptology ePrint Archive, Paper 2021/933. URL: https://eprint.iacr.org/2021/933
  30. McGuire Gary, Robinson Oisin. A New Angle on Lattice Sieving for the Number Field Sieve, 2020. URL: https://arxiv.org/pdf/2001.10860
  31. Gabrielle de Micheli, Pierrick Gaudry, Cécile Pierrot. Lattice Enumeration for Tower NFS: a 521- bit Discrete Logarithm Computation // 27th Annual International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2021, pp.67-96. DOI: 10.1007/978-3-030-92062-3_3
  32. Robinson O. An Implementation of the Extended Tower Number Field Sieve using 4d Sieving in a Box and a Record Computation in Fp4, 2022. URL: https://arxiv.org/abs/2212.04999
  33. Schnorr C.P., Hörner H.H. Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction // Advances in Cryptology, LNCS, 1995, vol. 921, pp 1-12. DOI: 10.1007/3-540-49264-X_1
  34. Gamma N., Nguyen P. Q., Regev O. Lattice Enumeration Using Extreme Pruning // Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology – EUROCRYPT, 2010, pp. 257–278. DOI: 10.1007/978-3-642-13190-5_13
  35. Babai L. On lovasz lattice reduction and the nearest lattice point problem // Combinatorica, 1986, vol. 6, pp. 1-13. DOI: 10.1007/BF02579403
  36. Micciancio D. The shortest vector problem is NP-hard to approximate to within some constant // SIAM Journal on Computing, 2001, no. 30, pp. 2008-2035. DOI: 10.1137/S0097539700373039
  37. Усатюк В.С. Вероятностный метод определения кодового расстояния линейного блочного кода // Proceedings of the III International conference "Engineering&Telecommunication - En&T 2016", Moscow, MIPT, 2016, pp. 43-46.
  38. Кузьмин О.В., Усатюк В.С. Параллельные алгоритмы вычисления локальных минимумов целочисленных решеток // Программные продукты и системы. 2015. № 1 (109). С. 55-62.
  39. Усатюк В.С. Реализация параллельных алгоритмов ортогонализации в задаче поиска кратчайшего базиса целочисленной решетки // Прикладная дискретная математика. Приложение. 2012. № 5. С. 120-122.
  40. Усатюк В.С., Егоров С.И. Устройство для оценки кодового расстояния линейного блочного кода методом геометрии чисел // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2017. № 4 (25), С. 24-33.
  41. Bosma W., Cannon J.J., Fieker C., Steel A. Handbook of Magma functions, 2019, 6129 p.
  42. Hernando F., Igual F. D., Quintana-Orti G. Algorithm 994: Fast Implementations of the Brouwer-Zimmermann Algorithm for the Computation of the Minimum Distance of a Random Linear Code // ACM Transactions on Mathematical Software, 2019, vol. 45, no. 2, pp. 1-28. DOI: 10.1145/3302389
  43. Support material for Low weight codewords problem search method. URL: https://github.com/Lcrypto/Low-weight_Codeword_Problem V2.22-3


Скачать статью

mai.ru — информационный портал Московского авиационного института

© МАИ, 2000—2024

 Вход