[Из песочницы] Систематические корректирующие коды. Линейно групповой код
В данной публикации будет рассматриваться линейно групповой код, как один из представителей систематических корректирующих кодов и предложена его реализация на C++.
Что из себя представляет из себя корректирующий код. Корректирующий код — это код направленный на обнаружение и исправление ошибок. А систематические коды — Это коды, в которых контрольные и информационные разряды размещаются по определенной системе. Одним из таких примеров может служить Код Хэмминга или собственно линейно групповые коды.
Линейно групповой код состоит из информационных бит и контрольных. Например, для исходной комбинации в 4 символа, линейно групповой код будет выглядеть вот так:
|1100|110|
Где первые 4 символа это наша исходная комбинация, а последние 3 символа это контрольные биты.
Общая длина линейно группового кода составляет 7 символов. Если число бит исходной комбинации нам известно, то чтобы вычислить число проверочных бит, необходимо воспользоваться формулой:
$$display$$d=log (n+1+log (n+1))$$display$$
Где n — это число информационных бит, то есть длина исходной комбинации, и log по основанию 2. И общая длина N кода будет вычисляться по формуле:
$$display$$N=n+d$$display$$
Допустим исходная комбинация будет составлять 10 бит.
$$display$$d=log (10+1+log (10+1))$$display$$
$$display$$d=3,867$$display$$
d всегда округляется в большую сторону, и d=4.
И полная длина кода будет составлять 14 бит.
Разобравшись с длиной кода, нам необходимо составить производящую и проверочную матрицу.
Производящая матрица, размерностью N на n, где N — это длина линейно группового кода, а n — это длина информационной части линейно группового кода. По факту производящая матрица представляет из себя две матрицы: единичную размерностью m на m, и матрицу контрольных бит размерностью d на n. Если единичная матрица составляется путём расставления единиц по главной диагонали, то составление «контрольной» части матрицы имеет некоторые правила. Проще объяснить на примере. Мы возьмем уже известную нам комбинацию из 10 информационных битов, но добавим коду избыточность, и добавим ему 5-ый контрольный бит. Матрица будет иметь размерность 15 на 10.
1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 1 1 1 1 0
0 0 1 0 0 0 0 0 0 0 1 1 1 0 1
0 0 0 1 0 0 0 0 0 0 1 1 0 1 1
0 0 0 0 1 0 0 0 0 0 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 1 1«Контрольная» часть составляется по схеме уменьшения двоичного числа и соблюдения минимального кодового расстояния между строками: в нашем случае это 11111, 11110, 11101…
Минимальное кодовое расстояние для комбинации будет вычисляться по формуле:
Wp=r+s
Где r — это ранг обнаруживаемой ошибки, а s — ранг исправляемой ошибки.
В нашем случае ранг исправляемой и обнаруживаемой ошибки 1.
Также необходимо составить проверочную матрицу. Она составляется путём транспонирования «контрольной» части и после неё добавляется единичная матрица размерности d на d.
1 1 1 1 1 0 1 1 1 0 1 0 0 0 0
1 1 1 1 0 1 1 1 0 1 0 1 0 0 0
1 1 1 0 1 1 1 0 0 0 0 0 1 0 0
1 1 0 1 1 1 0 0 1 1 0 0 0 1 0
1 0 1 1 1 1 0 1 1 1 0 0 0 0 1
Составив матрицы, мы уже можем написать линейно групповой код, путём суммирования строк производящей матрицы под номерами ненулевых бит исходного сообщения.
Рассмотрим этот этап на примере исходного сообщения 1001101010.
Линейно групповой код: 100110101011100
Сразу обозначим, что контрольные разряды в ЛГК определяются по правилам чётности суммы соответствующих индексов, в нашем случае, эти суммы составляют: 5,3,3,4,4. Следовательно, контрольная часть кода выглядит: 11100.
В результате мы составили линейно групповой код. Однако, как уже говорилось ранее, линейно групповой код имеет исправляющую способность, в нашем случае, он способен обнаружить и исправить одиночную ошибку.
Допустим, наш код был отправлен с ошибкой в 6-ом разряде. Для определения ошибок в коде служит, уже ранее составленная проверочная матрица
Для того, чтобы определить, в каком конкретно разряде произошла ошибка, нам необходимо узнать «синдром ошибки». Синдром ошибки вычисляется методом проверок по ненулевым позициям проверочной матрицы на чётность. В нашем случае этих проверок пять, и мы проводим наше полученное сообщение через все эти проверки.
$$display$$S1=n1+n2+n3+n4+n5+n7+n8+n9+n11$$display$$
$$display$$S2=n1+n2+n3+n4+n6+n7+n8+n10+n12$$display$$
$$display$$S3=n1+n2+n3+n5+n6+n7+n13$$display$$
$$display$$S4=n1+n2+n4+n5+n6+n9+n10+n14$$display$$
$$display$$S5=n1+n3+n4+n5+n6+n8+n9+n10+n15$$display$$
Получив двоичное число, мы сверяем его со столбцами проверочной матрицы. Как только находим соответствующий «синдром», определяем его индекс, и выполняем инверсию бита по полученному индексу.
В нашем случае синдром равен: 01111, что соответствует 6-му разряду в ЛГК. Мы инвертируем бит и получаем корректный линейно групповой код.
Декодирование скорректированного ЛГК происходит путём простого удаления контрольных бит. После удаления контрольных разрядов ЛГК мы получаем исходную комбинацию, которая была отправлена на кодировку.
В заключение можно сказать, что такие корректирующие коды как линейно групповые коды, Код Хэмминга уже достаточно устарели, и в своей эффективности однозначно уступят своим современным альтернативам. Однако они вполне справляются с задачей познакомится с процессом кодирования двоичных кодов и методом исправления ошибок в результате воздействия помех на канал связи.
Реализация работы с ЛГК на C++:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
setlocale(LC_ALL, "Russian");
cout<<"Производящая матрица:"<>str;
if(str.size()!=10)
{
cout<<"Недопустимая размерность строки!"< arr;
for(int i=0;i S;
vector > R;
for(int i=0;i<10;i++)
{
if(arr[i]==1)
{
vector T;
for(int j=0;j<15;j++)
{
T.push_back(matr[i][j]);
}
R.push_back(T);
}
}
cout<>::iterator it=R.begin();it!=R.end();it++)
{
copy((*it).begin(),(*it).end(),ostream_iterator(cout,"\t"));
cout<<"\n";
}
cout< P;
for(int i=0; i<15;i++)
{
int PT=0;
for(int j=0; j
Источники:
1. StudFiles — файловый архив студентов [Электронный ресурс] studfiles.net/preview/4514583/page:2/.
2. Задачник по теории информации и кодированию [Текст] / В.П. Цымбал. — Изд. объед. «Вища школа», 1976. — 276 с.
3. Тенников, Ф.Е. Теоретические основы информационной техники / Ф.Е. Тенников. — М.: Энергия, 1971. — 424 с.
