Множества и операции над ними. Отношение принадлежности. Множество. Элемент. Унификация объектов, страница 12

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

Можно представить декодер как устройство, в котором запомнены все исправляемые конфигурации ошибок z₁...z_m, которое, если принятый вектор не является допустимым, осуществляет подбор (не более чем за m шагов) образца наиболее вероятной ошибки по условию z_l+ỹÎB, или, если это условие не выполняется, фиксирует неисправляемую ошибку. Это намного проще, чем табличное сопоставление вход и выхода декодера из первого подхода, но все-таки требует определенного числа операций и, возможно, памяти для элементов множества B.

Так как код является систематическим, проверку принадлежности можно заменить на повторное вычисление проверочных символов по информационным и сравнение с имеющимися проверочными символами. Сравнение будет заключаться в вычислении результата операции Å между вычисленным и принятым из канала проверочными символами (всего n-k результатов). Если вектор ÎB, то все результаты равны 0. Можно представить эту процедуру в виде умножения принятого вектора на проверочную матрицу:

s=ỹ·H

где H - матрица размером n´(n-k), s - вектор-строка размерности n-k, называемый вектором синдрома.

Можно проверить, что s=0 Û ỹÎB и, что два вектора ỹ и ỹ¢ тогда и только тогда принадлежат одному и тому же смежному классу, когда их синдромы совпадают. Поэтому декодер можно еще упростить, сопоставив каждому из возможных 2^n-k синдромов оценку ошибки и сигнал о необнаруженной ошибке (в пределах каждой строки таблицы синдромы одинаковые, а у разных строк они различны). Так как исправлять необходимо только ошибки в информационных символах, можно представить следующую схему декодера:

1) По принятому вектору из n разрядов вычисляется n-k разрядов вектора синдрома (схема аналогична кодеру).

2) n-k разрядов синдрома используются как адрес в памяти части образцов ошибок для информационной части из k разрядов. Еще один разряд нужен для признака неисправимой ошибки (всего 2^n-k ячеек по k+1 разрядов).

3) k разрядов из памяти поступают на схему исправления ошибок (k операций Å, выполняемых параллельно), а признак неисправимой ошибки передается получателю.

При этом, несмотря на значительное упрощение (2^n-k ячеек по k+1 разрядов против 2ⁿ ячеек по k+1 разрядов), декодер остается эквивалентным декодеру максимального правдоподобия, рассмотренному в начале лекции.

Таким образом, если используется только обнаружение ошибок, код будет или обнаруживать 2ⁿ-2^k конфигураций ошибок, а не обнаруживать 2^k-1 конфигураций ошибок. Если используется исправление ошибок, то код будет исправлять m конфигураций ошибок, обнаруживать, но не исправлять 2^k(2^n‑k‑m‑1) конфигураций ошибок, не обнаруживать 2^k-1 конфигураций ошибок, и, наконец, обнаруживать, но не правильно исправлять m(2^k-1) конфигураций ошибок.

Алгебры с двумя операциями

1. Алгебры с двумя бинарными операциями

Обозначения

<A,+,·> - Алгебра с двумя  бинарными операциями + и · на множестве A.

0 - нейтральный элемент для операции +, если он есть.

1 - нейтральный элемент для операции ·, если он есть.

-x - унарная операция вычисления обратного элемента к x в алгебре <A,+>, если ее элементы обратимые.

x^-1 - унарная операция вычисления обратного элемента к x в алгебре <A\{0},·>, если A\{0} замкнуто относительно операции · и все элементы этой алгебры обратимые.

x-y - обозначение для x+(-y).

ⁱx - степень элемента x в алгебре <A,+> ().

xⁱ - степень элемента x в алгебре <A,·> ().

- обозначение для x·y^-1.

Типы алгебр с двумя операциями.

1. Кольца

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

1)  <A,+> - коммутативная группа;

2)  <A,·> - полугруппа ( · - ассоциативная операция);

3)  Выполняются два закона дистрибутивности:

x·(y+z)=(x·y)+(x·z)

(x+y)·z=(x·z)+(y·z).