Автоматическая система контроля

Автоматизация технологических процессов

Выбор оптимальных оснований СОК

Пусть диапазон представления чисел в СОК равен P = p1 p2 . pn. Поскольку желательно, чтобы P было как можно большим, проще всего принять p1 наибольшим нечетным числом, соответствующим машинному слову, в качестве p2 принять наибольшее нечетное число < p1, взаимно простое с p1, а в качестве p3 - наибольшее нечетное число < p2, взаимно простое как с p1, так и с p2, и т.д., пока не наберется столько pj, сколько будет достаточно для образования нужного P

При работе на двоичных компьютерах иногда желательно выбирать модули pj иным образом:

pj = 2ej - 1. (1.11)

Другими словами, значение каждого модуля на единицу меньше очередной степени двойки. Такой выбор значения модуля pj зачастую упрощает выполнение основных арифметических операций, т.к. выполнять вычисления с числами, представленными по модулю 2ej - 1, несколько проще, чем с числами, представленными в обратном коде. После того, как значения модулей выбраны таким образом полезно несколько ослабить условие 0 ≤ ai < pj и потребовать только, чтобы

0 ≤ ai < 2ej, (1.12)

ai ≡ N (mod 2ej - 1), (1.13) = (а1, а2, ., аn). (1.14)

Таким образом, значение pj = 2ej - 1 принимается в качестве оптимального, поскольку это означает, что pj может быть любым ej - битовым двоичным числом

Для работы с модулями вида 2ej - 1 необходимо знать, при каких условиях число 2e - 1 является взаимно простым с числом 2f - 1. К счастью для этого существует очень простое правило

gcd(2e - 1, 2f - 1) = 2 gcd(e, f) - 1. (1.15)

Формула (2.15) утверждает в частности, что 2e - 1 и 2f - 1 взаимно просты тогда и только тогда, когда взаимно просты e и f. Формула (1.15) следует из алгоритма Евклида и тождества

(2e - 1) (mod(2f - 1)) = 2e(mod f) - 1. (1.16)

Поэтому на компьютере с длиной слова 232 можно выбрать p1 = 229 - 1, p2 = 225 - 1, p3 = 223 - 1, p4 = 219 - 1, p5 = 217 - 1, p6 = 213 - 1, p7 = 211 - 1, p8 = 27 - 1 что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до p1 p2 p3 p4 p5 p6 p7 p8 < 2144 . В данном курсовом проекте для представления 64-х битных чисел используется следующая система модулей: (13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61) - все они взаимно просты друг с другом, их произведение равно 50 774 191 064 678 342 417> 18 446 744 073 709 551 616. Каждый из модулей не превышает 6 бит, то есть операции сложения и умножения будут производиться над 6-битными числами.

Другие статьи по теме

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

Механизмы фотоаппарата В современном мире фотография является средством информирования людей о событиях в мире, средством научных исследований, видом искусства. Изобретение фотографии относится к 1839году. Че ...

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