USE OF SPECIAL MODULES OF THE RESIDUE NUMBER SYSTEM FOR REDUNDANT REPRESENTATION
Authors:
1.
North-Caucasian Federal University
Type:
Article
Pages:
from 75
to 85
Status:
Published
Received:
05.04.2013
Accepted:
25.04.2013
Published:
25.04.2013
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.5
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
BBK (Ж/О) 31.264.5
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.5
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
BBK (Ж/О) 31.264.5
Language:
Russian
Keywords:
residue number system, converter of binary code to residue number system, carry save adder, computer arithmetic
Abstract (English):
The residue number system (RNS), due to its properties, is used in applications in which high accuracy of computations is not required. Since carries are not transmitted between the moduli in the RNS, the performance is only restricted by the speed of the operations in each modulus. A new method of number representation using the redundancy is suggested in which is a set of the reference modules, where and. This method provides a significant reduction of delay of computations and conversions and leads to a simplification of schemes.
The residue number system (RNS), due to its properties, is used in applications in which high accuracy of computations is not required. Since carries are not transmitted between the moduli in the RNS, the performance is only restricted by the speed of the operations in each modulus. A new method of number representation using the redundancy is suggested in which is a set of the reference modules, where and. This method provides a significant reduction of delay of computations and conversions and leads to a simplification of schemes.
Keywords:
residue number system, converter of binary code to residue number system, carry save adder, computer arithmetic
residue number system, converter of binary code to residue number system, carry save adder, computer arithmetic
Введение Система остаточных классов (СОК) предоставляет большие возможности для высокоскоростного выполнения арифметических операций за счет дробления операндов на несколько маленьких остатков и независимого параллельного проведения операций с остатками [1]. Система остаточных классов может поддерживать переносы, ограниченные высокой скоростью арифметических вычислений и высокими требованиями по обнаружению ошибок, а также с высокими требованиями и к приложениям, связанным с обнаружением ошибок [2]. Ввиду этих уникальных возможностей ее использование в различных областях стремительно растет. Приложениями СОК являются цифровая обработка сигналов (ЦОС), цифровая обработка изображений, цифровой фильтр, быстрое преобразование Фурье (БПФ) вычислений [3]. Наборы модулей должны быть выбраны таким образом, чтобы их члены были попарно взаимно простыми [4]. Если выбран набор модулей , то число X в пределах динамического диапазона M представлено соответствующими остатками j-кортежа набора : ... (1) В (1) является неотрицательным целым числом [4, 5]. Представим несколько наборов модулей: , , , , которые были использованы в последних работах по СОК [6]. В [7], однако, представлен набор модулей , где и , который используется в ходе наших исследований, что делает метод более общим по сравнению с . Последовательность подачи материала в статье такова: пояснения об избыточной системе остаточных классов (ИСОК); предложенный метод представления чисел; методология поиска эквивалентного числа ИСОК в модулях и связанных с ними схем; демонстрация сумматоров в этом наборе модулей; сравнение предложенного метода с другими; выводы. Избыточность в компьютерной арифметике и избыточная СОК При использовании избыточности в компьютерной арифметике учитываются следующие преимущества: 1) повышение надежности; 2) повышение скорости вычислений; 3) обеспечение структурной гибкости [8]. Для реализации первого используется аппаратная избыточность и (или) избыточные арифметические коды. Для второго и третьего случаев применяются различные методы. Одним из методов использования быстрых элементов является сумматор с запоминанием переноса (CSA). Избыточность в представлении – это другой устойчивый метод, который был широко использован в [8]. В СОК существуют три типа избыточности [4]: 1. Дополнительные остатки (модули), используемые в тех случаях, когда целью является создание желаемого динамического диапазона. 2. Избыточное представление обычных остатков, которые подходят, когда необходима быстрая арифметика. 3. Избыточные остатки с диапазоном, превышающим значения в для некоторых (в mod-m остатков). Мы, в отличие от ряда исследователей, которые сосредоточили свое внимание на первом случае, в данной статье исследуем комбинации второго и третьего случаев. Избыточное представление остатков в предлагаемом подходе Мы используем большие основания для набора модулей , где и , которые были широко исследованы в [9]. Для представления числа в обычной системе применим многозначную логику (МЗЛ). По сравнению с двоичной логикой, МЗЛ способна представлять большие числа с меньшим количеством позиций. Хотя n цифр достаточно для представления остатков в модулях , и , мы используем в нашем методе 2n цифр, которые означают, что мы выигрываем от n-битовой избыточности. CSA – основной элемент для реализации схем. Мы определим частичную Sum и частичный Carry последнего CSA в схемах как конечные выходы, которые показывают остаток, таким образом, чтобы полученный остаток имел 2n цифр вместо n цифр (n-значная Sum и n-значный Carry). В этом методе для представления остатка существует класс эквивалентности, который содержит все возможные представления остатка с n-значной Sum и n-значным Carry с заданным ограничением (Sum и Carry являются выходами CSA). Sum цифр принадлежит интервалу [0, r – 1], однако интервал Carry ограничен на интервале [0, 6], за исключением цифры младшего разряда Carry, которая может быть до 12. Преобразователи для набора модулей с избыточностью В обычной системе необходимо 3n цифр для представления чисел с набором модулей , потому что в динамическом диапазоне однозначно должны быть охвачены все возможные целые числа. Это доказывается следующим образом. Теорема 1. Динамический диапазон набора модулей охватывает 3n цифр. Доказательство. Докажем, что следующее неравенство является верным, что докажет теорему: . В последнем неравенстве правая часть наибольшего значения достигает, когда и . Тогда . Последнее неравенство всегда верно, так что теорема доказана. Таким образом, число X представлено следующим образом: . Согласно тому, что обсуждалось ранее, A, B и C являются n-значными. Остаток X по отношению к модулю будет получен следующим образом. A. Остаток по модулю Совершенно очевидно, что остаток по модулю – это число, которое показано самой правой цифрой X(C). . В нашем методе мы должны только преобразовать остаток в принятом избыточном представлении. Это будет реализовано набором всех n цифр Carry к нулю. Таким образом, представление выглядит следующим образом: . B. Остаток по модулю Этот остаток будет получен следующим образом: . (2) Формула (2) показывает, что требуется вычислить , а затем вычислить остаток полученной суммы по модулю . Для проверки правильности расчета были проанализированы различные возможные значения A, B и C. Динамическим диапазоном набора модулей является , где представимые числа принадлежат . Таким образом, самым большим представимым числом является . Это число вычисляется следующим образом: .. .. .. Поэтому мы можем записать: ... (3) В (3) суммирование A, B и C выводит выходной сигнала переноса 1. Теперь рассмотрим следующий случай в пределах динамического диапазона, который показывает, каким образом могут быть разработаны схемы: ..., где и . И для : ... (4) В (4) при расчете A + B + C выходной сигнал переноса равен 2. Так как в этом модуле каждое устройство выходного сигнала переноса (Cout) имеет значение 1, то, чтобы принять это значение для расчета, используется сумматор с запоминанием переноса с окончанием вокруг переноса (CSA с EAC). Популярный полный сумматор (ПС) ячейки в двоичном виде имеет 3-входа и 4-входа – в троичном виде, поэтому CSA в первом является 3-к-2 и в последнем – 4-к-2 [10]. CSA в системе счисления r описан в теореме 2. Теорема 2. CSA в системе счисления r может иметь до входов. Доказательство. Полный сумматор основной ячейки в системе счисления r имеет два однозначных выхода (Carry и Sum), а максимальное значение каждого выхода . Таким образом, максимальное представимое число в выходе ячейки в системе счисления r – это . Предположим, что все входы . Сумма этих входов должна быть представлена в выходе таким образом, чтобы максимальное число входов (l) определялось наибольшим представимым числом на выходе. Поэтому мы можем записать: . Доказано, что CSA в системе счисления r может иметь до входов. Каждая ячейка CSA, которая используется в дальнейшем, может занять цифр (входы) и возвращает две цифры (выходы) в качестве Sum и Carry. Если входов требуется меньше , мы будем применять на входах все нули, которые не связаны, однако эти неиспользуемые входы не проиллюстрированы на рисунках. При использовании в реализации CSA с EAC выходы показывают в любом случае правильный результат. На рис. 1 показан преобразователь по модулю . Рис. 1. Преобразователь по модулю C. Остаток по модулю Для получения остатка по этому модулю используется следующая процедура: . Пока основание системы счисления равно r , используется CSA, максимальное значение генерируется выходным сигналом переноса из расчета = 6. В этом модуле каждое устройство выходного сигнала переноса имеет значение 2, поэтому выходной сигнал переноса следует добавить к полученным Sum и Carry на следующем уровне. В этом модуле мы должны разработать преобразователь для пяти случаев отдельно. В системе счисления и максимальное количество входов равно 4 и 6 соответственно. Преобразователь по модулю , где , продемонстрирован на рис. 2, и преобразователь будет упрощен для , как показано на рис. 3. Так как для третий уровень CSA не создает выходной сигнал переноса, будет применено это упрощение, и выходной сигнал переноса второго уровня будет размещен в значимой позиции конечного Carry. Понятно, что для в этом модуле остаток всегда равен 0. Так как число входов ограничено, на первом уровне используются два параллельных CSA. Рис. 2. Преобразователь по модулю , где Рис. 3. Преобразователь по модулю , где ис. 4 иллюстрирует преобразователь по модулю 5n – 2. С каждой цифрой последнего Carry до 2 (получено путем анализа), для добавления выходного сигнала переноса, используется только одно основание r ПС (Cout и цифра младшего разряда являются входами). В этом модуле Sum ПС будет размещена в значимой позиции конечного Carry. Как и в случае предыдущего преобразователя, это преобразование осуществляется в трех уровнях, однако необходимое оборудование сокращается. Следовательно, преобразователи упрощаются. Этот факт станет очевидным на следующих рисунках, на которых показаны преобразователи высших оснований. Рис. 4. Преобразователь по модулю 5n – 2 Для преобразователь по модулю такой, как на рис. 5. Рис. 5. Преобразователь по модулю , где Для , где , преобразователь для модуля реализован на рис. 6. Рис. 6. Преобразователь по модулю , где СОК-сумматоры с набором модулей Арифметические операции могут быть выполнены, когда число X преобразуется к виду ИСОК в результате вышеуказанных уравнений. Напомним, что произведенный остаток имеет Sum, а также сопутствующий Carry и что в СОК каждый модуль имеет отдельный сумматор, поэтому сумматоры по модулям , и будут рассчитаны следующим образом. Предположим, что D и Е – это числа, которые будут сложены; F – это результирующее число. А. Сумматор модуля Согласно вышесказанному, в нашем методе Carries остатков по модулю равны нулю. Поэтому мы не используем Carries для выполнения операции сложения, мы только складываем, добавляя Sums. Цифры Carry не могут быть больше 6 (цифра младшего разряда не может быть более 12), сумматор показан на рис. 7. Рис. 7. Сумматор модуля B. Сумматор модуля Сумматор в этом модуле, показанный на рис. 8, реализован так же, как и предыдущий сумматор. В этом сумматоре используются как Sums, так и Carries в качестве входов CSA. Рис. 8. Сумматор модуля C. Сумматор модуля Максимальный выходной сигнал переноса из первых в CSA по модулю сумматора равен 2 и равен 1 для всех других случаев. На рис. 9 и 10 соответственно показаны сумматоры по модулю и другие модули типа . Cout и цифра младшего разряда Carry являются входами ПС на рис. 10. Рис. 9. Сумматор модуля Рис. 10. Сумматор модуля , где и Сравнения Поскольку набор модулей был введен и полностью описан в [9], мы сравним предложенную схему с [9]. Эти сравнения представлены в табл. 1 и 2. В табл. 1 приведены сравнения задержки в преобразовании, а в табл. 2 показано сравнение задержки в сложении. Таблицы показывают увеличение скорости в схемах. Схемы прямого преобразователя и сумматоров могут быть выполнены n раз самостоятельно ( – показатель по модулю ). Таким образом, происходит значительное сокращение задержек схем, которые более заметны на больших основаниях. Кроме того, по сравнению со схемами, приведенными в [9], для больших оснований соответствующие схемы в нашем методе намного проще. Таблица 1 Сравнение задержки в преобразовании Максимальная задержка в предложенном методе Максимальная задержка в [9] Модуль 0 0 Таблица 2 Сравнение задержки в сложении Максимальная задержка в предложенном методе Максимальная задержка в [9] Модуль Заключение Таким образом, нами были использованы большие основания для набора модулей. Предложен новый избыточный метод для представления остатков. Использование избыточного метода приводит к эффективной конструкции с точки зрения задержки соответствующих схем. За счет использования n избыточных цифр будет достигнуто значительное сокращение задержки преобразования и вычислительных сетей в арифметическом остатке. Задержки представленных схем с использованием общего набора модулей не зависят от показателя модуля n. Таким образом, большие модули, которые генерируют большие остатки, будут иметь короткие задержки в схемах, и, кроме того, для задержки – это постоянные кратные задержек основного полного сумматора ячейки, и это очевидно показывает развитие в построении схем СОК.
1. Chervyakov N. I. Neyrokomp'yutery v sisteme ostatochnyh klassov / N. I. Chervyakov, P. A. Sahnyuk, A. V. Shaposhnikov, A. N. Makoha: ucheb. posobie dlya vuzov. - M.: Radiotehnika, 2003. - 272 s.
2. Barsi F. Error Detection and Correction by Product Codes in Residue Number Systems / F. Barsi, P. Maestrini // IEEE Transactions on Computers. - 1974. - Vol. C-23, N 9. - P. 915-924.
3. Banerjee S. A reconfigurable Digital Signal Processor using residue number system / S. Banerjee, A. Sinha // Information Sciences Signal Processing and their Applications (ISSPA). 10th International Conference on 10-13 May 2010. - P. 405-408.
4. Garner Harvey L. The Residue Number System / Harvey L Garner // IRE Transactions on Electronic Computers. - 1959. - Vol. EC-8, N 2. - P. 140-147.
5. Parhami B. RNS representations with redundant residues / B. Parhami // Signals, Systems and Computers, 2001. Conference Record of the Thirty-Fifth Asilomar Conference. - 2001. - Vol. 2, pp. 1651-1655.
6. Molahosseini A. S. Efficient Reverse Converter Designs for the New 4-Moduli Sets and Based on New-CRTs / A. S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, S. Timarchi // Circuits and Systems I: Regular Papers, IEEE Transactions on. April 2010. - Vol. 57, N 4. - P. 823-835.
7. Khademolhosseini H. A new redundant method on representing numbers with moduli set / H. Khademolhosseini, A. Roohi // Communication and Electrical Technology (ICCCET), 2011. International Conference on. 18-19 March 2011. - P. 163-166.
8. Atkins D. E. Introduction to the Role of Redundancy in Computer Arithmetic / D. E. Atkins // IEEE Computer. - 1975. - Vol. 8, N 6. - P. 74-77.
9. Hosseinzadeh M. A New Moduli Set for Residue Number System: / M. Hosseinzadeh, K. Navi, S. Gorgin // Electrical Engineering, 2007. ICEE’07. International Conference on. 11-12 April 2007. - P. 1-6.
10. Abdallah M. On MultiModuli residue number systems with moduli of forms M. Abdallah, A. Skavantzos // Circuits and Systems I: Regular Papers, IEEE Transactions on. July 2005. - Vol. 52, no. 7, pp. 1253-1266.
