Описание КТО II

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
(Китайская теорема об остатках "второй версии")
(Китайская теорема об остатках "второй версии")
Строка 2: Строка 2:
  
 
При детальном рассмотрении, то что в [1] называется CRT II, по сути является ни чем иным, как обратным преобразователем на основе преобразования в полиадический код, в несколько видоизмененном виде. За основу взята стратегия devide and conquer (такая же стратегия используется в БПФ).
 
При детальном рассмотрении, то что в [1] называется CRT II, по сути является ни чем иным, как обратным преобразователем на основе преобразования в полиадический код, в несколько видоизмененном виде. За основу взята стратегия devide and conquer (такая же стратегия используется в БПФ).
Базисом КТО II является формула восстановления числа по двум остаткам <math>x_1, x_2</math>, по основаниям <math>m_1, m_2</math>:
+
Базисом КТО II является формула восстановления числа по двум остаткам <math>x_1, x_2</math>, по основаниям <math>p_1, p_2</math>:
  
<math>X=x_1+||x_2-x_1|_{m_2}\cdot|m_1^{-1}|_{m_2}|_{m_2}</math>
+
<math>X=x_1+||x_2-x_1|_{p_2}\cdot|p_1^{-1}|_{p_2}|_{p_2}</math>
  
 
Как мы можем видеть, формула  является переводом на базе перевода в полиадический код. Архитектура такого преобразователя можно изобразить следующим образом:
 
Как мы можем видеть, формула  является переводом на базе перевода в полиадический код. Архитектура такого преобразователя можно изобразить следующим образом:
Строка 10: Строка 10:
 
[[Файл:Crt2 1.JPG]]
 
[[Файл:Crt2 1.JPG]]
  
 
+
Если мы рассмотрим модулярную систему с большим числом оснований, то принцип состоит в следующем:
 
+
- Разбиваем имеющиеся вычеты по парам
 +
- По базовой формуле для всех пар находим <math>X_1, X_2, ...</math>. Это будут вычеты по произведениям пар модулей
 +
- Возвращаемся на пункт 1 с новыми вычетами <math>X_1, X_2, ...</math> и новыми модулями <math>p_1\cdotp_2</math>
  
  

Версия 15:47, 5 апреля 2013

Китайская теорема об остатках "второй версии"

При детальном рассмотрении, то что в [1] называется CRT II, по сути является ни чем иным, как обратным преобразователем на основе преобразования в полиадический код, в несколько видоизмененном виде. За основу взята стратегия devide and conquer (такая же стратегия используется в БПФ). Базисом КТО II является формула восстановления числа по двум остаткам x_1, x_2, по основаниям p_1, p_2:

X=x_1+||x_2-x_1|_{p_2}\cdot|p_1^{-1}|_{p_2}|_{p_2}

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

Crt2 1.JPG

Если мы рассмотрим модулярную систему с большим числом оснований, то принцип состоит в следующем: - Разбиваем имеющиеся вычеты по парам - По базовой формуле для всех пар находим X_1, X_2, .... Это будут вычеты по произведениям пар модулей - Возвращаемся на пункт 1 с новыми вычетами X_1, X_2, ... и новыми модулями Невозможно разобрать выражение (неизвестная функция\cdotp): p_1\cdotp_2


Crt2 2.JPG


[1]Yuke Wang, “Residue-to-Binary Converters Based On New Chinese Remainder Theorems,” IEEE Transactions on Circuits and Systems – II: Analog and Digital Signal Processing, vol. 47, No. 3, pp.197–205, March 2000.


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация