Алгоритм исправления ошибок в модулярном коде СОК, основанный на расширении системы оснований

Дата публикации: 2020-02-29 14:59:09
Статью разместил(а):
Гапочкин Артем Владимирович

Алгоритм исправления ошибок в модулярном коде СОК, основанный на расширении системы оснований

Method of correction localized errors in the code of RNS, based on the base extension

 

Автор: Гапочкин Артем Владимирович

Московский Политехнический Университет, г. Москва, Россия

e-mail: warrior_555@rambler.ru

Gapochkin Artem Vladimirovich 

Moscow Тechnical University, Moscow, Russia 

e-mail: warrior_555@rambler.ru 

 

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

Abstract: One of the most important applications of system residue number is to control errors in a numbers, transmitted on communication channels. The best known method is the method of projections for the localization of errors. The article describes a method of correct errors that are found by the method of projections, based on the base extension. This method is characterized by modularity of its constituent operations and efficiency compared to existing conventional counterparts. 

Ключевые слова: коррекция ошибок, система остаточных классов (СОК), модулярный код.

Keywords: error correction, system of residual classes (RNS), modular code.

Тематическая рубрика: технические науки и технологии.

 

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

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

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

Рассмотрим более подробно метод проекций. Пусть задана упорядоченная система взаимно простых оснований, в которой первых оснований являются информационными, а основания – контрольными. Информационные основания образуют рабочий диапазон представления СОК. Для обеспечения возможности локализации и исправления ошибок в коде СОК на выбор рабочих и контрольных оснований накладывается ряд ограничений, описанных в [3]. Пусть в данной системе представлено число. Требуется определить, ошибочно оно или нет, и по возможности исправить ошибку.

Обнаружить ошибку можно, сравнив число со значением. Если выполняется неравенство, то ошибки нет, иначе – в одном или нескольких каналах произошло искажение данных [3]. Сравнение в СОК является немодульной операцией. Один из самых простых путей решения проблемы сравнения – это преобразовать код СОК в позиционный и сравнить его с диапазоном в традиционной системе счисления.  Переход из СОК в ПСС можно осуществить, например, с помощью ортогональных базисов, где, по формуле. Такой подход влечет большие вычислительные затраты. Один из путей выхода из сложившегося положения предложен в [2], где для обнаружения ошибки применяется приближенный метод.

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

Непосредственно метод локализации состоит в следующем. Находятся все проекции числа. Далее с помощью рассмотренных ранее методов сравнения проверяется условие для каждой полученной проекции. Если условие не выполняется, то остаток по данному модулю считается правильным, в случае выполнения условия считается, что ошибка произошла по данному основанию [3,5].

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

Уменьшить число немодульных операций можно, применяя вместо формулы (1) специальный способ расширения системы оснований. Пусть есть диапазон усеченной системы остаточных классов, из которой исключено основание, в остатке по которому была обнаружена ошибка. Согласно построению избыточной СОК, где рабочий диапазон исходно СОК. Данное утверждение следует из того, что контрольные основания выбираются как самые большие из всего множества оснований. Таким образом, число не превосходит и применение расширения системы оснований является корректным. Один подходящих методов расширения системы оснований описан в [1,6].

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

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

 

Список литературы:

1. Червяков Н.И., Бабенко М. Г., Ляхов П. А., Лавриненко И. Н. Приближенный метод ускоренного обнаружения и локализации неисправного вычислительного канала в ЭВМ, функционирующей в системе остаточных классов // Нейрокомпьютеры: разработка, применение. М: «Радиотехника». № 10. 2011 г. – С. 13 – 19.

2. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Ряднов С. А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. – М: «Физматлит», 2003. – 288 с.

3. Gapochkin A.V., Popov D.I., Development and application of composite logistics functions to improve the speed of training of wavelet neural networks in speech recognition systems// ARPN Journal of Engineering and Applied Sciences. 2016. Т. 11. № 1. С. 73-77.

4. Гапочкин А.В., Калмыков М.И., Васильев П.С. обнаружение и коррекция ошибки на основе вычисления интервального номера кода классов вычетов // Современные наукоемкие технологии. 2014. № 6. С. 9-13.

5. Амербаев В.М. Теоретические основы машинной арифметики. – Алма-Ата: Наука, 1976. – 324 с.

6. Molahosseini A.S., Sorouri S., Zarandi A.A.E.   Research challenges in next-generation residue number system architectures // Proc. 7th IEEE Conf. On Computer Science & Education, Melbourne, 2012. P. 1658-1661.