Занятие №6 Исследование корректирующих способностей систематических кодов

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

Построить порождающую и проверочную матрицы для систематического кода длиной n = 15, исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации М₄₃ = 0101011. Провести декодирование полученной избыточной кодовой комбинации. Провести исследования корректирующей способности кода для однократных и двукратных ошибок, используя проверочную матрицу.

Решение.

• При построении порождающей матрицы воспользуемся основными правилами, согласно которым порождающая матрица имеет вид

Проверочная матрица получается из исходной Р_(15,7) и имеет вид

2. Покажем процесс получения разрешенной кодовой комбинации для исходной М₄₃ = 0101011 с использованием порождающей матрицы.

В₄₃=М₄₃*Р_(15,7)=1*010000010101010+1*000100010011001+1*00001010100101 + 1*000000111000011 = 0101011 01010101

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

S_i = H_(15,7) * B₄₃= 10101010 + 10011001 + 10100101 + 11000011 + 01000000 + + 00010000 + 00000100 + 00000001 = 0000 0000

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

Пусть в 3 разряде (а₃) принятой кодовой комбинации произошла ошибка. Тогда кодограмма представляется следующим образом

В₄₃^* = 0 1 1 1 0 1 1 0 1 0 1 0 10 1

Определим синдром ошибки

S_i = H_(15,7) * B₄₃^* = 10101010 + 11001100 + 10011001 + 10100101 + 11000011 + + 01000000 + 00010000 + 00000100 + 00000001 = 1100 1100

Полученнй синдром отличен от нуля. Следовательно, принятая кодовая комбинация не является разрешенной. Для определения местоположения ошибки обращаемся к проверочной матрице. Данный синдром соответствует третьей строке проверочной матрицы, что позволяет сделать вывод – ошибка произошла в третьем разряде. Тогда вектор ошибка

Е = 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

Для корректировки результата необходимо к принятой кодовой комбинации прибавить по модулю 2 вектор ошибки. Результатом будет.

В₄₃^* = 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1

Е = 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

В ₄₃ = 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1

Пусть произошла двукратная ошибка в а₄ и а₇. Тогда принятая комбинация имеет вид В₄₃^*= 0100010 01010101. Определим синдром ошибки.

S_i = H_(15,7) * B₄₃^*= 10101010 + 10100101 + 01000000 + 00010000 + 00000100 + + 00000001 = 0101 1010

Синдром отличен от нуля. Однако данная комбинация отсутствует в проверочной матрице. Это позволяет сделать вывод о том, что полученная кодовая комбинация содержит ошибку, кратность которой больше 1. Для определения местоположения ошибки необходимо произвести попарное суммирование по модулю 2 строк проверочной матрицы. Сумма четвертой и седьмой строк равна синдрому ошибки. Следовательно, ошибочными являются 4 и 7 разряды кодовой комбинации В₄₃^*, а вектор ошибки имеет вид

Е = 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0.

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

В₄₃^* = 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1

Е = 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0

.В₄₃ = 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1

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

Задание

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

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

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

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

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

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

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

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

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

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

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

Вопросы

1. Определение корректирующих кодов.

2. Классификация кодов.

3. Основные показатели корректирующих кодов.

4. Систематические коды и их свойства.