Архив за 30 мая 2012 - 5

В обычной жизни мы обычно пользуемся позиционной системой счисления. В позиционной системе счисления значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда) [1]. Однако существуют и так называемые «непозиционные системы счисления», к одной из которых относится «система счисления в остатках» (или в оригинале Residue Number System (RNS)), являющаяся основой модулярной арифметики. Модулярная арифметика базируется на «Китайской теореме об остатках» [2], которая для нашего случая звучит следующим образом:

Для любой системы взаимно простых чисел p1, … pn, любое число X из диапазона [0; M), где M = p1*p2*…*pn взаимооднозначно представимо в виде вектора (a1, a2, …, an), где ai = X%pi (здесь и далее «%» — операция взятия остатка от целочисленного деления X на pi).
p1, … pn – модули системы
a1, a2, …, an – остатки (вычеты) числа по заданной системе модулей

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

1. Отсутствие переноса разрядов в сложении и умножении. Пусть нам дано два числа X₁ и X₂, представленные в виде системы остатков (x₁₁, x₁₂, …, x_1n) и (x₂₁, x₂₂, …, x_2n) по системе взаимнопростых чисел (p₁, p₂, …, p_n). В этом случае:
   X₃ = X₁ + X₂ = ((x₁₁+x₂₁)%p₁, (x₁₂+x₂₂)%p₂, …, (x_1n+x_2n)%p_n)
   X₄ = X₁ * X₂ = ((x₁₁*x₂₁)%p₁, (x₁₂*x₂₂)%p₂, …, (x_1n*x_2n)%p_n)
   То есть что бы сложить или умножить два числа, достаточно сложить или умножить соответствующие элементы вектора, что для микроэлектроники означает, что это можно сделать параллельно и из-за малых размерностей p₁, p₂, …, p_n сделать очень быстро.
2. Ошибка в одной позиции вектора не влияет на расчеты в других позициях вектора. В отличие от позиционной системы счисления все элементы вектора равнозначны и ошибка в одном из них ведет всего лишь к сокращению динамического диапазона. Этот факт позволяет проектировать устройства с повышенной отказоустойчивостью и коррекцией ошибок.

Читать полностью »