Занятие №7. Исследование процесса кодирования и декодирования систематических кодов на основе проверочных уравнений

Теоретическая часть

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

1. В число этих кодограмм не должна входить нулевой.

2. Кодовое расстояние между двумя любыми парами больше либо равно d(min).

3. Каждая исходная комбинация должна содержать количество единиц больше либо равно d(min), т.е. вес ее должен быть равным либо превышать d(min).

4. Все исходные кодовые кодограммы должны быть линейно независимы (ни одна из них не должна представлять сумму других исходных кодограмм)

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

k первых столбцов являются информационными ;  последних столбцов являются проверочными символами;

Матрица P(n,k) является порождающей (образующей). Данную матрицу можно представить в виде двух матриц:

- информационной (размером k x k);

- проверочной.

Для построения порождающей матрицы информационную матрицу удобно представить в виде единичной матрицы (единицы по диагонали). Проверочная матрица должна строиться с соблюдением следующих условий:

1. Количество единиц должно быть не меньше равно d(min) - 1.

2. Сумма по модулю два любых двух комбинаций (строк) должна содержать не менее d(min) - 2 единиц.

Проверочные символы образуются за счет линейных операций над информационными символами. Для каждой кодовой комбинации должно быть построено  независимых сумм по модулю два. Весьма удобно проверочные суммы составлять с помощью проверочной матрицы согласно алгоритма:

1. В начале строится проверочная часть порождающей матрицы.

2. Затем снизу дописывается единичная матрица.

Произведение порождающей матрицы на проверочную матрицу равно нулю.

P(n,k)* H^*() = 0

Совокупность комбинаций линейного кода - есть множество разрешенных последовательностей B_i для которых произведение B_i* H^*() = 0, где B_i - матрица строка.

Алгоритм определения проверочных символов следующий:

1. Позиции, занимаемые в первом столбце должны участвовать в формировании первого проверочного символа.

2. Единицы во втором столбце участвуют в формировании второго проверочного символа.

3. Алгоритм продолжается для всех ρ столбцов матрицы.

4. В результате получается ρ проверочных уравнений, позволяющих определить значения проверочных символов в кодограмме.

Задание

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

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

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

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

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

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

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

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

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

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

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

Вопросы

1. Помехоустойчивые коды и их классификация

2. Корректирующие способности кодов

3. Минимальное кодовое расстояние и его связь с d_min.