Error-correcting codes

Краткое содержание учебной дисциплины, модуля / Brief summary

Тема 1. Основные понятия теории кодирования.

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

Тема 2. Линейные коды.

Линейные коды. Порождающая и проверочная матрицы линейного кода. Общие свойства линейных кодов. Систематическое кодирование. Вес линейного кода. Минимальное расстояние линейного кода, его связь с проверочной матрицей. Таблица стандартного расположения кода. Декодирование линейного кода по лидеру смежного класса и по синдрому. Двоичные коды Хэмминга. Коды Хэмминга над полем из элементов. Параметры кодов Хэмминга. Декодирование кодов Хэмминга.

Тема 3. Совершенные коды.

Совершенные коды. Критерий совершенности кода. Коды Хэмминга – совершенные коды. Коды Голея.

Тема 4. Границы объема кода.

Границы объема кода: граница Синглтона, граница Хэмминга, граница Варшамова-Гилберта, граница Плоткина.

Тема 5. Циклические коды.

Конечные поля и их свойства. Многочлены над конечными полями. Понятие циклического кода. Циклические коды – идеалы в факторкольце . Порождающий многочлен и порождающая матрица циклического кода. Проверочный многочлен и проверочная матрица циклического кода. Кодирование циклических кодов.

Тема 6. Коды БЧХ и коды Рида-Соломона.

Определение кодов БЧХ. Граница БЧХ. Декодирование кодов БЧХ. Коды Рида-Соломона и их применение.

Topic 1. Basic concepts of coding theory. 

Transmission of information, the main problem of information transmission. The concept of code. Hamming metric. Minimum code distance. The principle of decoding in the nearest. The number of errors detected and corrected by the code, its relationship with the minimum distance. 

Topic 2. Linear codes. 

Linear codes. Generator and parity-check matrices of a linear code. General properties of linear codes. Systematic coding. Weight of a linear code. Minimum distance of a linear code, its relationship with the parity-check matrix. Standard code arrangement table. Decoding a linear code by the coset leader and by syndrome. Binary Hamming codes. Hamming codes over a field of elements. Parameters of Hamming codes. Decoding Hamming codes. 

Topic 3. Perfect codes. 

Perfect codes. Criterion of code perfection. Hamming codes are perfect codes. Golay codes. 

Topic 4. Code size bounds. 

Code size bounds: Singleton bound, Hamming bound, Varshamov-Gilbert bound, Plotkin bound. 

Topic 5. Cyclic codes. 

Finite fields and their properties. Polynomials over finite fields. The concept of a cyclic code. Cyclic codes – ideals in a factor ring . Generator polynomial and generator matrix of a cyclic code. Parity-check polynomial and parity-check matrix of a cyclic code. Coding of cyclic codes. 

Topic 6. BCH codes and Reed-Solomon codes. 

Definition of BCH codes. BCH bound. Decoding BCH codes. Reed-Solomon codes and their applications

Формируемые компетенции / The formed competences

Специализированные компетенции:

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

Specialized competencies: 

Apply current methods of geometry and algebra in mathematical models.

Результаты обучения (знать, уметь, владеть) / Learning outcomes (know, can, be able)

В результате изучения учебной дисциплины студент должен

знать:

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

уметь:

– выполнять вычисления в конечных полях;

– строить коды с заданными параметрами;

– кодировать и декодировать информацию;

владеть:

• основными навыками решения задач, связанных с теорией кодов, исправляющих ошибки;
• методами доказательств основных теорем, встречающихся в курсе «Коды, исправляющие ошибки»;

– навыками самообразования и способами использования аппарата алгебры и теории чисел для проведения математических и междисциплинарных исследований.

As a result of studying the academic discipline, the student should 

know: 

– the basic concepts and results of the theory of error-correcting codes; 

– methods of proving the most important results studied within the framework of the academic discipline “Error-correcting codes”; 

– algorithms for solving problems in the discipline “Error-correcting codes”; 

be able to: 

– perform calculations in finite fields; 

– construct codes with given parameters; 

– encode and decode information; 

possess: 

– basic skills for solving problems related to the theory of error-correcting codes; 

– methods of proving the main theorems encountered in the course “Error-correcting codes”; 

– self-education skills and ways of using the apparatus of algebra and number theory to conduct mathematical and interdisciplinary research.

Семестр изучения учебной дисциплины, модуля / Semester of study

3

3

Пререквизиты / Prerequisites

Алгебра и теория чисел

Algebra and Number Theory 

Трудоемкость в зачетных единицах (кредитах) / Credit units

3 зачетные единицы.

3 credit units.

Количество аудиторных часов и часов самостоятельной работы / Academic hour of students’ class work, 

hours of self-directed learning

Всего 90 часов, из них 36 аудиторных часов и 54 часа самостоятельной работы.

A total of 90 hours, of which 36 academic hours of students’ class work and 54 hours of self-directed learning.

Требования и формы текущей и промежуточной аттестации / Requirements and forms of current and interim certification

Устный опрос, коллоквиум, 

контрольная работа.

Экзамен.

Oral survey, colloquium, test. 

The test.

Exam.