О построении самодополнительных кодов и их приложении в задаче сокрытия информации

Линейные коды широко применяются для защиты от ошибок в системах передачи и хранения данных, обеспечения стойкости различных криптографических алгоритмов и протоколов, для защиты скрытой информации от ошибок в стегоконтейнере. Одним из классов кодов, находящих применение в ряде перечисленных областей, является класс линейных самодополнительных кодов над бинарным полем. Такие коды содержат вектор из всех единиц, а их нумератор весов является симметрическим многочленом. В прикладных задачах от самодополнительных [n, k]-кодов часто требуется при заданной длине n и размерности k иметь максимально возможное кодовое расстояние d(k, n). Для n < 13 значения d(k, n) уже известны. В настоящей работе для самодополнительных кодов длины n=13, 14, 15 ставится задача нахождения нижних оценок на d(k, n), а также нахождение самих значений d(k, n). Разработка эффективного способа получения нижней оценки, близкой к d(k, n), является актуальной задачей, так как нахождение самих значений d(k, n) в общем случае является трудной задачей. В работе предложены четыре способа нахождения нижних оценок: на основе циклических кодов, на основе остаточных кодов, на основе (u|u + v)-конструкции и на основе тензорного произведения кодов. На совместном использовании этих способов для рассмотренных длин удалось получить эффективным образом нижние оценки, либо совпадающие с найденными значениями d(k, n), либо отличающиеся на единицу. В работе предложена последовательность проверок, которая в ряде случаев помогает доказать отсутствие самодополнительного [n, k]-кода с кодовым расстоянием d. В заключительной части работы на основе самодополнительных кодов предлагается конструкция для сокрытия информации, устойчивая к помехам в стегоконтейнере. Приведенные расчеты показывают большую эффективность новой конструкции по сравнению с известными конструкциями.

1. D. Jungnickel and V. D. Tonchev, “The classification of antipodal two-weight linear codes”, Finite Fields and Their Applications, vol. 50, pp. 372-381, 2018. doi: https://doi.org/10.1016/j.ffa.2017.12.010.

2. T. Klove and S. Yari, “Proper self-complementary codes”, in Proceedings of the 2010 International Symposium On Information Theory & Its Applications, 2010, pp. 118-122. doi: 10. 1109 / ISITA. 2010. 5649432.

3. E. M. Gabidulin and M. Bossert, “Codes Resistant to the Phase Rotation”, in Proceedings of the 4-th Simposium on Communication and Applications, 1997, pp. 65-84.

4. Y. V. Kosolapov and F. S. Pevnev, “Error-tolerant ZZW-construction”, Siberian Electronic Mathematical Reports, vol. 18, no. 2, pp. 1506-1516, 2021.

5. L. D. Grey, “Some bounds for error-correcting codes”, IRE Transactions on Information Theory, vol. 8, no. 3, pp. 200-202, 1962.

6. G. McGuire, “Qyasi-Symmetric Designs and Codes Meeting the Grey-Rankin Bound”, Journal of Combinatorial Theory, Series A, vol. 78, no. 2, pp. 280-291, 1997. doi: https : / /doi.org / 10. 1006 /jcta. 1997.2765.

7. I. Bouyukliev, S. Bouyuklieva, and S. Dodunekov, “On binary self-complementary [120, 9, 56] codes having an automorphism of order 3 and associated SDP designs”, Problems of Information Transmission, vol. 43, pp. 89-96, 2007. doi: https://doi.org/10.1134/S0032946007010020.

8. S. Dodunekov, S. Encheva, and S. Kapralov, “On the [28, 7, 12] binary self-complementary codes and their residuals”, Designs, Codes and Cryptography, vol. 4, pp. 57-67, 1994. doi: https://doi.org/10.1007/BF01388560.

9. I. Asemota, Binary Self-Complementary Codes. B. Sc., Benson Idahosa University, Nigeri, 2016.

10. R. H. Morelos-Zaragoza, The Art of Error Correcting Coding, 2nd Edition. Wiley, 2006.

11. R. Hill and D. Newton, “Optimal ternary linear codes”, in, vol. 2, 1992, pp. 137-157. doi: https://doi.org/10.1007/BF00124893.

12. M. Tomlinson, C. J. Tjhai, M. A. Ambroze, M. Ahmed, and M. Jibril, Error-Correction Coding and Decoding: Bounds, Codes, Decoders, Analysis and Applications. Springer Nature, 2017.

13. V. M. Deundyak, A. E. Maevskij, and M. N. C., Metody pomekhoustojchivoj zashchity dannyh. Rostov-na-Donu: Izdatelstvo yuzhnogo federalnogo universiteta, 2014, in Russian.

14. D. B. Jaffe, Binary Linear Codes: New Results on Nonexistence, 1996. [Online]. Available: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.628&rep=rep1&type=pdf.