отказоустойчивое устройство

Формула изобретения

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

Описание изобретения к патенту

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

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

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

Наиболее близким по техническому решению является самокорректирующееся дискретное устройство [2], содержащее исходную схему, первое кодирующее устройство, схему синдрома ошибки, дешифратор ошибки, корректор, второе, третье и четвертое кодирующие устройства, с первой по четвертую схемы свертки, схему признака ошибки, элемент ИЛИ, входы устройства подключены к исходной схеме и к входам первого кодирующего устройства, к входам второго кодирующего устройства, а выходы исходной схемы подключены к входам третьего и четвертого кодирующих устройств, к первым входам корректора, выходы которого являются выходами устройства, выходы с первого по четвертое кодирующих устройств подключены соответственно к входам с первой по четвертую схем свертки, выходы первой и третьей схем свертки подключены к входам схемы синдрома ошибки, выходы второй и четвертой схем свертки подключены к входам схемы признака ошибки, выходы схемы синдрома ошибки и признака ошибки подключены к входам дешифратора ошибки, первая группа выходов дешифратора ошибки подключена к вторым входам корректора, а вторая группа выходов подключена к входу элемента ИЛИ, с выхода которого снимается сигнал "отказ устройства".

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

Целью изобретения является повышение достоверности функционирования устройства за счет коррекции более 50% обнаруживаемых ошибок, не превышающих кратность k-1, при условии максимального обнаружения количества ошибок в кодовом наборе.

Поставленная цель достигается тем, что устройство, содержащее исходную схему, кодирующее устройство, схему синдрома ошибки, дешифратор, корректор, информационные входы устройства подключены к первым входам исходной схемы, выходы которой подключены к первым входам корректора, выходы корректора являются выходами устройства, отличающееся тем, что оно дополнительно содержит с первого по пятый элементы И, с первого по восьмой элементы ИЛИ, регистр, схему проверки на четность, элемент НЕ, адресные входы, вход записи, вход считывания, вход "Сброс", причем информационные входы устройства подключены к первым входам первого элемента И, адресные входы подключены к вторым входам исходной схемы и к первым входам регистра, вход записи подключен к третьему входу исходной схемы, к второму входу первого элемента И и к второму входу регистра, вход считывания подключен к четвертому входу исходной схемы, к первому входу второго элемента И, к первому входу третьего элемента И, к первому входу четвертого элемента И и к третьему входу регистра, вход "Сброс" подключен к пятому входу исходной схемы и к четвертому входу регистра, выходы исходной схемы подключены к вторым входам второго элемента И, выходы которого подключены к первым входам первого элемента ИЛИ, вторые входы которого подключены к выходам первого элемента И, а выходы подключены к входам схемы проверки на четность и к первым входам кодирующего устройства, выходы кодирующего устройства подключены к вторым входам третьего элемента И и к пятым входам регистра, выходы схемы проверки на четность подключены к вторым входам кодирующего устройства, к третьим входам третьего элемента И и к шестым входам регистра, первые входы схемы синдромов ошибки подключены к выходам третьего элемента И, вторые входы подключены к выходам регистра, а выходы подключены к входам дешифратора и к входам второго элемента ИЛИ, выход которого подключен к первому входу пятого элемента И, первая группа выходов дешифратора подключена к входам третьего элемента ИЛИ, вторая группа выходов дешифратора подключена к входам четвертого элемента ИЛИ, третья группа выходов дешифратора подключена к входам пятого элемента ИЛИ, четвертая группа выходов дешифратора подключена к входам шестого элемента ИЛИ, пятая группа выходов дешифратора подключена к входам седьмого элемента ИЛИ, выходы с третьего по шестой элементов ИЛИ подключены соответственно с второго по пятый входы четвертого элемента И и с первого по четвертый входы восьмого элемента ИЛИ, выход седьмого элемента ИЛИ подключен к пятому входу восьмого элемента ИЛИ, выход которого через элемент НЕ подключен к второму входу пятого элемента И, вход пятого элемента И является выходом устройства, выходы четвертого элемента И подключены к вторым входам корректора.

На чертеже представлена блок-схема устройства. Устройство содержит: исходную схему 1, первый элемент 2 И, второй элемент 3 И, третий элемент 4 И, четвертый элемент 5 И, пятый элемент 6 И, первый элемент 7 ИЛИ, второй элемент 8 ИЛИ, третий элемент 9 ИЛИ, четвертый элемент 10 ИЛИ, пятый элемент 11 ИЛИ, шестой элемент 12 ИЛИ, седьмой элемент 13 ИЛИ, восьмой элемент 14 ИЛИ, схему 15 проверки на четность, кодирующее устройство 16, регистр 17, схему синдрома ошибки 18, дешифратор 19, элемент 20 НЕ, корректор 21, информационные входы 22, адресные входы 23, вход 24 записи, вход 25 считывания, вход 26 сброс, выходы 27 устройства, выход 28 "Отказ устройства".

Информационные входы 22 устройства подключены к первым входам первого элемента 2 И к первым входам исходной схемы 1, выходы которой подключены к первым входам корректора 21, адресные входы 23 подключены к вторым входам исходной схемы 1 и к первым входам регистра 17, вход 24 записи подключен к третьему входу исходной схемы 1, к второму входу первого элемента 2 И и к второму входу регистра 17, вход 25 считывания подключен к четвертому входу исходной схемы 1, к первому входу второго элемента 3 И, к первому входу третьего элемента 4 И, к первому входу четвертого элемента 5 И и к третьему входу регистра 17, вход 26 "Сброс" подключен к пятому входу исходной схемы 1 и к четвертому входу регистра 17, выходы исходной схемы 1 подключены к вторым входам второго элемента 3 И, выходы которого подключены к первым входам первого элемента 7 ИЛИ, вторые входы которого подключены к выходам первого элемента 2 И, а выходы подключены к входам схемы 15 проверки на четность и к первым входам кодирующего устройства 16, выходы кодирующего устройства 16 подключены к вторым входам третьего элемента 4 И и к пятым входам регистра 17, выходы схемы 15 проверки на четность подключены к вторым входам кодирующего устройства 16, к третьим входам третьего элемента 4 И и к шестым входам регистра 17, первые входы схемы 18 синдромов ошибки подключены к выходам третьего элемента 4 И, вторые входы подключены к выходам регистра 17, а выходы подключены к входам дешифратора 19 и к входам второго элемента 8 ИЛИ, выход которого подключен к первому входу пятого элемента 6 И, первая группа выходов дешифратора 19 подключена к входам третьего элемента 9 ИЛИ, вторая группа выходов дешифратора 19 подключена к входам четвертого элемента 10 ИЛИ, третья группа выходов дешифратора 19 подключена к входам пятого элемента 11 ИЛИ, четвертая группа выходов дешифратора 19 подключена к входам шестого элемента 12 ИЛИ, пятая группа выходов дешифратора 19 подключена к входам седьмого элемента 13 ИЛИ, выходы с третьего 9 по шестой 12 элементов ИЛИ подключены соответственно с второго по пятый входы четвертого элемента 5 И и с первого по четвертый входы восьмого элемента 14 ИЛИ, выход седьмого элемента 13 ИЛИ подключен к пятому входу восьмого элемента 14 ИЛИ, выход которого через элемент 20 НЕ подключен к второму входу пятого элемента 6 И, вход пятого элемента 6 И является выходом устройства, выходы четвертого элемента И подключены к вторым входам корректора 21.

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

при этом:

1) схемой 15 проверки на четность для каждой строки информационной матрицы организуется проверка на четность;

2) в кодирующем устройстве 16 проводятся правые и левые диагональные проверки. Число диагональных проверок (число контрольных разрядов диагональных проверок) определяется по формуле:

R_д=k+4;

3) формирования (аналогичным образом) вектора контрольных разрядов R^П принятого кодового набора на основе информации, считываемой с выходов исходной схемы 1.

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

R=r₁r₂ ....................................ю..., r_(k+4) ,r_ЧЕТ1,r_ЧЕТ2

R^П=r₁ ^Пr^П.................................... r^П _(k+4).r ^П _ЧЕТ1,r^П _ЧЕТ2

Регистр 16 предназначен для хранения значений сигналов вектора контрольных разрядов, сформированного при записи информации в исходную схему 1.

Схема 17 синдрома ошибки представляет собой схему поразрядного сравнения и предназначена для формирования значений синдрома ошибки на основе передаваемой и полученной информации. результат сложения по mod 2 значений сигналов переданных и сформированных контрольных разрядов даст синдром ошибки:

E=e₁e ₂e₃.........e_k+4 e_rчет1e_rчет2

Дешифратор 18 содержит k+6 входа (число разрядов синдрома ошибки) и L=l₁+l₂+l ₃ выходов (по числу схем совпадения, представляющих собой k+6 - входовые схемы И), где

- l₁ -группа элементов И для различных синдромов, характеризующих ошибки только в информационных разрядах;

- l ₂ - группа элементов И для различных синдромов, характеризующих ошибки только в контрольных разрядах;

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

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

Выходы дешифратора 18 объединены соответственно в один выход с помощью третьего элемента 9 ИЛИ, четвертого элемента 10 ИЛИ, пятого элемента 11 ИЛИ, шестого (k-го) элемента 12 ИЛИ для формирования управляющих сигналов на корректор, соответственно для коррекции первого, второго ...k-го информационных разрядов.

Седьмой элемент 13 ИЛИ объединяет выходы дешифратора 18 (выходы схем И), принадлежащие подмножеству l₂ и соответствующие возникновению ошибок только в контрольных разрядах (для которых не требуется формирование управляющих сигналов на корректор).

Корректор 20 включает k элементов неравнозначности и предназначен для исправления ошибок , возникающих на выходах исходной схемы 1. При исправлении ошибок реализуется функция относительно управляющих сигналов ui, поступающих с выходов элементов ИЛИ:

При возникновении ошибок, принадлежащих подмножеству n₁ - для одинаковых синдромов, указывающих на ошибку в различных информационных разрядах (имеющих одинаковое значение синдромов и дополнительных проверок, см. приложение), характеризующихся наличием единичных значений на выходе схемы 17 синдромов ошибок и отсутствием единичных значений на выходах с третьего 9 по седьмой 13 элементов ИЛИ, с помощью второго элемента 8 ИЛИ, восьмого элемента 14 ИЛИ, элемента 19 НЕ, пятого элемента 6 И формируется сигнал "Отказ устройства".

Устройство работает следующим образом. Перед началом работы на вход 25 подается сигнал, устанавливающий устройство в исходное состояние. При поступлении входной информации на информационные входы 21, адресные входы 22 и сигнала "Запись" на вход 23 информация записывается по указанному адресу в исходной схеме 1. Одновременно она поступает на входы первого элемента 2 И, открытого сигналом со входа 23, и далее через элемент 7 ИЛИ входная информация поступает на вход кодирующего устройства 15. Кодирующее устройство 15, реализованное на группе сумматоров по mod 2, реализует проверку на четность строк информационной матрицы и правые и левые диагональные проверки.

С выходов кодирующего устройства 15 значение вектора контрольных разрядов поступает на вход регистра 16 и записывается по указанному адресу.

При считывании информации по указанному адресу сигналы с выхода исходной схемы 1 через второй элемент 3 И, открытый сигналом "Считывание" с входа 24, элемент 7 ИЛИ повторно поступают на вход кодирующего устройства 15, где формируются значения сигналов в контрольных разрядах проверок на четность и диагональных проверок матрицы, сформированной по полученной информации.

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

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

Дешифратор 18 при возникновении ошибки формирует на одном из своих выходов единичный сигнал в соответствии с поступающим значением синдрома ошибки. В зависимости от номера информационного разряда, имеющего ошибку, управляющий сигнал появится на выходе соответствующего (9...12) элемента ИЛИ. Данный сигнал через открытый четвертый элемент 5 И поступает на вход корректора 20, где происходит исправление ошибочного информационного разряда.

Если ошибка произошла только в контрольных разрядах, сигнал появится на выходе седьмого элемента 13 ИЛИ (не требуется подача управляющих сигналов на корректор).

Выходы дешифратора 18 объединены соответственно в один выход с помощью третьего элемента 9 ИЛИ, четвертого элемента 10 ИЛИ, пятого элемента 11 ИЛИ, шестого (k-го) элемента 12 ИЛИ для формирования управляющих сигналов на корректор, соответственно для коррекции первого, второго ...k-го информационных разрядов.

Седьмой элемент 13 ИЛИ объединяет выходы дешифратора 18 (выходы схем И), принадлежащие подмножеству l₂ и соответствующие возникновению ошибок только в контрольных разрядах (для которых не требуется формирование управляющих сигналов на корректор).

Корректор 20 включает k элементов неравнозначности и предназначен для исправления ошибок , возникающих на выходах исходной схемы 1. При исправлении ошибок реализуется функция относительно управляющих сигналов ui, поступающих с выходов элементов ИЛИ:

При возникновении ошибок, принадлежащих подмножеству n₁ -для одинаковых синдромов, указывающих на ошибку в различных информационных разрядах (имеющих одинаковое значение синдромов и дополнительных проверок, см. приложение), характеризующихся наличием единичных значений на выходе схемы 17 синдромов ошибок и отсутствием единичных значений на выходах с третьего 9 по седьмой 13 элементов ИЛИ, с помощью второго элемента 8 ИЛИ, восьмого элемента 14 ИЛИ, элемента 19 НЕ, пятого элемента 6 И формируется сигнал Отказ устройства .

Приложение

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

Процедура построения двумерного итеративного кода состоит в следующем [3]. Заданную совокупность информационных символов делят на группы (блоки, модули) информации, по b разрядов в каждой группе. Полученные модули информации представляют в виде информационной матрицы (1):

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

где H=h₁,h ₂,...,h_m - вектор четности строк; Z=z₁,z₂,...,z _b - вектор четности столбцов. Вектора четности строк и столбцов образуют совокупность контрольных разрядов R ₁={r₁,r₂,r _m+1,...,r_b}. При получении кодовой комбинации относительно информационных разрядов повторно формируются значения контрольных разрядов R₁ ^П={r₁,r₂,r _m,r_m+1,...,r_b }. В данном случае разница между переданными значениями контрольных разрядов и полученными после приема информации образует синдром ошибки Е:

При этом разряды синдрома ошибки е ₁е₂...е_m (полученные относительно вектора четности строк) указывают модуль информации, имеющей ошибку, а разряды е_mе _m+1...е_b (полученные относительно вектора четности столбцов) указывают ошибочный разряд в модуле информации.

Так как кодовые комбинации строк и столбцов имеют минимальное расстояние d=2, то минимальное расстояние данного кода d=4. Этот код позволяет исправлять любую одиночную ошибку и обнаруживать значительную долю кратных ошибок.

Структуры ошибок, не обнаруживаемых двумерным итеративным кодом, показаны на рисунке:

Рис.1. Структуры ошибок, не обнаруживаемых двумерным итеративным кодом: а) - ошибки кратности 4; б) - ошибки кратности 6.

Рис.2. Структуры ошибок двумерного итеративного кода, приводящие к ошибочной коррекции: а) - ошибки кратности 5; б) - ошибки кратности 7.

В общем случае можно строить итеративные коды более высокой размерности (трехмерные, четырехмерные и т.д.), где каждый информационный символ будет являться компонентой одновременно х различных кодовых слов. Параметры итеративных кодов размерности х таковы [3]:

где n_i, k _i, d_i - соответственно длина, количество информационных разрядов, минимальное расстояние кодовых наборов строк и столбцов.

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

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

Структура диагональных проверок, обнаруживающих рассматриваемые ошибки, имеет вид, представленный на рис.3.

Левые диагональные проверки образуются по правилу:

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

В этом случае общее число диагональных проверок равно 2l, или

Пример 1. Пусть рассматриваемое слово состоит из четырех информационных разрядов, которые имеют нулевые значения. Для данного кодового набора информационная матрица имеет вид:

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

В то же время правые и левые диагональные проверки дадут результат 101.

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

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

Рис.4. Структуры ошибок, не обнаруживаемых диагональными проверками и проверками строк и столбцов.

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

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

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

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

Для рассматриваемого примера кодирование информации осуществляется следующим образом:

r₁ =у₁; r₂=у ₂ у₃; r₃=у ₄; r₄=у₃; r ₅=у₁ у₄; r₆=у ₂.

Результат сложения значений сигналов контрольных разрядов переданных и полученных даст синдром ошибки:

где разряды вектора ошибки r ₁,r₂.........r_l соответствуют правым диагональным проверкам, r _l,r_l+1.........r_2l - левым и сформированным относительно полученных информационных разрядов;

- значения полученных контрольных разрядов.

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

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

Таким образом, каждой ошибке из множества ошибок М=(2ⁿ)k можно поставить в соответствие значение синдрома ошибки и значение дополнительных диагональных проверок.

Свойство 2. Каждой совокупности значения синдрома ошибок и значения дополнительных проверок соответствует подмножество Q-ошибок различной конфигурации.

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

В связи с этим предлагаемый метод кодирования включает следующие положения:

4) для того чтобы обеспечить коррекцию около 50% возникающих ошибок, целесообразно ограничиться исправлением ошибок, кратность которых не превышает k-1;

5) для каждой строки информационной матрицы организуется проверка на четность, т.е. информационная матрица представляется в виде:

6) для полученной информационной матрицы организуются правые и левые диагональные проверки. Число диагональных проверок (число контрольных разрядов диагональных проверок) определяется по формуле:

С учетом двух контрольных разрядов проверки на четность число контрольных разрядов составит:

7) кодовый набор передается в виде:

8) результат сложения значений сигналов переданных и сформированных контрольных разрядов даст синдром ошибки:

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

7) в результате имеем множество ошибок заданной кратности (в данном случае от одиночной до кратности k-1, определяемое выражением: ), характеризующихся определенными значением синдрома ошибки и дополнительной проверки;

8) множество N разбивается на четыре подмножества

N=n₁+n ₂+n₃+n₄, где n₁ - синдромы, имеющие одинаковые дополнительные проверки (некорректируемые ошибки, признак отказа устройства);

n₂ - подмножество групп (каждая группа включает 2^k-одинаковых значений синдромов) при наличии ошибок только в информационных разрядах;

n ₃ - подмножество групп (каждая группа включает 2 ^k-одинаковых значений синдромов) при наличии ошибок только в контрольных разрядах;

n₄ - подмножество групп (каждая группа включает 2_k-одинаковых значений синдромов) при наличии ошибок одновременно в информационных и контрольных разрядах.

Заметим, что для ошибок, не превышающих кратность k-1, нет ошибочных кодовых наборов, трансформируемых в разрешенные (исправные) кодовые наборы. На основе полученных правил кодирования формируется стратегия декодирования, решающая задачу различения ошибок в информационных и контрольных разрядах, и правила коррекции возникающих ошибок, которая включает следующие пункты:

1) выявляются одинаковые дополнительные проверки, по которым из множества N исключаются синдромы ошибок, принадлежащие подмножеству n₁ (выявляются некорректируемые ошибки, для которых формируется сигнал "Отказ устройства");

2) определяются группы одинаковых синдромов (указывающих на ошибку в соответствующих информационных разрядах) для подмножества n₂;

3) определяются группы синдромов ошибок, принадлежащих подмножеству n₃, для которых не требуется коррекция информационных разрядов;

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

Для рассматриваемого примера, реализующего предлагаемый метод кодирования, имеем:

- общее количество ошибок - 7504;

- число одинаковых синдромов ошибок, имеющих одинаковые дополнительные проверки (подмножество n₁) - 1824 (число обнаруживаемых ошибок);

- 5680 - число корректируемых ошибок (75%);

- число ошибок только в информационных разрядах - 224 (l₁=14 групп, каждая из которых включает по 16 одинаковых синдромов);

- число ошибок только в контрольных разрядах - 2064 (l₂=129 групп, каждая из которых включает по 16 одинаковых синдромов);

- число ошибок, имеющих искажения одновременно в информационных и контрольных разрядах - 3392 (l₃=212 групп, каждая из которых включает по 16 одинаковых синдромов).

В таблице представлена часть значений синдромов ошибок для подмножеств n₂, n₃, n ₄ (исключены синдромы ошибок подмножества n ₁, имеющие одинаковые значения дополнительных проверок).

Предлагаемый метод кодирования позволяет:

корректировать ошибку заданной кратности;

обнаруживать максимальное количество ошибок (за исключением ошибочных кодовых наборов, трансформируемых в разрешенные кодовые наборы);

сигнализировать о неисправности устройства памяти при возникновении некорректируемой ошибки.

Источники информации

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

2. Положительное решение по заявке (21)99111190/09 от 15.01.03 (подано 31.05.09), авторы: Царьков А.Н., Безродный Б.Ю., Новиков Н.Н., Романенко Ю.А., Павлов А.А.

3. Хетагуров Я.А., Руднев Ю.П. Повышение надежности цифровых устройств методами избыточного кодирования. М.: Энергия, 1974, 270 с.