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

т.е.

R#T

= R

или R'=

R#T = RT k×(n−k ) .

k×(n−k )

Итак,порождающаяматрица(

n,

k) – кодаявляетсясокрзапщенной

исьюкода.

Проверочнаяматрицауказываетсоотн

ошениемеждуизбыточнымиинформационнымиэлементамив

каждкодоймбинациивой.Междуп

орождающейипроверочнойматрицам

ивканоническойформе

сущежесткаявязьтвует,наосновекоторойзнаниеоднойматрицыпозволяетпостр

оитьдругую.

Пример5

.8. Проиллюстрирувып лнениеотношемний

v H T = 0 и G H T = 0 длякода

(5,Порождающая3).матрица

итранспонированнаяма

трицапроверокимеютвид:

&1

0#

&1 0 1 0 0#

0 1!

G(5, 3) =

1

1

0

1

0!

H (T5, 3)

!

= 1

0!

!

1 1!

0 1 0 0 1!

%

!

!

%0

1

Вычисляемихпроизведение:

&1

0#

&1 0 1 0 0#

0 1!

G

H T = 1 1 0 1 0!

0

!

= S

i j ]

×

!

!

1

!

[

1

0

0

1

0

1!

1

!

%

!

%0

1

Здесьэлементыматрицы	Sij размерности(3х2)вычисляследующимтся		бразом:
S11	=1.1+ 0.0 +1.1+ 0.1+ 0.0 = 0;	S12	=1.0 + 0.1+1.0 + 0.1+ 0.1 = 0;
S21	=1.1+1.0 + 0.1+1.1+ 0.0 = 0;	S 22	=1.0 +1.1+ 0.0 +1.1+ 0.1 = 0;
S31	= 0.1+1.0 + 0.1+ 0.1+1.0 = 0;	S12	= 0.0 +1.1+ 0.0 + 0.1+1.1 = 0.

Такимобр азом:

			&0	0#
G(5, 3) H	T			!
	(5, 3)	=	0	0!
			0	0!
			%

Пустьнаприемнуюстанциюсистемыпередачиданныхпост		упилакомбинация(1 1 1 1 1).
Какимобразомможноустафактналовошичиять		ибоквкомбинации?
Во-первых,проверитьсоответствиеинформационныхпров		ерочныхэлементов
соответствииправиломихформ р	ования:
a1 = a3 + a4 или	a1 + a3 + a4 = 0 и	a2 = a4 + a5 или a2 + a4 + a5 = 0 .
Дляприняткомбинациилучаемй

a1 + a3 + a4 = 1+1+1 = 1 ≠ 0

a2 + a4 + a5 = 1+1+1 = 1 ≠ 0.

78

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

ошибки.

Этотжесамыйпроцессвыявленсоответствприкомбняткоду(5,иформализуетсяйнации3)

вычислением:

																	1	0
																	%0	1
									V H T			1	1		1 1 1		%			1	1	00.
																	%
										(5, 3)		= [				]	1 0			= [	]≠
																	%
																	%1	1
																	%
																	&0	1#
	Проверочсоотданеошнулевойтсиое ие																	дром,указ			ывающийналичиеошибок
принятойкомбинации.
	Длярассматриваемогокода(5, 3):
								&1 0 1 0 0#								&1 0#						&1 1	0#
						G(5, 3)				1 0		1	!	,	R3×2 =			!			T
								= 1					0!			1		1! ,			R3×2	=	! .
								0 1 0 0 1!								0 1!						%0 1 1
								%								%
	Используясвойство5									.4получаем. :
H	& 1				0	1	1	0	#	,
	(5, 3) =		0		1	0	1	1	!
	%
		I 2
								RT	3×2
чтоп лностьюсовпа							даетсматрицей,по						лученнойвпримере5								.7.

79

5.2Задачи.5.

1Определить. минимкодоасстльнвкодеое, яниестоящемизсл

едующихкодовых

комбинаций: 000, 001, 110, 111.

2Построить. (3, 2)

– кодс

dmin=2.

3Можно. липостроитьгрупповойкоддлины

n=3с

dmin=3?Еслида,ток

акойэто? д

4.Заданапроверочнматриц(7, 4)ая

– кода:

&0

0

0

1

1

1

1#

H (7, 4)

=

0 1 1 0 0 1 1!

0

1

0

1

0

!

1

1!

%

Постпороматрицуитьждающуюдляэтогокода.

5Провер. ,принадлежиткомбинациять1 0коду1(7,пред04)1 0 1

ыдущейзадачи.

6Для.к

о,двойственногоакоду(5,3),написатьорождающуюпроверо

чнуюматрицыв

каноническойформе.

80

5.3.ДРУГИЕ

СВОЙСТВА ГРУППОВЫХ КОДОВ

5.3.1Корректирующиесвойствагрупповыхкодов

Эффективнопомех даупределяетсястминимальнымойчивогокод

овымрасстоя

нием.

Вышебылопоказано,что

dmin (n,k)-кода равном

инимальнвесуненулеввыхкодмуомбинаций.

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

dmin кода,невесовходявсехкодомбинвых

аций.Длягрупповых

кодовсуществуетспособопределения

dmin повидуматпроверицы

ок H(n, k ) .Этотспособосн

овывается

насоотн ошении V H (Tn, k ) = 0.

Пусть V - кодкомбваяс инвесомимальнымация.

Умножениек

одовойкомбинации

V наматрицу

H(Tn, k ) можнопредставитькакпоразрядноесложение

столбцовматрицы

H ( n, k ) ,которымсоответствуютединицыкомб

инации v.

Результатумндодатьлженянулевойси.ндромТаккакник

акаядругаякомбисменьшациям

числомединедаетницулевогосиндр

ома,то,следователь,код мбивойноации

минимвесального

соответствуетминимальноечислолинейнозависимыхст матлбцпров.ицыТерок

акимобразом,

можносформулопределенияватьправило

dmin групповогокода.

Теорема5

.1.

Групповойкодимеетминивесм(инимальныйкодовоер льное

сстояние)

,равное

минимальномучислулинейнозависимыхстол

бцовматрицыпроверок

H ( n, k ) .

Пример5.9

.Код(5,имеет3)

dmin =2,таккаквегос входятставкомб

инац(10и(01и100)

001)Расс.умноженримэткомбихнаиаенаций

трицу H(T5, 3) :

−1

0

+0

1(

&1#

&0#

&1#

&1#

&

0# &

1# &

1# &0#

+

(

(1 0 1 0 0) +1 0(

=1 !

+ 0 !

+1 ! + 0

!

+ 0 ! = ! + ! = !

+

(

!

!

!

!

! ! ! !

%0

%1

%0

%1

%

1 %

0 %

0 %0

+1

1(

+

(

,0

1)

Тоестькомбинации(1010

0)соответствуетлинейнаязавис

имость1

-гои3

-гостолбцов

H(5, 3) .

Аналогичноп

роверяется,чток мбинации(01

001)соотве

тствуетлинейнаязависимость2

-гои 5 -го

столбцов.

81

5.3.2Процекоддекодировурырованиягрупповогоание

А.Процедуракодирования

1Процедура. кодированиянаосновепорождающейматрицы

Пустьтребуетсяполучитькод мбинациювую(

n,k)-кода Vi,соответству ющуюнекоторому

сообщениюисточникаинформации,предст

авленному

идебе

зызбыточной

k-элементной

последовательности ki. Какбылопокавыше,этазарешаетсянодачасоставлениемлинейной

комбинациистрокпоро

ждающейматрицы:

Vi=ki1V1+ki2V2+…+ kikVk, где Vj, j=1…k,-кодомбинациивые(

n,k)-кода,я

вляющиесястр

оками

каноническойформыпорождающейматрицыэтогокода,

ki,j-

элементыкодируемой

k- элементной

последовательности.

Указаннаялинейнаякомбинациясоответствуетумнпоследователжению

ьности

ki на

порождающуюматрицукода,представленнуюканоническойформ

е:

ki ×G (n,k)=ki× [RIk]=(kiR,ki )

Врезультатеумнпожлучнимя

n-элементнуюкодомбинациюву

Vi,ук оторойнаместах

избыточныхэлементов

(v1,v2,…vn-k) нахпоследователдятся

ьность ri=kiR,анаместахинформационных

элементов- (vn-k+1,…,vn )- исходная кодируемаяпоследовательность

ki.

2. Процедуракодированиянаосновепроверочнойматрицы

.

Вэтомслучаепроцедурако

дированияоснована

наизвестномуравнении.

Vi×HT(n,r)=0.

Представим Vi ввиде

(ri,ki),где ri - последоваизбыточныхэлемеельность

нтовко

довой

комбинации,

ki - последоватинформационныхэлемельность

нтов.Представляя

HT(n,k) вканонической

форме,получаем:

(ri,ki)×[

In-kRT ]T=ri+kiR=0, откуда ri=kiR..

Изполученрешевидно,чтизбыточныеиягоэлементывточностисо

впадаютс

избыточнымиэлементамиприкодированиинаоснове

G(n,k)

Втехслучаях,когда

(n-k)<k или k ⁄ n >

1⁄2,кодированиенаосновепроверо

чнойматрицы

H(n,k)

требуетменьшегоколичествавычислений.

Б.Процедурадекодирования

Пусть

V0 , V1 , …, V2k −1 -

кодомбинавые

циинекоторогогруппового

ода,где

V0

-

нулевая

комбинац,тоестьединэлементигруппычныйя.Пр

оцедурадекодированиядляэтогокодамбытьжет

вырнаосновеботанасл

едующихпостроений.Строитсятаблицадекодированиятаблица

разложениягру

ппывсевозможных

n – элементныхдвоичкомбинацийсме

жныеклассы

по

подгруппе,составляющданныйкод.Образующиесмежныхклассовй

ыбираютсятакимобразом,

чтобывихсоставвошливсенаибовероятныедиспользуемогоее каналасвязиоб

разцыошибокв

82

кодовой мбинации.Длябольшейчастиреальныхканаловсвязикачестве

бразующихсмежных

классовследуетвыбиратькомбс инвесомимациид сменномльным

жномклассе.

Выпишемвкач строкиствервойтаблицывсекодовые

мби,начции

иснулевойая.

Вкачествеобразующихсмежныхкла

ссоввозьмем

2n−k

−1 наибвероятныхлеебразцовошибокдля

используемогоканала(

ei).

V0 ,

V1 ,

V2 ,

...,

V2k −1

!

e ,

e +V ,

e +V

2

,

...,

e +V

k

−1

!

1

1

1

1

1

2

2n-k

строк

!

−

−

−

−

−

!

e

e

,

e

#

e

,

i

+V ,

i

+V

2

...,

i

+V

k

−1

!

i

1

2

!

−

−

−

−

−

!

,

e

+V1 ,

e

+V2 ,

e

+V

!e

n −k

−1

n −k

−1

n −k

−1

n −k

−1

k

−1

2

2

2

2

2

2k столбцов

Каждыйизстолтабдекодированиялицыцовявляетсязащи

тнойзондлякодовой

комбинации,стоящейвоглавестолбца.

Решеноналичииошибвкодеокмбинациивойихструктурепр

оизводитсяповиду

синдрома

Si = Vi H(Tn,k ) .

Покажем,чтокаждомуобразцуисправляемойошибкисоотве

тствуетвполне

определенныйсиндром.

Есинли

дромчиснулевой,тсчи,чтоошибкиаетсявкод вой

мбинации

отсутствуют,хоэиневсегдаяверно,таккомбинациямс

еобнаруженнымиошибкамитакже

соответствуетнулевойсиндром.

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

бкой,тоесть

Vi

= Vi

+ ei ,

где ei - образецошибки,являющейсяобразующимсмежногокласса.

Вэтомслучаесиндромпринимаетвид:

S

i

= V

# H T

= (V + e

) H T

= V H T

+ e

i

H T

= e

i

H T

≠ 0 ,

i

(n, k )

i

i

(n, k )

i (n, k )

(n, k )

(n, k )

тоестьдлякаждогообразцаиспрошибв,чтлтояемыхсжек

амое,

длякаждогосмежногоклассасуществуетсвойси

ндром.

Переданнаякомбинация

Vi будетдекоди,вернпо оинвана

ятойкомбинации

Vi ! тогда

итолькотогда,когдавекторошибки

ei

= Vi

+Vi ! являетсяобразующим

смежногокласса,которому

принадлежит Vi ! .

83

	Процессдекодирприиспотаблльзованиидекодированияцыдляисправления
ошибокзаключаетсявследующем:
	1Для.принятойкомбинациивычсиндсляетсяопредом			еляетсясмежныйкласс,
которомупринадлежпринятаякомбинация. т
	2Определяется. образующийсмежногокласса,которомупр			инадлежитприня ая
комбинация,являющийсяпредполагаемойоши			бкой.
	3Сумми. помодулюп2руяедпобразецлагаемыйши		бкиспринятойкомбинацией,
получаемпередан	нуюкомбинацию.
Такимобразом,приисправленииошибкодокмбинациивойук			азаннымметодомколичество
исправляемыхошибокнеможетпревышачисласмежныхклассов,тестьчисла				2n−k −1,ив
точностиравноэтчиму		слувтехслучаях,когд	авкаждомсмежномклассеимеединственнаяя
комбинация,соответствующаянаиболеевер			оятнойструктуреошибок
Коды,которыеисправляютвсошибкикратностидо			t включительноинеисправляютникаких
ошибокбольшейкратности,называютсясоверше			нными.
Прио бнаруженииошибокпроцедурадекодированияупрощ			ает.Евычисленныйялисиндром	S ≠ 0 ,то
выдаетсясигналоши“		бка”илистирание” ”.
	Приэтомсавидсинимеетдромазначения,..всме		жныеклассыобъединяютсяв
общуюзащитнуюзону.Пр		ичастичномисправленииобн	аруженииошибокзадаетсякра	тностьшибок
t!,докоторойосуществляиспра,ошибкысшихленкратнтсяе			остейолькообнаруживаются,
			t
поэтомувтаблицедекодирования		ыделяется ∑Cni образцовошибок,подлежащихисправлению.Все
			i=1
		t
жеостальные	2n−k	− ∑Cni смежныхклассовобъединяобщузащитнуюзону.Есиндромсяли,
		i=1
соответствующийпринятойкомб		инациипринадлежзащитнойобщейзоне,тоф ксируется
обнаружениеошибки		– “стиран ие”.
	Есиндромлипринадсмежномуклежитасупра		вляемымобразошибки,т м
происходэтоисправлениеоши,какбылокиписановыше.

84

Пример5.10	. Рассмотримтаблицудекодированиядля(5, 3)		– кода,и	спользуемогов

предыдущихпримера.

) ошибоксмежных ссов (образцы

		(5, код3)подгруппа()
00000	10100	11010	01001	01110	11101	10011	00111
0 10101		11011	01000	01111	11100	10010	00110
0001
0 10110		11000	01011	01100	11111	10001	00101
0010

0 10000	11110	01101		01010	11001	10111	00011
0100
Изанализатаблицыдекодированияможносделать						едующиевыводы:
1. Синдромыимеютзначения
					&1	0#
					0	1!
						!
		S1	= (0 0 0 0 1) 1 0! = 0 1,
						!
					1	1!
						!
					%0	1
					&1	0#
					0	1!
						!
		S 2	= (0 0 0 1 0) 1 0! = 1 1,
						!
					1	1!
						!
					%0	1
					&1	0#
					0	1!
						!
		S3	= (0 0 1 0 0) 1 0! = 1 0,
						!
					1	1!
						!
					%0	1
т.е.всиндромыеразныевид	синодрнуказывомазначносмежныйкласс. ет
2Код.исправляетневсеобразцыодиночныхошибок.Например,ко						мбинации		0 0и0010010 0,
такжекаки0 и011принадлежато00000 0				дносмежномуклассу,следовательно,обепарыэтих
образцовошинемогутбытьокисправлены.Это,такнятнокак							dmin этогокодаравно2,для
исправлениявсехвариантовод	иночошибокнеобходимоыхиметь					dmin =3.

85

	Действитель,мынаходимсмежклассеобразуном						ющим0 еще0одну0 0 1
комбинациювеса1	– 0 1 0 т.е0.си0,				ндрому S1	= соот0 1дваретствуетвновероятныхобразца
однократныхош;сибокндрому				S2 =также1соответствуют0 дваобравновероятныхзцаоднократных
ошибок.Тольколишьси		ндрому S3 =соответствуетединственный1 1 образецодношкратной						ибки0 0 0
1 0.
	Такимобраз,однозначноисправляютсямтольколишькомбинации,принадлежащие
одномусмежн	омуклассу,т.е.ошви0бкада0 0 1				0даннымкодомисправляется.
5.3.3Укорочениекода
Наосновегруппового(				n, k) – кодаможнопостроитьтакжегрупп			овой(	n- i, k-i) – код,еслив
каждкодоймбинациивой(				n, k) – кодаисключить		i информацсионных.мволов
	Порождающаяматрица(			n- i, k-i) – кодаполучаетсяизканоническойформыматрицы				G(n, k)
вычеркиванием i последнихтрок				i	последнихтол	бцов.Пр	оверочнаяматрица(	n- i, k-i) – кода
получаетсяизканоническойфо				рмы Н(n,k) вычеркиванием i последнихтолбцов.Посколькуприэтом
числолинейнозависимыхст матлбцпровумеицынерокможетьши,то ься								dmin новокодаиего
корректирующиесвойстван			ехуже,чемисхо		дногокода.
	Коды,постакимроенобразом,принятоыеазывать						укороченнымикодами.
	Пример5.11		.Изизвестногокода(5,получить3)код(4, 2).

&1

G(5, 3) = 1

0

%

Вычеркиваемизматрицы столбец.Врезультатеполучаматрицупорожд ющую

0	1	0	0#		&1	0	1	1	0#
1	0	1	!	H
			0!,		(5, 3) =	1	1	1	!
0	0	0	1!		%0				1
G(5,3) третьюстрокуипястолбецый,аизма									трицы Н(5,3) пятый

трицупровероккода(4, 2):

&1	0	1	0#	H	&1	0	1	1#
G(4, 2) =	1	0	!,		(4, 2) =	1	0	! .
%1			1		%0			1

Минчилимальслонезависимыхйностоемалбцов			трицы Н(4,2) по-прежнемуравно2.
Следовательно,и	dmin этогок	одаравно2.
5.3.4Оценкаэффективностигрупповыхкодов
Вкачествеоценкипомехозащищенностик даустойчивого				спользуетсявероятность
ошибочногоприемакод мбинациивой.Длярасч			етаэтойвероятностидолжныбытьизвестны
следующиехарактер	истикикодаскретног		ок анала:
bni ( j) - функцияошибок,принимающаязначения01ук			азывающая
выявляетсяилиневыявляетсяданнымкодомконкре			тный j–тыйобразец	i-кратнойошибки;	j
призначенияимчистлт		уральнряотдо1аго	Cni ; i изменяетсяотдо1	n.
					86

Pn( j ) (i) - вероятностьпоявления				j-гообразца			i-кратнойошибкивди		скретном канале;
определяетсялибоврезультатестат				истическихиспытан,либовычисаналитй,есляетсяически
известенх	арактерраспределенияошиб			окиматематическийзаконихоп					исания.
	Вероятношибприемакодстьчногомбинациивойможетбыть								пределенакак
				Pош = ∑∑bni ( j)Pn( j ) (i).
				i	j
Это – точнаяформула.Однако,вбольшинствепрактислурасчетыподаннойвеских
формулезатруднительны.Вслух				чаях,когдаможносчитатьв				ероятностипоявленияразличных
образцовошибоккратности		i достатблизкимипзначениюочно,т..
			P(1)	(i) = P(2) (i) = ... = P( j ) (i) = ... = P(Cni ) (i)
			n	n	n				n
приведеннаявышеформулаупрощаетсяпринимаетвид
					i P(i, n)
				Pош = ∑ Bn				,
							i
					i		Cn
где Bni		- числовариантов	, невыявляекодоошибоккратностимых						i.Оч евидно,что
				Bni = ∑bni ( j).
					j

P(i, n)-вероятностьпоявлениядискретномканалеошибкикра

Еслиизвестно,чтоданныйпомехкгаодустойчивый

обнаруживаетзависимостиотрежимаиспользованияк
пределысумможноирут вания	чнить

Bi

Отношение n можнорассма

Cni

общегочиславозможныхшибокэтойкра

Прииспользованпроцессадекоди,опиврасиованиязделеннф3.2,рмулаго уточняетсявсоответствиииспользуемымрежимомкода.Рассмо использованиякода.

Однимизвозрежимовожныхявляетсяисправлениеошибок.

Ложноеотождествлепринятойкомбиоднойразрешеиеации случае,когдавкомбинацииестоошибкает,кратнкотпревышаетостьройкратносгарантьийн исправляемыхошибкотораяневошлачислообразующихсме

тности i.

P(i, n) = ∑ Pnj (i).

	j
		рантийновыявл	яет (исправляетили
		ода)всеошибкикратности	δ именее,то
n	i
	Bn
Pош = ∑		P(i, n).
	i
i=δ +1	Cn
триватькакдолюневыявляемыхошибо			к кратности i	от
тности.
		тримвозможныережим		ы

нныхпроисходитвтом

о

жныхклассов.

87