Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 48, 105--111, 2017. Further Results for Encoding and Decoding Procedures of Asymmetric Low Magnitude Error Correcting Codes Hamlet K. Khachatrian Institute for Informatics and Automation Problems of NAS RA e-mail: hamletkh@ipia.sci.am Abstract In this paper an implementation of encoding and decoding procedures for double ±1 error correcting optimal linear codes over rings 𝑍𝑍7 and 𝑍𝑍9 is presented. Keywords: Error correcting codes, Asymmetric low magnitude error correcting codes, 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 have been a couple of papers regarding the optimal ±1 single error correcting codes over the alphabet 𝑍𝑍𝑚𝑚 [1, 2]. Also there are some papers regarding the construction of optimal double ±1 error correcting codes [3, 4]. Here, we propose to construct encoding and decoding algorithms for the optimal codes correcting double ±1 errors. In [5] you can see the construction of encoding and decoding procedures for the optimal linear code (12, 8) over ring 𝑍𝑍5, which was given by parity check matrix 𝐻𝐻5: 𝐻𝐻5 = � 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 �. In this case the number of combinations for each code word that can be corrected is: (1 + 12 ∗ 2 + (12 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 4) = 289. 105 Further Results for Encoding and Decoding Procedures of Asymmetric Low Error Correcting Codes 106 Implementation of codes over large alphabets is much more difficult compared with small alphabets. In this paper we construct encoding and decoding procedures for the codes (16, 12) and (20, 16) over rings 𝑍𝑍7 and 𝑍𝑍9, which are developed in [4]. Using this codes we can correct consequently 512 and 800 errors of type ±1 in any vectors from 𝑍𝑍7 and 𝑍𝑍9 with lengths 12 and 16 by adding only 4 parity check symbols. 2. Presentation of the Codes (16, 12) and (20, 16) over Rings 𝒁𝒁𝟕𝟕 and 𝒁𝒁𝟗𝟗 In [4] you can see the construction of optimal linear codes over Rings Z7 and Z9 correcting double ±1 errors. 2.1 Code (16, 12) over Ring 𝒁𝒁𝟕𝟕 Let a linear (16, 12) code over ring Z7 be given by the following parity check matrix 𝐻𝐻7: 𝐻𝐻7 = � 1 1 1 1 1 1 1 0 1 2 3 4 5 6 1 1 6 5 4 3 2 1 0 2 2 2 2 2 2 2 1 1 4 3 6 6 3 4 2 4 3 6 6 3 4 2 1 6 1 1 1 1 1 1 1 4 3 6 6 3 4 2 0 0 � . A linear code over ring Z7 , with 12 information and 4 parity check symbols, given by the parity check matrix 𝐻𝐻7 can correct up to two errors of the type ±1, because 𝐻𝐻7 has a property according to which all the syndromes resulting from adding and subtracting operations between any two columns of the matrix 𝐻𝐻7 are different (±hi ± hj and hi ≠ hj). This code is optimal in the sense that it has a minimal possible number of parity check symbols. In this case the number of combinations for each code word that can be corrected is: 16 ∗ 2 + (16 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 4 = 512. 2.2 Code (20, 16) over Ring 𝒁𝒁𝟗𝟗 The parity check matrix 𝐻𝐻9 for an optimal linear code (20, 16) correcting double errors of the type ±1 over ring Z9 has the following form: 𝐻𝐻9 = � 1 1 1 1 1 1 1 1 8 7 6 5 4 3 2 1 1 1 2 4 7 6 5 4 3 2 1 0 2 2 2 2 2 2 2 2 1 1 2 4 7 3 2 4 4 2 3 7 7 3 2 4 4 2 3 7 1 1 2 4 1 1 1 1 1 1 1 1 7 3 2 4 4 2 3 7 6 3 7 2 �. A linear code over ring Z9 , with 16 information and 4 parity check symbols, given by the parity check matrix 𝐻𝐻9 can correct up to two errors of the type ±1. This code is optimal too in the sense that it has a minimal possible number of parity check symbols. In this case the number of combinations for each code word that can be corrected is: ( 20 ∗ 2 + (20 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 4) = 800 . In the next chapter we will construct encoding and decoding procedures for these two optimal linear codes. H. Khachatrian 107 3. Encoding and Decoding Procedures 3.1 Code (16, 12) For encoding every message in Z7 we must have the generator matrix 𝐺𝐺7. For this we should construct a combinatorial equivalent matrix 𝐻𝐻′7 from parity check matrix 𝐻𝐻7 of the code (16, 12): 𝐻𝐻′7 = � 1 0 0 0 5 2 5 1 5 2 5 0 1 1 6 1 0 1 0 0 2 1 5 5 0 6 4 1 4 6 0 4 0 0 1 0 0 0 0 0 4 1 6 5 5 6 5 5 0 0 0 1 1 5 5 2 3 1 1 3 0 6 2 3 �. Here all syndromes will be different, too. We know the theorem, which says, that 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, 𝐺𝐺𝐻𝐻′𝑇𝑇 = 0. (1) Thus, we can construct the generator matrix 𝐺𝐺7: 𝐺𝐺7 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 2 5 0 6 1 0 0 0 0 0 0 0 0 0 0 0 5 6 0 2 0 1 0 0 0 0 0 0 0 0 0 0 2 2 0 2 0 0 1 0 0 0 0 0 0 0 0 0 6 2 0 5 0 0 0 1 0 0 0 0 0 0 0 0 2 0 3 4 0 0 0 0 1 0 0 0 0 0 0 0 5 1 6 6 0 0 0 0 0 1 0 0 0 0 0 0 2 3 1 6 0 0 0 0 0 0 1 0 0 0 0 0 0 6 2 4 0 0 0 0 0 0 0 1 0 0 0 0 6 3 2 0 0 0 0 0 0 0 0 0 1 0 0 0 6 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 2 5 0 0 0 0 0 0 0 0 0 0 1 0 6 3 2 4 0 0 0 0 0 0 0 0 0 0 0 1⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ . Encoding procedure: In our scheme the message was presented by 12-tuples in Z7. 𝑣𝑣 = (𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3, … , 𝑎𝑎12) is an arbitrary 12-tuple, and consider the vector 𝑢𝑢 that is the linear combination of columns 𝐺𝐺7 with 𝑎𝑎𝑖𝑖 is the 𝑖𝑖𝑡𝑡ℎ coefficient. 𝑢𝑢 = 𝑣𝑣𝐺𝐺 = (𝑐𝑐1, 𝑐𝑐2, 𝑐𝑐3, 𝑐𝑐4, 𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3, … , 𝑎𝑎12), where the first 4 components of the code vector are the parity check symbols and the next 12 components are information symbols, where 𝑐𝑐𝑗𝑗 = �∑ 𝑎𝑎𝑖𝑖𝑝𝑝𝑖𝑖𝑗𝑗 𝑘𝑘 𝑖𝑖=1 �𝑚𝑚𝑜𝑜𝑚𝑚7. (2) Let us show the example to describe how we do these procedures. Further Results for Encoding and Decoding Procedures of Asymmetric Low Error Correcting Codes 108 Example. Let (0 1 2 6 4 0 6 5 4 1 2 2) be the message vector in Z7. From (2) we can obtain parity check symbols by multiplying this message vector with the columns of the matrix 𝐺𝐺7. For example, the first parity check symbol is c1: 𝑐𝑐1 = (0 ∗ 2) + (1 ∗ 5) + (2 ∗ 2) + (6 ∗ 6) + (4 ∗ 2) + (0 ∗ 5) + (6 ∗ 2) + (5 ∗ 0) + (4 ∗ 6) + (1 ∗ 6) + (2 ∗ 1) + (2 ∗ 6) = 0 + 5 + 4 + 1 + 1 + 0 + 5 + 0 + 3 + 6 + 2 + 5 = 4(𝑚𝑚𝑜𝑜𝑚𝑚7). (All operations are in Z7.) Similarly, we can find other 3 parity check symbols: 𝑐𝑐2 = 5, 𝑐𝑐3 = 3, 𝑐𝑐4 = 1. After performing other multiple operations with matrix 𝐺𝐺7 we obtain this encoded vector: (4 5 3 1 0 1 2 6 4 0 6 5 4 1 2 2). As we can see in this code, the encoded message (codeword) has the length 16, from which the first 4 are parity check symbols, and the last 12 are information symbols. Decoding procedure: Now we will show how a decoding procedure will be implemented using the parity check matrix 𝐻𝐻′7, if during the message sending process the errors occured in the codewords. We will describe the decoding procedure by 3 steps: 1. Receiver multiplies the vector with every row of matrix H′7 and gets the syndrome S = 𝐯𝐯H′. 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 occurred errors. These codes can correct only up to two errors with magnitude ±1. We know that all possible syndromes of matrix H′7 are different (±hi ± hj and hi ≠ hj). After calculating the syndrome the receiver knows from which two columns of the matrix H′7 the syndrome was resulted, consequently, it 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 and obtains the sent code vector (c1, c2, c3, c4, a1, a2, a3, … , a12). So (a1, a2, a3, … , a12) is our message vector. An example. (4 5 3 1 0 1 2 6 4 0 6 5 4 1 2 2) is an encoded vector from the previous example. Let 2 errors occur in the channel, and the receiver gets the vector (4 5 2 1 0 1 2 6 4 0 6 5 4 1 2 1). After performing multiple operations with rows of matrix 𝐻𝐻′7 the receiver obtains the syndrome(6 3 1 4). Next from the table of syndromes it finds the corresponding columns, now they are 3 and 16. Hence, the syndrome (6 3 1 4) was resulted from adding a negated column 3 of matrix 𝐻𝐻′7 to the negated column 16: 0 −1 0 −4 −1 −5 0 −3 = −1 −4 −6 −3 (𝑚𝑚𝑜𝑜𝑚𝑚7) = (6 3 1 4) (Because in 𝑍𝑍7 0 = 7, −1 = 6, −2 = 5 , −3 = 4, −5 = 2, −6 = 1). Hence, the error positions of encoded vector are 3 and 16 (both have a downward direction). H. Khachatrian 109 So, it adds 1 to 𝑡𝑡ℎ𝑜𝑜 3rd component and 1 to 16𝑡𝑡ℎ of vector (4 5 𝟐𝟐 1 0 1 2 6 4 0 6 5 4 1 2 𝟏𝟏) and obtains the sent encoded vector (4 5 3 1 0 1 2 6 4 0 6 5 4 1 2 2). Consequently, the message vector (code word) is (0 1 2 6 4 0 6 5 4 1 2 2) as we have in the example of the encoding procedure. Using this code we can find and correct all possible 512 errors of the type ±1 in every vector over ring 𝑍𝑍7. 3.2 Encoding and Decoding for the Code (20, 16) For the code (20, 16) over the ring Z9 correcting double errors of the type ±1 we can do the same encoding and decoding processes as we did for the code (16, 12). In this case, the parity check matrix 𝐻𝐻′9 and the generator matrix 𝐺𝐺9 will have the following form: 𝐻𝐻′9 = � 1 0 0 0 6 7 8 5 0 6 6 0 7 3 5 4 7 4 7 4 0 1 0 0 0 6 0 2 4 7 1 4 1 1 1 1 7 4 3 3 0 0 1 0 6 4 5 6 6 3 0 6 3 5 6 3 7 1 4 5 0 0 0 1 1 4 1 5 2 1 6 8 6 3 0 6 4 1 7 0 �, 𝐺𝐺9= ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 3 0 3 8 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 5 5 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 4 8 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 4 7 3 4 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 5 3 7 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 2 6 8 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 3 8 0 3 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 5 3 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 2 8 6 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 6 8 4 6 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 4 8 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 5 8 6 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 2 2 5 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 5 5 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 6 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 5 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ Unlike the previous case for the code (16, 12) over ring 𝑍𝑍7, in this case the message was presented by 16-tuples in 𝑍𝑍9. The encoded vector 𝑢𝑢 (codeword) has a length 20: 𝑢𝑢 = 𝑣𝑣𝐺𝐺 = (𝑐𝑐1, 𝑐𝑐2, 𝑐𝑐3, 𝑐𝑐4, 𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3, … , 𝑎𝑎16), where the first four are the parity check symbols: 𝑐𝑐𝑗𝑗 = �∑ 𝑎𝑎𝑖𝑖𝑝𝑝𝑖𝑖𝑗𝑗 𝑘𝑘 𝑖𝑖=1 �𝑚𝑚𝑜𝑜𝑚𝑚9 and the next 16 are information symbols. Using this code we can find and correct all possible 800 errors of the type ±1 in every vector over ring 𝑍𝑍9. Further Results for Encoding and Decoding Procedures of Asymmetric Low Error Correcting Codes 110 4. Conclusion In this paper an implementation of encoding and decoding procedures of optimal (16, 12) and (20, 16) linear codes over ring 𝑍𝑍7 and 𝑍𝑍9 correcting double ±1 errors is presented. We propose that this approach can be extended for implementation of similar procedures for the optimal codes over other rings 𝑍𝑍𝑛𝑛 and the research in this direction will follow. References [1] S. Martirossian, “Single error correcting close packed and perfect codes”, Proc.1st INTAS Int. Seminar Coding Theory and Combinatorics, Armenia, pp. 90-115, 1996. [2] H. Kostadinov, N.Manev and H.Morita, “On ±1 error correctable codes”, IEICE Trans.Fundamentals, vol. E93-A, pp. 2578-2761, 2010. [3] G. Khachatrian and H. Morita, “Construction of optimal 1 double error correcting linear codes over ring Z5 ”, 3rd International Workshop on Advances in Communications, Boppard, Germany, pp. 10-12, May 2014. [4] G. Khachatryan and H. Khachatryan, “Construction of double ±1 error correcting linear optimal codes over rings 𝑍𝑍7 and 𝑍𝑍9” , Mathematical Problems of Computer Science, vol. 45, pp. 106—110, 2016. [5] H. Khachatryan, “Encoding and decoding procedures for double ±1 error correcting linear code over ring 𝑍𝑍5”, Mathematical Problems of Computer Science, vol. 43, pp. 57—61, 2015. Submitted 17.09.2017, accepted 04.12.2017. Այլ արդյունքներ ասիմետրիկ փոքր մեծությամբ սխալներ ուղղող կոդերով կոդավորման և ապակոդավորման ալգորիթմների համար Հ. Խաչատրյան Ամփոփում Այս հոդվածի շրջանակներում ներկայացված են կոդավորման և ապակոդավորման ալգորիթմները 𝑍𝑍7 և 𝑍𝑍9 օղակներում կառուցված ասիմետրիկ փոքր ամպլիտուդայով սխալներ ուղղող կոդերի համար: H. Khachatrian 111 Алгоритмы кодирования и декодирования для кодов исправляющих асимметричные двойные ошибки Г. Хачатрян Аннотация В данной статье представлены алгоритмы кодирования и декодирования для кодов в кольцах 𝑍𝑍7 и 𝑍𝑍9 исправляющих двойные асимметричные ошибки. Hamlet K. Khachatrian