Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 49, 66--73, 2018. Construction of Linear Codes over Rings 𝑍𝑍𝑚𝑚 Correcting Double ±1 or ±2 Errors Gurgen H. Khachatrian* and Hamlet K. Khachatrian ** * American University of Armenia **Institute for Informatics and Automation Problems of NAS RA e-mail: gurgenkh@aua.am, hamletkh@ipia.sci.am Abstract In this paper a construction of double ±1 and ±2 errors correcting linear optimal and quasi-optimal codes over rings 𝑍𝑍5, 𝑍𝑍7 and 𝑍𝑍9 is presented with the limitation that both errors have the same amplitude in absolute value. Keywords: Error correcting codes, Codes over the rings 𝑍𝑍𝐴𝐴 , Errors with magnitude ±1 and ±2. 1. Introduction From a practical point of view the codes over rings 𝑍𝑍2𝑚𝑚 or 𝑍𝑍2𝑚𝑚+1 are interesting, because they can be used in 22𝑚𝑚 – 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 occuring in the channel usually 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 alphabet 𝑍𝑍𝑚𝑚 [1,2]. In this paper we will consider on errors with the magnitude ±1 or ±2. There have been a couple of papers regarding the ±1 and ±2 single error correcting codes [1, 3]. In this paper we will construct codes correcting double ±1 or ±2 errors with the limitation that both errors have the same amplitude in absolute value over the rings 𝑍𝑍𝑚𝑚. They are based on optimal codes with 4 parity check symbols correcting double errors over rings 𝑍𝑍𝑚𝑚 of value ±1 , adding only one parity check symbol. In this case, we cannot correct double errors with different magnitudes, for example, one error with a magnitude of +1 and the other one with a magnitude of +2. The optimality criteria for linear codes over the fixed ring 𝑍𝑍𝑚𝑚 can be considered in two ways (see [4]). 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, the optimality-2 criteria for the code is that for a given number of parity check symbols, it has a maximum possible length. Our constructed 66 mailto:gurgenkh@aua.am G. Khachatrian and H. Khachatrian 67 code will satisfy the first optimality criteria. In this case, we do not know codes, which satisfy the optimality criteria – 2. From [4] we know the optimal code (12, 8) correcting double ±1 errors over the ring 𝑍𝑍5. The linear code (12, 8) correcting double errors over the ring 𝑍𝑍5 of value ±1, presented in [4] satisfies the optimality criteria -1: 𝐻𝐻 = � 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 �. This code was given by the parity check matrix 𝐻𝐻, which has 8 information and 4 parity check symbols. In this case the number of combinations for each code word that can be corrected is (1 + 12 ∗ 2 + (12 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 4) = 289. Thus, we have that 289 ∗ 58 ≤ 512 and the cardinality of the best possible code is 512/289 < 59 . In this paper a construction of the optimal code (13, 8) over the ring 𝑍𝑍5 correcting either double ±1 or ±2 errors is presented. 2. Construction of Optimal 𝑪𝑪 (𝟏𝟏𝟏𝟏, 𝟖𝟖) Linear Code over Ring 𝑍𝑍5 Our purpose is to construct an optimal linear code over the ring 𝑍𝑍5 correcting double errors of the type ±1 or ±2 . Our constructed code will correct only double errors with the same magnitude (if both errors have magnitude ±1 , or ±2). It is well known, that a linear code given by the parity check matrix 𝐻𝐻, can correct up to two errors of the type ±1, only when 𝐻𝐻 has a property according to which all the syndromes resulting from adding and subtracting operations between any two columns of the matrix 𝐻𝐻 are different: ± ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑚𝑚 ≠ ± ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑖𝑖 (𝑗𝑗, 𝑚𝑚) ≠ (𝑙𝑙, 𝑘𝑘). In this case, for correcting up to two errors of the type ±1 or ±2, the syndromes of our parity check matrix 𝐻𝐻 must satisfy the following condition too: ±2 ∗ ℎ𝑖𝑖𝑖𝑖 ± 2 ∗ ℎ𝑖𝑖𝑚𝑚 ≠ ±ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑖𝑖 (𝑗𝑗, 𝑚𝑚) ≠ (𝑙𝑙, 𝑘𝑘). To construct this kind of matrix 𝐻𝐻, at first we will use the first 10 columns of the optimal linear code (12, 8) correcting double ±1 errors: � 1 1 1 1 1 0 1 2 3 4 0 1 2 3 4 2 2 2 2 2 3 2 4 4 2 3 2 4 4 2 1 1 1 1 1 3 2 4 4 2 �. Construction of Linear Codes over Rings 𝑍𝑍𝑚𝑚 Correcting Double ±1 or ±2 Errors 68 For this matrix we know, that all syndromes ± ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑚𝑚 ≠ ±ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑖𝑖 and ±2 ∗ ℎ𝑖𝑖𝑖𝑖 ± 2 ∗ ℎ𝑖𝑖𝑚𝑚 ≠ ±2(ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑖𝑖) are different. However, in this case there can be matches between the syndromes: ±2 ∗ ℎ𝑖𝑖𝑖𝑖 ± 2 ∗ ℎ𝑖𝑖𝑚𝑚 𝑎𝑎𝑎𝑎𝑎𝑎 ± ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑖𝑖 . To solve this problem, we need to add one parity check symbol to the code. Consequently, we need to add one additional row to the matrix, which will be the following row: [1 2 3 0 4 1 2 3 0 4]. After adding this row to the matrix, all the corresponding ±2 ∗ ℎ𝑖𝑖𝑖𝑖 ± 2 ∗ ℎ𝑖𝑖𝑚𝑚 ≠ ±ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑖𝑖 syndromes will be different. Now the code given by the parity check matrix below, can correct up to two errors of the type ±1 or ±2 : ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 0 1 2 3 4 0 1 2 3 4 2 2 2 2 2 3 2 4 4 2 3 2 4 4 2 1 1 1 1 1 3 2 4 4 2 1 2 3 0 4 1 2 3 0 4⎦ ⎥ ⎥ ⎥ ⎤ . Our constructed code has a length of 10, from which 5 are parity check symbols, and the other 5- information symbols. This constructed code (10, 5) over the ring 𝑍𝑍5 can correct up to two errors of the type ±1 and ±2, but it is not optimal in the sense that it has a minimal possible number of parity check symbols. To make this code optimal, we at least need to have a length of 13, therefore, we need to add 3 additional columns to the parity check matrix 𝐻𝐻. We have found the corresponding 3 columns by computer search: ⎣ ⎢ ⎢ ⎢ ⎡ 1 4 4 1 0 4 1 2 3 4 3 0 2 3 2⎦ ⎥ ⎥ ⎥ ⎤ . So, we obtain the parity check matrix 𝐻𝐻5 with a length of 13. The code given by this parity check matrix 𝐻𝐻5 can correct up to two errors of the type ±1 or ±2: 𝐻𝐻5 = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 0 1 2 3 4 1 4 4 0 1 2 3 4 2 2 2 2 2 1 0 4 3 2 4 4 2 3 2 4 4 2 1 2 3 1 1 1 1 1 3 2 4 4 2 4 3 0 1 2 3 0 4 1 2 3 0 4 2 3 2⎦ ⎥ ⎥ ⎥ ⎤ . Now we can prove the following lemma: Lemma 2.1. A linear code (13, 8) over the ring 𝑍𝑍5, given by the parity check matrix 𝐻𝐻5 with 5 parity check symbols, correcting up to two errors of the type ±1 or ±2, is optimal in the sense that it has a minimal possible number of parity check symbols. G. Khachatrian and H. Khachatrian 69 Proof. It can be checked that a linear code over the ring 𝑍𝑍5, given by the parity check matrix H5, can correct up to two errors of the type ±1 or ±2. This means that the syndromes of parity check matrix H5 satisfy the condition: ±2 ∗ ℎ𝑖𝑖𝑖𝑖 ± 2 ∗ ℎ𝑖𝑖𝑚𝑚 ≠ ±ℎ𝑖𝑖𝑖𝑖 ± ℎ𝑖𝑖𝑖𝑖 (𝑗𝑗, 𝑚𝑚) ≠ (𝑙𝑙, 𝑘𝑘). In this case, we have 8 possible types of double errors:  +1 𝑎𝑎𝑎𝑎𝑎𝑎 + 1  +1 𝑎𝑎𝑎𝑎𝑎𝑎 − 1  −1 𝑎𝑎𝑎𝑎𝑎𝑎 + 1  −1 𝑎𝑎𝑎𝑎𝑎𝑎 − 1  +2 𝑎𝑎𝑎𝑎𝑎𝑎 + 2  +2 𝑎𝑎𝑎𝑎𝑎𝑎 − 2  −2 𝑎𝑎𝑎𝑎𝑎𝑎 + 2  −2 𝑎𝑎𝑎𝑎𝑎𝑎 − 2 Additionally, we have 4 more cases for single errors of the type ±1 and ±2. In this case, the number of combinations for each code word that can be corrected is (1 + 13 ∗ 4 + (13 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 8) = 677. Thus, we have that 677 ∗ 58 ≤ 513 and the cardinality of the best possible code is 513/677 < 59 . 3. Construction of 𝑪𝑪 (𝟏𝟏𝟏𝟏, 𝟏𝟏𝟏𝟏) and 𝑪𝑪 (𝟏𝟏𝟏𝟏, 𝟏𝟏𝟏𝟏) Codes over Rings 𝑍𝑍7 and 𝑍𝑍9 In this paragraph we will construct asymmetric low magnitude error correcting codes over different rings 𝑍𝑍𝑚𝑚. As it was mentioned above, in this paper we intend to construct codes correcting double ±1 and ±2 errors with the same magnitude. In the previous paragraph we constructed the optimal code C (13, 8) over the ring 𝑍𝑍5 based on the optimal code C (12, 8) correcting only double ±1 errors by adding only one parity check symbol. Codes constructed during this paragraph will not be optimal in the sense that they have a minimal possible number of parity check symbols. 3.1 Construction of Code 𝑪𝑪 (𝟏𝟏𝟏𝟏, 𝟏𝟏𝟏𝟏) over Ring 𝑍𝑍7 It was shown in [5] that the optimal code C (16, 12) over the ring 𝑍𝑍7, correcting double ±1 errors, has the following parity check matrix: � 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 �. To construct the code C (17, 12), correcting double ±1 and ±2 errors with the same magnitude, we need to take the first 14 columns of the parity check matrix: Construction of Linear Codes over Rings 𝑍𝑍𝑚𝑚 Correcting Double ±1 or ±2 Errors 70 � 1 1 1 1 1 1 1 0 1 2 3 4 5 6 6 5 4 3 2 1 0 2 2 2 2 2 2 2 4 3 6 6 3 4 2 4 3 6 6 3 4 2 1 1 1 1 1 1 1 4 3 6 6 3 4 2 � and add one parity check symbol to this code. Consequently, we need to add one additional row to the parity check matrix, which will be the following row: [2 3 4 0 1 6 5 2 3 4 0 1 6 5]. Now the code given by the following parity check matrix, can correct up to two errors of the type ±1 and ±2: ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 1 1 0 1 2 3 4 5 6 6 5 4 3 2 1 0 2 2 2 2 2 2 2 4 3 6 6 3 4 2 4 3 6 6 3 4 2 1 1 1 1 1 1 1 4 3 6 6 3 4 2 2 3 4 0 1 6 5 2 3 4 0 1 6 5⎦ ⎥ ⎥ ⎥ ⎤ . Our newly constructed code given by this parity check matrix has a length of 14, from which 5 are parity check symbols and 9 - information symbols. We want to have the same number of information symbols as in code C (16, 12) with 4 parity check symbols and 12 information symbols. So, we need to add 3 additional columns to the matrix to have 12 information symbols. We found the corresponding 3 columns by computer search: ⎣ ⎢ ⎢ ⎢ ⎡ 6 6 6 1 2 3 5 4 1 3 1 4 5 5 4⎦ ⎥ ⎥ ⎥ ⎤ . So, we obtain the parity check matrix 𝐻𝐻7 , with a length of 17: 𝐻𝐻7 = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 1 1 0 1 2 3 4 5 6 6 6 6 6 5 4 3 2 1 0 2 2 2 2 2 2 2 1 2 3 4 3 6 6 3 4 2 4 3 6 6 3 4 2 5 4 1 1 1 1 1 1 1 1 4 3 6 6 3 4 2 3 1 4 2 3 4 0 1 6 5 2 3 4 0 1 6 5 5 5 4⎦ ⎥ ⎥ ⎥ ⎤ . The code given by this parity check matrix 𝐻𝐻7 with 5 parity check symbols and 12 information symbols, can correct up to two errors of the type ±1 and ±2 with the same magnitude. In this case the number of combinations for each code word that can be corrected is (1 + 17 ∗ 4 + (17 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 8) = 1157. As such, using this code 𝐶𝐶(17, 12) over the ring 𝑍𝑍7, correcting double ±1 and ±2 errors with the same magnitude, we can correct all 1157 errors, which can occur in the code word. This code does not satisfy the optimality criteria-1, since an equation 717/1157 < 713 is not satisfied in G. Khachatrian and H. Khachatrian 71 this case which means that the minimum number of parity check symbols should be 4 not 5, i.e., we have one extra parity check symbol. We will refer to this kind of codes as quasi-optimal. 3.2 Construction of Code 𝑪𝑪 (𝟏𝟏𝟏𝟏, 𝟏𝟏𝟏𝟏) over Ring 𝑍𝑍9 Again, from [5] we know the optimal code C (20, 16) over the ring 𝑍𝑍9, correcting double ±1 errors with 4 parity check symbols and 16 information symbols, which was given below presented by the following parity check matrix : � 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 �. To construct the code C (21, 16), correcting double ±1 and ±2 errors with the same magnitude, we need to take the first 16 columns of the matrix above in the same way as we did in the previous construction for the code C (17, 12) over the ring 𝑍𝑍7: � 1 1 1 1 1 1 1 1 8 7 6 5 4 3 2 1 7 6 5 4 3 2 1 0 2 2 2 2 2 2 2 2 7 3 2 4 4 2 3 7 7 3 2 4 4 2 3 7 1 1 1 1 1 1 1 1 7 3 2 4 4 2 3 7 � and add one parity check symbol to this code. Consequently, we need to add one additional row to the matrix, which will be the following row: [2 3 4 0 1 8 7 3 2 3 4 0 1 8 7 3]. Now the code given by the following parity check matrix, can correct up to two errors of the type ±1 and ±2 with the same magnitude: ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 1 1 1 8 7 6 5 4 3 2 1 7 6 5 4 3 2 1 0 2 2 2 2 2 2 2 2 7 3 2 4 4 2 3 7 7 3 2 4 4 2 3 7 1 1 1 1 1 1 1 1 7 3 2 4 4 2 3 7 2 3 4 0 1 8 7 3 2 3 4 0 1 8 7 3⎦ ⎥ ⎥ ⎥ ⎤ . Our newly constructed code given by this parity check matrix has a length of 16, from which 5 are parity check symbols, and 11 - information symbols. Again, we want to have the same number of information symbols as in code C (20, 16) with 4 parity check symbols and 16 information symbols correcting double ±1 errors. So, we need to add 5 additional columns to the matrix to have 16 information symbols. We found the corresponding 5 columns by computer search: Construction of Linear Codes over Rings 𝑍𝑍𝑚𝑚 Correcting Double ±1 or ±2 Errors 72 ⎣ ⎢ ⎢ ⎢ ⎡ 6 6 8 8 8 2 4 0 2 8 2 3 2 2 6 3 7 1 7 1 3 7 1 7 1⎦ ⎥ ⎥ ⎥ ⎤ . The code given by this parity check matrix 𝐻𝐻9 with 5 parity check symbols and 16 information symbols, can correct up to two errors of the type ±1 and ±2 with the same magnitude: 𝐻𝐻9 = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 1 1 1 8 7 6 5 4 3 2 1 6 6 8 8 8 7 6 5 4 3 2 1 0 2 2 2 2 2 2 2 2 2 4 0 2 8 7 3 2 4 4 2 3 7 7 3 2 4 4 2 3 7 2 3 2 2 6 1 1 1 1 1 1 1 1 7 3 2 4 4 2 3 7 3 7 1 7 1 2 3 4 0 1 8 7 3 2 3 4 0 1 8 7 3 3 7 1 7 1⎦ ⎥ ⎥ ⎥ ⎤ . In this case the number of error combinations for each code word that can be corrected is (1 + 21 ∗ 4 + (21𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 8) = 1765. As such, using this code 𝐶𝐶(21, 16) over the ring 𝑍𝑍9 correcting double ±1 and ±2 errors with the same magnitude, we can correct all 1765 errors which can occur in the code word. Again, in this case, similar to the 𝐶𝐶(17, 12) code over the ring 𝑍𝑍7 we have a quasi- optimal code. 4. Conclusion In this paper a construction of double ±1 and ±2 error correcting linear optimal code over the ring 𝑍𝑍5 and quasi-optimal codes over the rings 𝑍𝑍7 and 𝑍𝑍9 are constructed. We plan to investigate if the approach presented in this paper can be extended to construct codes for larger alphabets as well as to construct quasi-optimal codes with higher code rates. 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] A. J. Han Vinck and H. Morita, “Codes over the ring of integers modulo m”, IEICE Trans.Fundamentals , vol. E81-A, pp. 2013-2018, 1998. [4] 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. G. Khachatrian and H. Khachatrian 73 [5] G. Khachatrian and H. Khachatrian ”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. Submitted 26.10.2017, accepted 07.02.2018. ±𝟏𝟏 և ±𝟏𝟏 մեծությամբ կրկնակի սխալներ ուղղող գծային կոդերի կառուցումներ տարբեր մեծության 𝑍𝑍𝑚𝑚 օղակներում Գ. Խաչատրյան և Հ. Խաչատրյան Ամփոփում Այս հոդվածի շրջանակներում ներկայացված են 𝑍𝑍5, 𝑍𝑍7 և 𝑍𝑍9 օղակներում ±1 կամ ±2 միևնույն մեծությամբ կրկնակի սխալներ ուղղող օպտիմալ և քվազի-օպտիմալ կոդերի կառուցումներ: Построение кодов исправляющих двойные ошибки размера ±𝟏𝟏 и ±𝟏𝟏 в 𝑍𝑍𝑚𝑚 кольцах с разными величинами Г. Хачатрян и Г. Хачатрян Аннотация В данной статье представлено построение оптимальных и квази-оптимальных линейных кодов в кольцах 𝑍𝑍5, 𝑍𝑍7 и 𝑍𝑍9, исправляющих двойные ошибки размера ±1 и ±2 с одинаковыми величинами. Construction of Linear Codes over Rings ,𝑍-𝑚. Correcting Double ±1 or ±2 Errors Gurgen H. Khachatrian* and Hamlet K. Khachatrian ** In this paper a construction of double ±1 and ±2 errors correcting linear optimal and quasi-optimal codes over rings ,𝑍-5., ,𝑍-7. and ,𝑍-9. is presented with the limitation that both errors have the same amplitude in absolute value. ,,1-4-4-1-0-4-1-2-3-4-3-0-2-3-2...