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

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 40: Строка 40:
 
:<math> R \geq \prod^{(d_{min}-1)}_{j=1} m_{q_{j}}</math> (5)
 
:<math> R \geq \prod^{(d_{min}-1)}_{j=1} m_{q_{j}}</math> (5)
  
где <math>q_{j}=1,2,...,p</math>. Данная запись означает, что корректирующий R-код имеет минимальное расстояние <math>d_{min}</math> в том и только в том случае, если степень избыточности <math>R</math> не меньше произведения любых <math>(d_{min}-1)</math> оснований заданной СОК. На самом деле R-код с минимальным расстоянием <math>d_{min}</math> может обнаруживать и корректировать некоторое число ошибок более высокой кратности, чем та, которая определяется выражениями (2) и (3).
+
где <math>q_{j}=1,2,...,p</math>. Данная запись означает, что корректирующий R-код имеет минимальное расстояние <math>d_{min}</math> в том и только в том случае, если степень избыточности <math>R</math> не меньше произведения любых <math>(d_{min}-1)</math> оснований заданной СОК. На самом деле R-код с минимальным расстоянием <math>d_{min}</math> может обнаруживать и корректировать некоторое число ошибок более высокой кратности, чем та, которая определяется выражениями (3) и (4). Например, если в СОК имеются такие основания, число которых <math>d_{l} \geq d_{min}</math>, что их произведение меньше R, то любые ошибки по этим модулям можно обнаружить. В общем случае довольно сложно оценить долю ошибок произвольной кратности <math>t</math>, которые можно обнаружить или исправить при помощи кода с минимальным расстоянием, меньшим <math>dmin<2t+1</math>. Сложность заключается в том, что даже при достаточно грубых оценках необходимо знать не только величину <math>R</math>, но и величину каждого из модулей системы. Поэтому наиболее реальным способом получения информации о возможностях каждого конкретного кода является статистическое моделирование.
 +
Проанализировав условие (5), можно заключить, что минимальное расстояние R-кода напрямую зависит от степени избыточности системы остаточных классов, которая, каким образом, определяет корректирующие способности этого кода согласно выражениям (3) и (4). Очевидно, что чем больше избыточность СОК, тем более широкими возможностями обладает соответствующий ей R-код. Повышение степени избыточности достигается путем введения в СОК <math>r</math> дополнительных модулей, называемых также контрольными. Основные модули системы <math>{m_{1},m_{2},...,m_{p}}</math>, произведение которых равно <math>M</math>, в данном контексте называют информационными. Помимо этого целесообразно ввести также следующие обозначения:
 +
 
  
 
Литература
 
Литература

Версия 12:44, 2 октября 2013

Одним из основных параметров при проектировании сложных вычислительных устройств была и остается надежность их функционирования [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]. Ранее были перечислены основные преимущества модулярного подхода, из которых можно заключить, что модулярная арифметика обладает уникальными свойствами относительно обнаружения и коррекции ошибок. Во-первых, в ней отсутствует значимость порядка цифр в записи числа, а, во-вторых, и коды и проверяемые числа представляются в виде остатков, что позволяет считать такие коды полностью арифметическими. Исходя из этих свойств, можно .сделать вывод о том, что применение модулярной арифметики позволяет эффективно решать проблему построения отказоустойчивых систем и служит мощным инструментом для автоматического обнаружения и коррекции ошибок. Далее рассмотрим теорию, основные понятия и свойства корректирующих кодов в модулярной арифметике в объеме, достаточном для анализа вопросов аппаратной реализации отказоустойчивых вычислительных систем на их основе. Пусть имеется система остаточных классов (COK) с набором модулей \{m_{1}, m_{2},...,m_{p}\} и некоторый вектор A=\{a_{1}, a_{2},...,a_{p}\}, компонентами которого являются натуральные числа, удовлетворяющие условию: 0<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}), где HOK — наименьшее общее кратное, при условии N<M. Тогда каждому числу A из диапазона [0,...,N) можно поставить в соответствие некоторый вектор A из диапазона [0,...,P). При этом подмножество N различных векторов A называют корректирующим кодом, обозначим его через Q, а сами эти вектора кодовыми словами или кодовыми векторами. В случае M=N=P представление чисел в такой системе является безызбыточным. Однако, в общем случае это не так, а значит любую COK можно характеризовать величиной R=P/N, называемой степенью избыточности представления чисел в этой системе. Именно наличие определенной избыточности представления чисел в COK позволяет обнаруживать и корректировать ошибки, возникающие как в процессе ранения, так и обработки информации. В зависимости от соотношения между величинами 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},J_{2}) назовем число компонент, в которых эти векторы отличаются друг от друга. В свою очередь, минимальное расстояние кода d_{min} определяется следующим образом:

d_{min} = min \{d(A_{i},A_{j}): A_{i},A_{j} e Q, A_{i} \neq A_{j}\} (1)

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

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

Теперь, воспользовавшись понятием минимального расстояния кода можно определить его корректирующие возможности. Очевидно, что построение любой отказоустойчивой системы подразумевает под собой реализацию двух основных задач: 1) обнаружение ошибки, т.е. проверка, является ли полученный результат вычислений кодовым словом; 2) исправление (коррекция) ошибки, т.е. преобразование искаженного результата в правильное кодовое слово. Самым простым по своей сути, но сложным, с точки зрения реализации, способом обнаружения ошибки является сравнение результата с каждым возможным кодовым словом. Если он не является правильным, но принадлежит кодовому пространству Q, то произошла необнаруживаемая ошибка. Если же результат не принадлежит кодовому пространству Q, то наличие ошибки обнаружено. Это значит следует определить такой параметр корректирующего кода как способность обнаружения ошибки l - наибольшая кратность ошибки, которая может произойти при условии, что результат вычислений не будет принадлежать кодовому пространству Q. Иными словами это максимальный вес ошибки, при котором результат не попадает в кодовое пространство Q. Связь между способностью обнаружения ошибки и минимальным расстоянием кода устанавливается следующим соотношением:

l = d_{min}-1 (3)

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

k = | \frac{(d_{min}-1)} 2 | (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, в данном контексте называют информационными. Помимо этого целесообразно ввести также следующие обозначения:


Литература


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.


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация