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

	г)Понятиеконечныхполях
	Полемназываютмножествоэлементов, котопрдвеомеделеныопер						ации.Однанихз
называетсясложениемобозначается				a+b, адругая	– умножениемобознача		ется a b, дажееслиэт
операциинеявляютсяобычн		ымиопер		ациямисложенумножениячисел.Длятогочтмножествобы
элементов,накоторомзаданыоперациисложенияумнож						ения,былополем,необходимо		, чтобыпо
каждойизэтихоперацийвыполнялисьвсегру				пповыеаксиом		ы,атакжевыпо	лнялсядистрибутивный
закон,т.	е.длятрехлюбыхэлементовполя			а, b,	с былиспр	аведливыравенства		а (b+с)=аb+ас	и
(b+с)а=bа+са.
	Кртпо, каждойгомеопегруппации			адолжнабытькоммутативной,.			е.должновыполняться		,
а+b=b+a и аb=bа.Следуетзаметить,чтогрупп				овыесвойствапооперумножениясправедливыциидля
всненулевыхэл		ементовполя.
	Полясконечнымчислоэлементов			q назывполямиГаименилуаютпервогох
исследователяЭваристаГалуаобозн				ачают GF(q).
Числоэлементо		вполя q называют		порядкомполя	.Конечныеполяиспольз		уютсядлпостроения
большинстваизвестныхкоихдекодов				ирования.
	Взависимостиотзначения			q различают простые или расширенные поля.				Поленазывают
про,еслитым		q – простоечис.Добозначениял пр			остыхч	иселбудемиспользсимволвать		p.
	Простоеп лебразуютчислапомодулю			p: 0, 1, 2,…, p–1,а операциисложенияумножения
выполняютсямодулю		p.
	Наименьшеечислоэлементов,образующихполе,равноТак2.поледолжносодержать2
единичныхэлемент		а: 0 отноперациисительносложения				1 относительнооперацииумножения.Это
поле GF(2), илидвоичное.

108

Правсложенияумножла	енийдляэлементов					GF(2) задтаютсяблицами:
	табсложенияица: т умножблица										ения:
		+		0	1			·		0	1
	0			0	1	0				0	0
	1			1	0	1				0	1

GF(3) – троичноепосэлементами0, 1, 2					. Длянеготаблица					сложенияумножения		имеют
вид.
	+		1	2		·		0	1	2
		0
0		0	1	2	0			0	0	0
1		1	2	0	1			0	1	2
2		2	0	1	2			0	2	1

Формитаблицпропривизводитсявание			едениемрезультатасложеилиумнчожения	исел,
записвоглавестрокилинныхстолбцов,помодулю			p, т. е.вкачрествезультоппринимаетсяцта
остатокотделенияпол	ученчисланого		p.
Анализируясоставтаблиц,легкоубедиться,что			0 и 1 какединич ныеэлеме	нтыпооперации
сложеиумнизменяютожениязначендругэл иях			ементполяс ответствующейоперации.
Крто,вигоме,чтодлянока		ждогоэлементапооперациислождляненэлементовияулевыхпо
операцииумноженияимеютс		братные.

109

Ниже приведеныправсложенияумноженияладляэл											ементов GF(4) припопостроитьытке
этопизчиселле0,	1, 2, 3 попредыдущейконстру						кции.
	табсложения:ицатаблицаумножения:
	+			1	2	3	·				0	1	2	3
			0
	0		0	1	2	3	0				0	0	0	0
	1		1	2	3	0	1				0	1	2	3
	2		2	3	0	1	2				0	2	0	2
	3		3	0	1	2	3				0	3	2	1

Изанализатаблиц		ви,чтодляноэлементапо2оперумнции										оженияотсутствуетобратный,
т. е.наборчисел0,неявляетсяполем1, 2,приввед3опернии											ациипо		модулю 4. Такойрезультат
объяснимтем,что	4 неявл	яетсяпростымчис.Длялям								GF(5)сэлементами					0, 1, 2, З, 4 правила
сложенияумн	оженияимеютвид			.
		табсложения:ица						таблицаумножения:
									·
		+	0 1 2 3 4							0	1	2	3	4
		0	0	1	2	3	4	0		0	0	0	0	0
		1	1	2	3	4	0	1		0	1	2	3	4
		2	2	3	4	0	1	2		0	2	4	1	3
		3	3	4	0	1	2	3		0	3	1	4	2
		4	4	0	1	2	3	4		0	4	3	2	1

110

Изучимвозмпостржнполейэлементамиястьввпоследователде						ьностейчисел.
Определимусловия,прикотп рыхследов				ательностидлины	m сэлементамиизполя			GF(p)
образуютполе.
Рассмотримпоследовательностидлины			4 сэлементамииз		GF(2). Такиеп		оследовательности
можноскладыватькаквекторы,инулевымэл			ементомпооперациисложенияявляетс					я 0000. Для
заданияоперацииумнс пожения		ставимкаждойпоследовательностимног				очленот	α:
	Последовательность			Многочлен
		0 0 0 0		0
		1 0 0 0		1
		0 1 0 0		Α
		1 1 0 0		1+α
		0 0 1 0		α2
		1 0 1 0		1+α2
		0 0 0 1		α3
		…		…
		1 1 1 1		1+α+α2+α3

Умножениетакихмногочле		новможетдас ,епеньбольшую		, чем 3,	т. е.п оследовательность,
непринадлежащуюрассматриваемому			ожеству.
Например,	(1101)·(1001)↔(1+α+α3)·(1+α3)=1+α+α4+α6.Длятогочтсвбы				естиответк
многочленустепенинеболее		3, положим,что	α удовлетворяетуравн	ениюстепени	4, например:

Π( α)=1+α+α4=0,

или

α4=1+α.

Тогда

α5=α+α2,α 6=α2+ α3; 1+α+α 4+α6=1+α+1+α+α2+α3=α2+α3.

111

Этоэквивалентноделенам огочлению

1+α+α4 инахождению

статкаотделения:

α6+α4+α+1

α4+α+1

+ α6+α3+α2

α2+1

α+1

α4+α3+α2+

+ α4+α+1

α3+α2–остаток

Такобразомим, естоаналетприформгияполяизчрованиипсел

оследовательностей

чиселмногочленов( )Этааналогия. распр

остраняетсяинато,чтодлябратимостивведеннойоперации

умножениячтобы( систэлемввидепослеентова

довательностейдлины

m илимногочленовстепени

меньшей m,образовывалаполе)многочлен

Π( α)

долженбытьеприводимнадполемсвоих

коэффициентов.

П,образовлемногочапонноедленами

GF(р) помодулюнепривод

имогомногочлена

степени

m, называетсярасши

рениемполястепени

m над GF(p)илирасширеннымполем.Оно

содержит pm элементовиобознач

ается GF(pm).

П,образованншестнадцатьюледвоичнымип сле линыовательностями

4,

или

многочлестепениами

3 именеескоэффициентамииз

GF(2) помод

улюмногочлен

а α4+α+

1 ,

неприводимогонад

GF(2),являетсяпримеромра

сширенногополя

GF(24),

котмобытьроежет

обозначенотакже

GF(16)

Важнесвоконечныхйствомшимполейявлясл .дующеется

Множевснетвонулевыхэлементовконечногоп лябразуетгруппуоперации

умножения,

т.е.мультипликати

внуюгруппупорядка

q–1.

Рассовокупностьмотримэлементовмультипликативнойгруппы,образованнуюнекоторымэлементом

α

ивсемиегост

епенями α2, α3 ит.д.Таккакгруппаконечна,должно

появипов,т. ьсяорение

е. αi=αj.

Умножаяэторавенствона	(αi)–1 = (α–1)i,получим		1=αj-i.Следовательно,		екотораястепень		α равна 1.
Наименьшееположитчислольное		e,	такое,что	αe=1, называется порядкомэлемента				α.
Совокупностьэлементов	1, α, α2,…, αe–1 образуетподгруппу,			осколькупроизв		едениелюбыхдвух
элеменпринадлежиттосовйокупн		ости,аэлемент,обра ный		αj,	равен αe–j	итожевходит		в эту
совокупность.
Группа,котсоизстоитрая		всехтепенейодногоизееэл		ементов,называется			циклической
группой.

112

	Израссмсвойстваконтренного			ечныхполейвытекаютдваследсжных					твия.
	Первоеизнихутверждает,чтомногочлен					xq–1–1имеетсво		икорнямивсе			q–1ненулевых
элементовполя		GF(q),т.е.
				x q−1 −1= ∏( x −α)
						α GF (q)
						α≠0
	Вполе GF(q)элемент			α,имеющийпорядок	e=q–1,называется			примитивным.Отсюда следует,
чтолюбойненулевойэлемент				GF(q)являстептся	еньюпримитивнэлемента.Вторследствиеизого
рассмотренногосвойстваутвержда,чтолюбоконполечноет							GF(q)с одепржитимитивныйэлемент,
т. е. мультипликативнаягруппа				GF(q)являетсяциклич		еской.
Втабл..	6.представлены1 различнымисп			особамиэлементы		GF(24).
	Таблица6		.1
Последовательностьдлины				Многочлен			Степень			Логарифм
4
	1			2			3				4
	0000			0			0				–∞
	1000			1			1				0
	0100			Α			α				1
	0010			α2			α2				2
	0001			Α3			α3				3
	1100			1+α			α4				4
	0110			α+α2			α5				5
	0011			Α2+α3			α6				6
	1101			1+α+α3			α7				7
	1010			1+α2			α8				8
	0101			α+α3			α9				9
	1110			1+α+α2			α10				10
	0111			α +α 2+α 3			α11				11
	1111			1+α+α2+α3			α12				12
	1011			1+α2+α3			α13				13
	1001			1+α3			α14				14

113

Поле GF(24), представленное в табл. 6			.1, построеномодулю		α4+α+1 .Примитивныйэлементполя			α
являетсякорнемэтогомн. гочлена
Многочлен,корнемкоторогоявляетсяпримитивныйэлементполя,называется								итивным
многочленом. Есливкачестве		Π( α) выбратьпримитивныйнеприв				одимыймногочленстепени		m над
полем GF(2), тополучимполе		GF(2m) из всех 2m двоичныхпоследовательностейдлины						m.
Вышебылопоказано,что			GF(4) нельзяпредввидеставитьовокупностич					исел 0, 1, 2, 3.
Построимегокакрасширенноеполемод			улюмногочлена		Π(α)α=	2+α +1 .
Втабл. 6	.элементы2 этогополяпредставленыразличнымисп					особами.Здесьпринято,что
примитивныйэлемент	α являетсякорнем		Π( α), т.е . α2+α+1=0.
Таблица6	.2
Последовательность длины2			Многочлен		Степень		Логарифм
00			0		0			–∞
10			1		1			0
01			α		α			1
11			1+α		α2			2
Правсложенияумноженила			явэтомполеприведнижены			.

таблицаумноженумножениятаблица

+	0	1	α	α2	·		0 1		α	α2
0	0	1	α	α2	0		0	0	0	0
1	1	0	α2 α		1		0	1	α	α2
α	α	α2	0	1		α	0	α	α2	1
α2	α2 α		1	0		α2	0	α2	1	α

114

Формирпервстроки,первогованиейстолбцадиагонал						ьныхэлементовтабс оженияицы,а
такжедвухпервыхстрокидвухпервыхстолбцовта				блицыумнвыожениязатрудненияывает.
Пояснимформ		ированиедругихэлементов:
			1+α=α2, 1+α2=α, α+α2=1;
			α·α2=α3= α(1+α)=α+α2=1
наосновесоотношениядляпримитивногоэл				емента α2+α+1=0.
6.2Опреде. циклическогокодаение
Средимногообразиягрупповыхкосдместозанимаютбоецикл							ические(	n,k)			- коды.
Циклическиеодытличаютсяпрост			отойреализации,возмпожностьюстроениякодалюбойдлины
известнымикоррект	ру	ющимисвойствами,раци отношениемнальныммеждуизбыточностью
корректирующейспособнв(этомотношенииблизкистьюграницеХэмми							нга).
ОпределениеЦиклическим1. кодо			мназывают , групповой(			n, k) – к,обладающийследующим
свойством:длюбойякодкомбинвой				ации	V = (a0 , a1 ,		..., an−1 )	эткодаго
комбинацияV ' = (an−1 , a0 , a1 ,			..., an−2 ) , полученнаяциклическимсдвигомэлементов					V	наединицу
впр,тавокже	принадлежитэтко. му
Описанциклосновываетсяидовческихнапредставлениикод мбвыхвиденаций
многочленовотоднойнеизвестнойкоэффициенвидедвоичныхэлем0т1,.е.амиэлементов
поля GF(2). Используятакоепредставление,можно				атьследующее,эквивалентноеприведенному
выше,опредецикличение		ескогокода.
ОпределениеЦиклическим2. (			n, k) – кодомназываетсякод,множествокод мбинацийвых
которогопредставляесовокупномногстепчлтьюяенови					n-1именее,делящихсянанекото						рый
многочлен g(x)степени(		n-k)я, вляющийсясомножителемдвучлена				x n + 1.
Доказательствоэквивалентностиэтихдвухопределенийосновыва							ющеесянапредставлении
циклическодакакидеакольцаклаоговычссов				етовмногпомодулюдвучленов			члена		x	n	.(см.
											+ 1
свойстваи3кольца4).		Групповаяструктурациклич		ескихопределяетсядовтем,что,в						-первых,
операциясложениямногочл		еновсовпадаетоперациейсложениявекторов,во					-вторых,совокупность
многочле,делящихсянанекоов			торыймногочлен	g(x),должнабытьзамкн			утавотношенииоперац и
сложен,т.к.если, каждоеслагаемыхзяналится				g(x),тоихсуммаделитсяна			g(x) истепеньсуммы
нестаршестепсл ней		агаемых,в	-третьих,нулеваякомбинацияпринадцикличежит				ескомукод,				т.к. 0
делитбезоснятатка		g(x).
Струциктуракодлическнебудетраскрытаполностьюго,еслинеучитывать,чтосвойство
цикличностиэквивалензаданиюейсумнтвияно				ожениянадкодовымимбинациямикакнад
многочленанутостиизамкодомвыхбинац			ийпоэтомудействию.Дляобеспечениязамкнутости
											115

кодовыхкомбинацийпределахмножествамногочленовстепени							n-1именееумнкожениедовых
комбинацнеобхпроподимомодулюзводитьйдв					учлена x n		+ 1.Изопредсл2 ,ечтоклениядует
циклическодутносятсямулишьмногочленыстепени						n-1именее,кратныемногочлену			g(x).
Струциктуракодлическогоформируврезультатеследующихпостроенийся.Беск								онечное
множествомногочленовпроизвольныхстепенейпутемвычислостатковотденаления									x n	+ 1
(приведенияпомодулю			x n + 1)раскладываетсянаконеччислмн,облажестводинаковымающих
остатком,называ	емыхклассамивычетов.
Приэтомкаждыйногстепенионулевойчлендо(							n-1)-ойвключпринадлежиттельно
свопределеннемуклассувычетиполнегпредставляетмуостью.Классывычетовпритаком
разлоиграюттужероль,чтониисмежныеклассывразложениигруппыподгруппе.Вданном
случаерольподгруппыиграеткласодержащийвычетов, всемн							огочлены,	кратные x n + 1,т.е.
0, xn +1,	x(xn +1)	ит.д.Общеечислоклассоввычетовравночислуевозможныхмногочленов
степени n-1именее,т.. 2			n.
Разложебескомножестмногочленовиеечнаклассыычетовпо								одулю	x n	+ 1
единсткаждклассвенноычетоднйопределяетсязначмногочленомвлюбым,принадлежащим
даннкласс.Этоотноситсямукпервомуклассувычетов,содержащемуи0								x n + 1,котпорый
отнкостальнымшениюклассавычетовр ссматри					ваетсякакединичныйэлемент,..			xn	+ 1 = 0 .
(Аналогичнотому,какприсложениипом прдулю2 ни2=0)Полноемножествоклассовается.
вычетоврассматриваетсякакмножествовсехкомбин					ацийдлины		n представляющих.Вкачестве
кодомбинвых	ацийрассма		триваюттекласвыче,котсясодержатрыемногочленыв,кратные
g(x),исовокупнвсехмног,краосчленовтныхь					g(x),какбылопок		азановыше,своюочередьобразует
подгруппуидеал()множествавсехкла					ссоввычетовмногпомодулючленов		x n + 1.Следовательно,
классывычетовмногсвоюочмогутленовередьбытьразложенынасмежныеклассыподгруппе,
образующейциклическийкод.Таккакпринадлежит0 этойподгруппе,тоотношениюковсем
смежнымклассамразложенияклассов					вычетовпо	дгруппе,образующкод,справедливой
g(x) ϕ(x) = 0 ,где		ϕ(x)	произвольнмногочленкольцаклассовымногчетовйпомодулючленов
x n + 1. Нетруднопоказать,что				g(x)долженбытьделителем		x n	+ 1.
Действительно,посколькуопределению					g(x) имест,меньшуюпеньт,чем			n,томожно
записатьр	езультатделения		x n	+ 1 на g(x) ввидесл раведующего			нства
					xn +1 = g(x) q(x) + r(x),где
r(x) - остатокотдел				ения,степенькоторогоменьшестепени			g(x),а q(x) - частноеотделения.
Учи, тоывая	xn	+ 1 = 0 ,получаем			g(x) q(x) + r(x) = 0,атаккакмыустановиливыше,что

116

g(x) q(x) = 0 ,тои

r(x) = 0,т.е.

g(x) делит x n + 1 безостатка.Значит,

g(x) – сомножительдвучлена

x n + 1.

Многочлен g(x)принятоназыватьпорождилиобрмногочленомазующимц клического

кода.

Сдругойстороны

циклический(

n, k) – кодможетбытьзаданчерездвойств

енный (n, n-k) – код,

порожденныймног

очленом h(x) = (xn

+1) g(x). Таккак

h(x) g(x) = xn +1 = 0, то h(x)

ортогонален

g(x)иназываетсяпроверочныммногочленом.

Пример6

.3.Дано x7 +1 = (x +1)(x3 + x +1)(x3 + x2 +1).

Найтивсеци

клические(

n, k) – кодыс

n=7,котмобытьрыегутпостроенынаосноведанн

ого

разлож.Опрвсеомножителиделимния

x7 + 1,которыеибудутявлятьсяпорождающими

многочленамииско.Вдмыхзможныесомножителив

x7

+ 1

исоответствующие

мкоды

перечивслетаблиценыдующей.

Сомножитель x7 +1

Код

g1 (x) = x +1

(7,6)

g2 (x) = x3 + x +1

(7,4)

g3 (x) = x3 + x 2 + 1

(7,4)

g 4 (x) = (x +1)(x3 + x +1)

(7,3)

g5 (x) = (x + 1)( x3 + x2

+ 1)

(7,3)

g 6 (x) = (x 3 + x +1)( x 3 + x 2 +1)

(7,1)

Каждыйсомножительдвучлена

x n + 1 можетбытьвыбранкачествепоро

ждающегомногочлена

циклическогокодадлины

n.

Однаконелюбойсомнпорождаетциклическийжитель(

n, k) – кодстребуемыми

корректирующсвойствам.Методикми

авыборапорождающ

егомногдляпостроениячлена

циклическогокодазаданнымикоррект

ирующимисвойстванижебудетрассм. отрена

6.3Пост. порождающейипроверочнойениематрицциклических

одов.

Любойциклический(

n, k) – кодможетбытьзаданвсоответст

виисо

пределением2,

порождающиммногочленом

g(x) илипроверочныммногочл

еном h(x).

Знаниеэтихмногпозволяетпостроитьчленовпорожда

ющуюматрицуп .оверокицу

Дляциклического(

n, k) – кодасущепростойтвует

особнахождения

k линезависимыхйнокодовых

комбинаций,образующихпорождающуюматрицу

G( n,k ) .Этотспособвтоитледующем.

117