Полиадический код - История изменений

Isaeva в 09:24, 12 февраля 2015

2015-02-12T09:24:01Z

Isaeva в 09:13, 12 февраля 2015

2015-02-12T09:13:14Z

Isaeva в 13:09, 18 ноября 2013

2013-11-18T13:09:02Z

Isaeva в 14:31, 6 ноября 2013

2013-11-06T14:31:57Z

Isaeva в 14:15, 6 ноября 2013

2013-11-06T14:15:55Z

Isaeva в 21:46, 5 ноября 2013

2013-11-05T21:46:38Z

Isaeva в 19:28, 5 ноября 2013

2013-11-05T19:28:40Z

Isaeva в 19:12, 2 ноября 2013

2013-11-02T19:12:16Z

Isaeva в 18:49, 2 ноября 2013

2013-11-02T18:49:41Z

Isaeva в 14:55, 30 октября 2013

2013-10-30T14:55:30Z

@@ Строка 9: / Строка 9: @@
-Любое число <math>\{y_1,y_2,y_3,\ldots,y_n\}</math> в системе остаточных классов может быть представленно в виде полиадического кода
+Любое число <math>\{x_1,x_2,x_3,\ldots,x_n\}</math> в системе остаточных классов может быть представлено в виде полиадического кода
 :<math>X=\sum_{i=1}^Nx_iM_{i-1}=x_1+m_1(x_2+m_2(\cdots+m_{N-1}x_{N})\cdots),</math>
-где <math>x_k</math> - цифры полиадического кода, числа <math>M_k</math> - основание смешанной системы счисления:
+где <math>x_k</math> - цифры кода, числа <math>M_k</math> - основание смешанной системы счисления:
 :<math>M_0=1,M_i=\prod_{j=1}^i m_j</math> для <math>i>0</math> и <math>0\leq x_i<m_i.</math>

@@ Строка 2: / Строка 2: @@
 '''Полиадический код''' (или система счисления со смешанным основанием от англ. [http://en.wikipedia.org/wiki/Residue_number_system#Associated_mixed_radix_system associated mixed radix system (AMRS)])
 Любое число <math>\{y_1,y_2,y_3,\ldots,y_n\}</math> в системе остаточных классов может быть представленно в виде полиадического кода
 :<math>X=\sum_{i=1}^Nx_iM_{i-1}=x_1+m_1(x_2+m_2(\cdots+m_{N-1}x_{N})\cdots),</math>
-где
+где <math>x_k</math> - цифры полиадического кода, числа <math>M_k</math> - основание смешанной системы счисления:
 :<math>M_0=1,M_i=\prod_{j=1}^i m_j</math> для <math>i>0</math> и <math>0\leq x_i<m_i.</math>

@@ Строка 58: / Строка 58: @@
 Динамический диапазон каждой из троек превышает заданный (можно убедиться для каждой тройки: <math>p_1 \cdot p_2 \cdot p_3 > p_1 \cdot p_2</math>). В случае если ошибок не было, то при обратном преобразовании в позиционное представление значения всех троек должны лежать в диапазоне: <math>[0 <= X < p_1 \cdot p_2]</math> и быть равными. В случае, если в одном из каналов произошла ошибка, то правильное значение даст только одна тройка, в которой исключено неверное значение, все остальные тройки будут лежать вне динамического диапазона ('''здесь нужна ссылка на пруФФФФФ или сам пруф''').
-В этом случае для восстановления числа требуется сделать 4 обратных преобразователя для каждой из троек. Сравнить полученные значения с <math>p_1 \cdot p_2</math> и на основании сравнения выдать на выход правильное значение. Однако как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением.
+В этом случае для восстановления числа требуется сделать 4 обратных преобразователя для каждой из троек. Сравнить полученные значения с <math>p_1 \cdot p_2</math> и на основании сравнения выдать на выход правильное значение. Однако, как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением.
 Запишем, полиадическую формулу для каждой из троек:
@@ Строка 66: / Строка 66: @@
 * <math>X_{P_4} = {a_1}_{P_4} + {a_2}_{P_4}\cdot p_1 + {a_3}_{P_4}\cdot p_1\cdot p_2</math>
-Если посмотреть на самую правое слагаемое каждого из выражений можно заметить, что если любой из коэффициентов <math>{a_3}_{P_1}, {a_3}_{P_2}, {a_3}_{P_3}, {a_3}_{P_4}</math> отличается от нуля, то всё выражение получается больше, чем <math>p_1 \cdot p_2</math>. Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки не восстанавливая значение целиком ('''нужен пруф'''). Тем самым можно сократить площадь преобразователя.
+Если посмотреть на самую правое слагаемое каждого из выражений, можно заметить, что если любой из коэффициентов <math>{a_3}_{P_1}, {a_3}_{P_2}, {a_3}_{P_3}, {a_3}_{P_4}</math> отличается от нуля, то всё выражение получается больше, чем <math>p_1 \cdot p_2</math>. Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки, не восстанавливая значение целиком ('''нужен пруф'''). Тем самым можно сократить площадь преобразователя.
 == Схема сокращенного преобразователя в полиадический код для коррекции одиночной ошибки ==
-Использовать несколько параллельных преобразователей оказывается неэффективным. Как показано в [2] для этой цели можно использовать сокращенную форму (см. рисунок ниже).
+Использовать несколько параллельных преобразователей оказывается неэффективным. Как показано в [2], для этой цели можно использовать сокращенную форму (см. рисунок ниже).
 [[Изображение:Конвейерный преобразователь в полиадический код с коррекцией ошибок.png]]
@@ Строка 79: / Строка 79: @@
 * <math>A_{P_4} = \{{a_1}_{P_4}, {a_2}_{P_4}, {a_3}_{P_4}\} = \{S_1(1), S_1(2), S_1(3)\}</math>
-Для последующего восстановления исходного числа с коррекцией возможной ошибки, можно воспользоваться следующим алгоритмом:
+Для последующего восстановления исходного числа с коррекцией возможной ошибки можно воспользоваться следующим алгоритмом:
 <p><math>if ({a_3}_{P_1} == 0) \{</math></p>
@@ Строка 129: / Строка 129: @@
 Входами подсхемы <math>S_i, i>1</math> являются <math>N-i+1</math> p-входов <math>i-1</math> ступени подсхемы <math>S_1</math>. Выходы подсхемы <math>S_i, i>1</math>: от <math>S_{i}(i)</math> до <math>S_i(N)</math>.
-Выходы рассмотренной схемы преобразователя необходимы и достаточны для полиадического представления всех проекций. Цифры полиадического кода проекции <math>P_{N}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-1)</math>. Цифры полиадического кода проекции <math>P_{N-1}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-2)</math>, и <math>S_1(N-1)</math>.
+Выходы рассмотренной схемы преобразователя необходимы и достаточны для того, чтобы получить полиадическое представление всех проекций. Цифры полиадического кода проекции <math>P_{N}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-1)</math>. Цифры полиадического кода проекции <math>P_{N-1}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-2)</math>, и <math>S_1(N-1)</math>.
 Цифры полиадического кода проекции <math>P_{i}, i<N-1</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(i-1)</math>, если <math>i>1</math>, и от <math>S_1(i+1)</math> до <math>S_1(N)</math>.
@@ Строка 143: / Строка 143: @@
 В-четвертых, вторая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам второго порядка.
-Процесс продолжается до тех пор, пока не будут построены все <math>N-1</math> ступеней. Затем там, где необходимо, добавляются элементы '''LATCH''', чтобы провести все цифры полиадического кода до конца конвейера.
+Процесс продолжается до тех пор, пока не будут построены все <math>N-1</math> ступеней. Затем там, где необходимо, добавляются элементы '''LATCH''', чтобы передать все цифры полиадического кода до конца конвейера.
-Простой метод основанный на репликации требует <math>X = (N \cdot (N-1) \cdot (N-2))/2</math> LUT и ROM. Сокращенный метод требует <math>(Y-1)</math> ROM и <math>(Y-N+1)</math> LUT, где <math>Y = (N \cdot (N-1) \cdot (N+1))/6</math>. Количество уровней обоих методов совпадает и для реализации используются одинаковые элементы, поэтому тактовая частота работы после сокращения площади не изменится.
+Простой метод, основанный на репликации, требует <math>X = (N \cdot (N-1) \cdot (N-2))/2</math> LUT и ROM. Сокращенный метод требует <math>(Y-1)</math> ROM и <math>(Y-N+1)</math> LUT, где <math>Y = (N \cdot (N-1) \cdot (N+1))/6</math>. Количество уровней обоих методов совпадает, и для реализации используются одинаковые элементы, поэтому тактовая частота работы после сокращения площади не изменится.
 <table style="border: 1px solid black; padding: 3px;">

← Предыдущая		Версия 14:31, 6 ноября 2013
Строка 139:		Строка 139:
	Во-вторых, выявляются уникальные подформулы.		Во-вторых, выявляются уникальные подформулы.

−	В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих подформулам первого порядка (наибольшей вложенности).	+	В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам первого порядка (наибольшей вложенности).
		+
		+	В-четвертых, вторая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам второго порядка.
		+
		+	Процесс продолжается до тех пор, пока не будут построены все <math>N-1</math> ступеней. Затем там, где необходимо, добавляются элементы '''LATCH''', чтобы провести все цифры полиадического кода до конца конвейера.

← Предыдущая		Версия 14:15, 6 ноября 2013
Строка 132:		Строка 132:

	Цифры полиадического кода проекции <math>P_{i}, i<N-1</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(i-1)</math>, если <math>i>1</math>, и от <math>S_1(i+1)</math> до <math>S_1(N)</math>.		Цифры полиадического кода проекции <math>P_{i}, i<N-1</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(i-1)</math>, если <math>i>1</math>, и от <math>S_1(i+1)</math> до <math>S_1(N)</math>.
		+
		+	Данный преобразователь может быть реализован следующим образом:
		+
		+	Во-первых, при помощи преобразования в полиадический код определяются <math>N-1</math> цифр полиадического кода, которые должны быть вычислены для каждой из <math>N</math> проекций. Затем каждая из цифр выражается через элементы, необходимые для ее вычисления.
		+
		+	Во-вторых, выявляются уникальные подформулы.
		+
		+	В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих подформулам первого порядка (наибольшей вложенности).
		+

← Предыдущая		Версия 21:46, 5 ноября 2013
Строка 109:		Строка 109:
	Во-первых, из <math>N</math> каналов модулярного представления числа <math>X</math>, создаем <math>N</math> наборов по <math>N-1</math> каналов, причем последовательно исключается каждый канал, формируя так называемые проекции ("исключающие наборы"). Пусть <math>P_i</math> - проекция, полученная исключением канала <math>x_i</math>. Преобразуем в полиадический код каждую из проекций <math>P_i</math>. Если для всех проекций старшие разряды полученного полиадического кода равны нулю, ни в одном канале <math>x_i</math> ошибки нет. Если полученные старшие разряды ненулевые для всех проекций, кроме <math>P_j</math>, то в канале <math>x_j</math> присутствует ошибка, а <math>P_j</math> - правильное представление числа <math>X</math>.		Во-первых, из <math>N</math> каналов модулярного представления числа <math>X</math>, создаем <math>N</math> наборов по <math>N-1</math> каналов, причем последовательно исключается каждый канал, формируя так называемые проекции ("исключающие наборы"). Пусть <math>P_i</math> - проекция, полученная исключением канала <math>x_i</math>. Преобразуем в полиадический код каждую из проекций <math>P_i</math>. Если для всех проекций старшие разряды полученного полиадического кода равны нулю, ни в одном канале <math>x_i</math> ошибки нет. Если полученные старшие разряды ненулевые для всех проекций, кроме <math>P_j</math>, то в канале <math>x_j</math> присутствует ошибка, а <math>P_j</math> - правильное представление числа <math>X</math>.

		+
		+	Пусть '''ROMij''' - это любая схема или программа, получающая в момент времени 0 на вход целые <math>p</math> и <math>q</math> и в момент времени <math>T</math> выдающая на выход <math>r</math>, где <math>r = \|(p - q) \cdot p_j^{-1}\|_{p_i}</math>.
		+
		+	Пусть '''LATCH''' - это любая схема или программа, получающая в момент времени 0 на вход целое число и выдающая это число на выход в момент времени <math>T</math>.
		+
		+	Можно получить конвейерную схему, реализующую преобразование в полиадический код, разместив и соединив элементы '''ROMij''' и '''LATCH''', определенные выше, как показано на следующем рисунке.

	[[изображение:PoliadicCodeConvGeneralCase.PNG]]		[[изображение:PoliadicCodeConvGeneralCase.PNG]]
		+
		+
		+	Назовем эту схему схемой преобразователя в полиадический код размера <math>D</math>. На вход схемы поступают цифры остатков, обозначенные от <math>I1</math> до <math>ID</math>, а выходами являются цифры полиадического кода, обозначенные от <math>O1</math> до <math>OD</math>. Больший индекс соответствует старшему разряду. <math>D</math> столбцов рассматриваются от <math>1</math> до <math>D</math>, причем столбец <math>1</math> принимает младший вход. <math>D-1</math> ступеней конвейера рассматриваются от <math>1</math> до <math>D-1</math>, причем входы схемы поступают на ступень <math>1</math>. Каждая ступень конвейера срабатывает за время <math>T</math>. Каждая ступень конвейера состоит из некоторого числа элементов '''ROMij''' и '''LATCH''', на входы которых поступают выходы предыдущей ступени, а выходы передаются на входы следующей ступени. Элемент с индексами '''i.j''' - это '''ROMij''', если <math>i>j</math>, или '''LATCH''', в противном случае. Левый вход элемента '''ROMij''' - <math>p</math>, правый - <math>q</math>.
		+
		+	Для произвольного значения <math>N</math> схема сокращенного преобразователя в полиадический код - это конвейерная схема из <math>N-2</math> ступеней, содержащая <math>(Y-1)</math> элементов '''ROMij''' и <math>(Y-N+1)</math> элементов '''LATCH''', где <math>Y = (N \cdot (N-1) \cdot (N+1))/6</math>. Входом схемы являются <math>N</math> цифр модулярного представления, выходом - <math>(N+1) \cdot (N-1)/2</math> цифр полиадического кода. Данная реализация преобразователя заключает в себе <math>N-1</math> подсхем преобразователя в полиадический код, от <math>S_1</math> до <math>S_{N-1}</math>. Подсхема <math>S_z</math> содержит <math>N-z+1</math> элементов. Элемент '''ROMij''', находящийся в столбце <math>u</math>, ступени <math>v</math> подсхемы <math>S_z</math> определяется так:
		+
		+	* <math>i=u+z-1;\ j=v+z-1</math>.
		+
		+	Входами подсхемы <math>S_1</math> являются цифры от <math>x_1</math> до <math>x_N</math>. Подсхема <math>S_1</math> представляет собой особый случай, поскольку сокращена на одну ступень, ее выходы формируются после <math>N-2</math> ступени: это цифры полиадического кода от <math>S_{1}(1)</math> до <math>S_1(N)</math>.
		+
		+	Входами подсхемы <math>S_i, i>1</math> являются <math>N-i+1</math> p-входов <math>i-1</math> ступени подсхемы <math>S_1</math>. Выходы подсхемы <math>S_i, i>1</math>: от <math>S_{i}(i)</math> до <math>S_i(N)</math>.
		+
		+	Выходы рассмотренной схемы преобразователя необходимы и достаточны для полиадического представления всех проекций. Цифры полиадического кода проекции <math>P_{N}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-1)</math>. Цифры полиадического кода проекции <math>P_{N-1}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-2)</math>, и <math>S_1(N-1)</math>.
		+
		+	Цифры полиадического кода проекции <math>P_{i}, i<N-1</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(i-1)</math>, если <math>i>1</math>, и от <math>S_1(i+1)</math> до <math>S_1(N)</math>.

@@ Строка 101: / Строка 101: @@
 :<math> X \leq \prod^{(N-2)}_{i=1} p_{i}</math>
-Представление числа <math>X</math> в модулярном виде <math>N</math> набором остатков таково: <math>(x_1, x_2, x_3, ..., x_N)</math>, где <math>x_i</math> - значение остатка <math>X (mod  p_i)</math>. В этом случае 2 цифры остатков избыточны. Данный набор позволяет найти и исправить одиночную ошибку в одном из модулярных каналов.
+Представление числа <math>X</math> в модулярном виде <math>N</math> набором остатков таково: <math>(x_1, x_2, x_3, ..., x_N)</math>, где <math>x_i</math> - значение остатка <math>X (mod\  p_i)</math>. В этом случае 2 цифры остатков избыточны. Данный набор позволяет найти и исправить одиночную ошибку в одном из модулярных каналов.
 Для поиска и коррекции ошибок используется преобразование модулярного представления числа в полиадический код.

← Предыдущая	Версия 19:12, 2 ноября 2013
Строка 110:	Строка 110:


−	+	[[изображение:PoliadicCodeConvGeneralCase.PNG]]
−	+

@@ Строка 92: / Строка 92: @@
 <p>&nbsp;&nbsp;&nbsp;Ошибка более чем в 1 канале</p>
 <p><math>\}</math></p>
 Для произвольного значения <math>N</math> схема сокращенного преобразователя в полиадический код строится следующим образом.
 Возьмем систему остатков для следующего набора <math>N</math> взаимно простых целых модулей: <math>(p_1, p_2, p_3, ..., p_N)</math>, где <math>(p_{i+1} < p_{i})</math>.
-Пусть <math>k</math> - целое число, такое, что
+Пусть <math>X</math> - целое число, такое, что