В данной публикации будет рассматриваться линейно групповой код, как один из представителей систематических корректирующих кодов и предложена его реализация на C++.
Что из себя представляет корректирующий код. Корректирующий код – это код направленный на обнаружение и исправление ошибок. А систематические коды — Это коды, в которых контрольные и информационные разряды размещаются по определенной системе. Одним из таких примеров может служить Код Хэмминга или собственно линейно групповые коды.
Линейно групповой код состоит из информационных бит и контрольных. Например, для исходной комбинации в 4 символа, линейно групповой код будет выглядеть вот так:
Где первые 4 символа это наша исходная комбинация, а последние 3 символа это контрольные биты.
Общая длина линейно группового кода составляет 7 символов. Если число бит исходной комбинации нам известно, то чтобы вычислить число проверочных бит, необходимо воспользоваться формулой:
Где n — это число информационных бит, то есть длина исходной комбинации, и log по основанию 2. И общая длина N кода будет вычисляться по формуле:
Допустим исходная комбинация будет составлять 10 бит.
d всегда округляется в большую сторону, и d=4.
И полная длина кода будет составлять 14 бит.
Разобравшись с длиной кода, нам необходимо составить производящую и проверочную матрицу.
Производящая матрица, размерностью N на n, где N — это длина линейно группового кода, а n — это длина информационной части линейно группового кода. По факту производящая матрица представляет из себя две матрицы: единичную размерностью m на m, и матрицу контрольных бит размерностью d на n. Если единичная матрица составляется путём расставления единиц по главной диагонали, то составление «контрольной» части матрицы имеет некоторые правила. Проще объяснить на примере. Мы возьмем уже известную нам комбинацию из 10 информационных битов, но добавим коду избыточность, и добавим ему 5-ый контрольный бит. Матрица будет иметь размерность 15 на 10.
«Контрольная» часть составляется по схеме уменьшения двоичного числа и соблюдения минимального кодового расстояния между строками: в нашем случае это 11111, 11110, 11101…
Минимальное кодовое расстояние для комбинации будет вычисляться по формуле:
Где r – это ранг обнаруживаемой ошибки, а s – ранг исправляемой ошибки.
В нашем случае ранг исправляемой и обнаруживаемой ошибки 1.
Также необходимо составить проверочную матрицу. Она составляется путём транспонирования «контрольной» части и после неё добавляется единичная матрица размерности d на d.
Составив матрицы, мы уже можем написать линейно групповой код, путём суммирования строк производящей матрицы под номерами ненулевых бит исходного сообщения.
Рассмотрим этот этап на примере исходного сообщения 1001101010.
Линейно групповой код: 100110101011100
Сразу обозначим, что контрольные разряды в ЛГК определяются по правилам чётности суммы соответствующих индексов, в нашем случае, эти суммы составляют: 5,3,3,4,4. Следовательно, контрольная часть кода выглядит: 11100.
В результате мы составили линейно групповой код. Однако, как уже говорилось ранее, линейно групповой код имеет исправляющую способность, в нашем случае, он способен обнаружить и исправить одиночную ошибку.
Допустим, наш код был отправлен с ошибкой в 6-ом разряде. Для определения ошибок в коде служит, уже ранее составленная проверочная матрица
Для того, чтобы определить, в каком конкретно разряде произошла ошибка, нам необходимо узнать «синдром ошибки». Синдром ошибки вычисляется методом проверок по ненулевым позициям проверочной матрицы на чётность. В нашем случае этих проверок пять, и мы проводим наше полученное сообщение через все эти проверки.
Получив двоичное число, мы сверяем его со столбцами проверочной матрицы. Как только находим соответствующий «синдром», определяем его индекс, и выполняем инверсию бита по полученному индексу.
В нашем случае синдром равен: 01111, что соответствует 6-му разряду в ЛГК. Мы инвертируем бит и получаем корректный линейно групповой код.
Декодирование скорректированного ЛГК происходит путём простого удаления контрольных бит. После удаления контрольных разрядов ЛГК мы получаем исходную комбинацию, которая была отправлена на кодировку.
В заключение можно сказать, что такие корректирующие коды как линейно групповые коды, Код Хэмминга уже достаточно устарели, и в своей эффективности однозначно уступят своим современным альтернативам. Однако они вполне справляются с задачей познакомиться с процессом кодирования двоичных кодов и методом исправления ошибок в результате воздействия помех на канал связи.
Реализация работы с ЛГК на C++:
Источники:
1. StudFiles – файловый архив студентов [Электронный ресурс] studfiles.net/preview/4514583/page:2/.
2. Задачник по теории информации и кодированию [Текст] / В.П. Цымбал. – Изд. объед. «Вища школа», 1976. – 276 с.
3. Тенников, Ф.Е. Теоретические основы информационной техники / Ф.Е. Тенников. – М.: Энергия, 1971. – 424 с.
Что из себя представляет корректирующий код. Корректирующий код – это код направленный на обнаружение и исправление ошибок. А систематические коды — Это коды, в которых контрольные и информационные разряды размещаются по определенной системе. Одним из таких примеров может служить Код Хэмминга или собственно линейно групповые коды.
Линейно групповой код состоит из информационных бит и контрольных. Например, для исходной комбинации в 4 символа, линейно групповой код будет выглядеть вот так:
|1100|110|Где первые 4 символа это наша исходная комбинация, а последние 3 символа это контрольные биты.
Общая длина линейно группового кода составляет 7 символов. Если число бит исходной комбинации нам известно, то чтобы вычислить число проверочных бит, необходимо воспользоваться формулой:
Где n — это число информационных бит, то есть длина исходной комбинации, и log по основанию 2. И общая длина N кода будет вычисляться по формуле:
Допустим исходная комбинация будет составлять 10 бит.
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-ом разряде. Для определения ошибок в коде служит, уже ранее составленная проверочная матрица
Для того, чтобы определить, в каком конкретно разряде произошла ошибка, нам необходимо узнать «синдром ошибки». Синдром ошибки вычисляется методом проверок по ненулевым позициям проверочной матрицы на чётность. В нашем случае этих проверок пять, и мы проводим наше полученное сообщение через все эти проверки.
Получив двоичное число, мы сверяем его со столбцами проверочной матрицы. Как только находим соответствующий «синдром», определяем его индекс, и выполняем инверсию бита по полученному индексу.
В нашем случае синдром равен: 01111, что соответствует 6-му разряду в ЛГК. Мы инвертируем бит и получаем корректный линейно групповой код.
Декодирование скорректированного ЛГК происходит путём простого удаления контрольных бит. После удаления контрольных разрядов ЛГК мы получаем исходную комбинацию, которая была отправлена на кодировку.
В заключение можно сказать, что такие корректирующие коды как линейно групповые коды, Код Хэмминга уже достаточно устарели, и в своей эффективности однозначно уступят своим современным альтернативам. Однако они вполне справляются с задачей познакомиться с процессом кодирования двоичных кодов и методом исправления ошибок в результате воздействия помех на канал связи.
Реализация работы с ЛГК на C++:
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>
#include <cctype>
#include <cmath>
using namespace std;
int main()
{
setlocale(LC_ALL, "Russian");
cout<<"Производящая матрица:"<<endl;
int matr [10][15]={{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}};
for(int i=0;i<10;i++)
{
for(int j=0;j<15;j++)
{
cout<<matr[i][j]<<' ';
}
cout<<endl;
}
cout<<"Проверочная матрица:"<<endl;
int matr_2 [5][15]={{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}};
for(int i=0;i<5;i++)
{
for(int j=0;j<15;j++)
{
cout<<matr_2[i][j]<<' ';
}
cout<<endl;
}
cout<<"Введите комбинацию: "<<endl;
string str;
bool flag=false;
while(flag!=true)
{
cin>>str;
if(str.size()!=10)
{
cout<<"Недопустимая размерность строки!"<<endl;
flag=false;
}
else
flag=true;
}
vector <int> arr;
for(int i=0;i<str.size();i++)
{
if(str[i]=='1')
arr.push_back(1);
else if(str[i]=='0')
arr.push_back(0);
}
cout<<"Ваша комбинация: ";
for(int i=0;i<arr.size();i++)
cout<<arr[i];
cout<<endl;
vector <int> S;
vector <vector<int>> R;
for(int i=0;i<10;i++)
{
if(arr[i]==1)
{
vector <int> T;
for(int j=0;j<15;j++)
{
T.push_back(matr[i][j]);
}
R.push_back(T);
}
}
cout<<endl;
cout<<"Суммиирвоание строк для построения группового кода: "<<endl;
for(vector <vector<int>>::iterator it=R.begin();it!=R.end();it++)
{
copy((*it).begin(),(*it).end(),ostream_iterator<int>(cout,"\t"));
cout<<"\n";
}
cout<<endl;
vector <int> P;
for(int i=0; i<15;i++)
{
int PT=0;
for(int j=0; j<R.size();j++)
{
PT+=R[j][i];
}
P.push_back(PT);
}
for(int i=10; i<15;i++)
{
if(P[i]%2==0)
P[i]=0;
else if(P[i]%2!=0)
P[i]=1;
}
cout<<endl<<"Групповой линейный код: "<<endl;
for(int i=0; i<P.size();i++)
{
cout<<P[i]<<' ';
}
int rand_i;
rand_i=5;
cout<<endl<<"В сообщении сгенерирована ошибка: ";
if(P[rand_i]==0)
P[rand_i]=1;
else if(P[rand_i]==1)
P[rand_i]=0;
for(int i=0; i<P.size();i++)
{
cout<<P[i]<<' ';
}
int S1, S2, S3, S4, S5;
//Проверки на чётность
S1=P[0]+P[1]+P[2]+P[3]+P[4]+P[6]+P[7]+P[8]+P[10];
S2=P[0]+P[1]+P[2]+P[3]+P[5]+P[6]+P[7]+P[9]+P[11];
S3=P[0]+P[1]+P[2]+P[4]+P[5]+P[6]+P[12];
S4=P[0]+P[1]+P[3]+P[4]+P[5]+P[8]+P[9]+P[13];
S5=P[0]+P[2]+P[3]+P[4]+P[5]+P[7]+P[8]+P[9]+P[14];
//Составление синдрома
if(S1%2==0)
{
S1=0;
}
else if(S1%2!=0)
{
S1=1;
}
if(S2%2==0)
{
S2=0;
}
else if(S2%2!=0)
{
S2=1;
}
if(S3%2==0)
{
S3=0;
}
else if(S3%2!=0)
{
S3=1;
}
if(S4%2==0)
{
S4=0;
}
else if(S4%2!=0)
{
S4=1;
}
if(S5%2==0)
{
S5=0;
}
else if(S5%2!=0)
{
S5=1;
}
cout<<endl<<"Синдром ошибки: "<<S1<<S2<<S3<<S4<<S5<<endl;
int mas_s[5]={S1,S2,S3,S4,S5};
int index_j=0;
bool flag_s=false;
for(int i=0;i<15;i++)
{
if((matr_2[0][i]==mas_s[0])&&(matr_2[1][i]==mas_s[1])&&(matr_2[2][i]==mas_s[2])&&(matr_2[3][i]==mas_s[3])&&(matr_2[4][i]==mas_s[4]))
{
index_j=i;
}
}
cout<<endl<<"Разряд ошибки: "<<index_j+1<<endl;
if(P[index_j]==0)
P[index_j]=1;
else if(P[index_j]==1)
P[index_j]=0;
cout<<"Исправленный код: ";
for(int i=0; i<P.size();i++)
{
cout<<P[i]<<' ';
}
cout<<endl;
P.erase(P.begin()+14);
P.erase(P.begin()+13);
P.erase(P.begin()+12);
P.erase(P.begin()+11);
P.erase(P.begin()+10);
cout<<"Исходный код: ";
for(int i=0; i<P.size();i++)
{
cout<<P[i]<<' ';
}
cout<<endl;
return 0;
}Источники:
1. StudFiles – файловый архив студентов [Электронный ресурс] studfiles.net/preview/4514583/page:2/.
2. Задачник по теории информации и кодированию [Текст] / В.П. Цымбал. – Изд. объед. «Вища школа», 1976. – 276 с.
3. Тенников, Ф.Е. Теоретические основы информационной техники / Ф.Е. Тенников. – М.: Энергия, 1971. – 424 с.
mapron
Вопросы к автору:
1) Какая идея, посыл у статьи? Какую ценность для читателей она должна нести? Познакомить с корректирующими кодами? Предоставить готовую реализацию?
Ощущение, что я читаю чей-то доклад с 1-2 курса института.
2) Зачем приведены исходники? Код совершенно нечитаем, я лучше потрачу время и напишу сам, на основе описания/формул, чем буду использовать это, либо разбираться в логике его работы.
Это ваша первая программа на С++? Вы не программист, просто математик, верно?
phantom-code
Судя по коду — 100% математик. Эти ребята никогда не ставят пробелы и дают переменным максимально короткие имена.
lFeater Автор
Вы весьма проницательны. Опыта программирования у меня немного, и целью данной статьи действительно является познакомить читателей с корректирующими кодами, потому что когда-то мне это было необходимо и я не нашёл достаточно развёрнутого ответа на свой вопрос. И публикация опять же ориентирована на студентов, как вы уже сказали 1-го и 2-го курсов института. Исходники здесь лишь за тем, чтобы такие же валенки в программировании, как я, хотя бы посмотрели на реализацию работы с ЛГК, и просто скопировали его себе и посмотрели, как оно работает.
mapron
Хорошо, без всякой едкости, спасибо за ответы.