Алгебраические системы и некоторые их приложения в теории информации и автоматизации проектирования (1012854), страница 6
Текст из файла (страница 6)
Образует ли поле множество матрип вида ~ ) нз упражнения 2 к равд, 1.1О: 1Ь а а) с рапиональнымн й,Ь > б) с действительными >2, Ь у 2. ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ В теории передачи информапии чрезвычайно важной являет оя проблема кодиоования н декодирования, обеспечиваюшая надежкую передачу по каналам связи с "шумом". Передача информапии сводится к передаче по некоторому каналу связи символов некоторого алфавита.
Однако практичеоКи всегда, в реальных ситуациях, сигналы при передаче могут искажаться и переданный символ будет восприш>маться неправильно. Например, прн связь ЭВМ - ЭВМ одна иэ вычислительных машин может быть связана с другой через спутник. Канал связи в этом случае физически решдшуется электромагнитным лолем между поверхностью Земли и спутникам, ЭлектромагнитНые сигналы, накладываясь на внешнее поле, могут исказиться и ослабиться„ Для обеспечепвя вадежноств передачи информации в систе- мах типа систем связи со спутнвками и большими вычислвтепь- ными системами разработаны эффективные методы, связанные с вспольэовэнием кодов рээпвчвых типов. Мы рассмотрим одну иэ таких моделей, связанную с груп- повымн кодами.
Алфавит, в котором записываются сообщения, считаем со- стоящим вз двух символов 10, 1) ° Он называется двоичным алфавитом. Тогда сообшенве.есть конечная последоватепьпость свмвопов этого апфавята, Сообщение, подпежащее передаче, ко- дируется более длинной цоспедовательностью символов в апфавп те 1О, 1) по определенной схеме кодирования. Эта последова- тельность кэзывается кадом впи кодовым словом, При приеме мы можем исправлять ипи распознавать ошибки, возник шяе прк передаче по кэкапу связи, анализируя инфармацию, со- держащуюся в дополнвтеаьвых свмэолах, Прнпвтая поспедовате>п кость символов по определенной схеме декодируется в сообще- ние, с бопьшой вероятностью совпэдакхпее с переданным, Блочный двовчный (Р>т,РФ ) - код определяется двумя функ- циями Е:Г .,Г и Ю:Ю~ "Я»т, где~иеи и8~- множество всех двовчвь>х последовательностей дивны 7т, фуюшвя Е опре- депяет схему кодвровения, функция .Р— схему декодирования.
Математическую модель системы связи можно представать схе- мой ~рис. 2.1), где Т - фунюпи ошибок". При этом Е и Ю зыбнрак>тся так, чтобы композипвяЮэуэс быпа функцией, с боль- шой вероятностью бпиэкой к тождественной, Двоичный (Ртт, тх ) код содержит,8>'» кодовых слов, Рис, 2,1 Коды делятся на два больших кпасса - коды с обнаружением сшибок, которые с большой вероятностью определяют наличке ошибки в принятом сообщении, и коды с исправлением ошибок> хоторые могут с большой вероятностью восстановить посланное сообшевие„ э~,~,к„° ~ р и и> р ~ > стого коде, с большой вероятностью укаэываюцега на наличие >шпбкв.
Пусть О = й» ... й - сообпкшне длины 7п.. Схема кодирования определяется там Е (й.) -Ь**Б ...Ъпч~~, гней за; при х' 1„,. Рг», »тэ О, если Д ' Ь - четна~~ кь» »» »"Рх 1, еспн .У~ ф - нечетная . »=» Схеме декодирования: ЮЯ» *х С» ...С»»т, где С ° = Ь., при г' 1, „...»»г. Например, прн Рт»= 2 Е(0 01 ю 0 0 О, Е (О 1) = 0 1 1, Е (1 О) 10 1, Е (1 1) ~ 110. Очевидно, поразрядная сумма любой кодированной последаl»т>» ватепьностн Д, Ь . должна быть четной, т.е, Ь» +.„+»» «О »»»т»»д»с» ° Есин,Б Ь»' печатна, то это означает, что при пере»"- » даче соабшения произошла ашабка, если~'~» четна, то эта у= не означает, чта ашпбки не было.
Поразрядная сумма останется чет- ной, если произойдут две ошибки нпя ваобше любое четное чна- по ошибок. Дйймер Д: Код с тройным повторением. Эта пример очень неэксномного када с исправлением ошибок Он является (»»т, 3»»ч) кодом, Функпня Е определяется так: каждое сообшение разбшшетсн на блоки дпжы»»х н каждый блок передается тршкды, Декоди- рование, т.е, функция Ю, определяется следуюшей схемой. При пятое сообщение разбивается на бпакн дпиныЛ"рт, В каждом блоке из трех символов 6„', Ь» тх,Ьу»~„т, принимавших зна ченне 0 и 1, выбирается тот, который встретипся большее чио ко раз (т.е два или трн раза\, Зтот символ считается г -м символом в декаднраваниам сообшшппт, Можно определить также (1, » +1)-код с» -кратным по- вторением, в катаром каждый символ 0 ипи 1 кодируется после- довательностью нз г' » такого символа.
Множество кодовых спсв состоят аз звук слав 0 0 ...0 и 1 1... 1. При декодирования ре- шение принимается "большинствам голосов", т,е, считается пере- данным сьмвап, зстрочаюп1яйся бопыпее число раз, Прк больших » мы практически оба: опаснм себя >т ошибок, адпахо герецача саобьюнпй буде» 1щтн ишзвычайна моцпенпа. 2,1. Расстояние Хемминга На множестве двоичных слов длины ттг расстоянием С~(И,Ь ) между словами Ю и Ь назовем число несовпадаюшнх познпнй этих слов.
Например, расстояние между словами Д 01101 и Ь 00111 равно 2, Определенное таким обрезом понятие называется расстоя- нием Хемминга, и оно удовлетворяет аксиомам расстояния: 1. Ы/Й,ЯРО и ~~~й,фхО тогда и только тогда, когда 2'. ~Га,ИсЫИ,а); 3. ~~й, фткр(Ь,Г) В С~~а, С~ (неравенство треугольника). Весом Ю УИ) слова~1 называют число едииип среди его координат, Тогда расстояние между словами Я и Ь есть вес их суммы а+ Ь: Ш (я, 9 = иГ(а т Я.
Интуитивно понятяо, что код тем лучше приспособлен и об- иаружеюпо и испрввлеяшо ошибок, чем больше отличаются кодо- вые слова, Понятие расстояния Хеммшпа позволяет уточнить это, ть~ ~.п в «ю жить наличие ошибок в Л' (или менее) позипиях, необходимо я достаточно, чтобы наименьшее расстояние между кодовыми сло- вами было 'Ф Доказательство этой теоремы аналогично приведенному ни- же доказательству следуюшего утверждения, Теорема 2. Для того чтобы код давал возможность испра- вить все ошибки в А' (или менее) позипиях, иеобходямо и до- статочно, чтобы навменьшее расстояние между кодовыми слова- ен было 84+4. О Пй а* ловых слов й и Ь имеем с4)т, 9 З И~ У, Пусть при передаче чекоторого слова ~ произошло ~ КА ошибок и в результате бы- чо принято слово с, Тогдас~1а,г) = к4 .
Из неравенства греугольниха (аксиома З) следует, чтоа(а,г)+СККП)З йА~а,Ь) э~А~у . Отсюда расстояние д~(с',Ь) от с до любого кодового слова Ь больше 4 . Значит, для декодирования послан- чого слова надо найти кодовое слово ш , ближайшее к приня- гому слову с в смысл расстояния Хеммянга, Если жо наименьшее расстояние между кодовыми словами еопьш:, ~ем ГХ - ~, то найдутся таила даа ходовых слова с4 п б, расстаяли" м жду которыми с~(а,Б) н,. 4, Тогда, если в ш л чюм слов.: ш будет й ошибок, то ~ рячятое слово с нот~ ~ятся от другого кодового снова Ь ла расстоянии, но больше 1 чем от И . Поэтому нельзя определять, какое яэ слов д.
или Б было передано. В математической модели кодирования и декодяровения удобно рассматривать строки ошибок, Пшшое сообшениеа= «И Й~...а ~ перекоднруется в кодовое словоБ=З,ЬГ...Ьр~, Каиал связи при передаче добавляет к нему строку ошибок Р-фут... а так, что приемник принимает сигнал~=с' ГГ...Г гдеС хЬ;еду, Система, исправлшошая ошибки, переводит слово г~гт...С~ в ближайшее кодовое слово ~Дг...Б~х . Система, обнаруживакхпая ошибки, устанавливает только, является ли принятое слово кодовым или нет, Последнее означает, что при передаче произошла ошибка. Р «(Рс- «Р ° й Тогда множество кодовых слов есть 000, 101, 011, 110, Минимальное расстояние между кодовыми словами равно двум, я код обнаруживает однократную ошибку.
Дрор 2 Р *Р ««(2.61 й кодирования: Е(00) 00000 с~ Е(01) 01011 Б ~ Е(10) 10101 «Ьх Е(11) 11110 «3ч Минимальное расстояние между кодовыми словами равно Ерем. Этот код способен ясправлять однократную ошибку. Однократная ошибка приведет к приему слова, которое находится на расстоянии 1 от единственного кодового слова, которое и было передано. 2.2. Матрвчное код рвание При явном задании схемы кодярования в (пт, тк )-коде мы должны указать,с ~ кодовых слов, что весьма неэффективно. Одним нз экономных способов описания схемы кодирования является методика матричного кодирования, ПустьБ"=(( Ду ° )~ - матрипа порядка (Ри ° Рг) с элементами ~7; ., равнымн 0 или 1, Обозначим символом"+*сложение по Э модулю 2. Тогда схема кодирования задается системой уравнен ай Tтт ПЯ~~' ' ~)лх ~5~п '=~ ~г' ~ ю~ т / нпи в матричной форме Ь=й«~, гней=0 „, й - вектор, соответствуюший передаваемому сообшенню,д=Ь,...сд - вектор, соответствуюший кодированному сообшеншо, б' — порождаюшая матри:- па кода.
Пусть задан групповой код с порождавшей матрицей 0 и кодирование происходит по схеме 5 =аб". Прн передаче кодовые слова могут исказнться, и мы при- нимаем сообшениеС С,.„С... гдеС=Ь+Р иР=Р,, Ргх вектор (строка) ошибок, Предлагается следуюшая схема декодирования, при которой вероятность того, чтоЯ()1С~ тй, будет минимальна. Обозначим череэС множество всех слов, которые могут быть приняты, Это множество всех двоичных слов длины Рх, и оно образует коммутативную группу, Множеством всех кодовых слов есть подгруппа С . Рассмотрим множество смежных кэас- совС яо В, т,е, фактор группу С/3 . Лидером смежного класса назовем слово наименьшего веса, Поскольку смежные классы либо не пересекаются, либо совпадают, то любой элемент Сас' однозначно представляется в виде суммыСэЫ'~Ь кодового слова Ь н лидера Е~, Пекодированке слова С состоит в выборе кодового слова 5 в качестве переданного и последуюшем пере- ходе к слову й, где 5 эх~) ° Этот метод декодирования удобно реализовать с помошыо таблицы, первая строка которой есть множество кодовых слов, т.е, смежный класс Р+З > состояший из элементов Е)Ь,...,Ь я~~э ~ а остальные строки соответствуют остальным смежным классам по В, причем первый столбец этой таблицы есть столбец лиде ров, ,Пля примера 3 нэ равд.
2,2 приведем таблицу декодирова- ния (табл, 2,1). Здесь первая строка строка кодовых слов, первый столбец - столбец лидеров, Чтобы декодировать принятое слово С =Р "Ь~, где Р С лидер, следует отыскать его в таблице и выбрать в качестве переданного кодового слово Б~ в том же столбце и первой строке, Таблица 2.1 Например, если принято слово 110011, то считается, что передано слово 010011, если принято 100101, то считается, что передано 110101, если принято 110101, то считается, что опо н было передано„ Зб Псрождвюшая матрнпа кода определена неоднозначно. Код ие должен прнписывать различным оковам-сосбшениям одно и тс же кодовое слово. Можно докезать, что этогс можно добить- ся, если первые '~и стопбиов мвтрипы С образуют единичную матрипу, Земетвм, что вместо с' кодовых слов достаточно знать ттт слов, явпяюшихся строкамн метрипы ( ,11.ПР Й~Й Р Й(1,1+1) рением является матрипе (и (1„,1), так как (1...1)=М, (О...О) дпР(.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
