Исследование временных характеристик работы кодера кода Рида-Соломона в частотной области в зависимости от типа ДПФ параметров кода

Современная цивилизация немыслима без использования разнообразных средств передачи информации. По мере технического и социального прогресса требования к объемам передаваемых данных, качеству и широте охвата информационного сервиса непрерывно возрастают, стимулируя исследовательскую и инженерную активность и пополняя новыми людскими ресурсами контингент информационного сообщества.

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

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

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

Основное внимание в данной работе уделяется кодам Рида-Соломона, которые являются оптимальными кодами, исправляющими не только одиночные искажения, но и пачки ошибок и стираний. Разработаны разные методы кодирования этими кодами.

В дипломной работе рассмотрен спектральный метод кодирования кодов Рида-Соломона над полем GF (). В основе спектрального описания РС-кодов лежит дискретное преобразование Фурье (ДПФ над конечным полем.

Существует закон Гроша, устанавливающий связь между стоимостью и скоростью обработки информации в вычислительных сетях. Согласно этому закону, стоимость вычислений пропорциональна корню квадратному из скорости вычислений. Так, например, для снижения стоимости вычисления в 10 раз скорость вычислений должна быть увеличена в 100 раз.

Цель работы — исследование временных характеристик работы кодера кода Рида-Соломона в частотной области в зависимости от типа ДПФ параметров кода.

Для выполнения этой цели был разработан программный комплекс, реализующий ДПФ, трехмерное ДПФ, БПФ-преобразования и их укорочения. На основе этих программ реализован кодер кодов Рида-Соломона в частотной области и проведены вычислительные эксперименты для исследования временных характеристик алгоритма кодирования.

1. Основы теории помехоустойчивого кодирования

1.1 Основные определения

кодирование программный алгоритм преобразование

Повышение требований к скорости и достоверности передачи информации, увеличение протяженности линий связи приводит к необходимости принятия специальных мер, направленных на уменьшение вероятности возникновения ошибок в процессе передачи. Одним из возможных решений указанной задачи служит помехоустойчивое кодирование. Под помехоустойчивыми понимаются коды, позволяющие обнаруживать и исправлять ошибки, возникающие при передаче из-за воздействия помех. Суть данной процедуры состоит во введении в информационный поток специальным образом дополнительных символов, в результате чего каждому блоку из k информационных бит сопоставляется n символьная последовательность — число возможных сообщений. Поскольку, то не все последовательности длины n используются при кодировании M сообщений. Комбинации символов, используемые для отображения информационных блоков или сообщений, называют разрешенными комбинациями или кодовыми последовательностями (словами), тогда как остальные — запрещенными. Вся совокупность кодовых слов образует код, для обозначения которого обычно говорят «код объема длины «. Множество символов, из которых составляются кодовые слова, называется алфавитом кода, а число различных символов в алфавите — основанием кода, или объемом (мощностью) алфавита.

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

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

Существует несколько подходов к классификации кодов, мы приведем основные из них:

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

Классификация кодов может быть осуществлена и по возможности выделения информационных символов в кодовом слове. Коды, в которых, как правило, первые позиций занимают информационные символы, называются систематическими кодами. В противном случае — несистематическимими.

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

В заключении также отметим, что часто термину код предшествует слово, определяющее либо алгоритм его конструирования, либо имя ученого, открывшего правило формирования: линейные, циклические, полиномиальные коды, коды Хэмминга и др.

1.3 Принципы обнаружения и исправления ошибок

Пусть для передачи сообщений используется некоторый код длины и объема. Это означает, что на вход дискретного канала поступает одна из последовательностей, называемая кодовым словом. На приемной стороне наблюдается некоторая выходная последовательность (вектор наблюдений). Процедуру решения о том, произошла ли ошибка при передаче кодовой последовательности или нет, можно описать следующим алгоритмом. Все множество разбивается на две области и, причем область образована кодовыми последовательностями, а — запрещенными комбинациями. Очевидно, что если наблюдаемая последовательность, полученная в результате трансформации каналом некоторой кодовой комбинации, оказывается в области, то принимается решение об обнаружении ошибок в принятой последовательности. Если же наблюдаемая последовательность окажется в области, то принимается решение о безошибочной передаче информации.

Естественно возникает вопрос о том, а все ли ошибки могут быть обнаружены? Предположим, что алфавит входных и выходных символов одинаков, и его объем равен. Тогда объем кода, а значит и мощность множества, составляют величину, а число запрещенных комбинаций (или мощность множества) определится как. При передаче по каналу связи M кодовых комбинаций возможны их переходов в принятые наблюдения, из которых только будут правильными, тогда как остальные переходов сопровождаются искажениями. Как уже указывалось, решение об обнаружение ошибок в принятой последовательности принимается всякий раз, когда она оказывается в области. Подобной ситуации отвечают переходов и, значит, общее число обнаруживаемых ошибок составляет величину, что еще раз свидетельствует о возможности обнаружения ошибок только при условии, т. е. при введении избыточных символов. Сравнение же общего количества ошибок с числом обнаруживаемых демонстрирует, что не все ошибки удается зафиксировать. Последнее объясняется тем, что переход одной кодовой комбинации в другую под действием канальных помех невозможно обнаружить, причем общее количество подобных переходов составит величину .

Аналогичным образом реализуется и процедура исправления ошибок. Отличие заключается лишь в том, что все множество разбивается теперь на (по числу передаваемых сообщений) решающих областей, причем и при не пересекаются, а в каждую область решения включается только одна кодовая последовательность. Если оказывается, что вектор наблюдений принадлежит j-й области, т. е., то принимается решение о том, что было передано слово и, значит, канальные ошибки, вызвавшие трансформацию в, будут исправлены. Поскольку области решений не перекрываются, то общее число исправляемых ошибок определяется числом запрещенных комбинаций, распределяемых между M решающими областями. Следовательно, и, значит, как и в случае обнаружения ошибок, их исправление возможно лишь при, т. е. при введении избыточности.

1.4 Корректирующая способность кода

Для того, чтобы дать наглядное, геометрическое толкование процедуры различения сигналов, введем понятие расстояния Хэмминга.

Расстояние Хэмминга, определяется как число позиций, в которых кодовые символы двух слов отличаются друг от друга.

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

Для расстояния Хэмминга выполняются следующие три аксиомы:

— симметрии — ;

— неотрицательности —, причем если, то ;

— неравенства треугольника — .

Наряду с расстоянием Хэмминга широко используется такая характеристика, как вес Хэмминга. Весом Хэмминга вектора называется число его ненулевых компонент. Очевидно, что и, где под суммированием векторов понимается покомпонентное сложение.

Пример 1.4.1. Для двух двоичных векторов и расстояние Хэмминга, поскольку символы, стоящие на второй, третьей и пятой позиций различаются, а на первой и четвертой — совпадают. В свою очередь вес Хэмминга для указанных векторов составляет величину и .

Теорема 1.4.1. Код исправляет любые ошибки кратности и менее в том и только в том случае, если кодовое расстояние удовлетворяет неравенству

. (*)

Доказательство:

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

а значит, не позволяющие исправить ошибку кратности. Однако, как следует из аксиом расстояния,

что противоречит условию теоремы. Следовательно, неравенство (*) определяет достаточное условие исправление ошибок кратности и менее.

Необходимость: С другой стороны, если, то обязательно возникнет ситуация, при которой произойдет неверное декодирование. Например, если, то существует такой вектор наблюдения, для которого, и, следовательно, наблюдается неопределенность в принятии решения. Таким образом, условие (*) является необходимым.

Полезной иллюстрацией приведенного доказательства может служить диаграмма, представленная на рис. 1. На ней изображены сферы Хэмминга радиуса c центром, представляющие собой множество точек (векторов), расположенных отна расстоянии Хэмминга или ближе. Если все сферы Хэмминга радиуса, окружающие кодовые вектора, не перекрываются, декодер воспримет любой вектор внутри i-ой сферы, как i-ый кодовый вектор. Это означает, что любая ошибка кратности и менее в кодовом слове будет исправлена. Вместе с тем, при условии исправления любых ошибок кратности избежать перекрытия сфер можно только в том случае, если минимальное расстояние Хэмминга между кодовыми векторами не меньше, чем .

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

.

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

2. Арифметика и структура конечных полей Галуа. Многочлены над полями Галуа

2.1 Введение в теорию конечных полей

кодирование программный алгоритм преобразование

Математическое понятие конечного поля является ключевой категорией теории кодирования, и знакомство с ним начнем с определения поля.

Полем называется множество элементов, замкнутое относительно двух операций, называемых сложением и умножением (обозначаемых привычными знаками «+» и «» (или точкой)). Замкнутость операций означает, что результаты сложения или умножения также являются элементами поля: если, то .

Операции сложения и умножения удовлетворяют следующим аксиомам:

1. Сложение и умножение коммутативно:

;

2. Сложение и умножение ассоциативно:

;

3. Существует нейтральный элемент по сложению и умножению, не изменяющий значения любого элемента поля в этих операциях. Нейтральный элемент по сложению называется нулем и обозначается символом «0», а нейтральный элемент по умножению — единицей и обозначается как «1»:

;

4. Для любого элемента существует единственный обратный или противоположный по сложению (обозначаемый, как ««) элемент такой, что

;

5. Для любого элемента (за исключением 0) существует единственный обратный элемент (обозначаемый, как) по умножению такой, что

;

6. Сложение и умножение подчиняется дистрибутивному закону:

.

Непосредственно из вышеприведенных аксиом следует, что в любом поле наряду со сложением определена операция вычитания, а с умножением — деление:

а для — .

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

Теория кодирования в основном оперирует с конечными полями, состоящими из конечного числа элементов. Общепринятым обозначением конечного поля является (Galois field — в честь французского математика Эвариста Галуа), где — порядок конечного поля, т. е. число элементов поля. Нетрудно доказать, что существуют конечные поля только порядка, равного целой степени простого числа:, где — простое, а — натуральное числа. Конечное поле простого порядка называется простым полем и обозначается. Любое подобное поле может трактоваться как множество остатков от деления натуральных чисел на с операциями сложения и умножения по модулю .

Расширенные конечные поля (порядка, где) не могут быть построены на основании арифметики по, и их более сложная структура будет рассмотрена несколько позже.

2.2 Векторное пространство над конечными полями. Линейная зависимость и независимость

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

Векторным пространством над полем называется множество элементов (векторов), замкнутое относительно двух операций: сложения векторов и умножения вектора на скаляр, обозначаемых привычными символами «+» и «*», т. е. если, то .

Операции сложения и умножения удовлетворяют следующим аксиомам:

1. Сложение коммутативно и ассоциативно:

;

2. Существует нулевой (нейтральный) вектор по сложению, не изменяющий любой вектор, сложенный с ним:

;

3. Для любого вектора существует единственный противоположный (обратный) вектор такой, что:

;

4. Умножение на скаляр ассоциативно:

;

5. Умножение любого вектора на единичный скаляр (всегда существующий в) не меняет его значения:

;

6. Выполняется дистрибутивный закон

.

Модель векторного пространства, используемая в теории кодирования, есть ничто иное, как пространствомерных векторов (кодовых слов) с компонентами, принадлежащими заданному конечному полю:. Операции с векторами в этом пространстве выполняются по следующим простым правилам:

и ,

где сложение и умножение скаляров осуществляется в соответствии с правилами поля. Пространство такого типа может содержать до векторов. В двоичном пространстве максимальное число векторов не превосходит величины и согласно правилам поля

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

где все — скалярные коэффициенты. Напротив, если ни один из векторов не является линейной комбинацией других, то вектора называются линейно независимыми.

Максимальное число линейно независимых векторов в данном пространстве называется размерностью пространства (пространство размерности также называютмерным). Любое множество линейно независимых векторов вмерном пространстве образует его базис. Если — базис пространства, то любой вектор может быть получен в виде линейной комбинации :

где — компоненты или координаты в базисе, а само выше приведенное соотношение называют представлением в базисе .

Если в векторном пространстве существует подмножество, являющееся пространством над полем с такими же операциями сложения векторов и умножения на скаляр, то называется подпространством

2.3 Арифметика полиномов, заданных над конечным полем

Рассмотрим полином

в котором коэффициенты являются элементами поля .

Введем основные правила арифметических действий с формальными полиномами, коэффициенты которого принадлежат полю (подобные полиномы обычно называют полиномами над).

1. Суммой двух полиномов и называется полином, определяемый соотношением:

.

2. Умножение полинома на скаляр (где) осуществляется как

.

Установив операции сложения полиномов и умножения полинома на скаляр, можно сказать, что множество полиномов кодовых слов обладает структурой векторного пространства и для него справедливы утверждения:

— если, то ;

— если, то .

Рассмотрим некоторые определения, связанные с полиномами, заданными над конечным полем.

Пусть имеется многочлен .

Приведенным (или нормированным) полиномом называется полином, старший коэффициент которого .

Нулевым полиномом называется полином.

Степенью ненулевого полинома называется наибольшая степень формальной переменной при ненулевом коэффициенте и обозначается как .

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

Если и, то

где .

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

Другим, более известным примером кольца является множество целых чисел. Однако в кольце целых чисел операция умножения порождает еще одну, называемую делением с остатком. Возьмем некоторое положительное целое число. Тогда любое целое число может быть представлено в виде

где неотрицательное целое, меньшее, называется остатком (от деления на), называется частным от деления, — делимым, а — делителем.

Поскольку в кольце полиномов определена операция умножения, то, поступая аналогично, можно ввести операцию деления полиномов с остатком. Однако, для полиномов сравнение в терминах «больше-меньше» невозможно, поэтому для получения остатка сравниваются степени полиномов. Возьмем полином и представим произвольный полином как

.

В данном соотношении, возможном для любых и, назовем полиномы, , и делимым, делителем, частным и остатком соответственно. Операция деления полиномов известна под названием алгоритма Евклида. Определение частного и остатка от деления полиномов осуществляется «в столбик», как и при делении целых чисел.

В теории кодирования особая роль принадлежит остатку от деления, который часто называют вычетом многочлена по модулю многочлена. Данному определению соответствует запись

которая символизирует, что полиномы и имеют один и тот же остаток от деления на. Действительно, является остатком от деления на. С другой стороны, поскольку, то сразу же является остатком от деления на .

Если, т. е., то говорят, что делится на, или делит, или является множителем. Используется также выражение, что раскладывается на множители меньшей степени.

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

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

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

Если наибольший общий делитель двух полиномов равен единицы, т. е., то они называются взаимно простыми.

2.4 Расширенные конечные поля

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

Отметим, что среди полиномов степени не выше присутствуют и полиномы нулевой степени, т. е. элементы простого поля, сложение и умножение которых, осуществляются по правилам. Это означает, что простое поле полностью содержится в расширенном, или, другими словами, является подполем. Для поля порядок его простого подполя называется характеристикой поля. Например, любое расширенное поле является полем характеристики 2, вследствие чего вычисление коэффициентов полиномов, рассматриваемых как элементы поля, осуществляется по модулю два. В частности, для любого, поскольку .

2.5 Мультипликативный порядок элементов поля. Примитивные элементы. Другой подход к построению расширения поля Галуа

В любом поле, является ли оно простым или расширенным, определена операциякратного умножения элемента. Естественно назвать такое произведениеой степенью элемента, обозначив его как

.

Тогда

и для любого ненулевого

.

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

Возьмем некоторый ненулевой элемент и рассмотрим его степени вида. Поскольку все они являются элементами поля, то вследствие его конечности лишь ограниченное число подобных степеней будет различными, т. е. для некоторых и будет справедливо, а значит,. Назовем минимальное натуральное число, для которого

мультипликативным порядком элемента. Очевидно, что только единичный элемент любого конечного поля обладает мультипликативным порядком, равным единице, т. е. .

Следующая теорема, приводимая без доказательства, утверждает, что значения мультипликативных порядков элементов поля подчиняются достаточно строгому ограничению.

Теорема 2.5.1. Мультипликативный порядок любого ненулевого элемента поля делит , т.е. число ненулевых элементов поля .

Элемент поля, имеющий максимальный мультипликативный порядок, называется примитивным элементом поля.

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

Утверждение 2.5.1. Если мультипликативный порядок элемента равен , то порядок элемента определяется как

,

где — наибольший общий делитель .

Утверждение 2.5.2. В любом поле содержится примитивных элементов, где — функция Эйлера, указывающая число целых чисел из диапазона от 1 до , взаимно простых с.

Расширенное поле, построенное как множество полиномов по модулю некоторого неприводимого полинома, всегда содержит в качестве элемента поля полином. Если окажется, что — примитивный элемент, то соответствующий неприводимый полином называется примитивным полиномом. Примитивные полиномы произвольной степени определены над любым конечным полем. Они являются полезным инструментом для построения расширенных полей, поскольку позволяют реализовать очень простой вариант таблицы умножения элементов поля. Действительно, любые ненулевые элементы и расширенного поля могут быть выражены как некоторыея ия степени примитивного элемента: ,. Тогда и, значит, таблица умножения двух элементов поля и представляет собой ни что иное, как все не нулевые степени примитивного элемента.

Таким образом, построение расширенного поля в виде степеней примитивного элемента предполагает следующий алгоритм действий. На первом этапе выбирается некоторый примитивный полином степени над основным полем, которые содержатся в специальных таблицах:. Тогдая степень по модулю определится как. Предположение о примитивности позволяет задать в виде. Отсюда

.

Учитывая, что и подставляя его в последнее соотношение, получаем в явном виде выражение дляй степени. Последовательное возведение в степень позволяет, таким образом, определить все ненулевые элементы расширенного поля в виде линейной комбинации первых степеней: ,, …, с коэффициентами из основного поля .

2.6 Некоторые свойства расширенных конечных полей

Теорема 2.6.1. Среди всех элементов расширенного поля только для элементов основного подполя , т.е. для 0 и 1, выполняется соотношение

.

Доказательство: Справедливость указанного соотношения для нулевого элемента поля очевидна. Среди всех ненулевых элементов поля мультипликативный порядок, равный единице, имеет лишь 1, что и завершает доказательство теоремы.

Теорема 2.6.2. Пусть — конечной поле характеристики . Тогда для любых элементов , , выполняется соотношение

.

Доказательство: Поскольку поле имеет характеристику, равную 2, то сомножитель в разложении бинома обращается в нуль. Следовательно

.

Данная теорема может быть обобщена на случай любого натурального и произвольного числа элементов :

.

Познакомимся теперь с еще одним важным определением.

Пусть. Тогда элементы поля вида называются 2 — сопряженными с элементом .

Вследствие конечности поля последовательность, составленная из и 2 — сопряженных с ним элементов, имеет ограниченный набор отличающихся друг от друга элементов. Так, если все элементы вида различны, а продолжение последовательности приводит к повторению какого-либо уже содержащегося в ней элемента, то

.

Можно доказать, что длина любой последовательности (цикла) 2-сопряженных элементов поля всегда делит степень расширения .

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

3. Линейные блоковые коды

3.1 Линейные коды

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

.

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

Двоичным линейным кодом является любоемерное подпространство пространства векторов длины .

Поскольку подпространство содержит кодовых слов, то есть ни что иное, как число информационных символов, переносимых кодом, а — длина кода. Наряду с обозначением кода как код, встречается и другое, в котором используется еще один его параметр — кодовое расстояние: .

3.2 Определение циклического кода. Порождающий полином

Циклические коды являются подклассом линейных кодов, удовлетворяющие дополнительному структурному требованию. В силу этого требования поиск хороших помехоустойчивых кодов оказался наиболее продуктивным. При этом в качестве математического аппарата используется теория полей Галуа. Вне класса циклических кодов теория полей Галуа не столь эффективна.

Важность циклических кодов обусловлена также тем, что заложенные в основу их построения идеи теории конечных полей приводят к процедурам кодирования и декодирования, эффективным как с алгоритмической, так и вычислительной точек зрения.

Линейный блоковый код длины называется циклическим, если наряду с любым своим кодовым словом он содержит также циклический сдвиг этого слова. Иными словами, циклический код содержит все циклические сдвиги всех своих кодовых слов.

Лемма 3.2.1. Пусть некоторому слову циклического кода сопоставлен полином . Тогда его циклическому сдвигу будет соответствовать полином , являющийся вычетом полинома по модулю бинома , т.е. .

Доказательство: Добавим и вычтем в соотношении для и сгруппируем его слагаемые следующим образом

.

Откуда непосредственно следует утверждение леммы 3.2.1.

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

. (**)

Лемма 3.2.2. Если — кодовый полином слова циклического кода , то для произвольного полинома вычет произведения по модулю биномa также является кодовым полиномом.

Доказательство: Пусть, где. Тогда

.

Отсюда на основании леммы 3.2.1, ясно, что каждое слагаемое последнего выражения является кодовым полиномом, отвечающим некоторому циклическому сдвигу исходного слова. Учитывая же свойства линейного подпространства, т. е. тот факт, что умножение на скаляр и сложение кодовых слов вновь дают кодовое слово, следует, что вычет по модулю также соответствует кодовому слову.

Следствие. Если степень полинома удовлетворяет неравенству

,

то само произведение отвечает полиному некоторого слова циклического кода.

Рассмотрим множество полиномов, образующих циклический код и найдем среди них ненулевой полином наименьшей степени.

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

Следовательно, если, то

.

Теорема 3.2.1. Любой кодовый полином циклического кода делится без остатка на порождающий многочлен этого кода, т.е.

Доказательство: Предположим противное, т. е. что существует некоторый кодовый многочлен, который представим в виде

где остаток от деления на.

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

Таким образом, любой кодовый полином циклического кода может быть представлен в виде произведения

в котором — порождающий многочлен, а — некоторый информационный полином. Иными словами, отличие всех кодовых полиномов друг от друга определяется только информационными полиномами. Поскольку

то для двоичных кодов может существовать различных информационных полиномов, т. е. различных кодовых слов. Отсюда число информационных символов в каждом кодовом слове, и, значит,, тогда как степень порождающего многочлена соответствует числу проверочных символов.

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

Теорема 3.2.2. Порождающий многочлен циклического кода длины обязательно делит бином .

Доказательство: Из леммы 3.2.1 следует, что вычет из произведения по модулю является кодовым полиномом. Учитывая, что, то

и значит, как кодовый полином, делится без остатка на. Следовательно, и делится на .

3.3 Систематический циклический код

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

Для того чтобы прийти к систематической форме кодового слова необходимо осуществить некоторое согласование между информационным и кодовым полиномами. Пусть — информационный полином, а — кодовый. Систематическое правило кодирование предполагает получение кодового полинома в таком виде, чтобы коэффициенты при старших степенях полинома соответствовали информационным символам. Данное требование достигается путем умножения информационно полинома на многочлен :

что эквивалентно сдвигу информационного слова на позиций вправо и добавления слева аналогично числа нулей.

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

.

3.4 Коды Рида-Соломона

Остановимся здесь на важном частном случае циклического кода — коде Рида-Соломона (РС).

Коды РС являются недвоичными циклическими кодами, символы кодовых слов которых берутся из конечного поля. Здесь степень некоторого простого числа,, -простое.

Кодовые слова РС-кода отображаются в виде многочленов где — длина кода; - -ичные коэффициенты (символы кодовых слов), которые могут принимать любое значение из Коды РС являются максимальными, т.к. при длине кода и информационной последовательности они обладают наибольшим кодовым расстоянием

Порождающим многочленом РС-кода является делитель двучлена x^N+1 степени меньшей с коэффициентами из при условии, что элементы этого поля являются корнями. Здесь — примитивный элемент

На основе этого определения, а также теоремы Безу, выражение для порождающего многочлена РС-кода будет иметь вид

)

В РС-кодах принадлежность кодовых слов данному коду определяется выполнением d-1 уравнений в соответствии с выражением, где — символы-коэффициенты из

z₀, z₁… z_N-1 — ненулевые элементы

Элементы z₀, z₁… z_N-1 называются локаторами, т. е. указывающими на номер позиции символа кодового слова. Например, указателем — позиции является локатор или элемент ?ⁱ. Так как все локаторы должны быть различны и причем ненулевыми, то их число в равно. Следовательно, такое количество символов должно быть в кодовых словах кода. Поэтому обычно длина РС-кода определяется из выражения .

Приведем основные свойства РС-кодов.

1. Циклический сдвиг кодовых слов, символы которых принимают значение из, порождает новые кодовые слова этого же кода.

2. Сумма по двух и более кодовых слов дает кодовое слово, принадлежащее этому же коду.

3. В РС-коде, исправляющем t_u ошибок, порождающий многочлен определяется из выражения.

Обычно m₀ принимают равным 1. Однако, с помощью разумного выбора значения m₀, иногда можно упростить схему кодера.

4. Спектральное описание циклических кодов

4.1 Дискретное преобразование Фурье

В данном разделе мы рассмотрим один из способов описания циклических кодов, основанный на использовании дискретного преобразования Фурье (ДПФ) кодовых последовательностей, заданных над конечным полем. Данный подход позволяет в ряде случаев найти альтернативные методы кодирования и декодирования циклических кодов.

В поле комплексных чисел ДПФ вектора с комплексными компонентами определяется как вектор, компоненты которого вычисляются согласно соотношению

.

Ядром преобразования Фурье является, которое является корнем n-й степени из единицы в поле комплексных чисел. В конечном поле элемент порядка также является корнем n-й степени из единицы. Тогда, проводя аналогию между и, можно ввести следующее определение.

Пусть — вектор над, где n делит при некотором m и пусть — элемент мультипликативного порядка n в расширенном поле. Тогда ДПФ над полем вектора является вектор с элементами, задаваемыми равенствами

или в матричном представлении

.

Учитывая ранее указанную аналогию, дискретный индекс i естественно назвать дискретным временем, а вектор — временной функцией (последовательностью) или сигналом. Аналогично, индекс k можно назвать дискретной частотой, а вектор — частотной функцией (последовательностью) или спектром.называется ядром преобразования, а матрица в правой части равенства — матрицей Фурье.

Если спектр определяется прямым ДПФ, то с помощью обратного ДПФ по спектру может быть определен сам сигнал, т. е. компоненты вектора

.

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

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

Теорема 4.1.1. (Теорема о свертке) Пусть — временные последовательности, причем . Тогда компоненты ДПФ могут быть определены как

где двойные скобки означают, что индекс вычисляется в арифметике по модулю n.

Доказательство: Вычислим преобразование Фурье вектора с компонентами вида

.

Можно сформулировать и обратную теорему, поменяв местами временную и частотную области.

Теорема 4.1.2. Пусть — частотные последовательности, причем . Тогда компоненты вектора могут быть определены как

где двойные скобки означают, что индекс вычисляется в арифметике по модулю n.

Отметим также, что выбор в теореме о свертке приводит к формуле типа равенства Парсеваля

.

Замечание. Основываясь на этом свойстве ДПФ, возможен альтернативный вариант описания циклических кодов. Любое кодовое слово циклического кода может быть представлено в несистематическом виде как

где — информационный, а — проверочный полиномы. Во временной области коэффициенты кодового полинома определяются циклической сверткой коэффициентов информационного и порождающего полиномов

так что в частотной области, согласно теореме 4.1.2, операция кодирования может быть осуществлена покомпонентным перемножением спектров

и последующим вычислением обратного ДПФ для спектра кодового слова.

Теорема 4.1.3. (Свойство сдвига) Если последовательности и являются парой преобразования Фурье, то парами преобразований Фурье являются также и .

Доказательство осуществляется непосредственной подстановкой.

В том случае, когда кодовому вектору сопоставляется полином, он может быть преобразован в полином, коэффициенты которого отвечают спектральным компонентам ДПФ в поле Галуа вектора, а сам полином называется спектральным (или ассоциированным) с многочленом. Следующая теорема устанавливает, что свойства спектра тесно связана с корнями многочленов.

Теорема 4.1.4.

(i). Элемент является корнем полинома тогда и только тогда, когда k-й частотный компонент равен нулю.

(ii). Элемент является корнем многочлена тогда и только тогда, когда i-й временной компонент равен нулю.

Доказательство утверждения (i) очевидно, поскольку из непосредственной подстановки корня в полином имеем

.

Аналогичным образом доказывается и утверждение (ii).

На основании приведенной теоремы можно сделать следующее заключение. Поскольку любой кодовый многочлен содержит в качестве множителя порождающий многочлен, то корни порождающего полинома являются и корнями кодового. Тогда, согласно теореме 4.1.4, корням порождающего многочлена будут соответствовать нулевые спектральные компоненты кодовых слов на позициях. Следовательно, можно дать следующее альтернативное определение циклического кода. Циклическим кодом называется множество таких слов над конечным полем, у которых все спектральные компоненты, принадлежащие заданному множеству т.н. проверочных частот равны нулю

Кодовое слово кода Р-С длины и его спектр лежат в одном поле. Кодирование кода Рида-Соломона в частной области можно осуществить следующим образом: какие либо последовательных координат полагаются равными нулю, в остальных координатах записываются информационные символы. Например, информационный вектор может быть такой: .Кодовый вектор, соответствующий информационному вектору, определяется как ДПФ вектора с ядром б. Координаты кодового вектора задаются по правилутак как каждая компонента вычисляется как значение многочлена a (x) в точке:. Если a (x) — многочлен из информационной области, A (x) — многочлен из кодовой области, тогда дискретное преобразование Фурье с ядром б (прямое) переводит многочлен из информационной области в кодовую, а дискретное преобразование Фурье с ядром (обратное) переводит многочлен из кодовой области в информационную а (х) А (х), .

4.2 Китайская теорема об остатках

Рассмотрим более детально формулу (4.1), задающую ДПФ над полем. Например, для того, чтобы вычислить ДПФ над полем вектора длины, требуется умножений в поле. Как известно, умножение является одной из наиболее затратных по времени операций, т. е. алгоритм ДПФ имеет сложность порядка O (. Известные алгоритмы многомерного преобразования Фурье, а так же БПФ (быстрое преобразование Фурье) позволяют снизить эту цифру до N*logN умножений. Данные алгоритмы основаны на следующей китайской теореме об остатках.

Теорема 4.2.1. (Китайская теорема об остатках, единственность)

Для заданного множества целых положительных попарно взаимно-простых чисели множества неотрицательных целых чисел

при, система сравнений

имеет не более одного решенияc в интервале

Теорема 4.2.2. (Китайская теорема об остатках, существование)

Пусть —произведение целых положительных попарно взаимно-простых положительных чисел, пусть и пусть удовлетворяют равенству , тогда единственным решением системы сравнений

будет

Эта теорема позволяет каждое число n, 0? n

4.3 Трехмерное преобразование Фурье в поле

Рассмотрим ДПФ длины N=255, ядром которого является примитивный элемент поля .

В этом случае, М=255=3517, =3, = 5, =17, так что n (, ,), где

,

Произвольный ненулевой элемент поля) задается как степень примитивного элемента поля: = ,

Согласно (2)

= (,

, =, ==,

Где приняты обозначения: =, =,=

Более того, в силу попарной взаимной простоты модулей, если i (, ,) и j (, ,), то ij (, ,). Таким образом, формулу (4.1) определяющую ДПФ, можно переписать в виде:

, =, =

Это сразу подсказывает следующий алгоритм вычисления вектора по вектору. Сначала разбиваем координаты вектора на тройки чисел (прификсированных и) и к каждой из них применяем 3-точечное преобразование с ядром =; это дает набор из 255 величин

, =, =.

Затем к этому вектору длины 255 применяется 5-точечное ДПФ с ядром = по правилу: координаты вектора группируются по 5 чисел (по фиксированным и) и для каждой такой совокупности вычисляется 5-мерный вектор ,

, =, =.

Наконец, к вектору длины 255 применяется 17-точечное ДПФ с ядром =, приводящее к искомому 255-мерному вектору :

, =, =.

Описанный алгоритм вместо умножений при прямом вычислении по формуле (4.1) требует

умножений, где — число умножений, необходимое для выполнения i-точечного ДПФ, i=3,5,17. Аналогично выписывается и формула для числа сложений (кстати, напомним, что характеристика рассматриваемого поля равна 2, так что вычитание совпадает со сложением)

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

Таким образом, переход от ДПФ длины 255 к ДПФ длин 3, 5 и 17, каждое из которых вычисляется 255 раз в цикле, очень существенно понижает вычислительную сложность алгоритма.

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

4.4 Быстрое преобразование Фурье БПФ длины 3

3-точечное ДПФ с ядром в для вектора a=, a-0., a-1., a-2. задается формулой

A=(, A-0., A-1., A-2.)=

Так как ядро в удовлетворяет тождеству 1+, то легко проверить непосредственно, что числа могут быть вычислены по правилу:

s-1.=, a-1.+, a-2., m-1.=в?, s-1., A-1.=, s-2.+, a-1., ,

которое содержит только одно умножение и 5 сложений (вместо 4 умножений и 6 сложений). Если, в=, б-3.=, б-85.

4.5 Быстрое преобразование Фурье длины 5

5-точечное ДПФ с ядромзадается равенством

непосредственное вычисление по которому требует 16 умножений и 20 сложений. Использование только тождества на ядре (которое в данном случае имеет вид 1+++) дает 9 умножений и 21 сложение. Это достигается, например, следующим образом:

Аналогично,

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

Утверждение 4.5.1. Два двучлена и , , , , , можно перемножить, выполняя не более трех умножений чисел в поле F.