Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

11.2. Использование симметричности кода при поэтапном декодировании

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

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

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

Пример. Если есть некоторая перестановка символов, переставляющая компоненты вектора циклически на единицу вправо, то перестановки образуют группу, относительно которой инвариантен любой циклический -код. Однако часто коды будут обладать большими группами симметрии; так, можно показать, что -код Голея инварианте» слева относительно группы Матье [64].

Теорема 11.1. Вела код инвариантен относительно группы перестановок то нулевое пространство кода также инвариантно относительно группы

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

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

Пусть вектор, принадлежащий любой вектор из Тогда

но перестановка принадлежит поскольку -группа. Следовательно, вектор принадлежит а так как вектор принадлежит нулевому пространству кода то

Таким образом, вектор ортогонален любому вектору из откуда следует, что вектор принадлежит . Ч. т. д.

Теорема 11.2. Если смежный класс для кода инвариантного слева относительно перестановки то множество всех векторов, образованных применением перестановки к векторам из также является смежным классом для кода

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

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

Группа перестановок символов разбивает пространство V всех -компонентных векторов на классы. Два вектора принадлежат одному и тому же классу, если существует перестановка в группе О, для которой Если код инвариантен слева относительно группы О, то V, должен состоять из некоторого числа полных классов пространства Из теоремы 11.1 следует, что нулевое пространство кода также состоит из некоторого числа полных классов пространства

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

Пример. Рассмотрим совокупность всех -компокентных векторов над и группу циклических перестановок. 128 векторов этой совокупности разбиваются на 20 классов. По одному вектору из каждого класса представлено в табл. 11.1. Остальные векторы в каждом классе получаются как циклические сдвиги представителя этого класса. Векторы, состоящие из одних единиц или из одних нулей, порождают классы, содержащие один элемент. В остальных классах имеется по 7 векторов — 7 циклических сдвигов заданного вектора. Циклический -код, заданный в примере в разд. 8.2, включает классы и — всего 16 векторов.

Таблица 11.1 (см. скан) Классы -компонентных векторов

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

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

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

Теорема 11.3. Имеют место равенства

и

Доказательство. В соответствии с определением (11.3)

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

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

Первая часть теоремы доказана. Доказательство второй части проводится аналогично. Ч. т. д.

Теорема 11.4. Пусть некоторое -мерное подпространство пространства всех последовательностей длины и пусть его нулевое пространство, тогда

здесь суммирование ведется по всем из

Доказательство. Если принадлежит то для любого из следовательно, каждое слагаемое в сумме равно 1. Так как в пространстве всего различных векторов, то сумма равна Если не принадлежит пространству то существует по крайней мере один вектор из для которого Легко показать, что совокупность всех векторов из для которых скалярное произведение образует подпространство 1/3. Множество всех векторов для которых образует смежный класс по этому подпространству, так как если то следовательно, вектор лежит в подпространстве

Таким образом, скалярное произведение в точности для половины всех векторов а для второй половины Поэтому половина слагаемых в сумме (11.4) принимает значение и половина — значение —1, так что сумма равна 0. Ч. т. д.

Теорема 11.5. Пусть V — пространство всех последовательностей длины Тогда

и

где

(это соотношения ортогональности).

Доказательство. Так как то суммы равны. По теореме 11.3

Поэтому утверждение теоремы следует из теоремы 11.4 и того факта, что нулевое подпространство пространства V состоит одного нулевого вектора. Ч. т. д.

Теорема 11.6. Любая действительнозначная функция заданная на пространстве всех последовательностей длины

может быть представлена в виде

где

Доказательство. Рассмотрим совокупность всех действительнозначных функций заданных на пространстве V последовательностей длины Легко доказать, что они образуют векторное пространство. Множество из функций

для всех из V является базисом, поскольку такие функции линейно независимы и любая функция может быть представлена в виде линейной комбинации этих функций:

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

Соотношение (11.6) можно получить, подставляя выражение (11.5) для функции в правую часть равенства (11.6) и упрощая ее на основе результата теоремы 11.5. (Заметим, что это аналогично разложению функции в ряд Фурье.) Ч. т. д.

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

Теорема 11.7. Пусть линейный -код, инвариантный стносительно перестановок образующих группу Пусть

— функция, постоянная на каждом классе, образуемом смежными классами по подпространству Тогда 1) если не принадлежит нулевому пространству кода V, и 2) для любого и любой перестановки из группы

Доказательство. В соответствии с теоремой 11.6

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

и из теоремы 11.3. вытекает, что

где суммирование ведется по всем

Далее, по теореме 11.4,

если не принадлежит нулевому пространству кода и сумма равна если принадлежит нулевому пространству кода Таким образом, если не принадлежит нулевому пространству кода то Далее, если принадлежит нулевому пространству кода то

В соответствии с равенствами (11.1) и (11.3)

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

Равенство (11.7) можно переписать в другом виде. Обозначим класс векторов из нулевого пространства кода Положим

и обозначим значение принимаемое при всех из

Теорема 11.8. Функции взаимно ортогональны

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

где

Доказательство. Очевидно, что

Если то по теореме 11.5 каждая из трех сумм в правой части равенства равна 0. Если то, применяя снова теорему 11.5, найдем, что только сумм, для которых отличны от нуля, и каждая из них принимает значение откуда следует равенство Соотношение снова доказывается подстановкой выражения (11.10) для в равенство (11.11), а затем правая часть упрощается с помощью соотношений ортогональности (11.9) в точности тем же способом, который используется для рядов Фурье. Ч. т. д.

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

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

Скалярное произведение вычисляется по правилам операций в однако все остальные действия — обычные арифметические. Легко проверить, что (9 — 7 для любого кодового вектора, для любого другого вектора, и поэтому если функция определяется как вес образующего смежного класса, содержащего вектор то

Это лишь одна четвертая часть несоответствий среди семи вычисляемых проверочных соотношений. Конечно, для этого кода необходимо вычислить только синдром

и заметить, что если синдром равен 0, то вес образующего смежного класса равен 0, тогда как если синдром не равен 0, то вес образующего смежного класса равен 1, как в случае кода Хэмминга.

Нелегко получить нетривиальные примеры, поскольку единственный известный пока способ нахождения функций состоит в перечислении классов, на которые разбивается нулевое пространство кода. Даже для кодов умеренной длины это очень трудоемкое занятие. Конечно, нет необходимости пользоваться точным выражением для весовой функции, достаточно только найти функции для того, чтобы различать несовпадающие веса. Это несколько облегчает задачу. Другие примеры можно найти в работах [841, [111] и [112].

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление