Специальные системы модулей — различия между версиями

Версия 13:48, 1 апреля 2013

3-элементные системы

{2ⁿ-1, 2ⁿ, 2ⁿ+1}

{2ⁿ-1, 2ⁿ, 2ⁿ+1} - наиболее часто встречающийся набор специальных модулей. Преимущества: легкость реализаций сумматоров, умножителей и немодульных операций. Система отлично изучена и часто используется.

{2n-1, 2n, 2n+1}

Общий случай предыдущей системы. Оличается легкостью создания обратных преобразователей.

{2ⁿ-1, 2ⁿ, 2^n-1-1}

Система позволяет избежать сложных операций по модулю вида 2ⁿ+1, но сокращает динамический диапазон.

• Residue-to-binary arithmetic converter for the moduli set (2< sup> k</sup>, 2< sup> k</sup>-1, 2< sup> k-1</sup>-1)

4-элементные системы

{2ⁿ-1, 2ⁿ, 2ⁿ+1, 2ⁿ⁺¹-1}

• Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

{2ⁿ-1, 2ⁿ, 2ⁿ+1, 2^n-1-1}

• Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

{2ⁿ-1, 2ⁿ, 2ⁿ+1, 2²ⁿ+1}

• An efficient reverse converter for the 4-moduli set $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{2n} + 1\}$ based on the new chinese remainder theorem

{2ⁿ-1, 2ⁿ, 2ⁿ+1, 2^n-1+1}

Модули взаимнопросты для n = 2k + 1, k = 1, 2, 3...

{2ⁿ⁺²+3, 2ⁿ⁺¹+1, 2ⁿ+1, 2}

Модули взаимнопросты для всех n

5-элементные системы

{2ⁿ-1, 2ⁿ, 2ⁿ+1, 2ⁿ⁺¹-1, 2^n-1-1}

Работает для четных n. Динамический диапазон 5n-1 бит.

• A Residue-to-Binary Converter for a New Five-Moduli Set

Удобные простые числа

Близкие к степени 2

2ⁿ-1: 3 (2²-1) 7 (2³-1) 31 (2⁵-1) 127 (2⁷-1) 8191 (2¹³-1) 131071 (2¹⁷-1)

2ⁿ+1: 5 (2²+1) 17 (2⁴+1) 257 (2⁸+1) 65537 (2¹⁶+1)

2ⁿ-3: 13 (2⁴-3) 29 (2⁵-3) 61 (2⁶-3) 509 (2⁹-3) 1021 (2¹⁰-3) 4093 (2¹²-3) 16381 (2¹⁴-3)

2ⁿ+3: 11 (2³+3) 19 (2⁴+3) 67 (2⁶+3) 131 (2⁷+3) 4099 (2¹²+3) 32771 (2¹⁵+3) 65539 (2¹⁶+3) 262147 (2¹⁸+3)