Тема: Помехоустойчивое кодирование. Коды Рида – Соломона
Задание:
1) Ознакомится с теоретическим материалом ( краткое введение приведено ниже).
2) Создать скрипт в Mathcad, осуществляющий кодирование для приведенного ниже примера.
3) Создать скрипт, осуществляющий декодирование ( с проверкой на синтетических тестах)
Коды Рида-Соломона относятся к недвоичным, блочным, помехоустойчивым кодам и могут использоваться в области хранения информации для избегания потери поврежденной информации. Предупреждаю, что данный подход не будет рационален во многих случаях, но позволит реализовать помехоустойчивое кодирование данных с варьируемым процентом восстанавливаемой информации.
При работе с кодами Рида-Соломона процент избыточных символов в 2 раза больше восстанавливаемого объема данных. Объясню на примере: если мы имеем последовательность из 10 символов и хотим иметь возможность восстановить ошибки в 3ех из них (30% исходной информации), то нам нужно хранить 10+3*2=16 символов. Назовем каждую переменную: n – 10, количество информационных символов; f – 3, количество восстанавливаемых символов; g – 16, длина закодированной последовательности. Таким образом, формулу можно записать так: g = n + f * 2. Данные ходы компактнее кодов Хемминга на 1 символ.
Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа. Таким образом, результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т. е. количество его элементов, является некоторой натуральной степенью характеристики pm, где m N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m, такое поле называется расширенным. GF(pm) – обозначение поля Галуа.
Для работы с цифровыми данными естественно использовать p=2 в качестве характеристики поля. При m=1 элементом кодовой последовательности будет бит, при m=8 – 8 бит, то есть байт. Собственно коды Рида-Соломона работающие с байтами и являются наиболее распространенными.
Перед началом кодирования мы определились с необходимым полем GF(q), где q=pm. Длина кодовой последовательности должна быть q-1. Таким образом, в нашем случае с GF(8) кодовая последовательность состоит из 7 элементов. Дальше нужно выяснить какие элементы будут информационными, а какие проверочные (избыточные). В самом начале мы говорили о том, что количество избыточных символов должно быть в два раза больше, чем то количество ошибочных символов, которое мы хотим восстановить. Если необходимо исправить двукратную ошибку (t=2 – кратность ошибки), то, соответственно, следует использовать четыре проверочных символа. Применим это к нашему примеру: из семи элементов для исправления двукратной ошибки необходимы четыре избыточных, а значит три информационных. Кодовая последовательность выглядит следующим образом:
C=(c0, c1, c2, c3, c4, c5, c6), где c0, c1, c2 – информационные, c3, c4, c5, c6 – проверочные.
Хочу обратить внимание на тот факт, что исправление двукратной ошибки в кодовой последовательности из семи элементов означает, что можно бороться с ошибкой, вероятность возникновения которой не больше чем рош=2/7≈0,29. Если вероятность возникновения ошибки выше, то нужно увеличивать количество проверочных символов, иначе восстановить искаженную информацию все равно не получится.
Закодируем последовательность С=( 4, 6, 7, 0, 0, 0, 0), четыре последних символа – проверочные, равны нулю.
