Участник:Nikz - История изменений

NikZ в 18:35, 17 июня 2014

2014-06-17T18:35:21Z

NikZ в 15:49, 16 июня 2014

2014-06-16T15:49:50Z

NikZ в 15:21, 16 июня 2014

2014-06-16T15:21:51Z

NikZ в 16:47, 15 июня 2014

2014-06-15T16:47:24Z

NikZ в 15:59, 15 июня 2014

2014-06-15T15:59:38Z

NikZ в 14:19, 15 июня 2014

2014-06-15T14:19:26Z

NikZ в 14:03, 15 июня 2014

2014-06-15T14:03:11Z

NikZ в 18:31, 13 июня 2014

2014-06-13T18:31:02Z

NikZ в 11:24, 19 мая 2014

2014-05-19T11:24:35Z

NikZ в 11:24, 19 мая 2014

2014-05-19T11:24:00Z

@@ Строка 152: / Строка 152: @@
 == Декодирование Рида-Соломона ==
 Первым шагом необходимо выполнить деление полинома на порождающий полином <math>g(x)</math>. Если остаток от деления равен 0, то сообщение не искажено и декодирование для систематического кода тривиально.<br />
-В случае же присутствия ошибки придется выполнить следующие действия:<br />
+Разделим закодированное сообщение на образующий полином: <math>\frac{12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4}{x^{6}+7x^{5}+9x^{4}+3x^{3}+12x^{2}+10x+12}=0</math>,<br /> в этом можно убедиться, самостоятельно проделав операцию деления, согласно арифметике поля GF_{16}</math><br />
 Декодирование основано на построении многочлена синдрома ошибки S(x) и отыскании соответствующего ему многочлена локаторов L(x).<br />
 Локаторы ошибок – это элементы поля Галуа, степень которых совпадает с позицией ошибки. Так, если искажён коэффициент при <math>x^{4}</math>, то локатор этой ошибки равен <math>a^{4}</math>, если искажён коэффициент при <math>x^{7}</math> то локатор ошибки будет равен <math>a^{7}</math> и т.п. (а – примитивный член, т.е. в нашем случае a=2).
@@ Строка 160: / Строка 163: @@
 Ясно, что если этот многочлен будет найден, то мы легко сможем определить локаторы ошибок – для этого потребуется только определить его корни.<br />
 Для определения этого полинома сначала получают вспомогательный полином <math>S(x)</math>, так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен <math>r(x) = C(x) mod          g(x)</math>:    <math>S_i=e(a^{i})</math><br />
 Между <math>L(x)</math> и <math>S(x)</math> существует соотношение<br />
 <math>L(x)S(x)=W(x)modx^{N-K}</math><br />
@@ Строка 210: / Строка 216: @@
 <math>ML = V, \Rightarrow M^{-1}V</math>
 Например, для нашего примера – кода Рида-Соломона (6, 4) матрица M имеет вид:<br />
-<math> M = S_1</math>  , а вектор   <math>V = S_2; </math>   <math>  L(1) = S(2) / S(1)</math><br />
+<math> M = S_1</math>  , а вектор   <math>V = S_2; </math>   <math>  L(1) = S(2) / S(1) = 3 / 1 = 3 </math><br />
 Таким образом, вычисление полинома локаторов сводится к построению матрицы M, нахождению обратной ей и умножению на вектор V.
 Обратная матрица получается так же, как и в обычной математике, например Жордановым методом.
 После того, как полином <math>L(x)</math> найден, следует найти его корни – они будут обратны к локаторам ошибок. <br />
 После нахождения позиции ошибки,займемся нахождением значением ошибки:<br />
 Воспользуемся определением синдромной функции:<br /> <br />
@@ Строка 221: / Строка 228: @@
 <math>S(n) = r(\alpha) = e_1 L_1^{n} + e_2 L_2^{n} + ... + e_n L_n^{n}</math>,<br />
 <br /> где <math>e_1,e_2,..,e_n - </math>значение ошибки. <math>L_1,L_2,..,L_n - </math>позиция ошибки.<br /><br />
-Для нашего кода <math>RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1</math>
+Для нашего кода <math>RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1 = 1 / 3 = 2^{0} / 2^{4} = 2^{11} = 14</math> - позиция ошибки.<br />Таким образом сформируем многочлен вычисленной ошибки <math>E'(x) = 14x^{4}</math>, который совпадает с заданным <math>E(x)</math><br />

@@ Строка 215: / Строка 215: @@
 После того, как полином <math>L(x)</math> найден, следует найти его корни – они будут обратны к локаторам ошибок. <br />
 После нахождения позиции ошибки,займемся нахождением значением ошибки:<br />
-Воспользуемся определением синдромной функции:<br />
+Воспользуемся определением синдромной функции:<br /> <br />
-<math>S(1) = r(\alpha) = e_1 L_1 + e_2 L_2 + ... + e_n L_n</math>,<br /> где <math>e_1,e_2,..,e_n - </math>значение ошибки. <math>L_1,L_2,..,L_n - </math>позиция ошибки.<br />
+<math>S(1) = r(\alpha) = e_1 L_1 + e_2 L_2 + ... + e_n L_n</math>,<br />
 Для нашего кода <math>RS(6,4): S(1) = e_1 L_1; e_1 = S(1) / L_1</math>

@@ Строка 159: / Строка 159: @@
 где <math>X_1,X_2,..,X_i</math> - локаторы ошибок<br />
 Ясно, что если этот многочлен будет найден, то мы легко сможем определить локаторы ошибок – для этого потребуется только определить его корни.<br />
-Для определения этого полинома сначала получают вспомогательный полином <math>S(x)</math>, так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен <math>r(x)=C(x)mod g(x)</math><br />
+Для определения этого полинома сначала получают вспомогательный полином <math>S(x)</math>, так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен <math>r(x) = C(x) mod          g(x)</math>:    <math>S_i=e(a^{i})</math><br />
-<math>S_i=e(a^{i})</math>
+Между <math>L(x)</math> и <math>S(x)</math> существует соотношение<br />

← Предыдущая		Версия 16:47, 15 июня 2014
Строка 151:		Строка 151:
	<math>C(x)=12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4</math><br />		<math>C(x)=12x^{5}+10x^{4}+12x^{3}+7x^{2}+x+4</math><br />
	== Декодирование Рида-Соломона ==		== Декодирование Рида-Соломона ==
		+	Первым шагом необходимо выполнить деление полинома на порождающий полином <math>g(x)</math>. Если остаток от деления равен 0, то сообщение не искажено и декодирование для систематического кода тривиально.<br />
		+	В случае же присутствия ошибки придется выполнить следующие действия:<br />
		+	Декодирование основано на построении многочлена синдрома ошибки S(x) и отыскании соответствующего ему многочлена локаторов L(x).<br />
		+	Локаторы ошибок – это элементы поля Галуа, степень которых совпадает с позицией ошибки. Так, если искажён коэффициент при <math>x^{4}</math>, то локатор этой ошибки равен <math>a^{4}</math>, если искажён коэффициент при <math>x^{7}</math> то локатор ошибки будет равен <math>a^{7}</math> и т.п. (а – примитивный член, т.е. в нашем случае a=2).
		+	Многочлен локаторов <math>L(x)</math> – это многочлен, корни которого обратны локаторам ошибок. Таким образом, многочлен <math>L(x)</math> должен иметь вид <br />
		+	<math>L(x)=(1+xX_1 )(1+xX_2)..(1+xX_i)</math><br />
		+	где <math>X_1,X_2,..,X_i</math> - локаторы ошибок<br />
		+	Ясно, что если этот многочлен будет найден, то мы легко сможем определить локаторы ошибок – для этого потребуется только определить его корни.<br />
		+	Для определения этого полинома сначала получают вспомогательный полином <math>S(x)</math>, так называемый синдром ошибки. Коэффициенты синдрома ошибки получаются подстановкой степеней примитивного члена в остаток многочлен <math>r(x)=C(x)mod g(x)</math><br />
		+	<math>S_i=e(a^{i})</math>

@@ Строка 140: / Строка 140: @@
 <math>C(x) mod g(x)=0</math><br />
 В случае, если закодированное сообщение будет изменено, то это равенство будет нарушенным, не считая случая, когда ошибка окажется кратной <math>g(x)</math>. Факт искажения можно рассматривать как прибавление к <math>C(x)</math> некоторого полинома ошибки <math>E(x)</math>.<br />
-'''Пример:'''
+'''Пример:'''<br />
-<br />
+Рассмотрим кодирование информации. Пусть наше сообщение такое:
 == Декодирование Рида-Соломона ==

@@ Строка 125: / Строка 125: @@
 Кодирование Рида-Соломона будем производить систематическим кодом, это означает, что в закодированное сообщение будет содержать в себе в явном виде исходное сообщение. Каким образом это делается:
 Сначала полином сдвигается на <math>N-K</math> коэффициентов влево <br />
-<math>P'(x)=p(x)x^{N-K}</math>
+<math>p'(x)=p(x)x^{N-K}</math> ,а потом вычисляется остаток от деления на порождающий полином и прибавляется к <math>p'(x)</math>: <math>C(x)=p'(x)+p'(x)mod g(x)</math>. <br />
-,а потом вычисляется остаток от деления на порождающий полином и прибавляется к p’(x):
+Для систематического кого очевидно, что <math>K</math> старших коэффициентов полученного кода <math>C(x)</math> содержат исходное сообщение. Это удобно при декодировании.

← Предыдущая		Версия 14:03, 15 июня 2014
Строка 122:		Строка 122:
	Например, построим порождающий многочлен кода Рида-Соломона с <math>N=15,K=9</math>, способного исправлять до 3 ошибок <math>(15-9)/2=3</math>:		Например, построим порождающий многочлен кода Рида-Соломона с <math>N=15,K=9</math>, способного исправлять до 3 ошибок <math>(15-9)/2=3</math>:
	<math>g(x)=(x+2)(x+2^{2} )(x+2^{3} )(x+2^{4} )(x+2^{5} )(x+2^{6} )=x^{6}+7x^{5}+9x^{4}+3x^{3}+12x^{2}+10x+12</math>. ''(Возведение в степень и умножения выполнены над полем GF<sub>16</sub> )!''		<math>g(x)=(x+2)(x+2^{2} )(x+2^{3} )(x+2^{4} )(x+2^{5} )(x+2^{6} )=x^{6}+7x^{5}+9x^{4}+3x^{3}+12x^{2}+10x+12</math>. ''(Возведение в степень и умножения выполнены над полем GF<sub>16</sub> )!''
		+	== Кодирование Рида-Соломона ==
		+	Кодирование Рида-Соломона будем производить систематическим кодом, это означает, что в закодированное сообщение будет содержать в себе в явном виде исходное сообщение. Каким образом это делается:
		+	Сначала полином сдвигается на <math>N-K</math> коэффициентов влево <br />
		+	<math>P'(x)=p(x)x^{N-K}</math>
		+	,а потом вычисляется остаток от деления на порождающий полином и прибавляется к p’(x):

@@ Строка 1: / Строка 1: @@
 == Постановка задачи ==
 В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Строка разбивает на блоки длиной 4 бита и каждый блок представляет собой элемент поля Галуа GF<sub>16</sub>. Необходимо отследить и исправить одиночную ошибку, внесённую в один из блоков.
@@ Строка 4: / Строка 5: @@
 == Теоретические основы алгоритма ==
 === Поля Галуа ===
-Операцию сложения определим как «исключающее ИЛИ»(XOR).Очевидно, что в таком случае операция сложения является обратной самой себе. Тогда операция умножения в двоичном виде будет выглядеть так:
+Операцию сложения определим как "исключающее ИЛИ" <math>(XOR)</math>.Очевидно, что в таком случае операция сложения является обратной самой себе. Тогда операция умножения в двоичном виде будет выглядеть так:
 <math> \begin{matrix} *\underline{\begin{matrix}
@@ Строка 111: / Строка 112: @@
 '''Таким образом, получили поле <math>GF_{16}</math>, то есть для двоичных 4-разрядных чисел.'''

← Предыдущая		Версия 11:24, 19 мая 2014
Строка 110:		Строка 110:
	Таким образом, при дальнейшем умножении весь цикл повторится снова. Полученные степени двойки не сложно умножать между собой, например: <math> 1315=2^{13}2^{12}=2^{25 mod 15}=2^{10}=7 </math>. Можно проверить результат,разделив <math> \frac{7}{13}=\frac{2^{10}}{2^{13}}=2^{-3 mod 15}=2^{12}=15 </math>.<br />		Таким образом, при дальнейшем умножении весь цикл повторится снова. Полученные степени двойки не сложно умножать между собой, например: <math> 1315=2^{13}2^{12}=2^{25 mod 15}=2^{10}=7 </math>. Можно проверить результат,разделив <math> \frac{7}{13}=\frac{2^{10}}{2^{13}}=2^{-3 mod 15}=2^{12}=15 </math>.<br />

−	'''Таким образом, получили поле GF_{16}, то есть для двоичных 4-разрядных чисел.'''	+	'''Таким образом, получили поле <math>GF_{16}</math>, то есть для двоичных 4-разрядных чисел.'''