Описание КТО II — различия между версиями
DimaT (обсуждение | вклад) (→Китайская теорема об остатках "второй версии") |
DimaT (обсуждение | вклад) (→Китайская теорема об остатках "второй версии") |
||
| Строка 2: | Строка 2: | ||
При детальном рассмотрении, то что в [1] называется CRT II, по сути является ни чем иным, как обратным преобразователем на основе преобразования в полиадический код, в несколько видоизмененном виде. За основу взята стратегия devide and conquer (такая же стратегия используется в БПФ). | При детальном рассмотрении, то что в [1] называется CRT II, по сути является ни чем иным, как обратным преобразователем на основе преобразования в полиадический код, в несколько видоизмененном виде. За основу взята стратегия devide and conquer (такая же стратегия используется в БПФ). | ||
| − | Базисом КТО II является формула восстановления числа по двум остаткам <math>x_1, x_2</math>, по основаниям <math> | + | Базисом КТО II является формула восстановления числа по двум остаткам <math>x_1, x_2</math>, по основаниям <math>p_1, p_2</math>: |
| − | <math>X=x_1+||x_2-x_1|_{ | + | <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> | ||
Версия 12:47, 5 апреля 2013
Китайская теорема об остатках "второй версии"
При детальном рассмотрении, то что в [1] называется CRT II, по сути является ни чем иным, как обратным преобразователем на основе преобразования в полиадический код, в несколько видоизмененном виде. За основу взята стратегия devide and conquer (такая же стратегия используется в БПФ).
Базисом КТО II является формула восстановления числа по двум остаткам 
, по основаниям 
:
Как мы можем видеть, формула является переводом на базе перевода в полиадический код. Архитектура такого преобразователя можно изобразить следующим образом:
Если мы рассмотрим модулярную систему с большим числом оснований, то принцип состоит в следующем:
- Разбиваем имеющиеся вычеты по парам
- По базовой формуле для всех пар находим 
. Это будут вычеты по произведениям пар модулей
- Возвращаемся на пункт 1 с новыми вычетами и новыми модулями Невозможно разобрать выражение (неизвестная функция\cdotp): p_1\cdotp_2
[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.
