Методи виправлення помилок у закодованих повідомленнях матрицями Фібоначчі

Abstract

Проаналізовано наявні методики виправлення помилок у закодованих повідомленнях матрицями Фібоначчі, що дають можливість знаходити і виправляти декілька помилок у кодових словах, отриманих каналами зв’язку. З’ясовано, що за останнє десятиліття опубліковано багато різноманітних робіт, у кожній з яких обґрунтовано доцільність використання матриць Фібоначчі для (де)кодування даних. Встановлено, що елементи кодового слова, одержаного множенням блока повідомлення на матрицю Фібоначчі, мають чимало корисних властивостей, на яких ґрунтується методика виявлення та виправлення у ньому помилок. Дослідники стверджують, що відношення відповідних елементів кодового слова наближене до золотого перерізу, й це має важливе значення для відомих методик виправлення потенційних помилок. Така властивість кодового слова дає можливість ідентифікувати наявність подвійних і потрійних помилкових елементів, перевіривши, чи належать їхні відношення до фіксованого інтервалу. Хибна належність, як виявилось, свідчить про те, що в різних рядках кодового слова є дві помилки, для виправлення яких потрібно розв’язати відповідні діофантові рівняння. Розв’язки цих рівнянь повинні задовольнити певні умови виправлення помилок. З’ясовано, що для виправлення двох помилок у одному рядку кодового слова ставлять умову, згідно з якою набір блоків вхідного повідомлення має містити тільки мінімальні матриці, що дає можливість брати найменші розв’язки діофантового рівняння, придатність яких уточнюють перевіряльними співвідношеннями. Виявлено, що для виправлення трьох помилок у кодовому слові потрібно перевірити приналежність фіксованому інтервалу відношень відповідних його елементів та розв’язати нелінійне діофантове рівняння, реалізація якого є надзвичайно складною. Запропонований підхід зводиться до проб і помилок: спочатку потрібно знайти точне місце розташування помилкових елементів, а вже потім їх виправляти за відповідними методиками.

The main problems of detection and available methods of correcting errors in encoded messages with Fibonacci matrices, which make it possible to find and correct one, two and three errors in the same or different lines of the code word, are analyzed. It has been found that even in the last decade, many scientists have published a significant number of various publications, each of which to one degree or another substantiates the expediency of using Fibonacci matrices for (de)coding data. It has been established that the elements of a codeword obtained by multiplying a message block by a Fibonacci matrix have many useful properties, which are the basis for the method for detecting and correcting errors in them. The statement is given, according to which the ratio of the corresponding elements of the code word is close to the golden ratio, which is important for the existing methods of correcting potential errors. This property of the elements makes it possible to identify the presence of double and triple false elements by checking whether their ratios belong to a fixed interval. It is found that the false affiliation indicates that there are two errors in different lines of the codeword, which require solving the corresponding Diophantine equations, the suitability of the solution of which must satisfy certain conditions for error correction. It was found that in order to correct two errors in one line of the code word, a condition was introduced according to which the set of blocks of the input message should contain only minimal matrices, which makes it possible to take the smallest solutions of the Diophantine equation, the suitability of which is specified by test ratios. It was found that in order to correct three errors in a codeword, it is necessary to check whether the relations of its corresponding elements belong to a fixed interval and to solve a nonlinear Diophantine equation, the implementation of which is extremely difficult. The proposed approach boils down to trial and error, according to which you first need to find the exact location of the erroneous elements, and only then correct them according to the appropriate methods.