Исследование временных характеристик работы кодера кода Рида-Соломона в частотной области в зависимости от типа ДПФ параметров кода
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
?х вектора и такие, что
,
а значит, не позволяющие исправить ошибку кратности . Однако, как следует из аксиом расстояния,
,
что противоречит условию теоремы. Следовательно, неравенство (*) определяет достаточное условие исправление ошибок кратности и менее.
Необходимость: С другой стороны, если , то обязательно возникнет ситуация, при которой произойдет неверное декодирование. Например, если , то существует такой вектор наблюдения , для которого , и, следовательно, наблюдается неопределенность в принятии решения. Таким образом, условие (*) является необходимым.
Полезной иллюстрацией приведенного доказательства может служить диаграмма, представленная на рис. 1. На ней изображены сферы Хэмминга радиуса c центром , представляющие собой множество точек (векторов), расположенных отна расстоянии Хэмминга или ближе. Если все сферы Хэмминга радиуса , окружающие кодовые вектора , не перекрываются, декодер воспримет любой вектор внутри i-ой сферы, как i-ый кодовый вектор . Это означает, что любая ошибка кратности и менее в кодовом слове будет исправлена. Вместе с тем, при условии исправления любых ошибок кратности избежать перекрытия сфер можно только в том случае, если минимальное расстояние Хэмминга между кодовыми векторами не меньше, чем .
Из представленной диаграммы легко увидеть, что обнаружение ошибок кратности в принятых векторах возможно тогда, когда выполняется условие
.
Из рассмотренного видно, что основными параметрами блокового кода являются: кодовое расстояние , его объем и длина . Часто при описании характеристик кода вместо объема используют либо число информационных символов в кодовом слове , либо скорость кода . Именно с этими параметрами связаны два основных варианта задач, рассматриваемых теорией кодирования. Первая из них связана с максимизацией при заданных значениях ( или ) и для достижения хорошей корректирующей способности кода. Дуальной задачей является максимизация ( или) при минимуме и длины .
2. Арифметика и структура конечных полей Галуа. Многочлены над полями Галуа
.1 Введение в теорию конечных полей
кодирование программный алгоритм преобразование
Математическое понятие конечного поля является ключевой категорией теории кодирования, и знакомство с ним начнем с определения поля.
Полем называется множество элементов, замкнутое относительно двух операций, называемых сложением и умножением (обозначаемых привычными знаками + и (или точкой)). Замкнутость операций означает, что результаты сложения или умножения также являются элементами поля : если , то .
Операции сложения и умножения удовлетворяют следующим аксиомам:
. Сложение и умножение коммутативно:
;
. Сложение и умножение ассоциативно:
;
. Существует нейтральный элемент по сложению и умножению, не изменяющий значения любого элемента поля в этих операциях. Нейтральный элемент по сложению называется нулем и обозначается символом 0, а нейтральный элемент по умножению - единицей и обозначается как 1:
;
4. Для любого элемента существует единственный обратный или противоположный по сложению (обозначаемый, как ) элемент такой, что
;
. Для любого элемента (за исключением 0) существует единственный обратный элемент (обозначаемый, как ) по умножению такой, что
;
. Сложение и умножение подчиняется дистрибутивному закону:
.
Непосредственно из вышеприведенных аксиом следует, что в любом поле наряду со сложением определена операция вычитания, а с умножением - деление:
, а для - .
Простейшими примерами полей являются числовые поля (поле рациональных и вещественных чисел), имеющих бесконечной число элементов.
Теория кодирования в основном оперирует с конечными полями, состоящими из конечного числа элементов. Общепринятым обозначением конечного поля является (Galois field - в честь французского математика Эвариста Галуа), где - порядок конечного поля, т.е. число элементов поля. Нетрудно доказать, что существуют конечные поля только порядка, равного целой степени простого числа: , где - простое, а - натуральное числа. Конечное поле простого порядка называется простым полем и обозначается . Любое подобное поле может трактоваться как множество остатков от деления натуральных чисел на с операциями сложения и умножения по модулю .
Расширенные конечные поля (порядка , где ) не могут быть построены на основании арифметики по , и их более сложная структура будет рассмотрена несколько позже.
2.2 Векторное пространство над конечными полями. Линейная зависимость и независимость
Пусть - конечное поле, элементы которого будем называть скалярами.
Векторным пространством над полем называется множество элементов (векторов), замкнутое относительно двух операций: сложения векторов и умножения вектора на скаляр, обозначаемых привычными символами + и , т.е. если , то .
Операции сложения и умножения удовлетворяют следующим аксиомам:
. Сложение коммутативно и ассоциативно:
;
. Существует нулевой (нейтральный) вектор по сложению, не изменяющ?/p>