Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Փոքր ամպլիտուդայով սխալներ ուղղող կոդերի կառուցումը և իրականացումը

Խաչատրյան, Համլետ Կարենի (2018) Փոքր ամպլիտուդայով սխալներ ուղղող կոդերի կառուցումը և իրականացումը. PhD thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

[img] PDF (Thesis)
Available under License Creative Commons Attribution.

Download (14Mb)
    [img] PDF (Abstract)
    Available under License Creative Commons Attribution.

    Download (2714Kb)

      Abstract

      Սխալներ ուղղող կոդերի տեսությունը ինֆորմատիկայի մի ճյուղ է, որն առաջացել և բուռն զարգացում է ապրել համեմատաբար ոչ վաղ անցյալում` XX-րդ դարի երկրորդ կեսին: Համակարգում կապուղղով հաղորդագրություններ փոխանցելիս տարբեր գործոնների պատճառով սովորաբար տեղի են ունենում որոշակի սխալներ: Դրա համար պահանջվում են այնպիսի կոդեր, որոնք կարողանան ոչ միայն հայտնաբերել այլ նաև ուղղել այդ սխալները: Սխալներ ուղղող կոդերի տեսության հիմնական խնդիրներից են` Կոդերի կառուցման մեթոդների ստեղծումը։ Կոդավորման և ապակոդավորման արդյունավետ ալգորիթմների կառուցումը: Սխալներ ուղղող կոդերի տեսությունը ունի լայն կիրառություն հեռուստատեսության մեջ, ինչպես նաև արբանյակային ալեհավաքներով փոխանցված հաղորդագրություններում սխալներ հայտնաբերելու և ուղղելու նպատակով: Սխալներ ուղղող կոդերը օգտագործվում են նաև հեռախոսային գծերում և բջջային կապերում: Չնայած որ սխալներ ուղղող կոդերի ամենալայն կիրառությունը կապի գծերում է, այնուամենայնիվ, այժմ նրանք ունեն կիրառություններ նաև ֆլեշ հիշողություններում: Քանի որ ֆլեշ հիշողություններում առաջացած սխալները հիմնականում լինում են ասիմետրիկ և փոքր ամպլիտուդայով, անհրաժեշտ է կառուցել հենց այս տիպի սխալներ ուղղող կոդեր: Ֆլեշ հիշողությունների ծավալների մեծացմանը զուգընթաց խնդիր է առաջանում ստեղծել ավելի արագագործ կոդավորման և ապակոդավորման համակարգեր: Սխալներ ուղղող կոդերի խնդիրների վրա դրված երեք հիմնական պահանջներն են` Կոդերի կառուցումներ, որոնք կկարողանան պատշաճ կերպով ուղղել արտաքին գործոնների հետևանքով առաջացած սխալները։ Կառուցված կոդերով կոդավորման մեթոդի պրակտիկ իրականացում։ Ստացված արդյունքների կիրառական նշանակությունը նրանումն է, որ հետազոտությունները ցույց են տվել, որ ֆլեշ մեխանիզմներում տեղի ունեցող սխալները հիմնականում լինում են ասիմետրիկ և ունենում են փոքր ամպլիտուդա մեծություն , նաև նրանք անկախ են այբուբենի մեծությունից, որոնք կարող են լինել զգալիորեն ավելի մեծ քան սխալի մեծությունը: Դրա համար անհրաժեշտ է կառուցել հենց այդ տիպի սխալներ ուղղող կոդեր: Փոքր ամպլիտուդայով սխալներ ուղղող կոդերի կառուցումերը և իրագործումը ֆլեշ հիշողություններում և մոդուլյացիոն սխեմաներում զգալիորեն կարող են ավելացնել նրանց աշխատանքի կայունությունը: С практической точки зрения большой интерес вызывают коды на кольцах Z₂m и Z₂m₊₁, так как они имеют широкое применение в 2²ͫ –КАМ модуляционных схемах. Ошибки, возникающие в канале, в основном асимметричны, они также имеют ограниченную величину, и этот эффект особенно применим к флэш-памяти. Таким образом, должны создаваться коды, которые могут исправлять такие типы ошибок. Критерий оптимальности для линейных кодов по фиксированному кольцу Z m можно рассматривать двумя способами. Прежде всего, напомним, что код длиной n является оптимальным-1, если он имеет минимальное возможное количество символов проверки на четность. Во-вторых, критерий оптимальности-2 для кода заключаются в том, что для заданного числа символов проверки на четность он имеет максимально возможную длину. На данный момент мы не знаем никаких кодов, которые удовлетворяют критериям оптимальности-2. В данной работе представлено построение оптимальных кодов в кольцах Z₇ и Z₉ исправляющие двойные ошибки размера ±1, которые удовлетворяют критерии оптимальности-1. Кроме того, мы разработали метод построения новых кодов C(2N,2N-6), добавляя только два символа проверки на четность к оптимальным кодам C(N<N-4), исправляющих двойные ошибки размера ±1. Новые построенные коды в 2 раза больше, чем C(N,N-4) оптимальные коды. Более того, мы обратили внимание на случаи, когда величина ошибок не только±1. В следующей части работы построены коды C(N,N-5) с 5-ю символами проверки на четность, исправляющих двойные ±1 или ±2 ошибки с ограничением, что обе ошибки имеют одинаковую амплитуду по абсолютной величине над кольцами Z m. Они также основаны на оптимальных кодах C(N,N-4), исправляющих двойные ошибки размера ±1. В этом случае мы не можем исправлять двойные ошибки с разными величинами, например, одну ошибку с величиной +1 и другую с величиной +2. В заключительной части работы представлены построение и внедрение процедур кодирования и декодирования для линейных кодов, исправляющих двойные ошибки размера ±1 или ±2, которые были реализованы на языке программирования C++, результаты которого были представлены через диалоговое окно MFC. From practical point of view the codes over rings Z₂m or Z₂m₊₁ are interesting, because they can be used in 2²ͫ QAM (Quadrature amplitude modulation) schemes. Codes over finite rings, particularly over integer residue rings and their applications in coding theory have been studied for a long time. Errors happening in the channel are basically asymmetrical; they also have a limited magnitude and this effect is particularly applicable to flash memories. As such, we consider the problem of construction of codes, correcting these types of errors. The optimality criteria for the linear codes over fixed ring Zm can be considered in two ways. First of all, recall that the code of the length n is optimal-1 if it has a minimum possible number of parity check symbols. Secondly, optimality-2 criteria for the code is that for a given number of parity check symbols, it has a maximum possible length. At this point we do not know any codes that satisfy the optimality criteria-2.In this paper a construction of double ±1 error correcting linear optimal codes over rings Z₇ and Z₉ is presented, which satisfy to optimality criteria-1. Also, we construct a method for constructions of codes C(2N,2N-6, by adding only two parity check symbols to the optimal codes C(N,N-4) correcting double ±1 errors. The new constructed codes are 2 time longer then C(N,N-4) optimal codes, and they have a higher rate. Moreover, we pay attention to the cases when magnitude of errors are not only±1. In this paper we will construct codes C(N,N-5) with 5 parity check symbols correcting double ±1 or ±2 errors with the limitation that both errors have the same amplitude in absolute value over rings Zm. They are based on optimal codes C(N,N-4) with 4 parity check symbols correcting double errors over rings Zm of value ±1. In this case we can not correct double errors with different magnitude, for example one error with magnitude +1 and other with a magnitude +2. In the next part of the work, the construction and implementation of encoding and decoding procedures for double ±1 or (±1 and ±2) error correcting optimal linear codes arepresented.

      Item Type: Thesis (PhD)
      Additional Information: Построение кодов исправляющих ошибки малыми амплитудами и их реализация. Low-magnitude error correcting codes and their implementation.
      Uncontrolled Keywords: Хачатрян Гамлет Каренович, Khachatryan Hamlet Karen
      Subjects: Informatics and Computer Systems
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 04 Sep 2018 15:27
      Last Modified: 04 Sep 2018 15:27
      URI: http://etd.asj-oa.am/id/eprint/7591

      Actions (login required)

      View Item