конспект лекции__1

компонент e(x)описываетсяпаройэлементов:							Yi – величошибокна		Xi – номерпозицииошибки
(лок атошибкир).		Yi, Xi – элементы GF(q),иэл					емент Xi=αi,αi Є GF(q).
	Дляописанияошибисп: кльзуются
	1Мног. локаторовчленшибок:
				υ
			Λ(x) = ∏(1 − xX i ) = Λυ xυ + Λυ−1xυ−1 + ... + Λ1x + Λ0 ,
			i=1
имеющкорний		Xi–1, i = 1, …,v взаимныеклокаторамош					ибок,т.	е. Xi–1·α i	= 1.
	2Мног. значенийошибокчлен			Ω(x) :

Ω(x)=S(x)Λ(x) (mod x2t), (*)

2t	2t	υ
где S(x) = ∑S j x j	= ∑∑Yi X ij x j		–	синдрмномныйгочлен	бесконечнойстепени,длякоторо			гоизвестны
j=1	j=1i=1
только 2t коэффициентовдляпоступившейкомбинации					РС-кода.
Здесь S j	υ
	= ∑Yi Xij = e (α j )			– элементсиндрома,α	j – кореньпорожда		ющегомн РСгочлена		-кода.
	i=1
Значения Sj =e(αj)задаютсяпрове			рками:
Sj=C(αj)=f(αj)+e(αj)=e(α j),
где m0≤j≤m0+2t–1при		m0=1.
Равенство(*)определяетмнизжество(2					t–υ)уравненийназывается		ключевымуравнением		,
таккаконопредставляетсяключом« »решениза екодированияачи.
Этостан овитсяпонятным,еслиучесть,чтостепень					Ω(x)непревышает	υ–1ипоэтомуспр		аведливо:
				[Λ(x) S(x)]υ2t−1 = 0,
где [a(x)]mn = am xm + am+1xm+1 +... + an xn .

168

Из(*)необходимополучить

υ уравненийдля

υ неизвестныхкоэффициентов

Λk.Этиура

внения

являютсяинейн.Онимогутбрешенытьобычнымиметодалибоспомощьютерационных

процедур.Посленахож

дениямн

огочлена Λ(

x)

ключевоеуравнепозволяетнайтиеизвестныеие

компонентывектора

e(x)ипонимвыходнвектордек йд

ера: f(x)=C(x)+e(x).

Простейшимпутемнахождкор огочленаейния

Λ( x) являетсяметпроби шибокд,

известныйкак

процедураЧеня

.Э

тапроцедурасостоитвпослед

овательномвычислении

Λ(α j) для

каждого j ипр

оверкиполучензначеноныхий

ль.Есливеличина

Λ(α

–k) равнанулю,то

αk

является

взаиккормнымю

огочленалокаторошибовк

k-йэлементкодомбинациивойсодержитошибку.

Наиболеепростспособомвычислзначения

Λ( x) вточке

β является схемаГорнера

:

Λ(β) = (...(((Λυβ + Λυ−1 )β + Λυ−2 )β + Λυ−3 )β + ...Λ0 ) .

Длявычисления

Λ(β)

посхемеГорнератребуетсятолько

υ умножений υ слож,гдений

υ –

степень Λ( x).

Попрслелокаторделенияошибспомощьювк

ключеуранвненияого

аходимзначения

ошиб.Дляэт,используягокзначениясомножителей,вх

одящихвравенстводля

Ω( x),

перепишем

ключевоеуравнениеследующим

бразом:

+ 2t υ

(

+

υ

(1 − X

x)( (mod x2t

)=

Ω( x) = )

Y X j x j−1 &

i

∑∑ i

i

)∏

&

i=1

) j=1i=1

&

υ

+

x)

2t

( X

(

(1 − X

x) (mod x2t ).

=

Y X

i

)(1 − X

i

∑

i

x) j−1 &

∏

l

∑ i

)

i=1

j=1

& l ≠i

Сворачиваявыражениеквадратныхско

бках,получаемокончатель

но

υ

Ω( x) = ∑Yi X i (1 − X i2t x2t )∏(1 − X l x)(mod x2t )

i=1

l ≠i

Приводяэтовыражениепомодулю

x2t

,пол учаем

υ

Ω( x) = ∑Yi X i ∏(1 − X l x) .

i =1

l ≠i

169

Вычислиммногзнаошибокнаенийленп		озиции l: x = X l−1 .
	Ω( X −1 ) = Y X			l ∏	(1 − X	j	X −1 ) ,
	l		l				l
				j≠l
откуда			Ω( X l−1 ) X l−1
	Yl	=					.
			∏(1 − X j X l−1 )
			j≠l
Найдемпроизвотнлогочленадную	каторошибокв			Λ(x):

υ

Λ( х) = −∑ Xi ∏(1 − xX j ).

i=1 j≠i

Для l-й позицииполучаем:

Λ%( X l−1 ) = −X l ∏(1 − X j X l−1 ) .

			j≠l
Сучетомпоследнеговыражения		Yl значениеошибкип	озиции l принимаетвид
		Yl = −	Ω( X l−1 )	.
			Λ#( X l−1 )
Рассмспдекодированиятренныйсоб		позволяетнайтизначение		шибокпоизвестныммн	огочленам
локатизначенийошров	ибок.	Онизвлитературеесн		[ 4 ] как алгоритмФорни	. Указанные
многовычврезульисляюленырешенияключевоготсяатеура				внения.

170

	7.1.Задачи
	1. Построитьвсециклическиекодынаосноверазложенияд					вучлена x15 +1. Нижеприведены
сомнипожителиследовательностистепениихкорней.
СомножитСтепкоренльейи
x+1		0=15
x4+x+1		1	2	4	8
x4+x3 +x2 +x+1		3	6	9	12
x2+x+1		5	10
x4+x3 +1		7	11	13		14
	2. Определикоррексвойствациьклическогорующие(15,11)					– кода
а)с	g(x)=1+x+x4;
б)с	g(x)=1+x3+x4;
в)с	g(x)=1+x+x2+x3+x4.
	3. Определикоррексвойствациьклическогорующие(15,7)					– кода
а)с	g(x)=(1+x+x4)(1+x3+x4);
б)с	g(x)=(1+x+x4)(1+x+x2+x3+x4)
в)с	g(x)=(1+x3+x4)(1+x+x+x2+x3+x4)

4. Постпороматрицуитьждпющдляоверокицуукю						ороченногоциклического
(10,5) – кода,полученногоиз(15,10)		– кодас	g(x)=(1+x)(1+x+x4).
Определить dmin (10,5) – кода.
5. Привестиматп оверокицу		H(7,4),построеннуювпримере				5.5 кк аноническойформе.
6. Показать,чтоп ле	GF(23)спримитивнымэлементо					α,являющи мсякорнемнеприводи	мого
многочлена π( x)=1+x+x3	,можетбытьпре	дставленоследующемвиде:
Степень			Многочлен			Вектор
	0		0			000
	1		1		100
	α		α		010
	α2		α2		001
	α3		1	+ α	110
	α4		α+α 2		011
	α5		1	+ α + α2	111
	α6		1	+ α2	101
	α7=1		1		100
							171

7.2.БыстрдекодированиеБЧХдов

1).Ключевое уравнение

	Рассмпробысттримцедекодированияу угоприменительнок									кодамРида	-
Соломона(		PC)Дляэтих. кодовсправедливаграницаСинглтона:
					n-k= d-1=2t,
	где n-k — избыточнкод мбинациивой, сть
	d - минимкодовоерасстояниельное,
	t - кратностьгаранти рованноисправляемыхошибок.
	Будемполагать,чтокиспользуетсядврежимеисправленияошибок.									ПустьвприемникАПД
поступила кодкомбинациявая				PC-кода
					С(	x)=f (x)+e(x),
где f(x) - переданнаяпередатчикомбинацияАПДкод вая, второйпроц										ессепередачипо
каналусвязипроизошло			υ ошибок,отображаемыхмногочленом()Здесь. ≤0							v≤t.
	Многочлможноошибокпревдставитьвиде
					e(x)=ei1 xi1 +ei2xi2+…+eivxiv=∑ eilxil,
где eil - значениеошибки,			il - номерпозициикод мбинациивой,которойпр							оизошлаошибка.	Для
исправленияошибнеобходимоопределитьк					eil	и il. Этовозможно			выполнитьнаосновесиндрома.
Введемпонятиесиндрмно: многогочлена
					S(x)=S1x0+S2x1+…+Sn-k=2tx2t-1 .
	Коэффициенты		Si определяютсяподстановкой				С(х)	корней αl порождающемногочлена
кода PC.
					S1=C(x= αl)=f(x= αl)+е(х= αl)=e(αl),
						где l≤l≤2t.
	Теперьполучим,		S1=e1αi1 +e2αi2+…+eivαiv ит.д.
	ДЛЯ упрощензаписикомпонентовияндрмн многогочпределимдляена									всех l=1,...,v
значенияошибки		Уl= eil ,илокаторыошибок			Хl= ail=l, где il=l - истинноеположение					l-й ошибки.
	Вэтихновыхобозначениях				S1 запишетсяввиде:
					S1=Y1X1+ Y2X2+…+ YyXy.
Здесь Yl и Хl - элементыполя				GF(q) надкотпорымстроен			PC-код,а		α - примиэлементивныйого
поля.	Врезультатеполучследующуюсистм					емуиз2	t	уравнений относительно υ неизвестных
локаторов X1 ,..., Xv и v неизвестзначенийых					ошибок Y1,...,Yυ:

S1=Y1X1+ Y2X2+…+ YvXv,

172

	S2=Y1X12+ Y2X22+…+ YvXv2,
	. . .
	S2t=Y1X12t+ Y2X22t+…+ YvXv2t.
Всилуопределениясиндромаэтасистемауравненийдо	лжнаимехобыоднотья
реш.Втекодированияорииниедоказано,чтоэторешение	единственно.Изложениеизвестных
алгорпоэтогоирешенияскатмв	базируетсянапонятииключеура. вненияого
Дляегоформированияввоещедмногочленаятся:

1.Многочленлокат оровошибок

Λ(х)=1+		Λ1х+ Λ2 х2+ Λvxv, имеющкорн,обратныелокаторамийошибок	Xl-1, l=1…,v. Это
позволяетпредставить		Λ(x) вследующемвиде:
		ν
		Λ(x) = ∏(1 + xX l )
		l =1
2.	Многзначенийошибокчлен.Онопределяетсячерез		S(x) и Λ(х) в соответствии
видомввед	енноговышемногочленашибок

Ω(x)=S(x)*

Выражениедля Ω(х) определяетмножесиз ва уравнением,таккаконоявляетсяключомрешения

Ключевоеуравнениепозволяетполучить коэффициентов Λ(x). Этиураявненияляютсяинейными.Они методаитераци,либоспомощьюпроцедур.П сленных

позволяетнайти неизвесткомпомногочленаыеенты

комбинацию f(x)=C(x)+e(x).

Изизложеможносделатьвывдекодированиеного,чт кодовБЧХ ключеурараспдвавненияогоаэт.апается

I этап — вычислениемноглокаторошибочлена этапомдекодированиезавершается.

II этап - длянедвоичныхкодов,какимия ляютсяРС значенийошибок Ω( х), позвычислятьоляющего комбинации.

Длянахождениямногочленалокаторошибиз овк

1. АлгоритмПитерсона.

2 .АлгоБерлекемпаитм -Месси.

3- АлгоритмЕвклида - алгоритмСКХН.

Λ (x) (mod x2t)
2t-v уравнений		называетсяключевым
задекодированияачи.
v уравнений для v неизвестных
	могутбытьрешеныобычными
нахождения Λ(х)			ключеуравноение
е(х )	ипоним	переданнуюкодову
			наосновереш ния
к Λ(х).	Длядвоичных		кодовБЧХэтим
	-коды,	вычислениемногочлена
значениекаждойиз		υ	ошибоквпринятой

литературы известнытриалгоритма:

173

Авторыпервалгори р указговинхтмованы.званииАлгоритм					Евкдляцелейида
решенияключеурабылвпеногонияредвые			ложенчетырьмяавторами:Сугияма,Касахара,
ХирасаваНамекава.Вдальнейшем			длякраткостибудемназыватьалгоритмомЕвклида.
АлгоритмПитерсонаможетбытьиспользкаксамостоятельнаяван				процедурадекодирования
недвоичциклкодовинческихыха			II этапе.
АлгоБерлекемпаитм		-МессиалгоритмЕвклидана		II этапе	декодированиядля
недвоичныхциклическихкодовдополняюталгоритмом				Форни,позвпокорнямляющим	Λ (х ) и
многочлену Ω(x) найтизначения		ошибок.СочетанБерлекемпаалгоритма			-Мессиалгоритма
Форни получилоназвание	быстрогодекодированиякодовБЧХ.

174

Рассмотримсущностьизложенныхалгоритмовдекодирования

2).Решениеключеуравогонения

а)Алгоритм. Питерсона .

У.Питерсон[1]предстаключевоеуравненформематрил:ичной

&Sv+1		#
S	v+2	!
		!
•		! =
		!
•		!
S	2v	!
%

& S1S2

•

•%Sv

S2			Sv			#	&λv		#
S		3	S		v+1	!	λ		!
						!		v−1 !
•				•		! •			!
•				•		!			!
						!	•		!
S	v+1		S	2v−1		!	λ		!
							%	1

Такимобразом,задачаопределениякоэффициентовмногочлена								локаторошибовк
сводитсякпрямомурешениюсистемы				v линейных уравненийс			v неизвестными.
	б)АлгоритмЕвклида.
Известно,что		, еслиуществуетнаибольшийобщийделитель						d(x) двухмногочленов	а(х ) и
b(х),	то существуютмногочлены			f(x) и g(x) такие, что справедливо: a(x)f{x)+b(x)g(x)=d(x).
Многочлен d(x) можетбытьнайденпоалгоритмуЕв,котлидас встоитрый
последделениисовательномстатком				а(х)	на b(х), затем b(х)		напервый остаток r1(х) ,		затем r1(х)
навтостатокрой	r2(х)	и т.д.
ПридекодированиикодовБЧХинтересуютсяконечным								резуалгоритьтатома
Евклида,промежрезу,которльтататочнымие					можнопредставитьвиде:			a(x)f(x)+b(x)g(x)=r(x).
	У.Сугиямаегос авторы[3]использов				алиэтотрезультатдлярешения			ключевого
	уравненияследующимобразом:				b(x)g(x)= ri(x) (mod a(x)), полагая,
			а(х)=х	2t, b(x)=S(x), gl(x)=Λ		i(x), ri(x)=Ω		i(x).
		Приэтомиспользуется			свойсталгоритмаЕвклида:
				deg[gi(x)]+deg[ri-l(x)]=deg[a(x)].
		Если а(х)=х			2t, то deg[Λ i(x)]+deg[Ω i-l(x))=2t,
				deg[Λi(x)]+deg[Ω		i(x))<2t.
Припоявлении		v≤t ошибокимеем:		deg[Ω( x)]< deg[Λ (x)]≤			t.

175

Существуетединственныйточндопостмножителяьюоянного					(элементаполя)
многочлен Λ(х) степени ≤t, удовлетура:воряющийнению
	Ωi(x) =S(x) Λi(x) (mod x2t),
	если deg[Ω	i-1(x)]≥t	при	deg[Λi(x)]≤t
	и deg[Ωi(x)]<t при deg[Λi+1,(x)]>t.
Поэтпромреужуточнзультатна ые		I-омшагедают		единственное интересующеенас
решениеключура. вненияого
Такимобразом,длярешенияключеураслевненияого				дуетприменять	алгоритмЕвклидадо
техпор,поканебудетвыпоусловиенено
		deg[Ω i(x)]<t.
Итак,алгоЕвклидаритмешенияключеурапометвненияогоУ. ду					Сугиямыдр.
сводитсякследующему:
1.ПрименитьалгоритмЕвклида	а(х)=х	2t и b(x)=S(x).
2. Использоватьначальныеусловия:

Λ-1(х)=0, Λ0(х)=1,

Ω- 1 (x)=x2 t ,

Ω0(x)=S(x).

	3. Остановиться,если		deg[Ω i(x)]<t.
	4. Положить Λ(х)=		Λi(x) и Ω(x)=Ω i(x).
	Привычислзначениий		Λi(x) и Ωi(x) следуетиспользоватьсвойствоалгорит								маЕвклида:
каждоеиззначений		Λi(x)	и Ωi(x) получаетсяиздвух		предшезначенийпоследующейтвующих
общейформуле:
					(Ω		i−2	(x) %		∞
			Ei(x)=Ei-2(x)+qiEi-1(x),где gi = &						#
						Ωi−1 (x)				0
отделенияуказанныхмногочленов			т,е.многочленстепени0более.
	3)АлгоритмБерлекемпа		-Месси.
	Этоталгобылпредложенитм			Э.БерлекиДж.М[4]екакссимпом							итеративный
процесспостроенияминимальйноголин гистрасдвиг							обратсвязью, налогичногоой
схемерешеразностуравия, ненийых				генерирующеговсекомпонентысиндрмн многогочлена
S(x) no υ первым.
	Цеалгью	оритмаявляетсянахожденкоэффициен				товмногочлена					локаторошибовк
Λ(х) , значениекотоопревидыхделяет				обратныхсвязей	регистра.

176

Нарис.7.1	представлендоработанныйлгоритм,позволяющийкроме	А(х) получатьтакжеи
многзнаочшибокенийлен	Ω( x).

Рис.7.1 АлгоБерлекемпаитм

-Месси.

177