Частотное кодирование состоит в следующем. Информационные символы Qi , i = I, 2, . . . , к, трактуются как частоты некоторого спектра. Сообщение Q = (Qf, Qf i> • - > 2i) пополняется m нулями и подвергается обратному ДПФ (ОДПФ). В результате получается несистематическое кодовое слово v длины

Принятое кодовое слово при декодировании подвергается ДПФ, что эквивалентно вычислению синдрома S. Далее одним из способов решается ключевое уравнение (могут использоваться те же приемы, что и при декодировании во временной области) и составляется полином локаторов а(г). Наконец, по векторам Sua находится рекуррентное продолжение синдрома; к компонент этого продолжения совпадают с информационным сообщением Q.

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

Исключить последний недостаток удается при комбинированной реализа1щи процессов: кодирование (систематическое) - во временной

области, декодирование - в частотной.

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

1. Вычислить ?2-точечное ДПФ, включая гп компонент синдрома.

2. Решить ключевое уравнение (достаточно найти полином локаторов) .

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

4. Взять обратное А?-точечное ДПФ, следовательно, вычислить вектор ошибки е (этот вектор должен иметь i; < 0,5т ненулевых компонент, причем степень попинома локаторов должна совпадать с числом v). Косвенная проверка правильности нахождения вектора ошибки е может состоять также в контрольном вычислении синдрома непосредственно по вектору ошибки.

5. Скорректировать принятое кодовое слово, вычитая из него вектор е, и выделить сообщение Q, отбрасывая проверочные символы.

Основное достоинство декодирования в частотной области - возможность использования быстрых алгоритмов ДПФ и ОДПФ; некоторые из этих алгоритмов будут приведены в гл. 4.

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

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

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

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

Устранить недостатки программной реализации блоковых кодов удается при использовании специальных алгебр - простых конечных полей GF(p), где р - простое число, или конечных колец (при составном р). в этом случае обычные арифметические операции заменяются модульными (см. § 1.3). Подобные операции достаточно "близки" к операциям над рациональными числами, более того - над целыми числами, причем деление в поле GF(p) всегда выполняется как бы "нацело". Выбирая в качестве модуля специальные числа, например числа Мерсенна и Ферма (см. § 4.1), можно существенно упростить операции приведения по модулю. Частотные методы кодирования и декодирования на основе ДПФ также легко реализуются в перечисленных конечных алгебрах.

Итак, бесконечные поля (вещественных и рациональных чисел), а также простые конечные поля GF(p) целесообразно использовать при программной реализации процессов помехоустойчивого кодирования - декодирования; например, при обеспечении отказоустойчивости вычислительных систем. Коды над указанными полями используются и при телепередаче данных от ЦВМ или к ЦВМ. Но в условиях взаимодействия ЦВМ и терминалов, не обладающих средствами программирования, приходится вводить специальные устройства в виде приставок, например, к телеграфным аппаратам. Такие средства (кодеры и декодеры) схемно реализуют процедуры кодирования и декодирования и могут строиться по правилам той же алгебры, которая используется в ЦВМ.

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

как правило, применяются помехоустойчивые коды над расширенными конечными полями (в основном характеристики 2) [8-11, 20, 36, 40, 43]. Сказанное справедливо также в том случае, если специализированные кодеры и декодеры выполняются на базе микропроцессоров и микро-ЭВМ. Именно такие коды над расширенными конечными полями и рассматриваются в дальнейшем.

1.3. ЭЛЕМЕНТЫ ТЕОРИИ ВЕКТОРНЫХ ПРОСТРАНСТВ

И КОНЕЧНЫХ ПОЛЕЙ

Модульные операции н простые поля. Выше отмечалось, что буквы алфавита к являются наборами из р элементов, где р - простое число. Такое ограничение на величину р объясняется тем, что только при простых числах р над множеством элементов Р = ( О, 1, .. . , р- 1 можно ввести две специальные бинарные операции Ф и © со свойствами, аналогичными сложшию и умножению вещественных чисел, в частности, допускающими выполнение обратных операций типа вычитания и деления (кроме деления на нуль), а также выделяющими нулевой О и единичный 1 элементы, для которых

ОФа=а Ф 0=а О-а = а . 0 = 0;

1 • а = а • 1 = о:,

(1.33а) (1.336) (1.33в)

где ае Р = (о, 1,... ,р- l) .

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

определяемые соотношениями: сложение Ф по модулю р

а ® b - rest

а +6

(1.34а)

умножение 0 по модулю р

а о b = rest

а • b

(1.346)

где rest[. .. ] означает остаток от деления на простое число р суммы а + b или произведения а • b -- обычных арифметических операций сложения и умножения

целых чисел из множества Р = [ О, 1, .. ., р - 1} .

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

Если в качестве модуля выбрать составное число р\ то операция деления, обратная умножению (1.346), окажется неоднозначной (или вообще невыполнимой) даже при ненулевом делителе. Например, уравнению 2х = 4 по модулю р = 6 удовлетворяют значения х = 2 и л: = 5, т. е. результат деления неоднозначен: х= (4 : 2) е (2,5).

Конечнре множество Р = ( О, 1, .. . , р - 1 мощности р с модульными операциями сложения и умножения (по модулю р), гдер- простое число, называется простым полем и обозначается GF(p).