WWW.DIS.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 | 5 |   ...   | 33 |

«Содержание этой книги составляет годовой курс Алгебраические коды, который автор читал в течение ряда лет в Московском физико-техническом институте (государственном ...»

-- [ Страница 1 ] --

Введение в алгебраические

коды

Сагалович Ю.Л.

4 октября 2011 г.

Предисловие

Содержание этой книги составляет годовой курс "Алгебраические коды", который автор читал в течение ряда лет в Московском физико-техническом институте (государственном университете). Разумеется, за 120-130 академических часов, включая и семинарские занятия, можно сообщить студентам лишь

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

Тем более автор был поставлен в тупик, когда ему порекомендовали написать для студентов учебное пособие под названием "Алгебраические коды". Можно ли согласиться на такой шаг, когда мировое сообщество специалистов и исследователей имеет в своем распоряжении книги У.У. Питерсона; В.Д. Колесника и Е.Т. Мирончикова; Э. Берлекэмпа; Э.Л. Блоха и В.В. Зяблова; У.У. Питерсона и Уэлдона; Т. Касами, Н. Токура, Ё. Ивадари и Я. Инагаки; Ф. Дж. Мак-Вильямс и Н.Дж.А. Слоэна; Э.М. Габидулина и В.Б. Афанасьева; Р. Блэйхута; Лидла и Нидеррейтера.

Однако по здравом размышлении автор уяснил два главных факта. Книги указанных выше авторов давно стали библиографической редкостью, и надежды на их переиздание нет. Сами же эти руководства настолько насыщены и полны, а подчас не просто полны, но полны энциклопедически, что для первого чтения трудны. Процесс преподавания, его временные ограничения, уровень подготовки студентов способствовали естественному отбору содержания курса. Естественный отбор, однако, был не столь беспощаден, как в животном мире. Всякое вынужденное отсечение безусловно интересных сведений, коПредисловие торые буквально просились на страницы книжки, было поистине болезненным. Когда логика рассуждений требовала продолжить изложение темы, но заданный объем курса, а значит и книжки, ставил понятное препятствие, приходилось идти на компромисс. Искушенный читатель без труда обнаружит соответствующие места.

В то же время в данную книжку включена специальная глава "Начальные сведения из теории чисел", хотя в перечисленных выше источниках теоретико-числовые сведения использованы, но разрозненно.

Дело в том, что ни в один курс математики технических вузов не включается даже упоминания о теории чисел. Если в монографии можно ограничиться лишь ссылкой на источник, где можно прочитать, скажем, о теореме Эйлера, то в учебнике это было бы неуважением к читателю. Теория чисел настолько близка к алгебре, что в книге об алгебраических кодах она выглядит вполне органичной, так как является одним из исторических корней современной алгебры. Теоретико-числовые факты служат яркой иллюстрацией к большинству утверждений теории групп, а без нее теория кодов вовсе и не теория.

Возможность доказать, например, (малую) теорему Ферма или теорему Вильсона различными способами, в зависимости от того, в каком месте книжки находится читатель, демонстрирует тесную связь между различными разделами курса. Наконец, читатель, решивший освоить основное содержание теории алгебраических кодов, вполне способен и достоин чести познакомиться с основами "царицы математики" как раздела, цементирующего математическую культуру.

Возвращаясь к теме объема, приведем, пожалуй, самый главный аргумент против расширения содержания книжки и доведения ее в конце концов до уровня энциклопедии по кодам.

Такой уровень был выдающимся достижением тридцать лет тому назад, когда вышла в свет книга Ф. Дж. Мак-Вильямс и Н. Дж. А. Слоэна. Теперь другое время, и когда накоплен огромный запас методов построения кодов, удовлетворяющих разнообразным практическим нуждам, когда необычайным образом разрастается тематика исследований по теории кодирования, когда специалистам, овладевшим началами теории кодов, предоставлен широкий ассортимент способов построения реальных систем связи, назревает другая необходимость. Это — необходимость подняться в преподавании теории кодирования на новый уровень абстракции. Возможность к такому переходу обеспечена появлением монографии "Алгеброгеометрические коды (Основные понятия)" трех авторов: С.Г. Вледуца, Д.Ю. Ногина и М.А. Цфасмана. На мой взгляд, сформирована Предисловие и аудитория молодых людей с хорошей математической подготовкой, способная к восприятию новых серьезных сведений.

Данная же книжка преследует куда более скромную цель:

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

Автор искренне благодарит В.Б. Афанасьева и В.В. Зяблова за труд первого чтения, сопровождавшегося рядом важных советов и замечаний, которые послужили улучшению предлагаемой книги, Д.С. Осипова и Д.В. Лаконцева за помощь в оформлении оригинала-макета, В.С. Козякина за неоценимое содействие и помощь.

Предисловие ко второму изданию В настоящем издании прежде всего устранены недочёты предыдущего издания; улучшено изложение в нескольких местах книги; внесены незначительные изменения в списки задач к главам; существенно расширена глава с указаниями к решению задач. Внесены дополнения в главу о конечных полях В теоретикочисловую главу помещен раздел об алгоритме Эвклида отыскания наибольшего общего делителя двух целых чисел. Это вызвано тем, что в разделах 7.7 — 7.10, написанных при участии В.Б.Афанасьева, подробно изложен метод декодирования, основанный на алгоритме Эвклида. Среди других методов этому методу отдано предпочтение по той причине, что алгоритм Эвклида, известный с незапямятных времён, через столетия оказался как будто специально приспособленным для весьма специфических нужд теории кодирования.



Введение 0.1. Система передачи информации.

Двоичный симметричный канал В простейшем случае система передачи сообщений состоит из передатчика, канала связи, и приемника. Схематически он выглядит, как показано на рис. П а П а П Ка а Рис. 1. Простейшая система передачи информации Передатчик передает сообщения в виде последовательностей одинаковой длины n, состоящих из нулей и единиц:

(0.1.1) u = (u1, u2,..., un ), ui = 0, 1.

(Вообще говоря, последовательности могут иметь и разные длины, но здесь этот случай рассматриваться не будет.) В канале действует случайная помеха: каждый символ передаваемой последовательности независимо от других может быть искажен с вероятностью (0.1.2) 1/2.

Это означает, что с вероятностью 1/2 происходят переходы 0 1, 1 0 и с вероятностью = 1 компоненты 0 и 1 последовательности u сохраняют свое значение. Такой канал называется двоичным симметричным. Схематически он изображен на рис. 2.

Часто вместо "последовательности" применяют термины "слово" или "вектор". Для нас это синонимы, но для определенности и единообразия в дальнейшем употребляется термин "вектор".

Процесс действия помехи на передаваемый вектор можно описать следующим образом. Введем в рассмотрение вектор где ei = 1, если символ ui искажен, и ei = 0 — в противном случае. Вектор (0.1.3) называется вектором-ошибкой.

Пусть передавался вектор u = (110001001), а на приемном конце получен вектор v = (010001101). Это означает, что в канале подверглись искажению первый и седьмой символы передававшегося вектора. Это означает, что в векторе e единицы расположены на первом и седьмом местах, т.е. e = (100000100).

Легко заметить, что вектор v получается поразрядным сложением векторов u и e по модулю два: 0+0=1+1=0, 0+1=1+0=1.

Вообще, если передается вектор (0.1.1), то на приёмном конце получают вектор Про такой канал говорят, что это канал с "аддитивной помехой".

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

"повторить передачу", а значит, правильным считать тот символ, который встречается чаще. И чем больше повторять передачу, тем надежнее она будет. Такая уверенность основана на том, что в силу условия (0.1.2) правильных значений передаваемого символа окажется больше, чем неправильных.

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

Можно с уверенностью утверждать, что не будь разумной альтернативы методу многократного повторения передаваемого символа, наука, которая называется "Алгебраические коды", не была бы известна.

Положим в общем случае, что ради надежной передачи информации, вместо k символов приходится передавать n k символов. Сопоставление некоторым способом n символов заданным k символам вектора называют кодированием. Отношение k/n называется скоростью передачи. В предыдущем случае k = 1, и скорость передачи k/n = 1/n.

Восстановление закодированных k символов по n переданным символам, каждый из которых мог подвергнуться искажению с вероятностью (0.1.2), называется декодированием. Не исключена возможность, что это декодирование окажется ошибочным.

Теперь систему передачи информации можно детализировать более подробно, как показано на рис. 3. Из источника сообщений извлекается вектор длины k, кодер преобразует его в вектор длины n, который передается по каналу связи с помехой, а затем декодируется и поступает по назначению.

Альтернативу методу многократного повторения доставляет знаменитая теорема Шеннона.

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

Достоверность передачи измеряется вероятностью P ошибки декодирования.

Основную роль в точном формулировании теоремы Шеннона играет функция энтропии H(x). Она имеет вид Если не оговорено иное, логарифмы берутся при основании 2. Натуральный и десятичный логарифмы, как обычно, пишутся соответственно ln и lg. Если же логарифмы берутся при некотором основании q, то пользуются обозначением Hq (x). Последнее имеет место в случае так называемого q-ичного канала, который будет обсуждаться в одной из следующих глав.

С помощью функции энтропии определяется упомянутая пропускная способность C( ) канала, представленного на рис. 2.

Она зависит только от величины – вероятности искажения одного двоичного символа.

В этих терминах теорема Шеннона, которая первоначально доказывалась на случай двоичного симметричного канала, звучит следующим образом:

Каково бы ни было 0, при достаточно большом n, и k/n C( ) = 1 H( ), существует такое кодирование, при котором P.

Теорема Шеннона доказана методом случайного выбора векторов и не говорит, как реализовать такое кодирование. Однако, если доказано существование "хорошего" кодирования, то это прямой сигнал к поиску конструктивных методов создания кодов с заданными свойствами. Значительная часть книги посвящена именно этой теме.



Pages:     || 2 | 3 | 4 | 5 |   ...   | 33 |

Похожие работы:

«Министерство образования и науки Российской Федерации ФГБОУ ВПО Московский архитектурный институт (государственная академия) А.А. Климухин Е.Г. Киселева Проектирование акустики зрительных залов Учебно-методические указания к курсовой расчетно-графической работе Москва МАРХИ 2012 1 УДК 534.2 ББК 38.113 П 79 Климухин А.А., Киселева Е.Г. Проектирование акустики зрительных залов: учебно-методические указания к курсовой расчетно-графической работе / А.А. Климухин, Е.Г. Киселева. — М.: МАРХИ, 2012. —...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (МГТУ МИРЭА) ЛЕВИТАЦИЯ НАМАГНИЧЕННЫХ СВЕРХПРОВОДЯЩИХ КОЛЕЦ С ТОКОМ Методические указания по выполнению лабораторной работы по курсам Физическая химия материалов и процессов электронной техники и Физико-химические основы процессов микро- и...»

«Академия управления при Президенте Республики Беларусь Факультет инновационной подготовки Кафедра экономико-математических методов управления О. Б. Плющ Г. М. Северин Т. В. Безъязычная Информационные технологии анализа и обработки данных Практикум Минск 2010 Р е ц е н з е н т ы: кандидат физико-математических наук В. А. Иванюкович кандидат технических наук А. А. Перепелица Плющ, О. Б. Информационные технологии анализа и обработки данных: практикум / О. Б. Плющ, Г. М. Северин, Т. В. Безъязычная....»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра Информационных и управляющих систем УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Моделирование систем Основной образовательной программы по специальности 230102 – Автоматизированные системы обработки информации и управления Благовещенск, 2012 г. УМКД разработан кандидатом физико-математических наук,...»

«ФИЗИКО-ХИМИЧЕСКИЕ ПРОЦЕССЫ ПРИ ОБРАБОТКЕ МЕТАЛЛОВ Методические указания и контрольные задания по дисциплине Физико-химические процессы при обработке металлов Министерство образования и науки РФ ФГБОУ ВПО СибАДИ Кафедра Конструкционные материалы и специальные технологии ФИЗИКО-ХИМИЧЕСКИЕ ПРОЦЕССЫ ПРИ ОБРАБОТКЕ МЕТАЛЛОВ Методические указания и контрольные задания по дисциплине Физико-химические процессы при обработке металлов Составитель М. С. Корытов (в авторской редакции) Омск СибАДИ УДК 621....»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УЧЕБНАЯ ПОЛЕВАЯ ПРАКТИКА ПО ОБЩЕЙ ГЕОЛОГИИ НА СЕМИЛУКСКОМ ПОЛИГОНЕ Учебное пособие для вузов Издательско-полиграфический центр Воронежского государственного университета 2008 Утверждено научно-методическим советом геологического факультета 21 февраля 2008 г., протокол № 2 Авторы: В.Ф. Лукьянов, В.Н. Бунеев, Г.В. Войцеховский, С.А. Коваль,...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ РАДИОФИЗИКИ И ЭЛЕКТРОНИКИ КАФЕДРА РАДИОФИЗИКИ Методические указания к лабораторной работе Исследование невзаимных пассивных микрополосковых устройств СВЧ по курсам Прикладная электродинамика, Электроника СВЧ для студентов специальностей Н.02.02.00-Радиофизика, Н.02.03.00-Физическая электроника Минск 2002 Составители: А.Г. Будай, к.т.н. В.И. Демидчик, доцент В.С.Курило, старший преподаватель...»

«Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра аналитической химии АНАЛИТИЧЕСКАЯ ХИМИЯ Программа, методические указания и контрольные задания по дисциплинам Аналитическая химия, Аналитическая химия и физико-химические методы анализа для студентов химикотехнологических специальностей заочной формы обучения Минск 2012 1 УДК 543(075.4) ББК 24.4я73 А64 Рассмотрены и рекомендованы к изданию редакционноиздательским советом университета Составители: А. Е....»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный университет технологии и дизайна Кафедра наноструктурных, волокнистых и композиционных материалов им. А.И. Меоса ХИМИЯ И ФИЗИКА ПОЛИМЕРОВ Методические указания к самостоятельному изучению курса и выполнения контрольной работы для студентов квалификации Бакалавр направлений Технология изделий легкой...»

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет радиофизики и компьютерных технологий Кафедра радиофизики и цифровых медиа технологий Учебное пособие по курсу Прикладная электродинамика автор: Демидчик Валерий Иосифович Введение ОБЩИЕ ПРИНЦИПЫ ЭЛЕКТРОДИНАМИКИ ПОЛЕЙ, ГАРМОНИЧЕСКИ МЕНЯЮЩИХСЯ ВО ВРЕМЕНИ Для электромагнитных колебаний, используемых в радиосвязи, радиовещании, телевидении существует общепринятая система разделения и наименования частотных диапазонов. Интересующие нас в рамках...»




 
© 2013 www.dis.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.