Линейные групповые коды
Линейными называются коды, в которых проверочные символы представляют собой линейные комбинации информационных символов.
Для двоичных кодов в качестве линейной операции используется сложение по модулю 2.
Последовательность нулей и единиц, принадлежащих данному коду, будем называть кодовым вектором.
Свойство линейных кодов:
сумма (разность) кодовых векторов линейного кода дает вектор, принадлежащий данному коду.
Линейные коды образуют алгебраическую группу по отношению к операции сложения по модулю 2. В этом смысле они являются групповыми кодами.
Свойство группового кода:
минимальное кодовое расстояние между кодовыми векторами группового кода равно минимальному весу ненулевых кодовых векторов.
Вес кодового вектора (кодовой комбинации) равен числу его ненулевых компонент.
Расстояние между двумя кодовыми векторами равно весу вектора, полученного в результате сложения исходных векторов по модулю 2. Таким образом, для данного группового кода
Wmin =d0.
Групповые коды удобно задавать матрицами, размерность которых определяется параметрами кода k и . Число строк матрицы равно k, число столбцов равно
n = k + :
Коды, порождаемые этими матрицами, известны как (n,k)-коды, соответствующие им матрицы называют порождающими (производящими, образующими).
Порождающая матрица P может быть представлена двумя матрицами Uk и H (информационной и проверочной). Число столбцов матрицы H равно , число столбцов матрицы Uk равно k
Теорией и практикой установлено, что в качестве матрицы Uk удобно брать единичную матрицу в канонической форме
Для кодов с d0 = 2 производящая матрица P имеет вид
Во всех комбинациях кода построенного при помощи такой матрицы, четное число единиц.
Для кодов с d0 3 порождающая матрица не может быть представлена в форме, общей для всех кодов с данным d0. Вид матрицы зависит от конкретных требований к порождающему коду. Этими требованиями могут быть либо минимум корректирующих разрядов, либо максимальная простота аппаратуры.
Корректирующие коды с минимальным количеством избыточных разрядов называют плотно упакованными или совершенными кодами.
Для кодов d0 = 3 соотношения n и k следующие: (3; 1), (7; 4), (15; 11), (31; 26), (63; 57) и так далее.
Строчки образующей матрицы P представляют собой k комбинаций искомого кода. Остальные комбинации кода строятся при помощи образующей матрицы по следующему правилу: корректирующие символы, предназначенные для обнаружения и исправления ошибки в информационной части кода, находятся путем суммирования по модулю 2 тех строк матрицы H, номера которых совпадают с номерами разрядов, содержащих единицы в кодовом векторе, представляющем информационную часть кода. Полученную комбинацию приписывают справа к информационной части кода и получают полный вектор корректирующего кода. Аналогичную процедуру проделывают со второй, третьей и последующими информационными кодовыми комбинациями, пока не будет построен корректирующий код для передачи всех символов первичного алфавита.
Алгоритм образования проверочных символов по известной информационной части кода может быть записан следующим образом
или
.
В процессе декодирования осуществляются проверки, идея которых в общем виде может быть представлена следующим образом
Для каждой конкретной матрицы существует своя, одна-единственная система проверок. Проверки производятся по следующему правилу : в первую проверку вместе с проверочным рядом b1 входят информационные разряды, которые соответствуют единицам первого столбца проверочной матрицы H; во вторую проверку входит второй проверочный разряд b2 и информационные разряды, и т. д. Число проверок равно числу проверочных разрядов корректирующего кода .
В результате осуществления проверок образуется проверочный вектор S1, S2, ..., S, который называется синдромом. Если вес синдрома равен нулю, то принятая комбинация считается безошибочной. Если хотя бы один разряд проверочного вектора содержит единицу, то принятая комбинация содержит ошибку. Исправление ошибки производится по виду синдрома, так как каждому ошибочному разряду соответствует один единственный проверочный вектор.
Вид синдрома для каждой конкретной матрицы может быть определен при помощи проверочной матрицы Н’, которая представляет собой транспонированную матрицу H, дополненной единичной матрицей I, число столбцов которой равно число проверочных разрядов кода
Н’ = HТI.
Столбцы такой матрицы представляют собой значение синдрома для разряда, соответствующего номеру столбца матрицы Н’.
Процедура исправления ошибок в процессе декодирования групповых кодов сводится к следующему.
Строится кодовая таблица. В первой строке таблицы располагаются все кодовые векторы Ai. В первом столбце второй строки размещается вектор a1, вес которого равен 1.
Остальные позиции второй строки заполняются векторами, полученными в результате суммирования по модулю 2 вектора a1 с Аi, расположенным в соответствующем столбце первой строки. В первом столбце третьей строки записывается вектор a2, вес которого также равен 1, однако , если вектор a1 содержит единицу в первом разряде, то a2 - во втором. В остальные позиции третьей строки записывают суммы Аi и a2 .
Аналогично поступают до тех пор, пока не будут просуммированы с векторами Аi все векторы aj весом 1, с единицей в каждом из n разрядов. Затем суммируются по модулю 2 векторы aj, весом 2, с последовательным перекрытием всех возможных разрядов. Вес вектора aj определяет число исправляемых ошибок. Число векторов aj определяется возможным числом неповторяющихся синдромов и равно 2-1 (нулевая комбинация говорит об отсутствии ошибки). Условие неповторяемости синдрома позволяет по его виду определять один-единственный соответствующий ему вектор aj. Векторы aj есть векторы ошибок, которые могут быть исправлены данным групповым кодом.
По виду синдрома принятая комбинация может быть отнесена к тому или иному смежному классу, образованному сложением по модулю 2 кодовой комбинации Аi с вектором ошибки aj, т. е. к определенной строке кодовой таблицы 3.2.1.
Таблица 3.2.1- Кодовая таблица групповых кодов
a | A1 | A2 | ... | A(2k-1) |
a1 | a1A1 | a2A2 | ... | a1A(2k-1) |
a2 | a2A1 | a2A2 | ... | a2A(2k-1) |
... | ... | ... | ... | ... |
a(2-1) | a(2 - 1)A1 | a(2-1)A2 | ... | a(2-1)A(2k-1) |
Принятая кодовая комбинация Axn сравнивается с векторами, записанными в строке, соответствующей полученному в результате проверок синдрому. Истинный код будет расположен в строке той же колонки таблицы. Процесс исправления ошибки заключается в замене на обратное значение разрядов.
Векторы a1, a2, ...,a(2-1) не должны быть равными ни одному из векторов А1, А2, ..., А(2-1), в противном случае в таблице появились бы нулевые векторы.
Пример.
Построить кодовую таблицу, при помощи которой обнаруживаются и исправляются все одиночные ошибки и некоторые ошибки кратностью r + 1, в информационной части кода (11,7), построенного по матрице
Решение.
Используя таблицу 3.2.1, строим кодовую таблицу 3.2.2 для кодов, построенных по данной матрице P, кодовые комбинации строятся путем добавления к четырехразрядным комбинациям натурального двоичного кода корректирующих разрядов по правилу, описанному выше.
Определяем систему проверок исходя из матрицы H
Находим вид синдрома для каждой строки таблицы. Для этого достаточно произвести проверки для кодовых комбинаций любого столбца кодовой таблицы.
Для нашего примера возьмем столбец A3 .
Таблица 3.2.1 – Пример таблицы для столбца А3
№ | e | A1 1000111 | A2 0100011 | A3 1100100 | A4 0010110 | A5 1010001 | A6 0110101 | A7 1110010 |
1 2 3 4 5 6 7 | 1000000 0100000 0010000 0001000 1100000 1001000 1010000 | 0000111 1100111 1010111 1001111 0100111 0001111 0010111 | 1100011 0000011 0110011 0101011 1000011 1101011 1110011 | 0100100 1000100 1110100 1101100 0000100 0101100 0110100 | 1010110 0110110 0000110 0011110 1110110 1011110 1000110 | 0010001 1110001 1000001 1011001 0110001 0011001 0000001 | 1110101 0010101 0100101 0111101 1010101 1111101 1100101 | 0110010 1010010 1100010 1111010 0010010 0111010 0100010 |
|
|
|
|
|
|
|
|
|
№ | A8 0001101 | A9 1001010 | A10 0101110 | A11 1101001 | A12 0011011 | A13 1011100 | A14 0111000 | A15 1111111 |
1 2 3 4 5 6 7 | 1001101 0101101 0011101 0000101 1101101 1000101 1011101 | 0001010 1101010 1011010 1000010 0101010 0000010 0011010 | 1101110 0001110 0111110 0100110 1001110 1100110 1111110 | 0101001 1001001 1111001 1100001 0001001 0100001 0111001 | 1011011 0111011 0001011 0010011 1111011 1010011 1001011 | 0011100 1111100 1001100 1010100 0111100 0010100 0001100 | 1111000 0011000 0101000 0110000 1011000 1110000 1101000 | 0111111 1011111 1101111 1110111 0011111 0110111 0101111 |
-
0 1 0 0 1 0 0
-
1 0 0 0 1 0 0
-
1 1 1 0 1 0 0
-
1 1 0 1 1 0 0
-
0 0 0 0 1 0 0
-
0 1 0 1 1 0 0
-
0 1 1 0 1 0 0
Таким образом вектору ошибки a1 соответствует синдром 1 1 1
“ a2 “ 0 1 1
“ a3 “ 1 1 0
“ a4 “ 1 0 1
“ a5 “ 1 0 0
“ a6 “ 0 1 0
“ a7 “ 0 0 1
Предположим, приняты комбинации 1011001, 1000101, 0001100, 0000001 и 1010001. Производим проверки
Синдром первой принятой комбинации - 101, значит вектор ошибки а4 = 0001000, исправление ошибки производится заменой символа в четвертом разряде принятой комбинации на обратный. Истинная комбинация - А5, так как принятая комбинация находится в шестом столбце таблицы в строке, соответствующей синдрому 101.
Синдром второй принятой комбинации - 010, находим ее в шестой строке (010 соответствует а6) и в девятом столбце. Истинная комбинация А8 = 0001101, т.е. исправлена двойная ошибка.
Синдром третьей принятой комбинации - 001 соответствует а7, истинная комбинация А13.
Синдром четвертой из принятых комбинаций - 001 также соответствует а7, но принятую комбинацию мы находим в шестом столбце таблицы , следовательно, истинная комбинация - А5.
Синдром шестой принятой комбинации - 000. Ошибки нет.
- Введение
- Элементы теории чисел
- Модулярная арифметика
- Алгоритм Евклида для нахождения наибольшего общего делителя
- Вычисление обратных величин
- Основные способы нахождения обратных величин
- Расширенный алгоритм Евклида
- Китайская теорема об остатках
- Квадратичные вычеты
- Вычисления в конечных полях
- Свойства многочленов в двоичном поле gf(2)
- Достоинства вычислений в поле Галуа gf(2 n)
- Кодирование
- Оптимальное кодирование
- Обнаружение и исправление ошибок
- Общие понятия
- Линейные групповые коды
- Код Хэмминга
- Циклические коды
- Построение и декодирование конкретных циклических кодов
- Циклические коды, исправляющие две и большее количество ошибок, d0 5
- Сжатие информации
- Исключение повторения строк в последующих строках
- Алгоритм lzw
- Задания для самостоятельного выполнения
- Расчетно-графическая работа №1
- Расчетно-графическая работа №2
- Список рекомендуемой литературы
- Рекомендованная литература