В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 26
Текст из файла (страница 26)
2. Доказать. что матрицы вида ( ' Ь ) с действитетысыма 12Ь «1 а и Ь абрйэуют кольцо относительно обычссых операнвй сзоясения и умножения матриц. 3. Будут лн следующие ннажествэ аодкольцанн унз»аиных колец: а) множество 7 целых чисел в катьке 2[х) вело'шсэеннык .саагочленов; б) множества л2[х[ ива«оксенов.
ьоэффивнентм ьоторьсх нратли числу я) 1, в ка.тьце 2[к[ целачасэсиных многочлснав. з) множества 2 целых чскеэ в кольце А целых гауссоэлх чэсел, т. е. чисел вида а+Ы с целыни а. Ьт Е Образуют лн поле относительно атожсння и умна.кения члсслс а) комплексные числа; б) комплексные числа вида а+Ь) с нетымв а и Ь; в) комплексные числа вида а+М с рацноиальнымн а и Ьь 5.
Образует ли позе множество натрии вида [ '„ " )с 2Ь «э' а) с раннанальнымн а, Ьг б) с действительными а, Ь? 22. ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ В теории передачи информации чрезвычайно важным является решение проблемы кодирования н декодирования, обеспечивающее надежную передачу ио каналам связи с «шумом». Передача информации сводится к лередвче па некоторому каналу связи символов некоторого алфавита. Однако в реальных снтуацннх сигналы ири передаче лрактичсскн всегда могут сссквжаться. и нередаивый символ будет восприниматься неправильно. Нэнрсс»сер, в системе ЭВЫ вЂ” ЭВМ одна нз вмчислительиых наиши может быть свлзана с другой через спутник.
Канал связи в эгон случае физически реа.твзуется элентромагннтвым вилем чежл) поверхностью Земли и спутником. Электромагнитные сигналы, накладываясь на внешнее вале, могут мсказнтьси н ослабспьсв. Для обеспечения надежности иередачи информа- 121 ынн» тан»х системах разрабатаны аффективные методы, нс. полат!юшке коли разлнчвых тннап. Рагсыатрнм одну нз такнх моделей, связанную с ерршюзы.
мп ля!ам». Ллфавнт. в нагаром зепнсынаютсл саобщсння. сч»таем со. сшящан нз леул символов (О. Ц Он»взывастся деоячным аа. фаннтом. Тогда сообщение есть ьансчнел погас»азате гьнссгь символа» эта!а алфеева, Сообщение, паллсхищсе передаче, ко. даруется по апредслешгай схеме более ллпнноб паслелоаатсль.
»остью символов в алфавнте (О, Ц. Эта последовательность на. зыаается юдо» нлн надоамм слсюом. Прн пресне можно попран. лять нлв распознавать ошпбюг. возннкшнс прн передаче по ка. малу сена», анап»акру» нн(юрмашео, содержащуюся в Лопол- лнтельных символах. Прка»тая пасзазовагельнасть снмаогюв лсьалнрустс» па определенной схеме н ссабщснпс, с большой вероятностью сонпадаюнгес с передлнным. Олачнытг лва»нный (ы. «)-кад опрелеляетсн двумя фунхцня- ын: Е . (О, Ц (О, Ц " » Р: (О Ц (О Ц , где шщл п .(О. Ц" — множество всех двоичных ггаслезозатсльнсстей длнвы л.
Функция Е онрелсляст схему код»розане», а функция Р— схему декаднроввння М»тснатггчсскую ыодель системы сааза можно прсчставнть в вале схемы Кх»вы н Р„н„г! Дса»Р ен Здесь Т вЂ” «функция ашкбонь; Е п Р выбнраюшя ганам обре- зом, чтобы композиция РОТОЕ была фунннней, с балыной за роятнастью блнзной к тажлсственнай. Двончный (щ, п)-нод со- дсржнт 2 каковых шгоз. Калы делятся на два большак класса: коли с обнаруженном а!я»бок, которые с большой вероятностью опрсдцтяют нзанчне ашпбьн в принятом саобшснвн, н «алы с псправзеннсн ошибок, которые с большой вероятностью могут васстановпть посланное сааб!целее.
Пр»мер 2ЛО. !. Код с проверкой четности. Это «рнмер простота кода. с большой верантнасгью указывавшею на налпч»е ошнбкя. Пусть а=ег...а — сообщен»с панны ы. С лрм юмрем с м сараю г к(е! =Ь-Ь, ... з.м, гас Ь вЂ” е, нра ! !...., м выл кз,— гычыас: ь „= !.чав хе — нюВюы . !ш схема декодирования опредешетсл таким образомп В(Ь) с=со..с, где сг=й~ прн ! 1, ..., ш. Па Рпшп. пп м-2 б!Сс)-ПСС. б!П!)-ЕП, й(йр-!Ш, ДО!1 По. О е ыш, аодршр д я уыы ыб Э шмр ым ы оо и атю асов 2 Ь, доамва быть втша, т.
е. Ь,.1-... ч-а, Сйп 12). 2«зи Х Ь, ясчешаь о о апатшт, чп пея перед е Наев а пр п ыаа манах.Оанко,е я па, ешая,тоэоеме ео аае. о емпщ е было. пораар паш «!паа осташ «в й прн паут еы (ыах в сме ыбчы ча асы ах юс е. 2. Код с тройным повторенном. Это пример весьма неэпономногп кода с поправлен»ем ошнбпн. Схема кадпровавня. т. е. функпяв Б, о»рсдсляется таким образом: каждое сообщение разбнваетск па блоки кланы пт н каждый блок асрсдается трижды. Слема дскаднрованкя, т. е. функпня О, апределяетсн следующим образом: прв»ятое сообщение разбивается нв бдокн длнны Зю в в каждом блохе аа трех символов Ьь Ь «, Ьыв„прав»вающих значепнс О нлн 1, выбирается тот, который встретвлся бсаьшсе чнсло раз (двв нла трн реза).
Зтш с»нэпа счнтестсв 1-и спмволам в декодырованном спобщепнв. Можно опредсшмь также (1, г)-код с г-кратным повторением, в котором каждый снмвпл 0 пл» 1 кодируется последовательностью нз г таких символов. Ь1ножество кодовых с.то» состоит нз двух слов: 00...0 н !1...1. Пр» декодярованпн решение прнпкмается «большинством голпсона, т. е. передзнным считается символ, встрсчаюшвнся большее число раз. Прк больших г мы пракшчесхп абезопаспм себя от ошибок, однако передача ссобщенпй будет кеты чрезвычайно медленно. 2.3.1.
Расстояыке Хсммннщ На ынажествс двавч»ых слов данны т расстоянием б(п, Ь) между словами и в Ь называнп чнсяо веотвпадающнх пгвнпый этих слов, напрямер: расстояпве между словамн а=01101 ы Ь 00)П равна 2. Определенное такам образом понятые называется росстошшгт йеллппгш Оно удовлетворяет следующим аксиомам росстовьяйг !) О(а, Ь) ~0 в И(а, Ь) О тогда н тольао тогда, когд* я=й; 21 д(а, Ь) =д(Ь, а); 3) д(о, ь)+к(ь, с) жд(а, с) (аеравенство треугольника). босом ш(а) слова а называют число едкннк среди его каор.
лзизт. Тогда расстояние между словамн а н Ь есть вес нх суммы о — , 'Ь: г((а, Ь) =то(а+Ь), где символом + обозначена операция езкоордннатпого слаженна по модулю 2. Пнтуятпвно понятно. что «од тем лучше прпспособшн к об. наруженпю и поправлению ошибок, чем больше различаются копание слова. Понятне расстояния Хеммннга позволяет зто уточ.
леть. Теорема 220. Длл гого чтобы код лгюеошл обнаруживать ош бои в й (или менее) позициях, иеобходшзо и досгагочло, чтобы иаимепьшэе распоялис между кодовыми слоеами бьио зй+1. Доказательство этой теоремы . аналогнчно доказательству следующего утверждения. Теорема 2.1!. Для гого чтобы код позволял ислраелхгь есе ошабки е й (или менее) позициях, необходимо и достаточно, чгтбы наименьшее расстояние пожду кодовыми словами было ) 22+1. Действительно, если наименьшее расстояине между кодовымн словамк ~2й+1, то для любых кодовых слов а п Ь имеем д(а, Ь)~22+1. Пусть прн передаче некоторого слова а произошло г(й ошибок. в результате чего было принято слово с.
Татаа д(а. с) =г(й. Из неравенства треуголыгпка (аксномы 31 следует, что д(а, с)+д(с, Ь) жд(а, Ь))22+1. Отсюда расстояние г1(с, Ь) от слова с до любого другого кодового слова Ь больше й. Эначнт. для деноднровання послепного слова надо нзйтп кодовое слово а, бллжайшее к принятому слову с а смысле расстояння Хемминга. Если наименьшее расстояние между кодовымн словамн меньше, чем 2й+1, то найдутся такие два кодовых слова а н Ь, расстояние между которыми будет д(а, Ь) ~уй. Тогда, если в кодовом слове а будет й ошнбок, принятое слово с находится от другого кодового слова Ь на расстоянин, пс большем, чем от а. Поэтому нельзя определпть, каное яз слов (а нлц Ь) было передано.
В мзтематнческой модели кодпрованвя н декодирование удобно рассматривать строкн ошибок. Данное сообщевпе а =а~аз...а кодируется кодовым словом Ь=Ь,Ьь.,Ь . Прн передаче канал связи добавляет к нему строку ошпбок е=е,еь..ем так что прнемннк прннпмает сигнал с с,сь..см где ст=Ьт+ее Система, исправляющая ошибки, переводит слово с,сь..с в блн. жаднее кодовое слово Ь~йз...й,. Система, обнаруживающая ошибки, толька устанавливает, является лн принятое слово кодовым пли нет. Последнее означает, что при нерсдаче произошла ошнбка.
гтт Пример гл!. 1. Рассмотрим (2, 3)-код с проверкой четноста, . мхх (см. пример 2.10. а. Ц множество «адовых слов есть ООО. 10!. 011. !1О. Минимальное расстааане межлу «одовымм слов»ми равно даун. Зтог код способен обнаруживать однократную ошибку. 2. Рассмотрю» (2, б)-кад со схемой кодирования Е(001 = =Е)ООО=Ь»1 б(ОЦ=О!Оп=3', б(!О)=!ОРО(=ЬЦ 31(Ц= =1!110=3».
Минимальное расстояние между кодовыми с»ов»- ми равно трем. Зтот код способен поправлять однократную ошибку. Однократная ошибка приводит к приему гдова. иены дящегося на ра«стоянии ! от единственного кодового с.»оаз, которое п было передано. 2.3.2. Матричное каднрввамие При явном задании схемы кодирования в (гн, н)-коде следует укатать 2 кодовых слов, чта весьма пезффективиа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
