Тема 17. Двоичные групповые коды: матричное кодирование, групповые свойства и таблица стандартной расстановки. Исправление ошибок.

Рассмотрим способ задания кода, обеспечивающий свойства группы для B,+. Для этого введем операцию “умножения” двоичного вектора на двоичную матрицу, аналогичную операции умножения числового вектора на числовую матрицу. Определение получится заменой умножения на операцию & - “логическое и” и сложения на операцию- “исключающее или”. Порядок перебора индексов и требования к размерностям не изменяются. В результате получаем определение для операции · :

Можно проверить (аналогично числовым матрицам), что для операции · выполняется дистрибутивность относительно поэлементного “исключающего или”: (x+y)·M=x·M+y·M. Кроме того, если матрица невырожденнаяx·M=0 x=0(0- вектор, все компоненты которого равны 0). Эти свойства обеспечивают задание двоичного группового кода любой невырожденной двоичной матрицей, если задатьy=f(x)=x·M(здесь используется представление входных и выходных последовательностей в виде векторов-строк). Такое задание называется матричным кодированием. Проверим выполнение свойств подгруппы для множестваBпри матричном кодировании.

1. Замкнутость:

yB, zBx,tV^k:y=x·M,z=t·M y+z =x·M+t·M = (x+t)·M B

2. 0 - нейтральный элемент вA,

0=0·MB

3. Обратимость:

yB y+y=0.

Систематическому коду соответствует матрица (очевидно, невырожденная) с единичной подматрицей вида:

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

Пример задания кода - двоичный групповой систематический (3,6) код:

Схема кодирующего устройства приведена на рис. 6.

Рис. 6.

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

Рассмотрим теперь построение декодера и оценим его сложность. Всего из канала может быть получено 2ⁿразличных блоков. Если сопоставить каждому возможному входу выход декодера изkразрядов оценки и еще один разряд - признак неисправимой ошибки, потребуется память из 2ⁿ(k+1)-разрядных ячеек. Декодирование осуществляется за одну операцию выборки из памяти. Такой подход пригоден только для очень малых размеров блоков.

Для упрощения декодирования рассмотрим разбиение множества Aна смежные классы по подгруппеB:A/B={y+B|yA}. Смежный класс, порожденный нейтральным элементом - вектором0- запишем в виде первой строки таблицы, а остальные классы - следующими строками. Первая строка совпадает с самой подгруппой допустимых кодовых комбинаций0+B=B. Всего в таблице будет 2^n-kстрок по 2^kэлементов в каждой строке.

Рассмотрим условие возникновения необнаруженной ошибки. Для этого необходимо, чтобы ỹBилиy+e=z,zB. Тогда, так как в рассматриваемой группе каждый элемент обратный самому себе,e=y+zи, так какyB, по замкнутости подгруппы относительно бинарной операции +eB. Таким образом, не обнаруживаются те и только те комбинации ошибок, векторные представления которых сами являются допустимыми кодовыми комбинациями. Всего таких комбинаций будет 2^k-1, так как элемент0B- не ошибка. Запишем первую строку таблицы так, чтобы первым элементом был вектор0.

Остальные строки таблицы могут быть двух видов:

1) В строке (классе разбиения p+B) существует единственный элемент с наименьшим весом:zp+B:tp+Bw(z)w(t). Тогда такой вектор z назовемлидеромклассаp+B, выберем его порождающим элементом (любой элемент класса может быть порождающим) и запишем первым в данной строке.

2) В строке такого элемента нет - порождающим элементом выберем произвольный элемент класса и запишем первым в данной строке.

Порядок расположения остальных элементов в строках зададим такой, чтобы элемент являлся “суммой” (результатом бинарной операции +) между заголовком строки (лидером zдля строк первого типа или произвольным порождающим элементом для строк второго типа) и заголовком столбца (элементом подгруппы допустимых кодовых комбинаций. Схема построения такой таблицы показана на рис. 7.

Рис. 7

На этом рисунке mстрок первого типа и 2^n-k-mстрок второго типа. Всеми своими элементами таблица полностью покрывает множество векторов, которые могут быть получены из канала. Поэтому правило оптимального приема с исправлением ошибок будет заключаться в следующем:

1) Если принятый вектор попал в первую строку, то наиболее вероятно, что ошибок нет и =f^-1(ỹ) - то есть для систематического кода просто берутся информационные символы.

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

3) Если принятый вектор попал в одну из строк второго типа, то фиксируется обнаруженная, но не исправляемая ошибка.

Таким образом, двоичный групповой код исправляет те и только те конфигурации ошибок, которые являются лидерами в строках первого типа. На рисунке 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) конфигураций ошибок.