ПОСТРОЕНИЕ АЛГОРИТМОВ НА ОСНОВЕ КОДОВ РИДА СОЛОМОНА ДЛЯ КОРРЕКЦИИ ОШИБОК В ДВУХМЕРНЫХ МАССИВАХ ЦИФРОВЫХ ДАННЫХ

Гарнышев И.Н., Казанцев С.В., Мальков Р.Ю., Семенов И.Д., Юдин С.В.

Email: Garnyshev672@scientifictext.ru

Гарнышев Игорь Николаевич - сетевой инженер,

Отдел администрирования сетей передачи данных,

Тинькофф Банк;

Казанцев Сергей Владимирович - главный инженер,

Департамент сетей передачи данных,

Сбербанк;

Мальков Роман Юрьевич – эксперт,

Центр компетенций по облачным решениям,

Техносерв,

г. Москва;

Семенов Иван Дмитриевич - старший инженер,

Департамент сетей передачи данных,

Servers.com Лимассол, Кипр;

Юдин Степан Вячеславович - администратор сети,

Департамент технического обеспечения и развития инфраструктуры информационных систем,

Спортмастер, г. Москва

Аннотация: в статье проведен анализ принципов помехоустойчивого кодирования и эффективного декодирования блоков двоичных данных, представленных в виде двумерных массивов. Предложенный математический аппарат базируется на принципах модулярной арифметики и модели линейного блочного кодирования. Разработана схема построения последовательностей кода Рида‑Соломона на базе порождающего полинома. Предложена математическая модель представления двумерных последовательностей кода Рида-Соломона, которая основывается на теории биграфов. Построена комплексная методология помехоустойчивого кодирования данных и восстановления частично поврежденных кодовых последовательностей.

Ключевые слова: коды Рида-Соломона, составное изображение, модулярная арифметика, простое расширение поля, порождающий полином, расширение графа, двудольный граф.

DEVELOPMENT OF ALGORITHMS BASED ON THE REED SOLOMON CODES FOR ERROR CORRECTION OF TWO-DIMENSIONAL ARRAYS OF DIGITAL DATA

Garnyshev I.N., Kazantsev S.V., Malkov R.Yu., Semenov I.D., Iudin S.V.

Garnyshev Igor Nikolaevich - Network Engineer,

DATA NETWORK ADMINISTRATION DEPARTMENT,

TINKOFF BANK;

Kazantsev Sergei Vladimirovich - Senior Engineer,

NETWORK DEPARTMENT,

SBERBANK;

Malkov Roman Yurevich – Expert,

CLOUD SOLUTIONS DEPARTMENT,

TECHNOSERV CLOUD,

MOSCOW;

Semenov Ivan Dmitrievich - Senior Engineer,

NETWORK DEPARTMENT.

SERVERS.COM LIMASSOL, CYPRUS;

Iudin Stepan Vyacheslavovich - Network Administrator,

DEPARTMENT OF TECHNICAL SUPPORT AND INFORMATION SYSTEMS INFRASTRUCTURE DEVELOPMENT,

SPORTMASTER, MOSCOW

Abstract: the article analyzes the principles of error-correcting coding and efficient coding of binary data arrays presented in the form of two-dimensional arrays. The proposed mathematical apparatus is based on the principles of modular arithmetic and a linear block coding model. A scheme for constructing Reed-Solomon code sequences on the basis of a generating polynomial is developed. A mathematical model is presented for representing two-dimensional sequences of the Reed-Solomon code, which is based on the theory of bipartite graphs. A comprehensive methodology for the error-correcting data coding and restoration of partially damaged code sequences has been built.

Keywords: Reed–Solomon codes, compound image, modular arithmetic, primitive element, generator polynomial, graph expansion, bipartite graph.

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

Stamplecoskie S., 2006. A study of the concatenated Reed Solomon: convolutional coding performance used in WiMAX. Ottawa: Defence R&D Canada - Ottawa.
Sungkar M. & Berger T., 2018. Discrete Reconstruction Alphabets in Discrete Memoryless Source Rate-Distortion Problems. 2018 IEEE International Symposium on Information Theory (ISIT). doi:10.1109/isit.2018.8437835.
Lei W., Yizhou G., Fucai Z. & Yong W., The Method to Recognize Linear Block Code Based on the Distribution of Code Weight. 2018 13th APCA International Conference on Control and Soft Computing (CONTROLO). doi:10.1109/controlo.2018.8439758.
Ding W., Lu Y. & Wu F., Enable Efficient Compound Image Compression in H.264/AVC Intra Coding. 2007 IEEE International Conference on Image Processing. doi: 10.1109/icip.2007.4379161.
Zhu W., Ding W., Xiong R., Shi Y. & Yin B., Compound image compression by multi-stage prediction. 2012 Visual Communications and Image Processing. doi: 10.1109/vcip.2012.6410758.
Andre J., Owens D.A. & Harvey L.O., 2003. Visual perception: the influence of H.W. Leibowitz. Washington, DC: American Psychological Association.
Slovak J., Bornholdt C., Bauer S., Kreissl J., Schlak M. & Sartoriu B., 2006. Novel concept for all-optical clock recovery from NRZ format PRBS data streams. 2006 Optical Fiber Communication Conference and the National Fiber Optic Engineers Conference. doi: 10.1109/ofc.2006.215908.
Milster T.D. & Kim Y.S., Adaptive optics for data recovery on optical disk fragments (Conference Presentation). Optical Data Storage 2017: From New Materials to New Systems. doi: 10.1117/12.2277078.
Masters G. & Turner P., 2007. Forensic data recovery and examination of magnetic swipe card cloning devices. Digital Investigation, 4, 16–22. doi: 10.1016/j.diin.2007.06.018.
Sato N., Modular arithmetic. Ottawa: Canadian Mathematical Society = Société mathématique du Canada.
Hunter D.J., 2017. Essentials of discrete mathematics. Burlington, MA: Jones & Bartlett Learning.
Jadhao M.G., Performance Analysis of Linear Block Code, Convolution code and Concatenated code to Study Their Comparative Effectiveness. IOSR Journal of Electrical and Electronics Engineering, 1(1), 53-61. doi:10.9790/1676-0115361.
Mei T., Zhang C. & Dai Q., Using Linear Block Code and Concatenated Code to Build (k,n) Threshold Scheme. 2011 International Conference on Internet Technology and Applications. doi:10.1109/itap.2011.6006219.
Kim S., Reversible Data-Hiding Systems with Modified Fluctuation Functions and Reed-Solomon Codes for Encrypted Image Recovery. Symmetry, 9(5), 61. doi: 10.3390/sym9050061.
Chaari L., Fourati M. & Kamoun L., Image transmission quality analysis over adaptive Reed-Solomon coding. Melecon 2010 - 2010 15th IEEE Mediterranean Electrotechnical Conference. doi: 10.1109/melcon.2010.5476245.
Matching Viterbi Decoders and Reed-Solomon Decoders in a Concatenated System, 2009. Reed-Solomon Codes and Their Applications. doi: 10.1109/9780470546345.ch11.
Yedidia J. (n.d.). Sparse factor graph representations of reed-solomon and related codes. International Symposium OnInformation Theory, 2004. ISIT 2004. Proceedings. doi: 10.1109/isit.2004.1365296.
Hoholdt T. & Justesen J., Graph Codes with Reed-Solomon Component Codes. 2006 IEEE International Symposium on Information Theory. doi: 10.1109/isit.2006.261904.
Hirschfeld J.W.P., Korchmáros G. & Torres F., 2008. Algebraic curves over a finite field. Princeton (New Jersey): Princeton University Press.
Nasseri M., Xiao X., Zhang S., Wang T. & Lin S., Concatenated finite geometry and finite field LDPC codes. 2017 11th International Conference on Signal Processing and Communication Systems (ICSPCS). doi: 10.1109/icspcs.2017.8270513.
Lavrauw M. & Voorde G.V.D., Field reduction and linear sets in finite geometry. Topics in Finite Fields Contemporary Mathematics, 271–293. doi: 10.1090/conm/632/12633.
Lavrauw M. & Zanella C., Geometry of the inversion in a finite field and partitions of PG(2k − 1, q) in normal rational curves. Journal of Geometry. 105 (1), 103–110. doi: 10.1007/s00022-013-0197-8.

Ссылка для цитирования данной статьи

Тип лицензии на данную статью – CC BY 4.0. Это значит, что Вы можете свободно цитировать данную статью на любом носителе и в любом формате при указании авторства.

Электронная версия. Гарнышев И.Н., Казанцев С.В., Мальков Р.Ю., Семенов И.Д., Юдин С.В. ПОСТРОЕНИЕ АЛГОРИТМОВ НА ОСНОВЕ КОДОВ РИДА СОЛОМОНА ДЛЯ КОРРЕКЦИИ ОШИБОК В ДВУХМЕРНЫХ МАССИВАХ ЦИФРОВЫХ ДАННЫХ // Вестник науки и образования №18 (72), 2019. [Электронныйресурс].URL: http://scientificjournal.ru/images/PDF/2019/VNO-72/postroenie-algoritmov.pdf (Дата обращения:ХХ.ХХ.201Х).

Печатная версия. Гарнышев И.Н., Казанцев С.В., Мальков Р.Ю., Семенов И.Д., Юдин С.В. ПОСТРОЕНИЕ АЛГОРИТМОВ НА ОСНОВЕ КОДОВ РИДА СОЛОМОНА ДЛЯ КОРРЕКЦИИ ОШИБОК В ДВУХМЕРНЫХ МАССИВАХ ЦИФРОВЫХ ДАННЫХ// Вестник науки и образования № 18 (72), 2019, C. {см. журнал}.