экзамен / kekzamenypoPK_IKTY-9798

Вопросы к экзамену по дисциплине «Помехоустойчивое кодирование в инфокоммуникационных системах».

(гр. ИКТУ - 97,98)

1. Помехоустойчивое кодирование. Назначение. Основные термины, определения и характеристики кода. Классификация помехоустойчивых кодов. Место расположения помехоустойчивого кодирования в обобщенной структурной схеме системы передачи сообщений.

2. Ошибки в канале и причины их возникновения. Модели ошибок в дискретных каналах связи. Эффективность помехоустойчивого кодирования. Энергетический выигрыш в каналах АБГШ.

3. Блочные коды с обнаружением ошибок. Оценка корректирующих свойств (n,k)-кода в зависимости от минимального расстояния . Общие выражения для вероятностей правильного приема, приема с обнаруженными кодом ошибками и приема с необнаруженными ошибками в двоичном симметричном канале.

4. Двоичный код с проверкой на четность и его характеристики. Матричное представление. Корректирующие способности кода. Принципы декодирования. Реализация кодера и декодера.

5. Блочные двоичные помехоустойчивые коды с обнаружением ошибок с формированием построчной контрольной суммы по модулю 2. Способность такого кода по обнаружению ошибок. Вероятностные характеристики.

6. Блочные двоичные помехоустойчивые коды байтовой структуры с формированием контрольных проверочных элементов путем суммирования строк и столбцов по модулю 2. Способность такого кода по обнаружению ошибок. Вероятностные характеристики.

7. Блочные байтовые двоичные помехоустойчивые коды с обнаружением ошибок с формированием контрольной суммы по модулю 255 (протокол ХМодем). Способность такого кода по обнаружению ошибок. Вероятностные характеристики.

8. .Принципы обнаружения ошибок в протоколах Интернет на транспортном и межсетевом уровнях. Алгоритмы вычисления контрольной суммы кодером и принятия решения декодером об отсутствии ошибок. Способность таких кодов по обнаружению ошибок.

9. Систематические циклические коды с простой циклической проверкой CRC-m с нулевыми исходными состояниями ячеек регистра с обратной связью. Алгоритмы кодирования и декодирования комбинаций систематических циклических (n,k)-кодов. Принципы обнаружения ошибок. Способности кода по обнаружению ошибок.

10. Систематические циклические коды с расширенной циклической проверкой CRC с составным порождающим многочленом G(x)=(x+1)P(x).. Алгоритмы кодирования и декодирования комбинаций таких систематических циклических (n,k)-кодов. Оценка способностей таких кодов по обнаружению ошибок.

11. Нециклические (псевдоциклические) коды с проверкой CRC с составным порождающим многочленом G(x)=(x+1)P(x) и с предварительной установкой ячеек регистра кодера и декодера в единичные состояния. Алгоритмы кодирования и декодирования комбинаций таких систематических псевдоциклических (n,k)-кодов. Оценка способностей таких кодов по обнаружению ошибок.

12. Нециклические (псевдоциклические) коды с проверкой CRC с составным порождающим многочленом G(x)=(x+1)P(x) и с предварительной установкой ячеек регистра кодера и декодера в единичные состояния. Алгоритмы кодирования и декодирования комбинаций таких систематических псевдоциклических (n,k)-кодов. Оценка способностей таких кодов по обнаружению ошибок. Доказать – почему такие коды считаются псевдо- циклическими.

13. Синдромы комбинаций циклических кода БЧХ и Рида-Соломона, их назначение и вычисление. Алгоритм Горнера.

14. Циклические коды БЧХ. Построение порождающего многочлена кода, исправляющего до t ошибок включительно. Порождающая и проверочная матрицы систематического кода БЧХ. Рассмотреть на примере: длина информационной комбинации n=14, t=2, поле Галуа образовано примитивным многочленом P(x) = 1 +x³+ x⁴.

15. Многочлен локаторов ошибок циклического кода БЧХ. Две формы представления многочлена локаторов ошибок. Чем они отличаются? Процедура Ченя нахождения ошибочных позиций.

16. Принцип декодирования циклических кодов БЧХ на основе тождеств Ньютона. Ключевое уравнение. Алгоритм Питерсона-Горинстейна-Цирлера.

17. Циклические коды Рида-Соломона. Отличия от кодов БЧХ. Построение порождающего многочлена кода, исправляющего до t ошибок включительно. Синдромы циклического кода Рида-Соломона. Показать на примере.

18. Построение проверочной матрицы кода Рида-Соломона. Привести пример для кода Рида-Соломона над полем GF(2⁴) c длиной комбинации n=15, исправляющего t≤3 ошибочных элементов кода. Многочлен, образующий поле GF(2⁴), например, имеет вид:

P(x)= 1+x³ +x⁴.

19. Ключевое уравнение циклического кода Рида-Соломона. Исправление ошибок. Формула Форни.

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

21. Диаграмма состояний сверточного кода и анализ весового спектра кода на основе формулы Мэзона-Циммермана.

22. Алгоритм Витерби декодирования сверточных кодов.

23. Принципы построения каскадных кодов. Их достоинство и недостатки.

Рассмотреть пример построения двухкаскадного внешнего кода Рида-Соломона над полем GF(2³) с образующим многочленом P(x)=1+x+x³ и внутренним кодом БЧХ (7,3) с тем же образующим поле многочленом.

24. Анализ каскадного помехоустойчивого кодирования в системе передачи информации реального времени РАВИС.

25. Помехоустойчивое кодирование в системах наземного цифрового телевизионного вещания европейского стандарта DVB-T, DVB-T2.

26. Построение циклических кодов с мажоритарным декодированием.

27. Коды с малой плотностью проверок на чётность (МППЧ). Принципы построения. Алгоритм кодирования. Алгоритм декодирования с «жёстким» принятием решения (алгоритм с перевертыванием битов).

28. Перемежение в системах помехоустойчивого кодирования. Назначение, принципы построения. Плюсы и минусы.

29. Скремблирование в цифровых системах передачи информации. Назначение. Алгоритмы скремблирования и дескремблирования. Сравнение. Принципы реализации.

Задачи к экзаменационным вопросам.

1. Необходимо построить классический систематический циклический (n,k)-код, у которого n=14. Определить наибольшее значение k при условии, что код должен исправлять однократные ошибки. Выбрать для такого кода порождающий многочлен и построить порождающую матрицу.

2. Изобразить схему кодирующего устройства классического систематического циклического кода (n,k), исправляющего однократные ошибки, с порождающим многочленом P(x)=1+x+x⁴ и длиной комбинации n = 13.

3. Изобразить схему кодирующего устройства классического несистематического циклического кода (n,k), исправляющего однократные ошибки, с порождающим многочленом P(x)=1+x³+x⁴ и длиной комбинации n = 12.

4. Построить образующую и проверочную матрицы классического систематического циклического кода (n,k)=(13,9), исправляющего однократные ошибки, с порождающим многочленом P(x)=1+x+x⁴.

5. Построить образующую и проверочную матрицы несистематического циклического кода (n,k)=(12,8), исправляющего однократные ошибки, с порождающим многочленом P(x)=1+x³+x⁴.

6. Необходимо построить классический несистематический циклический (n,k)-код, у которого n=12. Определить наибольшее значение k при условии, что код должен исправлять однократные ошибки. Выбрать для такого кода порождающий многочлен и построить порождающую матрицу.

7. Построить поле Галуа GF(2⁵) с образующим примитивным многочленом P(x)=1+x²+x⁵. Определить количество первообразных элементов поля и число возможных примитивных многочленов пятой степени.

8. Процедура нахождения наибольшего общего (НОД) делителя двух чисел алгоритмом Евклида. Привести последовательность действий алгоритма. Найти по алгоритму Евклида НОД чисел 525 и 321.

9. Имеется непрерывный канал с АБГШ с полосой пропускания W=3КГц. Какая будет пропускная способность (бит/с) такого канала, если соотношение сигнал/ шум в канале равно 10дБ?

10. Разложить двучлен на минимальные многочлены. Определить корни минимальных многочленов как элементов расширенного поля GF(2⁴) с образующим поле полиномом f(x) = x⁴+x³+1. Определить двойственные минимальные многочлены и их корни.

1. Задачи по сверточным кодам:

1.1. Нарисуйте схему сверточного кодера, изобразите соответствующую ему древовидную и решетчатую диаграммы кода с относительной скоростью передачи равной 1/3 при кодовом ограничении К=3 и следующих полиномах связей:

• g₂(x) = 1 + x;

• g₃(x) = 1 + x + x²;

• g₁(x) = x + x² .

Составьте образующую матрицу данного сверточного кода.

1.2. Изобразите диаграмму состояний и решетчатую диаграмму для сверточного кодера, схема которого представлена ниже:

1.3. Дан сверточный кодер:

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

1.4. Для сверточного кодера

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

2. Задачи на циклическое кодирование в соответствии с протоколом HDLC (с единичными исходными состояниями ячеек регистра деления)

2.1. Задан систематический циклический (n,k) = (7.4)-код с образующим полиномом P(x) = 1+ x² + x³ и единичными исходными состояниями ячеек регистра деления. Пусть на вход кодера поступает нулевая комбинация. Определить комбинацию, которая появится на выходе кодера, используя математические преобразования.

2.2. Задан систематический циклический (n,k) = (7.4)-код с образующим полиномом P(x) = 1+ x² + x³ и единичными исходными состояниями ячеек регистра деления. Пусть на вход кодера поступает комбинация (1001). Нарисуйте схему кодера и покажите в потактовом режиме формирование выходной последовательности. Представьте полученную комбинацию в виде полинома f(x).

2.3. Пусть задан систематический циклический (n,k) = (7.4)-код с образующим полиномом P(x) = 1+ x² + x³ и единичными исходными состояниями ячеек регистра деления. Определить, какой будет получен синдром после декодирования разрешённой комбинации кода с ошибкой в пятом разряде, т.е. e(x) = x⁵.

2.4. Задан систематический циклический (n,k) = (7.4)-код с образующим полиномом P(x) = 1+ x² + x³ и единичными исходными состояниями ячеек регистра деления. Пусть на вход декодера поступили комбинации: h₁(x) =1 + x² и h₂(x) = 1 + x² +x⁵. Определить, есть ли в этих комбинациях ошибки.

2.5. Пусть задан систематический циклический (n,k) = (7.4)-код с образующим полиномом P(x) = 1+ x² + x³ и единичными исходными состояниями регистра деления. Изобразить схему декодера и в потактовом режиме декодировать комбинацию h(x) = 1 + x³ + x⁴ + x⁶ и сделать вывод – имеются в принятой комбинации ошибки или нет.

6. Задан псевдоциклический систематический код (n,k) = (7,4) с порождающим многочленом P(x)=1+x+x³ и единичными исходными состояниями ячеек регистра деления.

Пусть от источника передана некоторая разрешенная кодовая комбинация f(x)=1+х²+х⁴. В канале переданная кодовая комбинация сложилась по модулю 2 с многочленом ошибок e(x)=1+x⁴+x⁵, т.е. комбинация на входе декодера будет иметь вид h(x)= f(x)+ e(x).

Используя математические преобразования, покажите, какое решение примет декодер – а) ошибки в принятой комбинации h(x) не обнаружены; или б) ошибки в принятой комбинации обнаружены.

6. Задан псевдоциклический систематиче код (n,k) с порождающим многочленом P(x) степени (n-k) и единичными исходными состояниями регистра деления..

Пусть от источника передана некоторая разрешенная кодовая комбинация f(x). В канале переданная кодовая комбинация сложилась по модулю 2 с многочленом ошибок e(x)=g(x)P(x), где степень g(x) меньше или равна k., т.е. комбинация на входе декодера будет иметь вид h(x)= f(x)+ e(x).

Используя математические преобразования, покажите, какое решение примет декодер – а) ошибки в принятой комбинации не обнаружены; или б) ошибки в принятой комбинации обнаружены

6. Задан псевдоциклический систематический код (n,k) = (7,4) с порождающим многочленом P(x)=1+x+x³ и единичными исходными состояниями регистра деления.

Пусть от источника передана некоторая разрешенная кодовая комбинация f₁(x). В канале переданная кодовая комбинация сложилась по модулю 2 с некоторой другой разрешенной комбинацией f₂(x), т.е. комбинация на входе декодера будет иметь вид h(x)= f₁(x)+ f₂(x).

Используя математические преобразования, покажите, какое решение примет декодер – принадлежат ли данная комбинация h(x) к числу разрешенных или запрещенных.

1. Определить порождающий многочлен систематического циклического кода БЧХ, длиной n = 2^m − 1, где m=4, с исправлением двукратных ошибок (t=2) в предположении, что примитивный элемент  поля GF(2^m) является корнем минимальной функции m₁(x)=1 + x³ + x⁴.

2. Построить порождающую матрицу систематического циклического кода БЧХ, длиной n = 2^m − 1, где m=4, с исправлением двукратных ошибок (t=2), в предположении, что примитивный элемент  поля GF(2^m) является корнем минимальной функции m₁(x)=1 + x + x⁴.

3. Построить проверочную матрицу систематического циклического кода БЧХ, длиной n = 2^m − 1, где m=4, с исправлением двукратных ошибок (t=2), в предположении, что примитивный элемент  поля GF(2^m) является корнем минимальной функции m₁(x)=1 + x³ + x⁴.

4. Построить порождающую матрицу несистематического циклического кода БЧХ, длиной n = 2^m − 1, где m=4, с исправлением двукратных ошибок (t=2), в предположении, что примитивный элемент  поля GF(2^m) является корнем минимальной функции m₁(x)=1 + x + x⁴.

5. Построить проверочную матрицу несистематического циклического кода БЧХ, длиной n = 2^m − 1, где m=4, с исправлением двукратных ошибок (t=2), в предположении, что примитивный элемент  поля GF(2^m) является корнем минимальной функции m₁(x)=1 + x³ + x⁴.

6. Пусть имеется циклический код БЧХ с длиной комбинации n=15, исправляющий до 3 ошибок включительно (t=3). Поле GF(2^m) построено по модулю многочлена P(x)=1 + x + x⁴. Принятая комбинация имеет вид: h(x)= x + x⁴ + x⁶. Используя элементы поля, вычислить синдромы принятой комбинации.

7. Пусть имеется циклический код БЧХ с длиной комбинации n=15, исправляющий до 3 ошибок включительно (t=3). Поле GF(2^m) построено по модулю многочлена P(x)=1 + x + x⁴. Принятая комбинация имеет вид: h(x)=1 + x + x² + x³ + x⁵ + x⁶ + x⁸ + x¹². Используя алгоритм Горнера, вычислить синдромы принятой комбинации.

8. Определить порождающий многочлен циклического кода Рида-Соломона длиной n=15 c исправлением двух ошибочных элементов поля GF(2⁴), образованного примитивным элементом , являющегося корнем примитивного многочлена P(x)=1 + x + x⁴.

9. Построить поле Галуа GF(2⁵) с образующим примитивным многочленом P(x)=1 + x² + x⁵. Определить количество первообразных элементов поля и число возможных примитивных многочленов пятой степени.

Литература.

1.Когновицкий О. С., Охорзин В. М., Владимиров С. С. Практика помехоустойчивого кодирования. Часть 1. Системы с обнаружением ошибок и обратной связью…СПбГУТ, СПб, 2018 г.

2. Когновицкий О. С., Охорзин В. М. Теория помехоустойчивого кодирования. Часть 1. Циклические коды. Учебное пособие. СПбГУТ, СПб, 2013 г.

3. Когновицкий О. С., Охорзин В. М., Небаев И. А. Практика помехоустойчивого кодирования. Часть 2. Сверточные коды, турбокоды. Учебное пособие.…СПбГУТ, СПб, 2015 г.

4. Презентации лекций по дисциплине ПКв ИКС.

10