Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 43, 57--61, 2015. Encoding and Decoding Procedures for Double ±1 Error Correcting Linear Code over Ring 𝑍𝑍5 Hamlet K. Khachatryan Institute for Informatics and Automation Problems of NAS RA e-mail: hamletxachatryan.08@gmail.com Abstract From practical point of view the codes over 𝑍𝑍2𝑚𝑚 or 𝑍𝑍2𝑚𝑚+1 are interesting, because they can be used in 22𝑚𝑚 –QAM (Quadrature amplitude modulation) schemes. In this paper a construction of encoding and decoding procedures for double ±1 error correcting optimal(12,8) linear code over ring 𝑍𝑍5 is presented. Keywords: Error correcting codes, Codes over the ring 𝑍𝑍5, Encoding and Decoding procedures. 1. Introduction 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.There are many constructed codes capable to correct up to two errors of value ±1 .The earliest paper discussing the codes over the ring 𝑍𝑍𝐴𝐴 of integers modulo 𝐴𝐴 are due to Blake [1], [2]. The optimality criteria for the linear code over fixed ring 𝑍𝑍𝑚𝑚 was considered in 2 ways in [3]. 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. Here, we propose to construct encoding and decoding algorithms for the optimal codes. The code presented in this paper satisfies the optimality criteria-1([3]). At this point we do not know any codes that satisfy the optimality criteria-2. There have been encoding and decoding procedures for the (4, 2) code over ring 𝑍𝑍9 in [4]. Implementation of codes over large alphabets is much more difficult compared with small alphabets. In this paper a construction of encoding and decoding procedures of (12, 8) linear code over ring 𝑍𝑍5 correcting double ±1 errors is presented. 57 Encoding and Decoding Procedures for Double ±1 Error Correcting Linear Code Over Ring 𝒁𝒁𝟓𝟓 58 2. Presentation of the Code Let a linear (12, 4) code over ring Z5 be given by the following parity check matrix 𝐻𝐻: 𝐻𝐻 = � 1 1 1 1 1 0 1 2 3 4 1 1 0 1 2 3 4 2 2 2 2 2 1 1 3 2 4 4 2 3 2 4 4 2 1 1 1 1 1 1 1 3 2 4 4 2 0 4 �. A linear code over Z5 given by the parity check matrix 𝐻𝐻 can correct up to two errors of the type ±1, because 𝐻𝐻 has a property according to which all the syndromes resulting from adding and subtracting operations between any two columns of the matrix 𝐻𝐻 are different (±hi± hj and hi≠hj)(proof of this you can see in [3]). In this case the number of combinations for each code word that can be corrected is (1 + 12 ∗ 2 + (12 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 4) = 289. For encoding every vector in 𝑍𝑍5 we should have the generator matrix 𝐺𝐺. For this we should construct a combinatorial equivalent matrix 𝐻𝐻′ from matrix 𝐻𝐻. 𝐻𝐻′ = � 1 0 0 0 3 1 0 3 4 3 4 0 0 1 0 0 2 2 4 4 0 2 4 3 0 0 1 0 0 0 2 4 2 1 3 1 0 0 0 1 1 3 2 0 4 4 3 3 �. In this matrix all 289 possible syndromes will be different, too. From [5] we know, that 𝐺𝐺𝐻𝐻′𝑇𝑇 = 0. (1) If H′ = [−PT|In−k], then G = [Ik|P] (the reverse statement is also true), where Ik is a 𝑘𝑘 ∗ 𝑘𝑘 identity matrix and P is a 𝑘𝑘 ∗ (𝑛𝑛 − 𝑘𝑘) matrix[5]. Thus, we can construct the generator matrix 𝐺𝐺: 𝐺𝐺 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 2 3 0 4 1 0 0 0 0 0 0 0 4 3 0 2 0 1 0 0 0 0 0 0 0 1 3 3 0 0 1 0 0 0 0 0 2 1 1 0 0 0 0 1 0 0 0 0 1 0 3 1 0 0 0 0 1 0 0 0 2 3 4 1 0 0 0 0 0 1 0 0 1 1 2 2 0 0 0 0 0 0 1 0 0 2 4 2 0 0 0 0 0 0 0 1⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ . H. Khachatryan 59 3. Encoding and Decoding Procedures 3.1 Encoding Procedure In our scheme the message was presented by 8-tuples in Z5. Let 𝐺𝐺 be a generator matrix for (12,8) linear code. 𝑣𝑣 = (𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3, … , 𝑎𝑎8) is an arbitrary 8-tuple, and consider the vector 𝑢𝑢 that is the linear combination of columns 𝐺𝐺 with 𝑎𝑎𝑖𝑖 is the 𝑖𝑖𝑡𝑡ℎ coefficient. 𝑢𝑢 = 𝑣𝑣𝐺𝐺 = (𝑐𝑐1, 𝑐𝑐2, 𝑐𝑐3, 𝑐𝑐4, 𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3, … , 𝑎𝑎8), where the first 4 components of the code vector are the check symbols, the next 8 components are information symbols and 𝑐𝑐𝑗𝑗 = �∑ 𝑎𝑎𝑖𝑖𝑝𝑝𝑖𝑖𝑗𝑗 𝑘𝑘 𝑖𝑖=1 �𝑚𝑚𝑜𝑜𝑚𝑚5. (2) Example. Let (3 4 0 0 2 1 1 4) be the message vector in 𝑍𝑍5. From (2) we can obtain check symbols. For example, the first check symbol is c1: 𝑐𝑐1 = (3 ∗ 2) + (4 ∗ 4) + (0 ∗ 0) + (0 ∗ 2) + (2 ∗ 1) + (1 ∗ 2) + (1 ∗ 1) + (4 ∗ 0) = = 6 + 16 + 0 + 0 + 2 + 2 + 1 + 0 = 27𝑚𝑚𝑜𝑜𝑚𝑚5 = 2 . Similarly, we can find other 3 check symbols: 𝑐𝑐2 = 3, 𝑐𝑐3 = 3, 𝑐𝑐4 = 3. After performing other multiple operations with matrix 𝐺𝐺 we obtain this encoded vector: (2 3 3 3 3 4 0 0 2 1 1 4). 3.2 Decoding Procedure In this section we describe the decoding procedure: 1. Receiver multiplies the vector with every column of matrix H′ and gets the syndrome S = vH′. If S = (0,0,0,0) then there were not any errors in the received vector. 2. If the calculated syndrome S is a nonzero vector, then there are some errors. This (12,8) code can correct only up to two errors with magnitude ±1. We know that all possible syndromes of matrix H′ are different (±hi, ±hj and hi ≠ hj) (the number of them is 288 and syndrome (0,0,0,0)). After calculating the syndrome the receiver knows from which two columns of the matrix H′ the syndrome was resulted, consequently, he can find the two corresponding components of the vector, where the error was occurred and the direction of the error (if +hi, then upward direction or if −hi downward direction). On the other hand, if in the table of syndromes we do not have the resulted syndrome, then we cannot correct this kind of errors. 3. After finding the error components the receiver adds or subtracts 1 from them (he adds if downward, else subtracts) and obtains the sent code vector (𝒄𝒄𝟏𝟏, 𝒄𝒄𝟐𝟐, 𝒄𝒄𝟑𝟑, 𝒄𝒄𝟒𝟒, 𝒂𝒂𝟏𝟏, 𝒂𝒂𝟐𝟐, 𝒂𝒂𝟑𝟑, … , 𝒂𝒂𝟖𝟖). So (𝒂𝒂𝟏𝟏, 𝒂𝒂𝟐𝟐, 𝒂𝒂𝟑𝟑, … , 𝒂𝒂𝟖𝟖) is our message vector. Encoding and Decoding Procedures for Double ±1 Error Correcting Linear Code Over Ring 𝒁𝒁𝟓𝟓 60 Example. (2 3 3 3 3 4 0 0 2 1 1 4) is an encoded vector from the previous example. Let there occur 2 errors in the channel, and the receiver get the vector (2 3 3 3 3 4 0 4 2 2 1 4). After performing multiple operations with rows of matrix 𝐻𝐻′ 𝑡𝑡ℎ𝑜𝑜 receiver obtains the syndrome (0 3 2 4). Next from the table of syndromes he finds the corresponding columns, now they are -8 and 10. Hence, the syndrome (0 3 2 4) was resulted from adding a negated column 8 of matrix 𝐻𝐻 to column −3 +3 −4 +2 −4 +1 0 +4 = 0 −2 −3 4 (𝑚𝑚𝑜𝑜𝑚𝑚5) = (0 3 2 4), (because in 𝑍𝑍5, 0 = 5, −1 = 4, −2 = 3 , −3 = 2, −4 = 1). Hence, the error positions of encoded vector are 8 and 10 (in 8𝑡𝑡ℎ downward direction and in 10𝑡𝑡ℎ upward). So, he adds 1 to 8𝑡𝑡ℎ component and subtracts 1 from 10𝑡𝑡ℎ of vector (2 3 3 3 3 4 0 4 2 2 1 4) and obtains the sent encoded vector (2 3 3 3 3 4 0 0 2 1 1 4). Consequently, the message vector 𝑖𝑖𝑜𝑜 (3 4 0 0 2 1 1 4). 4. Conclusion In this paper a construction of encoding and decoding procedures of optimal-1 (12,8) linear code over ring 𝑍𝑍5 correcting double ±1 errors is presented. We propose that this approach can be extended for constructing similar procedures for the optimal codes over other rings 𝑍𝑍𝑛𝑛 and the research in this direction will follow. References [1] I. Blake, “Codes over certain rings”, Information and Control, vol. 20, pp. 396-404, 1972. [2] I. Blake, “Codes over integer residue rings”, Information and Control, vol. 29, 1975, 295-300. [3] G. Khachatrian and H. Morita, “Construction of optimal 1 double error correcting linear codes over ring Z5 ”, 3th International Workshop on Advances in Communications, Boppard, Germany, pp. 10-12, May 2014. [4] H. Kostadinov, N. Manev and H. Morita, “Double ±1-error correctable codes and their applications to modulation schemes”, Proc. Elev. Intern. Workshop ACCT, Pamporovo,June 16-22, pp 155-160,2008. [5] W. W. Peterson and E.J. Weldon, Error-Correcting Codes, M.I.T. Press, Cambridge, Mass.,1972. Submitted 15.10.2014, accepted 12. 02. 2015. H. Khachatryan 61 Կոդավորման և ապակոդավորման ալգորիթմը Z5 օղակում ±1 մեծությամբ կրկնակի սխալ ուղղող կոդերի համար Հ. Խաչատրյան Ամփոփում Պրակտիկ տեսանկյունից մեծ հետաքրքրություն են առաջացնում 𝒁𝒁𝟐𝟐𝟐𝟐 կամ 𝒁𝒁𝟐𝟐𝟐𝟐+𝟏𝟏 օղակների վրա դիտարկված կոդերը, քանի որ նրանք ունեն լայն կիրառություն 𝟐𝟐𝟐𝟐𝟐𝟐 –QAM մոդուլյացիոն սխեմաներում: Այս հոդվածի շրջանակներում ներկայացված է կոդավորման և ապակոդավորման ալգորիթմը Z5 օղակում ±1 մեծության մինչև 2 սխալ ուղղող օպտիմալ (12, 8) գծային կոդի համար: Алгоритм кодирования и декодирования в кольце Z5 для кодов исправляющих двойные ошибки размера ±1 Г. Хачатрян Аннотация С практической точки зрения большой интерес вызывают коды на кольцах 𝑍𝑍2𝑚𝑚 и 𝑍𝑍2𝑚𝑚+1, так как они имеют широкое применение в 22𝑚𝑚 –К А М модуляционных схемах. В данной статье представлен алгоритм кодирования и декодирования в кольце Z5 для оптимального (12,8) линейного кода, исправляющего до двух ошибок размера ±1. Encoding and Decoding Procedures for Double ±1 Error Correcting Linear Code over Ring ,𝑍-5. Hamlet K. Khachatryan From practical point of view the codes over ,𝑍-2𝑚. or ,𝑍-2𝑚+1. are interesting, because they can be used in ,2-2𝑚. –QAM (Quadrature amplitude modulation) schemes. In this paper a construction of encoding and decoding procedures for double ±1 erro... 1. Introduction 2. Presentation of the Code