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

Способы борьбы с ошибками

Одним из основных параметров при проектировании сложных вычислительных устройств была и остается надежность их функционирования [1], [2], [3], [4], [5]. Ведь, с одной стороны, постоянный рост требований к скоростным характеристикам вычислительных устройств приводит к необходимости организации параллельных вычислений, а с другой стороны, при этом увеличивается частота возникновения отказов, и возрастает время простоя процессоров, вызванное трудностью отыскания и ликвидации неисправности. Очевидно, что независимо от того, какие характеристики проявляет вычислительное устройство, единственная ошибка в любом из его блоков может отключить или повредить всю систему и в некоторых случаях привести к катастрофическим неисправностям. Проблема высокой надежности не только передачи информации, но и ее обработки особенно актуальна в современных системах, работающих в реальном времени, где ошибки работы оборудования должны быть обнаружены и исправлены немедленно. Стоит отметить и то, что переход на новейшие субмикронные технологии только усугубляет данную проблему, так как сложность изготовления ИС многократно возрастает, а вместе с ней возрастает и вероятность возникновения отказов. Такие отказы могут быть обнаружены заблаговременно и влиять на процент выхода годных, так и на этапе их непосредственной эксплуатации, что крайне нежелательно для целого ряда систем, таких, например, как медицинская техника, навигационное оборудование и другая аппаратура, неисправности в работе которой могут обходиться очень дорого. Таким образом, высокая надежность в этом случае должна достигаться не столько совершенствованием самих технических средств передачи информации, сколько за счет применения таких способов ее кодирования, которые были бы устойчивы по отношению к возможным случайным искажениям и позволяли бы при необходимости осуществлять коррекцию данных. В связи с этим наиболее перспективным путем решения рассматриваемой проблемы является придание вычислительным устройствам свойства устойчивости к отказам и сбоям в процессе функционирования. Принято считать вычислительную систему отказоустойчивой (fault-tolerant system), если при возникновении отказа она сохраняет свои функциональные возможности в полном (fail-save) или уменьшенном (fail-soft) объеме. При этом отказоустойчивость обеспечивается сочетанием избыточности системы и наличием механизма обнаружения ошибок, а также процедур для автоматического восстановления ее правильного функционирования. Fail-save устойчивость к отказам характеризует способность вычислительной системы обеспечивать корректную работу, несмотря на возникновение отказа, но с понижением качества, то есть находясь в состоянии постепенного снижения эффективности. Именно в таком контексте будет рассматриваться далее понятие отказоустойчивости.

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

Рис.1. Основные способы обеспечения отказоустойчивости цифровых схем.

Самым простым и распространенным методом борьбы как с отказами, так и сбоями элементов является аппаратное резервирование цифровых устройств и систем [1],[2],[3],[4],[6]. Существует много различных методов резервирования. Рассмотрим, например, два наиболее известных метода: нагруженное ("горячее") и ненагруженное ("холодное") резервирование. В последнем случае используется резервный комплект оборудования, который подключается, когда рабочий комплект начинает выдавать ошибочную информацию. Рабочий комплект в этот момент, естественно, отключается. При "горячем" резервировании одновременно функционируют все комплекты оборудования, выходы которых объединяются через мажоритарный элемент. Как видно, для любого из методов резервирования характерна очень высокая избыточность. Так, например, в большинстве случаев обнаружение правильности результатов достигается двойным просчетом, а выбор правильного результата по совпадающим данным тройным просчетом. Такая высокая избыточность объясняется тем, что при резервировании практически полностью игнорируется специфика самого устройства и корректируются ошибки с любой вероятностью возникновения. Однако во многих вычислительных устройствах для обеспечения надежной работы достаточно исправить лишь часть наиболее вероятных ошибок.

Другим способом обеспечения отказоустойчивости является применение специальных позиционных кодов, широко используемых в каналах связи [7],[8],[9],[4]. Такие коды призваны обнаруживать и исправлять случайные ошибки, возникающие в процессе хранения или передачи информации. Для каждого специального кода, от которого требуется, чтобы он обладал способностью к обнаружению и коррекции ошибки, характерно наличие двух групп цифр - информационной и контрольной. Обозначим через $J_{A}$ и $K_{A}$ соответственно информационную и контрольную части кода $A$. Контрольная часть $K_{A}$ является функцией информационной части: $K_{A} = F(J_{A})$. Основной особенностью известных специальных позиционных кодов является неравноправность информационной и контрольной частей кода относительно арифметических операций. Пусть $J_{A}$, $K_{A}$, $J_{B}$, $K_{B}$ информационные и соответственно контрольные части кодов чисел $A$ и $B$, и пусть над $J_{A}$ и $J_{B}$ должна быть совершена некоторая арифметическая операция $f(J_{A},J_{B})$. Обе части кода были бы равноправны, если бы операция $f$ совершалась над полным кодом, т.е. вычислялась бы величина $C=f(A,B)$, причем $J_{C}=f(J_{A},J_{B})$. Тогда, вычислив $K'_{C}=f(J_{C})$ и сопоставив его с $K_{C}$ - фактической контрольной частью кода $C$, можно проконтролировать правильность выполнения операции $f$. Между тем в известных позиционных кодах операция $f$ производится не над полным кодом чисел $A$ и $B$, а над $J_{A}$ и $J_{B}$, т.е. получается $C'=f(J_{A},J_{B})$, а $K_{C}$ вычисляется как $F(C')$, после чего составляется полный код $C$, для которого $J_{C}=C'$. Здесь $K_{A}$ и $K_{B}$ в арифметической операции не участвуют, что не дает никакой возможности по контрольным частям операндов составить контрольную часть результата, т.е. исключается возможность контроля правильности выполнения арифметических операций. Именно это свойство неарифметичности специальных позиционных кодов препятствует их применению в вычислительных системах, поскольку веденные контрольные разряды не позволяют контролировать результат арифметической операции, в то время как такой контроль для вычислительной системы не менее важен, чем контроль передачи информации [1], [7]. Поэтому в случаях, когда информация подвергается определенным преобразованиям, необходимо применять специальные коды, инвариантные к этим преобразованиям.

Наконец, третий способ обеспечения отказоустойчивости предполагает применение так называемых арифметических кодов - корректирующих кодов, сохраняющих свои свойства при выполнении некоторых арифметических операций [9], [4]. Известны два основных класса арифметических кодов, исправляющих ошибки. К первому классу относятся такие коды, которые не изменяют формы представления исходных чисел. Эти коды, называемые обычно AN-кодами, могут достаточно эффективно использоваться для коррекции ошибок в вычислительных устройствах последовательного типа. В этом случае декодирующая схема получается достаточно - простой. Однако при переходе к устройствам параллельного типа декодирующая аппаратура сильно усложняется даже для кодов, исправляющих только одиночные ошибки. В то же время наличие общих цепей у схем, относящихся к различным разрядам, ставит под сомнение независимость ошибок в этих схемах. Поэтому AN-коды используются в вычислительных машинах в основном для обнаружения ошибок.

Значительно более широкими корректирующими возможностями обладают арифметические коды второго класса - непозиционные коды в модулярной арифметике [1], [4], [10], [11], [12], [13], [14], [15], [16], [5], [17], [18]. Ранее были перечислены основные преимущества модулярного подхода, из которых можно заключить, что модулярная арифметика обладает уникальными свойствами относительно обнаружения и коррекции ошибок. Во-первых, в ней отсутствует значимость порядка цифр в записи числа, а, во-вторых, и коды и проверяемые числа представляются в виде остатков, что позволяет считать такие коды полностью арифметическими. Исходя из этих свойств, можно сделать вывод о том, что применение модулярной арифметики позволяет эффективно решать проблему построения отказоустойчивых систем и служит мощным инструментом для автоматического обнаружения и коррекции ошибок.

Корректирующие коды в модулярной арифметике

Рассмотрим теорию, основные понятия и свойства корректирующих кодов в модулярной арифметике в объеме, достаточном для анализа вопросов аппаратной реализации отказоустойчивых вычислительных систем на их основе. Пусть имеется система остаточных классов (СОК) с набором модулей $\{m_{1}, m_{2},...,m_{p}\}$ и некоторый вектор $\bar A=\{\bar a_{1}, \bar a_{2},...,\bar a_{p}\}$, компонентами которого являются натуральные числа, удовлетворяющие условию: $0< \bar a_{i}<m_{i}$, где $i=1,2,...,p$. Число различных векторов такого типа, отличающихся хотя бы одной компонентой, будет равно произведению $P=m_{1}\cdot m_{2}\cdot...\cdot m_{p}$. Как известно, любое положительное число $A$, находящееся в диапазоне $0< A<N$ однозначно представляется в системе остаточных -классов с общим основанием $M=HOK(m_{1},m_{2},...,m_{p})$, где НОК — наименьшее общее кратное, при условии $N<M$. Тогда каждому числу $A$ из диапазона $[0,...,N)$ можно поставить в соответствие некоторый вектор $A$ из диапазона $[0,...,P)$. При этом подмножество $N$ различных векторов $A$ называют корректирующим кодом, обозначим его через $\Omega$, а сами эти вектора кодовыми словами или кодовыми векторами. В случае $M=N=P$ представление чисел в такой системе является безызбыточным. Однако, в общем случае это не так, а значит любую СОК можно характеризовать величиной $R=P/N$, называемой степенью избыточности представления чисел в этой системе. Именно наличие определенной избыточности представления чисел в СОК позволяет обнаруживать и корректировать ошибки, возникающие как в процессе ранения, так и обработки информации.

В зависимости от соотношения между величинами $N$, $M$ и $P$ можно классифицировать корректирующие коды, как показано на рис.2 [4].

Рис.2. Классификация корректирующих кодов в модулярной арифметике.

При этом R-коды соответствуют системам со взаимно простыми основаниями, а коды второго и третьего классов соответствуют системам с основаниями, не являющимися взаимно простыми. В данной работе рассматриваются наиболее распространенные и эффективные R-коды в классической системе остаточных классов со взаимно попарно простыми модулями ${m_{i},m_{2},...,m_{p}}$, для которой $M=P$.

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

Поскольку избыточность системы остаточных классов является первостепенным фактором при оценке эффективности любого корректирующего кода, то необходимо становить связь между ее величиной и свойствами кода по обнаружению и коррекции ошибок. Чаще всего для этого используют понятие минимального расстояния кода, т.е. наименьшего расстояния между любыми двумя кодовыми словами [4], [13], [14], [16], [17]. В общем случае, расстоянием $d$ между любыми двумя векторами $A_{1}$ и $A_{2}$ или $d(A_{1},A_{2})$ назовем число компонент, в которых эти векторы отличаются друг от друга. В свою очередь, минимальное расстояние кода $d_{min}$ определяется следующим образом:

$d_{min} = min \{d(\bar A_{i},\bar A_{j}): \bar A_{i},\bar A_{j} \isin \Omega, \bar A_{i} \neq \bar A_{j}\}$ (1)

Очевидно, что величина расстояния между различными векторами изменяется от 1 до p, при этом двум соседним числам $A_{1}$ и $A_{2}$, отличающимся на единицу, соответствуют векторы $\bar A_{1}$ и $\bar A_{2}$, расстояние между которыми равно $p$ для любой СОК. Кроме того, каждому вектору $\bar A$ можно присвоить определенный вес $W(\bar A)$, равный числу ненулевых компонент этого вектора. Связь расстояния между двумя векторами и их весами можно легко установить с помощью выражения:

$d(\bar A_{1},\bar A_{2}) = W(\bar A_{1}-\bar A_{2})$ (2)

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

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

2) исправление (коррекция) ошибки, т.е. преобразование искаженного результата в правильное кодовое слово.

Самым простым по своей сути, но сложным, с точки зрения реализации, способом обнаружения ошибки является сравнение результата с каждым возможным кодовым словом. Если он не является правильным, но принадлежит кодовому пространству $\Omega$, то произошла необнаруживаемая ошибка. Если же результат не принадлежит кодовому пространству $\Omega$, то наличие ошибки обнаружено. Это значит следует определить такой параметр корректирующего кода как способность обнаружения ошибки $l$ - наибольшая кратность ошибки, которая может произойти при условии, что результат вычислений не будет принадлежать кодовому пространству $\Omega$. Иными словами это максимальный вес ошибки, при котором результат не попадает в кодовое пространство $\Omega$. Связь между способностью обнаружения ошибки и минимальным расстоянием кода устанавливается следующим соотношением:

$l = d_{min}-1$ (3)

Таким образом, корректирующий код в СОК может обнаружить все совокупности из $l$ или меньшего числа ошибок лишь в том случае, если минимальное расстояние кода больше $l$.

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

$k = \left\lfloor \frac{(d_{min}-1)} 2 \right\rfloor$ (4)

Другими словами, корректирующий код в СОК может исправить (скорректировать) все совокупности из $k$ или меньшего числа ошибок лишь в том случае, если минимальное расстояние кода больше удвоенного числа ошибок. Из выражений (2) и (3) следует, что корректирующий код в избыточной СОК способен исправлять любые $k$ ошибок и одновременно обнаруживать любые $l (l>k)$ ошибок в том случае, если его минимальное расстояние больше либо равно $k+l+1$. Таким образом, определив минимальное расстояние кода, можно получить представление о его корректирующих способностях. Стоит заметить, однако, что минимальное расстояние дает довольно грубую оценку возможностей кода, не раскрывая полностью его структуру, и позволяет определить лишь гарантируемый минимум числа обнаруживаемых или корректируемых ошибок. Переходя к рассмотрению непосредственно R-кодов, применяемых для построения отказоустойчивых систем, отметим, что для них $M=P$, а степень избыточности R зависит от соотношения $M/N$. Такие коды могут иметь любое минимальное расстояние в зависимости от величины $R$, определяемое из условия:

$R \geq \prod^{(d_{min}-1)}_{j=1} m_{q_{j}}$ (5)

где $q_{j}=1,2,...,p$. Данная запись означает, что корректирующий R-код имеет минимальное расстояние $d_{min}$ в том и только в том случае, если степень избыточности $R$ не меньше произведения любых $(d_{min}-1)$ оснований заданной СОК. На самом деле R-код с минимальным расстоянием $d_{min}$ может обнаруживать и корректировать некоторое число ошибок более высокой кратности, чем та, которая определяется выражениями (3) и (4). Например, если в СОК имеются такие основания, число которых $d_{l} \geq d_{min}$, что их произведение меньше R, то любые ошибки по этим модулям можно обнаружить. В общем случае довольно сложно оценить долю ошибок произвольной кратности $t$, которые можно обнаружить или исправить при помощи кода с минимальным расстоянием, меньшим $dmin<2t+1$. Сложность заключается в том, что даже при достаточно грубых оценках необходимо знать не только величину $R$, но и величину каждого из модулей системы. Поэтому наиболее реальным способом получения информации о возможностях каждого конкретного кода является статистическое моделирование.

Проанализировав условие (5), можно заключить, что минимальное расстояние R-кода напрямую зависит от степени избыточности системы остаточных классов, которая, каким образом, определяет корректирующие способности этого кода согласно выражениям (3) и (4). Очевидно, что чем больше избыточность СОК, тем более широкими возможностями обладает соответствующий ей R-код. Повышение степени избыточности достигается путем введения в СОК $r$ дополнительных модулей, называемых также контрольными. Основные модули системы ${m_{1},m_{2},...,m_{p}}$, произведение которых равно $M$, в данном контексте называют информационными. Помимо этого целесообразно ввести также следующие обозначения:

$M=m_{1} \cdot m_{2} \cdot ... \cdot m_{p} = \prod^{p}_{i=1} m_{i}$ (6)

$M^{T}=m_{1} \cdot m_{2} \cdot ... \cdot m_{p} \cdot m_{p+1} \cdot ... \cdot m_{p+r} = \prod^{p+r}_{i=1} m_{i}$ (7)

$M^{R}=m_{p+1} \cdot m_{p+2} \cdot ... \cdot m_{p+r} = \prod^{p+r}_{i=p+1} m_{i}$ (8)

Будем называть величину $M$, рабочим диапазоном, а $M^{T} = M \cdot M^{R}$ полным диапазоном системы. Если сравнивать полученный таким образом R-код с рассмотренными выше специальными позиционными кодами, то он также состоит из двух частей - информационной (1:p) и контрольной (p+1:r):

$\bar A=\{\bar a_{1}, \bar a_{2},...,\bar a_{p}, \bar a_{p+1}, \bar a_{p+2},...,\bar a_{r} \}$ (9)

Ключевое отличие заключается в том, что обе части такого кода равноправно участвуют во всех операциях внутри независимых вычислительных каналов, соответствующих каждому из модулей системы. Отсюда следует, что любой из информационных разрядов числа в модулярном виде можно заменить контрольным при восстановлении результата вычислений в двоичную систему счисления. Фактически именно эта особенность кодов в модулярной арифметике тем или иным образом используется для коррекции ошибок. Между вводимыми в СОК контрольными модулями и минимальным расстоянием кода существует определенная связь, а именно, минимальное расстояние кода равно $d_{min}$, если и только если произведение контрольных модулей удовлетворяет соотношению:

$max \{\prod^{(d_{min})}_{j=1} m_{q_{j}} \} > M^{R} \geq max \{\prod^{(d_{min}-1)}_{j=1} m_{q_{j}} \}$, где $l \leq q_{j} \leq p+r$. (10)

Из выражения (10) следует, что в общем случае выбор контрольных модулей неоднозначен для заданного набора модулей и минимального расстояния кода $d_{min}$. В связи с этим возникает вопрос о поиске оптимального набора контрольных |модулей для избыточной СОК. Под оптимальным в этом случае понимается такой набор контрольных модулей, при котором значение М* будет минимально для данного минимального расстояния кода $d_{min}$. Очевидно, что наименьшее значение М* при минимальном расстоянии кода $d_{min}$ определяется из (10) как

$M^{R} = max \{\prod^{(d_{min}-1)}_{j=1} m_{q_{j}} \}, 1 < q_{j} < p+r$ (11)

Полученное выражение означает, что оптимальным набором дополнительных или контрольных модулей при минимальном расстоянии кода $d_{min}$ являются $(d_{min}-1)$ наибольших значений в полном наборе модулей. Отсюда следует важное свойство: если каждый контрольный модуль больше любого информационного, то минимальное расстояние кода на единицу больше числа контрольных модулей, т.е.

$d_{min} = r+1$ (12)

при условии

$m_1 < m_2 < ... < m_p < m_{p+1} < ... < m_r$ (13)

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

Обнаружение и коррекция ошибок с помощью R-кодов

Рассмотрим механизм обнаружения и коррекции ошибок с помощью R-кодов. Первый шаг в любой процедуре коррекции и единственный в процедуре обнаружения ошибки это проверка, является ли полученный в результате вычислений вектор кодовым словом. Поскольку все числа, с которыми оперирует устройство должны лежать в диапазоне $[0, M)$, то его называют диапазоном правильных чисел, а принадлежащие ему числа правильными. В то же время числа из диапазона $[M, M^T)$ являются неправильными, а сам он называется диапазоном неправильных чисел. Очевидно, что если в результате какой-либо операции или при передаче числа оказалось, что получено число $\bar A' > M$, то при проведении операции была допущена ошибка. Таким образом, обнаружение одиночной ошибки основано на том факте, что любое искажение цифры по одному из оснований превращает все число в неправильное. Поэтому для обнаружения одиночной ошибки в числе $\bar A'$ его нужно сравнить с рабочим диапазоном $M$. При этом, если $\bar A' \geq M$, значит произошла ошибка по крайней мере в одном из каналов. Если $\bar A' < M$, то либо ошибки нет, либо она носит более сложный характер.

Описанное выше свойство корректирующих кодов применяется при обнаружении и коррекции ошибок на основе метода проекций [1], [4], [10], [11], [12], [15], [17]. Проекцией числа $A$ по основанию $m_i$, называется число $A_i$, полученное из $A$ вычеркиванием соответствующего остатка $a_i$. По своей сути алгоритм определения ошибочной цифры и ответствующего ей модуля на основе проекций довольно прост. Необходимо вычислить проекции числа $\bar A'$ по каждому из модулей системы, а затем сравнить их с величиной $M$. Если какая-либо из проекций $\bar A'_i$ окажется меньше значения $M$, т.е. будет правильным числом, то ошибка произошла в соответствующем модуле $m_i$. Иными словами, если полученное в результате вычислений число $\bar A'$ является правильным, то все его проекции должны быть неправильными числами. Таким образом, метод проекций позволяет установить в цифре по какому из модулей системы произошла ошибка, т.е. обеспечивает ее локализацию. Однако, как и сам алгоритм определения ошибочной цифры, так и последующая ее коррекция на основе метода проекций представляются малоэффективными и затратными с точки зрения практической реализации. А именно, вычисление каждой из проекций требует выполнения операции восстановления числа из модулярного представления в двоичное и последующих вычислений над числами большой разрядности, что вносит значительный вклад как в аппаратные затраты, так и в задержку работы устройства. Кроме того, такой метод подразумевает исправление лишь ошибочного остатка, а не всего числа, приводя к необходимости восстанавливать число с уже правильными значениями всех остатков. В связи с этим возникает необходимость искать другие методы реализации механизма обнаружения и коррекции ошибок в СОК.

Одной из альтернатив методу проекций для обнаружения и коррекции ошибок в СОК является синдромное декодирование с вычислением так называемых синдромов ошибки по контрольным основаниям системы [19], [13], [14], [20], [16], [17]. В основе этого метода чаще всего лежит так называемая операция расширения системы оснований (base extension, ВЕХ). Это немодульная операция, позволяющая по известным остаткам числа, соответствующим некоторым модулям СОК, определить значения остатков этого же числа для других оснований. Обычно для реализации операции расширения системы оснований используют систему счисления со смешанными основаниями (ССО), переход к которой носит итеративный характер и может привести к ухудшению быстродействия всего устройства.

Суть метода синдромного декодирования заключается в следующем. Пусть в результате вычислений в СОК получено некоторое число $Y'=\{y'_1,y'_2, ..., y'_p\}$. Для определения правильности числа $Y'$ необходимо по известным остаткам $y'_1,y'_2, ..., y'_p$ определить значения его остатков по контрольным основаниям $y'_{p+1},y'_{p+2}, ..., y'_{p+r}$. Затем следует сравнить значения $y'_{p+1},y'_{p+2}, ..., y'_{p+r}$ с $\bar y_{p+1},\bar y_{p+2}, ..., \bar y_{p+r}$ - остатками по тем же модулям, но образованными уже в ходе вычислений над входными данными, аналогичных тем, в результате которых было получено само число $Y'$. Сравнение остатков по контрольным основаниям можно осуществить их вычитанием:

$s_{p+i} = {|y'_{p+i} - \bar y_{p+i}|}_{p+i}$, где $i=1, ... ,r$. (14)

Числа $s_{p+i}$ называются синдромами ошибки, т.е. позволяют определить [правильность результата вычислений в СОК. В предположении, что в полученном числе $Y'$ оказались искаженными не больше чем $t$ остатков, для кода, имеющего минимальное расстояние $d_{min} = 2t+1$, можно сформулировать следующие свойства синдромов ошибки:

1) Если все значения синдромов равны нулю: $s_{p+1}=s_{p+2}=...=s_{p+r}=0$, то ошибки не возникло и вектор $Y'$ является кодовым словом;

2) Если $j$ значений синдромов $(1 \geq j \geq t)$ не равны нулю, то ошибки произошли в соответствующих остатках по контрольным модулям, при этом вектор $Y'$ является кодовым словом;

3) Если больше чем $t$ значений синдромов не равны нулю, то произошла по меньшей мере одиночная ошибка в векторе $Y'$.

Для демонстрации данного механизма обнаружения и исправления ошибок с применением корректирующих кодов в модулярной арифметике, рассмотрим случай построения отказоустойчивой системы с исправлением одиночных ошибок. Такая система обеспечивает минимальные возможности по коррекции ошибок и наиболее часто обсуждается в литературе. Согласно формуле (4) такой код должен иметь минимальное расстояние $d_{min}=3$. В соответствии с (12) данное значение минимального расстояния кода достигается введением в СОК двух контрольных модулей $m_{p+1}$ и $m_{p+2}$. Обычно значения синдромов ошибки $s_{p+1}$ и $s_{p+2}$ используют как для обнаружения, так и для коррекции обнаруженных ошибок. Это становится возможным благодаря тому, что каждой паре значений $\{s_{p+1}, s_{p+2}\}$ соответствует единственное значение вектора ошибки, а значит и корректирующего слова для ее исправления. Таким образом, коррекция ошибки при использовании данного метода осуществляется сложением числа, содержащего ошибку, и корректирующего слова, вычисленного по значениям синдромов $s_{p+1}$ и $s_{p+2}$. Стоит также отметить, что при коррекции в данном случае складываются обычные двоичные числа, а поэтому нет необходимости в каких-либо дополнительных преобразованиях.

Одним из наиболее эффективных и распространенных в литературе вариантов и отказоустойчивых систем с указанными выше свойствами является представленная на рис.3 архитектура [19], [20].

Рис.3. Вариант общей архитектуры отказоустойчивой системы с обнаружением и коррекцией одиночных ошибок в СОК.

Для достижения требуемого уровня надежности устройства необходимо введение определенной избыточности путем включения в систему оснований контрольных модулей. Учитывая условие (13), становится вполне очевидным, что в результате повышения избыточности системы таким образом, при соблюдении условия взаимной простоты ее оснований, разрядность контрольных модулей неизбежно растет, а следовательно растут и разрядности операндов в соответствующих вычислительных каналах. Это обстоятельство может привести к значительному ухудшению быстродействия всего устройства, что, безусловно, является неприемлемой платой для большинства современных вычислительных систем. Поэтому возникает необходимость разработки эффективных методов аппаратной реализации основных вычислительных блоков отказоустойчивых систем, позволяющих избежать снижения быстродействия при их проектировании с одной стороны, а с другой - минимизировать аппаратную избыточность (Рис.4)[26].

Рис.4. Особенности применения R-кодов при реализации систем повышенной надежности на основе аппарата модулярной арифметики.

Хотя значительная часть известных методов и алгоритмов функционирования основных вычислительных узлов в модулярной арифметике либо ориентированы на устаревшую элементную базу, либо рассмотрены лишь с теоретической точки зрения, а их эффективная аппаратная реализация и реальные оценки ее сложности представлены недостаточно для применения на практике при проектировании вычислительных систем. Часто методы, описанные в основном в зарубежной литературе, носят незаконченный характер и не дают полного представления о внутренней структуре того иного блока, что необходимо для действительно эффективной с практической точки зрения реализации. В то же время современное развитие различных методов, приемов и средств проектирования позволяет по-новому взглянуть даже на существующие и известные принципы построения как отдельных вычислительных узлов, так и систем в целом, в том числе и систем повышенной надежности [21], [22], [23], [24], [25], [26].

Литература

1. Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. - М.: Советское радио, 1968. - 440с.

2. Коёкин А. И. Структурные методы обеспечения надежности информационных систем// Диссертация на соискание ученой степени доктора технических наук. - Москва, 1974. - 303с.

3. Конопелько В. К., Борискевич А. А. Контроль ошибок в цифровых устройствах// Учеб. пособие по курсам "Теория кодирования" и "Цифровые и микропроцессорные устройства". - Мн.: БГУИР, 2003. - 18с.

4. Торгашев В. А. Система остаточных классов и надежность ЦВМ. - М.: Советское радио, 1973. - 120с.

5. Watson R. W., Hastings C. W. Self-Checked Computation Using Residue Arithmetic// Proceedings of the IEEE, vol. 54, no. 12, December 1966. - P.1920-1931.

6. Угрюмов Е. П. Цифровая схемотехника. - СПб.: БХВ-Петербург, 2002. - 528с.

7. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986.-576с.

8. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. М.: Радио и связь, 1987. - 391с.

9. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976. -590с.

10. Barsi F., Maestrini P. Error Correcting Properties of Redundant Residue Number Systems// IEEE Transactions on Computers, vol. C-21, no. 3, March 1973. P. 307-315.

11. Barsi F., Maestrini P. Error Detection and Correction by Product Codes in Residue Number Systems// IEEE Transactions on Computers, vol. C-23, no. 9, September 1974. -P. 915-924.

12. Jenkins W.K., Altman E.J. Self-Checking Properties of Residue Number Error Checkers Based on Mixed Radix Conversion// IEEE Transactions on Circuits and Systems, vol. 35, no. 2, February 1988. P. 159-167.

13. Krishna H., Lin K.-Y., Sun J.-D. A Coding Theory Approach to Error Control in Redundant Residue Number Systems - Part I: Theory and Single Error Correction// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 39, no. 1, January 1992.-P. 8-17.

14. Krishna H., Sun J.-D. On Theory and Fast Algorithms for Error Correction in Residue Number System Product Codes// IEEE Transactions on Computers, vol. 42, no. 7, July 1993.-P. 840-853.

15. Orton G.A., Peppard L.E., Tavares S. E. New Fault Tolerant Techniques for Residue Number Systems// IEEE Transactions on Computers, vol. 41, no. 11, November 1992. -P.1453-1464.

16. Sun J.-D., Krishna H. A Coding Theory Approach to Error Control in Redundant Residue Number Systems - Part I: Multiple Error Detection and Correction// IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 39, no. 1, January 1992.-P. 18-34.

17. Yang L.-L., Hanzo L. Coding Theory and Performance Of Redundant Residue Number System Codes// submitted to IEEE Transactions on Information Theory, 1999. 40 p.

18. Yang L.-L., Hanzo L. Redundant Residue Number System Based Error Correction Codes// IEEE Vehicular Technology Conference, 2001. IEEE VTC 54th, vol. 3, 7-11 October 2001.-P. 1472-1476.

19. Cosentino R.J. Fault Tolerance in a Systolic Residue Arithmetic Processor Array// IEEE Transactions on Computers, vol. 37, no. 7, July 1988. P. 886-890.

20. Radhakrishnan D., Preethy A.P. A novel 36-bit single fault tolerant multiplier using 5-bit moduli// IEEE TENCON 98, vol. 1, pp. 128-130, New Delhi, India, Dec. 1998.

21. Исследование методов пректирования и разработка прграмных средств синтеза быстродействующих арифметических устройств// Отчет о НИР по программе ОИТВС РАН " Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сетевых технологий" (шифр "Вега-О-Ст-2006"). #ГР 01.200606060, инв.#0220.0701842. М.: ИППМ РАН, 2006.

22. Калашников В.С. Основные принципы построения отказоустойчивых систем с применением аппарата модулярной арифметики. Микроэлектроника и информатика-2006. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов, М.:МИЭТ, 2006. - С. 237.

23. Корнилов А.И., Семенов М.Ю., Ласточкин О.В., Калашников В.С. Методология проектирования специализированных вычислителей на основе автоматизированной генерации технологически независимых IP-блоков.// Проблемы разработки перспективных микроэлектронных схем -2005. Сборник научных трудов/ под общ. ред. А. Л. Стемпковского. М.: ИППМ РАН, 2005. - 537с., С.487-492.

24. Корнилов А.И., Семенов М.Ю., Ласточкин О.В., Калашников В.С. Реализация специализированных быстродействующих вычислителей на основе нетрадиционных алгоритмов с применением IP-генераторов. 5 Международная научно-техническая конференция "Электроника и информатика". - 2005.

25. Стемпковский А.Л., Корнилов А.И., Семенов М.Ю., Ласточкин О.В., Калашников В.С. Построение систем повышенной надежности на основе аппарата модулярной арифметики с применением современных методов и средств проектирования// Проблемы разработки перспективных микроэлектронных схем -2006. Сборник научных трудов/ под общ. ред. А. Л. Стемпковского. М.: ИППМ РАН, 2006. - 452с., С.253-258.

26. Калашников В.С. Исследование и разработка методов проектирования быстродействующих вычислительных узлов для реализации отказоустойчивых систем на основе модулярной арифметики// Диссертация на соискание ученой степени доктора технических наук. - Москва, 2007. - 180 с.