Устройство хранения и передачи данных с обнаружением ошибок

Изобретение относится к вычислительной технике. Технический результат заключается в повышении достоверности функционирования устройства за счет обнаружения 100% одиночных и максимального количества двойных ошибок (7,5%) при минимальной информационной избыточности. Результат достигается кодированием исходной двоичной информации на основе организации независимых проверок и за счет введения входного блока 2 кодирования, выходного блока 3 кодирования, блока 4 выявления ошибки, блока 5 элементов И, элемента 6 И, блока 7 элементов ИЛИ. 1 ил., 2 табл.

 

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

Известно устройство памяти с обнаружением двойных ошибок [1], содержащее узел памяти, входной блок кодирования, формирующий значения контрольных разрядов r1 и r2 путем сложения по модулю 2 информационных символов x1, x2, x3, y1, y2, y3, поступающих на входы входного блока кодирования, в соответствии с правилом: r1=х1⊕х2⊕у1⊕у2; r2=х2⊕х3⊕у2⊕у3, выходной блок кодирования, формирующий значения проверочных контрольных разрядов r1П, r2П путем сложения по модулю 2 информационных символов x1C, х2C, х3C, у1C, у2C, у3C, поступающих на входы выходного блока кодирования и полученных при считывании информации с информационных выходов узла памяти в соответствии с правилом: r1П=х1C⊕х2C⊕у1C⊕у2C; r2П=х2С⊕х3С⊕у2С⊕у3С, блок выявления ошибки, блок элементов И, элемент И, блок элементов ИЛИ, вход установки устройства в нулевое состояние, вход записи, вход считывания, адресные входы, информационные входы, вход синхронизации, информационные выходы, выход сигнала при возникновении ошибки, вход установки в нулевое состояние, вход записи, вход считывания, адресные входы, информационные входы, вход синхронизации подключены соответственно к первому, второму, третьему и четвертому, пятому и шестому входам узла памяти, информационные выходы узла памяти подключены к входам выходного блока кодирования и к первым входам блока элементов И, выходы выходного блока кодирования подключены к первым входам блока выявления ошибки, вторые входы которого подключены к выходом контрольных разрядов узла памяти, а выходы подключены к входам блока элементов ИЛИ, выход которого подключен к первому входу элемента И, второй вход блока элементов И и второй вход элемента И подключены к входу синхронизации, выходы первого блока элементов И являются информационными выходами устройства, выход элемента И является выходом сигнала "Ошибка".

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

Наиболее близким по техническому решению является контролируемое устройство хранения и передачи информации [2], содержащее узел памяти, входной блок кодирования, формирующий значения контрольных разрядов r1, r2 и r3, выходной блок кодирования, формирующий значения проверочных контрольных разрядов r1p, r2p, r3p блок выявления ошибки, блок элементов ИЛИ, блок элементов И, элемент И, вход установки устройства в нулевое состояние, вход записи, вход считывания, адресные входы, информационные входы, вход синхронизации, информационные выходы, выход сигнала при возникновении ошибки, вход установки в нулевое состояние, вход записи, вход считывания, адресные входы, вход синхронизации подключены соответственно к первому, второму, третьему и четвертому, пятому входам узла памяти, информационные входы подключены к шестым входам узла памяти и к входам входного кодирующего устройства, выходы которого подключены к седьмым входам узла памяти, информационные выходы узла памяти подключены к входам выходного блока кодирования и к первым входам блока элементов И, выходы выходного блока кодирования подключены к первым входам блока выявления ошибки, вторые входы которого подключены к выходом контрольных разрядов узла памяти, а выходы подключены к входам блока элементов ИЛИ, выход которого подключен к первому входу элемента И, второй вход блока элементов И и второй вход элемента И подключены к входу синхронизации, выходы первого блока элементов И являются информационными выходами устройства, выход элемента И является выходом сигнала "Ошибка", входной блок кодирования формирует значение контрольного разрядов r1 путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r1 = y3 ⊕ y4 ⊕ y5 ⊕ y6 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12, значение контрольного разрядов r2 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r2 = y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕y11 ⊕ y12, значение контрольного разрядов r3 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r3 = y1 ⊕ у2 ⊕ у4 ⊕ у5 ⊕ у7 ⊕ у8 ⊕ у10 ⊕ y11, выходной блок кодирования, формирующий значения проверочных контрольных разрядов r1p, r2p, r3p, путем сложения по модулю 2 информационных символов y1p, y4p,y5p,y6p, y7p,y8p,y9p, y10p,y11p,y12p, поступающих на его входы при считывании информации с информационных выходов узла памяти, в соответствии с правилом: r1p = y3p ⊕ y4p ⊕ y5p ⊕ y6p ⊕ y9p ⊕ y10p ⊕ y11p ⊕ y12p; r2p = у ⊕ у ⊕ у ⊕ у ⊕ у ⊕ у10р ⊕ y11p ⊕ y12p; r3p = y1p ⊕ y2p ⊕ y4p ⊕ y5p ⊕ y7p ⊕ y8p ⊕ y10p ⊕ y11p, блок выявления ошибки осуществляет поразрядное сложения по mod2 значений контрольных разрядов r1S, r2S и r3S, считываемых с вторых выходов узла 1 памяти, соответственно с значениями контрольных разрядов r1p, r2p, r3p, сформированных на выходах выходного блока 3 кодирования.

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

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

Поставленная цель достигается тем, что устройство, содержащее узел памяти, входной блок кодирования, формирующий значения контрольных разрядов r1, r2 и r3, выходной блок кодирования, формирующий значения проверочных контрольных разрядов r1p, r2p, r3p, блок выявления ошибки, блок элементов ИЛИ, блок элементов И, элемент И, вход установки устройства в нулевое состояние, вход записи, вход считывания, адресные входы, информационные входы, вход синхронизации, информационные выходы, выход сигнала при возникновении ошибки, вход установки в нулевое состояние, вход записи, вход считывания, адресные входы, вход синхронизации подключены соответственно к первому, второму, третьему и четвертому, пятому входам узла памяти, информационные входы подключены к шестым входам узла памяти и к входам входного кодирующего устройства, выходы которого подключены к седьмым входам узла памяти, информационные выходы узла памяти подключены к входам выходного блока кодирования и к первым входам блока элементов И, выходы выходного блока кодирования подключены к первым входам блока выявления ошибки, вторые входы которого подключены к выходам контрольных разрядов узла памяти, а выходы подключены к входам блока элементов ИЛИ, выход которого подключен к первому входу элемента И, второй вход блока элементов И и второй вход элемента И подключены к входу синхронизации, выходы первого блока элементов И являются информационными выходами устройства, выход элемента И является выходом сигнала "Ошибка", отличается тем, что входной блок кодирования формирует значение контрольного разрядов r1 путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r1 = y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12 значение контрольного разрядов r2 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r2 = y2 ⊕ y4 ⊕ y5 ⊕ y8 ⊕ y9 ⊕ y10 ⊕y11 ⊕ y12, значение контрольного разрядов r3 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r3 = y1 ⊕ у4 ⊕ у5 ⊕ у6 ⊕ у7 ⊕ у10 ⊕ у11 ⊕ y12, выходной блок кодирования, формирующий значения проверочных контрольных разрядов r1p, r2p, r3p, путем сложения по модулю 2 информационных символов y1p, y4p,y5p,y6p, y7p,y8p,y9p, y10p,y11p,y12p, поступающих на его входы при считывании информации с информационных выходов узла памяти, в соответствии с правилом: r1p = y3p ⊕ y6p ⊕ y7p ⊕ y8p ⊕ y9p ⊕ y10p ⊕ y11p ⊕ y12p; r2p = у ⊕ у ⊕ у ⊕ у ⊕ у ⊕ у10р ⊕ y11p ⊕ y12p; r3p = y1p ⊕ y4p ⊕ y5p ⊕ y6p ⊕ y7p ⊕ y10p ⊕ y11p ⊕ y12p, блок выявления ошибки осуществляет поразрядное сложения по mod2 значений контрольных разрядов r1S, r2S и r3S, считываемых с вторых выходов узла 1 памяти, соответственно с значениями контрольных разрядов r1p, r2p, r3p, сформированных на выходах выходного блока 3 кодирования.

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

Вход 8 установки в нулевое состояние, вход 9 записи, вход 10 считывании, адресные входы 11, вход 13 синхронизации подключены соответственно к первому, второму, третьему и четвертому, пятому входам узла 1 памяти, информационные входы 12 подключены к шестым входам узла 1 памяти и к входам входного кодирующего устройства 2, выходы которого подключены к седьмым входам узла 1 памяти, информационные выходы узла 1 памяти подключены к входам выходного блока 3 кодирования и к первым входам блока 5 элементов И, выходы выходного блока 3 кодирования подключены к первым входам блока 4 выявления ошибки, вторые входы которого подключены к выходам контрольных разрядов узла 1 памяти, а выходы подключены к входам блока 7 элементов ИЛИ, выход которого подключен к первому входу элемента 6 И, второй вход блока элементов 5 И и второй вход элемента 6 И подключены к входу 13 синхронизации, выходы блока 5 элементов И являются информационными выходами устройства, выход элемента 6 И является выходом сигнала "Ошибка", устройство отличается тем, что входной блок кодирования формирует значение контрольного разрядов r1 путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r1 = y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12, значение контрольного разрядов r2 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r2 = y2 ⊕ y4 ⊕ y5 ⊕ y8 ⊕ y9 ⊕ y10 ⊕y11 ⊕ y12, значение контрольного разрядов r3 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r3 = y1 ⊕ у4 ⊕ у5 ⊕ у6 ⊕ у7 ⊕ у10 ⊕ у11 ⊕ y12, выходной блок 3 кодирования, формирующий значения проверочных контрольных разрядов r1p, r2p, r3p, путем сложения по модулю 2 информационных символов y1p, y4p,y5p,y6p, y7p,y8p,y9p, y10p,y11p,y12p, поступающих на его входы при считывании информации с информационных выходов узла памяти, в соответствии с правилом:

r1p = y3p ⊕ y6p ⊕ y7p ⊕ y8p ⊕ y9p ⊕ y10p ⊕ y11p ⊕ y12p; r2p = у ⊕ у ⊕ у ⊕ у ⊕ у ⊕ у10р ⊕ y11p ⊕ y12p; r3p = y1p ⊕ y4p ⊕ y5p ⊕ y6p ⊕ y7p ⊕ y10p ⊕ y11p ⊕ y12p, блок 4 выявления ошибки осуществляет поразрядное сложения по mod2 значений контрольных разрядов r1S, r2S и r3S, считываемых с вторых выходов узла 1 памяти, соответственно с значениями контрольных разрядов r1p, r2p, r3p, сформированных на выходах выходного блока 3 кодирования.

Узел 1 памяти, в данном случае, представляет собой статическое полупроводниковое оперативное устройство памяти и предназначен для хранения кодовых слов: УК = y1y2 у3 у4 y5 y6 y7 y8 y9, y10 y11 y12 r1 r2 r3 полученных при кодировании исходной информации.

Входной блок 2 кодирования предназначен для формирования значений контрольных разрядов r1, r2, r3, путем сложения по mod2 информационных символов в соответствии с правилом:

r1 = y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12;

r2 = y2 ⊕ y4 ⊕ y5 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12;

r3 = y1 ⊕ у4 ⊕ у5 ⊕ у6 ⊕ у7 ⊕ у10 ⊕ у11 ⊕ y12.

Выходной блок 3 кодирования предназначен формирования значений проверочных контрольных разрядов r1p, r2p, r3p, путем сложения по mod2 информационных символов, полученных при считывании информации с узла 1 памяти в соответствии с правилом:

r1p = y3p ⊕ y6p ⊕ y7p ⊕ y8p ⊕ y9p ⊕ y10p ⊕ y11p ⊕ y12p;

r2p = у ⊕ у ⊕ у ⊕ у ⊕ у ⊕ у10р ⊕ y11p ⊕ y12p;

r3p = y1p ⊕ y4p ⊕ y5p ⊕ y6p ⊕ y7p ⊕ y10p ⊕ y11p ⊕ y12p,

Блок 4 выявления ошибки предназначен для обнаружения ошибки в кодовом слове при считывании информации с узла 1 памяти путем сложения по mod2 значений контрольных разрядов r1S, r2S, r3S, считываемых с вторых выходов узла 1 памяти, соответственно с значениями контрольных разрядов r1p, r2p и r3p, сформированных на выходах выходного блока 3 кодирования:

λ1 = r1S ⊕ r1p;

λ2 = r2S ⊕ r2p;

λ3 = r3S ⊕ r3p.

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

Выходы λ1, λ2, λ3 блока 4 выявления ошибки объединены в один выход первым элементом 7 ИЛИ, значение сигнала на данном выходе поступает первый вход элемента 6 И.

Считывание выходной информации с выходов 14 устройства проводится при поступлении сигнала с входа 13 синхронизации на второй вход блока 5 элементов И и второй вход элемента 6 И.

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

При записи информации в узел 1 памяти, подается единичный сигнал на вход 9 записи, адресные входы 11 и информационные входы 12.

Например, на информационные входы поступает двенадцатиразрядное слово, имеющие в своих разрядах следующие значения: 110 001 101 111.

Входной блок 2 кодирования сформирует значения контрольных разрядов:

r1 = y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12 = 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0;

r2 = y2 ⊕ y4 ⊕ y5 ⊕ y8 ⊕ y9 ⊕ y10 ⊕y11 ⊕ y12 = 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1;

r3 = y1 ⊕ у4 ⊕ у5 ⊕ у6 ⊕ у7 ⊕ у10 ⊕ у11 ⊕ y12 = 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0.

В результате имеем кодовое слово: Ук = 110 001 101 111 010 (последние четыре разряда являются контрольными разрядами), которое записывается в узле 1 памяти.

При считывании информации с узла 1 памяти, второй блок 3 кодирования, относительно принятой информации сформирует значения контрольных разрядов: Rp = {r1p, r2p, r3p,} = {010}

Если ошибок нет, то имеем результат: R=(010), Rp=(010), RS=(010), λ=(000).

Пусть, произошла одиночная ошибка во первом информационном разряде: 0* 10 001 1 01 111 010.

На выходе второго блока 3 кодирования имеем результат: Rp=(011), а с вторых выходов узла 1 памяти считывается значения переданных контрольных разрядов RS=(010),

В этом случае сигналы на выходе блока 4 выявления ошибки принимают значение: λ=(001).

Соответственно на выходе блока 5 ИЛИ появится единичное значение сигнала, которое при поступлении сигнала с входа 13 синхронизации, поступит на вход элемента 6 И, на выходе которого появится значение сигнала "Ошибка".

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

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

1. Патент на изобретение №2403615 "Устройство хранения и передачи информации с обнаружением двойных ошибок" / Павлов А.А., Царьков А.Н. и др. от 27.01.2009 г.

2. Патент на полезную модель №161373 "Контролируемое устройство хранения и передачи информации " / Бутранов А.С., Павлов А.А., Царьков А.Н. и др. от 29.03.2016 г.

Приложение к заявке на изобретение «Устройство хранения и передачи данных с обнаружением ошибок»

1. Введение

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

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

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

обеспечить минимальное время на кодирование и декодирование информации;

обладать минимальной информационной избыточностью;

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

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

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

d≥t+1.

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

r=] log2(n+1) [,

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

В этом случае проверочная матрица кода Хэмминга состоит из всех различных ненулевых векторов длины r.

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

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

Известно контролируемое устройство хранения и передачи информации [1], в котором минимизированные проверки для формирования значений контрольных разрядов имеют вид:

r1 = y3 ⊕ y4 ⊕ y5 ⊕ y6 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12,

r2=y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕y11 ⊕ y12,

r3 = y1 ⊕ у2 ⊕ у4 ⊕ у5 ⊕ у7 ⊕ у8 ⊕ у10 ⊕ y11

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

Ук = 000 000 000 000 000 0000.

Примечание:

Из 120 возможных одиночных и двойных ошибок не обнаруживаются 12 двойных ошибок или 10% (номера не обнаруживаемых ошибок выделены жирным шрифтом) от числа возможных одиночных и двойных ошибок.

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

2. Правила построения корректирующих кодов, повышенной обнаруживающей способности

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

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

Полученные информационные блоки представляют в виде информационной матрицы:

В результате имеем информационную матрицу, имеющую m-строк и b-столбцов. Пусть: z=(b+m) - нечетное число; m≥b+1.

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

где {s1, s2, …, sb} - вектор четности столбцов; {sb+1, sb+2, …, sz} - вектор четности строк.

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

Rl = {r1, r2, …, rz} или Rl = rh + ru, rh = log2b, ru = log2 (b + z + 1).

При коррекции одиночной ошибки Rl = ] log2(n+1) [.

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

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

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

Если разряды синдрома ошибки {e1, е2, …, eb} имеют нулевые значения, а в разрядах {eb+1, eb+2, …, ez} имеются единичные значения (и наоборот), то это свидетельствует о наличии ошибок в контрольных разрядах.

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

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

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

Причем:

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

Количество повторений одного и того же столбца равно:

если n делится без остатка.

Если при делении имеем остаток β, то имеем β столбцов, у которых число повторений равно α+1.

В этом случае число необнаруженных ошибок определяется выражением:

Следовательно, вероятность появления необнаруженных комбинаций кода составляет:

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

Количество строк и столбцов матрицы кодирования равно семи.

Требуемое число контрольных разрядов: r*=log27=3. Соответственно длина кода равна 15.

Проверочная матрица Н кода имеет следующий вид:

Проверки для формирования значений контрольных разрядов определяются выражением:

r1 = y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12;

r2 = y2 ⊕ y4 ⊕ y5 ⊕ y8 ⊕ y9 ⊕ y10 ⊕y11 ⊕ y12;

r3 = y1 ⊕ у4 ⊕ у5 ⊕ у6 ⊕ у7 ⊕ у10 ⊕ у11 ⊕ y12.

В таблице 2 представлены значения синдромов при возникновении одиночных и двойных ошибок в информационных и контрольных разрядах относительно кодового слова: Ук=000 000 000 000 000.

Примечание:

Из 120 одиночных и двойных ошибок не обнаруживаются 9 двойных ошибок, или 7,5% от возможного числа ошибок (необнаруженные двойные ошибки выделены жирным шрифтом).

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

При использовании предлагаемого метода для построения кодирующего устройства потребуется 21 сумматор по mod 2. Для построения декодирующего устройства потребуется 21 сумматора по mod 2 и три сумматора по mod 2 для формирования синдрома ошибки, Итого - 45 сумматоров по mod 2.

При использовании кода Хэмминга (код-12,5), потребуется пять контрольных разрядов.

При использовании кода Хэмминга (12,5) для кодирования информации потребуется 32 сумматора по mod 2. Для декодирования потребуется 32 сумматора по mod 2, итого 64 сумматора по mod 2. Если учесть, что для хранения значений контрольных разрядов в устройстве памяти так же требуются аппаратурные затраты, то выигрыш в аппаратурных затратах от использования предлагаемого метода значительно выше.

Заметим, что число контрольных разрядов при использовании предлагаемого метода кодирования зависит от размерности матрицы кодирования. Так, например, при кодировании пятидесяти четырех информационных символов и использовании матрицы кодирования размерности (3×18) потребуется пять контрольных разрядов.

При кодировании информации предлагаемым методом двоичного слова, содержащего 56 информационных разрядов (использовании матрицы кодирования 7×8), потребуется четыре контрольных разряда. При этом Ре 60=4,9%.

При использовании кода Хэмминга (код-57,6) для этого потребуется шесть контрольных разрядов, т.е. на два разряда больше.

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

Литература

1. Патент на полезную модель №161373 "Контролируемое устройство хранения и передачи информации" / Бутранов А.С., Павлов А.А., Царьков А.Н. и др. от 29.03.2016 г.

Устройство хранения и передачи данных с обнаружением ошибок, содержащее узел памяти, входной блок кодирования, формирующий значения контрольных разрядов r1, r2 и r3, выходной блок кодирования, формирующий значения проверочных контрольных разрядов r1p, r2p, r3p, блок выявления ошибки, блок элементов ИЛИ, блок элементов И, элемент И, вход установки устройства в нулевое состояние, вход записи, вход считывания, адресные входы, информационные входы, вход синхронизации, информационные выходы, выход сигнала при возникновении ошибки, вход установки в нулевое состояние, вход записи, вход считывания, адресные входы, вход синхронизации подключены соответственно к первому, второму, третьему и четвертому, пятому входам узла памяти, информационные входы подключены к шестым входам узла памяти и к входам входного кодирующего устройства, выходы которого подключены к седьмым входам узла памяти, информационные выходы узла памяти подключены к входам выходного блока кодирования и к первым входам блока элементов И, выходы выходного блока кодирования подключены к первым входам блока выявления ошибки, вторые входы которого подключены к выходам контрольных разрядов узла памяти, а выходы подключены к входам блока элементов ИЛИ, выход которого подключен к первому входу элемента И, второй вход блока элементов И и второй вход элемента И подключены к входу синхронизации, выходы первого блока элементов И являются информационными выходами устройства, выход элемента И является выходом сигнала "Ошибка", отличающееся тем, что входной блок кодирования формирует значение контрольного разрядов r1 путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r1 = y3 ⊕ y6 ⊕ y7 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ У12, значение контрольного разрядов r2 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r2=y2 ⊕ y4 ⊕ y5 ⊕ y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12, значение контрольного разрядов r3 - путем сложения по модулю 2 информационных символов y1,y2,y3, y4,y5,y6, y7,y8,y9, y10,y11,y12, поступающих на его входы, в соответствии с правилом: r3=y1 ⊕ y4 ⊕ y5 ⊕ y6 ⊕ y7 ⊕ y10 ⊕ y11 ⊕ y12, выходной блок кодирования, формирующий значения проверочных контрольных разрядов r1p, r2p, r3p, путем сложения по модулю 2 информационных символов y1p,y2p,y3p, y4p,y5p,y6p, y7p,y8p,y9p, y10p,y11p,y12p, поступающих на его входы при считывании информации с информационных выходов узла памяти, в соответствии с правилом: r1p = y3p ⊕ y6p ⊕ y7p ⊕ y8p ⊕ y9p ⊕ y10p ⊕ y11p ⊕ y12p; r2p = y2p ⊕ y4p ⊕ у ⊕ у ⊕ y9p ⊕ y10p ⊕ y11p ⊕ y12p; r3p = y1p ⊕ у ⊕ у ⊕ у ⊕ y7p ⊕ y10p ⊕ y11p ⊕ у12р, блок выявления ошибки осуществляет поразрядное сложения по mod2 значений контрольных разрядов r1S, r2S и r3S, считываемых с вторых выходов узла 1 памяти, соответственно с значениями контрольных разрядов r1p, r2p, r3p, сформированных на выходах выходного блока 3 кодирования.



 

Похожие патенты:

Изобретение относится к протоколу связи, пригодному для передачи данных с использованием вспомогательных физических каналов. Способ передачи устройством обработки информации, таким как карта с чипом, сообщения, используя по меньшей мере один скрытый физический канал связи, в виде детектируемого и контролируемого изменения аппаратной характеристики упомянутого устройства, содержит следующие этапы: передают преамбулу, состоящую из переменной последовательности символов, кодирующей двоичные значения '0' и '1', за которыми следует символ-разделитель; передают значащую часть, образующую содержимое упомянутого сообщения и состоящую из последовательности символов '0' и '1', необязательно разделенных символом-разделителем '2', причем способ также содержит этап предварительной передачи маркера начала последовательности в виде символа, отличного от символов, служащих для кодирования сообщения, и/или последующий этап передачи маркера конца последовательности в виде символа, отличного от символов, служащих для кодирования сообщения.

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

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

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

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

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

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

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

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

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

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

Для управления периферийным устройством (108, 112, 116) регулирования осуществляют прием через контроллер (102), связанный с периферийным устройством (108, 112, 116) регулирования, данных от системы (122) управления, удаленной от контроллера (102), с целью обеспечения функционирования периферийного устройства (108, 112, 116) регулирования в условиях отсутствия ошибки; обнаружение (306) возникновения состояния ошибки и обеспечение функционирования (506) периферийного устройства (108, 112, 116) регулирования на основании данных, поступающих от системы (122) управления, если возникновение состояния ошибки не обнаружено.

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

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

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

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

Изобретение относится к области вычислительной техники и может быть использовано для выполнения распределенных вычислений в беспроводном оптическом канале и канале, состоящем из одной волоконно-оптической линии.

Изобретение относится к области электроники и вычислительной техники. Технический результат - повышение надежности работы устройства и сохранение работоспособности устройства при возникновении отказов/повреждений в его оборудовании.

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

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

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

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

Наверх