РУП ЧелГУ - Свёрточные помехоустойчивые коды

(2008 г.)

Министерство образования Российской федерации

Челябинский государственный университет

Кафедра «Компьютерной безопасности и прикладной алгебры»




УТВЕРЖДАЮ
Декан математического факультета
……………………… Фёдоров В.Е.
«……….»…………………..2008 г.


РАБОЧАЯ ПРОГРАММА



дисциплины СД.@@@        Свёрточные и турбокоды и многопороговое декодирование

для специальности         075200          –  Компьютерная безопасность
специализация               
направление подготовки

Факультет                Математический
Кафедра-разработчик       Компьютерной безопасности и прикладной алгебры

Рабочая программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования и примерной программой дисциплины по специальности 075200 – Компьютерная безопасность



Рабочая программа рассмотрена и одобрена на заседании кафедры «Компьютерной безопасности и прикладной алгебры»

Протокол № ……… от   «…..» ……… 2008 года.


Зав. кафедрой-разработчика                д.ф.-м.н., проф. Соловьёв А.А.

Разработчик программы                старш. преп. Горшков А.В.

Учёный секретарь кафедры                к.т.н., доц. Кораблёва В.В.

Челябинск

2008

СОДЕРЖАНИЕ

1. Выписка из ГОС
2. Учебная программа дисциплины «Свёрточные и турбокоды и многопороговое декодирование»
2.1. Пояснительная записка.
2.2. Содержание.
2.3. Литература.
3. Рабочая программа дисциплины «Свёрточные и турбокоды и многопороговое декодирование»
3.1. Тематический план
3.2. Планы лекционного курса.
3.3. Планы лабораторных и практических занятий.
3.4. Организация самостоятельной работы.
3.4.1. Методические рекомендации.
3.4.2. Список тем рефератов.
3.4.3. Список тем исследовательских работ.
4. Методические рекомендации о контроле знаний, умений, навыков студентов

1. ВЫПИСКА ИЗ ГОС
Требования к обязательному минимуму содержания основной образовательной программы подготовки специалиста по специальности
@@@@@@ГОС 071400, ОКСО 210101 – Физическая электроника

@@@@@В связи с отсутствием ГОС по дисциплине специальной подготовки «Свёрточные и турбокоды и многопорогове декодирование» для ОКСО 210101 разработчик вынужденно опирается на сочетание следующих наиболее близких по существу ГОС:

@@@@@Индекс ЕН.Ф.02. для ОКСО 210100  «Электроника и микроэлектроника»
дисциплина Информатика:
… модели решения функциональных и вычислительных задач; … локальные и глобальные сети ЭВМ; основы защиты информации и сведений, составляющих государственную тайну; методы защиты информации…

@@@@Индекс СД.07 для ОКСО «Вычислительные машины, комплексы, системы и сети», дисциплина Сети ЭВМ и средства телекоммуникаций (всего часов – 214).
Основные разделы: принципы многоуровневой организации локальных и  глобальных сетей ЭВМ; методы и технологии проектирования средств телекоммуникаций; протоколы канального, сетевого,  транспортного и сеансового уровней; конфигурации локальных вычислительных сетей и методы доступа в них; сети ЭВМ с моноканалом и кольцевые; проектирование сетей ЭВМ по принципу "клиент-сервер"; конфигурации  глобальных  сетей ЭВМ и методы коммутации в них;         менеджмент в телекоммуникационных системах;  аппаратные  средства телекоммуникации;  программные средства  телекоммуникации; обеспечение безопасности телекоммуникационных связей и административный контроль; проблемы секретности в сетях ЭВМ и  методы  криптографии; тенденции развития телекоммуникационных систем.

2. УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ «СВЁРТОЧНЫЕ И ТУРБОКОДЫ И МНОГОПОРОГОВОЕ ДЕКОДИРОВАНИЕ»

2.1. Пояснительная записка.

Дисциплина «Свёрточные и турбокоды и многопороговое декодирование» изучается в @@@@ семестре. Из общего объёма 90 часов – 34 часов аудиторных занятий, 56 часов самостоятельной работы.

Формы аудиторных занятий – лекции 34 часов, лабораторные работы 0 часов, практические занятия 0 часов.

Формы контроля – проверка посещения, текущий опрос, @@@проверка лабораторно-практических, зачёт.

Целью дисциплины является усвоение студентами современных представлений о широко применяемых в практике (в системах связи, стойких к разнообразным помехам достоверности содержания, достоверности авторства, безотказности удостоверенного получения, распознавания свой/чужой, в том числе совместно с обеспечением несовершенной секретности) разновидности непрерывных кодов – «свёрточных», их свойствах и методах декодирования; также о разновидности параллельных каскадных кодов – «турбокодах», разработанных в основном  со свёрточными кодеками в качестве элементарных; также о многопороговом декодировании, реализуемым с линейно малыми затратами, хорошо сопрягаемым со свёрточным и турбокодированием; а также об особенностях приёма в каналах со сколь угодно малым отношением сигнал/помеха.

Связь с другими дисциплинами: алгебра (теория групп, теория конечных полей), теория случайных процессов, общая теория помехоустойчивого кодирования.

Требования к знаниям, умениям и навыкам, приобретаемым студентами в процессе изучения этой дисциплины, соответствуют квалификационной характеристике выпускника математического факультета университета и включают, в соответствии с ГОС @@@@071400:
– знание основных понятий,  принципов, законов и методов, применяемых при построении свёрточных кодов и параллельных каскадов, итерационных пороговых схем декодирования, предельных теорем кодирования;
– умение применять теоретические знания для решения типичных задач выбора структуры и параметров свёрточного, турбо и многопорогового (МПД) кодека, в т.ч. для каскадирования  турбокодека с МПД, в т.ч. для особо грязных каналов;
– навык  расчётов характеристик по параметрам и оптимизации параметров по заданным характеристикам.

Имеющийся у автора задел: опыт чтения лекций и проведения практических занятий по курсу «Защита информации» со студентами ЭиУ ЮУрГУ в 2004-2007 гг; публикация ряда статей в специальной литературе по теме курса (см. в списке литературы).

2.2. Содержание

Тема 1. ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О ДЕКОДИРОВАНИИ

(Определения) Критерии качества, в т.ч. вероятность ошибки; энтропия декодирования. Правило формирования решающих областей. Примеры метрик. Области Вороного.

(Обзор) Декодирование по критериям максимального математического ожидания вероятности (Котельников, Зигерт, Нейман и Пирсон, Галлагер, Мэсси и др.), в т.ч. с априорными вероятностями и с весами важности, наибольшего правдоподобия, минимума энтропии ошибки символа, минимума энтропии ошибки в целом, и др. типы «наблюдателей» (по Харкевичу §16).

(Обзор) Декодирование с априорной информацией по дополнительным критериям наименьшего расстояния в линейной абсолютной метрике, в квадратичной метрике, в метрике наибольшего, в негэнтропийной метрике.

(Вывод формул) Дискретный канал. Стационарный канал. Канал без памяти. Дискретный постоянный канал. Дискретный симметричный канал. Логарифмическая функция правдоподобия для ДСК. Лемма об эквивалентности в ДСК максимального правдоподобия и минимального расстояния Хэмминга.

(Вывод формул) Полунепрерывный канал с АБГШ. Логарифмическая функция правдоподобия для для ПНК с АБГШ. Лемма об эквивалентности в таком канале максимума правдоподобия, минимума евклидова расстояния и максимума скалярного произведения принятого и переданного.

(Обзор) Основные методы декодирования: полный («древнейший», «переборный», «перечислительный», «табличный», «отобразительный», «MP») метод декодирования и вычислительные затраты; «Монте–Карло» без вычёркивания, с вычёркиванием Бочека и вычислительные затраты; функциональный (в т.ч. прохождение упорядоченного дерева) и вычислительные затраты; мажоритарные однопороговые (простой однопороговый «повторы» Шиллинга–Якоби, 1954 Рида–Маллера, 1963 теория Питерсона–Берлекэмпа–Мэсси), циклические мажоритарные коды Гоппы, Сидельникова, «инь-ян» (Горшков 2007, противоинверсный вырожденный групповой линейный циклический случайный), инверсно-стойкий (вырожденный и блочный варианты) мажоритарно-зазеркальный (2007) жёсткий и мягкий, многопороговые Золотарёва (итеративное решение синдромного уравнения) жёские и мягкие, оценки вычислительных затрат; итеративное декодирование (1954, Элайес, iterated, в т.ч. 2- и многомерные, и его свойства : асимптотически верность растёт неограничено, скорость к конечному пределу), в т.ч многопроходное декодирование с мягким решением, итеративный мажоритарный алгоритм Рида (1954, для декодирования блоковых кодов Рида–Мюллера (Маллер, Muller)), способ Возенкрафта1955–Рейффена декодирования поточных кодов (теория Фано 1963, Зигангирова 1966, Джелинека 1969), итеративные алгоритмы Галлагера (разделимый систематический нециклический случайный 1962, для декодирования блочных с низкой плотностью проверок LDPC на чётность с итерацией наихудших и его свойства, в т.ч. группирование ошибок при малом отношении сигнал/помеха; зато асимптотически отношение кодового расстояния к значности стремится к ненулю, его варианты с N;3-мерными тензорами) и Маккея, алгоритм Колесникова и Мирончикова 1965 «последовательного мажоритарного декодирования» поточных кодов с бесконечно длинным «деревом», алгоритм Витерби 1967 максимального правдоподобия кодового слова, в т.ч. модифицированный SOVA, максимальной апостериорной вероятности бита Бала–Кока–Джелинека–Равива(1974) и его модификация Бэророу–Глэвиюкса–Титимажшимы SPA, проекционные варианты Качмажа, Бочека, Тараско, Абрамова, Горшкова, Елсакова, оценки вычислительных затрат. Дискуссия о других фундаментальных методах декодирования.

Теорема о невозможности исправления всех изменений в общем случае.

Вероятность ошибки для составных кодов (см. в Морелос-Сарагоса),  в т.ч. для параллельных каскадов. Дискуссия об оптимальной последовательности малоизбыточного и высокоизбыточного кодирований. Дискуссия, целесообразны ли 2-, 3- и более мерные  мажоритарные декодеры.

Декодер «с ограниченным расстоянием».

«Хорошее», «плохое» и «очень плохое» кодовое расстояние.
«Хорошие» («сильные») и «плохие» («слабые») коды.
Примеры «хорошего кода с плохим кодовым расстоянием», «плохого кода с хорошим кодовым расстоянием» и др. Доказательство «хорошего» поведения семейства каскадных декодеров на основе простых однопороговых мажоритарных в области низковерного в попытках, высоковерного в сеансе приёма с признаком истинности и обратной связью с неограниченным повтором.

Кратко (забегая вперёд): обзор нерешённых проблем создания "достоверных" кодов в общем случае.

Тема 2. СВЁРТОЧНЫЕ КОДЫ и ОБЗОР ВООБЩЕ ПОТОЧНЫХ

Принципиальная общая схема непрерывных кодов и свёрточных в частности. Место свёрточных кодов в классификации. Длина информационного кадра, задержка, длина кодового ограничения, длина кодового кадра, скорость кода; «конструктивная длина кода», «информационная длина слова», «кодовая длина блока». Инициализатор, терминатор.

Предварительные  замечания о преимуществах и недостатках свёрточных кодов по сравнению с блоковыми, мнение об области применения.

Формы представления свёрточных кодеров: аппаратная, «вокзал», многочлены и  тензор многочленов, векторы коэффициентов и тензор коэффициентов многочленов, древовидная, решётчатая, конечный автомат.

Весовой спектр свёрточного кода. Влияние кодовых слов малого веса на вероятность ошибки. Катастрофические кодеры, теорема о них. Свободное расстояние кода и его связь с исправляющей способностью и вероятностью ошибки.

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

Эквивалентность максимума правдоподобия и минимального пути на некотором орграфе (Форни, 1974). Методы его поиска. Полный перебор. Случайный перебор без вычёркивания, с вычёркиванием Бочека 1952. Упрощённый перебор. Принцип Беллмана о кратчайших путях через промежуточную точку.

Алгоритм Виттерби (1967), его эквивалентность максимуму правдоподобия (Омура, 1969). решётчатый граф Форни, ширина окна декодирования, терминаторы.
Случай усечённой (пресечённой, терминированной) последовательности; инициализация, конкуренция, выживание путей; реализация алгоритма на ярусах, не больших длины кодового ограничения. Случай бесконечных последовательностей; оптимизация окна декодирования; стратегии выбора невыродившихся путей при большой помехе. Декодер Виттерби для канала с мягким решением внутреннего декодера; оптимизация мягкости. Затраты на метрики путей; нормализация метрики; затраты на хранение путей.

(Обзор) Модифицированный алгоритм типа Виттерби  SOVA, максимальной апостериорной вероятности бита Бала–Кока–Джелинека–Равива(1974) и его модификация Бэророу–Глэвиюкса–Титимажшимы SPA.

(Обзор не только свёрточных, а вообще поточных кодеков) Код Финка_и_Шляпоберского(1955)–Хагельбергера(Хагельбаргера,1959), близость скорости кода к 1. Свёрточный код Элайеса (1955, convolutional) – Килмера (1960, «рекуррентный»). Способ Возенкрафта1955–Рейффена декодирования поточных кодов (теория Фано 1963, Зигангирова 1966, Джелинека 1969). Алгоритм Колесникова и Мирончикова 1965 «последовательного мажоритарного декодирования» поточных кодов с бесконечно длинным «деревом». Экономичный алгоритм Панюкова (90-е гг.). Высокошумные каналы, нелинейные поточные кодеки, алгоритм Горшкова с евклидовой метрикой с использованием субалгоритмов Качмажа, Бочека, Тараско, Абрамова, Горшкова, Елсакова. Мажоритарно-свидетельский (с прямым декодированием), мажоритарно-разностный и др. 2007 Горшкова жёсткие и мягкие.
(Ссылка на последующее МПД свёрточных кодов)

Тема 3. ТУРБО-КОДЕКИ и ОБЗОР ВООБЩЕ ПАРАЛЛЕЛЬНЫХ КАСКАДНЫХ

Место турбо-кодов в классификации. Параллельные каскады систематических свёрточных кодов с перемежением  Бэрроу 1993, Глэвиюкса, Титимажшимы и др. Эквивалентность некоторому блоковому коду.  Весовой спектр кода. Требование к перемежителям турбо-кода. Терминирование свёрток. Сравнение свойств турбо-кодеков с перемежителями: случайным равновероятным, произведение по модулю и др.

Сравнение разных элементарных кодеров в составе турбо.

Достоинства и недостатки турбо-кодеков. Области применения.

Не-турбо параллельные каскадные кодеки (обзор).

(Ссылка на последующее МПД свёрточных кодов)

Тема 4. «МНОГОПОРОГОВЫЕ» КОДЕКИ

Мажоритарное декодирование; области гарантированной и по вероятности исправляющей способности; вычислительные затраты; скорость. Итеративное декодирование; теорема Банаха о сжимающих отображениях; выбор метрик и отображений. Простые мажоритарные неитеративные кодеки (примеры кратко, в т.ч. Месси для самоортогональных кодов). Простые мажоритарные итеративные («многопороговые») кодеки Золотарёва.

Случай линейных систематических [блоковых, поточных, в т.ч. свёрточных] самоортогональных кодов в полунепрерывном канале с АБГШ.

Случай двоичного канала. Схема однопорогового кодека Месси. Схема МПД Золотарёва в случае двоичном, с жёстким решением внутреннего декодера. Регистры: информационный, синдромный, разностный; пороговый элемент. Алгоритм работы. Строгая сходимость к решению оптимального декодера без гарантии достижения в общем случае. Дискуссия об условиях гарантии достижения.

МПД Золотарёва для случая двоичного, с мягким решением.
МПД Золотарёва для недвоичного диофантова случая.

Достоинства и недостатки МПД по сравнению с кодами Рида–Соломона,  Хоквингема–Боуза–Рой-Чоудхури, свёрточными Виттерби, турбо, низкоплотностных и др.

Оптимизация последовательного каскадирования МПД с кодами с низкой и с высокой исправляющей способностью (обзор вычислительных экспериментов).

Каскадирование МПД со свёрточными и турбокодами.

Область применения МПД.

Тема 5. ДОСТОВЕРНЫЙ ПРИЁМ В ОСОБО ГРЯЗНЫХ КАНАЛАХ

Актуальность задачи. Разные определения энтропии. Обобщённая основная теорема кодирования (А.В.Г.?) и следствия из неё (Мак-Кей, Добрушин, Шеннон, Фэно, Котельников и др.). Верность приёма оптимальным декодером, оптимизация по скорости приёма кодеков: мономажоритарного, бимажоритарного Горшкова, со свидетелем Горшкова, ОФ-мажоритарного Петровича–Горшкова.

Тема 6. ДОСТОВЕРНОЕ РАСПОЗНАВАНИЕ СВОЙ-ЧУЖОЙ
В ОСОБО ГРЯЗНЫХ КАНАЛАХ.

Актуальность задачи. Теорема о предельных ошибках 1-го и 2-го родов в сколь угодно грязных каналах. Пример метода оптимального согласования избыточности с помехой для задачи распознавания по заданным критериям ошибок обоих родов для «оптимального» кодека.

Без темы (к сведению студентов). ОТДЕЛЬНЫЕ (при необходимости) СВЕДЕНИЯ (для повторения)

Основная теорема кодирования (с доказательством). Её следствия:
1) теорема Новикова о невозможности исправления всех возможных помех,
2) теорема Котельникова о невозможности помехоустойчивого приёма без избыточности,
3) теорема Агеева(1939)–Шеннона(1948) о максимальной скорости помехоустойчивого приёма,
4) основная теорема помехоустойчивого кодирования,
5) теорема Шеннона–Фэно об экономичном кодировании для бернуллиевского источника,
6) основная теорема секретного кодирования,
7) теоремы Котельникова(1941), Шеннона(1946), Фэно о секретном кодировании,
8) теорема Симмонса о мере сочетания секретного и достоверного кодирования,
9) дискуссия о связи с теоремой Варшамова–Гильберта,
10) дискуссия о связи с теоремой Косарева,
11) дискуссия о связи с теоремой Вольфа–Слепяна.

Роды сложности задачи кодирования и декодирования: вычислительная (по операциям), временная (по тактам), аппаратная (по потокам, глубине стека, по узлам, по памяти, по размерности процессора), Колмогоровская (алгоритмическая), экономическая.

Мера сложности: слабее линейной, линейная, полиноминальная и т.п., экспоненциальная и т.п., сильнее экспоненциальной.

Дискуссия о «совершенном браковании», теоретический предел.

Дискуссия о «совершенном восстановлении», теоретический предел.

Параметры и классификация кодов.

Непозиционные и позиционные.
По натуральному основанию ;2 и по ненатуральным основаниям.
Двоичный и недвоичные.
По значности (длине, позиционности) и т.п.
«Мощность» кода (как множества).
«Расстояние Хэмминга» между двоичными кодовыми словами; «вес» двоичного кода (как слова); «кодовое расстояние» («минимальное расстояние кода») двоичного кода (как множества).
Полный и неполный.
Равномерный и неравномерный.
С разделителями, с дополнительным каналом (стробы, часы и т.п.), без разделителей.
Неприводимые (префиксные) и приводимые.
Избыточный, безызбыточный, недостаточный (сокращающий); без потерь (принципиально обратимый) и с потерями (принципиально необратимый).
Подстановочный и перестановочный.
Детерминированный (вызывающие смысловую путаницу термины «функциональный», «конструктивный») и случайный (стохастический).
Неключезависимый и ключезависимый.
Симметричный/асимметричный по алгоритму/ключу.
Необнаруживающий/обнаруживающий помеху, неисправляющий помеху (бракующий) / исправляющий (восстанавливающий, Агеев 1935 ? ; за рубежом с 1949 Голей); дискуссия о кодах и кодеках, вносящих помеху, и областях их применения.
Исправляющие только независимые помехи и исправляющие зависимые помехи (в т.ч. пакеты помех, т.е. зависимые в позициях).
Согласованные с распределением помех, несогласованные.
• Коды «без памяти» (указать на парадоксальность такого названия):
; вырожденный («с единичной информационной ёмкостью», не вполне отличающие названия «поточный без памяти», «последовательный без памяти», «элементарный блоковый», «минимальный блоковый», «минимальный поточный»);
; блочный («блоковый», не вполне отличающие неудачные названия «прерывный», «параллельный»),  в т.ч. не вполне отличающе названный «полноблочный» («цельноблочный», «полнотекстовый»).
• Коды «с памятью» [точнее, неполной памятью]: поточный с конечной памятью («рекуррентный», «цепной», не вполне отличающие названия «непрерывный», «последовательный»), в том числе «оконный» («слайдовый», «скользящий», «древовидный», «ветвящийся», «непрерывный», «последовательный»).
Сделать примечание во избежание путаницы: один из блочных кодов Элайеса назван «скользящий, sliding» (а Фэно его назвал «конволюционный») из-за особенности кодека.
Основные параметры кодов без памяти: значность (длина, неудачный термин «позиционность»), скорость кода, (удельная) цена кода, информационное (значащее) содержание, избыточное содержание, избыточность, кодовое расстояние, обнаруживающая способность, исправляющая способность.
Основные параметры кодов с памятью, причём оконных: длина кодового ограничения («длина окна»), конструктивная длина, скорость кода, (удельная) цена кода, информационное (значащее) содержание, избыточное содержание, избыточность, свободное расстояние, обнаруживающая способность, исправляющая способность.
• Разделимые («разделённые», «сепарабельные») коды:
; систематические («с проверками на чётность»):
o линейные: порождающая матрица и эквивалентные коды, проверочная матрица, синдром, граница Синглтона и линейные коды «с максимальным расстоянием»;
o нелинейные;
; также систематические коды подразделяют на несамоортогональные
; и самоортогональные (self-dual, «самосопряжённые, самодвойственные»);
; несистематические.
• Неразделимые коды.

Сделать примечание: поточные линейные коды называют «свёрточные», «конволюционные».

Нециклические, циклические Прейнджа 1957 (сдвиги разрешённых не выводят из множества разрешённых; по Харкевичу же не о разрешённых, а о кодовых векторах вообще).

Систематические (причём обычно линейные), причём циклические, коды; производящий многочлен, примитивная длина, проверочный многочлен, синдромный многочлен, многочлен ошибок, «эффективность». Для систематических линейных циклических – эквивалентные многочленам матрицы. Теорема о монотонном росте обнаруживающей способности с ростом степени порождающего полинома.

Групповые (метод Слепяна 1956), негрупповые. Лемма: любой групповой двоичный код является систематическим. Стандартное расположение группового кода.

Эквидистантные (разновидность линейных) коды: ортогональный двузначный, биортогональный трёхзначный, симплексный («М-коды»: «тетраэдры» в 3-мерном и N-мерные;  1950 Райс; стойкость к белому шуму 1955-1958 Блох, Харкевич, Игнатьев (?);  теорема Котельникова о заведомо ограниченной скорости безошибочного приёма с симплексными сигналами и помехой). Теорема о числе вершин симплекса в N-мерном пространстве. Связь эквидистантных кодов с матрицами Адамара.

Частотно-компактные (согласование с фильтрами, уменьшение внеполосных излучений) и расширяющие Фурье-спектр (уменьшение вероятности коррелированных помех). Сделать примечание: не путать со «спектром кода» – распределением весов Хэмминга слов кода.

Производные коды: расширенный (добавление символов, увеличение расстояния), укороченный (сокращение информационных символов, расстояние неизменно), выколотый («перфорированный», исключение некоторых символов).

Простые («цельные», «непроизводные») коды
и составные: блоковые произведения («коды-произведения», неудачность запутывающего названия «блоковый турбо, матричный турбо») 2-мерные, N-мерные; каскадные (последовательные каскады Форни 1954, их теория Блоха–Зяблова 1966 и др.; параллельные «турбо» каскады Бэрроу и др. 1993 ). Внешние и внутренние коды в последовательных каскадах.

2.3. СПИСОК ЛИТЕРАТУРЫ, РЕКОМЕНДУЕМОЙ УЧАЩИМСЯ

1. Харкевич А.А. Борьба с помехами. М.: «Наука». 1965. С.276.
2. Прохоров Ю.В. Канал связи. // В сб.: Математич. энциклопедический словарь. М., Научное издательство "Большая Российская Энциклопедия". 1995. Гл.ред. Ю.В. Прохоров. 847 С.
3. Соловьёва Ф.И. Введение в теорию кодирования. Новосибирск, 2006. 124 с.
4. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.:  «Техносфера». 2005.
5. Золотарёв В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник./Под ред. чл.-корр. РАН Ю.Б. Зубарева. М.: «Горячая линия – Телеком», 2004. 126с.
6. Золотарёв В.В. Теория и алгоритмы многопорогового декодирования. М.: Радио и связь, 2006.
7. Золотарёв В.В. Многопороговые декодеры для систем связи с предельно малой энергетикой сигнала.
8. Гоппа В.Д. Введение в алгебраическую теорию информации. М.: Физматлит, 1995. 112 с. [в т.ч. молекулярно-биологические]
9. Варгаузин В. Вблизи границы Шеннона. // Телемультимедиа. 2005. Июнь.
10. Золотарёв В.В. Субоптимальные многопороговые декодеры для канала с большим уровнем шума.
11. Кулик И.А., Супрун А.В., Голофост И.В. Мажоритарное использование помехоустойчивых кодов. // СМКЭС-2004. С.63-64. 2004.
12. Зубарев Ю.Б., Золотарёв В.В., Овечкин Г.В. Обзор методов помехоустойчивого кодирования с использованием многопороговых алгоритмов. // Цифровая обработка сигналов. 2008. №1.
13. Золотарёв В.В., Овечкин Г.В. Эффективные алгоритмы помехоустойчивого кодирования для цифровых систем связи. // Электросвязь. 2003. №9. с.34.
14. Горшков А.В. Логарифмически небольшое отличие скорости инверсно-стойкого мажоритарного каскада от пропускной способности в очень грязных каналах. / Труды 4-го Международного форума (9-й Международной конференции молодых учёных и студентов) "Актуальные проблемы современной науки". 2008. Секция «Радиотехника и связь». Самара: Изд-во СамГТУ, 2008.
15. Горшков АВ Оценки практически достижимой скорости помехоустойчивого приёма в сколь угодно грязных каналах в однонаправленных системах без априорной информации о сообщении, а также в двунаправленных с признаком истинности декодирования. / Направлено в печать. 2008.
16. D. J.C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. 2003.
17. Финк Л.Н. Теория передачи дискретных сообщений. М.: Советское радио, 1970.
18. Каган Б.Д., Финк Л.М. Метод последовательного приёма в целом, для кодов, допускающих мажоритарное декодирование. // Электросвязь, 1967. №1. С.14-22.
19. Рюмшин К.Ю. Особенности построения и анализа турбокодов. // Сборник трудов международной конференции "Актуальные проблемы современной науки". Самара, СамГТУ, сентябрь 2003. Секция радиотехники.
20. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987.
21. Кузьмин И.В. Основы теории информации и кодирования. Минск:  Вышейшая школа,1986.
22. Кассами Т. Теория кодирования. М.: Мир, 1978.
23. Аршинов М.Н., Садовский Л.Е. Коды и математика (рассказы о кодировании). М.: Наука, 1983. 144 с.
24. Берлекэмп Э.Р. Алгебраическая теория кодирования. М.: Мир, 1971. 477 с.
25. Блэйхут Р. Теория и практика кодов, контролирующих ошибки. / Пер. с англ. М.: Мир, 1986. 576 с.
26. Блох Э.Л., Харкевич А.А. [перемежение и независимость помех] // Электросвязь. 1960. №9.
27. Физический энциклопедический словарь. Ред. А.М. Прохоров. М., БРЭ. 1991.
28. Харкевич А.А. Информация и техника. // Коммунист. 1962. №12.
29. Самойленко С.И., Давыдов А.А., Золотарёв В.В., Третьякова Е.И. Вычислительные сети. М.: Наука, 1981. 278 С.
30. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. -СПб.: Издательство «Питер», 1999.
31. Олифер В.Г., Олифер Н.А. Сетевые операционные системы. -СПб.: Издательство «Питер», 2002.

3. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
«СВЁРТОЧНЫЕ И ТУРБОКОДЫ И МНОГОПОРОГОВОЕ ДЕКОДИРОВАНИЕ»

3.1. ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ ,
в т.ч. 3.2. ТЕМЫ ЛЕКЦИОННОГО КУРСА

№ Тема Лекционных часов Лаб. и практ. работ Само-стоя-тельная работа

1 Современный желаемый диапазон верности, скорости приёма, аппаратных и вычислительных затрат.  «Хорошие» и «плохие» кодовые расстояния, «сильные» и «слабые» коды и их сочетания. 2 2
2 Краткий обзор общих методов восстанавливающего декодирования и критериев качества. Неитеративные: перебор, Монте-Карло, аналитический функциональный, мажоритарные однопороговые, особенности циклических мажоритарных. Итеративные: мажоритарные со свидетелем, мажоритарные «многопороговые», низкоплотные, прослеживаемые, проекционные. 4 2
3 Построение свёрточного кода. Переборные методы декодирования. 2 2 2
4 Алгоритм Виттерби, его оптимизация. 2 2 4
5 Краткий обзор поточных кодеков Финка–Шляпоберского, Возенкрафта, Колесникова–Мирончикова, Панюкова, проекционные. Сравнение. 4 4

6 Построение турбокода. Вероятность ошибки оптимального декодирования в последовательных и в параллельных каскадах. 2 2 2
7 Сравнение различных перемежителей при фиксированном кодеке струи. 2 2 2
8 Сравнение различных кодеков струй при фиксированном перемежителе. 2 2 2

9 Многоитерационный мажоритарный декодер. Сравнение с обычными блоковыми, 1-итерационными мажоритарными, свёрточными типа Виттерби, турбо, низкоплотностными. 2 2 4
10 Каскадирование МПД со свёрточными. 2 2 2
11 Каскадирование МПД с турбо 2 2 2

12 Обобщённая основная теорема кодирования и следствия из неё. 2 2
13 Высоковерный приём в особо грязных каналах. Противоинверсные кодеки и их оптимизация в каскадах. Однопороговые 0,1-итерационные мажоритарные кодеки. 4 2 4
14 Достоверное распознавание в особо грязных каналах. 2 2

Зачёт
ВСЕГО  90 часов, в том числе 34 18 38

3.3. ЛАБОРАТОРНЫЕ И ПРАКТИЧЕСКИЕ РАБОТЫ

Также в форме очных потоковых заданий по оптимизации параметров по заданным характеристикам, кодированию/декодированию.
1. Свёрточные кодеки.
a. Построение материнского свёрточного кодера
b. Оценка его спектра
c. Катастрофический кодер
d. Нематеринский кодер
e. Переборный декодер
f. Декодер Виттерби.
g. (Дополнительно) Декодер Возенкрафта и другие (по выбору).
2. Турбо-кодеки.
a. Построение перемежителей и турбокодека (на свёртках).
b. Сравнение перемежителей.
c. Сравнение разных кодеков струй.
3. МПД.
a. Построение МПД-кодека и сравнение с другими.
b. Исследование свойств каскадов МПД+свёрточный, свёрточный+МПД.
c. Исследование свойств каскадов турбо+МПД(элементарные по выбору), МПД+турбо(элементарные по выбору), МПД+турбо+МПД(элементарные по выбору).
4. Высокодостоверный приём в особо грязных каналах и достоверное распознавание свой/чужой и опознавание.
a. Построение изолиний диаграммы верности помехоустойчивого кодирования.
b. Исследование противоинверсных и 0,1-итерационных однопороговых мажоритарных кодеков (по вариантам) в модели особо грязного канала.
c. (Дополнительно) Достоверное распознавание «свой–чужой», опознавание «конкретный из множества своих – чужой» в модели особо грязного канала с непреднамеренной помехой.
d. (Дополнительно) Построение изолиний диаграммы верности обобщённого кодирования; пример (по выбору) стохастического помехоустойчивого частично секретного кодирования с секретным ключом.

3.4. ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

3.4.1. Методические рекомендации
Формы самостоятельной работы:
1. Чтение рекомендованной литературы, журналов, а также поиск в Internet.
2. Решение домашних задач.
4. Написание и защита рефератов.
5. Исследовательская работа под руководством автора курса (по желанию).

3.4.2. Список тем рефератов
Для студентов, пропустивших лекции – по теме лекции (без дополнительной оценки).
Для студентов, желающих углублённого освоения темы – по указанию преподавателя (на дополнительную оценку).

4. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ О КОНТРОЛЕ
ЗНАНИЙ, УМЕНИЙ, НАВЫКОВ СТУДЕНТОВ

Виды контроля.
1. Устный опрос.
2. Публичное решение задач.
3. Проверка выполнения лабораторно-практических заданий в форме очных контрольных работ (потоком).
4. Проверка и публичная защита рефератов.
5. Проверка и публичная защита исследовательских работ.
6. Зачёт.

Посещаемость занятий обязательно 100%, за пропуск (по неуважительной причине) студент обязан выполнить и защитить реферат.

Инициативное выдвижение полезной идеи, даже без последующей её реализации, добавляет дополнительно 5 баллов.

За добровольные рефераты дополнительно до 5 баллов.

За успешную исследовательскую работу 5 баллов и более того.

К участию в НИОКР желающие студенты допускаются преподавателем вовсе не с первых дней, а лишь спустя несколько недель от начала курса, по принципу философа Кун-Фу-цзы «изучать что-либо и не задумываться над этим – бесполезно, но задумываться над чем-либо, не изучив предварительно предмет раздумий – опасно»; причём только достаточно хорошо успевающие по курсу, потому что даже для отличников НИР является весьма значительной нагрузкой, могущей повредить учебному процессу в случае передозировки; однако посильная тематика для хорошо успевающего студента стимулирует его комплексное развитие и самостоятельное мышление; успешная защита вызывает также и положительные эмоции, также способствующие всему хорошему. При успешном выполнении исследовательской работы студент, по существу, не нуждается в процедуре зачёта и он, по усмотрению преподавателя, может быть выставлен «автоматом» или после контроля вызывающих сомнение тем (например, вследствие пропусков).

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

(2008 г.)