1.7. Стандартное расположение кода

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

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

Однако существенный прогресс в области микроэлектроники и создание больших объемов памяти при относительно небольших ее геометрических размерах позволяют применить такие методы обработки кодовых векторов, которые были бы невозможны десятилетия назад. И в современных условиях задача декодирования заключается в том, чтобы максимально использовать введенную в код избыточность. Одним из таких методов является метод декодирования блоковых кодов на основе стандартной расстановки [79,82, 84].

Пусть – групповой  двоичный (n,k,d) код,  – единичный элемент группы (нулевой вектор) и , , …,  – остальные кодовые векторы. Тогда таблицу декодирования для аддитивной группы можно составить следующим образом. Кодовые векторы располагаются в виде строки с нулевым вектором слева. Затем один из оставшихся наборов длины , например,  помещается под нулевым вектором. Обычно это бывает один из наиболее вероятных образцов ошибок, который приемник получает на своем выходе, при условии, что по каналу передавался нулевой вектор. Далее строка заполняется так, чтобы под каждым кодовым вектором  помещался вектор (знак  означает сложение по модулю два). Аналогично в первый столбец второй строки помещается вектор  и строка заполняется таким же способом. Процесс продолжается до тех пор, пока каждый возможный набор длины  не появится где-нибудь в таблице. Так же как и в мультипликативной группе строки аддитивной группы являются смежными классами,  а векторы в первом столбце  представляют  образующие смежных классов. Подобная конструкция группы получила название стандартной расстановки (стандартного расположения) кода. Стандартное расположение полезно при анализе  и блоковых, и сверточных кодов. Рассмотрим несколько результатов, относящихся к стандартному расположению блоковых кодов.  На первом этапе уточним, что код  исправляет только одиночные ошибки. Пусть ,   … , тогда в сочетании с элементами  подгруппы веса три  (весовой спектр кода приведен выше) будет образовано   комбинация веса два. Это означает, что все двукратные ошибки вошли в состав смежных классов  с образующими , , …. Параметры кода по исправлению всех образцов одиночных ошибок подтверждаются. Рассмотрим другой  групповой код. Стандартное расположение кода представлено в табл. 1.4.

Табл. 1.4 Стандартная расстановка кода (5,2,3)

00000	0	01011		10110		11101
00001		01010		10111		11100
00010		01001		10100		11111
00100		01111		10010		11001
01000		00011		11110		10101
10000		11011		00110		01101
10001		11010		00111		01100
01100		00111		11010		10001
11000		10011		01110		00101
00101		01100		10011		11000

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

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

Если образующий смежного класса  имеет вес равный единице, то в сочетании с векторами подгрупп веса три будут образованы элементы смежных классов с весом два. Легко убедиться  в том, что таких векторов будет ровно 6, но , следовательно, . Это означает, что укороченный код способен исправить некоторые образцы двукратных ошибок. Такие образцы представлены в столбце образующих смежных классов курсивом (см. табл. 1.4). Дальнейший анализ показывает, что образец ошибки вида 10001   в качестве элемента смежного класса содержит комбинацию вида 01100, следовательно, выделенный в таблице образующий смежного класса 01100  не может быть принят в качестве такового. Аналогичные рассуждения справедливы для   значений  и .  Из анализа стандартной расстановки  следует, что имеется два сочетания  двойных ошибок, а именно: 10001  и  11000, которые  могут быть исправлены декодером,  хотя минимальное расстояние кода осталось равным 3. Таким образом, процедура укорочения кода приводит к повышению кратности исправляемых ошибок, образцы которых подлежат уточнению. 

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

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

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

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

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

Если при делении значения принятого вектора на полином  синдром оказался не равен нулевому значению, это означает, что приемник может  определить номер смежного класса и затем по таблице отыскивается образующий смежного класса, являющийся предполагаемым вектором ошибок. Вычитание его из полученного вектора с высокой вероятностью обеспечивает получение переданного кодового вектора. В большинстве важных с практической точки зрения случаев такая процедура во много раз уменьшает требования к объему памяти при осуществлении декодирования, но этот объем все-таки может быть очень большим. Например, для двоичного (40,32,4) кода, используемого в системе АТМ требуется таблица декодирования с числом входов , что, конечно, выходит за пределы разумного. Число же смежных классов равно , что приемлемо для практического использования. Подобное соотношение смежных классов и синдромов для кода (5,2,3) представлено в табл. 1.5.

Табл. 1.5 Соотношение образующих смежных классов и синдромов для  кода

Образующий смежного класса	00000	00001	00010	00100	01000	10000	10001	11000
Синдром	000	001	010	100	011	110	111	101

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

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

Чтобы задать автомат,  необходимо указать три множества:

•  множество сигналов на   входе  устройства;
•  множество   состояний  автомата;
•  множество сигналов на выходе  устройства.

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

,     ,

где   и  .

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

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

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

Функционирование автомата отнюдь не исчерпывается реагированием на отдельные сигналы. На вход автомата может поступать  серия сигналов, идущих один за другим. Пусть, например, автомат находится во внутреннем состоянии , и на его вход поступает сначала сигнал х1, а затем сигнал х2. После поступления сигнала х1 автомат переходит в новое внутреннее состояние f(х1,a), а на выходе «выдает» сигнал g(х1, a). Следующий сигнал на входе х2 «застает» автомат  во внутреннем  состоянии f(х1,a) и  переводит  его в состояние f(х2, f(х1,a)). Сигнал на выходе также изменяется и переходит в g(х2, f(х1,a)).

Как показывают аналогичные рассуждения, если автомат первоначально находится во внутреннем состоянии а и на вход поступают сигналы х1, х2,  х3, то автомат перейдет из состояния а в конечное состояние f(х3, f(х2, f(х1,a))), а на выходе последовательно появятся сигналы g( х1, a), g(х2, f(х1,a)), g(х3, f(х2, f(х1,a))). Разумеется, это соответствие  не означает, что, если автомат нахо­дится в состоянии а и на вход посту­пает сигнал х2, то на выходе появля­ется сигнал y2, а если на вход пода­ется сигнал x3, то па выходе возни­кает сигнал y3, поскольку сигнал на выходе зависит не только от сигнала на входе, но и от внутреннего состояния автомата, а состояния а1 = f(х1,a) и  а2 = f(х2, а1)  отличаются   от   исходного.

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