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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

Узел 1 памяти, в данном случае, представляет собой статическое полупроводниковое оперативное устройство памяти и предназначен для хранения кодовых наборов: У К=x1 x2 x 3 y1 y2 y 3 r1 r2 полученных при кодировании исходных двоичных наборов:

У=x 1, x2, x3, y1, y2, y 3.

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

r1=x1x2y1y2;

r2 =x2x3y2y3.

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

r=x1Cx2Cy1Cy2C;

r =x2Cx3Cy2Cy3C.

Блок 4 сравнения предназначен для обнаружения ошибки в кодовом наборе при считывании информации с узла 1 памяти путем сложения по mod2 значений контрольных разрядов r1C и r2C, считываемых с вторых выходов узла 1 памяти, соответственно с значениями контрольных разрядов r и r , сформированных на выходах выходного блока 3 кодирования

1=r1Cr;

2=r2Cr2П.

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

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

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

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

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

Например, на информационные входы поступает кодовая комбинация: x1 x2 x 3 y1 y2 y 3 соответствующая значению -000 110

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

r 1=x1x2y1y2=0; r2=x 2x3y2y3=1.

Соответственно в узел 1 памяти запишется информация: 00011001.

При считывании информации на вход 10 полезной модели подается сигнал, разрешающий считывание информации с узла 1 памяти. Если ошибки нет, то выходной блок 3 кодирования относительно информационных разрядов формирует значения: r=0 и r =1, которые равны соответственно значениям r1C и r2C, поэтому на выходе блока 4 сравнения имеем значения: 1=0, 2=0.

Допустим произошла ошибка в первом информационном разряде: 1 00110 01. В этом случае на выходах выходного блока 3 кодирования получим значения сигналов: r =l и r=1. Так как

значение r r1C (10), то на выходе блока 4 сравнения получим значения сигналов: 1=1, 2=0 соответственно на выходе элемента 7 ИЛИ появится единичное значение сигнала, которое при поступлении сигнала с входа 13 синхронизации поступит на выход элемента 6 И, что свидетельствует о возникновении ошибки. Аналогичным образом полезная модель работает при появлении других ошибок.

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

Приложение

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

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

только нечетные ошибки. В то же время опыт эксплуатации дискретных устройств показывает, что наиболее вероятным событием является возникновение одиночных и двойных ошибок. (соответственно на одиночные ошибки приходится 80-85%, на двойные ошибки 25-20% и ошибки прочей кратности до 2%) [1], т.е. основным недостатком метода контроля на четность является невозможность обнаружения двойных ошибок.

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

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

Обоснование метода кодирования информации

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

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

где t-число ошибочных разрядов в кодовом наборе.

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

Так как, достоверность функционирования и скорость обработки контролируемой информации существенно зависит от

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

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

Проведенные для этой цели исследования показали, что для поставленной задачи целесообразно использовать независимые ортогональные проверки. Так, для трехразрядного двоичного набора Y=x1 , x2, x3 формирование значений двух контрольных разрядов можно осуществить двумя проверками: r1=x1x2 r2=x 2x3. Соответственно кодовый набор представляется в виде:

В Табл. 1 представлена обнаруживающая способность полученного кода относительно безошибочного кодового набора:

YK=000 00.

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

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

наборов, при этом обнаруживается 100% одиночных ошибок, а из десяти двукратных ошибок не обнаруживается одна ошибка.

Таблица 1.
№п/пБезошибочный кодовый набор: 000000 №п/пБезошибочный кодовый набор: 000000
Ошибочные кодовые наборыПризнак ошибки:    Ошибочные кодовые наборыПризнак ошибки
r1r2 r1r 2
1 000 01- 17100 01
2000 10-  18100 10- -
3000 11 19100 11- -
4001 00- - 20101 00
5001 01-  21101 01-
6001 10 22101 10-
7001 11-  23101 11- -
8010 00 24110 00-
9010 01--  25110 01--
10010 10- 26110 10
11 010 11 27110 11-
12011 00-  28111 00- -
13011 01- 29111 01-
14 011 10--  30111 10-
15011 11 31111 11
16 100 00 -      

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

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

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

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

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

или:

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

В табл.2. представлены ошибочные кодовые наборы для одиночных и двойных ошибок относительно безошибочного кодового набора: 000000 00.

Анализ Табл.2, показывает, что одиночные ошибки обнаруживаются 100%, из двадцати шести двойных ошибок не обнаруживаются шесть. На кодирование двоичного набора предлагаемым методом потребуется шесть сумматоров по mod2 (при контроле по методу четности -пять сумматоров по mod2). На декодирование кодового набора для предлагаемого метода потребуется восемь сумматоров по mod2 (при контроле на четность шесть сумматоров по mod2).

Таблица 2.
№п/пБезошибочный кодовый набор 00000000Признак ошибки  №п/п Безошибочный кодовый набор 00000000 Признак ошибки
Ошибочный   Ошибочный  
кодовый наборr 1r2 кодовый наборr1r2
1000 000 01- 19001 000 10
2000 000 10-  20010 000 10-
3000 001 00- 21100 000 10- -
4000 010 00 22000 011 00-
5000 100 00-  23000 101 00
6001 000 00- 24001 001 00- -
7010 000 00 25010 001 00-
8100 000 00-  26100 001 00
9000 000 11 27000 110 00- *
10000 001 01--  28001 010 00-
11000 010 01-  29010 010 00--
12 000 100 01 30100 010 00-
13 001 000 01-- 31 001 100 00
14 010 000 01-  32010 100 00-
15 100 000 01-  33100 100 00--
16 000 001 10 34011 000 00-
17000 010 10- 35101 000 00
18 000 100 10   36 110 000 00-

Общие аппаратурные затраты для предлагаемого метода кодирования составят четырнадцать сумматоров по mod2, а для контроля на четность -одиннадцать сумматоров по mod2.

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

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

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

Б.М.Коган, И.Б.Мкртумян Основы эксплуатации ЭВМ. М: Энергоатом издат, 1988, 430 с., рис.4.17.

2. Щербаков Н.С.Самокорректирующееся дискретные устройства. М: Машиностроение, 1975, 216 с., рис 28., 224 с. рис.39, рис.44.

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



 

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