Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

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

Повышение требований к скорости и достоверности передачи информации, увеличение протяженности линий связи приводит к необходимости принятия специальных мер, направленных на уменьшение вероятности возникновения ошибок в процессе передачи. Одним из возможных решений указанной задачи служит помехоустойчивое кодирование. Подпомехоустойчивыми понимаются коды, позволяющие обнаруживать и исправлять ошибки, возникающие при передаче из-за воздействия помех. Суть данной процедуры состоит во введении в информационный поток специальным образом дополнительных символов, в результате чего каждому блоку из k информационных бит сопоставляется n символьная последовательность Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru – число возможных сообщений. Поскольку Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , то не все последовательности длины n используются при кодировании M сообщений. Комбинации символов, используемые для отображения информационных блоков или сообщений, называют разрешенными комбинациями или кодовыми последовательностями (словами), тогда как остальные – запрещенными. Вся совокупность кодовых слов Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru образует код, для обозначения которого обычно говорят «код объема Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru длины Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru ». Множество символов, из которых составляются кодовые слова, называется алфавитом кода, а число различных символов в алфавите – основанием кода, или объемом (мощностью) алфавита.

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

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

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

В зависимости от позиций, с которых рассматривается процедура кодирования, классификация кодов может осуществляться различным образом. Простейшим вариантом может служить классификация по размеру алфавита кода. Если символы кода Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru или Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , то код называется двоичным или бинарным соответственно. Если же алфавит кода содержит Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru символов, соответствующий ему код носит наименование Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru –ичного. В данной работе основное внимание будет концентрироваться на двоичных или бинарных кодах.

Классификация кодов может быть осуществлена и по возможности выделения информационных символов в кодовом слове. Коды, в которых, как правило, первые Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru позиций занимают информационные символы, называются систематическими кодами. В противном случае – несистематическимими.

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

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

МНОГОЧЛЕНЫ НАД ПОЛЯМИ ГАЛУА

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

Теперь у нас есть все необходимые сведения, чтобы расширить поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru до поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru ( Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru – простое число).Как уже известно, существуют конечные поля только порядка Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru ( Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru – простое, Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru – натуральное числа). Простое поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru порядка Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru может трактоваться как множество остатков от деления целых чисел на Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru : Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru с операциями сложения и умножения по модулю Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Аналогичным образом расширенное поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru порядка Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , может трактоваться как множество остатков от деления полиномов над Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru на некоторый неприводимый полином Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru степени Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru с операциями сложения и умножения по модулю Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Другими словами, поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru содержит все полиномы над полем Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru степени не выше Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru с общепринятыми операциями сложения и умножением, осуществляемым в два этапа – вначале производится обычное умножение полиномов, а затем удерживается только остаток от деления полученного произведения на полином Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

Отметим, что среди полиномов степени не выше Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru присутствуют и полиномы нулевой степени, т.е. элементы простого поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , сложение и умножение которых, осуществляются по правилам Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Это означает, что простое поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru полностью содержится в расширенном Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , или, другими словами, Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru является подполем Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Для поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru порядок его простого подполя Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru называется характеристикой поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Например,любое расширенное поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru является полем характеристики 2, вследствие чего вычисление коэффициентов полиномов, рассматриваемых как элементы поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , осуществляется по модулю два. В частности, для любого Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , поскольку Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

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

Рассмотрим множество Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , состоящее из Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru всех возможных Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru –компонентных векторов Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , элементы которого Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Очевидно, что Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru образует Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru –мерное векторное пространство. Выберем в этом пространстве Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru линейно независимых векторов Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , что всегда возможно, поскольку в Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru –мерном пространстве всегда существуют Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru линейно независимых векторов. Построим множество Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , содержащее Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru векторов, образованных как линейная комбинация Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru вида:

Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

Непосредственной проверкой легко убедиться, что множество Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru замкнуто по сложению векторов и умножению их на скаляр из Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , и, следовательно, Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru является векторным пространством, т.е. подпространством Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Это подпространство имеет размерность Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru и непосредственно является той конструкцией, которую назовем линейным кодом.

Двоичным Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru линейным кодом является любое Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru –мерное подпространство пространства векторов длины Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

Поскольку подпространство содержит Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru кодовых слов, то Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru есть ни что иное, как число информационных символов, переносимых кодом, а Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru – длина кода. Наряду с обозначением кода как Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru код, встречается и другое, в котором используется еще один его параметр – кодовое расстояние: Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

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

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

Коды РС являются недвоичными циклическими кодами, символы кодовых слов которых берутся из конечного поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Здесь Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru степень некоторого простого числа, Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru –простое.

Кодовые слова РС-кода отображаются в виде многочленов

Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru


где Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru - длина кода; Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru - Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru -ичные коэффициенты (символы кодовых слов), которые могут принимать любое значение из Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru Коды РС являются максимальными, т.к. при длине кода Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru и информационной последовательности Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru они обладают наибольшим кодовым расстоянием Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru


Порождающим многочленом Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru РС-кода является делитель двучлена xN+1 степени меньшей Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru с коэффициентами из Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru при условии, что элементы Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru этого поля являются корнями Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Здесь Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru - примитивный элемент Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru


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

Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru )

Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru

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

Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru где Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru - символы-коэффициенты из Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru
z0, z1... zN-1 - ненулевые элементы Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru


Элементы z0, z1... zN-1 называются локаторами, т.е. указывающими на номер позиции символа кодового слова. Например, указателем Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru - позиции является локатор Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru или элемент ai Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Так как все локаторы должны быть различны и причем ненулевыми, то их число в Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru равно Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Следовательно, такое количество символов должно быть в кодовых словах кода.Поэтому обычно длина РС-кода определяется из выражения Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

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

1. Циклический сдвиг кодовых слов, символы которых принимают значение из Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , порождает новые кодовые слова этого же кода.

2. Сумма по Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru двух и более кодовых слов дает кодовое слово, принадлежащее этому же коду.

3. В РС-коде, исправляющем tu ошибок, порождающий многочлен определяется из выражения. Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru

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


Теорема 4.1.4.

(i). Элемент Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru является корнем полинома Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru тогда и только тогда, когда k–й частотный компонент Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru равен нулю.

(ii). Элемент Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru является корнем многочлена Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru тогда и только тогда, когда i–й временной компонент Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru равен нулю.

Доказательство утверждения (i) очевидно, поскольку из непосредственной подстановки корня в полином Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru имеем

Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

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

На основании приведенной теоремы можно сделать следующее заключение. Поскольку любой кодовый многочлен содержит в качестве множителя порождающий многочлен, то корни порождающего полинома являются и корнями кодового. Тогда, согласно теореме 4.1.4, корням порождающего многочлена Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru будут соответствовать нулевые спектральные компоненты кодовых слов на позициях Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Следовательно, можно дать следующее альтернативное определение циклического кода. Циклическим кодом Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru называется множество таких слов над конечным полем Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , у которых все спектральные компоненты, принадлежащие заданному множеству т.н. проверочных частот Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru равны нулю

Кодовое слово кода Р-С длины Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru и его спектр лежат в одном поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .Кодирование кода Рида-Соломона в частной области можно осуществить следующим образом: какие либо Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru последовательных координат полагаются равными нулю, в остальных Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru координатах записываются информационные символы. Например, информационный вектор может быть такой: Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .Кодовый вектор, соответствующий информационному вектору, определяется как ДПФ вектора Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru с ядром α. Координаты кодового вектора задаются по правилу Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru так как каждая компонента Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru вычисляется как значение многочлена a(x) в точке Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru : Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Если a(x) – многочлен из информационной области, A(x) – многочлен из кодовой области, тогда дискретное преобразование Фурье с ядром α (прямое) переводит многочлен из информационной области в кодовую, а дискретное преобразование Фурье с ядром Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru (обратное) переводит многочлен из кодовой области в информационную а(х) Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru А(х), Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru .

ЗАКЛЮЧЕНИЕ

На основании китайской теоремы об остатках получен результат, существенно понижающий вычислительную сложность ДПФ. Приведены формулы для трехмерного преобразования Фурье поле Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru . Построены алгоритмы быстрого преобразование Фурье (БПФ) длин 3, 5 и 17 на основе алгоритма Рейдера и алгоритма Винограда вычисления циклической свертки. Показана эквивалентность между вычислением ДПФ простой длины и вычислением циклической свертки.

На основании трехмерного преобразования Фурье построеныукороченные преобразования длин 15, 51, 85, которые рационально применять, когда не требуется кодировать слова длины 255. Показана эквивалентность между укорочением преобразования и переходом на соответствующую ему подгруппу мультипликативной группы поля.

В приложении представлен программный комплекс, реализующий построение поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru основные операции в этом поле, вычисление значения произвольного многочлена в любой точке поле, вычисление ДПФ, ОДПФ, трехмерного преобразования Фурье и БПФ длин 255,85,51,15,17,5,3, кодирование кодом Рида-Соломона в частотной области.

Проведенные вычислительные эксперименты показали практическую эффективность перехода от ДПФ к трехмерному преобразованию: если на вычисление ДПФ длины 255 затрачивается примерно 300-350 мс машинного времени, то трехмерное преобразование занимает от 20 до 35 мс. При этом на вычисление БПФ длины 255 затрачивается всего 13-17 мс.

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

Языком реализации выбранBorlandDelphiEnterprise 2007.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Берлекэмп Э. Р. Алгебраическая теория кодирования. М.: Мир, 1971

2. Nussbaumer H. J. Fast Fourier Transform and Convolution Algorithms. – Springer-Verlag: Berlin, Heidelberg, New York, 1981.

3. Помехоустойчивое кодирование и надежность ЭВМ. М.: Наука, 1987.

4. Макмеллан Дж. Х., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

6. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г.

7. Золотарев В. В. Помехоустойчивое кодирование. Методы и алгоритмы:

справочник / В. В. Золотарев, Г. В. Овечкин. – М.: Горячая линия –

Телеком, 2004. – 126 с.

8. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.

9. Лидл Р., Нидеррайтер Г. Конечные поля, т.1. М.: Мир, 1988

10. Волошина В. Н., Руднева И. В. Надежное хранение информации с помощью кодов Рида-Соломона: Препр. Владивосток: ИАПУ ДВНЦ АН СССР, 1987, 13 с.

11. Волошина В. Н., Герасимов В. В., Руднева И. В., Программно-технологическая система хранения информации с повышенной надежностью: Препр. Владивосток: ИАПУ ДВО АН СССР, 1989, 22 с.

ПРИЛОЖЕНИЯ

Приложение 1.

Приложение 2

Листинг программы

Модуль программного комплекса, реализующего построение поля Раздел 1. ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ - student2.ru , введение основных операций в этом поле, вычисление значения произвольного многочлена в любой точке поля, вычисление прямого и обратного ДПФ,ОДПФ, трехмерного преобразования Фурье и БПФ длин 255,3,5,17,15,51,85, кодирование вектора несистематическим кодом Рида-Соломона.

program GF2_8;

{$APPTYPE CONSOLE}

uses

SysUtils;

const n=255;

n1=8;

type m = packed array [1..n1] of char;

type Gal = array [0..n] of m;

type vect= array [0..n-1] of m;

type D3vect=array [0..2] of m;

type D5vect=array [0..4] of m;

type D17vect=array [0..16] of m;

type multPol=array [0..6] of m;

type deg3Pol=array [0..3] of m;

type degBig=array [0..18] of m;

type deg15Pol=array [0..15] of m;

type D85vect=array [0..84] of m;

type D51vect=array [0..50] of m;

type D15vect=array [0..14] of m;

//-----------------------

function plus(a,b:m):m;

var i: integer;

begin

for i:=1 to 8 do

if a[i]<>b[i] then plus[i]:='1'

else plus[i]:='0';

end;

//-----------------------

function LogZ(a:m; G:Gal): integer;

var i: integer;

label 1;

begin

if a='00000000' then LogZ:=-1 else begin

for i:=0 to n-1 do

if a=G[i] then begin LogZ:=i; goto 1; end;

end;

1:end;

//------------------------

function expZ(k: integer; A:Gal): m;

begin

if k=-1 then expZ:='00000000'

else

expZ:=A[k];

end;

//-----------------------

function mult(a,b:m; G:Gal):m;

var i,j,Log: integer;

begin

i:=LogZ(a,G);

j:=LogZ(b,G);

if (i=-1)or(j=-1) then mult:='00000000'

else begin Log:=(i+j) mod 255

mult:=expZ(Log,G);

end;

end;

//-----------------------

procedure Generate(var A:Gal);

var C7: m;

i,j:integer;

c:char;

fl: boolean;

begin

A[0]:='00000001';

C7:='00011101';

fl := false;

for i:= 1 to n do

begin

c:=A[i-1,1];

if c = '1' then fl := true;

for j:=1 to 8 do

A[i,j]:=A[i-1,j+1];

A[i,8]:='0';

if fl = true then begin

for j := 1 to n1 do

if A[i, j] <> C7[j] then A[i, j] :='1' else A[i, j] := '0';

fl:=false;

end;

end;

end;

//----------------------

function powZ(a:m; i:integer; G:gal):m;

var k,t: integer;

begin

if a='00000000' then powZ:='00000000' else begin //0^a=0

k:=LogZ(a,G);

t:=k*i mod 255;

powZ:=expZ(t,G);

end;

end;

//--------------------------------------------------

function dim3FUR(c:vect;G:gal):vect;

var i,j,k,t,t1,t2,t3: integer;

A,f3,f5,f17: array[0..16,0..4,0..2] of m;

temp,su,D,DD: m; it: integer;

begin

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do begin

A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];

end;

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do begin

su:='00000000';

for t:=0 to 2 do begin

DD:=powZ(G[85],t*k,G);

temp:=mult(A[i,j,t],DD,G);

su:=plus(su,temp);

end;

f3[i,j,k]:=su;

end;

for i:=0 to 16 do

for k:=0 to 2 do

for j:=0 to 4 do begin

su:='00000000';

for t:=0 to 4 do begin

DD:=powZ(G[51],t*j,G);

temp:=mult(f3[i,t,k],DD,G);

su:=plus(su,temp);

end;

f5[i,j,k]:=su;

end;

for j:=0 to 4 do

for k:=0 to 2 do

for i:=0 to 16 do begin

su:='00000000';

for t:=0 to 16 do begin

DD:=powZ(G[120],t*i,G);

temp:=mult(f5[t,j,k],DD,G);

su:=plus(su,temp);

end;

f17[i,j,k]:=su;

end;

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do

dim3FUR[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];

end;

//-------------------------------------------------------------

function DPF256(c:vect;G:gal):vect;

var i,j: integer;

temp,r:m;

begin

for j:=0 to n-1 do begin

r:='00000000';

for i:=0 to n-1 do begin

temp:=mult(c[i],powZ(G[1],i*j,G),G);

r:=plus(temp,r);

end;

DPF256[j]:=r;

end;

end;

//-------------------------------------------------------------

function DPF256back(c:vect;G:gal):vect;

var i,j: integer;

temp,r:m;

begin

for j:=0 to n-1 do begin

r:='00000000';

for i:=0 to n-1 do begin

temp:=mult(c[i],powZ(G[254],i*j,G),G);

r:=plus(temp,r);

end;

DPF256back[j]:=r;

end;

end;

//------------------------------------------------------------------

function DPF17(c:D17vect;G:gal):d17vect

var i,j: integer;

temp,r:m;

begin

for j:=0 to 16 do begin

r:='00000000';

for i:=0 to 16 do begin

temp:=mult(c[i],powZ(G[120],i*j,G),G);

r:=plus(temp,r);

end;

DPF17[j]:=r;

end;

end;

//------------------------------------------------------------------

function DPF17back(c:D17vect;G:gal):d17vect;

var i,j: integer;

temp,r:m;

begin

for j:=0 to 16 do begin

r:='00000000';

for i:=0 to 16 do begin

temp:=mult(c[i],powZ(G[135],i*j,G),G);

r:=plus(temp,r);

end;

DPF17back[j]:=r;

end;

end;

//------------------------------------------------------------------

function DPF3(c:D3vect;G:gal):d3vect;

var i,j: integer;

temp,r:m;

begin

for j:=0 to 2 do begin

r:='00000000';

for i:=0 to 2 do begin

temp:=mult(c[i],powZ(G[85],i*j,G),G);

r:=plus(temp,r);

end;

DPF3[j]:=r;

end;

end;

//------------------------------------------------------------------

function DPF3back(c:D3vect;G:gal):d3vect;

var i,j: integer;

temp,r:m;

begin

for j:=0 to 2 do begin

r:='00000000';

for i:=0 to 2 do begin

temp:=mult(c[i],powZ(G[170],i*j,G),G);

r:=plus(temp,r);

end;

DPF3back[j]:=r;

end;

end;

//------------------------------------------------------------------

function DPF5(c:D5vect;G:gal):d5vect;

var i,j: integer;

temp,r:m;

begin

for j:=0 to 4 do begin

r:='00000000';

for i:=0 to 4 do begin

temp:=mult(c[i],powZ(G[51],i*j,G),G);

r:=plus(temp,r);

end;

DPF5[j]:=r;

end;

end;

//------------------------------------------------------------------

//------------------------------------------------------------------

function DPF5back(c:D5vect;G:gal):d5vect;

var i,j: integer;

temp,r:m;

begin

for j:=0 to 4 do begin

r:='00000000';

for i:=0 to 4 do begin

temp:=mult(c[i],powZ(G[204],i*j,G),G);

r:=plus(temp,r);

end;

DPF5back[j]:=r;

end;

end;

//------------------------------------------------------------------

function RootOfPol(pol:vect;root:m; G:gal):m;

var temp_v: vect;

sum: m;

i: integer;

begin

temp_v[0]:=pol[0];

for i:=1 to 254 do

if pol[i]<>'00000000' then

temp_v[i]:=mult(pol[i],powZ(root,i,G),G)

else temp_v[i]:='00000000';

sum:='00000000';

for i:=0 to 254 do

sum:=plus(sum,temp_v[i]);

RootOfPol:=sum;

end;

//-------------------------------------------------------------------

function RS_Encrypt(inf: vect; G:Gal):vect;

var i: integer;

begin

for i:=0 to 254 do

RS_Encrypt[i]:=RootOfPol(inf,G[255-i],G);

end;

//--------------------------------------------------------------------

procedure waste(DateTime,DateTime1:TDateTime);

var Hour,Min,Sec,Msec,Hour1,Min1,Sec1,Msec1:word;

Ms,sss:integer;

begin

decodetime(DateTime,Hour,Min,Sec,Msec); decodetime(DateTime1,Hour1,Min1,Sec1,Msec1);

ms:=Msec1-msec;

sss:=sec1-sec;

if ms<0 then begin

MS:=ms+1000;

SSS:=sss-1;

end;

writeln('algorithm waste is ',sss,' seconds, and ',ms{mod 65000},' milliseconds');

end;

//--------------------------------------------------------------------

function Dim3RPF(h:D3vect;G:Gal):D3vect;

var s1,m1,s2,tt: m;

begin

s1:=plus(h[1],h[2]);

m1:=mult(G[85],s1,G);

tt:=plus(h[0],s1);

s2:=plus(tt,m1);

Dim3RPF[1]:=plus(s2,h[1]);

Dim3RPF[2]:=plus(s2,h[2]);

Dim3RPF[0]:=tt;

end;

//--------------------------------------------------------------------

function Dim3RPFback(h:D3vect;G:Gal):D3vect;

var s1,m1,s2,tt: m;

begin

s1:=plus(h[1],h[2]);

m1:=mult(G[170],s1,G);

tt:=plus(h[0],s1);

s2:=plus(tt,m1);

Dim3RPFback[1]:=plus(s2,h[1]);

Dim3RPFback[2]:=plus(s2,h[2]);

Dim3RPFback[0]:=tt;

end;

//--------------------------------------------------------------------

function Dim5RPF(h:D5vect;G:Gal):D5vect;

var s1,s2,s3,s4,s5,m1,m2,m3,m4,m5,s6,s7,s8,s9,s10,s11,s12,tt: m;

begin

s1:=plus(h[2],h[3]);

s2:=plus(h[1],h[4]);

s3:=plus(h[1],h[3]);

s4:=plus(h[2],h[4]);

s5:=plus(s1,s2);

tt:=plus(s5,h[0]);

Dim5RPF[0]:=tt;

m1:=mult(plus(G[0],G[153]),s5,G);

m2:=mult(plus(G[153],G[204]),s1,G);

m3:=mult(plus(G[51],G[153]),s2,G);

m4:=mult(plus(G[51],G[204]),s3,G);

m5:=mult(plus(G[51],G[204]),s4,G);

s6:=plus(tt,m1);

s7:=plus(s6,m2);

s8:=plus(s6,m3);

s9:=plus(m5,h[2]);

s10:=plus(m4,h[1]);

s11:=plus(m5,h[4]);

s12:=plus(m4,h[3]);

Dim5RPF[1]:=plus(s8,s9);

Dim5RPF[2]:=plus(s7,s10);

Dim5RPF[3]:=plus(s7,s11);

Dim5RPF[4]:=plus(s8,s12);

end;

//--------------------------------------------------------------------

//--------------------------------------------------------------------

function Dim5RPFback(h:D5vect;G:Gal):D5vect;

var s1,s2,s3,s4,s5,m1,m2,m3,m4,m5,s6,s7,s8,s9,s10,s11,s12,tt: m;

begin

s1:=plus(h[2],h[3]);

s2:=plus(h[1],h[4]);

s3:=plus(h[1],h[3]);

s4:=plus(h[2],h[4]);

s5:=plus(s1,s2);

tt:=plus(s5,h[0]);

Dim5RPFback[0]:=tt;

m1:=mult(plus(G[0],G[102]),s5,G);

m2:=mult(plus(G[102],G[51]),s1,G);

m3:=mult(plus(G[204],G[102]),s2,G);

m4:=mult(plus(G[204],G[51]),s3,G);

m5:=mult(plus(G[204],G[51]),s4,G);

s6:=plus(tt,m1);

s7:=plus(s6,m2);

s8:=plus(s6,m3);

s9:=plus(m5,h[2]);

s10:=plus(m4,h[1]);

s11:=plus(m5,h[4]);

s12:=plus(m4,h[3]);

Dim5RPFback[1]:=plus(s8,s9);

Dim5RPFback[2]:=plus(s7,s10);

Dim5RPFback[3]:=plus(s7,s11);

Dim5RPFback[4]:=plus(s8,s12);

end;

//----------------------------

function multVaryOnVary(R,B:deg3Pol; G:Gal): multPol;

var s1,s2,s3,s4,s5,s6,m1,m2,m3,m4,s7,m5,m6,m7: m;

h0,h1,h2,h3,h4,h5,h6: m;

begin

s1:=plus(r[0],r[1]);

s2:=plus(r[0],r[2]); //s2:=plus(r[0],r[2]);

s3:=plus(r[1],r[3]);

s4:=plus(s2,s3);

s5:=plus(s4,s1);

h0:=mult(r[0],b[0],G);

m1:=mult(s1,plus(b[0],b[1]),G);

m2:=mult(r[1],b[1],G);

s6:=plus(h0,m2);

h1:=plus(s6,m1);

m3:=mult(r[2],b[2],G);

h6:=mult(r[3],b[3],G);

m4:=mult(s2,plus(b[0],b[2]),G);

h2:=plus(s6,plus(m3,m4));

s7:=plus(m3,h6);

m5:=mult(s3,plus(b[1],b[3]),G);

m6:=mult(s5,plus(b[2],b[3]),G);

m7:=mult(s4,plus(plus(b[0],b[1]),plus(b[2],b[3])),G);

h5:=plus(s7,m6);

h4:=plus(s7,plus(m2,m5));

h3:=plus(plus(h1,h5),plus(m4,plus(m5,m7)));

multVaryOnVary[0]:=h0;

multVaryOnVary[1]:=h1;

multVaryOnVary[2]:=h2;

multVaryOnVary[3]:=h3;

multVaryOnVary[4]:=h4;

multVaryOnVary[5]:=h5;

multVaryOnVary[6]:=h6;

end;

//--------------------------

function multFixonVary(r:deg3Pol;G:Gal):multPol;

begin

multFixonVary[0]:=plus(r[0],mult(r[0],G[85],G));

multFixonVary[1]:=plus(plus(r[0],r[1]),mult(r[1],G[85],G));

multFixonVary[2]:=plus(plus(r[1],r[2]),mult(plus(r[0],r[2]),G[85],G));

multFixonVary[3]:=plus(plus(r[0],r[2]),plus(r[3],mult(plus(r[1],r[3]),G[85],G)));

multFixonVary[4]:=plus(plus(r[1],r[3]),mult(r[2],G[85],G));

multFixonVary[5]:=plus(r[2],mult(r[3],G[85],G));

multFixonVary[6]:=r[3];

end;

//----------------------------------

function sumBigPol(H,P:degBig):degBig;

var i: integer;

begin

for i:=0 to 18 do

sumBigPol[i]:=plus(H[i],P[i]);

end;

//--------------------------

function sum3Pol(H,P:Deg3Pol):deg3Pol;

var i: integer;

begin

for i:=0 to 3 do

sum3Pol[i]:=plus(H[i],P[i]);

end;

//----------------------

function sumSmallPol(H,P:multPol):multPol;

var i: integer;

begin

for i:=0 to 6 do

sumSmallPol[i]:=plus(H[i],P[i]);

end;

//--------------------

function sum17Pol(H,P:D17Vect):D17Vect;

var i: integer;

begin

for i:=0 to 16 do

sum17Pol[i]:=plus(H[i],P[i]);

end;

//-------------------

function PxmoDD(P:DegBig): deg15Pol;

var i: integer;

begin

for i:=15 downto 3 do

PxmoDD[i]:=P[i];

PxmoDD[2]:=plus(P[2],P[18]);

PxmoDD[1]:=plus(P[1],P[17]);

PxmoDD[0]:=plus(P[0],P[16]);

end;

//---------------------

function mult15to15deg(U:deg15Pol;G:Gal):deg15pol;

var W:deg15pol; i:integer;

U1,U2,U3,U4:deg3Pol;

W1,W2,W3,W4:deg3Pol;

F1,F2,F3,F4:multPol;

Temp1,Temp3,Temp5,Temp6,Temp7,temp4:multPol;

Temp2:Deg3Pol;

temp8,temp9,temp10:multPol;

temp11,temp12,temp13,temp14,temp15,temp16:multPol;

temp17,temp18,temp19,temp20,temp21,temp22,temp23,temp24:multPol;

vec1,vec2,vec3,vec4:degBig;

FullPol: degBig;

begin

w[0]:=powZ(G[120],8,G);

w[1]:=powZ(G[120],6,G);

w[2]:=powZ(G[120],13,G);

w[3]:=powZ(G[120],14,G);

w[4]:=powZ(G[120],2,G);

w[5]:=powZ(G[120],10,G);

w[6]:=powZ(G[120],16,G);

w[7]:=powZ(G[120],12,G);

w[8]:=powZ(G[120],9,G);

w[9]:=powZ(G[120],11,G);

w[10]:=powZ(G[120],4,G);

w[11]:=powZ(G[120],3,G);

w[12]:=powZ(G[120],15,G);

w[13]:=powZ(G[120],7,G);

w[14]:=powZ(G[120],1,G);

w[15]:=powZ(G[120],5,G);

U1[0]:=U[0];

U1[1]:=U[1];

U1[2]:=U[2];

U1[3]:=U[3];

U2[0]:=U[4];

U2[1]:=U[5];

U2[2]:=U[6];

U2[3]:=U[7];

U3[0]:=U[8];

U3[1]:=U[9];

U3[2]:=U[10];

U3[3]:=U[11];

U4[0]:=U[12];

U4[1]:=U[13];

U4[2]:=U[14];

U4[3]:=U[15];

W1[0]:=W[0];

W1[1]:=W[1];

W1[2]:=W[2];

W1[3]:=W[3];

W2[0]:=W[4];

W2[1]:=W[5];

W2[2]:=W[6];

W2[3]:=W[7];

W3[0]:=W[8];

W3[1]:=W[9];

W3[2]:=W[10];

W3[3]:=W[11];

W4[0]:=W[12];

W4[1]:=W[13];

W4[2]:=W[14];

W4[3]:=W[15];

temp1:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G); temp2:=sum3Pol(sum3Pol(U1,U2),sum3Pol(U3,U4));

temp3:=multVaryOnVary(temp2,W2,G);

temp4:=sumSmallPol(temp1,temp3);

temp5:=multVaryOnVary(sum3Pol(U1,U3),sum3Pol(W2,W3),G);

temp6:=multFixonVary(U2,G);

temp7:=sumSmallPol(temp4,temp5);

F1:=sumSmallPol(temp7,temp6);

temp8:=multVaryOnVary(sum3Pol(W1,W3),temp2,G);

temp9:=sumSmallPol(temp8,F1);

temp10:=multFixOnVary(sum3Pol(U2,U4),G);

F3:=sumSmallPol(temp10,temp9);

temp11:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);

temp12:=multVaryOnVary(temp2,sum3Pol(W1,sum3Pol(W2,W3)),G);

temp13:=sumSmallPol(temp11,temp12);

temp14:=multVaryOnVary(sum3Pol(U4,U2),sum3Pol(W1,W2),G);

temp15:=multFixOnVary(U3,G);

temp16:=sumSmallPol(temp14,Temp15);

F2:=sumSmallPol(temp16,temp13);

temp17:=multFixOnVary(temp2,G);

temp18:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);

temp19:=sumSmallPol(temp17,temp18);

temp20:=multVaryOnVary(temp2,W2,G);

temp21:=multVaryOnVary(sum3Pol(U2,U4),sum3Pol(W3,W4),G);

temp22:=sumSmallPol(temp21,temp20);

temp23:=sumSmallPol(temp22,temp19);

temp24:=multFixOnVary(U3,G);

F4:=sumSmallPol(temp24,temp23);

for i:=0 to 18 do begin

vec1[i]:='00000000';

vec2[i]:='00000000';

vec3[i]:='00000000';

vec4[i]:='00000000';

end;

vec1[0]:=F1[0];

vec1[1]:=F1[1];

vec1[2]:=F1[2];

vec1[3]:=F1[3];

vec1[4]:=F1[4];

vec1[5]:=F1[5];

vec1[6]:=F1[6];

//*x^4

vec2[4]:=F2[0];

vec2[5]:=F2[1];

vec2[6]:=F2[2];

vec2[7]:=F2[3];

vec2[8]:=F2[4];

vec2[9]:=F2[5];

vec2[10]:=F2[6];

//*x^8

vec3[8]:=F3[0];

vec3[9]:=F3[1];

vec3[10]:=F3[2];

vec3[11]:=F3[3];

vec3[12]:=F3[4];

vec3[13]:=F3[5];

vec3[14]:=F3[6];

//*x^12

vec4[12]:=F4[0];

vec4[13]:=F4[1];

vec4[14]:=F4[2];

vec4[15]:=F4[3];

vec4[16]:=F4[4];

vec4[17]:=F4[5];

vec4[18]:=F4[6];

FullPol:=sumBigPol(sumBigPol(vec1,vec2),sumBigPol(vec3,vec4));

mult15to15deg:=PxmoDD(FullPol);

end;

//-------------------

function mult15to15degobr(U:deg15Pol;G:Gal):deg15pol;

var W:deg15pol; i:integer;

U1,U2,U3,U4:deg3Pol;

W1,W2,W3,W4:deg3Pol;

F1,F2,F3,F4:multPol;

Temp1,Temp3,Temp5,Temp6,Temp7,temp4:multPol;

Temp2:Deg3Pol;

temp8,temp9,temp10:multPol;

temp11,temp12,temp13,temp14,temp15,temp16:multPol;

temp17,temp18,temp19,temp20,temp21,temp22,temp23,temp24:multPol;

vec1,vec2,vec3,vec4:degBig;

FullPol: degBig;

begin

w[0]:=powZ(G[135],8,G);

w[1]:=powZ(G[135],6,G);

w[2]:=powZ(G[135],13,G);

w[3]:=powZ(G[135],14,G);

w[4]:=powZ(G[135],2,G);

w[5]:=powZ(G[135],10,G);

w[6]:=powZ(G[135],16,G);

w[7]:=powZ(G[135],12,G);

w[8]:=powZ(G[135],9,G);

w[9]:=powZ(G[135],11,G);

w[10]:=powZ(G[135],4,G);

w[11]:=powZ(G[135],3,G);

w[12]:=powZ(G[135],15,G);

w[13]:=powZ(G[135],7,G);

w[14]:=powZ(G[135],1,G);

w[15]:=powZ(G[135],5,G);

U1[0]:=U[0];

U1[1]:=U[1];

U1[2]:=U[2];

U1[3]:=U[3];

U2[0]:=U[4];

U2[1]:=U[5];

U2[2]:=U[6];

U2[3]:=U[7];

U3[0]:=U[8];

U3[1]:=U[9];

U3[2]:=U[10];

U3[3]:=U[11];

U4[0]:=U[12];

U4[1]:=U[13];

U4[2]:=U[14];

U4[3]:=U[15];

W1[0]:=W[0];

W1[1]:=W[1];

W1[2]:=W[2];

W1[3]:=W[3];

W2[0]:=W[4];

W2[1]:=W[5];

W2[2]:=W[6];

W2[3]:=W[7];

W3[0]:=W[8];

W3[1]:=W[9];

W3[2]:=W[10];

W3[3]:=W[11];

W4[0]:=W[12];

W4[1]:=W[13];

W4[2]:=W[14];

W4[3]:=W[15];

temp1:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G); temp2:=sum3Pol(sum3Pol(U1,U2),sum3Pol(U3,U4));

temp3:=multVaryOnVary(temp2,W2,G);

temp4:=sumSmallPol(temp1,temp3);

temp5:=multVaryOnVary(sum3Pol(U1,U3),sum3Pol(W2,W3),G);

temp6:=multFixonVary(U2,G);

temp7:=sumSmallPol(temp4,temp5);

F1:=sumSmallPol(temp7,temp6);

temp8:=multVaryOnVary(sum3Pol(W1,W3),temp2,G);

temp9:=sumSmallPol(temp8,F1);

temp10:=multFixOnVary(sum3Pol(U2,U4),G);

F3:=sumSmallPol(temp10,temp9);

temp11:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);

temp12:=multVaryOnVary(temp2,sum3Pol(W1,sum3Pol(W2,W3)),G);

temp13:=sumSmallPol(temp11,temp12);

temp14:=multVaryOnVary(sum3Pol(U4,U2),sum3Pol(W1,W2),G); temp15:=multFixOnVary(U3,G);

temp16:=sumSmallPol(temp14,Temp15);

F2:=sumSmallPol(temp16,temp13);

temp17:=multFixOnVary(temp2,G);

temp18:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);

temp19:=sumSmallPol(temp17,temp18);

temp20:=multVaryOnVary(temp2,W2,G);

temp21:=multVaryOnVary(sum3Pol(U2,U4),sum3Pol(W3,W4),G);

temp22:=sumSmallPol(temp21,temp20);

temp23:=sumSmallPol(temp22,temp19);

temp24:=multFixOnVary(U3,G);

F4:=sumSmallPol(temp24,temp23);

for i:=0 to 18 do begin

vec1[i]:='00000000';

vec2[i]:='00000000';

vec3[i]:='00000000';

vec4[i]:='00000000';

end;

//*x^0

vec1[0]:=F1[0];

vec1[1]:=F1[1];

vec1[2]:=F1[2];

vec1[3]:=F1[3];

vec1[4]:=F1[4];

vec1[5]:=F1[5];

vec1[6]:=F1[6];

//*x^4

vec2[4]:=F2[0];

vec2[5]:=F2[1];

vec2[6]:=F2[2];

vec2[7]:=F2[3];

vec2[8]:=F2[4];

vec2[9]:=F2[5];

vec2[10]:=F2[6];

//*x^8

vec3[8]:=F3[0];

vec3[9]:=F3[1];

vec3[10]:=F3[2];

vec3[11]:=F3[3];

vec3[12]:=F3[4];

vec3[13]:=F3[5];

vec3[14]:=F3[6];

//*x^12

vec4[12]:=F4[0];

vec4[13]:=F4[1];

vec4[14]:=F4[2];

vec4[15]:=F4[3];

vec4[16]:=F4[4];

vec4[17]:=F4[5];

vec4[18]:=F4[6];

FullPol:=sumBigPol(sumBigPol(vec1,vec2),sumBigPol(vec3,vec4));

mult15to15degobr:=PxmoDD(FullPol);

end;

//*****************************************************************************

function Dim17RPF(v:D17Vect; G: Gal):D17Vect;

var i: integer;

firstV: D17Vect;

secondV: deg15pol;

item: D17Vect;

res: D17Vect;

U: deg15pol;

s:m;

begin

s:='00000000';

for i:=0 to 16 do

s:=plus(s,v[i]);

FirstV[0]:=s;

for i:=1 to 16 do

FirstV[i]:=v[0];

U[0]:=v[5];

U[1]:=v[1];

U[2]:=v[7];

U[3]:=v[15];

U[4]:=v[3];

U[5]:=v[4];

U[6]:=v[11];

U[7]:=v[9];

U[8]:=v[12];

U[9]:=v[16];

U[10]:=v[10];

U[11]:=v[2];

U[12]:=v[14];

U[13]:=v[13];

U[14]:=v[6];

U[15]:=v[8];

secondV:=mult15to15deg(U,G);

item[0]:='00000000';

for i:=1 to 16 do

item[i]:=secondV[i-1];

res:=sum17Pol(item,firstV);

Dim17RPF[0]:=res[0];

Dim17RPF[5]:=res[1];

Dim17RPF[8]:=res[2];

Dim17RPF[6]:=res[3];

Dim17RPF[13]:=res[4];

Dim17RPF[14]:=res[5];

Dim17RPF[2]:=res[6];

Dim17RPF[10]:=res[7];

Dim17RPF[16]:=res[8];

Dim17RPF[12]:=res[9];

Dim17RPF[9]:=res[10];

Dim17RPF[11]:=res[11];

Dim17RPF[4]:=res[12];

Dim17RPF[3]:=res[13];

Dim17RPF[15]:=res[14];

Dim17RPF[7]:=res[15];

Dim17RPF[1]:=res[16];

end;

//*****************************************************************************

function Dim17RPFobr(v:D17Vect; G: Gal):D17Vect;

var i: integer;

firstV: D17Vect;

secondV: deg15pol;

item: D17Vect;

res: D17Vect;

U: deg15pol;

s:m;

begin

s:='00000000';

for i:=0 to 16 do

s:=plus(s,v[i]);

FirstV[0]:=s;

for i:=1 to 16 do

FirstV[i]:=v[0];

U[0]:=v[5];

U[1]:=v[1];

U[2]:=v[7];

U[3]:=v[15];

U[4]:=v[3];

U[5]:=v[4];

U[6]:=v[11];

U[7]:=v[9];

U[8]:=v[12];

U[9]:=v[16];

U[10]:=v[10];

U[11]:=v[2];

U[12]:=v[14];

U[13]:=v[13];

U[14]:=v[6];

U[15]:=v[8];

secondV:=mult15to15degobr(U,G);

item[0]:='00000000';

for i:=1 to 16 do

item[i]:=secondV[i-1];

res:=sum17Pol(item,firstV);

Dim17RPFobr[0]:=res[0];

Dim17RPFobr[5]:=res[1];

Dim17RPFobr[8]:=res[2];

Dim17RPFobr[6]:=res[3];

Dim17RPFobr[13]:=res[4];

Dim17RPFobr[14]:=res[5];

Dim17RPFobr[2]:=res[6];

Dim17RPFobr[10]:=res[7];

Dim17RPFobr[16]:=res[8];

Dim17RPFobr[12]:=res[9];

Dim17RPFobr[9]:=res[10];

Dim17RPFobr[11]:=res[11];

Dim17RPFobr[4]:=res[12];

Dim17RPFobr[3]:=res[13];

Dim17RPFobr[15]:=res[14];

Dim17RPFobr[7]:=res[15];

Dim17RPFobr[1]:=res[16];

end;

//--------------------

function RPF256(c:vect;G:Gal):vect;

var i,j,k,t: integer;

A,f3,f5,f17: array[0..16,0..4,0..2] of m;

temp:D3vect;

temp1:D5Vect;

fur2:D5vect;

fur1:D3Vect;

fur3:D17Vect;

temp2:D17Vect;

s:m;

r:integer;

begin

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do begin

A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];

end;

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do begin

temp[k]:=A[i,j,k];

if k=2 then begin

fur1:=dim3RPF(temp,G);

for t:=0 to 2 do

f3[i,j,t]:=fur1[t];

end;

end;

for i:=0 to 16 do

for k:=0 to 2 do

for j:=0 to 4 do begin

temp1[j]:=f3[i,j,k];

if j=4 then begin

fur2:=dim5RPF(temp1,G);

for t:=0 to 4 do

f5[i,t,k]:=fur2[t];

end;

end;

for j:=0 to 4 do

for k:=0 to 2 do

for i:=0 to 16 do begin

temp2[i]:=f5[i,j,k];

if i=16 then begin

fur3:=dim17RPF(temp2,G);

for t:=0 to 16 do

f17[t,j,k]:=fur3[t];

end;

end;

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do

RPF256[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];

end;

//-----------------------------------------------------------------------------

function RPF256back(c:vect;G:Gal):vect;

var i,j,k,t: integer;

A,f3,f5,f17: array[0..16,0..4,0..2] of m;

temp:D3vect;

temp1:D5Vect;

fur2:D5vect;

fur1:D3Vect;

fur3:D17Vect;

temp2:D17Vect;

s:m;

r:integer;

begin

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do begin

A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];

end;

for i:=0 to 16 do

for j:=0 to 4 do

for k:=0 to 2 do begin

temp[k]:=A[i,j,k];

if k=2 then begin

fur1:=dim3RPFback(temp,G);

for t:=0 to 2 do

f3[i,j,t]:=fur1[t];

end;

end;

for i:=0 to 16 do

for k:=0 to 2 do

for j:=0 to 4 do begin

temp1[j]:=f3[i,j,k];

if j=4 then begin

fur2:=dim5RPFback(temp1,G);

for t:=0 to 4 do

f5[i,t,k]:=fur2[t];

end;

end;

for j:=0 to 4 do

for k:=0 to 2 do

for i:=0 to 16 do begin

temp2[i]:=f5[i,j,k];

Наши рекомендации