Описание КТО II — различия между версиями

Версия 07:00, 8 апреля 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} \cdot p_1$

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

Если мы рассмотрим модулярную систему с большим числом оснований, то принцип состоит в следующем:

Разбиваем имеющиеся вычеты по парам
По базовой формуле для всех пар находим $X_1, X_2, ...$ . Это будут вычеты по произведениям пар модулей
Возвращаемся на пункт 1 с новыми вычетами $X_1, X_2, ...$ и новыми модулями $P_k=p_{i} \cdot p_j$

В качестве примера рассмотрим реализацию обратного преобразователя для четырех оснований $p_1, p_2, p_3, p_4$ и четырех остатков $x_1, x_2, x_3, x_4$ :

1 этап. Находим остаток $X_1$ числа $X$ по модулю $P_1=p_1*p_2$

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

2 этап. Находим остаток $X_2$ числа $X$ по модулю $P_2=p_3*p_4$

$|X|_{p_3*p_4}=X_2=x_3+||x_4-x_3|_{p_4} \cdot |p_3^{-1}|_{p_4}|_{p_4} \cdot p_3$

3 этап. Находим $X$ по остаткам $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} \cdot P_1$

Преимущества данной структуры над обычным преобразователем через смешанную систему оснований еще требует проверки.

[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.

Описание КТО II — различия между версиями

Версия 07:00, 8 апреля 2013

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

Навигация

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

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты

Версия 07:00, 8 апреля 2013 (просмотреть исходный код) DimaT (обсуждение \| вклад) (→‎Китайская теорема об остатках "второй версии") ← Предыдущая правка		Версия 07:00, 8 апреля 2013 (просмотреть исходный код) DimaT (обсуждение \| вклад) (→‎Китайская теорема об остатках "второй версии") Следующая правка →
Строка 34:		Строка 34:

	Преимущества данной структуры над обычным преобразователем через смешанную систему оснований еще требует проверки.		Преимущества данной структуры над обычным преобразователем через смешанную систему оснований еще требует проверки.
		+
		+

	[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.		[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.