eng
Цель этой статьи — напоминить специалистам конца 90-х о достижениях отечественной науки в области вычислительной техники в 70—80-х годах. Одно из направлений, где был достигнут значительный успех, — компьютерные арифметики. Сегодня даже школьники знают, что вычислительная техника работает в двоичной системе счисления, и мало кто задумывается над вопросом: только ли эта система пригодна для построения компьютеров. Возможно, некоторым такой вопрос покажется неактуальным. Однако автор статьи, принимавший непосредственное участие в создании самой предовой для своего времени вычислительной техники, придерживается иной точки зрения, и не без оснований...
В 70–80-е годы усилиями советских ученых С.А.Лебедева, В.М.Глушкова, М.А.Карцева, И.Я.Акушского, Д.И.Юдицкого, Г.Я. Гуськова, В.С.Семенихина, И.В. Прангишвили, Н.Я.Матюхина и многих других были созданы образцы вычислительной техники, превосходящие по своим параметрам, новизне идей и архитектуре все мировые достижения. В качестве примера назову лишь некоторые из вычислительных машин тех лет: серия ЭВМ класса БЭСМ и “Эльбрус”, ЭВМ “Стрела”, серии ЭВМ М-20, М-220, 5Э76, “Мир”, ПС и др. И лишь после того, как СССР стал воспроизводить ЭВМ класса IBM-360 (ЕС ЭВМ) и копировать, а не разрабатывать микроэлектронную элементную базу, судьба советской вычислительной техники была предрешена. Ответственность за это лежит не на ученых и разработчиках, а на руководстве страны.
В те же годы в СССР коллективы ученых исследовали и разрабатывали различные арифметики, позволявшие создавать ЭВМ с более высокой скоростью обработки данных по сравнению с широко распространенной двоичной системой счисления. Так, под руководством И.Я. Акушского и Д.И. Юдицкого была создана ЭВМ К-340 на основе системы счисления в остаточных классах, которая длительное время выпускалась нашей промышленностью и отличалась высокой производительностью и надежностью. Коллективом специалистов во главе с В.М. Глушковым были созданы и запущены в производство ЭВМ серии “Мир” с новой архитектурой и системой программирования, позволявшие производить вычисления с переменной (регулируемой) разрядностью. Тогда же под руководством И.В.Прангишвили разрабатываются и производятся ЭВМ серии ПС на основе ассоциативных процессоров с параллельной архитектурой, а под руководством М.А.Карцева – высокопроизводительные, высоконадежные вычислительные комплексы большой разрядности (до 512 двоичных разрядов) для специальных применений.
В начале 80-х годов появляются первые публикации советских ученых о Фибоначчиевой системе счисления [1] и иерархических системах счисления [2], которые позволяли создавать более высокопроизводительные и надежные вычислительные средства на основе новых элементов микроэлектроники, в том числе и многозначных. Одновременно разрабатываются и алгоритмы выполнения арифметических операций в ЭВМ, основанные на новых арифметиках.
Кратко опишем наиболее интересные системы счисления для вычислительных устройств, быстродействие и надежность которых превосходят аналоги, основанные на двоичной арифметике.
Знако-разрядная система счисления
Число в знако-разрядной системе счисления [3], как и в любой позиционной системе, можно записать в виде
...
где xi={-R, -R+1,...,-1, 0, 1,...,R}, S=2R или S=2R+1.
При таком подходе, естественно, возникает избыточность представления, которая по сравнению с двоичной может быть выражена в соответствии с методикой, изложенной в работе [3].
В таблице указана относительная избыточность (S) для некоторых значений S=2k–3 (K=4, 5, 6, 7) и S=2k (K=3, 4, 5, 6, 7). При основаниях S=2к, обеспечивающих простоту совмещения знако-разрядной системы с двоичной, избыточность максимальна и уменьшается с ростом S. Максимум избыточности представления знако-разрядной системы (100%) достигается при S=21. Однако при значениях S=2к–3 избыточность знако-разрядной системы минимальна, что и отражено в таблице.
Сложение двух чисел в знако-разрядной системе счисления выполняется в два такта. В первом такте формируются поцифровые промежуточные суммыwi и цифры поразрядных переносов ti, которые могут принимать значения –1, 0 и +1, т.е. xi+yi= =wi+tiЧS.
Во втором такте формируется окончательная сумма путем сложения цифр промежуточных разрядных сумм и соответствующих им цифр поразрядных переносов, т.е. Zi=wi+ti+1.
Умножение чисел в знако-разрядной системе счисления выполняется последовательным сложением (вычитанием) и сдвигом вправо результатов умножения множимого на S-ичные цифры множителя, начиная с младшего S-ичного разряда. Деление чисел подчиняется общим правилам деления в S-ичной системе счисления.
Основным достоинством знако-разрядной системы счисления является то, что сигнал переноса при выполнении операции сложения распространяется не далее соседнего разряда, а время выполнения операции не зависит от разрядности операндов. То есть любая операция сложения выполняется за два такта (под тактом здесь понимается время вычисления разрядной суммы. – Авт.).
Фибоначчиева система счисления
Среди позиционных весомозначных систем счисления есть системы, в которых веса разрядов выражаются не известным соотношением Di=Si, а другими, например числами ряда Фибоначчи, т.е. Di=Di-2+Di-1 . В этом случае система счисления называется Фибоначчиевой. Другой пример позиционной весомозначной системы счисления с нетрадиционным законом формирования весов разрядов – так называемая полиадическая система счисления. Веса разрядов в ней определяются выражениемDi=piЧDi-1, где pi – взаимно-простые числа.
Остановимся на Фибоначчиевой системе счисления. В работе [1] показано, что любое натуральное число N может быть представлено в двоичной р-системе счисления при pі0, весами разрядов в которой являются числа Фибоначчи. При этом после каждой единицы слева направо следует не менее p нулей. Так, например, при p=1 число 75 в двоичной 1-системе счисления можно записать как 75=1001010100=1Ч55+0Ч34+0Ч21+1Ч13+0Ч.8+1Ч5+0Ч3+1Ч2+0Ч1+0Ч1.
Одно и то же число N в p-Фибоначчиевой системе счисления может иметь несколько представлений, которые получаются друг из друга путем последовательного применения к двоичным изображениям Фибоначчиевого числа операций свертки и развертки двоичных разрядов. Свертка (нормализация) состоит в замене двух рядом стоящих единиц на одну в старшем разряде. Развертка – обратный процесс.
Отметим две особенности сложения значащих разрядов в двоичной 1-системе счисления. Во-первых, при суммировании единиц возникает перенос не одной единицы (как в классической двоичной системе счисления), а нескольких одновременно. Во-вторых, единицы можно складывать двумя способами. В первом способе при сложении i-х разрядов чисел в i-м разряде промежуточной суммы записывается 1 и возникают переносы двух единиц одновременно – в (i-1)-й и в (i-p-1)-й разряды. При втором способе сложения единиц в соответствующем (i-м) разряде промежуточной суммы записывается 0 (как и в классической двоичной арифметике) и возникает перенос p+1 единиц (одна единица – в старший (i+1)-й и р единиц – в младшие (i-p-1), (i-p-2),...,(i-2p) разряды).
Наиболее рациональный способ умножения двоичных Фибоначчиевых чисел в 1-системе счисления аналогичен умножению в классической двоичной, хотя и обладает своей спецификой [1].
Основной способ деления чисел (Z=X/Y) в Фибоначчиевой системе счисления: накапливаются кратные числам Фибоначчи значения делителя, т.е. N=YЧKj (Kj=1,2,3,5,...). Кратные делителя сравниваются с делимым, начиная с максимального кратного. В зависимости от результата сравнения формируется частное, т.е.
...
Избыточность представления чисел в Фибоначчиевой двоичной 1-системе счисления по сравнению с классической двоичной колеблется от 28% до 45%. Следовательно, данная система требует для представления чисел на 28–45% больше двоичных разрядов, чем двоичная. Кроме того, из-за межразрядных переносов и большего количества самих разрядов в представлении числа алгоритмы сложения, вычитания, умножения и деления не могут быть быстрее соответствующих алгоритмов двоичной системы. Однако достоинство Фибоначчиевой системы счисления – в том, что ее избыточность позволяет обнаруживать ошибки при выполнении арифметических преобразований данных. По утверждению автора системы [1], процент обнаруживаемых ошибок достигает 99,99%.
Несмотря на очевидную непрактичность Фибоначчиевой системы счисления для конструирования цифровых вычислительных устройств, работы создателя системы и его учеников представляют собой значительный научный результат, который показывает неисследованность разнообразия систем счисления и необходимость поиска систем с новыми качествами.
Система остаточных классов
Система остаточных классов (СОК) – это непозиционная система счисления, числа в которой представляются остатками от деления на выбранную систему оснований Р1, Р2,...,Рn и являются взаимнопростыми числами. Операции сложения, вычитания и умножения над числами в СОК производятся независимо по каждому основанию без переносов между разрядами (основаниями). Диапазон представимых чисел P=P1ЧP2Ч...ЧPn [4].
Если задан ряд положительных взаимнопростых чисел Р1, Р2,...,Рn, то целое положительное число А, представленное в виде набора наименьших положительных остатков (вычетов) от деления числа А на выбранные основания Р1, Р2,...,Рn, можно записать в виде А=(a1, a2,...,an),
...
где [ ] – целочисленное деление. Это и есть запись числа в СОК.
Если исходные числа А, В, их сумма А+В и их произведение А'В находятся в диапазоне [0,P), то результаты операций сложения А+В и умножения АВ могут быть однозначно представлены соответственно остатками gi и ri по тем же основаниям Рi, т.е.
А=(a1, a2,...,an), B=(b1, b2,...,bn)
А+В=(g1, g2,...,gn), АВ=(r1, r2,..., rn), где
...
Рассмотрим примеры выполнения операций сложения и умножения чисел в СОК. Пусть основаниями системы являются Р1=2, Р2=3, Р3=5, Р4=7. Диапазон представимых чисел в данной системе Р=2Ч3Ч5Ч7=210. Требуется сложить числа А=34 и В=87. По выбранным основаниям числа А и В в СОК будут иметь вид А=(0, 1, 4, 6), В=(1, 0, 2, 3).
Сложим числа А и В
...
Легко проверить, что число А+В, представленное по выбранным основаниям как (1, 1, 1, 2), равно 121.
Пусть требуется умножить числа А=17 и В=8. А=(1, 2, 2, 3), В=(0, 2, 3, 1).
...
В самом деле, число АхВ, представленное по выбранным основаниям как (0, 1, 1, 3), равно 136.
Такие операции, как деление, сравнение и др., требующие информации о величине всего числа, в СОК выполняются по более сложным алгоритмам. И в этом заключается существенный недостаток данной системы счисления, сдерживающий ее широкое применение в качестве компьютерной арифметики. Однако сегодня даже в самых современных компьютерах при работе с большими и супербольшими числами используют СОК, ибо только эта арифметика позволяет получать результаты вычислений в реальном времени. В таких случаях в качестве оснований СОК применяют величины, близкие к 2m (m – двоичная разрядность компьютера), например 2m-1-1, 2m-1, 2m-1+1 и т.д. Компьютер вычисляет результат по одному из модулей за один проход. Другие области применения СОК – помехоустойчивое кодирование, криптография и т.п.
Начиная с 1952 года специалисты многих стран мира, включая и СССР, занимались проблемой повышения скорости выполнения “неудобных” операций в СОК. Особую роль в решении данной проблемы сыграл Израиль Яковлевич Акушский. Немалый вклад в эту область науки внесли также Д.И.Юдицкий, В.М.Амербаев, А.А.Коляда.
Иерархические системы счисления
В конце 80-х – начале 90-х годов родилась идея соединения позиционных и непозиционных систем счисления, т.е. конструирования иерархических систем, которые должны сочетать в себе положительные стороны включенных в них систем счисления и быть свободными от их недостатков [5, 6]. Принцип построения иерархическиx систем в целом прост. Выбирается некоторая внешняя система счисления A=, где a – алфавит системы, а W=W0, Wr – ее сигнатура. Сигнатура состоит из двух частей: операционной (W0), содержащей символы операций системы, и реляционной (Wr), содержащей символы отношений. Цифры, т.е. элементы алфавита А этой системы, записываются в виде слов (кодов) другой (внутренней) системы счисления B=. Такую систему обозначают А[B].
Рассмотрим пример. Пусть A – десятичная позиционная система, а B – двоичная система.Тогда a={0,1,2,...,9}, b={0,1}. Двоичное кодирование цифр системы A (десятичной) производится, например, тетрадами: 0® 0000, 1® 0001,... , 9® 1001. Тогда число 23 (десятичное) запишется в иерархической системе счисления в виде двух тетрад (0010, 0011). Система A[B] в нашем примере – хорошо известная двоично-кодированная десятичная система, применяемая для представления десятичных чисел в современных ЭВМ.
Очевидно, что степень вложенности иерархической системы может быть и более двух. Иначе говоря, существуют иерархические системы счисления A0[A1[A2...[An]...] с основаниями S0, S1,...,Sn, причем S0>S1>...>Sn. Система счисления (двоичная, восьмеричная, шестнадцатеричная), для которых
S0=S1Ч2m1, S1=S2Ч2m2 ,..., Sn=Sn-1Ч2mn на уровне представления являются безызбыточными. Если данное условие не выполняется, система избыточна (например, двоично-кодированная десятичная).
Позиционно-остаточная система счисления
При конструировании иерархических систем счисления большой интерес представляет сочетание систем различных типов. Рассмотрим систему вида A[B], для которой A – позиционная система счисления с основанием S, а B – система счисления в остаточных классах с базовыми модулями P1, P2,..., Pr, такими, что PіS, P=P1ЧP2Ч...ЧPr. Такую систему называют позиционно-остаточной системой счисления.
Неравенство PіS – необходимое и достаточное условие однозначного представления цифр 0,1,...,S-1 позиционной системы наборами вычетов по модулямP1, P2,..., Pr. Однако учитывая необходимость корректной реализации арифметических операций в системе A[B] (например, формирование переноса и т.п.), можно поставить более жесткое условие P=P1ЧP2Ч...ЧPrі2S.
Весьма важен выбор величины основания S позиционной системы счисления и модулей системы счисления в остаточных классах. Отдавая дань двоичной системе счисления, можно выбирать Sі2m. В этом случае модули СОК и их произведение должны удовлетворять условию Pі2m+1. Для человека же наиболее удобны основания, кратные 10 (100, 1000 и т.д.).
Двоично-кодированная десятичная система – в известной мере компромисс между человеком и компьютером. Но ее относительная избыточность – 26,5%. Чтобы преодолеть данный недостаток, ряд исследователей предлагают для арифметики с плавающей запятой вместо основания 10 использовать 100 [7]. Тогда для хранения двух десятичных цифр достаточно иметь семь двоичных разрядов вместо восьми (избыточность представления – 22,7%). Переход к основанию 1000 позволяет размещать три десятичные цифры в 10 двоичных разрядах вместо 12 (избыточность представления – 2,35%). Расплата за экономичное представление чисел при переходе к основаниям вида 10n – более сложные алгоритмы кодирования и декодирования таких чисел. Однако на уровне машинного представления арифметика все равно остается двоичной.
Арифметические операции в позиционно-остаточной системе счисления выполняются отдельно над цифрами внешней и внутренней системы. Такая ступенчатая реализация операций позволяет практически без изменений переносить алгоритмы внешней системы счисления на операции в системе A[B]. При этом “цифровые” операции системы счисления А заменяются процедурами системы счисления B.
Знако-разрядная позиционно-остаточная система счисления
Еще один пример иерархической системы счисления – знако-разрядная система с основанием S, цифры которой представляются в системе остаточных классов с базовыми модулями P=P1, P2,...,Pr [8]. Достоинство данной системы счисления – высокая скорость выполнения арифметических операций над разрядными цифрами и минимальная длина пути распространения переноса между S-ичными разрядами (не далее соседнего разряда). Высокое быстродействие достигается за счет того, что при суммировании в каждом S-ичном разряде (S>2) одновременно формируются три величины: xi+yi, xi+yi-1, xi+yi+1. Затем одна из них выбирается в качестве результата в зависимости от значения сигнала переноса ti, принимающего значения –1, 0, +1.
Таким образом, появляется возможность параллельной обработки на нескольких компьютерах больших чисел с основаниями S=2m. Обрабатывать большие числа в “реальном времени” способны даже двоичные персональные компьютеры, работающие по алгоритмам знако-разрядной позиционно-остаточной системы счисления.
Новейшие западные технологии, появляющиеся на российском рынке, в совокупности с отечественными разработками в области недвоичных компьютерных арифметик и синтеза новых способов и алгоритмов ускорения вычислений открывают перед разработчиками вычислительных систем новые возможности. Автор будет рад любым контактам со специалистами, заинтересовавшимися изложенными в статье идеями.
Литература
1. Стахов А.П. Введение в алгоритмическую теорию измерений. – М.: Сов.радио, 1997.
2. Евстигнеев В.Г. Недвоичная машинная арифметика и специализированные процессоры. – М.: МИФИ СЕРВИС и АО “ИНСОФТ”, 1992.
3. Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия. – М.: Высшая школа, 1970.
4. Акушский И.Д., Юдицкий Д.И. Машинная арифметика в остаточных классах. – М.: Сов. радио, 1968.
5. Евстигнев В.Г. S-ичный сумматор. – Электронная техника. Сер. 10, 1986, вып. 5(59), с.17–19.
6. Евстигнеев В.Г. S-ичный сумматор. Авт. свид. №1273925.
7. Schoichet S.R. The LISP Machine. Mini-Micro System, 1978, №11(5), р. 68–74.
8. Евстигнеев В.Г., Евстигнеева О.В. Устройство для сложения n-разрядных чисел в избыточной системе счисления. Авт. свид №. 1188731.
В те же годы в СССР коллективы ученых исследовали и разрабатывали различные арифметики, позволявшие создавать ЭВМ с более высокой скоростью обработки данных по сравнению с широко распространенной двоичной системой счисления. Так, под руководством И.Я. Акушского и Д.И. Юдицкого была создана ЭВМ К-340 на основе системы счисления в остаточных классах, которая длительное время выпускалась нашей промышленностью и отличалась высокой производительностью и надежностью. Коллективом специалистов во главе с В.М. Глушковым были созданы и запущены в производство ЭВМ серии “Мир” с новой архитектурой и системой программирования, позволявшие производить вычисления с переменной (регулируемой) разрядностью. Тогда же под руководством И.В.Прангишвили разрабатываются и производятся ЭВМ серии ПС на основе ассоциативных процессоров с параллельной архитектурой, а под руководством М.А.Карцева – высокопроизводительные, высоконадежные вычислительные комплексы большой разрядности (до 512 двоичных разрядов) для специальных применений.
В начале 80-х годов появляются первые публикации советских ученых о Фибоначчиевой системе счисления [1] и иерархических системах счисления [2], которые позволяли создавать более высокопроизводительные и надежные вычислительные средства на основе новых элементов микроэлектроники, в том числе и многозначных. Одновременно разрабатываются и алгоритмы выполнения арифметических операций в ЭВМ, основанные на новых арифметиках.
Кратко опишем наиболее интересные системы счисления для вычислительных устройств, быстродействие и надежность которых превосходят аналоги, основанные на двоичной арифметике.
Знако-разрядная система счисления
Число в знако-разрядной системе счисления [3], как и в любой позиционной системе, можно записать в виде
...
где xi={-R, -R+1,...,-1, 0, 1,...,R}, S=2R или S=2R+1.
При таком подходе, естественно, возникает избыточность представления, которая по сравнению с двоичной может быть выражена в соответствии с методикой, изложенной в работе [3].
В таблице указана относительная избыточность (S) для некоторых значений S=2k–3 (K=4, 5, 6, 7) и S=2k (K=3, 4, 5, 6, 7). При основаниях S=2к, обеспечивающих простоту совмещения знако-разрядной системы с двоичной, избыточность максимальна и уменьшается с ростом S. Максимум избыточности представления знако-разрядной системы (100%) достигается при S=21. Однако при значениях S=2к–3 избыточность знако-разрядной системы минимальна, что и отражено в таблице.
Сложение двух чисел в знако-разрядной системе счисления выполняется в два такта. В первом такте формируются поцифровые промежуточные суммыwi и цифры поразрядных переносов ti, которые могут принимать значения –1, 0 и +1, т.е. xi+yi= =wi+tiЧS.
Во втором такте формируется окончательная сумма путем сложения цифр промежуточных разрядных сумм и соответствующих им цифр поразрядных переносов, т.е. Zi=wi+ti+1.
Умножение чисел в знако-разрядной системе счисления выполняется последовательным сложением (вычитанием) и сдвигом вправо результатов умножения множимого на S-ичные цифры множителя, начиная с младшего S-ичного разряда. Деление чисел подчиняется общим правилам деления в S-ичной системе счисления.
Основным достоинством знако-разрядной системы счисления является то, что сигнал переноса при выполнении операции сложения распространяется не далее соседнего разряда, а время выполнения операции не зависит от разрядности операндов. То есть любая операция сложения выполняется за два такта (под тактом здесь понимается время вычисления разрядной суммы. – Авт.).
Фибоначчиева система счисления
Среди позиционных весомозначных систем счисления есть системы, в которых веса разрядов выражаются не известным соотношением Di=Si, а другими, например числами ряда Фибоначчи, т.е. Di=Di-2+Di-1 . В этом случае система счисления называется Фибоначчиевой. Другой пример позиционной весомозначной системы счисления с нетрадиционным законом формирования весов разрядов – так называемая полиадическая система счисления. Веса разрядов в ней определяются выражениемDi=piЧDi-1, где pi – взаимно-простые числа.
Остановимся на Фибоначчиевой системе счисления. В работе [1] показано, что любое натуральное число N может быть представлено в двоичной р-системе счисления при pі0, весами разрядов в которой являются числа Фибоначчи. При этом после каждой единицы слева направо следует не менее p нулей. Так, например, при p=1 число 75 в двоичной 1-системе счисления можно записать как 75=1001010100=1Ч55+0Ч34+0Ч21+1Ч13+0Ч.8+1Ч5+0Ч3+1Ч2+0Ч1+0Ч1.
Одно и то же число N в p-Фибоначчиевой системе счисления может иметь несколько представлений, которые получаются друг из друга путем последовательного применения к двоичным изображениям Фибоначчиевого числа операций свертки и развертки двоичных разрядов. Свертка (нормализация) состоит в замене двух рядом стоящих единиц на одну в старшем разряде. Развертка – обратный процесс.
Отметим две особенности сложения значащих разрядов в двоичной 1-системе счисления. Во-первых, при суммировании единиц возникает перенос не одной единицы (как в классической двоичной системе счисления), а нескольких одновременно. Во-вторых, единицы можно складывать двумя способами. В первом способе при сложении i-х разрядов чисел в i-м разряде промежуточной суммы записывается 1 и возникают переносы двух единиц одновременно – в (i-1)-й и в (i-p-1)-й разряды. При втором способе сложения единиц в соответствующем (i-м) разряде промежуточной суммы записывается 0 (как и в классической двоичной арифметике) и возникает перенос p+1 единиц (одна единица – в старший (i+1)-й и р единиц – в младшие (i-p-1), (i-p-2),...,(i-2p) разряды).
Наиболее рациональный способ умножения двоичных Фибоначчиевых чисел в 1-системе счисления аналогичен умножению в классической двоичной, хотя и обладает своей спецификой [1].
Основной способ деления чисел (Z=X/Y) в Фибоначчиевой системе счисления: накапливаются кратные числам Фибоначчи значения делителя, т.е. N=YЧKj (Kj=1,2,3,5,...). Кратные делителя сравниваются с делимым, начиная с максимального кратного. В зависимости от результата сравнения формируется частное, т.е.
...
Избыточность представления чисел в Фибоначчиевой двоичной 1-системе счисления по сравнению с классической двоичной колеблется от 28% до 45%. Следовательно, данная система требует для представления чисел на 28–45% больше двоичных разрядов, чем двоичная. Кроме того, из-за межразрядных переносов и большего количества самих разрядов в представлении числа алгоритмы сложения, вычитания, умножения и деления не могут быть быстрее соответствующих алгоритмов двоичной системы. Однако достоинство Фибоначчиевой системы счисления – в том, что ее избыточность позволяет обнаруживать ошибки при выполнении арифметических преобразований данных. По утверждению автора системы [1], процент обнаруживаемых ошибок достигает 99,99%.
Несмотря на очевидную непрактичность Фибоначчиевой системы счисления для конструирования цифровых вычислительных устройств, работы создателя системы и его учеников представляют собой значительный научный результат, который показывает неисследованность разнообразия систем счисления и необходимость поиска систем с новыми качествами.
Система остаточных классов
Система остаточных классов (СОК) – это непозиционная система счисления, числа в которой представляются остатками от деления на выбранную систему оснований Р1, Р2,...,Рn и являются взаимнопростыми числами. Операции сложения, вычитания и умножения над числами в СОК производятся независимо по каждому основанию без переносов между разрядами (основаниями). Диапазон представимых чисел P=P1ЧP2Ч...ЧPn [4].
Если задан ряд положительных взаимнопростых чисел Р1, Р2,...,Рn, то целое положительное число А, представленное в виде набора наименьших положительных остатков (вычетов) от деления числа А на выбранные основания Р1, Р2,...,Рn, можно записать в виде А=(a1, a2,...,an),
...
где [ ] – целочисленное деление. Это и есть запись числа в СОК.
Если исходные числа А, В, их сумма А+В и их произведение А'В находятся в диапазоне [0,P), то результаты операций сложения А+В и умножения АВ могут быть однозначно представлены соответственно остатками gi и ri по тем же основаниям Рi, т.е.
А=(a1, a2,...,an), B=(b1, b2,...,bn)
А+В=(g1, g2,...,gn), АВ=(r1, r2,..., rn), где
...
Рассмотрим примеры выполнения операций сложения и умножения чисел в СОК. Пусть основаниями системы являются Р1=2, Р2=3, Р3=5, Р4=7. Диапазон представимых чисел в данной системе Р=2Ч3Ч5Ч7=210. Требуется сложить числа А=34 и В=87. По выбранным основаниям числа А и В в СОК будут иметь вид А=(0, 1, 4, 6), В=(1, 0, 2, 3).
Сложим числа А и В
...
Легко проверить, что число А+В, представленное по выбранным основаниям как (1, 1, 1, 2), равно 121.
Пусть требуется умножить числа А=17 и В=8. А=(1, 2, 2, 3), В=(0, 2, 3, 1).
...
В самом деле, число АхВ, представленное по выбранным основаниям как (0, 1, 1, 3), равно 136.
Такие операции, как деление, сравнение и др., требующие информации о величине всего числа, в СОК выполняются по более сложным алгоритмам. И в этом заключается существенный недостаток данной системы счисления, сдерживающий ее широкое применение в качестве компьютерной арифметики. Однако сегодня даже в самых современных компьютерах при работе с большими и супербольшими числами используют СОК, ибо только эта арифметика позволяет получать результаты вычислений в реальном времени. В таких случаях в качестве оснований СОК применяют величины, близкие к 2m (m – двоичная разрядность компьютера), например 2m-1-1, 2m-1, 2m-1+1 и т.д. Компьютер вычисляет результат по одному из модулей за один проход. Другие области применения СОК – помехоустойчивое кодирование, криптография и т.п.
Начиная с 1952 года специалисты многих стран мира, включая и СССР, занимались проблемой повышения скорости выполнения “неудобных” операций в СОК. Особую роль в решении данной проблемы сыграл Израиль Яковлевич Акушский. Немалый вклад в эту область науки внесли также Д.И.Юдицкий, В.М.Амербаев, А.А.Коляда.
Иерархические системы счисления
В конце 80-х – начале 90-х годов родилась идея соединения позиционных и непозиционных систем счисления, т.е. конструирования иерархических систем, которые должны сочетать в себе положительные стороны включенных в них систем счисления и быть свободными от их недостатков [5, 6]. Принцип построения иерархическиx систем в целом прост. Выбирается некоторая внешняя система счисления A=, где a – алфавит системы, а W=W0, Wr – ее сигнатура. Сигнатура состоит из двух частей: операционной (W0), содержащей символы операций системы, и реляционной (Wr), содержащей символы отношений. Цифры, т.е. элементы алфавита А этой системы, записываются в виде слов (кодов) другой (внутренней) системы счисления B=. Такую систему обозначают А[B].
Рассмотрим пример. Пусть A – десятичная позиционная система, а B – двоичная система.Тогда a={0,1,2,...,9}, b={0,1}. Двоичное кодирование цифр системы A (десятичной) производится, например, тетрадами: 0® 0000, 1® 0001,... , 9® 1001. Тогда число 23 (десятичное) запишется в иерархической системе счисления в виде двух тетрад (0010, 0011). Система A[B] в нашем примере – хорошо известная двоично-кодированная десятичная система, применяемая для представления десятичных чисел в современных ЭВМ.
Очевидно, что степень вложенности иерархической системы может быть и более двух. Иначе говоря, существуют иерархические системы счисления A0[A1[A2...[An]...] с основаниями S0, S1,...,Sn, причем S0>S1>...>Sn. Система счисления (двоичная, восьмеричная, шестнадцатеричная), для которых
S0=S1Ч2m1, S1=S2Ч2m2 ,..., Sn=Sn-1Ч2mn на уровне представления являются безызбыточными. Если данное условие не выполняется, система избыточна (например, двоично-кодированная десятичная).
Позиционно-остаточная система счисления
При конструировании иерархических систем счисления большой интерес представляет сочетание систем различных типов. Рассмотрим систему вида A[B], для которой A – позиционная система счисления с основанием S, а B – система счисления в остаточных классах с базовыми модулями P1, P2,..., Pr, такими, что PіS, P=P1ЧP2Ч...ЧPr. Такую систему называют позиционно-остаточной системой счисления.
Неравенство PіS – необходимое и достаточное условие однозначного представления цифр 0,1,...,S-1 позиционной системы наборами вычетов по модулямP1, P2,..., Pr. Однако учитывая необходимость корректной реализации арифметических операций в системе A[B] (например, формирование переноса и т.п.), можно поставить более жесткое условие P=P1ЧP2Ч...ЧPrі2S.
Весьма важен выбор величины основания S позиционной системы счисления и модулей системы счисления в остаточных классах. Отдавая дань двоичной системе счисления, можно выбирать Sі2m. В этом случае модули СОК и их произведение должны удовлетворять условию Pі2m+1. Для человека же наиболее удобны основания, кратные 10 (100, 1000 и т.д.).
Двоично-кодированная десятичная система – в известной мере компромисс между человеком и компьютером. Но ее относительная избыточность – 26,5%. Чтобы преодолеть данный недостаток, ряд исследователей предлагают для арифметики с плавающей запятой вместо основания 10 использовать 100 [7]. Тогда для хранения двух десятичных цифр достаточно иметь семь двоичных разрядов вместо восьми (избыточность представления – 22,7%). Переход к основанию 1000 позволяет размещать три десятичные цифры в 10 двоичных разрядах вместо 12 (избыточность представления – 2,35%). Расплата за экономичное представление чисел при переходе к основаниям вида 10n – более сложные алгоритмы кодирования и декодирования таких чисел. Однако на уровне машинного представления арифметика все равно остается двоичной.
Арифметические операции в позиционно-остаточной системе счисления выполняются отдельно над цифрами внешней и внутренней системы. Такая ступенчатая реализация операций позволяет практически без изменений переносить алгоритмы внешней системы счисления на операции в системе A[B]. При этом “цифровые” операции системы счисления А заменяются процедурами системы счисления B.
Знако-разрядная позиционно-остаточная система счисления
Еще один пример иерархической системы счисления – знако-разрядная система с основанием S, цифры которой представляются в системе остаточных классов с базовыми модулями P=P1, P2,...,Pr [8]. Достоинство данной системы счисления – высокая скорость выполнения арифметических операций над разрядными цифрами и минимальная длина пути распространения переноса между S-ичными разрядами (не далее соседнего разряда). Высокое быстродействие достигается за счет того, что при суммировании в каждом S-ичном разряде (S>2) одновременно формируются три величины: xi+yi, xi+yi-1, xi+yi+1. Затем одна из них выбирается в качестве результата в зависимости от значения сигнала переноса ti, принимающего значения –1, 0, +1.
Таким образом, появляется возможность параллельной обработки на нескольких компьютерах больших чисел с основаниями S=2m. Обрабатывать большие числа в “реальном времени” способны даже двоичные персональные компьютеры, работающие по алгоритмам знако-разрядной позиционно-остаточной системы счисления.
Новейшие западные технологии, появляющиеся на российском рынке, в совокупности с отечественными разработками в области недвоичных компьютерных арифметик и синтеза новых способов и алгоритмов ускорения вычислений открывают перед разработчиками вычислительных систем новые возможности. Автор будет рад любым контактам со специалистами, заинтересовавшимися изложенными в статье идеями.
Литература
1. Стахов А.П. Введение в алгоритмическую теорию измерений. – М.: Сов.радио, 1997.
2. Евстигнеев В.Г. Недвоичная машинная арифметика и специализированные процессоры. – М.: МИФИ СЕРВИС и АО “ИНСОФТ”, 1992.
3. Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия. – М.: Высшая школа, 1970.
4. Акушский И.Д., Юдицкий Д.И. Машинная арифметика в остаточных классах. – М.: Сов. радио, 1968.
5. Евстигнев В.Г. S-ичный сумматор. – Электронная техника. Сер. 10, 1986, вып. 5(59), с.17–19.
6. Евстигнеев В.Г. S-ичный сумматор. Авт. свид. №1273925.
7. Schoichet S.R. The LISP Machine. Mini-Micro System, 1978, №11(5), р. 68–74.
8. Евстигнеев В.Г., Евстигнеева О.В. Устройство для сложения n-разрядных чисел в избыточной системе счисления. Авт. свид №. 1188731.
Отзывы читателей
