RU2542665C1 - Device of data storage and transmission with detection and correction of errors in information bytes - Google Patents

Abstract

FIELD: information technologies.

SUBSTANCE: device comprises a memory unit, an input coding unit, an output coding unit, an error syndrome calculation unit, a decoder, a unit of error vector storage, a corrector, an AND element unit, units of OR elements, an element of non-equivalence.

EFFECT: increased fault tolerance of a device due to correction of errors in two bytes of information and detection of non-corrected errors.

1 dwg, 1 tbl, 1 app

Description

The invention relates to computer technology and can be used to increase the reliability of the storage devices.

A self-correcting device [1] is known that uses a correction code (the most frequently used Hamming code is that corrects a single error and detects a double error).

The disadvantage of this device is the low detecting ability of the code, since only double errors are detected.

The closest in technical solution is a device for storing and transmitting data with error correction in an information byte and error detection in information bytes [2], which contains a memory node, an input coding unit, an output coding unit, an error syndrome calculation unit, a decoder, a switch, a switch unit , corrector, corrector block, first block of OR elements, second block of OR elements, inverter, element AND, block of AND elements, input of setting the device to zero, write input, read input, address inputs, dv twenty-four bit information inputs, synchronization input, information outputs, error signal output, zero input, write input, read input, address inputs are connected respectively to the first, second, third and fourth inputs of the memory node, the synchronization input is connected to the fifth input of the memory node and to the first input of the block of AND elements, the information inputs are connected to the sixth inputs of the memory node and to the inputs of the input coding block, which generates the values of the control bits r ₁ , r ₂ , r ₃ , r ₄ , r ₅ , r ₆ , r ₇ , r ₈ by adding modulo 2 information symbols x ₁ x ₂ x ₃ , z ₁ z ₂ z ₃ , and ₁ a ₂ a ₃ , c ₁ c ₂ c ₃ , e ₁ e ₂ e ₃ , f ₁ f ₂ f ₃ , g ₁ g ₂ g ₃ , h ₁ h ₂ h ₃ received at the inputs of the input coding unit, in accordance with the rule: r ₁ = x ₁ ⊕z ₁ ⊕a ₁ ⊕c ₁ ⊕e ₁ ⊕f ₁ ⊕g ₁ ⊕h ₁ ; r ₂ = x ₂ ⊕z ₂ ⊕a ₂ ⊕c ₂ ⊕e ₂ ⊕f ₂ ⊕g ₂ ⊕h ₂ ; r ₃ = x ₃ ⊕z ₃ ⊕а ₃ ⊕с ₃ ⊕е ₃ ⊕f ₃ ⊕g ₃ ⊕h ₃ ; r ₄ = x ₁ ⊕z ₃ ⊕a ₂ ⊕ a ₃ ⊕ c ₂ ⊕ e ₁ ⊕ e ₃ ⊕ f ₁ ⊕ f ₂ ⊕g ₁ ⊕ g ₂ ⊕ g ₃ ; r ₅ = x ₂ ⊕ x ₃ ⊕ z ₁ ⊕ a ₃ ⊕ c ₁ ⊕ c ₃ ⊕e ₁ ⊕e ₂ ⊕ f ₂ ⊕g ₁ ⊕ g ₂ ⊕ g ₃ ; r ₆ = x ₃ ⊕ z ₂ ⊕ z ₃ © a ₁ ⊕ s ₁ ⊕ c ₂ ⊕ e ₂ ⊕ f ₁ ⊕ f ₃ ⊕g ₁ ⊕ g ₂ ⊕ g ₃ ; r ₇ = x ₃ ⊕ z ₃ ⊕ a ₁ ⊕ a ₃ ⊕ c ₂ ⊕ e ₁ ⊕ f ₂ ⊕g ₁ ⊕ g ₂ ⊕ g ₃ ; r ₈ = x ₁ ⊕ x ₂ ⊕ z ₂ ⊕ a ₂ ⊕ a ₃ ⊕ c ₃ ⊕ e ₃ ⊕ f ₂ ⊕ f ₃ ⊕ g ₁ ⊕ g ₂ ⊕ g ₃ , which are fed to the seventh inputs of the memory node, information outputs of the node memory are connected respectively to the first inputs of the corrector, the corrector block and the inputs of the output coding block, which generates the values of the test check bits r _1P , r _2P , r _3P , r _4P , r _5P , r _6P r _7P r _8P by modulo 2 information characters x _1P x _2P x _3P , z _1P z _2P z _3P , a _1P a _2P a _3P , c _1P c _2P c _3P , e _1P e _2P e _3P , f _1P f _2P f _3P , g _1P g _2P g _3P , h h _{1P 2P 3P} h is input to the input information encoding unit nnyh memory unit outputs, in accordance with the rule: r = x _{1P 1P 1P} ⊕z ⊕a ⊕s _{1P 1P 1P} ⊕e ⊕f ⊕g _{1P 1P 1P} ⊕h; r _2P = x _2P ⊕z _2P ⊕a _2P ⊕c _2P ⊕e _2P ⊕f _2P ⊕g _2P ⊕h _2P ; r _3P = x _3P ⊕z _3P ⊕a _3P ⊕s _3P ⊕e _3P ⊕f _3P ⊕g _3P ⊕h _3P ; r _4P = x _1P ⊕z _3P ⊕ a _2P ⊕ a _3P ⊕ s _2P ⊕ e _1P ⊕ e _3P ⊕ f _1P ⊕ f _2P ⊕g _1P ⊕ g _2P ⊕ g _3P ; r _5P = x _2P ⊕ x _3P ⊕ z _1P ⊕ a _3P ⊕ s _1P ⊕ s _3P ⊕e _1P ⊕e _2P ⊕ f _2P ⊕g _1P ⊕ g _2P ⊕ g _3P ; r _6P = x _3P ⊕ z _2P ⊕ z _3P ⊕ a _1P ⊕ s _1P ⊕ c _2P ⊕ e _2P ⊕ f _1P ⊕ f _3P ⊕g _1P ⊕ g _2P ⊕ g _3P ; r _7P = x _3P ⊕ z _3P ⊕ a _1P ⊕ a _3P ⊕ C _2P ⊕ e _1P ⊕ f _2P ⊕g _1P ⊕ g _2P ⊕ g _3P ; r _8P = x _1P ⊕ x _2P ⊕ z _2P ⊕ a _2P ⊕ a _3P ⊕ s _3P ⊕ e _3P ⊕ f _2P ⊕f _3P ⊕g _1P ⊕ g _2P ⊕ g _3P , the outputs of the output coding unit are connected to the first inputs of the syndrome calculation unit errors, to the second inputs of which the outputs of the control bits of the memory node are connected, the first outputs of the error syndrome calculation unit are connected to the first inputs of the decoder, to the first inputs of the switch, to the inputs of the first block of OR elements and to the first inputs of the switch block, the second outputs of the error syndrome calculation unit to the second inputs of the decoder and to the second inputs ne of the first block of OR elements, the outputs of the decoder are connected to the inputs of the second block of OR elements, the first output of the decoder is connected to the second input of the switch, the second outputs are connected to the second inputs of the block of switches, the output of the second block of OR elements through the inverter is connected to the first input of the AND element, the second input of which is connected to the output of the first block of OR elements, the output of the AND element is the output of the "error" signal, the outputs of the switch are connected to the second inputs of the corrector, the outputs of the block of switches are connected to the second correctors inputs, outputs, and corrector correctors block unit are connected to second inputs of the AND block whose outputs are information device outputs.

The disadvantage of this device is the low corrective ability of errors, since only single error bytes are corrected.

The aim of the invention is to increase the fault tolerance of the device due to error correction in two bytes of information and detection of non-correctable errors.

, $$r_2^f$$

, $$r_3^f$$

, $$r_4^f$$

, $$r_5^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{11}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{14}^g$$

, $$r_{15}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{18}^g$$

, $$r_{19}^g$$

, $$r_{20}^g$$

путем сложения по модулю 2 информационных символов а₀ a₁ а₂ а₃, b₀ b₁ b₂ b₃, c₀ c₁ c₂ c₃, d₀ d₁ d₂ d₃, e₀ e₁ е₂ e₃, f₀ f₁ f₃, g₀ g₁ g₂ g₃, h₀ h₁ h₂ h₃, i₀ i₁ i₂ i₃, j₀ j₁ j₂ j₃, k₀ k₁ k₂ k₃, l₀ l₁ l₂ l₃, m₀ m₁ m₂ m₃, n₀ n₁ n₂ n₃, o₀ o₁ o₂ o₃, p₀ p₁ p₂ p₃, поступающих на входы входного блока кодирования, в соответствии с правилом:This goal is achieved in that the device containing the memory node, the input coding unit, the output coding unit, the error syndrome calculation unit, the decoder, the corrector, the block of AND elements, the input of setting the device to zero, the write input, read input, address inputs, information inputs, synchronization input, information outputs, characterized in that it further comprises an error vector storage unit, a first block of OR elements, a second block of OR elements, an ambiguity element, an input to the zero standing, write input, read input, address inputs are connected respectively to the first, second, third and fourth inputs of the memory node, the synchronization input is connected to the fifth input of the memory node and to the first input of the AND block, information inputs are connected to the sixth inputs of the memory node and to the inputs of the input coding block, which generates the values of the control bits $$r_{\mathrm{one}}^f$$

, $$r_2^f$$

, $$r_3^f$$

, $$r_{\mathrm{four}}^f$$

, $$r_5^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{\mathrm{eleven}}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{\mathrm{fourteen}}^g$$

, $$r_{\mathrm{fifteen}}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{\mathrm{eighteen}}^g$$

, $$r_{19}^g$$

, $$r_{\mathrm{twenty}}^g$$

by adding modulo 2 information symbols a ₀ a ₁ a ₂ a ₃ , b ₀ b ₁ b ₂ b ₃ , c ₀ c ₁ c ₂ c ₃ , d ₀ d ₁ d ₂ d ₃ , e ₀ e ₁ e ₂ e ₃ , f ₀ f ₁ f ₃ , g ₀ g ₁ g ₂ g ₃ , h ₀ h ₁ h ₂ h ₃ , i ₀ i ₁ i ₂ i ₃ , j ₀ j ₁ j ₂ j ₃ , k ₀ k ₁ k ₂ k ₃ , l ₀ l ₁ l ₂ l ₃ , m ₀ m ₁ m ₂ m ₃ , n ₀ n ₁ n ₂ n ₃ , o ₀ o ₁ o ₂ o ₃ , p ₀ p ₁ p ₂ p ₃ to the inputs of the input coding block, in accordance with the rule:

, $$r_{2П}^f$$

, $$r_{3П}^f$$

, $$r_{4П}^f$$

, $$r_{5П}^f$$

, $$r_{6П}^f$$

, $$r_{7П}^f$$

, $$r_{8П}^f$$

, $$r_{9П}^g$$

, $$r_{10П}^g$$

, $$r_{11П}^g$$

, $$r_{12П}^g$$

, $$r_{13П}^g$$

, $$r_{14П}^g$$

, $$r_{15П}^g$$

, $$r_{16П}^g$$

, $$r_{17П}^g$$

, $$r_{18П}^g$$

, $$r_{19П}^g$$

$$r_{20П}^g$$

путем сложения по модулю 2 информационных символов а_0П a_1П а_2П а_3П, b_0П b_1П b_2П b_3П, с_0П с_1П с_2П с_3П, d_0П d_1П d_2П d_3П, е_0П е_1П е_2П е_3П, f_0П f_1П f_2П f_3П, g_0П g_1П g_2П g_3П, h_0П h_1П h_2П h_3П, i_0П i_1П i_2П i_3П, j_0П j_1П j_2П j_3П, k_0П k_1П k_2П k_3П, l_0П, l_1П l_2П l_3П, m_0П m_1П m_2П m_3П, n_0П n_1П n_2П n_3П, о_0П о_1П о_2П о_3П, р_0П р_1П р_2П р_3П, поступающих на входы входного блока кодирования с информационных выходов узла памяти, в соответствии с правилом:the outputs of the input coding block are connected to the seventh inputs of the memory node, the information outputs of the memory node are connected respectively to the first inputs of the corrector and to the inputs of the output coding block, which generates the values of the test control bits $$r_{\mathrm{one}P}^f,$$

, $$r_{2P}^f$$

, $$r_{3P}^f$$

, $$r_{\mathrm{four}P}^f$$

, $$r_{5P}^f$$

, $$r_{6P}^f$$

, $$r_{7P}^f$$

, $$r_{8P}^f$$

, $$r_{9P}^g$$

, $$r_{10P}^g$$

, $$r_{\mathrm{eleven}P}^g$$

, $$r_{12P}^g$$

, $$r_{13P}^g$$

, $$r_{\mathrm{fourteen}P}^g$$

, $$r_{\mathrm{fifteen}P}^g$$

, $$r_{16P}^g$$

, $$r_{17P}^g$$

, $$r_{\mathrm{eighteen}P}^g$$

, $$r_{19P}^g$$

$$r_{\mathrm{twenty}P}^g$$

by adding modulo 2 information symbols a _0P a _1P a _2P a _3P , b _0P b _1P b _2P b _3P , s _0P s _1P s _2P s _3P , d _0P d _1P d _2P d _3P , e _0P e _1P e _2P e _3P , f _0P f _1P f _2P f _3P , g _0P g _1P g _2P g _3P , h _0P h _1P h _2P h _3P , i _0P i _1P i _2P i _3P , j _0P j _1P j _2P j _3P , k _0P k _1P k _2P k _3P , l _0P , l _1P l _2P l _3P , m _0P m _1P m _2P m _3P , n _0P n _1P n _2P n _3P , o _0P about _1P o _2P about _3P , p _0P p _1P p _2P p _3P received at the inputs of the input coding block from the information outputs of the memory node, in accordance with the rule:

, выходы выходного блока кодирования подключены к первым входам блока вычисления синдрома ошибки, к вторым входам которого подключены выходы контрольных разрядов узла памяти, выходы блока вычисления синдрома ошибки подключены к входам первого блока элементов ИЛИ и к входам дешифратора, выходы которого подключены к входам второго блока элементов ИЛИ и к входам блока хранения векторов ошибок, выходы блока хранения векторов ошибок подключены к вторым входам корректора, выходы которого подключены к вторым входам блока элементов И, выходы первого и второго блоков элементов ИЛИ подключены к входам элемента неравнозначности, выход которого подключен к третьему входу блока элементов И, первые выходы блока элементов И являются информационными выходами устройства, а второй выход блока элементов И является выходом «отказ устройства».

, the outputs of the output coding unit are connected to the first inputs of the error syndrome calculation unit, the outputs of the control bits of the memory node are connected to its second inputs, the outputs of the error syndrome calculation unit are connected to the inputs of the first block of OR elements and to the inputs of the decoder whose outputs are connected to the inputs of the second block of elements OR to the inputs of the error vector storage unit, the outputs of the error vector storage unit are connected to the second inputs of the corrector, the outputs of which are connected to the second inputs of the AND element block, the outputs are The first and second blocks of elements OR are connected to the inputs of the element of ambiguity, the output of which is connected to the third input of the block of elements AND, the first outputs of the block of elements AND are information outputs of the device, and the second output of the block of elements AND is the output “device failure”.

Figure 1 presents a block diagram of a device. A device for storing and transmitting data with error correction in two bytes of information contains: a memory unit 1, an encoding input unit 2, an encoding output unit 3, an error syndrome calculation unit 4, a decoder 5, an error vector storage unit 6, a corrector 7, a block of 8 AND elements , the first block 9 of the OR elements, the second block 10 of the OR elements, the element 11 of ambiguity, the input 12 is set to the zero state, the input 13 records, input 14 reads, address inputs 15, information inputs 16, synchronization input 17, information outputs 18, output 19 “Device failure” .

, $$r_2^f$$

, $$r_3^f$$

, $$r_4^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{11}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{14}^g$$

, $$r_{15}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{18}^g$$

, $$r_{19}^g$$

, $$r_{20}^g$$

, путем сложения по модулю 2 информационных символов а₀ a₁ а₂ а₃, b₀ b₁ b₂ b₃, c₀ c₁ c₂ c₃, d₀ d₁ d₂ d₃, e₀ e₁ е₂ е₃, f₀ f₁ f₂ f₃, g₀ g₁ g₂ g₃, h₀ h₁ h₂ h₃, i₀ i₁ i₂ i₃, j₀ j₁ j₂ j₃, k₀ k₁ k₂ k₃, l₀ l₁ l₂ l₃, m₀ m₁ m₂ m₃, n₀ n₁ n₂ n₃, o₀ o₁ o₂ o₃, р₀ p₁ р₂ p₃, поступающих на входы входного блока 2 кодирования, в соответствии с правилом:The input of the zeroing state 12, the write input 13, the read input 14, the address inputs 15 are connected respectively to the first, second, third and fourth inputs of the memory node 1, the synchronization input 17 is connected to the fifth input of the memory node 1 and to the first input of the block of 8 elements And, the information inputs 16 are connected to the sixth inputs of the memory node 1 and to the inputs of the encoding input unit 2, which generates the values of the control bits $$r_{\mathrm{one}}^f$$

, $$r_2^f$$

, $$r_3^f$$

, $$r_{\mathrm{four}}^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{\mathrm{eleven}}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{\mathrm{fourteen}}^g$$

, $$r_{\mathrm{fifteen}}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{\mathrm{eighteen}}^g$$

, $$r_{19}^g$$

, $$r_{\mathrm{twenty}}^g$$

, by adding modulo 2 information symbols a ₀ a ₁ a ₂ a ₃ , b ₀ b ₁ b ₂ b ₃ , c ₀ c ₁ c ₂ c ₃ , d ₀ d ₁ d ₂ d ₃ , e ₀ e ₁ e ₂ e ₃ , f ₀ f ₁ f ₂ f ₃ , g ₀ g ₁ g ₂ g ₃ , h ₀ h ₁ h ₂ h ₃ , i ₀ i ₁ i ₂ i ₃ , j ₀ j ₁ j ₂ j ₃ , k ₀ k ₁ k ₂ k ₃ , l ₀ l ₁ l ₂ l ₃ , m ₀ m ₁ m ₂ m ₃ , n ₀ n ₁ n ₂ n ₃ , o ₀ o ₁ o ₂ o ₃ , p ₀ p ₁ p ₂ p ₃ , arriving at the inputs of the input coding block 2, in accordance with the rule:

$$r_{2П}^f$$

, $$r_{3П}^f$$

, $$r_{4П}^f$$

, $$r_{5П}^f$$

, $$r_{6П}^f$$

, $$r_{7П}^f$$

, $$r_{8П}^f$$

, $$r_{9П}^g$$

, $$r_{10П}^g$$

, $$r_{11П}^g$$

, $$r_{12П}^g$$

, $$r_{13П}^g$$

, $$r_{14П}^g$$

, $$r_{15П}^g$$

, $$r_{16П}^g$$

, $$r_{17П}^g$$

, $$r_{18П}^g$$

, $$r_{19П}^g$$

, $$r_{20П}^g$$

путем сложения по модулю 2 информационных символов а_0П a_1П а_2П а_3П, b_0П b_1П b_2П b_3П, с_0П с_1П с_2П с_3П, d_0П d_1П d_2П d_3П, е_0П е_1П е_2П е_3П, f_0П f_1П f_2П f_3П, g_0П g_1П g_2П g_3П, h_0П h_1П h_2П h_3П, i_0П i_1П i_2П i_3П, j_0П j_1П j_2П j_3П, k_0П k_1П k_2П k_3П, l_0П l_1П l_2П l_3П, m_0П m_1П m_2П m_3П, n_0П n_1П n_2П n_3П, о_0П о_1П о_2П о_3П, р_0П р_1П р_2П р_3П, поступающих на входы входного блока 3 кодирования с информационных выходов узла 1 памяти, в соответствии с правилом:the outputs of the input coding unit 2 are connected to the seventh inputs of the memory unit 1, the information outputs of the memory unit 1 are connected respectively to the first inputs of the corrector 7 and to the inputs of the output coding unit 3, which generates the values of the test control bits $$r_{\mathrm{one}P}^f,$$

$$r_{2P}^f$$

, $$r_{3P}^f$$

, $$r_{\mathrm{four}P}^f$$

, $$r_{5P}^f$$

, $$r_{6P}^f$$

, $$r_{7P}^f$$

, $$r_{8P}^f$$

, $$r_{9P}^g$$

, $$r_{10P}^g$$

, $$r_{\mathrm{eleven}P}^g$$

, $$r_{12P}^g$$

, $$r_{13P}^g$$

, $$r_{\mathrm{fourteen}P}^g$$

, $$r_{\mathrm{fifteen}P}^g$$

, $$r_{16P}^g$$

, $$r_{17P}^g$$

, $$r_{\mathrm{eighteen}P}^g$$

, $$r_{19P}^g$$

, $$r_{\mathrm{twenty}P}^g$$

by adding modulo 2 information symbols a _0P a _1P a _2P a _3P , b _0P b _1P b _2P b _3P , s _0P s _1P s _2P s _3P , d _0P d _1P d _2P d _3P , e _0P e _1P e _2P e _3P , f _0P f _1P f _2P f _3P , g _0P g _1P g _2P g _3P , h _0P h _1P h _2P h _3P , i _0P i _1P i _2P i _3P , j _0P j _1P j _2P j _3P , k _0P k _1P k _2P k _3P , l _0P l _1P l _2P l _3P , m _0P m _1P m _2P m _3P , n _0P n _1P n _2P n _3P , o _0P about _1P o _2P about _3P , p _0P p _1P p _2P p _3P arriving at the inputs of the input coding unit 3 from the information outputs of the memory node 1, in accordance with the rule:

, выходы выходного блока 3 кодирования подключены к первым входам блока 4 вычисления синдрома ошибки, к вторым входам которого подключены выходы контрольных разрядов узла 1 памяти, выходы блока 4 вычисления синдрома ошибки подключены к входам первого блока 9 элементов ИЛИ и к входам дешифратора 5, выходы которого подключены к входам второго блока 10 элементов ИЛИ и к входам блока 6 хранения векторов ошибок, выходы блока 6 хранения векторов ошибок подключены к вторым входам корректора 7, выходы которого подключены к вторым входам блока 8 элементов И, выходы первого 9 и второго 10 блоков элементов ИЛИ подключены к входам элемента 11 неравнозначности, выход которого подключен к третьему входу блока 8 элементов И, первые выходы блока 8 элементов И являются информационными выходами 18 устройства, а второй выход 19 блока 8 элементов И является выходом «отказ устройства».

, the outputs of the output coding unit 3 are connected to the first inputs of the error syndrome calculation unit 4, the outputs of the control bits of the memory unit 1 are connected to its second inputs, the outputs of the error syndrome calculation unit 4 are connected to the inputs of the first block 9 of OR elements and to the inputs of the decoder 5, the outputs of which connected to the inputs of the second block of 10 elements OR and to the inputs of block 6 for storing error vectors, the outputs of block 6 for storing error vectors are connected to the second inputs of corrector 7, the outputs of which are connected to the second inputs of block 8 in AND, the outputs of the first 9 and second 10 blocks of OR elements are connected to the inputs of the element 11 of ambiguity, the output of which is connected to the third input of the block of 8 elements AND, the first outputs of the block of 8 elements AND are information outputs 18 of the device, and the second output 19 of the block of 8 elements AND is the “device failure” output.

, $$r_2^f$$

, $$r_3^f$$

, $$r_4^f$$

, $$r_5^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{11}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{14}^g$$

, $$r_{15}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{18}^g$$

, $$r_{19}^g$$

, $$r_{20}^g$$

, полученных при кодировании исходных шестидесяти четырех разрядных двоичных наборов.The memory node 1, in this case, is a static semiconductor operational memory device and is designed to store code sets: _K = a ₀ a ₁ a ₂ a ₃ , b ₀ b ₁ b ₂ b ₃ , c ₀ c ₁ c ₂ c ₃ , d ₀ d ₁ d ₂ d ₃ , e ₀ e ₁ e ₂ e ₃ , f ₀ f ₁ f ₂ f ₃ , g ₀ g ₁ g ₂ g ₃ , h ₀ h ₁ h ₂ h ₃ , i ₀ i ₁ i ₂ i ₃ , j ₀ j ₁ j ₂ j ₃ , k ₀ k ₁ k ₂ k ₃ , l ₀ l ₁ l ₂ l ₃ , m ₀ m ₁ m ₂ m ₃ , n ₀ n ₁ n ₂ n ₃ , o ₀ o ₁ o ₂ o ₃ , p ₀ p ₁ p ₂ p ₃ , $$r_{\mathrm{one}}^f$$

, $$r_2^f$$

, $$r_3^f$$

, $$r_{\mathrm{four}}^f$$

, $$r_5^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{\mathrm{eleven}}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{\mathrm{fourteen}}^g$$

, $$r_{\mathrm{fifteen}}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{\mathrm{eighteen}}^g$$

, $$r_{19}^g$$

, $$r_{\mathrm{twenty}}^g$$

obtained by encoding the original sixty-four bit binary sets.

, $$r_2^f$$

, $$r_3^f$$

, $$r_4^f$$

, $$r_5^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{11}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{14}^g$$

, $$r_{15}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{18}^g$$

, $$r_{19}^g$$

, $$r_{20}^g$$

, путем сложения по mod2 информационных символов в соответствии с правилом::The input coding unit 2 is intended for generating control bit values $$r_{\mathrm{one}}^f$$

, $$r_2^f$$

, $$r_3^f$$

, $$r_{\mathrm{four}}^f$$

, $$r_5^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{\mathrm{eleven}}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{\mathrm{fourteen}}^g$$

, $$r_{\mathrm{fifteen}}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{\mathrm{eighteen}}^g$$

, $$r_{19}^g$$

, $$r_{\mathrm{twenty}}^g$$

, by adding mod2 information symbols in accordance with the rule ::

$$r_{2П}^f$$

, $$r_{3П}^f$$

, $$r_{4П}^f$$

, $$r_{5П}^f$$

, $$r_{6П}^f$$

, $$r_{7П}^f$$

, $$r_{8П}^f$$

, $$r_{9П}^g$$

, $$r_{10П}^g$$

, $$r_{11П}^g$$

, $$r_{12П}^g$$

, $$r_{13П}^g$$

, $$r_{14П}^g$$

, $$r_{15П}^g$$

, $$r_{16П}^g$$

, $$r_{17П}^g$$

, $$r_{18П}^g$$

, $$r_{19П}^g$$

, $$r_{20П}^g$$

, путем сложения по модулю 2 информационных символов а_0П a_1П а_2П а_3П, b_0П b_1П b_2П b_3П, с_0П с_1П с_2П с_3П, d_0П d_1П d_2П d_3П, е_0П е_1П е_2П е_3П, f_0П f_1П f_2П f_3П, g_0П g_1П g_2П g_3П, h_0П h_1П h_2П h_3П, i_0П i_1П i_2П i_3П, j_0П j_1П j_2П j_3П, k_0П k_1П k_2П k_3П, l_0П l_1П l_2П l_3П, m_0П m_1П m_2П m_3П, n_0П n_1П n_2П n_3П, о_0П о_1П о_2П о_3П, р_0П р_1П р_2П р_3П, поступающих на входы входного блока 3 кодирования с информационных выходов узла 1 памяти, в соответствии с правилом:The output coding unit 3 is designed to generate the values of the test check bits $$r_{\mathrm{one}P}^f,$$

$$r_{2P}^f$$

, $$r_{3P}^f$$

, $$r_{\mathrm{four}P}^f$$

, $$r_{5P}^f$$

, $$r_{6P}^f$$

, $$r_{7P}^f$$

, $$r_{8P}^f$$

, $$r_{9P}^g$$

, $$r_{10P}^g$$

, $$r_{\mathrm{eleven}P}^g$$

, $$r_{12P}^g$$

, $$r_{13P}^g$$

, $$r_{\mathrm{fourteen}P}^g$$

, $$r_{\mathrm{fifteen}P}^g$$

, $$r_{16P}^g$$

, $$r_{17P}^g$$

, $$r_{\mathrm{eighteen}P}^g$$

, $$r_{19P}^g$$

, $$r_{\mathrm{twenty}P}^g$$

, by adding modulo 2 information symbols a _0P a _1P a _2P a _3P , b _0P b _1P b _2P b _3P , s _0P from _1P with _2P with _3P , d _0P d _1P d _2P d _3P , e _0P e _1P e _2P e _3P , f _0P f _1P f _2P f _3P , g _0P g _1P g _2P g _3P , h _0P h _1P h _2P h _3P , i _0P i _1P i _2P i _3P , j _0P j _1P j _2P j _3P , k _0P k _1P k _2P k _3P , l _0P l _1P l _2P l _3P , m _0P m _1P m _2P m _3P , n _0P n _1P n _2P n _3P , o _0P about _1P o _2P about _3P , p _0P p _1P p _2P p _3P received at the inputs of the input coding unit 3 from the information outputs of the memory node 1, in accordance with the rule:

, $$r_2^f$$

, $$r_3^f$$

, $$r_4^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{11}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{14}^g$$

, $$r_{15}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{18}^g$$

, $$r_{19}^g$$

, $$r_{20}^g$$

, считываемых с вторых выходов узла 1 памяти, соответственно с значениями контрольных разрядов $$r_{1П}^f$$

, $$r_{2П}^f$$

, $$r_{3П}^f$$

, $$r_{4П}^f$$

, $$r_{5П}^f$$

, $$r_{6П}^f$$

, $$r_{7П}^f$$

, $$r_{8П}^f$$

, $$r_{9П}^g$$

, $$r_{10П}^g$$

, $$r_{11П}^g$$

, $$r_{12П}^g$$

, $$r_{13П}^g$$

, $$r_{14П}^g$$

, $$r_{15П}^g$$

, $$r_{16П}^g$$

, $$r_{17П}^g$$

, $$r_{18П}^g$$

, $$r_{19П}^g$$

, $$r_{20П}^g$$

, сформированных на выходах выходного блока 3 кодирования.Block 4 of the calculation of the error syndrome is designed to detect errors in the code set when reading information from the memory node 1 by adding mod2 values of the control bits $$r_{\mathrm{one}}^f$$

, $$r_2^f$$

, $$r_3^f$$

, $$r_{\mathrm{four}}^f$$

, $$r_6^f$$

, $$r_7^f$$

, $$r_8^f$$

, $$r_9^g$$

, $$r_{10}^g$$

, $$r_{\mathrm{eleven}}^g$$

, $$r_{12}^g$$

, $$r_{13}^g$$

, $$r_{\mathrm{fourteen}}^g$$

, $$r_{\mathrm{fifteen}}^g$$

, $$r_{16}^g$$

, $$r_{17}^g$$

, $$r_{\mathrm{eighteen}}^g$$

, $$r_{19}^g$$

, $$r_{\mathrm{twenty}}^g$$

read from the second outputs of the memory node 1, respectively, with the values of the control bits $$r_{\mathrm{one}P}^f$$

, $$r_{2P}^f$$

, $$r_{3P}^f$$

, $$r_{\mathrm{four}P}^f$$

, $$r_{5P}^f$$

, $$r_{6P}^f$$

, $$r_{7P}^f$$

, $$r_{8P}^f$$

, $$r_{9P}^g$$

, $$r_{10P}^g$$

, $$r_{\mathrm{eleven}P}^g$$

, $$r_{12P}^g$$

, $$r_{13P}^g$$

, $$r_{\mathrm{fourteen}P}^g$$

, $$r_{\mathrm{fifteen}P}^g$$

, $$r_{16P}^g$$

, $$r_{17P}^g$$

, $$r_{\mathrm{eighteen}P}^g$$

, $$r_{19P}^g$$

, $$r_{\mathrm{twenty}P}^g$$

formed at the outputs of the output coding unit 3.

The result of bitwise addition:

A zero result of the sum indicates the absence of an error, and its presence otherwise.

The decoder 5 generates a single signal value at one of its outputs in accordance with the value of the error syndrome (generates an error vector address in the error vector storage unit 6).

Table 1 presents a part of the values of the error syndromes for code 84, 20.

Note: In Table 1, the values of information bits, control bits, and error values in information bytes are presented in the hexadecimal number system, and the values of the error syndrome are presented in binary.

The unit for storing error vectors 6 is designed to store the values of the error vectors in accordance with the values of the error syndromes (the error vector has single signal values in those bits of the code set in which the error occurred).

The corrector 7 is designed to correct the corrected error by adding mod2 of the same category bits of the information block having an error with the value of the error vector.

The first 9, second 10 blocks of OR elements, element 11 of ambiguity are designed to generate a signal “device failure” in the presence of a single signal at the output of the first block of 9 OR elements and in the absence of a single signal at the output of the second block of 10 OR elements and vice versa.

The device operates as follows. Before starting the operation of the device to the input 12 "set to zero state" is a single signal, which puts the device into zero state.

When recording information in the memory node 1, single signals are supplied to the synchronization input 17, the recording input 13, the address inputs 15 and the information inputs 16.

Let's say you need to encode a binary set:

Then the values of the control bits formed relative to the received set by the input coding unit 2 have zero values, i.e. we have a code set:

If there is no error, the value of the code set recorded in the memory node 1 is equal to the read value (transmitted to the code set):

In this case, at the output of the error syndrome calculation unit 4, we have zero signal values.

Let there be a single error in the fourth bit of the sixteenth block of information (P = 0001 ^* ), then the output coding block 3 will generate, relative to the received code set, the values of the control bits:

In block 4 of the calculation of the error syndrome, the transmitted control bits with the control bits formed relative to the received code set are added up, as a result, we obtain the error syndrome S:

In this case, the error syndrome indicates the fourth error category of block P (the second row of Table 1).

At the output of the decoder 5, a single signal value appears, which generates an address for reading the error vector value from the error vector storage unit 6 in accordance with the value of the error syndrome.

In this case, the value of the error vector is fed to the inputs of the corrector 7, where it is added mod2 with the values of the information bits. As a result, we have the correct value of the information.

Errors that occur in other single and double bytes of information are similarly corrected.

The occurrence of an uncorrectable error (the presence of a single signal value at least at one output of the error syndrome calculation unit 4) and the absence of a single signal at the outputs of the decoder 5 leads to the appearance of a single signal at the output of the first block of 9 OR elements and a zero signal value at the output of the second block of 10 OR elements . In this case, a single signal value appears at the output of the discontinuity element 11, which indicates the presence of an uncorrectable error (device failure).

INFORMATION SOURCES

1. Scherbakov N.S. The reliability of digital devices. M.: Engineering, 1989, p. 82, fig. 39, 224 p.

2. RF patent for the invention No. 2448359 "Device for storing and transmitting data with error correction in the byte of information and detection of errors in the bytes of information" / Borisov K.Yu., Malofeev Yu.G., Osipenko PN, Pavlov A.A ., Pavlov A.A., Pavlov P.A., Tsarkov A.N., Khruzhenko O.V. Date of issue: 04/20/2012

APPENDIX

1. Introduction and statement of the problem

In many cases, error detection and correction codes are used with the detection and correction of error bytes (in this case, the error byte is understood to be errors whose multiplicity does not exceed the number of bits b of the information block).

These codes include codes [1]:

- correcting single errors and detecting single bytes of errors;

- codes correcting single errors, detecting double independent errors and detecting single bytes of errors;

-codes correcting single error bytes;

-codes correcting single and detecting double bytes of errors.

Reed-Solomon codes are widely used, having cyclic properties and having the highest detecting and correcting ability.

The Reed-Solomon (PC) code is a block code (w, N) that allows you to detect and correct errors in bytes. The input word for it is a block of w bytes, the output is a code word of N bytes, consisting of w source and N-w test bytes. It is guaranteed that during decoding, t = (N-w) / 2 bytes will be detected and corrected in the codeword, regardless of their location inside the codeword. The PC encoder is implemented based on a shift register with 2t byte memory elements and feedbacks. The process of encoding and decoding is reduced to the operations of addition and multiplication modulo.

The use of these codes is associated with large time costs, which is a significant drawback in their use for systems operating in real time, so there is a need to develop a simpler linear procedure for constructing corrective codes that solve this problem.

2. Development of a linear correction code with error correction in two bytes of information

A method is proposed for constructing a correction code that corrects errors in two bytes of information that implements a linear procedure for constructing a correction code with syndromic decoding.

Information Encoding Rules

Rule 2.1 The binary set Y containing k information symbols is divided into w = k / b bytes of information (byte of information is the number of information bits that do not exceed the value of b, and let b be a multiple of k).

An error byte means errors whose multiplicity does not exceed the number of bits b of the information block.

As a result, a binary set can be represented as:

Definition 2.1. The error vector obtained with respect to the addition of the same bits of the transmitted and received bytes of information will be called the additive error vector.

Rule 2.2. For the formation of the first additive error vector, we will add mod2 bytes of information by the same name bits starting from the first through (b-1) - an information block, and to form the second additive error vector we will add mod2 of information bytes of the same name bits starting from the second to b - an information block (we will perform the interleaving operation) and add the result of the summation to the binary set Y.

As a result, we obtain the code set Y _K1 :

To correct erroneous bits of information, it becomes necessary to form a set of checks (develop a rule for encoding information), which allows to determine a block (byte) of information containing an error.

To this end, we encode information blocks using w encoding matrices.

Property 2.1 Each coding matrix contains g _H = [log ₂ (k + 1)] sink for an odd value of b and g _× = [log ₂ (k + 1)] + 1 for an even value of b.

Property 2.2 Each row of the encoding matrix contains b bits.

Note: Square brackets mean rounding the result up.

Rule 2.3. Let us represent the rows of coding matrices of the same name with a binary set corresponding to one of the values of the set {2 ^b } so that the result of checking the parity of the rows of the coding matrix in the binary set forms the number u _i belonging to the set {2 g _H } with an odd value of b set {2 g _Ч } - with even b, and for this, the condition u _j- -u _i ≥2t was fulfilled for the obtained numbers.

Rule 2.4 Values of control checks (values of control bits) of the coding matrix are formed by adding mod2 to the elements of the matrix rows having unit values.

Property 2.3 To exclude the coincidence of error syndromes (for k = b2 ^b ), the second part of the error syndromes requires r _gЧ = [log ₂ (2b2 ^b ) +1] - control bits for an even value of b, and r _gH = log ₂ (2b2 ^b ) - with odd.

In this case, the number of additional control bits (rows of the coding matrix) will be r _SECD = [log ₂ (2b2 ^b ) + 1-b] for an even value of b, and r _SECD = [log ₂ (2b2 ^b ) -b] for odd.

The boundary of the number of check bits for a code that corrects errors in two bytes of information with the formation of an additive error vector is estimated by the expression:

Rule 2.5 Combining mod2 of the same name checks for all coding matrices, we obtain the values of the second part of the control bits

Thus, we have a regular procedure for constructing a code set with additive formation of an error vector:

, $$r_{i2}^f$$

, $$r_i^g$$

и контрольных разрядов $$r_{i1}^{fП}$$

, $$r_{i2}^{fП}$$

, $$r_i^{gП}$$

, сформированных относительно полученных информационных разрядов, даст значение синдрома ошибки, включающего две части:The result of mod2 addition of the transmitted values of the control bits $$r_{i\mathrm{one}}^f$$

, $$r_{i2}^f$$

, $$r_i^g$$

and control bits $$r_{i\mathrm{one}}^{fP}$$

, $$r_{i2}^{fP}$$

, $$r_i^{gP}$$

formed relative to the received information bits will give the value of the error syndrome, which includes two parts:

, $$S_2^f$$

представляют собой аддитивные векторы ошибки (указывают ошибочные разряды в блоках информации), а значение синдрома ошибки S^g определяет номера ошибочных блоков (байтов) информации.Error Syndrome Values $$S_{\mathrm{one}}^f$$

, $$S_2^f$$

represent additive error vectors (indicate erroneous bits in information blocks), and the value of the error syndrome S ^g determines the numbers of error information blocks (bytes).

Property 2.4 The occurrence of errors in adjacent bytes of information leads to distortion of error vectors.

Corollary 2.1 When errors occur in adjacent bytes, error vectors are generated in accordance with the error syndrome.

Decoding rule 2.6 includes the following strategy:

Similarly, a code is constructed that corrects errors in a given n-number of bytes of information (n≤b).

The boundary of the number of control bits of the correction code that corrects errors in a given number of bytes of information (with an odd value of b) is estimated by the expression:

If b is even, one is added to this expression.

Thus, the proposed error correction method in a given number of bytes of information with additive formation of an error vector has a regular and relatively simple matrix coding procedure. It allows to reduce the time spent on encoding and decoding information (to exclude a cyclic encoding procedure).

With respect to the Reed-Solomon code, it eliminates the time spent on finding the roots of the error locator polynomial. So, to solve the key equation of the PC code (78.8) according to the Euclidean algorithm, 96 clock cycles of the decoding device will be required.

The time spent on coding information using the proposed method is comparable to the time taken to control information for parity (requiring minimal time consumption), which makes it possible to ensure the operation of the data transmission channel in real time.

The proposed method allows to reduce hardware costs for the construction of a decoding device, because in most cases, it does not require hardware costs for calculating the error vector.

Using the proposed method allows to increase the reliability of the transmitted information by detecting uncorrectable errors. Unlike PC codes, which use the least degree of error polynomial correction (when implementing decoding using the "maximum likelihood" method), which in some cases leads to erroneous correction.

Example 2. Suppose you want to perform error correction in two bytes of information of multiplicity 4, in a binary set containing 64 information bits, i.e. build code (84, 20).

, $$r_2^g$$

… $$r_{ДОПi}^g$$

(табл.2.1).Using the obtained rules, we construct information coding matrices for the formation of the second part of the control bits: - $$r_{\mathrm{one}}^g$$

, $$r_2^g$$

... $$r_{D\mathrm{ABOUT}Pi}^g$$

(table 2.1).

Control checks (values of the second part of the control bits) obtained relative to the received coding matrices are of the form:

Table 2.2 shows a part of the values of the error syndromes for code 84.20.

Note: in Table 2.2, the values of information bits, control bits and error values in information bytes are presented in the hexadecimal number system, and the values of the error syndrome are presented in binary.

Analysis of the table shows that 94% of error syndromes have different meanings, i.e. 6% of errors in two blocks of information are not corrected.

The introduction of additional control bits allows the correction of up to 100% of errors, but this leads to a significant increase in hardware costs, so it is advisable to limit the correction of this number of errors.

Thus, the developed error correction method in two bytes of information differs from the existing ones in that it allows:

- carry out error correction with algebraic-syndromic decoding (exclude the cyclic procedure for encoding and decoding information);

- has a regular and relatively simple procedure for encoding information;

- reduce the time spent on coding and decoding information and ensure the operation of the data channel in real time.

Literature

1. Scherbakov N.S. The reliability of digital devices. M.: Engineering, 1989, p. 122, Fig. 45, 224 p.

Claims (1)

A device for storing and transmitting data with the detection and correction of errors in bytes of information, containing a memory node, an input coding unit, an output coding unit, an error syndrome calculation unit, a decoder, an corrector, a block of AND elements, a device zero setting input, a recording input, an input readings, address inputs, information inputs, synchronization input, information outputs, characterized in that it further comprises an error vector storage unit, a first block of OR elements, a second block of OR elements, an element disambiguations, the input to the zero state, the write input, the read input, the address inputs are connected respectively to the first, second, third and fourth inputs of the memory node, the synchronization input is connected to the fifth input of the memory node and to the first input of the AND block, the information inputs are connected to sixth inputs of the memory node and to the inputs of the input coding block, which generates the values of the control bits

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

by adding modulo 2 information symbols a ₀ a ₁ a ₂ a ₃ , b ₀ b ₁ b ₂ b ₃ , c ₀ c ₁ c ₂ c ₃ , d ₀ d ₁ d ₂ d ₃ , e ₀ e ₁ e ₂ e ₃ , f ₀ f ₁ f ₂ f ₃ , g ₀ g ₁ g ₂ g ₃ , h ₀ h ₁ h ₂ h ₃ , i ₀ i ₁ i ₂ i ₃ , j ₀ j ₁ j ₂ j ₃ , k ₀ k ₁ k ₂ k ₃ , l ₀ l ₁ l ₂ l ₃ , m ₀ m ₁ m ₂ m ₃ , n ₀ n ₁ n ₂ n ₃ , o ₀ o ₁ o ₂ o ₃ , p ₀ p ₁ p ₂ p ₃ arriving at the inputs of the input coding block, in accordance with the rule:

the outputs of the input coding block are connected to the seventh inputs of the memory node, the information outputs of the memory node are connected respectively to the first inputs of the corrector and to the inputs of the output coding block, which generates the values of the test control bits

, r _2P ^f , r _3P ^f , r _4P ^f , r _5P ^f , r _6P ^f , r _7P ^f , r _8P ^f , r _9P ^g , r _10P ^g , r _11P ^g , r _12P ^g , r _13P ^g , r _14P ^g , r _15P ^g , r _16P ^g , r _17P ^g , r _18P ^g , r _19P ^g , r _20P ^g by adding modulo 2 information symbols a _0P a _1P a _2P a _3P , b _0P b _1P b _2P b _3P with _0L to _1P to _2P with _3P, d _0n d _1H d _2P d _3P, f _0L e _1P f _2n e _3P, f _0L f _1P f _2n f _3P, g _0L g _1P g _2P g _3P, h _0L h _1P h _2P h _3P , i _0P i _1P i _2P i _3P , j _0P j _1P j _2P j _3P , k _0P k _1P k _2P k _3P , l _0P l _1P l _2P l _3P , m _0P m _1P m _2P m _3P , n _0P n _1P n _2P n _3P , o _0P about _1P about _2P about _3P , p _0P p _1P p _2P p _3P received at the inputs of the input coding block from the information outputs of the memory node, in accordance with the rule:

the outputs of the output coding unit are connected to the first inputs of the error syndrome calculation unit, the outputs of the control bits of the memory node are connected to its second inputs, the outputs of the error syndrome calculation unit are connected to the inputs of the first block of OR elements and to the inputs of the decoder, the outputs of which are connected to the inputs of the second block of OR elements and to the inputs of the error vector storage unit, the outputs of the error vector storage unit are connected to the second inputs of the corrector, the outputs of which are connected to the second inputs of the block of AND elements, the outputs are not the first and second blocks of elements OR are connected to the inputs of the element of ambiguity, the output of which is connected to the third input of the block of elements AND, the first outputs of the block of elements AND are information outputs of the device, and the second output of the block of elements AND is the output "device failure".