ОТКАЗОУСТОЙЧИВОЕ УСТРОЙСТВО Российский патент 2007 года по МПК G06F11/08 H03M13/11 G11C29/42 

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

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

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

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

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

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

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

На чертеже представлена блок-схема устройства.

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

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

Кодирующее устройство 7 предназначено для:

1) реализации правых и левых диагональных проверок на основе использования группы сумматоров по mod 2, при записи информации, в соответствии с правилами, представленными в приложении. Диагональные проверки образуют вектор R=r₁,r₂,............r_2l.;

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

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

R=r₁,r₂,............r_2l,,

R^П=r₁ ^П,r^П ₂,............r^П _2l.

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

Схема 9 синдрома ошибки представляют собой схему поразрядного сравнения и предназначена для формирования значений синдрома ошибки на основе передаваемой и полученной информации.

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

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

Второй дешифратор 12 формирует на одном из своих выходов единичный сигнал в соответствии с поступающим значением дополнительной проверки.

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

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

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

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

Схема 8 свертки уменьшает на один разряд число разрядов правых и левых диагональных проверок путем сложения по mod 2 значения первого разряда диагональных проверок с остальными разрядами диагональных проверок (см. приложение).

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

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

При этом информация с выходов схемы 8 свертки поступает на первые входы схемы 9 синдрома ошибки, на вторые входы которой поступает информации, считываемая с регистра 14.

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

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

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

Второй дешифратор 12 формирует на одном из своих выходов единичный сигнал в соответствии с поступающим значением дополнительной проверки.

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

Приложение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.3 Структура диагональных проверок:

- результаты правых диагональных проверок; - результаты левых диагональных проверок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где k - число информационных разрядов.

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

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

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

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

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

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

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

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

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

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

Тогда для рассматриваемого примера таблица синдромов ошибок может быть представлена в виде табл.2.

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

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

Для рассматриваемого примера дополнительные проверки имеют вид:

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

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

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

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

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

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

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

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

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

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

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