Лaткoв A., Бapaнoвa Е., Гapтель И. Teopия инфopмaции: Mетодические

Подождите немного. Документ загружается.

? l.]t

T RА

R,1'A

U N SАКz{J*] t,

/Ns

iГf

Тs

',J1

*#'f'

--ё

A. ЛATКOB,

Е. БAPAHOBA,

И. ГAPТЕЛЬ

тЕoPия

иHФoPMAции

MeтoдинeскИе

yкaзaHИя

пo

BЬlпoлHеHиЮ ЛaoopатopHЬIХ

pa6oT

l.;i}Ф

.r-^\*

*].

j}&.Ф

.&t.э

&e'!E,e

l,l.

.aJ

'Ф

.Ф,

ri*

E'i9&.e.)

r*-

ф*.*

1оя*J

ч.r:'i

33:i;'

,*E* \

,-i {t

, la:

::,'ll )

TRANSPoRтA UN SAKARU

|NsтIтUТs

lЗ-J

Лaткoв,

Е. Бapaнoыa, 14. Гapтель

тЕoPиЯ иHФoPMAЦии

Meтoдичeскиe

yкaзaния

пo

выпoлнeнию

лaбopатopныx

paбoт

Ригa

2Ф5

519

Л27з

Тransporta

un sakaru

institЕts

Инсгицrг

тpaнспopтa

Lт

cBЯЗу|

Лaткoв

A., Бapaнoзa

Е., Гapтнrь

И.

J|273

Teopuя

инфopмaции:

MgгодичесIсие yка:raни,I

пo вьIIloJIнrниlo

лaбopaтopньш

paбoт.

Pигa:

Инсгrгщ

тpaнспopтa

и cвязvl,2Ф5.48

Мeтoдинеские yкaз'rrия'пpеднaзнa.rены

стyдентaм

фaкyльтeгa

''Кoмпьtoтеp-

нЬIе

нayки

и эЛектpol{икa''

дlIя

вьIIIoлнeниJI

ими лaбopaтopньlx

paбoт

пo

дисциIIJIине

i.Tеopия

инфoрмauии''.

B кaхсдoй

лaбopaтopнoй paбoте

дa.пIJ

ocнoвIlЬIе

тeopетичeские

IIoлo)кеI{ия

и контpoльIlъtе

BoпрoсьI'

спoсoбствyloщие

зaкPeплеI{иIо

тroprти.tескoгo

мaтеpи€}лa.

.{aнньlе

yкaзarrия

мoryт

бьrть пoJIезI{ЬI

к.lк

стyдентaм,

тaк

спеЦиtlлистaм,

'i(елaloщиМ

о.lмoстoЯтrльI{o

изrIитЬ

pElздеЛьI

yкtlз.ll{нoгo

кypсa.

@ Л.aткoв

A., Бapaнoвa

Е., Гapгель

И.,2oo5

@ Тranspoги

un sakaru institiits,

2005

,-/

BвЕдEHиE

fiиcциллwнa

..Tеopия

Инфopмarии,' пoсвященa oзнaкoмлeниIo с oсtloв€lми

теopии инфopмaции, кoдиpoвaния и

декoдиpoBaния

инфopмaции' с c|4ГНaлaNlИ

рteтoдaМи их

oбpaбoтки,

пpеoбpaзoвaтеJulМи' Кypс лaбopaтoрньж

paбoт,

пPeдлla-

гaеМЬIх в

Дaннoй

paбoтe,

нaпpaвлeн нaтo, vтoбьI пoзнaкoмить

стyдентoв

с:

пpaктиЧескиMи нaвЬIкaми IIo сиIrтезy кaк линеЙньlх'

тaк и

цикJII,tческиx

[n,

t].кoдoв;

сo спrlсгpaми сигl{аJIoв

и кpитrpияМи вьIбopa пoлoсьI

щoпyскaния

кaEaJIa;

с пpеoбpaзoвaтеляl\{и нaтIряrl(rнI,tя B кoд.

Кaждaя лaбopaтopнaя

paбoтa

сoдер)кит кpaткий тeopетический

мaтepиaп,

кoтopьtй мo}I(ет

бьшь

полезен пpи вьIIIoлI{ении

дaннoй

paбoтьr,

пopяДoк

вьIпoл-

нения

сaмoй

paбoтьI

и oIlисaниe eе

peзyлЬтaтoB'

ссЬIлI(и

нa литеparypy,

списoк

вoпpoсoв

.ц,IIя

сaМoпpoBеpки.

Пеpед вьlпoлt{ениrlt,t лaбopaтopнoй

paбoтьI

неoбxo.цимo

изyчитЬ сooтветстBy-

roЩий тeopeгинeский мaтеpиttJl и пpoсчитaтЬ

BapиaЕт

пoJryченtloгo зapaнее ЗaДaн.ИЯ.

Зaтем вьlпoлнить

лaбopaтopнyю

paбory

сoглaснo

yкaзaннoмy

пoрядкy.

Пpoгpaммньtе мo.ryли

дJIя

тpex пеpвЬIx лaбopaтopньtx

paбoт

t{;lхo.цятся

Intranеt'е.

Haдo зaйти B IntгaneL B

paздeJl

пoовященньIй изyчarМoN{y

кypcy

(Tеopия

инфopмauии).

B пaпке с лaбopaтopньtми

paбoтaми

вьIбpaть неoбхoдимyю

длтя

BЬIпoлtlеt|иЯ.

Lаboгаtоrijas

dафi

Лабopaтоpньle

pаботьt

лабoратoрная

paбoта

"иЕслeAованиe

cпeктpа пepиoдинeскoгo сигнала.

пoPяAoк вь|пфнения ла6oрэrcрнoй

pа6oтьl

(прoзePкв

reoР.тяqtrих

Рэflеrcв

еoеro вэрианта oгналв)

лабoратopная

pабoта

пo линeйным кщам

пoр4ок 3ьlпФнени'

ла6oрmрнoй

pа6oтьt

ла6oратoрt{ая

pа6oта

пo

цикличeскиM

кoдёt'4

пoр'дoк вьlпфнени'.ла6оpатoрнoй

pа6oъr (пракwе*вa

пpoвеPкв тeoРеmeскorc

раёeтa

Фoеro

варивнтв

зцания)

Мeтoдиceскиe

yказaния

пo выпoлнeнию ла6opатopнoй

ра6oтьt

.Линейныe

кoды.

Лабoрarcpнш

paбoта

пo

щeобpвoвавям

(нaпpяreш

в кoл)

Пo

кaя<дoй лaбopaтopнoй

paбoте

oфopмляется oтнег.

oтчsг

дoлlкен

сo.цеp)I(aтЬ:

тrryльньIй лиcт с

yк€lзaнием

tI.}:lBaEия }lЗyчaeмoгo IIpедl\{ет4 темьl

лaбopa.

тopнoй

paбoтьI,

имеttи испoлtIIrгеJUI' нoMерa гpyппЬl, имеIrи прoBrpяIощегo;

темy лaбopaтopнoй

paбoтьI;

целЬ

лaбop€rтopнoй

paбoтьI;

зaдaние

нa лaбopaтopнyю

paбoтy

(иtцивилyaльньIй

BapиaЕт);

Пoсле oфopмлeниJl oтчетa лaбopaтоpнyю

paбoтy

l{еoбхoдимo

зaщитить.

,_-1

лAБOPAтOPHAя

PAБOтA

Ns 1

..ЛинeйнЬle

кoдЬl''

1.1.

ЦЕЛЬ

сOДЕРI(AIIиЕ

PAБOTьI

[елью

paбoтьl

является

зaкpеплеI{иe

знaниЙ пo теopии

пoмехoyстoй.rивoгo

кoдиpoвaния

нa пpиМepe

пoстpoeниJt

линeйнoгo

кoдa.

пpoцeсое

paбoтьt

стy.цеIrтЬI

вьIпoлняrот

пoстpoениe

линeйнoгo

кoдa'

зaдarr-

tloгo

IIpепoдaBaтеЛем,

и нa

пpaKгике

пpoBrpяIoт

пpilвиJlьtloсти

paсчетa

исслeryЮт

вoзмoжнoсти

кoдa.

|.2.

TEOPЕTиЧЕскAяЧACТЬ

l'.2.1.

OснoвнЬlr

пoнятия

oпpеДелerrия

Пpoсгьle

кoдЬI xapaктepизyloтся

тrм' чтo

BЛЯ

лepeДaчI4 инфopмauии

испoJIь-

зyются

вce

кoдoвьIе

слoвa

(кoмбинaции),

кoлI.Iчествo кoтopЬIх

paьнo

N=qo

ocнoBaниe

кoДa,

a n

Длинa

кoдa).

B oбщeм

сJryчae

olrи мoгyт oтлиЧaтЬся

Дpyг

oт

,цpyгa

o.цним

cимBoJloм.

Пoэтoмy.ц€Dке

oдиI{

oшибoчнo пpинliтьrй

оиNrBoЛ

пpивoдиТ

зaмrtiе

oднoгo

кoдoвoгo

слoвa

дpyги[,r

и,

cледoвaтeлЬнo,

к нeпpaBилЬнoN{y

пpиеN{y

сooбщеяия

цeлoM.

IroмаоуclttoЙчaвылrш

н€}зьIвaIoтся

кodьt, пoзвoляющиr

oбнapy-

я(ивaть

и,

(или)

испpaвJutть

otцибки

B кoдoвьlх

слoвaх, кoтopьIe

вoзlrикaloт

пpи

пepе.цaЧе

пo кaн€UIaм

связи.

Эти

кoдЬI стpoятся

тaкиМ oбpaзoм,

чтo

.ILIIя

пepе.цaчи

сooбщения

испoЛЬзyется

лиIIIь чaстЬ

кo.цoвьrх

слoв,

кoтopЬIe oтличalотся

дpyг

oт

дpyгa

бoлee

чеМ в

o.цнol\,{ симвoле.

Эти кoдoвьIе

слoBa

I{€lзЬIвaются

paзpеIIIeннЬIMи.

Bсе

oqгальньlr

кoдoвьIе

слoвa I{r

испoльзyroтся

oтнoсятсЯ к Числy

зaпрещeнI{ьIx.

Пpименeние

пoмeхoyстoйчивьIх

кoДoв

для

пoвьIцIени,I Brpl{oсти

пеprдaчи

.цaннЬlх

овязaннo

pеIIIeниrМ

зaдaч кo.циpoBaНИя

декoдиpoвaниJl.

Пpoстейurей

praлизaцией

кoppектиpyющиx

кoдoв явлЯtoтся

элeMеIlтapнЬlr

koдЬI'

пpивe,цеtlньIе

щи.пolкении

Зaдaчa кo.цирoBaIIия

зaKiIIoчaется

в пoщ/tIеI{ии

при пеprдaче

дпя

кaждoй

элементнoй

кoмбинaции

из МIloл(eствa

сooтветсгвyloщeгo

ей

кoДoвoгo

слoвa

длинoю

из мнoжествa qn.

Зaдaчa

дeкoДиpoвaния

сoстoит B

пoJryчении

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

кoмбинaции

из

IIpиI{'tтoгo

tl-ptвpядI{oгo

кoдoвoгo

слoвa пpи

oДI{oвpемrЕЦoм

oбнapyясе||Lьv|

|4JI'1

испpaвлеt{ии

oцrибoк.

Кoд, в кoтopoМ

к:Dкдoе

кoдoвoe слoвo нaчинaeтся

c инфo-

pмaциoнньIx

симBoлoв

и зaкal{чивaется

пpoвеpoчI{ьIми

симвoлaMи'

IlaзЬrвaется

cucmемаmaчecкuJ'|,

Bec

кodoвozo

c].oвa

кoличестBo

eгo нeHyлeBЬIx

кoмпoнeнтoв

(al).

Beкmop

otцшбoк

pезyЛьтaт

слo)t(еI{иJI

вxo.цI{oгo и вЬIхoднoгo

кoдoвьIx

олoв

пo

mod2 пpи

пеpедaче IIo

кaнalry.

Общee чuano кodoвых

кolпбuнацuй

для .цBoичнoгo

кoдa

No=2n,

a чuano

pаapеu|еI'IIь'х

кoloвых

кolибuнацuЙ

N=2*, т0гДa

числo зaпpeщенI{ьrх

кoдoвьIx

кoмбинaций:

l/"_N.

oпpeдeлениr:

пoдмнo)l(еcтвo

вelсгopoв

paзpядIroсти

n, кoтopoе

явЛЯется

пoд.

пpoотpaнствoМ

вeктoptloгo

пpoстрaнствa

всех

пoсле,цoвaтельнoстeй

(кoдoвьrх

слoв)

дпинoй

n, н,aзЬtл,aсrtcЯ

лaнейныла кodoлl.

Mнoхсeотвo У

нaзьtвasтся ве't|''opны]I| npocmpанс,t'вoм IIaД пoлем

F, eсли

.цJIя

нeгo вЬl пoЛ

шrются слe.щ/Ioщиe aксиoM ЬI :

Aксиoмa L, V

aДл.prтuBII.ш aбeлeвa грyппa.

Aксиомa 2.

(зaмкнyтoсгь

oтtloсltтельнo

yМнolt(eния

нa скаляp)

Для

лroбoгo

вeктopa

(элементa)

vе V

любoгo элемrнтa пoля с oпредeлel{o

прoизвe.цеItие с v' являIoщееся

вrктopoм.

Aксиoмa

(aссoциaтивньtй

зaкoн). Еcлlц v е V, a c и d

скаляpьI, тo

с(dv)=(cфv

И Iv=v.

Aксиoмa 4.

(пеpвый

дистpибщивный

зaкoн).

.{ля

любьtx

двyx

элеl{еIlтoв

u, v е V И Лto6oгo

элrмrflтa

(с)

вьIпoлняетcя cooтнoltlеIlие

с(u+ v)=

11+ с v.

Aксиoмa 5.

(втopoй

дистpибyтивньlй

зaкoн).

,{ля

лroбoгo

элeмeнтa vе V,

лIoбЬrх

дByx

элеМelrтoв c, dс, Е спpaведlивo

p€lвенcтвo

Гpуnno

ilG нaзьIвaeтоя

"o"o*,n*o"'lТ

?;;

"::

::кoтopЬгх

oпpe.целеIla

нe-

кoтopaя

6инapнaя

oпrpaция и BьIIIoЛIIяtoтся

слеДyющие aксиoмьI:

Aксиoмa 1.

(зaмкнщoсгь)

oпepaция мo}I(ет бьrгь пpимeненa

лroбьrм

двyм

эЛеМеIIтaМ сoвoкyпlloсти' взятьIМ B

oпpeделеннolvl пopя.цкe'

pезyлЬтaтe

чeгo пoJryчaется

элeМент, пpинa.ryIе)кaщий

этoй ясe

сoвoкyпIloсти

vуv2€ G., v1Фv2€ G.

Aксиoмa

(accoЦиaтиъньiй

зaкoн)

,lIдя

тpeх элeментoB а, b lа c

оoвoкyпI{o-

сти пpиI\,tеHимo

сooтнoцIeниe

а+

(b+

c)=(а+ b)

rсли oпеpaция

Зzlписaнa

"}if,

i,"![}xf ;'^"

eсли

oпеpaци,r зaIIисаI{a кaк

yNtнoжеI{ие.

Aксиoма

3. Cyшeствylот

е.циничньIе элeмeнтьI,

oбoзнaчaeмьle B сJr}дiaе

)l(eния кaк 0, в

сrryчaе

yМнox(eниJl

кaк l и

oIIpeделяeмьIе

oтнoшrнием

a+а=а+0=а,

|а=а|=а,

гдr

лtoбotrl элrМeнт сoвoкyпI{oсти' вKпючtUI

и едининньIй.

AксЙoмa 4. Кaждьtй

элемеltт

сoвoкyllнoсти oблaдagг oбpaтньtм

элеilrеI{тoм

аа-L

Кo.ц

имеeт

фoрмaт,

изoбpокенньIй нa

pис.

1.1, тo

еgгь

сoдepжит

tlеизМеIltlyЮ

uнфopпацuoнt'уIo

чаctt'ь

длинoй

t симвoлoв и uзбыmoчн'тo

(npoвepouнуto)

длинoй

симвoлoв.

_,,

--\a

Puс'

1.1. Пpеdcmавлeнuе

фop'маmа

кodа

Лtoбoй

нaбop

бaзионьrх

вектopoB

линейнoгo

кoдa Имoхснo paосмaТpивaть

кaк

стpoки

п4aтpицЬI

назьtвaeмoЙ

oбpазуloщеЙ

,uаmpaцей

кoДa

(в

некoтoрьIх

истoчникaх

- пopoж.цЕlloщей).

ПpoстpaнстBo

cтpoк

мaтpицЬI

является

линейньlм

кoдoм

И. Pазличньte

линейньlе

кoмбинaции

стpoк

Мaтpицьl

дaют

p€lзличньrr

кoдoBьtе

вектoрЬl.

Bсeгo

пoдпpoстpal{сTвo

УсoДеpлсит

2t векгopoв.

Тaкoй

кoд

нaзьь

вaeтcя

fn,k}.кodoлl.

Bектop

яBляrтся

кo.цoвЬlМ

Bектopoм

тoгдa

тoЛькo

тoгДa'

кoгдa

oI{ яBЛяется

линейнoй

кoмбинaцией

стpoк

мaтpицьl

G. Если

paЗМrplroстЬ

вектopнoГo

пpoотpaнствa

Vpaвнa&,

тo числo

cтpок

мaтpицьl

paвнo

oбlaзyЮщaя

Мaтpицa

пpиведенo-стyпerrчaтoй

фopмe

имеег

следyющий

видG=[IoP]:

100htpn

0IoPлPzz

0 0

l ...

Pзt

Pзz

IPrtР*z

\_--.-nJ

V являeтcя

нyлеBьIМ

Ilo.цпpoстpaнствoМ

стpoк

пpoвeрoннoй

МaтpицЬI

Пpи

пoстpoении

пpoвepovнoЙ

N{aтpицЬI

дoлжнo

вЬIпoлI{яться

сле.цyюIцее

прaвилo:

|npu

noс-poенuu

лrаrпpuцьt

H кodа

c кodoвьtлl pаccmoЯнuел|

d любoй

cпoлбец не

doлэюeн 6ьtmь

лuнейнoй

кoм6uнаt1lleй

любьtх

dpуzuх

(d-2)

лeньulееo

нucла

cmoлбцoв.

oбщий

ви.ц

гrpoвеpoЧнoй

мaтpиЦьI:

Pr*r

Pzr-r

eм4

o:,"

P*r

p*t

I 0

D," 0 I 0l

O"n"r

0 .l

o:r"--;

; ; ;]

Пo

yслoвиto

opтoгoll€Ulьнoсти:

HТ

\------

In-t

Если кaждoмy

вrкгoрy

orшибки пpинaдJIея(ит

свoй

синд-

poМ'

не

сoвпaдaющий

ни с одI{иi\,t из

дpyгих

сиt{'цpoМoB'

тo c

ПoI\,{ощЬIo

тaкoй

тaблицьI

синдpol\4oв

и oIIIибoк, l\4o'{нo

o,цнo-

знaчIto

испpaBлять

orпибки.

Cиндpoмьr

oДнoкpaтнЬIx Beктopoв

oшибoк

стpoки

мaтpицьl

Hr.

=vхG

u=(щ,а2,...,Qt,CьCz,

...,Cп_td,

{

.дО

ai_ сoдep)кимoе

f.тoгo

инфopмaциol{I{oгo

paзpЯДa.,

€1

100...0

0 1 0...0

1101

1100

000...

I 1111

L.2.2.

Оcнoвньre свoйствa

линейньrх

кoДoв

Кoдoвьlе слoвa

линeйнoгo

кoдa u

o6paзуютcя

yмнoжeниeМ

Bxoдrroгo

слoвa

(ау

а2, ,

ai Ha пopoя(дЕlloщylo

мaтpицy

с;

сo.ЦеP)киМoе jl-тoгo

пpoBepoчI{oгo

paзpЯДa,

!ля

декoдиpoBaния

исIIoльЗyется

свoйствo

opтoгоI{uUIЬ}toсти вектopoB,l

стpoк

МaтpицЬI

H, пpи

этol\,{ пpoизвeдение

paзpeшrеI{нoгo

кoДoBoгo

cЛoBa

u Нa

тpaнсflol{иpoBaнIlyЮ

llpoBepoЧЕyю

мaтрицy

Дaет

нyлеBoй вектop

pазмеpнoсти

h-h

иxIIТ

=0.

3) Пpoизведeние

некoтopoгo кoдoBoгo

слoвa v,

Ll + еi с otшибкoй,

нa

трaнс-

пoниpoвaннylо

пpoBepoчкyю

Мaтpицy

I{aзЬIBaется

оинДрoМoМ и

oбoзнavaeтся

хIJT

(и Фe,)xHT

uxIIT *

xIIr

S..

MeNtдy

пopo)кдаIoщей

и пpoвеpoннoй

мaтpицaми

в систeМaтичeскoМ

BиДе

сylцествyет

oднoзrjaЧнoе

сooтBeтствие'

a иМeннo:

Двa

кoдa l{itзЬIвaются

эквиB€UIеIIтньIMи'

rcь|уr Иx lloponqцаIoщие

МaтрицьI

oтлиЧaются

пepeстaнoBкoй

кoop.Цинaт' т.

е. пoрo)кдaЮщиr

Мaтpицьr

пoлyча}oтся

oДнa

зa.цpyгoй

пеpестaновкoй

стoлбцoв

и элеМel{тapнЬIx

olrеpaций нaд

cтpoкaми.

1'.2.3.

Mетoдика

пoстpoения

линейнoгo

кoДa

ЗaДaниe

к пoстpoеt{иIo

Мo)кgг

бЬIтЬ oпpeДелrнo.цByмя

спoсoбaМи:

Dz,

ft]-кoд;

зaдaнo числo

paзpeшенньIx

кoдoBьrх

кoмбинaций

(

щaтнoсть

orпиб-

ки испpаBления

o6нapу>кeния

(q,,и

q).

Пoстpoeние

кoдa пo пеpBoмy

спoсoбy ЗaДall.Ия

Пo гpaнице

BapuraМoвa-Гильбеpтa

oIIpеделЯеTся

кoдoвoе

pacстoяниe

(Ф

у,ltt,l

Paзpя.цнoсть

КoДan:

сi+с|+...+С!-2

<2"-k

-|.

(1.1)

oпpeделяется

кpaтнoоть

испpaBлeниJI

oбнapyжeния

orцибoк

(q"pт

q):

2q.. +1,

I ..

(1.2)

ld>q.+1.