самокорректирующееся устройство хранения информации

Классы МПК:G06F11/08 обнаружение и исправление ошибок с помощью избыточности в представлении данных, например с помощью корректирующих кодов 
H03M13/11 с использованием нескольких разрядов четности
G11C29/42 с использованием кодов с исправлением ошибок (ECC) или констроля соотношений
Автор(ы):, , , , , , , ,
Патентообладатель(и):ИНСТИТУТ ИНЖЕНЕРНОЙ ФИЗИКИ РОССИЙСКАЯ ФЕДЕРАЦИЯ (ИИФ РФ) (RU)
Приоритеты:
подача заявки:
2004-07-14
публикация патента:

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

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

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

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

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

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

Целью изобретения является повышение достоверности функционирования устройства за счет коррекции 90% обнаруживаемых ошибок, не превышающих кратность 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 устройства, выход 29 "Отказ устройства".

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

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

Блок 20 инверсии предназначен для инвертирования значений информационных разрядов, поступающих с выходов первого элемента 7 ИЛИ соответственно при записи и считывании информации.

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

самокорректирующееся устройство хранения информации, патент № 2297030

где yi, самокорректирующееся устройство хранения информации, патент № 2297030 rЧЕТ, самокорректирующееся устройство хранения информации, патент № 2297030 - соответственно прямые и обратные значения i-го информационного разряда и значения разряда четности кодового набора.

Относительно сформированной матрицы в кодирующем устройстве 15 проводятся правые и левые диагональные проверки.

Число диагональных проверок определяется по формуле:

RД =2(k+2).

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

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

R=r1r2......................................., r2(k+2),

RП =r1 Пr П.................................... r П 2(k+2).

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

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

E=е 1e2е3............е 2(k+2)еЧЕТ.

Дешифратор 17 содержит 2k+5-входа (число разрядов синдрома ошибки) и L=l 1+l2+l3 выходов (по числу схем совпадения, представляющих собой 2k+5-входовые схемы И), где

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

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

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

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

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

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

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

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

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

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

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

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

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

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

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

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

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

Приложение

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

где Н=h1,h 2,...,hm - вектор четности строк; Z=z1,z2,...,z b - вектор четности столбцов. Вектора четности строк и столбцов образуют совокупность контрольных разрядов R 1={r1,r2,r m,rm+1,...,rb }. При получении кодовой комбинации относительно информационных разрядов повторно формируются значения контрольных разрядов R 1 П={r1,r 2,rm,rm+1,...,r b}. В данном случае, разница между переданными значениями контрольных разрядов и полученными после приема информации образует синдром ошибки Е:

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

r1 =y1; r2=y 2самокорректирующееся устройство хранения информации, патент № 2297030 y3; r3=y 4; r4=y3; r 5=y1самокорректирующееся устройство хранения информации, патент № 2297030 y4; r6=y 2.

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

самокорректирующееся устройство хранения информации, патент № 2297030

где разряды вектора ошибки r 1,r2,............r l - соответствуют правым диагональным проверкам, r l,rl+1............r 2l - левым и сформированным относительно полученных информационных разрядов;

самокорректирующееся устройство хранения информации, патент № 2297030 - значения полученных контрольных разрядов.

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

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

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

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

2) осуществляется проверка на четность информационных разрядов;

3) из прямых инверсных значений информационных разрядов и

полученного значения разряда четности формируется информационная матрица:

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

самокорректирующееся устройство хранения информации, патент № 2297030

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

9) множество N разбивается на четыре подмножества N=n1+n 2+n3+n4, где

n1 - синдромы, имеющие одинаковые дополнительные проверки (некорректируемые ошибки);

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

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

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

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

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

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

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

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

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

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

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

- число одинаковых синдромов ошибок, имеющих одинаковые дополнительные проверки - 1280;

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

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

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

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

В табл.1 представлены часть значений синдромов ошибок для подмножеств n2, n3, n 4 (исключены синдромы ошибок подмножества n 1, имеющие одинаковые значения дополнительных проверок).

самокорректирующееся устройство хранения информации, патент № 2297030

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

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

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

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

Класс G06F11/08 обнаружение и исправление ошибок с помощью избыточности в представлении данных, например с помощью корректирующих кодов 

способ восстановления записей в запоминающем устройстве и система для его осуществления -  патент 2502124 (20.12.2013)
самопроверяемый специализированный вычислитель систем булевых функций -  патент 2485575 (20.06.2013)
устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в эвм, функционирующих в системе остаточных классов -  патент 2483346 (27.05.2013)
масштабируемый информационный сигнал, устройство и способ для кодирования масштабируемого информационного контента, устройство и способ для исправления ошибок масштабируемого информационного сигнала -  патент 2461052 (10.09.2012)
устройство для коррекции ошибок в полиномиальной системе классов вычетов -  патент 2453902 (20.06.2012)
устройство хранения и передачи данных с исправлением одиночных ошибок в байте информации и обнаружением произвольных ошибок в байтах информации -  патент 2450331 (10.05.2012)
способ проверки совпадения состояний видеокодера и видеодекодера -  патент 2432704 (27.10.2011)
устройство хранения информации повышенной достоверности функционирования -  патент 2421786 (20.06.2011)
самопроверяемый модулярный вычислитель систем логических функций -  патент 2417405 (27.04.2011)
способ передачи цифровой информации через параллельную магистраль -  патент 2413283 (27.02.2011)

Класс H03M13/11 с использованием нескольких разрядов четности

способ и устройство помехоустойчивого декодирования сигналов, полученных с использованием кода проверки на четность с низкой плотностью -  патент 2522299 (10.07.2014)
способ и устройство для канального кодирования и декодирования в системе связи, в которой используются коды контроля четности с низкой плотностью -  патент 2520406 (27.06.2014)
способ и устройство для канального кодирования и декодирования в системе связи, в которой используются коды контроля четности с низкой плотностью -  патент 2490791 (20.08.2013)
способ помехоустойчивого декодирования сигналов, полученных с использованием параллельного каскадного кода проверки на четность с низкой плотностью -  патент 2461964 (20.09.2012)
способ и устройство для декодирования кода с генераторной матрицей низкой плотности -  патент 2461963 (20.09.2012)
способ и устройство для канального кодирования и декодирования в системе связи, в которой используются коды контроля четности с низкой плотностью -  патент 2454794 (27.06.2012)
способ кодирования управляющей информации в системе беспроводной связи, а также способ и устройство для передачи и приема управляющей информации -  патент 2453992 (20.06.2012)
способ и устройство для канального кодирования и декодирования в системе связи, в которой используются коды контроля четности с низкой плотностью -  патент 2450443 (10.05.2012)
способ и устройство для кодирования и декодирования канала в системе связи с использованием кодов с низкой плотностью проверок на четность -  патент 2450442 (10.05.2012)
кодирование и декодирование ldpc пакетов переменных размеров -  патент 2443053 (20.02.2012)

Класс G11C29/42 с использованием кодов с исправлением ошибок (ECC) или констроля соотношений

Наверх