В обычной жизни мы обычно пользуемся позиционной системой счисления. В позиционной системе счисления значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда) [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 свойства, которые позволяют эффективно использовать модулярную арифметику в некоторых областях микроэлектроники:
- Отсутствие переноса разрядов в сложении и умножении. Пусть нам дано два числа X1 и X2, представленные в виде системы остатков (x11, x12, …, x1n) и (x21, x22, …, x2n) по системе взаимнопростых чисел (p1, p2, …, pn). В этом случае:
X3 = X1 + X2 = ((x11+x21)%p1, (x12+x22)%p2, …, (x1n+x2n)%pn)
X4 = X1 * X2 = ((x11*x21)%p1, (x12*x22)%p2, …, (x1n*x2n)%pn)
То есть что бы сложить или умножить два числа, достаточно сложить или умножить соответствующие элементы вектора, что для микроэлектроники означает, что это можно сделать параллельно и из-за малых размерностей p1, p2, …, pn сделать очень быстро.
- Ошибка в одной позиции вектора не влияет на расчеты в других позициях вектора. В отличие от позиционной системы счисления все элементы вектора равнозначны и ошибка в одном из них ведет всего лишь к сокращению динамического диапазона. Этот факт позволяет проектировать устройства с повышенной отказоустойчивостью и коррекцией ошибок.
Читать полностью »
На форуме Dangerous Prototypes я однажды принял участие в одном обсуждении, посвященном проблемам с шиной SPI, кторая переставала нормально работать, начиная с некоторой длины. Мой опыт подсказывал мне две вещи: 1) проверить источник питания, 2) проверить линию на наличие отражений. Тогда я понял, что это должно быть общей проблемой для всех радиолюбителей. Линии передачи данных — сложная тема, и настало время снять покров таинственности с этой электронной магии.
