УСТРОЙСТВО ХРАНЕНИЯ И ПЕРЕДАЧИ ДАННЫХ С ОБНАРУЖЕНИЕМ И ИСПРАВЛЕНИЕМ ОШИБОК В БАЙТАХ ИНФОРМАЦИИ Российский патент 2015 года по МПК G06F11/08 G11C29/42 H03M13/11 

Изобретение относится к вычислительной технике и может быть использовано для повышения достоверности функционирования запоминающих устройств.

Известно самокорректирующееся устройство [1], использующее корректирующий код (наиболее часто используется код Хемминга, корректирующий одиночную ошибку и обнаруживающий двойную ошибку).

Недостатком устройства является низкая обнаруживающая способность кода, так как обнаруживаются только двойные ошибки.

Наиболее близким по техническому решению является устройство хранения и передачи данных с исправлением ошибок в байте информации и обнаружением ошибок в байтах информации [2], содержащее узел памяти, входной блок кодирования, выходной блок кодирования, блок вычисления синдрома ошибки, дешифратор, коммутатор, блок коммутаторов, корректор, блок корректоров, первый блок элементов ИЛИ, второй блок элементов ИЛИ, инвертор, элемент И, блок элементов И, вход установки устройства в нулевое состояние, вход записи, вход считывания, адресные входы, двадцати четырех разрядные информационные входы, вход синхронизации, информационные выходы, выход сигнала «ошибка», вход установки в нулевое состояние, вход записи, вход считывания, адресные входы, подключены соответственно к первому, второму, третьему и четвертому входам узла памяти, вход синхронизации подключен к пятому входу узла памяти и к первому входу блока элементов И, информационные входы подключены к шестым входам узла памяти и к входам входного блока кодирования, который формирует значения контрольных разрядов r₁, r₂, r₃, r₄, r₅, r₆, r₇, r₈ путем сложения по модулю 2 информационных символов x₁ x₂ x₃, z₁ z₂ z₃, а₁ a₂ а₃, c₁ c₂ c₃, е₁ е₂ е₃, f₁ f₂ f₃, g₁ g₂ g₃, h₁ h₂ h₃, поступающих на входы входного блока кодирования, в соответствии с правилом: r₁=x₁⊕z₁ ⊕a₁ ⊕c₁ ⊕e₁⊕f₁ ⊕g₁⊕h₁; r₂=x₂⊕z₂ ⊕a₂ ⊕c₂⊕e₂⊕f₂ ⊕g₂⊕h₂; r₃=х₃⊕z₃⊕а₃⊕с₃⊕е₃⊕f₃⊕g₃⊕h₃; r₄=x₁⊕z₃⊕a₂⊕ а₃⊕ c₂⊕ e₁⊕ e₃⊕ f₁⊕ f₂⊕g₁⊕ g₂⊕ g₃; r₅=x₂⊕ x₃⊕ z₁⊕ а₃⊕ c₁⊕ c₃⊕e₁⊕e₂⊕ f₂⊕g₁⊕ g₂⊕ g₃; r₆=x₃⊕ z₂⊕ z₃© а₁⊕ с₁⊕ c₂⊕ e₂⊕ f₁⊕ f₃⊕g₁⊕ g₂⊕ g₃; r₇= x₃⊕ z₃⊕ a₁⊕ а₃⊕ c₂⊕ e₁⊕ f₂⊕g₁⊕ g₂⊕ g₃; r₈=x₁⊕ x₂⊕ z₂⊕ a₂⊕ a₃⊕ c₃⊕ е₃⊕ f₂⊕f₃ ⊕g₁⊕ g₂⊕ g₃, которые поступают на седьмые входы узла памяти, информационные выходы узла памяти подключены соответственно к первым входам корректора, блока корректоров и к входам выходного блока кодирования, который формирует значения проверочных контрольных разрядов r_1П, r_2П, r_3П, r_4П, r_5П, r_6П r_7П r_8П путем сложения по модулю 2 информационных символов x_1П x_2П х_3П, z_1П z_2П z_3П, a_1П a_2П a_3П, c_1П c_2П c_3П, е_1П е_2П е_3П, f_1П f_2П f_3П, g_1П g_2П g_3П, h_1П h_2П h_3П, поступающих на входы входного блока кодирования с информационных выходов узла памяти, в соответствии с правилом: r_1П=x_1п⊕z_1П ⊕а_1П ⊕с_1П ⊕e_1П⊕f_1П ⊕g_1П⊕h_1П; r_2П=x_2П⊕z_2П ⊕a_2П ⊕c_2П⊕е_2П⊕f_2П ⊕g_2П⊕h_2П; r_3П=х_3П⊕z_3П⊕a_3П⊕с_3П⊕е_3П⊕f_3П⊕g_3П⊕h_3П; r_4П=x_1П⊕z_3П⊕ а_2П⊕ а_3П⊕ с_2П⊕ e_1П⊕ е_3П⊕ f_1П⊕ f_2П⊕g_1П⊕ g_2П⊕ g_3П; r_5П=x_2П⊕ х_3П⊕ z_1П⊕ а_3П⊕ с_1П⊕ с_3П⊕е_1П⊕е_2П⊕ f_2П⊕g_1П⊕ g_2П⊕ g_3П; r_6П=х_3П⊕ z_2П⊕ z_3П⊕ а_1П⊕ с_1П⊕ c_2П⊕ е_2П⊕ f_1П⊕ f_3П⊕g_1П⊕ g_2П⊕ g_3П; r_7П=х_3П⊕ z_3П⊕ а_1П⊕ а_3П⊕ C_2П⊕ е_1П⊕ f_2П⊕g_1П⊕ g_2П⊕ g_3П; r_8П=х_1П⊕ х_2П⊕ z_2П⊕ a_2П⊕ а_3П⊕ с_3П⊕ е_3П⊕ f_2П⊕f_3П ⊕g_1П⊕ g_2П⊕ g_3П, выходы выходного блока кодирования подключены к первым входам блока вычисления синдрома ошибки, к вторым входам которого подключены выходы контрольных разрядов узла памяти, первые выходы блока вычисления синдрома ошибки подключены к первым входам дешифратора, к первым входам коммутатора, к входам первого блока элементов ИЛИ и к первым входам блока коммутаторов, вторые выходы блока вычисления синдрома ошибки подключены к вторым входам дешифратора и к вторым входам первого блока элементов ИЛИ, выходы дешифратора подключены к входам второго блока элементов ИЛИ, при этом первый выход дешифратора подключен к второму входу коммутатора, а вторые выходы подключены к вторым входам блока коммутаторов, выход второго блока элементов ИЛИ через инвертор подключен к первому входу элемента И, второй вход которого подключен к выходу первого блока элементов ИЛИ, выход элемента И является выходом сигнала «ошибка», выходы коммутатора подключены к вторым входам корректора, выходы блока коммутаторов подключены к вторым входам блока корректоров, выходы корректора и блока корректоров подключены к вторым входам блока элементов И, выходы которого являются информационными выходами устройства.

Недостатком устройства является низкая корректирующая способность ошибок, так как корректируются только одиночные байты ошибок.

Целью изобретения является повышение отказоустойчивости устройства за счет коррекции ошибок в двух байтах информации и обнаружения не корректируемых ошибок.

Поставленная цель достигается тем, что устройство, содержащее узел памяти, входной блок кодирования, выходной блок кодирования, блок вычисления синдрома ошибки, дешифратор, корректор, блок элементов И, вход установки устройства в нулевое состояние, вход записи, вход считывания, адресные входы, информационные входы, вход синхронизации, информационные выходы, отличающееся тем, что дополнительно содержит блок хранения векторов ошибок, первый блок элементов ИЛИ, второй блок элементов ИЛИ, элемент неравнозначности, вход установки в нулевое состояние, вход записи, вход считывания, адресные входы подключены соответственно к первому, второму, третьему и четвертому входам узла памяти, вход синхронизации подключен к пятому входу узла памяти и к первому входу блока элементов И, информационные входы подключены к шестым входам узла памяти и к входам входного блока кодирования, который формирует значения контрольных разрядов $$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$$ путем сложения по модулю 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₃, поступающих на входы входного блока кодирования, в соответствии с правилом:

выходы входного блока кодирования подключены к седьмым входам узла памяти, информационные выходы узла памяти подключены соответственно к первым входам корректора и к входам выходного блока кодирования, который формирует значения проверочных контрольных разрядов $$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$$ путем сложения по модулю 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П, поступающих на входы входного блока кодирования с информационных выходов узла памяти, в соответствии с правилом:

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

На фиг.1 представлена блок-схема устройства. Устройство хранения и передачи данных с исправлением ошибок в двух байтах информации содержит: узел 1 памяти, входной блок 2 кодирования, выходной блок 3 кодирования, блок 4 вычисления синдрома ошибки, дешифратор 5, блок 6 хранения векторов ошибок, корректор 7, блок 8 элементов И, первый блок 9 элементов ИЛИ, второй блок 10 элементов ИЛИ, элемент 11 неравнозначности, вход 12 установки к нулевое состояние, вход 13 записи, вход 14 считывания, адресные входы 15, информационные входы 16, вход 17 синхронизации, информационные выходы 18, выход 19 «отказ устройства».

Вход 12 установки в нулевое состояние, вход 13 записи, вход 14 считывания, адресные входы 15 подключены соответственно к первому, второму, третьему и четвертому входам узла 1 памяти, вход 17 синхронизации подключен к пятому входу узла 1 памяти и к первому входу блока 8 элементов И, информационные входы 16 подключены к шестым входам узла 1 памяти и к входам входного блока 2 кодирования, который формирует значения контрольных разрядов $$r_1^f$$ , $$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 кодирования, в соответствии с правилом:

выходы входного блока 2 кодирования подключены к седьмым входам узла 1 памяти, информационные выходы узла 1 памяти подключены соответственно к первым входам корректора 7 и к входам выходного блока 3 кодирования, который формирует значения проверочных контрольных разрядов $$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$$ путем сложения по модулю 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 памяти, в соответствии с правилом:

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

Узел 1 памяти, в данном случае, представляет собой статическое полупроводниковое оперативное устройство памяти и предназначен для хранения кодовых наборов: У_К = а₀ 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₃, $$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$$ , полученных при кодировании исходных шестидесяти четырех разрядных двоичных наборов.

Входной блок 2 кодирования предназначен для формирования значений контрольных разрядов $$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$$ , путем сложения по mod2 информационных символов в соответствии с правилом::

Выходной блок 3 кодирования предназначен для формирования значений проверочных контрольных разрядов $$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$$ , путем сложения по модулю 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 памяти, в соответствии с правилом:

Блок 4 вычисления синдрома ошибки предназначен для обнаружения ошибки в кодовом наборе при считывании информации с узла 1 памяти путем сложения по mod2 значений контрольных разрядов $$r_1^f$$ , $$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 кодирования.

Результат поразрядного сложения:

Нулевой результат суммы свидетельствует об отсутствии ошибки, и ее наличии в противном случае.

Дешифратор 5 формирует единичное значение сигнала на одном из своих выходов в соответствии с значением синдромом ошибки (формирует адрес вектора ошибки в блоке 6 хранения векторов ошибок).

В таблице 1 представлена часть значений синдромов ошибок для кода 84, 20.

Примечание: В табл.1 значения информационных разрядов, контрольных разрядов и значения ошибки в байтах информации представлены в шестнадцатеричной системе счисления, а значения синдрома ошибки - в двоичной.

Блок 6 хранения векторов ошибок предназначен для хранения значений векторов ошибок в соответствии с значениями синдромов ошибок (вектор ошибки имеет единичные значения сигналов в тех разрядах кодового набора, в которых произошла ошибка).

Корректор 7 предназначен для исправления корректируемой ошибки путем сложения по mod2 одноименных разрядов блока информации, имеющего ошибку с значением вектора ошибки.

Первый 9, второй 10 блоки элементов ИЛИ, элемент 11 неравнозначности предназначены для формирования сигнала «отказ устройства» при наличии единичного сигнала на выходе первого блока 9 элементов ИЛИ и отсутствии единичного сигнала на выходе второго блока 10 элементов ИЛИ и наоборот.

Устройство работает следующим образом. Перед началом работы устройства на вход 12 "установки в нулевое состояние" подается единичный сигнал, который переводит устройство в нулевое состояние.

При записи информации в узел 1 памяти подаются единичные сигналы на вход 17 синхронизации, вход 13 записи, адресные входы 15 и информационные входы 16.

Допустим, необходимо закодировать двоичный набор:

Тогда значения контрольных разрядов, сформированных относительно полученного набора входным блоком 2 кодирования, имеют нулевые значения, т.е. имеем кодовый набор:

При отсутствии ошибки значение кодового набора, записанного в узле 1 памяти, равно считанному (переданному кодовому набору):

В этом случае на выходе блока 4 вычисления синдрома ошибки имеем нулевые значения сигналов.

Пусть произошла одиночная ошибка в четвертом разряде шестнадцатого блока информации (Р=0001^*), тогда выходной блок 3 кодирования сформирует относительно полученного кодового набора значения контрольных разрядов:

В блоке 4 вычисления синдрома ошибки складываются переданные контрольные разряды с контрольными разрядами, сформированными относительно полученного кодового набора, в результате получим синдром ошибки S:

В этом случае, синдром ошибки указывает четвертый ошибочный разряд блока Р (вторая строка табл.1).

На выходе дешифратора 5 появится единичное значение сигнала, которое формирует адрес для считывания значения вектора ошибки из блока 6 хранения векторов ошибок в соответствии с значением синдрома ошибки.

В этом случае, значение вектора ошибки поступает на входы корректора 7, где складывается по mod2 с значениями информационных разрядов. В результате имеем правильное значение информации.

Аналогичным образом корректируются ошибки, возникающие в других одиночных и двойных байтах информации.

Возникновение некорректируемой ошибки (наличия единичного значения сигнала хотя бы на одном выходе блока 4 вычисления синдрома ошибки) и отсутствие единичного сигнала на выходах дешифратора 5 приводит к появлению единичного сигнала на выходе первого блока 9 элементов ИЛИ и нулевому значению сигнала на выходе второго блока 10 элементов ИЛИ. В этом случае на выходе элемента 11 неравнозначности появится единичное значение сигнала, которое свидетельствует о наличии некорректируемой ошибки (отказе устройства).

ИСТОЧНИКИ ИНФОРМАЦИИ

1. Щербаков Н.С. Достоверность работы цифровых устройств. М.: Машиностроение, 1989, с.82, рис.39, 224 с.

2. Патент РФ на изобретение №2448359 "Устройство хранения и передачи данных с исправлением ошибок в байте информации и обнаружением ошибок в байтах информации" / Борисов К.Ю., Малофеев Ю.Г., Осипенко П. Н., Павлов А.А., Павлов А.А., Павлов П.А., Царьков A.Н, Хоруженко О.В. Дата выдачи: 20.04.2012 г.

ПРИЛОЖЕНИЕ

1. Введение и постановка задачи

Во многих случаях для обнаружения и исправления ошибок используются коды с обнаружением и исправлением байтов ошибок (в этом случае, под байтом ошибок понимаются ошибки, кратность которых не превышает число разрядов b блока информации).

К таким кодам следует отнести коды [1]:

- исправляющие одиночные ошибки и обнаруживающие одиночные байты ошибок;

- коды, исправляющие одиночные ошибки, обнаруживающие двойные независимые ошибки и обнаруживающие одиночные байты ошибок;

-коды, исправляющие одиночные байты ошибок;

-коды исправляющие одиночные и обнаруживающие двойные байты ошибок.

Широкое распространение получили коды Рида-Соломона, обладающие циклическими свойствами и имеющие наибольшую обнаруживающую и корректирующую способность.

Код Рида-Соломона (РС) - это блочный код (w, N), позволяющий обнаруживать и исправлять ошибки в байтах. Входным словом для него является блок из w байтов, выходным - кодовое слово из N байтов, состоящее из w исходных и N-w проверочных байтов. При этом гарантировано, что при декодировании в кодовом слове будут обнаружены и исправлены t=(N-w)/2 байтов независимо от их расположения внутри кодового слова. Кодирующее устройство РС реализуется на основе регистра сдвига с 2t байтовыми элементами памяти и обратными связями. Процесс кодирования и декодирования сводится к операциям сложения и умножения по модулю.

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

2. Разработка линейного корректирующего кода с исправлением ошибок в двух байтах информации

Предлагается метод построения корректирующего кода, исправляющего ошибки в двух байтах информации, реализующий линейную процедуру построения корректирующего кода с синдромным декодированием.

Правила кодирования информации

Правило 2.1 Двоичный набор Y, содержащий k информационных символов, разбивается на w=k/b байтов информации (под байтом информации понимается число информационных разрядов, не превышающих значение b, и пусть b кратно k).

Под байтом ошибок понимаются ошибки, кратность которых не превышает число разрядов b блока информации.

В результате двоичный набор может быть представлен в виде:

Определение 2.1 Вектор ошибки, полученный относительно сложения одноименных разрядов переданных и полученных байтов информации, будем называть аддитивным вектором ошибки.

Правило 2.2 Для формирования первого аддитивного вектора ошибки осуществим сложение по mod2 одноименных разрядов байтов информации начиная с первого по (b-1) - блок информации, а для формирования второго аддитивного вектора ошибки осуществим сложение по mod2 одноименных разрядов байтов информации начиная с второго по b - блок информации (осуществим операцию перемежения) и результат суммирования добавим к двоичному набору Y.

В результате получим кодовый набор Y_K1:

Для исправления ошибочных разрядов информации возникает необходимость формирования совокупности проверок (разработки правила кодирования информации), позволяющих определить блок (байт) информации, содержащий ошибку.

С этой целью осуществим кодирование блоков информации, используя w матриц кодирования.

Свойство 2.1 Каждая матрица кодирования содержит g_H=[log₂(k+1)] сток при нечетном значении b и g_Ч=[log₂(k+1)]+1 - при четном значении b.

Свойство 2.2 Каждая строка матрицы кодирования содержит b разрядов.

Примечание: Квадратные скобки означают округление результата в большую сторону.

Правило 2.3 Представим одноименные строки матриц кодирования двоичным набором, соответствующим одному из значений множества {2^b} таким образом, чтобы результат проверки на четность строк матрицы кодирования в двоичном наборе образовывал номер u_i, принадлежащий множеству {2 g_H} при нечетном значении b и множеству {2 g_Ч} - при четном значении b, и при этом для полученных значений номеров выполнялось условие u_j--u_i≥2t.

Правило 2.4 Значения контрольных проверок (значений контрольных разрядов) матрицы кодирования формируются сложением по mod2 элементов строк матрицы, имеющих единичные значения.

Свойство 2.3 Для исключения совпадения синдромов ошибок (при k=b2^b) для второй части синдромов ошибок требуется r_gЧ=[log₂(2b2^b)+1] - контрольных разрядов при четном значении b, и r_gH=log₂(2b2^b) - при нечетном.

В этом случае, число дополнительных контрольных разрядов (строк матрицы кодирования) составит r_ДОПЧ=[log₂(2b2^b)+1-b] при четном значении b, и r_ДОПЧН=[log₂(2b2^b)-b] - при нечетном.

Граница числа контрольных разрядов для кода, корректирующего ошибки в двух байтах информации с формированием аддитивного вектора ошибки, оценивается выражением:

Правило 2.5 Объединяя по mod2 одноименные контрольные проверки для всех матриц кодирования, получим значения второй части контрольных разрядов

Таким образом, имеем регулярную процедуру построения кодового набора с аддитивным формирование вектора ошибки:

Результат сложения по mod2 переданных значений контрольных разрядов $$r_{i1}^f$$ , $$r_{i2}^f$$ , $$r_i^g$$ и контрольных разрядов $$r_{i1}^{fП}$$ , $$r_{i2}^{fП}$$ , $$r_i^{gП}$$ , сформированных относительно полученных информационных разрядов, даст значение синдрома ошибки, включающего две части:

Значения синдрома ошибки $$S_1^f$$ , $$S_2^f$$ представляют собой аддитивные векторы ошибки (указывают ошибочные разряды в блоках информации), а значение синдрома ошибки S^g определяет номера ошибочных блоков (байтов) информации.

Свойство 2.4 Возникновение ошибок в соседних байтах информации приводит к искажениям векторов ошибок.

Следствие 2.1 При возникновении ошибок в соседних байтах вектора ошибок формируются в соответствии с синдромом ошибок.

Правило 2.6 декодирования включает следующую стратегию:

Аналогичным образом строится код, корректирующий ошибки в заданном n-числе байтов информации (n≤b).

Граница числа контрольных разрядов корректирующего кода, исправляющего ошибки в заданном числе байтов информации (при нечетном значении b), оценивается выражением:

При четном значении b к данному выражению прибавляется единица.

Таким образом, предлагаемый метод коррекции ошибок в заданном числе байтов информации с аддитивным формированием вектора ошибки имеет регулярную и относительно простую процедуру матричного кодирования. Позволяет сократить временные затраты на кодирование и декодирование информации (исключить циклическую процедуру кодирования).

По отношению к коду Рида-Соломона позволяет исключить временные затраты на нахождения корней полинома локаторов ошибок. Так, для решения ключевого уравнения кода PC (78,8) по алгоритму Евклида потребуется 96 тактов работы декодирующего устройства.

Временные затраты на кодирование информации предлагаемым методом сопоставимы с временными затратами при контроле информации на четность (требующим минимальных временных затрат), что дает возможность обеспечить работу канала передачи данных в реальном масштабе времени.

Предлагаемый метод позволяет сократить аппаратурные затраты на построение декодирующего устройства, т.к. в большинстве случаев не требует аппаратурных затрат на вычисление вектора ошибки.

Использование предлагаемого метода позволяет повысить достоверность передаваемой информации за счет обнаружения некорректируемых ошибок. В отличие от кодов PC, использующих для коррекции полином ошибок наименьшей степени (при реализации декодирования по методу «максимума-правдоподобия»), что в некоторых случаях приводит к ошибочной коррекции.

Пример 2. Допустим, требуется осуществить коррекцию ошибок в двух байтах информации кратности 4, в двоичном наборе, содержащем 64 информационных разряда, т.е. построить код (84, 20).

Используя полученные правила, построим матрицы кодирования информации для формирования второй части контрольных разрядов:- $$r_1^g$$ , $$r_2^g$$ … $$r_{ДОПi}^g$$ (табл.2.1).

Контрольные проверки (значения второй части контрольных разрядов), полученные относительно полученных матриц кодирования, имеют вид:

В табл.2.2 представлена часть значений синдромов ошибок для кода 84,20.

Примечание: В табл.2.2 значения информационных разрядов, контрольных разрядов и значения ошибки в байтах информации представлены в шестнадцатеричной системе счисления, а значения синдрома ошибки - в двоичной.

Анализ таблицы показывает, что 94% синдромов ошибок имеют разные значения, т.е. не корректируется 6% ошибок в двух блоках информации.

Введение дополнительных контрольных разрядов позволяет осуществить коррекцию до 100% ошибок, однако это ведет к значительному росту аппаратурных затрат, по этому целесообразно ограничиться коррекцией данного числа ошибок.

Таким образом, разработанный метод коррекции ошибок в двух байтах информации отличается от существующих тем, что позволяет:

- осуществлять коррекцию ошибок с алгебраически-синдромным декодированием (исключить циклическую процедуру кодирования и декодирования информации);

- имеет регулярную и относительно простую процедуру кодирования информации;

- сократить временные затраты на кодирование и декодирование информации и обеспечить работу канала передачи данных в реальном масштабе времени.

Литература

1. Щербаков Н.С. Достоверность работы цифровых устройств. М.: Машиностроение, 1989, с.122, рис.45, 224 с.

Изобретение относится к области телемеханики, автоматики и вычислительной техники и предназначено для использования в устройствах хранения и передачи информации. Техническим результатом является повышение отказоустойчивости устройства за счет коррекции ошибок в двух байтах информации и обнаружения некорректируемых ошибок. Устройство содержит узел памяти, входной блок кодирования, выходной блок кодирования, блок вычисления синдрома ошибки, дешифратор, блок хранения векторов ошибок, корректор, блок элементов И, блоки элементов ИЛИ, элемент неравнозначности. 1 ил., 1 табл., 1 прилож.

Устройство хранения и передачи данных с обнаружением и исправлением ошибок в байтах информации, содержащее узел памяти, входной блок кодирования, выходной блок кодирования, блок вычисления синдрома ошибки, дешифратор, корректор, блок элементов И, вход установки устройства в нулевое состояние, вход записи, вход считывания, адресные входы, информационные входы, вход синхронизации, информационные выходы, отличающееся тем, что дополнительно содержит блок хранения векторов ошибок, первый блок элементов ИЛИ, второй блок элементов ИЛИ, элемент неравнозначности, вход установки в нулевое состояние, вход записи, вход считывания, адресные входы подключены соответственно к первому, второму, третьему и четвертому входам узла памяти, вход синхронизации подключен к пятому входу узла памяти и к первому входу блока элементов И, информационные входы подключены к шестым входам узла памяти и к входам входного блока кодирования, который формирует значения контрольных разрядов , , , , , , , , , , , , , , , , , , , путем сложения по модулю 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₃, поступающих на входы входного блока кодирования, в соответствии с правилом:


выходы входного блока кодирования подключены к седьмым входам узла памяти, информационные выходы узла памяти подключены соответственно к первым входам корректора и к входам выходного блока кодирования, который формирует значения проверочных контрольных разрядов , 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П а_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П, поступающих на входы входного блока кодирования с информационных выходов узла памяти, в соответствии с правилом:


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